2017電大計(jì)算機(jī)考試題

2017電大計(jì)算機(jī)考試題一、選擇題?1.下列程序段的時(shí)間復(fù)雜度為()。?i=0，s=0;while(s?(A)O(n1/2)(B)O(n1/3)(C)O(n)(D)O(n)?2.設(shè)某鏈表中最常用的操作是在鏈表的尾部插入或刪除元素，則選用下列()存儲(chǔ)方式最節(jié)省運(yùn)算時(shí)間。?(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的操作序列為()。?(A)s-next=p-next;p-next=-s;?(B)q-next=s;s-next=p;?(C)p-next=s-next;s-next=p;?(D)p-next=s;s-next=q;?4.設(shè)輸入序列為1、2、3、4、5、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，3?5.設(shè)有一個(gè)10階的下三角矩陣A(包括對(duì)角線)，按照從上到下、從左到右的順序存儲(chǔ)到連續(xù)的55個(gè)存儲(chǔ)單元中，每個(gè)數(shù)組元素占1個(gè)字節(jié)的存儲(chǔ)空間，則A[5][4]地址與A[0][0]的地址之差為()。?(A)10(B)19(C)28(D)55?6.設(shè)一棵m叉樹中有N1個(gè)度數(shù)為1的結(jié)點(diǎn)，N2個(gè)度數(shù)為2的Nm個(gè)度數(shù)為m的結(jié)點(diǎn)，則該樹中共有()個(gè)葉子結(jié)點(diǎn)。?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)229?9.設(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(n-1)/2?10.設(shè)某棵二叉樹中只有度數(shù)為0和度數(shù)為2的結(jié)點(diǎn)且度數(shù)為0的結(jié)點(diǎn)數(shù)為n，則這棵二叉中共有()個(gè)結(jié)點(diǎn)。?(A)2n(B)n+l(C)2n-1(D)2n+l?11.設(shè)一組初始記錄關(guān)鍵字的長度為8，則最多經(jīng)過()趟插入排序可以得到有序序列。?(A)6(B)7(C)8(D)9?12.設(shè)一組初始記錄關(guān)鍵字序列為(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?13、設(shè)有序表中的元素為(13，18，24，35，47，50，62)，則在其中利用二分法查找值為24的元素需要經(jīng)過()次比較。?(A)1(B)2(C)3(D)4?14、設(shè)指針變量p指向雙向鏈表中結(jié)點(diǎn)A，指針變量s指向插入的結(jié)點(diǎn)X，則在結(jié)點(diǎn)A的后面插入結(jié)點(diǎn)X的操作序列為()。?(A)p-right=s;s-left=p;p-right-left=s;s-right=p-right;?(B)s-left=p;s-right=p-righ;p-right=s;p-right-left=s;?(C)p-right=s;p-right-left=s;s-left=p;s-right=p-right;?(D)s-left=p;s-right=p-right;p-right-left=s;p-right=s;?15、下列各種排序算法中平均時(shí)間復(fù)雜度為O(n2)是()。?(A)快速排序(B)堆排序(C)歸并排序(D)冒泡排序?16.進(jìn)程的三個(gè)基本狀態(tài)在一定條件下可以相互轉(zhuǎn)化，進(jìn)程由就緒狀態(tài)變?yōu)檫\(yùn)行狀態(tài)的條件是()。?(B)A.時(shí)間片用完B.等待某事件發(fā)生?(C)C.等待的某事件已發(fā)生D.被進(jìn)程調(diào)度程序選中?17.進(jìn)程的三個(gè)基本狀態(tài)在一定條件下可以相互轉(zhuǎn)化，進(jìn)程由運(yùn)行狀態(tài)變?yōu)樽枞麪顟B(tài)的條件是()。?(D)A.時(shí)間片用完B.等待某事件發(fā)生?(E)C.等待的某事件已發(fā)生D.被進(jìn)程調(diào)度程序選中?18.下列的進(jìn)程狀態(tài)變化中，()變化是不可能發(fā)生的。?A.運(yùn)行à就緒B.就緒à運(yùn)行C.等待à運(yùn)行D.等待à就緒?19.一個(gè)運(yùn)行的進(jìn)程用完了分配給它的時(shí)間片后，它的狀態(tài)變?yōu)?)。?A.就緒B.等待C.運(yùn)行D.由用戶自己確定?20.用V操作喚醒一個(gè)等待進(jìn)程時(shí)，被喚醒進(jìn)程的狀態(tài)變?yōu)?)。?A.等待B.就緒C.運(yùn)行D.完成?二：綜合題?1、下圖所示的森林：?(1)求樹(a)的先根序列和后根序列;?(2)求森林先序序列和中序序列;?(3)將此森林轉(zhuǎn)換為相應(yīng)的二叉樹;?2、設(shè)散列表的地址范圍是[0..9]，散列函數(shù)為H(key)=(key+2)MOD9,并采用鏈?表處理沖突，請(qǐng)畫出元素7、4、5、3、6、2、8、9依次插入散列表的存儲(chǔ)結(jié)構(gòu)。?3、已知數(shù)據(jù)六個(gè)字母及在通信中出現(xiàn)頻率如下表：?把這些字母和頻率作為葉子結(jié)點(diǎn)及權(quán)值，完成如下工作(7分，要有過程)。?(1)畫出對(duì)應(yīng)的Huffman樹。?(2)計(jì)算帶權(quán)路徑長度WPL。?(3)求A、B、C、D、E、F的Huffman編碼。?4、已知有如下的有向網(wǎng)：?求頂點(diǎn)A到其它各頂點(diǎn)的最短路徑(采用Dijkstra算法，要有過程)。?5、編寫算法，實(shí)現(xiàn)帶頭結(jié)點(diǎn)單鏈表的逆置算法?voidinvent(Lnode*head){Lnode*p,*q;if(!head-next)returnERROR;p=head-next;q=p-next;p-next=NULL;while(q){p=q;q=q-next;p-next=head-next;head-next=p;}}?6、設(shè)順序表va中的數(shù)據(jù)元數(shù)遞增有序。試寫一算法，將x插入到順序表的適當(dāng)位置上，以保持該表的有序性。?voidInsert_sq(Sqlistva[],ElemTypex){inti,j,n;n=length(va[]);if(x=va[i])va[n]=x;else{i=0;while(xva[i])i++;for(j=n-1;j=I;j--)va[j+1]=va[j];va[i]=x;}n++;}?7、已知線性表中的元素以值遞增有序排列，并以單鏈表作存儲(chǔ)結(jié)構(gòu)。試寫一算法，刪除表中所有大于x且小于y的元素(若表中存在這樣的元素)同時(shí)釋放被刪除結(jié)點(diǎn)空間。?voidDelete_list(Lnode*head,ElemTypex,ElemTypey){Lnode*p,*q;if(!head)returnERROR;p=head;q=p;while(!p){if(p-datax)&&(p-datanext;free(p);p=head;q=p;}else{q-next=p-next;free(p);p=q-next;}else{q=p;p=p-next;}}}?8、對(duì)于一個(gè)棧，給出輸入項(xiàng)A,B,C,D，如果