數(shù)據(jù)結(jié)構(gòu)與算法試題及答案

1、緒論一、填空題1、數(shù)據(jù)的邏輯結(jié)構(gòu)是數(shù)據(jù)元素之間的邏輯關(guān)系，通常有下列4類：集合_、線性結(jié)構(gòu)_、樹型結(jié)構(gòu)_、圖狀結(jié)構(gòu)2、數(shù)據(jù)的存儲結(jié)構(gòu)是數(shù)據(jù)在計算機存儲器里的表示，主要有4種基本存儲方法：順序存儲_、鏈?zhǔn)酱鎯、索引存儲、散列存儲二、選擇題1、一個算法必須在執(zhí)行有窮步之后結(jié)束，這是算法的（B）。A、正確性B、有窮性C、確定性D、可行性2、算法的每一步必須有確切的定義，也就是說，對于每步需要執(zhí)行的動作必須嚴格、清楚地給出規(guī)定，這是算法的（A）oA、止確性B、有窮性C、確定性D、可行性3、算法原則上都是能夠有機器或人所完成的。整個算法好象是一個解決問題的“工作序列”，其中的每一步都是我們力所能及的一

2、個動作，這是算法的（D）A、正確性B、有窮性C、確定性D、可行性三、簡單題1、什么是數(shù)據(jù)結(jié)構(gòu)？什么是算法？兩者有什么關(guān)系？什么是數(shù)據(jù)結(jié)構(gòu)？費據(jù)結(jié)構(gòu)是按某種邏輯關(guān)系組織起來的一批數(shù)據(jù)（或稱帶結(jié)構(gòu)的數(shù)據(jù)元素的集合）應(yīng)用計算機語言并按一定的存儲表示方式把它們存儲在訃算機的存儲器也并在其上定義了一個運算的集合。什么是算法？廣義地說，為解決個問題而采取的方法和步驟,就稱為“算法”兩者有什么關(guān)系？算法與數(shù)據(jù)結(jié)構(gòu)關(guān)系密切。選擇的數(shù)據(jù)結(jié)構(gòu)是否恰當(dāng)直接影響算法的效率；而數(shù)據(jù)結(jié)構(gòu)的優(yōu)劣由算法的執(zhí)行來體現(xiàn)。2、什么是復(fù)雜度和空間復(fù)雜度？時間復(fù)雜度是指執(zhí)行算法所需要的計算工作疑：而空間復(fù)雜度是指執(zhí)行這個算法所需要的內(nèi)

3、存空間。3、數(shù)據(jù)的邏輯結(jié)構(gòu)分幾種？存儲結(jié)構(gòu)又有哪幾種？數(shù)據(jù)的邏輯結(jié)構(gòu)：結(jié)構(gòu)左義中的關(guān)系”，描述的是數(shù)據(jù)元素之間的邏借關(guān)系；包括線性結(jié)構(gòu)（線性表、棧、隊、串、數(shù)組）和非線性結(jié)構(gòu)（圖形結(jié)構(gòu)、樹形結(jié)構(gòu)）；數(shù)據(jù)的存儲結(jié)構(gòu)（物理結(jié)構(gòu)）：數(shù)據(jù)結(jié)構(gòu)在計算機中的表示（又稱映像），包括數(shù)據(jù)元素的表示和關(guān)系德表示。有順序存貯（向量存貯）、鏈?zhǔn)酱尜A、索引存貯、散列存貯。線性表1、一個線性表第一個元素的存儲地址是100,每個元素的長度為2,則第5個元素的地址是（B）o（A）110（B）108（C）100（D）1202、向一個有127個元素的順序表中插入一個新元素并保持原來順序不變，平均要移動（C）個元素。（A）64（

4、B）63（C）63.5（D）72、線性表采用鏈?zhǔn)酱鎯Y(jié)構(gòu)時，其地址（D）o（A）必須是連續(xù)的（B）部分地址必須是連續(xù)的(C)一定是不連續(xù)的(D)連續(xù)與否均可以3 .在一個單鏈表中，若p所指結(jié)點不是最后結(jié)點，在P之后插入s所指結(jié)點，則執(zhí)行但)。(A)s->next=p;p->next=s;(B)s->next=p->next;p->next=s;(C)s->next=p->next;p=s;(D)p->next=s;s->next=p;4 .在一個單鏈表中，若刪除p所指結(jié)點的后續(xù)結(jié)點，則執(zhí)行(A)(A) p->next=p->ne

