1、一、選擇題。(每小題2分，共40分)(1) 計算機識別.存儲和加工處理的對象被統(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ù)項 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ù)在計算機存儲器內(nèi)表示時，物理地址與邏輯地址相同并且是連續(xù)的，稱之為_ C _。A.存儲結(jié)構(gòu) B.邏輯結(jié)構(gòu) C.順序存儲結(jié)構(gòu) D.鏈式存儲結(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) 對一個算法的評價，不包括如下_ B _方面的內(nèi)容。A.健壯性和可讀性 B.并行性 C.正確性 D.時空復(fù)雜度(10) 算法分析的兩個方面是_ A _。

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

4、的是_ D _。A.線性表采用順序存儲必須占用一片連續(xù)的存儲空間B.線性表采用鏈式存儲不必占用一片連續(xù)的存儲空間C.線性表采用鏈式存儲便于插入和刪除操作的實現(xiàn)D.線性表采用順序存儲便于插入和刪除操作的實現(xiàn)(16) 設(shè)指針q指向單鏈表中結(jié)點A，指針p指向單鏈表中結(jié)點A的后繼結(jié)點B，指針s指向被插入的結(jié)點X，則在結(jié)點A和結(jié)點B之間插入結(jié)點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é)點A，則刪除

5、結(jié)點A的后繼結(jié)點B需要的操作為_ A _。A. p-next=p-next-next B. p=p-nextC. p=p-next-next D. p-next=p(18) 下列說法哪個正確？_ D _A. 堆棧是在兩端操作、先進后出的線性表B. 堆棧是在一端操作、先進先出的線性表C. 隊列是在一端操作、先進先出的線性表D. 隊列是在兩端操作、先進先出的線性表(19) 棧和隊列的共同點是_ C _。A. 都是先進后出 B. 都是先進先出C. 只允許在端點處插入和刪除元素 D. 沒有共同點(20) 棧與一般線性表的區(qū)別主要在_D_。A、元素個數(shù) B、元素類型 C、邏輯結(jié)構(gòu) D、插入、刪除元素的位

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

7、top(25) 4個元素進S棧的順序是A,B,C,D，經(jīng)運算POP(S)后，棧頂元素是_ C _。A. AB. BC. CD. D(26) 一個棧的輸入序列是a,b,c,d,e,則棧的不可能的輸出序列是_ C _。A. edcbaB. decbaC. dceabD. abcde(27) 設(shè)輸入序列是1、2、3、n，經(jīng)過棧的作用后輸出序列的第一個元素是n，則輸出序列中第i個輸出元素是_ C _。A. n-iB. n-1-iC. n+1-iD.不能確定(28) 字符A、B、C、D依次進入一個棧，按出棧的先后順序組成不同的字符串，至多可以組成_ B _個不同的字符串？A. 15B. 14C. 16D

8、. 21(29) 設(shè)指針變量top指向當前鏈式棧的棧頂，則刪除棧頂元素的操作序列為_ D _。A. top=top+1; B. top=top-1; C. top-next=top; D. top=top-next; (30) 設(shè)棧S和隊列Q的初始狀態(tài)為空，元素E1、E2、E3、E4、E5和E6依次通過棧S，一個元素出棧后即進入隊列Q，若6個元素出列的順序為E2、E4、E3、E6、E5和E1，則棧S的容量至少應(yīng)該是_ C _。A. 6B. 4C. 3D. 2(31) 若用一個大小為6的數(shù)組來實現(xiàn)循環(huán)隊列，且當前rear和front的值分別為0和3。當從隊列中刪除一個元素，再加入兩個元素后，re

9、ar和front的值分別為_ B _。A. 1和5B. 2和4C. 4和2D. 5和1(32) 設(shè)順序循環(huán)隊列Q0：M-1的頭指針和尾指針分別為F和R，頭指針F總是指向隊頭元素的前一位置，尾指針R總是指向隊尾元素的當前位置，則該循環(huán)隊列中的元素個數(shù)為_ C _。A. R-FB. F-RC. (R-F+M)%MD. (F-R+M)%M(33) 設(shè)指針變量front表示鏈式隊列的隊頭指針，指針變量rear表示鏈式隊列的隊尾指針，指針變量s指向?qū)⒁腙犃械慕Y(jié)點X，則入隊列的操作序列為_ 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. 串長度是指串中不同字符的個數(shù)B. 串是n個字母的有限序列C. 如果兩個串含有相同的字符，則它們相等D. 只有當兩個串的長度相等，并且各個對應(yīng)位置的字符都相符時才相等(36) 字符串的長度是指_ C _。A. 串中不同字符的個數(shù)B. 串中不同字母的個數(shù)C. 串中所含字符的個數(shù)D. 串中不同數(shù)字的個數(shù) (37) 兩個字符串相等的充要條

