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

1、一、選擇題。(每小題2分，共40分)(1) 計(jì)算機(jī)識別.存儲和加工處理的對象被統(tǒng)稱為_a_。a.數(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.存儲和邏輯結(jié)構(gòu) b.存儲和抽象 c.理想和抽象 d.理想與邏輯(3) 不是數(shù)據(jù)的邏輯結(jié)構(gòu)是_ a _。a.散列結(jié)構(gòu) b.線性結(jié)構(gòu) c.樹結(jié)構(gòu) d.圖結(jié)構(gòu) (4) 數(shù)據(jù)結(jié)構(gòu)被形式地定義為,其中d是_ b _的有限集，r是_ c _的有限集。a.算法 b.數(shù)據(jù)元素 c.數(shù)據(jù)操作 d.邏輯結(jié)構(gòu)(5) 組成數(shù)據(jù)的基本單位是_ a _。 a.數(shù)據(jù)項(xiàng) b.數(shù)據(jù)類型c.數(shù)據(jù)元素 d.數(shù)據(jù)變量(6) 設(shè)數(shù)據(jù)

2、結(jié)構(gòu)a=(d，r)，其中d=1，2，3，4，r=r，r=，則數(shù)據(jù)結(jié)構(gòu)a是_ a _。a.線性結(jié)構(gòu) b.樹型結(jié)構(gòu) c.圖型結(jié)構(gòu) d.集合(7) 數(shù)據(jù)在計(jì)算機(jī)存儲器內(nèi)表示時(shí)，物理地址與邏輯地址相同并且是連續(xù)的，稱之為_ c _。a.存儲結(jié)構(gòu) b.邏輯結(jié)構(gòu) c.順序存儲結(jié)構(gòu) d.鏈?zhǔn)酱鎯Y(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)與動態(tài)結(jié)構(gòu)c.線性結(jié)構(gòu)與非線性結(jié)構(gòu) d.緊湊結(jié)構(gòu)與非緊湊結(jié)構(gòu)(9) 對一個(gè)算法的評價(jià)，不包括如下_ b _方面的內(nèi)容。a.健壯性和可讀性 b.并行性 c.正確性 d.時(shí)空復(fù)雜度(10) 算法分析的兩個(gè)方面是_ a _。

3、a.空間復(fù)雜性和時(shí)間復(fù)雜性 b.正確性和簡明性c.可讀性和文檔性 d.數(shù)據(jù)復(fù)雜性和程序復(fù)雜性(11) 線性表是具有n個(gè)_ c _的有限序列（n0)。a.表元素 b.字符 c.數(shù)據(jù)元素 d.數(shù)據(jù)項(xiàng)(12) 線性表的存儲結(jié)構(gòu)是一種_ b _的存儲結(jié)構(gòu)。a.隨機(jī)存取 b.順序存取 c.索引存取 d.hash存取(13) 在一個(gè)長度為n 的順序表中，向第i個(gè)元素（1 i n）之前插入一個(gè)新元素時(shí)，需要向后移動_ b _個(gè)元素。a.n-i b.n-i+1 c.n-i-1 d.i(14) 鏈表是一種采用_ b _存儲結(jié)構(gòu)存儲的線性表；a.順序 b.鏈?zhǔn)?c.星式 d.網(wǎng)狀(15) 下面關(guān)于線性表的敘述錯(cuò)誤

4、的是_ d _。a.線性表采用順序存儲必須占用一片連續(xù)的存儲空間b.線性表采用鏈?zhǔn)酱鎯Σ槐卣加靡黄B續(xù)的存儲空間c.線性表采用鏈?zhǔn)酱鎯Ρ阌诓迦牒蛣h除操作的實(shí)現(xiàn)d.線性表采用順序存儲便于插入和刪除操作的實(shí)現(xiàn)(16) 設(shè)指針q指向單鏈表中結(jié)點(diǎn)a，指針p指向單鏈表中結(jié)點(diǎn)a的后繼結(jié)點(diǎn)b，指針s指向被插入的結(jié)點(diǎn)x，則在結(jié)點(diǎn)a和結(jié)點(diǎn)b之間插入結(jié)點(diǎn)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) 設(shè)指針變量p指向單鏈表結(jié)點(diǎn)a，則刪除

