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

...wd......wd......wd...一、選擇題。(每題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.數(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ù)在計算機存儲器內(nèi)表示時，物理地址與邏輯地址一樣并且是連續(xù)的，稱之為___C____。A.存儲構造B.邏輯構造C.順序存儲構造D.鏈式存儲構造(8)在數(shù)據(jù)構造的討論中把數(shù)據(jù)構造從邏輯上分為___A____。A.內(nèi)部構造與外部構造B.靜態(tài)構造與動態(tài)構造C.線性構造與非線性構造 D.緊湊構造與非緊湊構造(9)對一個算法的評價，不包括如下____B_____方面的內(nèi)容。A.強健性和可讀性B.并行性C.正確性D.時空復雜度(10)算法分析的兩個方面是__A____。A.空間復雜性和時間復雜性B.正確性和簡明性C.可讀性和文檔性D.數(shù)據(jù)復雜性和程序復雜性(11)線性表是具有n個___C_____的有限序列〔n≠0)。A.表元素B.字符C.數(shù)據(jù)元素D.數(shù)據(jù)項(12)線性表的存儲構造是一種____B____的存儲構造。A.隨機存取B.順序存取C.索引存取D.HASH存取(13)在一個長度為n的順序表中，向第i個元素〔1≤i≤n＋１〕之前插入一個新元素時，需要向后移動____B____個元素。A.n-iB.n-i+1C.n-i-1D.i(14)鏈表是一種采用____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->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->next C.p=p->next->next D.p->next=p(18)以下說法哪個正確____D______A.堆棧是在兩端操作、先進后出的線性表B.堆棧是在一端操作、先進先出的線性表C.隊列是在一端操作、先進先出的線性表D.隊列是在兩端操作、先進先出的線性表(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.棧

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í)行____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,那么棧的不可能的輸出序列是____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.不能確定(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=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。當從隊列中刪除一個元素，再參加兩個元素后，rear和front的值分別為____B_____。A.1和5

B.2和4

C.4和2

D.5和1(32)設順序循環(huán)隊列Q[0：M-1]的頭指針和尾指針分別為F和R，頭指針F總是指向隊頭元素的前一位置，尾指針R總是指向隊尾元素的當前位置，那么該循環(huán)隊列中的元素個數(shù)為____C_____。A.R-F

B.F-R

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；

D.s->next=front；front=s；(34)如下陳述中正確的選項是___A______。A.串是一種特殊的線性表B.串的長度必須大于零C.串中元素只能是字母D.空串就是空白串(35)以下關于串的表達中，正確的選項是___D______。A.串長度是指串中不同字符的個數(shù)B.串是n個字母的有限序列C.如果兩個串含有一樣的字符，那么它們相等D.只有當兩個串的長度相等，并且各個對應位置的字符都相符時才相等(36)字符串的長度是指___C______。A.串中不同字符的個數(shù)B.串中不同字母的個數(shù)C.串中所含字符的個數(shù)D.串中不同數(shù)字的個數(shù)(37)兩個字符串相等的充要條件是____C______。A.兩個字符串的長度相等B.兩個字符串中對應位置上的字符相等C.同時具備(A)和(B)兩個條件D.以上答案都不對(38)串是一種特殊的線性表，其特殊性表達在____B_______。A.可以順序存儲B.數(shù)據(jù)元素是一個字符C.可以鏈接存儲D.數(shù)據(jù)元素可以是多個字符(39)設有兩個串p和q，求q在p中首次出現(xiàn)的位置的運算稱作____B______。A.連接B.模式匹配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.BCDEFB.BCDEFGC.BCPQRSTD.BCDEFEF(41)函數(shù)substr(“DATASTRUCTURE〞，5，9)的返回值為___A______。A.“STRUCTURE〞B.“DATA〞C.“ASTRUCTUR〞D.“DATASTRUCTURE〞(42)設串S=〞IAMATEACHER!〞，其長度是____D______。A.16B.11C.14D.15(43)假定在一棵二叉樹中，雙分支結點數(shù)為15個，單分支結點數(shù)為32個，那么葉子結點數(shù)為____B____。A.15B.16C.17D.47(44)假定一棵二叉樹的結點數(shù)為18個，那么它的最小高度____B____。A.4B.5C.6D.18(45)在一棵二叉樹中第五層上的結點數(shù)最多為____C____。A.8B.15C.16D.32(46)在一棵具有五層的滿二叉樹中，結點總數(shù)為____A____。A.31B.32C.33D.16(47)8個數(shù)據(jù)元素為(34、76、45、18、26、54、92、65)，按照依次插入結點的方法生成一棵二叉排序樹后，最后兩層上的結點總數(shù)為____B____。A.1B.2C.D.4(48)由分別帶權為9、2、5、7的四個葉子結點構造一棵哈夫曼樹，該樹的帶權路徑長度為____C____。A.23B.37C.44D.46(49)在樹中除根結點外，其余結點分成m(m≥0)個____A____的集合T1,T2,T3...Tm,每個集合又都是樹，此時結點T稱為Ti的父結點，Ti稱為T的子結點(1≤i≤m)。A.互不相交B.可以相交C.葉結點可以相交D.樹枝結點可以相交(50)如果結點A有三個兄弟，而且B是A的雙親，那么B的出度是____B____。A.3B.4C.5D.1(51)在一個有向圖中，所有頂點的入度之和等于所有頂點的出度之和的____B____倍。A.1/2B.1C.2D.4(52)具有n個頂點的無向完全圖，邊的總數(shù)為____D____條。A.n-1B.nC.n+1D.n*(n-1)/2(53)在無向圖G的鄰接矩陣A中，假設A[i,j]等于1，那么A[j,i]等于____C____。A.i+jB.i-jC.1D.0(54)圖的深度優(yōu)先或廣度優(yōu)先遍歷的空間復雜性均為____A____。(訪問標志位數(shù)組空間)A.O(n)B.O(e)C.O(n-e)D.O(n+e)(55)請指出在順序表{2、5、7、10、14、15、18、23、35、41、52}中，用折半法查找關鍵碼12需做____C___次關鍵碼比較。A.2B.3C.4D.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，35，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)當α的值較小時，散列存儲通常比其他存儲方式具有_____B______的查找速度。A.較慢 B.較快 C.一樣D.不確定(62)對線性表進展折半查找最方便的存儲構造是____B_______。A．順序表B．有序的順序表C．鏈表D．有序的鏈表(63)如果要求一個線性表既能較快的查找，又能適應動態(tài)變化的要求，可以采用_____D____查找方法。A．分塊B．順序C．折半D．散列(64)散列函數(shù)有一個共同性質(zhì)，即函數(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.快速排序 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,84B.46,56,38,79,40,84C.38,40,46,56,84,79D.38,46,79,56,40,84(70)每次從無序表中取出一個元素，把它插入到有序表中的適當位置，此種排序方法叫做___A_____排序。A.插入B.堆C.快速D.歸并(71)每次從無序表中挑選出一個最小或最大元素，把它交換到有序表的一端，此種排序方法叫做___B_____排序。A.插入B.堆C.快速D.歸并(72)設一組初始記錄關鍵字序列(5，2，6，3，8)，以第一個記錄關鍵字5為基準進展一趟快速排序的結果為____C____。 A.2，3，5，8，6 B.3，2，5，8，6 C.3，2，5，6，8 D.2，3，6，5，8(73)以下排序方法中，哪一種方法的比較次數(shù)與紀錄的初始排列狀態(tài)無關___D_____。A.直接插入排序B.起泡排序C.快速排序D.直接選擇排序(74)設有關鍵碼初始序列{Q，H，C，Y，P，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)的時間內(nèi)完成對數(shù)組的排序，且要求排序是穩(wěn)定的，那么可選排序方法是___C_____。A.快速排序B．堆排序C．歸并排序D．直接插入排序(77)將兩個各有n個元素的有序表歸并成一個有序表，其最少的比較次數(shù)是___B_______。A．nB．2n-1C．2nD．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)一種抽象數(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)______。(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的單鏈存儲的線性表，在表頭插入元素的時間復雜度為___Ο(1)______，在表尾插入元素的時間復雜度為_____Ο(n)_______。(18)棧的插入和刪除只能在棧的棧頂進展，后進棧的元素必定先出棧，所以又把棧稱為____FILO________表；隊列的插入和刪除運算分別在隊列的兩端進展，先進隊列的元素必定先出隊列，所以又把隊列稱為_____FIFO______表。(19)s=〞Iamaman〞長度為____10_______。(20)s1=〞hello“,s2=〞boy〞,s1,s2連接后為：________helloboy______________。(21)s=〞thisisthemainstring〞,sub=〞string〞,strindex(s,sub)是：_______13_______。(22)inta[10][10],a=1000,sizeof(int)=2,求a[3][3]地址：_______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的鄰接表表示中，每個頂點鄰接表中所含的結點數(shù)，對于無向圖來說等于該頂點的______度數(shù)______，對于有向圖來說等于該頂點的______出度數(shù)______。(28)假定一個圖具有n個頂點和e條邊，那么采用鄰接矩陣表示的空間復雜性為______O(n2)______，采用鄰接表表示的空間復雜性為______O(n+e)______。(29)對于長度為n的線性表，假設進展順序查找，那么時間復雜度為______O(n)____；假設采用折半法查找，那么時間復雜度為______O(log2n)____。(30)假設在有序線性表A[1..20]上進展折半查找，那么比較一次查找成功的結點數(shù)為____1_______，那么比較二次查找成功的結點數(shù)為____2_______，那么比較三次查找成功的結點數(shù)為____4_______，那么比較四次查找成功的結點數(shù)為_____8______，那么比較五次查找成功的結點數(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)在線性表的散列存儲中，裝填因子又稱為裝填系數(shù)，假設用m表示散列表的長度，n表示待散列存儲的元素的個數(shù)，那么等于____n/m_______。(35)散列表中解決沖突的兩種方法是____開放地址法_________和____鏈地址法_________。(36)在散列存儲中，裝填因子a的值越大，那么_______產(chǎn)生沖突的可能性就越大____________；a的值越小，那么_____產(chǎn)生沖突的可能性就越小___________。(37)散列法存儲的基本思想是由________關鍵碼直接______________決定數(shù)據(jù)的存儲地址。(38)構造哈希函數(shù)的方法有(寫二個)______________直接定址法，數(shù)字分析法，平方取中法，折疊法，除留余數(shù)法，隨機數(shù)法_________________________________________。(39)在分塊查找中首先查找_____索引________，然后再查找相應的______塊_________。(40)散列表的查找效率主要取決于散列表造表時選擇的_____哈希函數(shù)________和______裝填因子_________。(41)對兩棵具有一樣關鍵字集合而形狀不同的二叉排序樹，____中序_______遍歷它們得到的序列的順序是一樣的。(42)當待排序的記錄數(shù)較大，排序碼較隨機且對穩(wěn)定性不作要求時，宜采用______快速_________排序；當待排序的記錄數(shù)較大，存儲空間允許且要求排序是穩(wěn)定時，宜采用______歸并_________排序。(43)在堆排序的過程中，對任一分支結點進展篩運算的時間復雜度為___O(log2n)_____，整個堆排序過程的時間復雜度為____O(nlog2n)____。(44)當向一個大根堆插入一個具有最大值的元素時，需要逐層____向上_____調(diào)整，直到被調(diào)整到_____根結點_______位置為止。(45)對一組初始關鍵字序列〔40，50，95，20，15，70，60，45，10〕進展冒泡排序，那么第一趟需要進展相鄰記錄的比較的次數(shù)為____8______，在整個排序過程中最多需要進展_____8_____趟排序才可以完成。(46)在在插入排序、選擇排序、快速排序、堆排序、歸并排序和基數(shù)排序中，平均比較次數(shù)最少的排序是___快速_______，需要內(nèi)存容量最多的是____歸并______。(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_____次。(50)二路歸并排序的時間復雜度是___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．在單鏈表中，任何兩個元素的存儲位置之間都有固定的聯(lián)系，因為可以從頭結點查找任何一個元素。(×)6．在單鏈表中，要取得某個元素，只要知道該元素的指針即可，因此，單鏈表是隨機存取的存儲構造。(×)7．鏈表的每個結點中，都恰好包含一個指針。(×)8．數(shù)組是同類型值的集合。(√)9．使用三元組表示稀疏矩陣的元素，有時并不能節(jié)省存儲時間。(√)10.線性表可以看成是廣義表的特例，如果廣義表中的每個元素都是原子，那么廣義表便成為線性表。(√)11.由樹轉換成二叉樹，其根結點的右子樹總是空的。(×)12.后序遍歷樹和中序遍歷與該樹對應的二叉樹，其結果不同。(×)13.假設有一個結點是某二叉樹子樹的中序遍歷序列中的最后一個結點，那么它必是該子樹的前序遍歷序列中的最后一個結點。(√)14.假設一個樹葉是某子樹的中序遍歷序列中的最后一個結點，那么它必是該子樹的前序遍歷序列中的最后一個結點。(×)15.二叉樹的前序遍歷和后序遍歷序列并不能唯一地確定這棵樹，因為不知道樹的根結點是哪一個。(×)16.在哈夫曼編碼中，當兩個字符出現(xiàn)的頻率一樣時，其編碼也一樣，對于這種情況應作特殊處理。(√)17.有回路的圖不能進展拓撲排序。(×)18.連通分量是無向圖中的極小連通子圖。(√)19.散列法存儲的基本思想是由關鍵碼的值決定數(shù)據(jù)的存儲地址。(√)20.散列表的查找效率取決于散列表造表時選取的散列函數(shù)和處理沖突的方法。(√)21.m階B-樹每一個結點的子樹個數(shù)都小于或等于m。(√)22.中序遍歷二叉排序樹的結點就可以得到排好序的結點序列。(√)23.在二叉排序樹上插入新的結點時，不必移動其它結點，僅需改動某個結點的指針，由空變?yōu)榉强占纯伞?√)24.當待排序的元素很多時，為了交換元素的位置，移動元素要占用較多的時間，這是影響時間復雜性的主要因素。(√)25.對于n個記錄的集合進展快速排序，所需要的平均時間是O(nlog2n)。(√)26.對于n個記錄的集合進展歸并排序，所需要的平均時間是O(nlog2n)。(√)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ù)項指不可分割的、具有獨立意義的最小數(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〕或者讀取棧頂元素或者稱為“彈出、出棧〞(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，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=“IAMASTUDENT〞,t=“GOOD〞，q=“WORKER〞。求：StrLength(s)，StrLength(t)，SubStr(s，8，7)，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〞,StrIndex(s,“A〞)=3,StrIndex(s，t)=0,StrRep(s，“STUDENT〞，q)=〞IAMAWORKER〞,7.簡述以下每對術語的區(qū)別：空串和空格串；串變量和串常量；主串和子串；串變量的名字和串變量的值。答：空串：不含任何字符；空格串：所含字符都是空格。串變量和串常量:串常量在程序的執(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)1000+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)后序序列和中序序列一樣：空樹或缺右子樹的單支樹； (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,21,10，試為這8個設計哈夫曼編碼。答：哈夫曼樹為:在上述哈夫曼樹的每個左分支上標以0，右分支上標以1，并設這8個字母分別為A、B、C、D、E、F、G和H，那么它們的哈夫曼樹為分別為:A：0000B：10C：00110D：0010E：01F：00111G：11H：000116.畫出無向圖G1的鄰接矩陣和鄰接表示意圖，并寫出每個頂點的度。答：〔1〕鄰接矩陣:〔2〕鄰接鏈表：〔3〕每個頂點的度：頂點度V13V23V32V43V5317.畫出有向圖G2的鄰接矩陣、鄰接表和逆鄰接表示意圖，并寫出每個頂點的入度和出度。答：〔1〕鄰接鏈表：〔2〕逆鄰接鏈表：〔3〕頂點入度出度V130V222V312V413V521V62318.對應圖G3，寫出從v1出必的深度優(yōu)先遍歷序列和廣度優(yōu)先遍歷序列各三個。答：深度優(yōu)先查找遍歷序列：V1V2V3V4V5;V1V3V5V4V2;V1V4V3V5V2廣度優(yōu)先查找遍歷序列：V1V2V3V4V5;V1V3V2V4V5;V1V4V3V2V519.何謂二叉排序樹?答：一棵二叉排序樹(又稱二叉查找樹)或者是一棵空樹，或者是一棵同時滿足以下條件的二叉樹：(1)假設它的左子樹不空，那么左子樹上所有結點的鍵值均小于它根結點鍵值。(2)假設它的右子樹不空，那么右子樹上所有結點的鍵值均大于它根結點鍵值。(3)它的左、右子樹也分別為二叉排序樹。20.順序查找時間為O(n)，二分查找時間為O(log2n)，散列查找