數(shù)據(jù)結構復習題及答案(12級)

1、一、選擇題。(每小題2分，共40分)(1) 計算機識別.存儲和加工處理的對象被統(tǒng)稱為_A_。A.數(shù)據(jù) B.數(shù)據(jù)元素 C.數(shù)據(jù)結構 D.數(shù)據(jù)類型(2) 數(shù)據(jù)結構通常是研究數(shù)據(jù)的_ A _及它們之間的聯(lián)系。A.存儲和邏輯結構 B.存儲和抽象 C.理想和抽象 D.理想與邏輯(3) 不是數(shù)據(jù)的邏輯結構是_ A _。A.散列結構 B.線性結構 C.樹結構 D.圖結構 (4) 數(shù)據(jù)結構被形式地定義為<D,R>,其中D是_ B _的有限集，R是_ C _的有限集。A.算法 B.數(shù)據(jù)元素 C.數(shù)據(jù)操作 D.邏輯結構(5) 組成數(shù)據(jù)的基本單位是_ A _。 A.數(shù)據(jù)項 B.數(shù)據(jù)類型C.數(shù)據(jù)元素 D.

2、數(shù)據(jù)變量(6) 設數(shù)據(jù)結構A=(D，R)，其中D=1，2，3，4，R=r，r=<1，2>，<2，3>，<3，4>，<4，1>，則數(shù)據(jù)結構A是_ A _。A.線性結構 B.樹型結構 C.圖型結構 D.集合(7) 數(shù)據(jù)在計算機存儲器內表示時，物理地址與邏輯地址相同并且是連續(xù)的，稱之為_ C _。A.存儲結構 B.邏輯結構 C.順序存儲結構 D.鏈式存儲結構(8) 在數(shù)據(jù)結構的討論中把數(shù)據(jù)結構從邏輯上分為_ A _。A.內部結構與外部結構 B.靜態(tài)結構與動態(tài)結構C.線性結構與非線性結構 D.緊湊結構與非緊湊結構(9) 對一個算法的評價，不包括如下_ B

3、 _方面的內容。A.健壯性和可讀性 B.并行性 C.正確性 D.時空復雜度(10) 算法分析的兩個方面是_ A _。A.空間復雜性和時間復雜性 B.正確性和簡明性C.可讀性和文檔性 D.數(shù)據(jù)復雜性和程序復雜性(11) 線性表是具有n個_ C _的有限序列（n0)。A.表元素 B.字符 C.數(shù)據(jù)元素 D.數(shù)據(jù)項(12) 線性表的存儲結構是一種_ B _的存儲結構。A.隨機存取 B.順序存取 C.索引存取 D.HASH存取(13) 在一個長度為n 的順序表中，向第i個元素（1 i n）之前插入一個新元素時，需要向后移動_ B _個元素。A.n-i B.n-i+1 C.n-i-1 D.i(14) 鏈

4、表是一種采用_ B _存儲結構存儲的線性表；A.順序 B.鏈式 C.星式 D.網(wǎng)狀(15) 下面關于線性表的敘述錯誤的是_ D _。A.線性表采用順序存儲必須占用一片連續(xù)的存儲空間B.線性表采用鏈式存儲不必占用一片連續(xù)的存儲空間C.線性表采用鏈式存儲便于插入和刪除操作的實現(xiàn)D.線性表采用順序存儲便于插入和刪除操作的實現(xiàn)(16) 設指針q指向單鏈表中結點A，指針p指向單鏈表中結點A的后繼結點B，指針s指向被插入的結點X，則在結點A和結點B之間插入結點X的操作序列為_ B _。A. s->next=p->next；p->next=-s；B. q->next=s； s->

5、;next=p；C. p->next=s->next；s->next=p；D. p->next=s；s->next=q；(17) 設指針變量p指向單鏈表結點A，則刪除結點A的后繼結點B需要的操作為_ A _。A. p->next=p->next->next B. p=p->nextC. p=p->next->next D. p->next=p(18) 下列說法哪個正確？_ D _ A. 堆棧是在兩端操作、先進后出的線性表B. 堆棧是在一端操作、先進先出的線性表C. 隊列是在一端操作、先進先出的線性表D. 隊列是在

6、兩端操作、先進先出的線性表(19) 棧和隊列的共同點是 _ C _。A. 都是先進后出 B. 都是先進先出C. 只允許在端點處插入和刪除元素 D. 沒有共同點(20) 棧與一般線性表的區(qū)別主要在_D_。A、元素個數(shù) B、元素類型 C、邏輯結構 D、插入、刪除元素的位置(21) 鏈棧與順序棧相比，比較明顯的優(yōu)點是_D_。A、插入操作更加方便 B、刪除操作更加方便C、不會出現(xiàn)下溢的情況 D、不會出現(xiàn)上溢的情況(22) 以下數(shù)據(jù)結構中哪一個是非線性結構_ D _。A.隊列     B.棧    