5、結(jié)點(diǎn)a的后繼結(jié)點(diǎn)b需要的操作為_ a _。a. p-next=p-next-next b. p=p-nextc. p=p-next-next d. p-next=p(18) 下列說法哪個(gè)正確？_ d _a. 堆棧是在兩端操作、先進(jìn)后出的線性表b. 堆棧是在一端操作、先進(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、插入、刪除元素的位

6、置(21) 鏈棧與順序棧相比，比較明顯的優(yōu)點(diǎn)是_d_。a、插入操作更加方便 b、刪除操作更加方便c、不會出現(xiàn)下溢的情況 d、不會出現(xiàn)上溢的情況(22) 以下數(shù)據(jù)結(jié)構(gòu)中哪一個(gè)是非線性結(jié)構(gòu)_ d _。a.隊(duì)列b.棧c.線性表d.二叉樹(23) 若已知一個(gè)棧的入棧序列是1，2，3，n，其輸出序列為p1，p2，p3，pn，若p1=n，則pi為_ c _。a. ib. b. n=i c. n-i+1d.不確定(24) 當(dāng)利用大小為n的一維數(shù)組順序存儲一個(gè)棧時(shí)，假定用top=n表示?？?，則向這個(gè)棧插入一個(gè)元素時(shí)，首先應(yīng)執(zhí)行_ b _語句修改top指針。a. top+ b. top- c. top=0d.

7、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. n-1-ic. n+1-id.不能確定(28) 字符a、b、c、d依次進(jìn)入一個(gè)棧，按出棧的先后順序組成不同的字符串，至多可以組成_ b _個(gè)不同的字符串？a. 15b. 14c. 16d

8、. 21(29) 設(shè)指針變量top指向當(dāng)前鏈?zhǔn)綏５臈ｍ敚瑒t刪除棧頂元素的操作序列為_ d _。a. top=top+1; b. top=top-1; c. top-next=top; d. top=top-next; (30) 設(shè)棧s和隊(duì)列q的初始狀態(tài)為空，元素e1、e2、e3、e4、e5和e6依次通過棧s，一個(gè)元素出棧后即進(jìn)入隊(duì)列q，若6個(gè)元素出列的順序?yàn)閑2、e4、e3、e6、e5和e1，則棧s的容量至少應(yīng)該是_ c _。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è)元素后，re

9、ar和front的值分別為_ b _。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ù)為_ c _。a. r-fb. f-rc. (r-f+m)%md. (f-r+m)%m(33) 設(shè)指針變量front表示鏈?zhǔn)疥?duì)列的隊(duì)頭指針，指針變量rear表示鏈?zhǔn)疥?duì)列的隊(duì)尾指針，指針變量s指向?qū)⒁腙?duì)列的結(jié)點(diǎn)x，則入隊(duì)列的操作序列為_ c _。a. front-next=s；front=s；b. s-next=rear；rear=s；c. rear

10、-next=s；rear=s；d. s-next=front；front=s；(34) 如下陳述中正確的是_ a _。a. 串是一種特殊的線性表b. 串的長度必須大于零c. 串中元素只能是字母d. 空串就是空白串(35) 下列關(guān)于串的敘述中，正確的是_ d _。a. 串長度是指串中不同字符的個(gè)數(shù)b. 串是n個(gè)字母的有限序列c. 如果兩個(gè)串含有相同的字符，則它們相等d. 只有當(dāng)兩個(gè)串的長度相等，并且各個(gè)對應(yīng)位置的字符都相符時(shí)才相等(36) 字符串的長度是指_ c _。a. 串中不同字符的個(gè)數(shù)b. 串中不同字母的個(gè)數(shù)c. 串中所含字符的個(gè)數(shù)d. 串中不同數(shù)字的個(gè)數(shù) (37) 兩個(gè)字符串相等的充要條

11、件是_ c _。a. 兩個(gè)字符串的長度相等b. 兩個(gè)字符串中對應(yīng)位置上的字符相等c. 同時(shí)具備(a)和(b)兩個(gè)條件 d. 以上答案都不對(38) 串是一種特殊的線性表，其特殊性體現(xiàn)在_ b _。a. 可以順序存儲b. 數(shù)據(jù)元素是一個(gè)字符c. 可以鏈接存儲d. 數(shù)據(jù)元素可以是多個(gè)字符(39) 設(shè)有兩個(gè)串p和q，求q在p中首次出現(xiàn)的位置的運(yùn)算稱作_ b _。a. 連接b. 模式匹配c. 求子串d. 求串長(40) 設(shè)串si=abcdefg,s2=pqrst,函數(shù)con(x,y)返回x和y串的連接串,subs(s,i,j)返回串s的從序號i的字符開始的j個(gè)字符組成的子串，len(s)返回串s的長度

