耿國華數(shù)據(jù)結(jié)構(gòu)附錄a樣卷習(xí)題答案及b卷習(xí)題答案

1、數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)附錄附錄A樣卷一樣卷一一、判斷題：（一、判斷題：（1010分）分）正確在括號內(nèi)打√，錯誤打正確在括號內(nèi)打√，錯誤打()1.1.在單鏈表中，頭結(jié)點是必不可少的。在單鏈表中，頭結(jié)點是必不可少的。（）2如果一個二叉樹中沒有度為如果一個二叉樹中沒有度為1的結(jié)點，則必為滿二叉樹。的結(jié)點，則必為滿二叉樹。()3.3.循環(huán)鏈表的結(jié)點結(jié)構(gòu)與單鏈表的結(jié)點結(jié)構(gòu)完全相同，只是結(jié)點間的連接方式不循環(huán)鏈表的結(jié)點結(jié)構(gòu)與單鏈表的結(jié)點結(jié)構(gòu)完全相同，只是

2、結(jié)點間的連接方式不同。同。()4.4.順序存儲結(jié)構(gòu)只能用來存放線性結(jié)構(gòu)；鏈?zhǔn)酱鎯Y(jié)構(gòu)只能用來存放非線性結(jié)構(gòu)。順序存儲結(jié)構(gòu)只能用來存放線性結(jié)構(gòu)；鏈?zhǔn)酱鎯Y(jié)構(gòu)只能用來存放非線性結(jié)構(gòu)。()5.5.在一個大根堆中，最小元素不一定在最后。在一個大根堆中，最小元素不一定在最后。()6.6.在一個有向圖中，所有頂點的入度之和等于所有頂點的出度之和。在一個有向圖中，所有頂點的入度之和等于所有頂點的出度之和。（）7.7.在采用線性探測法處理沖突的散列表中

