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

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

2、=r, r=<l, 2>, <2, 3>, <3, 4>, <4, 1>,則數(shù)據(jù)結(jié)構(gòu) A 是 AoA.線性結(jié)構(gòu) C.圖型結(jié)構(gòu)(7)數(shù)據(jù)在計(jì)算機(jī)存儲(chǔ)器內(nèi)表示時(shí)，物理地址與邏輯地址相同并且是連續(xù)的，稱(chēng)之為C A.存儲(chǔ)結(jié)構(gòu)C順序存儲(chǔ)結(jié)構(gòu)D：齧蔓薯魯結(jié)構(gòu)(8)在數(shù)據(jù)結(jié)構(gòu)的討論中把數(shù)據(jù)結(jié)構(gòu)從邏輯上分為AA.內(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.健壯性和可讀性C.正確性 (10)算法分析的兩個(gè)方面是A oA空間復(fù)雜性和時(shí)間復(fù)雜B.正確性和

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

4、空間C. 線性表采用鏈?zhǔn)酱鎯?chǔ)便于插入和刪除操作的實(shí)現(xiàn)D. 線性表釆用順序存儲(chǔ)便于插入和刪除操作的實(shí)現(xiàn)(16)設(shè)指針q指尚車(chē)確奏審給點(diǎn)A,指S向車(chē)確表審結(jié) 點(diǎn)A的后繼番點(diǎn)B,指針s指向被插入的給點(diǎn)X,則在結(jié)點(diǎn) A和結(jié)點(diǎn)B之間插入結(jié)點(diǎn)X的操作序列為 B。(16)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；設(shè)指針變量p指向單鏈表結(jié)點(diǎn)A,則刪除結(jié)點(diǎn)A的后繼佰訐貿(mào)重卩于百B需要的

5、操佐為AoA. p->next=p->next-nextB p=p->nextC p=p->next->nextD p->next二p(18)下列說(shuō)法哪個(gè)正確?A. 堆棧是在兩端操作T先進(jìn)后曲的線性表B. 堆棧是在一端操作、先進(jìn)先出的線性表C. 隊(duì)列是在一端操作、先進(jìn)先出的線性表D. 隊(duì)列是在兩端操作、先進(jìn)先出的線性表(19) 棧和隊(duì)列的共同點(diǎn)是A.都是先進(jìn)后出 先出C.只允許在端點(diǎn)處插入和刪除元素 點(diǎn)(20) 棧與一般線性表的區(qū)別主要在DB.都是先進(jìn)D.沒(méi)有共同A、元素個(gè)數(shù)B、元素輯結(jié)構(gòu)D、插入、刪除元素的位置 鏈棧與順序棧相比，比較明顯的優(yōu)點(diǎn)是D oA、

6、插入操作更加方便B、刪豫操作更加方(21)情況(22)C、不會(huì)出現(xiàn)下溢的情況D、不會(huì)出現(xiàn)上溢的以下數(shù)據(jù)結(jié)構(gòu)中哪一個(gè)是非線性結(jié)構(gòu)DA.隊(duì)列B.棧忑裁性D.二叉樹(shù) 若已知一個(gè)茂的入棧序列是1, 2, 3, n,其輸出序 pl, p2, p3,，pn,若 pl=n,則 pi 為C。AiB. Bn二iCB棧n-i+1D.不確定(24)當(dāng)利甩大小為N的一維數(shù)組順序存儲(chǔ)一個(gè)棧時(shí)，假定用 top=N 空，則向這個(gè)棧插吳一個(gè)兀素虬 音先血抗 行 B語(yǔ)旬穆改topA. top+B. top一一C.top二0D top(25) 4個(gè)元素進(jìn)S棧的順序是A,B,C,D,經(jīng)運(yùn)算POP(S)后,棧頂兀素是 CA. AB

