數(shù)據(jù)結(jié)構(gòu)-復(fù)習(xí)資料

1、1. 快速排序在最壞情況下的時(shí)間復(fù)雜度為（ D ）。AO（log 2n）BO（nlog 2n）C O （n） D. O （n2）2設(shè)一棵二叉樹的深度為k,則該二叉樹中最多有（D ）個(gè)結(jié)點(diǎn)。A. 2k-1B. 2kC.2 k-1D. 2k-13. 二叉樹中第i（i > 1）層上的結(jié)點(diǎn)數(shù)最多有（C ）個(gè)。ii-1A. 2iB. 2 iC. 2i-1D. 2i-14. 設(shè)指針變量p指向單鏈表結(jié)點(diǎn)A,則刪除結(jié)點(diǎn)A的后繼結(jié)點(diǎn)B需要的操作 為（ A ）。A. p->next=p->next->nextB. p=p->nextC. p=p->next->nextD.

2、 p->next=p5. 設(shè)棧S和隊(duì)列Q的初始狀態(tài)為空，元素 E1、E2、E3 E4 E5和E6依次通 過棧S, 個(gè)元素出棧后即進(jìn)入隊(duì)列 Q,若6個(gè)元素出列的順序?yàn)镋2、E4 E3 E6、E5和E1，則棧S的容量至少應(yīng)該是（C ）。A. 6B. 4C. 3D. 26. 設(shè)有以下四種排序方法,則（ B ）的空間復(fù)雜度最大。A. 冒泡排序 B. 快速排 C. 堆排序 D. 希爾排序7. 設(shè)結(jié)點(diǎn)A有3個(gè)兄弟結(jié)點(diǎn)且結(jié)點(diǎn)B為結(jié)點(diǎn)A的雙親結(jié)點(diǎn)，則結(jié)點(diǎn)B的度數(shù) 數(shù)為（ B ）。A. 3B. 4C. 5D. 18. 根據(jù)二叉樹的定義可知二叉樹共有（B ）種不同的形態(tài)。A. 4B. 5C. 6D. 79.

3、 對一個(gè)算法的評價(jià),不包括如下（A ）方面的內(nèi)容。A .并行性 B .健壯性和可讀性 C .正確性 D .時(shí)空復(fù)雜度10. 在二叉排序樹中插入一個(gè)結(jié)點(diǎn)的時(shí)間復(fù)雜度為（C ）。A.O（1）B.O（n）C . O（log 2n）D.O（n2）11. 隊(duì)列是一種（ B ）的線性表。A.先進(jìn)后出B.先進(jìn)先出C .只能插入D.只能刪除12. 采用開放定址法處理散列表的沖突時(shí),其平均查找長度（ C ）A.低于鏈接法處理沖突B.與鏈接法處理沖突相同C 高于鏈接法處理沖突 D 高于二分查找13. 設(shè)有序順序表中有n個(gè)數(shù)據(jù)元素，則利用二分查找法查找數(shù)據(jù)元素 X的最 多比較次數(shù)不超過（ A ）。A. log 2n

4、+1Blog 2n-1C. log 2n D. log 2（n+1）14. 從數(shù)據(jù)結(jié)構(gòu)上講，字符串是比較特殊的（ C ）。A.堆棧 B .隊(duì)列 C.線性表D.二叉樹15函數(shù) substring （“DATASTRUCTU”R，E 5， 9）的返回值為（ A ）。ASTRUCTUREBDATACASTRUCTURDDATASTRUCTURE16隊(duì)列是一種（ B ）的線性表。A.先進(jìn)后出B.先進(jìn)先出C .只能插入D.只能刪除17對一個(gè)算法的評價(jià)，不包括如下（ A ）方面的內(nèi)容。A 并行性 B 健壯性和可讀性 C 正確性 D 時(shí)空復(fù)雜度18. 從二叉搜索樹中查找一個(gè)元素時(shí)，其時(shí)間復(fù)雜度大致為（ C

