數(shù)據(jù)結(jié)構(gòu)習題C++版

1、、選擇題(D)1、若線性表最常用的操作是存取第i個元素及其前驅(qū)的值，則采用存儲方式節(jié)省時間：A、單鏈表B、雙鏈表C、單循環(huán)鏈表D、順序表。(A)2、將一棵有100個結(jié)點的完全二叉樹從根這一層開始，每一層從左到右依次對結(jié)點進行編號，根結(jié)點編號為1,則編號為49的結(jié)點的左孩子的編號為。A、98B、99C、50D、48(A)3、數(shù)組A1.5,1.6的每個元素占5個單元，將其按行優(yōu)先次序存儲在起始地址為1000的連續(xù)內(nèi)存單元中，則A5,5的地址是。A、1140B、1145C、1120D、1125(C)4、對二叉樹從1開始編號，要求每個結(jié)點的編號大于其左右孩子的編號，同一個結(jié)點的左右孩子中，其左孩子的編

2、號小于其右孩子的編號，則可采用實現(xiàn)編號。A、先序遍歷B、中序遍歷C、后序遍歷D、從根開始進行層次遍(B)5、棧和隊列都是。A、順序存儲的線性結(jié)構(gòu)B、限制存取點的線性結(jié)構(gòu)G鏈式存儲的線性結(jié)構(gòu)D、限制存取點的非線性結(jié)構(gòu)(C)6、若二叉樹的任一結(jié)點出發(fā)到根的路徑上所經(jīng)過的結(jié)點序列按其關(guān)鍵字有序，則該二叉樹是。A、二叉排序樹B、哈夫曼樹C、堆D、AVIM(C)7、在順序表(3,6,8,10,12,15,16,18,21,25,30)中，用折半法查找關(guān)鍵碼值11,所需的關(guān)鍵碼比較次數(shù)為。A、2B、3C、4D、5(C)8、一組記錄的關(guān)鍵字為(46,79,56,38,40,84),禾U用快速排序的方法，以第

3、一記錄為基準得到的一次劃分結(jié)果為。A、38,40,46,56,79,84B、40,38,46,79,56,84C、40,38,46,56,79,84D、40,38,46,84,56,79(D)9、對包含n個元素的哈希表進行查找，平均查找長度為。A、O(log2n)B、O(n)C、O(nlog2n)D、不直接依賴于n(C)10、一個有n個頂點的無向圖最多有邊。A、nB、n(n-1)C、n(n-1)/2D2n(B)11、有一個100*90的稀疏矩陣，非0元素有10個，設(shè)每個整型數(shù)占2字節(jié)，則用三元組表示該矩陣時，所需的字節(jié)數(shù)是。A.60B.66C.18000D.33(B)12、有關(guān)二叉樹下列說法正

4、確的是。A.二叉樹的度為2B.一棵二叉樹的度可以小于2C.二叉樹中至少有一個結(jié)點的度為2D.二叉樹中任何一個結(jié)點的度都為2(C)13、二叉樹的第I層上最多含有結(jié)點數(shù)為()A.21B.21-1-1C.21-1D.21-1(D)14、n個結(jié)點的完全有向圖含有邊的數(shù)目。A.n*nB.n(n+1)C,n/2D.n*(nl)(BD)15、一個有n個結(jié)點的圖，最少有個連通分量，最多有個連通分量。A.0B,1C.n-1D.n(B)16、一個有向無環(huán)圖的拓撲排序序列()是唯一的。A.一定B.不一定(A)17、關(guān)鍵路徑是事件結(jié)點網(wǎng)絡(luò)中()。A.從源點到匯點的最長路徑B.從源點到匯點的最短路徑C.最長回路D.最短

