数据结构试卷答案

《数据结构试卷答案》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、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. 

2、      哈夫曼树略，WPL=783.3.       (18,5,16,19,21,23)，(5，16，21，19，18，23)4.4.       线性探测：链地址法：5.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.t

3、op=-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,*rchi

4、ld;}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);}1.3.       设计判断一棵二叉树是否是二叉排序树的算法。intminnum=-32768,flag=1;typedefstructnode{intkey;structnode*lchild,*rchild

5、;}bitree;voidinorder(bitree*bt){if(bt!=0){inorder(bt->lchild);if(minnum>bt->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.

6、       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. 

7、      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(ix)