7、BC. CD. D(26) 一個(gè)棧的輸入序列是a，bcd,e，則棧的不可能的輸出序列是 C。A. edcbaBe decbaC.dceabD abode(27) 設(shè)輸入序列是1、2、3、n,經(jīng)過(guò)棧的作用后輸岀c.序列的第一個(gè)元素是m則輸出序列中第i個(gè)輸出元素是 C OA. n-iB n-l-in+l-iD.不能確克(28) 字符A、B、C、D依次進(jìn)入一個(gè)棧，按出棧的先后順序 如成不同的字符串，至多可以組成B_個(gè)不同的字符 串？A. 15B. 14C. 16D. 21(29) 設(shè)指針變量top指向當(dāng)前鏈?zhǔn)綏５臈ｍ?則刪除棧頂元素的操作序列為DoA. top二top+1;B top二top-1;C

8、 top->next二top;D. top二top一>next;(30) 設(shè)棧S和隊(duì)列Q的初始狀態(tài)為空，元素El、E2、E3、E4、E5 JO E6依次通過(guò)棧S, 一個(gè)元素出棧后即進(jìn)入隊(duì)列Q, 若6個(gè)元素出列的順序?yàn)镋2、E4、E3、E6、E5和E1,則 棧S的容量至少應(yīng)該是 CoA. 6B.C. 3D. 2(31) 若用一個(gè)大小為6的數(shù)組來(lái)實(shí)現(xiàn)循環(huán)隊(duì)列，且當(dāng)前rear 和fron值分別為0和3。當(dāng)從隊(duì)列中刪除一個(gè)元素，再加 入兩個(gè)兀素后，rear和front的值分別為 B 。A. 1 和 5B. 2 和 4C2D. 5 和 1(32) 設(shè)順序0： Ml的頭指針和尾指針?lè)謩e為F和R

9、,頭指針F總是指向隊(duì)頭元素的前一位置，尾指針R總 是指向隊(duì)尾元素的當(dāng)前位置，則該循環(huán)隊(duì)列中的元素個(gè)數(shù)為C OA7TFB. F-RC.(R-F+M)%MD. (FR+M)%MB.(33) 設(shè)指針變量fnmt表示鏈?zhǔn)疥?duì)列的隊(duì)頭指針，指針變量 rear表示鏈?zhǔn)疥?duì)列的隊(duì)尾指針，指針變量s指向?qū)⒁腙?duì)列 的結(jié)點(diǎn)X,則入隊(duì)列的操作序列為_(kāi) CD.A. front->next=s； front=s； s->next二rear； rear二s；C rear->next=s； rear=s；s-next二frorrt ； frorrt二s ；(34) 如下陳述中正確的是AA.串是一種特殊的線性

10、表 必須大子零C.串中元素只能是字母 空白串B串的長(zhǎng)度D.空串就是(35)° 串是n個(gè)字母的有限序列B.D：霹蠶霜離驟書(shū)篤濤隊(duì)翱畫(huà)位置的字符都相符時(shí)才相等(36) 字符串的長(zhǎng)度是指_ CoA.串中不同字符的個(gè)數(shù)B.母的個(gè)數(shù)C.串中所含字符的個(gè)數(shù)D.字的個(gè)數(shù)(37) 兩個(gè)字符串相等的充要條件是C_A.兩個(gè)字符串的長(zhǎng)度相等 符串中對(duì)應(yīng)位置上的字符相等C.同時(shí)具備(A)和(B)兩個(gè)條件 案都不對(duì)串中不同字串中不同數(shù)(38)串是一種特殊的線性表,其特殊性體現(xiàn)在了兩個(gè)字D.以上答B(yǎng)A.可以順序存儲(chǔ) 符C.可以鏈接存儲(chǔ)B.數(shù)據(jù)元素是一個(gè)字個(gè)字符D.數(shù)據(jù)元素可以是多(3?)設(shè)有兩個(gè)串P和q，求q在

