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

2022年泰山学院计算机科学与技术专业《数据结构与算法》科目期末

试卷A（有答案）

一、选择题

1、哈希文件使用哈希函数将记录的关键字值计算转化为记录的存放地址，因为哈希函数
是一对一的关系，则选择好的（）方法是哈希文件的关键。

A.哈希函数

B.除余法中的质数

C.冲突处理

D.哈希函数和冲突处理

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

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

3、若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，
则利用（）存储方式最节省时间。

A.顺序表B.双链表C.带头结点的双循环链表D.单循环链表

4、已知有向图G=(V，E)，其中V={V1，V2，V3，V4，V5，V6，V7}，E=｛<V1，V2>，
<V1，V3>，<V1，V4>，<V2，V5>，<V3，V5>，<V3，V6>，<V4，V6>，<V5，V7>，
<V6，V7>｝，G的拓扑序列是（）。

A.V1，V3，V4，V6，V2，V5，V7B.V1，V3，V2，V6，V4，V5，V7

C.V1，V3，V5，V2，V6，V7D.V1，V2，V5，V3，V4，V6，V7

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

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

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

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

D.某些关键活动若提前完成，那么整个工程将会提前完成
6、已知字符串S为“abaabaabacacaabaabcc”，模式串t为“abaabc”，采用KMP算法进行
匹配，第一次出现“失配”（s!＝t）时，i＝j＝5，则下次开始匹配时，i和j的值分别
（）。

A．i＝1，j＝0B．i＝5，j＝0C．i＝5，j＝2D．i＝6，j＝2

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

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

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

8、一个具有1025个结点的二叉树的高h为（）。

A.11B.10C.11至1025之间D.10至1024之间

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

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

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

C.其中只有一个叶结点

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

10、在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A，并已知A
的左孩子的平衡因子为0，右孩子的平衡因子为l，则应作（）型调整以使其平衡

A.LLB.LRC.RLD.RR

二、填空题

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

12、顺序查找n个元素的顺序表，若查找成功，则比较关键字的次数最多为______次；当
使用监视哨时，若查找失败，则比较关键字的次数为______。

13、对于一个具有n个结点的单链表，在已知的结点半p后插入一个新结点的时间复杂
度为______，在给定值为x的结点后插入一个新结点的时间复杂度为______。

14、在双向循环链表中，向p所指的结点之后插入指针f所指的结点，其操作是______、
______、______、______。

15、索引顺序文件既可以顺序存取，也可以______存取。
16、设数组A[0..8，1..10]，数组中任一元素A[i，j]均占内存48个二进制位，从首地址
2000开始连续存放在主内存里，主内存字长为16位，那么

（1）存放该数组至少需要的单元数是______。

（2）存放数组的第8列的所有元素至少需要的单元数______。

（3）数组按列存储时，元素A[5，8]的起始地址是______。

17、在顺序存储的二叉树中，编号为i和j的两个结点处在同一层的条件是______。

18、设T和P是两个给定的串，在T中寻找等于P的子串的过程称为______，又称P为
______。

三、判断题

19、倒排序文件的优点是维护简单。（）

20、直接访问文件也能顺序访问，只是一般效率不高。（）

21、队列和栈都是运算受限的线性表，只允许在表的两端进行运算。（）

22、循环队列也存在空间溢出问题。（）

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

24、深度为k的二叉树中结点总数小于等于2k-1。（）

25、为了很方便地插入和删除数据，可以使用双向链表存放数据。

（）

26、外部排序是把外存文件调入内存，可利用内部排序的方法进行排序，因此排序所花的
时间取决于内部排序的时间。（）

27、对两棵具有相同关键字集合的而形状不同的二叉排序树，按中序遍历它们