數(shù)據(jù)結(jié)構(gòu)考試試題庫含答案解析

1、.數(shù)據(jù)結(jié)構(gòu)習(xí)題集含答案目錄目錄1選擇題2第一章緒論2第二章 線性表4第三章 棧和隊列5第四章 串6第五章 數(shù)組和廣義表7第六章 樹和二叉樹7第七章 圖9第八章 查找11第九章 排序12簡答題15第一章緒論15第二章 線性表20第三章 棧和隊列22第四章 串24第五章 數(shù)組和廣義表24第六章 樹和二叉樹26第七章 圖31第八章 查找33第九章 排序34編程題36第一章緒論36第二章線性表36第三章 棧和隊列46第四章 串46第五章 數(shù)組和廣義表46第六章 樹和二叉樹46第七章 圖46第八章 查找46第九章 排序51選擇題第一章緒論1. 數(shù)據(jù)結(jié)構(gòu)這門學(xué)科是針對什么問題而產(chǎn)生的？（A ）A、針對非數(shù)

2、值計算的程序設(shè)計問題B、針對數(shù)值計算的程序設(shè)計問題C、數(shù)值計算與非數(shù)值計算的問題都針對D、兩者都不針對2. 數(shù)據(jù)結(jié)構(gòu)這門學(xué)科的研究內(nèi)容下面選項最準確的是（D ）A、研究數(shù)據(jù)對象和數(shù)據(jù)之間的關(guān)系B、研究數(shù)據(jù)對象C、研究數(shù)據(jù)對象和數(shù)據(jù)的操作D、研究數(shù)據(jù)對象、數(shù)據(jù)之間的關(guān)系和操作3. 某班級的學(xué)生成績表中查得張三同學(xué)的各科成績記錄，其中數(shù)據(jù)結(jié)構(gòu)考了90分，那么下面關(guān)于數(shù)據(jù)對象、數(shù)據(jù)元素、數(shù)據(jù)項描述正確的是（C ）A、某班級的學(xué)生成績表是數(shù)據(jù)元素，90分是數(shù)據(jù)項B、某班級的學(xué)生成績表是數(shù)據(jù)對象，90分是數(shù)據(jù)元素C、某班級的學(xué)生成績表是數(shù)據(jù)對象，90分是數(shù)據(jù)項D、某班級的學(xué)生成績表是數(shù)據(jù)元素，90分是數(shù)

3、據(jù)元素4. *數(shù)據(jù)結(jié)構(gòu)是指（A ）。A、數(shù)據(jù)元素的組織形式B、數(shù)據(jù)類型C、數(shù)據(jù)存儲結(jié)構(gòu)D、數(shù)據(jù)定義5. 數(shù)據(jù)在計算機存儲器內(nèi)表示時，物理地址與邏輯地址不相同，稱之為（C ）。A、存儲結(jié)構(gòu)B、邏輯結(jié)構(gòu)C、鏈式存儲結(jié)構(gòu)D、順序存儲結(jié)構(gòu)6. 算法分析的目的是（C ）A、找出數(shù)據(jù)的合理性B、研究算法中的輸入和輸出關(guān)系C、分析算法效率以求改進D、分析算法的易懂性和文檔型性7. 算法分析的主要方法（A ）。A、空間復(fù)雜度和時間復(fù)雜度B、正確性和簡明性C、可讀性和文檔性D、數(shù)據(jù)復(fù)雜性和程序復(fù)雜性8. 計算機內(nèi)部處理的基本單元是（B ）A、數(shù)據(jù)B、數(shù)據(jù)元素C、數(shù)據(jù)項D、數(shù)據(jù)庫9. 數(shù)據(jù)在計算機內(nèi)有鏈式和順序兩

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

5、結(jié)構(gòu)。A、隨機存取B、順序存取C、索引存取D、散列存取14. *下列程序的時間復(fù)雜度是（A ）for (i=1; i=n; +i)for (j=1; j=n; +j) c ij=0;A、O(n2)B、O(n)C、O(2n)D、O(2n2)15. *下列程序的空間復(fù)雜度是（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. *求下列程序段的時間復(fù)雜度( B )for( i=1; i=n ; i + + )for ( j=1; j=n ; j + + ) x=x+1;A、O(n2) B

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

