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

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

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

3、面的內(nèi)容。 A并行性 B健壯性和可讀性 C正確性 D時空復(fù)雜度10在二叉排序樹中插入一個結(jié)點的時間復(fù)雜度為（ C ）。AO(1)BO(n) CO(log2n)DO(n2)11. 隊列是一種（ B ）的線性表。A先進(jìn)后出B先進(jìn)先出 C只能插入D只能刪除 12采用開放定址法處理散列表的沖突時，其平均查找長度（ C ）。A低于鏈接法處理沖突 B. 與鏈接法處理沖突相同 C高于鏈接法處理沖突 D高于二分查找13.設(shè)有序順序表中有n個數(shù)據(jù)元素，則利用二分查找法查找數(shù)據(jù)元素X的最多比較次數(shù)不超過（ A ）。A. log2n+1Blog2n-1 C. log2nD. log2(n+1)14. 從數(shù)據(jù)結(jié)構(gòu)上講

4、，字符串是比較特殊的（ C ）。 A堆棧 B 隊列 C線性表D二叉樹15函數(shù)substring(“DATASTRUCTURE”，5，9)的返回值為（ A ）。ASTRUCTUREBDATACASTRUCTURDDATASTRUCTURE16隊列是一種（ B ）的線性表。A先進(jìn)后出B先進(jìn)先出 C只能插入D只能刪除 17對一個算法的評價，不包括如下（ A ）方面的內(nèi)容。 A并行性 B健壯性和可讀性 C正確性 D時空復(fù)雜度18. 從二叉搜索樹中查找一個元素時，其時間復(fù)雜度大致為（ C ）。A. O(n) B. O(1) C. O(log2n) D. O(n2)19采用開放定址法處理散列表的沖突時，其

5、平均查找長度（ C ）。A低于鏈接法處理沖突 B. 與鏈接法處理沖突相同 C高于鏈接法處理沖突 D高于二分查找20.設(shè)有序順序表中有n個數(shù)據(jù)元素，則利用二分查找法查找數(shù)據(jù)元素X的最多比較次數(shù)不超過（ A ）。A. log2n+1Blog2n-1 C. log2nD. log2(n+1)21下列四種排序中（ D ）的空間復(fù)雜度最大。A.堆B冒泡排序 C.希爾排序D.快速排序22設(shè)某二叉樹中度數(shù)為0的結(jié)點數(shù)為N0，度數(shù)為1的結(jié)點數(shù)為Nl，度數(shù)為2的結(jié)點數(shù)為N2，則下列等式成立的是（ B ）。A. N0=N1+1B N0=N2+1 C. N0=Nl+N2 D. N0=2N1+l23時間復(fù)雜度不受數(shù)據(jù)

6、初始狀態(tài)影響而恒為O(nlog2n)的是（ B ）。A. 冒泡排序B.堆排序C.希爾排序D.快速排序1字符串必須以字符0表示串值的終結(jié)。2哈夫曼樹中沒有度數(shù)為1的結(jié)點。3冒泡排序在初始關(guān)鍵字序列為逆序的情況下執(zhí)行的交換次數(shù)最多。4設(shè)初始記錄關(guān)鍵字基本有序，則快速排序算法的時間復(fù)雜度為O(nlog2n)。5分塊查找的平均查找長度不僅與索引表的長度有關(guān)，而且與塊的長度有關(guān)。6如果兩個關(guān)鍵字的值不等但哈希函數(shù)值相等，則稱這兩個關(guān)鍵字為同義詞。7有向圖的鄰接表和逆鄰接表中表結(jié)點的個數(shù)不一定相等。 8如果某個有向圖的鄰接表中第i條單鏈表為空，則第i個頂點的出度為零。9線性表中的所有元素都有一個前驅(qū)元素和

7、后繼元素。10帶權(quán)無向圖的最小生成樹是唯一的。11. 線性表中的所有元素都有一個前驅(qū)元素和后繼元素。12.  非空的雙向循環(huán)鏈表中任何結(jié)點的前驅(qū)指針均不為空。13圖的鄰接矩陣法：n個頂點需要n*n個單元存儲邊(弧)；空間效率為O(n2)。14稀疏矩陣的壓縮存儲可以用一個三元組表來表示稀疏矩陣中的非0元素。15入棧操作和入隊列操作在鏈?zhǔn)酱鎯Y(jié)構(gòu)上實現(xiàn)時需要考慮棧溢出的情況。16中序遍歷一棵二叉排序樹可以得到一個有序的序列。17順序表查找指的是在順序存儲結(jié)構(gòu)上進(jìn)行查找。1設(shè)指針變量p指向單鏈表中結(jié)點A，指針變量s指向被插入的結(jié)點X，則在結(jié)點A的后面插入結(jié)點X需要執(zhí)行的語句序列：s->

8、;next=p->next; p->next = s; ;。2. 具有n個頂點， _ n（n1）/2_條邊的圖，稱為完全無向圖；具有n個頂點， _ n(n-1)_條弧的有向圖，稱為完全有向圖。3. 設(shè)輸入序列為1、2、3，則經(jīng)過棧的作用后可以得到_5_種不同的輸出序列。4. 設(shè)二叉樹中結(jié)點的兩個指針域分別為lchild和rchild，則判斷指針變量p所指向的結(jié)點為葉子結(jié)點的條件是_ p->lchild=0&&p->rchild=0 _。5. 設(shè)二叉樹中結(jié)點的兩個指針域分別為lchild和rchild，則判斷指針變量p所指向的結(jié)點為葉子結(jié)點的條件是_ p-

