數(shù)據(jù)結構考試試題庫含答案解析

1、數(shù)據(jù)結構習題集含答案錯誤! 未定義書簽。錯誤! 未定義書簽。錯誤 ! 未定義書簽。錯誤 ! 未定義書簽。錯誤 ! 未定義書簽。錯誤 ! 未定義書簽。錯誤 ! 未定義書簽。錯誤 ! 未定義書簽。錯誤 ! 未定義書簽。錯誤 ! 未定義書簽。錯誤 ! 未定義書簽。錯誤 ! 未定義書簽。錯誤 ! 未定義書簽。錯誤 ! 未定義書簽。錯誤 ! 未定義書簽。錯誤 ! 未定義書簽。錯誤 ! 未定義書簽。錯誤 ! 未定義書簽。錯誤 ! 未定義書簽。錯誤 ! 未定義書簽。錯誤 ! 未定義書簽。錯誤 ! 未定義書簽。錯誤 ! 未定義書簽。錯誤 ! 未定義書簽。錯誤 ! 未定義書簽。錯誤 ! 未定義書簽。錯誤 ! 未

2、定義書簽。錯誤 ! 未定義書簽。錯誤 ! 未定義書簽。錯誤 ! 未定義書簽。錯誤 ! 未定義書簽。目錄目錄 選擇題 第一章緒論 第二章 線性表 第三章 棧和隊列 第四章 串 第五章 數(shù)組和廣義表第六章 樹和二叉樹第七章 圖 第八章 查找 第九章 排序 簡答題 第一章緒論 第二章 線性表 第三章 棧和隊列 第四章 串 第五章 數(shù)組和廣義表第六章 樹和二叉樹第七章 圖 第八章 查找 第九章 排序 編程題 第一章緒論 第二章線性表 第三章 棧和隊列 第四章 串 第五章 數(shù)組和廣義表第六章 樹和二叉樹第七章 圖 第八章 查找 第九章 排序 A、某班級的學生成績表是數(shù)據(jù)元素， 日某班級的學生成績表是數(shù)據(jù)

3、對象， C某班級的學生成績表是數(shù)據(jù)對象， D某班級的學生成績表是數(shù)據(jù)元素，4. *數(shù)據(jù)結構是指（A ） 。A數(shù)據(jù)元素的組織形式C數(shù)據(jù)存儲結構5. 數(shù)據(jù)在計算機存儲器內表示時，A存儲結構C鏈式存儲結構6. 算法分析的目的是（ C ）A找出數(shù)據(jù)的合理性BC分析算法效率以求改進口7. 算法分析的主要方法（ A ） 。A、空間復雜度和時間復雜度C可讀性和文檔性選擇題第一章緒論1. 數(shù)據(jù)結構這門學科是針對什么問題而產(chǎn)生的？（ A ）A、針對非數(shù)值計算的程序設計問題B、針對數(shù)值計算的程序設計問題C數(shù)值計算與非數(shù)值計算的問題都針對D、兩者都不針對2. 數(shù)據(jù)結構這門學科的研究內容下面選項最準確的是（ D ）A

4、、研究數(shù)據(jù)對象和數(shù)據(jù)之間的關系B、研究數(shù)據(jù)對象C研究數(shù)據(jù)對象和數(shù)據(jù)的操作D、研究數(shù)據(jù)對象、數(shù)據(jù)之間的關系和操作3. 某班級的學生成績表中查得張三同學的各科成績記錄， 其中數(shù)據(jù)結構考了 90分，那么下面關于數(shù)據(jù)對象、數(shù)據(jù)元素、數(shù)據(jù)項描述正確的是（ C ）90 分是數(shù)據(jù)項90 分是數(shù)據(jù)元素90 分是數(shù)據(jù)項90 分是數(shù)據(jù)元素B、數(shù)據(jù)類型D數(shù)據(jù)定義物理地址與邏輯地址不相同， 稱之為 （ C ）B、邏輯結構D順序存儲結構研究算法中的輸入和輸出關系分析算法的易懂性和文檔型性B、正確性和簡明性H數(shù)據(jù)復雜性和程序復雜性8 .計算機內部處理的基本單元是（B ）R數(shù)據(jù)元素C、數(shù)據(jù)項D、數(shù)據(jù)庫9 .數(shù)據(jù)在計算機內有

5、鏈式和順序兩種存儲方式，在存儲空間使用的靈活性上, 鏈式存儲比順序存儲要（B ）。A、低R高G相同D不好說10 .算法的時間復雜度取決于（C ）日待處理數(shù)據(jù)的初始狀態(tài)D不好說A、問題的規(guī)模C問題的規(guī)模和待處理數(shù)據(jù)的初始狀態(tài)11 .數(shù)據(jù)結構既研究數(shù)據(jù)的邏輯結構，又研究物理結構，這種觀點（ B ）A、正確B、錯誤C前半句對，后半句錯H前半句錯，后半句對12 .在數(shù)據(jù)結構中，從邏輯上可以把數(shù)據(jù)結構分成（ C ）A動態(tài)結構和靜態(tài)結構C線性結構和非線性結構13.線性表的順序存儲結構是一種種（A ）存儲結構。B、緊湊結構和非緊湊結構Dk內部結構和外部結構（）的存儲結構，線性表的鏈式存儲結構是B、順序存取A

6、、隨機存取14. *下列程序的時間復雜度是（A ）for (i=1; i<=n; +i)for (j=1； j<=n; +j)c ij=0;A、O(n2)R O(n)C、O(2n) D O(2n2)15. *下列程序的空間復雜度是(A )for (i=1; i<=n; +i)for (j=1; j<=m; +j)c ij=0;A、O(m*n)B O(m+n)C、O(m-n) D O(m/n)16. *求下列程序段的時間復雜度（B）for(i=1; i<=n ;i + + )for(j=1;j<=n ;j + + ) x=x+1;A、O(n2)B 、O(n)