11、P中首次岀現(xiàn)的位置的運(yùn) 算稱(chēng)作 B。A.連接B.模式匹配串D.求串長(zhǎng)(40) 設(shè)串 sI=nABCDEFG,s2=nPQRST,函數(shù)con(x，y)返回 x和y串的連接串,subs(s,iJ)M回串s的從房號(hào)i的孚特開(kāi)始 的j個(gè)字符組成的子串，len返回串s的長(zhǎng)度，貝！| con(subs(sl,2,len(s2), subs(sl,len(s2), 2)的結(jié)果串是_ Dl¥lC.求子A. BCDEFB. BCDEFGC.BCPQRSTD. BCDEFEF(41) 函數(shù) substr( “DATASTRUCTURE” , 5, 9)的返回 值為 A oA. “STRUCTURE”B.

12、 “DATA”C.“ASTRUCTUR”D. “DATASTRUCTURE”(42) 設(shè)串 S=”I AM A TEACHER! 其長(zhǎng)度是 DA. 16B. 11C. 14D.15塞殊，棵辯霧點(diǎn)錚逬籃數(shù)弓15個(gè)，單分支A. 15B. 16C. 17D. 47(44) 假定一棵二叉樹(shù)的結(jié)點(diǎn)數(shù)為18個(gè)，則它的最小高度B oA. 4B. 5C 6D 18(45) 在一棵二叉樹(shù)中第五層上的結(jié)點(diǎn)數(shù)最多為C。A. 8B. 15C. 16D. 32(46) 在一棵具有五層的滿二叉樹(shù)中，結(jié)點(diǎn)總數(shù)為A. 31B. 32C. 33D. 16C.D.(47)已知 8 個(gè)數(shù)據(jù)元素為(34、76、45、18、26、54

13、、92、 65),按照依次插入結(jié)點(diǎn)的方法生成一棵二叉排序樹(shù)后，最后 兩層上的結(jié)點(diǎn)總數(shù)為B_A. 1B 24D.(48)由分別帶權(quán)為9、2、5、7的四個(gè)葉子結(jié)點(diǎn)構(gòu)造一棵哈 夫曼樹(shù)，該樹(shù)的帶權(quán)路徑長(zhǎng)度為COA. 23B. 37C. 4446(49) 在樹(shù)中除根結(jié)點(diǎn)外，其余結(jié)點(diǎn)分成m(mMO)個(gè) A 的集合T1，T2，T3.Tm海個(gè)集合又都是樹(shù)，此時(shí)結(jié)點(diǎn)T 稱(chēng)為T(mén)i的父結(jié)點(diǎn)，Ti稱(chēng)為T(mén)的子結(jié)點(diǎn)(lWiWm)。A.互不相交B.可以相交C.葉結(jié)點(diǎn)可以相交D.樹(shù)枝結(jié)點(diǎn)可以相交(50) 如果結(jié)點(diǎn)A有三個(gè)兄弟，而且B是A的雙親，則B的出度是BoA. 3B. 4C. 5D.1(51)在一個(gè)有向圖中，所有頂點(diǎn)的入

14、度之和等于所有頂點(diǎn) 的出度之和的B倍oA. 1/2B. 1C. 2D.具有n個(gè)頂點(diǎn)的無(wú)向完全圖,邊的總數(shù)為DA. n-1B. nC. n+1D.n*(n-1)/2翳豊向圖G的鄰接矩陣A中，若A悶等于】，則A麗 A. i+jB. i-jC. 1D. 0(54) 圖的深度優(yōu)先或廣度優(yōu)先遍歷的空間復(fù)雜性均為 A o (訪問(wèn)標(biāo)志位數(shù)組空間)A. O(n)B. 0(e)D 0 (n+e)(55) 請(qǐng)指出在順序表2、5、7、10、14、41、52中，用折半法查找關(guān)鍵碼12需做. 碼比較。A.2B.3C.4=1 I15、D. 5C 0 (n_e)18、 23、 35、C次關(guān)鍵(56)對(duì)線性表進(jìn)行折半查找時(shí)，

15、必須要求線性表A.式存儲(chǔ)以順序方式存儲(chǔ)B.以鏈接方c.D.(57) 設(shè)二叉排序樹(shù)中有n個(gè)結(jié)點(diǎn)，則在二叉排序樹(shù)的平均查找長(zhǎng)度為BoA. 0(1) B 0(log2n)C 0(n) D.0(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 次p,削則讓豔聘"b空單元'散列函數(shù)叫)g %A.小于等于m的最大畜數(shù)B.小于等于m的最大素c.小于等于m的最大偶數(shù)D.小于等于m的最大合(60)D是HASH查找的沖突處理方法。A.求余

16、法 B.平方取中法C.二分法 D.開(kāi)(61)當(dāng)a的值較小時(shí)，散列存儲(chǔ)通常比其他存儲(chǔ)方式具有放地址法的查找速度。 BA.較慢 B.較快C相同D.不確定(62)對(duì)線性表進(jìn)行折半查找最方便的存儲(chǔ)結(jié)構(gòu)是BA順序表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.平吻概率下述排序算法中，穩(wěn)定的是B。A.直接選擇排序 B.直接插入排序C.快速D.堆排序(65)排序(66)大。下列排序算法中,

17、A需要的輔助存儲(chǔ)空間最序(67)A快速排序B.插入排序C.希爾排序D.基數(shù)排下列各種排序算法中平均時(shí)間復(fù)雜度為0(/)是_ d=;l=iA.快速排序 B.堆排序 C.歸并排序 D. 冒泡排序(68)在基于關(guān)鍵碼比較的排序算法中，C算法在最壞情況下，關(guān)鍵碼比較次數(shù)不高于O(nlog2n)oA.起泡排序B.直接插入排序C.二路歸并排序D快速排序一組記錄為46, 79, 56, 38, 84, 40,則采用冒泡排B o排序。黑按升序排列時(shí)第一趟排序結(jié)果是A. 46, 79, 56, 3& 40, 84B. 46, 56, 3& 79, 40, 84C. 38, 40, 46, 56,

18、 84, 79D. 38, 46, 79, 56, 40, 84(70) 每次從無(wú)序表中取出一個(gè)元素，把它插入到有序表中 的適當(dāng)位置，此種排序方法叫做AD.A.插入B.堆C快速歸并(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ì)錄

19、的初始排列狀態(tài)無(wú)關(guān)DoA.直接插入排序B.起泡排序C.快速排序D.直接選擇排序(74) 設(shè)有關(guān)鍵碼初始序列Q, H, C, Y, P, A，M，S，R，D，F(xiàn)，X, 新序列F, H, C, D, P, A, M, Q, R, S, Y，X是采用 C 方法對(duì)初始序列進(jìn)行第一趟掃描的結(jié)果。A.直接插入排序B.二路D.基數(shù)歸并排序一一C.以第一兀素為分界兀素的快速排序 排序(75) 在待排序文件已基本有序的前提下，下述排序方法中 效率最高的是C。A.直接插入排序C.快速排序C OB堆排D.直接插入排序A.C.(76) 若需在O(nlog2n)的時(shí)間內(nèi)完成對(duì)數(shù)組的排序，且要求 排序是穩(wěn)定的，則可選排序

20、方法是快速排序歸并排序_(77) 將兩個(gè)各有n個(gè)元素的有序表歸并成一個(gè)有序表，其A. n B. 2n-l C. 2n D. n-1 (78)下列排序算法中，C 算法可能會(huì)出現(xiàn)下面情 況：初始數(shù)據(jù)有序時(shí)，花費(fèi)的間反而最多。A. 堆排序B.冒泡排序D. SHELL 排序1=排序C.快速最少的比較次數(shù)是Bo1=二、填空題。侮空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)從邏輯上劃分為三種基本類(lèi)型:線性數(shù)據(jù)結(jié)構(gòu)、樹(shù)型結(jié)構(gòu)和圖結(jié)構(gòu)(4)數(shù)據(jù)的物理結(jié)構(gòu)被分為順序存儲(chǔ)儲(chǔ)、索

21、引存儲(chǔ)和散列表(Hash)存儲(chǔ)四種。(5) 一種抽象數(shù)據(jù)類(lèi)型包括變量的取值范圍操作的類(lèi)別兩個(gè)部分。(6) 數(shù)據(jù)的邏輯結(jié)構(gòu)是指數(shù)據(jù)元素間的邏輯關(guān)系,數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是指數(shù)據(jù)元素存儲(chǔ)方式或者數(shù)據(jù)元素的物理關(guān)系O(7) 數(shù)據(jù)結(jié)構(gòu)是指數(shù)據(jù)及其相互之間的關(guān)系o當(dāng)結(jié)點(diǎn)之間存在M對(duì)N (M： N)的聯(lián)系時(shí),稱(chēng)這種結(jié)構(gòu)為網(wǎng)狀結(jié)構(gòu)。當(dāng)結(jié)點(diǎn)之間存在1對(duì)N (1： N)的聯(lián)系時(shí)，稱(chēng)這種結(jié)構(gòu)為樹(shù)結(jié)構(gòu)(8) 對(duì)算法從時(shí)間和空間兩方面進(jìn)行度量，分別稱(chēng)為空間復(fù)雜度和時(shí)間復(fù)雜度分析。(9) 算法的效率可分為空間效率和時(shí)間效率。(10) for(i=l, t=l, s=0； i<=n； i+) t=t*i； s=s+t；

22、的時(shí)間復(fù)雜度為O (n)(11)線性表是n個(gè)元素的有限序列(12)線性表的存儲(chǔ)結(jié)構(gòu)洎順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)0(n)第i個(gè)位置上的數(shù)據(jù)元素需要移動(dòng)表中n-i個(gè)元素。昭摯世疇翳與刪除操作,該線性表應(yīng)采躊蠶冊(cè)冊(cè)W怛結(jié)M 儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)順序查找的平均時(shí)間復(fù)雜度為(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)o(18) 棧的插入和刪除只能在棧的棧頂進(jìn)行，后進(jìn)棧的元素必定先出棧，所以又把棧稱(chēng)為FILO表；隊(duì)列的插入和刪除運(yùn)算分別在隊(duì)列的兩端進(jìn)行，先進(jìn)隊(duì)列的元素必定先出隊(duì)列，所以又把隊(duì)列稱(chēng)

