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

1、 數(shù)據(jù)結(jié)構(gòu) 附錄A 樣卷一一、判斷題：（10 分）  正確在括號內(nèi)打，錯誤打× (  ) 1.在單鏈表中，頭結(jié)點是必不可少的。（  ）2如果一個二叉樹中沒有度為1的結(jié)點，則必為滿二叉樹。 (  ) 3. 循環(huán)鏈表的結(jié)點結(jié)構(gòu)與單鏈表的結(jié)點結(jié)構(gòu)完全相同，只是結(jié)點間的連接方式不同。 (  ) 4. 順序存儲結(jié)構(gòu)只能用來存放線性結(jié)構(gòu)；鏈式存儲結(jié)構(gòu)只能用來存放非線性結(jié)構(gòu)。 (  ) 5. 在一個大根堆中，最小元素不一定在最后。 (  ) 6. 在一個有向圖中，所有頂點的入度之

2、和等于所有頂點的出度之和。（  ）7. 在采用線性探測法處理沖突的散列表中，所有同義詞在表中相鄰。（  ）8. 內(nèi)部排序是指排序過程在內(nèi)存中進行的排序。（  ）9. 拓撲排序是指結(jié)點的值是有序排列。 (  )10. AOE網(wǎng)所表示的工程至少所需的時間等于從源點到匯點的最長路徑的長度。 二、選擇題(30分, 每題1.5分)1有一個含頭結(jié)點的單鏈表，頭指針為head,  則判斷其是否為空的條件為：_   A head=NIL     B. head.next=NIL&#

3、160;     C.  head.next=head    D. head<>NIL或 A head=NULL  B. Head->next=NULL  C.  head->next=head  D. Head!=NULL2非空的循環(huán)單鏈表head的尾指針p滿足_。   A.  p.next=NIL      B.  p=NIL   

4、;      C.  p.next=head      D.  p=head或 A.  p->next=NULL    B.  p=NULL     C.  P->next=head     D.  p=head3鏈表不具有的特點是       

5、。   A、可隨機訪問任一個元素                        B、插入刪除不需要移動元素   C、不必事先估計存儲空間                &

6、#160;       D、所需空間與線性表的長度成正比4若某鏈表中最常用的操作是在最后一個結(jié)點之后插入一個結(jié)點和刪除最后一個結(jié)點，則采用        存儲方式最節(jié)省運算時間。   A、單鏈表              B、雙鏈表       &#

7、160;    C、單循環(huán)鏈表     D、帶頭結(jié)點的雙循環(huán)鏈表5若線性表最常用的操作是存取第i個元素及其前驅(qū)的值，則采用        存儲方式節(jié)省時間。   A、單鏈表              B、雙鏈表        &#

8、160;   C、單循環(huán)鏈表            D、順序表6設(shè)一個棧的輸入序列為A，B，C，D，則借助一個棧所得到的輸出序列不可能的是        。    A、 A，B，C，D               

9、60;                    B、D，C，B，AC、 A，C，D，B                           &

10、#160;        D、D，A，B，C7一個隊列的入隊序列是1，2，3，4，則隊列的輸出序列是        。   A、4，3，2，1              B、1，2，3，4     C、1，4，3，2     D、

11、3，2，4，18設(shè)循環(huán)隊列中數(shù)組的下標范圍是1n，其頭尾指針分別為f，r，若隊列中元素個數(shù)為        。   A、r-f                    B 、r-f+1           

12、60; C、（r-f+1）mod n    D、（r-f+n）mod n9串是        。   A、不少于一個字母的序列                        B、任意個字母的序列   C、不少于一個字符的序列 &#

13、160;                      D、有限個字符的序列10數(shù)組A1.5,1.6的每個元素占5個單元，將其按行優(yōu)先次序存儲在起始地址為1000的連續(xù)內(nèi)存單元中，則A5，5的地址是        。   A、1140      

14、;    B、1145         C、1120         D、112511將一棵有100個結(jié)點的完全二叉樹從根這一層開始，每一層從左到右依次對結(jié)點進行編號，根結(jié)點編號為1，則編號為49的結(jié)點的左孩子的編號為        。   A、98      

15、;        B、99            C、50            D、4812對二叉樹從1開始編號，要求每個結(jié)點的編號大于其左右孩子的編號，同一個結(jié)點的左右孩子中，其左孩子的編號小于其右孩子的編號， 則可采用       