7、C 、。D 、O(0)第二章線性表1 .關于線性表的說法不正確的是？ （ D）A、存在唯一的一個被稱為“第一個”的數(shù)據(jù)元素（開始結點）日存在唯一的一個被稱為“最后一個”的數(shù)據(jù)元素（終端結點）C除第一個之外，集合中的每個數(shù)據(jù)元素均只有一個前驅D除第一個之外，集合中的每個數(shù)據(jù)元素均只有一個后繼2 .關于順序表的說法不正確的是？ （ D ）A、邏輯關系上相鄰的兩個元素在物理存儲位置上也相鄰日可以隨機存取表中任一元素，方便快捷C在線性表中插入某一元素時，往往需要移動大量元素D在線性表中刪除某一元素時，無需移動大量元素3 .當線性表的元素總數(shù)基本穩(wěn)定，且很少進行插入和刪除操作，但要求以最快 的速度存取線

8、性表中的元素時，應采用什么存儲結構? （ A ）A順序表 R單鏈表C、循環(huán)鏈表 D、雙鏈表4 .在一個長度為n的順序表中第i個元素（1<=i<=n）之前插入一個元素時， 需向后移動多少個元素。（C ）A、n-1 B、n-i C n-i+10 n-i-15 .在單鏈表中設置頭結點的作用是（）oA、單鏈表定義而已 已 指定表的起始位置C為雙向鏈表做準備 D、為循環(huán)鏈表做準備6 .根據(jù)線性表鏈式存儲結構中每一個結點包含的指針數(shù)，將線性鏈表分成（C）A、單鏈表與循環(huán)鏈表B、單鏈表與十字鏈表C單鏈表與雙鏈表D循環(huán)鏈表與多鏈表7 .鏈接存儲的特點是利用化”表示數(shù)據(jù)元素之間的邏輯關系（A ）A引

9、用B、串聯(lián)C、掛接D、指派8 .已知指針p指向單鏈表L中的某結點，則刪除其后繼結點的語句是（D）9 . A、p = R p=null G =null D> =在單鏈表L中，指針p所指結點 有后繼結點的條件是（B ）A p=B、！=null10 . G =null D =在單鏈表p結點之后插入s結點的操作是（C ）A、=s；=； R =;=、 =;=s;D、=p； =s；第三章棧和隊列1. 棧、隊列通常采用兩種存儲結構，它們是（B ）A、散列方式和索引方式B、順序存儲結構和鏈式存儲結構C鏈表存儲結和數(shù)組D、線性和非線性存儲結構2. 一個棧入棧序列是a,b,c,d,則棧輸出序列不可能是（C

10、）A d,c,b,a B c,d,b,aC、d,c,a,b D 、a,b,c,d3. 判斷順序棧（最多結點數(shù)為m為棧滿的條件是（D ）A top=0 B 、top!=m C 、top!=0 D 、top=m4. 棧存取數(shù)據(jù)原則（或棧特點）是（B ）A、后進后出 B、后進先出C、先進先出 D 、隨意進出5. *經(jīng)過以下棧運算后，x的值是（A ）InitStack（s）;Push（s,d）;Push（s,e）;Pop（s,x）;Pop（s,x）;GetTop（s,x）;A、dB 、eC 、xD 、s6. 一個隊列的進隊序列為：a, b, c, d,則出隊序列是：（A）A a, b, c, dB、

11、d , c, b, aC a, d, c, bD、 c , b, d, a7. 循環(huán)隊列為空隊列的條件是：（ D）A、 =0B 、 Q. （ rear+1）%MaxSize=C、 =0D、 =8. 在存儲結構上，如果用帶頭節(jié)點單鏈表實現(xiàn)隊列（假定front 和 rear 分別為隊首和隊尾指針） ，則刪除一個結點的操作為（ A ） 。A、 = B、 rear=C、 rear=D、 front=9. 棧和隊列共同點是（ C ）A、先進后出日先進先出C允許在端點處進行操作線性表D無共同點10. 插入和刪除只能在一端進行的線性表是（ B ）A循環(huán)隊列B 、棧C隊列 D 、循環(huán)棧11. 插入和刪除分別在

12、兩端端進行的線性表是（ C ）A循環(huán)隊列B 、棧C隊列 D 、循環(huán)棧12. 循環(huán)隊列為滿隊列的條件是： （ B ）A、 =0B 、 Q. （ rear+1）%MaxSize=C、 =0D、 =1. 關于串的敘述，錯誤的是：A.串是字符有限序列C.模式匹配是串的重要運算2. 串長度是指（ B ）A.串所含不同字母數(shù)目BC.串所含不同字符數(shù)目D第四章 串（ B ）B.空串是由空格構成的串D 串有用順序、鏈式兩種存儲方式串所含字符數(shù)目串所含非空格字符數(shù)目3. *若串S=” database” ,其子串數(shù)目是（ B ）。A 16 B 37 C 8 D 364. 設用S1是用S子申，則求S1在S中定位運

13、算稱為（B ）A.求子串 B .串匹配 C ,聯(lián)接 D .求串長5. 設有串 s1=” welcome to zdsoft colleage! ”和 s2=” so” , 那么 s2 在 s1 中的索引位置是（ C ）A 12 B 14 C 13 D 106. *若串 S=“software “ , 其子串的數(shù)目是（ B ） 。A 8 B 37 C 36 D 9第五章 數(shù)組和廣義表第六章 樹和二叉樹1. 假設在一棵二叉樹中，雙分支結點數(shù)為15，單分支結點數(shù)為30 個，則葉子結點數(shù)為（ B ）個。A. 15B. 16C. 17D. 472. 假定一棵三叉樹的結點數(shù)為50，則它的最小高度為（C ）

