安徽工业大学《数据结构》2022-2023学年期末模拟试卷.docxVIP

安徽工业大学《数据结构》2022-2023学年期末模拟试卷

学校：__________姓名：__________班级：__________考号：__________

一、单项选择题

1．如图所示的带权无向图的最小生成树的权为（）

A.51 B.52

C.54 D.56

2．有向图中所有顶点入度之和与所有顶点出度之和的比是

A．1/2 B.1

C．2 D.4

3．假设以三元组表表示稀疏矩阵，则与如图所示三元组表对应的4×5的稀疏矩阵是（注：矩阵的行列下标均从1开始）（）

A. B.

C. D.

4．若进栈次序为a，b，c，且进栈和出栈可以穿插进行，则可能出现的含3个元素的出栈序列个数是（）

A．3 B．5

C．6 D．7

5．散列文件是一种（）

A.顺序存取的文件 B.随机存取的文件

C.索引存取的文件 D.索引顺序存取的文件

6．某索引顺序表共有元素395个，平均分成5块。若先对索引表采用顺序查找，再对块中元素进行顺序查找，则在等概率情况下，分块查找成功的平均查找长度是（）

A.43 B.79

C.198 D.200

7．下列排序方法中稳定的是

A．直接插入排序 B．直接选择排序

C．堆排序 D．快速排序

8．无论待排序列是否有序，排序算法时间复杂度都是O(n2)的排序方法是（）

A.快速排序 B.归并排序

C.冒泡排序 D.直接选择排序

9．A是7×4的二维数组，按行优先方式顺序存储，元素A[0][0]的存储地址为1000，若每个元素占2个字节，则元素A[3][3]的存储地址为

A．1015 B．1016

C．1028 D．1030

10．通常将链串的结点大小设置为大于1是为了()

A.提高串匹配效率 B.提高存储密度

C.便于插入操作 D.便于删除操作

11．上溢现象通常出现在（）

A．顺序栈的入栈操作过程中 B．顺序栈的出栈操作过程中

C．链栈的入栈操作过程中 D．链栈的出栈操作过程中

12．ISAM文件的周期性整理是为了空出（）

A．磁道索引 B．柱面索引

C．柱面基本区 D．柱面溢出区

13．若在9阶B-树中插入关键字引起结点分裂，则该结点在插入前含有的关键字个数为

()

A.4B.5

C.8D.9

14．下图所示带权无向图的最小生成树的权为()

A.14

B.15

C.17

D.18

15．已知一棵树的前序序列为ABCDEF，后序序列为CEDFBA，则对该树进行层次遍历得到的序列为()

A．ABCDEF B．ABCEFD

C．ABFCDE D．ABCDFE

16．从广义表LS＝（(p,q),r,s）中分解出原子q的运算是（）

A．tail(head(LS)) B．head(tail(head(LS)))

C．head(tail(LS)) D．tail(tail(head(LS)))

17．已知广义表的表头为a，表尾为(b,c)，则此广义表为()

A.(a,(b,c))B.(a,b,c)

C.((a),b,c)D.((a,b,c))

18．设有两个串T和P，求P在T中首次出现的位置的串运算称作()

A.联接B.求子串C.字符定位D.子串定位

19．为查找某一特定单词在文本中出现的位置，可应用的串运算是()

A.插入B.删除C.串联接D.子串定位

20．在一棵度为3的树中,度为3的结点个数为2,度为2的结点个数为1,则度为0的结点个数为()

A．4B．5C．6D．7

二、填空题

21．顺序文件中记录存放的物理顺序和顺序一致。

22．在快速排序、堆排序和归并排序中，最坏时间复杂度为O(n2)的排序算法有___________。

23．任意一棵完全二叉树中，度为1的结点数最多为________。

24．广义表(a，(d，(c)))的深度为_________。

25．使用一个100个元素的数组存储循环队列，如果采取少用一个元素空间的方法来区别循环队列的队空和队满，约定队头指针front等于队尾指针rear时表示队空。若为front=8，rear=7