23、為 FIFO表。(19) s=" I am a man" 長(zhǎng)度為10。(20) sl=hello 篤s2二”boy”，sl，s2 連接后為:hellos=”this is the main string "，sub= "string "，strindex(s，sub) 13oint a1010,已知 a=1000,sizeof(int)=2,求 班33地址:1066o(23) 設(shè)肴兩個(gè)串p和q,隸q在p中首次出現(xiàn)的位置的運(yùn)算稱(chēng)為模戎匹配O(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+l。(26) 由分別帶權(quán)為3,9,6,2,5的共五個(gè)葉子結(jié)點(diǎn)構(gòu)成一棵哈夫曼樹(shù)，則帶權(quán)路徑長(zhǎng)度為55o(27) 在圖G的鄰接表表示中，每個(gè)頂點(diǎn)鄰接表中所含的結(jié)點(diǎn)數(shù)，對(duì)于無(wú)向圖來(lái)說(shuō)等于該 頂點(diǎn)的 度數(shù),對(duì)于有向圖來(lái)說(shuō)等于該頂點(diǎn)的出度數(shù)。輜鬍復(fù)越佇墨匕空間復(fù)雜性為O(n+e)o對(duì)于長(zhǎng)度為n的線性表，若進(jìn)行順序查找，則時(shí)間復(fù)雜0(n)；若采用折半法查找，則時(shí)間復(fù)雜度為0(log2n)(30)假設(shè)在有序線性表Al20上進(jìn)行折半查找，則比較一4,則比較四次查找成功的結(jié)點(diǎn)數(shù)為8