3、，所有同義詞在表中相鄰。在采用線性探測法處理沖突的散列表中，所有同義詞在表中相鄰。（）8.8.內(nèi)部排序是指排序過程在內(nèi)存中進行的排序。內(nèi)部排序是指排序過程在內(nèi)存中進行的排序。（）9.9.拓撲排序是指結(jié)點的值是有序排列。拓撲排序是指結(jié)點的值是有序排列。()10.)10.AOEAOE網(wǎng)所表示的工程至少所需的時間等于從源點到匯點的最長路徑的長度。網(wǎng)所表示的工程至少所需的時間等于從源點到匯點的最長路徑的長度。二、選擇題二、選擇題(30(30分每

4、題每題1.51.5分)1有一個含頭結(jié)點的單鏈表，頭指針為有一個含頭結(jié)點的單鏈表，頭指針為headhead則判斷其是否為空的條件為：則判斷其是否為空的條件為：________________________________Ahead=NILhead=NILB.B.head^.next=NILhead^.next=NILC.C.head^.next=headhead^.next=headD.D.headNIL或Ahead==NULLhead

5、==NULLB.B.Headnext==NULLHeadnext==NULLC.C.headnext==headheadnext==headD.D.Head!=NULLHead!=NULL2非空的循環(huán)單鏈表非空的循環(huán)單鏈表headhead的尾指針的尾指針p滿足滿足____________________________。A.A.p^.next=NILp^.next=NILB.B.p=NILp=NILC.C.p^.next=headp^.

6、next=headD.D.p=headp=head或A.A.pnext=NULLpnext=NULLB.B.p==NULLp==NULLC.C.Pnext==headPnext==headD.D.p==headp==head3鏈表不具有的特點是鏈表不具有的特點是。A、可隨機訪問任一個元素、可隨機訪問任一個元素B、插入刪除不需要移動元素、插入刪除不需要移動元素C、不必事先估計存儲空間、不必事先估計存儲空間D、所需空間與線性表的長度成正、所

7、需空間與線性表的長度成正比4若某鏈表中最常用的操作是在最后一個結(jié)點之后插入一個結(jié)點和刪除最后一個結(jié)點，則若某鏈表中最常用的操作是在最后一個結(jié)點之后插入一個結(jié)點和刪除最后一個結(jié)點，則采用采用存儲方式最節(jié)省運算時間。存儲方式最節(jié)省運算時間。A、單鏈表、單鏈表B、雙鏈表、雙鏈表C、單循環(huán)鏈表、單循環(huán)鏈表D、帶頭結(jié)點的雙、帶頭結(jié)點的雙循環(huán)鏈表循環(huán)鏈表5若線性表最常用的操作是存取第若線性表最常用的操作是存取第i個元素及其前驅(qū)的值，則采用個元素及其

8、前驅(qū)的值，則采用存儲方式節(jié)省存儲方式節(jié)省時間。時間。A、單鏈表、單鏈表B、雙鏈表、雙鏈表C、單循環(huán)鏈表、單循環(huán)鏈表D、順序表、順序表6設(shè)一個棧的輸入序列為設(shè)一個棧的輸入序列為A，B，C，D，則借助一個棧所得到的輸出序列不可能的，則借助一個棧所得到的輸出序列不可能的是。A、A，B，C，DB、D，C，B，AC、A，C，D，BD、D，A，B，C7一個隊列的入隊序列是一個隊列的入隊序列是1，2，3，4，則隊列的輸出序列是，則隊列的輸出序列是。A

9、、4，3，2，1B、1，2，3，4C、1，4，3，2D、3，2，4，18設(shè)循環(huán)隊列中數(shù)組的下標(biāo)范圍是設(shè)循環(huán)隊列中數(shù)組的下標(biāo)范圍是1~n1~n，其頭尾指針分別為，其頭尾指針分別為f，r，若隊列中元素個數(shù)，若隊列中元素個數(shù)為。A、rfrfB、rf1rf1C、（、（rf1rf1）modmodnD、（、（rrfnfn）modmodn9串是串是。A、不少于一個字母的序列、不少于一個字母的序列B、任意個字母的序列、任意個字母的序列C、不少于一個字符

10、的序列、不少于一個字符的序列D、有限個字符的序列、有限個字符的序列1010數(shù)組數(shù)組A[1..51..6]A[1..51..6]的每個元素占的每個元素占5個單元，將其按行優(yōu)先次序存儲在起始地址為個單元，將其按行優(yōu)先次序存儲在起始地址為10001000的連續(xù)內(nèi)存單元中，則的連續(xù)內(nèi)存單元中，則A[5A[5，5]5]的地址是的地址是。A、11401140B、11451145C、11201120D、112511251010設(shè)一哈希表表長設(shè)一哈希表

11、表長M為100100，用除留余數(shù)法構(gòu)造哈希函數(shù)，即，用除留余數(shù)法構(gòu)造哈希函數(shù)，即H（K）=K=KMODMODP（P〈=M=M〉為使函數(shù)具有較好性能，為使函數(shù)具有較好性能，P應(yīng)選應(yīng)選1111單鏈表與多重鏈表的區(qū)別是單鏈表與多重鏈表的區(qū)別是1212深度為深度為6（根層次為（根層次為1）的二叉樹至多有）的二叉樹至多有個結(jié)點。個結(jié)點。1313已知二維數(shù)組已知二維數(shù)組A[0..20][0..10]A[0..20][0..10]采用行序為主方式存儲

12、，每個元素占采用行序為主方式存儲，每個元素占4個存儲單元個存儲單元并且A[0][0]A[0][0]的存儲地址是的存儲地址是10161016則A[10][5]A[10][5]的存儲地址是的存儲地址是1414循環(huán)單鏈表循環(huán)單鏈表LaLa中，指針中，指針P所指結(jié)點為表尾結(jié)點的條件是所指結(jié)點為表尾結(jié)點的條件是1515在查找方法中，平均查找長度與結(jié)點個數(shù)無關(guān)的查找方法是在查找方法中，平均查找長度與結(jié)點個數(shù)無關(guān)的查找方法是。1616隊列的特性是隊列

13、的特性是1717具有具有3個結(jié)點的二叉樹有個結(jié)點的二叉樹有種1818已知一棵二叉樹的前序序列為已知一棵二叉樹的前序序列為ABDFCEABDFCE，中序序列為，中序序列為DFBACEDFBACE，后序序列為，后序序列為1919已知一個圖的鄰接矩陣表示，要刪除所有從第已知一個圖的鄰接矩陣表示，要刪除所有從第i個結(jié)點出發(fā)的邊，在鄰接矩陣運算是個結(jié)點出發(fā)的邊，在鄰接矩陣運算是四、構(gòu)造題：（四、構(gòu)造題：（3030分）分）1已知關(guān)鍵字序列為：（已知

14、關(guān)鍵字序列為：（75753333525241411212888866662727）哈希表長為）哈希表長為1010，哈希函數(shù)，哈希函數(shù)為：為：H(k)=KH(k)=KMODMOD77解決沖突用線性探測再散列法，構(gòu)造哈希表，求等概率下查找成功的平均查解決沖突用線性探測再散列法，構(gòu)造哈希表，求等概率下查找成功的平均查找長度。找長度。2已知無向圖如圖已知無向圖如圖1所示，所示，（1）給出圖的鄰接表。）給出圖的鄰接表。（2）從）從A開始，給出一棵