14、 。A. 3B. 4C. 5D. 63. 在一棵二叉樹上第 4 層的結點數(shù)最多為（ D ） 。A. 2B. 4C. 6D. 84. 用順序存儲的方法將完全二叉樹中的所有結點逐層存放在數(shù)組中 R1.n ，結點 Ri 若有左孩子，其左孩子的編號為結點（ B ） 。A. R2i+1 B. R2iC. Ri/2D. R2i-15. 設n, m為一棵二叉樹上的兩個結點，在中序遍歷序列中n在m前的條件是（B ）。A. n在m右方B. n 在m左方C.n是m的祖先D.n是m的子孫6. 下面敘述正確的是（D ）。A.二叉樹是特殊的樹B.二叉樹等價于度為 2的樹C.完全二叉樹必為滿二叉樹D.二叉樹的左右子樹有次

15、序之分7 .現(xiàn)有一深度為5的二叉樹，請問其最多有（D ）個結點。A. 32B.5D. 318 .現(xiàn)有一深度為4的二叉樹，請問其最多有（A ）個結點。A. 15B. 169 .在一棵二叉排序樹上按（B ）遍歷得到的結點序列是一個有序序列。A.先序B.中序C.后序D.頭序10 .在一棵二叉樹中，度為0的結點數(shù)為n0,度為2的結點數(shù)為n2,則n0= （ C ）A. n+1 B.n+2+111 .由三個結點構成的二叉樹，共有（A. 4B. 512 . 一棵含有n個結點的樹，（A ）A.單支樹 B.二叉樹13 .不含任何結點的空樹（C ）。A .是一棵樹； 樹；C.是一棵樹也是一棵二叉樹；14 .二叉樹

16、是非線性數(shù)據(jù)結構，所以（A .它不能用順序存儲結構存儲； 儲；C .順序存儲結構和鏈式存儲結構都能存儲D .順序存儲結構和鏈式存儲結構都不能使用+1B ）種不同的形態(tài)形態(tài)達到最大深度。C.三叉樹 叉樹B .是一棵二叉D.既不是樹也不是二叉樹C）。B.它不能用鏈式存儲結構存15 .具有n（n>0）個結點的完全二叉樹的深度為(C )A .log2(n)B .10g2(n)C .10g2(n)+1D .log2(n)+116 .在一棵三元樹中度為3的結點數(shù)為2個，度為2的結點數(shù)為1個，度為1的 結點數(shù)為2個，則度為0的結點數(shù)為（D ）個。A. 4B. 517 .有關二叉樹下列說法正確的是（B

17、）A.二叉樹的度為 2B, 一棵二叉樹的度可以小于2C.二叉樹中至少有一個結點的度為2D.二叉樹中任何一個結點的度都為218 .在完全二叉樹中，若一個結點是葉結點，則它沒（C ）。A.左子結點B.右子結點C.左子結點和右子結點D.左子結點，右子結點和兄弟結點19 .在下列情況中，可稱為二叉樹的是（B ）A.每個結點至多有兩棵子樹的樹B.哈夫曼樹C.每個結點至多有兩棵子樹的有序樹D.每個結點只有一棵右子樹第七章圖1 .圖的深度優(yōu)先遍歷類似于二叉樹的（A ）。A.先序遍歷B .中序遍歷 C .后序遍歷D .層次遍歷2 .已知一個圖如圖所示，若從頂點a出發(fā)按深度優(yōu)先遍歷，則可能得到的一種 頂點序列為

18、（C）A. abecdfB. acfebdC. aebcfd D. aedfcb3 .若從無向圖的任意一個頂點出發(fā)進行一次深度優(yōu)先搜索可以訪問圖中所有的頂點，則該圖一定是（B ）圖。A.非連通B .連通 C .強連通 D .有向4 .在一個圖中，所有頂點的度數(shù)之和等于所有邊數(shù)的（ C ）倍。A 1/2 B 15 .在一個有向圖中，所有頂點的入度之和等于所有頂點出度之和的（ B ） 倍。A1/2B1 C2 D36 . 一個有N個頂點的有向圖最多有（ B ）條邊。AN B N（N-1） C N（n-1）/2 D 2N7 .具有4個頂點的無向完全圖有（A ）條邊。A 6B12C18 D 208 .具

19、有6個頂點的無向圖至少有（A ）條邊才能確保是一個連通圖。A 5 B 6 C 7 D 89 .對于一個具有N個頂點的無向圖，若采用鄰接矩陣表示，則該矩陣大小是 （D ）A N B （N-1）2 C N-1 D N*N10 . 一個具有N個頂點的無向圖中，要連通全部頂點至少要（ C ）條邊A N BN+1CN-1 D N/211. *已知圖的鄰接矩陣如圖所示，則從頂點0出發(fā)按深度優(yōu)先遍歷的結果是0 111 10 0 110 0 0 110 010 11 0 0 0 1110 01 0 10 0 11 0 01 1 00 1 01 0 10 1 0A. 0243 1 56B. 0 1 36542C

