耿國華數(shù)據(jù)結構附錄a樣卷習題答案及b卷習題答案

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

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

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

4、題每題1.51.5分)1有一個含頭結點的單鏈表，頭指針為有一個含頭結點的單鏈表，頭指針為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é)省運算時間。A、單鏈表、單鏈表B、雙鏈表、雙鏈表C、單循環(huán)鏈表、單循環(huán)鏈表D、帶頭結點的雙、帶頭結點的雙循環(huán)鏈表循環(huán)鏈表5若線性表最常用的操作是存取第若線性表最常用的操作是存取第i個元素及其前驅的值，則采用個元素及其

8、前驅的值，則采用存儲方式節(jié)省存儲方式節(jié)省時間。時間。A、單鏈表、單鏈表B、雙鏈表、雙鏈表C、單循環(huán)鏈表、單循環(huán)鏈表D、順序表、順序表6設一個棧的輸入序列為設一個棧的輸入序列為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設循環(huán)隊列中數(shù)組的下標范圍是設循環(huán)隊列中數(shù)組的下標范圍是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ù)內存單元中，則的連續(xù)內存單元中，則A[5A[5，5]5]的地址是的地址是。A、11401140B、11451145C、11201120D、112511251010設一哈希表表長設一哈希表

11、表長M為100100，用除留余數(shù)法構造哈希函數(shù)，即，用除留余數(shù)法構造哈希函數(shù)，即H（K）=K=KMODMODP（P〈=M=M〉為使函數(shù)具有較好性能，為使函數(shù)具有較好性能，P應選應選1111單鏈表與多重鏈表的區(qū)別是單鏈表與多重鏈表的區(qū)別是1212深度為深度為6（根層次為（根層次為1）的二叉樹至多有）的二叉樹至多有個結點。個結點。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所指結點為表尾結點的條件是所指結點為表尾結點的條件是1515在查找方法中，平均查找長度與結點個數(shù)無關的查找方法是在查找方法中，平均查找長度與結點個數(shù)無關的查找方法是。1616隊列的特性是隊列

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

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