2022年成都大学计算机科学与技术专业《数据结构与算法》科目期末
试卷A（有答案）
一、选择题
1、哈希文件使用哈希函数将记录的关键字值计算转化为记录的存放地址，因为哈希函数
是一对一的关系，则选择好的（）方法是哈希文件的关键。

A.哈希函数
B.除余法中的质数
C.冲突处理
D.哈希函数和冲突处理
2、设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储， a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（）。

A.13
B.33
C.18
D.40
3、连续存储设计时，存储单元的地址（）。

A.一定连续
B.一定不连续
C.不一定连续
D.部分连续，部分不连续
4、用不带头结点的单链表存储队列，其队头指针指向队头结点，队尾指针指向队尾结点，则在进行出队操作时（）。

A.仅修改队头指针
B.仅修改队尾指针
C.队头、队尾指针都可能要修改
D.队头、队尾指针都要修改
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中，end1指向队头元素，end2指向队尾元素的后一个位置。

假设队列两端均可进行入队和出队操作，队列中最多能容纳M－1个元素。

初始时为空，
下列判断队空和队满的条件中，正确的是（）。

A．队空：end1＝＝end2；队满：end1＝＝（end2＋1）mod M
B．队空：end1＝＝end2；队满：end2＝＝（end1＋1）mod （M－1）
C．队空：end2＝＝（end1＋1）mod M；队满：end1＝＝（end2＋1） mod M
D．队空：end1＝＝（end2＋1）mod M；队满：end2＝＝（end1＋1） mod （M－1）
8、在下述结论中，正确的有（）。

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

②二叉树的度为2。

③二叉树的左右子树可任意交换。

④深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。

A.①②③
B.⑦③④
C.②④
D.①④
9、下述二叉树中，哪一种满足性质：从任一结点出发到根的路径上所经过的结点序列按
其关键字有序（）。

A.二叉排序树
B.哈夫曼树
C.AVL树
D.堆
10、分别以下列序列构造二叉排序树，与用其他三个序列所构造的结果不同的是（）。

A.（100，80，90，60，120，110，130）
B.（100，120，110，130，80，60，90）
C.（100，60，80，90，20，110，130）
D.（100，80，60，90，120，130，110）
二、填空题
11、顺序查找n个元素的顺序表，若查找成功，则比较关键字的次数最多为______次；当使用监视哨时，若查找失败，则比较关键字的次数为______。

12、在有n个顶点的有向图中，每个顶点的度最大可达______。

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

14、文件可按其记录的类型不同而分成两类，即______和______文件。

15、VSAM（虚拟存储存取方法）文件的优点是：动态地______，不需要文件进行______，并能较快地______进行查找。

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

设栈为顺序栈，每个元素占4个字节。

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

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

三、判断题
19、哈希表与哈希文件的唯一区别是哈希文件引入了“桶”的概念。

（）
20、倒排文件的目的是为了多关键字查找。

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

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

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

（）
24、一个树形的叶结点，在前序遍历和后序遍历下，皆以相同的相对位置出现。

（）
25、为了很方便地插入和删除数据，可以使用双向链表存放数据。

（）
26、排序算法中的比较次数与初始元素序列的排列无关。

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

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

（）
四、简答题
29、假定对有序表：（3，4，5，7，24，30，42，54，63，72，87，95）进行折半查找，试回答下列问题：
（1）画出描述折半查找过程的判定树。

（2）若查找元素54，需依次与哪些元素比较?
（3）若查找元素90，需依次与哪些元素比较?
（4）假定每个元素的查找概率相等，求查找成功时的平均查找长度。

30、设有n个元素采用起泡排序法进行排序，通常需要进行多少趟排序? 对于第J趟起泡
通常需要进行多少次关键字比较?在程序设计中如何设置判断条件，有可能使起泡趟数可
以减少并且能完成排序。

31、已知世界六大城市为：北京(Pe)、纽约(N)、巴黎(Pa)、伦敦(L)、东京(T)、墨西哥(M)，下表给定了这六大城市之间的交通里程：
世界六大城市交通里程表(单位：百公里)
（1）画出这六大城市的交通网络图。

（2）画出该图的邻接表表示法。

（3）画出该图按权值递增的顺序来构造的最小（代价）生成树。

五、算法设计题
32、图G有n个点，利用从某个源点到其余各点最短路径算法思想，设计一产生G的最小生成树的算法。

33、设计算法将一棵以二叉链表存储的二叉树按顺序方式存储到一维数组中（注：按层从上到下，由左到右）。

34、已知P是指向单向循环链表最后一个结点的指针，试编写只包含一个循环的算法，将线性表（a1，a2，…，a n-1，a n）改造为（a1，a2，…，a n-1，a n，a n-1，…，a2，a1）。

35、已知一棵高度为K具有n个结点的二叉树，按顺序方式存储。

（1）编写用前序遍历树中每个结点的非递归算法。

（2）编写将树中最大序号叶结点的祖先结点全部打印输出的算法。

参考答案
一、选择题
1、【答案】D
2、【答案】B
3、【答案】A
4、【答案】C
5、【答案】A
6、【答案】A
7、【答案】A
8、【答案】D
9、【答案】D
10、【答案】C
二、填空题
11、【答案】n；n+1
12、【答案】2(n-1)
13、【答案】2；4；3
【解析】二分法查找元素次数列表
查找100是找到115就停止了。

14、【答案】操作系统文件；数据库
15、【答案】分配和释放存储空间；重组；对插入的记录@
16、【答案】23；100CH
17、【答案】++a*b3*4-cd；18
【解析】中缀式相当于中序遍历，前缀式相当于前序遍历，后缀式相当于后序遍历。

18、【答案】33
三、判断题
19、【答案】×
20、【答案】√
21、【答案】×
22、【答案】√
23、【答案】×
24、【答案】√
25、【答案】√
26、【答案】×
27、【答案】×
28、【答案】√
四、简答题
29、答：（1）判定树如图所示：
（2）若查找元素54，需依次和元素30、63、42、54比较，查找成功。

（3）若查找元素90，需依次和元素30、63、87、95比较，查找失败。

（4）
30、答：n个元素采用起泡排序法进行排序，通常需要进行n-1趟排序。

第j趟起泡排序要进行n-j次比较。

在一趟排序中，若没有记录交换，则表示排序完成。

因而，可通过设标记来控制排序结束，下面语句段说明了标记flag的使用。

31、答：(1)这六大城市的交通网络图如图所示：
(2)该图的邻接表表示法如图所示：
(3)最小生成树有6个顶点与条边：V(G)={Pe，N，Pa，L，T，M}E(G)=｛(L，Pa，3)，(Pe，T，21)，(M，N，32)，(L，N，55)，(L， Pe，81)}
五、算法设计题
32、答：算法如下：
33、答：算法如下：
34、答：算法如下：
35、答：（1）算法如下：
（2）算法如下：。