20、. 0 1 342 56D. 036 1 54212 .已知圖的鄰接表下圖所示，則從頂點0出發(fā)按廣度優(yōu)先遍歷的結果是（）, 按深度優(yōu)先遍歷的結果是（D ）0A. 0 132 B . 02 3 1 C .032 1 D ,012313 .已知圖的鄰接表下圖所示，則從頂點0出發(fā)按廣度優(yōu)先遍歷的結果是（）, 按深度優(yōu)先遍歷的結果是（）。A. 0 132 B0231 C , 03210 12 314 . 當在一個有序的順序表上查找一個數(shù)據(jù)時，既可用折半查找，也可用順序查找，但前者比后者的查找速度（ C ） 。A.必定快B.不一定C.在大部分情況下要快D.取決于表遞增還是遞減15 . 折半查找有序表（

21、4， 6， 10， 12， 20， 30， 50， 70， 88， 100） 。若查找表中元素58，則它將依次與表中（A ）比較大小，查找結果是失敗。A 20， 70， 30， 50B 30， 88， 70， 50C 20， 50D 30， 88， 50第八章 查找1. 順序查找法適合于存儲結構為（ B ）的線性表。A.散列存儲B.順序存儲或鏈式存儲C.壓縮存儲D.索引存儲2. 在查找過程中，若同時還要增、刪工作，這種查找稱為（ B ） 。A、靜態(tài)查找B 、 動態(tài)查找 C 、 內查找 D 、 外查找3. 索引順序表的特點是順序表中的數(shù)據(jù)（ A ） 。A、有序 B 、 無序C、 塊間有序 D 、

22、 散列4. 采用順序查找方法查找長度為 n 的線性表時， 每個元素的平均查找長度為（ C）A、 n B、 n/2 C、 （n+1）/2D、 （n-1）/25. *將 10個元素散列到 1000000個單元的哈希表，則（ C ）產(chǎn)生沖突。A、 一定會 B 、一定不會C 、仍可能會 D 、以上都不對6. *散列表的地址區(qū)間為016,散列函數(shù)H（k尸k%17,采用線性探測法解決地址沖突，將關鍵字26、 25、 72、 38、 1、 18、 59依次存儲到散列表中。元素59 存放在散列表中的地址為（ A ）A、 8B、 9C、 10 D、 117. 設有序表的關鍵字序列為 1,3,9,12,32,41

23、,45,62,75,77,82,95,100， 當采用二分查找法查找值為 82 的節(jié)點時，經(jīng)（ C ）次比較后查找成功。A、 1B、 2C、 3D、 48. 設有 100 個元素，用折半查找法進行查找時，最大、最小比較次數(shù)分別時 （ A ）A、7,1 B 、 6,1C、 5,1 D、 8,1第九章 排序1. 對 n 個不同的記錄按排序碼值從小到大次序重新排列， 用冒泡 （ 起泡 ） 排序方法，初始序列在（A ） 情況下，與排序碼值總比較次數(shù)最少。A.按排序碼值從小到大排列B .按排序碼值從大到小排列C.隨機排列（完全無序） D .基本按排序碼值升序排列2. 對 n 個不同的記錄按排序碼值從小到

24、大次序重新排列， 用冒泡 （ 起泡 ） 排序方法，在（ B）情況下，與排序碼值總比較次數(shù)最多。A.按排序碼值從小到大排列B .按排序碼值從大到小排列C.隨機排列（完全無序） D .基本按排序碼值升序排列3. 對n個不同的記錄按排序碼值從小到大次序重新排列，用直接插入排序方法，初始序列在（ A）情況下，與排序碼值總比較次數(shù)最少。A.按排序碼值從小到大排列B .按排序碼值從大到小排列C.隨機排列（完全無序） D .基本按排序碼值升序排列4. 對 n 個不同的記錄按排序碼值從小到大次序重新排列， 用直接插入排序方法，初始序列在（ B）情況下，與排序碼值總比較次數(shù)最多。A.按排序碼值從小到大排列B .

25、按排序碼值從大到小排列C.隨機排列（完全無序） D .基本按排序碼值升序排列5. 對 n 個不同的記錄按排序碼值從小到大次序重新排列，用快速排序方法在（ C）情況下，與排序碼值總比較次數(shù)最少。A.按排序碼值從小到大排列B .按排序碼值從大到小排列C.隨機排列（完全無序） D .基本按排序碼值升序排列6. 對 n 個不同的記錄按排序碼值從小到大次序重新排列，用快速排序方法，在（ A）情況下與排序碼值總比較次數(shù)最多。A.按排序碼值從小到大排列B .按排序碼值從大到小排列C.隨機排列（完全無序） D .基本按排序碼值升序排列7. 用冒泡排序方法對n 個記錄按排序碼值從小到大排序時， 當初始序列是按排

26、序碼值從大到小排列時，與碼值總比較次數(shù)是( D)。A n-1 B n C n+1 D n(n-1) 28. 下列排序方法中， 與排序碼值總比較次數(shù)與待排序記錄的初始序列排列狀態(tài)無關的是 (D)。A.直接插入排序B .冒泡排序C .快速排序D .直接選擇排序9. 將 6 個不同的整數(shù)進行排序，至少需要比較(A)次。A5B6C15D2110. 將 6個不同的整數(shù)進行排序，至多需要比較(C)次。A5B6C15D2111. *若需要時間復雜度在O(nlog 2n) 內，對整數(shù)數(shù)組進行排序，且要求排序方法是穩(wěn)定的，則可選擇的排序方法是(B)。A.快速排序B .歸并排序 C .堆排序 D .直接插入排序1

27、2. 當待排序的整數(shù)是有序序列時，采用 (B) 方法比較好，其時間復雜度為O(n)。A.快速排序B .冒泡排序 C .歸并排序D .直接選擇排序13. 當待排序的整數(shù)是有序序列時，采用(A)方法比較差，達到最壞情況下時間復雜度為O(n2) 。A.快速排序B .冒泡排序 C .歸并排序D .直接選擇排序14. 當待排序的整數(shù)是有序序列時，無論待排序序列排列是否有序，采用( D)方法的時間復雜度都是O(n2) 。A.快速排序B .冒泡排序 C .歸并排序D .直接選擇排序15. *堆是一種 (B) 排序。A.插入 B .選擇 C .交換 D .歸并16. *若一組記錄的排序碼值序列為 40 ， 8

