（3）对于有n个顶点的有向图，由弗洛伊德（Floyd）算法求每一对顶之间的最短路径的时间复杂度是（ ）。 A）O(1)
（4）对n个记录的文件进行快速排序，所需要的辅助存储空间为（ ）。 A）O（1）
B）O（log2n）
C）O（n）
D）O（n2）
（5）哈夫曼树中一定不存在（ ）。 A）度为0的结点
B）度为1的结点
C）度为2的结点 D）带权的结点
（6）设D={A,B,C,D}，R={
（7）（ ）关键码序列不符合堆的定义。 A）A、C、D、G、H、M、P、Q、R、X B）A、C、M、D、H、P、X、G、Q、R C）A、D、P、R、C、Q、X、M、H、G D）A、D、C、M、P、G、H、X、R、Q
（8）假定关键字K=442205883，允许存储地址为四位十进制数，并且Hash地址为6111，则所采用的构造Hash函数的方法是（ ）。
A）直接定址法 B）平方取中法 C）除留余数法，模为97 D）折叠法
（9）在算法的时间复杂度中，n表示问题规模，f(n)表示基本操作重复执行的次数，则随问题的规模n的增大，算法执行时间的增长率同（ ）相同。 A）f(n)
B）n
C）O(n)
D）前面都不正确
B）O(n)
C）O(n)
D）O(n3)
（10）对线性表进行二分法查找，其前提条件是（ ）。 A）线性表以顺序方式存储，并且按关键码值排好序
B）线性表以顺序方式存储，并且按关键码值的检索频率排好序 C）线性表以链接方式存储，并且按关键码值排好序
D）线性表以链接方式存储，并且按关键码值的检索频率排好序
二、（本题8分）
在如下表所示的数组A中链接存储了一个线性表，表头指针存放在A[0].next，试写出该线性表。 线性表
A Data next
0 4 1 60 0 2 50 5 3 78 2 4 90 7 5 34 1 6 7 40 3 三、（本题8分）
已知一棵二叉树的前序遍历的结果是ABKCDFGHIJ，中序遍历的结果是KBCDAFHIGJ，试画出这棵二叉树。
五、（本题8分）
向最小根堆中依次插入数据4, 2, 5, 8, 3, 6, 10, 1时，画出每插入一个数据后堆的变化。
八、（本题8分）
给出一组关键字29、18、25、47、58、12、51、10，分别写出按下列各种排序方法进行排序时的变化过程：
（1）归并排序，每归并一次书写一个次序。
（2）快速排序，每划分一次书写一个次序以及最后排好序后的序列。 （2）快速排序： (10,18,25,12)29(58,51,47) (10(18,25,12)29((47,51)58) (10((12)18(25))29((47(51))58)
(10,12,18,25,29,47,51,58)
（3）堆排序，先建成一个堆，然后每从堆顶取下一个元素后，将堆调整一次。
九、（本题9分）
试分别画出具有3个结点的树和具有3个结点的二叉树的所有不同形态。
十、（本题15分）
设计以单链表存储的两个集合求交集的算法。
【答案】==================================
一、单项选择题（每小题 2 分，共20分） （1）A （6）B
（2）C （7）C
（3）D （8）D
（4）B （9）A
（5）B （10）A
二、（本题8分）
线性表为：(90,40,78,50,34,60) 三、（本题8分）
五、（本题8分） 如下图所示：
八、（本题8分） 变化过程如下：
（1）归并排序： (l8,29)(25,47)(12,58)(l0,51) (l8,25,29,47)(10,12,51,58)
(l0,12,18,25,29,47,51,58)
（2）快速排序： (10,18,25,12)29(58,51,47) (10(18,25,12)29((47,51)58)
(10((12)18(25))29((47(51))58) (10,12,18,25,29,47,51,58)
（3）堆排序： 初始堆（大顶推）：(58,47,51,29,18,12,25,10) 第一次调整：(51,47,25,29,18,12,10)(58) 第二次调整：(47,29,25,10,18,12)(51,58) 第三次调整：(29,18,25,10,12)(47,51,58) 第四次调整：(25,18,12,10)(29,47,51,58) 第五次调整：(l8,10,12)(25,29,47,51,58) 第六次调整：(l2,10)(18,25,29,47,51,58) 第七次调整：(l0,12,18,25,29,47,51,58) 九、（本题9分）
具有3个结点的树的不同形态如下图所示。
具有3个结点的二叉树的不同形态如下图所示。
十、（本题15分）
用单链表lc表示集合 C。分别将la中元素取出，再在lb中进行查找，如在lb中出现，则将其插入到lc中。
C语言版测试程序见exam6\\10c，具体算当如下：
void interaction(LinkList la,LinkList lb,LinkList &lc) // {
LinkList pa,pb,pc;
lc=new LNode;
//生成lc的头结点
将链表la与lb中共同出现的元素插入到链表lc中
pc=lc;
//pc永远指向lc的尾结点
//pa指向la的第一个元素
pa=la->next;
while(pa)
{
pb=lb->next;
while(pb&&pb->data!=pa->data)
pb=pb->next;
//在pb中定位pa->data
//定位成功
if(pb)
}
{ }
//pc为尾结点，其后继为空
pc->next=new LNode; pc=pc->next;
//生成lc新的尾结点
//pc指向新的尾结点
pc->data=pa->data; }
pa=pa->next;
//将pa->data复制到pc中
pc->next=NULL;