16、實現(xiàn)編號。  A、先序遍歷            B、中序遍歷         C、后序遍歷        D、從根開始進行層次遍歷13某二叉樹的先序序列和后序序列正好相反，則該二叉樹一定是        的二叉樹。  A、空或只有一個結(jié)點 

17、;                         B、高度等于其結(jié)點數(shù)  C、任一結(jié)點無左孩子                     &

18、#160;    D、任一結(jié)點無右孩子14在有n個葉子結(jié)點的哈夫曼樹中，其結(jié)點總數(shù)為        。  A、不確定 B、2n     C、2n+1        D、2n-115一個有n個頂點的無向圖最多有        條邊。  A、n     

19、     B、n（n-1）         C、n（n-1）/2             D、2n16任何一個無向連通圖的最小生成樹        。  A、只有一棵         

20、60;  B、有一棵或多棵         C、一定有多棵            D、可能不存在17一組記錄的關(guān)鍵字為（46，79，56，38，40，84），利用快速排序的方法，以第一個記錄為基準得到的一次劃分結(jié)果為        。  A、38，40，46，56，79，84  B、40，38，46，79，5

21、6，84  C、40，38，46，56，79，84  D、40，38，46，84，56，7918已知數(shù)據(jù)表A中每個元素距其最終位置不遠，則采用        排序算法最節(jié)省時間。    A、堆排序        B、插入排序    C、快速排序    D、直接選擇排序19下列排序算法中，     &

22、#160;  算法可能會出現(xiàn)下面情況：初始數(shù)據(jù)有序時，花費時間反而最多。    A、堆排序            B、冒泡排序         C、快速排序        D、SHELL 排序20對于鍵值序列（12，13，11，18，60，15，7，18，25，100），用篩選法建堆，必須從鍵值為&

23、#160;       的結(jié)點開始。   A、100            B、60            C、12            D、15三、填空題（40分）1 在順序表（即順序存

24、儲結(jié)構(gòu)的線性表）中插入一個元素，需要平均動       個元素.2.         快速排序的最壞情況，其待排序的初始排列是                           .3. 

25、為防止在圖中走回，應(yīng)設(shè)立                             .4. 一個棧的輸入序列為123，寫出不可能是棧的輸出序列               

26、   。5. N個結(jié)點的二叉樹,采用二叉鏈表存放,空鏈域的個數(shù)為             .6. 要在一個單鏈表中p所指結(jié)點之后插入s所指結(jié)點時,     應(yīng)執(zhí)行                    和    

27、;                   的操作. 7.Dijkstra算法是按                   的次序產(chǎn)生一點到其余各頂點最短路徑的算法.8.在N個結(jié)點完全二叉樹中，其深度是  &

28、#160;                    .9.對二叉排序樹進行          遍歷, 可得到結(jié)點的有序排列.10設(shè)一哈希表表長M為100 ，用除留余數(shù)法構(gòu)造哈希函數(shù)，即H（K）=K MOD P（P=M,  為使函數(shù)具有較好性能，P應(yīng)選      

29、                11單鏈表與多重鏈表的區(qū)別是                  12深度為6（根層次為1）的二叉樹至多有            

30、    個結(jié)點。13已知二維數(shù)組A0.200.10采用行序為主方式存儲，每個元素占4個存儲單元,并且A00的存儲地址是1016, 則A105的存儲地址是             14循環(huán)單鏈表La中，指針P所指結(jié)點為表尾結(jié)點的條件是              15在查找方法中，平均查找長度與結(jié)點個數(shù)無關(guān)的查找

31、方法是               。16隊列的特性是                  17具有3個結(jié)點的二叉樹有           種18已知一棵二叉樹的前序序列為ABDFCE，中序序

32、列為DFBACE，后序序列為           19已知一個圖的鄰接矩陣表示，要刪除所有從第i個結(jié)點出發(fā)的邊，在鄰接矩陣運算是                          四、構(gòu)造題：（30 分）1已知關(guān)鍵字序列為：（75, 33, 52,

33、41, 12, 88, 66, 27）哈希表長為10，哈希函數(shù)為：H(k)=K MOD 7, 解決沖突用線性探測再散列法，構(gòu)造哈希表，求等概率下查找成功的平均查找長度。 2已知無向圖如圖1所示，    （1）給出圖的鄰接表。    （2）從A開始，給出一棵廣度優(yōu)先生成樹。 3給定葉結(jié)點權(quán)值：（1，3，5，6，7，8），構(gòu)造哈夫曼樹，并計算其帶權(quán)路徑長度。4從空樹開始，逐個讀入并插入下列關(guān)鍵字，構(gòu)造一棵二叉排序樹：      （24，88，42，97，22，15，7，