28、0， 50， 30， 60， 70 ，利用堆排序方法進行排序，初建的大頂堆是(D )。A80，40，50，30 ，60，70B80 ， 70，60， 50，40 ， 30C80，70，50，40 ，30，60D80 ， 60，70， 30，40 ， 5017. 若一組記錄的排序碼值序列為 50 ， 80， 30， 40， 70， 60 利用快速排序方法，以第一個記錄為基準，得到一趟快速排序的結果為（ B ） 。A30，40， 50， 60 ，70， 80B40 ， 30， 50，80， 70 ， 60C 50，30， 40， 70 ，60， 80D40 ， 50， 30，70， 60 ， 80

29、18. * 下列幾種排序方法中要求輔助空間最大的是（ C ） 。A.堆排序B .直接選擇排序C .歸并排序 D .快速排序19. 已知 Am 中每個數(shù)組元素距其最終位置不遠，采用下列 （A） 排序方法最 節(jié)省時間。A.直接插入B .堆 C .快速 D .直接選擇20. *設有10000個互不相等的無序整數(shù)，若僅要求找出其中前10個最大整數(shù)，最好采用（ B）排序方法。A.歸并 B .堆 C .快速 D .直接選擇21. *在下列排序方法中不需要對排序碼值進行比較就能進行排序的是（ A）A:基數(shù)排序B .快速排序C .直接插入排序D .堆排序22. *給定排序碼值序列為F ， B， J， C， E

30、， A， I ， D， C， H ，對其按字母的字典序列的次序進行排列，希爾 （Shell） 排序的第一趟 （d1=5） 結果應為（ D ）A B ，B C，F(xiàn)， C， J ， A， E， D， I ， C， HB， D， A， E， F， I ， C， J， HH， JC B ， F， C， E， A， I ， D， C，D A ，B， D， C， E， F， I ， J ， C， H23. 給定排序碼值序列為F, B, J, C, E, A, I, D, C, H,對其按字母的字典序列的次序進行排列，冒泡排序（ 大數(shù)下沉 ） 的第一趟排序結果應為（ C ） 。ABJ，A，C，HBCA，E，

31、J，HCBE，A，H，JDAC，E，C，H24. 給定排序碼值序列為F, B, J, C, E, A, I, D, C, H,對其按字母的字典序列的次序進行排列，快速排序的第一趟排序結果為（ B ） 。A B ，B C，F(xiàn)， C， J ， A， E， D， I ， C， HB， D， A， E， F， I ， C， J， HH， JC B ， F， C， E， A， I ， D， C，D A ，B， D， C， E， F， I ， J ， C， H25. *給定排序碼值序列為 F ， B， J， C， E， A， I ， D， C， H ，對其按字母的字典序列的次序進行排列，二路歸并排序的第一

32、趟排序結果是（ A ） 。AB ，F(xiàn)，C，J ，A，E，D，I ，C，HBC，B，D，A，E，F(xiàn)，I ，C，J，HCB ，F(xiàn)，C，E，A，I ，D，C，H，JDA ，B，D，C，E，F(xiàn)，I ，J ，C，H簡答題第一章緒論1. 請分別給出數(shù)據(jù)、 數(shù)據(jù)對象、 數(shù)據(jù)元素、 數(shù)據(jù)項的含義， 并說明四者的關系。數(shù)據(jù) （Data）: 是對信息的一種符號表示。在計算機科學中是指所有能輸入到計算機中并能被計算機程序處理的符號的總稱。 （一個得分點）數(shù)據(jù)元素 （Data Element）: 是數(shù)據(jù)的基本單位，在計算機程序中通常作為一個整體進行考慮和處理，相當于表中的一條記錄。 （一個得分點）數(shù)據(jù)項：相當于記錄的

33、“域” , 是數(shù)據(jù)的不可分割的最小單位, 如學號（一個得分點）數(shù)據(jù)對象：性質相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個子集. 例如 : 同一個班的所有學生記錄集合。 （一個得分點）關系：包含關系：數(shù)據(jù)泛指所有。數(shù)據(jù)對象是數(shù)據(jù)的一個子集，由數(shù)據(jù)元素組成，數(shù)據(jù)元素是由數(shù)據(jù)項組成。 （一個得分點）評分標準，總共 5 個得分點，每段話一個得分。2. 請給出數(shù)據(jù)的邏輯結構的含義，并舉例說明數(shù)據(jù)的邏輯結構通常有哪些。數(shù)據(jù)的邏輯結構： 指數(shù)據(jù)元素之間的邏輯關系。 即用自然語言描述數(shù)據(jù)， 它與數(shù)據(jù)的存儲無關，是獨立于計算機的，邏輯結構有四種。 （一個得分點）集合結構： 僅同屬一個集合（結構名字個得分點、舉例得分點）線

34、性結構 :一對一（ 1:1） （結構名字個得分點、舉例得分點）樹 結 構:一對多（ 1:n） （結構名字個得分點、舉例得分點）圖 結 構: 多對多 （m:n） （結構名字個得分點、舉例得分點）評分標準：每段話一個得分點，總共 5 個得分點。什么是數(shù)據(jù)的物理結構？有哪些物理結構？數(shù)據(jù)的物理結構與邏輯結構有什么區(qū)別與聯(lián)系？數(shù)據(jù)的物理結構： 物理結構亦稱存儲結構， 是數(shù)據(jù)的邏輯結構在計算機存儲器內的表示（或映像） 。它依賴于計算機。 （一個得分點）存儲結構可分為 4 大類：順序、鏈式、索引、散列。 （共 2 個得分點，一個得分點）區(qū)別： 數(shù)據(jù)的邏輯結構屬于用戶視圖， 是面向問題的， 數(shù)據(jù)的存儲結構屬

