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

1、一、選才i題。(每小題2分，共40分)(1)計(jì)算機(jī)識(shí)別.存儲(chǔ)和加工處理的對(duì)象被統(tǒng)稱為AA.數(shù)據(jù)B.數(shù)據(jù)元素C.數(shù)據(jù)結(jié)構(gòu)D.數(shù)據(jù)類型(2)數(shù)據(jù)結(jié)構(gòu)通常是研究數(shù)據(jù)的_A及它們之間的聯(lián)系。A.存儲(chǔ)和邏輯結(jié)構(gòu)B.存儲(chǔ)和抽象C.理想和抽象D.理想與邏輯不是數(shù)據(jù)的邏輯結(jié)構(gòu)是AOA.散列結(jié)構(gòu)B.線性結(jié)構(gòu)C.樹(shù)結(jié)構(gòu)D.圖結(jié)構(gòu)(4)數(shù)據(jù)結(jié)構(gòu)被形式地定義為<D,R>,其中D是B的有限集，R是_C的有限集。A.算法B.數(shù)據(jù)兀素C.數(shù)據(jù)操作D.邏輯結(jié)構(gòu)組成數(shù)據(jù)的基本單位是AOA.數(shù)據(jù)項(xiàng)B.數(shù)據(jù)類型C.數(shù)據(jù)兀素D.數(shù)據(jù)變量(6)設(shè)數(shù)據(jù)結(jié)構(gòu)A=(D,R),其中1D=1,2,3,4,R=r,r=<1,2&

2、gt;,<2,3>,<3,4>,<4,1>,則數(shù)據(jù)結(jié)構(gòu)A是AoA.線性結(jié)構(gòu)B.樹(shù)型結(jié)構(gòu)C.圖型結(jié)構(gòu)D.集合(7)數(shù)據(jù)在計(jì)算機(jī)存儲(chǔ)器內(nèi)表示時(shí)，物理地址與邏輯地址相同并且是連續(xù)的，稱之為CA.存儲(chǔ)結(jié)構(gòu)B.邏輯結(jié)構(gòu)C.順序存儲(chǔ)結(jié)構(gòu)D.鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)(8)在數(shù)據(jù)結(jié)構(gòu)的討論中把數(shù)據(jù)結(jié)構(gòu)從邏輯上分為A。A.內(nèi)部結(jié)構(gòu)與外部結(jié)構(gòu)B.靜態(tài)結(jié)構(gòu)與動(dòng)態(tài)結(jié)構(gòu)C.線性結(jié)構(gòu)與非線性結(jié)構(gòu)D.緊湊結(jié)構(gòu)與非緊湊結(jié)構(gòu)(9)對(duì)一個(gè)算法的評(píng)價(jià)，不包括如下B方面的內(nèi)容。A.健壯性和可讀性B.并行性C.正確性D.時(shí)空復(fù)雜度(10)算法分析的兩個(gè)方面是A。A.空間復(fù)雜性和時(shí)間復(fù)雜性B.正確性和簡(jiǎn)明性C.可

3、讀性和文檔性D.數(shù)據(jù)復(fù)雜性和程序復(fù)雜性(11)線性表是具有n個(gè)C的有限序列(nw0)A.表元素B.字符C.數(shù)據(jù)元素D.數(shù)據(jù)項(xiàng)(12)線性表的存儲(chǔ)Z構(gòu)是一種B的存儲(chǔ)結(jié)構(gòu)。A.隨機(jī)存取B.順序存取C.索引存取D.HASH存取(13)在一個(gè)長(zhǎng)度為個(gè)元素。的順序表中，向第i個(gè)元素(1Wi<n+1)之前插入一個(gè)新元素時(shí)，需要向后移動(dòng)A.n-iB.n-i+1C.n-i-1D.i鏈表是一種采用B存儲(chǔ)結(jié)構(gòu)存儲(chǔ)的線性表;A.順序B.鏈?zhǔn)紺.星式D.網(wǎng)狀下面關(guān)于線性表的敘述錯(cuò)誤的是D。A.線性表采用順序存儲(chǔ)必須占用一片連續(xù)的存儲(chǔ)空間B.線性表采用鏈?zhǔn)酱鎯?chǔ)不必占用一片連續(xù)的存儲(chǔ)空間C.線性表采用鏈?zhǔn)酱鎯?chǔ)便于插

4、入和刪除操作的實(shí)現(xiàn)D.線性表采用順序存儲(chǔ)便于插入和刪除操作的實(shí)現(xiàn)設(shè)指針q指向單鏈表中結(jié)點(diǎn)A,指針p指向單鏈表中結(jié)點(diǎn)A的后繼結(jié)點(diǎn)B,指針s指向被插入的結(jié)點(diǎn)X,則在A和結(jié)點(diǎn)B之間插入結(jié)點(diǎn)X的操作序列為_(kāi)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=ss->next=q設(shè)指針變量p指向單鏈表結(jié)點(diǎn)A,則刪除結(jié)點(diǎn)A的后繼結(jié)點(diǎn)B需要的操作為AA.p->next=p->next->next

