數(shù)據(jù)結(jié)構(gòu)經(jīng)典復(fù)習(xí)題(僅供參考)

1、【精品文檔】如有侵權(quán)，請聯(lián)系網(wǎng)站刪除，僅供學(xué)習(xí)與交流數(shù)據(jù)結(jié)構(gòu)經(jīng)典復(fù)習(xí)題(僅供參考).精品文檔.一、選擇題(20分)1下面關(guān)于線性表的敘述錯誤的是（ D ）。(A) 線性表采用順序存儲必須占用一片連續(xù)的存儲空間(B) 線性表采用鏈?zhǔn)酱鎯Σ槐卣加靡黄B續(xù)的存儲空間(C) 線性表采用鏈?zhǔn)酱鎯Ρ阌诓迦牒蛣h除操作的實(shí)現(xiàn)(D) 線性表采用順序存儲便于插入和刪除操作的實(shí)現(xiàn)2設(shè)某棵二叉樹的中序遍歷序列為ABCD，前序遍歷序列為CABD，則后序遍歷該二叉樹得到序列為（ A ）。(A) BADC(B) BCDA(C) CDAB(D) CBDA3設(shè)某棵二叉樹中有2000個結(jié)點(diǎn)，則該二叉樹的最小高度為（ C ）。(A

2、) 9(B) 10(C) 11(D) 124設(shè)二叉排序樹中有n個結(jié)點(diǎn)，則在二叉排序樹的平均平均查找長度為（ B ）。(A) O(1)(B) O(log2n)(C)(D) O(n2)5設(shè)有5000個待排序的記錄關(guān)鍵字，如果需要用最快的方法選出其中最小的10個記錄關(guān)鍵字，則用下列（ B ）方法可以達(dá)到此目的。(A) 快速排序(B) 堆排序(C) 歸并排序(D) 插入排序第9小題分析：9快速排序、歸并排序和插入排序必須等到整個排序結(jié)束后才能夠求出最小的10個數(shù)，而堆排序只需要在初始堆的基礎(chǔ)上再進(jìn)行10次篩選即可，每次篩選的時間復(fù)雜度為O(log2n)。6.下列四種排序中（ D ）的空間復(fù)雜度最大。(

3、A) 插入排序(B) 冒泡排序(C) 堆排序(D) 歸并排序7設(shè)一維數(shù)組中有n個數(shù)組元素，則讀取第i個數(shù)組元素的平均時間復(fù)雜度為（C ）。(A) O(n)(B) O(nlog2n)(C) O(1)(D) O(n2)8設(shè)一棵二叉樹的深度為k，則該二叉樹中最多有（D ）個結(jié)點(diǎn)。(A) 2k-1(B) 2k(C) 2k-1(D) 2k-19在二叉排序樹中插入一個結(jié)點(diǎn)的時間復(fù)雜度為（B ）。(A) O(1)(B) O(n)(C) O(log2n)(D) O(n2)10設(shè)用鏈表作為棧的存儲結(jié)構(gòu)則退棧操作（ B ）。(A) 必須判別棧是否為滿(B) 必須判別棧是否為空(C) 判別棧元素的類型(D) 對棧不

4、作任何判別11下列四種排序中（A ）的空間復(fù)雜度最大。(A) 快速排序(B) 冒泡排序(C) 希爾排序(D) 堆12設(shè)某二叉樹中度數(shù)為0的結(jié)點(diǎn)數(shù)為N0，度數(shù)為1的結(jié)點(diǎn)數(shù)為Nl，度數(shù)為2的結(jié)點(diǎn)數(shù)為N2，則下列等式成立的是（ C ）。(A) N0=N1+1(B) N0=Nl+N2(C) N0=N2+1(D) N0=2N1+l13.設(shè)有序順序表中有n個數(shù)據(jù)元素，則利用二分查找法查找數(shù)據(jù)元素X的最多比較次數(shù)不超過（A ）。(A) log2n+1(B) log2n-1(C) log2n(D) log2(n+1)14數(shù)據(jù)的最小單位是（ A ）。(A) 數(shù)據(jù)項(xiàng)(B) 數(shù)據(jù)類型(C) 數(shù)據(jù)元素(D) 數(shù)據(jù)變量