7、60; C.線性表      D.二叉樹 (23) 若已知一個棧的入棧序列是1，2，3，n，其輸出序列為p1，p2，p3，pn，若p1=n，則pi為 _ C _。A. i    B. B. n=i      C. n-i+1     D.不確定(24) 當利用大小為N的一維數(shù)組順序存儲一個棧時，假定用top=N表示?？?，則向這個棧插入一個元素時，首先應執(zhí)行 

8、 _ B _語句修改top指針。A. top+     B. top-     C. top=0     D. top(25) 4個元素進S棧的順序是A,B,C,D，經(jīng)運算POP(S)后，棧頂元素是_ C _。A. A    B. B     C. C     D. D(26) 一個棧的輸入序列是a,b,c,d,e,則

9、棧的不可能的輸出序列是_ C _。A. edcba    B. decba     C. dceab     D. abcde(27) 設輸入序列是1、2、3、n，經(jīng)過棧的作用后輸出序列的第一個元素是n，則輸出序列中第i個輸出元素是_ C _。A. n-i    B. n-1-i     C. n+1-i     D.

10、不能確定(28) 字符A、B、C、D依次進入一個棧，按出棧的先后順序組成不同的字符串，至多可以組成_ B _個不同的字符串？A. 15    B. 14     C. 16     D. 21(29) 設指針變量top指向當前鏈式棧的棧頂，則刪除棧頂元素的操作序列為_ D _。A. top=top+1;       B. top=top-1;   C. top->next

11、=top;    D. top=top->next; (30) 設棧S和隊列Q的初始狀態(tài)為空，元素E1、E2、E3、E4、E5和E6依次通過棧S，一個元素出棧后即進入隊列Q，若6個元素出列的順序為E2、E4、E3、E6、E5和E1，則棧S的容量至少應該是_ C _。A. 6    B. 4     C. 3     D. 2(31) 若用一個大小為6的數(shù)組來實現(xiàn)循環(huán)隊列，且當前rear和front的值分別為0和3。當從隊

12、列中刪除一個元素，再加入兩個元素后，rear和front的值分別為 _ B _。A. 1和5    B. 2和4     C. 4和2     D. 5和1(32) 設順序循環(huán)隊列Q0：M-1的頭指針和尾指針分別為F和R，頭指針F總是指向隊頭元素的前一位置，尾指針R總是指向隊尾元素的當前位置，則該循環(huán)隊列中的元素個數(shù)為_ C _。A. R-F    B. F-R    

13、; C. (R-F+M)%M     D. (F-R+M)%M  (33) 設指針變量front表示鏈式隊列的隊頭指針，指針變量rear表示鏈式隊列的隊尾指針，指針變量s指向將要入隊列的結點X，則入隊列的操作序列為 _ C _。A. front->next=s；front=s；    B. s->next=rear；rear=s；  C. rear->next=s；rear=s；    &

14、#160;D. s->next=front；front=s；(34) 如下陳述中正確的是_ A _。A. 串是一種特殊的線性表      B. 串的長度必須大于零  C. 串中元素只能是字母       D. 空串就是空白串(35) 下列關于串的敘述中，正確的是 _ D _。A. 串長度是指串中不同字符的個數(shù)       B. 串是n個字母的有限序列C. 如果兩

15、個串含有相同的字符，則它們相等    D. 只有當兩個串的長度相等，并且各個對應位置的字符都相符時才相等(36)  字符串的長度是指_ C _。A. 串中不同字符的個數(shù)      B. 串中不同字母的個數(shù)  C. 串中所含字符的個數(shù)      D. 串中不同數(shù)字的個數(shù) (37) 兩個字符串相等的充要條件是_ C _。A. 兩個字符串的長度相等     

16、60; B. 兩個字符串中對應位置上的字符相等C. 同時具備(A)和(B)兩個條件     D. 以上答案都不對(38) 串是一種特殊的線性表，其特殊性體現(xiàn)在_ B _。A. 可以順序存儲      B. 數(shù)據(jù)元素是一個字符C. 可以鏈接存儲      D. 數(shù)據(jù)元素可以是多個字符(39) 設有兩個串p和q，求q在p中首次出現(xiàn)的位置的運算稱作 _ B _。A. 連接    B.

