1、、選擇題。 (每小題 2 分，共 40分)(1) 計算機識別 . 存儲和加工處理的對象被統稱為 AA. 數據 B. 數據元素C. 數據結構 D. 數據類型(2)數據結構通常是研究數據的及它們之間的聯系。A. 存儲和邏輯結構B.存儲和抽象C.理想和抽象D.理想與邏輯(3)不是數據的邏輯結構是A. 散列結構B.線性結構C. 樹結構D.圖結構B. 靜態結構與動態結構D. 緊湊結構與非緊湊結構 B 方面的內容。并行性時空復雜度_。B. 正確性和簡明性數據復雜性和程序復雜性的有限序列(nz 0)B.字符D. 數據項 數據結構被形式地定義為D,R,其中D是B的有限集，R是C的有限集。A. 算法B.數據元素

2、C. 數據操作D.邏輯結構(5) 組成數據的基本單位是 A 。A. 數據項B.數據類型C. 數據元素D.數據變量 設數據結構 A=(D，R)，其中 D=1，2，3，4，R=r，r=1，2，2，3，3，4，4，1，則數據結構 A 是 A 。A. 線性結構B.樹型結構C. 圖型結構D.集合(7) 數據在計算機存儲器內表示時，物理地址與邏輯地址相同并且是連續的，稱之為_ CA. 存儲結構B.邏輯結構C. 順序存儲結構D.鏈式存儲結構(8) 在數據結構的討論中把數據結構從邏輯上分為 _ AA. 內部結構與外部結構C.線性結構與非線性結構(9) 對一個算法的評價，不包括如下A. 健壯性和可讀性B.C.