5、）。2A. O（n） B. O（1） C. O（log2n）D. O（n2）19采用開放定址法處理散列表的沖突時(shí)，其平均查找長度（C ）。A.低于鏈接法處理沖突B.與鏈接法處理沖突相同C 高于鏈接法處理沖突 D 高于二分查找20.設(shè)有序順序表中有n個(gè)數(shù)據(jù)元素，則利用二分查找法查找數(shù)據(jù)元素 X的最 多比較次數(shù)不超過（ A ）。A. log 2n+1Blog 2n-1C. log 2n D. log 2（n+1）21下列四種排序中（ D ）的空間復(fù)雜度最大。A.堆B冒泡排序C.希爾排序D.快速排序22. 設(shè)某二叉樹中度數(shù)為0的結(jié)點(diǎn)數(shù)為M,度數(shù)為1的結(jié)點(diǎn)數(shù)為N，度數(shù)為2 的結(jié)點(diǎn)數(shù)為則下列等式成立的是

6、（B ）0A. N 0=N1+1B. N0=N2+1 C. N 0=Nl+N2 D. N 0=2N1+l23. 時(shí)間復(fù)雜度不受數(shù)據(jù)初始狀態(tài)影響而恒為O（nlog2n） 的是（ B ）1 字符串必須以字符0'表示串值的終結(jié)。V2 哈夫曼樹中沒有度數(shù)為1的結(jié)點(diǎn)。V3. 冒泡排序在初始關(guān)鍵字序列為逆序的情況下執(zhí)行的交換次數(shù)最多。V4. 設(shè)初始記錄關(guān)鍵字基本有序，則快速排序算法的時(shí)間復(fù)雜度為O(nlog2n)。5. 分塊查找的平均查找長度不僅與索引表的長度有關(guān)，而且與塊的長度有關(guān)。V6. 如果兩個(gè)關(guān)鍵字的值不等但哈希函數(shù)值相等，則稱這兩個(gè)關(guān)鍵字為同義詞。V7 .有向圖的鄰接表和逆鄰接表中表結(jié)點(diǎn)

7、的個(gè)數(shù)不一定相等。8. 如果某個(gè)有向圖的鄰接表中第i條單鏈表為空，則第i個(gè)頂點(diǎn)的出度為零。V9. 線性表中的所有元素都有一個(gè)前驅(qū)元素和后繼元素。10. 帶權(quán)無向圖的最小生成樹是唯一的。11. 線性表中的所有元素都有一個(gè)前驅(qū)元素和后繼元素。12. 非空的雙向循環(huán)鏈表中任何結(jié)點(diǎn)的前驅(qū)指針均不為空。V13. 圖的鄰接矩陣法：n個(gè)頂點(diǎn)需要n*n個(gè)單元存儲(chǔ)邊(弧)；空間效率為O(n2) <V14 .稀疏矩陣的壓縮存儲(chǔ)可以用一個(gè)三元組表來表示稀疏矩陣中的非0元素。15 .入棧操作和入隊(duì)列操作在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上實(shí)現(xiàn)時(shí)需要考慮棧溢出的情況。16. 中序遍歷一棵二叉排序樹可以得到一個(gè)有序的序列。V17. 順

8、序表查找指的是在順序存儲(chǔ)結(jié)構(gòu)上進(jìn)行查找。1 .設(shè)指針變量p指向單鏈表中結(jié)點(diǎn)A,指針變量s指向被插入的結(jié)點(diǎn)X,則在結(jié)點(diǎn)A的后面插入結(jié)點(diǎn) X需要執(zhí)行的語句序列：s->next=p->next;p->next =s;2. 具有n個(gè)頂點(diǎn)， n (n 1) 12條邊的圖，稱為完全無向圖；具有 n個(gè)頂點(diǎn)，n-1)條弧的有向圖，稱為完全有向圖。3. 設(shè)輸入序列為1、2、3，則經(jīng)過棧的作用后可以得到 5種不同的輸出序列。4. 設(shè)二叉樹中結(jié)點(diǎn)的兩個(gè)指針域分別為Ichild和rchild，則判斷指針變量p所指向的結(jié)點(diǎn)為葉子結(jié)點(diǎn)的條件是 _ p->lchild=0&&p-&g

