復(fù)習(xí)題數(shù)據(jù)結(jié)

1、WOR格式專業(yè)資料整理1.數(shù)據(jù)的（A.存儲結(jié)構(gòu)）包括集合、線性、樹和圖B.邏輯結(jié)構(gòu)4種基本類型C.基本運算D.算法描述2.對一個長度為 A. n-in的順序表，在第B. n-i+1i個元素 1< i < n+1）之前插入一個新元素時需向右移動（ （）個元素。C. n-i-1D. i3下面程序的時間復(fù)雜度為（）。For(i=0;i<m;i+)For(j=0;j <n ;j+)Aij=i*j；A.O(m2)B.O(n2)C.O(n*m)D.O(n+m)4長度為n的線性表采用順序存儲結(jié)構(gòu)，在其第 i個位置插入一個新元素的算法時間復(fù)雜度為（）。A. O（0）5.數(shù)據(jù)結(jié)構(gòu)就是研究

2、（B. 0(1)C. 0(n)D. 0(n2)）。A. 數(shù)據(jù)的邏輯結(jié)構(gòu)B. 數(shù)據(jù)的存儲結(jié)構(gòu)C. 數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)D. 數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)及其數(shù)據(jù)在運算上的實現(xiàn)6下面關(guān)于算法的說法，錯誤的是（）。A.算法最終必須由計算機程序?qū)崿F(xiàn)B.為解決某問題的算法和為該問題編寫的程序含義是相同的C.算法的可行性是指指令不能有二義性D.以上三種說法都錯誤7線性表L= （a1, a2, ?an,）下列說法正確的是（）。A.每個元素都有一個直接前驅(qū)和一個直接后繼B.線性表中至少要有一個元素C.表中所有元素的排列順序必須是由小到大或由大到小8.卜面關(guān)于線性表敘述錯誤的是（D.除第一個和最后一個元素外，其

3、余每個元素都有且僅有一個直接前驅(qū)和一個直線八日接后繼）。A.B.線性表采用順序存儲，必須占用一段地址連續(xù)的單元線性表采用順序存儲，便于進行插入和刪除操作C.線性表采用鏈?zhǔn)酱鎯?，不必占用一段地址連續(xù)的單元D.線性表采用鏈?zhǔn)酱鎯?，便于進行插入和刪除操作9用鏈表表示線性表的優(yōu)點是（）A.便于隨機存取B. 存儲空間比順序存儲方式少C.便于插入和刪除D.數(shù)據(jù)元素的存儲順序與邏輯順序相同10若某線性表中最常用的操作是取第個元素和找第i個元素的前趨元素，則采用（）存儲方式最節(jié)省時間。A.單鏈表B.雙鏈表C.單向循環(huán)D.順序表B.由元素進入隊列的先后順序決定()11. 若隊列采用順序存儲結(jié)構(gòu)，元素的排列順序A

4、.與元素值的大小有關(guān)C. 與隊頭指針和隊尾指針的取值有關(guān)D. 與作為順序存儲結(jié)構(gòu)的數(shù)組大小有關(guān)12.三個元素按A,B,C的順序入棧，下列哪一個是不合法的出棧序列？（昭八、A.ABCB.CABC.ACBD.BAC13假定一個順序循環(huán)隊列存儲于長度為n的一維數(shù)組中，其隊頭和隊尾指針分別用front和rear表示，則判斷隊滿的條件是（）A.( rear+1 ) %n=frontB. front+1=rearC. rear= (front-1 ) %nD. rear= (front+1 ) %n14假定一個順序循環(huán)隊列的隊頭和隊尾指針分別用front和rear表示，則判隊空的條件是（）。A.( fro

5、nt+1 ) %n=rearB. front=rear+1C. front=015.深度為5 （假設(shè)空樹的深度為0）的二叉樹至多有（2的n次方-1）結(jié)點。A. 64B. 32C.31D.63D. front=rear16 一個具有n個頂點的無向完全圖的邊數(shù)為（A. n(n+1)/2B. n(n-1)/2C.n(n-1)D.n(n+1)B.對棧不作任何判別D.判別棧元素的類型18.線性表采用鏈?zhǔn)酱鎯r，其地址（）。A.必須連續(xù)B.部分地址必須連續(xù)C.必須連續(xù)D.連續(xù)與否均可17如果以鏈表作為棧的存儲結(jié)構(gòu)，則出棧操作時A.必須判別棧是否滿C.必須判別棧是否空19. 一棵完全二叉樹上有15個結(jié)點，其

