【正文】 able[ ],int k){int i,j。 else_____________。 (A) log2n+1 (B) log2n1 (C) log2n (D) log2(n+1)二、填空題(每空1分共 20分)1． 設(shè)有n個(gè)無(wú)序的記錄關(guān)鍵字，則直接插入排序的時(shí)間復(fù)雜度為_(kāi)_______，快速排序的平均時(shí)間復(fù)雜度為_(kāi)________。 struct node *next。四、算法設(shè)計(jì)題(每題10分，共30分)1． 設(shè)單鏈表中有僅三類(lèi)字符的數(shù)據(jù)元素(大寫(xiě)字母、數(shù)字和其它字符)，要求利用原單鏈表中結(jié)點(diǎn)空間設(shè)計(jì)出三個(gè)單鏈表的算法，使每個(gè)單鏈表只包含同類(lèi)字符。4. 棧的插入和刪除只能在棧的棧頂進(jìn)行，后進(jìn)棧的元素必定先出棧，所以又把棧稱(chēng)為_(kāi)_________表；隊(duì)列的插入和刪除運(yùn)算分別在隊(duì)列的兩端進(jìn)行，先進(jìn)隊(duì)列的元素必定先出隊(duì)列，所以又把隊(duì)列稱(chēng)為_(kāi)________表。 int others。 (A) [41，12，34，45，27] 55 [72，63] (B) [45，34，12，41] 55 [72，63，27] (C) [63，12，34，45，27] 55 [41，72] (D) [12，27，45，41] 55 [34，63，72]3．設(shè)一條單鏈表的頭指針變量為head且該鏈表沒(méi)有頭結(jié)點(diǎn)，則其判空條件是（ ）。（ ）4．滿二叉樹(shù)一定是完全二叉樹(shù)，完全二叉樹(shù)不一定是滿二叉樹(shù)。 (D) top=topnext。6. 高度為h的完全二叉樹(shù)中最少有________個(gè)結(jié)點(diǎn)，最多有________個(gè)結(jié)點(diǎn)。i=i+1。 (A) aedfcb (B) acfebd (C) aebcfd (D) aedfbc10. 隊(duì)列是一種（ ）的線性表。}bitree。四、算法設(shè)計(jì)題(20分)1. 設(shè)計(jì)一個(gè)在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上統(tǒng)計(jì)二叉樹(shù)中結(jié)點(diǎn)個(gè)數(shù)的算法。 (A) 1，2，3，4 (B) 2，3，4，1 (C) 1，4，2，3 (D) 1，2，4，3(34，76，45，18，26，54，92)，則由這組記錄關(guān)鍵字生成的二叉排序樹(shù)的深度為（ ）。( )7． 中序遍歷一棵二叉排序樹(shù)可以得到一個(gè)有序的序列。 (A) n2 (B) n(n+1) (C) n(n+1)/2 (D) n(n1)/2，則這棵二叉中共有（ ）個(gè)結(jié)點(diǎn)。struct node *lchild。} lklist。 LNode* p=HL。amp。if(q!=0){ t=(lklist *)malloc(sizeof(lklist))。p!=0。 r[j]x) j=j1。2． 設(shè)計(jì)在二叉排序樹(shù)上查找結(jié)點(diǎn)X的算法。createbitree(btrchild)。11. 設(shè)一組初始關(guān)鍵字序列為(38，65，97，76，13，27，10)，則第3趟簡(jiǎn)單選擇排序后的結(jié)果為_(kāi)_____________________。 (A) 10 (B) 19 (C) 28 (D) 556．設(shè)一棵m叉樹(shù)中有N1個(gè)度數(shù)為1的結(jié)點(diǎn)，N2個(gè)度數(shù)為2的結(jié)點(diǎn)，……，Nm個(gè)度數(shù)為m的結(jié)點(diǎn)，則該樹(shù)中共有（ ）個(gè)葉子結(jié)點(diǎn)。( )3． 子串“ABC”在主串“AABCABCD”中的位置為2。 (A) n(n1)/2 (B) n(n1) (C) n(n+1)/2 (D) (n1)/2，則順序查找的平均比較次數(shù)為（ ）。7． 設(shè)有向圖中不存在有向邊Vi,Vj，則其對(duì)應(yīng)的鄰接矩陣A中的數(shù)組元素A[i][j]的值等于____________。2． 下面程序段的功能是實(shí)現(xiàn)在二叉排序樹(shù)中插入一個(gè)新結(jié)點(diǎn)，請(qǐng)?jiān)谙聞澗€處填上正確的內(nèi)容。 (A) O(n) (B) O(1og2n) (C) O(nlog2n) (D) O(n2)6. 設(shè)一個(gè)順序有序表A[1:14]中有14個(gè)元素，則采用二分法查找元素A[4]的過(guò)程中比較元素的順序?yàn)? )。 while(ij){ while (ij amp。2. 設(shè)完全有向圖中有n個(gè)頂點(diǎn)，則該完全有向圖中共有________條有向條；設(shè)完全無(wú)向圖中有n個(gè)頂點(diǎn)，則該完全無(wú)向圖中共有________條無(wú)向邊。 (A) 1 (B) 2 (C) 3 (D) 4，則刪除棧頂元素的操作序列為（ ）。6．設(shè)F和R分別表示順序循環(huán)隊(duì)列的頭指針和尾指針，則判斷該循環(huán)隊(duì)列為空的條件為_(kāi)____________________。 (A) O(n) (B) O(n2) (C) O(nlog2n) (D) O(1og2n)，則有向圖G中頂點(diǎn)i的入度為（ ）。四、算法設(shè)計(jì)題(28分)1． 設(shè)計(jì)判斷兩個(gè)二叉樹(shù)是否相同的算法。r[j]=temp。 (A) ni (B) n1i (C) n+1i (D) 不能確定10 設(shè)一組初始記錄關(guān)鍵字序列為(45，80，55，40，42，85)，則以第一個(gè)記錄關(guān)鍵字45為基準(zhǔn)而得到一趟快速排序的結(jié)果是（ ）。 snext=hashtable[k]。13． 設(shè)前序遍歷某二叉樹(shù)的序列為ABCD，中序遍歷該二叉樹(shù)的序列為BADC，則后序遍歷該二叉樹(shù)的序列為_(kāi)____________。 (A) 3 (B) 4 (C) 5 (D) 87．設(shè)用鏈表作為棧的存儲(chǔ)結(jié)構(gòu)則退棧操作（ ）。}bitree。13. 下列算法實(shí)現(xiàn)在順序散列表中查找值為x的關(guān)鍵字，請(qǐng)?jiān)谙聞澗€處填上正確的語(yǔ)句。 (A) O(1) (B) O(log2n) (C) (D) O(n2)7．設(shè)無(wú)向圖G中有n個(gè)頂點(diǎn)e條邊，則其對(duì)應(yīng)的鄰接表中的表頭結(jié)點(diǎn)和表結(jié)點(diǎn)的個(gè)數(shù)分別為（ ）。5. 設(shè)某棵二叉樹(shù)中度數(shù)為0的結(jié)點(diǎn)數(shù)為N0，度數(shù)為1的結(jié)點(diǎn)數(shù)為N1，則該二叉樹(shù)中度數(shù)為2的結(jié)點(diǎn)數(shù)為_(kāi)________；若采用二叉鏈表作為該二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)，則該二叉樹(shù)中共有_______個(gè)空指針域。 (A) RF (B) FR (C) (RF+M)％M (D) (FR+M)％M4．設(shè)某棵二叉樹(shù)的中序遍歷序列為ABCD，前序遍歷序列為CABD，則后序遍歷該二叉樹(shù)得到序列為（ ）。amp。5. 若用鏈表存儲(chǔ)一棵二叉樹(shù)時(shí)，每個(gè)結(jié)點(diǎn)除數(shù)據(jù)域外，還有指向左孩子和右孩子的兩個(gè)指針。3. 假定一棵樹(shù)的廣義表表示為A（C，D（E，F(xiàn)，G），H（I，J）），則樹(shù)中所含的結(jié)點(diǎn)數(shù)為_(kāi)_________個(gè)，樹(shù)的深度為_(kāi)__________，樹(shù)的度為_(kāi)________。 用克魯斯卡爾算法得到最小生成樹(shù)，試寫(xiě)出在最小生成樹(shù)中依次得到的各條邊。 int CountX(LNode* HL,ElemType x)數(shù)據(jù)結(jié)構(gòu)試卷（二）一、選擇題(24分)1．下面關(guān)于線性表的敘述錯(cuò)誤的是（ ）。_________________。 (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個(gè)待排序的記錄關(guān)鍵字，則在堆排序中需要（ ）個(gè)輔助記錄單元。10. 設(shè)有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)，如果按照從自上到下、從左到右從1開(kāi)始順序編號(hào)，則第i個(gè)結(jié)點(diǎn)的雙親結(jié)點(diǎn)編號(hào)為_(kāi)___________，右孩子結(jié)點(diǎn)的編號(hào)為_(kāi)__________。typedef struct node{int key。 (A) n (B) e (C) 2n (D) 2e4．在二叉排序樹(shù)中插入一個(gè)結(jié)點(diǎn)的時(shí)間復(fù)雜度為（ ）。10． 設(shè)一組初始記錄關(guān)鍵字序列為(20，18，22，16，30，19)，則根據(jù)這些初始關(guān)鍵字序列建成的初始堆為_(kāi)_______________________。i++){s=(lklist *)malloc(sizeof(lklist))。 (A) Nl+N2+……+Nm (B) l+N2+2N3+3N4+……+(m1)Nm (C) N2+2N3+3N4+……+(m1)Nm (D) 2Nl+3N2+……+(m+1)Nm7．設(shè)有序表中有1000個(gè)元素，則用二分查找查找元素X最多需要比較（ ）次。 j_____________。2. 設(shè)無(wú)向圖G（如右圖所示），給出該圖的最小生成樹(shù)上邊的集合并計(jì)算最小生成樹(shù)各邊上的權(quán)值之和。 (A) frontnext=s；front=s； (B) snext=rear；rear=s； (C) rearnext=s；rear=s； (D) snext=front；front=s；，則建立該圖鄰接表的時(shí)間復(fù)雜度為（ ）。3．設(shè)有向圖G的二元組形式表示為G =（D，R），D={1，2，3，4，5}，R={r}，r={1,2，2,4，4,5，1,3，3,2，3,5}，則給出該圖的一種拓?fù)渑判蛐蛄衉_________。 (A) O(n) (B) O(nlog2n) (C) O(n2) (D) O(n3/2)7．設(shè)帶有頭結(jié)點(diǎn)的單向循環(huán)鏈表的頭指針變量為head，則其判空條件是（ ）。（ ）9．線性表中的所有元素都有一個(gè)前驅(qū)元素和后繼元素。i){ int j=t。 (A) 串中不同字符的個(gè)數(shù) (B) 串中不同字母的個(gè)數(shù) (C) 串中所含字符的個(gè)數(shù) (D) 串中不同數(shù)字的個(gè)數(shù)2. 建立一個(gè)長(zhǎng)度為n的有序單鏈表的時(shí)間復(fù)雜度為（ ） (A) O(n) (B) O(1) (C) O(n2) (D) O(log2n)3. 兩個(gè)字符串相等的充要條件是（ ）。（ ）9. 圖的深度優(yōu)先遍歷算法中需要設(shè)置一個(gè)標(biāo)志數(shù)組，以便區(qū)分圖中的每個(gè)頂點(diǎn)是否被訪問(wèn)過(guò)。4． 設(shè)指針變量head指向雙向鏈表中的頭結(jié)點(diǎn)，指針變量p指向雙向鏈表中的第一個(gè)結(jié)點(diǎn)，則指針變量p和指針變量head之間的關(guān)系是p=_________和head=__________（設(shè)結(jié)點(diǎn)中的兩個(gè)指針域分別為llink和rlink）。 (A) ni (B) n1i (C) n+l i (D) 不能確定8．設(shè)散列表中有m個(gè)存儲(chǔ)單元，散列函數(shù)H(key)= key % p，則p最好選擇（ ）。10． 設(shè)無(wú)向圖G（如右圖所示），則其最小生成樹(shù)上所有邊的權(quán)值之和為_(kāi)________________。 (A) 單向鏈表 (B) 單向循環(huán)鏈表(C) 雙向鏈表 (D) 雙向循環(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的操作序列為（ ）。8. 設(shè)無(wú)向圖G中有n個(gè)頂點(diǎn)e條邊，則用鄰接矩陣作為圖的存儲(chǔ)結(jié)構(gòu)進(jìn)行深度優(yōu)先或廣度優(yōu)先遍歷時(shí)的時(shí)間復(fù)雜度為_(kāi)________；用鄰接表作為圖的存儲(chǔ)結(jié)構(gòu)進(jìn)行深度優(yōu)先或廣度優(yōu)先遍歷的時(shí)間復(fù)雜度為_(kāi)________。else{ bt=(bitree*)malloc(sizeof(bitree))。else {qnext=p。void quickpass(int r[], int s, int t){ int i=s, j=t, x=r[s]。void intersection(lklist *ha,lklist *hb,lklist *amp。 hc=t。j=j1。 }//while, 出循環(huán)時(shí)i中的值即為x結(jié)點(diǎn)個(gè)數(shù) return i。i=n。void createbitree(bitree *amp。(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. 設(shè)需要對(duì)5個(gè)不同的記錄關(guān)鍵字進(jìn)行排序，則至少需要比較_____________次，至多需要比較_____________次。（ ）10． 堆是完全二叉樹(shù)，完全二叉樹(shù)不一定是堆。4． 對(duì)一組初始關(guān)鍵字序列（40，50，95，20，15，70，60，45，10）進(jìn)行冒泡排序，則第一趟需要進(jìn)行相鄰記錄的比較的次數(shù)為_(kāi)_________，在整個(gè)排序過(guò)程中最多需要進(jìn)行__________趟排序才可以完成。for(i=0； im； i++) for(j=0； jt； j++) c[i][j]=0；for(i=0； im； i++) for(j=0； jt； j++) for(k=0； kn； k++) c[i][j]=c[i][j]+a[i][k]*b[k][j]； (A) O(m*n*t) (B) O(m+n+t) (C) O(m+n*t) (D) O(m*t+n)2．設(shè)順序線性表中有n個(gè)數(shù)據(jù)元素，則刪除表中第i個(gè)元素需要移動(dòng)（ ）個(gè)元素。tdata=k。（ ）3. 分塊查找的基本思想是首先在索引表中進(jìn)行查找，以便確定給定的關(guān)鍵字可能存在的塊號(hào)，然后再在相應(yīng)的塊內(nèi)進(jìn)行順序查找。j=j1。9. 設(shè)一棵二叉樹(shù)的前序序列為ABC，則有______________種不同的二叉樹(shù)可以得到這種序列。（ ）3．設(shè)某堆中有n個(gè)結(jié)點(diǎn)，則在該堆中插入一個(gè)新結(jié)點(diǎn)的時(shí)間復(fù)雜度為O(log2n)。３． 在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上設(shè)計(jì)直接插入排序算法數(shù)據(jù)結(jié)構(gòu)試卷（七）一、選擇題(30分)1．設(shè)某無(wú)向圖有n個(gè)頂點(diǎn)，則該無(wú)向圖的鄰接表中有（ ）個(gè)表頭結(jié)點(diǎn)。（ ）7．設(shè)一棵樹(shù)T可以轉(zhuǎn)化成二叉樹(shù)BT，則二叉樹(shù)BT中一定沒(méi)有右子樹(shù)。 (A) 空或只有一個(gè)結(jié)點(diǎn) (B) 高度等于其結(jié)點(diǎn)數(shù) (C) 任一結(jié)點(diǎn)無(wú)左孩子 (D) 任一結(jié)點(diǎn)無(wú)右孩子6．一趟排序結(jié)束后不一定能夠選出一個(gè)元素放在其最終位置上的是（ ）。 while