大數(shù)據(jù)的結(jié)構(gòu)復(fù)習(xí)的題目及問題解釋

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

2、.D.樹型結(jié)構(gòu)集合數(shù)據(jù)在計(jì)算機(jī)存儲(chǔ)器內(nèi)表示時(shí)，物理地址與邏輯地址相同并且是連續(xù)的，稱之為A.存儲(chǔ)結(jié)構(gòu)C.順序存儲(chǔ)結(jié)構(gòu)B.D.邏輯結(jié)構(gòu)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)在數(shù)據(jù)結(jié)構(gòu)的討論中把數(shù)據(jù)結(jié)構(gòu)從邏輯上分為A.內(nèi)部結(jié)構(gòu)與外部結(jié)構(gòu)C.線性結(jié)構(gòu)與非線性結(jié)構(gòu)對(duì)一個(gè)算法的評(píng)價(jià)，不包括如下A.健壯性和可讀性C.正確性D.B.D.B.算法分析的兩個(gè)方面是AA.空間復(fù)雜性和時(shí)間復(fù)雜性C.可讀性和文檔性線性表是具有n個(gè) CA.表元素C.數(shù)據(jù)元素B.D.則數(shù)據(jù)結(jié)構(gòu)A靜態(tài)結(jié)構(gòu)與動(dòng)態(tài)結(jié)構(gòu)緊湊結(jié)構(gòu)與非緊湊結(jié)構(gòu)并行性方面的內(nèi)容。時(shí)空復(fù)雜度正確性和簡明性數(shù)據(jù)復(fù)雜性和程序復(fù)雜性的有限序列（nz 0）。B.字符D.數(shù)據(jù)項(xiàng)(12)線性表的存儲(chǔ)結(jié)構(gòu)是

3、一種的存儲(chǔ)結(jié)構(gòu)。A.隨機(jī)存取B.順序存取C.索引存取D.HASH存取(13)在一個(gè)長度為的順序表中，向第i個(gè)元素(1 i 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)設(shè)指針變量p指向單鏈表結(jié)點(diǎn)A,則刪除結(jié)點(diǎn)A的后繼結(jié)點(diǎn)B需要的操作為AA. p-n ext=p-n ext- nextB. p=p-nextC. p=p-n ext- nextD. p_n ext=p(18)下列說法哪個(gè)正確？DA. 堆棧是在兩端操作、先進(jìn)后出的線性表B.

4、 堆棧是在一端操作、先進(jìn)先出的線性表C. 隊(duì)列是在一端操作、先進(jìn)先出的線性表D. 隊(duì)列是在兩端操作、先進(jìn)先出的線性表(19) 棧和隊(duì)列的共同點(diǎn)是 C。A. 都是先進(jìn)后出B.都是先進(jìn)先出C.只允許在端點(diǎn)處插入和刪除元素D.沒有共同點(diǎn)(20) 棧與一般線性表的區(qū)別主要在 D。A、元素個(gè)數(shù)B 、元素類型 C 、邏輯結(jié)構(gòu) D、插入、刪除元素的位置(21) 鏈棧與順序棧相比，比較明顯的優(yōu)點(diǎn)是 D。A、插入操作更加方便B刪除操作更加方便A.隊(duì)列B.棧C.線性表D.二叉樹(23)C若已知一個(gè)棧的入棧序列是1，。2，3,，n，其輸出序列為 p1，p2，p3,，pn，若p1= n，貝U pi為A. iB. B.