17、 模式匹配     C. 求子串     D. 求串長(40) 設串sI="ABCDEFG",s2="PQRST",函數(shù)con(x,y)返回x和y串的連接串,subs(s,i,j)返回串s的從序號i的字符開始的j個字符組成的子串，len(s)返回串s的長度，則con(subs(s1,2,1en(s2)，subs(sl,len(s2)，2)的結果串是_ D _。A. BCDEF     B. BCDEFG&#

18、160;    C. BCPQRST     D. BCDEFEF (41) 函數(shù)substr(“DATASTRUCTURE”，5，9)的返回值為_ A _。A. “STRUCTURE”    B. “DATA”    C. “ASTRUCTUR”    D. “DATASTRUCTURE”(42) 設串S=”I AM A TEACHER!”，其長度是_ D _。A. 16   

19、0;B. 11     C. 14     D. 15  (43) 假定在一棵二叉樹中，雙分支結點數(shù)為15個，單分支結點數(shù)為32個，則葉子結點數(shù)為_B_。 A. 15 B. 16 C. 17 D. 47(44) 假定一棵二叉樹的結點數(shù)為18個，則它的最小高度_B_。A. 4 B. 5 C. 6 D. 18(45) 在一棵二叉樹中第五層上的結點數(shù)最多為_C_。A. 8 B. 15 C. 16 D. 32(46) 在一棵具有五層的滿二叉樹中，結點總數(shù)為_A_。A. 31 B. 3

20、2 C. 33 D. 16(47) 已知8個數(shù)據(jù)元素為(34、76、45、18、26、54、92、65)，按照依次插入結點的方法生成一棵二叉排序樹后，最后兩層上的結點總數(shù)為_B_。A. 1 B. 2 C. D. 4(48) 由分別帶權為9、2、5、7的四個葉子結點構造一棵哈夫曼樹，該樹的帶權路徑長度為_C_。 A. 23 B. 37 C. 44 D. 46(49) 在樹中除根結點外，其余結點分成m (m0)個_A _的集合T1,T2,T3.Tm,每個集合又都是樹，此時結點T稱為Ti的父結點，Ti稱為T的子結點(1im)。A. 互不相交 B. 可以相交 C. 葉結點可以相交 D. 樹枝結點可以相

21、交(50) 如果結點A有三個兄弟，而且B是A的雙親，則B的出度是_B_。A. 3 B. 4 C. 5 D. 1(51) 在一個有向圖中，所有頂點的入度之和等于所有頂點的出度之和的_B_倍。A. 1/2 B. 1 C. 2 D. 4(52) 具有n個頂點的無向完全圖，邊的總數(shù)為_ D_條。A. n-1 B. n C. n+1 D. n*(n-1)/2(53) 在無向圖G的鄰接矩陣A中，若Ai,j等于1，則Aj,i等于_C _。A. i+j B. i-j C. 1 D. 0(54) 圖的深度優(yōu)先或廣度優(yōu)先遍歷的空間復雜性均為_A_ 。(訪問標志位數(shù)組空間)A. O(n) B. O(e) C. O(

22、n-e) D. O(n+e)(55) 請指出在順序表2、5、7、10、14、15、18、23、35、41、52中，用折半法查找關鍵碼12需做_ C _次關鍵碼比較。A.2 B.3 C.4 D.5 (56) 對線性表進行折半查找時，必須要求線性表 _ C _。A. 以順序方式存儲 B. 以鏈接方式存儲C. 以順序方式存儲，且結點按關鍵字有序排列D. 以鏈接方式存儲，且結點按關鍵字有序排列(57) 設二叉排序樹中有n個結點，則在二叉排序樹的平均查找長度為_ B _。A. O(1) B. O(log2n) C. O(n) D. O(n2)(58) 依次插入序列(50，72，43，85，75，20，3

23、5，45，65，30)后建立的二叉搜索樹中，查找元素35要進行_ A _元素間的比較。A.4次B.5次C.7次D.10次(59) 設散列表中有m個存儲單元，散列函數(shù)H(key)= key % p，則p最好選擇_ B _。A. 小于等于m的最大奇數(shù)B. 小于等于m的最大素數(shù)C. 小于等于m的最大偶數(shù)D. 小于等于m的最大合數(shù)(60) _ D _是HASH查找的沖突處理方法。A.求余法 B. 平方取中法 C. 二分法 D. 開放地址法(61) 當?shù)闹递^小時，散列存儲通常比其他存儲方式具有_ B _的查找速度。A. 較慢B. 較快C. 相同 D. 不確定(62) 對線性表進行折半查找最方便的存儲結構

24、是_ B _。A順序表 B有序的順序表C鏈表 D有序的鏈表(63) 如果要求一個線性表既能較快的查找，又能適應動態(tài)變化的要求，可以采用_ D _查找方法。A分塊 B順序 C折半 D散列(64) 散列函數(shù)有一個共同性質，即函數(shù)值應按_ C _取其值域的每一個值。A最大概率 B最小概率 C同等概率 D平均概率(65) 下述排序算法中，穩(wěn)定的是_ B _。A.直接選擇排序 B. 直接插入排序 C.快速排序 D.堆排序 (66) 下列排序算法中，_ A _需要的輔助存儲空間最大。A.快速排序B.插入排序C.希爾排序D.基數(shù)排序(67) 下列各種排序算法中平均時間復雜度為O(n2)是_ D _。A. 快

25、速排序 B. 堆排序 C. 歸并排序 D. 冒泡排序(68) 在基于關鍵碼比較的排序算法中，_ C _算法在最壞情況下，關鍵碼比較次數(shù)不高于O(nlog2n)。A. 起泡排序B. 直接插入排序C. 二路歸并排序D. 快速排序(69) 一組記錄為46，79，56，38，84，40，則采用冒泡排序法按升序排列時第一趟排序結果是_ B _ 。A. 46,79,56,38,40,84 B.46,56,38,79,40,84C. 38,40,46,56,84,79 D.38,46,79,56,40,84(70) 每次從無序表中取出一個元素，把它插入到有序表中的適當位置，此種排序方法叫做_ A _ 排序。

26、A. 插入 B. 堆 C.快速 D.歸并(71) 每次從無序表中挑選出一個最小或最大元素，把它交換到有序表的一端，此種排序方法叫做_ B _排序。A. 插入 B. 堆 C.快速 D.歸并(72) 設一組初始記錄關鍵字序列(5，2，6，3，8)，以第一個記錄關鍵字5為基準進行一趟快速排序的結果為_ C _。A. 2，3，5，8，6B. 3，2，5，8，6C. 3，2，5，6，8D. 2，3，6，5，8(73) 下列排序方法中，哪一種方法的比較次數(shù)與紀錄的初始排列狀態(tài)無關_ D _。A. 直接插入排序 B. 起泡排序C. 快速排序 D. 直接選擇排序(74) 設有關鍵碼初始序列Q，H，C，Y，P，

27、A,M,S,R,D,F,X，新序列F，H，C，D，P，A，M，Q，R，S，Y,X是采用_ C _ 方法對初始序列進行第一趟掃描的結果。A. 直接插入排序 B二路歸并排序C以第一元素為分界元素的快速排序 D基數(shù)排序(75) 在待排序文件已基本有序的前提下，下述排序方法中效率最高的是_ C _。A. 直接插入排序 B. 直接選擇排序C 快速排序 D 歸并排序(76) 若需在O(nlog2n)的時間內完成對數(shù)組的排序，且要求排序是穩(wěn)定的，則可選排序方法是_ C _ 。A. 快速排序 B 堆排序C 歸并排序 D 直接插入排序(77) 將兩個各有n個元素的有序表歸并成一個有序表，其最少的比較次數(shù)是_ B

28、 _。A n B 2n-1 C 2n D n-1(78) 下列排序算法中，_ C _ 算法可能會出現(xiàn)下面情況：初始數(shù)據(jù)有序時，花費的間反而最多。A. 堆排序 B冒泡排序 C快速排序 D SHELL排序二、填空題。(每空1分，共10分)(1) 數(shù)據(jù)結構是一門研究非數(shù)值計算的程序設計問題中計算機的 數(shù)據(jù) 以及它們之間的 關系 和運算等的學科。(2) 數(shù)據(jù)結構包括數(shù)據(jù)的邏輯結構結構和物理結構結構。(3) 數(shù)據(jù)結構從邏輯上劃分為三種基本類型：_線性數(shù)據(jù)結構_、_樹型結構_和_圖結構_。(4) 數(shù)據(jù)的物理結構被分為_順序存儲_、_鏈式存儲_、_索引存儲_和_散列表（Hash）存儲_四種。(5) 一種抽象

29、數(shù)據(jù)類型包括_變量的取值范圍_和 _操作的類別_兩個部分。(6) 數(shù)據(jù)的邏輯結構是指 數(shù)據(jù)元素間的邏輯關系 ，數(shù)據(jù)的存儲結構是指 數(shù)據(jù)元素存儲方式或者數(shù)據(jù)元素的物理關系 。(7) 數(shù)據(jù)結構是指數(shù)據(jù)及其相互之間的_關系_。當結點之間存在M對N（M：N）的聯(lián)系時，稱這種結構為_網(wǎng)狀結構_。當結點之間存在1對N（1：N）的聯(lián)系時，稱這種結構為_樹結構_。(8) 對算法從時間和空間兩方面進行度量，分別稱為 空間復雜度和時間復雜度 分析。(9) 算法的效率可分為_空間_效率和_時間_效率。(10) for(i=1，t=1，s=0；i<=n；i+) t=t*i；s=s+t；的時間復雜度為_(n)_。

30、(11) 線性表是n個元素的_有限序列_。(12) 線性表的存儲結構有_順序存儲和鏈式存儲_。(13) 設線性表中有n個數(shù)據(jù)元素，則在順序存儲結構上實現(xiàn)順序查找的平均時間復雜度為_(n)_，在鏈式存儲結構上實現(xiàn)順序查找的平均時間復雜度為_ O(n)_。(14) 設順序線性表中有n個數(shù)據(jù)元素，則第i個位置上插入一個數(shù)據(jù)元素需要移動表中_ n-i+1_個數(shù)據(jù)元素；刪除第i個位置上的數(shù)據(jù)元素需要移動表中_ n-i _個元素。(15) 若頻繁地對線性表進行插入與刪除操作，該線性表應采用_鏈式_存儲結構。(16) 鏈式存儲結構中的結點包含_數(shù)據(jù)_域和_指針_域。(17) 對于一個長度為n的單鏈存儲的線性

31、表，在表頭插入元素的時間復雜度為_(1)_，在表尾插入元素的時間復雜度為_(n)_。(18) 棧的插入和刪除只能在棧的棧頂進行，后進棧的元素必定先出棧，所以又把棧稱為_ FILO _表；隊列的插入和刪除運算分別在隊列的兩端進行，先進隊列的元素必定先出隊列，所以又把隊列稱為 _ FIFO _表。(19) s=” I am a man” 長度為_10_ 。(20) s1=”hello “,s2=”boy”,s1,s2連接后為：_ hello boy _ 。(21) s=”this is the main string”,sub=”string”,strindex(s,

32、sub)是：_13_。(22) int a1010,已知a=1000,sizeof(int)=2,求a33地址：_1066_ 。(23) 設有兩個串p和q，求q在p中首次出現(xiàn)的位置的運算稱為_模式匹配_。(24) 在樹型結構中，樹根結點沒有_前趨_結點，其余每個結點有且僅有_一_個前驅結點；樹葉結點沒有_后繼_結點，其余每個結點的_后繼_結點數(shù)不受限制。(25) 在一棵二叉樹中，度為0的結點的個數(shù)為n0 ，度為2的結點的個數(shù)為n2 ，則：n0 =_n2 +1_。(26) 由分別帶權為3,9,6,2,5的共五個葉子結點構成一棵哈夫曼樹，則帶權路徑長度為_ 55_。(27) 在圖G的鄰接

33、表表示中，每個頂點鄰接表中所含的結點數(shù)，對于無向圖來說等于該 頂點的 _度數(shù)_，對于有向圖來說等于該頂點的_出度數(shù)_。(28) 假定一個圖具有n個頂點和e條邊，則采用鄰接矩陣表示的空間復雜性為_O(n2 ) _， 采用鄰接表表示的空間復雜性為_ O(n+e) _。(29) 對于長度為n的線性表，若進行順序查找，則時間復雜度為_ O(n)_；若采用折半法查找，則時間復雜度為_ O(log2n)_。(30) 假設在有序線性表A1.20上進行折半查找，則比較一次查找成功的結點數(shù)為_1_，則比較二次查找成功的結點數(shù)為_2_，則比較三次查找成功的結點數(shù)為_4_，則比較四次查找成功的結點數(shù)為_8_，則比較

34、五次查找成功的結點數(shù)為_5_，平均查找長度為_ log2(n+1)-1_。(31) 在一棵二叉排序樹中，每個分支結點的左子樹上所有結點的值一定_小于_該結點的值，右子樹上所有結點的值一定_大于_該結點的值。 (32) 對一棵二叉排序樹進行中序遍歷時，得到的結點序列是一個_增序序列_。(33) 對于線性表（70，34，55，23，65，41，20）進行散列存儲時，若選用H（K）=K %7作為散列函數(shù)，則散列地址為0的元素是_70_，散列地址為6的是_34,20,55_。(34) 在線性表的散列存儲中，裝填因子a又稱為裝填系數(shù)，若用m表示散列表的長度，n表示待散列存儲的元素的個數(shù)，則a等于_ n/

35、m _。(35) 散列表中解決沖突的兩種方法是_開放地址法_和_鏈地址法_。(36) 在散列存儲中，裝填因子a的值越大，則_產(chǎn)生沖突的可能性就越大_；a的值越小，則_產(chǎn)生沖突的可能性就越小_。(37) 散列法存儲的基本思想是由_關鍵碼直接_決定數(shù)據(jù)的存儲地址。(38) 構造哈希函數(shù)的方法有(寫二個)_直接定址法，數(shù)字分析法，平方取中法，折疊法，除留余數(shù)法，隨機數(shù)法_。(39) 在分塊查找中首先查找 _索引_，然后再查找相應的_塊_。(40) 散列表的查找效率主要取決于散列表造表時選擇的_哈希函數(shù)_ 和_裝填因子_。(41) 對兩棵具有相同關鍵字集合而形狀不同的二叉排序樹，_中序_ 遍歷它們得到

36、的序列的順序是一樣的。(42) 當待排序的記錄數(shù)較大，排序碼較隨機且對穩(wěn)定性不作要求時，宜采用_快速_排序；當待排序的記錄數(shù)較大，存儲空間允許且要求排序是穩(wěn)定時，宜采用_歸并_排序。(43) 在堆排序的過程中，對任一分支結點進行篩運算的時間復雜度為_ O(log2n)_，整個堆排序過程的時間復雜度為_ O(nlog2n)_。(44) 當向一個大根堆插入一個具有最大值的元素時，需要逐層_向上_調整，直到被調整到_根結點_位置為止。(45) 對一組初始關鍵字序列（40，50，95，20，15，70，60，45，10）進行冒泡排序，則第一趟需要進行相鄰記錄的比較的次數(shù)為_8_，在整個排序過程中最多需

37、要進行_8_趟排序才可以完成。(46) 在在插入排序、選擇排序、快速排序、堆排序、歸并排序和基數(shù)排序中，平均比較次數(shù)最少的排序是_快速_，需要內存容量最多的是_歸并_。(47) 堆排序是不穩(wěn)定，空間復雜度為 _ O(1)_。在最壞情況下，其時間復雜度也為_ O(nlog2n)_。(48) 若待排序的文件中存在多個關鍵字相同的記錄，經(jīng)過某種排序方法排序后，具有相同關鍵字的記錄間的相對位置保持不變，則這種排序方法是_穩(wěn)定_的排序方法。(49) 在對一組記錄(50,40,95，20，15,70,60,45,80)進行直接插入排序時，當把第7個記錄60插入到有序表時，為尋找插入位置需比較_3_次。(5

38、0) 二路歸并排序的時間復雜度是_ O(nlog2n)_。(51) 對于n個記錄的集合進行歸并排序，所需的附加空間消耗是_ O(n)_。(52) 設表中元素的初始狀態(tài)是按鍵值遞增的，分別用堆排序、快速排序、冒泡排序和歸并排序方法對其仍按遞增順序進行排序，則_冒泡排序_最省時間，_快速排序_最費時間。三、判斷題。(每小題1分，共10分)( × )1數(shù)據(jù)元素是數(shù)據(jù)的最小單位。( × )2數(shù)據(jù)項是數(shù)據(jù)的基本單位。( )3順序存儲的線性表可以隨機存取。( )4線性表中的元素可以是各種各樣的，但同一線性表中的數(shù)據(jù)元素具有相同的特性， 因此，是屬于同一數(shù)據(jù)對象。( × )5在

39、單鏈表中，任何兩個元素的存儲位置之間都有固定的聯(lián)系，因為可以從頭結點查找任何一個元素。( × )6在單鏈表中，要取得某個元素，只要知道該元素的指針即可，因此，單鏈表是隨機存取的存儲結構。( × )7鏈表的每個結點中，都恰好包含一個指針。( × )8數(shù)組是同類型值的集合。 ( )9使用三元組表示稀疏矩陣的元素，有時并不能節(jié)省存儲時間。( )10. 線性表可以看成是廣義表的特例，如果廣義表中的每個元素都是原子，則廣義表便成為線性表。( )11. 由樹轉換成二叉樹，其根結點的右子樹總是空的。( × )12. 后序遍歷樹和中序遍歷與該樹對應的二叉樹，其結果不同。

40、( × )13. 若有一個結點是某二叉樹子樹的中序遍歷序列中的最后一個結點，則它必是該子 樹的前序遍歷序列中的最后一個結點。( )14.若一個樹葉是某子樹的中序遍歷序列中的最后一個結點，則它必是該子樹的前序 遍歷序列中的最后一個結點。( × )15. 已知二叉樹的前序遍歷和后序遍歷序列并不能唯一地確定這棵樹，因為不知道樹 的根結點是哪一個。( × )16. 在哈夫曼編碼中，當兩個字符出現(xiàn)的頻率相同時，其編碼也相同，對于這種情況應作特殊處理。( )17. 有回路的圖不能進行拓撲排序。( × )18. 連通分量是無向圖中的極小連通子圖。 ( )19. 散列法

41、存儲的基本思想是由關鍵碼的值決定數(shù)據(jù)的存儲地址。( )20. 散列表的查找效率取決于散列表造表時選取的散列函數(shù)和處理沖突的方法。( )21. m階B-樹每一個結點的子樹個數(shù)都小于或等于m。( )22. 中序遍歷二叉排序樹的結點就可以得到排好序的結點序列。( )23. 在二叉排序樹上插入新的結點時，不必移動其它結點，僅需改動某個結點的指針， 由空變?yōu)榉强占纯伞? )24. 當待排序的元素很多時，為了交換元素的位置，移動元素要占用較多的時間，這是影響時間復雜性的主要因素。( )25. 對于n個記錄的集合進行快速排序，所需要的平均時間是O(nlog2 n)。( )26. 對于n個記錄的集合進行歸并排

