发布时间 : 星期日 文章自考数据结构02331历年试题及答案(2009--2015个人整理版) - 图文更新完毕开始阅读f39217d870fe910ef12d2af90242a8956aecaa04
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) (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); substr(s,s,2,strlen(s)-1); f31(s); return strcat(s,t); } main( ) { char str[100]= ''String''; printf(''%s\\n'',f31(str)); } (1)请写出执行该程序后的输出结果; (2)简述函数f31的功能。 32.下面程序实现插入排序算法。 typedef struct{ int key; Info otherinfo; }SeqList; void InsertSort(SeqList R[],int n) {/* 待排序列保存在R[1..n]中*/ 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) (2) (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) { if (head->data>A&&head->data p=head; head=head->next; } if (p !=NULL) printf(\ } (1)已知链表h如下图所示,给出执行f33(h,5,8)之后的输出结果; (2)简述算法f33的功能。 五、算法设计题(本题10分) 34.已知二叉树的定义如下: typedef struct node{ int data; struct node *lchild, *rchild; }*Bitptr; 编写递归算法求二叉树的高度。函数原型为:int f34(Bitptr t);