5、B.p=p->nextC.p=p->next->nextD.p->next=pDA.堆棧是在兩端操作、先進(jìn)后出的線性表B.堆棧是在一端操作、先進(jìn)先出的線性表C.隊(duì)列是在一端操作、先進(jìn)先出的線性表D.隊(duì)列是在兩端操作、先進(jìn)先出的線性表?xiàng)：完?duì)列的共同點(diǎn)是C。A.都是先進(jìn)后出B.都是先進(jìn)先出C.只允許在端點(diǎn)處插入和刪除元素D.沒(méi)有共同點(diǎn)DA、元素個(gè)數(shù)B、元素類型鏈棧與順序棧相比，比較明顯的優(yōu)點(diǎn)是A、插入操作更加方便C不會(huì)出現(xiàn)下溢的情況以下數(shù)據(jù)結(jié)構(gòu)中哪一個(gè)是非線性結(jié)構(gòu)A.隊(duì)列B.棧C、邏輯結(jié)構(gòu)D、插入、刪除元素的位置Do日刪除操作更加方便H不會(huì)出現(xiàn)上溢的情況DoC.線性表D.二

6、叉樹(shù)(14)(15)(16)結(jié)點(diǎn)(17)(18)(19)(20)(21)(22)(23)若已知一個(gè)棧的入棧序列是1,2,3,，n,其輸出序列為p1,p2,p3,，pn,若p1=n,則pi為A.iB.B.n=iC.n-i+1D.不確定(24)當(dāng)利用大小為N的一維數(shù)組順序存儲(chǔ)一個(gè)棧時(shí)，假定用top=N表示?？眨瑒t向這個(gè)棧插入一個(gè)元素時(shí)，首先應(yīng)執(zhí)行語(yǔ)句修改top指針。A.top+B.top-C.top=0D.top(25)A.AB.BC.CD.D4個(gè)元素進(jìn)S棧的順序是A,B,C,D,經(jīng)運(yùn)算POP(S)后，棧頂元素是C(26)A.edcbaB.decbaC.dceabD.abcde(27)是設(shè)輸入序列

7、是1、2、3、n,經(jīng)過(guò)棧的作用后輸出序列的第一個(gè)元素是n,則輸出序列中第i個(gè)輸出元素A.n-iB. n-1-iC. n+1-iD.不能確定(28)字符A、B、字符串？C、D依次進(jìn)入一個(gè)棧，按出棧的先后順序組成不同的字符串，至多可以組成B個(gè)不同的A.15B.14C.16D.21(29)設(shè)指針變量top指向當(dāng)前鏈?zhǔn)綏５臈ｍ?，則刪除棧頂元素的操作序列為A. top=top+1;B. top=top-1;C.top->next=top;D.top=top->next;一個(gè)棧的輸入序列是a,b,c,d,e,則棧的不可能的輸出序列是(30)設(shè)棧S和隊(duì)列Q的初始狀態(tài)為空，元素E1、E2、E3、E

8、4、E5和E6依次通過(guò)棧S,一個(gè)元素出棧后即進(jìn)入隊(duì)列Q,若6個(gè)元素出列的順序?yàn)镋2、E4、E3、E6、E5和E1,則棧S的容量至少應(yīng)該是A.6B.4C.3D.2(31)若用一個(gè)大小為再加入兩個(gè)元素后，6的數(shù)組來(lái)實(shí)現(xiàn)循環(huán)隊(duì)列，且當(dāng)前rear和front的值分別為0和3。當(dāng)從隊(duì)列中刪除一個(gè)元素,rear和front的值分別為A. 1和5B. 2和4C. 4和2D. 5和1(32)設(shè)順序循環(huán)隊(duì)列Q0:M-1的頭指針和尾指針?lè)謩e為F和R,頭指針F總是指向隊(duì)頭元素的前一位置，尾指針R總是指向隊(duì)尾元素的當(dāng)前位置，則該循環(huán)隊(duì)列中的元素個(gè)數(shù)為A.R-FB.F-RC.(R-F+M)%MD.(F-R+M)%M(3

9、3)設(shè)指針變量front表示鏈?zhǔn)疥?duì)列的隊(duì)頭指針，指針變量rear表示鏈?zhǔn)疥?duì)列的隊(duì)尾指針，指針變量s指向?qū)⒁腙?duì)列的結(jié)點(diǎn)X,則入隊(duì)列的操作序列為A.front->next=s;front=s;C.rear->next=s;rear=s;(34)如下陳述中正確的是AA.串是一種特殊的線性表C.串中元素只能是字母(35)下列關(guān)于串的敘述中，正確的是A.串長(zhǎng)度是指串中不同字符的個(gè)數(shù)COB.s->next=rear;rear=s;D.s->next=front;front=s;B.串的長(zhǎng)度必須大于零D.空串就是空白串D。B.串是n個(gè)字母的有限序列C.如果兩個(gè)串含有相同的字符，則它

10、們相等D.只有當(dāng)兩個(gè)串的長(zhǎng)度相等，并且各個(gè)對(duì)應(yīng)位置的字符都相符時(shí)才相等(36)字符串的長(zhǎng)度是指C。A.串中不同字符的個(gè)數(shù)B.串中不同字母的個(gè)數(shù)C.串中所含字符的個(gè)數(shù)D.串中不同數(shù)字的個(gè)數(shù)(37)兩個(gè)字符串相等的充要條件是C。A.兩個(gè)字符串的長(zhǎng)度相等B.兩個(gè)字符串中對(duì)應(yīng)位置上的字符相等C.同時(shí)具備(A)和(B)兩個(gè)條件D.以上答案都不對(duì)(38)串是一種特殊的線性表，其特殊性體現(xiàn)在B。A.可以順序存儲(chǔ)B.數(shù)據(jù)元素是一個(gè)字符C.可以鏈接存儲(chǔ)D.數(shù)據(jù)元素可以是多個(gè)字符(39)設(shè)有兩個(gè)串p和q,求q在p中首次出現(xiàn)的位置的運(yùn)算稱作B。A.連接B.模式匹配C.求子串D.求串長(zhǎng)(40)設(shè)串sI="A

