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

2、個(gè)直接前趨和一個(gè)直接后繼。非線(xiàn)性結(jié)構(gòu)：非線(xiàn)性結(jié)構(gòu)的邏輯特征是一個(gè)結(jié)點(diǎn)可能有多個(gè)直接前趨和直接后繼。2. 比較C語(yǔ)言與pascal語(yǔ)言的差異。C語(yǔ)言和Pascal語(yǔ)言是目前對(duì)計(jì)算機(jī)發(fā)展影響較深的兩門(mén)計(jì)算機(jī)程序設(shè)計(jì)語(yǔ)言。兩種語(yǔ)言各有特點(diǎn)：Pascal語(yǔ)言是一種結(jié)構(gòu)式程序設(shè)計(jì)語(yǔ)言，最初是為系統(tǒng)地教授程序設(shè)計(jì)而發(fā)明的，語(yǔ)法嚴(yán)謹(jǐn)，特點(diǎn)是簡(jiǎn)明化和結(jié)構(gòu)化，適合教學(xué)，科學(xué)計(jì)算等。C語(yǔ)言那么是國(guó)際上應(yīng)用最廣泛的計(jì)算機(jī)中級(jí)語(yǔ)言，具有語(yǔ)言簡(jiǎn)潔緊湊，使用方便靈活及運(yùn)算符豐富等特點(diǎn)，語(yǔ)法限制不嚴(yán)格，程序設(shè)計(jì)自由度大，程序可移植性好。3. 試描述頭指針、頭結(jié)點(diǎn)、開(kāi)始結(jié)點(diǎn)的區(qū)別，并說(shuō)明頭指針和頭結(jié)點(diǎn)的作用。開(kāi)始結(jié)點(diǎn)是指鏈表

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

4、其大小時(shí)，為了節(jié)約存儲(chǔ)空間，宜采用順序表；反之，當(dāng)線(xiàn)性表長(zhǎng)度變化大，難以估計(jì)其存儲(chǔ)規(guī)模時(shí)，采用動(dòng)態(tài)鏈表作為存儲(chǔ)結(jié)構(gòu)為好。 2.基于時(shí)間的考慮。假設(shè)線(xiàn)性表的操作主要是進(jìn)行查找，很少做插入和刪除操作時(shí)，采用順序表做存儲(chǔ)結(jié)構(gòu)為宜；反之，假設(shè)需要對(duì)線(xiàn)性表進(jìn)行頻繁地插入或刪除等的操作時(shí)，宜采用鏈表做存儲(chǔ)結(jié)構(gòu)。并且，假設(shè)鏈表的插入和刪除主要發(fā)生在表的首尾兩端，那么采用尾指針表示的單循環(huán)鏈表為宜。5. 為什么在單循環(huán)鏈表中設(shè)置尾指針比設(shè)置頭指針更好 答：尾指針是指向終端結(jié)點(diǎn)的指針，用它來(lái)表示單循環(huán)鏈表可以使得查找鏈表的開(kāi)始結(jié)點(diǎn)和終端結(jié)點(diǎn)都很方便，設(shè)一帶頭結(jié)點(diǎn)的單循環(huán)鏈表，其尾指針為rear，那么開(kāi)始結(jié)點(diǎn)和終

5、端結(jié)點(diǎn)的位置分別是rear-next-next 和 rear, 查找時(shí)間都是O(1)。假設(shè)用頭指針來(lái)表示該鏈表，那么查找終端結(jié)點(diǎn)的時(shí)間為O(n)。6. 比較以下每隊(duì)術(shù)語(yǔ)的區(qū)別空串和空格串；串常量和串變量；主串和子串；靜態(tài)分配的順序串和動(dòng)態(tài)分配的順序串；目標(biāo)串和模式串；有效位移和無(wú)效位移。答：空串是指不包含任何字符的串，它的長(zhǎng)度為零?？崭翊侵赴粋€(gè)或多個(gè)空格的串，空格也是字符。串常量是指在程序中只可引用但不可改變其值的串。串變量是可以在運(yùn)行中改變其值的。主串和子串是相對(duì)的，一個(gè)串中任意個(gè)連續(xù)字符組成的串就是這個(gè)串的子串，而包含子串的串就稱(chēng)為主串。靜態(tài)分配的順序串是指串的存儲(chǔ)空間是確定的，即串

6、值空間的大小是靜態(tài)的，在編譯時(shí)刻就被確定。動(dòng)態(tài)分配的順序串是在編譯時(shí)不分配串值空間，在運(yùn)行過(guò)程中用malloc和free等函數(shù)根據(jù)需要?jiǎng)討B(tài)地分配和釋放字符數(shù)組的空間(這個(gè)空間長(zhǎng)度由分配時(shí)確定，也是順序存儲(chǔ)空間)。 目標(biāo)串和模式串:在串匹配運(yùn)算過(guò)程中，將主串稱(chēng)為目標(biāo)串，而將需要匹配的子串稱(chēng)為模式串，兩者是相對(duì)的。 有效位移和無(wú)效位移：在串定位運(yùn)算中，模式串從目標(biāo)的首位開(kāi)始向右位移，每一次合法位移后如果模式串與目標(biāo)中相應(yīng)的字符相同，那么這次位移就是有效位移(也就是從此位置開(kāi)始的匹配成功)，反之，假設(shè)有不相同的字符存在，那么此次位移就是無(wú)效位移(也就是從此位置開(kāi)始的匹配失敗)。串名和串值的區(qū)別串變量