9、t;rchiId=O 。5. 設(shè)二叉樹中結(jié)點(diǎn)的兩個(gè)指針域分別為lchild和rchild，則判斷指針變量p所指向的結(jié)點(diǎn)為葉子結(jié)點(diǎn)的條件是 _ p->lchild=0&&p->rchild=O。6. 設(shè)一組初始記錄關(guān)鍵字序列為(20，18，22，16, 30，19)，則以20為中軸的一趟快速排序結(jié)果為 19,18,16,20,30,22。7. for(i=1，t=1，s=0； i<=n ； i+) t=t*i ； s=s+t;的時(shí)間復(fù)雜度為 0(n)。8. 設(shè)有n個(gè)結(jié)點(diǎn)的完全二叉樹，如果按照從自上到下、從左到右從1開始順序編號，則第i個(gè)結(jié)點(diǎn)的雙親結(jié)點(diǎn)編號為j/2

10、，右孩子結(jié)點(diǎn)的編號為 2i+1.。9. 設(shè)某無向圖中頂點(diǎn)數(shù)和邊數(shù)分別為n和e，所有頂點(diǎn)的度數(shù)之和為 d，則e= 。10. 設(shè)有向圖G的二元組形式表示為 G( V ,E),V=1 ,2,3,4, 5 ,E=<1,2>， <2,4>，<4,5> , <1,3> , <3,2> , <3,5>,則該圖的一種拓?fù)渑判蛐蛄袨?3,2,4,5_ 。11. 設(shè)查找表中有100個(gè)元素，如果用二分法查找方法查找數(shù)據(jù)元素 X，則最多需要比較7一次就可以斷定數(shù)據(jù)元素X是否在查找表中。12. 設(shè)一組初始記錄關(guān)鍵字序列為(49 , 38, 65,

11、97, 76, 13, 27, 50)，則以d=4為增量的一趟希爾排序結(jié)束后的結(jié)果為 49, 13, 27, 50, 76,38, 65, 97。13. 設(shè)某棵二叉樹的中序遍歷序列為 ABCD后序遍歷序列為BADC則其前序遍歷序列為BADC。14. 完全二叉樹中第 5層上最少有 丄個(gè)結(jié)點(diǎn)，最多有_16個(gè)結(jié)點(diǎn)。15設(shè)有一組初始記錄關(guān)鍵字序列為(50, 16, 23, 68, 94, 70, 73)，則將 它們調(diào)整成初始堆只需把16與 50相互交換即可。16.子串的定位運(yùn)算通常稱為串的 串匹配 ，是串處理中最重要的運(yùn)算之一 若n為主串長度，m為子串長度，則串的匹配算法時(shí)間復(fù)雜度為 m*n 。17在

12、堆排序的過程中，對任一分支結(jié)點(diǎn)進(jìn)行篩運(yùn)算的時(shí)間復(fù)雜度為_O(log2n)，整個(gè)堆排序過程的時(shí)間復(fù)雜度為O(nlog2n)。18. 具有n個(gè)頂點(diǎn)，n (n 1)/2條邊的圖,稱為完全無向圖；具有n個(gè)頂點(diǎn)，_ n(n-1) 弧的有向圖，稱為完全有向圖。19 一組有序的記錄關(guān)鍵字序列為(13, 18, 24, 35, 47, 50, 62, 83, 90), 查找方法用二分查找，查找關(guān)鍵字 62時(shí)的比較次數(shù)為2 ，查找成功時(shí)的平均查找長度 ASL=91*1+2*2+3*4+4*2)=25/9。20.設(shè)有一組初始記錄關(guān)鍵字序列為(50, 16, 23, 68, 94, 70, 73)，則將 它們調(diào)整成