5、15設(shè)一個有序的單鏈表中有n個結(jié)點(diǎn)，現(xiàn)要求插入一個新結(jié)點(diǎn)后使得單鏈表仍然保持有序，則該操作的時間復(fù)雜度為（ D ）。(A) O(log2n)(B) O(1)(C) O(n2)(D) O(n)16設(shè)一棵m叉樹中度數(shù)為0的結(jié)點(diǎn)數(shù)為N0，度數(shù)為1的結(jié)點(diǎn)數(shù)為Nl，度數(shù)為m的結(jié)點(diǎn)數(shù)為Nm，則N0=（B ）。(A) Nl+N2+Nm(B) l+N2+2N3+3N4+(m-1)Nm(C) N2+2N3+3N4+(m-1)Nm(D) 2Nl+3N2+(m+1)Nm17設(shè)輸入序列是1、2、3、n，經(jīng)過棧的作用后輸出序列的第一個元素是n，則輸出序列中第i個輸出元素是（C ）。(A) n-i(B) n-1-i(C)

6、 n+1-i(D) 不能確定18時間復(fù)雜度不受數(shù)據(jù)初始狀態(tài)影響而恒為O(nlog2n)的是（ A ）。(A) 堆排序(B) 冒泡排序(C) 希爾排序(D) 快速排序19設(shè)二叉樹的先序遍歷序列和后序遍歷序列正好相反，則該二叉樹滿足的條件是（D ）。(A) 空或只有一個結(jié)點(diǎn)(B) 高度等于其結(jié)點(diǎn)數(shù)(C) 任一結(jié)點(diǎn)無左孩子(D) 任一結(jié)點(diǎn)無右孩子20順序查找不論在順序線性表中還是在鏈?zhǔn)骄€性表中的時間復(fù)雜度為（A ）。(A) O(n)(B) O(n2)(C) O(n1/2)(D) O(1og2n)21二路歸并排序的時間復(fù)雜度為（ C ）。(A) O(n)(B) O(n2)(C) O(nlog2n)(D

7、) O(1og2n)22. 深度為k的完全二叉樹中最少有（B ）個結(jié)點(diǎn)。(A) 2k-1-1(B) 2k-1(C) 2k-1+1(D) 2k-123.設(shè)二叉排序樹上有n個結(jié)點(diǎn)，則在二叉排序樹上查找結(jié)點(diǎn)的平均時間復(fù)雜度為（D ）。(A) O(n)(B) O(n2)(C) O(nlog2n)(D) O(1og2n)24（ B ）二叉排序樹可以得到一個從小到大的有序序列。(A) 先序遍歷(B) 中序遍歷(C) 后序遍歷(D) 層次遍歷25設(shè)按照從上到下、從左到右的順序從1開始對完全二叉樹進(jìn)行順序編號，則編號為i結(jié)點(diǎn)的左孩子結(jié)點(diǎn)的編號為（B ）。(A) 2i+1(B) 2i(C) i/2(D) 2i-

8、126程序段s=i=0；do i=i+1； s=s+i；while(inext=top;(D) top=top-next;28.建立一個長度為n的有序單鏈表的時間復(fù)雜度為（ C ）(A) O(n)(B) O(1)(C) O(n2)(D) O(log2n)29.在二叉排序樹中插入一個關(guān)鍵字值的平均時間復(fù)雜度為（ B ）。(A) O(n)(B) O(1og2n)(C) O(nlog2n)(D) O(n2)30.設(shè)一棵完全二叉樹中有65個結(jié)點(diǎn)，則該完全二叉樹的深度為（ B ）。(A) 8(B) 7(C) 6(D) 531.隊(duì)列是一種（A ）的線性表。(A) 先進(jìn)先出(B) 先進(jìn)后出(C) 只能插入(

9、D) 只能刪除 32.利用直接插入排序法的思想建立一個有序線性表的時間復(fù)雜度為（ C ）。 (A) O(n)(B) O(nlog2n)(C) O(n2)(D) O(1og2n)33設(shè)指針變量p指向雙向鏈表中結(jié)點(diǎn)A，指針變量s指向被插入的結(jié)點(diǎn)X，則在結(jié)點(diǎn)A的后面插入結(jié)點(diǎn)X的操作序列為（D ）。(A) p-right=s； s-left=p； p-right-left=s； s-right=p-right；(B) s-left=p；s-right=p-right；p-right=s； p-right-left=s；(C) p-right=s； p-right-left=s； s-left=p； s

10、-right=p-right；(D) s-left=p；s-right=p-right；p-right-left=s； p-right=s；34. 一個棧的進(jìn)棧序列是a，b，c，d，e，則棧的不可能的輸出序列是 C 。Aedcba Bdecba Cdceab DAbcdeA：a,b,c,d,e進(jìn)，之后依次出棧B：a,b,c,d,進(jìn)，d出，e進(jìn)，e,c,b,a出D：a進(jìn)a出，b進(jìn)b出e進(jìn)e出C：的話dce都好辦，之后的ab做不到這道題就是沒告訴你進(jìn)棧的同時可以隨時出棧=二、填空題1. 數(shù)據(jù)的物理結(jié)構(gòu)主要包括順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)兩種情況。2. 數(shù)據(jù)結(jié)構(gòu)從邏輯上劃分為三種基本類型：線性結(jié)構(gòu)、樹

