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

1、一、選擇題(20分)1下面關(guān)于線性表的敘述錯(cuò)誤的是（ D ）。(A) 線性表采用順序存儲(chǔ)必須占用一片連續(xù)的存儲(chǔ)空間(B) 線性表采用鏈?zhǔn)酱鎯?chǔ)不必占用一片連續(xù)的存儲(chǔ)空間(C) 線性表采用鏈?zhǔn)酱鎯?chǔ)便于插入和刪除操作的實(shí)現(xiàn)(D) 線性表采用順序存儲(chǔ)便于插入和刪除操作的實(shí)現(xiàn)2設(shè)某棵二叉樹的中序遍歷序列為ABCD，前序遍歷序列為CABD，則后序遍歷該二叉樹得到序列為（ A ）。(A) BADC(B) BCDA(C) CDAB(D) CBDA3設(shè)某棵二叉樹中有2000個(gè)結(jié)點(diǎn)，則該二叉樹的最小高度為（ C ）。(A) 9(B) 10(C) 11(D) 124設(shè)二叉排序樹中有n個(gè)結(jié)點(diǎn)，則在二叉排序樹的平均平均

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

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

4、希爾排序(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個(gè)數(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ù)變量15設(shè)一個(gè)有序的單鏈表中有n個(gè)結(jié)點(diǎn)，現(xiàn)要求插入一個(gè)新結(jié)點(diǎn)后使得單鏈表仍然保持有序，則該操作的時(shí)

5、間復(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)過棧的作用后輸出序列的第一個(gè)元素是n，則輸出序列中第i個(gè)輸出元素是（C ）。(A) n-i(B) n-1-i(C) n+1-i(D) 不能確定18時(shí)間復(fù)雜度不受數(shù)據(jù)初始狀態(tài)影響而恒為O(nlog2n)的是（

6、A ）。(A) 堆排序(B) 冒泡排序(C) 希爾排序(D) 快速排序19設(shè)二叉樹的先序遍歷序列和后序遍歷序列正好相反，則該二叉樹滿足的條件是（D ）。(A) 空或只有一個(gè)結(jié)點(diǎn)(B) 高度等于其結(jié)點(diǎn)數(shù)(C) 任一結(jié)點(diǎn)無左孩子(D) 任一結(jié)點(diǎn)無右孩子20順序查找不論在順序線性表中還是在鏈?zhǔn)骄€性表中的時(shí)間復(fù)雜度為（A ）。(A) O(n)(B) O(n2)(C) O(n1/2)(D) O(1og2n)21二路歸并排序的時(shí)間復(fù)雜度為（ C ）。(A) O(n)(B) O(n2)(C) O(nlog2n)(D) O(1og2n)22. 深度為k的完全二叉樹中最少有（B ）個(gè)結(jié)點(diǎn)。(A) 2k-1-1(

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

8、雜度為（A ）。(A) O(n)(B) O(nlog2n)(C) O(n2)(D) O(n3/2)27.設(shè)指針變量top指向當(dāng)前鏈?zhǔn)綏５臈ｍ?，則刪除棧頂元素的操作序列為（ D ）。(A) top=top+1;(B) top=top-1;(C) top->next=top;(D) top=top->next;28.建立一個(gè)長度為n的有序單鏈表的時(shí)間復(fù)雜度為（ C ）(A) O(n)(B) O(1)(C) O(n2)(D) O(log2n)29.在二叉排序樹中插入一個(gè)關(guān)鍵字值的平均時(shí)間復(fù)雜度為（ B ）。(A) O(n)(B) O(1og2n)(C) O(nlog2n)(D) O(n2

9、)30.設(shè)一棵完全二叉樹中有65個(gè)結(jié)點(diǎn)，則該完全二叉樹的深度為（ B ）。(A) 8(B) 7(C) 6(D) 531.隊(duì)列是一種（A ）的線性表。(A) 先進(jìn)先出(B) 先進(jìn)后出(C) 只能插入(D) 只能刪除 32.利用直接插入排序法的思想建立一個(gè)有序線性表的時(shí)間復(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

10、； 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->right=p->right；(D) s->left=p；s->right=p->right；p->right->left=s； p->right=s；34. 一個(gè)棧的進(jìn)棧序列是a，b，c，d，e，則棧的不可能的輸出序列是

11、 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)棧的同時(shí)可以隨時(shí)出棧=二、填空題1. 數(shù)據(jù)的物理結(jié)構(gòu)主要包括順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)兩種情況。2. 數(shù)據(jù)結(jié)構(gòu)從邏輯上劃分為三種基本類型：線性結(jié)構(gòu)、樹型結(jié)構(gòu)和圖型結(jié)構(gòu)。3.4. 公式：二維數(shù)組A中任一元素aij的存儲(chǔ)位置：（LOC（0，0）是a00的存儲(chǔ)位置） LOC(i，j)=LOC（0，0）+（b2*i+j）L5.快速排序的時(shí)間性能分析最好情況：每一次劃