5、回路(D)18、設(shè)一個棧的輸入序列是A,B,C,D,則借助一個棧所得到的輸出序列不可能是。A.A,B,C,DB.D,C,B,AC.A,C,D,BD.D,A,B,C(C)19、將一棵有100個結(jié)點的完全二叉樹從根這一層開始，每一層從左到右依次對結(jié)點進行編號，根結(jié)點編號為1,則編號最大的非葉結(jié)點的編號為0A、48B、49C、50D、511、已知L是帶表頭結(jié)點的非空單鏈表，且圖點既不是頭結(jié)點，也不是尾結(jié)點,請?zhí)顚憚h除圖點直接后繼結(jié)點的主要語句序列(可利用輔助結(jié)點變量Q)：Q=P->NEXT、P->NEXT=P->NEXT->NEXT、free(Q)。2、廣義表A=(),(a,

6、(b,c),d)的表尾Gettail(A)為：(a,(b,c),d)。3、對任意一棵二叉樹，若終端結(jié)點數(shù)為n0,則度為2的結(jié)點數(shù)為：n0-1。4、在順序表(即順序存儲結(jié)構(gòu)的線性表)中插入一個元素，需要平均移動n/2元素。5、已知一棵二叉樹的前序序列為ABDFCE中序序歹為DFBACE則后序序列為：FDBECA。6、通常是以算法執(zhí)行所耗費的時間和所占用的空間來判斷一個算法的優(yōu)劣。7、已知一個3行、4列的二21數(shù)組A(各維下標均從1開始)，如果按“以列為主”的順序存儲，則排在第8個位置的元素是：A23。三、判斷題：正確的在()中填入錯誤的填入“X”。(X)1、線性表的邏輯順序與物理順序總是一致的。

7、(X)2、線性表的順序存儲表示優(yōu)于鏈式存儲表示。(，)3、線性表若采用鏈式存儲表示時所有結(jié)點之間的存儲單元地址可連續(xù)可不連續(xù)。(X)4、二維數(shù)組是其數(shù)組元素為線性表的線性表。(，)5、每種數(shù)據(jù)結(jié)構(gòu)都應具備三種基本運算：插入、刪除和搜索。(X)6、如果一個二叉樹中沒有度為1的結(jié)點，則必為滿二叉樹。(X)7、內(nèi)部排序是指排序過程在內(nèi)存中進行的排序。(，)8、在一個有向圖中，所有頂點的入度之和等于所有頂點的出度之和。(X)9、拓撲排序是按AO刎中每個結(jié)點事件的最早發(fā)行時間對結(jié)點進行排序。(x)10、具有三個結(jié)點的二叉樹有三種。四、分析題1、將關(guān)鍵碼45,24,53,12,28,90依次插入到一棵初始

8、為空的二叉排序樹中，畫出插完所有關(guān)鍵碼后的二叉排序樹。解:2、某二叉樹的結(jié)點數(shù)據(jù)采用順序存儲表示如下：012345678910111213141516171819HIJACDBFGY4553(1)試畫出此二叉樹的圖形表示。(2)寫出結(jié)點D的雙親結(jié)點及左、右子女。解：(1)(2)結(jié)點D的雙親結(jié)點為J,左子女結(jié)點為空，右子女為G3、已知無向圖如下圖1所示，給出圖的鄰接表。從A開始，給出一棵廣度優(yōu)先生成樹。A4、已知一棵樹如圖2所示，要求將該樹轉(zhuǎn)化為二叉樹3題解答4題解答ABCDEFBAAABDCCBCCCDAEADFAFAEAEFA5、已知一個序列abcdefghi,其字符對應的權(quán)分別為:字符ab

9、cdefghi權(quán)51020123048225畫出對應的哈夫曼樹生成過程，并給出每個字符的哈夫曼編碼解：字符abcdefghi編碼000011011110011000011110000010016、有如圖4所示的帶權(quán)圖，使用普里姆算法來求最小生成樹，將邊的加入順序填入下表中。解答:序號12345678邊d-ee-he-ch-ff-gh-ic-bb-a五、設(shè)計題1、假設(shè)稱正讀和反讀都相同的字符序列為“回文”，例如，abba'和'abcba'是回文，'abcde'和'ababab'則不是回文。試寫一個算法判別讀入的一個以'為結(jié)束符的字符

10、序列是否是“回文”。2、若矩陣Amxn中的某個元素aij是第i行中的最小值，同時又是第j列中的最Amx大值，則稱此元素為該矩陣中的一個馬鞍點。假設(shè)以二維數(shù)組存儲矩陣n,試編寫求出矩陣中所有馬鞍點的算法。解答：1、intPalindrome_Test()/陰J別輸入的字符串是否回文序列，是則返回1,否則返回0(InitStack(S);InitQueue(Q);while(c=getchar()!='')(Push(S,c);EnQueue(Q,c);狗時使用棧和隊列兩種結(jié)構(gòu)while(!StackEmpty(S)(Pop(S,a);DeQueue(Q,b);if(a!=b)returnERROR;returnOK;/Palindrome_Test2、voidGet_Saddle(intAmn)/求矩陣A中的馬鞍點(for(i=0;i<m;i+)(for(min=Ai0,j=0;j<n;j+)if(Aij<min)min=Aij;/求一行中的最小值for(j=0;