西安科技大学地址

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

期末试卷A（有答案）

一、选择题

1、若需在O（nlog2n）的时间内完成对数组的排序，且要求排序是稳定的，则可选择的

排序方法是（）。

A.快速排序B.堆排序C.归并排序D.直接插入排序

2、用数组r存储静态链表，结点的next域指向后继，工作指针j指向链中结点，使j沿

链移动的操作为（）。

A.j=r[j].nextB.j=j+lC.j=j->nextD.j=r[j]->next

3、线性表的顺序存储结构是一种（）。

A.随机存取的存储结构B.顺序存取的存储结构

C.索引存取的存储结构存取的存储结构

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

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

5、用不带头结点的单链表存储队列，其队头指针指向队头结点，队尾指针指向队尾结点，

则在进行出队操作时（）。

A.仅修改队头指针

B.仅修改队尾指针

C.队头、队尾指针都可能要修改

D.队头、队尾指针都要修改

6、循环队列放在一维数组A中，end1指向队头元素，end2指向队尾元素的后一个位置。

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

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

A．队空：end1＝＝end2；队满：end1＝＝（end2＋1）modM

B．队空：end1＝＝end2；队满：end2＝＝（end1＋1）mod（M－1）

C．队空：end2＝＝（end1＋1）modM；队满：end1＝＝（end2＋1）modM

D．队空：end1＝＝（end2＋1）modM；队满：end2＝＝（end1＋1）mod（M－1）

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

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

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

8、每个结点的度或者为0或者为2的二叉树称为正则二叉树。n个结点的正则二叉树中

有（）个叶子。

2

nB.（n－1）/

2

n+1D.（n＋1）/2

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

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

②二叉树的度为2。

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

同的满二叉树。

A.①②③

B.⑦③④

C.②④

D.①④

10、对关键码序列28，16，32，12，60，2，5，72快速排序，从小到大一次划分结果

为（）。

A.（2，5，12，16）26（60，32，72）

B.（5，16，2，12）28（60，32，72）

C.（2，16，12，5）28（60，32，72）

D.（5，16，2，12）28（32，60，72）

二、填空题

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

12、下面程序的功能是用递归算法将一个整数按逆序存放到一个字符数组中。如123存放

成321。请填空：

13、已知有序表为（12，18，24，35，47，50，62，83，90，115，134）当用二分法查

找90时，需______次查找成功，查找47时______成功，查找100时，需______次才能确

定不成功。

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

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

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

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

16、设数组a[1..50，1..80]的基地址为2000，每个元素占2个存储单元，若以行序为主序

顺序存储，则元素a[45，68]的存储地址为______；若以列序为主序顺序存储，则元素a[45，

68]的存储地址为______。

17、已知一循环队列的存储空间为[m..n]，其中n>m，队头和队尾指针分别为front和

rear，则此循环队列判满的条件是______。

18、设有N个结点的完全二叉树顺序存放在向量A[1：N]中，其下标值最大的分支结点

为______。

三、判断题

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

20、文件系统采用索引结构是为了节省存储空间。（）

21、队列和栈都是运算受限的线性表，只允许在表的两端进行运算。（）

22、设栈采用顺序存储结构。若已有i-1个元素入栈，则将第i个元素入栈时，入栈算法

的时间复杂性为O（i）。（）

23、一棵树中的叶子数一定等于与其对应的二叉树的叶子数。（）

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

二叉树一定是哈夫曼树。（）

25、排序的稳定性是指排序算法中的比较次数保持不变，且算法能够终止。（）

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

27、对大小均为n的有序表和无序表分别进行顺序查找，在等概率查找的情况下，对于查

找成功，它们的平均查找长度是相同的，而对于查找失败，它们的平均查找长度是不同的。

（）

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

闲置空间的碎片。（）

四、简答题

29、调用下列C函数f（n），回答下列问题：

（1）试指出f（n）值的大小，并写出，f（n）值的推导过程。

（2）假定n=5，试指出，f（5）值的大小和执行，f（5）时的输出结果。

C函数：

30、请写出应填入下列叙述中（）内的正确答案。排序有各种方法，如插入排序、快

速排序、堆排序等。设一数组中原有数据如下：15，13，20，18，12，60。下面是一组用

不同排序方法进行一遍排序后的结果。

（）排序的结果为：12，13，15，18，20，60

（）排序的结果为：13，15，18，12，20，60

（）排序的结果为：13，15，20，18，12，60

（）排序的结果为：12，13，20，18，15，60

31、对下面的关键字集{30，15，21，40，25，26，36，37}若查找表的装填因子为0.8，

采用线性探测再哈希方法解决冲突，做：（1）设计哈希函数；（2）画出哈希表；（3）

计算查找成功和查找失败的平均查找长度；（4）写出将哈希表中某个数据元素删除的算

法。

五、算法设计题

32、设计将数组A[n]中所有的偶数移到奇数之前的算法。要求不增加存储空间，且时间

复杂性为O（n）。

33、试将下列递归过程改写为非递归过程。

34、按图的宽度优先搜索法写一算法判别以邻接矩阵存储的有向图中是否存在由顶点V

i

到顶点V

j

的路径(i≠j)

35、编写一算法，利用叶结点中的空指针域将所有叶结点链接为一个带有头结点的双链表，

算法返回头结点的地址。

参考答案

一、选择题

1、【答案】C

2、【答案】A

3、【答案】A

4、【答案】B

5、【答案】C

6、【答案】A

7、【答案】D

8、【答案】D

9、【答案】D

10、【答案】B

二、填空题

11、【答案】希尔排序、简单选择排序、快速排序、堆排序等

12、【答案】a+1；n%10

【解析】通过递归算法，首先找到最高位的值，将其放到str对应的数组中，依次反向获

取从高位到地位的值，将其放到数组中，完成了将整数逆序放到一个字符数组中。

13、【答案】2；4；3

【解析】二分法查找元素次数列表

查找100是找到115就停止了。

14、【答案】（Q，A，C，S，Q，D，F，X，R，H，M,Y）；（F，H，C，D，a，A，M，

Q，R，S，Y，X）

15、【答案】P->next!=NULL

16、【答案】9174；8788

17、【答案】（rear+1）%（n-m+1）==front

18、【答案】

【解析】最大的分支结点是最后一个叶子结点的父结点。

三、判断题

19、【答案】×

20、【答案】×

21、【答案】×

22、【答案】×

23、【答案】×

24、【答案】×

25、【答案】×

26、【答案】×

27、【答案】√

28、【答案】√

四、简答题

29、答：（1）第一层for循环判断n+1次，往下执行n次，第二层for执行次数为（n+

（n-1）+（n-2）+…+1），第三层循环体受第一层循环和第二层循环的控制，其执行次

数如表1-1所示。

执行次数为f(n)=（1+2+…+，n）+（2+3+…+，n）+…+n=n*n（n+1）/2-n（n2-1）/6。

（2）在n=5对，f（5）=55，执行过程中，输出结果为：

30、答：①快速排序②起泡排序③直接插入排序④堆排序

31、答：（1）由于装填因子为0.8，关键字有8个，所以表长为8/0.8=10。用除留余数

法设计哈希函数，哈希函数为14（key）=key%7。

（2）哈希表如表所示：

（3）计算查找失败时的平均查找长度，必须计算不在表中的关键字，当其哈希地址为i

（0≤i≤m-1）时的查找次数。本例中m=10。故查找失败和查找成功时的平均查找长度分别

为：

（4）算法如下：

五、算法设计题

32、答：算法如下：

33、答：算法如下：

34、答：算法如下：

35、答：算法如下：