甘肅省專升本西北師范大學計算機科學與技術習題

1、2011年甘肅省專升本西北師范大學計算機科學與技術習題 班別學號姓名成績一、單項選擇（每小題2分，共24分） 1.若某線性表的常用操作是取第i個元素及其前趨元素，則采用( A )存儲方式最節(jié)省時間A.順序表B.單鏈表C.雙鏈表D.單向循環(huán)2.串是任意有限個( B )A.符號構成的序列B.字符構成的序列 C.符號構成的集合D.字符構成的集合3.設矩陣A(aij,1<=i,j<=10)的元素滿足: aij<>0(i>=j,1<=i,j<=10),aij =0 (i<j,1<=i,j<=10) 若將A的所有非0元素以行為主序存于首地址為20

2、00的存儲區(qū)域中，每個元素占4個單元,則元素A59的首地址為( C )A.2340B.2336C.2220D.21604.如果以鏈表作為棧的存儲結構,則退棧操作時( D ) A.必須判別棧是否滿干 B.對棧不作任何判別 C.判別棧元素的類型 D.必須判別棧是否空5.設數(shù)組Data0.m作為循環(huán)隊列SQ的存儲空間，front為隊頭指針，rear為隊尾指針，則執(zhí)行出隊操作的語句為( A )A.front=(front+1)%(m+1) B.front=(front+1)% mC.rear=(rear+1)% mD. front=front+16.深度為6(根的層次為1)的二叉樹至多有( B )結點

3、A.64B.63C.31D.32 7.將含100個結點的完全二叉樹從根這一層開始，每層從左至右依次對結點編號，根結點的編號為1。編號為47的結點X的雙親的編號為( C )A.24B.25C.23D.2無法確定8.設有一個無向圖G=(V,E)和G'=(V',E')，如果G'為G的生成樹，則下面不正確的說法是( D )A.G'為G的子圖 B.G'為G的一個無環(huán)子圖C.G'為G的極小連通子圖且V'=V D.G'為G的連通分量9.用線性探測法查找閉散列上，可能要探測多個散列地址，這些位置上的鍵值( D )A.一定都是同義詞B.一定

4、都不是同義詞C.都相同D.不一定都是同義詞 10.二分查找要求被查找的表是( C )A.鍵值有序的鏈接表B.鏈接表但鍵值不一定有序表C.鍵值有序的順序表D.順序表但鍵值不一定有序表 11.當初始序列已經(jīng)按鍵值有序，用直接插入法對其進行排序，需要比較的次數(shù)為( B )A. n2B. n-1C. log2nD. nlog2n12.堆是一個鍵值序列K1,K2,.,Ki,.,Kn,對i=1,2,., n/2 ，滿足(A)A. Ki<=K2i且Ki<=K2i+1(2i+1<=n)B.Ki<K2i<K2i+1C. Ki<=K2i或Ki<=K2i+1(2i+1<

5、;=n) D.Ki<=K2i<=K2i+1二、判斷題(正確的在括號內打"V",錯的在括號內打"X",每小題1分，共10分) 1.雙鏈表中至多只有一個結點的后繼指針為空( V )2.在循環(huán)隊列中，front指向隊列中第一個元素的前一位置，rear指向實際的隊尾元素，隊列為滿的條件是front=rear( X )3.對線性表進行插入和刪除操作時，不必移動結點。( X )4.隊可以作為對樹的層次遍歷的一種數(shù)據(jù)結構。( V )5.在一個有向圖的拓樸序列中，若頂點a在頂點b之前，則圖中必有一條弧<a,b>。( X )6.對有向圖G，如果從任

6、一頂點出發(fā)進行一次深度優(yōu)先或廣度優(yōu)先搜索就能訪問每個頂點，則該圖一定是完全圖。( X )7."二分查找法"必需在有序表上進行。( V )8.向二叉排序樹中插入一個新結點時，新結點一定成為二叉排序樹的一個葉子結點。( V )9.鍵值序列A,C,D,B,E,E,F是一個堆。( X )10.在二路歸并時，被歸并的兩個子序列中的關鍵字個數(shù)不一定相等。( V )三、填空題(每空2分，共24分)1.設r指向單鏈表最后一個結點，要在最后一個結點之后插入s所指的結點，需執(zhí)行的三條語句是r->next=s ; r=s; r->next=NULL 。2.在帶頭結點單鏈表L中，表空的