7、的名字代表該串的首地址，即第一個(gè)字符的地址。串變量的值指的是該變量中存放的字符串。7.比較棧與隊(duì)列的區(qū)別棧與隊(duì)列的相同點(diǎn)：1.都是線(xiàn)性結(jié)構(gòu)。2.插入操作都是限定在表尾進(jìn)行。3.都可以通過(guò)順序結(jié)構(gòu)和鏈?zhǔn)浇Y(jié)構(gòu)實(shí)現(xiàn)。、4.插入與刪除的時(shí)間復(fù)雜度都是O1，在空間復(fù)雜度上兩者也一樣。5.多鏈棧和多鏈隊(duì)列的管理模式可以相同。棧與隊(duì)列的不同點(diǎn)：1.刪除數(shù)據(jù)元素的位置不同，棧的刪除操作在表尾進(jìn)行，隊(duì)列的刪除操作在表頭進(jìn)行。2.應(yīng)用場(chǎng)景不同；常見(jiàn)棧的應(yīng)用場(chǎng)景包括括號(hào)問(wèn)題的求解，表達(dá)式的轉(zhuǎn)換和求值，函數(shù)調(diào)用和遞歸實(shí)現(xiàn)，深度優(yōu)先搜索遍歷等；常見(jiàn)的隊(duì)列的應(yīng)用場(chǎng)景包括計(jì)算機(jī)系統(tǒng)中各種資源的管理，消息緩沖器的管理和廣度優(yōu)

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

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

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

11、答：分別在前序線(xiàn)索二叉樹(shù)和后序線(xiàn)索二叉樹(shù)中查找前趨和后繼時(shí)，線(xiàn)索無(wú)幫助作用。4. 高度為h的嚴(yán)格二叉樹(shù)至少有多少個(gè)結(jié)點(diǎn)至多有多少個(gè)結(jié)點(diǎn) 答：所謂嚴(yán)格二叉樹(shù)是指該樹(shù)中沒(méi)有度數(shù)為1的分支結(jié)點(diǎn)的二叉樹(shù)。所以：高度為h的的嚴(yán)格二叉樹(shù)至少有2h-1個(gè)結(jié)點(diǎn)；至多有2h-1個(gè)結(jié)點(diǎn)(即滿(mǎn)二叉樹(shù))。5. DFS深度優(yōu)先搜索遍歷和BFS廣度優(yōu)先搜索遍歷遍歷各采用什么樣的數(shù)據(jù)結(jié)構(gòu)來(lái)暫存頂點(diǎn)當(dāng)要求連通圖的生成樹(shù)的高度最小，應(yīng)采用何種遍歷 答：DFS遍歷采用棧來(lái)暫存頂點(diǎn)。BFS采用隊(duì)列來(lái)暫存頂點(diǎn)。當(dāng)要求連通圖的生成樹(shù)的高度最小時(shí)，應(yīng)采用BFS遍歷。當(dāng)候選輕邊集中的輕邊數(shù)始終等于1條時(shí)，其最小生成樹(shù)是唯一的。假設(shè)關(guān)鍵字是

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

13、圖，這時(shí)用鄰接矩陣表示節(jié)省存儲(chǔ)空間；假設(shè)e接近于n2準(zhǔn)確地說(shuō)，無(wú)向圖e接近于nn-1/2，有向圖e接近于nn-1，此類(lèi)圖稱(chēng)作稠密圖。深度優(yōu)先搜索遍歷類(lèi)似于樹(shù)的前序遍歷；它的特點(diǎn)是盡可能先對(duì)縱深方向進(jìn)行搜索，故稱(chēng)之為深度優(yōu)先搜素。廣度優(yōu)先搜索遍歷類(lèi)似于樹(shù)的按層次遍歷；它的特點(diǎn)是盡可能先對(duì)橫向進(jìn)行搜索。把生成樹(shù)各邊的權(quán)值總和稱(chēng)為生成樹(shù)的權(quán)，并把權(quán)最小的生成樹(shù)稱(chēng)為G的最小生成樹(shù)。交換排序的基本思想是：兩兩比較待排序記錄的關(guān)鍵字，發(fā)現(xiàn)兩個(gè)記錄的次序相反時(shí)即進(jìn)行交換，直到?jīng)]有反序的記錄為止。起泡排序和快速排序?qū)儆趦煞N交換排序。算法的時(shí)間復(fù)雜度是一個(gè)函數(shù)，它定性描述了該算法的運(yùn)行時(shí)間。這是一個(gè)關(guān)于代表算法

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字符串的長(zhǎng)度的函數(shù)。時(shí)間復(fù)雜度常用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符號(hào)表述，不包括

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

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