25、,則比較五次查找成功的結(jié)點(diǎn)數(shù)為5,豐均查找喪度為 log2(n+l)-lo (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è)增序序列O(33) 對(duì)于線性表(70, 34, 55, 23, 65, 41, 20)進(jìn)行散列70存儲(chǔ)時(shí)，若選用H (K) =K %7作為散列函數(shù)，則散列地址 為0的元素是70,散列地址為6的是34 20 55則a等于 n/m(35)散列表中解決沖突的兩種方法是開(kāi)放地址法両在'線桂表的散列存禱中,裝填因子OC又稱(chēng)為裝填系數(shù)，

26、 若用m表示散列表的長(zhǎng)度,n表示待散列存儲(chǔ)的元素的個(gè)數(shù),和鏈地址法oa的值越小，則關(guān)鍵碼直接直接定(38) 構(gòu)造哈希函數(shù)的方法有(寫(xiě)二個(gè))址法，數(shù)字分析法，平方取中法，折疊法，除留余數(shù)法，隨 機(jī)數(shù)法(39) 在分塊查找中首先查找找相應(yīng)的索引(36)在散列存儲(chǔ)中，裝填因子a的值越大，則 沖突的可能性就越大 生沖突的可能性就越小塊(40) 散列表的查找效率主要取決于散列表造表時(shí)選擇的哈希函數(shù)和裝填因子O a1-*(41) 對(duì)兩棵具有相同關(guān)鍵字集合而形狀不同的二叉排序樹(shù),中序 遍歷它們得到的序列的順序是一樣的。(42) 當(dāng)待排序的記錄數(shù)較大，排序碼較隨機(jī)且對(duì)穩(wěn)定性不祜要求時(shí)，宜采用快速排序；當(dāng)待排序

