數(shù)據(jù)結構復習習題和答案

1、第一章 緒論 一、 單項選擇題1 數(shù)據(jù)結構是一門研究非數(shù)值計算的程序設計問題中計算機的以及它們之間的和操作等的學科。 A.操作對象 B計算方法 C·邏輯存儲 D.數(shù)據(jù)映象 A.結構 B關系 C運算 D.算法2數(shù)據(jù)結構被形式地定義為（D，R），其中D是的有限集合，R是D上的有限集合。 A.算法 B.數(shù)據(jù)元素 C數(shù)據(jù)操作 D邏輯結構 A.操作 B.映象 C、存儲 D.關系3在數(shù)據(jù)結構中，從邏輯上可以把數(shù)據(jù)結構分成（ ）。A.動態(tài)結構和靜態(tài)結構 B緊湊結構和非緊湊結構C.線性結構和非線性結構 D內部結構和外部結構 4·算法分析的目的是，算法分析的兩個主要方面是。 A. 找出數(shù)據(jù)結

2、構的合理性 B研究算法中的輸入和輸出的關系 C. 分析算法的效率以求改進 D. 分析算法的易懂性和文檔性 A. 空間復雜性和時間復雜性 B正確性和簡明性 C可讀性和文檔性 D數(shù)據(jù)復雜性和程序復雜性 5計算機算法指的是，它必具備輸入、輸出和等五個特性。 A. 計算方法 B排序方法 C. 解決問題的有限運算序列 D調度方法 A. 可行性、可移植性和可擴充性 B. 可行性、確定性和有窮性 C. 確定性、有窮性和穩(wěn)定性 D易讀性、穩(wěn)定性和安全性 6. 線性表的邏輯順序與存儲順序總是一致的，這種說法（ ）。 A. 正確 B不正確 7. 線性表若采用鏈式存儲結構時，要求內存中可用存儲單元的地址（ ）。 A

3、. 必須是連續(xù)的 B部分地址必須是連續(xù)的 C. 一定是不連續(xù)的 D. 連續(xù)或不連續(xù)都可以 8數(shù)據(jù)結構通常是研究數(shù)據(jù)的（ ）及它們之間的相互聯(lián)系。 A存儲和邏輯結構 B存儲和抽象 C理想與抽象 D理想與邏輯 9數(shù)據(jù)在計算機存儲器內表示時，物理地址與邏輯地址相同并且是連續(xù)的，稱之為（）。 A存儲結構 B邏輯結構 C順序存儲結構 D鏈式存儲結構 11非線性結構是數(shù)據(jù)元素之間存在一種（）。 A一對多關系 B多對多關系 C多對一關系 D一對一關系 12非線性結構中，每個結點（）。 A無直接前趨 B只有一個直接前驅和后繼 C只有一個直接前趨和個數(shù)受限制的直接后繼 D有個數(shù)不受限制的直接前趨和后繼 13除了

4、考慮存儲數(shù)據(jù)結構本身所占用的空間外，實現(xiàn)算法所用輔助空間的多少稱為（）。 A時間效率 B空間效率 C硬件效率 D軟件效率 14鏈式存儲的存儲結構所占存儲空間（）。 A分兩部分，一部分存放結點值，另一部分存放表示結點間關系的指針 B只有一部分，存放結點值 C只有一部分，存儲表示結點間關系的指針 D分兩部分，一部分存放結點值，另一部分存放結點所占單元數(shù) 15設語句x十的時間是單位時間，則語句： for（il；in；i） X； 的時間復雜度為（）。 AO（l） BO（n） CO（n2） DO（n3）二、 填空題 1數(shù)據(jù)元素之間的關系稱為（結構），通常分為4種（ 集合 ）（ 線性結構 ）（樹形結構）（

5、圖狀結構或網(wǎng)狀結構）。 2在線性結構中，第一個結點（無）前驅結點，其余每個結點有且只有（ 1 ）個前驅結點；最后一個結點（ 無 ）后續(xù)結點，其余每個結點有且只有（ 1 ）個后續(xù)結點。 3在樹形結構中，樹根結點沒有（ 前驅）結點，其余每個結點有且只有（ 1 ）個前驅結點；葉子結點沒有（ 后繼）結點，其余每個結點的后繼結點可以（ 多個 ）。 4在圖形結構中，每個結點的前驅結點數(shù)和后續(xù)結點數(shù)可以（ 多個 ）。 5線性結構中元素之間存在（ 一對一）關系，樹形結構中元素之間存在（ 一對多 ）關系，圖形結構中元素之間存在（ 多對多 ）關系。 6下面程序段的時間復雜度是（ O( mn ) ）。 for（i0