11、BCDEFG",s2="PQRST",函數(shù)con(x,y)返回x和y串的連接串，subs(s,i,j)返回串s的從序號(hào)i的字符開(kāi)始白j個(gè)字符組成的子串，len(s)返回串s的長(zhǎng)度，貝Ucon(subs(s1,2,1en(s2),subs(sl,len(s2),2)的結(jié)果串是_DA.BCDEFB.BCDEFGC.BCPQRSTD.BCDEFEF(41) 函數(shù)substr("DATASTRUCTURE"，5,9)的返回值為A。A."STRUCTUREB."DATAC."ASTRUCTURD."DATASTRU

12、CTURE(42) 設(shè)串S="IAMATEACHER!”，其長(zhǎng)度是D。A.16B.11C.14D.15(43)假定在一棵二叉樹(shù)中，雙分支結(jié)點(diǎn)數(shù)為15個(gè)，單分支結(jié)點(diǎn)數(shù)為32個(gè)，則葉子結(jié)點(diǎn)數(shù)為B。A.15B.16C.17D.47(44)假定一棵二叉樹(shù)的結(jié)點(diǎn)數(shù)為18個(gè)，則它的最小高度B。A.4B.5C.6D.18(45)在一棵二叉樹(shù)中第五層上的結(jié)點(diǎn)數(shù)最多為C。A.8B.15C.16D.32(46)在一棵具有五層的滿二叉樹(shù)中，結(jié)點(diǎn)總數(shù)為A。A.31B.32C.33D.16(47)已知8個(gè)數(shù)據(jù)元素為(34、76、45、18、26、54、92、65),按照依次插入結(jié)點(diǎn)的方法生成一棵二叉排序樹(shù)后，

13、最后兩層上的結(jié)點(diǎn)總數(shù)為B。A.1B.2C.D.4(48)由分別帶權(quán)為9、2、5、7的四個(gè)葉子結(jié)點(diǎn)構(gòu)造一棵哈夫曼樹(shù)，該樹(shù)的帶權(quán)路徑長(zhǎng)度為C。A.23B.37C.44D.46(49)在樹(shù)中除根結(jié)點(diǎn)外，其余結(jié)點(diǎn)分成m(mR0)個(gè)A的集合T1,T2,T3.Tm,每個(gè)集合又都是樹(shù)，此時(shí)結(jié)點(diǎn)T稱為T(mén)i的父結(jié)點(diǎn)，Ti稱為T(mén)的子結(jié)點(diǎn)(1Wiwm)。A.互不相交B.可以相交C.葉結(jié)點(diǎn)可以相交D.樹(shù)枝結(jié)點(diǎn)可以相交(50)如果結(jié)點(diǎn)A有三個(gè)兄弟，而且B是A的雙親，則B的出度是B。A.3B.4C.5D.1(51)在一個(gè)有向圖中，所有頂點(diǎn)的入度之和等于所有頂點(diǎn)的出度之和的B倍。A.1/2B.1C.2D.4(52)具有n個(gè)

14、頂點(diǎn)的無(wú)向完全圖，邊的總數(shù)為D條。A.n-1B.nC.n+1D.n*(n-1)/2(53)在無(wú)向圖G的鄰接矩陣A中，若Ai,j等于1,則Aj,i等于C。A.i+jB.i-jC.1D.0(54)圖的深度優(yōu)先或廣度優(yōu)先遍歷的空間復(fù)雜性均為A。(訪問(wèn)標(biāo)志位數(shù)組空間)A.O(n)B.O(e)C.O(n-e)D.O(n+e)(55)請(qǐng)指出在順序表2、5、7、10、14、15、18、23、35、41、52中，用折半法查找關(guān)鍵碼12需做C次關(guān)鍵碼比較。A.2B.3C.4D.5(56)對(duì)線性表進(jìn)行折半查找時(shí)，必須要求線性表C。A.以順序方式存儲(chǔ)B.以鏈接方式存儲(chǔ)C.以順序方式存儲(chǔ)，且結(jié)點(diǎn)按關(guān)鍵字有序排列D.以

15、鏈接方式存儲(chǔ)，且結(jié)點(diǎn)按關(guān)鍵字有序排列(57)設(shè)二叉排序樹(shù)中有n個(gè)結(jié)點(diǎn)，則在二叉排序樹(shù)的平均查找長(zhǎng)度為B。A.O(1)B.O(log2n)C.O(n)D.O(n2)(58)依次插入序列(50,72,43,85,75,20,35,45,65,30)后建立的二叉搜索樹(shù)中，查找元素35要進(jìn)行_A元素間的比較。A.4次B.5次C.7次D.10次(59)設(shè)散列表中有m個(gè)存儲(chǔ)單元，散列函數(shù)H(key尸key%p,則p最好選擇BA.小于等于m的最大奇數(shù)B.小于等于m的最大素?cái)?shù)C.小于等于m的最大偶數(shù)D.小于等于m的最大合數(shù)(60)D是HASH查找的沖突處理方法。A.求余法B.平方取中法C.二分法D.開(kāi)放地址法

