數(shù)據(jù)結構復習資料

1、1 . 快速排序在最壞情況下的時間復雜度為（ D ） 。A O（log 2n）B O（nlog 2n）C O （n） D. O （n2）2 .設一棵二叉樹的深度為k,則該二叉樹中最多有（D ）個結點。A. 2k-1B. 2 kC.2 k-1D. 2 k-13 .二叉樹中第i（i 1）層上的結點數(shù)最多有（C ）個。A. 2iB. 2 iC. 2 i-1D. 2i-14 .設指針變量p指向單鏈表結點A,則刪除結點A的后繼結點B需要的操作 為（ A ） 。A. p-next=p-next-nextB. p=p-nextC. p=p-next-nextD. p-next=p5 .設棧S和隊列Q的初始狀

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

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

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

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

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

7、個有向圖的鄰接表中第i條單鏈表為空，則第i個頂點的出度為零。9 .線性表中的所有元素都有一個前驅元素和后繼元素。10 .帶權無向圖的最小生成樹是唯一的。11 .線性表中的所有元素都有一個前驅元素和后繼元素。12 .非空的雙向循環(huán)鏈表中任何結點的前驅指針均不為空。V13 .圖的鄰接矩陣法：n個頂點需要n*n個單元存儲邊(弧)；空間效率為O(n2) ,14 .稀疏矩陣的壓縮存儲可以用一個三元組表來表示稀疏矩陣中的非0元素。15 .入棧操作和入隊列操作在鏈式存儲結構上實現(xiàn)時需要考慮棧溢出的情況。16 .中序遍歷一棵二叉排序樹可以得到一個有序的序列。V17 .順序表查找指的是在順序存儲結構上進行查找。

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

9、,則判斷指針變量p所 指向的結點為葉子結點的條件是 _ p-lchild=0&p-rchild=0。6 .設一組初始記錄關鍵字序列為(20, 18, 22, 16, 30, 19),則以20為中軸 的一趟快速排序結果為 19,18,16,20,30,22。7 . for(i=1 , t=1, s=0； i=n ； i+) t=t*i ； s=s+t；的時間復雜度為 O(n) 。8 .設有n個結點的完全二叉樹，如果按照從自上到下、從左到右從 1開始順 序編號，則第i個結點的雙親結點編號為 返，右孩子結點的編號為 2i+1.。9 .設某無向圖中頂點數(shù)和邊數(shù)分別為n和e,所有頂點的度數(shù)之和為 d,則

10、e=_2d。10 .設有向圖G的二元組形式表示為 G =(V,E),V=1 ,2,3,4,5,E=, , , , , ,則該圖的一種拓撲排序序列為_1.324.5_ 。11 .設查找表中有100個元素，如果用二分法查找方法查找數(shù)據(jù)元素 X,則最 多需要比較7一次就可以斷定數(shù)據(jù)元素X是否在查找表中。12 .設一組初始記錄關鍵字序列為(49, 38, 65, 97, 76, 13, 27, 50),則 以d=4為增量的一趟希爾排序結束后的結果為 49. 13. 27. 50. 76. 38、65、97。13 .設某棵二叉樹的中序遍歷序列為 ABCD后序遍歷序列為BADC則其前序 遍歷序列為 BAD

11、C14 .完全二叉樹中第 5層上最少有 1 個結點,最多有 16 個結點。15 .設有一組初始記錄關鍵字序列為(50, 16, 23, 68, 94, 70, 73),則將它們調(diào)整成初始堆只需把16與 50相互交換即可。16 .子用的定位運算通常稱為用的 用匹配 ，是再處理中最重要的運算之一 若n為主用長度，m為子用長度，則用的匹配算法時間復雜度為 m*n 。17在堆排序的過程中，對任一分支結點進行篩運算的時間復雜度為_O(log2n),整個堆排序過程的時間復雜度為O(nlog2n)。18 .具有n個頂點，n(n 1)/2條邊的圖,稱為完全無向圖；具有n個頂點，,n(n-1)條弧的有向圖，稱為

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

13、ext) p=p next;p next=q; q next=NULL;return L;請回答下列問題：1)說明語句S1的功能； 答：查詢鏈表的尾結點2)設鏈表表示的線性表為(a1,a2,an),寫出算法執(zhí)行后的返回值所表示 的線性表(a2,a3,，an,a1 ) 。2 .閱讀下面算法:void ABC(BTNode * BT) if(BT) ABC (BT-left); coutdataright); 該算法的功能是：遞歸地后序遍歷鏈式存儲的二叉樹。3 .閱讀下面算法void conversion()Stack s; int n; SElemType e; initstack(s);pri

14、ntf(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)指出該算法的功能。 答：十進制轉六進制2)若輸入數(shù)據(jù)為10,則輸出結果為一14一_4 .閱讀下列函數(shù)int arrange(int a口，int 1, int h, int x) /1和h分別為數(shù)據(jù)區(qū)的下界和上界int i,j,ti=1； j=h ；while(ij)while(i=x)j-；while(i=x)i+；if(ij)t=aj ； aj=ai； ai=t ；i

15、f(aix) return i；else return i 1； 指出該算法的功能是。答：調(diào)整整數(shù)數(shù)組 a口中的元素并返回分界值i ,使所有 x的元素均落在 a1.i上，使所有學x的元素均落在ai +1.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)

16、 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(ij)while(i=x)j-；while(i=x)i+；if(ij) t=aj； aj=ai； ai=t ； if(aix) return i；else return i 1 ； 指出該算法的功能。答：調(diào)整整數(shù)數(shù)組a口中的元素并返回分界值i ,使所有next)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;指出該算法的功能。答：在單鏈表中刪除值相同的多余結點9 .閱讀以下二叉樹操作算法，指出該算法的功能。Template void BinTree unknown(BinTreeNode *t) BinTreeNode *p = t, *temp;if (p!=NULL) temp = p leftchild;p leftchild = p frigh