一、在供选择的答案中选择与下列各括号中内容相匹配的答案，把其编号与其括号的标识对应起来(单选，每个答案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分)

[1]  [2]