【正文】 60 56 42 38 B p→link=s。 增加111. 11. coutBTdata39。11. 11.二、 二、 用鏈接方式存儲(chǔ)的隊(duì)列，在進(jìn)行插入運(yùn)算時(shí)( ). A. 僅修改頭指針 　 B. 頭、尾指針都要修改 C. 僅修改尾指針 、尾指針可能都要修改3. 3.ElemType temp=pdata。 功能為：從初始點(diǎn)vi出發(fā)廣度優(yōu)先搜索由鄰接表GL所表示的圖。 閱讀算法（每題7分，共14分）1. 1. //在左子表上繼續(xù)查找 else __________________________________。 while(!QueueEmpty(Q)) { int k=QDelete(Q)。E={2,1,3,2,3,6,4,3,4,5,4,6,5,1,5,7,6,1,6,2,6,5}。 設(shè)有一個(gè)輸入數(shù)據(jù)的序列是 { 46, 25, 78, 62, 12, 80 }, 試畫(huà)出從空樹(shù)起，逐個(gè)輸入各個(gè)數(shù)據(jù)而生成的二叉搜索樹(shù)。二、 二、 A．健壯性和可讀性 B．并行性 C．正確性 D．時(shí)空復(fù)雜度2. 2. hb!=0) if(hadatahbdata){if(s==0) hc=s=ha。scanf(“%d”,amp。else{ bt=(bitree*)malloc(sizeof(bitree))。 設(shè)有向圖G中的有向邊的集合E={1，2，2，3，1，4，4，5，5，3，4，6，6，5}，則該圖的一個(gè)拓?fù)湫蛄袨開(kāi)________________________。8. 8.(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 p!=0。 while(ij){ while (ij amp。 (24，65，33，80，70，56，48)10. 10. CBDA8. 8. 快速，堆6. 6. m14. 4. pnext，sdata2. 2. 設(shè)計(jì)將所有奇數(shù)移到所有偶數(shù)之前的算法。 設(shè)一棵二叉樹(shù)的中序遍歷序列為BDCA，后序遍歷序列為DBAC，則這棵二叉樹(shù)的前序序列為_(kāi)___________________。 (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ù)的深度為（ ）。 g[j].firstarc=p。void adjmatrixtoadjlist(gadjmatrix g1[ ],glinkheadnode g2[ ]){int i,j。四、算法設(shè)計(jì)題1. 1.2. 2.t,int k){if (t==0 ) {____________________________。（ ）3. 3. (A) 5 (B) 6 (C) 7 (D) 89. 9. (A) A[1]，A[2]，A[3]，A[4] (B) A[1]，A[14]，A[7]，A[4] (C) A[7]，A[3]，A[5]，A[4] (D) A[7]，A[5] ，A[3]，A[4]7. 7. (A) 99 (B) 97 (C) 91 (D) 935. 5. 建立一個(gè)長(zhǎng)度為n的有序單鏈表的時(shí)間復(fù)雜度為（ ） (A) O(n) (B) O(1) (C) O(n2) (D) O(log2n)3. 3.}}數(shù)據(jù)結(jié)構(gòu)試卷（十二）head){ lklist *p,*q,*s。 設(shè)計(jì)在鏈?zhǔn)浇Y(jié)構(gòu)上實(shí)現(xiàn)簡(jiǎn)單選擇排序算法。 r[j].key) j=j1。（ ）2．當(dāng)向二叉排序樹(shù)中插入一個(gè)結(jié)點(diǎn)，則該結(jié)點(diǎn)一定成為葉子結(jié)點(diǎn)。一、選擇題(30分)1．設(shè)某無(wú)向圖有n個(gè)頂點(diǎn)，則該無(wú)向圖的鄰接表中有（ ）個(gè)表頭結(jié)點(diǎn)。 (D) top=topnext。 i=s。 qdata=t。 t[j]= 39。 if (btkey==x) return。 (A) 先進(jìn)先出 (B) 先進(jìn)后出 (C) 只能插入 (D) 只能刪除 （ ）8. 8.struct node *rchild。 08. 8.}}2. 2.typedef struct node2{int vertexinfo。p=(glinklistnode *)malloc(sizeof(glinklistnode))。 (A) n (B) n/2 (C) (n+1)/2 (D) (n1)/2(13，18，24，35，47，50，62)，則在其中利用二分法查找值為24的元素需要經(jīng)過(guò)（ ）次比較。 設(shè)某棵完全二叉樹(shù)中有100個(gè)結(jié)點(diǎn)，則該二叉樹(shù)中有______________個(gè)葉子結(jié)點(diǎn)。2． 2． 設(shè)計(jì)判斷單鏈表中元素是否是遞增的算法。 (A) n2 (B) n(n+1) (C) n(n+1)/2 (D) n(n1)/2，則這棵二叉中共有（ ）個(gè)結(jié)點(diǎn)。4. 4.if(ch==39。head ){ for (i=1。hc){ lklist *s=hc=0。3. 3. 快速排序在最壞情況下的時(shí)間復(fù)雜度為（ ）。6. 6.一棵結(jié)點(diǎn)數(shù)為N的二叉樹(shù)，其所有結(jié)點(diǎn)的度的總和是_____________。三、 三、 else return 0。 39。int high=n1。 單選題（每題2分，共20分） 二、 二、 2i+1 2i+2 (i1)/211. 11.exit(1)。 樹(shù)最適合用來(lái)表示( )。 圖10請(qǐng)畫(huà)出圖10的鄰接矩陣和鄰接表。 }//while, 出循環(huán)時(shí)i中的值即為x結(jié)點(diǎn)個(gè)數(shù) return i。A n B n/2 C (n+1)/2 D (n1)/2 在一個(gè)單鏈表中,若q所指結(jié)點(diǎn)是p所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn),若在q與p之間插入一個(gè)s所指的結(jié)點(diǎn),則執(zhí)行( )。 一種抽象數(shù)據(jù)類(lèi)型包括______________和_____________兩個(gè)部分。 在對(duì)m階的B_樹(shù)插入元素的過(guò)程中，每向一個(gè)結(jié)點(diǎn)插入一個(gè)索引項(xiàng)（葉子結(jié)點(diǎn)中的索引項(xiàng)為關(guān)鍵字和空指針）后，若該結(jié)點(diǎn)的索引項(xiàng)數(shù)等于______個(gè)，則必須把它分裂為_(kāi)______個(gè)結(jié)點(diǎn)。圖深度優(yōu)先序列廣度優(yōu)先序列鄰接矩陣表示時(shí)datanext s→link=p。 用克魯斯卡爾算法得到的最小生成樹(shù)為： (1,2)3, (4,6)4, (1,3)5, (1,4)8, (2,5)10, (4,7)204. 4. e 2e7. 7. O(n)3. 3.五、 五、 閱讀算法（每題7分，共14分）1. 1. A 0 1 2 3 4 5 6 7 data 在堆排序的過(guò)程中，對(duì)任一分支結(jié)點(diǎn)進(jìn)行篩運(yùn)算的時(shí)間復(fù)雜度為_(kāi)_______，整個(gè)堆排序過(guò)程的時(shí)間復(fù)雜度為_(kāi)_______。 在一個(gè)具有n個(gè)頂點(diǎn)的無(wú)向完全圖中，包含有________條邊，在一個(gè)具有n個(gè)頂點(diǎn)的有向完全圖中，包含有________條邊。 對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的有向圖和無(wú)向圖，在其對(duì)應(yīng)的鄰接表中，所含邊結(jié)點(diǎn)分別有_______個(gè)和________個(gè)。5. 5.} DFS：????… BFS：???…? 4. 4.六、 六、 if(!visited[j]) { coutj39。四、 四、其余類(lèi)推，則A[ i ]元素的左孩子元素為_(kāi)_______,右孩子元素為_(kāi)______________，雙親元素為_(kāi)___________。5. 5.3. 3. 若需要利用形參直接訪(fǎng)問(wèn)實(shí)參時(shí)，應(yīng)將形參變量說(shuō)明為（ ）參數(shù)。void adjustheap(int r[ ],int n){ int j=n,i=j/2,temp=r[j1]。}。三、算法設(shè)計(jì)題1. 1.if(i==1)head=q=p。createbitree(btrchild)。 快速排序算法的平均時(shí)間復(fù)雜度為_(kāi)___________，直接插入排序算法的平均時(shí)間復(fù)雜度為_(kāi)__________。}數(shù)據(jù)結(jié)構(gòu)試卷（十四） if (ij) {r[i]=r[j]。( )9． 9．( )5． 5．三、判斷題(20分)1． 1．6． 6．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è)順序線(xiàn)性表中有n個(gè)數(shù)據(jù)元素，則刪除表中第i個(gè)元素需要移動(dòng)（ ）個(gè)元素。i=n1。 (49，13，27，50，76，38，65，97)2. 2.}else if (tdatak) bstinsert(tlchild,k)。 稀疏矩陣的壓縮存儲(chǔ)可以用一個(gè)三元組表來(lái)表示稀疏矩陣中的非0元素。 如果某個(gè)有向圖的鄰接表中第i條單鏈表為空，則第i個(gè)頂點(diǎn)的出度為零。 for(q=head。 ij amp。} while (____________________) i=i+1。（ ）5．哈夫曼樹(shù)中沒(méi)有度數(shù)為1的結(jié)點(diǎn)。 (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，804．（ ）二叉排序樹(shù)可以得到一個(gè)從小到大的有序序列。 (A) top=top+1。三、填空題(30分)1. 1.3. 3.5. 5.7. 7.9. 9.void quickpass(struct record r[], int s, int t, int amp。3. 3. s=p。else { for(i=start1,j=0。 struct node *lchild,*rchild。 向二叉排序樹(shù)中插入一個(gè)結(jié)點(diǎn)需要比較的次數(shù)可能大于該二叉樹(shù)的高度。 下面程序段的功能是實(shí)現(xiàn)在二叉排序樹(shù)中插入一個(gè)新結(jié)點(diǎn)，請(qǐng)?jiān)谙聞澗€(xiàn)處填上正確的內(nèi)容。 設(shè)連通圖G中有n個(gè)頂點(diǎn)e條邊，則對(duì)應(yīng)的最小生成樹(shù)上有___________條邊。一、選擇題1．C 2．C 3．C 4．B 5．B6．C 7．B 8．C 9．A 10．A t=(bitree *)malloc(sizeof(bitree))，bstinsert(trchild,k)3. 3.count){ if(bt!=0) {count++。int adjvertex。padjvertex=j。 (A) 小于等于m的最大奇數(shù) (B) 小于等于m的最大素?cái)?shù) (C) 小于等于m的最大偶數(shù) (D) 小于等于m的最大合數(shù)9．設(shè)在一棵度數(shù)為3的樹(shù)中，度數(shù)為3的結(jié)點(diǎn)數(shù)有2個(gè)，度數(shù)為2的結(jié)點(diǎn)數(shù)有1個(gè)，度數(shù)為1的結(jié)點(diǎn)數(shù)有2個(gè)，那么度數(shù)為0的結(jié)點(diǎn)數(shù)有（ ）個(gè)。7． 7． 對(duì)鏈表進(jìn)行插入和刪除操作時(shí)不必移動(dòng)鏈表中結(jié)點(diǎn)。 用鄰接矩陣作為圖的存儲(chǔ)結(jié)構(gòu)時(shí)，則其所占用的存儲(chǔ)空間與圖中頂點(diǎn)數(shù)無(wú)關(guān)而與圖中邊數(shù)有關(guān)。 sum(btlchild,s)。} } r[i]=x。 (A) (B) (C) (D) 7. 二叉排序樹(shù)中左子樹(shù)上所有結(jié)點(diǎn)的值均（ ）根結(jié)點(diǎn)的值。 設(shè)需要對(duì)5個(gè)不同的記錄關(guān)鍵字進(jìn)行排序，則至少需要比較_____________次，至多需要比較_____________次。void createbitree(bitree *amp。 struct node *next。 設(shè)計(jì)在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上合并排序的算法。 12465313. 13.} if(ha==0) snext=hb。}3. 3. p=HL。