16、(61)當(dāng)a的值較小時(shí)，散列存儲(chǔ)通常比其他存儲(chǔ)方式具有B的查找速度。A.較慢B.較快C.相同D.不確定(62)對(duì)線性表進(jìn)行折半查找最方便的存儲(chǔ)結(jié)構(gòu)是B。A.順序表B.有序的順序表C.鏈表D.有序的鏈表(63)如果要求一個(gè)線性表既能較快的查找，又能適應(yīng)動(dòng)態(tài)變化的要求，可以采用D查找方法。A.分塊B.順序C.折半D.散列(64)散列函數(shù)有一個(gè)共同性質(zhì)，即函數(shù)值應(yīng)按C取其值域的每一個(gè)值。A.最大概率B.最小概率C.同等概率D.平均概率(65)下述排序算法中，穩(wěn)定的是B。A.直接選擇排序B.直接插入排序C.快速排序D.堆排序(66)下列排序算法中，A需要的輔助存儲(chǔ)空間最大。A.快速排序B.插入排序C.

17、希爾排序D.基數(shù)排序(67)下列各種排序算法中平均時(shí)間復(fù)雜度為O(n2)是_D。A.快速排序B.堆排序C.歸并排序D.冒泡排序(68)在基于關(guān)鍵碼比較白排序算法中，C算法在最壞情況下，關(guān)鍵碼比較次數(shù)不高于O(nlog2n)。A,起泡排序B,直接插入排序C.二路歸并排序D.快速排序(69) 一組記錄為46,79,56,38,84,40,則采用冒泡排序法按升序排列時(shí)第一趟排序結(jié)果是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)每次從無(wú)序表中取出一個(gè)元素，把它插入到有序表中的適當(dāng)位置

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

19、,P,A,M,Q,R,S,Y,X是采用C方法對(duì)初始序列進(jìn)行第一趟掃描的結(jié)果。A.直接插入排序B.二路歸并排序C.以第一元素為分界元素的快速排序D.基數(shù)排序(75)在待排序文件已基本有序的前提下，下述排序方法中效率最高的是_C。A.直接插入排序B.直接選擇排序C.快速排序D.歸并排序(76)若需在O(nlog2n)的時(shí)間內(nèi)完成對(duì)數(shù)組的排序，且要求排序是穩(wěn)定的，則可選排序方法是C。A.快速排序B.堆排序C.歸并排序D.直接插入排序(77)將兩個(gè)各有n個(gè)元素的有序表歸并成一個(gè)有序表，其最少的比較次數(shù)是B。A.nB.2n-1C.2nD.n-1(78)下列排序算法中，C算法可能會(huì)出現(xiàn)下面情況：初始數(shù)據(jù)有

20、序時(shí)，花費(fèi)的間反而最多。A.堆排序B.冒泡排序C.快速排序D.SHELL排序二、填空題。(每空1分，共10分)(1)數(shù)據(jù)結(jié)構(gòu)是一門(mén)研究非數(shù)值計(jì)算的程序設(shè)計(jì)問(wèn)題中計(jì)算機(jī)的數(shù)據(jù)以及它們之間的關(guān)系和運(yùn)算等的學(xué)科。(2)數(shù)據(jù)結(jié)構(gòu)包括數(shù)據(jù)的邏輯結(jié)構(gòu)結(jié)構(gòu)和物理結(jié)構(gòu)結(jié)構(gòu)。(3)數(shù)據(jù)結(jié)構(gòu)從邏輯上劃分為三種基本類型：線性數(shù)據(jù)結(jié)構(gòu)、樹(shù)型Z構(gòu)和圖結(jié)構(gòu)O(4)數(shù)據(jù)的物理Z構(gòu)被分為順序存儲(chǔ)、鏈?zhǔn)酱鎯?chǔ)、索引存儲(chǔ)和散列表(Hash)存儲(chǔ)四種。(5) 一種抽象數(shù)據(jù)類型包括變量的取值范圍和操作的類別兩個(gè)部分。(6)數(shù)據(jù)的邏輯結(jié)構(gòu)是指數(shù)據(jù)元素間的邏輯關(guān)系，數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是指數(shù)據(jù)元素存儲(chǔ)方式或者數(shù)據(jù)元素的物理關(guān)系。(7)數(shù)據(jù)結(jié)構(gòu)是

21、指數(shù)據(jù)及其相互之間的關(guān)系。當(dāng)結(jié)點(diǎn)之間存在M對(duì)N(M:N)的聯(lián)系時(shí)，稱這種結(jié)構(gòu)為網(wǎng)狀結(jié)構(gòu)。當(dāng)結(jié)點(diǎn)之間存在1對(duì)N(1:N)的聯(lián)系時(shí)，稱這種結(jié)構(gòu)為樹(shù)結(jié)構(gòu)。(8)對(duì)算法從時(shí)間和空間兩方面進(jìn)行度量，分別稱為空間復(fù)雜度和時(shí)間復(fù)雜度分析。(9)算法的效率可分為空間效率和時(shí)間效率。(10) for(i=1,t=1,s=0;i<=n;i+)t=t*i;s=s+t;的時(shí)間復(fù)雜度為O(n)。(11)線性表是n個(gè)元素的有限序列。(12)線性表的存儲(chǔ)結(jié)構(gòu)有順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)。(13)設(shè)線性表中有n個(gè)數(shù)據(jù)元素，則在順序存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)順序查找的平均時(shí)間復(fù)雜度為O(n)，在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上實(shí)現(xiàn)順序查找的平均時(shí)間復(fù)雜度為O