12、，則con(subs(s1,2,1en(s2)，subs(sl,len(s2)，2)的結(jié)果串是_ d _。a. bcdefb. bcdefgc. bcpqrstd. bcdefef (41) 函數(shù)substr(“datastructure”，5，9)的返回值為_ a _。a. “structure” b. “data” c. “astructur” d. “datastructure”(42) 設(shè)串s=”i am a teacher!”，其長度是_ d _。a. 16b. 11c. 14d. 15(43) 假定在一棵二叉樹中，雙分支結(jié)點(diǎn)數(shù)為15個(gè)，單分支結(jié)點(diǎn)數(shù)為32個(gè)，則葉子結(jié)點(diǎn)數(shù)為_b_。

13、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ù)為_b_。a. 1 b. 2 c. d. 4(48) 由分別帶權(quán)為9、2、5、7的四個(gè)葉子結(jié)點(diǎn)構(gòu)造一棵哈夫

14、曼樹，該樹的帶權(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)(1im)。a. 互不相交 b. 可以相交 c. 葉結(jié)點(diǎn)可以相交 d. 樹枝結(jié)點(diǎn)可以相交(50) 如果結(jié)點(diǎn)a有三個(gè)兄弟，而且b是a的雙親，則b的出度是_b_。a. 3 b. 4 c. 5 d. 1(51) 在一個(gè)有向圖中，所有頂點(diǎn)的入度之和等于所有頂點(diǎn)的出度之和的_b_倍。a. 1/2 b. 1 c. 2 d. 4(52) 具有n個(gè)頂點(diǎn)的無向完全圖，邊的總數(shù)為

15、_ 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. 1 d. 0(54) 圖的深度優(yōu)先或廣度優(yōu)先遍歷的空間復(fù)雜性均為_a_ 。(訪問標(biāo)志位數(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中，用折半法查找關(guān)鍵碼12需做_ c _次關(guān)鍵碼比較。a.2 b.3 c.4 d.5 (56) 對線性表進(jìn)行折半查找時(shí)，必須要求線性表 _ c _。a. 以順序方式存

16、儲 b. 以鏈接方式存儲c. 以順序方式存儲，且結(jié)點(diǎn)按關(guān)鍵字有序排列d. 以鏈接方式存儲，且結(jié)點(diǎn)按關(guān)鍵字有序排列(57) 設(shè)二叉排序樹中有n個(gè)結(jié)點(diǎ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要進(jìn)行_ a _元素間的比較。a.4次b.5次c.7次d.10次(59) 設(shè)散列表中有m個(gè)存儲單元，散列函數(shù)h(key)= key % p，則p最好選擇_ b _。a. 小于等于m的最大奇數(shù)b. 小于等于m的最大素?cái)?shù)c.

17、 小于等于m的最大偶數(shù)d. 小于等于m的最大合數(shù)(60) _ d _是hash查找的沖突處理方法。a.求余法 b. 平方取中法 c. 二分法 d. 開放地址法(61) 當(dāng)?shù)闹递^小時(shí)，散列存儲通常比其他存儲方式具有_ b _的查找速度。a. 較慢b. 較快c. 相同 d. 不確定(62) 對線性表進(jìn)行折半查找最方便的存儲結(jié)構(gòu)是_ b _。a順序表 b有序的順序表c鏈表 d有序的鏈表(63) 如果要求一個(gè)線性表既能較快的查找，又能適應(yīng)動態(tài)變化的要求，可以采用_ d _查找方法。a分塊 b順序 c折半 d散列(64) 散列函數(shù)有一個(gè)共同性質(zhì)，即函數(shù)值應(yīng)按_ c _取其值域的每一個(gè)值。a最大概率 b最

18、小概率 c同等概率 d平均概率(65) 下述排序算法中，穩(wěn)定的是_ b _。a.直接選擇排序 b. 直接插入排序 c.快速排序 d.堆排序 (66) 下列排序算法中，_ a _需要的輔助存儲空間最大。a.快速排序b.插入排序c.希爾排序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，4

19、0，則采用冒泡排序法按升序排列時(shí)第一趟排序結(jié)果是_ b _ 。a. 46,79,56,38,40,84 b.46,56,38,79,40,84c. 38,40,46,56,84,79 d.38,46,79,56,40,84(70) 每次從無序表中取出一個(gè)元素，把它插入到有序表中的適當(dāng)位置，此種排序方法叫做_ a _ 排序。a. 插入 b. 堆 c.快速 d.歸并(71) 每次從無序表中挑選出一個(gè)最小或最大元素，把它交換到有序表的一端，此種排序方法叫做_ b _排序。a. 插入 b. 堆 c.快速 d.歸并(72) 設(shè)一組初始記錄關(guān)鍵字序列(5，2，6，3，8)，以第一個(gè)記錄關(guān)鍵字5為基準(zhǔn)進(jìn)行一

20、趟快速排序的結(jié)果為_ c _。a. 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)無關(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，p，a，m，q，r，s，y,x是采用_ c _ 方法對初始序列進(jìn)行第一趟掃描的結(jié)果。a. 直接插入排序 b二路歸并排序c以第一元素為分界元素的快速排序 d基數(shù)排序(75) 在待排序文件已基本有序的前提下，下述排序方法中效率最高

21、的是_ c _。a. 直接插入排序 b. 直接選擇排序c 快速排序 d 歸并排序(76) 若需在o(nlog2n)的時(shí)間內(nèi)完成對數(shù)組的排序，且要求排序是穩(wěn)定的，則可選排序方法是_ c _ 。a. 快速排序 b 堆排序c 歸并排序 d 直接插入排序(77) 將兩個(gè)各有n個(gè)元素的有序表歸并成一個(gè)有序表，其最少的比較次數(shù)是_ b _。a n b 2n-1 c 2n d n-1(78) 下列排序算法中，_ c _ 算法可能會出現(xiàn)下面情況：初始數(shù)據(jù)有序時(shí)，花費(fèi)的間反而最多。a. 堆排序 b冒泡排序 c快速排序 d shell排序二、填空題。(每空1分，共10分)(1) 數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計(jì)算的程序

22、設(shè)計(jì)問題中計(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)_、_樹型結(jié)構(gòu)_和_圖結(jié)構(gòu)_。(4) 數(shù)據(jù)的物理結(jié)構(gòu)被分為_順序存儲_、_鏈?zhǔn)酱鎯、_索引存儲_和_散列表（hash）存儲_四種。(5) 一種抽象數(shù)據(jù)類型包括_變量的取值范圍_和 _操作的類別_兩個(gè)部分。(6) 數(shù)據(jù)的邏輯結(jié)構(gòu)是指 數(shù)據(jù)元素間的邏輯關(guān)系 ，數(shù)據(jù)的存儲結(jié)構(gòu)是指 數(shù)據(jù)元素存儲方式或者數(shù)據(jù)元素的物理關(guān)系 。(7) 數(shù)據(jù)結(jié)構(gòu)是指數(shù)據(jù)及其相互之間的_關(guān)系_。當(dāng)結(jié)點(diǎn)之間存在m對n（m：n）的聯(lián)系時(shí)，稱這種結(jié)構(gòu)為_網(wǎng)