42、序，所需要的平均時間是O(nlog2 n)。( )27. 堆中所有非終端結點的值均小于或等于（大于或等于）左右子樹的值。( × )28. 磁盤上的順序文件中插入新的記錄時，必須復制整個文件。( × )29. 在索引順序文件中插入新的記錄時，必須復制整個文件。( × )30. 索引順序文件是一種特殊的順序文件，因此通常存放在磁帶上。四、簡答題。(共6小題，每小題約5分，共32分) 1. 簡述下列術語：數(shù)據(jù)、數(shù)據(jù)項、數(shù)據(jù)元素、數(shù)據(jù)邏輯結構、數(shù)據(jù)存儲結構、數(shù)據(jù)類型和算法。數(shù)據(jù)：數(shù)據(jù)是信息的載體，是計算機程序加工和處理的對象，包括數(shù)值數(shù)據(jù)和非數(shù)值數(shù)據(jù)。數(shù)據(jù)項：數(shù)據(jù)項指不可

43、分割的、具有獨立意義的最小數(shù)據(jù)單位，數(shù)據(jù)項有時也稱為字段或域。數(shù)據(jù)元素：數(shù)據(jù)元素是數(shù)據(jù)的基本單位，在計算機程序中通常作為一個整體進行考慮和處理，一個數(shù)據(jù)元素可由若干個數(shù)據(jù)項組成。數(shù)據(jù)邏輯結構：數(shù)據(jù)的邏輯結構就是指數(shù)據(jù)元素間的關系。數(shù)據(jù)存儲結構：數(shù)據(jù)的物理結構表示數(shù)據(jù)元素的存儲方式或者數(shù)據(jù)元素的物理關系。數(shù)據(jù)類型：是指變量的取值范圍和所能夠進行的操作的總和。算法：是對特定問題求解步驟的一種描述，是指令的有限序列。2. 簡述棧和線性表的區(qū)別。答：一般線性表使用數(shù)組來表示的。線性表一般有插入、刪除、讀取等對于任意元素的操作。而棧只是一種特殊的線性表。棧只能在線性表的一端插入（稱為入棧,push）或者