6、深度是不超過（）的最大整數(shù)。A. 2B. 3C. 4D.AC 項都不對）存20. 若某線性表中最常用的操作是在最后一個元素之后插入一個元素和刪除最后一個元素，則采用（ 儲方式最節(jié)省運算時間。A.單鏈表B.雙鏈表C.帶頭結(jié)點的雙循環(huán)鏈表D.容量足夠大的順序表21. 二叉樹中第5層上的結(jié)點個數(shù)最多為A.8B.1522. 深度為5的二叉樹至多有（A. 64B. 32_2的k-1次方-1C.16）結(jié)點C. 31D. 63D.32#23.將一棵有100個結(jié)點的完全二叉樹從上到下，從左到右依次對結(jié)點進行編號，根結(jié)點的編號為1,則編號為49的結(jié)點的左孩子的編號為()。(P124)A.98B.99C.50D.

7、4824.已知廣義表的表頭為A,表尾為（B,C）,則此廣義表為（)A. (A,(B,C)B.(A,B,C)C.(A),B,C)D.(A,B,C)#25.在目標(biāo)串 T0?n-1：=” xwxxyxy 中”，對模式串 p0?m-1=:xy進行子串定位操作的結(jié)果A.0B.2C.3D.526. 如果二叉樹的前序遍歷結(jié)果是12345，后序遍歷結(jié)果是 24531，那么該二叉樹的中序遍歷結(jié)果是（c） ?A.23145B.32154C.21435D.無法確定27. 已知一棵二叉樹的先序遍歷結(jié)果是ABC則以下哪個序列是不可能的中序遍歷結(jié)果：（）A. ABCB. BACC. CBAD. CAB29.樹最適合于用來

8、表示。A.有序數(shù)據(jù)元素B.無序數(shù)據(jù)元素C.元素之間無聯(lián)系的數(shù)據(jù)D.元素之間具有分支層次關(guān)系的數(shù)據(jù)30.下面的函數(shù)PreOrderPrintLeaves（BinTreeBT）按前序遍歷的順序打印出二叉樹BT的所有葉子結(jié)點。則下列哪條表達(dá)式應(yīng)被填在空中？voidPreOrderPrintLeaves（BinTreeBT）if（BT）if（）printf（"%d",BT->Data）;PreOrderPrintLeaves(BT->Left);PreOrderPrintLeaves(BT->Right);B. !BT->RightC . !BT->L

9、eft31. 對二叉排序樹進行什么遍歷可以得到從小到大的排A.前序遍歷B.后序遍歷C.中序遍歷32. 已知 8 個數(shù)據(jù)元素為(34, 76, 45, 18, 26, 54, 92, 65) 最后兩層上的結(jié)點總數(shù)為：A. BT->Data!=OD. !(BT->Left&&BT->Right)序序列？D.層次遍歷，按照依次插入結(jié)點的方法生成一棵二叉排序樹后,33. 由分別帶權(quán)為9、2、5、7的四個葉子結(jié)點構(gòu)成一棵哈夫曼樹,A. 23B. 37C. 4434. 設(shè)一段文本中包含字符 碼后，文本所占字節(jié)數(shù)為：A. 40B. 36C. 25該樹的帶權(quán)路徑長度為:D.

