2011年甘肅省專升本西北師范大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)習(xí)題(共7頁)

1、精選優(yōu)質(zhì)文檔-傾情為你奉上2011年甘肅省專升本西北師范大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)習(xí)題 班別學(xué)號(hào)姓名成績(jī)一、單項(xiàng)選擇（每小題2分，共24分） 1.若某線性表的常用操作是取第i個(gè)元素及其前趨元素，則采用( A )存儲(chǔ)方式最節(jié)省時(shí)間A.順序表B.單鏈表C.雙鏈表D.單向循環(huán)2.串是任意有限個(gè)( B )A.符號(hào)構(gòu)成的序列B.字符構(gòu)成的序列 C.符號(hào)構(gòu)成的集合D.字符構(gòu)成的集合3.設(shè)矩陣A(aij,1<=i,j<=10)的元素滿足: aij<>0(i>=j,1<=i,j<=10),aij =0 (i<j,1<=i,j<=10) 若將A的所有非0元素

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

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

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

5、K2i+1(2i+1<=n) D.Ki<=K2i<=K2i+1二、判斷題(正確的在括號(hào)內(nèi)打"V",錯(cuò)的在括號(hào)內(nèi)打"X",每小題1分，共10分) 1.雙鏈表中至多只有一個(gè)結(jié)點(diǎn)的后繼指針為空( V )2.在循環(huán)隊(duì)列中，front指向隊(duì)列中第一個(gè)元素的前一位置，rear指向?qū)嶋H的隊(duì)尾元素，隊(duì)列為滿的條件是front=rear( X )3.對(duì)線性表進(jìn)行插入和刪除操作時(shí)，不必移動(dòng)結(jié)點(diǎn)。( X )4.隊(duì)可以作為對(duì)樹的層次遍歷的一種數(shù)據(jù)結(jié)構(gòu)。( V )5.在一個(gè)有向圖的拓樸序列中，若頂點(diǎn)a在頂點(diǎn)b之前，則圖中必有一條弧<a,b>。( X

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

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

8、,Vj和Vk的相對(duì)位置為Vj->Vi->Vk。8.設(shè)表中元素的初始狀態(tài)是按鍵值遞增的，分別用堆排序、快速排序、冒泡排序和歸并排序方法對(duì)其進(jìn)行排序(按遞增順序)，冒泡排序最省時(shí)間，快速排序最費(fèi)時(shí)間。9.下面是將鍵值為X的結(jié)點(diǎn)插入到二叉排序樹中的算法，請(qǐng)?jiān)趧澗€處填上適當(dāng)?shù)膬?nèi)容。typedefstruct node *pnodestruct node int key; pnode left,right;void searchinsert(int x; pnode t);/t為二叉排序樹根結(jié)點(diǎn)的指針/ if(t=NULL ) p=malloc(size); p->key=x; p-&

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

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

11、.設(shè)n個(gè)元素的有序表為R,K為一個(gè)給定的值，二分查找算法如下：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. 問改動(dòng)后，算法能否正常工作？請(qǐng)說明原因。若能

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

13、共14分)1.一棵二叉樹以二叉鏈表為存儲(chǔ)結(jié)構(gòu) lchilddatarchild 。設(shè)計(jì)一個(gè)算法，求在前序序列中處于第K個(gè)位置的結(jié)點(diǎn)。(本題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的結(jié)點(diǎn)結(jié)構(gòu)為 datanext ，結(jié)點(diǎn)個(gè)數(shù)至少3個(gè)，試畫出該鏈表的結(jié)構(gòu)圖，并編寫算法判斷該鏈表的元素是否成等差關(guān)系，即:設(shè)各元素值依次為a1,a2,.,an, 判斷ai+1-ai=ai-ai-1是否成立，其中i滿足2<=