while (++i<=x)
if (n%i==0) break; if (i>x) return 1; else return 0; }
(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)); }
yxh：(1)q中的元素为(8,7,5,4,2); (2)把队列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; //q为头结点
if (__q->next==q ________) //rear-> next== rear printf( “it is empty!\\n” ); else { p=q->next; x=p->data;
___q->next=p->next______________ ; //删除首元结点 if (_q->next==q__________) rear=q; //空，或rear== p 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) ; p=L->next
Lc=(LinkList) malloc(sizeof(ListNode)); Lc->next=Lc; while(p!=L) if(p->data>c) {
pre->next=p->next;
(2) ; p->next=Lc->next Lc->next=p; p=pre->next; } else {
pre=p;
(3) ; p=p->next } return Lc; }
5、已知图的邻接链表的顶点表结点结构为
边表结点EdgeNode的结构为
下列算法计算有向图G中顶点vi的入度。请在空缺处填入合适的内容，使其成为一个完整的算法。 int FindDegree(ALGraph *G,int i)//ALGraph为图的邻接表类型 {
int dgree, j; EdgeNode *p;
degree= (1) ; 0 for(j=0;j
p=G->adjlist［j］. firstedge; while ( (2) ) p {
if( (3) ) p->adjvex==i {
degree++; break; }
p=p->next;
adjvex next vertex firstedge } }
return degree; }
六 简单应用题
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
5、哈夫曼树在构造时，首先进行初始化存储空间，结果如左下图，当构造完成后，请填写最后状态表，如 A(0) 1 2 3 A(1) 1 2 3 A(2) 1 2 3 A(3) 1 2 3 PATH(0) 1 2 3 PATH(1) 1 2 3 PATH(2) 1 2 3 PATH(3) 1 2 3 右下图。
weight Parent
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
5 29 7 8 14 23 3 11 -- -- -- -- -- -- -- Lchild Rchild 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
weight Parent
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Lchild Rchild 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
6、考虑右图：
(1)从顶点A出发，求它的深度优先生成树(4分) (2)从顶点E出发，求它的广度优先生成树(4分)
(3）根据普利姆(Prim) 算法，求它的最小生成树(请画出过程)
(设该图用邻接表存储结构存储，顶点的邻接点按顶点编号升序排列)(6分)
答案如下：