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

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

试卷A（有答案）

一、选择题

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

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

2、无向图G=(V，E)，其中：V={a，b，c，d，e，f}，E={(a，b)，(a，e)，(a，c)，(b，

e)，(c，f)，(f，d)，(e，d)}，对该图进行深度优先遍历，得到的顶点序列正确的是

（）。

A.a，b，e，c，d，fB.a，c，f,e，b，d

C.a，e，b，c，f,dD.a，e，d，f，c，b

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

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

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

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

A.仅修改队头指针

B.仅修改队尾指针

C.队头、队尾指针都可能要修改

D.队头、队尾指针都要修改

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

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

6、排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一趟排序。下列排序

方法中，每一趟排序结束时都至少能够确定一个元素最终位置的方法是（）。

Ⅰ．简单选择排序Ⅱ．希尔排序Ⅲ．快速排序Ⅳ．堆排Ⅴ．二路归并排序

A．仅Ⅰ、Ⅲ、ⅣB．仅Ⅰ、Ⅱ、ⅢC．仅Ⅱ、Ⅲ、ⅣD．仅Ⅲ、Ⅳ、Ⅴ

7、下列选项中，不能构成折半查找中关键字比较序列的是（）。

A．500，200，450，180B．500，450，200，180

C．180，500，200，450D．180，200，500，450

8、有n（n0）个分支结点的满二叉树的深度是（）。

A.n-1

2

B.log（n+1）+1

2

C.log（n+1）

2

D.log（n-l）

2

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

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

10、若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查

找一个记录，其平均查找长度ASL为（）。

A.(n-1)/2

B.n/2

C.(n+1)/2

D.n

二、填空题

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

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

12、N个顶点的连通图用邻接矩阵表示时，该矩阵至少有______个非零元素。

13、已知有序表为（12，18，24，35，47，50，62，83，90，115，134）当用二分法查

找90时，需______次查找成功，查找47时______成功，查找100时，需______次才能确

定不成功。

14、设单链表的结点结构为（data，next），next为指针域，已知指针px指向单链表中

data为x的结点，指针py指向data为y的新结点，若将结点y插入结点x之后，则需

要执行以下语句：______

15、索引顺序文件既可以顺序存取，也可以______存取。

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

______。

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

18、已知链队列的头尾指针分别是f和r，则将值x入队的操作序列是______。

三、判断题

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