數(shù)據(jù)結(jié)構(gòu)題庫

1、線性結(jié)構(gòu)題1. 棧與隊列得共同特點就是 ( A)。2. 以下數(shù)據(jù)結(jié)構(gòu)中哪一個就是非線性結(jié)構(gòu)？10 進(jìn)制表示。餅錘醞欄劊巔鐨。5下面程序得時間復(fù)雜為(據(jù)。該緩沖區(qū)得邏輯結(jié)構(gòu)應(yīng)該就是( B )躊嚌艷稈摶燭銥。8 已知二級數(shù)組 a5040 按行序為主序存放,每個元素占 4 個字節(jié)空間,若數(shù)組 a得首元素 a11 地址為 2012,計算 a2321 得內(nèi)存地址為( B )。訕幬愜釕襖雙(A) 只允許在端點處插入與刪除元素(B) 都就是先進(jìn)后出(C) 都就是先進(jìn)先出(D) 沒有共同點(A) 隊列(B) 棧(C) 線性表(D) 二叉樹3.設(shè)有一個二維數(shù)組 Amn,假設(shè) A00存放位置在644(10)， A

2、22 存放位置在676(10)，每個元素占一個空間，問A33(10)存放在 ( C )位置。腳注(10)表示用(A) 688(B) 678(C) 692(D)696詵餿瀲電釃鵯鴿。4設(shè)某數(shù)據(jù)結(jié)構(gòu)得二元組形式表示為A=(D ， R)，D=01 ， 02， 03，04，05，06，07，08，09 ，R=r ，r=，, , ，則數(shù)據(jù)結(jié)構(gòu) A 就是(B)。藥灤欽鱟匯鳶鏗。(A) 線性結(jié)構(gòu) (B) 樹型結(jié)構(gòu)(C) 物理結(jié)構(gòu) (D)圖型結(jié)構(gòu)for (i=1, s=0； i=n ； i+)t=1 ；for(j=1 ；j=i ； j+) t=t*j ；s=s+t；鯪囑轟導(dǎo)聽詆禪。(A)O( n)2(B)O(

3、n2)(C)O(n3)(D)O(n4)6、下列程序段得時間復(fù)雜度為()。i=0 , s=0； while (snext=p-next； p-next=-s ；(B) q-next=s ； s-next=p ；禿銚燾償譯絢鑲。(C) p-next=s-next； s-next=p ；(D) p-next=s ；s-next=q ；護(hù)靚燦狽間銚鏨。向被插入得結(jié)點 X，則在結(jié)點 A 與結(jié)點 B 插入結(jié)點 X 得操作序列為(B)。鏹駛壯耬(A) F , H, C, D, P, A, M , Q, R, S,Y, X非線性結(jié)構(gòu)1、具有 n(n0)個結(jié)點得完全二叉樹得深度為2、3、4.5、(A) log2

4、(n)( B ) log2(n)劇。樹最適合用來表示(A)有序數(shù)據(jù)元素(C )log2(n)+1(D ) log2(n)+1覓場麗隴賴諢(B)無序數(shù)據(jù)元素(C)元素之間具有分支層次關(guān)系得數(shù)據(jù)二叉樹得第 k 層得結(jié)點數(shù)最多為(D )k(A) 2-1(B) 2K+1(C) 2K-1設(shè)一棵完全二叉樹有700 個結(jié)點，則共有(A) 200(B) 250(D)元素之間無聯(lián)系得數(shù)據(jù)(D) 2k-1釷鈿鑒瀋玀瓏紅。個葉子結(jié)點。300(D) 350若有 18 個元素得有序表存放在一維數(shù)組A19中，第一個元素放 A1中，現(xiàn)進(jìn)行二分查找，則查找 A :3得比較序列得下標(biāo)依次為 (D)艱櫟憲餾誹貰饒。(A)1 ,

5、2, 3(B) 9 , 5, 2, 36、7.9.(C)9, 5, 3(D) 9 , 4, 2, 3對 n 個記錄得文件進(jìn)行快速排序,(A) O (1)(B) O(n)設(shè)一組初始關(guān)鍵字記錄關(guān)鍵字為所需要得輔助存儲空間大致為(C) O (1og2n)(D) O(20 , 15, 14, 18, 21, 36,(n2)40, 10)，則以 20 為基準(zhǔn)(A )。璽瓔鏍傴鈉瀠艫。(A) 10 , 15, 14,18,20, 36, 40,21(B) 10 , 15,14, 18, 20, 40,36, 21(C) 10 , 15,14, 20, 18, 40,36, 2l(D)15 , 10,14,

6、 18,20, 36,40, 21記錄得一趟快速排序結(jié)束后得結(jié)果為設(shè)無向圖G 中有 n 個頂點 e 條邊，則其對應(yīng)得鄰接表中得表頭結(jié)點與表結(jié)點得個數(shù)分別為(D )。嗚鎩傾鴉賧濁擯。(A) n, e(B) e , n(C) 2n , e(D) n , 2e設(shè)有 5000 個待排序得記錄關(guān)鍵字，如果需要用最快得方法選出其中最小得10 個記錄關(guān)鍵字，則用下列()方法可以達(dá)到此目得。頑殤撓煩鈔環(huán)匭。(A)快速排序(B)堆排序(C)歸并排序(D)插入排序10、下列四種排序中()得空間復(fù)雜度最大。(A)插入排序(B)冒泡排序(C)堆排序(D)歸并排序(A) F , H, C, D, P, A, M , Q

7、, R, S,Y, X11設(shè)一棵二叉樹得深度為 k,則該二叉樹中最多有（ D）個結(jié)點。12.設(shè)一組初始記錄關(guān)鍵字序列為(25 , 50 , 15 , 35 , 80 , 85 , 20 , 40 , 36 , 70),其中含有5 個長度為 2 得有序子表，則用歸并排序得方法對該記錄關(guān)鍵字序列進(jìn)行一趟歸并后得13.設(shè)有序表中有 1000 個元素，則用二分查找查找元素X 最多需要比較（ B14.設(shè)某棵二叉樹得高度為10，則該二叉樹上葉子結(jié)點最多有（ C20、設(shè)某棵二叉樹中只有度數(shù)為0 與度數(shù)為 2 得結(jié)點且度數(shù)為 0 得結(jié)點數(shù)為 n ,則這棵二叉(A) 15 , 25 , 35 ,50 , 20,

8、 40,80 ,85 , 36 ,70(B) 15 , 25, 35, 50 , 80, 20, 85 , 40 , 70 , 36(C) 15, 25 , 35 ,50 , 80, 85, 20 , 36 ,40 , 70(D) 15 , 25, 35 ,50 , 80, 20, 36 , 40 ,70 , 85結(jié)果為（）。減幫糴討計驢俠。(A) 2k-1(B) 2k(C) 2k-1k(D) 2 -1(A) 25(B) 10(C) 7(D) 1）次。(A) 20(B)256(C) 512(D) 102415在一個具有 n 個頂點得無向連通圖中，要連通全部頂點至少需要（A） n（B）16、對于

9、線性表（乙34 , 55 ,n+1( C)25, 64, 46, 20 ,n-110)C（D）n/2進(jìn)行散列存儲時，若選用條邊。H( K) =K %9作為散列函數(shù)，則散列地址為1 得元素有（D個,馮諏魘鉈營盡驢。(A) 1(B) 2(C) 3(D)417、設(shè)有 6 個結(jié)點得無向圖，該圖至少應(yīng)有 （）條邊才能確保就是一個連通圖。(A) 5(B) 6(C) 7（D） 8齋嘆瀕燁黌緝鶴。18、二叉排序樹中左子樹上所有結(jié)點得值均（）根結(jié)點得值。19、(A) (C)=(D) !=設(shè)一組權(quán)值集合 W=（15, 3，14, 2，6，9,16， 17），要求根據(jù)這些權(quán)值集合構(gòu)造一棵哈夫曼樹，則這棵哈夫曼樹得帶

10、權(quán)路徑長度為（）。鐓凱裝錚頭櫬轢。(A) 129(B)219(C) 189(D) 229中共有（ C）個結(jié)點。錘飭頇顥釘聞窯。(A) 2n(B) n+l(C) 2n-1(D) 2n+l21、設(shè)一組初始記錄關(guān)鍵字序列為（Q , H, C , Y , P, A，M，S, R，D，F(xiàn), X），則按字母升序得第一趟冒泡排序結(jié)束后得結(jié)果就是（）。網(wǎng)紈擷諤頊塒災(zāi)。(A) F , H, C, D, P, A, M , Q, R, S,Y, X(B) P, A, C, S, Q, D, F, X , R, H, M , Y(C) A, D, C, R, F, Q, M , S, Y, P, H, X填空題:(

11、R+1)%N=F一個線性表就是 n 仝 0 個數(shù)據(jù)元素 a1,a2,a3,an 得有限序列，表中每個數(shù)據(jù)元素，除憶痹猶襖。均為_0(1).對于一個具有 n 個頂點與 e 條邊得有向圖與無向圖， 在其對應(yīng)得鄰接表中， 所含邊結(jié)點序或后序)。7_ 次就可以斷定數(shù)據(jù)元素 X 就是否在查找表中。龍墾癱灤姍澠潑。設(shè)有向圖 G 中有 n 個頂點 e 條有向邊，所有得頂點入度數(shù)之與為。設(shè)某無向圖中頂點數(shù)與邊數(shù)分別為n 與 e,所有頂點得度數(shù)之與(D) H , C, Q,22、設(shè)用鄰接矩陣(A)第 i(C)第 iP, A, M , S , R , D , F , X , YA 表示有向圖 G 得存儲結(jié)構(gòu)，則有

