2022年东北大学计算机科学与技术专业《数据结构与算法》科目期末试卷A(有答案).pdf

2022年东北大学计算机科学与技术专业《数据结构与算法》科目期末

试卷A（有答案）

一、选择题

1、已知广义表LS=（（a，b，c），（d，e，f）），用head和tail数取出LS中原子e

的运算是（）。

A.head（tail（LS））B.tail（head（LS））

C.head（tail（head（tail（LS））））D.head（tail（tail（head（LS））））

2、下列说法不正确的是（）。

A.图的遍历是从给定的源点出发每个顶点仅被访问一次

B.遍历的基本方法有两种：深度遍历和广度遍历

C.图的深度遍历不适用于有向图

D.图的深度遍历是一个递归过程

3、静态链表中指针表示的是（）。

A.下一元素的地址

B.内存储器的地址

C.下一元素在数组中的位置

D.左链或右链指向的元素的地址

4、最大容量为n的循环队列，队尾指针是rear，队头：front，则队空的条件是（）。

A.（rear+1）MODn=front

B.rear=front

C.rear+1=front

D.（rear-1）MODn=front

5、循环队列A[0..m-1]存放其元素值，用front和rear分别表示队头和队尾，则当前队列

中的元素数是（）。

A.（rear-front+m）%m

B.rear-front+1

C.rear-front-1

D.rear-front

6、下列关于无向连通图特性的叙述中，正确的是（）。

Ⅰ．所有的顶点的度之和为偶数Ⅱ．边数大于顶点个数减1Ⅲ．至少有一个顶点的度为1

A．只有ⅠB．只有ⅡC．Ⅰ和ⅡD．Ⅰ和Ⅲ

7、下列叙述中，不符合m阶B树定义要求的是（）。

A．根结点最多有m棵子树B．所有叶结点都在同一层上

C．各结点内关键字均升序或降序排列D．叶结点之间通过指针链接

8、一棵非空的二叉树的前序序列和后序序列正好相反，则该二叉树一定满足（）。

A.其中任意一个结点均无左孩子

B.其中任意一个结点均无右孩子

C.其中只有一个叶结点

D.其中度为2的结点最多为一个

9、下述二叉树中，哪一种满足性质：从任一结点出发到根的路径上所经过的结点序列按

其关键字有序（）。

A.二叉排序树B.哈夫曼树C.AVL树D.堆

10、对序列{15，9，7，8，20，-1，4}用希尔排序方法排序，经一趟后序列变为{15，-1，

4，8，20，9，7}则该次采用的增量是（）。

A.1B.4C.3D.2

二、填空题

11、阅读下列程序，指出其功能，并写出空格处应填上的语句。

12、无用单元是指______，例______

13、应用Prim算法求解连通网络的最小生成树问题。（1）针对如图所示的连通网络，

试按如下格式给出在构造最小生成树过程中顺序选出的各条边。

（2）下面是Prim算法的实现，中间有5个地方缺失，请阅读程序后将它们补上。

14、在一棵m阶B-树中，若在某结点中插入一个新关键字而引起该结点分裂，则此结点

中原有的关键字的个数是______；若在某结点中删除一个关键字而导致结点合并，则该

结点中原有的关键字的个数是______。

15、设T是一棵结点值为整数的二叉排序树，A是一个任意给定的整数。在下面的算法中，

free_tree（T）在对二叉排序树丁进行后序遍历时释放二又排序树T的所有结点；

delete_subtree（T，A），首先在二叉排序树T中查找值为A的结点，根据查找情况分别

进行如下处理：（1）若找不到值为A的结点，则返回根结点的地址（2）若找到值为A

的结点，则删除以此结点为根的子树，并释放此子树中的所有结点，若值为A的结点是查

找树的根结点，删除后变成空的二叉树，则返null