山東財經(jīng)大學(xué)-數(shù)據(jù)結(jié)構(gòu)試題

山東財經(jīng)大學(xué)?數(shù)據(jù)結(jié)構(gòu)?期末模擬試題TOC\o"1-5"\h\z\o"CurrentDocument"數(shù)據(jù)結(jié)構(gòu)試卷（二） 6數(shù)據(jù)結(jié)構(gòu)試卷（三） 9數(shù)據(jù)結(jié)構(gòu)試卷（四） 12數(shù)據(jù)結(jié)構(gòu)試卷（五） 15卷（） 19數(shù)據(jù)結(jié)構(gòu)試卷（七） 22\o"CurrentDocument"數(shù)據(jù)結(jié)構(gòu)試卷（九） 28\o"CurrentDocument"數(shù)據(jù)結(jié)構(gòu)試卷（十） 32\o"CurrentDocument"數(shù)據(jù)結(jié)構(gòu)試卷（一）參考答案 36\o"CurrentDocument"數(shù)據(jù)結(jié)構(gòu)試卷（二）參考答案 38\o"CurrentDocument"數(shù)據(jù)結(jié)構(gòu)試卷（三）參考答案 40數(shù)據(jù)結(jié)構(gòu)試卷（四）參考答案 43數(shù)據(jù)結(jié)構(gòu)試卷（五）參考答案 46數(shù)據(jù)結(jié)構(gòu)試卷（六）參考答案 47數(shù)據(jù)結(jié)構(gòu)試卷（七）參考答案 50數(shù)據(jù)結(jié)構(gòu)試卷（A）參考答案 52數(shù)據(jù)結(jié)構(gòu)試卷（九）參考答案 53數(shù)據(jù)結(jié)構(gòu)試卷（+）參考答案 55數(shù)據(jù)結(jié)構(gòu)試卷（一）一、單選題（每題2分，共20分）.棧和隊列的共同特點是（）.A.只允許在端點處插入和刪除元素B.都是先進后出C.都是先進先出D.沒有共同點.用鏈接方式存儲的隊列，在進行插入運算時（）.A.僅修改頭指針 B.頭、尾指針都要修改C.僅修改尾指針 D.頭、尾指針可能都要修改.以下數(shù)據(jù)結(jié)構(gòu)中哪一個是非線性結(jié)構(gòu)？（）A.隊列 B.棧C.線性表D.二叉樹.設(shè)有一個二維數(shù)組A[m][n],假設(shè)4[0][0]存放位置在644（10）,4[2][2]存放位置在676uo）,每個元素占一個空間，問存放在什么位置？腳注（⑼表示用10進制表示。A.688B.A.688B.678C.692D.696.樹最適合用來表示（ ）。B.無序數(shù)據(jù)元素D.B.無序數(shù)據(jù)元素D.元素之間無聯(lián)系的數(shù)據(jù)D.2卜'C.元素之間具有分支層次關(guān)系的數(shù)據(jù).二叉樹的第k層的結(jié)點數(shù)最多為（）.A.2-1B.2K+1C.2K-1.若有18個元素的有序表存放在一維數(shù)組A[19]中，第一個元素放A[l]中，現(xiàn)進行二分查找，則查找A[3]的比較序列的下標依次為（ ）A.1,2,3 B.9,5,2,3C.9,5.3 D.9,4,2,3.對n個記錄的文件進行快速排序，所需要的輔助存儲空間大致為A.0（1）B.0（n）C.0（log2n）D.0（n2）.對于線性表（7,34,55,25,64,46,20,10）進行散列存儲時，若選用H（K）=K%9作為散列函數(shù)，則散列地址為1的元素有（）個，A.1 B.2 C.3 D.4.設(shè)有6個結(jié)點的無向圖，該圖至少應(yīng)有（ ）條邊才能確保是一個連通圖。A.5 B.6 C.7 D.8二、填空題（每空1分，共26分）.通常從四個方面評價算法的質(zhì)量：、、和.一個算法的時間復(fù)雜度為(〃3+"21og2〃+14〃)/〃2,其數(shù)量級表示為。.假定一棵樹的廣義表表示為A(C,D(E,F,G),H(I,J)),則樹中所含的結(jié)點數(shù)為個，樹的深度為,樹的度為o.后綴算式923+-102/-的值為o中綴算式(3+4X)-2Y/3對應(yīng)的后綴算式為。.若用鏈表存儲一棵二叉樹時，每個結(jié)點除數(shù)據(jù)域外，還有指向左孩子和右孩子的兩個指針。在這種存儲結(jié)構(gòu)中，n個結(jié)點的二叉樹共有個指針域，其中有個指針域是存放了地址，有個指針是空指針。.對于一個具有n個頂點和e條邊的有向圖和無向圖，在其對應(yīng)的鄰接表中，所含邊結(jié)點分別有個和個O.AOV網(wǎng)是一種的圖。.在一個具有n個頂點的無向完全圖中，包含有條邊，在一個具有n個頂點的有向完全圖中，包含有條邊。.假定一個線性表為(12,23,74,55,63,40),若按Key%4條件進行劃分，使得同一余數(shù)的元素成為一個子表，則得到的四個子表分別為、、和..向一棵B-樹插入元素的過程中，若最終引起樹根結(jié)點的分裂，則新樹比原樹的高度.在堆排序的過程中，時任一分支結(jié)點進行篩運算的時間復(fù)雜度為,整個堆排序過程的時間復(fù)雜度為。.在快速排序、堆排序、歸并排序中，排序是穩(wěn)定的。三、計算題(每題6分，共24分)1.在如下數(shù)組A中鏈接存儲了一個線性表，表頭指針為A⑼.next,試寫出該線性表。A01234567data605078903440next35720412.請畫出下圖的鄰接矩陣和鄰接表.已知一個圖的頂點集V和邊集E分別為：V={1,2,3,4,5,6,7}：E={(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15,,(3,6)9,(4,6)4,(4,7)20,(5,6)18,(6,7)25};用克魯斯卡爾算法得到最小生成樹，試寫出在最小生成樹中依次得到的各條邊。.畫出向小根堆中加入數(shù)據(jù)4,2,5,8,3時，每加入一個數(shù)據(jù)后堆的變化。四、閱讀算法(每題7分，共14分)LinkListmynote(LinkListL){//L是不帶頭結(jié)點的單鏈表的頭指針if(L&&L->next){q=L；L=L->next；p=L；SI： while(p->next)p=p—>next；S2： p—>next=q；q—>next=NULL：)returnL；}請回答下列問題：(1)說明語句si的功能；(2)說明語句組S2的功能；(3)設(shè)鏈表表示的線性表為(a/2,…,%)，寫出算法執(zhí)行后的返回值所表示的線性表。voidABC(BTNode*BT)(ifBT{ABC(BT->left);ABC(BT->right);cout?BT->data?')}該算法的功能是：五、算法填空(共8分)二叉搜索樹的查找一遞歸算法：boolFind(BTreeNode*BST,ElemType&item)if(BST==NULL)returnfalse;//查找失敗else(if(item=BST->data){item=:BST->data;〃查找成功return;}elseif(item<BST^>data)returnFind(,item);elsereturnFind(,item);)//if)六、編寫算法(共8分)統(tǒng)計出單鏈表HL中結(jié)點的值等于給定值X的結(jié)點數(shù)。intCountX(LNode*IIL,ElemTypex)數(shù)據(jù)結(jié)構(gòu)試卷(二)一、選擇題(24分).下面關(guān)于線性表的敘述錯誤的是()o(A)線性表采用順序存儲必須占用一片連續(xù)的存儲空間(B)線性表采用鏈式存儲不必占用一片連續(xù)的存儲空間(0線性表采用鏈式存儲便于插入和刪除操作的實現(xiàn)(D)線性表采用順序存儲便于插入和刪除操作的實現(xiàn).設(shè)哈夫曼樹中的葉子結(jié)點總數(shù)為m,若用二叉鏈表作為存儲結(jié)構(gòu)，則該哈夫曼樹中總共有()個空指針域。(A)2m-1 (B)2m (C)2m+l(D)4m.設(shè)順序循環(huán)隊列Q[0：MT]的頭指針和尾指針分別為F和R,頭指針F總是指向隊頭元素的前一位置，尾指針R總是指向隊尾元素的當前位置，則該循環(huán)隊列中的元素個數(shù)為()o(A)R-F (B)F-R (C)(R-F+M)%M(D)(F-R+M)%M.設(shè)某棵二叉樹的中序遍歷序列為ABCD,前序遍歷序列為CABD,則后序遍歷該二叉樹得到序列為()。(A)BADC (B)BCDA (C)CDAB (D)CBDA.設(shè)某完全無向圖中有n個頂點，則該完全無向圖中有()條邊。(A)n(n-l)/2 (B)n(n-l) (C)n- (D)nJ-l.設(shè)某棵二叉樹中有2000個結(jié)點，則該二叉樹的最小高度為()?(A)9 (B)10 (C)11 (D)12.設(shè)某有向圖中有n個頂點，則該有向圖對應(yīng)的鄰接表中有()個表頭結(jié)點。(A)n-1 (B)n (C)n+1 (D)2n-l.設(shè)一組初始記錄關(guān)鍵字序列(5,2,6,3,8),以第一個記錄關(guān)鍵字5為基準進行一趟快速排序的結(jié)果為()o(D)2,3,6,5,8(A)2,3,5,8,6 (B)3,2,5,8,6(D)2,3,6,5,8(C)3,2,5,6,8二、填空題(24分).為了能有效地應(yīng)用HASH查找技術(shù)，必須解決的兩個問題是和.下面程序段的功能實現(xiàn)數(shù)據(jù)x進棧，要求在下劃線處填上正確的語句。typedefstruct{ints[100];inttop;}sqstack;voidpush(sqstack&stack,intx)(if(stack.top==m-l)printf("overflow")；else{;；}).中序遍歷二叉排序樹所得到的序列是序列(填有序或無序)。.快速排序的最壞時間復(fù)雜度為,平均時間復(fù)雜度為..設(shè)某棵二叉樹中度數(shù)為0的結(jié)點數(shù)為No,度數(shù)為1的結(jié)點數(shù)為N.,則該二叉樹中度數(shù)為2的結(jié)點數(shù)為；若采用二叉鏈表作為該二叉樹的存儲結(jié)構(gòu)，則該二叉樹中共有個空指針域。.設(shè)某無向圖中頂點數(shù)和邊數(shù)分別為n和e,所有頂點的度數(shù)之和為d,則6=o.設(shè)一組初始記錄關(guān)鍵字序列為(55,63,44,38,75,80,31,56),則利用篩選法建立的初始堆為O.已知一有向圖的鄰接表存儲結(jié)構(gòu)如下：從頂點1出發(fā)，DFS遍歷的輸出序列是,BFS遍歷的輸出序列是圖的鄰接表存儲結(jié)構(gòu)三、應(yīng)用題(36分).設(shè)一組初始記錄關(guān)鍵字序列為(45,80,48,40,22,78),則分別給出第4趟簡單選擇排序和第4趟直接插入排序后的結(jié)果。.設(shè)指針變量P指向雙向鏈表中結(jié)點A,指針變量q指向被插入結(jié)點B,要求給出在結(jié)點A的后面插入結(jié)點B的操作序列(設(shè)雙向鏈表中結(jié)點的兩個指針域分別為11ink和rlink)。.設(shè)一組有序的記錄關(guān)鍵字序列為(13,18,24,35,47,50,62,83,90),查找方法用二分查找，要求計算出查找關(guān)鍵字62時的比較次數(shù)并計算出查找成功時的平均查找長度。.設(shè)一棵樹T中邊的集合為｛(A,B),(A,C),(A,D),(B,E),(C,F),(C,G)),要求用孩子兄弟表示法(二叉鏈表)表示出該樹的存儲結(jié)構(gòu)并將該樹轉(zhuǎn)化成對應(yīng)的二叉樹。.設(shè)有無向圖G,要求給出用普里姆算法構(gòu)造最小生成樹所走過的邊的集合。.設(shè)有一組初始記錄關(guān)鍵字為(45,80,48,40,22,78),要求構(gòu)造一棵二叉排序樹并給出構(gòu)造過程。四、算法設(shè)計題(16分).設(shè)有一組初始記錄關(guān)鍵字序列(M,Kz,…，K")，要求設(shè)計一個算法能夠在0(n)的時間復(fù)雜度內(nèi)將線性表劃分成兩部分，其中左半部分的每個關(guān)鍵字均小于K,,右半部分的每個關(guān)鍵字均大于等于K,。.設(shè)有兩個集合A和集合B,要求設(shè)計生成集合C=ACB的算法，其中集合A、B和C用鏈式存儲結(jié)構(gòu)表示。