27、的記排序。錄數(shù)較大，存儲(chǔ)空間允許且要求排序是穩(wěn)定時(shí),宜采用歸并(43) 在堆排序的過(guò)程中，對(duì)任一分支結(jié)點(diǎn)進(jìn)行篩運(yùn)算的時(shí)間復(fù)雜度為0(log2n),整個(gè)堆排序過(guò)程的時(shí)間復(fù)雜度為 0(nlog2n)1=1(44) 當(dāng)向一個(gè)知堆插入一個(gè)具有最大值的元素時(shí)，需要逐層向上調(diào)整,直到被調(diào)整到根結(jié)點(diǎn)l¥i位置為止。(45) 對(duì)一組初始關(guān)鍵字序列(40, 50, 95, 20, 15, 70,60, 45, 10)進(jìn)行冒泡排序，則第一趟需要進(jìn)行相鄰記錄的比較的次數(shù)為8,在整個(gè)排序過(guò)程中最多需要進(jìn)行趟排序才可以完成。(46) 在在插入排序、選擇排序、快速排序、堆排序、歸并排序和基數(shù)排序中，平均比較次數(shù)

28、最少的排序是快速 ，需要內(nèi)存容量最多的是歸并(47) 堆排序是不穩(wěn)定，空間復(fù)雜度為 0(1) 最壞情況下，其時(shí)間復(fù)雜度也為0(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í)間復(fù)雜度是0(nlog2n)(51) 對(duì)于n個(gè)記錄的集合進(jìn)行歸并排序，所需的附加空間 消痛是(52) 設(shè)表中元素的初始

29、狀態(tài)是按鍵值遞增的，分別用堆排 審、快速排序、冒泡排序和歸并排序方法對(duì)其仍按遞增順序0(n)I'll麟忖窗飜排序=;1=11=最省時(shí)間，快速三、判斷題。(每小題1分，共10分)1.數(shù)據(jù)元素是數(shù)據(jù)的最小單位。)2.數(shù)據(jù)項(xiàng)是數(shù)據(jù)的基本單位。)3 順序存儲(chǔ)的線性表可以隨機(jī)存取。)4.線性表中的元素可以是各種各樣的，但同一線性表 飯據(jù)元素具有相同的特性，因此，是屬于同一數(shù)據(jù)對(duì)象。111)5.在單鏈表中，任何兩個(gè)元素的存儲(chǔ)位置之間都有固 定的聯(lián)系，因?yàn)榭梢詮念^結(jié)點(diǎn)査找任何一個(gè)元素。(X )6.在單鏈表中，要取得某個(gè)元素，只要知道該元素的 指針即可，因此，單鏈表是隨機(jī)存取的存儲(chǔ)結(jié)構(gòu)。(X )7.鏈

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

31、序列中的最后一個(gè)結(jié)(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 )1&連通分量是無(wú)向圖中的極小連通子圖。的存儲(chǔ)地址。(J )19.散列法存儲(chǔ)的基本思想是由關(guān)鍵碼的值決定數(shù)據(jù) (V )20.散列表的查找效率取決于散列表造表時(shí)選取的散 列函數(shù)和處理沖突的方法。(V )21. m階B樹(shù)每一個(gè)結(jié)點(diǎn)的子樹(shù)個(gè)數(shù)都小于或等于nr。(V )22.中序遍歷二叉排序樹(shù)的結(jié)點(diǎn)就可以得到排好序的 結(jié)點(diǎn)序列

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