7、要求以最快的速度存取線性表中的元素時，應(yīng)采用什么存儲結(jié)構(gòu)？（A ）A、順序表B、單鏈表C、循環(huán)鏈表D、雙鏈表4. 在一個長度為n的順序表中第i個元素（1=i0)個結(jié)點的完全二叉樹的深度為(C )。.log2(n).log2(n).log2(n) +1.log2(n)+116. 在一棵三元樹中度為3的結(jié)點數(shù)為2個，度為2的結(jié)點數(shù)為1個，度為1的結(jié)點數(shù)為2個，則度為0的結(jié)點數(shù)為（D ）個。A. 4 B. 5 C.6 D.717. 有關(guān)二叉樹下列說法正確的是（B）A二叉樹的度為2B一棵二叉樹的度可以小于2C二叉樹中至少有一個結(jié)點的度為2D二叉樹中任何一個結(jié)點的度都為218. 在完全二叉樹中，若一個結(jié)

8、點是葉結(jié)點，則它沒（C）。A左子結(jié)點B右子結(jié)點C左子結(jié)點和右子結(jié)點D左子結(jié)點，右子結(jié)點和兄弟結(jié)點19. 在下列情況中，可稱為二叉樹的是（B）A每個結(jié)點至多有兩棵子樹的樹B.哈夫曼樹C每個結(jié)點至多有兩棵子樹的有序樹D.每個結(jié)點只有一棵右子樹第七章 圖1. 圖的深度優(yōu)先遍歷類似于二叉樹的（ A ）。A先序遍歷 B中序遍歷 C后序遍歷 D層次遍歷2. 已知一個圖如圖所示，若從頂點a出發(fā)按深度優(yōu)先遍歷，則可能得到的一種頂點序列為（C ）AabecdfBacfebdCaebcfdDaedfcb3. 若從無向圖的任意一個頂點出發(fā)進行一次深度優(yōu)先搜索可以訪問圖中所有的頂點，則該圖一定是（ B ）圖。A非連通

9、 B連通 C強連通 D有向4. 在一個圖中，所有頂點的度數(shù)之和等于所有邊數(shù)的（ C ）倍。A 1/2 B 1 C 2 D 35. 在一個有向圖中，所有頂點的入度之和等于所有頂點出度之和的（ B ）倍。A 1/2 B 1 C 2 D 36. 一個有N個頂點的有向圖最多有（ B ）條邊。A N B N(N-1) C N(n-1)/2 D 2N7. 具有4個頂點的無向完全圖有（ A ）條邊。A 6 B 12 C 18 D 208. 具有6個頂點的無向圖至少有（ A ）條邊才能確保是一個連通圖。A 5 B 6 C 7 D 89. 對于一個具有N個頂點的無向圖，若采用鄰接矩陣表示，則該矩陣大小是（D ）

10、A N B (N-1)2 C N-1 D N*N10. 一個具有N個頂點的無向圖中，要連通全部頂點至少要（ C ）條邊A N B N+1 C N-1 D N/211. *已知圖的鄰接矩陣如圖所示，則從頂點0出發(fā)按深度優(yōu)先遍歷的結(jié)果是（ C ）。A0 2 4 3 1 5 6B0 1 3 6 5 4 2C0 1 3 4 2 5 6D0 3 6 1 5 4 212. 已知圖的鄰接表下圖所示，則從頂點0出發(fā)按廣度優(yōu)先遍歷的結(jié)果是（ ），按深度優(yōu)先遍歷的結(jié)果是（ D ）。A0 1 3 2 B0 2 3 1C0 3 2 1 D0 1 2 313. 已知圖的鄰接表下圖所示，則從頂點0出發(fā)按廣度優(yōu)先遍歷的結(jié)果