6、；i<n；i） for（j0；jm；j） Aij=0； 7數(shù)據(jù)結構包括數(shù)據(jù)的(邏輯結構)、數(shù)據(jù)的( 存儲結構 )。 8數(shù)據(jù)結構按邏輯結構可分為兩大類，它們分別是（線性結構）和（非線性結構）。 9數(shù)據(jù)的存儲結構分為（順序存儲結構）和（鏈式存儲結構 ）。10一個算法的效率可分為（ 時間 ）效率和（ 空間）效率。11.數(shù)據(jù)元素是數(shù)據(jù)的（基本）單位，（數(shù)據(jù)項）是數(shù)據(jù)的最小單位。12數(shù)據(jù)對象是（ 性質 ）相同數(shù)據(jù)元素的集合。 三、閱讀理解題 設n為正整數(shù)，利用大“O”記號，將下列程序段的執(zhí)行時間表示為n的函數(shù)。 x0； for(i=l; in;i) for（j=i+1; jn; j） x+;答案：

7、n(n+1)/2 ,即O( n2 )第2章 線性表一、單項選擇題：1線性表的的順序存儲結構是一種( )的存儲結構，線性表的鏈式存儲結構是一種（ ）的存儲結構。 A·隨機存取 B.順序存取 C索引存取 D散列存取 2在以下的敘述中，正確的是( )。 A. 線性表的順序存儲結構優(yōu)于鏈表存儲結構 B二維數(shù)組是其數(shù)據(jù)元素為線性表的線性表 C棧的操作方式是先進先出 D. 隊列的操作方式是先進后出 3不帶頭結點的單鏈表head為空的判定條件是( )。A. head=NULL Bheadnext=NULL Cheadnext=head Dhead！=NULL 4帶頭結點的單鍵表head為空的判定條

8、件是( )。A. head=NULL Bheadnext=NULL Cheadnext=head Dhead！=NULL 5非空的循環(huán)單鏈表head的尾結點（由p所指向）滿足( )。 A. pnext=NULL Bp=NULL Cp->next=head D p=head 6在一個單鏈表中，已知q所指結點是p所指結點的前驅結點，若在q和p之間插入s結點，則執(zhí)行( )。 A s-nextp-next；p-nexts； B p-nexts-next；s-next=p； C q-nexts；s-nextp； D p-nexts；s-nextq； 7在單鏈表中，若p所指結點不是最后結點，在p之后

9、插入S所指結點，則執(zhí)行( )。 A Snext=P；Pnext=s； Bs-next=p-next；p-nexts； Cs-nextp-next；ps； D p-nexts；s-nextp； 8在一個單鏈表中，若刪除P所指結點的后繼結點，則執(zhí)行( )。 A p-nextp-next-next； B pp-next；p-nextp-next-next； Cpnextp-next； D ppnext-next 9從一個具有n個結點的單鏈表中查找其值等于x結點時，在查找成功的情況下，需平均比較( )個結點。 A. n Bn2 C（nl）2 D（n十1）2 10在具有n個結點的有序單鏈表中插入一個新結

10、點并仍然有序的時間復雜度是( )。 A. O（l） BO（n） CO（n2） DO（nlog2n） 11用單鏈表方式存儲的線性表，每個結點需要兩個域，一個是數(shù)據(jù)域，另一個是（）。 A當前結點所在地址域 B.指針域 C空指針域 D空閑域 12在具有n個結點的單鏈表中，實現(xiàn)（）的操作，其算法的時間復雜度都是O（n）。 A遍歷鏈表和求鏈表的第i個結點 B在地址為P的結點之后插入一個結點 C刪除開始結點 D刪除地址為p的結點的后繼結點 13.單鏈表的存儲密度（）。 A.大于1 B.等于1 C小于1 D不能確定 14.已知一個順序存儲的線性表，設每個結點需占m個存儲單元，若第一個結點的地址為dal，則第

11、i個結點的地址為（）。 A. dal（i l）*m Bdali*m C dal-i*m D da1（i+ 1）*m 二、填空題： 1在線性結構中，第一個結點（無）前驅結點，其余每個結點有且只有（1）個前驅結點；最后一個結點（無）后續(xù)結點，其余每個結點有且只有（1）個后續(xù)結點。 2單鏈表是（線性表）的鏈式存儲表示。 3若數(shù)組第一個元素的存儲地址是100，每個元素的長度為2，則第5個元素的地址是（108）。 4.在一個長度為n的線性表的第i個元素（1=i=n1）之前插入一個元素時，需向后移動（n+1-i）個元素。 5在長度為n的線性表中刪除第i個元素（1in）時，需向前移動（n-i）個元素。 6在