33、個(gè)文件。(x )29.在索引順序文件中插入新的記錄時(shí)，必須復(fù)制整 個(gè)文件(X )31).索引順序文件是一種特殊的順序文件，因此通常 存放在磁帶上。四、簡(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ù)類(lèi)型和算法。數(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í)也稱(chēng)為字段或域。數(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)就

34、是指數(shù)據(jù)元素間的關(guān)系。 數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)：數(shù)據(jù)的物理結(jié)構(gòu)表示數(shù)據(jù)元素的存儲(chǔ)方式或 者數(shù)據(jù)元素的物理關(guān)系。數(shù)據(jù)類(lèi)型:是指變量的取值范圍和所能夠進(jìn)行的操作的總和。 算法：是對(duì)特定問(wèn)題求解步驟的一種描述，是指令的有限序 列。2. 簡(jiǎn)述棧和線性表的區(qū)別。答：一般線性表使用數(shù)組來(lái)表示的。線性表一般有插入、刪 除、讀取等對(duì)于任意元素的操作。而棧只是一種特殊的線性表。棧只能在線性表的一端插入(稱(chēng)為入棧,push)或者讀取棧頂元素或者稱(chēng)為“彈出、出?！?(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)行

35、插入，刪除操作；隊(duì)列在 一端(top)刪除，一端(rear)插入。棧序列有多少種？寫(xiě)岀全部的可能序列。4.如果進(jìn)棧的元素序列為A, B, C, D,則可能得到的出答：可能序列有 14 種：ABCD; ACBD; ACDB; ABDC; ADCB; BACD;BADC; BCAD; BCDA; BDCA; CBAD; CBDA; CDBA; DCBA。3, 5, 6, 1, 2 和 1, 3, 5,4, 2, 6的出棧序列?并說(shuō)明為什么不能得到或如何得到。5.如果進(jìn)棧的元素序列為1, 2, 3, 4, 5, 6,能否得到4,答：不能得到4, 3, 5, 6, 1, 2,最先出棧的是4,則按321

36、的方式出，不可能得到1在2前的序列，可以得到1, 3, 5, 4,2,6,按如下方式進(jìn)行 push(l), pop (), push(2), push(3), pop (), push (4), push(5), pop (), pop (), pop (), push(6), pop () o 6.設(shè) s=“I AM A STUDENTt=aGOOD, q二“WORKER”。 求：StrLength (s), StrLength (t), SubStr( s, 8, 7), SubStr(t, 2, 1), Strlndex(s，"A" ), Strindex (s, t

37、), StrRep(s,"STUDENT”，q), SubStr (SubStr (s, 6, 2), StrConcat (t, SubStr(s, 7, 8)0答:StrLength (s)=14, StrLength (t) =4, SubStr( s, 8, 7)=” STUDENT” , SubStr(t, 2, 1)=” 0” , Strlndex(s, "A" )=3, Strindex (s, t)=0, StrRep(s,“STUDENT”，q)二” I AM A WORKER” , 7.簡(jiǎn)述下列每對(duì)術(shù)語(yǔ)的區(qū)別：空串和空格串；串變量和串常 量；主

38、串和子串；串變量的名字和串變量的值。答：空串：不含任何字符；空格串：所含字符都是空格。串變量和串常量：串常量在程序的執(zhí)行過(guò)程中只能引用不能 改變；串變量的值在程序執(zhí)行過(guò)程中是可以改變和重新賦值 的。主串與子串：子串是主串的一個(gè)子集。串變量的名字與串變量的值:串變量的名字表示串值的標(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í)，元素Al，4的起地址；(4) 按列優(yōu)先存放時(shí)，元素A4,7的起地址。(1) 6*8*6=288(2) 1000+47*6=128

39、2(3) 1000+(8+4)*8=1096(4) 1000+(6*7+4)*8二1368 9.分別畫(huà)出含三個(gè)結(jié)點(diǎn)的無(wú)序樹(shù)與二叉樹(shù)的所有不同形態(tài)。 答：無(wú)序樹(shù)形態(tài)如下：OAYO二叉樹(shù)形態(tài)如下:分別寫(xiě)出圖1中所示二叉樹(shù)的先序遍歷、歷、后ABCDE FGHIJ圖110.序遍歷的結(jié)點(diǎn)訪問(wèn)序列。答：先序遍歷序列:ABDEHICFJG列:DBHEIAFJCG中序遍歷序后序遍歷序列:DHIEBJFGCA11試找出分別滿足下列條件的所有二叉樹(shù)。(1) 先序序列與中序序列相同。(2) 后序序列與中序序列相同。(3)先序序列與后序序列相同。答：(1)先序序列和中序序列相同：空樹(shù)或缺左子樹(shù)的單支 樹(shù);（2）后序序

40、列和中序序列相同:空樹(shù)或缺右子樹(shù)的單支樹(shù);（3）先序序列和后序序列相同：空樹(shù)或只有根結(jié)點(diǎn)的二叉 樹(shù)。12已知一棵二叉樹(shù)的中序序列和后序序列分別為BDCEAFHG和DECBHGFA,試畫(huà)出這棵二叉樹(shù)。答：這棵二叉樹(shù)為:中序遍歷序列:DGBAEHCF:ABDGCEHF13分別寫(xiě)出圖2中所示二叉樹(shù)的先序遍歷、中序遍歷、后ABcDEFGH圖2序遍歷的結(jié)點(diǎn)訪問(wèn)序列。W.答：先序遍歷序列后序遍歷序列:GDBHEFCA14.給定權(quán)值1& 3, 32, 5, 26,12, 8),構(gòu)造的哈夫曼樹(shù)。答:哈夫曼樹(shù)為1=1 15假設(shè)用于通信的電文僅由8個(gè)字母組成,字母在電文中出現(xiàn)的頻率分別為7, 19, 2,