13、初始堆只需把16與 50相互交換即可。1. 閱讀下面的算法Lin kList myno te(L in kList L) /L是不帶頭結(jié)點(diǎn)的單鏈表的頭指針if(L&&L- >n ext)q=L; L=L >n ext; p=L;S1:while(p >n ext) p=p >n ext;p >n ext=q; q >n ext=NULL;return L;請回答下列問題：1) 說明語句S1的功能；答：查詢鏈表的尾結(jié)點(diǎn)2) 設(shè)鏈表表示的線性表為(a,a2,an),寫出算法執(zhí)行后的返回值所表示的線性表(a2,a3 ,an,a1 ) _。2. 閱讀

14、下面算法:void ABC(BTNode * BT) if(BT)ABC (BT->left);cout<vBT->data<v''ABC (BT->right);該算法的功能是：遞歸地后序遍歷鏈?zhǔn)酱鎯?chǔ)的二叉樹。3.閱讀下面算法void conv ersi on()Stack s; intn; SElemType e; in itstack(s);prin tf("Please in put nu mber:");scanf( “%d，&n);while( n)push(s, n%6); n=n/6;while(!sta

15、ckempty(s)pop(s,e); printf( “%d ,e);1) 指出該算法的功能。答：十進(jìn)制轉(zhuǎn)六進(jìn)制2) 若輸入數(shù)據(jù)為10,則輸出結(jié)果為 一14_ _。4. 閱讀下列函數(shù) int arran ge(i nt a, int 1, int h, int x) /1和h分別為數(shù)據(jù)區(qū)的下界和上界int i,j,t ；i=1 ； j=h ；while(i<j)while(i<j && aj>=x)j-；while(i<j && aj>=x)i+；if(i<j)t=aj ；aj=ai；ai=t ；if(ai<x) re

16、turn i ；else return i 1； 指出該算法的功能是。答：調(diào)整整數(shù)數(shù)組 a中的元素并返回分界值i，使所有v x的元素均落在a1.i上，使所有x的元素均落在ai + 1.h上。5. 閱讀下列算法void quickpass(int r, int s, int t)int i=s,j=t,x=rs;while(i<j)while (i<j && rj%2=0) j=j-1; if (i<j) ri=rj;i=i+1;while (i<j && ri%2=1) i=i+1; if (i<j) rj=ri;j=j-1;ri=

17、x; 指出該算法的功能。 答：所有奇數(shù)移到所有偶數(shù)之前6. 閱讀下面算法：void myMethod(List *L) int m,i,j,flag=1;RecordType x;m=n-1;while(m>0)&&(flag=1) flag=0;for(j=1;jv=m;j+)if(L->rj.key>L->rj+1.key) flag=1;x=L->rj; L->rj=L->rj+1; L->rj+1=x;m-;該算法的功能是：二冒泡排序_。7. 閱讀下列算法int arran ge(i nt a, int 1, int h,

18、 int x) int i,j,t; i=1 ; j=h ； 1和h分別為數(shù)據(jù)區(qū)的下界和上界while(i<j)while(i<j && aj>=x)j-；while(i<j && aj>=x)i+；if(i<j) t=aj； aj=ai； ai=t ； if(ai<x) return i；else return i 1 ； 指出該算法的功能。答：調(diào)整整數(shù)數(shù)組a中的元素并返回分界值i，使所有v x的元素均落在a1.i上，使所有x的元素均落在ai + 1.h上。8. 閱讀下列算法typedef int datatype;typedef struct node datatype data; struct node *n ext;lklist;void delred un da nt(lklist *&head)Iklist *p,*q,*s;for(p=head;p!=0;p=p->n ext)for(q=p-