5、 n=iC. n-i+1D.不確定(24)當(dāng)利用大小為N的一維數(shù)組順序存儲(chǔ)一個(gè)棧時(shí)，假定用top=N表示?？眨瑒t向這個(gè)棧插入一個(gè)兀素時(shí)，首先應(yīng)執(zhí)行B語句修改top指針。A. top+B. top-C. top=0D. top(25) 4 個(gè)兀素進(jìn)S棧的順序是A,B,C,D，經(jīng)運(yùn)算POP(S)后，棧頂兀素是C。A. AB. BC. CD. D(26)一個(gè)棧的輸入序列是a,b,c,d,e,則棧的不可能的輸出序列是C。A. edcbaB. decbaC.dceabD.abcde(27)設(shè)輸入序列是1、2、3、n，經(jīng)過棧的作用后輸出序列的第一個(gè)兀素是n，則輸出序列中第i個(gè)輸出元素是C。A. n-iB.

6、 n-1-iC. n+1-iD.不能確定DO(28)字符AD依次進(jìn)入一個(gè)棧，按出棧的先后順序組成不同的字符串，至多可以組成CB個(gè)不同的(22)以下數(shù)據(jù)結(jié)構(gòu)中哪一個(gè)是非線性結(jié)構(gòu)C不會(huì)出現(xiàn)下溢的情況D不會(huì)出現(xiàn)上溢的情況字符串?A. 15B. 14C. 16D. 21(29)設(shè)指針變量top指向當(dāng)前鏈?zhǔn)綏５臈ｍ?，則刪除棧頂元素的操作序列為A. top=top+1;B. top=top-1;C. top-n ext=top;D. top=top-n ext;(30)設(shè)棧S和隊(duì)列Q的初始狀態(tài)為空，元素 E1、E2、E3、E4、E5和E6依次通過棧S, 個(gè)元素出棧后即進(jìn)入隊(duì)列Q若6個(gè)元素出列的順序?yàn)?E2

7、、E4、E3、E6、E5和E1,則棧S的容量至少應(yīng)該是A. 6B. 4C. 3D. 2(31)若用一個(gè)大小為6的數(shù)組來實(shí)現(xiàn)循環(huán)隊(duì)列，且當(dāng)前 rear和front的值分別為0和3。當(dāng)從隊(duì)列中刪除一個(gè)元素，再加入兩個(gè)元素后,rear和front的值分別為A. 1 和 5B. 2 和 4C. 4 和 2D. 5 和 1(32)設(shè)順序循環(huán)隊(duì)列Q0: M-1的頭指針和尾指針分別為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(33)設(shè)指針變量front表示鏈?zhǔn)疥?duì)列的隊(duì)頭指針

8、，指針變量rear表示鏈?zhǔn)疥?duì)列的隊(duì)尾指針，指針變量s指向?qū)⒁腙?duì)列的結(jié)點(diǎn)X，則入隊(duì)列的操作序列為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.串是一種特殊的線性表B.串的長度必須大于零C.串中兀素只能是字母D.空串就是空白串(35)下列關(guān)于串的敘述中，正確的是D。A.串長度是指串中不同字符的個(gè)數(shù)B.串是n個(gè)字母的有限序列C.如果兩個(gè)串含有相同的字符，則它們相等D.只有當(dāng)兩個(gè)串的長度相等，并且各個(gè)對(duì)應(yīng)位置的

9、字符都相符時(shí)才相等(36)字符串的長度是指C。A.串中不同字符的個(gè)數(shù)B.串中不同字母的個(gè)數(shù)C.串中所含字符的個(gè)數(shù)D.串中不同數(shù)字的個(gè)數(shù)(37)兩個(gè)字符串相等的充要條件是C。A.兩個(gè)字符串的長度相等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.求串長(40) 設(shè)串sl=ABCDEFG,s2=PQRST,函數(shù)con(x,y)

