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

2022年成都工业学院计算机科学与技术专业《数据结构与算法》科目

期末试卷A（有答案）

一、选择题

1、设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素，

其存储地址为1，每个元素占一个地址空间，则a85的地址为（）。

A.13B.33C.18D.40

2、下列排序算法中，占用辅助空间最多的是（）。

A.归并排序B.快速排序C.希尔排序D.堆排序

3、某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则

采用（）存储方式最节省运算时间。

A.单链表仅B.有头指针的单循环链表双C.链表仅D.有尾指针的单循环链表

4、有六个元素6，5，4，3，2，1顺序入栈，下列不是合法的出栈序列的是（）。

A.543612B.453126C.346521D.234156

5、在下列表述中，正确的是（）

A.含有一个或多个空格字符的串称为空格串

B.对n（n0）个顶点的网，求出权最小的n-1条边便可构成其最小生成树

C.选择排序算法是不稳定的

D.平衡二叉树的左右子树的结点数之差的绝对值不超过l

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

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

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

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

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

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

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

A.n-1

2

B.log（n+1）+1

2

C.log（n+1）

2

D.log（n-l）

2

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

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

②二叉树的度为2。

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

同的满二叉树。

A.①②③

B.⑦③④

C.②④

D.①④

10、下面关于B和B+树的叙述中，不正确的是（）

A.B树和B+树都是平衡的多叉树树B.B和B+树都可用于文件的索引结构

C.B树和B+树都能有效地支持顺序检索D.B树和B+树都能有效地支持随机检索

二、填空题

11、以下程序的功能是实现带附加头结点的单链表数据结点逆序连接，请填空完善之。

12、属于不稳定排序的有______。

13、数据结构是研讨数据的______和______以及它们之间的相互关系，并对与这种结构定义

相应的______，设计出相应的______。

14、关键码序列（Q，H，C，Y，Q，A，M，S，R，D，F，X），要按照关键码值递增的

次序进行排序，若采用初始步长为4的希尔排序法，则一趟扫描的结果是______；若采用

以第一个元素为分界元素的快速排序法，则扫描一趟的结果是______。

15、在单链表L中，指针P所指结点有后继结点的条件是______。

16、下列程序是快速排序的非递归算法，请填写适当的语句，完成该功能。

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

的地址为______。

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

三、判断题

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

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

21、栈的输入序列是1，2，…，n，输出序列是a1，a2，…，