數(shù)據(jù)結(jié)構(gòu)試卷答案

1、1.數(shù)據(jù)結(jié)構(gòu)試卷（一）參考答案數(shù)據(jù)結(jié)構(gòu)試卷（一）參考答案一、選擇題一、選擇題1.C2.C3.D4.C5.A6.C7.C8.B9.B10.B二、填空題二、填空題1.1.(F1)%m2.2.O(n)，O(n)3.3.2n，n14.4.snext=pnextsnext=s5.5.n2e6.6.m=2e7.7.CBA8.8.4，169.9.ij1，010.10.n1三、應(yīng)用題三、應(yīng)用題1.1.鏈式存儲結(jié)構(gòu)略，前序ABDEC，中序DBEAC，后序

2、DEBCA。2.2.哈夫曼樹略，WPL=783.3.(18516192123)，(5，16，21，19，18，23)4.4.線性探測：6827322510876543210??鏈地址法：276832251086543210????????????hhhhhhh5.5.深度：125364，廣度：123456，最小生成樹T的邊集為E=(1，4)，(1，3)，(3，5)，(5，6)，(56)四、算法設(shè)計題四、算法設(shè)計題1.1.設(shè)計判斷單鏈表中

3、結(jié)點是否關(guān)于中心對稱算法。typedefstructints[100]inttopsqstackintlklistsymmetry(lklisthead)sqstackstackstack.top=1lklistpf(p=headp!=0p=pnext)stack.topstack.s[stack.top]=pdataf(p=headp!=0p=pnext)if(pdata==stack.s[stack.top])stack.top=s

4、tack.top1elsereturn(0)return(1)2.2.設(shè)計在鏈式存儲結(jié)構(gòu)上建立一棵二叉樹的算法。typedefdatatypetypedefstructnodedatatypedatastructnodelchildrchildbitreevoidcreatebitree(bitreescanf(“%c“f(q=hbq!=0q=qnext)if(qdata==pdata)breakif(q!=0)t=(lklist)ma

5、lloc(sizeof(lklist))tdata=pdatatnext=hchc=t數(shù)據(jù)結(jié)構(gòu)試卷（三）參考答案數(shù)據(jù)結(jié)構(gòu)試卷（三）參考答案一、選擇題一、選擇題1.B2.B3.A4.A5.A6.B7.D8.C9.B10.D第3小題分析：首先用指針變量q指向結(jié)點A的后繼結(jié)點B，然后將結(jié)點B的值復(fù)制到結(jié)點A中，最后刪除結(jié)點B。第9小題分析：9快速排序、歸并排序和插入排序必須等到整個排序結(jié)束后才能夠求出最小的10個數(shù)，而堆排序只需要在初始堆的基

6、礎(chǔ)上再進行10次篩選即可，每次篩選的時間復(fù)雜度為O(log2n)。二、填空題二、填空題1.1.順序存儲結(jié)構(gòu)、鏈式存儲結(jié)構(gòu)2.2.9，5013.3.54.4.出度，入度5.5.06.6.e=d7.7.中序8.8.79.9.O(1)10.10.i2，2i111.11.(5，16，71，23，72，94，73)12.12.(1，4，3，2)13.13.j1，hashtable[j].key==k14.14.return(t)，t=trchil

7、d第8小題分析：二分查找的過程可以用一棵二叉樹來描述，該二叉樹稱為二叉判定樹。在有序表上進行二分查找時的查找長度不超過二叉判定樹的高度1log2n。三、算法設(shè)計題三、算法設(shè)計題1.1.設(shè)計在單鏈表中刪除值相同的多余結(jié)點的算法。typedefintdatatypetypedefstructnodedatatypedatastructnodenextlklistvoiddelredundant(lklistf(p=headp!=0p=pne

8、xt)f(q=pnexts=qq!=0)if(qdata==pdata)snext=qnextfree(q)q=snextelses=qq=qnext2.2.設(shè)計一個求結(jié)點x在二叉樹中的雙親結(jié)點算法。typedefstructnodedatatypedatastructnodelchildrchildbitreebitreeq[20]intr=0f=0flag=0voidpreder(bitreebtx)if(bt!=0returnel

9、ser=(r1)%20q[r]=btpreder(btlchildx)preder(btrchildx)voidparent(bitreebtx)intipreder(btx)f(i=f1ilchilddata==x||q[i]rchilddata)breakif(flag==0)printf(“notfoundxn“)elseif(idata)elseprintf(“notparent“)數(shù)據(jù)結(jié)構(gòu)試卷（四）參考答案數(shù)據(jù)結(jié)構(gòu)試卷（四）參