数据结构实验教程-第一套

1．在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A，并已知A的左孩子的平衡因子为1，右孩子的平衡因子为0，则应作_型调整以使其平衡。
A.LL
B.LR
C.RL
D.RR
1
2
3
4
5

答案为a，错选了c。
平衡因子 = 左子树高度 - 右子树高度
错因:找到了最小不平衡子树为左孩子的左子树（LL）应做右单旋转，但这个操作的名称叫LL。

LL:右单旋转
RR:左单旋转
LR:左旋转再右旋转
RL:右旋转再左旋转

线性表中每个元素都有一个前驱和一个后继元素。
1

这个说法是不对的，第一个元素无前驱节点，最后一个元素无后继节点。

若从某顶点出发对无向图G进行深度优先搜索遍历,所得的遍历序列唯一，则可断定图中有两个顶点的度为1。
1

这个说法是正确的。（就算是环，也有两种序列，因为是无向图）

广义表A=(((a,b),(c,d),e))，取出A中的原子e的操作是_
1

在广义表中，head取出的是表中第一个元素，tail取出的是当前表的下一个元素。
因此答案为:head ( tail ( tail ( head(A) ) ) )

解答本题时，首先要清楚取表头和表尾运算 head 和 tail运算的含义: head(A)返回A表中的第一个元素;tail(A)则返回在A表中去掉第一个元素后所得到的表。
为取出元素e，首先要将e所在的元素（子表〉取出来，即执行head(A)，得到A的第一个元素((a,b).(c,d),e)，由于e是其中第三个元素，故要连续去掉其前面两个元素，即执行两次取表尾元素，然后再执行取表头运算，按由里到外的次序合成得到答案。
类似地，若要取出其中的原子b，其复合函数应是head(tail(head(head(A)))).

9．在有序表A[22]中，按二分查找方法进行查找，查找值为A[15]的元素依次比较的元素的下标是
1

第一次 mid = (0+21)/2 = 10
第二次
low = mid+1 = 11
mid = (11+21)/2 = 16
第三次
high = mid-1 = 15
mid = (15+11)/2 = 13
第四次
low = mid + 1 = 14
mid = (14+15)/2 = 14
第五次
low = mid + 1 = 15
mid = (15+15)/2 = 15

因此搜索下标应该为 10 16 13 14 15
关键在于更新时，若low更新因为low = mid - 1 若high更新应为high = mid+1，别把+1或者-1忘了

3．已知散列表的地址空间为0～13，散列函数为H(k)=k%13，用线性探查法处理冲突。
将下列元素依次插入到初值为空的散列表中，画出该表，并求出在等概率情况下，查找成功时的平均查找长度。
( 11,22,33,57,65,31,43,98,77,100,30,28)
1
2
3

注意要看清是如何解决冲突的，别想当然用拉链法去解决。最终答案为2.

2．设计算法按先序次序遍历先序线索二叉树。要求采用非递归形式，且不用栈。
1

BiTnode *NextNode(BiTnode *p){
    if(p->ltag == 0) return p->lchild;
    //如果有左孩子，后继是其左孩子
    else return p->rchild;
    //没有左孩子的话后继是右孩子或者后继线索
}

void PreTraverse(BiTnode *t){
    BiTnode *p = t;
    //第一个节点为t
    for(;p;p = NextNode(p))
        visit(p)
}
1
2
3
4
5
6
7
8
9
10
11
12
13

与之相对应的是中序线索二叉树的遍历，注意进行区分。

BiTnode *FirstNode(BiTnode *t){
    //找到中序的第一个节点
    while(p->tag == 0) p = p->lchild;
    return p;
    //最左下节点
}

BiTnode *NextNode(BiTnode *t){
    //找到中序后继节点
    if(t->rtag == 1) return t->rchild;
    //右孩子是线索，直接返回
    else return FirstNode(t->rchild);
    //返回右子树的第一个节点
}

void InTraverse(BiTnode *t){
    for(BiTnode *p = FirstNode(t);p;p = NextNode(p))
        visit(p);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

注意上述代码第一个函数中while(p->ltag == 0) p = p->lchild;这个条件可不可以替换为while(p->lchild) p = p->lchild;显然是不可以的，因为在后续调用中， p = p->lchild有可能为线索这个条件一定要注意。

void swap(int *a,int *b){
    int tmp;
    tmp = *a;
    *a = *b;
    *b = tmp;
}
void sort(int a[],int n){
    int low = 0,high = n-1;
    while(low<high){
        while(a[low]%3 == 0)low++;
        while(a[high]%3 != 0) high--;
        if(low<=high) swap(&a[low],&a[high]);
        else break;
    }
    high = n-1;low++;
    while(low<high){
        while(a[low]%3 == 1)low++;
        while(a[high]%3 != 1) high--;
        if(low<=high) swap(&a[low],&a[high]);
        else break;
    }
    high = n-1;low++;
    while(low<high){
        while(a[low]%3 == 2)low++;
        while(a[high]%3 != 2) high--;
        if(low<=high) swap(&a[low],&a[high]);
        else break;
    }
}
int main()
{
    int num[] = {1,3,5,7,9,2,4,6,8,10};
    for(int i=0;i<10;i++){
        printf("%4d",num[i]);
    }

    printf("\n");
    sort(num,10);
    for(int i=0;i<10;i++){
        printf("%4d",num[i]);
    }
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

别忘了在swap前加一个判断是否low

struct TreeNode {
     int val;
     struct TreeNode *left;
     struct TreeNode *right;
 };


struct TreeNode* Build(int *preorder,int p1,int p2,int *order,int o1,int o2){
    struct TreeNode *root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->val = preorder[p1];
    int mid;
    for(mid = o1;order[mid]!=root->val;mid++) ;
    int llen = mid - o1;
    int rlen = o2 - mid;
    if(llen){
        root->left = Build(preorder,p1+1,p1+llen,order,o1,o1+llen-1);
    }
    else
        root->left = NULL;
    if(rlen){
        root->right = Build(preorder,p2-rlen+1,p2,order,o2-rlen+1,o2);
    }
    else
        root->right = NULL;
    return root;
}
struct TreeNode* buildTree(int* preorder, int preorderSize, int* inorder, int inorderSize){
    struct TreeNode *root;
    root = Build(preorder,0,preorderSize-1,inorder,0,inorderSize-1);
    return root;
}

void traverse(struct TreeNode* t){
    if(!t) return;
    if(t->left)
        printf("( %d , %d )\n",t->val,t->left->val);
    traverse(t->left);
    traverse(t->right);

}
int main()
{
    int pre[] = {3,9,20,15,7};
    int in[] = {9,3,15,20,7};
    struct TreeNode* t = buildTree(pre,5,in,5);
    traverse(t);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48