2017電大計算機考試題

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