1（16分）
填空

①设只包含要根结点的二*树的高度为0，则高度为k的二*树的最大结点数为，最小结点数为。

②某二*树结点的对称序序列为A，B，C，D，E，F，G，后序序列为B，D，C，A，F，G，E，则该二*树结点的前序序列为，该二*树对应的树林包括棵树。

③求具有最小带权外部路径长度的扩充二*树的算法称为算法，对于给出的一组权W={10，12，16，21，30}，通过该算法求出的扩充二*树的带权外部路径长度为。

④设有关键码序列（Q，H，C，Y，Q，A，M，S，R，D，F，X），要按照关键码值递增的次序进行排序，若采用初始步长为4的Shell排序法，则一趟扫描的结果是；若采用以第一个元素为分界元素的快速排序法，则一趟扫描的结果是。

2（10分）

请简要回答下列问题

①什么是抽象数据类型？试举一例说明之。

②什么是广义表？请简述广义表与线性表的主要区别。

3（6分）

给定关键码序列（26，25，20，33，21，24，45，204，42，38，29，31），要用散列法进行存储，规定负载因子a=0.6。

①请给出除余法的散列函数。

②用开地址线性探查法解决碰撞，请画出插入所有的关键码后得到的散列表，并指出发生碰撞的次数。

4（6分）

本题要求在检索各结点的概率不相等的条件下构造最佳二*排序树。给出关键码集合

{B,E,H}

key1key2key3

以及权的序列

(9458613)

p1p2p3q0q1q2q3

请构造最佳二*排序树。

5（12分）

①请画出往图1的5阶B-树中插入一个关键码390后得到的B-树，以及再删除关键码150后得到的B-树。

②包括n个关键码的m阶B-树在一次检索中最多涉及多少个结点？（要求写出推导过程）


图1题5图

6（10分）

如图2所示是一棵正在进行插入运算的AVL树，关键码70的插入使它失去了平衡，按照AVL树的插入方法，需要对它的结构进行调整以恢复平衡。

①请画出调整后的AVL树。

②假设AVL树用llink-rlink法存储，T是指向根结点的指针、请用PASCAL（或C）语句表示出这个高速的过程。

（说明：不必写出完整的程序，只需用几个语句表示出在本题所给的具体情况下调整过程中指针的变化。在调整过程中还有两个指针变量p和q可以使用）。


图2题6图

7（16分）

请仔细阅读下面的堆排序算法。待排序记录存储在一维数组中，说明如下：

TYPEnode=RECORD

key:integer;

info:datatype

END

heaptype=ARRAY[1..n0]OFnode;

过程heapsort的功能是将数组heap中的前n个记录按关键码值递减的次序排序。heapsort调用sift,sift的参数heap,h和r具有如下的含义：调用sift时，以heap[h 1],heap[h 2],……，heap[r/2]为根的子树已经是堆；sift执行后，以heap[h],heap[h 1],heap[h 2],……heap[r/2]为根的子树都成为堆。

PROCEDUREsift(VARheap:heaptype;h,r:integer);

VARi,j:integer;

x:node;

finish:boolean;

BEGIN

i:=h;

x:=heap[i];

j=2*i;

finish:=false;



WHILEDO

BEGIN

IF(jheap[j 1].key)

THENj:=j 1;

IFx.key>heap[j].key

THENBEGIN



END

ELSEfinish:=true;

END;



END;

PROCEDUREheapsort(VARheap:heaptype;n:integer);

VARh,r,i,j:integer;

x:node;

BEGIN

FORh:=nDIV2DOWNTO1DO



FORr:=nDOWNTO2DO

BEGIN

x:=heap[1];

heap[1]:=heap[r];

heap[r]:=x;



END

END;

①请在sift过程和heapsort过程的空缺处填入适当内容，使它们能正确工作。

②若调用heapsort的参数值n=10，那么在heapsort的执行过程中sift过程被调用了多少次？

8（24分）

试设计一个算法解决地图着色判断问题。

设一幅地图有n个区域（例如，省）。用不多于4种颜色对这些区域进行着色，着色应满足的要求是相邻的区域具有不同的颜色。你的算法以一种着色方案（即哪一个区域着什么颜色）为输入，算法对该着色方案进行考察，若满足着色要求，则输出true,否则输出false。

①用自然语言和PASCAL（或C）语言描述你为解决问题而设计的数据结构（逻辑结构，存储结构）。数据结构的设计应考虑对问题的清楚描述和算法的效率。