12、分對一個(gè)記錄定位后，該記錄的左側(cè)子表與右側(cè)子表的長度相同，為O(nlog2n)。最壞情況：每次劃分只得到一個(gè)比上一次劃分少一個(gè)記錄的子序列（另一個(gè)子序列為空），為 O(n2)。 平均情況：為O(nlog2n)。6. 在快速排序、堆排序、歸并排序中，_歸并_排序是穩(wěn)定的。7.在堆排序的過程中，對任一分支結(jié)點(diǎn)進(jìn)行篩運(yùn)算的時(shí)間復(fù)雜度為_O(log2n)_，整個(gè)堆排序過程的時(shí)間復(fù)雜度為_ O(nlog2n)_。8.快速排序的最壞時(shí)間復(fù)雜度為O(n2)，平均時(shí)間復(fù)雜度為O(nlog2n)。9.散列表中解決沖突的兩種方法是開放定址法和鏈地址法。10.在堆排序和快速排序中，如果從平均情況下排序的速度最快的角

13、度來考慮應(yīng)最好選擇_快速_排序，如果從節(jié)省存儲(chǔ)空間的角度來考慮則最好選擇_堆_排序。3、 判斷題全對或全錯(cuò)得5分1調(diào)用一次深度優(yōu)先遍歷可以訪問到圖中的所有頂點(diǎn)。（× ）2分塊查找的平均查找長度不僅與索引表的長度有關(guān)，而且與塊的長度有關(guān)。（ ）3冒泡排序在初始關(guān)鍵字序列為逆序的情況下執(zhí)行的交換次數(shù)最多。（ ）4滿二叉樹一定是完全二叉樹，完全二叉樹不一定是滿二叉樹。（ ）5設(shè)一棵二叉樹的先序序列和后序序列，則能夠唯一確定出該二叉樹的形狀。（ × ）6層次遍歷初始堆可以得到一個(gè)有序的序列。（× ）7設(shè)一棵樹T可以轉(zhuǎn)化成二叉樹BT，則二叉樹BT中一定沒有右子樹。（ ）8線

14、性表的順序存儲(chǔ)結(jié)構(gòu)比鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)更好。（ × ）9中序遍歷二叉排序樹可以得到一個(gè)有序的序列。（ ）10.快速排序是排序算法中平均性能最好的一種排序。（ ）11不論是入隊(duì)列操作還是入棧操作，在順序存儲(chǔ)結(jié)構(gòu)上都需要考慮“溢出”情況。（ ）12當(dāng)向二叉排序樹中插入一個(gè)結(jié)點(diǎn)，則該結(jié)點(diǎn)一定成為葉子結(jié)點(diǎn)。（ ）13設(shè)某堆中有n個(gè)結(jié)點(diǎn)，則在該堆中插入一個(gè)新結(jié)點(diǎn)的時(shí)間復(fù)雜度為O(log2n)。（ ）14完全二叉樹中的葉子結(jié)點(diǎn)只可能在最后兩層中出現(xiàn)。（ ）15哈夫曼樹中沒有度數(shù)為1的結(jié)點(diǎn)。（ ）16對連通圖進(jìn)行深度優(yōu)先遍歷可以訪問到該圖中的所有頂點(diǎn)。（ ）17先序遍歷一棵二叉排序樹得到的結(jié)點(diǎn)序列不一定