11、是（ ），按深度優(yōu)先遍歷的結(jié)果是（ ）。A0 1 3 2 B0 2 3 1 C0 3 2 1 D0 1 2 314. 當在一個有序的順序表上查找一個數(shù)據(jù)時，既可用折半查找，也可用順序查找，但前者比后者的查找速度（ C ）。 A必定快 B不一定 C在大部分情況下要快 D取決于表遞增還是遞減15. 折半查找有序表（4，6，10，12，20，30，50，70，88，100）。若查找表中元素58，則它將依次與表中（ A ）比較大小，查找結(jié)果是失敗。A20，70，30，50 B30，88，70，50 C20，50 D30，88，50第八章 查找1. 順序查找法適合于存儲結(jié)構(gòu)為（B ）的線性表。A散列存儲

12、 B順序存儲或鏈式存儲 C壓縮存儲 D索引存儲2. 在查找過程中，若同時還要增、刪工作，這種查找稱為（ B ）。A、 靜態(tài)查找 B、 動態(tài)查找 C、 內(nèi)查找 D、 外查找3. 索引順序表的特點是順序表中的數(shù)據(jù)（ A ）。A、 有序 B、 無序 C、 塊間有序 D、 散列4. 采用順序查找方法查找長度為n的線性表時，每個元素的平均查找長度為（C）A、 nB、n/2C、(n+1)/2D、(n-1)/25. *將10個元素散列到1000000個單元的哈希表，則（ C ）產(chǎn)生沖突。A、 一定會 B、一定不會 C、仍可能會 D、以上都不對6. *散列表的地址區(qū)間為016，散列函數(shù)H(k)=k%17，采用

13、線性探測法解決地址沖突，將關(guān)鍵字26、25、72、38、1、18、59依次存儲到散列表中。元素59存放在散列表中的地址為（ A ）A、 8 B、 9 C、 10D、 117. 設(shè)有序表的關(guān)鍵字序列為1,3,9,12,32,41,45,62,75,77,82,95,100，當采用二分查找法查找值為82的節(jié)點時，經(jīng)（ C ）次比較后查找成功。A、 1B、 2 C、 3D、 48. 設(shè)有100個元素，用折半查找法進行查找時，最大、最小比較次數(shù)分別時（ A ）A、 7,1B、6,1C、5,1D、8,1第九章 排序1. 對n個不同的記錄按排序碼值從小到大次序重新排列，用冒泡(起泡)排序方法，初始序列在

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

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

16、列(完全無序) D基本按排序碼值升序排列7. 用冒泡排序方法對n個記錄按排序碼值從小到大排序時，當初始序列是按排序碼值從大到小排列時，與碼值總比較次數(shù)是 （D） 。An-1 Bn Cn+1 Dn(n-1)28. 下列排序方法中，與排序碼值總比較次數(shù)與待排序記錄的初始序列排列狀態(tài)無關(guān)的是 (D) 。A直接插入排序 B冒泡排序 C快速排序 D直接選擇排序9. 將6個不同的整數(shù)進行排序，至少需要比較 (A) 次。A5 B6 C15 D2110. 將6個不同的整數(shù)進行排序，至多需要比較 (C) 次。A5 B6 C15 D2111. *若需要時間復(fù)雜度在O(nlog2n)內(nèi)，對整數(shù)數(shù)組進行排序，且要求排

17、序方法是穩(wěn)定的，則可選擇的排序方法是 (B) 。A快速排序 B歸并排序 C堆排序 D直接插入排序12. 當待排序的整數(shù)是有序序列時，采用 (B) 方法比較好，其時間復(fù)雜度為O(n)。A快速排序 B冒泡排序 C歸并排序 D直接選擇排序13. 當待排序的整數(shù)是有序序列時，采用 （A）方法比較差，達到最壞情況下時間復(fù)雜度為O(n2)。A快速排序 B冒泡排序 C歸并排序 D直接選擇排序14. 當待排序的整數(shù)是有序序列時，無論待排序序列排列是否有序，采用 （D）方法的時間復(fù)雜度都是O(n2)。A快速排序 B冒泡排序 C歸并排序 D直接選擇排序15. *堆是一種 (B) 排序。A插入 B選擇 C交換 D歸

