數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)習(xí)題和答案

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

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

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

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

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

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

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

8、件是( )。A. head=NULL Bheadnext=NULL Cheadnext=head Dhead！=NULL 5非空的循環(huán)單鏈表head的尾結(jié)點(diǎn)（由p所指向）滿足( )。 A. pnext=NULL Bp=NULL Cp->next=head D p=head 6在一個(gè)單鏈表中，已知q所指結(jié)點(diǎn)是p所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，若在q和p之間插入s結(jié)點(diǎn)，則執(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所指結(jié)點(diǎn)不是最后結(jié)點(diǎn)，在p之后

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

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

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

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

13、儲(chǔ)有三種，分別是(單鏈表 )(雙向鏈表)( 循環(huán)鏈表)。用數(shù)組描述的線性鏈表稱為(靜態(tài)鏈表). 13在順序表中訪問任意一結(jié)點(diǎn)的時(shí)間復(fù)雜度均為(O(1)，因此，順序表也稱為 ( 隨機(jī)存取 )的數(shù)據(jù)結(jié)構(gòu)。 14在n個(gè)結(jié)點(diǎn)的單鏈表中要?jiǎng)h除已知結(jié)點(diǎn)*p，需找到( 該結(jié)點(diǎn)的前驅(qū) )，其時(shí)間復(fù)雜度為( O(n) )。 15在循環(huán)鏈表中，可根據(jù)任一結(jié)點(diǎn)的地址遍歷整個(gè)鏈表，而單鏈表中需知道( 頭指針 )才能遍歷整個(gè)鏈表。所以，整個(gè)單鏈表是由（ 頭指針）來作為唯一標(biāo)識(shí)的。三、閱讀理解題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章 棧和隊(duì)列一、單項(xiàng)選擇題：1一個(gè)棧的入棧序列是a，b，c，d，e，則棧的不可能的輸出序列是（ ）。 A. edcba B. decba Cdceab Dabcde。 2.棧結(jié)構(gòu)通常采用的兩種存儲(chǔ)結(jié)構(gòu)是（ ）。 A. 順序存儲(chǔ)結(jié)構(gòu)和鏈表存儲(chǔ)結(jié)構(gòu) B散列方式和索引方式 C鏈表存儲(chǔ)結(jié)構(gòu)和數(shù)組 D線性存儲(chǔ)結(jié)構(gòu)和非線性存儲(chǔ)結(jié)構(gòu) 3棧的特點(diǎn)是（ B ），隊(duì)列的特點(diǎn)是（ A ）。 A. 先進(jìn)先出 B先進(jìn)后出4一個(gè)隊(duì)列的

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

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

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

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

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

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

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

22、r-Q.front+ m ) % m )( 設(shè)循環(huán)隊(duì)列長(zhǎng)度為m)。12在順序隊(duì)列中，為了避免（假溢出）現(xiàn)象引入了循環(huán)隊(duì)列的概念。其入隊(duì)和出隊(duì)操作為( 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. 可以順序存儲(chǔ) B.數(shù)據(jù)元素是一個(gè)字符 C. 可以鏈接存儲(chǔ) D.數(shù)據(jù)元素可以是多個(gè)字符3. 設(shè)有兩個(gè)串p和q， 求q在p中首次出現(xiàn)的位置的

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

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

25、章 數(shù)組與廣義表1. 設(shè)二維數(shù)組A5×6的每個(gè)元素占4個(gè)字節(jié)，已知Loc(a00)=1000，A共占多少字節(jié)？120 A的終端結(jié)點(diǎn)a45的起始地址為何？1116 按行和按列優(yōu)先存儲(chǔ)時(shí)，a25的起始地址分別為何？行優(yōu)先：1068 列優(yōu)先：11082稀疏矩陣的存儲(chǔ)方法及其分類。三元組及其行列數(shù)分類：三元組順序表，行邏輯鏈接的順序表，十字鏈表3廣義表的概念和存儲(chǔ)結(jié)構(gòu)：如何區(qū)分表結(jié)點(diǎn)和原子結(jié)點(diǎn)4求下列廣義表運(yùn)算的結(jié)果：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章 樹和二叉樹 一、單項(xiàng)選擇題： 1對(duì)于任何一棵二叉樹T，如果其終端結(jié)點(diǎn)數(shù)為no，度為2的結(jié)點(diǎn)數(shù)為n2，則（）。 Ano=n2+1 B n2=n0+1 Cn0=2n2+1 Dn2=2n0+1 2設(shè)X是一棵樹，x是對(duì)應(yīng)于X的二叉樹，則X的先序遍歷和X的（）遍歷相同。 A先序 B中序 C后序 D不確定 3深度為K的二叉樹至多有（）個(gè)結(jié)點(diǎn)。 A. 2k B. 2k 1 C. 2k-1 D. 2k-1 -14對(duì)于二叉樹來

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

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

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

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

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

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

33、）來實(shí)現(xiàn)算法的。 A棧 B隊(duì)列 C樹 D圖2用鄰接表表示圖進(jìn)行深度優(yōu)先遍歷時(shí)，通常采用（）來實(shí)現(xiàn)算法的。 A棧 B隊(duì)列 C樹 D圖3已知圖的鄰接矩陣，則從頂點(diǎn)0出發(fā)按深度優(yōu)先遍歷的結(jié)點(diǎn)序列是（ ）。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，則從頂點(diǎn)0出發(fā)按廣度優(yōu)先遍歷結(jié)點(diǎn)序列是（）。A0

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

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

36、。7、若求一個(gè)稠密圖G的最小生成樹，最好用（ Prim ）算法來求解。8、拓?fù)渑判蜉敵龅捻旤c(diǎn)數(shù)小于有向圖的頂點(diǎn)數(shù)，則該圖一定存在（環(huán)）。三簡(jiǎn)答題1. 已知圖G如下所示，畫出G的鄰接矩陣和鄰接表、逆鄰接表。AB C D E2. 假定無向圖G有6個(gè)結(jié)點(diǎn)和9條邊，并依次輸入這9條邊為（0，1），（0，2），（0，4），（0，5），（1，2），（2，3），（2，4），（3，4），（4，5）。試從頂點(diǎn)0出發(fā)，分別寫出按深度優(yōu)先搜索和廣度優(yōu)先搜索進(jìn)行遍歷的結(jié)點(diǎn)序列。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中頂點(diǎn)的所有拓?fù)渑判颉?/p>

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

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

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

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

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

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

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