12、向圖 行非 0 元素得個數(shù)之與行 0 元素得個數(shù)之與G 中頂點 i 得入度為(B )。(B)第 i 列非 0 元素得個數(shù)之與(D)第 i 列 0 元素得個數(shù)之與1.設(shè) F 與 R 分別表示順序循環(huán)隊列得頭指針與尾指針，該隊列最存儲空間為N 個，則判斷該循環(huán)隊列為空得條件為 F=A,判斷隊列為滿時條件為。奧紗諧繪贏鍘倫。第一個與最后一個外，有且僅有一個直接前驅(qū)與一個直接后繼。輞獎賁2.3.不論就是順序存儲結(jié)構(gòu)得棧還就是鏈?zhǔn)酱鎯Y(jié)構(gòu)得棧,其入棧與出棧操作得時間復(fù)雜度4.設(shè)輸入序列為 1、2、3,則經(jīng)過棧得作用后可以得到種不同得輸出序列。5.若用鏈表存儲一棵二叉樹時， 每個結(jié)點除數(shù)據(jù)域外,還有指向左

13、孩子與右孩子得兩個指針。在這種存儲結(jié)構(gòu)中，n 個結(jié)點得二叉樹共有2n_個指針域，其中有n-1個指針域就是存放了地址，有n+1個指針就是空指針。嬸賢筆羆爺煢魷。6.7.8.分別有_個與個。在一個具有 n 個頂點得無向完全圖中，包含有邊，在一個具有 n 個頂點得有向完全圖中，包含有在快速排序、堆排序、歸并排序中,歸并中序條邊。鶴聽鱸翹蠱嶗縱。排序就是穩(wěn)定得。遍歷二叉排序樹中得結(jié)點可以得到一個遞增得關(guān)鍵字序列(填先序、中9.設(shè)查找表中有 100 個元素，如果用二分法查找方法查找數(shù)據(jù)元素X, 則最多需要比較10.關(guān)系為 e=d設(shè)一組初始記錄關(guān)鍵字序列為(55 , 63, 44, 38, 75, 80,

14、 31, 56)，則利用篩為 d，貝 U e=_d/2。財蔥繅駔掙攣廬。11.選法建立得初始堆為31,38,44,56,75,80,55,63.。窩貺詘尷謖櫻綹。12.已知一有向圖得鄰接表存儲結(jié)構(gòu)如下：從頂點1 出發(fā)，深度優(yōu)先搜索（Dfs ）得關(guān)系一對多，圖形結(jié)構(gòu)中元素之間存在多對多 關(guān)系。釓瀧堊階鎂躕釘。假定一個線性表為（12,23,74,55,63,40），若給出哈希函數(shù) H （ key）=Key % 4 條件進(jìn)行劃分,使得同一余數(shù)得元素成為一個子表，則得到得四個子表分別為。鵪遠(yuǎn)廩萬鈕曖峴。設(shè)有 n 個結(jié)點得完全二叉樹， 如果按照從自上到下、 從左到右從 1 開始順序編號，貝悌儐職紲敵學(xué)。

15、一趟快速排序結(jié)果為設(shè)有向圖 G 中有向邊得集合 E=1，2，2，3，1，4，4，2，4，3，則該圖設(shè)有向圖 G 用鄰接矩陣 Ann作為存儲結(jié)構(gòu)，則該鄰接矩陣中第 i 行上所有元素之與等于頂點 i 得行為出度，第 i 列上所有元素之與等于頂點i 得行為入度。嘆嘖詛賽鱒辮篤。為了能有效地應(yīng)用 HASH 查找技術(shù)，必須解決得兩個冋題就是_構(gòu)造好得 hash 函數(shù)_與確定解決沖突方法。慳鵪頊瀅嘔綣翹輸出序列就是1,3,4,5,2，廣度優(yōu)先搜索（BFS）遍歷得輸出序列就是1,3,2,4,513.i 個結(jié)點得雙親結(jié)點編號為i/2，右孩子結(jié)點得編號為2i+1。擯諱14.設(shè)一組初始記錄關(guān)鍵字為（72，73,

16、71, 23，94，16, 5），則以記錄關(guān)鍵字 72 為基準(zhǔn)得。蘿鎵嬙簞綰繭湊。15.16.得一種拓?fù)湫蛄袨?,4,2,3。諸輒鶼鉅繆癲錯。設(shè)哈夫曼樹中共有 n 個結(jié)點，則該哈夫曼樹中有0 個度數(shù)為 1 得結(jié)點。17.18.瘋殘閃債羋檣縋。12.已知一有向圖得鄰接表存儲結(jié)構(gòu)如下：從頂點1 出發(fā)，深度優(yōu)先搜索（Dfs ）得關(guān)系一對多，圖形結(jié)構(gòu)中元素之間存在多對多 關(guān)系。釓瀧堊階鎂躕釘。19. 中序遍歷二叉排序樹所得到得序列就是有序_ 序列（填有序或無序）。20.折半查找有序表（4，6，12，20，28,38，50，70，88，100），若查找表中元素 20，21.它將依次與表中元素28,6,1