18、并16. *若一組記錄的排序碼值序列為40，80，50，30，60，70，利用堆排序方法進行排序，初建的大頂堆是 (D ) 。A80，40，50，30，60，70B80，70，60，50，40，30C80，70，50，40，30，60 D80，60，70，30，40，5017. 若一組記錄的排序碼值序列為50，80，30，40，70，60利用快速排序方法，以第一個記錄為基準，得到一趟快速排序的結(jié)果為（B ） 。A30，40，50，60，70，80B40，30，50，80，70，60 C50，30，40，70，60，80D40，50，30，70，60，8018. *下列幾種排序方法中要求輔助空間

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

20、5)結(jié)果應(yīng)為（D ）。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，H23. 給定排序碼值序列為F，B，J，C，E，A，I，D，C，H，對其按字母的字典序列的次序進行排列，冒泡排序(大數(shù)下沉)的第一趟排序結(jié)果應(yīng)為（C ）。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，H24. 給定排序碼值序列為F，B，J，C，E，A，I，D，C，H，對其按字母的字典序列的次序進行排列，快速

21、排序的第一趟排序結(jié)果為（B ）。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，H25. *給定排序碼值序列為F，B，J，C，E，A，I，D，C，H，對其按字母的字典序列的次序進行排列，二路歸并排序的第一趟排序結(jié)果是（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ù)項的含義，并說明四者的關(guān)系。數(shù)據(jù)(Data

22、):是對信息的一種符號表示。在計算機科學(xué)中是指所有能輸入到計算機中并能被計算機程序處理的符號的總稱。（一個得分點）數(shù)據(jù)元素(Data Element):是數(shù)據(jù)的基本單位，在計算機程序中通常作為一個整體進行考慮和處理，相當于表中的一條記錄。（一個得分點）數(shù)據(jù)項：相當于記錄的“域”, 是數(shù)據(jù)的不可分割的最小單位,如學(xué)號（一個得分點）數(shù)據(jù)對象：性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個子集.例如: 同一個班的所有學(xué)生記錄集合。（一個得分點）關(guān)系：包含關(guān)系：數(shù)據(jù)泛指所有。數(shù)據(jù)對象是數(shù)據(jù)的一個子集，由數(shù)據(jù)元素組成，數(shù)據(jù)元素是由數(shù)據(jù)項組成。（一個得分點）評分標準，總共5個得分點，每段話一個得分。2. 請給出數(shù)

23、據(jù)的邏輯結(jié)構(gòu)的含義，并舉例說明數(shù)據(jù)的邏輯結(jié)構(gòu)通常有哪些。數(shù)據(jù)的邏輯結(jié)構(gòu)：指數(shù)據(jù)元素之間的邏輯關(guān)系。即用自然語言描述數(shù)據(jù)，它與數(shù)據(jù)的存儲無關(guān)，是獨立于計算機的，邏輯結(jié)構(gòu)有四種。（一個得分點）集合結(jié)構(gòu)： 僅同屬一個集合（結(jié)構(gòu)名字0.5個得分點、舉例0.5得分點）線性結(jié)構(gòu): 一對一（1:1) （結(jié)構(gòu)名字0.5個得分點、舉例0.5得分點） 樹 結(jié) 構(gòu): 一對多（1:n) （結(jié)構(gòu)名字0.5個得分點、舉例0.5得分點） 圖 結(jié) 構(gòu): 多對多 (m:n) （結(jié)構(gòu)名字0.5個得分點、舉例0.5得分點）評分標準：每段話一個得分點，總共5個得分點。什么是數(shù)據(jù)的物理結(jié)構(gòu)？有哪些物理結(jié)構(gòu)？數(shù)據(jù)的物理結(jié)構(gòu)與邏輯結(jié)構(gòu)有什