11、型結(jié)構(gòu)和圖型結(jié)構(gòu)。3. 公式：二維數(shù)組A中任一元素aij的存儲位置：（LOC（0，0）是a00的存儲位置） LOC(i，j)=LOC（0，0）+（b2*i+j）L5.快速排序的時間性能分析最好情況：每一次劃分對一個記錄定位后，該記錄的左側(cè)子表與右側(cè)子表的長度相同，為O(nlog2n)。最壞情況：每次劃分只得到一個比上一次劃分少一個記錄的子序列（另一個子序列為空），為 O(n2)。平均情況：為O(nlog2n)。6. 在快速排序、堆排序、歸并排序中，_歸并_排序是穩(wěn)定的。7.在堆排序的過程中，對任一分支結(jié)點(diǎn)進(jìn)行篩運(yùn)算的時間復(fù)雜度為_O(log2n)_，整個堆排序過程的時間復(fù)雜度為_ O(nlog

12、2n)_。8.快速排序的最壞時間復(fù)雜度為O(n2)，平均時間復(fù)雜度為O(nlog2n)。9.散列表中解決沖突的兩種方法是開放定址法和鏈地址法。10.在堆排序和快速排序中，如果從平均情況下排序的速度最快的角度來考慮應(yīng)最好選擇_快速_排序，如果從節(jié)省存儲空間的角度來考慮則最好選擇_堆_排序。3、 判斷題全對或全錯得5分1調(diào)用一次深度優(yōu)先遍歷可以訪問到圖中的所有頂點(diǎn)。（ ）2分塊查找的平均查找長度不僅與索引表的長度有關(guān)，而且與塊的長度有關(guān)。（ ）3冒泡排序在初始關(guān)鍵字序列為逆序的情況下執(zhí)行的交換次數(shù)最多。（ ）4滿二叉樹一定是完全二叉樹，完全二叉樹不一定是滿二叉樹。（ ）5設(shè)一棵二叉樹的先序序列和后

13、序序列，則能夠唯一確定出該二叉樹的形狀。（ ）6層次遍歷初始堆可以得到一個有序的序列。（ ）7設(shè)一棵樹T可以轉(zhuǎn)化成二叉樹BT，則二叉樹BT中一定沒有右子樹。（ ）8線性表的順序存儲結(jié)構(gòu)比鏈?zhǔn)酱鎯Y(jié)構(gòu)更好。（ ）9中序遍歷二叉排序樹可以得到一個有序的序列。（ ）10.快速排序是排序算法中平均性能最好的一種排序。（ ）11不論是入隊(duì)列操作還是入棧操作，在順序存儲結(jié)構(gòu)上都需要考慮“溢出”情況。（ ）12當(dāng)向二叉排序樹中插入一個結(jié)點(diǎn)，則該結(jié)點(diǎn)一定成為葉子結(jié)點(diǎn)。（ ）13設(shè)某堆中有n個結(jié)點(diǎn)，則在該堆中插入一個新結(jié)點(diǎn)的時間復(fù)雜度為O(log2n)。（ ）14完全二叉樹中的葉子結(jié)點(diǎn)只可能在最后兩層中出現(xiàn)。（

