中国大学MOOC-陈越、何钦铭-数据结构-2019夏期末考试

冷不防 2024-04-17 06:26 66阅读 0赞

1-1对一棵平衡二叉树，所有非叶结点的平衡因子都是0，当且仅当该树是完全二叉树。(2分) F

1-2n!是O(n^n)的。 (2分) T

1-3若用平方探测法解决冲突，则插入新元素时，若散列表容量为质数，插入就一定可以成功。 F

1-4在任一有向图中，所有顶点的入度之和等于所有顶点的出度之和。 (2分) T

1-5对N个不同的数据采用冒泡排序进行从大到小的排序，当元素基本有序时交换元素次数肯定最多。 (2分) F

2-1 A

设一个栈的输入序列是1、2、3、4、5，则下列序列中，是栈的合法输出序列的是？ (4分)

1.  3 2 1 5 4
2.  5 1 2 3 4
3.  4 5 1 3 2
4.  4 3 1 2 5

2-2 B

已知一棵二叉树的树形如下图所示，其后序序列为\{ `e`, `a`, `c`, `b`, `d`, `g`, `f` \}。树中与结点`a`同层的结点是：(2分)

![format_png][]

1.  `c`
2.  `d`
3.  `f`
4.  `g`

2-3 D

给定有权无向图的邻接矩阵如下，其最小生成树的总权重是： (4分)

![format_png 1][]

1.  10
2.  11
3.  12
4.  14

2-4 B

已知一个图的邻接矩阵如下，则从顶点V1出发按深度优先搜索法进行遍历，可能得到的一种顶点序列为： (2分)

![format_png 2][]

1.  V1,V2,V3,V4,V5,V6
2.  V1,V2,V4,V5,V6,V3
3.  V1,V3,V5,V2,V4,V6
4.  V1,V3,V5,V6,V4,V2

2-5 D

设散列表的地址区间为\[0,16\]，散列函数为H(Key)=Key%17。采用线性探测法处理冲突，并将关键字序列\{ 26，25，72，38，8，18，59 \}依次存储到散列表中。元素59存放在散列表中的地址是： (4分)

1.  8
2.  9
3.  10
4.  11

2-6 C

在拓扑排序算法中用堆栈和用队列产生的结果会不同吗？(2分)

1.  是的肯定不同
2.  肯定是相同的
3.  有可能会不同
4.  以上全不对

2-7 C

哈夫曼树是n个带权叶子结点构成的所有二叉树中（）最小的二叉树。 (2分)

1.  权值
2.  高度
3.  带权路径长度
4.  度

2-8 C

对给定序列\{ 110，119，7，911，114，120，122 \}采用次位优先（LSD）的基数排序，则两趟收集后的结果为： (2分)

1.  7, 110, 119, 114, 911, 120, 122
2.  7, 110, 119, 114, 911, 122, 120
3.  7, 110, 911, 114, 119, 120, 122
4.  110, 120, 911, 122, 114, 7, 119

2-9 B

在并查集问题中，已知集合元素0~8所以对应的父结点编号值分别是\{ 1, -4, 1, 1, -3, 4, 4, 8, -2 \}（注：−n表示树根且对应集合大小为n），那么将元素6和8所在的集合合并（要求必须将小集合并到大集合）后，该集合对应的树根和父结点编号值分别是多少？ (4分)

1.  1和-6
2.  4和-5
3.  8和-5
4.  8和-6

2-10 B

在一个有权无向图中，如果顶点b到顶点a的最短路径长度是10，顶点c与顶点b之间存在一条长度为3的边。那么下列说法中有几句是正确的？ (4分)

1.  c与a的最短路径长度就是13
2.  c与a的最短路径长度就是7
3.  c与a的最短路径长度不超过13
4.  c与a的最短路径不小于7

2-11 A

已知一个图的邻接矩阵如下，则从顶点V1出发按广度优先搜索法进行遍历，可能得到的一种顶点序列为： (2分)

![format_png 3][]

1.  V1,V2,V3,V5,V4,V6
2.  V1,V2,V4,V5,V6,V3
3.  V1,V3,V5,V2,V4,V6
4.  V1,V3,V5,V6,V4,V2

2-12 D

如果循环队列用大小为`m`的数组表示，队头位置为`front`、队列元素个数为`size`，那么队尾元素位置`rear`为： (2分)