12、雙向鏈表中，每個結點有兩個指針域，一個指向（直接前驅），另一個指向（直接后繼）。7在一個單鏈表中p所指結點之后插入一個s所指結點時，應執(zhí)行snext=（ pnext ）和pnext=（ s ）的操作。8對于一個具有n個結點的單鏈表，在已知P所指結點后插入一個新結點的時間復雜度是（O(1) ）；在給定值為X的結點后插入一個新結點的時間復雜度是（ O(n) ）。 9順序表相對于鏈表的優(yōu)點有(可以隨機存取，存儲密度高)。 10鏈表相對于順序表的優(yōu)點有(不需要連續(xù)的存儲空間，插入和刪除時不需要移動元素 )。11在n個結點的順序表中插入和刪除一個結點需平均移動大約( n/2 )個結點。12線性表的鏈式存

13、儲有三種，分別是(單鏈表 )(雙向鏈表)( 循環(huán)鏈表)。用數(shù)組描述的線性鏈表稱為(靜態(tài)鏈表). 13在順序表中訪問任意一結點的時間復雜度均為(O(1)，因此，順序表也稱為 ( 隨機存取 )的數(shù)據(jù)結構。 14在n個結點的單鏈表中要刪除已知結點*p，需找到( 該結點的前驅 )，其時間復雜度為( O(n) )。 15在循環(huán)鏈表中，可根據(jù)任一結點的地址遍歷整個鏈表，而單鏈表中需知道( 頭指針 )才能遍歷整個鏈表。所以，整個單鏈表是由（ 頭指針）來作為唯一標識的。三、閱讀理解題NODE *demol(NODE *head, NODE *p) NODE *q=head->link; while(q

14、&& q->next!=p) q=q->link; if(q) return q; else printf(“*p not in linklist.n”); 第3章 棧和隊列一、單項選擇題：1一個棧的入棧序列是a，b，c，d，e，則棧的不可能的輸出序列是（ ）。 A. edcba B. decba Cdceab Dabcde。 2.棧結構通常采用的兩種存儲結構是（ ）。 A. 順序存儲結構和鏈表存儲結構 B散列方式和索引方式 C鏈表存儲結構和數(shù)組 D線性存儲結構和非線性存儲結構 3棧的特點是（ B ），隊列的特點是（ A ）。 A. 先進先出 B先進后出4一個隊列的

15、入列序列是1，2，3，4，則隊列的輸出序列是( )。 A. 4，3，2，l B. 1，2，3，4 Cl，4，3，2 D3，2，4，l 5判定一個循環(huán)隊列 QU（最大空間是 mo）為空的條件是( )。 A. QU.front= =QU.rear B. QU.front！=QU.rear C QU.front=（QU.rearl）%mo DQU.front！=（QU.rear1）mo 6判定一個循環(huán)隊列QU（最大空間是mo）為滿隊列的條件是( )。 AQU.frontQU.rear BQU.front！=QU.rear C. QU.front=（QU.rearl）%mo DQU.front！=（Q

16、U.rearl）%mo 7循環(huán)隊列用數(shù)組 A0，ml存放其元素值，已知其頭尾指針分別是 front和 rear，則當前隊列中的元素個數(shù)是( )。 A.（rear-frontm）% m B. rear-front + 1 Crearfront1 D rearfront 8棧和隊列的共同點是( )。 A都是先進后出 B都是先進先出 C只允許在端點處插入和刪除元素 D沒有共同點 9向一個棧頂指針為 top的鏈棧中插入一個S所指結點時，則執(zhí)行( )。 A .topnext=s； Bs-nexttop-next； topnexts； C s-nexttop；tops； D s-nexttop；topto

17、pnext; 10從一個棧頂指針為top的鏈棧中刪除一結點時，用X保存被刪結點的值，則執(zhí)行( ). A. x=top；top=topnext； B xtopdata； C toptop-next；xtop-data； D xtop-data；toptop-next 11在鏈隊列中，設front和rear分別為隊首和隊尾指針，插入s所指結點的運算為（ ）。 A . frontnext=s； front=s； B rear-nexts；rears； C s-nextrear；rears； D snext=front；front=s； 12在鏈隊中，設front和rear分別為隊首和隊尾指針，則刪除

18、一個結點的運算為（ ）。 A rearfront-next； B rearrear-next； C frontfrontnext； D frontrear-next 13插入和刪除只能在一端進行的線性表，稱為（）。 A隊列 B循環(huán)隊列 C棧 D循環(huán)棧 14.在棧中，出棧操作的時間復雜度為（）。 A. O（1） BO（log2n） CO（n） DO（n2）15設長度為n的單循環(huán)鏈隊列，若只設頭指針，則入隊操作的時間復雜度為（）。 A. O(1) BO（log2n） CO（n） DO（n2） 21.設長度為n的單循環(huán)鏈隊列，若只設尾指針，則出隊操作的時間復雜度為（）。 A. O（1） BO（log

19、2n） CO（n） DO（n2）二、填空題： 1 線性表、棧和隊列都是( 線性)結構，可以在線性表的（任何）位置插入和刪除元素；對于棧只能在（ 棧頂 ）插入和刪除元素；對于隊列只能在（ 隊尾）插入元素和（ 對頭 ）刪除元素。 2向順序棧中壓入元素的操作是（判斷棧是否已滿，如果未滿，將元素存入棧頂指針指向的存儲位置，棧頂指針增一 ；否則先增加棧的空間，然后壓棧。 ）。向鏈棧中壓入元素的操作是（壓入元素的指針指向鏈棧的頭指針，再修改鏈棧的頭指針指向剛壓入的元素 ）。3對順序棧進行出棧時的操作是（如果?？?，出棧失敗；否則，棧頂指針減一，并將棧頂指針指向的元素取出）。對鏈棧進行出棧時的操作是（如果棧空

20、，出棧失?。环駝t，取出棧頂指針指向的元素，并將棧頂指針指向下一個元素）。 4在一個循環(huán)隊列中，隊首指針指向隊首元素的（ 存儲位置 ）。5從循環(huán)隊列中刪除一個元素時，其操作是（ 如果隊列空，刪除失?。环駝t，取出隊首指針指向的元素，然后修改隊首指針指向下一個元素的存儲位置）。 6在具有n個單元的循環(huán)隊列中，隊滿時共有（ n-1 ）個元素。 7一個棧的輸入序列是12345，則棧的輸出序列43512是（ 錯誤的 ）。 8一個棧的輸入序列是12345，則棧的輸出序列12345是（正確的）。9在有n個元素的棧中，進棧和出棧操作的時間復雜度為（ O（1） ）和（O（1） ）。 10設長度為n的鏈隊列用單循環(huán)

21、鏈表表示，若只設頭指針，則入隊和出隊操作的時間復雜度分別為（O（n） ）和（ O（1） ）；若只設尾指針，則人隊和出隊操作的時間復雜度分別為（ O（1）和（ O（1） ）。 11在循環(huán)隊列中，設隊頭指針front指向隊頭元素的前一個位置，隊尾指針rear指向隊尾元素。(1) 在循環(huán)隊列中，隊空標志為( Q.rear=Q.front )；隊滿標志為( (Q.rear+1)%maxsize=Q.front )。(2)當rear=front時，隊列長度為( Q.rear-Q.front 或 (Q.rear-Q.front+ m ) % m ) ；當 rear front時，隊列長度是( (Q.rea

22、r-Q.front+ m ) % m )( 設循環(huán)隊列長度為m)。12在順序隊列中，為了避免（假溢出）現(xiàn)象引入了循環(huán)隊列的概念。其入隊和出隊操作為( Q.baseQ.rear=e;Q.rear=(Q.rear+1）%maxsize ）和 （ e=Q.baseQ.front;Q.front=(Q.front+1）%maxsize ）。第4章 串一、選擇題1. 空串與空格串是相同的，這種說法 A. 正確 B.不正確2. 串是一種特殊的線性表，其特殊性體現(xiàn)在 A. 可以順序存儲 B.數(shù)據(jù)元素是一個字符 C. 可以鏈接存儲 D.數(shù)據(jù)元素可以是多個字符3. 設有兩個串p和q， 求q在p中首次出現(xiàn)的位置的

23、運算稱作 A 連接 B 模式匹配 C求子串 D 求串長4. 設串s1=ABCDEFG,s2='PQRST',函數(shù)con(x,y)返回x和y串的連接串，subs（s,i,j）返回串s的從序號i的字符開始的j個字符組成的字串， len(s)返回串s的長度，則con(subs(s1,2,len(s2), subs(s1,len(s2),2)的結果串是A）BCDEF B）BCDEFG C）BCPQRST D）BCDEFEF二、填空題1. 串的兩種最基本的存儲方式是 順序存儲 和 鏈式存儲 2. 兩個串相等的充分必要條件是 串的長度相等且各個位置的字符相同 3. 空串是 零個字符的串 ，

24、其長度等于 0 。4. 空格串是 一個或多個空格組成的串 ， 其長度等于 空格字符的個數(shù) 。5. 設s='I_AM_A_TEACHER', 其長度是 14 三、操作題：1. 已知兩個串為 s1="bc cad cabcadf"，s2="abc"，試求兩個串的長度，并判斷s2串是否是s1串的子串；如果s2是s1的子串，請指出s2在s1中的起始位置。94. 針對串的兩種存儲表示各設計一算法，判斷該字符串是否是回文（即正讀與反讀相同，如"abcba"是一個回文，而"abc"則不是）（僅寫出算法思想）。第5

25、章 數(shù)組與廣義表1. 設二維數(shù)組A5×6的每個元素占4個字節(jié)，已知Loc(a00)=1000，A共占多少字節(jié)？120 A的終端結點a45的起始地址為何？1116 按行和按列優(yōu)先存儲時，a25的起始地址分別為何？行優(yōu)先：1068 列優(yōu)先：11082稀疏矩陣的存儲方法及其分類。三元組及其行列數(shù)分類：三元組順序表，行邏輯鏈接的順序表，十字鏈表3廣義表的概念和存儲結構：如何區(qū)分表結點和原子結點4求下列廣義表運算的結果：1) GetHead(p,h,w) ：p2) GetTail(b,k,p,h) ：（k, p, h）3) GetHead(a,b),(c,d) ：（a, b）4) GetTai

26、l(a,b),(c,d) ：(c,d)5) GetHead(GetTail(a,b),(c,d) ：（c,d）6) GetTail(GetHead(a,b),(c,d) ： （b）第6章 樹和二叉樹 一、單項選擇題： 1對于任何一棵二叉樹T，如果其終端結點數(shù)為no，度為2的結點數(shù)為n2，則（）。 Ano=n2+1 B n2=n0+1 Cn0=2n2+1 Dn2=2n0+1 2設X是一棵樹，x是對應于X的二叉樹，則X的先序遍歷和X的（）遍歷相同。 A先序 B中序 C后序 D不確定 3深度為K的二叉樹至多有（）個結點。 A. 2k B. 2k 1 C. 2k-1 D. 2k-1 -14對于二叉樹來

27、說，第i層上至多有（）個結點。 A. 2i B. 2i 1 C. 2i-1 D. 2i-1 -1 5結點先序為XYZ的不同二叉樹，那么它有（）不同形態(tài)。 A3 B4 C5 D6 6某二叉樹的前序遍歷序列為IJKLMNO，中序遍歷序列為JLKNMOI，則后序遍歷序列為（）。 AJLKMNOI BLKNOMI CLKJNOMI DLNOMKJI 7.某二叉樹的后序遍歷序列為dabec，中序遍歷序列為debac，則前序序列遍歷為（ ）。 Aached Bdecab C. deabc Dcedba 8具有35個結點的完全二叉樹的深度為（）。 A5 B. 6 C7 D8 9將一棵有100個結點的完全二叉

28、樹從上到下，從左到右依次對結點進行編號，根結點的編號為1，則編號為49的結點的左孩子編號為（）。 A98 B99 C50 D48 10某二叉樹的前序和后序序列正好相反，則該二又樹一定是（）的二叉樹。A空或只有一個結點 B、高度等于其結點數(shù) C任一結點無左孩子 D任一結點無右孩子 11設X是一棵樹，x是對應于X的二叉樹，則X的后序遍歷和X的（）遍歷相同。 A先序 B中序 C后序 D層次序 12樹最適合用來表示（）。 A有序數(shù)據(jù)元素 B.無序數(shù)據(jù)元素 C.元素之間無聯(lián)系的數(shù)據(jù) D.元素之間有分支層次關系 13對于一棵滿二叉樹，m個樹葉，n個結點，深度為h，則（）。 A nhm B hm=2n Cm

29、h-1 Dn2h-l 14.判斷線索二叉樹中某結點p有左孩子的條件是（）。 A p！null Bp-lchild!=null Cp->ltag=0 Dp-ltag=1 15二叉樹按某種順序線索化后，任一結點均有指向其前驅和后繼的線索，這種說法（ ）。 A.正確 B錯誤16深度為5的二叉樹至多有( )個結點。 A.16 B32 C31 D10 17在一非空二叉樹的中序遍歷序列中，根結點的右邊( )。 A.只有右子樹上的所有結點 B只有右子樹上的部分結點 C只有左子樹上的部分結點 D只有左子樹上的所有結點 18設n，m為一棵二叉樹上的兩個結點，在中序遍歷時，n在m前的條件是( )。 A. n

30、在m右方 Bn是m祖先 Cn在m左方 Dn是m子孫 二、填空題:1 對于二叉樹來說，第i層上至多有( 2i-1 )個結點。2 深度為k的二叉樹至多有( 2K-1 )個結點。3 樹中結點的最大層次稱為樹的( 深度 )。 4由一棵二叉樹的前序序列和(中序序列)可唯一確定這棵二叉樹。 5高度為5的完全二叉樹至少有（ 16 ）個結點。 6將一棵樹轉換成一棵二叉樹后，二叉樹根結點沒有（ 右 ）子樹。 7一棵含有n個結點的完全二叉樹，它的高度是（ floor(log2n)+1 ）。 8含有n個結點的二叉樹用二叉鏈表表示時，有（n+1）個空鏈域。 9哈夫曼樹是帶權路徑長度（最小）的二叉樹。 10具有m個葉結

31、點的哈夫曼樹共有（2m-1）個結點。 11已知完全二叉樹的第8層有8個結點，則其葉子結點數(shù)是（ 68 ）。 12已知完全二叉樹的第7層有10個葉子結點，則整個二叉樹的結點數(shù)最多是（ 73 ）。 13.一棵二叉樹的第i（i>=l）層最多有(2i-1 )個結點；一棵有n（n0）個結點的滿二叉樹共有( (n+1)/2 )個葉子和(n-1)/2 )個非終端結點。 14現(xiàn)有按中序遍歷二叉樹的結果為abc，問有( 5 )種不同形態(tài)的二叉樹可以得到這一遍歷結果，這些二叉樹分別是( )。15.以數(shù)據(jù)集4，5，6，7，10，12，18為結點權值所構造的Huffman樹為（ ），其帶權路徑長度為（ ）。三、

32、簡答題： 1已知權值：4，2，5，7，5，請畫出相應的哈夫曼樹并計算其帶權路徑長度WPL。 2如果二叉樹的后序和中序分別為：A，C，D，B，G，I，H，F(xiàn)，E和A，B，C，D，E，F(xiàn)，G，H，I 請給出二叉樹的前序。3如何實現(xiàn)森林轉化為一棵二叉樹。 4一棵二叉樹的先序、中序和后序序列分別如下，其中一部分未給出，試求出空格處的內容，并畫出二叉樹。 先序：B FICEH G 中序：DKFIA EJC 后序： K FBHJ G A四，畫圖題假設一顆二叉樹的層次序列為ABCDEFGHIJ和中序序列為DBGEHJACIF。請畫出該樹第7章 圖一、單項選擇題：1用鄰接表表示圖進行廣度優(yōu)先遍歷時，通常采用（

33、）來實現(xiàn)算法的。 A棧 B隊列 C樹 D圖2用鄰接表表示圖進行深度優(yōu)先遍歷時，通常采用（）來實現(xiàn)算法的。 A棧 B隊列 C樹 D圖3已知圖的鄰接矩陣，則從頂點0出發(fā)按深度優(yōu)先遍歷的結點序列是（ ）。0 1 1 1 1 0 1 A. 0 2 4 3 1 5 61 0 0 1 0 0 1 B. 0 1 3 6 5 4 21 0 0 0 1 0 0 C. 0 4 2 3 1 6 5 1 1 0 0 1 1 0 D. 0 3 6 1 5 4 2 1 0 1 1 0 1 0 0 0 0 1 1 0 1 1 1 0 0 0 1 04已知圖的鄰接矩陣同上題8，則從頂點0出發(fā)按廣度優(yōu)先遍歷結點序列是（）。A0

34、243651 B0136425 C0423156 D0134256 5、深度優(yōu)先遍歷類似于二叉樹的（ ）。A. 先序遍歷 B. 中序遍歷 C. 后序遍歷 D. 層次遍歷6、廣度優(yōu)先遍歷類似于二叉樹的（ ）。A. 先序遍歷 B. 中序遍歷 C. 后序遍歷 D. 層次遍歷7、任何一個無向連通圖的最小生成樹（ ）。A. 只有一棵 B. 一棵或多棵 C. 一定有多棵 D. 可能不存在8、對于一個具有n個頂點的有向圖，采用鄰接矩陣表示該矩陣的大小是（ ）。A. n B. (n-1)2 C. n-1 D. n210、對于一個具有n個頂點和e條邊的無向圖，采用鄰接表表示，則表頭向量的大小為（）；所有弧結點的

35、總數(shù)是（ ）。A. n B. n+1 C.n-1 D.n+eA. e/2 B. e C. 2e D. n+e二、填空題：1、圖有（鄰接矩陣）、（ 鄰接表）（十字鏈表）（鄰接多重表）等存儲結構，遍歷圖有（深度優(yōu)先搜索）、（廣度優(yōu)先搜索）等方法。2、有向圖用鄰接矩陣存儲，第i行元素之和等于頂點i的（ 度 ）。3、設有一稀疏圖，則G采用（鄰接表）存儲較省空間。4、設有一稠密圖，則G采用（鄰接矩陣）存儲較省空間。5、已知一個圖用鄰接矩陣表示，刪除所有從第i個頂點出發(fā)的邊的方法是（鄰接矩陣的第i行置0；如果是無向圖，第i列也同時置0）。6、若求一個稀疏圖G的最小生成樹，最好用（Kruskal）算法來求解

36、。7、若求一個稠密圖G的最小生成樹，最好用（ Prim ）算法來求解。8、拓撲排序輸出的頂點數(shù)小于有向圖的頂點數(shù)，則該圖一定存在（環(huán)）。三簡答題1. 已知圖G如下所示，畫出G的鄰接矩陣和鄰接表、逆鄰接表。AB C D E2. 假定無向圖G有6個結點和9條邊，并依次輸入這9條邊為（0，1），（0，2），（0，4），（0，5），（1，2），（2，3），（2，4），（3，4），（4，5）。試從頂點0出發(fā)，分別寫出按深度優(yōu)先搜索和廣度優(yōu)先搜索進行遍歷的結點序列。3. 圖G=（V，E），V=0，1，2，3，4，5，E=0，1，0，2，1，4，2，5，5，4，4，3，5，3。寫出圖G中頂點的所有拓撲排序。

37、4. 從某源點到其余頂點的最短路徑的計算方法。5. 設無向圖G的鄰接矩陣如下所示，畫出用Prim算法和Kruskal 算法所得的最小生成樹。 1 2 2 21 3 2 3 1 2 1 3 2 3 第9章 查 找一、單項選擇題： 1順序查找法適合于存儲結構為（ ）的線性表。 A.散列存儲 B順序存儲或鏈接存儲 C壓縮存儲 D索引存儲 2對線性表進行折半查找時，要求線性表必須( )。 A以順序方式存儲 B以鏈接方式存儲C以順序方式存儲，且結點按關鍵字有序排序 D以鏈接方式存儲，且結點接關鍵字有序排序 3采用順序查找方法查找長度為n的線性表時，每個元素的平均查找長度為( )。 A . n B n2

38、C（n l）2 D（n 1）2 4采用折半查找方法查找長度為n的線性表時，每個元素的平均查找長度為( )。 A.O(n2) BO(nlog2n) CO(n ) DO(log2n) 6有一個有序表為1，3，9，12，32，41，45，62，75，77，82，95，100，當折半查找值為82的結點時，（ ）次比較后查找成功。 A. 1 B2 C4 D8 7.設哈希表長m=14，哈希函數(shù)H（key）二key11。表中已有4個結點： addr(15) 4 addr（38）5 addr（61）=6 addr（84）=7 其余地址為空, 如用二次探測再散列處理沖突，關鍵字為49的結點的地址是( )。 A.

39、 8 B. 3 C5 D9 8.有一個長度為12的有序表，按折半查找法對該表進行查找，在表內個元素等概率情況下查找成功所需的平均查找長度為（ ）。A. 35/12 B. 37/12 C39/12 D43/12 9采用分塊查找時，若線性表中共有625個元素，查找每個元素的概率相同，假設采用順序查找來確定結點所在的塊時，每塊應分( )個結點最佳。 A. 10 B25 C6 D62510.如果要求一個線性表既能較快地查找，又能適應動態(tài)變化的要求，可以采用( )查找方法。A. 分塊 B順序 C二分 D散列 11.設有100個元素，用折半查找法進行查找時，最大比較次數(shù)是（ ）。A. 25 B50 C10

40、 D7 （判定樹的深度foor(log2n)+1） 12設有100個元素，用折半查找法進行查找時，最小比較次數(shù)是（ ）。A. 7 B4 C2 D1 13哈希函數(shù)有一個共同性質，即函數(shù)值應當以（ ）取其值域的每個值。A. 同等概率 B最大概率 C最小概率 D平均概率14設哈希地址空間為0.m-1，k為關鍵字，取哈希函數(shù)為H(k)=k % p，為了減少發(fā)生沖突的頻率，一般取p為（ ）。A. 小于m的最大奇數(shù) B小于m的最大偶數(shù)C小于m的最大質數(shù) D小于m的最大合數(shù) 15某順序存儲的表格中有90000個元素，已按關鍵字值升序排列，假定對每個元素進行查找的概率是相同的，且每個元素的關鍵字值皆不同，用順

41、序查找法查找時，平均比較次數(shù)約為（ C ），最大比較次數(shù)約為（ D）。A. 25000 B30000 C45000 D90000二、填空題：1在各種查找方法中，平均查找長度與結點個數(shù)n無關的查法方法是（ 哈希表查找）。2折半查找的存儲結構僅限于（ 有序表 ），且是（ 順序存儲）。3在分塊查找方法中，首先查找（ 索引表 ），然后再查找相應的（ 塊 ）。4長度為255的表，采用分塊查找法，每塊的最佳長度是（ 15 ）。5假設在有序線性表Al20上進行折半查找，則比較一次查找成功的結點數(shù)為（1），則比較二次查找成功的結點數(shù)為（ 2 ），則比較三次查找成功的結點數(shù)為（ 4 ），則比較四次查找成功的結點

42、數(shù)為（ 8 ），則比較五次查找成功的結點數(shù)為（ 5 ），平均查找長度為（ 3.7 ）。6對于長度為n的線性表，若進行順序查找，則時間復雜度為（ O(n ) ）；若采用折半法查找，則時間復雜度為（ (log2n) ）；若采用分塊查找（假定總塊數(shù)和每塊長度均接近），則時間復雜度為（ O(n1/2 ) ）。7在散列存儲中，裝填因子的值越大，則(發(fā)生沖突的可能越大，查找時關鍵字進行比較的次數(shù)越多)；的值越小，則(發(fā)生沖突的可能越小，查找時關鍵字進行比較的次數(shù)越少)。8.哈希查找的基本思想是按（關鍵字）決定數(shù)據(jù)的存儲地址。9哈希表的查找效率主要取決于選取的（哈希函數(shù)），（處理沖突的方法）和（ 哈希表的裝

43、填因子 ）。10.折半查找不成功時，出現(xiàn)（low>high）情況，程序終止。三、簡答題：1 設哈希表的長度為13，哈希函數(shù)為H(k)=k %13，給定的關鍵字序列為：19，14，23，01，68，20，84，27，55，11，10，79，畫出用線性探測法和鏈地址法解決沖突時所構成的散列表，并求等概率情況下這兩種方法查找成功時的平均查找長度。2 假定有n個關鍵字，它們具有相同的哈希函數(shù)值，用線性探測法把這n個關鍵字存入到散列地址中要做多少次探測？（n+1）*n/23 設有序表為a,b,c,d,e,f,g,h,i，請畫出分別對給定值e和k進行折半查找的過程。4 畫出對長度為10的有序表進行折

44、半查找的判定樹，并求其等概論時查找成功的ASL.第10章 內 部 排 序一、單項選擇題：1、在所有的排序方法中，（ ）不是穩(wěn)定的排序方法。A. 希爾排序 B. 冒泡排序 C. 直接插入排序 D. 歸并排序2、設有1000個無序的元素，希望用最快的速度挑選出其中前10個最大的元素，最好選用（ ）方法。A. 冒泡排序 B. 快速排序 C. 堆排序 D. 基數(shù)排序3、在待排序的元素序列基本有序的前提下，效率最高的排序方法是（ ）。A. 插入排序 B. 選擇排序 C. 快速排序 D. 歸并排序4、一組記錄的排序碼為（46, 79, 56, 38, 40, 84），則利用堆排序的方法建立的初始堆為（ ）

45、。A. 79，46，56，38，40，80 B. 84，79，56，38，40，46C. 84，79，56，46，40，38 D. 84，56，79，40，46，385、一組記錄的排序碼為（46, 79, 56, 38, 40, 84），則利用快速排序的方法，以第一個記錄為基準得到的一次劃分結果為（ ）。A. 38，40，46，56，79，84 B. 40，38，46，79，56，84C. 40，38，46，56，79，84 D. 40，38，46，84，56，796、一組記錄的排序碼為（25，48，16，35，79，82，23，40，36，72），其中含有5個長度為2的有序表，按歸并排序的方

46、法對該序列進行一趟歸并后的結果為（ ）。A. 16,25,35,48,23,40,79,82,36,72 B. 16,25,35,48,79,82,23,36,40,72C. 16,25,48,35,79,82,23,36,40,72 D. 16,25,35,48,79,23,36,40,72,827、排序方法中，從未排序序列中依次取出元素與已排序序列（初始時為空）中的元素進行比較，將其放入已排序序列的正確位置上的方法，稱為（ ）。A. 希爾排序 B. 冒泡排序 C. 插入排序 D. 選擇排序8、排序方法中，從未排序序列中挑選元素，并將其依次放入已排序序列（初始時為空）的一端的方法，稱為（ ）

47、。A. 希爾排序 B. 歸并排序 C. 插入排序 D. 選擇排序9、用某種排序方法對線性表（25,84,21,47,15,27,68,35,20）進行排序時，元素序列的變化情況如下： 25,84,21,47,15,27,68,35,20 20,15,21,25,47,27,68,35,84 15,20,21,25,35,27,47,68,84 15,20,21,25,27,35,47,68,84，則所采用的排序方法是（ ）。A. 選擇排序 B. 希爾排序 C. 歸并排序 D. 快速排序10、下述幾種排序方法中，不是基于比較的排序方法是（ ）。A. 插入排序 B. 選擇排序 C. 快速排序 D. 基數(shù)排序11、下述幾種排序方法中，要求內存量最大的是（ ）。A. 插入排序 B. 選擇排序 C. 快速排序 D. 歸并排序12、快速排序方法在（ ）情況下最不利于發(fā)揮其長處。A. 要排序的數(shù)據(jù)量太大 B. 要排序的數(shù)據(jù)中含有多個相同值C. 要排序的數(shù)據(jù)已基本有序 D.