...科学与技术专业《数据结构与算法》科目期末试卷A(有答案)

一、选择题

1、从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为（　　）排序法。

A.插入 选择 希尔 二路归并

2、哈希文件使用哈希函数将记录的关键字值计算转化为记录的存放地址，因为哈希函数是一对一的关系，则选择好的（　　）方法是哈希文件的关键。

A.哈希函数

B.除余法中的质数

C.冲突处理

D.哈希函数和冲突处理

3、以下数据结构中，（　　）是非线性数据结构。

A.树 字符串 队 栈

4、向一个栈顶指针为h的带头结点的链栈中插入指针s所指的结点时，应执行（　　）。

A.h->next=s

B.s->next=h

C.s->next=h;h->next=s

D.s->next=h-next;h->next=s

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

A.串是字符的有限序列

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

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

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

6、已知字符串S为“abaabaabacacaabaabcc”，模式串t为“abaabc”，采用KMP算法进行匹配，第一次出现“失配”（s!＝t）时，i＝j＝5，则下次开始匹配时，i和j的值分别（　　）。

A．i＝1，j＝0  B．i＝5，j＝0．i＝5，j＝2．i＝6，j＝2

7、若元素a，b，c，d，e，f依次进栈，允许进栈、退栈操作交替进行，但不允许连续三次进行退栈操作，则不可能得到的出栈序列是（　　）。

8、有n（n>0）个分支结点的满二叉树的深度是（　　）。

A.n2-1

B.log2（n+1）+1

C.log2（n+1）

D.log2（n-l）

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

A.CBEFDA           B.FEDCBA          C.CBEDFA                D.不定

10、下面关于B和B+树的叙述中，不正确的是（　　）

A.B树和B+树都是平衡的多叉树 树和B+树都可用于文件的索引结构

C.B树和B+树都能有效地支持顺序检索  D.B树和B+树都能有效地支持随机检索

二、填空题

11、如果按关键码值递增的顺序依次将关键码值插入到二叉排序树中，则对这样的二叉排序树检索时，平均比较次数为______。

12、以下程序的功能是实现带附加头结点的单链表数据结点逆序连接，请填空完善之。

13、VSAM系统是由______、______、______构成的。

14、数据结构中评价算法的两个重要指标是______。

15、如下的算法分别是后序线索二叉树求给定结点node的前驱结点与后继结点的算法，请在算法空格处填上正确的语句。设线索二叉树的结点数据结构为（lflag，left，data，right，rflag），其中：lflag=0，left指向其左孩子，lflag=1，left指向其前驱；rflag=0，right指向其右孩子， rflag=1，right指向其后继。

16、设数组A[0..8，1..10]，数组中任一元素A[i，j]均占内存48个二进制位，从首地址2000开始连续存放在主内存里，主内存字长为16位，那么

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

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

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

17、假设一个15阶的上三角矩阵A按行优先顺序压缩存储在一维数组B 中，则非零元素A9.9在B中的存储位置k=______。（注：矩阵元素下标从1开始）

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

三、判断题

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

20、对磁带机而言，ISAM是一种方便的文件组织方法（　　）

21、稀疏矩阵压缩存储后，必会失去随机存取功能。（　　）

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

23、二叉树是一般树的特殊情形。（　　）

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

25、数据的逻辑结构是指数据的各数据项之间的逻辑关系。（　　）

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

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

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

四、简答题

29、写出下列排序算法的基本思想，并写出对序列（23，12，35，47， 16，25，36，19，21，16）进行排序时每一趟的结果。

30、对于具有n个叶结点且所有非叶结点都有左、右孩子的二叉树。

(1)试问这种二叉树的结点总数是多少?

(2)试证明2-（li-1）=1。其中：li表示第i个叶结点所在的层号（设根结点所在层号为1）。

31、已知有6个顶点（顶点编号为0～5）的有向带权图G，其邻接矩阵A 为上三角矩阵，按行为主序（行优先）保存在如下的一维数组中。