1.  `front+size`
2.  `front+size-1`
3.  `(front+size)%m`
4.  `(front+size-1)%m`

2-13 B

对于序列\{ 49，38，65，97，76，13，27，50 \}，按由小到大进行排序，下面哪一个是初始步长为4的希尔排序法第一趟的结果？ (4分)

1.  13,27,38,49,50,65,76,97
2.  49,13,27,50,76,38,65,97
3.  49,76,65,13,27,50,97,38
4.  97,76,65,50,49,38,27,13

2-14 C

将 \{28, 15, 42, 18, 22, 5, 40\} 逐个按顺序插入到初始为空的最小堆（小根堆）中。则该树的前序遍历结果为：(4分)

1.  5, 18, 15, 28, 22, 42, 40
2.  5, 15, 18, 22, 28, 42, 40
3.  5, 18, 28, 22, 15, 42, 40
4.  5, 15, 28, 18, 22, 42, 40

2-15 D

设栈S和队列Q的初始状态均为空，元素\{1, 2, 3, 4, 5, 6, 7\}依次进入栈S。若每个元素出栈后立即进入队列Q，且7个元素出队的顺序是\{2, 5, 6, 4, 7, 3, 1\}，则栈S的容量至少是： (2分)

1.  1
2.  2
3.  3
4.  4

2-16 C

要判断一个整数N（>10）是否素数，我们需要检查3到√N之间是否存在奇数可以整除N。则这个算法的时间复杂度是：(2分)

1.  O(N/2)
2.  O(√NlogN)
3.  O(√N)
4.  O(0.5logN)

2-17 C

若数据元素序列\{ 11，12，13，7，8，9，23，4，5 \}是采用下列排序方法之一得到的第二趟排序后的结果，则该排序算法只能是： (2分)

1.  冒泡排序
2.  选择排序
3.  插入排序
4.  归并排序

2-18 B

数据结构中Dijkstra算法用来解决哪个问题？ (2分)

1.  关键路径
2.  最短路径
3.  拓扑排序
4.  字符串匹配

2-19 A

给定输入序列 \{4371, 1323, 6173, 4199, 4344, 9679, 1989\} 以及散列函数 h(X)=X%10。如果用大小为10的散列表，并且用分离链接法解决冲突，则输入各项经散列后在表中的下标为：（-1表示相应的插入无法成功）(4分)

1.  1, 3, 3, 9, 4, 9, 9
2.  1, 3, 4, 9, 7, 5, -1
3.  1, 3, 4, 9, 5, 0, 8
4.  1, 3, 4, 9, 5, 0, 2

2-20 D

将1~6这6个键值插到一棵初始为空的二叉搜索树中。如果插入完成后，搜索树结构如图所示，问：可能的插入序列是什么？ (2分)

![format_png 4][]

1.  1 2 3 4 5 6
2.  4 1 2 3 5 6
3.  4 1 3 2 6 5
4.  4 1 3 2 5 6

2-21 A

将 \{ 10, 12, 1, 14, 6, 5, 8, 15, 3, 9, 7 \} 逐个按顺序插入到初始为空的最小堆中，然后连续执行两次删除最小元素操作（DeleteMin），再插入4，16，此后堆顶的元素是什么？ (4分)

1.  4
2.  5
3.  7
4.  9

2-22 A

将 9, 8, 7, 2, 3, 5, 6, 4 顺序插入一棵初始为空的AVL树。下列句子中哪句是错的？ (4分)

1.  5 是根结点
2.  2 和 5 是兄弟
3.  有2个结点的平衡因子为-1
4.  最后得到的AVL树的高度是3

5-1 不会。。这道题0分

下列代码的功能是利用散列函数`hash`将一个元素插入到散列表`ht[]`中。其中`list`类型的结点包含`element`类型的项`item`、以及一个`next`指针。如果插入成功，则函数返回1，否则返回0。

int insert( struct element item, list_pointer ht[] )
    {
       int ret, hash_value;
       list_pointer ptr, trail, lead;
    
       ret = 1;
       hash_value = hash(item.key);
       trail = NULL; lead = ht[hash_value];
       for ( ; lead; trail = lead, lead = lead->next) {
          if (!strcmp(lead->item.key, item.key)) {
             printf("The key is in the table\n");
             ret = 0;
          }
       }
       if (ret) {
          ptr = (list_pointer)malloc(sizeof(struct list));
          (3分);
          ptr->next = NULL;
          if (trail)
             (3分);
          else
             (3分);
       }
       return ret;
    }

