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

1、精選優(yōu)質(zhì)文檔-傾情為你奉上精選優(yōu)質(zhì)文檔-傾情為你奉上專心-專注-專業(yè)專心-專注-專業(yè)精選優(yōu)質(zhì)文檔-傾情為你奉上專心-專注-專業(yè)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

2、-nextC. p=p-next-nextD. p-next=p5設(shè)棧S和隊列Q的初始狀態(tài)為空，元素E1、E2、E3、E4、E5和E6依次通過棧S，一個元素出棧后即進入隊列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

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

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

5、 D. O(n2)19采用開放定址法處理散列表的沖突時，其平均查找長度（ 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

6、=Nl+N2 D. N0=2N1+l23時間復(fù)雜度不受數(shù)據(jù)初始狀態(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條單鏈表為空，則第

7、i個頂點的出度為零。9線性表中的所有元素都有一個前驅(qū)元素和后繼元素。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)上進行查找。1設(shè)指針變量p指向單鏈表中結(jié)點A，指針變量s指向被插入的結(jié)點X，則在結(jié)點A

8、的后面插入結(jié)點X需要執(zhí)行的語句序列：s-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-lchild

9、=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的二元組形式表示為G =（V，E），V=1，2，3，4，

10、5，E=，則該圖的一種拓?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è)某棵二叉樹的中序遍歷序列為ABCD，后序遍歷序列為BADC，則其前序遍歷序列為_BADC_。14完全二叉樹中第5層上最少有_1_個結(jié)點，最多有_16_個結(jié)點。15設(shè)有一組初始記錄關(guān)鍵字序列為(50，16，23，68，94，

11、70，73)，則將它們調(diào)整成初始堆只需把16與_50_相互交換即可。16. 子串的定位運算通常稱為串的_串匹配_，是串處理中最重要的運算之一若n為主串長度，m為子串長度，則串的匹配算法時間復(fù)雜度為_m*n_。17 在堆排序的過程中，對任一分支結(jié)點進行篩運算的時間復(fù)雜度為_ O(log2n)_，整個堆排序過程的時間復(fù)雜度為_ O(nlog2n)_。18. 具有n個頂點， _ n（n1）/2_條邊的圖，稱為完全無向圖；具有n個頂點， _ n(n-1)_條弧的有向圖，稱為完全有向圖。19 一組有序的記錄關(guān)鍵字序列為(13，18，24，35，47，50，62，83，90)，查找方法用二分查找，查找關(guān)鍵

12、字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) q=L; L=Lnext; p=L; S1: while(pnext) p=pnext; pnext=q; qnext=NULL; return L;請回答下列問題：說明語句S1的功能；答：查詢鏈表的尾結(jié)點2）設(shè)鏈表表示的

13、線性表為（a1,a2, ,an）,寫出算法執(zhí)行后的返回值所表示的線性表_（a2,a3,an,a1）_。2.閱讀下面算法： void ABC(BTNode * BT) if （BT） ABC (BT-left); coutdataright); 該算法的功能是：_遞歸地后序遍歷鏈?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(!sta

14、ckempty(s)pop(s,e); printf(“%d”,e); 指出該算法的功能。答：十進制轉(zhuǎn)六進制2) 若輸入數(shù)據(jù)為10，則輸出結(jié)果為_14_。4. 閱讀下列函數(shù)int arrange(int a, int 1, int h, int x) /1和h分別為數(shù)據(jù)區(qū)的下界和上界 int i,j,t； i=1；j=h； while(ij) while(i=x)j-； while(i=x)i+； if(ij) t=aj；aj=ai；ai=t； if(aix) return i； else return i1；指出該算法的功能是。答：調(diào)整整數(shù)數(shù)組a中的元素并返回分界值i，使所有x的元素均落在a

15、1.i上，使所有x 的元素均落在ai1.h上。5. 閱讀下列算法void quickpass(int r, int s, int t) int i=s,j=t,x=rs; while(ij) while (ij & rj%2=0) j=j-1; if (ij) ri=rj;i=i+1; while (ij & ri%2=1) i=i+1; if (i0)&(flag=1) flag=0; for(j=1;jrj.keyL-rj+1.key) flag=1; x=L-rj; L-rj=L-rj+1; L-rj+1=x; m-; 該算法的功能是：_冒泡排序_。7. 閱讀下列算法int arrang

16、e(int a, int 1, int h, int x) int i,j,t； i=1；j=h；/1和h分別為數(shù)據(jù)區(qū)的下界和上界 while(ij) while(i=x)j-； while(i=x)i+； if(ij) t=aj；aj=ai；ai=t； if(ainext) for(q=p-next,s=q;q!=0; ) if (q-data=p-data) s-next=q-next; free(q);q=s-next; else s=q,q=q-next;指出該算法的功能。答：在單鏈表中刪除值相同的多余結(jié)點9. 閱讀以下二叉樹操作算法，指出該算法的功能。Template void BinTree ：unknown(BinTreeNode *t) BinTreeNode *p = t, *temp; if (p!=NULL) temp = pleftchild; pleftchild = prightchild; prightchild = temp; unknown(pleftchild); unknown(pri