24、么區(qū)別與聯(lián)系？數(shù)據(jù)的物理結(jié)構(gòu)：物理結(jié)構(gòu)亦稱存儲結(jié)構(gòu)，是數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機存儲器內(nèi)的表示（或映像）。它依賴于計算機。（一個得分點）存儲結(jié)構(gòu)可分為4大類：順序、鏈式、索引、散列。（共2個得分點，一個0.5得分點）區(qū)別：數(shù)據(jù)的邏輯結(jié)構(gòu)屬于用戶視圖，是面向問題的，數(shù)據(jù)的存儲結(jié)構(gòu)屬于具體實現(xiàn)的視圖，是面向計算機的。（一個得分點）聯(lián)系：一種數(shù)據(jù)的邏輯結(jié)構(gòu)可以用多種存儲結(jié)構(gòu)來存儲，而采用不同的存儲結(jié)構(gòu)其處理的效率往往不同。（一個得分點）評分標準：共5個得分點，按照每段話各自標注的得分點進行評分。3. 求兩個正整數(shù) m，n 中的最大數(shù)MAX的算法 （1）若 m n 則 max=m （2）若 m = n 則

25、 max=n 請根據(jù)上述算法解釋一下算法的組成要素有哪些，分別是什么。算法由操作、控制結(jié)構(gòu)、數(shù)據(jù)結(jié)構(gòu)3要素組成操作包含：算術(shù)運算、關(guān)系比較、邏輯運算、數(shù)據(jù)傳送（輸入、輸出、賦值）（一個得分點）例子中有關(guān)系比較和賦值計算的操作。（一個得分點）控制結(jié)構(gòu)包含：順序結(jié)構(gòu)、選擇結(jié)構(gòu)、循環(huán)結(jié)構(gòu)（一個得分點）例子中有選擇結(jié)構(gòu)（一個得分點）數(shù)據(jù)結(jié)構(gòu)：算法操作的對象是數(shù)據(jù)，數(shù)據(jù)間的邏輯關(guān)系、數(shù)據(jù)的存儲方式及處理方式就是數(shù)據(jù)結(jié)構(gòu)。（一個得分點）本例是數(shù)值問題，涉及到兩個正整數(shù)，因此使用基本的整數(shù)類型就可以解決問題。（一個得分點）評分標準：本題共6個得分點，每段話一個得分點。4. 簡述算法的基本性質(zhì)1）輸入：0個或

26、多個輸入2）輸出：1個或多個輸出3）有窮性：算法必須在有限步內(nèi)結(jié)束4）確定性：組成算法的操作必須清晰無二義性5）可行性：組成算法的操作必須能夠在計算機上實現(xiàn)評分標準，本題共5個得分點，每個要點一分。5. 簡述算法的設(shè)計要求1、正確性（correctness）2、可讀性（readability）3、健壯性（robustness）4、通用性（generality）5、效率與存儲的要求（執(zhí)行算法所耗費的存儲空間、執(zhí)行算法所耗費的時間）評分標準，本題共5個得分點，每個要點一分。6. 評價算法好壞的3條主要標準1）算法實現(xiàn)所耗費的時間。2）算法實現(xiàn)所耗費的存儲空間，其中主要考慮輔助存儲空間。3）算法應(yīng)易

27、于理解、易于編碼、易于調(diào)試等。評分標準，本題共3個得分點，每個要點一分。7. 請簡述數(shù)據(jù)結(jié)構(gòu)所研究的三種基本結(jié)構(gòu)，以及數(shù)據(jù)元素間的關(guān)系。線性結(jié)構(gòu)：數(shù)據(jù)元素之間一對一的關(guān)系。（2分）樹形結(jié)構(gòu)：數(shù)據(jù)元素之間一對多的關(guān)系。（1.5分）圖形結(jié)構(gòu)：數(shù)據(jù)元素之間多對多的關(guān)系。（1.5分）8. 請問算法的分析和評價的兩個標準，以及各自作用。時間復(fù)雜度：評估算法運行所需時間。（1.5+1分）空間復(fù)雜度：評估算法運行時所需最大存儲空間。（1.5+1分）9. 請說出三種邏輯數(shù)據(jù)結(jié)構(gòu)，以及他們的特點。（5分）（1）線性結(jié)構(gòu)：數(shù)據(jù)元素只有一個前驅(qū)數(shù)據(jù)元素和一個后繼數(shù)據(jù)元素。（2分）（2）樹結(jié)構(gòu)：每個數(shù)據(jù)元素只有一個前