7、條件是 L->next=NULL 3.設一個鏈棧的棧頂指針為ls，棧中結點格式為 infolink ，?？盏臈l件是ls=NULL。若棧不空，則退棧操作為p=ls；ls=ls->link；free(p). 4.已知一棵度為3的樹有2個度為1的結點，3個度為2的結點，4個度為3的結點，則該樹中有12個葉子結點。5.樹有三種常用的存儲結構，即孩子鏈表法，孩子兄弟鏈表法和雙親表示法。6.n-1個頂點的連通圖的生成樹有n-2條邊。7.一個有向圖G中若有弧<Vj,Vi>、<Vi,Vk>和<Vj,Vk>，則在圖G的拓樸序列中，頂點Vi,Vj和Vk的相對位置為V

8、j->Vi->Vk。8.設表中元素的初始狀態(tài)是按鍵值遞增的，分別用堆排序、快速排序、冒泡排序和歸并排序方法對其進行排序(按遞增順序)，冒泡排序最省時間，快速排序最費時間。9.下面是將鍵值為X的結點插入到二叉排序樹中的算法，請在劃線處填上適當?shù)膬热?。typedefstruct node *pnodestruct node int key; pnode left,right;void searchinsert(int x; pnode t);/t為二叉排序樹根結點的指針/ if(t=NULL ) p=malloc(size); p->key=x; p->left=nil;

9、p->right=nil; t=p;elseif (x<t->key) searchinsert(x,t->left) else searchinsert(x,t-> right);四、應用題(本題共28分)1.給定權值5,10,12,15,30,40,構造相應的哈夫曼樹，要求寫出構造步驟。(4分)哈夫曼樹構造步驟:2.已知一表為(Jan,Feb,Mar,Apr,May,Jun,Jul,Aug,Sep,Oct,Nov,Dec),按表中順序依次插入初始為空的二叉排序樹，要求：(1)在右邊畫出建立的二叉排序樹。(4分)(2)求出在等概率情況下查找成功的平均查

10、找長度。(2分) ASLSU =(1+2*2+3*3+4*3+5*2+6)/12=42/12=3.53.下圖表示一個地區(qū)的交通網(wǎng)，頂點表示城市，邊表示連結城市間的公路，邊上的權表示修建公路花費的代價。怎樣選擇能夠溝通每個城市且總造價最省的n-1條公路，畫出所有可能的方案.(4分)  4.已知一個無向圖的鄰接表為:(本題4分,每小題2分)  (1)畫出這個圖。(2)以V1為出發(fā)點，對圖進行廣度優(yōu)先搜索，寫出所有可能的訪問序列。 V1->V2->V4->V5->V3 V1->V4->V2->V3->V55.設n個元素的有序表為R,

11、K為一個給定的值，二分查找算法如下：int binsearch(sqlist R; keytype K:);l=1; h=n; suc=false;while (l<=h)&&(!suc) do mid=(l+h)/2;caseK=Rmid.key: suc=true;K<Rmid.key: h=mid-1;K>Rmid.key: l=mid+1end if (suc) return(mid) else return(0)將上述算法中劃線語句改為：K<Rmid.key: h=mid. 問改動后，算法能否正常工作？請說明原因。若能正常工作，請給出一個查找序

12、列和查找某個鍵值的比較次數(shù).(本題4分)答：（1）若K在R中或大于R中的最大值，則算法能正常運行； 若K不在R中或小于R中的最大值，則算法不能正常運行，會出現(xiàn)死循環(huán)； （2）如：在2，4，6，8中，當K=7時，算法出現(xiàn)死循環(huán)； 當K=6時，算法能正常運行，查找成功，比較次數(shù)為2次。6.有一組鍵值27,84,21,47,15,25,68,35,24,采用快速排序方法由小到大進行排序，請寫出每趟的結果，并標明在第一趟排序過程中鍵值的移動情況。(本題共6分)答：(1)每趟的結果：    (2)第一趟排序鍵值移動情況： 五、設計題(本題共14分)1.一棵二叉樹以

13、二叉鏈表為存儲結構 lchilddatarchild 。設計一個算法，求在前序序列中處于第K個位置的結點。(本題6分)類型定義如下:typedef struct node * pointer ;struct node datatype data ; pointer lchild, rchild ;typedef pointer bitreptr ;算法如下:void pre ( bitreptr t ; int k; bitreptr p ) if ( t!=NULL ) i=i+1; if ( i=k) p=t; return(p); pre(t->lchild, k,p ) ; pre(t->rchild, k,p ) ; 2.某單鏈表L的結點結構為 datanext ，結點個數(shù)至少3個，試畫出該鏈表的結構圖，并編寫算法判斷該鏈表的元素是否成等差關系，即:設各元素值依次為a1,a2,.,an, 判斷ai+1-ai=ai-ai-1是否成立，其中i滿