2022年郑州科技学院计算机科学与技术专业《数据结构与算法》科目期末试.pdfVIP

2022年郑州科技学院计算机科学与技术专业《数据结构与算法》科目

期末试卷A（有答案）

一、选择题

1、用数组r存储静态链表，结点的next域指向后继，工作指针j指向链中结点，使j沿

链移动的操作为（）。

A.j=r[j].nextB.j=j+lC.j=j-nextD.j=r[j]-next

2、下列排序算法中，占用辅助空间最多的是（）。

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

3、以下与数据的存储结构无关的术语是（）。

A.循环队列链B.表哈希表C.栈D.

4、下列关于AOE网的叙述中，不正确的是（）。

A.关键活动不按期完成就会影响整个工程的完成时间

B.任何一个关键活动提前完成，那么整个工程将会提前完成

C.所有的关键活动提前完成，那么整个工程将会提前完成

D.某些关键活动若提前完成，那么整个工程将会提前完成

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

A.（rear+1）MODn=front

B.rear=front

C.rear+1=front

D.（rear-1）MODn=front

6、已知字符串S为“abaabaabacacaabaabcc，”模式串t为“abaabc，”采用KMP算法进行

匹配，第一次出现失配“”（s!＝t）时，i＝j＝5，则下次开始匹配时，i和j的值分别

（）。

A．i＝1，j＝0B．i＝5，j＝0．Ci＝5，j＝2．Di＝6，j＝2

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

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

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

8、设X是树T中的一个非根结点，B是T所对应的二叉树。在B中，X是其双亲的右孩

子，下列结论正确的是（）。

A.在树T中，X是其双亲的第一个孩子

B.在树T中，X一定无右兄弟

C.在树T中，X一定是叶结点

D.在树T中，X一定有左兄弟

9、在下述结论中，正确的有（）。

①只有一个结点的二叉树的度为0。

②二叉树的度为2。

③二叉树的左右子树可任意交换。④深度为K的完全二叉树的结点个数小于或等于深度相

同的满二叉树。

A.①②③

B.⑦③④

C.②④

D.①④

10、对关键码序列28，16，32，12，60，2，5，72快速排序，从小到大一次划分结果

为（）。

A.（2，5，12，16）26（60，32，72）

B.（5，16，2，12）28（60，32，72）

C.（2，16，12，5）28（60，32，72）

D.（5，16，2，12）28（32，60，72）

二、填空题

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

12、若用n表示图中顶点数目，则有______条边的无向图成为完全图。

13、数据结构是研讨数据的______和______以及它们之间的相互关系，并对与这种结构定义

相应的______，设计出相应的______。

14、建立索引文件的目的是______。

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

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

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

16、阅读下列程序说明和程序，填充程序中的______。

【程序说明】本程序完成将二叉树中左、右孩子交换的操作。交换的结果如下所示（编者

略）。

本程序采用非递归的方法，设立一个堆栈stack存放还没有转换过的结点，它的栈顶指针

为tp。交换左、右子树的算法为：

（1）把根结点放入堆栈。

（2）当堆栈不空时，取出栈顶元素，交换它的左、右子树，并把它的左、右子树分别入

栈。

（3）重复（2）直到堆栈为空时为止。

1