大学计算机科学与技术专业《数据结构与算法》科目期末试卷A(有.pdf

2022年大连海事大学计算机科学与技术专业《数据结构与算法》科目

期末试卷A（有答案）

一、选择题

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

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

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，f，B.ac，f,e，b，d

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

3、链表不具有的特点是（）。

A.插入、删除不需要移动元素可随机B.访问任一元素

C.不必事先估计存储空间所需空D.间与线性长度成正比

4、最大容量为n的循环队列，队尾指针是rear，队头：front，则队空的条件是（）。

A.（rear+1）MODn=front

B.rear=front

C.rear+1=front

D.（rear-1）MODn=front

5、动态存储管理系统中，通常可有（）种不同的分配策略。

A.1B.2C.3D.4

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

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

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

7、下列叙述中，不符合m阶B树定义要求的是（）。
A．根结点最多有m棵子树．所有叶B结点都在同一层上

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

8、一棵非空的二叉树的前序序列和后序序列正好相反，则该二叉树一定满足（）。

A.其中任意一个结点均无左孩子

B.其中任意一个结点均无右孩子

C.其中只有一个叶结点

D.其中度为2的结点最多为一个

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

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

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

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

二、填空题

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

12、阅读下列程序，指出其功能，并写出空格处应填上的语句。

13、按LSD进行关键字排序，除最次位关键字之外，对每个关键字进行排序时，只能用
______的排序方法。
14、一个算法具有5个特性：______、______、______、有零个或多个输入、有一个或多个输
出。

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

16、当两个栈共享一存储区时，栈利用一维数组stack（1，n）表示，两栈顶指针为top[1]
与top[2]，则当栈1空时，top[1]为______，栈2空时，top[2]为______，栈满时为______。

17、设广义表L=（（），（）），则head（L）是______；tail（L）是______；L的长度是
______；深度是______。

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

三、判断题

19、对处理大量数据的外存介质而言，索引顺序存取方法是一种方便的文件组织方法。
（）

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

21、循环队列也存在空间溢出问题。（）

22、数组不适合作为任何二叉树的存储结构。（）

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

24、若从二叉树的任一结点出发，到根的路径上所经过的结点序列按其关键字有序，则该
二叉树一定是哈夫曼树。（）

25、顺序存储结构的主要缺点是不利于插入或删除操作。（）

26、若中序遍历平衡的二叉排序树，可得到排好序的关键码序列。（）

27、无环有向图才能进行拓扑排序。（）

28、对大小均为n的有序表和无序表分别进行顺序查找，在等概率查找的情况下，对于查
找成功，它们的平均查找长度是相同的，而对于查找失败，它们的平均查找长度是不同的。
（）

四、简答题

29、已知n阶下三角矩阵A（即当i＜j时，有a=0），按照压缩存储的思想，可以将其
ij
主对角线以下所有元素（包括主对角线上元素）依次存放于一维数组B中，请写出从第
一列开始采用列序为主序分配方式时在B中确定元素a的存放位置的公式。
ij

30、用一个数组S（设大小为MAX）作为两个堆栈的共享空间。请说明共享方法，栈满
／栈空的判断条件，并用C语言或PASCA