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

1、數(shù)據(jù)結(jié)構(gòu)復(fù)習題及答案（12級）一、選擇題。(每小題2分，共40分)(1)計算機識別存儲和加工處理的對象被統(tǒng)稱為 Ao據(jù)B.數(shù)據(jù)元素C.數(shù)據(jù)結(jié)構(gòu)D.數(shù)據(jù)類型聯(lián)系。 數(shù)據(jù)結(jié)構(gòu)通常是研究數(shù)據(jù)的A及它們之間的B.存儲和抽象D.理想與邏輯 AoA.存儲和邏輯結(jié)構(gòu)C.理想和抽象(3) 不是數(shù)據(jù)的邏輯結(jié)構(gòu)是A.散列結(jié)構(gòu)B.線性結(jié)構(gòu)C.樹結(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ù)項B.數(shù)據(jù)類型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ù)在計算機存儲器內(nèi)表示時，物理地址與邏輯地址相同并且是連續(xù)的，稱之為C A.存儲結(jié)構(gòu)C順序存儲結(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)與動態(tài)結(jié)構(gòu)"C.線性結(jié)構(gòu)與非線性結(jié)構(gòu)D.緊湊結(jié)構(gòu)與非緊湊結(jié)構(gòu)(9)對一個算法的評價，不包括如下 B方面的內(nèi)容。昭雜度A.健壯性和可讀性C.正確性 (10)算法分析的兩個方面是A oA空間復(fù)雜性和時間復(fù)雜B.正確性和

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

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

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

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

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

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

9、,頭指針F總是指向隊頭元素的前一位置，尾指針R總 是指向隊尾元素的當前位置，則該循環(huán)隊列中的元素個數(shù)為C OA7TFB. F-RC.(R-F+M)%MD. (FR+M)%MB.(33) 設(shè)指針變量fnmt表示鏈式隊列的隊頭指針，指針變量 rear表示鏈式隊列的隊尾指針，指針變量s指向?qū)⒁腙犃?的結(jié)點X,則入隊列的操作序列為_ 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串的長度D.空串就是(35)° 串是n個字母的有限序列B.D：霹蠶霜離驟書篤濤隊翱畫位置的字符都相符時才相等(36) 字符串的長度是指_ CoA.串中不同字符的個數(shù)B.母的個數(shù)C.串中所含字符的個數(shù)D.字的個數(shù)(37) 兩個字符串相等的充要條件是C_A.兩個字符串的長度相等 符串中對應(yīng)位置上的字符相等C.同時具備(A)和(B)兩個條件 案都不對串中不同字串中不同數(shù)(38)串是一種特殊的線性表,其特殊性體現(xiàn)在了兩個字D.以上答B(yǎng)A.可以順序存儲 符C.可以鏈接存儲B.數(shù)據(jù)元素是一個字個字符D.數(shù)據(jù)元素可以是多(3?)設(shè)有兩個串P和q，求q在

