數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)_考試題及答案匯總(共7套)

1、華東交大數(shù)據(jù)結(jié)構(gòu)期考試卷及答案(一)參考答案以及評(píng)分標(biāo)準(zhǔn)(A )卷題號(hào)四五六七八九十總分累分人 簽名題分20205010100得分考生注意事項(xiàng)：1、本試卷共上頁(yè)，總分100分,考試時(shí)間120分鐘。2、考試結(jié)束后，考生不得將試卷、答題紙和草稿紙帶出考場(chǎng)。一甲的用孫alp淋 =la。系辿sis魁一廿運(yùn)出拈悵哩三靜-H卦帝郛K-定東盤(pán)與三陽(yáng)勿舊聞 盟數(shù)eEw震疥幽卡津賓卻”YWT都鐘？YW磐S京員zsis s數(shù)據(jù)結(jié)構(gòu)(C )課程 課程類別：堂、限、任閉卷(1開(kāi)卷(范圍)(僅限課本)：考試日期：20卷-7-5一、選擇題(每題2分，共20分)|得分|評(píng)閱人1、在數(shù)據(jù)結(jié)構(gòu)的討論中把數(shù)據(jù)結(jié)構(gòu)從邏輯上分為(C

2、 )A)內(nèi)部結(jié)構(gòu)與外部結(jié)構(gòu) B)靜態(tài)結(jié)構(gòu)與動(dòng)態(tài)結(jié)構(gòu)I I0線性結(jié)構(gòu)與非線性結(jié)構(gòu) D)緊湊結(jié)構(gòu)與非緊湊結(jié)構(gòu)2、在一個(gè)單鏈表中，若q結(jié)點(diǎn)是p結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，若在q與p之間插入結(jié)點(diǎn)s, 則執(zhí)行( D )。A) sTink=plink;p->link=s;B) plink=s;slink=q;C) plink=slink;slink=p;D) qlink=s;sTink=p;3、隊(duì)和棧的主要區(qū)別是(D )A)邏輯結(jié)構(gòu)不同B)存儲(chǔ)結(jié)構(gòu)不同C)所包含的運(yùn)算個(gè)數(shù)不同D)限定插入和刪除的位置不同4、在循環(huán)隊(duì)列中用數(shù)組A0.mT存放隊(duì)列元素，其隊(duì)頭和隊(duì)尾指針?lè)謩e為 front和rear,則當(dāng)前隊(duì)列中的元素

3、個(gè)數(shù)是( D )。A) (front rear+1)%mB) (rear front+l)%mC) (front rear+m)%mD) (rear front+m)%m5、下面程序段的時(shí)間復(fù)雜度為( C )for (int i=0;i<m;i+)for (int j=O;j<n;j+) aij=i*j;A) 0(m:) B) 0(n2) C) 0 (m*n) D) 0 (m+n)6、 一棵二叉樹(shù)的前序遍歷序列為ABCDEFG,它的中序序列可能是（B/D）A） CABDEFG B） ABCDEFG C） DACEFBG D）BADCFEG7、下面結(jié)構(gòu)中最適于表示稀疏無(wú)向圖的是（E

4、）A）鄰接矩陣B）逆鄰接表C）鄰接多重表D）十字鏈表E）鄰接表8、一個(gè)對(duì)象序列的排序碼為46, 79, 56, 38, 40, 84,采用快速排序以位于最 左位置的對(duì)象為基準(zhǔn)而得到的第一次劃分結(jié)果為（C ）。A） 38, 46, 79, 56, 40, 84B） 38, 79, 56, 46, 40, 84C） 40, 38, 46, 56, 79, 84D） 38, 46, 56, ?9, 40, 849、設(shè)F是一個(gè)森林，B是由F轉(zhuǎn)換得到的二叉樹(shù)，F(xiàn)中有n個(gè)非葉結(jié)點(diǎn)，則B中右指針域?yàn)榭盏慕Y(jié)點(diǎn)有（C ）個(gè)。A）n-1 B） n C） n+110、線性鏈表不具有的特點(diǎn)是（A ）。A）隨機(jī)訪問(wèn)0插

5、入與刪除時(shí)不必移動(dòng)元素D） n+2B）不必事先估計(jì)所需存儲(chǔ)空間大小D）所需空間與線性表長(zhǎng)度成正比二、填空題（每題1分，共20分）得分評(píng)閱人1、采用順序搜索方法查找長(zhǎng)度為n的順序表時(shí)，搜索成功的平均搜索長(zhǎng)度為（n+l）/2 ）2、將一個(gè)遞歸算法改為對(duì)應(yīng)的非遞歸算法時(shí)，通常需要使用（棧 ）3、二又樹(shù)中第5層上的結(jié)點(diǎn)個(gè)數(shù)最多為（16）4、已知五個(gè)元素ABCDE的進(jìn)棧次序?yàn)锳BCDE,若C為第一個(gè)出棧元素，則下一個(gè) 出棧的元素不可能是（A ）；5、向一個(gè)由HS指向的帶頭結(jié)點(diǎn)的鏈棧中插入一個(gè)結(jié)點(diǎn)時(shí)p時(shí)，需要執(zhí)行的操作 是（.p->next=HS->next; HS->next=p ）；

6、刪除一個(gè)結(jié)點(diǎn)時(shí)，需要執(zhí)行的操作 是（_ HS->next =HS->next->next _）（假設(shè)棧不空而且無(wú)需回收被刪除結(jié)點(diǎn)）。 6、已知鏈棧的結(jié)點(diǎn)結(jié)構(gòu)的棧頂指針為top,則實(shí)現(xiàn)將指針p所指結(jié)點(diǎn)插入棧頂?shù)?語(yǔ)句依次為（ p->next=top ）和（ top=p ）o7、對(duì)于線性表（70, 34, 55, 23, 65, 41, 20）進(jìn)行散列存儲(chǔ)時(shí)，若選用H （K） 二K%7作為散列函數(shù)，則散列地址為0的元素有（1 ）個(gè)，散列地址為6的有（4） 個(gè)。8、假定一棵樹(shù)的廣義表表示為A （D （E, G）, H （I, J）,則樹(shù)中所含的結(jié)點(diǎn)數(shù) 為7個(gè)，樹(shù)的深度為_(kāi)3

