您好,欢迎访问三七文档
1.数据结构试卷(一)参考答案一、选择题1.C2.C3.D4.C5.A6.C7.C8.B9.B10.B二、填空题1.1.(F+1)%m2.2.O(n),O(n)3.3.2n,n+14.4.s-next=p-next;s-next=s5.5.n,2e6.6.m=2e7.7.CBA8.8.4,169.9.i-j+1,010.10.n-1三、应用题1.1.链式存储结构略,前序ABDEC,中序DBEAC,后序DEBCA。2.2.哈夫曼树略,WPL=783.3.(18,5,16,19,21,23),(5,16,21,19,18,23)4.4.线性探测:6827322510876543210链地址法:276832251086543210hhhhhhh5.5.深度:125364,广度:123456,最小生成树T的边集为E={(1,4),(1,3),(3,5),(5,6),(5,6)}四、算法设计题1.1.设计判断单链表中结点是否关于中心对称算法。typedefstruct{ints[100];inttop;}sqstack;intlklistsymmetry(lklist*head){sqstackstack;stack.top=-1;lklist*p;for(p=head;p!=0;p=p-next){stack.top++;stack.s[stack.top]=p-data;}for(p=head;p!=0;p=p-next)if(p-data==stack.s[stack.top])stack.top=stack.top-1;elsereturn(0);return(1);}2.2.设计在链式存储结构上建立一棵二叉树的算法。typedefchardatatype;typedefstructnode{datatypedata;structnode*lchild,*rchild;}bitree;voidcreatebitree(bitree*&bt){charch;scanf(%c,&ch);if(ch=='#'){bt=0;return;}bt=(bitree*)malloc(sizeof(bitree));bt-data=ch;createbitree(bt-lchild);createbitree(bt-rchild);}3.3.设计判断一棵二叉树是否是二叉排序树的算法。intminnum=-32768,flag=1;typedefstructnode{intkey;structnode*lchild,*rchild;}bitree;voidinorder(bitree*bt){if(bt!=0){inorder(bt-lchild);if(minnumbt-key)flag=0;minnum=bt-key;inorder(bt-rchild);}}数据结构试卷(二)参考答案一、选择题1.D2.B3.C4.A5.A6.C7.B8.C二、填空题1.1.构造一个好的HASH函数,确定解决冲突的方法2.2.stack.top++,stack.s[stack.top]=x3.3.有序4.4.O(n2),O(nlog2n)5.5.N0-1,2N0+N16.6.d/27.7.(31,38,54,56,75,80,55,63)8.8.(1,3,4,2),(1,3,2,4)三、应用题1.1.(22,40,45,48,80,78),(40,45,48,80,22,78)2.2.q-llink=p;q-rlink=p-rlink;p-rlink-llink=q;p-rlink=q;3.3.2,ASL=91*1+2*2+3*4+4*2)=25/94.4.树的链式存储结构略,二叉树略5.5.E={(1,3),(1,2),(3,5),(5,6),(6,4)}6.6.略四、算法设计题1.1.设有一组初始记录关键字序列(K1,K2,…,Kn),要求设计一个算法能够在O(n)的时间复杂度内将线性表划分成两部分,其中左半部分的每个关键字均小于Ki,右半部分的每个关键字均大于等于Ki。voidquickpass(intr[],ints,intt){inti=s,j=t,x=r[s];while(ij){while(ij&&r[j]x)j=j-1;if(ij){r[i]=r[j];i=i+1;}while(ij&&r[i]x)i=i+1;if(ij){r[j]=r[i];j=j-1;}}r[i]=x;}2.2.设有两个集合A和集合B,要求设计生成集合C=A∩B的算法,其中集合A、B和C用链式存储结构表示。typedefstructnode{intdata;structnode*next;}lklist;voidintersection(lklist*ha,lklist*hb,lklist*&hc){lklist*p,*q,*t;for(p=ha,hc=0;p!=0;p=p-next){for(q=hb;q!=0;q=q-next)if(q-data==p-data)break;if(q!=0){t=(lklist*)malloc(sizeof(lklist));t-data=p-data;t-next=hc;hc=t;}}}数据结构试卷(三)参考答案一、选择题1.B2.B3.A4.A5.A6.B7.D8.C9.B10.D第3小题分析:首先用指针变量q指向结点A的后继结点B,然后将结点B的值复制到结点A中,最后删除结点B。第9小题分析:9快速排序、归并排序和插入排序必须等到整个排序结束后才能够求出最小的10个数,而堆排序只需要在初始堆的基础上再进行10次筛选即可,每次筛选的时间复杂度为O(log2n)。二、填空题1.1.顺序存储结构、链式存储结构2.2.9,5013.3.54.4.出度,入度5.5.06.6.e=d7.7.中序8.8.79.9.O(1)10.10.i/2,2i+111.11.(5,16,71,23,72,94,73)12.12.(1,4,3,2)13.13.j+1,hashtable[j].key==k14.14.return(t),t=t-rchild第8小题分析:二分查找的过程可以用一棵二叉树来描述,该二叉树称为二叉判定树。在有序表上进行二分查找时的查找长度不超过二叉判定树的高度1+log2n。三、算法设计题1.1.设计在单链表中删除值相同的多余结点的算法。typedefintdatatype;typedefstructnode{datatypedata;structnode*next;}lklist;voiddelredundant(lklist*&head){lklist*p,*q,*s;for(p=head;p!=0;p=p-next){for(q=p-next,s=q;q!=0;)if(q-data==p-data){s-next=q-next;free(q);q=s-next;}else{s=q,q=q-next;}}}2.2.设计一个求结点x在二叉树中的双亲结点算法。typedefstructnode{datatypedata;structnode*lchild,*rchild;}bitree;bitree*q[20];intr=0,f=0,flag=0;voidpreorder(bitree*bt,charx){if(bt!=0&&flag==0)if(bt-data==x){flag=1;return;}else{r=(r+1)%20;q[r]=bt;preorder(bt-lchild,x);preorder(bt-rchild,x);}}voidparent(bitree*bt,charx){inti;preorder(bt,x);for(i=f+1;i=r;i++)if(q[i]-lchild-data==x||q[i]-rchild-data)break;if(flag==0)printf(notfoundx\n);elseif(i=r)printf(%c,bt-data);elseprintf(notparent);}数据结构试卷(四)参考答案一、选择题1.C2.D3.D4.B5.C6.A7.B8.A9.C10.A二、填空题1.1.O(n2),O(nlog2n)2.2.pllink-rlink=p-rlink;p-rlink-llink=p-rlink3.3.34.4.2k-15.5.n/26.6.50,517.7.m-1,(R-F+M)%M8.8.n+1-i,n-i9.9.(19,18,16,20,30,22)10.10.(16,18,19,20,32,22)11.11.A[i][j]=112.12.等于13.13.BDCA14.14.hashtable[i]=0,hashtable[k]=s三、算法设计题1.1.设单链表中有仅三类字符的数据元素(大写字母、数字和其它字符),要求利用原单链表中结点空间设计出三个单链表的算法,使每个单链表只包含同类字符。typedefchardatatype;typedefstructnode{datatypedata;structnode*next;}lklist;voidsplit(lklist*head,lklist*&ha,lklist*&hb,lklist*&hc){lklist*p;ha=0,hb=0,hc=0;for(p=head;p!=0;p=head){head=p-next;p-next=0;if(p-data='A'&&p-data='Z'){p-next=ha;ha=p;}elseif(p-data='0'&&p-data='9'){p-next=hb;hb=p;}else{p-next=hc;hc=p;}}}2.2.设计在链式存储结构上交换二叉树中所有结点左右子树的算法。typedefstructnode{intdata;structnode*lchild,*rchild;}bitree;voidswapbitree(bitree*bt){bitree*p;if(bt==0)return;swapbitree(bt-lchild);swapbitree(bt-rchild);p=bt-lchild;bt-lchild=bt-rchild;bt-rchild=p;}3.3.在链式存储结构上建立一棵二叉排序树。#definen10typedefstructnode{intkey;structnode*lchild,*rchild;}bitree;voidbstinsert(bitree*&bt,intkey){if(bt==0){bt=(bitree*)malloc(sizeof(bitree));bt-key=key;bt-lchild=bt-rchild=0;}elseif(bt-keykey)bstinsert(bt-lchild,key);elsebstinsert(bt-rchild,key);}voidcreatebsttree(bitree*&bt){inti;for(i=1;i=n;i++)bstinsert(bt,random(100));}数据结构试卷(五)参考答案一、选择题1.A2.B3.A4.A5.D6.B7.B8.B9.C10.C二、填空题1.1.top1+1=top22.2.可以随机访问到任一个顶点的简单链表3.3.i(i+1)/2+j-14.4.FILO,FIFO5.5.ABDECF,DBEAFC,DEBFCA6.6.8,647.7.出度,入度8.8.ki=k2i&&ki=k2i+19.9.n-i,r[j+1]=r[j]10.10.mid=(low+high)/2,r[mid].keyk三、应用题1.1.DEBCA2.2
本文标题:数据结构试卷答案
链接地址:https://www.777doc.com/doc-1818973 .html