22、(n)。(14)設(shè)順序線性表中有n個(gè)數(shù)據(jù)元素，則第i個(gè)位置上插入一個(gè)數(shù)據(jù)元素需要移動(dòng)表中n-i+1個(gè)數(shù)據(jù)元素；刪除第i個(gè)位置上的數(shù)據(jù)元素需要移動(dòng)表中n-i個(gè)元素。(15)若頻繁地對(duì)線性表進(jìn)行插入與刪除操作，該線性表應(yīng)采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。(16)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中的結(jié)點(diǎn)包含數(shù)據(jù)域和指針域。(17)對(duì)于一個(gè)長(zhǎng)度為n的單鏈存儲(chǔ)的線性表，在表頭插入元素的時(shí)間復(fù)雜度為0(1)，在表尾插入元素的時(shí)間復(fù)雜度為O(n)。(18)棧的插入和刪除只能在棧的棧頂進(jìn)行，后進(jìn)棧的元素必定先出棧，所以又把棧稱為FILO表；隊(duì)列的插入和刪除運(yùn)算分別在隊(duì)列的兩端進(jìn)行，先進(jìn)隊(duì)列的元素必定先出隊(duì)列，所以又把隊(duì)列稱為FIFO表。(19)

23、 s="Iamaman”長(zhǎng)度為10。(20) s1="hello",s2="boy",s1,s2連接后為：helloboy。(21) s="thisisthemainstring",sub="string”,strindex(s,sub)是：13。(22) inta1010,已知a=1000,sizeof(int)=2,求a33地址：1066。(23)設(shè)有兩個(gè)串p和q,求q在p中首次出現(xiàn)的位置的運(yùn)算稱為模式匹配。(24)在樹(shù)型結(jié)構(gòu)中，樹(shù)根結(jié)點(diǎn)沒(méi)有前趨結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)有且僅有一個(gè)前驅(qū)結(jié)點(diǎn)；樹(shù)葉結(jié)點(diǎn)沒(méi)有后繼結(jié)點(diǎn)，其余

24、每個(gè)結(jié)點(diǎn)的后繼結(jié)點(diǎn)數(shù)不受限制。(25)在一棵二叉樹(shù)中，度為0的結(jié)點(diǎn)的個(gè)數(shù)為n0,度為2的結(jié)點(diǎn)的個(gè)數(shù)為n2,則：n0=n2+1。(26)由分別帶權(quán)為3,9,6,2,5的共五個(gè)葉子結(jié)點(diǎn)構(gòu)成一棵哈夫曼樹(shù)，則帶權(quán)路徑長(zhǎng)度為55。(27)在圖G的鄰接表表示中，每個(gè)頂點(diǎn)鄰接表中所含的結(jié)點(diǎn)數(shù)，對(duì)于無(wú)向圖來(lái)說(shuō)等于該頂點(diǎn)的度數(shù),對(duì)于有向圖來(lái)說(shuō)等于該頂點(diǎn)的出度數(shù)。(28)假定一個(gè)圖具有n個(gè)頂點(diǎn)和e條邊，則采用鄰接矩陣表示的空間復(fù)雜性為O(n2),采用鄰接表表示的空間復(fù)雜性為O(n+e)。(29)對(duì)于長(zhǎng)度為n的線性表，若進(jìn)行順序查找，則時(shí)間復(fù)雜度為O(n);若采用折半法查找，則時(shí)間復(fù)雜度為O(log2n)。(30)

25、假設(shè)在有序線性表A1.20上進(jìn)行折半查找，則比較一次查找成功的結(jié)點(diǎn)數(shù)為1,則比較二次查找成功的結(jié)點(diǎn)數(shù)為2,則比較三次查找成功的結(jié)點(diǎn)數(shù)為4,則比較四次查找成功的結(jié)點(diǎn)數(shù)為8,則比較五次查找成功的結(jié)點(diǎn)數(shù)為5,平均查找長(zhǎng)度為log沏+1)-1。(31)在一棵二叉排序樹(shù)中，每個(gè)分支結(jié)點(diǎn)白左子樹(shù)上所有結(jié)點(diǎn)的值一定小于該結(jié)點(diǎn)的值，右子樹(shù)上所有結(jié)點(diǎn)的值一定大于該結(jié)點(diǎn)的值。(32)對(duì)一棵二叉排序樹(shù)進(jìn)行中序遍歷時(shí)，得到的結(jié)點(diǎn)序列是一個(gè)增序序列。(33)對(duì)于線T表(70,34,55,23,65,41,20)進(jìn)行散列存儲(chǔ)時(shí)，若選用H(K)=K%7作為散列函數(shù)，則散列地址為0的元素是70,散列地址為6的是34,20,5

26、5。(34)在線性表的散列存儲(chǔ)中，裝填因子a又稱為裝填系數(shù)，若用m表示散列表的長(zhǎng)度，n表示待散列存儲(chǔ)的元素的個(gè)數(shù)，則a等于n/m。(35)散列表中解決沖突的兩種方法是開(kāi)放地址法和鏈地址法。(36)在散列存儲(chǔ)中，裝填因子a的值越大，則產(chǎn)生沖突的可能性就越大;a的值越小，則產(chǎn)生沖突的可能性就越小。(37)散列法存儲(chǔ)的基本思想是由關(guān)鍵碼直接決定數(shù)據(jù)的存儲(chǔ)地址。(38)構(gòu)造哈希函數(shù)的方法有(寫(xiě)二個(gè))直接定址法，數(shù)字分析法，平方取中法，折疊法，除留余數(shù)法，隨機(jī)數(shù)法。(39)在分塊查找中首先查找索引,然后再查找相應(yīng)的塊。(40)散列表的查找效率主要取決于散列表造表時(shí)選擇的哈希函數(shù)和裝填因子。(41)對(duì)兩棵