5、xt->next;(B) p=p->next;p->next=p->next->next;(C) p->next=p->next;(D)p=p->next->next;5 .在長度為n的順序表的第i(IWiWn+l)個位置上插入一個元素，元素的移動次數(shù)為一，刪除第i個位置元素，元素的移動次數(shù)為旦。A.n-i+1B.n-iC.iD.i-16 .算法分析的兩個主要方面是_A_。A.空間復(fù)雜性和時間復(fù)雜性B.正確性和簡明性C.可讀性和文檔性D.數(shù)據(jù)復(fù)雜性和程序復(fù)雜性7 .寫出順序表插入、刪除及就地逆置算法(見實驗)順序表的逆置voidrevers

6、e(SqListL)inti,j,k;for(i=0,j=L.length-1;i<j;i+,j一)k=L.elemi;L.elemi=Lelemj;Lelemj=k;)8、寫出單鏈表插入、刪除、求表長及逆置算法(見教材”2頁算法2.19)排序1下列排序算法中，時間復(fù)雜度不受數(shù)據(jù)初始狀態(tài)影響，恒為0(log2n)的是_A_。A.堆排序B.冒泡排序C.直接選擇排序D.快速排序解析：本題考察的是排序的性能。2 .若表R在排序前已按鍵值遞增順序排列，貝LA_算法的比較次數(shù)最少。A.直接插入排序B.快速排序C.堆排序D.選擇排序3 .已知一組關(guān)鍵字29,18,23,1,68,41,8,65,請分

7、別寫出按插入排序、冒泡排序、直接選擇排序和快速排序方法排序過程，每一起排序結(jié)束時的關(guān)鍵字的狀態(tài)。(見書本P47-P52)4 .寫出簡單排序算法和一場快速排序算法等等棧的基礎(chǔ)知識1、若入棧序列是a,。,Gd©則不可能的出棧序列是(C)。(A)edcba(B)decba(C)dceab(D)abode2、判定一個棧ST(最多元素為m。)為空的條件是(B)。(A)ST.top!=-1(B)ST.top=-1(C)ST.top!=mo-1(D)ST.top=mo-13、判定一個棧ST(最多元素為m。)為滿的條件是(D)。(A)ST.top!=0(B)ST.top=0(C)ST.top!=-1