11、P中首次岀現(xiàn)的位置的運 算稱作 B。A.連接B.模式匹配串D.求串長(40) 設(shè)串 sI=nABCDEFG,s2=nPQRST,函數(shù)con(x，y)返回 x和y串的連接串,subs(s,iJ)M回串s的從房號i的孚特開始 的j個字符組成的子串，len返回串s的長度，貝！| 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! 其長度是 DA. 16B. 11C. 14D.15塞殊，棵辯霧點錚逬籃數(shù)弓15個，單分支A. 15B. 16C. 17D. 47(44) 假定一棵二叉樹的結(jié)點數(shù)為18個，則它的最小高度B oA. 4B. 5C 6D 18(45) 在一棵二叉樹中第五層上的結(jié)點數(shù)最多為C。A. 8B. 15C. 16D. 32(46) 在一棵具有五層的滿二叉樹中，結(jié)點總數(shù)為A. 31B. 32C. 33D. 16C.D.(47)已知 8 個數(shù)據(jù)元素為(34、76、45、18、26、54

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

14、度之和等于所有頂點 的出度之和的B倍oA. 1/2B. 1C. 2D.具有n個頂點的無向完全圖,邊的總數(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 (訪問標志位數(shù)組空間)A. O(n)B. 0(e)D 0 (n+e)(55) 請指出在順序表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)對線性表進行折半查找時，

15、必須要求線性表A.式存儲以順序方式存儲B.以鏈接方c.D.(57) 設(shè)二叉排序樹中有n個結(jié)點，則在二叉排序樹的平均查找長度為BoA. 0(1) B 0(log2n)C 0(n) D.0(n2)(58) 依次插入序列(50, 72, 43, 85, 75, 20, 35, 45, 65, 30)后建立的二叉搜索樹中，查找元素35要進行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.開(61)當a的值較小時，散列存儲通常比其他存儲方式具有放地址法的查找速度。 BA.較慢 B.較快C相同D.不確定(62)對線性表進行折半查找最方便的存儲結(jié)構(gòu)是BA順序表B有序的順序表C 璉癡D 看序的鏈麥(63) 如果要求一個線性表既能較快的查找，又能適應(yīng)動態(tài)變化的要求，可以采用 D查找方法。A.分塊B.順序C.折半D.散列(64) 散列函數(shù)有一個共同性質(zhì)，即函數(shù)值應(yīng)按C取其值域的每一個值。A.最大概率 B.最小概率C.同等概率D.平吻概率下述排序算法中，穩(wěn)定的是B。A.直接選擇排序 B.直接插入排序C.快速D.堆排序(65)排序(66)大。下列排序算法中,

17、A需要的輔助存儲空間最序(67)A快速排序B.插入排序C.希爾排序D.基數(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排序。黑按升序排列時第一趟排序結(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) 每次從無序表中取出一個元素，把它插入到有序表中 的適當位置，此種排序方法叫做AD.A.插入B.堆C快速歸并(71) 每次從無序表中挑選出一個最小或最大元素，把它交換到有序表的一端，此種排序方法叫做_ B排序。A.插入B.堆C快速D.歸并(72) 設(shè)一組初始記錄關(guān)鍵字序列(5, 2, 6, 3, 8),以第一 個記錄關(guān)鍵字5為基準進行一趟快速排序的結(jié)果為CA 2, 3, 5, 8, 6B 3, 2、5, 8, 6C 3, 2, 5, 6, 8D 2, 3, 6, 5, 8(73) 下列排序方法中，哪一種方法的比較次數(shù)與紀錄

19、的初始排列狀態(tài)無關(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 方法對初始序列進行第一趟掃描的結(jié)果。A.直接插入排序B.二路D.基數(shù)歸并排序一一C.以第一兀素為分界兀素的快速排序 排序(75) 在待排序文件已基本有序的前提下，下述排序方法中 效率最高的是C。A.直接插入排序C.快速排序C OB堆排D.直接插入排序A.C.(76) 若需在O(nlog2n)的時間內(nèi)完成對數(shù)組的排序，且要求 排序是穩(wěn)定的，則可選排序

20、方法是快速排序歸并排序_(77) 將兩個各有n個元素的有序表歸并成一個有序表，其A. n B. 2n-l C. 2n D. n-1 (78)下列排序算法中，C 算法可能會出現(xiàn)下面情 況：初始數(shù)據(jù)有序時，花費的間反而最多。A. 堆排序B.冒泡排序D. SHELL 排序1=排序C.快速最少的比較次數(shù)是Bo1=二、填空題。侮空1分，共10分)(1)數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計算的程序設(shè)計問題中計算機的數(shù)據(jù)以及它們之間的_關(guān)系和運算等的學科。(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)、樹型結(jié)構(gòu)和圖結(jié)構(gòu)(4)數(shù)據(jù)的物理結(jié)構(gòu)被分為順序存儲儲、索

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

22、的時間復(fù)雜度為O (n)(11)線性表是n個元素的有限序列(12)線性表的存儲結(jié)構(gòu)洎順序存儲和鏈式存儲0(n)第i個位置上的數(shù)據(jù)元素需要移動表中n-i個元素。昭摯世疇翳與刪除操作,該線性表應(yīng)采躊蠶冊冊W怛結(jié)M 儲結(jié)構(gòu)上實現(xiàn)順序查找的平均時間復(fù)雜度為(16) 鏈式存儲結(jié)構(gòu)中的結(jié)點包含數(shù)據(jù)域和指針域。(17) 對于一個長度為n的單鏈存儲的線性表，在表頭插入元素的時間復(fù)雜度為0(1),在表尾插入元素的時間復(fù)雜度為O (n)o(18) 棧的插入和刪除只能在棧的棧頂進行，后進棧的元素必定先出棧，所以又把棧稱為FILO表；隊列的插入和刪除運算分別在隊列的兩端進行，先進隊列的元素必定先出隊列，所以又把隊列稱

23、為 FIFO表。(19) s=" I am a man" 長度為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è)肴兩個串p和q,隸q在p中首次出現(xiàn)的位置的運算稱為模戎匹配O(24) 在樹型結(jié)構(gòu)中，樹根結(jié)點沒有前趨結(jié)點，其余每個結(jié)點有且僅有一個前驅(qū)結(jié)點；樹葉結(jié)點沒有后繼結(jié)點，其余每

24、個結(jié)點的后繼結(jié)點數(shù)不受限制。(25) 在一棵二叉樹中，度為0的結(jié)點的個數(shù)為n0 ,度為2的結(jié)點的個數(shù)為n2 ,貝!|： n0=n2+l。(26) 由分別帶權(quán)為3,9,6,2,5的共五個葉子結(jié)點構(gòu)成一棵哈夫曼樹，則帶權(quán)路徑長度為55o(27) 在圖G的鄰接表表示中，每個頂點鄰接表中所含的結(jié)點數(shù)，對于無向圖來說等于該 頂點的 度數(shù),對于有向圖來說等于該頂點的出度數(shù)。輜鬍復(fù)越佇墨匕空間復(fù)雜性為O(n+e)o對于長度為n的線性表，若進行順序查找，則時間復(fù)雜0(n)；若采用折半法查找，則時間復(fù)雜度為0(log2n)(30)假設(shè)在有序線性表Al20上進行折半查找，則比較一4,則比較四次查找成功的結(jié)點數(shù)為8

25、,則比較五次查找成功的結(jié)點數(shù)為5,豐均查找喪度為 log2(n+l)-lo (31)在一棵二叉排序樹中，每個分支結(jié)點的左子樹上所有結(jié) 點的值一定小于該結(jié)點的值，右子樹上所有結(jié)點的值一定大于該結(jié)點的值。小于(32) 對一棵二叉排序樹進行中序遍歷時，得到的結(jié)點序列是一個增序序列O(33) 對于線性表(70, 34, 55, 23, 65, 41, 20)進行散列70存儲時，若選用H (K) =K %7作為散列函數(shù)，則散列地址 為0的元素是70,散列地址為6的是34 20 55則a等于 n/m(35)散列表中解決沖突的兩種方法是開放地址法両在'線桂表的散列存禱中,裝填因子OC又稱為裝填系數(shù)，

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

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

28、最少的排序是快速 ，需要內(nèi)存容量最多的是歸并(47) 堆排序是不穩(wěn)定，空間復(fù)雜度為 0(1) 最壞情況下，其時間復(fù)雜度也為0(nlog2n)_(48) 若待排序的文件中存在多個關(guān)鍵字相同的記錄，經(jīng)過某種排序方法排序后，具有相同關(guān)鍵字的記錄間的相對位置 保持不變，則這種排序方法是穩(wěn)定的排序方法。(49) 在對一組記錄(50,40,95, 20, 15,70,60,45,80)進行直接插入排序時，當把第7個記錄60插入到有序表時，為尋找插 入位置需比較3次。(50)二路歸并排序的時間復(fù)雜度是0(nlog2n)(51) 對于n個記錄的集合進行歸并排序，所需的附加空間 消痛是(52) 設(shè)表中元素的初始

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

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

31、序列中的最后一個結(jié)(x )15.已知二叉樹的前序遍歷和后序遍歷序列并不能唯 一地確定這棵樹，因為不知道樹 的根結(jié)點是哪一個。(X )16.在哈夫曼編碼中，當兩個字符出現(xiàn)的頻率相同時, 其編碼也相同，對于這種情況應(yīng)作特殊處理。(V )17.有回路的圖不能進行拓撲排序。(X )1&連通分量是無向圖中的極小連通子圖。的存儲地址。(J )19.散列法存儲的基本思想是由關(guān)鍵碼的值決定數(shù)據(jù) (V )20.散列表的查找效率取決于散列表造表時選取的散 列函數(shù)和處理沖突的方法。(V )21. m階B樹每一個結(jié)點的子樹個數(shù)都小于或等于nr。(V )22.中序遍歷二叉排序樹的結(jié)點就可以得到排好序的 結(jié)點序列

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

33、個文件。(x )29.在索引順序文件中插入新的記錄時，必須復(fù)制整 個文件(X )31).索引順序文件是一種特殊的順序文件，因此通常 存放在磁帶上。四、簡答題。(共6小題，每小題約5分，共32分)1. 簡述下列術(shù)語：數(shù)據(jù)、數(shù)據(jù)項、數(shù)據(jù)元素、數(shù)據(jù)邏輯結(jié) 構(gòu)、數(shù)據(jù)存儲結(jié)構(gòu)、數(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ù)邏輯結(jié)構(gòu)：數(shù)據(jù)的邏輯結(jié)構(gòu)就

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