27、具有相同關(guān)鍵字集合而形狀不同的二叉排序樹(shù)，中序遍歷它們得到的序列的順序是一樣的。(42)當(dāng)待排序的記錄數(shù)較大，排序碼較隨機(jī)且對(duì)穩(wěn)定性不作要求時(shí)，宜采用快速排序；當(dāng)待排序的記錄數(shù)較大，存儲(chǔ)空間允許且要求排序是穩(wěn)定時(shí)，宜采用歸并排序。(43)在堆排序的過(guò)程中，對(duì)任一分支結(jié)點(diǎn)進(jìn)行篩運(yùn)算的時(shí)間復(fù)雜度為O(log2n),整個(gè)堆排序過(guò)程的時(shí)間復(fù)雜度為O(nlog2n)。(44)當(dāng)向一個(gè)大根堆插入一個(gè)具有最大值的元素時(shí)，需要逐層向上調(diào)整，直到被調(diào)整到根結(jié)點(diǎn)位置為止。(45)對(duì)一組初始關(guān)鍵字序列(40,50,95,20,15,70,60,45,10)進(jìn)行冒泡排序，則第一趟需要進(jìn)行相鄰記錄的比較的次數(shù)為8,在整

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

29、復(fù)雜度是O(nlog2n)。(51)對(duì)于n個(gè)記錄的集合進(jìn)行歸并排序，所需的附加空間消耗是O(n)。(52)設(shè)表中元素的初始狀態(tài)是按鍵值遞增的，分別用堆排序、快速排序、冒泡排序和歸并排序方法對(duì)其仍按遞增順序進(jìn)行排序，則冒泡排序最省時(shí)間，快速排序最費(fèi)時(shí)間。三、判斷題。(每小題1分，共10分)(x)1.數(shù)據(jù)元素是數(shù)據(jù)的最小單位。(X)2.數(shù)據(jù)項(xiàng)是數(shù)據(jù)的基本單位。(，)3.順序存儲(chǔ)的線性表可以隨機(jī)存取。(V)4.線性表中的元素可以是各種各樣的，但同一線性表中的數(shù)據(jù)元素具有相同的特性，因此，是屬于同一數(shù)據(jù)對(duì)象。(X)5.在單鏈表中，任何兩個(gè)元素的存儲(chǔ)位置之間都有固定的聯(lián)系，因?yàn)榭梢詮念^結(jié)點(diǎn)查找任何一個(gè)元

30、素。(X)6.在單鏈表中，要取得某個(gè)元素，只要知道該元素的指針即可，因此，單鏈表是隨機(jī)存取的存儲(chǔ)結(jié)構(gòu)。(X)7.鏈表的每個(gè)結(jié)點(diǎn)中，都恰好包含一個(gè)指針。(X)8.數(shù)組是同類型值的集合。(V)9.使用三元組表示稀疏矩陣的元素，有時(shí)并不能節(jié)省存儲(chǔ)時(shí)間。(V)10.線性表可以看成是廣義表的特例，如果廣義表中的每個(gè)元素都是原子，則廣義表便成為線性表。(V)11.由樹(shù)轉(zhuǎn)換成二叉樹(shù)，其根結(jié)點(diǎn)的右子樹(shù)總是空的。(x)12.后序遍歷樹(shù)和中序遍歷與該樹(shù)對(duì)應(yīng)的二叉樹(shù)，其結(jié)果不同。(X)13.若有一個(gè)結(jié)點(diǎn)是某二叉樹(shù)子樹(shù)的中序遍歷序列中的最后一個(gè)結(jié)點(diǎn)，則它必是該子樹(shù)的前序遍歷序列中的最后一個(gè)結(jié)點(diǎn)。(V)14.若一個(gè)樹(shù)葉

31、是某子樹(shù)的中序遍歷序列中的最后一個(gè)結(jié)點(diǎn)，則它必是該子樹(shù)的前序遍歷序列中的最后一個(gè)結(jié)點(diǎn)。(x)15.已知二叉樹(shù)的前序遍歷和后序遍歷序列并不能唯一地確定這棵樹(shù)，因?yàn)椴恢罉?shù)的根結(jié)點(diǎn)是哪一個(gè)。(x)16.在哈夫曼編碼中，當(dāng)兩個(gè)字符出現(xiàn)的頻率相同時(shí)，其編碼也相同，對(duì)于這種情況應(yīng)作特殊處理。(V)17.有回路的圖不能進(jìn)行拓?fù)渑判颉?X)18.連通分量是無(wú)向圖中的極小連通子圖。(V)19.散列法存儲(chǔ)的基本思想是由關(guān)鍵碼的值決定數(shù)據(jù)的存儲(chǔ)地址。(V)20.散列表的查找效率取決于散列表造表時(shí)選取的散列函數(shù)和處理沖突的方法。(V)21.m階B-樹(shù)每一個(gè)結(jié)點(diǎn)的子樹(shù)個(gè)數(shù)都小于或等于m。(V)22.中序遍歷二叉排序樹(shù)

32、的結(jié)點(diǎn)就可以得到排好序的結(jié)點(diǎn)序列。(V)23.在二叉排序樹(shù)上插入新的結(jié)點(diǎn)時(shí)，不必移動(dòng)其它結(jié)點(diǎn)，僅需改動(dòng)某個(gè)結(jié)點(diǎn)的指針，由空變?yōu)榉强占纯伞?V)24.當(dāng)待排序的元素很多時(shí)，為了交換元素的位置，移動(dòng)元素要占用較多的時(shí)間，這是影響時(shí)間復(fù)雜性的主要因素。(V)25.對(duì)于n個(gè)記錄的集合進(jìn)行快速排序，所需要的平均時(shí)間是O(nlog2n)。(V)26.對(duì)于n個(gè)記錄的集合進(jìn)行歸并排序，所需要的平均時(shí)間是O(nlog2n)。(V)27.堆中所有非終端結(jié)點(diǎn)的值均小于或等于(大于或等于)左右子樹(shù)的值。(X)28.磁盤(pán)上的順序文件中插入新的記錄時(shí)，必須復(fù)制整個(gè)文件。(X)29.在索引順序文件中插入新的記錄時(shí)，必須復(fù)制