要求：

（1）写出图G的邻接矩阵A。

（2）画出有向带权图G。求图G的关键路径，并计算该关键路径的长度。

五、算法设计题

32、假设一个仅包含二元运算符的算术表达式以链表形式存储在二叉树BT中，写出计算该算术表达式值的算法。

33、辅助地址表的排序是不改变结点物理位置的排序。辅助地址表实际上是一组指针，用它来指出结点排序后的逻辑顺序地址。设用K[1]， K[2]，…，K[n]表示n个结点的值，用T[1]，T[2]，…，T[n]表示辅助地址表。初始时T[i]：=i，在排序中，凡需对结点交换就用它的地址来进行。例如当n=3时，对K（31，11，19）则有T（2，3，1）。试编写实现辅助地址表排序（按非递减序）算法的语句序列。

34、已知二叉树T，试写出复制该二叉树的算法（t→T）。

35、设二叉排序树的各元素值均不相同，采用二叉链表作为存储结构，试分别设计递归和非递归算法按递减序打印所有左子树为空，右子树非空的结点的数据域的值。

参

一、选择题

1、【答案】A

2、【答案】D

3、【答案】A

4、【答案】D

5、【答案】B

6、【答案】C 

7、【答案】D

8、【答案】C

9、【答案】A

10、【答案】C

二、填空题

11、【答案】（n+1）/2

12、【答案】

（1）p!=NULL //链表未到尾就一直进行

（2）q //将当前结点作为头结点后的第一元素结点插入

13、【答案】索引集；顺序集；数据集

14、【答案】算法的时间复杂度和空间复杂度

15、【答案】node->rflag==0；*x=bt；*x=node->right；prior（t，x）

16、【答案】270；27；2204

17、【答案】93

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

三、判断题

19、【答案】×

20、【答案】×

21、【答案】√

22、【答案】×

23、【答案】×

24、【答案】√

25、【答案】×

26、【答案】×

27、【答案】×

28、【答案】√

四、简答题

29、答：此排序为双向起泡排序：从前向后一趟排序下来得到一个最大值，若其中发生交换，则再从后向前一趟排序，得到一个最小值。第一趟：12，23，35，16，25，36，19，21，16，47 第二趟：12，16，23，35，16，25，36，19，21，47 第三趟：12，16，23，16，25，35，19，21，36，47 第四趟：12，16，16，23，19，25，35，21，36，47 第五趟：12，16，16，19，23，25，21，35，36，47 第六趟：12，16，16，19，21，23，25，35，36，47 第七趟：12，16，16，19，21，23，25，35，36，47

30、答：（1）根据二叉树中度为2的结点个数等于叶结点个数减1的性质，故具有n个叶结点且非叶子结点均有左子树的二叉树的结点数是2n-1。

（2）证明：当i=1时，2-（1-1）=20=1，公式成立。设当i=n-1时公式成立，证明当i=n时公式仍成立。设某叶结点的层号为t，当将该结点变为内部结点，从而再增加两个叶结点时，这两个叶结点的层号都是t+1，对于公式的变化，是减少了一

个原来的叶结点，增加了两个新叶结点，反映到公式中，因为2-（t-1）=2-（t+1-1）+2-（t+1-1），所以结果不变，这就证明当i=n时公式仍成立。证毕。

31、答：（1）由题可以画出待定上三角矩阵的结构图如下（图中？为待定元素）：

可以看出，第一行至第五行主对角线上方的元素分别为5，4，3，2，1 个，由此可以画出压缩存储数组中的元素所属行的情况，如下图所示：

将各元素填入各行即得邻接矩阵：

（2）根据第一步所得矩阵A容易做出有向带权图G，如下：

（3）关键路径为0-＞1-＞2-＞3-＞5（如下图所示粗线表示），长度为4＋5＋4＋3＝16。

五、算法设计题

32、答：算法如下：

33、答：算法如下：

34、答：算法如下：

35、答：（1）递归算法如下：

（2）非递归算法如下：