2019年秋学期 数据结构 期末测试题

院 系 级 班

姓名 学号 题号 一 二 三 四 总分 得分 得分 评卷人

一、单选题（每题 2 分，共30分）

1. 对一个算法的评价，不包括．．．的内容是__。 A．健壮性和可读性 B．正确性 C．并行性 D．时空复杂度

2. 对线性表，在下列选项中应当采用链表表示的是__。 A.经常需要随机地存取元素 B.经常需要进行插入和删除操作

C.表中元素需要占据一片连续的存储空间 D.表中元素的个数不变

3. 在带有头结点的双向链表H中，要向表头插入一个由指针p指向的结点，则执行__。

A. p->next=H->next; H->next=p; p->prior=H; H->next->prior=p; B. p->next=H->next; H->next=p; p->prior=H; p->next->prior=p; C. p->next=H; H->prior=p; p=H; D. H=p; p->next=H; H->prior=p; p=H; 4. 栈和队列的共同特点是__。

A.只允许在端点处插入和删除元素 B.都是先进后出 C.都是先进先出 D.没有共同点

5. 一个栈的输入序列为1 2 3 4，则下列序列中不可能．．．是栈的输出序列的是__。 A. 2 3 4 1 B. 3 2 1 4 C. 1 2 3 4

D. 3 4 1 2

第1页 (共6页)

6. 关于有关串的描述中，下列正确的是__。

A．串是一种特殊的线性表 B．空串就是空白串

C．串中元素只能是字母 D．串的长度必须大于零 7. 设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每个元素占一个空间， A[3][3](10)存放在的位置是__。 （脚注(10)表示用10进制表示。） A．688 B．678 C．692 D．696 8. 二叉树的第k层的结点数最多为__。 A．2k-1 B.2K+1 C.2K-1 D. 2k-1

9. 在一棵度为3的树中,度为3的结点个数为2,度为2 的结点个数为1, 则度为0的结点个数为__。 A．4 B．5 C．6 D．7 10. 设二叉树的中序遍历序列为BDAEC，后序遍历序列为DBECA,则该二叉树的先序序列为__。

A．ABCDE B．ABDCE C．ACEBD D．ACEBD 11. 设有7个结点的无向图，确保该图是一个连通图至少应含有的边条数为( ) A．6 B．7 C．8 D．9 12. AOV网是一种__。 A．有向图 B．无向图 C．无向无环图 D．有向无环图 13. 若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二分查找，则查找A[3]的比较序列的下标依次为__。

A. 1，2，3 B. 9，4，2，3 C. 9，5，3 D. 9，5，2，3 14. 对于线性表(7,34,55,25,64,46,20,10）进行散列存储时，若选用H(K)=K %9作为散列函数，则散列地址为1的元素个数是__。 A．1 B．2 C．3 D．4 15. 用某种排序方法对关键字序列(25,84,21,47,15,27,68,35,20)进行排序时，序列的变化情况如下：

20，15，21，25，47，27，68，35，84 15，20，21，25，35，27，47，68，84 15，20，21，25，27，35，47，68，84 则所采用的排序方法是__。

A. 选择排序 B. 希尔排序 C. 快速排序 D. 归并排序

第2页 (共6页)

二、填空题（每题1分，共`10分）

16. 一个算法的时间复杂度为(n3+n2log2n+14n)，

其数量级表示为_______________。

17. 中缀表达式（3+4*x）-2*y/3对应的后缀表达

式为_____________________________。

18. 假定一棵树用广义表表示为A(C,D(E,F,G),H(I,J))，则树的深度为

___________，树的度为_________。

19. 一棵结点数为N的二叉树，其所有结点的度的总和是________。

得分 评卷人 20. 对于一个具有n个顶点和e条弧的有向图，在其对应的正邻接表中，

所含弧结点有_______个。

21. 在一个具有n个顶点的无向完全图中，包含有________条边。 22. 假定一个线性表为(12,23,74,55,61,40)，若按Key % 4条件进行划分，

使得同一余数的元素成为一个子表，则得到的四个子表分别为 ______________、____________、___________和______________。 23. 向一棵B-树插入元素的过程中，若最终引起树根结点的分裂，则新

树比原树的高度___________。 24. 在堆排序的过程中，对任一分支结点进行筛选运算的时间复杂度为

________。

25. 在希尔排序、快速排序、堆排序、归并排序中，_________排序是

稳定的。

得分 评卷人 三、简答题（6小题，共32分）

26. (4分)已知一个65稀疏矩阵如下所示，

试写出：(1)写出它的三元组线性表；

(2)给出三元组线性表的顺序存储表示。

00001 00000 01000 00002 50000 00700

第3页 (共6页)

27. (5分)设给定一个权值集合W=(5，6，9，10，13，14，17，26)，要求：(1)根据给定的权值集合构造一棵哈夫曼树（左子树权值不大于右子树权）; (2)计算哈夫曼树的带权路径长度WPL。

28. (5分)请画出下图的邻接矩阵和邻接表。

29. (6分)已知一个图的顶点集V和边集E分别为：V={1,2,3,4,5,6,7}; E={(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15,

(3,5)12,(3,6)9,(4,6)4,(4,7)20,(5,6)18,(6,7)25}; (1)画出该图; (说明：(i,j)D表示边(i,j)的权值为D)

(2)用Prim算法得到其最小生成树,并在最小生成树中依次得到的各条边。

第4页 (共6页)

30. (6分)已知一个图的顶点集V和边集E分别为：

V={1,2,3,4,5,6,7}; E={<2,1>,<3,2>,<3,6>,<4,3>,<4,5>,<4,6>,<5,1>, <5,7>,<6,1>,<6,2>,<6,5>}; 若存储它采用邻接表，并且每个顶点邻接表中的边结点都是按照终点序号从小到大的次序链接的，按教材中介绍的拓朴排序算法进行排序，试画出该图，并给出得到的拓朴排序的序列。

31. (6分)画出向小顶堆中加入数据4, 2, 5, 8, 3时，每加入一个数据后堆

的变化。

第5页 (共6页)

四、算法题（每题9分，共18分）

32.统计出带头结点单向链表H中结点的值等于给

定值x的结点数。

int CountX(SLinkList H,ElemType x)

33. 设计在链式存储结构上交换二叉树中所有结点左右子树的算法。

得分 评卷人 typedef struct node { ElemType data;

struct node *lchild, *rchild; } BiTNode,*BiTree;

第6页 (共6页)