23、狀結(jié)構(gòu)_。當(dāng)結(jié)點(diǎn)之間存在1對n（1：n）的聯(lián)系時(shí)，稱這種結(jié)構(gòu)為_樹結(jié)構(gòu)_。(8) 對算法從時(shí)間和空間兩方面進(jìn)行度量，分別稱為 空間復(fù)雜度和時(shí)間復(fù)雜度 分析。(9) 算法的效率可分為_空間_效率和_時(shí)間_效率。(10) for(i=1，t=1，s=0；i1)的各棵樹中，高度最小的樹的高度是多少?它有多少個(gè)葉結(jié)點(diǎn)?多少個(gè)分支結(jié)點(diǎn)?高度最大的樹的高度是多少?它有多少個(gè)葉結(jié)點(diǎn)?多少個(gè)分支結(jié)點(diǎn)?答：結(jié)點(diǎn)個(gè)數(shù)為n時(shí)，高度最小的樹的高度為1，有兩層，它有n-1個(gè)葉結(jié)點(diǎn)，1個(gè)分支結(jié)點(diǎn)；高度最大的樹的高度為n-l，有n層，它有1個(gè)葉結(jié)點(diǎn)，n-1個(gè)分支結(jié)點(diǎn)。24. 什么是內(nèi)部排序?什么是排序方法的穩(wěn)定性?答：假定給定含有n個(gè)記錄的文件(r1，r2，rn)，其相應(yīng)的關(guān)鍵字為(k1，k2，kn)，則排序就是確定文件的一個(gè)序列r1，r2，rn，使得k1k2kn，從而使得文件中n個(gè)記錄按其對應(yīng)關(guān)鍵字有序排列。如果整個(gè)排序過程在內(nèi)存中進(jìn)行，則排序叫內(nèi)部排序。假設(shè)在待排序的文件中存在兩個(gè)或兩個(gè)以上的記錄具有相同的關(guān)鍵字，若采用某種排序方法后，使得這些具有相同關(guān)鍵字的記錄在排序前后相對次序依然保持不變，則認(rèn)為該排序方法是穩(wěn)定的，否則就認(rèn)為排序方法是不穩(wěn)定的。五、分析題。(每小題4分，共8分