33、整個(gè)文件。(X)30.索引順序文件是一種特殊的順序文件，因此通常存放在磁帶上。四、簡(jiǎn)答題。(共6小題，每小題約5分，共32分)1 .簡(jiǎn)述下列術(shù)語(yǔ)：數(shù)據(jù)、數(shù)據(jù)項(xiàng)、數(shù)據(jù)元素、數(shù)據(jù)邏輯結(jié)構(gòu)、數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)、數(shù)據(jù)類型和算法。數(shù)據(jù)：數(shù)據(jù)是信息的載體，是計(jì)算機(jī)程序加工和處理的對(duì)象，包括數(shù)值數(shù)據(jù)和非數(shù)值數(shù)據(jù)。數(shù)據(jù)項(xiàng)：數(shù)據(jù)項(xiàng)指不可分割的、具有獨(dú)立意義的最小數(shù)據(jù)單位，數(shù)據(jù)項(xiàng)有時(shí)也稱為字段或域。數(shù)據(jù)元素：數(shù)據(jù)元素是數(shù)據(jù)的基本單位，在計(jì)算機(jī)程序中通常作為一個(gè)整體進(jìn)行考慮和處理，一個(gè)數(shù)據(jù)元素可由若干個(gè)數(shù)據(jù)項(xiàng)組成。數(shù)據(jù)邏輯結(jié)構(gòu)：數(shù)據(jù)的邏輯結(jié)構(gòu)就是指數(shù)據(jù)元素間的關(guān)系。數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)：數(shù)據(jù)的物理結(jié)構(gòu)表示數(shù)據(jù)元素的存儲(chǔ)方式或者數(shù)

34、據(jù)元素的物理關(guān)系。數(shù)據(jù)類型：是指變量的取值范圍和所能夠進(jìn)行的操作的總和。算法：是對(duì)特定問(wèn)題求解步驟的一種描述，是指令的有限序列。2 .簡(jiǎn)述棧和線性表的區(qū)別。答：一般線性表使用數(shù)組來(lái)表示的。線性表一般有插入、刪除、讀取等對(duì)于任意元素的操作。而棧只是一種特殊的線性表。棧只能在線性表的一端插入(稱為入棧，push)或者讀取棧頂元素或者稱為“彈出、出棧"(pop)。3 .簡(jiǎn)述棧和隊(duì)列這兩種數(shù)據(jù)結(jié)構(gòu)的相同點(diǎn)和不同點(diǎn)。答：相同點(diǎn)：棧和隊(duì)列都是特殊的線性表，只在端點(diǎn)處進(jìn)行插入，刪除操作。不同點(diǎn)：棧只在一端(棧頂)進(jìn)行插入，刪除操作；隊(duì)列在一端(top)刪除，一端(rear)插入。4 .如果進(jìn)棧的元

35、素序列為A,B,C,D,則可能得到的出棧序列有多少種？寫(xiě)出全部的可能序列。答：可能序歹U有14種：ABCD;ACBD;ACDB;ABDC;ADCB;BACD;BADC;BCAD;BCDA;BDCA;CBAD;CBDA;CDBA;DCBA5 .如果進(jìn)棧的元素序列為1,2,3,4,5,6,能否得到4,3,5,6,1,2和1,3,5,4,2,6的出棧序列？并說(shuō)明為什么不能得到或如何得到。答：不能得到4,3,5,6,1,2,最先出棧的是4,則按321的方式出，不可能得到1在2前的序列，可以得到1,3,5,4,2,6,按如下方式進(jìn)行push(1),pop(),push(2),push(3),pop(),

36、push(4),push(5),pop(),pop(),pop(),push(6),pop()。6 .設(shè)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

37、,StrLength(t)=4,SubStr(s,8,7)="STUDENT,SubStr(t,2,1)="O',StrIndex(s,"A")=3,StrIndex(s,t)=0,StrRep(s'STUDENTq尸"IAMAWORKER”，7 .簡(jiǎn)述下列每對(duì)術(shù)語(yǔ)的區(qū)別：空串和空格串；串變量和串常量；主串和子串；串變量的名字和串變量的值。答：空串：不含任何字符；空格串：所含字符都是空格。串變量和串常量：串常量在程序的執(zhí)行過(guò)程中只能引用不能改變；串變量的值在程序執(zhí)行過(guò)程中是可以改變和重新賦值的。主串與子串：子串是主串的一個(gè)子集。

38、串變量的名字與串變量的值：串變量的名字表示串值的標(biāo)識(shí)符。8 .設(shè)有二維數(shù)組A(6X8),每個(gè)元素占6個(gè)字節(jié)存儲(chǔ)，順序存放，A的起地址為1000,計(jì)算：數(shù)組A的體積(即存儲(chǔ)量)；(2)數(shù)組的最后一個(gè)元素A的起地址；(3)按行優(yōu)先存放時(shí)，元素A1,4的起地址；(4)按列優(yōu)先存放時(shí)，元素A4,7的起地址。6*8*6=288(2)1000+47*6=12821000+(8+4)*8=1096(4)1000+(6*7+4)*8=13689 .分別畫(huà)出含三個(gè)結(jié)點(diǎn)的無(wú)序樹(shù)與二叉樹(shù)的所有不同形態(tài)。答：無(wú)序樹(shù)形態(tài)如下：二叉樹(shù)形態(tài)如下：10 .分別寫(xiě)出圖1中所示二叉樹(shù)的先序遍歷、中序遍歷、后序遍歷的結(jié)點(diǎn)訪問(wèn)序列。

