(1)指出该算法的功能；
(2)该算法的时间复杂度是多少？ （期中试题）
5. 写出下述算法A的功能： 其中BiTree定义如下: Typedef struct BiTNode{
TElemType data;
struct BiTNode *LChild, *RChild; }BiTNode, *BiTree;
Status A(BiTree T) { Queue Q; InitQueue(Q); ENQueue(Q,T);
While(not QueueEmpty(Q)) { DeQueue(Q,e);
If(e==NULL) break; Else
{ Print(e.data);
ENQueue(Q,e.LChild); ENQueue(Q.e.RChild); }
} }
（期中试题）
6.阅读下列函数algo,并回答问题：
(1)假设队列q中的元素为(2,4,5,7,8),其中“2”为队头元素。写出执行函数调用algo(&q)
后的队列q；
(2)简述算法algo的功能。 void algo(Queue *Q) {
Stack S;
InitStack(&S);
while (!QueueEmpty(Q)) Push(&S, DeQueue(Q)); while (! StackEmpty(&S)) ＥnQueue(Q,Pop(&S)); }
（1）q=(8,7,5,4,2)
（2）算法利用栈S辅助实现队列Q的逆置。
五 算法填空
1、下面是在带表头结点的循环链表表示的队列上，进行出队操作，并将出队元素的值保留
在x中的函数，其中rear是指向队尾结点的指针。请在横线空白处填上适当的语句。 typedef struct node {
int data;
struct node *next; } lklist;
void del( lklist rear, int &x); { lklist p,q; q=rear-> next;
if (_q = = rear_________) printf( “it is empty!\\n” ); else {
p=q->next; x=p->data;
__q->next=p->next____________ ; if (_rear= =p__________) rear=q; free(p) ; }; };
2、堆分配存储方式下，串连接函数。（期中试题） typedef struct {
char * ch； int len； } HString；
HString *s， t;
Status StrCat(s， t) /* 将串t连接在串s的后面 */ {
int i;
char *temp;
f if (temp==NULL) return(0); for (i=0; ;i++) temp［i］=s->ch［i］;
for ( ;i
fr s->ch=temp; return(1); }
3、向单链表的末尾添加一个元素的算法。（期中试题） LNode是一个包含（data，Next）的结构体
Void InsertRear(LNode*& HL,const ElemType& item) {
LNode* newptr; newptr=new LNode;
If (______________________) {
cerr<<\exit(1); }
________________________=item; newptr->next=NULL; if (HL==NULL)
HL=__________________________; else{
LNode* P=HL;
While (P->next!=NULL) ____________________; p->next=newptr; }
}
4、L为一个带头结点的循环链表。函数f30的功能是删除L中数据域data的值大于c的所有结点，并由这些结点组建成一个新的带头结点的循环链表，其头指针作为函数的返回值。请在空缺处填入合适的内容，使其成为一个完整的算法。 LinkList f30(LinkList L, int c) {
LinkList Lc,p,pre; pre=L;
p= (1) ; Lc=(LinkList) malloc(sizeof(ListNode)); Lc->next=Lc; while(p!=L) if(p->data>c) {
pre->next=p->next; (2) ; Lc->next=p; p=pre->next; } else {
pre=p;
(3) ; } return Lc; }
(1)L->next;
(2)p->next=Lc->next; (3)p=p->next;
vertex firstedge 5、已知图的邻接链表的顶点表结点结构为
边表结点EdgeNode的结构为 adjvex next
下列算法计算有向图G中顶点vi的入度。请在空缺处填入合适的内容，使其成为一个完整
的算法。
int FindDegree(ALGraph *G,int i)//ALGraph为图的邻接表类型 {
int degree, j; EdgeNode *p;
degree= (1) ; for(j=0;j
p=G->adjlist［j］. firstedge; while ( (2) ) {
if( (3) ) {
degree++; break; }
p=p->next; } }
return degree; }
(1) 0 (2)p!=NULL; (3) p->adjvex= =i;
六 简单应用题
1、已知一个非空二元树，其按中根和后根遍历的结果分别为： 中根：C G B A H E D J F I 后根：G B C H E J I F D A
试将这样二元树构造出来;若已知先根和后根的遍历结果，能否构造这棵二元树，为什么?
若二叉树中各结点的值均不相同，则由二叉树的先序序列和中序序列，或由其后序序列和中序序列均能唯一地确定一棵二叉树；但由先序序列和后序序列却不一定能唯一地确定一棵二叉树。
由二叉树的前序序列和后序序列不能唯一确定一棵二叉树，因无法确定左右子树两部分。（因为前序序列的第一个元素是根结点，该元素将二叉树中序序列分成两部分，左边表示左子树，若左边无元素，则说明左子树为空；右边是右子树，若为空，则右子树为空。）例如，任何结点只有左子树的二叉树和任何结点只有右子树的二叉树，其前序序列相同，后序序列相同，但却是两棵不同的二叉树。
2、对于下图，画出按Kruskal（克鲁斯卡尔）算法和Prim（普里姆）算法构造最小生成树的过程。
（根据算法思想画）
3、画出由下面的二叉树转换成的森林。
（根据二叉树转换成的森林的方法画）
4、用Floyed（弗洛伊徳）算法求下图每一对顶点之间的最短路径及其长度，将计算过程的中间和最后结果填入下表：
A 1 2 3 PATH 1 2 3 A(0) 1 3 10 2 5 3 2 6 A(1) 1 3 10 2 5 3 2 5 A(2) 1 3 8 2 5 3 2 5 A(3) 1 3 8 2 7 5 3 2 5 PATH(0) 1 ba ca 2 cb 3 ac bc PATH(1) 1 ba ca 2 cb 3 ac bac PATH(2) 1 ba cba 2 cb 3 ac bac PATH(3) 1 ba cba 2 acb cb 3 ac bac