44、半查找的判定樹，并求其等概論時(shí)查找成功的ASL.第10章 內(nèi) 部 排 序一、單項(xiàng)選擇題：1、在所有的排序方法中，（ ）不是穩(wěn)定的排序方法。A. 希爾排序 B. 冒泡排序 C. 直接插入排序 D. 歸并排序2、設(shè)有1000個(gè)無序的元素，希望用最快的速度挑選出其中前10個(gè)最大的元素，最好選用（ ）方法。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），則利用快速排序的方法，以第一個(gè)記錄為基準(zhǔn)得到的一次劃分結(jié)果為（ ）。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個(gè)長(zhǎng)度為2的有序表，按歸并排序的方

46、法對(duì)該序列進(jìn)行一趟歸并后的結(jié)果為（ ）。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、排序方法中，從未排序序列中依次取出元素與已排序序列（初始時(shí)為空）中的元素進(jìn)行比較，將其放入已排序序列的正確位置上的方法，稱為（ ）。A. 希爾排序 B. 冒泡排序 C. 插入排序 D. 選擇排序8、排序方法中，從未排序序列中挑選元素，并將其依次放入已排序序列（初始時(shí)為空）的一端的方法，稱為（ ）

47、。A. 希爾排序 B. 歸并排序 C. 插入排序 D. 選擇排序9、用某種排序方法對(duì)線性表（25,84,21,47,15,27,68,35,20）進(jìn)行排序時(shí)，元素序列的變化情況如下： 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、下述幾種排序方法中，要求內(nèi)存量最大的是（ ）。A. 插入排序 B. 選擇排序 C. 快速排序 D. 歸并排序12、快速排序方法在（ ）情況下最不利于發(fā)揮其長(zhǎng)處。A. 要排序的數(shù)據(jù)量太大 B. 要排序的數(shù)據(jù)中含有多個(gè)相同值C. 要排序的數(shù)據(jù)已基本有序 D.