44、讀取棧頂元素或者稱為“彈出、出棧”(pop)。3. 簡述棧和隊列這兩種數(shù)據(jù)結構的相同點和不同點。答：相同點：棧和隊列都是特殊的線性表，只在端點處進行插入，刪除操作。不同點：棧只在一端（棧頂）進行插入，刪除操作；隊列在一端（top）刪除，一端(rear)插入。4. 如果進棧的元素序列為A，B，C，D，則可能得到的出棧序列有多少種? 寫出全部的可能序列。答：可能序列有14種：ABCD; ACBD; ACDB; ABDC; ADCB; BACD; BADC; BCAD; BCDA; BDCA; CBAD; CBDA; CDBA; DCBA。5. 如果進棧的元素序列為1，2，3，4，5，6，能否得到4

45、，3，5，6，1，2和1，3，5，4，2，6的出棧序列?并說明為什么不能得到或如何得到。答：不能得到4，3，5，6，1，2，最先出棧的是4,則按321的方式出，不可能得到1在2前的序列，可以得到1，3，5，4，2，6，按如下方式進行push(1), pop(), push(2), push(3), pop(), push(4), push(5), pop(), pop(), pop(), push(6), pop()。6. 設s=“I AM A STUDENT”,t=“GOOD”，q=“WORKER”。求：StrLength (s)， StrLength (t)，SubStr( s，8，7)，

