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

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

一、选择题

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

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

2、有一个100*90的稀疏矩阵，非0元素有10个，设每个整型数占2字节，则用三元组表示该矩阵时，所需的字节数是（）。

A.60B.66C.18000D.33

3、若线性表最常用的操作是存取第i个元素及其前驱和后继元素的值，为节省时间应采用的存储方式（）。

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、循环队列A[0..m-1]存放其元素值，用front和rear分别表示队头和队尾，则当前队列中的元素数是（）。

A.（rear-front+m）%m

B.rear-front+1

C.rear-front-1

D.rear-front

6、下列关于无向连通图特性的叙述中，正确的是（）。

Ⅰ．所有的顶点的度之和为偶数Ⅱ．边数大于顶点个数减1Ⅲ．至少有一个顶点的度为1

A．只有ⅠB．只有ⅡC．Ⅰ和ⅡD．Ⅰ和Ⅲ

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

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

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

8、下述二叉树中，哪一种满足性质：从任一结点出发到根的路径上所经过的结点序列按其关键字有序（）。

A.二叉排序树B.哈夫曼树C.AVL树D.堆

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

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

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

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

二、填空题

11、设用希尔排序对数组{98，36，-9，0，47，23，1，8，10，7}进行排序，给出的步长（也称增量序列）依次是4，2，1则排序需______趟，写出第一趟结束后，数组中数据的排列次序______。

12、下面程序的功能是用递归算法将一个整数按逆序存放到一个字符数组中。如123存放成321。请填空：

13、按LSD进行关键字排序，除最次位关键字之外，对每个关键字进行排序时，只能用______的排序方法。

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

15、设单链表的结点结构为（data，next），next为指针域，已知指针px指向单链表中data为x的结点，指针py指向data为y的新结点，若将结点y插入结点x之后，则需要执行以下语句：______

16、设正文串长度为n，模式串长度为m，则串匹配的KMP算法的时间复杂度为______。

17、设有一个10阶对称矩阵A采用压缩存储方式（以行为主序存储：a11=1），则a85的地址为______。

18、已知一循环队列的存储空间为[m..n]，其中nm，队头和队尾指针分别为front和rear，则此循环队列判满的条件是______。

三、判断题

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

20、文件系统采用索引结构是为了节省存储空间。（）

21、栈的输入序列是1，2，…，n，输出序列是a1，a2，…，an若ai=n（1≤i≤n）则有：aiai+1…an。（）

22、广义表（（（a，b，c），d，e，f））的长度是4。（）

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

24、哈夫曼树度为1的结点数等于度为2和0的结点数之差。（）

25、排序的稳定性是指排序算法中的比较次数保持不变，且算法能够终止。（）

26、归并排序辅助存储为O（1）。（）

27、当改变网上某一关键路径上任一关键活动后，必将产生不同的关