35、于具體實現(xiàn)的視圖，是面向計算機的。 （一個得分點）聯(lián)系： 一種數(shù)據(jù)的邏輯結構可以用多種存儲結構來存儲， 而采用不同的存儲結構其處理的效率往往不同。 （一個得分點）評分標準：共 5 個得分點，按照每段話各自標注的得分點進行評分。3. 求兩個正整數(shù)m, n中的最大數(shù)MAX勺算法（ 1 ）若 m > n 則 max=m（ 2 ）若 m <= n 則 max=n請根據(jù)上述算法解釋一下算法的組成要素有哪些，分別是什么。算法由操作、控制結構、數(shù)據(jù)結構3 要素組成操作包含：算術運算、關系比較、邏輯運算、數(shù)據(jù)傳送（輸入、輸出、賦值） （一個得分點）例子中有關系比較和賦值計算的操作。 （一個得分點）

36、控制結構包含：順序結構、選擇結構、循環(huán)結構（一個得分點）例子中有選擇結構（一個得分點）數(shù)據(jù)結構： 算法操作的對象是數(shù)據(jù)， 數(shù)據(jù)間的邏輯關系、 數(shù)據(jù)的存儲方式及處理方式就 是數(shù)據(jù)結構。 （一個得分點）本例是數(shù)值問題，涉及到兩個正整數(shù)，因此使用基本的整數(shù)類型就可以解決問題。 （一個得分點）評分標準：本題共 6 個得分點，每段話一個得分點。4. 簡述算法的基本性質1）輸入：0 個或多個輸入2）輸出：1 個或多個輸出3）有窮性：算法必須在有限步內結束4）確定性：組成算法的操作必須清晰無二義性5）可行性：組成算法的操作必須能夠在計算機上實現(xiàn)評分標準，本題共 5 個得分點，每個要點一分。5. 簡述算法的設

37、計要求1、正確性（correctness）2、可讀性（readability）3、健壯性（robustness）4、通用性（generality）5、效率與存儲的要求（執(zhí)行算法所耗費的存儲空間、執(zhí)行算法所耗費的時間）評分標準，本題共5 個得分點，每個要點一分。6. 評價算法好壞的3 條主要標準1）算法實現(xiàn)所耗費的時間。2）算法實現(xiàn)所耗費的存儲空間，其中主要考慮輔助存儲空間。3）算法應易于理解、易于編碼、易于調試等。評分標準，本題共 3 個得分點，每個要點一分。7. 請簡述數(shù)據(jù)結構所研究的三種基本結構，以及數(shù)據(jù)元素間的關系。線性結構：數(shù)據(jù)元素之間一對一的關系。（ 2分）樹形結構：數(shù)據(jù)元素之間一對

38、多的關系。（分）圖形結構：數(shù)據(jù)元素之間多對多的關系。（分）8. 請問算法的分析和評價的兩個標準，以及各自作用。時間復雜度：評估算法運行所需時間。 （ +1 分）空間復雜度：評估算法運行時所需最大存儲空間。+1 分）5 分）9. 請說出三種邏輯數(shù)據(jù)結構，以及他們的特點。（ 1 ）線性結構：數(shù)據(jù)元素只有一個前驅數(shù)據(jù)元素和一個后繼數(shù)據(jù)元素。 （ 2 分）（ 2 ）樹結構：每個數(shù)據(jù)元素只有一個前驅數(shù)據(jù)元素，可有零個或若干個后繼數(shù)據(jù)元素。（分）（ 3 ）圖結構：每個數(shù)據(jù)元素可有零個或若干個前驅數(shù)據(jù)元素，零個或若干個后繼數(shù)據(jù)元素。 （分）10. 評價算法的主要標準是什么？（ 1 ）算法實現(xiàn)所耗費的時間（

39、2 分）（ 2 ）算法實現(xiàn)所耗費的存儲空間，其中主要考慮輔助存儲空間。（ 2 分）（ 3 ）算法應易于理解、易于編碼、易于調試。（ 1 分）11. 請說出三種邏輯數(shù)據(jù)結構，并分別畫圖表示它們。（ a, 2 分， b,c 各分）12. 算法的基本性質有哪些？并簡述每個特性。 （5 分 ）1 ）有窮性 （1 分）2 ）確定性 （ 1 分）3 ）可行性 （ 1 分）4 ）輸入性 （ 1 分）5 ）輸出性 （ 1 分）13. 通常從那幾個方面來評價算法的質量? （5 分 ）通常從四個方面評價算法的質量：正確性、可讀性、健壯性和高效性。 （少一個扣 1 分）14. 請描述線性數(shù)據(jù)結構的兩種存儲方式，并說

40、出其各有什么特點。順序存儲：連續(xù)存儲，易于定位，不易于插入和刪除。 （ 1+分）鏈式存儲：非連續(xù)存儲，不易于定位，易于插入和刪除。 （ 1+分）15. 請問算法的分析和評價的兩種方法，它們關注點各有什么不同？（簡單）空間效率：關注算法對內存的占用度。 （ 1+分）時間效率：關注算法的運算速度。（ 1+分）第二章 線性表1. 請問如果要插入一個數(shù)據(jù)到一個線性表中， 順序表和鏈表哪個的效率高？為什么？鏈表的效率高 （ 2 分） ， 因為順序表要移動插入位置后的每一個元素的位置給新數(shù)據(jù)騰位置（分） 。鏈表只需要將前一個數(shù)據(jù)的指針指向新數(shù)據(jù)并將新數(shù)據(jù)的指針指向后一個數(shù)據(jù)即可（分） 。2. 線性表有哪些