8、(D)ST.top=mo-l4、在n(n>0)個元素的順序棧中插入1個元素的時間復(fù)雜度為(C)。A.O(nlog2n)B.0()C.0(1)D.O(n)5、 在n(n>0)個元素的順序棧中刪除1個元素的時間復(fù)雜度為(D)。A.0(n)B.0()C.O(nlog2n)D.0(1)填空題部分1、棧的特點是(后進先出(或UFO),隊列的特點是(先進先出(或FIFO)o2、線性表、棧和隊列都是(線性)結(jié)構(gòu)，可以在線性表的(任何)位置插入和刪除元素，棧只能在(表尾)插入和刪除元素，隊列只能在(表尾)插入元素和(表首)刪J除元素。3、若隊列的入隊序列是1,2,3,4,則出隊序列是(B)。(A)

9、4,3,2,1(B)1,2,3,4(01,4,3,2(0)3,2,4,1隊列基礎(chǔ)知識1、循環(huán)隊列用數(shù)組存放其元素值，已知其頭尾指針分別是front和rear則當(dāng)前隊列中的元素個數(shù)是(A)。(A)(rear-front+m)%m(B)rear-front+1(C)rear-front-1(D)rear-front2、以數(shù)組Q0m-1存放循環(huán)隊列中的元素，變量rear和qulen分別指示循環(huán)隊列中隊尾元素的實際位置和當(dāng)前隊列中元素的個數(shù)，隊列第一個元素的實際位置是(D)。(A)rear-qulen(B)rear-qulen+m(C)/riqulen(D)I+(rear+mqulen)%m3.設(shè)循環(huán)

10、隊列中數(shù)組的下標(biāo)范圍是其頭尾指針分別為f和r,則判斷循環(huán)隊列滿的條件為但)A.r=fB.f=(r+l)%nC.r=(f+l)%(n+1)D.r=f+l一、填空題1、線性表、棧和隊列都是一線性一結(jié)構(gòu)，線性表可以在_任意位卷插入和刪除元素：對于棧只能在棧頂插入和刪除元素；對于隊列只能在一隊尾插入和一隊首刪除元素。2、棧是一種特殊的線性表，允許插入和刪除運算的一端稱為一棧去，不允許插入和刪除運算的一端稱為.棧底。3、隊列一是被限泄為只能在表的一端進行插入運算，在表的另一端進行刪除運算的線性表。4、向棧中壓入元素的操作是先移動棧頂指針，后一存入元素。5、在操作序列push(l),push(2)Jpop

11、(),push(5)Jpush(7),pop(),push(6)ZJn,棧頂元素是_6,棧底元素是(push(k)表示整數(shù)k入棧，pop表示棧頂元素出棧。)6、用單鏈表表示的鏈?zhǔn)疥犃械年狀^是在鏈表的一鏈尾一位置。二叉樹和樹1 .二叉樹的前序遍歷序列中，任意一個結(jié)點均處在其子女結(jié)點的前面，這種說法(A)(A)正確(B)錯誤2 .由于二叉樹中每個結(jié)點的度最大為2,所以二叉樹是一種特殊的樹，這種說法(B)(A)正確(B)錯誤3 .已知某二叉樹的后序遍歷序列是dabeco中序遍歷序列是debac,它的前序遍歷序列是(D(A)acbed(B)decab(C)deabc(D)cedba4 .某二叉樹的前序

12、遍歷結(jié)點訪問順序是abdgcefh,中序遍歷的結(jié)點訪問順序是dgbaechf,則其后序遍歷的結(jié)點訪問順序是(D(A)bdgcefha(B)gdbeefha(C)bdgaechf(D)gdbehfea5 .在一非空二叉樹的中序遍歷序列中，根結(jié)點的右邊(A)(A)只有右子樹上的所有結(jié)點(B)只有右子樹上的部分結(jié)點(C)只有左子樹上的部分結(jié)點(D)只有左子樹上的所有結(jié)點6 .任一二叉樹的葉子結(jié)點在先、中和后序遍歷序列中的相對次序(A)。(A)不發(fā)生改變(B)發(fā)生改變(C)不能確定(D)以上都不對7、對二叉樹從1開始進行連續(xù)編號，要求每個結(jié)點的編號大于其左右孩子的編號，同一個結(jié)點的左右孩子中，其左孩子

13、的編號小于其右孩子的編號，則可采用_J遍歷實現(xiàn)編號。A.無序B.中序C.后序D.從根開始的層次遍歷8深度為k的二叉樹的結(jié)點總數(shù)，最多為£個。A)2klB)log2kC)2k.iD)2k9 .深度為9的二叉樹中至少有2個結(jié)點。A)29B)28C)9D)29-l10 .二叉樹有n個葉子，沒有度為1的結(jié)點，共有2nI個結(jié)點分析：度為2的結(jié)點有nl個，所以共2n1個結(jié)點。11 .設(shè)一棵完全二叉樹具有1000個結(jié)點，則它有500個葉子結(jié)點，有型個度為2的結(jié)點，有L個結(jié)點只有非空左子樹，有一。個結(jié)點只有非空右子樹。12一棵深度為6的滿二叉樹有絲個葉子和31個分支結(jié)點。13.n個葉子結(jié)點的二叉樹最

14、少有2rv：L結(jié)點。作業(yè)：K一棵哈夫曼樹有19個結(jié)點，則其葉子結(jié)點的個數(shù)是(10)02、有七個帶權(quán)結(jié)點，其權(quán)值分別為3,7,826,10,14,試以它們?yōu)槿~結(jié)點構(gòu)造一棵哈夫曼樹(請按照每個結(jié)點的左子樹根結(jié)點的權(quán)小于等于右子樹根結(jié)點的權(quán)的次序構(gòu)造)，并計算出帶權(quán)路徑長度WPL及該樹的結(jié)點總數(shù)。例：50291514782111105623上圖為樹,所以帶權(quán)路徑長度為2x4+3x4+6x3+10x2+7x3+8x3+14x2=1313、有一電文共使用五種字符a,b,c,d©其出現(xiàn)頻率依次為4,7,5,2,9°(1)、試畫出對應(yīng)的編碼哈夫曼樹(要求左子樹根結(jié)點的權(quán)小于等于右子樹根結(jié)

15、點的權(quán))。(2)、求出每個字符的哈夫曼編碼。(3)、求出傳送電文的總長度。(4).并譯出編碼系列11000111000101011的相應(yīng)電文。(P143)(1)27II189II117II651I24WPL=9*1+嚴2+5*3+(2+4)*4=62(2)5種字符a、b、c、d、e的哈夫曼編碼依次為011、10、00、010.114、對于給定的一組權(quán)值W=1,3,7,8,14,20,28建立哈夫曼樹，并計算帶權(quán)路徑長度。5、假定有7個字符a,b,c,d,e,f,g出現(xiàn)的概率分別為0.07,0.09,0.14,0.23,0.44,0.58,0.77,求這7個字符的哈夫曼編碼。6、某通信過程中使用