34、13）。  5對長度為8的有序表，給出折半查找的判定樹，給出等概率情況下的平均查找長度。  6已知一棵樹如圖2所示，要求將該樹轉(zhuǎn)化為二叉樹。         五、算法設(shè)計題(40分)算法題可用類PASCAL或類C語言,每題20分 1  已知一棵二叉樹采用二叉鏈表存放，寫一算法，要求統(tǒng)計出二叉樹中葉子結(jié)點個數(shù)并輸出二叉樹中非終端結(jié)點（輸出無順序要求）。2編寫算法，判斷帶頭結(jié)點的雙循環(huán)鏈表L是否對稱。對稱是指：設(shè)各元素值a1,a2,.,an, 則有ai=an-

35、i+1   即指：a1= an，a2= an-1  。    結(jié)點結(jié)構(gòu)為 priordatanext 數(shù)據(jù)結(jié)構(gòu) 附錄B 樣卷二一、簡答題（15分，每小題3分）1. 簡要說明算法與程序的區(qū)別。2. 在哈希表中，發(fā)生沖突的可能性與哪些因素有關(guān)？為什么？3. 說明在圖的遍歷中，設(shè)置訪問標志數(shù)組的作用。4. 說明以下三個概念的關(guān)系：頭指針，頭結(jié)點，首元素結(jié)點。5. 在一般的順序隊列中，什么是假溢出？怎樣解決假溢出問題？二、判斷題（10分，每小題1分） 正確在括號內(nèi)打，錯誤打×( )（1）廣義表( a ), b), c )

36、的表頭是( a ), b)，表尾是( c )。( )（2）在哈夫曼樹中，權(quán)值最小的結(jié)點離根結(jié)點最近。( )（3）基數(shù)排序是高位優(yōu)先排序法。( )（4）在平衡二叉樹中，任意結(jié)點左右子樹的高度差（絕對值）不超過1。( )（5）在單鏈表中，給定任一結(jié)點的地址p，則可用下述語句將新結(jié)點s插入結(jié)點p的后面 ：p->next = s; s->next = p->next;( )（6）抽象數(shù)據(jù)類型（ADT）包括定義和實現(xiàn)兩方面，其中定義是獨立于實現(xiàn)的，定義僅給出一個ADT的邏輯特性，不必考慮如何在計算機中實現(xiàn)。( )（7）數(shù)組元素的下標值越大，存取時間越長。( )（8）用鄰接矩陣法存儲一個

37、圖時，在不考慮壓縮存儲的情況下，所占用的存儲空間大小只與圖中結(jié)點個數(shù)有關(guān)，而與圖的邊數(shù)無關(guān)。( )（9）拓撲排序是按AOE網(wǎng)中每個結(jié)點事件的最早發(fā)生時間對結(jié)點進行排序。( )（10）長度為1的串等價于一個字符型常量。三、單項選擇題（10分, 每小題1分）1排序時掃描待排序記錄序列，順次比較相鄰的兩個元素的大小，逆序時就交換位置。這是哪種排序方法的基本思想？ A、堆排序B、直接插入排序C、快速排序D、冒泡排序2 已知一個有向圖的鄰接矩陣表示，要刪除所有從第i個結(jié)點發(fā)出的邊，應(yīng)該：A）將鄰接矩陣的第i行刪除 B）將鄰接矩陣的第i行元素全部置為0C）將鄰接矩陣的第i列刪除 D）將鄰接矩陣的第i列元素

38、全部置為03有一個含頭結(jié)點的雙向循環(huán)鏈表，頭指針為head, 則其為空的條件是：A. head->priro=NULL B. head->next=NULL C. head->next=head D. head->next-> priro=NULL4. 在順序表 ( 3, 6, 8, 10, 12, 15, 16, 18, 21, 25, 30 ) 中，用折半法查找關(guān)鍵碼值11，所需的關(guān)鍵碼比較次數(shù)為： A) 2 B) 3 C) 4 D) 55. 以下哪一個不是隊列的基本運算？A）從隊尾插入一個新元素 B）從隊列中刪除第i個元素 C）判斷一個隊列是否為空 D）讀取

