一、选择题

1、设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储， a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（　　）。

A.13    B.33       C.18         D.40

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

A.哈希函数

B.除余法中的质数

C.冲突处理

D.哈希函数和冲突处理

3、计算机算法指的是解决问题的步骤序列，它必须具备（　　）三个特性。

A.可执行性、可移植性、可扩充性

B.可执行性、确定性、有穷性

C.确定性、有穷性、稳定性

D.易读性、稳定性、安全性

4、已知串S='aaab'，其next数组值为（　　）。

A.0123    B.1123    C.1231         D.1211

5、下列关于AOE网的叙述中，不正确的是（　　）。

A.关键活动不按期完成就会影响整个工程的完成时间

B.任何一个关键活动提前完成，那么整个工程将会提前完成 

C.所有的关键活动提前完成，那么整个工程将会提前完成

D.某些关键活动若提前完成，那么整个工程将会提前完成

6、循环队列放在一维数组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）

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

A．500，200，450，1．500，450，200，180

C．180，500，200，4．180，200，500，450

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

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

9、一棵非空的二叉树的前序序列和后序序列正好相反，则该二叉树一定满足（　　）。

A.其中任意一个结点均无左孩子

B.其中任意一个结点均无右孩子

C.其中只有一个叶结点

D.其中度为2的结点最多为一个

10、对n个记录的线性表进行快速排序为减少算法的递归深度，以下叙述正确的是（　　）。

A.每次分区后，先处理较短的部分

B.每次分区后，先处理较长的部分

C.与算法每次分区后的处理顺序无关

D.以上三者都不对

二、填空题

11、对n个记录的表r[1..n]进行简单选择排序，所需进行的关键字间的比较次数为______。

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

13、线性表L=（a1，a2，…，an）用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是______。

14、n个顶点的有向图用邻接矩阵array表示，下面是其拓扑排序算法，试补充完整。

注：(1)图的顶点号从0开始计。

(2)indegree是有n个分量的一维数组，放顶点的入度，

(3)函数crein用于计算顶点入度。

(4)有三个函数push(data)，pop()，check()其含义为数据data入栈，出栈和测试栈是否空(不空返回l，否则0)。

15、索引顺序文件既可以顺序存取，也可以______存取。

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

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

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

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

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

18、一棵有n个结点的满二叉树有______个度为1的结点、有______个分支（非终端）结点和______个叶子，该满二叉树的深度为______。

三、判断题

19、倒排文件是对次关键字建立索引。（　　）

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

21、串是一种数据对象和操作都特殊的线性表。（　　）

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

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

24、用一维数组存储二叉树时，总是以前序遍历顺序存储结点。（　　）

25、在任何情况下，归并排序都比简单插入排序快。（　　）

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

27、对大小均为n的有序表和无序表分别进行顺序查找，在等概率查找的情况下，对于查找成功，它们的平均查找长度是相同的，而对于查找失败，它们的平均查找长度是不同的。（　　）

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

四、简答题

29、给出一组关键字：29，18，25，47，58，12，51，10，分别写出按下列各种排序方法进行排序时的变化过程：

（1） 归并排序，每归并一次书写一个次序。

（2） 快速排序，每划分一次书写一个次序。

（3） 堆排序，先建成一个堆，然后每从堆顶取下一个元素后，将堆调整一次。

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

31、已知一个带有表头结点的单链表，结点结构为

假设该链表只给出了头指针list。在不改变链表的前提下，请设计一个尽可能高效的算法，查找链表中倒数第k个位置上的结点（k为正整数）。若查找成功，算法输出该结点的data域的值，并返回1；否则，只返回0。要求：

（1）描述算法的基本设计思想。

（2）描述算法的详细实现步骤。

（3）根据设计思想和实现步骤，采用程序设计语言描述算法（使用C或C＋＋或JAVA语言实现），关键之处请给出简要注释。

五、算法设计题

32、借助于快速排序的算法思想，在一组无序的记录中查找给定关键字值等于key的记录。设此组记录存放于数组r[1..h]中。若查找成功，则输出该记录在r数组中的位置及其值，否则显示“not find”信息。请编写出算法并简要说明算法思想。

33、以顺序存储结构表示串，设计算法。求串s中出现的第一个最长重复子串及其位置并分析算法的时间复杂度。

34、结点类型和存储结构如下：

试设计一个排序算法，要求不移动结点的存储位置，只在结点的count 字段记录结点在排序中的序号，并将排序结果按升序输出。

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

参

一、选择题

1、【答案】B

2、【答案】D

3、【答案】B

4、【答案】A

5、【答案】B

6、【答案】A

7、【答案】A

8、【答案】A

9、【答案】C

10、【答案】A

二、填空题

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

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

13、【答案】（n-1）/2

14、【答案】0；j；i；0；indegree[i]=0；[vex][i]；k==l；indegree[i]=0

【解析】有向图用邻接矩阵表示时，顶点i的入度等于第i列的所有元素之和。拓扑排序过程：首先将入度为0的顶点全部进栈。然后弹出栈顶结点，并将与弹出的顶点相连的其他顶点的入度减一，然后判断这些顶点的入度是否为零，如果为零，继续进栈，重复这些操作，完成拓扑排序。

15、【答案】随机

16、【答案】23；100CH

17、【答案】270；27；2204

18、【答案】

【解析】满二叉树没有度为1的结点，度为0的结点等于度为2的结点个数+1。

三、判断题

19、【答案】√

20、【答案】×

21、【答案】√

22、【答案】√

23、【答案】√

24、【答案】×

25、【答案】×

26、【答案】×

27、【答案】√

28、【答案】√

四、简答题

29、答：（1）2一路归并第一趟：18，29，25，47，12，58，10，51。

第二趟：18，25，29，47，10，12，51，58。

第三趟：10，12，18，25，29，47，51，58。

（2）快速排序第一趟：10，18，25，12，29，58，51，47。

第二趟：10，18，25，12，29，47，51，88。

第三趟：10，12，18，25，29，47，51，88。

（3）堆排序

建大堆：58，47，51，29，18，12，25，10。

151，47，25，29，18，12，10，58。

247，29，25，10，18，12，51，58。

329，18，25，10，12，47，51，58。

425，18，12，10，29，47，51，58。

518，10，12，25，29，47，51，58。

612，10，18，25，29，47，51，58。

710，12，18，25，29，47，51，58。

30、答：此排序为双向起泡排序：从前向后一趟排序下来得到一个最大值，若其中发生交换，则再从后向前一趟排序，得到一个最小值。第一趟：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

31、答：（1）算法的基本设计思想定义两个指针变量p和q，初始时均指向头结点的下一个结点。p指针沿链表移动；当p指针移动到第k个结点时，q指针开始与p指针同步移动；当p指针移动到链表最后一个结点时，因为p和q相隔k，故q指针所指元素为倒数第k个结点。以上过程对链表仅进行一遍扫描。

（2）算法的详细实现步骤

① count＝0，p和q指向链表表头结点的下一个结点。

②若p为空，转⑤。

③若count等于k，则q指向下一个结点；否则，count＝count＋1。

④ p指向下一个结点，转步骤②。

⑤若count等于k，则查找成功，输出该结点的data域的值，返回1；否则，查找失败，返回0。

⑥算法结束。

（3）算法实现

五、算法设计题

32、答：算法如下：

33、答：算法如下：

时间复杂度：算法的时间复杂度为O（n），每个字符与其后继比较一次。

34、答：算法如下

35、答：算法如下：下载本文