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

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

2、和等于所有頂點(diǎn)的出度之和。（  ）7. 在采用線性探測(cè)法處理沖突的散列表中，所有同義詞在表中相鄰。（  ）8. 內(nèi)部排序是指排序過程在內(nèi)存中進(jìn)行的排序。（  ）9. 拓?fù)渑判蚴侵附Y(jié)點(diǎn)的值是有序排列。 (  )10. AOE網(wǎng)所表示的工程至少所需的時(shí)間等于從源點(diǎn)到匯點(diǎn)的最長(zhǎng)路徑的長(zhǎng)度。 二、選擇題(30分, 每題1.5分)1有一個(gè)含頭結(jié)點(diǎn)的單鏈表，頭指針為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鏈表不具有的特點(diǎn)是       

5、。   A、可隨機(jī)訪問任一個(gè)元素                        B、插入刪除不需要移動(dòng)元素   C、不必事先估計(jì)存儲(chǔ)空間                &

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

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

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

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

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

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

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

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

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

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

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

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

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

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

20、60;  B、有一棵或多棵         C、一定有多棵            D、可能不存在17一組記錄的關(guān)鍵字為（46，79，56，38，40，84），利用快速排序的方法，以第一個(gè)記錄為基準(zhǔn)得到的一次劃分結(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中每個(gè)元素距其最終位置不遠(yuǎn)，則采用        排序算法最節(jié)省時(shí)間。    A、堆排序        B、插入排序    C、快速排序    D、直接選擇排序19下列排序算法中，     &

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

38、全部置為03有一個(gè)含頭結(jié)點(diǎn)的雙向循環(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. 以下哪一個(gè)不是隊(duì)列的基本運(yùn)算？A）從隊(duì)尾插入一個(gè)新元素 B）從隊(duì)列中刪除第i個(gè)元素 C）判斷一個(gè)隊(duì)列是否為空 D）讀取

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

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

42、（4分）已知數(shù)據(jù)結(jié)構(gòu)DS的定義如下，請(qǐng)給出其邏輯結(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分）對(duì)以下關(guān)鍵字序列建立哈希表：（SUN, MON, TUE, WED, THU, FRI, SAT）,哈希函數(shù)

43、為H(K) =（K中最后一個(gè)字母在字母表中的序號(hào)）MOD 7。用線性探測(cè)法處理沖突，要求構(gòu)造一個(gè)裝填因子為0.7的哈希表，并計(jì)算出在等概率情況下查找成功的平均查找長(zhǎng)度。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 ，要求給出哈夫曼樹，并計(jì)算其帶權(quán)路徑長(zhǎng)度WPL。六、算法分析題（10分）閱讀下面程序，并回答有關(guān)問題。其中BSTree為用二叉鏈表表示的二叉排序樹類型。（1） 簡(jiǎn)要說明程序功能。（5分）（2） n個(gè)結(jié)點(diǎn)的滿二叉樹的深度h是多少？（3分）（3） 假設(shè)二叉排序樹*bst是有n個(gè)結(jié)點(diǎn)的

44、滿二叉樹,給出算法的時(shí)間復(fù)雜度。（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è)計(jì)題（25分）1 已知一個(gè)帶頭結(jié)點(diǎn)的整數(shù)單鏈表L，要求將其拆分為一個(gè)正整數(shù)單鏈表L1和一個(gè)負(fù)整數(shù)單鏈表L2。（9分）2 無向圖采用鄰接表存儲(chǔ)結(jié)構(gòu)，編寫算法輸出圖中各連通分量的結(jié)點(diǎn)序列。（8分） 3 編