39、隊頭元素的值6. 在長度為n的順序表的第i個位置上插入一個元素（1 i n+1），元素的移動次數(shù)為：A) n i + 1 B) n i C) i D) i 1 7對于只在表的首、尾兩端進行插入操作的線性表，宜采用的存儲結(jié)構(gòu)為:A) 順序表 B) 用頭指針表示的循環(huán)單鏈表C) 用尾指針表示的循環(huán)單鏈表 D) 單鏈表8對包含n個元素的哈希表進行查找，平均查找長度為：A) O(log2n) B) O(n) C) O(nlog2n) D) 不直接依賴于n9將一棵有100個結(jié)點的完全二叉樹從根這一層開始，每一層從左到右依次對結(jié)點進行編號，根結(jié)點編號為1，則編號最大的非葉結(jié)點的編號為： A、48B、49C

40、、50D、5110某二叉樹結(jié)點的中序序列為A、B、C、D、E、F、G，后序序列為B、D、C、A、F、G、E，則其左子樹中結(jié)點數(shù)目為：A）3 B）2 C）4 D）5四、填空題（10分，每空1分）1填空完成下面一趟快速排序算法：int QKPass ( RecordType r , int low， int high) x = r low ； while ( low < high )while ( low < high && r . key >= x.key ) high - -；if ( low < high ) r = r high ； low+; wh

41、ile ( low < high && r . key < x. key ) low+;if ( low < high ) r = r low ； high-; r low = x； return low ; 2. 假設(shè)用循環(huán)單鏈表實現(xiàn)隊列，若隊列非空，且隊尾指針為R, 則將新結(jié)點S加入隊列時，需執(zhí)行下面語句： ； ；R=S；3通常是以算法執(zhí)行所耗費的 和所占用的 來判斷一個算法的優(yōu)劣。4已知一個3行、4列的二維數(shù)組A（各維下標均從1開始），如果按“以列為主”的順序存儲，則排在第8個位置的元素是： 5高度為h的完全二叉樹最少有 個結(jié)點。五、構(gòu)造題（20 分）1

42、（4分）已知數(shù)據(jù)結(jié)構(gòu)DS的定義如下，請給出其邏輯結(jié)構(gòu)圖示。DS = (D, R)D = a, b, c, d, e, f, g R = T T = <a, b>, <a, g>, <b, g>, <c, b>, <d, c>, <d, f>, <e, d>, <f, a>, <f, e>, <g, c>, <g, d>, <g, f> 2（6分）對以下關(guān)鍵字序列建立哈希表：（SUN, MON, TUE, WED, THU, FRI, SAT）,哈希函數(shù)

43、為H(K) =（K中最后一個字母在字母表中的序號）MOD 7。用線性探測法處理沖突，要求構(gòu)造一個裝填因子為0.7的哈希表，并計算出在等概率情況下查找成功的平均查找長度。3.（6分）將關(guān)鍵字序列（3，26，12，61，38，40，97，75，53， 87）調(diào)整為大根堆。4（4分）已知權(quán)值集合為： 5，7，2，3，6，9 ，要求給出哈夫曼樹，并計算其帶權(quán)路徑長度WPL。六、算法分析題（10分）閱讀下面程序，并回答有關(guān)問題。其中BSTree為用二叉鏈表表示的二叉排序樹類型。（1） 簡要說明程序功能。（5分）（2） n個結(jié)點的滿二叉樹的深度h是多少？（3分）（3） 假設(shè)二叉排序樹*bst是有n個結(jié)點的

44、滿二叉樹,給出算法的時間復雜度。（2分）int Proc (BSTree *bst, KeyType K) BSTree f, q, s;s=(BSTree)malloc(sizeof(BSTNode); s-> key = K; s-> lchild = NULL; s-> rchild = NULL; if ( *bst = NULL ) *bst = s; return 1; f = NULL; q = *bst; while( q != NULL ) if ( K < q -> key ) f = q; q = q -> lchild; else f = q; q = q -> rchild; if ( K < f -> key ) f -> lchild = s; else f -> rchild = s; return 1; 七、算法設(shè)計題（25分）1 已知一個帶頭結(jié)點的整數(shù)單鏈表L，要求將其拆分為一個正整數(shù)單鏈表L1和一個負整數(shù)單鏈表L2。（9分）2 無向圖采用鄰接表存儲結(jié)構(gòu)，編寫算法輸出圖中各連通分量的結(jié)點序列。（8分） 3 編