11、件是_ C _。A. 兩個字符串的長度相等B. 兩個字符串中對應(yīng)位置上的字符相等C. 同時具備(A)和(B)兩個條件 D. 以上答案都不對(38) 串是一種特殊的線性表，其特殊性體現(xiàn)在_ B _。A. 可以順序存儲B. 數(shù)據(jù)元素是一個字符C. 可以鏈接存儲D. 數(shù)據(jù)元素可以是多個字符(39) 設(shè)有兩個串p和q，求q在p中首次出現(xià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個字符組成的子串，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é)點數(shù)為15個，單分支結(jié)點數(shù)為32個，則葉子結(jié)點數(shù)為_B_。

13、A. 15 B. 16 C. 17 D. 47(44) 假定一棵二叉樹的結(jié)點數(shù)為18個，則它的最小高度_B_。A. 4 B. 5 C. 6 D. 18(45) 在一棵二叉樹中第五層上的結(jié)點數(shù)最多為_C_。A. 8 B. 15 C. 16 D. 32(46) 在一棵具有五層的滿二叉樹中，結(jié)點總數(shù)為_A_。A. 31 B. 32 C. 33 D. 16(47) 已知8個數(shù)據(jù)元素為(34、76、45、18、26、54、92、65)，按照依次插入結(jié)點的方法生成一棵二叉排序樹后，最后兩層上的結(jié)點總數(shù)為_B_。A. 1 B. 2 C. D. 4(48) 由分別帶權(quán)為9、2、5、7的四個葉子結(jié)點構(gòu)造一棵哈夫

14、曼樹，該樹的帶權(quán)路徑長度為_C_。 A. 23 B. 37 C. 44 D. 46(49) 在樹中除根結(jié)點外，其余結(jié)點分成m (m0)個_A _的集合T1,T2,T3.Tm,每個集合又都是樹，此時結(jié)點T稱為Ti的父結(jié)點，Ti稱為T的子結(jié)點(1im)。A. 互不相交 B. 可以相交 C. 葉結(jié)點可以相交 D. 樹枝結(jié)點可以相交(50) 如果結(jié)點A有三個兄弟，而且B是A的雙親，則B的出度是_B_。A. 3 B. 4 C. 5 D. 1(51) 在一個有向圖中，所有頂點的入度之和等于所有頂點的出度之和的_B_倍。A. 1/2 B. 1 C. 2 D. 4(52) 具有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_ 。(訪問標志位數(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) 對線性表進行折半查找時，必須要求線性表 _ C _。A. 以順序方式存

16、儲 B. 以鏈接方式存儲C. 以順序方式存儲，且結(jié)點按關(guān)鍵字有序排列D. 以鏈接方式存儲，且結(jié)點按關(guān)鍵字有序排列(57) 設(shè)二叉排序樹中有n個結(jié)點，則在二叉排序樹的平均查找長度為_ 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要進行_ A _元素間的比較。A.4次B.5次C.7次D.10次(59) 設(shè)散列表中有m個存儲單元，散列函數(shù)H(key)= key % p，則p最好選擇_ B _。A. 小于等于m的最大奇數(shù)B. 小于等于m的最大素數(shù)C.

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

18、小概率 C同等概率 D平均概率(65) 下述排序算法中，穩(wěn)定的是_ B _。A.直接選擇排序 B. 直接插入排序 C.快速排序 D.堆排序 (66) 下列排序算法中，_ A _需要的輔助存儲空間最大。A.快速排序B.插入排序C.希爾排序D.基數(shù)排序(67) 下列各種排序算法中平均時間復(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，則采用冒泡排序法按升序排列時第一趟排序結(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) 每次從無序表中取出一個元素，把它插入到有序表中的適當位置，此種排序方法叫做_ A _ 排序。A. 插入 B. 堆 C.快速 D.歸并(71) 每次從無序表中挑選出一個最小或最大元素，把它交換到有序表的一端，此種排序方法叫做_ B _排序。A. 插入 B. 堆 C.快速 D.歸并(72) 設(shè)一組初始記錄關(guān)鍵字序列(5，2，6，3，8)，以第一個記錄關(guān)鍵字5為基準進行一

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ù)與紀錄的初始排列狀態(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 _ 方法對初始序列進行第一趟掃描的結(jié)果。A. 直接插入排序 B二路歸并排序C以第一元素為分界元素的快速排序 D基數(shù)排序(75) 在待排序文件已基本有序的前提下，下述排序方法中效率最高

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

22、設(shè)計問題中計算機的 數(shù)據(jù) 以及它們之間的 關(guā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)被分為_順序存儲_、_鏈式存儲_、_索引存儲_和_散列表（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)系 。(7) 數(shù)據(jù)結(jié)構(gòu)是指數(shù)據(jù)及其相互之間的_關(guān)系_。當結(jié)點之間存在M對N（M：N）的聯(lián)系時，稱這種結(jié)構(gòu)為_網(wǎng)

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