《算法與數(shù)據(jù)結(jié)構(gòu)》A卷

1、2011-2012（A）課程名稱 算法與數(shù)據(jù)結(jié)構(gòu)任課教師簽名 二維數(shù)A106采用行優(yōu)先的存儲(chǔ)方法，若每個(gè)元素4個(gè)存儲(chǔ)單元，已知素A34的存儲(chǔ)地址1000，則元A43的存儲(chǔ)地址()A. 1020B.1024C.1036D.1240用二叉鏈表表示具n個(gè)結(jié)點(diǎn)的二叉樹(shù)時(shí)，值為空的指針域的個(gè)數(shù)()出題教師簽2011計(jì)算機(jī)合作聯(lián)盟命題組審題教師簽名A. n-1B.n+lC.nD.2n考試方式（ 閉 ）卷適用專業(yè)10 計(jì)科1-2考試時(shí)間（110）分鐘題號(hào)題號(hào)得分一二三四五六七總分（注：判斷題和選擇題的答案寫(xiě)在答題紙上）一、單項(xiàng)選擇題（每小題 2 分，共 30 分）與數(shù)據(jù)元素本身的形式、內(nèi)容、相對(duì)位置、個(gè)數(shù)無(wú)

2、關(guān)的是數(shù)據(jù)(A.存儲(chǔ)結(jié)構(gòu)儲(chǔ)存實(shí)現(xiàn)C.邏輯結(jié)構(gòu)運(yùn)算實(shí)現(xiàn)和qs所指結(jié)點(diǎn)之后插入上述鏈表應(yīng)執(zhí)行的語(yǔ)句為()A.q-next=s-next；s-next=p；B.s-next=p；q-next=s-next；C.p-next=s-next；s-next=q；D.s-next=q；p-next=s-next；隊(duì)和棧的主要區(qū)別()A.邏輯結(jié)構(gòu)不同存儲(chǔ)結(jié)構(gòu)不同C.所包含的運(yùn)算個(gè)數(shù)不同限定插入和刪除的位置不同二叉樹(shù)中第5層上的結(jié)點(diǎn)個(gè)數(shù)最多()A.8B.16C.15D.32一棵完全二叉樹(shù)上有1001 個(gè)結(jié)點(diǎn)，其中葉子結(jié)點(diǎn)的個(gè)數(shù)(A 250 500 254D501若無(wú)向G含21條邊，G的頂點(diǎn)個(gè)數(shù)至少(A. 7B.

3、8C. 21D. 22若采用鄰接矩陣法存儲(chǔ)一個(gè)n 個(gè)頂點(diǎn)的無(wú)向圖，則該鄰接矩陣是一個(gè)(A. 上三角矩陣B. 稀疏矩陣C. 對(duì)角矩陣D. 對(duì)稱矩陣以 v1 為起始結(jié)點(diǎn)對(duì)下圖進(jìn)行深度優(yōu)先遍歷，正確的遍歷序列()Av1，v2，v3，v4，v5，v6，v7Cv1，v2，v3，v4，v7，v5，v6對(duì)表長(zhǎng)為n查找長(zhǎng)度()已知廣義表的表頭為a，表尾(b,c)，則此廣義表(A.(a,(b,c)B.(a,b,c)C.(a),b,c)D.(a,b,c)n-1nn12B.2C. 2D.n32的有序表中進(jìn)行二分查找，當(dāng)查找成功時(shí)和給定值進(jìn)行比較的關(guān)鍵1字個(gè)數(shù)最多()A. 4B. 5C.6D.71個(gè)元素為基準(zhǔn)的一次劃

4、分的結(jié)果為()A. (5，1，4，3，6，2，8，7)B.(5，1，4，3，2，6，7，8)C. (5，1，4，3，2，6，8，7)D.(8，7，6，5，4，3，2，1)15. 下列排序方法中穩(wěn)定的為()冒泡排序B.堆排序C. 希爾排序D.快速排序 二、填空題（本大題共10小題，每小題2分，若有兩個(gè)空格，每個(gè)空1分，共20分）請(qǐng)?jiān)诿總€(gè)空格中填上正確答案。錯(cuò)填、不填均無(wú)分。數(shù)據(jù)元素及其關(guān)系在計(jì)算機(jī)存儲(chǔ)器內(nèi)的表示稱。已知在結(jié)點(diǎn)個(gè)數(shù)大1的單循環(huán)鏈表中，指指向表中某個(gè)結(jié)點(diǎn)，則下列程段執(zhí)行結(jié)束時(shí)，指q指向結(jié)*p的結(jié)點(diǎn)。q=p;while (q-next!=p) q=q-next;假設(shè)和X分別表示進(jìn)棧和出

5、棧操作，由輸入序列得到輸出序列的操作序列則得的操作序列假設(shè)以行優(yōu)先順序?qū)⒁浑A的對(duì)角矩陣壓縮存儲(chǔ)到一維數(shù)中，則數(shù)Q大小至少。森林的中根遍歷序列正是相應(yīng)二叉樹(shù)遍歷序列，森林先根遍歷序列正是相應(yīng)二叉樹(shù)遍歷序列。一棵含999個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度。普里姆算法適用于網(wǎng)的最小生成樹(shù)魯斯卡爾）算法適用于網(wǎng)的最小生成樹(shù)。三、解答題（本大題共 4 小題，每小題 7 分，共 28 分）a,b,c,d,e,f,g0110，10，110，111，00，011101001) (1)） (2) 和 9曼樹(shù)的帶權(quán)路徑長(zhǎng)度WPL。（2 分）Prim（頂點(diǎn)B出發(fā)）求如下連通圖的最小生成樹(shù)，要求：畫(huà)出最小生（如第1V0V12

6、V3）。3從空樹(shù)起，依次插入關(guān)鍵字 37，50，42，18，48，12，56，30，23，構(gòu)造一棵二叉排序樹(shù)。畫(huà)出該二叉排序樹(shù)（4分）畫(huà)出從37（3分4016（Job,Fly,Man,Apple,Max,Key,Kid,Big,Lady,No,Set,Oct,Name）用線性探測(cè)再散列開(kāi)放地址法處理沖突。并求在等概率情況下查找成功時(shí)的平均查8.在一個(gè)無(wú)向圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)倍9對(duì)于關(guān)鍵字序列49，38，65，97，76，13，進(jìn)行 2-路歸并升序排序，則第一找長(zhǎng)度。設(shè)哈希函數(shù)為H(x)/（例如：）,其中 i 為關(guān)鍵字中趟歸并排序的結(jié)果。10.若在線性表中采用二分查找法查找元素，

7、該線性表應(yīng)該元素按值有序，且采用 存儲(chǔ)結(jié)構(gòu)。第一個(gè)字母在字母表中的序號(hào)(字母A 的序號(hào)為 1)。2四、算法閱讀題（2 6 12 分）1. 設(shè)棧S=(1,2,3,4,5,6,7),其中7為棧頂元素。f4_1(&SS；（4分）f4_1中第（2分）void f4_1 (Stack *S)Queue Q; Stack T; int i=0;InitQueue(&Q); InitStack(&T); while(!StackEmpty(S)i+;if (i%2= =1) Push(&T,Pop(S); else EnQueue(&Q,Pop(S);while (!StackEmpty(&T) Push(

8、S,Pop(&T); while(!QueueEmpty(&Q) Push(S,DeQueue(&Q);typedef struct nodeDataTypestruct node * next; * LinkList;void f4_2( LinkList Ls )LinkList p, q;q = Ls-next;if ( q & q-next ) Ls-next = q-next; p=qwhile ( p-next )p = p-next; p-next = q;q-next = NULL;請(qǐng)回答下列問(wèn)題：當(dāng)Ls（4分）請(qǐng)簡(jiǎn)述算法的功能（2分）五、算法設(shè)計(jì)題（本題 10 分）假設(shè)以帶頭

9、結(jié)點(diǎn)的單鏈表表示有序表(非遞減排列)，單鏈表的類型定義如下：typedef struct node DataType data; struct node *nextLinkNode, *LinkList;編寫(xiě)算法，從有序表A 中刪除所有和有序表B 中元素相同的結(jié)點(diǎn)。算法的函數(shù)原型給定為：voidf5(LinkList A,LinkList 32011-2012 學(xué)年第一學(xué)期期末考試試題 （A）卷算法與數(shù)據(jù)結(jié)構(gòu)參考答案及評(píng)分標(biāo)準(zhǔn)1112131415DC1112131415DCCCA12345678910CADBABBDBB二、填空題（本大題共10小題，每小題2分，若有兩個(gè)空格，每個(gè)空格分，共20

10、分）請(qǐng)?jiān)诿總€(gè)空格中填上正確答案。錯(cuò)填、不填均無(wú)分。果 1 分；哈夫曼樹(shù) 5 分，每對(duì) 3 個(gè)關(guān)鍵字得 2 分）gWPL=3*4+35*2+13*3+15*3+20*2+4*5+9*3=2531 存儲(chǔ)結(jié)構(gòu)3. XSX1 存儲(chǔ)結(jié)構(gòu)3. XSXSXSXXB5.2A7.3頂點(diǎn)：D9. 8 697 37E2 直接前驅(qū)10頂點(diǎn)：E8. 210.順序G5頂點(diǎn)：E頂點(diǎn)：H6頂點(diǎn)：E頂點(diǎn)：C三、解答題（本大題共4小題，每7頂點(diǎn)：D頂點(diǎn)：F小題7分，共28分）1. （WPL 21最小生成樹(shù)為：BBCAEDFGH44b3.(1) 4211211118910111213141516MaxKidLayNoSetOctN

11、ame24553685121211118910111213141516MaxKidLayNoSetOctName245536837185012371850123042562348 13 3.08(2) 331四、算法閱讀題（本大題共2小題，每小題6分，共12分）1. （1）S=(1,3,5,7,6,4,2),其中2為棧頂元素；(4分)42將棧S偶數(shù)次出棧的元素入隊(duì)列Q。(2分)30183018501223425648123048502.(1) 執(zhí)行函數(shù)f4_2（4分）/2/23451LS或23(2)如果單鏈表LS中的元素個(gè)數(shù)不少于2一個(gè)結(jié)點(diǎn)后面。（2分）4.（ASL 21153鍵字得 1 分）001234567AppleBigFlyJobKeyMan五、算法設(shè)計(jì)題（本題10分）void f5(LinkList A,LinkList B)5