二叉树转换成森林 1） 抹线：将二叉树中根结点与其右孩子连线，及沿右分支搜索到的所有右孩子间连线全部抹掉，使之变成孤立的二叉树 2） 还原：将孤立的二叉树还原成树 将二叉树转换成树 1） 加线：若p结点是双亲结点的左孩子，则将p的右孩子，右孩子的右孩子，……沿分支找到的所有右孩子， 都与p的双亲用线连起来 2） 抹线：抹掉原二叉树中双亲与右孩子之间的连线 3） 调整：将结点按层次排列，形成树结构
请画出该二叉树对应的森林。
a a b e b e c f g c f g d h k d h k j j
a a e e b c d f h g k b c f g j d h k j
- 本套试题共分9页，当前页是第5页-
29.请回答下列问题：127
(1)英文缩写DAG的中文含义是什么？有向无环图（directed acyclic graph） (2)请给出下面DAG图的全部拓扑排序。
a bd c efg a bd cfeg adbcfeg adbcefg
四、算法阅读题（本大题共4小题，每小题5分，共20分）
30.已知线性表(a1,a2,a3...，an)按顺序存放在数组a中，每个元素均为整数，下列程序的功能是将所有小于0的元素移到全部大于等于0的元素之前。例如，有7个整数的原始序列为(x,x,-x,-x,x,x,-x)，变换后数组中保存的序列是(-x,-x,-x,x,x,x,x)。请在程序处填入合适的内容，使其成为完整的算法。 f30(int a［］，int n) { int k，m,temp；
m= (1) ；
while (a［m］<0 &&m m= (2) ； k=m; while (k { while(a［k］>=0&&k k= (3) ； if(k { temp=a［k］； a［k］=a［m］； a［m］= (4) ； m= (5) ； } } } (1) - 本套试题共分9页，当前页是第6页- （1）0 （2）m+1 （3）k+1 （4）temp （5）m+1 (2) (3) (4) (5) 31.阅读下列程序，并回答问题： #include substr(char*t,char*s,int pos,int len) { while（len>0&&*s） { *t=*(s+pos-l); t++;s++;len--; } *t='\\0'; } char *f31(char*s) { char t[100]; if (strlen(s)=1) return s; substr(t,s,1,1); t S t substr(s,s,2,strlen(s)-1); s tring ring f31(s); return strcat(s,t); } main( ) { char str[100]= ''String''; printf(''%s\\n'',f31(str)); } (1)请写出执行该程序后的输出结果； gnirtS (2)简述函数f31的功能。 将已知字符串首尾颠倒 32.下面程序实现插入排序算法。 typedef struct{ int key; Info otherinfo; }SeqList; void InsertSort(SeqList R［］,int n) {/* 待排序列保存在R［1..n］中*/ - 本套试题共分9页，当前页是第7页- r i ing ng n g SeqList x； int i，j，k，lo,hi,mi; for (i=2；i<=n；i++) { (1) ； lo=1； hi=i-l; while (lo<=hi) { mi=(lo+hi)/2; if ( (2) ) break; if (R［mi］.key>x.key) hi=mi-l; else lo=mi+l; } if (mi=lo) k=i - mi; else k=i - mi-1; for (j=0；j (3) ； R［i-j］=x； } } 在空白处填写适当的内容，使该程序功能完整。 (1) x=R[i].key (2) R[i].key== R[mi].key (3) 33.设有单链表类型定义如下：（单链表） typedef struct node { int data; struct node *next; } *LinkList; 阅读下列算法，并回答问题： void f33(LinkList head, int A, int B) { LinkList p=NULL; While (head !=NULL) { - 本套试题共分9页，当前页是第8页- if (head->data>A&&head->data p=head; head=head->next; } if (p !=NULL) printf(\ } (1)已知链表h如下图所示，给出执行f33(h，5，8)之后的输出结果；7 (2)简述算法f33的功能。 输出以head为头指针的链表中，最后一个数据值在A和B之间的节点的数值 五、算法设计题（本题10分） 34.已知二叉树的定义如下： typedef struct node{ int data; struct node *lchild, *rchild; }*Bitptr； 编写递归算法求二叉树的高度。函数原型为：int f34（Bitptr t）； /*计算机二叉树的高度*/ int treedepth(BiTree bt) { int hl,hr,max; if (bt!=NULL) { hl=treedepth(bt->lch); hr=treedepth(bt->rch); max=(hl>hr)?hl:hr; return(max+1); } else return(0); } - 本套试题共分9页，当前页是第9页-