【正文】 2] 3．設(shè)一條單鏈表的頭指針變量為head且該鏈表沒有頭結(jié)點，則其判空條件是（）。else low=mid+1。} if(exchange==0)return； } } ，請在下劃線處填上正確的語句。，則A中第i行中所有非零元素個數(shù)之和等于頂點i的________，第i列中所有非零元素個數(shù)之和等于頂點i的__________。(A)abedfc(B)acfebd(C)aebdfc(D)aedfcb 9．設(shè)輸入序列是……、n，經(jīng)過棧的作用后輸出序列的第一個元素是n，則輸出序列中第i個輸出元素是（）。prlinkllink=prlink ，51 ，(RF+M)%M +1i，ni .(19，18，16，20，30，22).(16，18，19，20，32，22)[i][j]=1 [i]=0，hashtable[k]=s數(shù)據(jù)結(jié)構(gòu)試卷（五）一、選擇題(30分)1．?dāng)?shù)據(jù)的最小單位是（）。void createlkhash(lklist *hashtable[ ]){ int i,k。11．11．設(shè)某無向圖G中有n個頂點，用鄰接矩陣A作為該圖的存儲結(jié)構(gòu)，則頂點i和頂點j互為鄰接點的條件是______________________。3． 3． 根據(jù)初始關(guān)鍵字序列(19，22，01，38，10)建立的二叉排序樹的高度為____________。(A)O(1)(B)O(n)(C)O(log2n)(D)O(n2)5．設(shè)某有向圖的鄰接表中有n個表頭結(jié)點和m個表結(jié)點，則該圖中有（）條有向邊。}數(shù)據(jù)結(jié)構(gòu)試卷（三）參考答案一、選擇題 第3小題分析：首先用指針變量q指向結(jié)點A的后繼結(jié)點B，然后將結(jié)點B的值復(fù)制到結(jié)點A中，最后刪除結(jié)點B。typedef struct node{int key。j=i=k % p。，如果按照從自上到下、從左到右從1開始順序編號，則第i個結(jié)點的雙親結(jié)點編號為____________，右孩子結(jié)點的編號為___________。，則該二叉樹的深度為__________；若用二叉鏈表作為該完全二叉樹的存儲結(jié)構(gòu)，則共有___________個空指針域。(A)線性結(jié)構(gòu)(B)樹型結(jié)構(gòu)(C)物理結(jié)構(gòu)(D)圖型結(jié)構(gòu) 2．下面程序的時間復(fù)雜為（）for（i=1，s=0； i(A)q=pnext；pdata=qdata；pnext=qnext；free(q)；(B)q=pnext；qdata=pdata；pnext=qnext；free(q)；(C)q=pnext；pnext=qnext；free(q)；(D)q=pnext；pdata=qdata；free(q)；4．設(shè)有n個待排序的記錄關(guān)鍵字，則在堆排序中需要（）個輔助記錄單元。4． 4． 設(shè)一棵樹T中邊的集合為{(A，B)，(A，C)，(A，D)，(B，E)，(C，F(xiàn))，(C，G)}，要求用孩子兄弟表示法（二叉鏈表）表示出該樹的存儲結(jié)構(gòu)并將該樹轉(zhuǎn)化成對應(yīng)的二叉樹。平均時間復(fù)雜度為__________。typedef struct {int s[100]。(A)2m1(B)2m(C)2m+1(D)4m 3．設(shè)順序循環(huán)隊列Q[0：M1]的頭指針和尾指針分別為F和R，頭指針F總是指向隊頭元素的前一位置，尾指針R總是指向隊尾元素的當(dāng)前位置，則該循環(huán)隊列中的元素個數(shù)為（）。：（1）重點污染防治區(qū)，指對地下水環(huán)境有污染的物料或污染物泄漏后，不能發(fā)現(xiàn)和處理的區(qū)域或部位，為隱蔽工程區(qū)。另外，改擴(kuò)建及異地搬遷項目需說明現(xiàn)有工程固體廢物特別是危險廢物的處置措施情況、存在的環(huán)境保護(hù)問題及擬采取的整改措施等內(nèi)容。黨的十八屆三中全會明確指出，全面深化改革的總目標(biāo)是：完善和發(fā)展中國特色社會主義制度，推進(jìn)國家治理體系和治理能力現(xiàn)代化。必須(ABCD)。A、解放市場 B、解放思想 C、解放和發(fā)展社會生產(chǎn)力 D、解放和增強(qiáng)社會活力十八屆三中全會通過的《中共中央關(guān)于全面深化改革若干重大問題的決定》指出全面深化改革的總目標(biāo)是(C D)。A、堅持創(chuàng)新B、堅持發(fā)展C、堅持改革D、堅持開放 2013年11月12日，中共十八屆三中全會通過的《中共中央關(guān)于全面深化改革若干重大問題的決定》指出全面深化改革的重點是（B）。j: 0..n。Count 初值為0 ProcedureCount_node(t: pointer。quicksort(R,s,i1)。repeatwhile(R〔i〕.key＞=)and(i＜j＝doj:=j1。VAR X:node。進(jìn)入算法時,二叉樹已用二叉鏈表存儲,t指向根結(jié)點,count初值為 0 Procedure node_Count(t: pointer。t↑.lchild←t↑.rchild。c=(n+1)檢索次數(shù)平均查找長度為：1/12（1+2*2+3*4+4*5）=37/12六、得到:深度遍歷結(jié)果為：1，2，3，5，4，6，7，8Y=0Low≤HighLow：=Mid+1High：=Mid1VARR：table。Binfind:=y。WHILE t(a ij)n * n的上三角元素逐行存放于數(shù)組 B[1..m]中(m 充分大),使得 B[k]=a ij ,且 k=f 1(i)+f 2(j)+C,試推導(dǎo)出函數(shù) f 1(i), f 2(j)和常數(shù) C,要求 f 1(i)和 f 2(j){Jan,Feb,Mar,Apr,May,Jun,Jul,Aug,Sep,Oct,Nov,Dec},按字母序號排號序為{Apr,Aug,Dec,Feb,Jan,Jul,Jun,Mar,May,Nov,Oct,Sep},然后用二分發(fā)進(jìn)行檢索,．綜合題（5+5+8+10+8）．對于下圖給出其鄰接表,并從頂點 1 出發(fā)依據(jù)存儲結(jié)構(gòu)進(jìn)行深度遍歷,．程序填空:在橫線處填入適當(dāng)?shù)膬?nèi)容,:在有序表中用二分檢索法查找關(guān)鍵碼為 K的記錄,若找到則返回其位置, :TYPE node=RECORDKey: integer。key:integer。四、簡答題（第 2 題每小題 6 分，第 5 題每小題 8 分，共 36 分）1．已知一個無向圖的頂點集為{a, b, c, d, e} ,其鄰接矩陣如下圖 1 所示(1)畫出該圖的圖形；（2）根據(jù)鄰接矩陣從頂點 a出發(fā)進(jìn)行深度優(yōu)先遍歷和廣度優(yōu)先遍歷,寫出相應(yīng)的遍歷序列。（）三、填空題（每空 1 分，共 15分）1．用起泡法對 n 個關(guān)鍵碼排序，在最好情況下，只需做__次比較和 _______次移動； 在最壞的情況下要做___ _ _ _次比較。（）。2．（1）堆是 n個元素的有限序列 K1，K2，? , KN，且滿足以下條件: Ki 1I=1,2,?, n/2（最小堆）或Ki = K2i 且Ki = K2i+1I=1,2,?, n/2（最大堆）（2）因為完全二叉樹采用順序存儲更加有效，所以堆應(yīng)采用順序存儲結(jié)構(gòu)。（），所有同義詞在表中相鄰。（）2．有向圖的鄰接表和逆鄰接表中的結(jié)點數(shù)一定相同。，堆頂結(jié)點的值是所有結(jié)點中的_________，在一個大根堆中，堆頂結(jié)點的值是所有結(jié)點中的_________。（）[A] acbed[B] decab[C] deabc[D] cedba 。（）[A] n[B] n/2[C](n+1)/2[D](n1)/23．設(shè)每個字符占一個字節(jié)，二維數(shù)組 A中每個元素有6個字符組成，其行下標(biāo)從0到9，列下標(biāo)從0到3，元素_____當(dāng)A按行優(yōu)先存儲起始地址與當(dāng)A按列優(yōu)先存儲的起始地址相同。()[A] K1[B] K[C] K+1[D] K（K+1）/22二、填空題（每小題2分，共20分）1．對于一個長度為n的順序存儲的線性表，在表頭插入元素的時間復(fù)雜度為______，在表尾插入元素的時間復(fù)雜度為________。9．快速排序在平均情況下的空間復(fù)雜度為_____，在最壞情況下的空間復(fù)雜度為_____。（），所以二叉樹是一種特殊的樹。數(shù)據(jù)結(jié)構(gòu)試題6答案一、 二、1．O（n）O（1）2．163．2 h 一 h 一14．最小值 最大值5．n一16．O（n 2）O（n十e）、7．順序 有序8．開放定址法 鏈接法（次序無先后）9．O（1og2n）O（n）10．9三、2.√ 5.√8.√四、1．區(qū)別：數(shù)組占用連續(xù)的內(nèi)存空間，鏈表不要求結(jié)點的空間連續(xù)。，只有直接插入排序、冒泡排序、直接選擇排序易于在鏈表上實現(xiàn)。（） 樹的任何子樹都是 AVL樹。6．在一個帶頭結(jié)點的單循環(huán)鏈表中，p 指向尾結(jié)點的直接前驅(qū)，則指向頭結(jié)點的指針 head可用 p 表示為 head=_______。5．從一棵空的 AVL 樹開始，將關(guān)鍵碼 xal,wan,wil,zol,yo,xum 逐個插入，畫出每插入一 個關(guān)鍵碼后得到的 AVL 樹。FOR i:=1 TO n DO Begin flag:=0。BEGINLow:=1。數(shù)據(jù)結(jié)構(gòu)試題8答案一、ADBCBADCBB1B1B1B1A1A二、初等，組合存儲密度散列函數(shù)的選取，沖突（碰撞）的解決樹（森）林按關(guān)鍵碼排序 1/2Σdi生成樹林相對位置三、B C EB CA B C D四、快速排序是不穩(wěn)定的如對初始類排序碼：81 2 5 82 4 1經(jīng)第一趟快排后為：〔1 2 5 82 4〕81經(jīng)第二趟快排后為： 1 〔2 5 82 4〕81經(jīng)第三趟快排后為： 1 2 〔5 82 4〕81經(jīng)第四趟快排后為： 1 2 4 5 8281和 82 相對位置發(fā)生了變化由于有了線索的存在而使的周游樹形結(jié)構(gòu)和找結(jié)點在指定次序下的前驅(qū)、后繼的算法變得很簡單、直截了當(dāng)。R〔j〕← R〔j1〕。數(shù)據(jù)結(jié)構(gòu)試題9 (每小題 1 分,15 分):（） 個要素 個要素 個要素 個要素,刪除節(jié)點 P之后的節(jié)點 Q 需要修改的指針域的個數(shù)為:（） :（） 表 SUBSTR(‘ABCDEF’,2,3)的引用結(jié)果是:（）A． ‘BCD’ B.‘BC’ C.‘CDE’ D.‘CD’ SQ有 m 個單元,其滿隊條件是:（）= MOD M+1= +1= = MOD M+1 A 4 * 4 的上三角元素 A(3,2)的位置是第:（） 個 個 個 個 D=(a,D)的深度為:（）C.+D.– A,B,C 可以構(gòu)成多少種二叉樹:（） n 個節(jié)點的完全二叉樹,其深度為:（）:（） n 個結(jié)點,e 條邊,則它的鄰接表需要表節(jié)點數(shù)目為:（）+1(KRUSKAL)算法求最小生成樹,是針對那種圖的:（） ,使用輔助空間為 O（n）的算法是:（） ,同義詞是指:（）≠ 且 HASH()=HASH()== 且 HASH()=HASH()= 文件屬于:（） (錯選,多選, 1 分,共 5 分),涉及到棧運算的有:（） ,算法的時間復(fù)雜度是 O(n 2)的有:（） :（） ,可以將排序分為:() :（） (每空1 分,共10 分),________,_________, : :(對的打”√”,錯的打”╳”, 2 分,判斷和說明各得 1 分,判斷3 錯誤, 10分) 2 的樹.（）,其時間復(fù)雜度為 O(n log 2 n).（）,限制在于節(jié)點的位置相對固定.（）.（）,則一般唯一.（）(每小題 3 分,共 9 分) (共 31分),并畫出主要轉(zhuǎn)化過程圖示.(4 分) W={2,3,4,7,8},試構(gòu)造關(guān)于 W 的一棵哈夫曼樹,并求其加權(quán)路徑長度 WPL 的 值.(6 分),并從頂點 1 出發(fā)依據(jù)存儲結(jié)構(gòu)進(jìn)行廣度遍歷, ABCDEF,中序序列為 BCAEDF,畫出此二叉樹的示意圖,并給 出其后序序列的線索樹.(6 分){51,28,36,86,7},請建立一個堆,要求畫出堆形成的示意圖.(6 分),現(xiàn)在要在節(jié)點P之后插入一個節(jié)點Q,請寫出插入動作的具體語句.(4分)（共20 分） A[1..m]作為循環(huán)隊列的存儲區(qū)域,試編寫一個出隊的類 PASCAL 語言算法.(6 分)2．利用類 pascal 語言寫出統(tǒng)計二叉樹中節(jié)點個數(shù)的算法（6 分）.3．利用類 pascal 語言寫出快速排序中一趟塊排的算法（8 分）.數(shù)據(jù)結(jié)構(gòu)試題9答案一、CBDADBCDAD1A1D1B1A1C二、A C DA BA C D ED EB C三、順序,鏈接,索引,散列相對位置指令必須有確切含義,無歧義性開地址法,拉鏈法修改,檢索四、√五、三元組表 P244拓?fù)渑判?P229AVL樹 P180六、鄰接表存儲表示同 A 卷六、2 廣度遍歷結(jié)果:1, 2, 6, 3, 4, 7, 8, 5后序:C B E F D A q↑.llink←pq↑.rlink←p↑.rlink p↑.rlink↑.llink←q p↑.rlink←q七、算法設(shè)計(6+6+8=20′)R=Fthenprint(‘underflow’)elseF←F MOD m+1算法結(jié)束TYPEpointer=↑nodenode=RECORD info: datatype。TYPE node=RECORD Key: integer。begini:=l。j:=j1〕 until i=j