9、>lchild=0&&p->rchild=0_。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；的時間復(fù)雜度為_ O(n) _。8. 設(shè)有n個結(jié)點的完全二叉樹，如果按照從自上到下、從左到右從1開始順序編號，則第i個結(jié)點的雙親結(jié)點編號為_i/2_，右孩子結(jié)點的編號為_ 2i+1 _。9. 設(shè)某無向圖中頂點數(shù)和邊數(shù)分別為n和e，所有頂點的度數(shù)之和為d，則e=_2d_。10. 設(shè)有向圖G的

10、二元組形式表示為G =（V，E），V=1，2，3，4，5，E=<1,2>，<2,4>，<4,5>，<1,3>，<3,2>，<3,5>，則該圖的一種拓?fù)渑判蛐蛄袨開1,3,2,4,5_ 。11. 設(shè)查找表中有100個元素，如果用二分法查找方法查找數(shù)據(jù)元素X，則最多需要比較_7_次就可以斷定數(shù)據(jù)元素X是否在查找表中。12設(shè)一組初始記錄關(guān)鍵字序列為(49，38，65，97，76，13，27，50)，則以d=4為增量的一趟希爾排序結(jié)束后的結(jié)果為_ 49，13，27，50，76，38，65，97 _。13設(shè)某棵二叉樹的中序遍歷序列為

11、ABCD，后序遍歷序列為BADC，則其前序遍歷序列為_BADC_。14完全二叉樹中第5層上最少有_1_個結(jié)點，最多有_16_個結(jié)點。15設(shè)有一組初始記錄關(guān)鍵字序列為(50，16，23，68，94，70，73)，則將它們調(diào)整成初始堆只需把16與_50_相互交換即可。16. 子串的定位運算通常稱為串的_串匹配_，是串處理中最重要的運算之一若n為主串長度，m為子串長度，則串的匹配算法時間復(fù)雜度為_m*n_。17 在堆排序的過程中，對任一分支結(jié)點進(jìn)行篩運算的時間復(fù)雜度為_ O(log2n)_，整個堆排序過程的時間復(fù)雜度為_ O(nlog2n)_。18. 具有n個頂點， _ n（n1）/2_條邊的圖，稱

12、為完全無向圖；具有n個頂點， _ n(n-1)_條弧的有向圖，稱為完全有向圖。19 一組有序的記錄關(guān)鍵字序列為(13，18，24，35，47，50，62，83，90)，查找方法用二分查找，查找關(guān)鍵字62時的比較次數(shù)為_2_，查找成功時的平均查找長度_ ASL=91*1+2*2+3*4+4*2)=25/9_。 20設(shè)有一組初始記錄關(guān)鍵字序列為(50，16，23，68，94，70，73)，則將它們調(diào)整成初始堆只需把16與_50_相互交換即可。1閱讀下面的算法LinkList mynote(LinkList L) /L是不帶頭結(jié)點的單鏈表的頭指針 if(L&&L->next)

13、q=L; L=L>next; p=L; S1: while(p>next) p=p>next; p>next=q; q>next=NULL; return L;請回答下列問題：1） 說明語句S1的功能；答：查詢鏈表的尾結(jié)點2）設(shè)鏈表表示的線性表為（a1,a2, ,an）,寫出算法執(zhí)行后的返回值所表示的線性表_（a2,a3,an,a1）_。2. 閱讀下面算法：  void ABC(BTNode * BT) if （BT） ABC (BT->left); cout<<BT->data<< ABC (BT->

14、right); 該算法的功能是：_遞歸地后序遍歷鏈?zhǔn)酱鎯Φ亩鏄洹。3閱讀下面算法void conversion() Stack s; int n; SElemType e; initstack(s); printf("Please input number:"); scanf(“%d”,&n);while(n)push(s,n%6); n=n/6; while(!stackempty(s)pop(s,e); printf(“%d”,e); 1) 指出該算法的功能。答：十進(jìn)制轉(zhuǎn)六進(jìn)制2) 若輸入數(shù)據(jù)為10，則輸出結(jié)果為_14_。4. 閱讀下列函數(shù)int arran

15、ge(int 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) return i； else return i1；指出該算法的功能是。答：調(diào)整整數(shù)數(shù)組a中的元素并返回分界值i，使所有x的元素均落在a1.i上，使所有x 的元素均落在ai1.h上。5. 閱讀下列算法void

16、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=x;指出該算法的功能。答：所有奇數(shù)移到所有偶數(shù)之前6. 閱讀下面算法：void myMethod(List *L) int m,i,j,flag=1; RecordType x; m=n-1; wh

17、ile(m>0)&&(flag=1) flag=0; for(j=1;j<=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 arrange(int a, int 1, int h, int x) int i,j,t； i=1；j=h；/1和h分別為數(shù)據(jù)區(qū)的下界和上界 while(i<j) while(i<j && aj>=x)j

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