7、,樹(shù)的度為2_o9、若對(duì)一棵完全二叉樹(shù)從0開(kāi)始進(jìn)行結(jié)點(diǎn)的編號(hào)，并按此編號(hào)把它順序存儲(chǔ)到一 維數(shù)組A中，即編號(hào)為0的結(jié)點(diǎn)存儲(chǔ)到A0中。其余類推，則Ai元素的左孩 子元素為_(kāi)21+1,右孩子元素為 2i+2,雙親元素為一（i-l）/2_o 10、在一個(gè)具有10個(gè)頂點(diǎn)的無(wú)向完全圖中，包含有_45一條邊，在一個(gè)具有n 個(gè)頂點(diǎn)的有向完全圖中，包含有_n（n-1）條邊。1. 11、后綴算式79 2 30 +- 4 2 /*的值為_(kāi)94。中綴算式（3+X*Y） -2*Y/3對(duì)應(yīng)的后綴算式為_(kāi)3 XY* + 2Y*3 / -。三、簡(jiǎn)答題（5題，共50分）1、已知某二義樹(shù)的前序序列為EBADCFHGI ,中序序

8、列為 ABCDEFGHL請(qǐng)畫(huà)出二義樹(shù)并寫(xiě)出它的后序序列。（構(gòu)造出二叉樹(shù) 7分，后序遍歷3分，共10分） 參考答案：得分評(píng)閱人后序序列:ACDBGIHFE 二義樹(shù)為:第12頁(yè)共5頁(yè)評(píng)分標(biāo)準(zhǔn)：構(gòu)造出二叉樹(shù)7分，后序遍歷3分2、將關(guān)鍵碼53, 78, 65, 17, 87, 09, 81, 45, 23依次插入到一棵初始為空的 二又搜索樹(shù)中，畫(huà)出每插入一個(gè)關(guān)鍵碼后的二又排序樹(shù)。（每個(gè)過(guò)程1分，共9分） 參考答案：評(píng)分標(biāo)準(zhǔn)：（每個(gè)過(guò)程1分，共9分）3、假定用于通訊的電文僅有8個(gè)字母Cl, C2,，C8組成，各個(gè)字母在電文中 出現(xiàn)的頻率分別為5, 25, 3, 6, 10, 11, 36, 4,試為這8

9、個(gè)字母設(shè)計(jì)哈夫曼編 碼樹(shù)并寫(xiě)出每個(gè)字母的編碼。（畫(huà)出哈夫曼樹(shù)得3分，寫(xiě)出一個(gè)字母的編碼是1分, 總分共n分） 參考答案：cS cl雖然哈夫曼樹(shù)的帶權(quán)路徑長(zhǎng)度是唯一的，但形態(tài)不唯一。本題中各字母編碼如下: cl:0110 c2:10 c3:0010 c4:0111 c5:000 c6:010 c7:ll c8:0011評(píng)分標(biāo)準(zhǔn)：畫(huà)出哈夫曼樹(shù)得3分，每個(gè)字母的編碼是1分，共8分4、已知一個(gè)圖的定點(diǎn)集V各邊集G如下：(16分)V=0,1,2, 3, 4, 5, 6, 7, 8, 9);E=(0, 1), (0,4), (1,2), (1,7), (2, 8), (3,4), (3, 8), (5,6

10、), (5, 8), (5, 9), (6, 7),(7,8), (8, 9)當(dāng)它用鄰接矩陣表示和鄰接表表示時(shí)，分別寫(xiě)出從頂點(diǎn)V0出發(fā)按深度優(yōu)先搜索遍歷得到的定點(diǎn)序列和按廣度優(yōu)先搜索遍歷得到的定點(diǎn)序列。假定每個(gè)頂點(diǎn)鄰接表中的節(jié)點(diǎn)是按頂點(diǎn)序號(hào)從大到小的次序鏈接的。圖深度優(yōu)先序列廣度優(yōu)先序列鄰接矩陣表示時(shí)鄰接表表示時(shí)參考答案4、圖浜度優(yōu)先序列廣度優(yōu)先序列鄰接印陽(yáng)表示時(shí)0, I. 2, 8, 3, 4,工 6, 7, 90, B, $ 2, 7, 3, 8. 6, 5, 9鄰接表表示時(shí)Or 4, 3, 8, 9r 5, 6, 7, b 20, 4, 1, 3, 7, 2, 8, 6, 9, 5評(píng)分標(biāo)

11、準(zhǔn)：正確寫(xiě)出每個(gè)序列得4分5、 LinkList mynote(LinkList L)/L是不帶頭結(jié)點(diǎn)的單鏈表的頭指針if(L&&L->next)q=L； L=L>next： p=L；SI：while(p >next) p=p >next；S2：p >next=q： q>next=NULL：return L：）請(qǐng)回答下列問(wèn)題：（l）說(shuō)明語(yǔ)句SI的功能；（2）說(shuō)明語(yǔ)句組S2的功能;（3）設(shè)鏈表表示的線性表為（al,a2,an），寫(xiě)出算法執(zhí)行后的返回值所 表示的線性表。答案：（1）查詢鏈表的尾結(jié)點(diǎn) （1分）（2）將第一個(gè)結(jié)點(diǎn)鏈接到鏈表的尾部，作為

12、新的尾結(jié)點(diǎn)-一（1分）（3）返回的線性表為（a2, a3, , an, al） （2分）四、程序編程題（每題5分，共10分）得分評(píng)閱人1、統(tǒng)計(jì)出單鏈表HL中結(jié)點(diǎn)的值等于給定值X的結(jié)點(diǎn)數(shù)。int CountX（LNode* HL, ElemType x）參考答案：int CountX（LNode* HL, ElemType x） int i=0; LNode* p=乩;1.為計(jì)數(shù)器 （1 分）while（p!=NULL） if （P->data=x） i+;p=p_>next;/while,出循環(huán)時(shí)i中的值即為x結(jié)點(diǎn)個(gè)數(shù) （3分）return i ;（ 1 分）/CountX2、試寫(xiě)

13、一算法寫(xiě)出用二義鏈表表示給定二義樹(shù)的葉子結(jié)點(diǎn)總數(shù)。int GetLeaves（ BinTree root）參考答案：int GetLeaves（ BinTree root）求葉結(jié)點(diǎn)總數(shù)static int leaf=0;此1用于記葉結(jié)點(diǎn)數(shù)，注意用靜態(tài)變量（1分）if（root） 遞歸計(jì)算葉結(jié)點(diǎn)數(shù)if（!（root->lchiId root->rchiId）leaf+;如果該結(jié)點(diǎn)無(wú)左右孩子，則葉子數(shù)加1GetLeaves（root->lchild）;算左子數(shù)的葉結(jié)點(diǎn)數(shù)GetLeaves （root->rchild）; 算右子樹(shù)的葉結(jié)點(diǎn)數(shù)）（3分）return leaf;

14、返回結(jié)果 （1 分）華東交大數(shù)據(jù)結(jié)構(gòu)期考試卷及答案（二）數(shù)據(jù)結(jié)構(gòu)（C ）課程 課程類別：必、限、任閉卷（1開(kāi)卷（范圍）（僅限課本）：考試日期：一用常淋nip淋 圣需 。去皿盡£魁一mW田理悵哩as題號(hào)四五六七八九十總分累分人 簽名題分2026241416100得分考生注意事項(xiàng)：1、本試卷共L頁(yè)，總分100分,考試時(shí)間120 分鐘。2、考試結(jié)束后，考生不得將試卷、答題紙和草稿紙帶出考場(chǎng)。一、 選擇題（每小題2分，共20分）1 .在一個(gè)帶有附加表頭結(jié)點(diǎn)的單鏈表HL中，若要向表頭插入一 個(gè)由指針P指向的結(jié)點(diǎn)，則執(zhí)行（）。A. HL=p; p->next=HL;B. p->nex

15、t=HL->next;C. p->next=HL; p=HL;D. p->next=HL; HL=p;HL->next=p;2 .若順序存儲(chǔ)的循環(huán)隊(duì)列的QueueMaxSizef,則該隊(duì)列最多可存儲(chǔ)（）個(gè)元A. nB. n-1 C. n+13 .下述哪一條是順序存儲(chǔ)方式的優(yōu)點(diǎn)？（）A.存儲(chǔ)密度大C.獲取符合某種條件的元素方便D.不確定B.插入和刪除運(yùn)算方便D.查找運(yùn)算速度快4,設(shè)有一個(gè)棧的輸入序列為1 2 3,則下列序列中不可能是棧的輸出序列的是( )A. 2 3 1B. 3 2 1C. 3 1 2D. 1 2 35 .下列關(guān)于二叉樹(shù)遍歷的敘述中，正確的是()。A.若一

16、個(gè)樹(shù)葉是某二叉樹(shù)的中序遍歷的最后一個(gè)結(jié)點(diǎn)，則它必是該二義樹(shù)的 前序遍歷最后一個(gè)結(jié)點(diǎn)B.若一個(gè)點(diǎn)是某二叉樹(shù)的前序遍歷最后一個(gè)結(jié)點(diǎn)，則它必是該二義樹(shù)的中序 遍歷的最后一個(gè)結(jié)點(diǎn)、C.若一個(gè)結(jié)3捻某二叉樹(shù)的中序遍歷的最后一個(gè)結(jié)點(diǎn)，則它必是該二叉樹(shù)的 前序最后一個(gè)結(jié)點(diǎn)D.若一個(gè)樹(shù)葉是某二叉樹(shù)的前序最后一個(gè)結(jié)點(diǎn)，則它必是該二義樹(shù)的中序遍 歷最后一個(gè)結(jié)點(diǎn)6 . k層二義樹(shù)的結(jié)點(diǎn)總數(shù)最多為().A. 2-1 B. 2K+1 C. 2K-1 D. 27 .對(duì)線性表進(jìn)行二分法查找，其前提條件是().A.線性表以鏈接方式存儲(chǔ)，并且按關(guān)鍵碼值排好序B.線性表以順序方式存儲(chǔ)，并且按關(guān)鍵碼值的檢索頻率排好序C.線性表以順

17、序方式存儲(chǔ)，并且按關(guān)鍵碼值排好序D.線性表以鏈接方式存儲(chǔ)，并且按關(guān)鍵碼值的檢索頻率排好序8 .對(duì)n個(gè)記錄進(jìn)行堆排序，所需要的輔助存儲(chǔ)空間為A. 0 (log:n) B. 0 (n) C. 0(1) D. 0 (n2)9 .對(duì)于線性表(7, 34, 77, 25, 64, 49, 20, 14)進(jìn)行散列存儲(chǔ)時(shí)，若選用H (K) =K%7作為散列函數(shù)，則散列地址為。的元素有()個(gè)，A. 1B. 2C. 3D. 410 .下列關(guān)于數(shù)據(jù)結(jié)構(gòu)的敘述中，正確的是().A.數(shù)組是不同類型值的集合B .遞歸算法的程序結(jié)構(gòu)比迭代算法的程序結(jié)構(gòu)更為精煉C .樹(shù)是一種線性結(jié)構(gòu)D,用一維數(shù)組存儲(chǔ)一棵完全二義樹(shù)是有效的

18、存儲(chǔ)方法2、 填空題(每空1分，共26分)1 .數(shù)據(jù)的邏輯結(jié)構(gòu)被分為、和 四利I。2 . 一個(gè)算法的時(shí)間復(fù)雜度為(3/+2000Hog二加90)/,其數(shù)量級(jí)表示為 03 .對(duì)于一個(gè)長(zhǎng)度為n的單鏈存儲(chǔ)的隊(duì)列，在表頭插入元素的時(shí)間復(fù)雜度為 ，在表尾插入元素的時(shí)間復(fù)雜度為。4 .假定一棵樹(shù)的廣義表表示為A (D (E, G), H (I, J),則樹(shù)中所含的結(jié)點(diǎn)數(shù)為 個(gè)，樹(shù)的深度為，樹(shù)的度為 c5 .后綴算式79 2 30 +- 4 2 / *的值為 二中綴算式(3+X*Y)-2Y/3對(duì)應(yīng)的后綴算式為 o6 .若對(duì)一棵完全二叉樹(shù)從0開(kāi)始進(jìn)行結(jié)點(diǎn)的編號(hào)，并按此編號(hào)把它順序存儲(chǔ)到一維數(shù)組A中，即編號(hào)為0

19、的結(jié)點(diǎn)存儲(chǔ)到A0中。其余類推，則A i 元素 的左孩子元素為,右孩子元素為，雙親元素為7 .在樹(shù)中，一個(gè)結(jié)點(diǎn)的直接后繼結(jié)點(diǎn)稱為該結(jié)點(diǎn)的,一個(gè)結(jié)點(diǎn)的直接 前趨結(jié)點(diǎn)稱為該結(jié)點(diǎn)的 O8 .在一個(gè)具有10個(gè)頂點(diǎn)的無(wú)向完全圖中，包含有 條邊，在一個(gè)具有n個(gè)頂點(diǎn)的有向完全圖中，包含有 條邊。9 .棧又稱為 表，隊(duì)列又稱為 表。10 .表示圖的兩種常用的存儲(chǔ)結(jié)構(gòu)為 和 c11 .隊(duì)列的插入操作是在隊(duì)列的 進(jìn)行，刪除操作是在隊(duì)列的進(jìn)行。12 .在線性表的散列存儲(chǔ)中，裝填因子a乂稱為裝填系數(shù)，若用m表示散列表的長(zhǎng) 度，n表示待散列存儲(chǔ)的元素的個(gè)數(shù)，則a等于。3、 運(yùn)算題(每題3分，共24分)1 .在如下數(shù)組A中

20、鏈接存儲(chǔ)了一個(gè)線性表，表頭指針存放在A 0. next,試寫(xiě) 出該線性表。234567data next2 .已知一棵二義樹(shù)的前序遍歷的結(jié)果是ABKCDFGHIJ,中序遍歷的結(jié)果是 KBCDAFHIGJ,試畫(huà)出這棵二叉樹(shù)。3 .已知一個(gè)圖的頂點(diǎn)集V為：¥=1, 2, 3, 4, 5, 6, 7);其共有10條邊。該圖用如下邊集數(shù)組存儲(chǔ):122552261364547677751122233457試用克魯斯卡爾算法依次求出該圖的最小生成樹(shù)中所得到的各條邊及權(quán)值。4、 閱讀算法(每題7分，共14分)1 .在下面的每個(gè)程序段中，假定線性表La的類型為L(zhǎng)ist,元素類型ElemType 為i

21、nt,并假定每個(gè)程序段是連續(xù)執(zhí)行的。試寫(xiě)出每個(gè)程序段執(zhí)行后所得 到的線性表Lao(1) InitList(La);Int a = 100, 26, 57, 34, 79;For (i=0;i<5;i+)Insert (La, ai);TraverseList(La);(2) DeleteFront (La);InsertRear(La, DeleteFront(La);TraverseList(La);(3) ClearList(La);For (i=0;i<5;i+)InsertFront(La, ai);TraverseList(La);2 .現(xiàn)面算法的功能是什么？void A

22、BC(BTNode * BT)(if BT cout«BT->data«，'ABC(BT->left);ABC(BT->right);5、 編寫(xiě)算法(共16分)HL為單鏈表的表頭指針，試寫(xiě)出在該單鏈表中查找具有給定的元素item的算法。 bool Find(LNode* HL, ElemType &item)參考答案:1、 單選題(每題2分，共20分)l.B 2.B 3.A 4.C 5.D 6.A 7.C8.C9.D10.D2、 填空題(每空1分，共26分)2. 集合結(jié)構(gòu)線性結(jié)構(gòu)樹(shù)結(jié)構(gòu)圖結(jié)構(gòu)3. 0(n)4. 0(1)0(1)5. 7226

23、. 943 XY* + 2Y*3/-7. 2i+l2i+2(i-l)/28. 孩子(或子)結(jié)點(diǎn) 雙親(或父)結(jié)點(diǎn)9. 45 n(n-l)10. 先進(jìn)后出先進(jìn)先出11. 鄰接矩陣鄰接表邊集數(shù)組12. 尾首13. n/m3、 運(yùn)算題(每題6分，共24分)1 . 線性表為:(90, 40, 78, 50, 34, 60)2 .當(dāng)前序序列為ABKCDFGHIJ,中序序列為KBCDAFHIGJ時(shí)，逐步形成二叉樹(shù)的過(guò)程如 下圖4所示：(1,6)1, (2,4)1, (2,5)2, (5,7)2, (2,6)3, (3,5)74.見(jiàn)圖5。L La=(26.34,57,79,100) La=(57.79,10

24、0.34)(3)La=(79.34,57,26/00)2.前序遍歷鏈?zhǔn)酱鎯?chǔ)的二叉樹(shù)。五、 編寫(xiě)算法(16分)bool Find(LNode* HL. ElemType &item)LNode* p=HL;if (p->data=item) return true;)else p=p->next;return false;)華東數(shù)據(jù)結(jié)構(gòu)期考試卷及答案（三）第17頁(yè)共5頁(yè)參考答案（B ）卷數(shù)據(jù)結(jié)構(gòu)（C ）課程 課程類別：名、限、任閉卷（1開(kāi)卷（范圍）（僅限課本）:考試日期：題號(hào)四五7V七八九十總分累分人 簽名題分20304010100得分考生注意事項(xiàng)：1、本試卷共上頁(yè)，總分10

25、0分,考試時(shí)間120分鐘。2、考試結(jié)束后，考生不得將試卷、答題紙和草稿紙帶出考場(chǎng)。一、 單選題（每題2分，共20分）1 .以下數(shù)據(jù)結(jié)構(gòu)中哪一個(gè)是線性結(jié)構(gòu)？（ B）A.有向圖 B.隊(duì)列C.線索二叉樹(shù)D.B樹(shù)2 .在一個(gè)單鏈表HL中，若要在當(dāng)前由指針p指向的結(jié)點(diǎn)后面插入一個(gè)由q指向 的結(jié)點(diǎn)，則執(zhí)行如下（D）語(yǔ)句序列。A. p=q; p->next=q;B. p->next=q; q->next=p;C. p->next=q->next; p=q;D. q->next=p->next; p->next=q;3 .以下哪一個(gè)不是隊(duì)列的基本運(yùn)算？ （ A

26、）A.在隊(duì)列第i個(gè)元素之后插入一個(gè)元素B.從隊(duì)頭刪除一個(gè)元素C.判斷一個(gè)隊(duì)列是否為空D.讀取隊(duì)頭元素的值4 .字符A、B、C依次進(jìn)入一個(gè)棧，按出棧的先后順序組成不同的字符串，至多 可以組成（B）個(gè)不同的字符串？A. 14B. 5C. 6D. 8A. 11 B. 35 C. 19圖15 .由權(quán)值分別為3,862的葉子生成一棵哈夫曼樹(shù)，它的帶權(quán)路徑長(zhǎng)度為（B ）。以下68題基于圖6.A. E> G F、A、C、D、B該二叉樹(shù)結(jié)點(diǎn)的前序遍歷的序:列為（CF、B、DD、G、FB. E、 A、 G CsD. E、 G、 As C、 D、 F、 BC. E、A、C、B、7 .該二又樹(shù)結(jié)點(diǎn)的中序遍歷的

27、序列為（AA. A、 B、 C、 D、 E、 G> FB. E、 A、 G、 C、 F、 B、 DC. E、A、C、B、D、G、FE. B、D、C、A、F、G、E8 .該二叉樹(shù)的按層遍歷的序列為（C）oB. E、A、Cx B、D、G、FD. E、 G、 A、 C、 D、 F、 BA. E G、 F、 A、 C、 D、 BC. E A、 G、 C、 F、 B、 D9 .下面關(guān)于圖的存儲(chǔ)的敘述中正確的是（B ）oA.用鄰接表法存儲(chǔ)圖，占用的存儲(chǔ)空間大小只與圖中邊數(shù)有關(guān)，而與結(jié)點(diǎn)個(gè)數(shù)無(wú)關(guān)B.用鄰接表法存儲(chǔ)圖，占用的存儲(chǔ)空間大小與圖中邊數(shù)和結(jié)點(diǎn)個(gè)數(shù)都有關(guān) C.用鄰接矩陣法存儲(chǔ)圖，占用的存儲(chǔ)空間大

28、小與圖中結(jié)點(diǎn)個(gè)數(shù)和邊數(shù)都有關(guān)D.用鄰接矩陣法存儲(chǔ)圖，占用的存儲(chǔ)空間大小只與圖中邊數(shù)有關(guān)，而與結(jié)點(diǎn) 個(gè)數(shù)無(wú)關(guān)10 .設(shè)有關(guān)鍵碼序列（q, g, m, z, a, n, p, x, h）,下面哪一個(gè)序列是從上述序 列出發(fā)建堆的結(jié)果?（B ）A. a, g, h, m, n, p, q, x, zB.a, g, m, h, q, n, p, x, zC. g, m, q, a, n, p, x, h, zD.h, g, m, p, a, n, q, x, z2、 填空題（每空1分，共26分）1 .數(shù)據(jù)的物理結(jié)構(gòu)被分為順序、鏈表、索引、散列一四種。2 .對(duì)于一個(gè)長(zhǎng)度為n的順序存儲(chǔ)的線性表，在表頭插入元

29、素的時(shí)間復(fù)雜 度為-0（n） ,在表尾插入元素的時(shí)間復(fù)雜度為一 0（1；二3 .向一個(gè)由HS指向的鏈棧中插入一個(gè)結(jié)點(diǎn)時(shí)p時(shí)，需要執(zhí)行的操作是 p->next=HS;HS=p ；刪除一個(gè)結(jié)點(diǎn)時(shí)，需要執(zhí)行的操作是 HS=HS->next （假設(shè)棧不空而且無(wú)需回收被刪除結(jié)點(diǎn)）。4 .對(duì)于一棵具有n個(gè)結(jié)點(diǎn)的二義樹(shù)，一個(gè)結(jié)點(diǎn)的編號(hào)為i（lWiWn）,若它有左孩子則左孩子結(jié)點(diǎn)的編號(hào)為_(kāi)2i,若它有右孩子，則右孩子 結(jié)點(diǎn)的編號(hào)為_(kāi)2i+l,若它有雙親，則雙親結(jié)點(diǎn)的編號(hào)為i/2（或 i/2 ）5 .當(dāng)向一個(gè)大根堆插入一個(gè)具有最大值的元素時(shí)，需要逐層一向上一 調(diào)整，直到被調(diào)整到一根位置為止。6 .表

30、示圖的兩種常用的存儲(chǔ)結(jié)構(gòu)為_(kāi)鄰接矩陣_、_鄰接表7 .對(duì)于線性表(70, 34, 55, 23, 65, 41, 20)進(jìn)行散列存儲(chǔ)時(shí)，若選 用H (K) =K%7作為散列函數(shù)，則散列地址為。的元素有_1一個(gè), 散列地址為6的有4個(gè)。8 .在歸并排序中，進(jìn)行每趟歸并的時(shí)間復(fù)雜度為-0(n),整個(gè)排序 過(guò)程的時(shí)間復(fù)雜度為 0(nlog：n：1,空間復(fù)雜度為_(kāi)0(n)。3、 運(yùn)算題(每題10分,共30分)1 .寫(xiě)出下列中綴表達(dá)式的后綴形式:(1) 3X/(Y-2)+l(2) 2+X*(Y+3)答案：(1) 3 X *Y 2 -/I +(2) 2 X Y 3 + * +2 .試對(duì)圖2中的二義樹(shù)畫(huà)出其

31、：(I)順序存儲(chǔ)表示的示意圖；(2)二義鏈表存儲(chǔ)表示的示意圖。123456789答案：(1)：0123678910111213141516(2)：見(jiàn)圖3所示3 .已知一個(gè)圖的頂點(diǎn)集V和邊集E分別為:V=1,2, 3,4, 5, 6,7;E=(1,2)3, (1,3)5, (1,4)8, (2,5)10, (2, 3)6, (3,4)15, (3, 5)12, (3,6)9, (4,6)4, (4,7)20, (5,6)18, (6, 7)25;按照普里姆算法從頂點(diǎn)1出發(fā)得到最小生成樹(shù)，試寫(xiě)出在最小生成樹(shù)中依 次得到的各條邊。答案：普里姆算法從頂點(diǎn)1出發(fā)得到最小生成樹(shù)為：(1,(2) (1,3)

32、5， (1,4)8, (4,6)4,(2,5)10, (4,7)204、 閱讀算法(每題10分,共20分)1. void AE(Stack& S)InitStack(S);Push(S,3);Push(S, 4);int x=Pop(S)+2*Pop(S);Push(S, x);int i, a5 = l, 5, 8,12,15);for(i=0;i<5;i+) Push(S, 2*ai);while(!StackEmpty(S) cout«Pop(S)«,;該算法被調(diào)用后得到的輸出結(jié)果為：30 24 16 10 2 102. void ABC (BTNode

33、 *BT,int &cl,int &c2) if (BT !=NULL) ABC(BT->Cft,c 1 ,c2);cl+;if (BT->left=NULL&&BT->right=NULL) c2+;ABC(BT->right,c 1 ,c2);)/if該函數(shù)執(zhí)行的功能是什么？答案：該函數(shù)的功能是：統(tǒng)計(jì)出BT所指向的二叉樹(shù)的結(jié)點(diǎn)總數(shù)和葉子總數(shù)5、 編寫(xiě)算法(共10分)編寫(xiě)從類型為L(zhǎng)ist的線性表L中將第i個(gè)元素刪除的算法，(假定不需要對(duì)i 的值進(jìn)行有效性檢查,也不用判別L是否為空表。)void Delete(List& L, i

34、nt i)答案：void Delete(List& L, int i)(for (int j=i-l;j<L size-1; j+)L. listj>L. listCj+1;第 i 個(gè)元素的下標(biāo)為 i-1L. size;)華東交大數(shù)據(jù)結(jié)構(gòu)期考試卷及答案（四）一”蛇撲DIP孫DIP孫。瞇辿S求蜜SH5與aB謖奧孌喀絲Te罪常七黑窕隱茶杰琪坦香R數(shù)據(jù)結(jié)構(gòu)（C ）課程課程類別：堂、限、任閉卷（1開(kāi)卷（范圍）（僅限課本）：考試日期：2011-1 -12題號(hào)四五六七八九十總分累分人 簽名題分20304010100得分考生注意事項(xiàng)：1、本試卷共上頁(yè)，總分100分,考試時(shí)間120分鐘。2

35、、考試結(jié)束后，考生不得將試卷、答題紙和草稿紙帶出考場(chǎng)。一、選擇題（每題2分，共20分）1、數(shù)據(jù)的四種存儲(chǔ)結(jié)構(gòu)是（A ）A,順序存儲(chǔ)結(jié)構(gòu)、鏈接存儲(chǔ)結(jié)構(gòu)、索引存儲(chǔ)結(jié)構(gòu)和散列存儲(chǔ)結(jié)構(gòu)B.線性存儲(chǔ)結(jié)構(gòu)、非線性存儲(chǔ)結(jié)構(gòu)、樹(shù)型存儲(chǔ)結(jié)構(gòu)和圖型存儲(chǔ)結(jié)構(gòu)C.集合存儲(chǔ)結(jié)構(gòu)、一對(duì)一存儲(chǔ)結(jié)構(gòu)、一對(duì)多存儲(chǔ)結(jié)構(gòu)和多對(duì)多存儲(chǔ)結(jié)構(gòu)D,順序存儲(chǔ)結(jié)構(gòu)、樹(shù)型存儲(chǔ)結(jié)構(gòu)、圖型存儲(chǔ)結(jié)構(gòu)和散列存儲(chǔ)結(jié)構(gòu)2、若對(duì)某線性表最常用的操作是在最后一個(gè)結(jié)點(diǎn)之后插入一個(gè)新結(jié)點(diǎn)或刪除最后 一個(gè)結(jié)點(diǎn)，要使操作時(shí)間最少，下列選項(xiàng)中，應(yīng)選擇的存儲(chǔ)結(jié)構(gòu)是（C）A.無(wú)頭結(jié)點(diǎn)的單向鏈表B.帶頭結(jié)點(diǎn)的單向鏈表C.帶頭結(jié)點(diǎn)的雙循環(huán)鏈表 D.帶頭結(jié)點(diǎn)的單循環(huán)鏈表3、若元素

36、的入棧順序?yàn)?, 2, 3., n,如果第2個(gè)出棧的元素是n,則輸出的 第i （l<=i<=n）個(gè)元素是（D ）A. n-iB. n-i+1C. n-i+2D.無(wú)法確定4、若一棵二叉樹(shù)的前序遍歷序列與后序遍歷序列相同，則該二義樹(shù)可能的形狀是 （B ）A.樹(shù)中沒(méi)有度為2的結(jié)點(diǎn) B.樹(shù)中只有一個(gè)根結(jié)點(diǎn)C.樹(shù)中非葉結(jié)點(diǎn)均只有左子樹(shù)D.樹(shù)中非葉結(jié)點(diǎn)均只有右子樹(shù)5、下面程序段的時(shí)間復(fù)雜度為( C )for (int i=0;i<m;i+)for (int j=O;j<n;j+) ai j=i*j;A) 0(m2) B) 0(n2) C) 0 (m*n)D) 0 (m+n)6、 設(shè)

37、有一組關(guān)鍵字(19, 14, 23, 1, 6, 20, 4, 27, 5, 11, 10, 9),用散列 函數(shù)H(key)=key%13構(gòu)造散列表，用拉鏈法解決沖突，散列地址為1的鏈中記錄 個(gè)數(shù)為(C ) A. 1B. 2C. 3 D. 47、指針p、q和r依次指向某循環(huán)鏈表中三個(gè)相鄰的結(jié)點(diǎn)，交換結(jié)點(diǎn)*q和結(jié)點(diǎn)*r 在表中次序的程序段是(A) A. p->next=r； q->next=r->next； r->next=q： B. p->next=r； r->next=q： q->next=r->next； C. r->next=q； q

38、->next=r->next； p->next=r； D. r->next=q： p->next=r： q->next=r->next；8、一個(gè)對(duì)象序列的排序碼為46, 79, 56, 38, 40, 84>,采用快速排序以位于最 左位置的對(duì)象為基準(zhǔn)而得到的第一次劃分結(jié)果為(C )。A) 38, 46, 79, 56, 40, 84B) 38, 79, 56, 46, 40, 84C) 40, 38, 46, 56, 79, 84D) 38, 46, 56, ?9, 40, 849、串的操作函數(shù)str定義為：int str(charts) cha

39、r *p-s； while (*p !='0' ) p+； return p-s； 則str( abcde")的返回值是(C)A. 3 B. 4 C. 5 D. 610、設(shè)已有m個(gè)元素有序，在未排好序的序列中挑選第m+1個(gè)元素，并且只經(jīng)過(guò) 一次元素的交換就使第m+1個(gè)元素排序到位，該方法是(D )oA.折半排序B.冒泡排序C.歸并排序D.簡(jiǎn)單選擇排序得分評(píng)閱人二、填空題(每題2分，共30分)3、采用順序搜索方法查找長(zhǎng)度為n的順序表時(shí)，搜索成功的平均搜索長(zhǎng)度為(n+l)/2 )4、將一個(gè)遞歸算法改為對(duì)應(yīng)的非遞歸算法時(shí)，通常需要使用(棧 )5、數(shù)據(jù)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的特點(diǎn)是借

40、助(指針)表示數(shù)據(jù)元素之間的邏輯關(guān)系。6、下面程序段的時(shí)間復(fù)雜度為(0(n)osum=l；for (i=0;sum<n;i+) sum+=l；5、給定一組數(shù)據(jù)6, 2, 7, 10, 3, 12以它構(gòu)造一棵哈夫曼樹(shù)，則樹(shù)高為_(kāi)5_, 帶權(quán)路徑長(zhǎng)度WPL的值為_(kāi)96_。6、假定一棵樹(shù)的廣義表表示為A （D （E, G）, H （I, J）,則樹(shù)中所含的結(jié)點(diǎn)數(shù) 為7個(gè)，樹(shù)的深度為_(kāi)3，樹(shù)的度為-2_o7、假定一個(gè)最大堆（大根堆）為（56, 38, 42, 30, 25, 40, 35, 20）,則依次 向它插入45和64兩個(gè)元素后得到的最大堆為：64, 56, 42, 38, 45, 40,

41、 35, 20, 30, 25 8、在一個(gè)具有10個(gè)頂點(diǎn)的無(wú)向完全圖中，包含有_45一條邊，在一個(gè)具有n個(gè) 頂點(diǎn)的有向完全圖中，包含有_n（n-l）條邊。9、后綴算式79 2 30 +- 4 2 /*的值為_(kāi)94。中綴算式（3+X*Y）-2*Y/3 對(duì)應(yīng)的后綴算式為_(kāi)3 XY* + 2Y*3/-o10、.由字符集（s, t, a, e, 1及其在電文中出現(xiàn)的頻度構(gòu)建的哈夫區(qū)樹(shù)如圖所示。已知某段 電文的哈夫曼編碼為111000010100,請(qǐng)根據(jù)該哈夫噠樹(shù)進(jìn)行譯碼，寫(xiě)出原來(lái)的電文（eatst）。第21頁(yè)共5頁(yè)得分評(píng)閱人三、簡(jiǎn)答題（5題，共53分）1、己知某二義樹(shù)的前序序列為EBADCFHGI ,

42、中序序列為 ABCDEFGHL請(qǐng)畫(huà)出二叉樹(shù)并寫(xiě)出它的后序序列。（構(gòu)造出二叉樹(shù) 7分，后序遍歷3分，共10分）參考答案：后序序列:ACDBGIHFE二義樹(shù)為：B) »EF評(píng)分標(biāo)準(zhǔn)：構(gòu)造出二義樹(shù)7分，后序遍歷3分2、在一棵空的二叉查找樹(shù)中依次插入關(guān)鍵字序列為20、30、8、12、34、5、60、3、1, 29, 畫(huà)出插入關(guān)鍵碼后的二義查找樹(shù)。（5分）3、.要在的向量空間中建立兩個(gè)棧stackl和stack2,請(qǐng)回答:應(yīng)該如何設(shè)計(jì)這兩個(gè)棧才能充分利用整個(gè)向量空間？（5分）若stackl的棧頂指針為topi, stack2的棧頂指針為top2,如果需要充分利用 整個(gè)向量空間，則：棧stack

43、l空的條件是：（）;（2分）棧stack2空的條件是：（）;（2分）棧stackl和棧stack2滿的條件是：（）。（2分）答：（1）采用雙向棧的形式，stackl的棧底設(shè)置在下標(biāo)為0的元素上，stack2的棧底設(shè)置在下標(biāo)為n-1的元素上。（2）topl=-l» top2=n, topl-l=top24、設(shè)有單鏈表類型定義如下： typedef struct node int data;struct node *next; *LinkList;閱讀下列算法，并回答問(wèn)題：void f (LinkList head, int A, int B) LinkList p二NULL;while

44、 (head !=NULL)if （head->data>A&&head->data<B）p=head;head=head->next;if （p !=NULL）printf（"%dn”, p->data）;（1）已知鏈表h如下圖所示，給出執(zhí)行f（h, 5, 8）之后的輸出結(jié)果；（5分）簡(jiǎn)述算法f的功能。 （5分）答：（1）7（2）輸出鏈表h中（若存在）最后一個(gè)大于A到小于B的值。5、 LinkList mynote（LinkList L）/L是不帶頭結(jié)點(diǎn)的單鏈表的頭指針if（L&&L-next）q=L； L=L&g

45、t;next； p=L；SI：while（p >next） p=p >next；S2：p >next=q； q>next=NULL；return L： 請(qǐng)回答下列問(wèn)題： （1）說(shuō)明語(yǔ)句SI的功能：（2）說(shuō)明語(yǔ)句組S2的功能;（3）設(shè)鏈表表示的線性表為（al,a2,an），寫(xiě)出算法執(zhí)行后的返回值所 表示的線性表。答案：（1）查詢鏈表的尾結(jié)點(diǎn) （1分）（2）將第一個(gè)結(jié)點(diǎn)鏈接到鏈表的尾部，作為新的尾結(jié)點(diǎn) -一（1分）（3）返回的線性表為（a2, a3, , an, al） （2分）得分評(píng)閱人四、程序編程題（每題10分，共10分）1、已知二義樹(shù)的定義如下： typedef st

46、ruct node int data;struct node *lchild, *rchild;*Bitptr;編寫(xiě)遞歸算法求二義樹(shù)的高度。函數(shù)原型為：int BiTreeHeight (Bitptrt)； 答：int BiTreeHeight (Bitptr t) if(!t) return 0;lh= BiTreeHeight (t->lchild);rh= BiTreeHeight (t->rchild);return lh>rh?lh+l:rh+l;)一W蛇 孫 圣舟。興辿s£魁一廿坦田弗誕映 軀戮eE話震洋健本津?qū)崊s物YWT部仲NYWS翅汞員.老蚓迎回教殳

47、，內(nèi)城M鐘知京看華東教數(shù)據(jù)結(jié)構(gòu)課程據(jù)結(jié)構(gòu)期考試卷及答案（五）試卷編號(hào):(A)卷課程類別：必題號(hào)四五六七八九十總分累分人 簽名題分2030103010XXXXX100得分XXXXX考生注意事項(xiàng)：1、本試卷共工頁(yè)，總分100分,考試時(shí)間120分鐘。2、考試結(jié)束看，考生不得將試卷、答題紙和草稿紙帶出考場(chǎng)。一、選擇題（每題2分，共20分）1、在一個(gè)鏈隊(duì)列中，若f, r分別為隊(duì)首、隊(duì)尾指針,指結(jié)點(diǎn)的操作為（ ）（A） f->next=c； f=s（C） s->next=r； r=s2、下面程序的時(shí)間復(fù)雜度為（for（i=0;i<m;i+）(B) r->next=s； r=s(D)

48、 s->next=f； f=s )for(j=0;j<n;j+)AiQ=iwj；(A) O(M2)(B) O(N2)(C) O(M*N) (D) O(M+N)3、設(shè)高度為h的二叉樹(shù)上只有度為0和度為2的結(jié)點(diǎn)，則此類二義樹(shù)中所包含的結(jié)點(diǎn)數(shù)至少為：()(A) 2h(B) 2h-1(C) 2h+1(D) h+14、設(shè)指針變量p指向單鏈表中結(jié)點(diǎn)A,若刪除單鏈表中結(jié)點(diǎn)A,則需要修改指針的 操作序列為()。(A) q=p->next： p->data=q->data； p->next=q>>next； free(q)：(B) q=p->next： q-

49、>data=p->data； p->next=q->next； free(q)：(C) q=p->next； p->next=q->next； free(q)：(D) q=p->next； p->data=q->data； free(q)；5、含N個(gè)頂點(diǎn)的連通圖中的任意一條簡(jiǎn)單路徑，其長(zhǎng)度不可能超過(guò)()(D)N14, 18, 21, 36, 40, 10),則以20 )°(A) 1(B) N/2(C) N-16、設(shè)一組初始關(guān)鍵字記錄關(guān)鍵字為(20, 15, 為基準(zhǔn)記錄的一趟快速排序結(jié)束后的結(jié)果為(7 7 H/A B c D/

50、10, 15, 14, 18,10, 15, 14, 18,10, 15, 14, 20,15, 10, 14, 18,20, 36,20, 40,18, 40,20,40, 2136, 2136, 2I36, 40, 21第27頁(yè)共5頁(yè)7、若在線性表中采用折半查找法查找元素，該線性表應(yīng)該()o(A)元素按值有序(B)采用順序存儲(chǔ)結(jié)構(gòu)(C)元素按值有序，且采用順序存儲(chǔ)結(jié)構(gòu)(D)元素按值有序，且采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)8、. n個(gè)節(jié)點(diǎn)的完全二叉樹(shù)，編號(hào)為i的節(jié)點(diǎn)是葉子結(jié)點(diǎn)的條件是()o(A) i<n (B) 2"iv=n (C) 2*i+1 >n (D) 2*i>n9、如果只

51、想得到1024個(gè)元素組成的序列中的前5個(gè)最小元素，那么用()方法最快。(A)起泡排序(B)快速排序 (C)堆排序 (D)直接選擇排序10、對(duì)于線性表(7, 34, 77, 25, 64, 49, 20, 14)進(jìn)行散列存儲(chǔ)時(shí)，若選用H(K) =K%7作為散列函數(shù)，則散列地址為0的元素有()個(gè)，(A)1(B)2(C)3(D)4二、填空題(每空2分，共30分)1、對(duì)于一個(gè)長(zhǎng)度為n的順序存儲(chǔ)的線性表，在表頭插入元素的時(shí)間復(fù)雜度為 (1),在表尾插入元素的時(shí)間復(fù)雜度為(2) o2、設(shè)查找表中有100個(gè)元素，如果用二分法查找方法查找數(shù)據(jù)元素X,則最多需要比較 (3) 一次就可以斷定數(shù)據(jù)元素X是否在查找表

52、中3、若無(wú)向圖G中有n個(gè)頂點(diǎn)m條邊，采用鄰接矩陣存儲(chǔ)，則該矩陣中非0元素的 個(gè)數(shù)為 (4)o4、若一棵二義樹(shù)中只有葉子結(jié)點(diǎn)和左、右子樹(shù)皆非空的結(jié)點(diǎn)，設(shè)葉結(jié)點(diǎn)的個(gè)數(shù)為M, 則左、右子樹(shù)皆非空的結(jié)點(diǎn)個(gè)數(shù)為一(5)5、設(shè)數(shù)組data 0m作為循環(huán)隊(duì)列SQ的存儲(chǔ)空間(判斷隊(duì)列滿，少用一個(gè)元素 空間)，front為隊(duì)頭指針，rear為隊(duì)尾指針，則執(zhí)行出隊(duì)操作的語(yǔ)句為(6)06、設(shè)哈夫曼樹(shù)中共有n個(gè)結(jié)點(diǎn)，則該哈夫曼樹(shù)中有(7)個(gè)度數(shù)為1的結(jié)點(diǎn)。7、設(shè)一組初始記錄關(guān)鍵字序列為(49, 38, 65, 97, 76, 13, 27, 50),則以d=4 為增量的一趟希爾排序結(jié)束后的結(jié)果為 (8) o8、隊(duì)列的

53、插入操作在 (9) 進(jìn)行,刪除操作在(10) 進(jìn)行。9、下面程序段的功能是建立二叉樹(shù)的算法，請(qǐng)?jiān)谙聞澗€處填上正確的內(nèi)容。 typedef struct node int data; struct node wlchild; (11) ;)bitree; void createbitree(bitree *&bt) (scanf( "c"，&ch);if(ch=,#t)(12;else bt=(bitree*)malloc(sizeof(bitree);bt->data=ch;(13);createbitree(bt->rchild); )10、下面程序段的功能是利用從尾部插入的方法建立單鏈表的算法，請(qǐng)?jiān)谙聞澗€處 填上正確的內(nèi)容。typedef struct