28、驅(qū)數(shù)據(jù)元素，可有零個或若干個后繼數(shù)據(jù)元素。（1.5分）（3）圖結(jié)構(gòu)：每個數(shù)據(jù)元素可有零個或若干個前驅(qū)數(shù)據(jù)元素，零個或若干個后繼數(shù)據(jù)元素。（1.5分）10. 評價算法的主要標準是什么？（1）算法實現(xiàn)所耗費的時間（2分）（2）算法實現(xiàn)所耗費的存儲空間，其中主要考慮輔助存儲空間。（2分）（3）算法應(yīng)易于理解、易于編碼、易于調(diào)試。（1分）11. 請說出三種邏輯數(shù)據(jù)結(jié)構(gòu)，并分別畫圖表示它們。（a, 2分，b,c各1.5分）12. 算法的基本性質(zhì)有哪些？并簡述每個特性。(5分)（1）有窮性. . . . . （1分）（2）確定性. . . . . （1分）（3）可行性. . . . . （1分）（4）輸入

29、性. . . . . （1分）（5）輸出性. . . . . （1分）13. 通常從那幾個方面來評價算法的質(zhì)量? (5分)通常從四個方面評價算法的質(zhì)量：正確性、可讀性、健壯性和高效性。（少一個扣1分）14. 請描述線性數(shù)據(jù)結(jié)構(gòu)的兩種存儲方式，并說出其各有什么特點。順序存儲：連續(xù)存儲，易于定位，不易于插入和刪除。（1+1.5分）鏈式存儲：非連續(xù)存儲，不易于定位，易于插入和刪除。（1+1.5分）15. 請問算法的分析和評價的兩種方法，它們關(guān)注點各有什么不同？（簡單）空間效率：關(guān)注算法對內(nèi)存的占用度。（1+1.5分）時間效率：關(guān)注算法的運算速度。（1+1.5分）第二章 線性表1. 請問如果要插入一個

30、數(shù)據(jù)到一個線性表中，順序表和鏈表哪個的效率高？為什么？鏈表的效率高（2分），因為順序表要移動插入位置后的每一個元素的位置給新數(shù)據(jù)騰位置（1.5分）。鏈表只需要將前一個數(shù)據(jù)的指針指向新數(shù)據(jù)并將新數(shù)據(jù)的指針指向后一個數(shù)據(jù)即可（1.5分）。2. 線性表有哪些特點？1）除第一個和最后一個數(shù)據(jù)元素外，每個數(shù)據(jù)元素只有一個前驅(qū)數(shù)據(jù)元素和一個后繼數(shù)據(jù)元素；（2分）2）第一個數(shù)據(jù)元素沒有前驅(qū)數(shù)據(jù)元素；（1.5分）3）最后一個數(shù)據(jù)元素沒有后繼數(shù)據(jù)元素。（1.5分）3. 順序存儲結(jié)構(gòu)的優(yōu)缺點有哪些? (中等)順序存儲結(jié)構(gòu)的優(yōu)點:（2.5分）存儲空間連續(xù)邏輯相鄰，物理相鄰可隨機存取任一元素缺點:（2.5分）插入、刪