15、是有序的序列。（ ）18由樹轉(zhuǎn)化成二叉樹，該二叉樹的右子樹不一定為空。（× ）19線性表中的所有元素都有一個(gè)前驅(qū)元素和后繼元素。（ × ）20.帶權(quán)無向圖的最小生成樹是唯一的。（ × ）21.如果兩個(gè)關(guān)鍵字的值不等但哈希函數(shù)值相等，則稱這兩個(gè)關(guān)鍵字為同義詞。（ ）22.設(shè)初始記錄關(guān)鍵字基本有序，則快速排序算法的時(shí)間復(fù)雜度為O(nlog2n)。（ × ）23.分塊查找的基本思想是首先在索引表中進(jìn)行查找，以便確定給定的關(guān)鍵字可能存在的塊號(hào)，然后再在相應(yīng)的塊內(nèi)進(jìn)行順序查找。（ ）24.二維數(shù)組和多維數(shù)組均不是特殊的線性結(jié)構(gòu)。（× ）25.向二叉排序樹

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

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

18、堆。（ ）4、 簡答題1、 四類數(shù)據(jù)結(jié)構(gòu)答；、集合；結(jié)構(gòu)中的數(shù)據(jù)元素之間除了“同屬于一個(gè)集合”的關(guān)系外，別無其他關(guān)系。、線性結(jié)構(gòu)：結(jié)構(gòu)中數(shù)據(jù)元素之間存在一個(gè)對一個(gè)的關(guān)系。、樹形結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一個(gè)對多個(gè)的關(guān)系。、圖形結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在多個(gè)對多個(gè)的關(guān)系。2、什么叫穩(wěn)定的排序？列出基本穩(wěn)定排序的算法。答：假定在Ki=Kj（1in，1jn，ij）,且在排序前的序列中Ri領(lǐng)先于Rj（即i<j）。若在排序后的序列中Ri仍領(lǐng)先于Rj，則稱所用的排序方法是穩(wěn)定的；反之，若可能使排序后的序列中Rj仍領(lǐng)先于Ri，則稱所用的排序方法是不穩(wěn)定的?；痉€(wěn)定的排序方法：直接插入

19、排序、冒泡排序、歸并排序、基數(shù)排序。不穩(wěn)定的排序方法：直接選擇排序、希爾排序、快速排序和堆排序。3、 散列函數(shù)的基本概念、設(shè)計(jì)原則。 答：基本概念：在記錄的存儲(chǔ)位置和它的關(guān)鍵字之間建立一個(gè)確定的對應(yīng)關(guān)系f，使每個(gè)關(guān)鍵字和結(jié)構(gòu)中一個(gè)唯一的存儲(chǔ)位置相對應(yīng)，我們稱這種對應(yīng)關(guān)系為f的散列函數(shù)。 設(shè)計(jì)原則：根據(jù)散列函數(shù)的思想建立一個(gè)散列表，在建立一個(gè)散列表之前需要解決兩個(gè)主要問題。（1） 構(gòu)造一個(gè)合適的散列表。常用方法有：直接定址法、數(shù)字分析法、平方取和法、折疊法、保留余數(shù)法、隨機(jī)數(shù)法。（2） 處理沖突的方法：開放定址法、鏈地址法、建立一個(gè)公共溢出區(qū)。4、 （給出一個(gè)時(shí)間復(fù)雜度或一種表示方法，分析每一個(gè)字母的含義）略5、 在一個(gè)雙向循環(huán)鏈表中，我們要實(shí)現(xiàn)數(shù)據(jù)元素的插入所對應(yīng)基本的操作。略五、綜合題1.已知二叉樹的前序遍歷序列是AEFBGCDHIKJ，中序遍歷序列是EFAGBCHKIJD，畫出此二叉樹，并畫出它的后序線索二叉樹。解：2、在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上設(shè)計(jì)直接插入排序算法解：void straightinsertsort(lklist *&head) lklist *s,*p,*q; int t; if (he