10、返回x和y串的連接串,subs(s,i,j) 返回串s的從序號(hào)i的 字符開始的j個(gè)字符組成的子串，len(s)返回串s的長度，則 con(subs(s1,2,1en(s2) ，subs(sl,len(s2) ，2) 的結(jié)果串是D _。A. BCDEFB. BCDEFGC. BCPQRSTD. BCDEFEF(41) 函數(shù) substr(“ DATASTRUCTU”E 5，9)的返回值為 _ A。A. STRUCTUREB. “DATAC. “ ASTRUCTURD. “ DATASTRUCTURE(42) 設(shè)串 S=” I AM A TEACHER! ”，其長度是 D。A. 16B. 11C.

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

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

13、B. 1 C. 2 D. 4(52) 具有n個(gè)頂點(diǎ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. 1D. 0(54) 圖的深度優(yōu)先或廣度優(yōu)先遍歷的空間復(fù)雜性均為A 。(訪問標(biāo)志位數(shù)組空間)A. 0(n) B. 0(e) C. 0(n-e)D. 0(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)行折半

14、查找時(shí)，必須要求線性表 C。A.以順序方式存儲(chǔ)B.以鏈接方式存儲(chǔ)C. 以順序方式存儲(chǔ)，且結(jié)點(diǎn)按關(guān)鍵字有序排列D. 以鏈接方式存儲(chǔ)，且結(jié)點(diǎn)按關(guān)鍵字有序排列(57)設(shè)一叉排序樹中有 n個(gè)結(jié)點(diǎn)，則在一叉排序樹的平均查找長度為B。A. O(1)B. O(log 2n)C. O( n)2D. O(n )(58)依次插入序列(50 , 72, 43,85, 75,20, 35,45, 65, 30)后建立的二叉搜索樹中，查找兀素35要進(jìn)行 A兀素間的比較。A.4次B.5次C.7次D.10 次(59)設(shè)散列表中有m個(gè)存儲(chǔ)單元，散列函數(shù)H(key)=key % p ，則p最好選擇B。A.小于等于白人戸._.來

15、&B.m的最大奇數(shù)小于等于m的最大素?cái)?shù)C.小于等于m的最大偶數(shù)D.小于等于m的最大合數(shù)(60).D是HASH查找的沖突處理方法。A.求余法 B.平方取中法C. 二分法 D. 開放地址法(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.有序的鏈表如果要求一個(gè)線性表既能較快的查找，又能適應(yīng)動(dòng)態(tài)變化的要求，可以采用D查找方法。A.分塊 B .順序 C .折半 D .散列散列函數(shù)有一個(gè)共同性質(zhì)，即函數(shù)值應(yīng)按C取其值域的每一個(gè)值。A.最大概率B .最小

16、概率 C .同等概率 D .平均概率下述排序算法中，穩(wěn)定的是B 。A.直接選擇排序B.直接插入排序C.快速排序D.堆排序下列排序算法中， A需要的輔助存儲(chǔ)空間最大。A.快速排序B.插入排序C.希爾排序D.基數(shù)排序下列各種排序算法中平均時(shí)間復(fù)雜度為0(n2)是_ D。A.快速排序B.堆排序C.歸并排序D.冒泡排序在基于關(guān)鍵碼比較的排序算法中， C算法在最壞情況下，關(guān)鍵碼比較次數(shù)不高于O(nlog2n)。A.起泡排序B.直接插入排序C.二路歸并排序D.快速排序一組記錄為46 , 79 , 56, 38, 84, 40，則采用冒泡排序法按升序排列時(shí)第一趟排序結(jié)果是B 。A. 46,79,56,38,

17、40,84B.46,56,38,79,40,84C. 38,40,46,56,84,79D.38,46,79,56,40,84每次從無序表中取出一個(gè)元素，把它插入到有序表中的適當(dāng)位置，此種排序方法叫做A 排序。A.插入 B. 堆 C. 快速 D. 歸并每次從無序表中挑選出一個(gè)最小或最大元素，把它交換到有序表的一端，此種排序方法叫做B 排(63)(64)(65)(66)(67)(68)(69)(70)(71) 序。(72)C_(73)(74)采用(75)A.插入 B. 堆 C. 快速D. 歸并設(shè)一組初始記錄關(guān)鍵字序列(5 , 2, 6, 3, 8),以第一個(gè)記錄關(guān)鍵字5為基準(zhǔn)進(jìn)行一趟快速排序的結(jié)

18、果為A. 2 , 3,5,8,6B. 3 , 2,5 ,8 , 6C. 3 , 2 ,5 ,6 ,8D. 2 , 3 ,6 ,5 , 8下列排序方法中，哪一種方法的比較次數(shù)與紀(jì)錄的初始排列狀態(tài)無關(guān)D。A.直接插入排序 B.起泡排序C.快速排序D.直接選擇排序設(shè)有關(guān)鍵碼初始序列Q , H, C,Y,P, A,M,S,R,D,F,X,新序列F ,H,C, D P,A ,M QR,S , Y,X是_ C 方法對(duì)初始序列進(jìn)行第一趟掃描的結(jié)果。A.直接插入排序B.二路歸并排序C.以第一元素為分界元素的快速排序D.基數(shù)排序在待排序文件已基本有序的前提下，下述排序方法中效率最高的是_ C。A.直接插入排序B

19、.直接選擇排序C.快速排序D .歸并排序(76) 若需在0(nlog 2n)的時(shí)間內(nèi)完成對(duì)數(shù)組的排序，且要求排序是穩(wěn)定的，則可選排序方法是CA.快速排序B堆排序C.歸并排序D直接插入排序(77) 將兩個(gè)各有n個(gè)元素的有序表歸并成一個(gè)有序表，其最少的比較次數(shù)是_ B。A. n B 2n-1 C . 2n D .n-1(78) 下列排序算法中， C 算法可能會(huì)出現(xiàn)下面情況：初始數(shù)據(jù)有序時(shí)，花費(fèi)的間反而最多。A. 堆排序 B冒泡排序C快速排序D . SHELL排序、填空題。(每空1分，共10分)(1) 數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計(jì)算的程序設(shè)計(jì)問題中計(jì)算機(jī)的 數(shù)據(jù)以及它們之間的_關(guān)系和運(yùn)算等的學(xué)科。(2

20、) 數(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) 數(shù)據(jù)的物理結(jié)構(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)是指數(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)為 樹結(jié)構(gòu)。(8) 對(duì)算法從時(shí)間和空間

21、兩方面進(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(n) 。(14) 設(shè)順序線性表中有 n個(gè)數(shù)據(jù)元素，則第i個(gè)位置上插入一個(gè)數(shù)據(jù)元素需要移動(dòng)表中n-i+1 個(gè)數(shù)據(jù)元素；刪除第i個(gè)

22、位置上的數(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è)長度為n的單鏈存儲(chǔ)的線性表，在表頭插入元素的時(shí)間復(fù)雜度為_0(1)，在表尾插入元素的時(shí)間復(fù)雜度為 O (n) 。(18) 棧的插入和刪除只能在棧的棧頂進(jìn)行，后進(jìn)棧的元素必定先出棧，所以又把棧稱為FIL0 表；隊(duì)列的插入和刪除運(yùn)算分別在隊(duì)列的兩端進(jìn)行，先進(jìn)隊(duì)列的元素必定先出隊(duì)列，所以又把隊(duì)列稱為FIFO表。(19) s= ” I am a man ” 長度為10 。(20) s1= ” hello “ ,s2

23、= ” boy”，s1,s2 連接后為： hello boy 。(21) s= ” this is the main string” ,sub= ” string ” ,strindex(s,sub)是: 13。(22) int a1010,已知 a=1000,sizeof(int)=2, 求 a33 地址： 1066 。(23) 設(shè)有兩個(gè)串p和q,求q在p中首次出現(xiàn)的位置的運(yùn)算稱為 模式匹配 。(24) 在樹型結(jié)構(gòu)中，樹根結(jié)點(diǎn)沒有 前趨結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)有且僅有 一個(gè)前驅(qū)結(jié)點(diǎn)；樹葉結(jié)點(diǎn)沒有 后繼結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)的 后繼結(jié)點(diǎn)數(shù)不受限制。(25) 在一棵二叉樹中，度為0的結(jié)點(diǎn)的個(gè)數(shù)為n0，度為

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

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

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

27、擇的 哈希函數(shù) 和裝填因子 。(41) 對(duì)兩棵具有相同關(guān)鍵字集合而形狀不同的二叉排序樹，中序 遍歷它們得到的序列的順序是一樣的。(42) 當(dāng)待排序的記錄數(shù)較大，排序碼較隨機(jī)且對(duì)穩(wěn)定性不作要求時(shí)，宜采用快速排序；當(dāng)待排序的記錄數(shù)較大，存儲(chǔ)空間允許且要求排序是穩(wěn)定時(shí)，宜采用歸并排序。(43) 在堆排序的過程中，對(duì)任一分支結(jié)點(diǎn)進(jìn)行篩運(yùn)算的時(shí)間復(fù)雜度為O(log 2n)，整個(gè)堆排序過程的時(shí)間復(fù)雜度為 O(nlog 2n)。(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，

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

29、把第7個(gè)記錄60插入到有序表時(shí)，為尋找插入位置需比較3次。(50) 二路歸并排序的時(shí)間復(fù)雜度是O(nlog 2n)。(51) 對(duì)于n個(gè)記錄的集合進(jìn)行歸并排序，所需的附加空間消耗是_ 0(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ù)的基本單位。(V )3 .順序存儲(chǔ)的線性表可以隨機(jī)存取。(V )4 .線性表中的元素可以是各種各樣的，但同一線性表中的數(shù)據(jù)元素具有相同的特性，因

30、此，是屬于同一數(shù)據(jù)對(duì)象。(x )5 在單鏈表中，任何兩個(gè)元素的存儲(chǔ)位置之間都有固定的聯(lián)系，因?yàn)榭梢詮念^結(jié)點(diǎn)查找任何一個(gè)元素。(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.由樹轉(zhuǎn)換成二叉樹，其根結(jié)點(diǎn)的右子樹總是空的。(X )12.后序遍歷樹和中序遍歷與該樹對(duì)應(yīng)的二叉樹，其結(jié)果不同。(

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

32、列表的查找效率取決于散列表造表時(shí)選取的散列函數(shù)和處理沖突的方法。(V )21. m 階B-樹每一個(gè)結(jié)點(diǎn)的子樹個(gè)數(shù)都小于或等于m(V )22.中序遍歷二叉排序樹的結(jié)點(diǎn)就可以得到排好序的結(jié)點(diǎn)序列。(V )23.在二叉排序樹上插入新的結(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(nlog2 n)(V )26.對(duì)于n個(gè)記錄的集合進(jìn)行歸并排序，所需要的平均時(shí)間是O(nlog2 n)(V )27.堆中所有非

33、終端結(jié)點(diǎn)的值均小于或等于(大于或等于)左右子樹的值。(X )28.磁盤上的順序文件中插入新的記錄時(shí)，必須復(fù)制整個(gè)文件。(X )29.在索引順序文件中插入新的記錄時(shí)，必須復(fù)制整個(gè)文件。(X )30.索引順序文件是一種特殊的順序文件，因此通常存放在磁帶上。四、簡答題。(共6小題，每小題約5分，共32分)1. 簡述下列術(shù)語：數(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ī)程序中

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

35、點(diǎn)：棧和隊(duì)列都是特殊的線性表，只在端點(diǎn)處進(jìn)行插入，刪除操作。不同點(diǎn)：棧只在一端(棧頂)進(jìn)行插入，刪除操作；隊(duì)列在一端(top )刪除，一端(rear)插入。4. 如果進(jìn)棧的元素序列為 A, B, C, D,則可能得到的出棧序列有多少種？寫出全部的可能序列。答：可能序列有 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的出棧序列？并說明為什么不能得到或如何得到。答：不能得

36、到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(),push(4), push(5), pop(), pop(),pop(), push (6), pop() ?！癎OO” , q= “WORKER。求：StrLength (s) , StrLength(t) , SubStr( s, 8,7) , SubStr(t , 2, 1), StrIndex(s,A” ) , StrIndex (s ,t) , StrRe

37、p(s，“ STUDENT , q) , SubStr (SubStr (s 答：StrLength (s)=14, StrLength (t)=4, SubStr( sStrIndex(s,“A” )=3, StrIndex (s, t)=0, StrRep(s,6 , 2) , StrC on cat (t , SubStr(s , 7 , 8)。,8 , 7)= ” STUDENT , SubStr(t , 2 , 1)=” O”“STUDENT, q)= ” I AM A WORKER”6. 設(shè) s= “ I AM A STUDENT” ,t=7. 簡述下列每對(duì)術(shù)語的區(qū)別：空串和空格串

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

39、88(2) 1000+47*6=1282(3) 1000+(8+4)*8=1096(4) 1000+(6*7+4)*8=13689. 分別畫出含三個(gè)結(jié)點(diǎn)的無序樹與二叉樹的所有不同形態(tài)。 答：無序樹形態(tài)如下：二叉樹形態(tài)如下：10. 分別寫出圖1中所示二叉樹的先序遍歷、中序遍歷、后序遍歷的結(jié)點(diǎn)訪問序列。BCDE FGHI)圖1J答：先序遍歷序列：ABDEHICFJG中序遍歷序列：DBHEIAFJCG后序遍歷序列：DHIEBJFGCA11. 試找出分別滿足下列條件的所有二叉樹。(1) 先序序列與中序序列相同。(2) 后序序列與中序序列相同?？諛浠蛉弊笞訕涞膯沃?； 空樹或缺右子樹的單支樹； 空樹或只

40、有根結(jié)點(diǎn)的二叉樹。(3) 先序序列與后序序列相同。答：(1)先序序列和中序序列相同:(2) 后序序列和中序序列相同:(3) 先序序列和后序序列相同:12. 已知一棵二叉樹的中序序列和后序序列分別為BDCEAFH和 DECBHGFA試畫出這棵二叉樹。答：這棵二叉樹為13. 分別寫出圖2中所示二叉樹的先序遍歷、中序遍歷、后序遍歷的結(jié)點(diǎn)訪問序列。BDEFGHH2答：先序遍歷序列：ABDGCEHF中序遍歷序列：DGBAEHCF后序遍歷序列：GDBHEFCA14. 給定權(quán)值(7,18,3,32,5,26,12,8)，構(gòu)造的哈夫曼樹。答：哈夫曼樹為：1114665，試為這815. 假設(shè)用于通信的電文僅由8

41、個(gè)字母組成，字母在電文中出現(xiàn)的頻率分別為7,19,2,6,32,3,21,10個(gè)設(shè)計(jì)哈夫曼編碼。答：哈夫曼樹為：在上述哈夫曼樹的每個(gè)左分支上標(biāo)以0，右分支上標(biāo)以1并設(shè)這8個(gè)字母分別為 AB、CD、E、F、G和H,則它們的哈夫曼樹為分別為：A: 0000 B : 10 C : 00110 D : 0010 E : 01 F : 00111 G : 11 H : 000116. 畫出無向圖G1的鄰接矩陣和鄰接表示意圖，并寫出每個(gè)頂點(diǎn)的度。0 111010 0 11M=10001110 0 10 1110(2)鄰接鏈表:(3)每個(gè)頂點(diǎn)的度：頂點(diǎn)度V1 3V2 3V3 2V4 3V5 317. 畫出有向圖G2的鄰接矩陣、鄰接表和逆鄰接表示意圖，并寫出每個(gè)頂點(diǎn)的入度和出度。答：（1）鄰接鏈表:VIAV2V3V4V5V63oF、40A1A42ZJ