1、.-簡答題比較兩個概念的相同和異同1. 簡述以下概念：數據，數據元素，數據類型，數據結構，邏輯結構，存儲結構，線性結構，非線性結構。數據:是客觀事物的符號表示，指所有能輸入到計算機中并被計算機程序處理的符號的總稱。數據元素：是數據的基本單位，在計算機常作為一個整體進行考慮和處理。在有些情況下，數據元素也稱為元素、結點、記錄等。數據類型：是具有相同性質的計算機數據的集合及其在這個數據集合上的一組操作。邏輯結構：指的是數據之間的相互關系，即數據的組織形式。存儲結構：數據對象在計算機中的存儲表示，也稱為物理結構。線性結構：線性結構的邏輯特征是：有且僅有一個開始結點和終端結點，并且所有結點都最多只有一

2、個直接前趨和一個直接后繼。非線性結構：非線性結構的邏輯特征是一個結點可能有多個直接前趨和直接后繼。2. 比較C語言與pascal語言的差異。C語言和Pascal語言是目前對計算機發展影響較深的兩門計算機程序設計語言。兩種語言各有特點：Pascal語言是一種結構式程序設計語言，最初是為系統地教授程序設計而發明的，語法嚴謹，特點是簡明化和結構化，適合教學，科學計算等。C語言那么是國際上應用最廣泛的計算機中級語言，具有語言簡潔緊湊，使用方便靈活及運算符豐富等特點，語法限制不嚴格，程序設計自由度大，程序可移植性好。3. 試描述頭指針、頭結點、開始結點的區別，并說明頭指針和頭結點的作用。開始結點是指鏈表

3、中的第一個結點，也就是沒有直接前趨的那個結點。鏈表的頭指針是一指向鏈表開始結點的指針(沒有頭結點時)，單鏈表由頭指針唯一確定，因此單鏈表可以用頭指針的名字來命名。頭結點是在鏈表的開始結點之前附加的一個結點。有了頭結點之后，頭指針指向頭結點，不論鏈表否為空，頭指針總是非空。而且頭指針的設置使得對鏈表的第一個位置上的操作與在表其他位置上的操作一致(都是在某一結點之后)。4. 何時選用順序表、何時選用鏈表作為線性表的存儲結構為宜答：在實際應用中，應根據具體問題的要求和性質來選擇順序表或鏈表作為線性表的存儲結構，通常有以下幾方面的考慮： 1.基于空間的考慮。當要求存儲的線性表長度變化不大，易于事先確定

4、其大小時，為了節約存儲空間，宜采用順序表；反之，當線性表長度變化大，難以估計其存儲規模時，采用動態鏈表作為存儲結構為好。 2.基于時間的考慮。假設線性表的操作主要是進行查找，很少做插入和刪除操作時，采用順序表做存儲結構為宜；反之，假設需要對線性表進行頻繁地插入或刪除等的操作時，宜采用鏈表做存儲結構。并且，假設鏈表的插入和刪除主要發生在表的首尾兩端，那么采用尾指針表示的單循環鏈表為宜。5. 為什么在單循環鏈表中設置尾指針比設置頭指針更好 答：尾指針是指向終端結點的指針，用它來表示單循環鏈表可以使得查找鏈表的開始結點和終端結點都很方便，設一帶頭結點的單循環鏈表，其尾指針為rear，那么開始結點和終

5、端結點的位置分別是rear-next-next 和 rear, 查找時間都是O(1)。假設用頭指針來表示該鏈表，那么查找終端結點的時間為O(n)。6. 比較以下每隊術語的區別空串和空格串；串常量和串變量；主串和子串；靜態分配的順序串和動態分配的順序串；目標串和模式串；有效位移和無效位移。答：空串是指不包含任何字符的串，它的長度為零。空格串是指包含一個或多個空格的串，空格也是字符。串常量是指在程序中只可引用但不可改變其值的串。串變量是可以在運行中改變其值的。主串和子串是相對的，一個串中任意個連續字符組成的串就是這個串的子串，而包含子串的串就稱為主串。靜態分配的順序串是指串的存儲空間是確定的，即串