35、插入，刪除操作；隊列在 一端(top)刪除，一端(rear)插入。棧序列有多少種？寫岀全部的可能序列。4.如果進棧的元素序列為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的出棧序列?并說明為什么不能得到或如何得到。5.如果進棧的元素序列為1, 2, 3, 4, 5, 6,能否得到4,答：不能得到4, 3, 5, 6, 1, 2,最先出棧的是4,則按321

36、的方式出，不可能得到1在2前的序列，可以得到1, 3, 5, 4,2,6,按如下方式進行 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.簡述下列每對術(shù)語的區(qū)別：空串和空格串；串變量和串常 量；主

38、串和子串；串變量的名字和串變量的值。答：空串：不含任何字符；空格串：所含字符都是空格。串變量和串常量：串常量在程序的執(zhí)行過程中只能引用不能 改變；串變量的值在程序執(zhí)行過程中是可以改變和重新賦值 的。主串與子串：子串是主串的一個子集。串變量的名字與串變量的值:串變量的名字表示串值的標識 符。8.設(shè)有二維數(shù)組A(6X8),每個元素占6個字節(jié)存儲，順 序存放，A的起地址為1000,計算：數(shù)組A的體積(即存儲量)；(2) 數(shù)組的最后一個元素A的起地址；(3) 按行優(yōu)先存放時，元素Al，4的起地址；(4) 按列優(yōu)先存放時，元素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.分別畫出含三個結(jié)點的無序樹與二叉樹的所有不同形態(tài)。 答：無序樹形態(tài)如下：OAYO二叉樹形態(tài)如下:分別寫出圖1中所示二叉樹的先序遍歷、歷、后ABCDE FGHIJ圖110.序遍歷的結(jié)點訪問序列。答：先序遍歷序列:ABDEHICFJG列:DBHEIAFJCG中序遍歷序后序遍歷序列:DHIEBJFGCA11試找出分別滿足下列條件的所有二叉樹。(1) 先序序列與中序序列相同。(2) 后序序列與中序序列相同。(3)先序序列與后序序列相同。答：(1)先序序列和中序序列相同：空樹或缺左子樹的單支 樹;（2）后序序

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

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

42、,并寫出每個頂點的入度和出度。G22答:(1)鄰接鏈表:VIAV2V3V4V5V6023430A51Z54(2)逆鄰接鏈表:VI72V3V4V5V6O2345 412(3) 頂點 入度 出度VIV222V312V413V5 21V6 2318 對應(yīng)圖G3,寫出從vl出必的深度優(yōu)先遍歷序列和廣度優(yōu)先遍歷序列各三個。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何謂二叉排序樹?答:一棵二叉排序樹（又稱二叉查找樹

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