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

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

试卷A（有答案）

一、选择题

1、哈希文件使用哈希函数将记录的关键字值计算转化为记录的存放地址，因为哈希函数

是一对一的关系，则选择好的（）方法是哈希文件的关键。

A.哈希函数

B.除余法中的质数

C.冲突处理

D.哈希函数和冲突处理

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

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

3、以下数据结构中，（）是非线性数据结构。

A.树字符串B.队C.栈D.

4、在用邻接表表示图时，拓扑排序算法时间复杂度为（）。

A.O(n)B.O(n+e)C.O(n*n)D.O(n*n*n)

5、用不带头结点的单链表存储队列，其队头指针指向队头结点，队尾指针指向队尾结点，

则在进行出队操作时（）。

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＝0．Ci＝5，j＝2．Di＝6，j＝2

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

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

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

8、一棵哈夫曼树共有215个结点，对其进行哈夫曼编码，共能得到（）个不同的码

字。

A.107B.108C.214D.215

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

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

②二叉树的度为2。

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

同的满二叉树。

A.①②③

B.⑦③④

C.②④

D.①④

10、下面给出的四种排序方法中，排序过程中的比较次数与排序方法无关的是（）。

A.选择排序法B.插入排序法C.快速排序法D.堆排序法

二、填空题

11、设m、n均为自然数，m可表示为一些不超过n的自然数之和，f（m，n）为这种表

示方式的数目。例f（5，3）=5，有5种表示方式：3+2，3+1+1，2+2+1，2+1+1+1，

1+1+1+1+1。

①以下是该函数的程序段，请将未完成的部分填入，使之完整。

②执行程序，f（6，4）=______。

12、对单链表中元素按插入方法排序的C语言描述算法如下，其中L为链表头结点指针。

请填充算法中标出的空白处，完成其功能。

13、以下是用类C语言写出的算法，该算法将以二叉链表存储的二叉树中的叶结点按从

左到右的顺序链成一个带头结点的双向循环链表，链接时，结点的Lchild域作为前链域，

指向结点的直接前驱，结点的Rchild域作为后链域，指向结点的直接后继。算法中，使

用一个顺序栈stack，栈顶指针为top，p，t为辅助指针，head为双向循环链表的头指针。

试填充算法中的空格，使算法完整。

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

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

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

15、线性表L=（a1，a2，…，an）用数组表示，假定删除表中任一元素的概率相同，则

删除一个元素平均需要移动元素的个数是______。

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