序排序，试编写此算法。算法申明如下：
template
void LinkList
2．(8分)下面是一个二叉树的中序遍历的递归算法，试改写此算法，消去第二个递归调用MidOrder(T->rchild,visit)。
template
void BiTree
MidOrder(T->lchild, Visit); Visit(T->data);
MidOrder(T->rchild, Visit); }//if
}//MidOrder
模拟试卷六参考答案
_
一、单项选择题（在每小题的四个备选答案中，选出一个正确的答案，并将其号码填在题干后的括号内。每小题1分，共10分）
1．B） 2．D） 3．B） 4．A） 5．D） 6．A） 7．B） 8．B） 9．D） 10．C） 二、填空题（每空1分，共15分） 1．参考答案：sizeof(LNode) 2．参考答案：O(n2)
3．参考答案：
n(n?1) 24．参考答案：(i-1)*n+j-1 5．参考答案：O(1) 6．参考答案：队尾 队头 7．参考答案：25 8．参考答案：n-1 n0= n2-1 9．参考答案：2
10．参考答案：n(n-1)/2 n(n-1)
11．参考答案：选择（直接选择排序或堆排序） 12．参考答案：操作
三、判断改错题（判断正误，将正确的划上“√”，错误的划上“×”，每小题1分，共10分）
1．参考答案：√ 2．参考答案：× 3．参考答案：× 4．参考答案：√ 5．参考答案：× 6．参考答案：√
26
7．参考答案：× 8．参考答案：× 9．参考答案：× 10．参考答案：×
四、简答题（每小题4分，共20分） 1．参考答案： s=new lnode; s->data=x; p->prior->next=s; s-prior=p->prior; s->next=p; p->prior=s; 2．参考答案：本题用Prim算法构造出最小生成树共需四步，具每一步的变化情况如如：
3．参考答案：
4．参考答案：哈夫曼树如下图所示：
WPL=20*2+15*2+14*2+7*3+3*4+4*4=147
27
5．参考答案：哈希表如下图所示：
五、算法题（共25分） 1．参考答案：T->lchild t->rchild Pop(S)
2．参考答案：e.key % m ++i UNSUCCESS e
3．(1)参考答案：
（2）参考答案：V1 V2 V4 V3
（3）参考答案：从顶点Vi出发进行深度优先搜索图。 六、写算法（共20分） 1．参考答案：
template
void LinkList
if(la->next){ p=la->next; while(p->next){ minp=p; q=p->next; while(q){
if(minp->data>q↑.data)minp=q; q=q->next; }//while if(minp!=p { x=p->data;
p->data=minp->data; minp->data:=x; }//if
p=p->next; }//while }//if
}//SimpleSelectSort
NULL
28
2．参考答案：
template
void BiTree
MidOrder(T->lchild, Visit); Visit(T->data); T=T->rchild; }//while
}//MidOrder
模拟试卷七
一、单项选择题（在每小题的四个备选答案中，选出一个正确的答案，并将其号码填在题干后的括号内。每小题1分，共10分）
1．假设执行语句S的时间为O（1），则执行下列程序段 for(i=1;i<=n;i++) for(j=i;j<=n;j++) S;
的时间为( )
A）O（n） B）O（n2） C）O（n*i） D）O（n+i） 2．设栈最大长度为3，入栈序列为1，2，3，4，5，6，则不可能的出栈序列是（ ）。
A）1，2，3，4，5，6 B）2，1，3，4，5，6 C）3，4，2，1，5，6 D）4，3，2，1，5，6
3．设单链表的结点结构为(data,next)，已知指针q所指结点是指针p所指结点的直接前驱，如在*q与*p之间插入结点*s，则应执行的操作为（ ）。
A）s->next=p->next; p->next=s; B）q->next=s; s->next=p; C）p->next=s-next; s->next=p; D）p->next=s; s-next=q; 4．串S='ABC DEF'的串长为（ ）。
A）3 B）4 C）7 D）8
5．下面二叉树按（ ）遍历得到的序列是FEDBIHGCA。
A）先序 C）后序
B）中序 D）层次
29
6．用Floyd算法求每一对顶点之间的最短路径的时间复杂度为（ ）。
A）O(n) B）O(n2) C）O(n3) D）O(nlogn)
7．具有n个顶点的无向图，它可能具有的边数的最大值为（ ）。
A）(n2+n)/2 B）n2 C）(n2-n)/2 D）n
8．二分查找法要求被查找的表是（ ）。
A）顺序表 B）链接表 C）顺序表且是按值递增或递减次序排列 D）不受上述的任何限制 9．在一待散列存储的线性表（18，25，63，50，42，32，90），若选用h(k)=k % 7作为散列函数，则与元素18冲突的元素有( )个。
A）0 B）1 C）2 D）3
10．在下列排序算法中，不稳定的是（ ）。
A）直接插入排序 B）折半插入排序 C）归并排序 D）直接选择排序 二、填空题（每空1分，共15分）
1．当一个传值型形式参数所占空间较大时，最好说明为( )，以节省参数值传输时间和存储参数的空间。
2．一个算法的时间复杂度为(5n6-3n2log2n+7n-9)/(3n2+1)，其数量级表示为( )。
3．有一矩阵为a[-3:1,2:6]，每个元素占一个存储单元，存储的首地址为100，以行序为主，则元素a(-1,4)的地址为（ ）。
4．一维数组的逻辑结构是（ ）。
5．在有n个结点的单链表la中，删除指定结点p的操作delete(la,p)的时间复杂度为（ ）。
6．栈的插入与删除操作在( )进行，出栈操作时，需要修改 ( )。 7．表达式3*(x+2) - 5的后缀表达式为（ ）。
8．对于一个具有9个结点的二叉树的最小深度为( )，最大深度为( )。
9．在一个具有n个顶点的无向图中，要连通所有顶点则至少需要( )条边。 10．表示图的最常用两种存储结构是( )与( )。
11．每次从无序表中取一个元素，把它插入到有序表中的适当位置，此种排序方法称为( )排序。
12．已知一有序表（13，20，25，37，48，58，61，78，83，90，128），当二分查找值48的元素时，经过（ ）次比较后查找成功。
三、判断改错题（判断正误，将正确的划上“√”，错误的划上“×”，每小题1分，共10分）
1．数据的逻辑结构是指数据元素之间的逻辑关系。 （ ） 2．数组不是一种随机存取结构。 （ ） 3．顺序表在物理存储空间中一定是连续的。 （ ） 4．设一个栈的入栈序列是ABCD，则借助于一个栈能得出栈序列ACDB。 （ ）
5．串的长度是指串中不同字符的个数。 （ ）
30