一、在供选择的答案中选择与下列各括号中内容相匹配的答案，把其编号与其括号的标识对

应起来（单选，每个答案2分）。

（1）用单链表表示的链式队列的对头在链表的（）位置。

（2）如果只想得到1000个元素组成的序列中第5个最小元素之前的部分排序的序列，用（）方法最快。

（3）如果待排序序列中两个数据元素具有相同的值，在排序前后它们的相互位置发生颠倒，则称该排序算法是不稳定的。（）就是不稳定的排序方法。

（4）线性表是具有n个（）的有限序列（ n>0）.

(5)设无向图的顶点个数为n，则该图最多有（）条边。

[供选择的答案]

A:（1）链头（2）链尾（3）链中

B:（1）起泡排序（2）快速排列（3）Shell排序（4）堆排序（5）简单选择排序

C:（1）起泡排列（2）归并排列（3）Shell排列（4）直接插入排列（5）简单选择排序D:（1）表元素（2）字符（3）数据元素（4）数据项（5）信息项

E: (1) n-1 (2) n(n-1) (3) n(n+1)/2 (4) 0 (5) n.*n

二、双端队列（deque）是一个可以在任一端进行插入和删除的线性表。现采用一个一维数

组作为双端队列的数据存储结构，使用类Pascal语言描述如下

const maxsize=32; {数组中可容纳的元素个数}

type deque=record

elem: array[0..maxsize-1]of datatype; {环形队列的存放数组}

end1,end2:0..maxsize; {环形数组的两端}、

end;

试编写两个算法add(Qu:duque;x:datatype;tag:0..i)和delete（Qu:duque; var x:datatype; tag:0..1）用以在此两端队列的任一端进行插入和删除。当tag=0时在左端 endl端操作，当tag=1时在右端end2端操作。（10分）

三、已知一个大小为512个字长的存储，假设先后有6个用户申请大小分别为23，45，52，100，11和19的存储空间，然后再顺序释放大小为45，52，11的占用块。假设以伙伴系统实现动态存储管理。

（1）画出可利用空间表的初始状态。（5分）

（2）画出为6个用户分配所需要的存储空间后可利用空间表的状态以及每个用户所得到的存储块的起始地址。（5分）

（3）画出在回收3个占用块之后可利用空间表的状态。（5分）

四、（1）设T是具有n个内结点的扩充二叉树，I是它的内路径长度，E是它的外路径长

度。试利用归纳法证明E=I+2n., n>=0.（5分）

（2）利用（1）的结果试说明：成功查找的平均比较次数s与不成功查找的平均比较次数u 之间的关系可用公式表示s=(1+1/n)u-1,n>=1. (5分)

五、使用散列函数hashf(x)=x mod 11,把一个整数值转换成散列表下标，现要把数据1,13,12,34,38,33,27,22插入到散列表中。

（1）使用线性表探查再散列表中来构造散列表。（5分）

（2）使用链地址法构造散列表。（5分）

针对这两种情况，确定其装填因子，查找成功的平均探查次数，以及查找不成功所需的平均查看次数。（5分）六、给定整型数组B[0..m,0..n] 。已知B 中数据在每一维方向上都按从小到大的次序排列，

且整型变量x在B中存在。试设计一个程序段找出一对满足B[i,j]=x的(i,j)值，要求比较次数不超过m+n. （10）

七、如下所示的连通图，请画出

（1）已顶点（1）为根的深度优先生成树（5分）

（2）如果有关节点，请找出所有的关节点（5分）

八、设目标为t=”abcaabbabcabaacbacba”,模式为p=”abcabaa:.

（1）计算模式p的naxtval函数值

（2）不写出算法,只画出利用KMP算法进行模式匹配时每一趟的匹配过程。（5）九、设有13个初始归并段,其长度分别为28,16,37,42,5,9,13,14,20,17,30,12,18.试画出4路归

并时的最佳并树并计算它的带权路径长度WPL. （10分）。下载本文