16、的編碼有8個字符AbCQEFGH,英出現(xiàn)的次數(shù)分別為20,6,34,11,9,7,8,5o若每個字符采用3位二進制數(shù)編碼，整個通信需要多少字節(jié)？請給出哈夫曼編碼，以及整個通信使用的字節(jié)數(shù)？7、對右圖所示的普通樹，完成以下操作：分別畫出這棵樹的雙親表示法、孩子表示法的存儲結(jié)構(gòu)圖：將這棵樹轉(zhuǎn)換成二叉樹：(3)寫出對上小題得到的二叉樹分別進行前序、中序、后序遍歷所得到的遍歷序列。8,設(shè)一棵二叉樹的先序、中序遍歷序歹lj分別為ABDFCEGH和BFDAGEHC,請寫出分析過程并畫出這棵二叉樹，然后寫出該二叉樹的后序遍歷序列。第7章圖選擇題1 .在一個圖中，所有頂點的度數(shù)之和等于所有邊數(shù)的(C)倍。(A

17、)J/2(B)1(C)2(D)42 .在一個有向圖中，所有頂點的入度之和等于所有頂點的出度之和的但)倍。(A)1/2(B)1(C)2(D)43 .一個有n個頂點的無向圖最多有(C)條邊。(A)n(B)n(n-l)(C)n(n-l)/2(D)2n4 .具有4個頂點的無向完全圖有(A)條邊。(A)6(B)12(C)16(D)205 .具有6個頂點的無向圖至少應(yīng)有(A)條邊才能確保是一個連通圖。(A)5(B)6(C)7(D)86 .在一個具有n個頂點的無向圖中，要連通全部頂點至少需要(C)條邊。(A)n(B)n+1(C)n-1(D)n/27 .對于一個具有n個頂點的無向圖，若采用鄰接矩陣表示，則該矩

18、陣的大小為(D)。(A)n(B)(n-l)2(C)n-1(D)n28 .對于一個具有n個頂點和e條邊的無向圖，若采用鄰接表表示，則表頭數(shù)組的大小為(A),所有鄰接表中的結(jié)點總數(shù)是(C)o(A)(B)n+1(C)n-1(D)n+e(A)e/2(B)e(C)2e(D)n+e9.在含有n個項點有e條邊的無向圖的鄰接矩陣中,零元素的個數(shù)為oA.eB.2eC.n2-eD.n2-2ei。圖的深度優(yōu)先遍歷算法類似于樹的(A)0(A)先根遍歷(B)后根遍歷(C)按層遍歷圖的廣度優(yōu)先遍歷算法類似于樹的(C(A)先根遍歷(B)后根遍歷(C)按層遍歷填空題部分1 .門個頂點的連通圖至少(N-l)條邊。2 .在一個無

19、向圖的鄰接表中，若表結(jié)點的個數(shù)是"，則圖中邊的條數(shù)是（M/2）條。3 .分別用普里姆和克魯斯卡爾算法構(gòu)造下圖所示網(wǎng)絡(luò)的最小生成樹。4 .分別求出圖4從V2出發(fā)按深度優(yōu)先搜索和廣度優(yōu)先搜索算法遍歷得到的頂點序列（假設(shè)圖的存儲結(jié)構(gòu)采用鄰接矩陣表示）。圖45,已知一個有向圖的鄰接表如圖5所示，求出根據(jù)深度優(yōu)先搜索算法從頂點VI出發(fā)遍歷得到的頂點序列。6、對右邊所示的有向圖鄰接矩陣：求出每個頂點的入度和出度。畫出圖的鄰接表；分別寫出自頂點1出發(fā)進行遍歷所得的深度優(yōu)先遹歷序列和廣度優(yōu)先遍歷序列。1234567891023456789100000101010100010000001000100010000000