数据结构(代码02331)2010年10月试题及答案 下载本文

二叉树转换成森林 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页-