3、正確性D.(10) 算法分析的兩個方面是 _ AA. 空間復雜性和時間復雜性C. 可讀性和文檔性D.(11) 線性表是具有 n 個_ C _A. 表元素C. 數據元素(12) 線性表的存儲結構是一種 B 的存儲結構。A. 隨機存取B.順序存取C. 索引存取D.HASH存取A.n-iB.n-i+1C.n-i-1D.i鏈表是一種采用A. 順序 B 存儲結構存儲的線性表；B.鏈式C. 星式D.網狀(14)(15)(16) 結點(17)(18)(19)(20)(21)(22)(23)(13) 在一個長度為個元素。的順序表中，向第i個元素(K i next=p-next ； p-next=-s ；B.

4、q-next=s ； s-next=p ；C. p-next=s-next； s-next=p ；D. p-next=s ；s-next=q ；設指針變量p指向單鏈表結點A，則刪除結點A的后繼結點B需要的操作為_ AA. p-n ext=p-n ext- nextB. p=p-nextC. p=p-next-nextD. p-next=p下列說法哪個正確？ D _A. 堆棧是在兩端操作、先進后出的線性表B. 堆棧是在一端操作、先進先出的線性表C. 隊列是在一端操作、先進先出的線性表D. 隊列是在兩端操作、先進先出的線性表棧和隊列的共同點是 C 。A. 都是先進后出B.都是先進先出pl, p2,

5、 p3,pn，若 p1=n，則 pi 為C. 只允許在端點處插入和刪除元素 D. 沒有共同點A、兀素個數B、兀素類型C 、邏輯結構D、插入、刪除元素的位置鏈棧與順序棧相比,比較明顯的優點是D。A、插入操作更加方便B刪除操作更加方便C不會出現下溢的情況D不會出現上溢的情況以下數據結構中哪一個是非線性結構_ D 。A. 隊列B. 棧C. 線性表D. 二叉樹棧與一般線性表的區別主要在 D若已知一個棧的入棧序列是1, 2, 3,，n,其輸出序列為A. iB. B. n=iC. n-i+1D.不確定(24) 當利用大小為 N 的一維數組順序存儲一個棧時，假定用top=N 表示棧空,則向這個棧插入一個元素

6、時,首先應執行語句修改 top 指針。A. top+B. top-C. top=0D. top(25)A. AB. BC. CD. D4 個元素進 S 棧的順序是 A,B,C,D ，經運算 POP(S) 后，棧頂元素是(26)A. edcbaB. decbaC. dceabD. abcde(27)設輸入序列是1、2、3、n,經過棧的作用后輸出序列的第一個元素是n,則輸出序列中第i個輸出元素A. n-iB. n-1-iC. n+1-iD. 不能確定(28) 字符 A 、B、 字符串？C、D 依次進入一個棧，按出棧的先后順序組成不同的字符串，至多可以組成B _個不同的A. 15B. 14C. 16

7、D. 21(29) 設指針變量top 指向當前鏈式棧的棧頂，則刪除棧頂元素的操作序列為A. top=top+1;B. top=top-1;C. top-next=top;D. top=top-next;一個棧的輸入序列是a,b,c,d,e,則棧的不可能的輸出序列是(30)設棧S和隊列Q的初始狀態為空，元素E1、E2、E3、E4、E5和E6依次通過棧S，個元素出棧后即進入隊列Q，若6個元素出列的順序為E2、E4、E3、E6、E5和E1，則棧S的容量至少應該是 C。A. 6B. 4C. 3D. 2(31) 若用一個大小為6 的數組來實現循環隊列,且當前rear和front的值分別為0和3。當從隊列

8、中刪除一個兀素,再加入兩個元素后,rear和front的值分別為_ B _。A. 1 和 5B. 2 和 4C. 4 和 2D. 5 和 1(32) 設順序循環隊列Q0 : M-1的頭指針和尾指針分別為F和R,頭指針F總是指向隊頭兀素的前一位置，尾指針R總是指向隊尾元素的當前位置，則該循環隊列中的元素個數為C。A. R-FB. F-RC. (R-F+M)%MD. (F-R+M)%M(33) 設指針變量front表示鏈式隊列的隊頭指針，指針變量rear表示鏈式隊列的隊尾指針，指針變量s指向將要入隊列的結點X，則入隊列的操作序列為_A. front-next=s ； front=s ；C. rea

9、r-next=s ； rear=s ；(34) 如下陳述中正確的是 _ A A. 串是一種特殊的線性表C. 串中元素只能是字母(35) 下列關于串的敘述中,正確的是 _A. 串長度是指串中不同字符的個數_ C 。B. s-next=rear ； rear=s ；D. s-next=front；front=s ；B. 串的長度必須大于零D. 空串就是空白串D 。B. 串是 n 個字母的有限序列C. 如果兩個串含有相同的字符,則它們相等D. 只有當兩個串的長度相等,并且各個對應位置的字符都相符時才相等(36) 字符串的長度是指 _ C 。A. 串中不同字符的個數C. 串中所含字符的個數B. 串中不

10、同字母的個數D. 串中不同數字的個數(37) 兩個字符串相等的充要條件是A. 兩個字符串的長度相等 C 。B. 兩個字符串中對應位置上的字符相等C. 同時具備 (A) 和 (B) 兩個條件D. 以上答案都不對(38) 串是一種特殊的線性表，其特殊性體現在 B A. 可以順序存儲B. 數據元素是一個字符C. 可以鏈接存儲D. 數據元素可以是多個字符(39) 設有兩個串p和q,求q在p中首次出現的位置的運算稱作 B。A. 連接B. 模式匹配C. 求子串D. 求串長(40) 設串sl=ABCDEFG,s2=PQRST,函數con(x,y)返回x和y串的連接串，subs(s,i,j)返回串s的從序號i

11、的字符開始的j個字符組成的子串，len(s)返回串s的長度，貝U con(subs(s1,2,1en(s2)，subs(sl,len(s2)，2)的結果串是 _DA. BCDEFB. BCDEFGC. BCPQRSTD. BCDEFEF(41) 函數 substr(“DATASTRUCTURE ”, 5, 9)的返回值為 _ A 。A. “ STRUCTUR”EB. “ DATA”C. “ASTRUCTU”RD. “DATASTRUCTU”RE(42) 設串 S=”l AM A TEACHER! ”,其長度是 D 。A. 16B. 11C. 14D. 15(43) 假定在一棵二叉樹中,雙分支結

12、點數為 15 個,單分支結點數為 32 個,貝葉子結點數為 B 。A. 15 B. 16 C. 17 D. 47(44) 假定一棵二叉樹的結點數為 18個,貝它的最小高度 B 。A. 4 B. 5 C. 6 D. 18(45) 在一棵二叉樹中第五層上的結點數最多為 C 。A. 8 B. 15 C. 16 D. 32(46) 在一棵具有五層的滿二叉樹中,結點總數為 A 。A. 31 B. 32 C. 33 D. 16(47) 已知 8 個數據元素為 (34、76、45、18、26、54、92、65),按照依次插入結點的方法生成一棵二叉排序樹后,最后兩層上的結點總數為 B 。A. 1B. 2 C.

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

14、/2 B. 1 C. 2 D. 4(52) 具有 n 個頂點的無向完全圖，邊的總數為 D條。A. n-1B. nC. n+1D. n*(n-1)/2(53) 在無向圖 G 的鄰接矩陣 A 中，若 Ai,j 等于 1，則 Aj,i 等于C 。A. i+jB. i-jC. 1D. 0(54) 圖的深度優先或廣度優先遍歷的空間復雜性均為 A 。 (訪問標志位數組空間 )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中，用折半法查找關鍵碼 12需做 C次關鍵碼比較。A.2 B.3

15、 C.4 D.5(56) 對線性表進行折半查找時，必須要求線性表 C 。A. 以順序方式存儲 B. 以鏈接方式存儲C. 以順序方式存儲，且結點按關鍵字有序排列D. 以鏈接方式存儲，且結點按關鍵字有序排列(57) 設二叉排序樹中有 n 個結點，則在二叉排序樹的平均查找長度為_ B 。2A. O(1)B. O(log 2n)C. O(n) D. O(n 2)(58) 依次插入序列 (50，72，43，85，75，20，35，45，65，30)后建立的二叉搜索樹中， 查找元素 35 要進行 _A 元素間的比較。A.4 次B.5 次C.7(59)設散列表中有m 個存儲單元，散列函數H(key)=A.小

16、于等于B.小于等于m的最大奇數C.小于等于m的最大偶數D.小于等于(60)_ D 是 HASH 查找的沖突處理方法。A.求余法 B. 平方取中法C. 二分法 D.(61)當a的值較小時，散列存儲通常比其他存儲方式具有A.較慢B. 較快C. 相同m的最大素數m的最大合數開放地址法對線性表進行折半查找最方便的存儲結構是(62)次D. 不確定key % p ，則 p 最好選擇 _ BD.10 次的查找速度。A.順序表有序的順序表C.鏈表.有序的鏈表(63) 如果要求一個線性表既能較快的查找，又能適應動態變化的要求，可以采用 D 查找方法。A分塊 B .順序 C .折半 D .散列(64) 散列函數有

17、一個共同性質，即函數值應按 _ C 取其值域的每一個值。A.最大概率 B .最小概率C .同等概率D .平均概率(65) 下述排序算法中，穩定的是 _ B 。A.直接選擇排序B.直接插入排序C.快速排序 D.堆排序(66) 下列排序算法中， A 需要的輔助存儲空間最大。A. 快速排序 B. 插入排序C. 希爾排序D. 基數排序(67) 下列各種排序算法中平均時間復雜度為0( n2)是_ D。A. 快速排序B. 堆排序C. 歸并排序 D. 冒泡排序(68)在基于關鍵碼比較的排序算法中,.算法在最壞情況下，關鍵碼比較次數不高于O(nlog2n)。(69)(70)(71)(72)(73)A.起泡排序

18、B.直接插入排序C.二路歸并排序D.快速排序一組記錄為46， 79,A. 46,79,56,38,40,84C. 38,40,46,56,84,7956 , 38, 84, 40，則采用冒泡排序法按升序排列時第一趟排序結果是B. 46,56,38,79,40,84D. 38,46,79,56,40,84每次從無序表中取出一個元素，把它插入到有序表中的適當位置，此種排序方法叫做A.插入 B.堆 C. 快速D. 歸并排序。每次從無序表中挑選出一個最小或最大元素,把它交換到有序表的一端，此種排序方法叫做排序。A.插入 B.C. 快速D. 歸并設一組初始記錄關鍵字序列A. 2 ， 3， 5,C. 3，

19、 2， 5,F列排序方法中,8，66，8(5，2，6,B. 3，D. 2，8)，以第一個記錄關鍵字 5為基準進行一趟快速排序的結果為5，8，66，5，8哪一種方法的比較次數與紀錄的初始排列狀態無關A.直接插入排序B.起泡排序c快速排序D.直接選擇排序(74)是采用C.以第一元素為分界元素的快速排序D .基數排序設有關鍵碼初始序列Q , H , C, Y , P, A,M,S,R,D,F,X，新序列F , H , C, D, P, A , M , Q, R, S, Y,X 方法對初始序列進行第一趟掃描的結果。二路歸并排序A.直接插入排序(75)A.直接插入排序B.直接選擇排序在待排序文件已基本有

20、序的前提下，下述排序方法中效率最咼的是歸并排序C. 快速排序(76)若需在O(nlog2n)的時間內完成對數組的排序，且要求排序是穩定的，則可選排序方法是A.快速排序B . 堆排序C.歸并排序D直接插入排序(77)(78)A.n B2n-1 C2n Dn-1F列排序算法中,算法可能會出現下面情況：初始數據有序時，花費的間反而最多。A. 堆排序B.冒泡排序C.快速排序D . SHELL 排序將兩個各有n個元素的有序表歸并成一個有序表，其最少的比較次數是二、填空題。(每空1分，共10分)(1) 數據結構是一門研究非數值計算的程序設計問題中計算機的 數據以及它們之間的關系和運算等的學科。(2) 數據

21、結構包括數據的 邏輯結構 結構和 物理結構 結構。(3)數據結構從邏輯上劃分為三種基本類型:線性數據結構樹型結構圖結構(4)數據的物理結構被分為 存儲順序存儲鏈式存儲索引存儲.散列表(Hash)四種。(5) 一種抽象數據類型包括變量的取值范圍和操作的類別兩個部分。(6)數據的邏輯結構是指數據元素間的邏輯關系，數據的存儲結構是指數據元素存儲方式或者數據元素的物理關系(7)數據結構是指數據及其相互之間的關系。當結點之間存在 M對N (M : N )的聯系時，稱這種結構為網狀結構。當結點之間存在1對N( 1 :N)的聯系時，稱這種結構為樹結構(8)對算法從時間和空間兩方面進行度量，分別稱為空間復雜度

22、和時間復雜度分析。(9)算法的效率可分為空間效率和時間效率。(10) for(i=1 , t=1 , s=0; i1)的各棵樹中，高度最小的樹的高度是多少 ？它有多少個葉結點？多少個分支結點？高度最大的 樹的高度是多少？它有多少個葉結點？多少個分支結點？答：結點個數為n時，高度最小的樹的高度為1,有兩層，它有n-1個葉結點，1個分支結點；高度最大的樹的高度為n-I ,有n層，它有1個葉結點，n-1個分支結點。24. 什么是內部排序？什么是排序方法的穩定性 ？答：假定給定含有 n個記錄的文件(r1 , r2，rn)，其相應的關鍵字為(k1 , k2，kn)，則排序就是確定文件 的一個序列r1 ,

23、 r2，rn，使得k1 k2kn，從而使得文件中 n個記錄按其對應關鍵字有序排列。如果整 個排序過程在內存中進行，則排序叫內部排序。假設在待排序的文件中存在兩個或兩個以上的記錄具有相同的關鍵字，若采用某種排序方法后，使得這些具有相同 關鍵字的記錄在排序前后相對次序依然保持不變，則認為該排序方法是穩定的，否則就認為排序方法是不穩定的。五、分析題。 （每小題 4 分，共 8分）1. 分析下面語句段執行的時間復雜度。(1) for(i= 1 ； i = n；i+)for(j= 1 ； j = n； j+)s+(2) for(i= 1 ；i = n；i+)for(j= i ； j = n； j+)s+；(3) for(i= 1 ；i = n；