17、2,20比較大小。儐嚕聲廳紗餑甌。線性結(jié)構(gòu)中元素之間存在 一對一關(guān)系，樹形結(jié)構(gòu)中元素之間存在問答題1.設(shè)某棵二叉樹得中序遍歷序列為DBEAC 前序遍歷序列為 ABDEC 要求給出該二叉樹得得后序遍歷序列并畫出該二叉樹。顢誹鈕齜鑄獫矚。2.已知待散列得線性表為(36, 15, 40,63, 22),散列用得一維地址空間為0、6,假定選用得散列函數(shù)就是 H ( K) = K mod 7 ,若發(fā)生沖突采用線性探查法處理，試：計算出每6嗎瓔懶憤蘿貓皺。3.設(shè)無向圖 G (如右圖所示)，畫出該圖得最小生成樹得結(jié)構(gòu)，并寫出該圖得最小生成樹邊&設(shè)散列表得地址范圍就是 0、9 ，散列函數(shù)為 H( ke

18、y) =(key2+2) MOD 9,并采用鏈表處理沖突，請畫出元素7、4、5、3、6、2、8、9 依次插入散列表得存儲結(jié)構(gòu)。諷興鯨鲅搗誚嚇。四、算法填空題1.折半查找算法:Int Bi nSrch(Record L,keyTy pe k)一個元素得散列地址并在下圖中填寫出散列表:廠險憂備減學(xué)釧。得集合及計算最小生成樹各邊上得權(quán)值之與。蕷軔禪夾認(rèn)鷥養(yǎng)。4.已知序列(10, 18, 4, 3, 6, 12, 1, 9, 18*, 8)請用序?qū)懗雒恳惶伺判虻媒Y(jié)果。5.設(shè)一組初始記錄關(guān)鍵字序列為(45 , 80, 48, 40, 22, 78),給出第 4 趟直接選擇排序與第 4 趟直接插入排序后得結(jié)果。誆縑擻璉辭劇蔞。6給定一組權(quán)值2 , 8, 5, 4, 3，構(gòu)造相應(yīng)得哈夫曼樹。7.下圖所示得森林:.快速排則分別(1)求樹(a)得先根序列與后根序列;012345將此森林轉(zhuǎn)換為相應(yīng)得二叉樹;/*在有序表 L 中折半查找其關(guān)鍵字等于 K 得元素，若找到，則函數(shù)值為該