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

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

一、选择题

1、下列说法不正确的是（）。

A.图的遍历是从给定的源点出发每个顶点仅被访问一次

B.遍历的基本方法有两种：深度遍历和广度遍历

C.图的深度遍历不适用于有向图

D.图的深度遍历是一个递归过程

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

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

3、以下与数据的存储结构无关的术语是（）。

A.循环队列B.链表C.哈希表D.栈

4、在用邻接表表示图时，拓扑排序算法时间复杂度为（）。

A.O(n)B.O(n+e)C.O(n*n)D.O(n*n*n)

5、下面关于串的叙述中，不正确的是（）。

A.串是字符的有限序列

B.空串是由空格构成的串

C.模式匹配是串的一种重要运算

D.串既可以采用顺序存储，也可以采用链式存储

6、若一棵二叉树的前序遍历序列为a，e，b，d，c，后序遍历序列为b，c，d，e，a，则根结点的孩子结点（）。

A．只有eB．有e、bC．有e、cD．无法确定

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

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

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

8、有关二叉树下列说法正确的是（）。

A.二叉树的度为2

B.一棵二叉树的度可以小于2

C.二叉树中至少有一个结点的度为2

D.二叉树中任何一个结点的度都为2

9、已知一棵二叉树的前序遍历结果为ABCDEF，中序遍历结果为CBAEDF，则后序遍历结果为（）。

A.CBEFDAB.FEDCBAC.CBEDFAD.不定

10、一组记录的关键码为（46，79，56，38，40，84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（）。

A.（38，40，46，56，79，84）B.（40，38，46，79，56，84）

C.（40，38，46，56，79，84）D.（40，38，46，84，56，79）

二、填空题

11、在哈希函数H（key）=key%p中，p值最好取______。

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

13、已知有序表为（12，18，24，35，47，50，62，83，90，115，134）当用二分法查找90时，需______次查找成功，查找47时______成功，查找100时，需______次才能确定不成功。

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

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

16、设有一个空栈，栈顶指针为1000H（十六进制），现有输入序列为l，2，3，4，5，经过PUSH，PUSH，POP，PUSH，POP，PUSH，PUSH之后，输出序列是______，而栈顶指针值是______。设栈为顺序栈，每个元素占4个字节。

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

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

三、判断题

19、倒排序文件的优点是维护简单。（）

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

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

22、在链队列中，即使不设置尾指针也能进行入队操作。（）

23、任何二叉树的后序线索树进行后序遍历时都必须用栈。（）

24、一般来说，若深度为k的n个结点的二叉树只有最小路径长度，那么

从根结点到第k-1层具有的最多结点数为2k-1-1，余下的n-2k-1+1个结点在第k层的任一位置上。（）

25、外部排序是把外存文件调入内存，可利用内部排序的方法进行排序，因此排序所花的时间取决于内部排序的时间。（）

26、在外部排序过程中，对长度为n的初始序列进行“置换-选择”排序时，可以得到的最大初始有序段的长度不超过n/2。（）

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

28、在动态存储管理系统中做空间分配时，最佳适配法与最先适配法相比，前者容易增加闲置空间的碎片。（）

四、简答题

29、已知n阶下三角矩阵A（即当i＜j时，有aij=0），按照压缩存储的思想，可以将其