6、值空間的大小是靜態的，在編譯時刻就被確定。動態分配的順序串是在編譯時不分配串值空間，在運行過程中用malloc和free等函數根據需要動態地分配和釋放字符數組的空間(這個空間長度由分配時確定，也是順序存儲空間)。 目標串和模式串:在串匹配運算過程中，將主串稱為目標串，而將需要匹配的子串稱為模式串，兩者是相對的。 有效位移和無效位移：在串定位運算中，模式串從目標的首位開始向右位移，每一次合法位移后如果模式串與目標中相應的字符相同，那么這次位移就是有效位移(也就是從此位置開始的匹配成功)，反之，假設有不相同的字符存在，那么此次位移就是無效位移(也就是從此位置開始的匹配失敗)。串名和串值的區別串變量

7、的名字代表該串的首地址，即第一個字符的地址。串變量的值指的是該變量中存放的字符串。7.比較棧與隊列的區別棧與隊列的相同點：1.都是線性結構。2.插入操作都是限定在表尾進行。3.都可以通過順序結構和鏈式結構實現。、4.插入與刪除的時間復雜度都是O1，在空間復雜度上兩者也一樣。5.多鏈棧和多鏈隊列的管理模式可以相同。棧與隊列的不同點：1.刪除數據元素的位置不同，棧的刪除操作在表尾進行，隊列的刪除操作在表頭進行。2.應用場景不同；常見棧的應用場景包括括號問題的求解，表達式的轉換和求值，函數調用和遞歸實現，深度優先搜索遍歷等；常見的隊列的應用場景包括計算機系統中各種資源的管理，消息緩沖器的管理和廣度優

8、先搜索遍歷等。3.順序棧能夠實現多棧空間共享，而順序隊列不能。6.2 一棵度為2的有序樹與一棵二叉樹有何區別 答：一棵度為二的有序樹與一棵二叉樹的區別在于:有序樹的結點次序是相對于另一結點而言的，如果有序樹中的子樹只有一個孩子時，這個孩子結點就無須區分其左右次序，而二叉樹無論其孩子數是否為2，均需確定其左右次序，也就是說二叉樹的結點次序不是相對于另一結點而言而是確定的。選擇填空判斷1. 一個深度為h的滿k叉樹有如下性質：第h層上的結點都是葉子結點，其余各層上每個結點都有k棵非空子樹。如果按層次順序(同層自左至右)從1開始對全部結點編號，問：(1)各層的結點數目是多少 (2)編號為i的結點的雙親