14、 ）15哈夫曼樹中沒有度數(shù)為1的結(jié)點(diǎn)。（ ）16對連通圖進(jìn)行深度優(yōu)先遍歷可以訪問到該圖中的所有頂點(diǎn)。（ ）17先序遍歷一棵二叉排序樹得到的結(jié)點(diǎn)序列不一定是有序的序列。（ ）18由樹轉(zhuǎn)化成二叉樹，該二叉樹的右子樹不一定為空。（ ）19線性表中的所有元素都有一個前驅(qū)元素和后繼元素。（ ）20.帶權(quán)無向圖的最小生成樹是唯一的。（ ）21.如果兩個關(guān)鍵字的值不等但哈希函數(shù)值相等，則稱這兩個關(guān)鍵字為同義詞。（ ）22.設(shè)初始記錄關(guān)鍵字基本有序，則快速排序算法的時間復(fù)雜度為O(nlog2n)。（ ）23.分塊查找的基本思想是首先在索引表中進(jìn)行查找，以便確定給定的關(guān)鍵字可能存在的塊號，然后再在相應(yīng)的塊內(nèi)進(jìn)行

15、順序查找。（ ）24.二維數(shù)組和多維數(shù)組均不是特殊的線性結(jié)構(gòu)。（ ）25.向二叉排序樹中插入一個結(jié)點(diǎn)需要比較的次數(shù)可能大于該二叉樹的高度。（ ）26.如果某個有向圖的鄰接表中第i條單鏈表為空，則第i個頂點(diǎn)的出度為零。（ ）27.非空的雙向循環(huán)鏈表中任何結(jié)點(diǎn)的前驅(qū)指針均不為空。（ ）28.不論線性表采用順序存儲結(jié)構(gòu)還是鏈?zhǔn)酱鎯Y(jié)構(gòu)，刪除值為X的結(jié)點(diǎn)的時間復(fù)雜度均為O(n)。（ ）29.圖的深度優(yōu)先遍歷算法中需要設(shè)置一個標(biāo)志數(shù)組，以便區(qū)分圖中的每個頂點(diǎn)是否被訪問過。（ ）30.稀疏矩陣的壓縮存儲可以用一個三元組表來表示稀疏矩陣中的非0元素。（ ）31.有向圖的鄰接表和逆鄰接表中表結(jié)點(diǎn)的個數(shù)不一定相

16、等。( )32.對鏈表進(jìn)行插入和刪除操作時不必移動鏈表中結(jié)點(diǎn)。( )33.子串“ABC”在主串“AABCABCD”中的位置為2。( )34.若一個葉子結(jié)點(diǎn)是某二叉樹的中序遍歷序列的最后一個結(jié)點(diǎn)，則它必是該二叉樹的先序遍歷序列中的最后一個結(jié)點(diǎn)。( )35.希爾排序算法的時間復(fù)雜度為O(n2)。( )36.用鄰接矩陣作為圖的存儲結(jié)構(gòu)時，則其所占用的存儲空間與圖中頂點(diǎn)數(shù)無關(guān)而與圖中邊數(shù)有關(guān)。( )37.中序遍歷一棵二叉排序樹可以得到一個有序的序列。()38.入棧操作和入隊(duì)列操作在鏈?zhǔn)酱鎯Y(jié)構(gòu)上實(shí)現(xiàn)時不需要考慮棧溢出的情況。( )39.順序表查找指的是在順序存儲結(jié)構(gòu)上進(jìn)行查找。（ ）40.堆是完全二叉

17、樹，完全二叉樹不一定是堆。（ ）4、 簡答題1、 四類數(shù)據(jù)結(jié)構(gòu)答；、集合；結(jié)構(gòu)中的數(shù)據(jù)元素之間除了“同屬于一個集合”的關(guān)系外，別無其他關(guān)系。、線性結(jié)構(gòu)：結(jié)構(gòu)中數(shù)據(jù)元素之間存在一個對一個的關(guān)系。、樹形結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一個對多個的關(guān)系。、圖形結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在多個對多個的關(guān)系。2、什么叫穩(wěn)定的排序？列出基本穩(wěn)定排序的算法。答：假定在Ki=Kj（1in，1jn，ij）,且在排序前的序列中Ri領(lǐng)先于Rj（即inext=0) return; else for(q=head,p=head-next;p!=0;p=q-next) for(s=head;s!=q-next;s=s-next) if (s-datap-data) break; if(s=q-next)q=p;elseq-next=p-next; p-next=s-next; s-next=p; t=p-data;p-data=s-data;s-data=t;3. 試編寫算法,刪除雙向循環(huán)鏈表