数据结构试卷及答案

38. 入栈操作和入队列操作在链式存储结构上实现时不需要考虑栈溢出的情况。(/ ) 39. 顺序表查找指的是在顺序存储结构上进行查找。（- ） 40. 堆是完全二叉树，完全二叉树不一定是堆。（ / ） 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．对

填空题

1. 了能有效地应用HASH查找技术，必须解决的两个问题是【构造一个好的HASH函数】和【确定解决冲突的方法】。

2. 序段的功能实现数据x进栈，要求在下划线处填上正确的语句。

typedef struct {

int s[100]; int top; } sqstack;

void push(sqstack &stack,int x) {

if (stack.top==m-1)

printf(“overflow”); else {

【stack.top++】;

【stack.s[stack.top]=x】; }

}

3. 中序遍历二叉排序树所得到的序列是【有序】序列（填有序或无序）。

4. 快速排序的最坏时间复杂度为【O(n2)】，平均时间复杂度为【O(nlog2n)】。

5. 设某棵二叉树中度数为0的结点数为N0，度数为1的结点数为N1，则该二叉树中度数为2的结点数为【N0-1】；若采用二叉链表作为该二叉树的存储结构，则该二叉树中共有【2N0+N1】个空指针域。 6. 设某无向图中顶点数和边数分别为n和e，所有顶点的度数之和为d，则e=【 d/2】。

7. 设一组初始记录关键字序列为(55，63，44，38，75，80，31，56)，则利用筛选法建立的初始堆为【(31，38，54，56，75，80，55，63)】。

8． 已知一有向图的邻接表存储结构如下：从顶点1出发，DFS遍历的输出序列是【(1，3，4，5，2)】，BFS遍历的输出序列是【(1，3，2，4，5)】。

9. 通常从四个方面评价算法的质量：【正确性】、【易读性】、【强壮性】和【高效率】。

10. 一个算法的时间复杂度为(n3+n2log2n+14n)/n2，其数量级表示为【O(n)】。 11. 假定一棵树的广义表表示为A（C，D（E，F，G），H（I，J）），则树中所含的结点数为【9】个，树的深度为【3】，树的度为【3】。

12. 后缀算式9 2 3 +- 10 2 / -的值为【-1】。中缀算式（3+4X）-2Y/3对应的后缀算式为【3 4 X * + 2 Y * 3 / -】。

13. 若用链表存储一棵二叉树时，每个结点除数据域外，还有指向左孩子和右孩子的两个指针。在这种存储结构中，n个结点的二叉树共有[2n]个指针域，其中有[n-1]个指针域是存放了地址，有[n+1]个指针是空指针。

1. 构造一个好的HASH函数，确定解决冲突的方法 2. stack.top++，stack.s[stack.top]=x 3. 有序

4. O(n2)，O(nlog2n) 5. N0-1，2N0+N1 6. d/2

7. (31，38，54，56，75，80，55，63) 8. (1，3，4，5，2)，(1，3，2，4，5) 1. 正确性 易读性 强壮性 高效率 2. O(n)

3. 9 3 3

4. -1 3 4 X * + 2 Y * 3 / - 5. 2n n-1 n+1

1. 数据的物理结构主要包括[顺序存储结构]和[链式存储结构]两种情况。

2. 设一棵完全二叉树中有500个结点，则该二叉树的深度为[9]；若用二叉链表作为该完全二叉树的存储结构，则共有[501]个空指针域。

3. 设输入序列为1、2、3，则经过栈的作用后可以得到[5]种不同的输出序列。

4. 设有向图G用邻接矩阵A[n][n]作为存储结构，则该邻接矩阵中第i行上所有元素之和等于顶点i的[出度]，第i列上所有元素之和等于顶点i的[入度]。

5. 设哈夫曼树中共有n个结点，则该哈夫曼树中有[0]个度数为1的结点。

6. 设有向图G中有n个顶点e条有向边，所有的顶点入度数之和为d，则e和d的关系为[e=d]。 7. [中序]遍历二叉排序树中的结点可以得到一个递增的关键字序列（填先序、中序或后序）。 8. 设查找表中有100个元素，如果用二分法查找方法查找数据元素X，则最多需要比较[7]次就可以断定数据元素X是否在查找表中(第8小题分析：二分查找的过程可以用一棵二叉树来描述，该二叉树称为二叉判定树。在有序表上进行二分查找时的查找长度不超过二叉判定树的高度1+log2n)。

9. 不论是顺序存储结构的栈还是链式存储结构的栈，其入栈和出栈操作的时间复杂度均为[O(1)]。 10. 设有n个结点的完全二叉树，如果按照从自上到下、从左到右从1开始顺序编号，则第i个结点的双亲结点编号为[i/2]，右孩子结点的编号为[2i+1]。 11. 设一组初始记录关键字为(72，73，71，23，94，16，5)，则以记录关键字72为基准的一趟快速排序结果为[(5，16，71，23，72，94，73)]。

12. 设有向图G中有向边的集合E={<1，2>，<2，3>，<1，4>，<4，2>，<4，3>}，则该图的一种拓扑序列为[(1，4，3，2)]。

13. 下列算法实现在顺序散列表中查找值为x的关键字，请在下划线处填上正确的语句。

struct record {

int key;

int others;

};

int hashsqsearch(struct record hashtable[ ],int k) {

int i,j;

j=i=k % p;

while (hashtable[j].key!=k&&hashtable[j].flag!=0) {

j=( [j+1]) %m; if (i==j)

return(-1);

}

if ([hashtable[j].key==k])

return(j); else

return(-1);

}

14. 下列算法实现在二叉排序树上查找关键值k，请在下划线处填上正确的语句。 typedef struct node {

int key;

struct node *lchild; struct node *rchild; }bitree;

bitree *bstsearch(bitree *t, int k) {

if (t==0 )

return(0); else

while (t!=0)

if (t->key==k)

[return(t)]; else if (t->key>k)

t=t->lchild; else

[t=t->rchild];

}

1. 顺序存储结构、链式存储结构 2. 9，501 3. 5

4. 出度，入度 5. 0 6. e=d