2022年衡阳师范学院南岳学院计算机科学与技术专业《数据结构与算法》科.pdfVIP

2022年衡阳师范学院南岳学院计算机科学与技术专业《数据结构与算

法》科目期末试卷A（有答案）

一、选择题

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

链移动的操作为（）。

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

2、n个结点的完全有向图含有边的数目（）。

A.n*nB.n(n+1)C.n/2D.n*(n-1)

3、连续存储设计时，存储单元的地址（）。

A.一定连续B.一定不连续C.不一定连续D.部分连续，部分不连续

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

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

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

A.串是字符的有限序列

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

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

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

6、下列选项中，不能构成折半查找中关键字比较序列的是（）。

A．500，200，450，180．B500，450，200，180

C．180，500，200，450．D180，200，500，450

7、排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一趟排序。下列排序

方法中，每一趟排序结束时都至少能够确定一个元素最终位置的方法是（）。

Ⅰ．简单选择排序Ⅱ．希尔排序Ⅲ．快速排序Ⅳ．堆排Ⅴ．二路归并排序

A．仅Ⅰ、Ⅲ、Ⅳ．B仅Ⅰ、Ⅱ、ⅢC．仅Ⅱ、Ⅲ、Ⅳ．D仅Ⅲ、Ⅳ、Ⅴ

8、一个具有1025个结点的二叉树的高h为（）。

A.11B.10至C.111025之间至D.101024之间

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

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

②二叉树的度为2。

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

同的满二叉树。

A.①②③

B.⑦③④

C.②④

D.①④

10、下列二叉排序树中查找效率最高的是（）。

A.平衡二叉树

B.二叉查找树

C.没有左子树的二叉排序树

D.没有右子树的二叉排序树

二、填空题

11、无用单元是指______，例______

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

成321。请填空：

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

14、以下是用类C语言写出的算法，该算法将以二叉链表存储的二叉树中的叶结点按从

左到右的顺序链成一个带头结点的双向循环链表，链接时，结点的Lchild域作为前链域，

指向结点的直接前驱，结点的Rchild域作为后链域，指向结点的直接后继。算法中，使

用一个顺序栈stack，栈顶指针为top，p，t为辅助指针，head为双向循环链表的头指针。

试填充算法中的空格，使算法完整。

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

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

定不成功。

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

17、设数组A[0..8，1..10]，数组中任一元素A[i，j]均占内存48个二进制位，从首地址

2000开始连续存放在主内存里，主内存字长为16位，那么

（1）存放该数组至少需要的单元数是______。

（2）存放数组的第8列的所有元素至少需要的单元数______。

（3）数组按列存储时，元素A[5，8]的起始地址是______。

18、已知一循环队列的存储空间为[m..n]，其