41、 6, 32, 3, 21, 10,試為這8個(gè)設(shè)計(jì)哈夫曼編碼。答：哈夫曼樹(shù)為:111在上述哈夫曼樹(shù)的每個(gè)左分支上標(biāo)以0,右分支上標(biāo)以1,并 設(shè)這8個(gè)字母分別為A、B、C、D、E、F、G和H,則它們的 哈夫曼樹(shù)為分別為：A： 0000 B： 10 C： 00110 D： 0010 E： 01 F：00111 G： 11 H： 00011='16.畫(huà)出無(wú)向圖G1的鄰接矩陣和鄰接表示意圖，并寫(xiě)出每個(gè)頂點(diǎn)的度。3答：（1）鄰接矩陣:1 01 10 10 11 0（2）鄰接鏈表:vl01234（3）每個(gè)頂點(diǎn)的度:頂點(diǎn)VIV23V32V43V5317畫(huà)出有向圖G2的鄰接矩陣、鄰接表和逆鄰接表示意圖

42、,并寫(xiě)出每個(gè)頂點(diǎn)的入度和出度。G22答:(1)鄰接鏈表:VIAV2V3V4V5V6023430A51Z54(2)逆鄰接鏈表:VI72V3V4V5V6O2345 412(3) 頂點(diǎn) 入度 出度VIV222V312V413V5 21V6 2318 對(duì)應(yīng)圖G3,寫(xiě)出從vl出必的深度優(yōu)先遍歷序列和廣度優(yōu)先遍歷序列各三個(gè)。G3答：深度優(yōu)先查找遍歷序列：VI V2 V3 V4 V5; VI V3 V5 V4V2; VI V4 V3 V5 V2廣度優(yōu)先查找遍歷序列：VI V2 V3 V4 V5; VI V3 V2 V4 V5;VI V4 V3 V2 V519何謂二叉排序樹(shù)?答:一棵二叉排序樹(shù)（又稱(chēng)二叉查找樹(shù)

43、）或者是一棵空樹(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=l,，ko當(dāng)給定值K與閉散列表中的某個(gè)鍵值是相對(duì)于某個(gè)散列函數(shù)乩的同義 詞因而發(fā)生沖突時(shí)，繼續(xù)計(jì)算該給定值K在下一個(gè)散列函數(shù)IU下的散列地址