10、46a,b,c,d,eD. 1235. 線性表、堆棧、隊列的主要區(qū)別是什么？ A.線性表用指針，堆棧和隊列用數(shù)組C.線性表和隊列都可以用循環(huán)鏈表實現(xiàn)，但堆棧不能 是順序表中第一個元素的存儲地址是A. 100B. 105C. 10836設(shè)一個堆棧的入棧順序是是：A. 1B. 3 C. 5 37、帶頭結(jié)點的單鏈表A. h=NULL;B38. 線性表1、,其出現(xiàn)頻率相應(yīng)為3,2,5,1,1。則經(jīng)過哈夫曼編B.堆棧和隊列都是插入、刪除受到約束的線性表D.堆棧和隊列都不是線性結(jié)構(gòu)，而線性表100,每個元素的長度為D. 1102、3、4、5。若第一個出棧的元素是D. 1或者5h為空的判定條件是：.h-&g

11、t;next=NULL;C.L在什么情況下適用于使用鏈?zhǔn)浇Y(jié)構(gòu)實現(xiàn)？A.需不斷對L進行刪除插入B.需經(jīng)常修改L中的結(jié)點值40. 對于一個具有NN個結(jié)點的單鏈表，在給定值為A. O(1)B. O(N/2)C. O(N)41. 數(shù)組A1.5,1.6每個元素占5個單元，存單元中，則元素 A5,5的地址為：A. 1120B. 1125C. 11402,則第5個元素的地址是()。4,則最后一個出棧的元素必定h->next=h;D.(1分)C. L中含有大量的結(jié)點h!=NULL;D. L中結(jié)點結(jié)構(gòu)復(fù)雜xx的結(jié)點后插入一個新結(jié)點的時間復(fù)雜度為D. O(NA2)將其按行優(yōu)先次序存儲在起始地址為D. 114

12、542. 將32,2,15,65,28,10依次插入初始為空的二叉排序樹。則該樹的前序遍歷結(jié)果是:A. 2,10,15,28,32,65B. 32,2,10,15,28,65C. 10,28,15,2,65,32D. 32,2,15,10,28,6543已知一棵完全二叉樹的第9層(設(shè)根為第多是：A. 311B. 823C. 184744具有65個結(jié)點的完全二叉樹其深度為(根的深度為A. 845下面(A. Prim算法46.堆是一種(A.插入1000的連續(xù)的內(nèi)1層)有100個葉結(jié)點，則該完全二叉樹的結(jié)點個數(shù)最D.無法確定1)：B. 7C. 6D. 5)算法適合構(gòu)造一個稠密圖G的最小生成樹。B.

13、Kruskal 算法C. Floyd 算法)排序。B.選擇C.交換時間復(fù)雜度和空間復(fù)雜度。1. 一個算法的好壞取決于該算法的2.克魯斯卡爾算法的時間復(fù)雜度為O (eloge)最小生成樹。D.Dijkstra 算法D.歸并,適合求稀疏圖3. 設(shè)單鏈表的結(jié)點結(jié)構(gòu)為（data , *next ），已知指針p指向單鏈表中X結(jié)點，指針q指向y的新結(jié)點，若將結(jié)點y插入到結(jié)點x之后，則需要執(zhí)行以下兩條語句_ q >next=p >next和p >next=q4. 圖的遍歷方式有廣度優(yōu)先遍歷和深度優(yōu)先遍歷兩種。5. 在有序表（12,24,36,48,602,84）中二分查找關(guān)鍵字72時所需進

14、行的關(guān)鍵字比較次數(shù)為。26. 已知廣義表 A=（a,b,c）,（d,e,f）, 則運算 head（head（tail（ A） ）=d7. 由帶權(quán)為3,9,6,2,5 的5個葉子結(jié)點構(gòu)成一棵哈夫曼樹，則帶權(quán)路徑長度為_55&一個哈夫曼（Huffman）樹有19個結(jié)點，則其葉結(jié)點的個數(shù)是109. 靜態(tài)查找表與動態(tài)查找表的根本區(qū)別在于施加在其上的操作不一樣01 0可以看出，該圖共有 3頂點。如果是無向圖，則共有10 110. 從鄰接矩陣A=< 1 0 011. 無向完全圖具有 n（n條邊。12. 廣義表 A（ a,b,c ），（ d,e,f ）的表尾為 。13. 對于給定的n個元素，可

