數(shù)據(jù)結(jié)構(gòu)期末復(fù)習(xí)題1doc

1、數(shù)據(jù)結(jié)構(gòu)習(xí)題1一、選擇題1、程序段如下：sum=0； for(i=1;i=1;j-) sum+；其中 n為正整數(shù)，那么最后一行的語句頻度在最壞情況下是 。 A、O(n B、 O(nlog2n) C、 O(n3) D、O(n2) 2、二維數(shù)組A88按行優(yōu)先順序存儲，假設(shè)數(shù)組元素A23的存儲地址為1087，A45的存儲地址為1159，那么數(shù)組元素A67的存儲地址為。A、1223B、1227C、1231D、12353已經(jīng)知道棧的最大容量為4。假設(shè)進(jìn)棧序列為1，2，3，4，5，6，且進(jìn)棧和出棧可以穿插進(jìn)行，那么不會出現(xiàn)的出棧序列為。A、4，3，2，1，5，6 B、3，2，1，6，4，5C、4，3，2，

2、1，6，5 D、3，2，1，6，5，4已經(jīng)知道廣義表C=(a，(b，c)，d)，那么：head( tail(tail(C)為( )A、dB、cC、bD、a已經(jīng)知道一棵完全二叉樹有256個葉子結(jié)點，那么該樹可能達(dá)到的最大深度為。A10B11C8D96、 已經(jīng)知道森林F=T1，T2，T3，T4，T5 ，T6，各棵樹Ti(i=1，2，3，4，5，6)中所含結(jié)點的個數(shù)分別為18，2，3，4，5，6, 將F按照左孩子右兄弟轉(zhuǎn)化為二叉樹，那么與F對應(yīng)的二叉樹的右子樹的結(jié)點個數(shù)為 。A19B20C17D187、對以下圖所示的無向圖，從頂點1開始進(jìn)行深度優(yōu)先遍歷，可得到頂點訪問序列 。 A. 1 2 4 5

3、6 3 7B.1 2 4 3 5 6 7C. 1 2 4 3 5 7 6D.1 2 3 4 5 7 68. 以下關(guān)鍵字序列中， 是堆。. 16, 72, 31, 23, 94, 53 . 94, 23, 31, 72, 16, 53 . 16, 53, 23, 94, 31, 72 . 16, 23, 53, 31, 94, 729、對記錄序列(314，508，298，123，486，145)依次按個位進(jìn)行一趟基數(shù)排序之后所得的結(jié)果為( )。A、298，123，508，486, 145，314 B、508，314，123，145，486，298C、 123，314，145，486，298，50

4、8D、123，314，145，486，508，29810、已經(jīng)知道關(guān)鍵字序列為(51，22，83，46，75，18，68，30)，對其進(jìn)行快速排序，第一趟劃分完成后的關(guān)鍵字序列是 。A、(18, 22, 30, 46, 51, 75, 68, 83)B、(30, 22, 18, 46, 51, 75, 83, 68)C、(30, 22, 18, 46, 51, 75, 68, 83)D、(30, 22, 18, 46, 51, 83, 68, 75)二、填空題1、使用一個30個元素的數(shù)組存儲循環(huán)隊列，如果采取少用一個元素空間的方法來區(qū)別循環(huán)隊列的隊空和隊滿，約定隊頭指針front等于隊尾指針r

5、ear時表示隊空。假設(shè)為front=29，rear=0，那么隊列中的元素個數(shù)為_。2、 一棵二叉樹有30個葉子結(jié)點，僅有一個孩子的結(jié)點有20個，那么該二叉樹共有 _ 個結(jié)點；假設(shè)某棵完全二叉樹共有100個結(jié)點，那么該葉子結(jié)點數(shù)為 。3、設(shè)某棵二叉樹的中序遍歷序列為ABCD，前序遍歷序列為CABD，那么后序遍歷該二叉樹得到的線性序列為 。4、在有序表22，34，46，58，70，82，94中二分查找關(guān)鍵字22時所需進(jìn)行的關(guān)鍵字比較次數(shù)為 。5、將整數(shù)序列40,50,70,20,10,30 中的數(shù)依次插入到一棵空的平衡二叉樹中，畫出相應(yīng)的平衡二叉樹 。三、應(yīng)用題1、已經(jīng)知道字符串a(chǎn)baababab

6、c，采用KMP算法，計算每個字符的next和nextval函數(shù)的值。 2、假設(shè)某系統(tǒng)在通信聯(lián)絡(luò)中只可能出現(xiàn)5個字符(a, b, c, d, e)，其概率分別為：0.15，0.30，0.20，0.28，0.07，畫出構(gòu)造的Huffman樹和Huffman編碼。 3、設(shè)帶權(quán)有向圖如下所示：求出源點V1到匯點V9之間的關(guān)鍵路徑。4、 已經(jīng)知道Hash函數(shù)為 HK=K mod 9 ，哈希表長為9，用二次探測再散列處理沖突，給出關(guān)鍵字23，34，56，24，75，12，49, 52在散列表中的分布，并求在等概率情況下查找成功的平均查找長度。 5、已經(jīng)知道3階B-樹如右圖所示，畫出將關(guān)鍵字18、110和1

7、20依次插入之后的B-樹。四、程序閱讀題 1、 設(shè)有單鏈表類型定義如下：void f41(LinkList head, int A, int B)LinkList p=head ;while (p !=NULL)if (p-data=A&p-datadata);p=p-next;已經(jīng)知道鏈表h如以下圖所示，給出執(zhí)行f41(h，4，8)之后的輸出結(jié)果；1h697851h697852、寫出下面程序運行之后的結(jié)果。void f42(int n) /n為非負(fù)的十進(jìn)制整數(shù) int e; SeqStack S; InitStack(& S); /堆棧初始化 do Push(& S,n%2); /入棧n =

8、n/2;while (n);while ( ! StackEmpty(& S) /如果堆棧不空，循環(huán)e =Pop(& S); /出棧printf (%ld, e);main() f42(100);3、假設(shè)以二叉鏈表作為二叉樹的存儲結(jié)構(gòu)，其類型定義如下：typedef struct node char data; struct node *lchild, *rchild; 左右孩子指針 BinTNode,*BinTree；已經(jīng)知道如下圖的二叉樹以T為指向根結(jié)點的指針，畫出執(zhí)行f 43(T)后的二叉樹；void f43(BinTree T) BinTree temp; if (T) f 43 (T

9、 - lchild) ; if ( ( T - lchild) & T-rchild) temp=T - lchild-data; T - lchild=T-rchild; T-rchild=temp; f 43(T - rchild) ;4、下面程序?qū)崿F(xiàn)二分查找算法。 Typedef struct KeyType key； InfoType otherinfo； SeqListN+1； int BinSearch(SeqList R, int n，KeyType K) int low=1，high=n； while( (1) ) mid=(1ow+high)2； if( (2) ) return mid； if(RmidkeyK) high=mid-1； else (3) ； return O； BinSearch 請在空白處填寫適當(dāng)內(nèi)容，使該程序功能完整。五、編程題每題10分，共20分1、已給一個帶表頭結(jié)點的單鏈表head，結(jié)點元素值按