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

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

2、和等于所有頂點的出度之和。（  ）7. 在采用線性探測法處理沖突的散列表中，所有同義詞在表中相鄰。（  ）8. 內部排序是指排序過程在內存中進行的排序。（  ）9. 拓撲排序是指結點的值是有序排列。 (  )10. AOE網(wǎng)所表示的工程至少所需的時間等于從源點到匯點的最長路徑的長度。 二、選擇題(30分, 每題1.5分)1有一個含頭結點的單鏈表，頭指針為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é)省運算時間。   A、單鏈表              B、雙鏈表       &#

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

8、160;   C、單循環(huán)鏈表            D、順序表6設一個棧的輸入序列為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設循環(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ù)內存單元中，則A5，5的地址是        。   A、1140      

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

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

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

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

18、#160;    D、任一結點無右孩子14在有n個葉子結點的哈夫曼樹中，其結點總數(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一組記錄的關鍵字為（46，79，56，38，40，84），利用快速排序的方法，以第一個記錄為基準得到的一次劃分結果為        。  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;       的結點開始。   A、100            B、60            C、12            D、15三、填空題（40分）1 在順序表（即順序存

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

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

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

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

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

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

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

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

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

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

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

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

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

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

38、全部置為03有一個含頭結點的雙向循環(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 ) 中，用折半法查找關鍵碼值11，所需的關鍵碼比較次數(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對于只在表的首、尾兩端進行插入操作的線性表，宜采用的存儲結構為:A) 順序表 B) 用頭指針表示的循環(huán)單鏈表C) 用尾指針表示的循環(huán)單鏈表 D) 單鏈表8對包含n個元素的哈希表進行查找，平均查找長度為：A) O(log2n) B) O(n) C) O(nlog2n) D) 不直接依賴于n9將一棵有100個結點的完全二叉樹從根這一層開始，每一層從左到右依次對結點進行編號，根結點編號為1，則編號最大的非葉結點的編號為： A、48B、49C

40、、50D、5110某二叉樹結點的中序序列為A、B、C、D、E、F、G，后序序列為B、D、C、A、F、G、E，則其左子樹中結點數(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. 假設用循環(huán)單鏈表實現(xiàn)隊列，若隊列非空，且隊尾指針為R, 則將新結點S加入隊列時，需執(zhí)行下面語句： ； ；R=S；3通常是以算法執(zhí)行所耗費的 和所占用的 來判斷一個算法的優(yōu)劣。4已知一個3行、4列的二維數(shù)組A（各維下標均從1開始），如果按“以列為主”的順序存儲，則排在第8個位置的元素是： 5高度為h的完全二叉樹最少有 個結點。五、構造題（20 分）1

42、（4分）已知數(shù)據(jù)結構DS的定義如下，請給出其邏輯結構圖示。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分）對以下關鍵字序列建立哈希表：（SUN, MON, TUE, WED, THU, FRI, SAT）,哈希函數(shù)

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

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; 七、算法設計題（25分）1 已知一個帶頭結點的整數(shù)單鏈表L，要求將其拆分為一個正整數(shù)單鏈表L1和一個負整數(shù)單鏈表L2。（9分）2 無向圖采用鄰接表存儲結構，編寫算法輸出圖中各連通分量的結點序列。（8分） 3 編