9、結點(假設存在)的編號是多少(3)編號為i的結點的第j個孩子結點(假設存在)的編號是多少 (4)編號為i的結點的有右兄弟的條件是什么 其右兄弟的編號是多少 解：(1) 層號為h的結點數目為kh-1(2) 編號為i的結點的雙親結點的編號是：|_ (i-2)/k _|+1(不大于(i-2)/k的最大整數。也就是(i-2)與k整除的結果以下/表示整除。(3) 編號為i的結點的第j個孩子結點編號是：k*(i-1)+1+j; (4) 編號為i的結點有右兄弟的條件是(i-1)能被k整除右兄弟的編號是i+1. 6.6高度為h的完全二叉樹至少有多少個結點至多有多少個結點 解：高度為h的完全二叉樹至少有2h-1

10、個結點，至多有2h-1個結點(也就是滿二叉樹)。2. 在具有n個結點的k叉樹(k=2)的k叉鏈表表示中，有多少個空指針 解：n個結點的K叉樹共有n*k個指針域，已使用的指針域為n-1,所以空指針的個數為：n(k-1)+1;(1) 前序序列和中序序列相同的二叉樹是：空二叉樹或沒有左子樹的二叉樹(右單支樹)。(2) 中序序列和后序序列相同的二叉樹是：空二叉樹或沒有右子樹的二叉樹(左單支樹)。(3) 前序序列和后序序列相同的二叉樹是：空二叉樹或只有根的二叉樹。(4) 前序、中序、后序序列均相同的二叉樹：空樹或只有根結點的二叉樹。3. 在何種線索樹中，線索對求指定結點在相應次序下的前趨和后繼并無幫助

11、答：分別在前序線索二叉樹和后序線索二叉樹中查找前趨和后繼時，線索無幫助作用。4. 高度為h的嚴格二叉樹至少有多少個結點至多有多少個結點 答：所謂嚴格二叉樹是指該樹中沒有度數為1的分支結點的二叉樹。所以：高度為h的的嚴格二叉樹至少有2h-1個結點；至多有2h-1個結點(即滿二叉樹)。5. DFS深度優先搜索遍歷和BFS廣度優先搜索遍歷遍歷各采用什么樣的數據結構來暫存頂點當要求連通圖的生成樹的高度最小，應采用何種遍歷 答：DFS遍歷采用棧來暫存頂點。BFS采用隊列來暫存頂點。當要求連通圖的生成樹的高度最小時，應采用BFS遍歷。當候選輕邊集中的輕邊數始終等于1條時，其最小生成樹是唯一的。假設關鍵字是

12、非負整數、快速排序、歸并、堆和基數排序啊一個最快假設要求輔助空間為O(1)，那么應選擇誰？假設要求排序是穩定的，且關鍵字是實數，那么應選擇誰 答：假設關鍵字是非負整數，那么基數排序最快；假設要求輔助空間為O(1)那么應選堆排序；假設要求排序是穩定的，且關鍵字是實數，那么應選歸并排序，因為基數排序不適用于實數，雖然它也是穩定的。恰好有n(n-1)/2條邊的無向圖稱為無向完全圖，恰有nn-1條邊的有向圖稱為有向完全圖。假設將圖的每條邊都賦上一個權，那么稱這種帶權圖為網絡。通常權是具有某種意義的數，比如，它們可以表示兩個定點之間的距離，耗費等。假設圖中的邊的數目遠遠小于n2是即en2，此類圖稱作稀疏

13、圖，這時用鄰接矩陣表示節省存儲空間；假設e接近于n2準確地說，無向圖e接近于nn-1/2，有向圖e接近于nn-1，此類圖稱作稠密圖。深度優先搜索遍歷類似于樹的前序遍歷；它的特點是盡可能先對縱深方向進行搜索，故稱之為深度優先搜素。廣度優先搜索遍歷類似于樹的按層次遍歷；它的特點是盡可能先對橫向進行搜索。把生成樹各邊的權值總和稱為生成樹的權，并把權最小的生成樹稱為G的最小生成樹。交換排序的基本思想是：兩兩比較待排序記錄的關鍵字，發現兩個記錄的次序相反時即進行交換，直到沒有反序的記錄為止。起泡排序和快速排序屬于兩種交換排序。算法的時間復雜度是一個函數，它定性描述了該算法的運行時間。這是一個關于代表算法

14、輸入值的HYPERLINK s:/baike.baidu /item/%E5%AD%97%E7%AC%A6%E4%B8%B2 t s:/baike.baidu /item/%E6%97%B6%E9%97%B4%E5%A4%8D%E6%9D%82%E5%BA%A6/_blank字符串的長度的函數。時間復雜度常用HYPERLINK s:/baike.baidu /item/%E5%A4%A7O%E7%AC%A6%E5%8F%B7 t s:/baike.baidu /item/%E6%97%B6%E9%97%B4%E5%A4%8D%E6%9D%82%E5%BA%A6/_blank大O符號表述，不包括

15、這個函數的低階項和首項系數。時間復雜度是指執行算法所需要的計算工作量；而空間復雜度是指執行這個算法所需要的存空間。算法的復雜性表達在運行該算法時的計算機所需資源的多少上，計算機資源最重要的是時間和空間即寄存器資源，因此復雜度分為時間和空間復雜度。計算題棧P42頁例如：9*3-1+2，屬于中綴表達式。我們需要將它轉換成后綴表達式：9 3 1 - * 2 +的形式求值。舉個例子：“9+(3-1)*3+10/2應該是先化為后綴表達式： 9 3 1-3*+10/+從左到右遍歷表達式的每個數字和符號，遇到數字就進棧，遇到符號就將棧頂的兩個數字出棧，進行運算，運算結果進棧，一直到最終獲得結果。解： 9 3

16、 1入棧遇到減號，1,3出棧3-1將結果重新入棧然后遇到3，進棧，遇到*，3和3-1出棧，變成3-1*3，將該結果再進棧，然后遇到的是加號，數據出棧，9+3-1*3，然后將該結果入棧，這里是15，直接將15入棧，同時下面數據遍歷到10,2也入棧遍歷繼續，到/號，出棧棧頂兩個數據元素：10/2，結果入棧，最后遍歷+，棧頂兩個數據元素出棧15+5 =20 ，為最終的結果。或解：畫出圖為： + + / 9 * 10 2 - 3 3 1 結果為9+(3-1)*3+10/2=20哈夫曼樹p112頁例題：假設用于通訊的電文僅由8個字母組成，字母在電文中出現的頻率分別為：7，19,2，6,32,3,21,10。試為這8個字母設計哈夫曼編碼。前中后序：二叉樹的前序序列為BCDEFAG，中序序列為DCFAEGB，請問后序序列