




版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報或認(rèn)領(lǐng)
文檔簡介
1、2011年甘肅省專升本西北師范大學(xué)計算機(jī)科學(xué)與技術(shù)習(xí)題 班別學(xué)號姓名成績一、單項選擇(每小題2分,共24分) 1.若某線性表的常用操作是取第i個元素及其前趨元素,則采用( A )存儲方式最節(jié)省時間A.順序表B.單鏈表C.雙鏈表D.單向循環(huán)2.串是任意有限個( B )A.符號構(gòu)成的序列B.字符構(gòu)成的序列 C.符號構(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元素以行為主序存于首地址為20
2、00的存儲區(qū)域中,每個元素占4個單元,則元素A59的首地址為( C )A.2340B.2336C.2220D.21604.如果以鏈表作為棧的存儲結(jié)構(gòu),則退棧操作時( D ) A.必須判別棧是否滿干 B.對棧不作任何判別 C.判別棧元素的類型 D.必須判別棧是否空5.設(shè)數(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 )結(jié)點(diǎn)
3、A.64B.63C.31D.32 7.將含100個結(jié)點(diǎn)的完全二叉樹從根這一層開始,每層從左至右依次對結(jié)點(diǎn)編號,根結(jié)點(diǎn)的編號為1。編號為47的結(jié)點(diǎn)X的雙親的編號為( C )A.24B.25C.23D.2無法確定8.設(shè)有一個無向圖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.當(dāng)初始序列已經(jīng)按鍵值有序,用直接插入法對其進(jìn)行排序,需要比較的次數(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二、判斷題(正確的在括號內(nèi)打"V",錯的在括號內(nèi)打"X",每小題1分,共10分) 1.雙鏈表中至多只有一個結(jié)點(diǎn)的后繼指針為空( V )2.在循環(huán)隊列中,front指向隊列中第一個元素的前一位置,rear指向?qū)嶋H的隊尾元素,隊列為滿的條件是front=rear( X )3.對線性表進(jìn)行插入和刪除操作時,不必移動結(jié)點(diǎn)。( X )4.隊可以作為對樹的層次遍歷的一種數(shù)據(jù)結(jié)構(gòu)。( V )5.在一個有向圖的拓樸序列中,若頂點(diǎn)a在頂點(diǎn)b之前,則圖中必有一條弧<a,b>。( X )6.對有向圖G,如果從任
6、一頂點(diǎn)出發(fā)進(jìn)行一次深度優(yōu)先或廣度優(yōu)先搜索就能訪問每個頂點(diǎn),則該圖一定是完全圖。( X )7."二分查找法"必需在有序表上進(jìn)行。( V )8.向二叉排序樹中插入一個新結(jié)點(diǎn)時,新結(jié)點(diǎn)一定成為二叉排序樹的一個葉子結(jié)點(diǎn)。( V )9.鍵值序列A,C,D,B,E,E,F是一個堆。( X )10.在二路歸并時,被歸并的兩個子序列中的關(guān)鍵字個數(shù)不一定相等。( V )三、填空題(每空2分,共24分)1.設(shè)r指向單鏈表最后一個結(jié)點(diǎn),要在最后一個結(jié)點(diǎn)之后插入s所指的結(jié)點(diǎn),需執(zhí)行的三條語句是r->next=s ; r=s; r->next=NULL 。2.在帶頭結(jié)點(diǎn)單鏈表L中,表空的
7、條件是 L->next=NULL 3.設(shè)一個鏈棧的棧頂指針為ls,棧中結(jié)點(diǎn)格式為 infolink ,??盏臈l件是ls=NULL。若棧不空,則退棧操作為p=ls;ls=ls->link;free(p). 4.已知一棵度為3的樹有2個度為1的結(jié)點(diǎn),3個度為2的結(jié)點(diǎn),4個度為3的結(jié)點(diǎn),則該樹中有12個葉子結(jié)點(diǎn)。5.樹有三種常用的存儲結(jié)構(gòu),即孩子鏈表法,孩子兄弟鏈表法和雙親表示法。6.n-1個頂點(diǎn)的連通圖的生成樹有n-2條邊。7.一個有向圖G中若有弧<Vj,Vi>、<Vi,Vk>和<Vj,Vk>,則在圖G的拓樸序列中,頂點(diǎn)Vi,Vj和Vk的相對位置為V
8、j->Vi->Vk。8.設(shè)表中元素的初始狀態(tài)是按鍵值遞增的,分別用堆排序、快速排序、冒泡排序和歸并排序方法對其進(jìn)行排序(按遞增順序),冒泡排序最省時間,快速排序最費(fèi)時間。9.下面是將鍵值為X的結(jié)點(diǎ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->left=nil;
9、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、找長度。(2分) ASLSU =(1+2*2+3*3+4*3+5*2+6)/12=42/12=3.53.下圖表示一個地區(qū)的交通網(wǎng),頂點(diǎn)表示城市,邊表示連結(jié)城市間的公路,邊上的權(quán)表示修建公路花費(fèi)的代價。怎樣選擇能夠溝通每個城市且總造價最省的n-1條公路,畫出所有可能的方案.(4分) 4.已知一個無向圖的鄰接表為:(本題4分,每小題2分) (1)畫出這個圖。(2)以V1為出發(fā)點(diǎn),對圖進(jìn)行廣度優(yōu)先搜索,寫出所有可能的訪問序列。 V1->V2->V4->V5->V3 V1->V4->V2->V3->V55.設(shè)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中的最大值,則算法能正常運(yùn)行; 若K不在R中或小于R中的最大值,則算法不能正常運(yùn)行,會出現(xiàn)死循環(huán); (2)如:在2,4,6,8中,當(dāng)K=7時,算法出現(xiàn)死循環(huán); 當(dāng)K=6時,算法能正常運(yùn)行,查找成功,比較次數(shù)為2次。6.有一組鍵值27,84,21,47,15,25,68,35,24,采用快速排序方法由小到大進(jìn)行排序,請寫出每趟的結(jié)果,并標(biāo)明在第一趟排序過程中鍵值的移動情況。(本題共6分)答:(1)每趟的結(jié)果: (2)第一趟排序鍵值移動情況: 五、設(shè)計題(本題共14分)1.一棵二叉樹以
13、二叉鏈表為存儲結(jié)構(gòu) lchilddatarchild 。設(shè)計一個算法,求在前序序列中處于第K個位置的結(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)個數(shù)至少3個,試畫出該鏈表的結(jié)構(gòu)圖,并編寫算法判斷該鏈表的元素是否成等差關(guān)系,即:設(shè)各元素值依次為a1,a2,.,an, 判斷ai+1-ai=ai-ai-1是否成立,其中i滿
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 視頻監(jiān)控的設(shè)計方案
- 自動控制原理試題庫有答案
- 黑龍江省大慶市肇源縣(五四學(xué)制)2023-2024學(xué)年八年級下學(xué)期7月期末考試道德與法治試卷
- 幼兒園大班《我們的小區(qū)》教案
- 財務(wù)-合理避稅60個方法和42個技巧匯 總 你所不知道的“合理避稅”方案
- 璀璨未來文化館館投資指南
- 2025年android狀態(tài)欄!Android面試你必須要知道的那些知識完整PDF
- 2025年Android小技巧:這些面試官常問的開發(fā)面試題你都掌握好了嗎?源碼+原理+手寫框架-android 面試會問框架原理嗎
- 部編版二年級下冊第八單元《祖先的搖籃》教案
- 建筑施工特種作業(yè)-樁機(jī)操作工真題庫-3
- 開票稅點(diǎn)自動計算器
- 國家開放大學(xué)電大《10861理工英語4》期末終考題庫及答案
- 2024年小學(xué)四年級下冊數(shù)學(xué)期末測試卷附完整答案【典優(yōu)】
- 廣東省中山市2022-2023學(xué)年高一年級下冊期末統(tǒng)一考試物理試題含解析
- 2024年橫州茉莉花投資集團(tuán)有限責(zé)任公司招聘筆試沖刺題(帶答案解析)
- 蔬菜栽培學(xué)智慧樹知到期末考試答案章節(jié)答案2024年浙江大學(xué)
- JB-T 14320-2022 氧氣用止回閥
- 專題強(qiáng)化三 異面直線、線面角和二面角技巧-2021-2022學(xué)年高一數(shù)學(xué)【考題透析】滿分計劃系列(人教A版2019必修第二冊)
- 產(chǎn)品封樣管理制度
- 2024年湖北襄陽市檢察機(jī)關(guān)襄陽市城郊地區(qū)檢察院招聘筆試參考題庫附帶答案詳解
- 人工智能專業(yè)發(fā)展規(guī)劃方案
評論
0/150
提交評論