39、AiBCD'EFGHIJ圖1答：先序遍歷序列：ABDEHICFJG中序遍歷序列：DBHEIAFJCG后序遍歷序列：DHIEBJFGCA11 .試找出分別滿足下列條件的所有二叉樹(shù)。(1) 先序序列與中序序列相同。(2) 后序序列與中序序列相同。(3) 先序序列與后序序列相同。答：(1)先序序列和中序序列相同：空樹(shù)或缺左子樹(shù)的單支樹(shù)；(2)后序序列和中序序列相同：空樹(shù)或缺右子樹(shù)的單支樹(shù)；(3)先序序列和后序序列相同：空樹(shù)或只有根結(jié)點(diǎn)的二叉樹(shù)。12.已知一棵二叉樹(shù)的中序序列和后序序列分別為BDCEAFHG1DECBHGFA試畫(huà)出這棵二叉樹(shù)。答：這棵二叉樹(shù)為：13 .分別寫(xiě)出圖2中所示二叉樹(shù)的

40、先序遍歷、中序遍歷、后序遍歷的結(jié)點(diǎn)訪問(wèn)序列。HHb1c圖2答：先序遍歷序列:ABDGCEHF中序遍歷序列：DGBAEHCF后序遍歷序列：GDBHEFCA14 .給定權(quán)值(7,18,3,32,5,26,12,8),構(gòu)造的哈夫曼樹(shù)。答：哈夫曼樹(shù)為：111466515 .假設(shè)用于通信白電文僅由8個(gè)字母組成，字母在電文中出現(xiàn)的頻率分別為7,19,2,6,32,3,21,10，試為這8個(gè)設(shè)計(jì)哈夫曼編碼。答：哈夫曼樹(shù)為：111在上述哈夫曼樹(shù)的每個(gè)左分支上標(biāo)以0,右分支上標(biāo)以1,并設(shè)這8個(gè)字母分別為A、B、GD、E、F、G和H,則它們的哈夫曼樹(shù)為分別為：A:0000B:10C:00110D:0010E:01

41、F:00111G:11H:000116 .畫(huà)出無(wú)向圖G1的鄰接矩陣和鄰接表示意圖，并寫(xiě)出每個(gè)頂點(diǎn)的度。答：（1）鄰接矩陣：0111010011M=100011100101110(2)鄰接鏈表:(3)每個(gè)頂點(diǎn)的度：頂點(diǎn)度V13V23V32V43V53答：（1）鄰接鏈表:鄰接表和逆鄰接表示意圖，并寫(xiě)出每個(gè)頂點(diǎn)的入度和出度O(3)頂點(diǎn)入度V130V222V312V413V521V623出度18 .對(duì)應(yīng)圖G3,寫(xiě)出從v1出必的深度優(yōu)先遍歷序列和廣度優(yōu)先遍歷序列各三個(gè)。答：深度優(yōu)先查找遍歷序歹U:V1V2V3V4V5;V1V3V5V4V2;V1V4V3V5V2廣度優(yōu)先查找遍歷序歹U:V1V2V3V4V5

42、;V1V3V2V4V5;V1V4V3V2V519 .何謂二叉排序樹(shù)？答：一棵二叉排序樹(shù)(又稱二叉查找樹(shù))或者是一棵空樹(shù)，或者是一棵同時(shí)滿足下列條件的二叉樹(shù):(1) 若它的左子樹(shù)不空，則左子樹(shù)上所有結(jié)點(diǎn)的鍵值均小于它根結(jié)點(diǎn)鍵值。(2) 若它的右子樹(shù)不空，則右子樹(shù)上所有結(jié)點(diǎn)的鍵值均大于它根結(jié)點(diǎn)鍵值。(3) 它的左、右子樹(shù)也分別為二叉排序樹(shù)。20 .順序查找時(shí)間為O(n),二分查找時(shí)間為O(log2n),散列查找時(shí)間為0(1),為什么有高效率的查找方法而不放棄低效率的方法？答：衡量算法的標(biāo)準(zhǔn)有很多，時(shí)間復(fù)雜度只是其中之一。盡管有些算法時(shí)間性能很好，但是其他方面可能就存在著不足。比如散列查找的時(shí)間性能很優(yōu)越，但是需要關(guān)注如何合理地構(gòu)造散列函數(shù)問(wèn)題，而且總存在著沖突等現(xiàn)象，為了解決沖突，還得采用其他方法。二分查找也是有代價(jià)的，因?yàn)槭孪缺仨殞?duì)整個(gè)查找區(qū)間進(jìn)行排序，而排序也是費(fèi)時(shí)的，所以常應(yīng)用于頻繁查找的場(chǎng)合。對(duì)于順序查找，盡管效率不高，但卻比較簡(jiǎn)單，常用于查找范圍較小或偶而進(jìn)行查找的情況。21 .簡(jiǎn)述多重散列法解決沖突的基本思想。答：此法要求設(shè)立多個(gè)散列函數(shù)H,i=1,，ko當(dāng)給定值K與閉散列表中的某個(gè)鍵值是相對(duì)于某個(gè)散列函數(shù)H的同義詞因而發(fā)生沖突時(shí)，繼續(xù)計(jì)算該給