41、特點？1）除第一個和最后一個數(shù)據(jù)元素外，每個數(shù)據(jù)元素只有一個前驅數(shù)據(jù)元素和一個后繼數(shù)據(jù)元素； （ 2 分）2）第一個數(shù)據(jù)元素沒有前驅數(shù)據(jù)元素； （分）3）最后一個數(shù)據(jù)元素沒有后繼數(shù)據(jù)元素。 （分）3. 順序存儲結構的優(yōu)缺點有哪些? （ 中等 ）順序存儲結構的優(yōu)點 : （分）存儲空間連續(xù)邏輯相鄰，物理相鄰可隨機存取任一元素缺點 : （分）插入、刪除操作需要移動大量的元素預先分配空間需按最大空間分配，利用不充分表容量難以擴充4. 單鏈式存儲結構的優(yōu)缺點有哪些? （ 中等 ）單鏈式存儲結構的優(yōu)點 : （分）不需預先分配空間，空間利用充分插入、刪除操作簡單, 無需移動大量的元素表容量易于擴充缺點 :

42、（分）每個數(shù)據(jù)元素，除存儲本身信息外，還需空間存儲其直接后繼的信息邏輯相鄰，物理不一定相鄰不可隨機存取任一元素 , 只能從鏈表頭依次查找.5. 有順序表A=（a0, a1, a2,a8,a9, - 19）,要在a8,a9之間插入一個元素 a20,請描述其操作（思想）步驟。（中等）插入思想或步驟： 根據(jù)順序表的存儲特點， 要在表中某位置10 插入一新數(shù)據(jù)元素 , 則要進行如下兩步操作：（ 1） 、 從位置 10 到表尾位置的所有數(shù)據(jù)元素均要從后至前依次向后移一個存儲位置，為新插入結點騰出第 10 個位置。 （ 2 分）（ 2） 、將新結點插入到空余位置10 處。 2 分）（ 3）表長度加1.（

43、1 分）6. 有順序表A=（a0, a1, a2,a8,a9, - 19）,要刪除一個元素 a9,請描述其 操作 （ 思想 ） 步驟。 （ 中等 ）（ 1 ）然后將從位置11 到表尾的所有數(shù)據(jù)元素依次向前移一個存儲位置。 （ 3 分）（ 2）表長度減1.（ 2 分）7. 請描述在順序表中第i 個位置插入新的數(shù)據(jù)x 操作過程。根據(jù)順序表的存儲特點， 要在表中某位置i 插入一新數(shù)據(jù)元素， 則要進行如下兩步操作：（ 1 ）從位置 i 到表尾位置的所有數(shù)據(jù)元素均要從后至前依次向后移一個存儲位置，為新插入結點騰出第 i 個位置；（ 2 分）（ 2 ）將新數(shù)據(jù)x 插入到空余位置i 處。 （ 2 分）（ 3

44、 ）表長度加1.（ 1 分）8. 請描述在順序表中刪除第i 個位置的數(shù)據(jù)的過程。（ 1 ）然后將從位置i 到表尾的所有數(shù)據(jù)元素依次向前移一個存儲位置。 （ 3 分）（ 2 ）表長度減1.（ 2 分）9 .請描述在一個單鏈表中插入一個數(shù)據(jù)q的插入過程(1)找到將插入數(shù)據(jù)位置的前一個結點p; (1分)(2) q的next值等于p的next值；(2分)(3) p的next值等于q； (2分)10 .請描述從一個單鏈表中刪除一個數(shù)據(jù)的刪除過程。(1)找到將被刪除數(shù)據(jù)的前一個結點p； (2分)(2) p的next指針指向被刪除數(shù)據(jù)的后一個結點；(2分)(3)將被刪除數(shù)據(jù)原來的next指針指向null;

45、(1分)第三章棧和隊列1 .請簡述線性表、棧和隊列三者之間的聯(lián)系。(簡單)(1)線性表、棧和隊列都屬于線性結構。(2分)(2)棧和隊列都是特殊的線性表，并且都有順序存儲、鏈式存儲兩種存儲方式。(1分)(3)棧是一種先進后出的線性表，隊列是一種先進先出的線性表(2分)2 .在計算機進行運算時，需要把十進制轉換為二進制。請問答：這種數(shù)制轉換 可以借助于哪種數(shù)據(jù)結構實現(xiàn)、及原因。答：棧。(2分)原因：(3分)在進行數(shù)值轉換時，其實質是求余的過程，并且余數(shù)的倒序序列正是所求結果。棧是一種先進后出的線性結構，能夠滿足這種操作。3 .有一字符序列abcde依次按照某一線性結構存儲，請回答以下問題：1 1)

46、、如果該線性結構是隊列，那么，寫出出隊序列。2 2)、如果該線性結構是棧，那么，輸出序列可能是d,c,e,a,b 嗎，為什么？3 3)、如果該線性結構是棧，且輸出序列是abcde。請寫出操作過程。(push(x):表示把x壓入棧內；pop (x):表示把x彈出棧)答：4 1)、abcde 11 分)5 2)、不可能，因為：d是第一出棧字符，說明 a,b已別壓入棧內；并且壓入棧的次序為abcde ;由以上得出：ab出棧的順序只能是 b、a,而不是a、b。所以，出棧序列d,c,e,a,b 是不可能的。(2分)6 3)、(2 分)push (a) , pop (a)push (b)pop (b)pu