15、以構(gòu)造出的邏輯結(jié)構(gòu)有（集合）、（線性結(jié)構(gòu)）、（樹結(jié)構(gòu)）、（圖結(jié)構(gòu)）4種。14線性結(jié)構(gòu)中的元素之間存在（一對一）關(guān)系，樹形結(jié)構(gòu)中元素之間存在（一對多）關(guān)系，圖形結(jié)構(gòu)中的元素之間存在（多對多）關(guān)系。15隊列的插入操作是在隊列的（隊尾）進行，刪除操作是在隊列的（隊頭）進行。16堆棧的邏輯特點是（先進后出），隊列的邏輯特點是（先進先出）。17堆棧操作設(shè)輸入元素的順序為1,2,3,4,5 ，要在棧的輸出端得到43521，則應(yīng)進行棧的基本運算表示應(yīng)為：Push（S,1 ），Push（S,2），Push（S,3），Push（S,4），Pop（S），（ Pop（S） ），（ Push（S,5） ），Pop（S

16、），Pop（S），Pop（S）。18、一棵二叉樹有67個結(jié)點，這些結(jié)點的度要么是 0,要么是2。這棵二叉樹中度數(shù)為 2的結(jié)點有33個。19. 一棵深度為6的滿二叉樹有31個分支結(jié)點和32個葉子。20. 克魯斯卡爾算法的時間復(fù)雜度為（ O（eloge），適合求（稀疏圖）的最小生成樹。21. 兩個字符串相等的充分必要條件是（長度相等，并且各個對應(yīng)位置上的字符都相等）。22寫出模式串p= “ abaabcac的” next函數(shù)值序列為（01122312）23、設(shè)有一稀疏圖 G,則G采用（鄰接表）存儲結(jié)構(gòu)較省空間。24. 在對一組記錄（54, 38, 96, 23, 15, 72, 60, 45, 8

17、3）進行直接插入排序時，當(dāng)把第7個記錄60插入到有序表時，為尋找插入位置至少需比較（3）次。25在有n個結(jié)點的二叉鏈表中，空鏈域的個數(shù)為_n + 1_。1. 已知二叉樹的前序ABCDEFGHI和中序CDBFEAIHGJ試構(gòu)造出相應(yīng)的二叉樹。2. 已知一棵二叉樹的后序遍歷序列為EICBGAHDF中序遍歷序列為 ECIFBAGDH請畫出這棵二叉樹，3已知某二叉樹，寫出前序遍歷、中序遍歷和后序遍歷4給定權(quán)值集合15,03,14,02,06,09,16,17，構(gòu)造相應(yīng)的哈夫曼樹，并計算它的帶權(quán)路徑長度。5用序列（46, 88, 45, 39, 70, 58, 101, 10, 66, 34）建立一個排

18、序二叉樹，畫出該樹，并求在等概率情況下查找成功的平均查找長度6設(shè)關(guān)鍵字的輸入次序為45, 24, 53, 45, 12, 24, 90。畫出生成的二叉排序樹的存儲結(jié)構(gòu)圖，并求它的長度。5分)。7 畫出下列廣義表(),a,(b,c),(),d),(e)8試畫出具有3個結(jié)點的二叉樹所有不同形態(tài)(1)每個頂點的入/出度;(2)鄰接矩陣；(3)鄰接表；(4)逆鄰接表。10對于所示的有向帶權(quán)圖9已知如圖所示的有向圖，請給出該圖的：(1) 作為AOE寫出從源點A到匯點G的所有路徑并指出哪一條路徑是關(guān)鍵路徑(2) 將該圖作為 AOE網(wǎng)，試寫出C的最早發(fā)生時間及活動FC的最晚開始時間。(3) 寫出A點到各頂點的最短路徑。11已知圖6.32所示的有向圖，請給出: 每個頂點的入度和出度； 鄰接矩陣； 鄰接表； 逆鄰接表。圖6.33 無向網(wǎng)圖6.32有向圖12已知如圖6.33所示的無向網(wǎng)，請給出：(1) 鄰接矩陣；(2) 寫出深度優(yōu)先搜索順序和廣度度優(yōu)先搜索順序