31、除操作需要移動大量的元素預(yù)先分配空間需按最大空間分配，利用不充分表容量難以擴充4. 單鏈式存儲結(jié)構(gòu)的優(yōu)缺點有哪些? (中等)單鏈式存儲結(jié)構(gòu)的優(yōu)點:（2.5分）不需預(yù)先分配空間，空間利用充分插入、刪除操作簡單, 無需移動大量的元素表容量易于擴充缺點:（2.5分）每個數(shù)據(jù)元素，除存儲本身信息外，還需空間存儲其直接后繼的信息邏輯相鄰，物理不一定相鄰不可隨機存取任一元素, 只能從鏈表頭依次查找.5. 有順序表A=(a0, a1, a2,.a8,a9,a19)，要在a8,a9之間插入一個元素a20，請描述其操作(思想)步驟。(中等)插入思想或步驟：根據(jù)順序表的存儲特點，要在表中某位置10插入一新數(shù)據(jù)元素

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

33、所有數(shù)據(jù)元素均要從后至前依次向后移一個存儲位置，為新插入結(jié)點騰出第i個位置；（2分）（2）將新數(shù)據(jù)x插入到空余位置i處。（2分）（3）表長度加1. （1分）8. 請描述在順序表中刪除第i個位置的數(shù)據(jù)的過程。（1）然后將從位置i到表尾的所有數(shù)據(jù)元素依次向前移一個存儲位置。（3分）（2）表長度減1. （2分）9. 請描述在一個單鏈表中插入一個數(shù)據(jù)q的插入過程。（1） 找到將插入數(shù)據(jù)位置的前一個結(jié)點p; （1分）（2） q的next值等于p的next值;（2分）（3）p的next值等于q；（2分）10. 請描述從一個單鏈表中刪除一個數(shù)據(jù)的刪除過程。（1）找到將被刪除數(shù)據(jù)的前一個結(jié)點p; （2分）（2

34、）p的next指針指向被刪除數(shù)據(jù)的后一個結(jié)點；（2分）（3）將被刪除數(shù)據(jù)原來的next指針指向null; （1分）第三章 棧和隊列1. 請簡述線性表、棧和隊列三者之間的聯(lián)系。（簡單）（1）線性表、棧和隊列都屬于線性結(jié)構(gòu)。（2分）（2）棧和隊列都是特殊的線性表，并且都有順序存儲、鏈式存儲兩種存儲方式。（1分）（3）棧是一種先進后出的線性表，隊列是一種先進先出的線性表（2分）2. 在計算機進行運算時，需要把十進制轉(zhuǎn)換為二進制。請問答：這種數(shù)制轉(zhuǎn)換可以借助于哪種數(shù)據(jù)結(jié)構(gòu)實現(xiàn)、及原因。答:棧。（2分）原因：（3分）在進行數(shù)值轉(zhuǎn)換時，其實質(zhì)是求余的過程，并且余數(shù)的倒序序列正是所求結(jié)果。棧是一種先進后出的

35、線性結(jié)構(gòu)，能夠滿足這種操作。3. 有一字符序列abcde依次按照某一線性結(jié)構(gòu)存儲，請回答以下問題：（1）、如果該線性結(jié)構(gòu)是隊列，那么，寫出出隊序列。（2）、如果該線性結(jié)構(gòu)是棧，那么，輸出序列可能是d,c,e,a,b嗎，為什么？（3）、如果該線性結(jié)構(gòu)是棧，且輸出序列是abcde。請寫出操作過程。（push (x)：表示把x壓入棧內(nèi)；pop (x)：表示把x彈出棧）答：（1）、abcde（1分）（2）、不可能，因為：d是第一出棧字符，說明a,b已別壓入棧內(nèi)；并且壓入棧的次序為abcde；由以上得出：ab出棧的順序只能是b、a，而不是a、b。所以，出棧序列d,c,e,a,b是不可能的。（2分）（3）

36、、（2分）push (a)，pop (a)push (b)，pop (b)push (c)，pop (c)push (d)，pop (d)push (e)，pop (e)4. 簡述棧和隊列的異同點。相同點：棧和隊列都是只允許在表的端點處進行插入、刪除操作的線性表。（2分）不同點：棧的特點是先進后出，隊列的特點是后進先出。（3分）5. 若依次讀入數(shù)據(jù)元素序列1、2、3，進棧的過程中允許出棧，試寫出各種可能的出棧序列。答:123、132、213、231、321（各1分）6. 如果入棧序列有組成, 請問輸出序列可能有哪些? (較難)輸出序列有5種：C B A, B C A, B A C, A C B