47、sh ,pop （c）push （d） , pop （d）push （e） , pop （e）7 .簡述棧和隊列的異同點。相同點：棧和隊列都是只允許在表的端點處進行插入、刪除操作的線性表。（2分）不同點：棧的特點是先進后出，隊列的特點是后進先出。（3分）8 .若依次讀入數(shù)據(jù)元素序列1、2、3,進棧的過程中允許出棧，試寫出各種可 能的出棧序列。答:123、132、213、231、321 （各 1 分）9 .如果入棧序列有ABC組成，請問輸出序列可能有哪些？（較難）輸出序列有5種：CBA,BCA,BAC,ACB,ABC （各 1 分）10 如果有abcde五個數(shù)據(jù)依次全部存入，如果采用隊列和棧來進

48、行存儲，依次 取出分別將獲得什么內容。（簡單）隊列：abcde （分）棧：edcba （分）11 設將整數(shù)1 , 2, 3, 4依次進棧，能否得到1423出棧序列和1432?并說明為 什么不能得到或者如何得到。（中等）不能彳#到1423,但可以得到1432 （2分）因為要得到4必須將所有數(shù)據(jù)入棧，這樣將只能依次獲取到1432不能獲得1423。采用push、pop、push、push、push、pop、pop、pop 可以獲得 1432。（3 分）12 循環(huán)隊列的優(yōu)點是什么？如何判斷它的空和滿？（可不考）循環(huán)隊列的優(yōu)點是可以克服順序隊列的"假上溢"現(xiàn)象，能夠使存儲隊列的向量空

49、間得到充分的利用。（3分）采用犧牲一個元素空間的方法，循環(huán)隊列隊空的條件是 front=rear :循環(huán)隊列隊滿的條件是：（rear+1）%M=front 。 （2分）第四章串1 .對于字符用S=' abcde',請問：（簡單）（1）字符串S的長度是多少？（2）字符串S的子串有幾個，并列出所有子串？答：（1）、5（1 分）（2）、16, （1 分）所有字串：a'、 b'、 c'、 d'、 e'、 ab'、 bc'、 cd' 、 de' 、 abc'、'bcd '、' cde&

50、#39;、' abcd'、' bcde'、' abcde'、。（3 分）2 .對于字符用S=' 12345',請問：（簡單）（1）字符串S的長度是多少？（2）字符串S的子串有幾個，并列出所有子串？答：（1）、5（1 分）（2）、16, （1 分）所有字串：1、 2'、 3'、 4'、 5、 12、 23'、 34 、 45' 、 ' 123'、'234 '、' 345'、' 1234'、' 2345'、'

51、 12345'、。（3 分）3 .請問答：什么用的模式匹配？模式匹配算法有幾種？（簡單）答：串的模式匹配是指子串的定位運算，即在主串中查找子串第一次出現(xiàn)的位置。模式匹配算法有兩種：簡單匹配算法（Brute-Force） 、KM法。（該題共4個得分點，答對串匹配定義或大意基本相同，得 2分；答對兩種匹配算，得2分，答錯或少答一個扣1分）第五章數(shù)組和廣義表1 .在數(shù)據(jù)結構中，數(shù)組是最基本的結構，請完成以下要求：（1）、定義一個能容納 5個整型元素的數(shù)組iAry ,且元素的值為10、20、30、40、50。（2）、*畫出數(shù)組iAry的順序存儲結構。（規(guī)定：整型長度為兩個字節(jié)）（1）、int

52、iAry5= 10、20、30、40、50 （2 分）（2）、如下圖：（3分，根據(jù)情況，酌情扣分 ）2 .簡述數(shù)組的定義、特點和分類。（簡單）定義：數(shù)組是n個相同數(shù)據(jù)類型的數(shù)據(jù)元素a0,a1,a2,an-1構成的有限集合。（1個得分點）特點：1）數(shù)組中各元素具有統(tǒng)一的類型；（1個得分點）2）數(shù)組元素的下標一般具有固定的上界和下界，即數(shù)組一旦被定義，它的維數(shù)和維界就不再改變。（1個得分點）3數(shù)組的基本操作比較簡單，除了結構的初始化和銷毀之外，只有存取元素和修改元素值的操作。 （1個得分點）分類：按維度可分為一維數(shù)組、二維數(shù)組、多維數(shù)組（1個得分點）3 .已知一個二維數(shù)組A如下所示。（較難）（1）

53、請按照行優(yōu)先、列優(yōu)先的方式進行順序存儲，給出順序存儲的序列（2個得分點）行優(yōu)先：a11a12a13a21a22a23列優(yōu)先：a11a21a12a22a13a23（2）若a11在內存中存儲的地址為a ,每個元素的存儲空間大小為L,則按照行優(yōu)先的方式和列優(yōu)先的方式分別存儲，其中a22的地址10c（a22）分別為多少（2個得分點）行優(yōu)先：10c（a22）= a +4L列優(yōu)先：10c（a22）= a +3L（3）對于數(shù)組，除了順序存儲外，還有沒有其他存儲方式？沒有填無，若有，請說明。有，鏈式存儲，如下圖所示（1個得分點）第六章樹和二叉樹1 .有一樹，如下圖所示：（簡單）請回答以下問題：（1）樹的葉子結點及其度。（2）非終端結點及其度。（3）樹的深度。答：（1）、葉子結點有：D、E、F、G,它們的度都為零。（2分）（2）、非終端結點有：A度為3, B度為2, C度為1。（2分）（3）、樹的深度為3。（1分）2 .請回答：樹與二叉樹