【正文】 組線性表；（2） （2）5稀疏矩陣如下所示， 運(yùn)算題（每題6分，共24分）1. 1.三、 三、 當(dāng)待排序的記錄數(shù)較大，排序碼較隨機(jī)且對(duì)穩(wěn)定性不作要求時(shí)，宜采用_______________排序；當(dāng)待排序的記錄數(shù)較大，存儲(chǔ)空間允許且要求排序是穩(wěn)定時(shí)，宜采用________________________排序。 在線性表的散列存儲(chǔ)中，處理沖突的常用方法有________________________和_____________________________兩種。其余類推，則A[ i ]元素的左孩子元素為_(kāi)_______,右孩子元素為_(kāi)______________，雙親元素為_(kāi)___________。10. 10.9. 9. 對(duì)一棵二叉搜索樹(shù)進(jìn)行中序遍歷時(shí)，得到的結(jié)點(diǎn)序列是一個(gè)______________。一棵結(jié)點(diǎn)數(shù)為N的二叉樹(shù)，其所有結(jié)點(diǎn)的度的總和是_____________。7. 7.6. 6.W中第6 行的元素和第4 列的元素共占用＿_(dá)______＿個(gè)字節(jié)。5. 5.4. 4.3. 3.2. 2. 數(shù)據(jù)結(jié)構(gòu)是指數(shù)據(jù)及其相互之間的______________。 A. O(n) B. O(1) C. O(log2n) D. O(n2) 快速排序在最壞情況下的時(shí)間復(fù)雜度為（ ）。A．行號(hào) B．列號(hào) C．元素值 D．非零元素個(gè)數(shù)9. 9. 若需要利用形參直接訪問(wèn)實(shí)參時(shí)，應(yīng)將形參變量說(shuō)明為（ ）參數(shù)。A．低于鏈接法處理沖突 B. 高于鏈接法處理沖突 C．與鏈接法處理沖突相同 D．高于二分查找7. 7. AOV網(wǎng)是一種（ ）。 一個(gè)棧的輸入序列為1 2 3，則下列序列中不可能是棧的輸出序列的是( C ) A. 2 3 1 B. 3 2 1 C. 3 1 2 D. 1 2 35. 5. 對(duì)線性表，在下列哪種情況下應(yīng)當(dāng)采用鏈表表示？( ) 4. 4.3. 3. D. HL=p。 C. pnext=HL。 B. pnext=HL。 A. pnext=HLnext。 對(duì)一個(gè)算法的評(píng)價(jià)，不包括如下（B ）方面的內(nèi)容。 單選題（每題 2 分，共20分）1. 1.}數(shù)據(jù)結(jié)構(gòu)（十五）一、 i=i/2。 else{r[j1]=r[i1]。void adjustheap(int r[ ],int n){ int j=n,i=j/2,temp=r[j1]。 return(0)。else if (pkeykey)p=plchild。bitree *bstsearch1(bitree *t, int key){ bitree *p=t。 else snext=ha。hb=hbnext。 s=hb。} else {if(s==0) hc=s=hb。}。 else {snext=ha。amp。hc){ lklist *s=hc=0。 設(shè)計(jì)在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上合并排序的算法。三、算法設(shè)計(jì)題1. 1.一、選擇題1．A 2．D 3．B 4．B 5．B 6．D7．A 8．D 9．D 10．C 11．B 12．D3． 3．2． 2．三、算法設(shè)計(jì)題(22分)1． 1．____________。if(i==1)head=q=p。(pdata))。i++){ p=(lklist *)malloc(sizeof(lklist))。head ){ for (i=1。} lklist。typedef struct node {int data。createbitree(btrchild)。 btdata=ch。) ___________。if(ch==39。bt){scanf(“%c”,amp。}bitree。struct node *lchild。 下面程序段的功能是建立二叉樹(shù)的算法，請(qǐng)?jiān)谙聞澗€處填上正確的內(nèi)容。13. 13. 設(shè)一組初始關(guān)鍵字序列為(38，65，97，76，13，27，10)，則第3趟簡(jiǎn)單選擇排序后的結(jié)果為_(kāi)_____________________。11. 11. 設(shè)散列表的長(zhǎng)度為8，散列函數(shù)H(k)=k % 7，用線性探測(cè)法解決沖突，則根據(jù)一組初始關(guān)鍵字序列(8，15，16，22，30，32)構(gòu)造出的散列表的平均查找長(zhǎng)度是________。9. 9. 數(shù)據(jù)結(jié)構(gòu)從邏輯上劃分為三種基本類型：___________、__________和___________。 設(shè)指針變量p指向單鏈表中結(jié)點(diǎn)A，則刪除結(jié)點(diǎn)A的語(yǔ)句序列為：q=pnext；pdata=qdata；pnext=___________；feee(q)；7. 7.6. 6. 設(shè)在長(zhǎng)度為20的有序表中進(jìn)行二分查找，則比較一次查找成功的結(jié)點(diǎn)數(shù)有_________個(gè)，比較兩次查找成功有結(jié)點(diǎn)數(shù)有_________個(gè)。4. 4. 快速排序算法的平均時(shí)間復(fù)雜度為_(kāi)___________，直接插入排序算法的平均時(shí)間復(fù)雜度為_(kāi)__________。2. 2. (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) n2 (B) n(n+1) (C) n(n+1)/2 (D) n(n1)/2，則這棵二叉中共有（ ）個(gè)結(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)造一棵哈夫曼樹(shù)，則這棵哈夫曼樹(shù)的帶權(quán)路徑長(zhǎng)度為（ ）。 (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)。(A) snext=pnext；pnext=s； (B) qnext=s； snext=p；(C) pnext=snext；snext=p； (D) pnext=s；snext=q；4．設(shè)輸入序列為6，則通過(guò)棧的作用后可以得到的輸出序列為（ ）。i=0，s=0； while (sn) {s=s+i；i++；} (A) O(n1/2) (B) O(n1/3) (C) O(n) (D) O(n2)2．設(shè)某鏈表中最常用的操作是在鏈表的尾部插入或刪除元素，則選用下列（ ）存儲(chǔ)方式最節(jié)省運(yùn)算時(shí)間。}數(shù)據(jù)結(jié)構(gòu)試卷（十四） q=p,p=pnext)if(qdatapdata) return(0)。elsefor(q=head,p=headnext。 設(shè)計(jì)判斷單鏈表中元素是否是遞增的算法。}3． 3．j=j1。 r[i]%2==1) i=i+1。} while (ij amp。 if (ij) {r[i]=r[j]。amp。void quickpass(int r[], int s, int t){ int i=s,j=t,x=r[s]。 sum(btrchild,s)。s){ if(bt!=0) {s=s+btdata。 設(shè)計(jì)計(jì)算二叉樹(shù)中所有結(jié)點(diǎn)值之和的算法。三、判斷題1．錯(cuò) 2．對(duì) 3．對(duì) 4．對(duì) 5．錯(cuò)6．錯(cuò) 7．對(duì) 8．對(duì) 9．錯(cuò) 10．對(duì)四、算法設(shè)計(jì)題1． 1．一、選擇題1．A 2．A 3．A 4．C 5．D6．D 7．C 8．B 9．C 10．A11．C 12．C 13．D 14．A 15．A3． 3．2． 2．五、算法設(shè)計(jì)題(20分)1． 1．（ ）10． 10．堆是完全二叉樹(shù)，完全二叉樹(shù)不一定是堆。( )9． 9．( )8． 8．( )7． 7．( )6． 6．( )5． 5．( )4． 4．( )3． 3．( )2． 2．三、判斷題(20分)1． 1． 設(shè)無(wú)向圖G（如右圖所示），則其最小生成樹(shù)上所有邊的權(quán)值之和為_(kāi)________________。10． 10． 設(shè)用于通信的電文僅由8個(gè)字母組成，字母在電文中出現(xiàn)的頻率分別為13210，根據(jù)這些頻率作為權(quán)值構(gòu)造哈夫曼樹(shù)，則這棵哈夫曼樹(shù)的高度為_(kāi)_______________。8． 8． 設(shè)一組初始記錄關(guān)鍵字序列為(20，12，42，31，18，14，28)，則根據(jù)這些記錄關(guān)鍵字構(gòu)造的二叉排序樹(shù)的平均查找長(zhǎng)度是_______________________________。6． 6． 對(duì)一組初始關(guān)鍵字序列（40，50，95，20，15，70，60，45，10）進(jìn)行冒泡排序，則第一趟需要進(jìn)行相鄰記錄的比較的次數(shù)為_(kāi)_________，在整個(gè)排序過(guò)程中最多需要進(jìn)行__________趟排序才可以完成。4． 4． 設(shè)某棵完全二叉樹(shù)中有100個(gè)結(jié)點(diǎn)，則該二叉樹(shù)中有______________個(gè)葉子結(jié)點(diǎn)。 設(shè)指針p指向單鏈表中結(jié)點(diǎn)A，指針s指向被插入的結(jié)點(diǎn)X，則在結(jié)點(diǎn)A的前面插入結(jié)點(diǎn)X時(shí)的操作序列為：1) snext=___________；2) pnext=s；3) t=pdata；4) pdata=___________；5) sdata=t；2． 2． (A) 4 (B) 5 (C) 6 (D) 7二、填空題(30分)1． 1． (A) 6 (B) 11 (C) 5 (D) ={1，2，2，3，3，4，1，4}，則下列屬于該有向圖G的一種拓?fù)渑判蛐蛄械氖牵? ）。 (A) n (B) n/2 (C) (n+1)/2 (D) (n1)/2(13，18，24，35，47，50，62)，則在其中利用二分法查找值為24的元素需要經(jīng)過(guò)（ ）次比較。 (A) 4 (B) 5 (C) 6 (D) 7，則該完全無(wú)向圖中有（ ）條邊。 (A) ni (B) n1i (C) n+l i (D) 不能確定8．設(shè)散列表中有m個(gè)存儲(chǔ)單元，散列函數(shù)H(key)= key % p，則p最好選擇（ ）。 (A) pright=s； sleft=p； prightleft=s； sright=pright； (B) sleft=p；sright=pright；pright=s； prightleft=s； (C) pright=s； prightleft=s； sleft=p； sright=pright； (D) sleft=p；sright=pright；prightleft=s； pright=s；6．下列各種排序算法中平均時(shí)間復(fù)雜度為O(n2)是（ ）。 (A) N11 (B) N21 (C) N2+N3 (D) N1+N34．利用直接插入排序法的思想建立一個(gè)有序線性表的時(shí)間復(fù)雜度為（ ）。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è)元素。}}數(shù)據(jù)結(jié)構(gòu)試卷（13）pnextarc=g[j].firstarc。p=(glinklistnode *)malloc(sizeof(glinklistnode))。pnextarc=g[i].firstarc。j++)if ([i][j]==1){p=(glinklistnode *)malloc(sizeof(glinklistnode))。i++) for(j=0。for(i=0。i=n1。 glinklistnode *p。}glinkheadnode。typedef struct node2{int vertexinfo。 struct node1 *nextarc。typedef struct node1{int info。 int edge[m][m]。 設(shè)計(jì)一個(gè)算法將無(wú)向圖的鄰接矩陣轉(zhuǎn)為對(duì)應(yīng)鄰接表的算法。}}2. 2. countnode(btlchild,count)。void countnode(bit