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

2022年首都师范大学计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）

一、选择题

1、将线性表的数据元素进行扩充，允许带结构的线性表是（）。

A.串B.树C.广义表D.栈

2、将两个各有N个元素的有序表归并成一个有序表，其最少的比较次数是（）。

A.NB.2N-1C.2ND.N-1

3、连续存储设计时，存储单元的地址（）。

A.一定连续B.一定不连续C.不一定连续D.部分连续，部分不连续

4、向一个栈顶指针为h的带头结点的链栈中插入指针s所指的结点时，应执行（）。

A.h-next=s

B.s-next=h

C.s-next=h;h-next=s

D.s-next=h-next;h-next=s

5、已知串S=aaab，其next数组值为（）。

A.0123B.1123C.1231D.1211

6、已知关键字序列5，8，12，19，28，20，15，22是小根堆（最小堆），插入关键字3，调整后的小根堆是（）。

A．3，5，12，8，28，20，15，22，19

B．3，5，12，19，20，15，22，8，28

C．3，8，12，5，20，15，22，28，19

D．3，12，5，8，28，20，15，22，19

7、若一棵二叉树的前序遍历序列为a，e，b，d，c，后序遍历序列为b，c，d，e，a，则根结点的孩子结点（）。

A．只有eB．有e、bC．有e、cD．无法确定

8、已知一棵二叉树的前序遍历结果为ABCDEF，中序遍历结果为CBAEDF，则后序遍历结果为（）。

A.CBEFDAB.FEDCBAC.CBEDFAD.不定

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

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

②二叉树的度为2。

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

A.①②③

B.⑦③④

C.②④

D.①④

10、在文件“局部有序”或文件长度较小的情况下，最佳内部排序的方法是（）。

A.直接插入排序B.起泡排序C.简单选择排序D.快速排序

二、填空题

11、如果按关键码值递增的顺序依次将关键码值插入到二叉排序树中，则对这样的二叉排序树检索时，平均比较次数为______。

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

13、VSAM（虚拟存储存取方法）文件的优点是：动态地______，不需要文件进行______，并能较快地______进行查找。

14、应用Prim算法求解连通网络的最小生成树问题。（1）针对如图所示的连通网络，试按如下格式给出在构造最小生成树过程中顺序选出的各条边。

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

15、以下是用类C语言写出的算法，该算法将以二叉链表存储的二叉树中的叶结点按从左到右的顺序链成一个带头结点的双向循环链表，链接时，结点的Lchild域作为前链域，指向结点的直接前驱，结点的Rchild域作为后链域，指向结点的直接后继。算法中，使用一个顺序栈stack，栈顶指针为top，p，t为辅助指针，head为双向循环链表的头指针。试填充算法中的空格，使算法完整。

16、一棵有n个结点的满二叉树有______个度为1的结点、有______个分支（非终端）结点和______个叶子，该满二叉树的深度为______。

17、下列程序是快速排序的非递归算法，请填写适当的语句，完成该功能。

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

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

本程序采用非递归的方法，设立一个堆栈stack存放还没有转换过的结点，它的栈顶指针为tp。交换左、右子树的算法为：

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

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

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

三、判断题

19、哈希表与哈希文件的唯一区别是哈希文件引入了“桶”的概念。（）

20、对磁带机而言，ISAM是一种方便的文件组织方法（）

21、数组不适合作为任何二叉树的存储结构。（）

22、设模式串的长度为m，目标串的长度为n，当n≈m且处理只匹配一次的模式时，朴素的匹配（即子串定位函数）算法所花的时间代价可能会更为节省。（）

23、树形结构中元素之间存在一对多的关系。（）

24、一个树形的叶结点，在前序遍历和后序遍历下，皆以相同的相对位置