template
void LinkList
2．(8分)下面是一个二叉树的前序遍历的递归算法，试改写此算法，消去第二个递归调用PreOrder(T->rchild,Visit)。
template
void BiTree
Visit(T->data);
PreOrder(T->lchild,Visit); PreOrder(T->rchild,Visit); }//if
}//PreOrder
模拟试卷七参考答案
一、单项选择题（在每小题的四个备选答案中，选出一个正确的答案，并将其号码填在题干后的括号内。每小题1分，共10分）
1．B） 2．D） 3．B） 4．C） 5．C）
6．C）
7．C）
8．C）
9．C）
10．D）
二、填空题（每空1分，共15分） 1．参考答案：引用型 2．参考答案：O(n4) 3．参考答案：112
4．参考答案：线性结构 5．参考答案：O(n) 6．参考答案：栈顶
栈顶指针
7．参考答案：3 x 2 + * 5 - 8．参考答案：4 9 9．参考答案：n-1
10．参考答案：邻接知阵 11．参考答案：插入
邻接表
12．参考答案：4
三、判断改错题（判断正误，将正确的划上“√”，错误的划上“×”，每小题1分，共10分）
1．参考答案：√
2．参考答案：× 3．参考答案：√ 4．参考答案：√ 5．参考答案：× 6．参考答案：× 7．参考答案：× 8．参考答案：× 9．参考答案：×
5
10．参考答案：√
四、简答题（每小题4分，共20分） 1．参考答案：在双向循环链表中p所指结点之后插入s所指结点的指针变化图示如下：
出语句序列如下： p->next->priou=s; s->next=p->next; s->priou=p;
p->next=s;
2．参考答案：（只要考生正确写出其中任四步即给满分）本题用Kruskal算法构造出最小生成树共需五步，具每一步的变化情况如如：
3．参考答案：
4．参考答案：
6
5．参考答案：如下图所示：
五、算法题（共25分） 1．参考答案：Visit(T->data) QueueEmpty(Q) DlQueue(Q,p) 2．参考答案：p->next e
q UNSUCCESS
3．（1）参考答案：求图中入度为零的顶点数。 （2）参考答案：图中入度为零的顶点数。 （3）参考答案：2
六、写算法（共20分） 1．参考答案：
template
void LinkList
if(la->next){ q=la->next->next; la->next->next=NULL; while(q){
pre=la;p=la->next;x=q->data; while(p && x>=p->data){ pre=p; p=p->next; }//while
p->rchild 7
t=q; q=q->next; pre->next=t; t->next=p; }//while }//if
}//StraitInsertSort 2．参考答案：
template
void BiTree
visit(T->data); PreOrder(T->lchild,Visit); T=T->rchild; }//while
}//PreOrder
模拟试卷八
一、 单项选择题(在下列每小题四个备选答案中选出一个正确答案，并将其字
母标号填入题干的括号内。每小题2分，共30分)
1．若给定有n个元素的向量，则建立一个有序单向链表的时间复杂性的量级是( )
A．O(1) B．O(n)
C．O(n2) D．O(nlog2n)
2．在一个具有n个结点的单链表中查找值为m的某结点，若查找成功，则平均比较( )个结点。
A．n B．n／2 C．(n-1)／2 D．(n+1)／2 3．研究数据结构就是研究( ) A．数据的逻辑结构 B．数据的存储结构
C．数据的逻辑结构和存储结构
D．数据的逻辑结构、存储结构及其数据在运算上的实现
4．为了方便地对图状结构的数据进行存取操作，则其数据存储结构宜采用( )方式。 A．顺序存储 B．链式存储 C．索引存储 D．散列存储
5．二维数组A[10．．20，5．．10]采用行序为主序方式存储，每个数据元素占4个存储单元，且[A10，5]的存储地址是1000，则A[18，9]的地址是( ) A．1208 B．1212 C．1368 D．1364
8