數(shù)據(jù)結(jié)構(gòu)試卷(三)一、選擇題(每題1分，共20分).設(shè)某數(shù)據(jù)結(jié)構(gòu)的二元組形式表示為A=(D,R),D={01,02,03,04,05,06,07,08,09},R={r},u{<01,02>,<01,03>,<01,04>,<02,05>,<02,06>,<03,07>,<03,08>,<03,09>},則數(shù)據(jù)結(jié)構(gòu)A是().(A)線性結(jié)構(gòu)(B)樹型結(jié)構(gòu) (C)物理結(jié)構(gòu)(D)圖型結(jié)構(gòu).下面程序的時間復(fù)雜為()for(i=l,s=0；i<=n；i++){t=l；for(j=1；j<=i；j++)t=t*j；s=s+t；}(A)0(n) (B)0(n2) (00(n3) (D)0(n*).設(shè)指針變量p指向單鏈表中結(jié)點A,若刪除單鏈表中結(jié)點A,則需要修改指針的操作序列為()oq=p->next； p->data=q->data； p->next=q->next； free(q)；q=p->next； q->data=p->data； p->next=q->next； free(q)；q=p->next； p->next=q->next； free(q)；q-p->next； p->data=q->data； free(q)；.設(shè)有n個待排序的記錄關(guān)鍵字，則在堆排序中需要()個輔助記錄單元。(A)1 (B)n (C)nlog2n(D)n3.設(shè)一組初始關(guān)鍵字記錄關(guān)鍵字為(20,15,14,18,21,36,40,10),則以20為基準記錄的一趟快速排序結(jié)束后的結(jié)果為()。TOC\o"1-5"\h\z10, 15, 14, 18, 20, 36, 40, 2110, 15, 14, 18, 20, 40, 36, 2110, 15, 14, 20, 18, 40, 36, 2115, 10, 14, 18, 20, 36, 40, 21.設(shè)二叉排序樹中有n個結(jié)點，則在二叉排序樹的平均平均查找長度為()。(A)0(1) (B)0(log2n)(C) (D)0(n2).設(shè)無向圖G中有n個頂點e條邊，則其對應(yīng)的鄰接表中的表頭結(jié)點和表結(jié)點的個數(shù)分別為().(A)n,ee,(A)n,ee,n2n,en,2e.設(shè)某強連通圖中有n個頂點，則該強連通圖中至少有（）條邊。(A)n(n-l)(B)n+1(0n(A)n(n-l)(B)n+1(0n(D)n(n+l).設(shè)有5000個待排序的記錄關(guān)鍵字，如果需要用最快的方法選出其中最小的10個記錄關(guān)鍵字，則用下列（）方法可以達到此目的。（A）快速排序 （B）堆排序 （C）歸并排序 （D）插入排序.下列四種排序中（）的空間復(fù)雜度最大。（A）插入排序 （B）冒泡排序 （C）堆排序 （D）歸并排序二、填空殖（每空1分共20分）.數(shù)據(jù)的物理結(jié)構(gòu)主要包括和兩種情況。.設(shè)一棵完全二叉樹中有500個結(jié)點，則該二叉樹的深度為;若用二叉鏈表作為該完全二叉樹的存儲結(jié)構(gòu)，則共有個空指針域。.設(shè)輸入序列為1、2、3,則經(jīng)過棧的作用后可以得到種不同的輸出序列。.設(shè)有向圖G用鄰接矩陣A[n][n]作為存儲結(jié)構(gòu)，則該鄰接矩陣中第i行上所有元素之和等于頂點i的,第i列上所有元素之和等于頂點i的。.設(shè)哈夫曼樹中共有n個結(jié)點，則該哈夫曼樹中有個度數(shù)為1的結(jié)點。.設(shè)有向圖G中有n個頂點e條有向邊，所有的頂點入度數(shù)之和為d,則e和d的關(guān)系為.遍歷二叉排序樹中的結(jié)點可以得到一個遞增的關(guān)健字序列（填先序、中序或后序）。.設(shè)查找表中有100個元素，如果用二分法查找方法查找數(shù)據(jù)元素X,則最多需要比較次就可以斷定數(shù)據(jù)元素X是否在查找表中。.不論是順序存儲結(jié)構(gòu)的棧還是鏈式存儲結(jié)構(gòu)的棧，其入棧和出棧操作的時間復(fù)雜度均為.設(shè)有n個結(jié)點的完全二叉樹，如果按照從自上到下、從左到右從1開始順序編號，則第i個結(jié)點的雙親結(jié)點編號為,右孩子結(jié)點的編號為。.設(shè)一組初始記錄關(guān)鍵字為（72,73,71,23,94,16,5）,則以記錄關(guān)鍵字72為基準的一趟快速排序結(jié)果為。.設(shè)有向圖G中有向邊的集合￡={<1,2>,<2,3>,<1,4>,<4,2>,<4,3>},則該圖的一種拓撲序列為。.下列算法實現(xiàn)在順序散列表中查找值為x的關(guān)鍵字，請在下劃線處填上正確的語句。structrecord{intkey;intothers;};inthashsqsearch(structrecordhashtable[],intk)(inti,j;j=i=k%p;while(hashtable|j].key!=k&&hashtable|j|.flag!=O){j=()%m;if(i=j)retum(-l);}if()retum(j);elseretum(-l);).下列算法實現(xiàn)在二叉排序樹上查找關(guān)鍵值k,請在下劃線處填上正確的語句。typedefstructnode{intkey;structnode*lchild;structnode*rchild;)bitree;bitree*bstsearch(bitree*t,intk)(if(t==0)retum(O);elsewhile(t!=0)if(t->key==k);elseif(t->key>k)t=t->lchild;else:三、計算題(每題10分，共30分).已知二義樹的前序遍歷序列是AEFBGCDHIKJ,中序遍歷序歹ij是EFAGBCHKIJD,畫出此二叉樹，并畫出它的后序線索二叉樹。.已知待散列的線性表為(36,15,40,63,22),散列用的一維地址空間為[0..6],假定選用的散列函數(shù)是H(K)=Kmod7,若發(fā)生沖突采用線性探查法處理，試：(1)計算出每一個元素的散列地址并在下圖中填寫出散列表：0 12 3 4 5 6(2)求出在查找每一個元素概率相等情況下的平均查找長度。.已知序列(10,18,4,3,6,12,1,9,18,8)請用快速排序?qū)懗雒恳惶伺判虻慕Y(jié)果。四、算法設(shè)計題(每題15分，共30分).設(shè)計在單鏈表中刪除值相同的多余結(jié)點的算法。.設(shè)計一個求結(jié)點x在二叉樹中的雙親結(jié)點算法。數(shù)據(jù)結(jié)構(gòu)試卷(四)一、選擇題(每題1分共20分).設(shè)一維數(shù)組中有n個數(shù)組元素，則讀取第i個數(shù)組元素的平均時間復(fù)雜度為().(A)O(n) (B)O(nlog2n)(C)0(1) (D)0(n2).設(shè)一棵二叉樹的深度為k,則該二叉樹中最多有()個結(jié)點。(A)2k-1 (B) 2k (C)2k-1 (D) 2k-1.設(shè)某無向圖中有n個頂點e條邊，則該無向圖中所有頂點的入度之和為()?(A)n (B) e (C)2n (D) 2e.在二叉排序樹中插入一個結(jié)點的時間復(fù)雜度為()。(A)0(1) (B)0(n) (C)0(logm) (D)0(n2).設(shè)某有向圖的鄰接表中有n個表頭結(jié)點和m個表結(jié)點，則該圖中有()條有向邊。(A)n (B)n-1 (C)m (D)m-1.設(shè)一組初始記錄關(guān)鍵字序列為(345,253,674,924,627),則用基數(shù)排序需要進行()趟的分配和回收才能使得初始關(guān)鍵字序列變成有序序列。(A)3 (B)4 (C)5 (D)8.設(shè)用鏈表作為棧的存儲結(jié)構(gòu)則退棧操作()o(A)必須判別棧是否為滿 (B)必須判別棧是否為空(0判別棧元素的類型 (D)對棧不作任何判別.下列四種排序中()的空間復(fù)雜度最大。(A)快速排序 (B)冒泡排序(C)希爾排序 (D)堆.設(shè)某二叉樹中度數(shù)為0的結(jié)點數(shù)為No,度數(shù)為1的結(jié)點數(shù)為Ni,度數(shù)為2的結(jié)點數(shù)為N”則下列等式成立的是()?(A)No=Ni+l(B)No=Ni+Nz(C)No=N2+1 (D)No=2N1+1.設(shè)有序順序表中有n個數(shù)據(jù)元素，則利用二分查找法查找數(shù)據(jù)元素X的最多比較次數(shù)不超過().(A)log2n+l(B)log2n-l(C)log2n(D)log2(n+l)二、填空題(每空1分共20分).設(shè)有n個無序的記錄關(guān)鍵字，則直接插入排序的時間復(fù)雜度為,快速排序的平均時間復(fù)雜度為..設(shè)指針變量p指向雙向循環(huán)鏈表中的結(jié)點X,則刪除結(jié)點X需要執(zhí)行的語句序列為_(設(shè)結(jié)點中的兩個指針域分別為llink和rlink)..根據(jù)初始關(guān)鍵字序列(19,22,01,38,10)建立的二叉排序樹的高度為..深度為k的完全二叉樹中最少有個結(jié)點。.設(shè)初始記錄關(guān)鍵字序列為(凡，心，…，K?),則用篩選法思想建堆必須從第一一個元素開始進行篩選。.設(shè)哈夫曼樹中共有99個結(jié)點，則該樹中有個葉子結(jié)點；若采用二叉鏈表作為存儲結(jié)構(gòu)，則該樹中有個空指針域。.設(shè)有一個順序循環(huán)隊列中有M個存儲單元，則該循環(huán)隊列中最多能夠存儲個隊列元素；當前實際存儲個隊列元素(設(shè)頭指針F指向當前隊頭元素的前一個位置，尾指針指向當前隊尾元素的位置)。.設(shè)順序線性表中有n個數(shù)據(jù)元素，則第i個位置上插入一個數(shù)據(jù)元素需要移動表中一個數(shù)據(jù)元素：刪除第i個位置上的數(shù)據(jù)元素需要移動表中個元素。.設(shè)一組初始記錄關(guān)鍵字序列為(20,18,22,16,30,19),則以20為中軸的一趟快速排序結(jié)果為。.設(shè)一組初始記錄關(guān)鍵字序列為(20,18,22,16,30,19),則根據(jù)這些初始關(guān)鍵字序列建成的初始堆為O.設(shè)某無向圖G中有n個頂點，用鄰接矩陣A作為該圖的存儲結(jié)構(gòu)，則頂點i和頂點j互為鄰接點的條件是。.設(shè)無向圖對應(yīng)的鄰接矩陣為A,則A中第i上非0元素的個數(shù)第i列上非0元素的個數(shù)(填等于，大于或小于)。.設(shè)前序遍歷某二叉樹的序列為ABCD,中序遍歷該二叉樹的序列為BADC,則后序遍歷該二叉樹的序列為O.設(shè)散列函數(shù)H(k)=kmodp,解決沖突的方法為鏈地址法。要求在下列算法劃線處填上正確的語句完成在散列表hashtalbe中查找關(guān)鍵字值等于k的結(jié)點，成功時返回指向關(guān)鍵字的指針，不成功時返回標志0。typedefstructnode{intkey;structnode*next;JIklist;voidcreatelkhash(lklist*hashtable[])inti,k;Iklist*s;fbr(i=0;i<m;i++);fbr(i=0;i<n;i++)|s=(Iklist*)malloc(sizeof(lklist));s->key=a[i];k=a[i]%p;s->next=hashtable[k];:}三、計算題(每題10分，共30分)1、畫出廣義表LS=((),(e),(a,(b,c,d)))的頭尾鏈表存儲結(jié)構(gòu)。2、下圖所示的森林：(1)求樹(a)的先根序列和后根序列；(2)求森林先序序列和中序序列；(3)將此森林轉(zhuǎn)換為相應(yīng)的二叉樹；3,設(shè)散列表的地址范圍是[0..9],散列函數(shù)為H(key)=(key2+2)MOD9,并采用鏈表處理沖突，請畫出元素7、4、5、3、6、2、8、9依次插入散列表的存儲結(jié)構(gòu)。四、算法設(shè)計題(每題10分，共30分).設(shè)單鏈表中有僅三類字符的數(shù)據(jù)元素(大寫字母、數(shù)字和其它字符)，要求利用原單鏈表中結(jié)點空間設(shè)計出三個單鏈表的算法，使每個單鏈表只包含同類字符。.設(shè)計在鏈式存儲結(jié)構(gòu)上交換二叉樹中所有結(jié)點左右子樹的算法。.在鏈式存儲結(jié)構(gòu)上建立一棵二叉排序樹。

數(shù)據(jù)結(jié)構(gòu)試卷(五)一、選擇題(20分).數(shù)據(jù)的最小單位是()o(A)數(shù)據(jù)項(B)數(shù)據(jù)類型 (C)數(shù)據(jù)元素(D)數(shù)據(jù)變量.設(shè)一組初始記錄關(guān)鍵字序列為(50,40,95,20,15,70,60,45),則以增量d=4的一趟希爾排序結(jié)束后前4條記錄關(guān)鍵字為()?40,50,20,95 (B)15,40,60,20(C)15,20,40,45 (D)45,40,15,203.設(shè)一組初始記錄關(guān)鍵字序列為(25,50,15,35,80,85,20,40,36,70),其中含有5個長度為2的有序子表，則用歸并排序的方法對該記錄關(guān)鍵字序列進行一趟歸并后的結(jié)果為()oTOC\o"1-5"\h\z(A)15, 25, 35, 50, 20, 40, 80, 85, 36, 7015, 25, 35, 50, 80, 20, 85, 40, 70, 3615, 25, 35, 50, 80, 85, 20, 36, 40, 7015, 25, 35, 50, 80, 20, 36, 40, 70, 854.函數(shù)substr("DATASTRUCTURE”,5,9)的返回值為()?(A)“STRUCTURE” (B)“DATA”(C)“ASTRUCTUR” (D)“DATASTRUCTURE”.設(shè)一個有序的單鏈表中有n個結(jié)點，現(xiàn)要求插入一個新結(jié)點后使得單鏈表仍然保持有序，則該操作的時間復(fù)雜度為()?(A)O(logzn)(B)0(1) (C)0(nz) (D)0(n).設(shè)一棵m叉樹中度數(shù)為0的結(jié)點數(shù)為N。，度數(shù)為1的結(jié)點數(shù)為N”……，度數(shù)為m的結(jié)點數(shù)為Nm,則No=()。(A)Ni+Nz+ +Nm (B)1+弗+22+3'+ +(m-l)Nm(C)M+2N3+3N計 +(m-l)Nm(D)2Ni+3Nz+ +(m+l)Nm.設(shè)有序表中有1000個元素，則用二分查找查找元素X最多需要比較()次。(A)25(B)10(A)25(B)10(07(D)1.設(shè)連通圖G中的邊集氏{6,b),(a,e),(a,c),(b,e),(e,d),(d,f),(f,c)},則從頂點a出發(fā)可以得到一種深度優(yōu)先遍歷的頂點序列為((A)abedfc(B)acfebd(C)aebdfc (D)aedfcb.設(shè)輸入序列是1、2、3,……、n,經(jīng)過棧的作用后輸出序列的第一個元素是n,則輸出序列中第i個輸出元素是()o(A)n-i (B)n-l-i(C)n+l-i (D)不能確定10設(shè)一組初始記錄關(guān)鍵字序列為(45,80,55,40,42,85),則以第一個記錄關(guān)鍵字45為基準而得到一趟快速排序的結(jié)果是().(A)40,42,45,55,80,83 (B)42,40,45,80,85,88(C)42,40,45,55,80,85 (D)42,40,45,85,55,80二、填空題(共20分).設(shè)有一個順序共享棧S[0：n-1],其中第一個棧項指針topi的初值為T,第二個枝頂指針toP2的初值為n,則判斷共享棧滿的條件是..在圖的鄰接表中用順序存儲結(jié)構(gòu)存儲表頭結(jié)點的優(yōu)點是。.設(shè)有一個n階的下三角矩陣A,如果按照行的順序?qū)⑾氯蔷仃囍械脑?包括對角線上元素)存放在n(n+l)個連續(xù)的存儲單元中，則與A[0][0]之間有個數(shù)據(jù)元素。.棧的插入和刪除只能在棧的棧頂進行，后進棧的元素必定先出棧，所以又把棧稱為—表：隊列的插入和刪除運算分別在隊列的兩端進行，先進隊列的元素必定先出隊列，所以又把隊列稱為表。.設(shè)一棵完全二叉樹的順序存儲結(jié)構(gòu)中存儲數(shù)據(jù)元素為ABCDEF,則該二叉樹的前序遍歷序列為 中序遍歷序列為,后序遍歷不列為 。.設(shè)一棵完全二叉樹有128個結(jié)點，則該完全二叉樹的深度為,有—個葉子結(jié)點。.設(shè)有向圖G的存儲結(jié)構(gòu)用鄰接矩陣A來表示，則A中第i行中所有非零元素個數(shù)之和等于頂點i的,第i列中所有非零元素個數(shù)之和等于頂點i的..設(shè)一組初始記錄關(guān)鍵字序列(k“k2,……，kJ是堆，則對i=l,2, n/2而言滿足的條件為?.下面程序段的功能是實現(xiàn)冒泡排序算法，請在下劃線處填上正確的語句。

voidbubble(intr[n])for(i=l;i<=n-l;i++)(for(exchange=O,j=O;j<;j++)if(r[j]>r[j+1|){temp=r|j+1];;r|j]=：temp;exchange=1;}if(exchange==O)return：}).下面程序段的功能是實現(xiàn)二分查找算法，請在下劃線處填上正確的語句。structrecord}intkey;intothers;);intbisearch(structrecordr[],intk)(intlow=0,mid,high=n-l;while(low<=high)if(r[mid|.key==k)return(mid+l);elseif()high=mid-l;elselow=mid+l;return(O);三、應(yīng)用題(32分).設(shè)某棵二叉樹的中序遍歷序列為DBEAC,前序遍歷序列為ABDEC,要求給出該二叉樹的的后序遍歷序列。.設(shè)無向圖G(如右圖所示)，給出該圖的最小生成樹上邊的集合并計算最小生成樹各邊上的權(quán)值之和。.設(shè)一組初始記錄關(guān)鍵字序列為(15,17,18,22,35,51,60),要求計算出成功查找時的平均查找長度。.設(shè)散列表的長度為8,散列函數(shù)H(k)=kmod7,初始記錄關(guān)鍵字序列為(25,31,8,27,13,68),要求分別計算出用線性探測法和鏈地址法作為解決沖突方法的平均查找長度。四、算法設(shè)計題（28分）.設(shè)計判斷兩個二叉樹是否相同的算法。.設(shè)計兩個有序單鏈表的合并排序算法。數(shù)據(jù)結(jié)構(gòu)試卷(六)一、選擇題(30分).設(shè)一組權(quán)值集合竹｛2,3,4,5,6),則由該權(quán)值集合構(gòu)造的哈夫曼樹中帶權(quán)路徑長度之和為()?(A)20 (B)30 (C)40 (D)45.執(zhí)行一趟快速排序能夠得到的序列是()。TOC\o"1-5"\h\z[41, 12, 34, 45, 27]55[72, 63][45, 34, 12, 41] 55[72,63, 27][63, 12, 34, 45, 27]55[41, 72][12, 27, 45, 41] 55[34,63, 72].設(shè)一條單鏈表的頭指針變量為head且該鏈表沒有頭結(jié)點，則其判空條件是()。(A)head==0 (B)head->next=O(C)head->next==head (D)head!=0.時間更雜度不受數(shù)據(jù)初始狀態(tài)影響而恒為0(nlog2n)的是()。(A)堆排序(B)冒泡排序(C)希爾排序(D)快速排序.設(shè)二叉樹的先序遍歷序列和后序遍歷序列正好相反，則該二叉樹滿足的條件是()。(A)空或只有一個結(jié)點 (B)高度等于其結(jié)點數(shù)(0任一結(jié)點無左孩子 (D)任一結(jié)點無右孩子.--趟排序結(jié)束后不一定能夠選出一個元素放在其最終位置上的是()?(A)堆排序(B)冒泡排序(C)快速排序 (D)希爾排序.設(shè)某棵三叉樹中有40個結(jié)點，則該三叉樹的最小高度為()。(A)3 (B)4 (C)5 (D)6.順序查找不論在順序線性表中還是在鏈式線性表中的時間復(fù)雜度為().(A)0(n) (B)0(n2) (C)0(n,/2) (D)0(log2n).二路歸并排序的時間復(fù)雜度為()。(A)0(n) (B)0(n2) (C)0(nlog2n) (D)0(log2n).深度為k的完全二叉樹中最少有()個結(jié)點。(A)2lr,-l (B)2r (C)2kl+l (D)2-1.設(shè)指針變量front表示鏈式隊列的隊頭指針，指針變量rear表示鏈式隊列的隊尾指針,指針變量s指向?qū)⒁腙犃械慕Y(jié)點X,則入隊列的操作序列為()。(A)front->next=s；front=s；(B)s->next=rear；rear=s；(C)rear_>next=s；rear=s； (D)s->next=front；front=s；.設(shè)某無向圖中有n個頂點e條邊，則建立該圖鄰接表的時間復(fù)雜度為().(A) 0(n+e) (B) 0(/) (C) 0(ne) (D) 0(n3).設(shè)某哈夫曼樹中有199個結(jié)點，則該哈夫曼樹中有()個葉子結(jié)點。(A) 99 (B) 100 (C) 101 (D) 102.設(shè)二叉排序樹上有n個結(jié)點，則在二叉排序樹上查找結(jié)點的平均時間復(fù)雜度為()。(A) 0(n) (B) 0(n2) (C) 0(nlog2n) (D) 0(log2n).設(shè)用鄰接矩陣A表示有向圖G的存儲結(jié)構(gòu)，則有向圖G中頂點i的入度為()?(A)第i行非。元素的個數(shù)之和(B)第i列非0元素的個數(shù)之和(0第i行。元素的個數(shù)之和(D)第i列0元素的個數(shù)之和二、判斷題(20分).調(diào)用一次深度優(yōu)先遍歷可以訪問到圖中的所有頂點。().分塊查找的平均查找長度不僅與索引表的長度有關(guān)，而且與塊的長度有關(guān)。().冒泡排序在初始關(guān)鍵字序列為逆序的情況下執(zhí)行的交換次數(shù)最多。().滿二叉樹一定是完全二叉樹，完全二叉樹不一定是滿二叉樹。().設(shè)一棵二叉樹的先序序列和后序序列，則能夠唯一確定出該二叉樹的形狀。().層次遍歷初始堆可以得到一個有序的序列。().設(shè)一棵樹T可以轉(zhuǎn)化成二叉樹BT,則二叉樹BT中一定沒有右子樹。().線性表的順序存儲結(jié)構(gòu)比鏈式存儲結(jié)構(gòu)更好。().中序遍歷二叉排序樹可以得到一個有序的序列。().快速排序是排序算法中平均性能最好的種排序。()三、填空題(30分).for(i=l,t=l,s=0；i<=n；i++){t=t*i；s=s+t；}的時間復(fù)雜度為..設(shè)指針變量p指向單鏈表中結(jié)點A,指針變量s指向被插入的新結(jié)點X,則進行插入操作的語句序列為(設(shè)結(jié)點的指針域為next)..設(shè)有向圖G的二元組形式表示為G=(D,R),D={1,2,3,4,5},R={r},u{<1,2>,<2,4>,<4,5>,<1,3>,<3,2>,<3,5>},則給出該圖的一種拓撲排序序列。.設(shè)無向圖G中有n個頂點，則該無向圖中每個頂點的度數(shù)最多是..設(shè)二叉樹中度數(shù)為0的結(jié)點數(shù)為50,度數(shù)為1的結(jié)點數(shù)為30,則該二叉樹中總共有一個結(jié)點數(shù)。.設(shè)F和R分別表示順序循環(huán)隊列的頭指針和尾指針，則判斷該循環(huán)隊列為空的條件為.設(shè)二叉樹中結(jié)點的兩個指針域分別為Ichild和rchild,則判斷指針變量p所指向的結(jié)點為葉子結(jié)點的條件是O.簡單選擇排序和直接插入排序算法的平均時間復(fù)雜度為..快速排序算法的空間復(fù)雜度平均情況下為,最壞的情況下為。.散列表中解決沖突的兩種方法是和o四、算法設(shè)計題（20分）.設(shè)計在順序有序表中實現(xiàn)二分查找的算法。.設(shè)計判斷二叉樹是否為二叉排序樹的算法。.在鏈式存儲結(jié)構(gòu)上設(shè)計直接插入排序算法數(shù)據(jù)結(jié)構(gòu)試卷(七)一、選擇題(30分).設(shè)某無向圖有n個頂點，則該無向圖的鄰接表中有()個表頭結(jié)點。(A)2n (B)n (C)n/2 (D)n(n-l).設(shè)無向圖G中有n個頂點，則該無向圖的最小生成樹上有()條邊。(A)n (B)n-1 (C)2n (D)2n-l.設(shè)一組初始記錄關(guān)鍵字序列為(60,80,55,40,42,85),則以第一個關(guān)鍵字45為基準而得到的一趟快速排序結(jié)果是()。(A)40,42,60,55,80,85 (B)42,45,55,60,85,80(C)42,40,55,60,80,85 (D)42,40,60,85,55,80.()二叉排序樹可以得到一個從小到大的有序序列。(A)先序遍歷(B)中序遍歷 (C)后序遍歷 (D)層次遍歷.設(shè)按照從上到下、從左到右的順序從1開始對完全二叉樹進行順序編號，則編號為i結(jié)點的左孩子結(jié)點的編號為().(A)2i+l (B)2i (C)i/2 (D)2i-l.程序段s=i=0；do{i=i+l；s=s+i；}while(i<=n)；的時間復(fù)雜度為()。(A)0(n) (B)0(nlog2n) (C)0(n2) (D)0(n3/2).設(shè)帶有頭結(jié)點的單向循環(huán)鏈表的頭指針變量為head,則其判空條件是().(A)head==0 (B)head->next=0(C)head->next=head (D)head!=0.設(shè)某棵二叉樹的高度為10,則該二叉樹上葉子結(jié)點最多有()。(A)20 (B)256 (C)512 (D)1024.設(shè)一組初始記錄關(guān)鍵字序列為(13,18,24,35,47,50,62,83,90,115,134),則利用二分法查找關(guān)鍵字90需要比較的關(guān)鍵字個數(shù)為(),(A)1 (B)2 (C)3 (D)4.設(shè)指針變量top指向當前鏈式棧的棧頂，則刪除棧頂元素的操作序列為()。top=top+l;top=top+l;(C)top->next=top;top=top-l;(D)top=top->next;二、判斷題（20分）.不論是入隊列操作還是入棧操作，在順序存儲結(jié)構(gòu)上都需要考慮“溢出”情況。（）.當向二叉排序樹中插入一個結(jié)點，則該結(jié)點一定成為葉子結(jié)點。（）.設(shè)某堆中有n個結(jié)點，則在該堆中插入一個新結(jié)點的時間復(fù)雜度為O（logzn）。（）.完全二叉樹中的葉子結(jié)點只可能在最后兩層中出現(xiàn)。（）.哈夫曼樹中沒有度數(shù)為1的結(jié)點。（）.對連通圖進行深度優(yōu)先遍歷可以訪問到該圖中的所有頂點。（）.先序遍歷一棵二叉排序樹得到的結(jié)點序列不一定是有序的序列。（）.由樹轉(zhuǎn)化成二叉樹，該二叉樹的右子樹不一定為空。（）.線性表中的所有元素都有一個前驅(qū)元素和后繼元素。（）.帶權(quán)無向圖的最小生成樹是唯一的。（）三、填空題（30分）.設(shè)指針變量p指向雙向鏈表中的結(jié)點A,指針變量s指向被插入的結(jié)點X,則在結(jié)點A的后面插入結(jié)點X的操作序列為=p；s->right=p->right；=s；p->right->left=s；（設(shè)結(jié)點中的兩個指針域分別為left和right）。.設(shè)完全有向圖中有n個頂點，則該完全有向圖中共有條有向條；設(shè)完全無向圖中有n個頂點，則該完全無向圖中共有條無向邊。.設(shè)關(guān)犍字序列為（K“ …，K?）,則用篩選法建初始堆必須從第個元素開始進行篩選。.解決散列表沖突的兩種方法是和..設(shè)一棵三叉樹中有50個度數(shù)為0的結(jié)點，21個度數(shù)為2的結(jié)點，則該二叉樹中度數(shù)為3的結(jié)點數(shù)有個。.高度為h的完全二叉樹中最少有個結(jié)點，最多有個結(jié)點。.設(shè)有一組初始關(guān)鍵字序列為（24,35,12,27,18,26）,則第3趟直接插入排序結(jié)束后的結(jié)果的是..設(shè)有一組初始關(guān)鍵字序列為（24,35,12,27,18,26）,則第3趟簡單選擇排序結(jié)束后的結(jié)果的是..設(shè)一棵二叉樹的前序序列為ABC,則有種不同的二叉樹可以得到這種序列。.下面程序段的功能是實現(xiàn)一趟快速排序，請在下劃線處填上正確的語句。structrecord{intkey;datatypeothers;};voidquickpass(structrecordr[],ints,intt,int&i)(intj=t;structrecordx=r[s];i=s;while(i<j)(while(i<j&&r[j].key>x.key)j=j-l;if(i<j){r[i]=r[j];i=i+l;}while( )i=i+l；if(i<j){r[j]=r[i]j=j-h}四、算法設(shè)計題（20分）.設(shè)計在鏈式結(jié)構(gòu)上實現(xiàn)簡單選擇排序算法。.設(shè)計在順序存儲結(jié)構(gòu)上實現(xiàn)求子串算法。.設(shè)計求結(jié)點在二叉排序樹中層次的算法。一、選擇題(30分).字符串的長度是指()o(A)串中不同字符的個數(shù)(0串中所含字符的個數(shù)數(shù)據(jù)結(jié)構(gòu)試卷(A)一、選擇題(30分).字符串的長度是指()o(A)串中不同字符的個數(shù)(0串中所含字符的個數(shù)數(shù)據(jù)結(jié)構(gòu)試卷(A)(B)串中不同字母的個數(shù)(D)串中不同數(shù)字的個數(shù).建立一個長度為n的有序單鏈表的時間復(fù)雜度為()(A)0(n) (B)0(1) (C)0(n2).兩個字符串相等的充要條件是().(D)0(log2n)(A)兩個字符串的長度相等(B)兩個字符串中對應(yīng)位置上的字符相等(0同時具備(A)和(B)兩個條件(D)以上答案都不對.設(shè)某散列表的長度為100,散列函數(shù)H(k)=k%P,則P通常情況下最好選擇()o(A)99 (B)97 (C)91 (D)93.在二叉排序樹中插入一個關(guān)鍵字值的平均時間復(fù)雜度為()?(A)0(n) (B)0(log2n) (C)0(nlog2n) (D)0(n2).設(shè)一個順序有序表A[l:14]中有14個元素，則采用二分法查找元素A[4]的過程中比較元素的順序為()。(A)A[l],A[2],A[3],A[4] (B)A[l],A[14],A[7],A[4](0A[7],A[3],A[5],A[4] (D)A[7],A[5],A[3],A[4].設(shè)一棵完全二叉樹中有65個結(jié)點，則該完全二叉樹的深度為()。(A)8 (B)7 (C)6 (D)5.設(shè)一棵三叉樹中有2個度數(shù)為1的結(jié)點，2個度數(shù)為2的結(jié)點，2個度數(shù)為3的結(jié)點,則該三叉鏈權(quán)中有()個度數(shù)為。的結(jié)點。(A)5 (B)6 (C)7 (D)8.設(shè)無向圖G中的邊的集合E={(a,b),(a,e),(a,c),(b,e),(e,d),(d,f),(f,c)},則從頂點a出發(fā)進行深度優(yōu)先遍歷可以得到的一種頂點序列為()。(A)aedfcb (B)acfebd (C)aebcfd (D)aedfbc.隊列是一種()的線性表。(A)先進先出 (B)先進后出 (C)只能插入 (D)只能刪除二、判斷題(20分).如果兩個關(guān)鍵字的值不等但哈希函數(shù)值相等，則稱這兩個關(guān)鍵字為同義詞。().設(shè)初始記錄關(guān)鍵字基本有序，則快速排序算法的時間復(fù)雜度為OSlogm)。().分塊查找的基本思想是首先在索引表中進行查找，以便確定給定的關(guān)鍵字可能存在的塊號，然后再在相應(yīng)的塊內(nèi)進行順序查找。().二維數(shù)組和多維數(shù)組均不是特殊的線性結(jié)構(gòu)。().向二叉排序樹中插入一個結(jié)點需要比較的次數(shù)可能大于該二叉樹的高度。().如果某個有向圖的鄰接表中第i條單鏈表為空，則第i個頂點的出度為零。().非空的雙向循環(huán)鏈表中任何結(jié)點的前驅(qū)指針均不為空。().不論線性表采用順序存儲結(jié)構(gòu)還是鏈式存儲結(jié)構(gòu)，刪除值為X的結(jié)點的時間復(fù)雜度均為0(n)o().圖的深度優(yōu)先遍歷算法中需要設(shè)置一個標志數(shù)組，以便區(qū)分圖中的每個頂點是否被訪問過。().稀疏矩陣的壓縮存儲可以用一個三元組表來表示稀疏矩陣中的非。藤O()三、填空題(30分).設(shè)一組初始記錄關(guān)鍵字序列為(49,38,65,97,76,13,27,50),則以d=4為增量的一趟希爾排序結(jié)束后的結(jié)果為o.下面程序段的功能是實現(xiàn)在二叉排序樹中插入一個新結(jié)點，請在下劃線處填上正確的內(nèi)容。typedefstructnode{intdata;structnode*lchild;streetnode*rchild;}bitree;voidbstinsert(bitree*&t,intk)(if(t==0){;t->data=k;t->lchild=t->rchild=O;}elseif(t->data>k)bstinsert(t->lchild,k);else;).設(shè)指針變量p指向單鏈表中結(jié)點A,指針變量s指向被插入的結(jié)點X,則在結(jié)點A的后面插入結(jié)點X需要執(zhí)行的語句序列：s->next=p->next;;。.設(shè)指針變量head指向雙向鏈表中的頭結(jié)點，指針變量p指向雙向鏈表中的第一個結(jié)點,則指針變量p和指針變量head之間的關(guān)系是p=和head=(設(shè)結(jié)點中的兩個指針域分別為Uink和rlink)..設(shè)某棵二叉樹的中序遍歷序列為ABCD,后序遍歷序列為BADC,則其前序遍歷序列為.完全二叉樹中第5層上最少有個結(jié)點，最多有個結(jié)點。.設(shè)有向圖中不存在有向邊<%,%>,則其對應(yīng)的鄰接矩陣A中的數(shù)組元素的值等于?.設(shè)一組初始記錄關(guān)鍵字序列為(49,38,65,97,76,13,27,50),則第4趟直接選擇排序結(jié)束后的結(jié)果為。.設(shè)連通圖G中有n個頂點e條邊，則對應(yīng)的最小生成樹上有條邊。.設(shè)有一組初始記錄關(guān)鍵字序列為(50,16,23,68,94,70,73),則將它們調(diào)整成初始堆只需把16與相互交換即可。四、算法設(shè)計題(20分).設(shè)計一個在鏈式存儲結(jié)構(gòu)上統(tǒng)計二叉樹中結(jié)點個數(shù)的算法。.設(shè)計一個算法將無向圖的鄰接矩陣轉(zhuǎn)為對應(yīng)鄰接表的算法。數(shù)據(jù)結(jié)構(gòu)試卷(九)一、選擇題(30分).下列程序段的時間復(fù)雜度為()ofor(i=0；i<m；i++)for(j=0；j<t；j++)c[i][j]=0；for(i=0；i<m；i++)for(j=0：j<t；j++)for(k=0；k<n；k++)c[i][j]=c[i]lj]+a[i][k]*b[k][j]；(A)0(m*n*t) (B)O(m+n+t)(C)0(m+n*t) (D) 0(m*t+n).設(shè)順序線性表中有n個數(shù)據(jù)元素，則刪除表中第i個元素需要移動()個元素。(A)n-i (B)n+1-i(C)n-l-i(D)i.設(shè)F是由Tl、T2和T3三棵樹組成的森林，與F對應(yīng)的二叉樹為B,Tl、T2和T3的結(jié)點數(shù)分別為Nl、N2和N3,則二義樹B的根結(jié)點的左子樹的結(jié)點數(shù)為()o(A)Nl-1 (B)N2-1 (C)N2+N3 (D)N1+N3.利用直接插入排序法的思想建立一個有序線性表的時間復(fù)雜度為()。(A)0(n) (B)0(nlog2n) (C)OCn2) (D)OClog^n).設(shè)指針變量p指向雙向鏈表中結(jié)點A,指針變量s指向被插入的結(jié)點X,則在結(jié)點A的后面插入結(jié)點X的操作序列為()op->right=s：s->left=p；p->right->left=s；s->right=p->right：s->left=p；s->right=p->right；p->right=s；p->right->left=s；p->right=s；p->right->left=s；s->left=p；s->right=p->right；s->left=p；s->right=p->right；p->right->left=s；p->right=s；.下列各種排序算法中平均時間復(fù)雜度為0(一)是()。(A)快速排序(B)堆排序(C)歸并排序 (D)冒泡排序.設(shè)輸入序列1、2、3、…、n經(jīng)過棧作用后，輸出序列中的第一個元素是n,則輸出序列中的第i個輸出元素是()?(A)n-i (B)n-l-i(0n+1-i(D)不能確定.設(shè)散列表中有m個存儲單元，散列函數(shù)H(key)=key%p,則p最好選擇((A)小(A)小于等于m的最大奇數(shù)(C)小于等于m的最大偶數(shù)(B)小于等于m的最大素數(shù)(D)小于等于m的最大合數(shù).設(shè)在一棵度數(shù)為3的樹中，度數(shù)為3的結(jié)點數(shù)有2個，度數(shù)為2的結(jié)點數(shù)有1個，度數(shù)為1的結(jié)點數(shù)有2個，那么度數(shù)為0的結(jié)點數(shù)有()個。(A)4 (B)5 (C)6 (D)7.設(shè)完全無向圖中有n個頂點，則該完全無向圖中有()條邊。(A)n(n-l)/2 (B)n(n-l) (C)n(n+l)/2 (D)(n-l)/2.設(shè)順序表的長度為n,則順序查找的平均比較次數(shù)為()?(A)n (B)n/2 (0(n+l)/2 (D)(n-l)/2.設(shè)有序表中的元素為(13,18,24,35,47,50,62),則在其中利用二分法查找值為24的元素需要經(jīng)過()次比較。(A)1 (B)2 (C)3 (D)4.設(shè)順序線性表的長度為30,分成5塊，每塊6個元素，如果采用分塊查找，則其平均查找長度為()。(A)6 (B)11 (C)5 (D)6.5.設(shè)有向無環(huán)圖G中的有向邊集合E={<1,2>,<2,3>,<3,4>,<1,4>},則下列屬于該有向圖G的一種拓撲排序序列的是()?(A)1,2,3,4 (B)2,3,4,1 (C)1,4,2,3(D)1,2,4,3.設(shè)有一組初始記錄關(guān)鍵字序列為(34,76,45,18,26,54,92),則由這組記錄關(guān)鍵字生成的二叉排序樹的深度為().(A)4 (B)5 (C)6 (D)7二、填空題(30分)設(shè)指針p指向單鏈表中結(jié)點A,指針s指向被插入的結(jié)點X,則在結(jié)點A的前面插入結(jié)點X時的操作序列為：s->next=；2)p->next=s；3)t=p->data；4)p->data=；5)s->data=t；設(shè)某棵完全二叉樹中有100個結(jié)點，則該二叉樹中有個葉子結(jié)點。設(shè)某順序循環(huán)隊列中有m個元素，且規(guī)定隊頭指針F指向隊頭元素的前一個位置，隊尾指針R指向隊尾元素的當前位置，則該循環(huán)隊列中最多存儲隊列元素。對一組初始關(guān)鍵字序列(40,50,95,20,15,70,60,45,10)進行冒泡排序，則第一趟需要進行相鄰記錄的比較的次數(shù)為,在整個排序過程中最多需要進行趟排序才可以完成。在堆排序和快速排序中，如果從平均情況下排序的速度最快的角度來考慮應(yīng)最好選擇排序，如果從節(jié)省存儲空間的角度來考慮則最好選擇排序。設(shè)一組初始記錄關(guān)鍵字序列為（20,12,42,31,18,14,28）,則根據(jù)這些記錄關(guān)鍵字構(gòu)造的二叉排序樹的平均查找長度是。設(shè)一棵二叉樹的中序遍歷序列為BDCA,后序遍歷序列為DBAC,則這棵二叉樹的前序序列為。設(shè)用于通信的電文僅由8個字母組成，字母在電文中出現(xiàn)的頻率分別為7、19、2、6、32、3、21、10,根據(jù)這些頻率作為權(quán)值構(gòu)造哈夫曼樹，則這棵 4哈夫曼樹的高度為. 1&設(shè)一組記錄關(guān)鍵字序列為（80,70,33,65,24,56,48）,則814用篩選法建成的初始堆為. 68\7）設(shè)無向圖G（如右圖所示），則其最小生成樹上所有邊的權(quán)值之和為.三、判斷題（20分）.有向圖的鄰接表和逆鄰接表中表結(jié)點的個數(shù)不一定相等。（）.對鏈表進行插入和刪除操作時不必移動鏈表中結(jié)點。（）.子串“ABC”在主串“AABCABCD”中的位置為2。（）.若一個葉子結(jié)點是某二叉樹的中序遍歷序列的最后一個結(jié)點，則它必是該二叉樹的先序遍歷序列中的最后一個結(jié)點。（）.希爾排序算法的時間復(fù)雜度為0（r）。（）.用鄰接矩陣作為圖的存儲結(jié)構(gòu)時，則其所占用的存儲空間與圖中頂點數(shù)無關(guān)而與圖中邊數(shù)有關(guān)。（）.中序遍歷一棵二叉排序樹可以得到一個有序的序列。（）.入棧操作和入隊列操作在鏈式存儲結(jié)構(gòu)上實現(xiàn)時不需要考慮棧溢出的情況。（）.順序表查找指的是在順序存儲結(jié)構(gòu)上進行查找。（）.堆是完全二叉樹，完全二叉樹不一定是堆。（）五、算法設(shè)計題（20分）.設(shè)計計算二叉樹中所有結(jié)點值之和的算法。.設(shè)計將所有奇數(shù)移到所有偶數(shù)之前的算法。.設(shè)計判斷單鏈表中元素是否是遞增的算法。數(shù)據(jù)結(jié)構(gòu)試卷(十)一、選擇題(24分).下列程序段的時間復(fù)雜度為()oi=0,s=0；while(s<n){s=s+i；i++；}(A)0(n,/2) (B)0(n1/3) (C)0(n) (D)0(n2).設(shè)某鏈表中最常用的操作是在鏈表的尾部插入或刪除元素，則選用下列()存儲方式最節(jié)省運算時間。(A)單向鏈表 (B)單向循環(huán)鏈表(0雙向鏈表 (D)雙向循環(huán)鏈表.設(shè)指針q指向單鏈表中結(jié)點A,指針p指向單鏈表中結(jié)點A的后繼結(jié)點B,指針s指向被插入的結(jié)點X,則在結(jié)點A和結(jié)點B插入結(jié)點X的操作序列為().(A)s->next=p->next；p->next=-s；(B)q->next=s；s->next=p；(C)p->next=s->next；s->next=p；(D)p->next=s；s->next=q；.設(shè)輸入序列為1、2,3、4,5、6,則通過棧的作用后可以得到的輸出序列為()o(A)5,3,4,6,1,2 (B)3,2,5,6,4,1(C)3,1,2,5,4,6 (D)1,5,4,6,2,3.設(shè)有一個10階的下三角矩陣A(包括對角線)，按照從上到下、從左到右的順序存儲到連續(xù)的55個存儲單元中，每個數(shù)組元素占1個字節(jié)的存儲空間，則A[5][4]地址與A的地址之差為()。(A)10 (B)19 (C)28 (D)55.設(shè)一棵m義樹中有N1個度數(shù)為1的結(jié)點，岫個度數(shù)為2的結(jié)點，……，Nm個度數(shù)為m的結(jié)點，則該樹中共有()個葉子結(jié)點。in m tn nt(A)Z(DM⑻Z'i(C)ZM⑻l+Z(iT)M1=1 (=1 i=2 i=2.二叉排序樹中左子樹上所有結(jié)點的值均()根結(jié)點的值。(A)< (B)> (0= (D)!=.設(shè)一組權(quán)值集合W=(15,3,14,2,6,9,16,17),要求根據(jù)這些權(quán)值集合構(gòu)造一棵哈夫曼樹，則這棵哈夫曼樹的帶權(quán)路徑長度為().(A)129 (B)219 (C)189 (D)229.設(shè)有n個關(guān)鍵字具有相同的Hash函數(shù)值，則用線性探測法把這n個關(guān)鍵字映射到HASH表中需要做()次線性探測。(A)nz (B)n(n+l)(C)n(n+l)/2 (D)n(n-l)/2.設(shè)某棵二叉樹中只有度數(shù)為0和度數(shù)為2的結(jié)點且度數(shù)為0的結(jié)點數(shù)為n,則這棵二叉中共有()個結(jié)點。(A)2n (B)n+1 (C)2nT (D)2n+l.設(shè)一組初始記錄關(guān)健字的氏度為8,則最多經(jīng)過()趟插入排序可以得到有序序列。TOC\o"1-5"\h\z(A)6 (B)7 (C)8 (D)9.設(shè)一組初始記錄關(guān)健字序列為(Q,H,C,Y,P,A,M,S,R,D,F,X),則按字母升序的第一趟冒泡排序結(jié)束后的結(jié)果是()。F, H, C, D, P, A, M, Q, R, S, Y, XP, A, C, S, Q, D, F,X, R, H, M, YA, D, C, R, F, Q, M, S, Y, P, H, XH, C, Q, P, A, M,S, R, D, F, X, Y二、填空題(48分，其中最后兩小題各6分).設(shè)需要對5個不同的記錄關(guān)鍵字進行排序，則至少需要比較次，至多需要比較次。.快速排序算法的平均時間復(fù)雜度為,直接插入排序算法的平均時間復(fù)雜度為?.設(shè)二叉排序樹的高度為h,則在該樹中查找關(guān)鍵字kev最多需要比較 次。.設(shè)在長度為20的有序表中進行二分查找，則比較一次查找成功的結(jié)點數(shù)有個，比較兩次查找成功有結(jié)點數(shù)有個。.設(shè)一棵m叉樹脂的結(jié)點數(shù)為n,用多重鏈表表示其存儲結(jié)構(gòu)，則該樹中有個空指針域。.設(shè)指針變量p指向單鏈表中結(jié)點A,則刪除結(jié)點A的語句序列為：q=p->next；p->data=q->data；p->next=；feee(q)；.數(shù)據(jù)結(jié)構(gòu)從邏輯上劃分為三種基本類型： 、 和.設(shè)無向圖G中有n個頂點e條邊，則用鄰接矩陣作為圖的存儲結(jié)構(gòu)進行深度優(yōu)先或廣度優(yōu)先遍歷時的時間復(fù)雜度為 ；用鄰接表作為圖的存儲結(jié)構(gòu)進行深度優(yōu)先或廣度優(yōu)先遍歷的時間復(fù)雜度為..設(shè)散列表的長度為8,散列函數(shù)H(k)=k/7,用線性探測法解決沖突，則根據(jù)一組初始關(guān)鍵字序列(8,15,16,22,30,32)構(gòu)造出的散列表的平均查找長度是。.設(shè)一組初始關(guān)健字序列為(38,65,97,76,13,27,10),則第3趟冒泡排序結(jié)束后的結(jié)果為..設(shè)一組初始關(guān)犍字序列為(38,65,97,76,13,27,10),則第3趟簡單選擇排序后的結(jié)果為..設(shè)有向圖G中的有向邊的集合E={<1,2>,<2,3>,<1,4>,<4,5>,<5,3>,<4,6>,<6,5>}(則該圖的一個拓撲序列為..下面程序段的功能是建立二叉樹的算法，請在下劃線處填上正確的內(nèi)容。typedefstructnode{intdata;structnode*lchild;;}bitree;voidcreatebitree(bitree*&bt)(scanf("%c”,&ch);if(ch==*#');else{bt=(bitree*)malloc(sizeof(bitree));bt->data=ch;;createbitree(bt->rchild);}I.下面程序段的功能是利用從尾部插入的方法建立單鏈表的算法，請在下劃線處填上正確的內(nèi)容。typedefstructnode{intdata;structnode*next;}Iklist;voidlklistcreate(*&head)(for(i=l;i<=n;i++){p=(lklist*)malloc(sizeof(lklist));scanfCi%d,\&(p->data));p->next=0;if(i==l)head=q=p;else{q->next=p;;}三、算法設(shè)計題(22分).設(shè)計在鏈式存儲結(jié)構(gòu)上合并排序的算法。.設(shè)計在二叉排序樹上查找結(jié)點X的算法。.設(shè)關(guān)鍵字序列(k“kz,…，ki)是堆，設(shè)計算法將關(guān)鍵字序列(k“kz,…，*,x)調(diào)整為堆。數(shù)據(jù)結(jié)構(gòu)試卷(一)參考答案一、選擇題(每題2分，共20分)TOC\o"1-5"\h\zA2.D3.D4.C5.C6.D7.D 8.C 9.D 10.A二、填空題(每空1分，共26分)正確性易讀性強壯性高效率0(n)9 3 3-1 34X*+2Y*3/-2nn-1 n+1e2e有向無回路n(n-1)/2 n(n-1)(12,40) () (74) (23,55,63)增加1O(logm)O(nlogm)12.歸并三、計算題(每題6分，共24分)1.線性表為：(78,50,40,60,34,90)2.鄰接矩陣:2.鄰接矩陣:0111010101110111010101110鄰接表如圖鄰接表如圖11所示:..用克魯斯卡爾算法得到的最小生成樹為：(1,2)3,(4,6)4,(1,3)5,(1,4)8,(2,5)10,(4,7)20.見圖12四、讀算法(每題四、讀算法(每題7分，共14分).(1)查詢鏈表的尾結(jié)點(2)將第一個結(jié)點鏈接到鏈表的尾部，作為新的尾結(jié)點(3)返回的線性表為(a2,a3」”,an,ai).遞歸地后序遍歷鏈式存儲的二叉樹。五、法填空(每空2分，共8分)trueBST->leftBST->righttrueBST->leftBST->right六、編寫算法(8分)intCountX(LNode*HL,ElemTypex){inti=0;LNode*p=HL，i為計數(shù)器while(p!=NULL){if(P->data==x)i++;p=p->next;}//while,出循環(huán)時i中的值即為x結(jié)點個數(shù)returni;}//CountX數(shù)據(jù)結(jié)構(gòu)試卷（二）參考答案一、選擇題D 2.B3.C 4.A5.A6.C7.B8.C二、填空題構(gòu)造一個好的HASH函數(shù)，確定解決沖突的方法stack.top++>stack.s[stack.top]=x有序0(1?),0(nlog2n)No-1,2N0+Md/2(31,38,54,56,75,80,55,63)(1,3,4,5,2),(1,3,2,4,5)三、應(yīng)用題(22,40,45,48,80,78),(40,45,48,80,22,78)q->llink=p;q->rlink=p->rlink;p->rlink->llink=q;p->rlink=q;2,ASL=91*l+2*2+3*4+4*2)=25/9樹的鏈式存儲結(jié)構(gòu)略，二叉樹略E={(1,3),(1,2),(3,5),(5,6),(6,4))略四、算法設(shè)計題設(shè)有一組初始記錄關(guān)鍵字序列(絡(luò)，…，K?),要求設(shè)計一個算法能夠在0(n)的時間復(fù)雜度內(nèi)將線性表劃分成兩部分，其中左半部分的每個關(guān)鍵字均小于K”右半部分的每個關(guān)鍵字均大于等于K,。voidquickpass(intr[],ints,intt)(inti=s,j=t,x=r[s];while(i<j){while(i<j&&r|j]>x)j=j-1;if(i<j){r[i]=r[j]；i=i+l；)while(i<j&&r[i]<x)i=i+l;if(i<j){r[j|=r[i];j=j-l;})r[i]=x;)設(shè)有兩個集合A和集合B,要求設(shè)計生成集合C=ACB的算法，其中集合A、B和C用鏈式存儲結(jié)構(gòu)表示。typedefstructnode{intdata;structnode*next;)lklist;voidintersection(lklist*ha,lklist*hb,lklist*&hc)(Iklist*p,*q,*t;for(p=ha,hc=0;p!=0;p=p->next){for(q=hb;q!=0;q=q->next)if(q->data==p->data)break;if(q!=O){t=(lklist*)malloc(sizeof(Iklist));t->data=p->data;t->next=hc;hc=t;}一、選擇題1.B 2.B 3.A 4.A 5.A6.B 7.D 8.C 9.B 10.D第3小題分析：首先用指針變量q指向結(jié)點A的后繼結(jié)點B,然后將結(jié)點B的值復(fù)制到結(jié)點A中，最后刪除結(jié)點B。第9小題分析：9快速排序、歸并排序和插入排序必須等到整個排序結(jié)束后才能夠求出最小的10個數(shù)，而堆排序只需要在初始堆的基礎(chǔ)上再進行10次篩選即可，每次篩選的時間復(fù)雜度為Odogzn）。二、填空題順序存儲結(jié)構(gòu)、鏈式存儲結(jié)構(gòu)9,5015出度，入度0e=d中序70(1)i/2,2i+l(5,16,71,23,72,94,73)(1,4,3,2)j+1,hashtable[j].key==kreturn(t),t=t->rchild2、H(36)=36mod7=1;2、H(36)=36mod7=1;(22)=(1+1)mod7=2;….沖突H(15)=15mod7=1;…?沖突H2(22)=(2+l)mod7=3;第8小題分析：二分查找的過程可以用一棵二叉樹來描述，該二叉樹稱為二叉判定樹。在有序表上進行二分查找時的查找長度不超過二叉判定樹的高度l+log2n。NULLkHi(15)=(l+l)mod7=2;H(40)=40mod7=5;H(63)=63mod7=0;H(22)=22mod7=1;????沖突3、(8,9,4,3,6,1),10,(12,18418)(1,6,4,3),8,(9),10,12,08,18)1,(3,4,6),8,9,10,12,18,(18)1,3,(4,6),8,9,10,12,18,181,3,4,6,8,9,10,12,18,18四、算法設(shè)計題

.設(shè)計在單鏈表中刪除值相同的多余結(jié)點的算法。typedefintdatatype;typedefstructnode{datatypedata;structnode*next;}lklist;voiddelredundant(lklist*&head)(Iklist*p,*q,*s;for(p=head;p!=0;p=p->next)(fbr(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;})).設(shè)計一個求結(jié)點x在二叉樹中的雙親結(jié)點算法。typedefstructnode{datatypedata;structnode*lchild,*rchild;}bitree;bitree*q[20];inti^O,f=O,flag=O;voidpreorder(bitree*bt,charx)(if(bt!=O&&flag==O)if(bt->data=x){flag=l;return;}else{r=(r+l)%20;q[r]=bt;preorder(bt->lchild,x);preorder(bt->rchild,x)；))voidparent(bitree*bt,charx)(inti;preor