46、SubStr(t，2，1)，StrIndex(s,“A”)，StrIndex (s，t)，StrRep(s，“STUDENT”，q)，SubStr (SubStr (s，6，2)，StrConcat (t，SubStr(s，7，8)。答：StrLength (s)=14, StrLength (t)=4, SubStr( s，8，7)=” STUDENT”, SubStr(t，2，1)=”O(jiān)”,StrIndex(s,“A”)=3, StrIndex (s，t)=0, StrRep(s，“STUDENT”，q)=” I AM A WORKER”,7. 簡述下列每對術語的區(qū)別：空串和空格串；串變量

47、和串常量；主串和子串；串變量的名字和串變量的值。答：空串：不含任何字符；空格串：所含字符都是空格。串變量和串常量:串常量在程序的執(zhí)行過程中只能引用不能改變；串變量的值在程序執(zhí)行過程中是可以改變和重新賦值的。主串與子串：子串是主串的一個子集。串變量的名字與串變量的值:串變量的名字表示串值的標識符。8. 設有二維數(shù)組A(6×8)，每個元素占6個字節(jié)存儲，順序存放，A的起地址為1000，計算：(1)數(shù)組A的體積(即存儲量)；(2)數(shù)組的最后一個元素A的起地址；(3)按行優(yōu)先存放時，元素A1,4的起地址；(4)按列優(yōu)先存放時，元素A4,7的起地址。 (1)6*8*6=288(2)1

48、000+47*6=1282(3)1000+(8+4)*8=1096(4)1000+(6*7+4)*8=13689. 分別畫出含三個結點的無序樹與二叉樹的所有不同形態(tài)。答：無序樹形態(tài)如下：二叉樹形態(tài)如下：10. 分別寫出圖1中所示二叉樹的先序遍歷、中序遍歷、后序遍歷的結點訪問序列。答：先序遍歷序列:ABDEHICFJG 中序遍歷序列:DBHEIAFJCG 后序遍歷序列:DHIEBJFGCA11. 試找出分別滿足下列條件的所有二叉樹。 (1) 先序序列與中序序列相同。 (2) 后序序列與中序序列相同。 (3) 先序序列與后序序列相同。答：(1) 先序序列和中序序列相同：空樹或缺左子樹的單支樹；(2

49、) 后序序列和中序序列相同：空樹或缺右子樹的單支樹；(3) 先序序列和后序序列相同：空樹或只有根結點的二叉樹。12. 已知一棵二叉樹的中序序列和后序序列分別為BDCEAFHG和DECBHGFA，試畫出這棵二叉樹。答：這棵二叉樹為:13. 分別寫出圖2中所示二叉樹的先序遍歷、中序遍歷、后序遍歷的結點訪問序列。答：先序遍歷序列:ABDGCEHF 中序遍歷序列:DGBAEHCF 后序遍歷序列:GDBHEFCA14. 給定權值(7,18,3,32,5,26,12,8)，構造的哈夫曼樹。答：哈夫曼樹為:15. 假設用于通信的電文僅由8個字母組成，字母在電文中出現(xiàn)的頻率分別為7,19,2,6,32,3,2

50、1,10，試為這8個設計哈夫曼編碼。答：哈夫曼樹為:在上述哈夫曼樹的每個左分支上標以0，右分支上標以1，并設這8個字母分別為A、B、C、D、E、F、G和H，則它們的哈夫曼樹為分別為:A：0000 B：10 C：00110 D：0010 E：01 F：00111 G：11 H：000116. 畫出無向圖G1的鄰接矩陣和鄰接表示意圖，并寫出每個頂點的度。答：（1）鄰接矩陣:（2）鄰接鏈表：（3）每個頂點的度：頂點 度 V1 3 V2 3 V3 2 V4 3 V5 3 17. 畫出有向圖G2的鄰接矩陣、鄰接表和逆鄰接表示意圖，并寫出每個頂點的入度和出度。答：（1）鄰接鏈表：（2）逆鄰接鏈表：（3）

51、頂點 入度 出度 V1 3 0 V2 2 2 V3 1 2 V4 1 3 V5 2 1 V6 2 318. 對應圖G3，寫出從v1出必的深度優(yōu)先遍歷序列和廣度優(yōu)先遍歷序列各三個。答：深度優(yōu)先查找遍歷序列：V1 V2 V3 V4 V5; V1 V3 V5 V4 V2; V1 V4 V3 V5 V2廣度優(yōu)先查找遍歷序列：V1 V2 V3 V4 V5; V1 V3 V2 V4 V5; V1 V4 V3 V2 V519. 何謂二叉排序樹?答：一棵二叉排序樹(又稱二叉查找樹)或者是一棵空樹，或者是一棵同時滿足下列條件的二叉樹： (1)若它的左子樹不空，則左子樹上所有結點的鍵值均小于它根結點鍵值。 (2)

52、若它的右子樹不空，則右子樹上所有結點的鍵值均大于它根結點鍵值。 (3)它的左、右子樹也分別為二叉排序樹。20. 順序查找時間為O(n)，二分查找時間為O(log2n)，散列查找時間為O(1)，為什么有高效率的查找方法而不放棄低效率的方法?答：衡量算法的標準有很多，時間復雜度只是其中之一。盡管有些算法時間性能很好，但是其他方面可能就存在著不足。比如散列查找的時間性能很優(yōu)越，但是需要關注如何合理地構造散列函數(shù)問題，而且總存在著沖突等現(xiàn)象，為了解決沖突，還得采用其他方法。 二分查找也是有代價的，因為事先必須對整個查找區(qū)間進行排序，而排序也是費時的，所以常應用于頻繁查找的場合。對于順序查找，盡管效率不高，但卻比較簡單，常用于查找