37、 , A B C（各1分）7. 如果有abcde五個數(shù)據(jù)依次全部存入，如果采用隊列和棧來進行存儲，依次取出分別將獲得什么內(nèi)容。（簡單）隊列：abcde （2.5分）棧: edcba （2.5分）8. 設(shè)將整數(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分）9. 循環(huán)隊列的優(yōu)點是什么？如何判斷它的空和滿？(可不考)循環(huán)隊列

38、的優(yōu)點是可以克服順序隊列的假上溢現(xiàn)象，能夠使存儲隊列的向量空間得到充分的利用。（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、 abcd、 bcde、 abcde、。（3分）2. 對于字符串S=12345，請問：（簡單）（1）字符串S的長度是

39、多少？（2）字符串S的子串有幾個，并列出所有子串？答：（1）、5 （1分）（2）、16，（1分）所有字串：1、2、3、4、5、 12、 23、 34 、45、123、 234、 345、 1234、 2345、 12345、。（3分）3. 請問答：什么串的模式匹配？模式匹配算法有幾種？（簡單）答：串的模式匹配是指子串的定位運算，即在主串中查找子串第一次出現(xiàn)的位置。 模式匹配算法有兩種：簡單匹配算法(Brute-Force)、KMP算法。（該題共4個得分點，答對串匹配定義或大意基本相同，得 2 分；答對兩種匹配算，得 2 分，答錯或少答一個 扣 1分）第五章 數(shù)組和廣義表1. 在數(shù)據(jù)結(jié)構(gòu)中，數(shù)組

40、是最基本的結(jié)構(gòu)，請完成以下要求：（1）、定義一個能容納5個整型元素的數(shù)組iAry，且元素的值為10、20、30、40、50 。（2）、*畫出數(shù)組iAry的順序存儲結(jié)構(gòu)。（規(guī)定：整型長度為兩個字節(jié)）（1）、int iAry5= 10、20、30、40、50 （2 分）（2）、如下圖：（3分，根據(jù)情況，酌情扣分）2. 簡述數(shù)組的定義、特點和分類。（簡單）定義：數(shù)組是n個相同數(shù)據(jù)類型的數(shù)據(jù)元素a0,a1,a2,.,an-1構(gòu)成的有限集合。（1個得分點）特點：1）數(shù)組中各元素具有統(tǒng)一的類型；（1個得分點）2）數(shù)組元素的下標一般具有固定的上界和下界，即數(shù)組一旦被定義，它的維數(shù)和維界就不再改變。（1個得分

41、點）3數(shù)組的基本操作比較簡單，除了結(jié)構(gòu)的初始化和銷毀之外，只有存取元素和修改元素值的操作。 （1個得分點）分類：按維度可分為一維數(shù)組、二維數(shù)組、多維數(shù)組（1個得分點）3. 已知一個二維數(shù)組A如下所示。（較難）（1）請按照行優(yōu)先、列優(yōu)先的方式進行順序存儲，給出順序存儲的序列（2個得分點）行優(yōu)先：a11a12a13a21a22a23列優(yōu)先：a11a21a12a22a13a23（2）若a11在內(nèi)存中存儲的地址為，每個元素的存儲空間大小為L，則按照行優(yōu)先的方式和列優(yōu)先的方式分別存儲，其中a22的地址loc(a22)分別為多少（2個得分點）行優(yōu)先：loc(a22)=+4L列優(yōu)先：loc(a22)=+3L（3）對于數(shù)組，除了順序存儲外，還有沒有其他存儲方式？沒有填無，若有，請說明。有，鏈式存儲，如下圖所示（1個得分點）第六章 樹和二叉樹1. 有一樹，如下圖所示： （簡單）請回答以下問題：（1）樹的葉子結(jié)點及其度。（2）非終端結(jié)點及其度。（3）樹的深度。答： （1）、葉子結(jié)點有：D 、E、F