5-2

本函数的功能是从有`N`个元素的线性表`A`中查找第`K`大的元素。其中函数`BuildMinHeap(H, K)`是将元素`H[1]` ... `H[K]`调整为一个最小堆。请完成下列填空。

ElementType FindKthLargest ( int A[], int N, int K )
    {   /* it is assumed that K<=N */
        ElementType *H;
        int i, next, child;
    
        H = (ElementType *)malloc((K+1)*sizeof(ElementType));
        for ( i=1; i<=K; i++ ) H[i] = A[i-1];
        BuildMinHeap(H, K);
    
        for ( next=K; next<N; next++ ) {
            H[0] = A[next];
            if ( H[0] > H[1] ) {
                for ( i=1; i*2<=K; i=child ) {
                    child = i*2;
                    if ( child!=K && H[child+1]<H[child] (4分) ) child++;
                    if ( H[child]<H[0] (5分) )
                        H[i] = H[child];
                    else break;
                }
                H[i] = H[0];
            }
        }
        return H[1];
    }

7-1 还原二叉树 (8 分)

给定一棵二叉树的先序遍历序列和中序遍历序列，要求计算该二叉树的高度。

### 输入格式: ###

输入首先给出正整数N（≤50），为树中结点总数。下面两行先后给出先序和中序遍历序列，均是长度为N的不包含重复英文字母（区别大小写）的字符串。

### 输出格式: ###

输出为一个整数，即该二叉树的高度。

### 输入样例: ###

9
    ABDFGHIEC
    FDHGIBEAC

### 输出样例: ###

#include<stdio.h>
    #include<string.h>
    #include<math.h>
    #include<iostream>
    #include<string>
    #include<sstream>
    #include<algorithm>
    #include<map>
    #include<set>
    #include<queue>
    #include<stack>
    #include<vector>
    using namespace std;
    #define inf 0x3f3f3f3f
    #define LL long long
    int pre[505],in[505],l[505],r[505];
    int maxx;
    int dfs(int l1,int r1,int l2,int r2)
    {
    	if(l1>r1)return -1;
    	int root=pre[l1];
    	int p=l2;
    	while(root!=in[p])p++;
    	int cnt=p-l2;
    	l[root]=dfs(l1+1,l1+cnt,l2,p-1);
    	r[root]=dfs(l1+cnt+1,r1,p+1,r2);
    	return root;
    }
    void sc(int x,int s)
    {
    	if(l[x]==-1&&r[x]==-1)
    	{
    		if(s>maxx)
    		maxx=s;
    		return;
    	}
    	if(l[x]!=-1)sc(l[x],s+1);
    	if(r[x]!=-1)sc(r[x],s+1);
    }
    int main()
    {
    	int n,i,j;
    	char p[55],inn[55];
    	memset(l,-1,sizeof l);
    	memset(r,-1,sizeof r);
    	scanf("%d",&n);
    	scanf("%s",p);
    	scanf("%s",inn);
    	for(i=0;i<n;i++)
    	{
    		pre[i]=p[i]-'A';
    		in[i]=inn[i]-'A';
    	}
    	maxx=-1;
    	dfs(0,n-1,0,n-1);
    	sc(pre[0],1);
    	printf("%d\n",maxx);
    }

[format_png]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9pbWFnZXMucHRhdXNlcmNvbnRlbnQuY29tLzI4MQ?x-oss-process=image/format,png
[format_png 1]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9pbWFnZXMucHRhdXNlcmNvbnRlbnQuY29tLzI1?x-oss-process=image/format,png
[format_png 2]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9pbWFnZXMucHRhdXNlcmNvbnRlbnQuY29tLzE5?x-oss-process=image/format,png
[format_png 3]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9pbWFnZXMucHRhdXNlcmNvbnRlbnQuY29tLzI0?x-oss-process=image/format,png
[format_png 4]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9pbWFnZXMucHRhdXNlcmNvbnRlbnQuY29tLzIwMQ?x-oss-process=image/format,png