【文章內(nèi)容簡介】 雙向循環(huán)鏈表3．設(shè)指針q指向單鏈表中結(jié)點(diǎn)A，指針p指向單鏈表中結(jié)點(diǎn)A的后繼結(jié)點(diǎn)B，指針s指向被插入的結(jié)點(diǎn)X，則在結(jié)點(diǎn)A和結(jié)點(diǎn)B插入結(jié)點(diǎn)X的操作序列為（ ）。(A) snext=pnext；pnext=s； (B) qnext=s； snext=p；(C) pnext=snext；snext=p； (D) pnext=s；snext=q；4．設(shè)輸入序列為6，則通過棧的作用后可以得到的輸出序列為（ ）。(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，35．設(shè)有一個(gè)10階的下三角矩陣A（包括對角線），按照從上到下、從左到右的順序存儲到連續(xù)的55個(gè)存儲單元中，每個(gè)數(shù)組元素占1個(gè)字節(jié)的存儲空間，則A[5][4]地址與A[0][0]的地址之差為（ ）。 (A) 10 (B) 19 (C) 28 (D) 556．設(shè)一棵m叉樹中有N1個(gè)度數(shù)為1的結(jié)點(diǎn)，N2個(gè)度數(shù)為2的結(jié)點(diǎn)，……，Nm個(gè)度數(shù)為m的結(jié)點(diǎn)，則該樹中共有（ ）個(gè)葉子結(jié)點(diǎn)。 (A) (B) (C) (D) 7. 二叉排序樹中左子樹上所有結(jié)點(diǎn)的值均（ ）根結(jié)點(diǎn)的值。 (A) (B) (C) = (D) !=8. 設(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) 2299. 設(shè)有n個(gè)關(guān)鍵字具有相同的Hash函數(shù)值，則用線性探測法把這n個(gè)關(guān)鍵字映射到HASH表中需要做（ ）次線性探測。 (A) n2 (B) n(n+1) (C) n(n+1)/2 (D) n(n1)/2，則這棵二叉中共有（ ）個(gè)結(jié)點(diǎn)。 (A) 2n (B) n+l (C) 2n1 (D) 2n+l ，則最多經(jīng)過（ ）趟插入排序可以得到有序序列。 (A) 6 (B) 7 (C) 8 (D) 9(Q，H，C，Y，P，A，M，S，R，D，F(xiàn)，X)，則按字母升序的第一趟冒泡排序結(jié)束后的結(jié)果是（ ）。(A) F，H，C，D，P，A，M，Q，R，S，Y，X(B) P，A，C，S，Q，D，F(xiàn)，X，R，H，M，Y(C) A，D，C，R，F(xiàn)，Q，M，S，Y，P，H，X(D) H，C，Q，P，A，M，S，R，D，F(xiàn)，X，Y二、填空題(48分，其中最后兩小題各6分)1. 1. 設(shè)需要對5個(gè)不同的記錄關(guān)鍵字進(jìn)行排序，則至少需要比較_____________次，至多需要比較_____________次。2. 2. 快速排序算法的平均時(shí)間復(fù)雜度為____________，直接插入排序算法的平均時(shí)間復(fù)雜度為___________。3. 3. 設(shè)二叉排序樹的高度為h，則在該樹中查找關(guān)鍵字key最多需要比較_________次。4. 4. 設(shè)在長度為20的有序表中進(jìn)行二分查找，則比較一次查找成功的結(jié)點(diǎn)數(shù)有_________個(gè)，比較兩次查找成功有結(jié)點(diǎn)數(shù)有_________個(gè)。5. 5. 設(shè)一棵m叉樹脂的結(jié)點(diǎn)數(shù)為n，用多重鏈表表示其存儲結(jié)構(gòu)，則該樹中有_________個(gè)空指針域。6. 6. 設(shè)指針變量p指向單鏈表中結(jié)點(diǎn)A，則刪除結(jié)點(diǎn)A的語句序列為：q=pnext；pdata=qdata；pnext=___________；feee(q)；7. 7. 數(shù)據(jù)結(jié)構(gòu)從邏輯上劃分為三種基本類型：___________、__________和___________。8. 8. 設(shè)無向圖G中有n個(gè)頂點(diǎn)e條邊，則用鄰接矩陣作為圖的存儲結(jié)構(gòu)進(jìn)行深度優(yōu)先或廣度優(yōu)先遍歷時(shí)的時(shí)間復(fù)雜度為_________；用鄰接表作為圖的存儲結(jié)構(gòu)進(jìn)行深度優(yōu)先或廣度優(yōu)先遍歷的時(shí)間復(fù)雜度為_________。9. 9. 設(shè)散列表的長度為8，散列函數(shù)H(k)=k % 7，用線性探測法解決沖突，則根據(jù)一組初始關(guān)鍵字序列(8，15，16，22，30，32)構(gòu)造出的散列表的平均查找長度是________。10. 10. 設(shè)一組初始關(guān)鍵字序列為(38，65，97，76，13，27，10)，則第3趟冒泡排序結(jié)束后的結(jié)果為_____________________。11. 11. 設(shè)一組初始關(guān)鍵字序列為(38，65，97，76，13，27，10)，則第3趟簡單選擇排序后的結(jié)果為______________________。12. 12. 設(shè)有向圖G中的有向邊的集合E={1，2，2，3，1，4，4，5，5，3，4，6，6，5}，則該圖的一個(gè)拓?fù)湫蛄袨開________________________。13. 13. 下面程序段的功能是建立二叉樹的算法，請?jiān)谙聞澗€處填上正確的內(nèi)容。typedef struct node{int data。struct node *lchild。________________。}bitree。void createbitree(bitree *amp。bt){scanf(“%c”,amp。ch)。if(ch==39。39。) ___________。else{ bt=(bitree*)malloc(sizeof(bitree))。 btdata=ch。 ________。createbitree(btrchild)。}}14. 14. 下面程序段的功能是利用從尾部插入的方法建立單鏈表的算法，請?jiān)谙聞澗€處填上正確的內(nèi)容。typedef struct node {int data。 struct node *next。} lklist。 void lklistcreate(_____________ *amp。head ){ for (i=1。i=n。i++){ p=(lklist *)malloc(sizeof(lklist))。scanf(“%d”,amp。(pdata))。pnext=0。if(i==1)head=q=p。else {qnext=p。____________。}} }三、算法設(shè)計(jì)題(22分)1． 1． 設(shè)計(jì)在鏈?zhǔn)酱鎯Y(jié)構(gòu)上合并排序的算法。2． 2． 設(shè)計(jì)在二叉排序樹上查找結(jié)點(diǎn)X的算法。3． 3． 設(shè)關(guān)鍵字序列(k1，k2，…，kn1)是堆，設(shè)計(jì)算法將關(guān)鍵字序列(k1，k2，…，kn1，x)調(diào)整為堆。數(shù)據(jù)結(jié)構(gòu)試卷（14）參考答案一、選擇題1．A 2．D 3．B 4．B 5．B 6．D7．A 8．D 9．D 10．C 11．B 12．D二、填空題1. 1. 4，102. 2. O(nlog2n)，O(n2)3. 3. n4. 4. 1，25. 5. n(m1)+16. 6. qnext7. 7. 線性結(jié)構(gòu)，樹型結(jié)構(gòu)，圖型結(jié)構(gòu)8. 8. O(n2)， O(n+e)9. 9. 8/310. 10. (38，13，27，10，65，76，97)11. 11. (10，13，27，76，65，97，38)12. 12. 12465313. 13. struct node *rchild，bt=0，createbitree(btlchild)14. 14. lklist，q=p三、算法設(shè)計(jì)題1. 1. 設(shè)計(jì)在鏈?zhǔn)酱鎯Y(jié)構(gòu)上合并排序的算法。void mergelklist(lklist *ha,lklist *hb,lklist *amp。hc){ lklist *s=hc=0。 while(ha!=0 amp。amp。 hb!=0) if(hadatahbdata){if(s==0) hc=s=ha。 else {snext=ha。 s=ha。}。ha=hanext。} else {if(s==0) hc=s=hb。 else {snext=hb。 s=hb。}。hb=hbnext。} if(ha==0) snext=hb。 else snext=ha。}2. 2. 設(shè)計(jì)在二叉排序樹上查找結(jié)點(diǎn)X的算法。bitree *bstsearch1(bitree *t, int key){ bitree *p=t。 while(p!=0) if (pkey==key) return(p)。else if (pkeykey)p=plchild。 else p=prchild。 return(0)。}3. 3. 設(shè)關(guān)鍵字序列(k1，k2，…，kn1)是堆，設(shè)計(jì)算法將關(guān)鍵字序列(k1，k2，…，kn1，x)調(diào)整為堆。void adjustheap(int r[ ],int n){ int j=n,i=j/2,temp=r[j1]。 while (i=1) if (temp=r[i1])break。 else{r[j1]=r[i1]。 j=i。 i=i/2。} r[j1]=temp。}數(shù)據(jù)結(jié)構(gòu)（十五）一、 單選題（每題 2 分，共20分）1. 1. 對一個(gè)算法的評價(jià)，不包括如下（B ）方面的內(nèi)容。 A．健壯性和可讀性 B．并行性 C．正確性 D．時(shí)空復(fù)雜度2. 2. 在帶有頭結(jié)點(diǎn)的單鏈表HL中，要向表頭插入一個(gè)由指針p指向的結(jié)點(diǎn)，則執(zhí)行( )。 A. pnext=HLnext。 HLnext=p。 B. pnext=HL。 HL=p。 C. pnext=HL。 p=HL。 D. HL=p。 pnext=HL。3. 3. 對線性表，在下列哪種情況下應(yīng)當(dāng)采用鏈表表示？( ) 4. 4. 一個(gè)棧的輸入序列為1 2 3，則下列序列中不可能是棧的輸出序列的是( C ) A. 2 3 1 B. 3 2 1 C. 3 1 2 D. 1 2 35. 5. AOV網(wǎng)是一種（ ）。 A．有向圖 B．無向圖 C．無向無環(huán)圖 D．有向無環(huán)圖6. 6. 采用開放定址法處理散列表的沖突時(shí)，其平均查找長度（ ）。A．低于鏈接法處理沖突 B. 高于鏈接法處理沖突 C．與鏈接法處理沖突相同 D．高于二分查找7. 7. 若需要利用形參直接訪問實(shí)參時(shí)，應(yīng)將形參變量說明為（ ）參數(shù)。A．值 B．函數(shù) C．指針 D．引用8. 8. 在稀疏矩陣的帶行指針向量的鏈接存儲中，每個(gè)單鏈表中的結(jié)點(diǎn)都具有相同的（ ）。A．行號 B．列號 C．元素值 D．非零元素個(gè)數(shù)9. 9. 快速排序在最壞情況下的時(shí)間復(fù)雜度為（ ）。A．O(log2n) B．O(nlog2n) C．0(n) D．0(n2)10. 10. 從二叉搜索樹中查找一個(gè)元素時(shí)，其時(shí)間復(fù)雜度大致為( )。 A. O(n) B. O(1) C. O(log2n) D. O(n2)二、 二、 運(yùn)算題（每題 6 分，共24分）1. 1. 數(shù)據(jù)結(jié)構(gòu)是指數(shù)據(jù)及其相互之間的______________。當(dāng)結(jié)點(diǎn)之間存在M對N（M：N）的聯(lián)系時(shí)，稱這種結(jié)構(gòu)為_____________________。2. 2. 隊(duì)列的插入操作是在隊(duì)列的___尾______進(jìn)行，刪除操作是在隊(duì)列的____首______進(jìn)行。3. 3. 當(dāng)用長度為N的數(shù)組順序存儲一個(gè)棧時(shí)，假定用top==N表示棧空，則表示棧滿的條件是___top==0___(要超出才為滿)_______________。4. 4. 對于一個(gè)長度為n的單鏈存儲的線性表，在表頭插入元素的時(shí)間復(fù)雜度為_________，在表尾插入元素的時(shí)間復(fù)雜度為____________。5. 5. 設(shè)W為一個(gè)二維數(shù)組，其每個(gè)數(shù)據(jù)元素占用4個(gè)字節(jié)，行下標(biāo)i從0到7 ，列下標(biāo)j從0到3 ，則二維數(shù)組W的數(shù)據(jù)元素共占用＿_(dá)____＿個(gè)字節(jié)。W中第6 行的元素和第4 列的元素共占用＿_(dá)______＿個(gè)字節(jié)。若按行順序存放二維數(shù)組W，其起始地址為100，則二維數(shù)組元素W[6，3]的起始地址為＿_(dá)_______＿。6. 6. 廣義表A= (a,(a,b),((a,b),c)),則它的深度為____________，它的長度為____________。7. 7. 二叉樹是指度為2的____________________樹。一棵結(jié)點(diǎn)數(shù)為N的二叉樹，其所有結(jié)點(diǎn)的度的總和是_____________。8. 8. 對一棵二叉搜索樹進(jìn)行中序遍歷時(shí)，得到的結(jié)點(diǎn)序列是一個(gè)______________。對一棵由算術(shù)表達(dá)式組成的二叉語法樹進(jìn)行后序遍歷得到的結(jié)點(diǎn)序列是該算術(shù)表達(dá)式的__________________。9. 9. 對于一棵具有n個(gè)結(jié)點(diǎn)的二叉樹，用二叉鏈表存儲時(shí)，其指針總數(shù)為_____________個(gè)，其中_______________個(gè)用于指向孩子，___________