下載本文檔
版權(quán)說(shuō)明:本文檔由用戶(hù)提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
1、試題紙(閉卷)課程名稱(chēng):數(shù)據(jù)結(jié)構(gòu)(A)適用專(zhuān)業(yè)年級(jí): 2008級(jí)計(jì)算機(jī)、軟件、網(wǎng)絡(luò) 考生學(xué)號(hào): 考生姓名:一、填空題(每空2分,共20分)1、在長(zhǎng)度為n的順序表中第i(1=iLlink=q;q-Rlink=p;p-Llink-Rlink=q;q-Llink=q;B. p-Llink=q;p-Llink-Rlink=q;q-Rlink=p;q-Llink=p-Llink;C. q-Rlink=p;q-Llink=p-Llink;p-Llink-Rlink=q;p-Llink=q;D. q-Llink=p-Llink;q-Rlink=q;p-Llink=q;p-Llink=q;5、若棧采用順序存儲(chǔ)
2、方式存儲(chǔ),現(xiàn)兩棧共享空間V1.m,topi代表第i個(gè)棧( i =1,2)棧頂,棧1的底在v1,棧2的底在Vm,則棧滿(mǎn)的條件是( )。A. |top2-top1|=0 B. top1+1=top2 C. top1+top2=m D. top1=top26、循環(huán)隊(duì)列存儲(chǔ)在數(shù)組A0.m中,則入隊(duì)時(shí)的操作為( )。A. rear=rear+1 B. rear=(rear+1) mod (m-1) C. rear=(rear+1) mod m D. rear=(rear+1)mod(m+1)7、設(shè)有下三角矩陣用數(shù)組A0.10,0.10表示,按行優(yōu)先順序存放其非零元素,每個(gè)非零元素占2個(gè)字節(jié),存放的基址為
3、100,則元素A5,5的存放地址為(DD)。A)110 B)120 C)130 D)1408、設(shè)樹(shù)T的度為4,其中度為1,2,3和4的結(jié)點(diǎn)個(gè)數(shù)分別為4,2,1,1,則T中的葉子數(shù)為( )。A5 B6 C7 D89、在有向圖G的拓?fù)湫蛄兄?,若頂點(diǎn)Vi在頂點(diǎn)Vj之前,則下列情形不可能出現(xiàn)的是( )。AG中有弧 BG中有一條從Vi到Vj的路徑CG中沒(méi)有弧 DG中有一條從Vj到Vi的路徑10、就排序算法所用的輔助空間而言,堆排序,快速排序,歸并排序的關(guān)系是( )。A堆排序快速排序歸并排序 B堆排序歸并排序歸并排序快速排序 D堆排序快速排序歸并排序三、判斷題(每題1分,共10分,對(duì)的打,錯(cuò)的打)1、數(shù)據(jù)
4、元素是數(shù)據(jù)的最小單位。2、順序存儲(chǔ)方式只能用于存儲(chǔ)線(xiàn)性結(jié)構(gòu)。3、一個(gè)廣義表的表尾總是一個(gè)廣義表。4、一個(gè)稀疏矩陣Am*n采用三元組形式表示, 若把三元組中有關(guān)行下標(biāo)與列下標(biāo)的值互換,并把m和n的值互換,則就完成了Am*n的轉(zhuǎn)置運(yùn)算。5、二叉樹(shù)是度為2的有序樹(shù)。6、一個(gè)樹(shù)的葉結(jié)點(diǎn),在前序遍歷和后序遍歷下,皆以相同的相對(duì)位置出現(xiàn)。7、有n個(gè)頂點(diǎn)的無(wú)向圖, 采用鄰接矩陣表示, 圖中的邊數(shù)等于鄰接矩陣中非零元素之和的一半。8、在圖G的最小生成樹(shù)G1中,可能會(huì)有某條邊的權(quán)值超過(guò)未選邊的權(quán)值。9、若一個(gè)有向圖的鄰接矩陣對(duì)角線(xiàn)以下元素均為零,則該圖的拓?fù)溆行蛐蛄斜囟ù嬖凇?0、在AOE圖中,關(guān)鍵路徑上活動(dòng)的
5、時(shí)間延長(zhǎng)多少,整個(gè)工程的時(shí)間也就隨之延長(zhǎng)多少。四、綜合應(yīng)用題(30分)1、已知一個(gè)森林的先序序列和后序序列如下,請(qǐng)構(gòu)造出該森林。(5分)先序序列:ABCDEFGHIJKLMNO 后序序列:CDEBFHIJGAMLONK2、有一份電文共使用到7個(gè)字符:C1,C2,C3,C4,C5,C6,C7,它們的出現(xiàn)頻率分別為6,8,5,1,23,10,3,請(qǐng)回答以下問(wèn)題:(7分)(1)畫(huà)出對(duì)應(yīng)的哈夫曼樹(shù)(按左子樹(shù)根結(jié)點(diǎn)的權(quán)值右子樹(shù)根結(jié)點(diǎn)的權(quán)值的次序構(gòu)造);(2)寫(xiě)出每個(gè)字符的哈夫曼編碼。3、對(duì)有五個(gè)結(jié)點(diǎn) A,B, C, D, E的圖的鄰接矩陣,基于鄰接矩陣,從A出發(fā),寫(xiě)出圖的深度、廣度優(yōu)先遍歷序列,和圖的關(guān)
6、鍵路徑。(5分)4、對(duì)以下關(guān)鍵字序列建立哈希表:(SUN,MON,TUE,WED,THU,FRI,SAT),哈希函數(shù)為H(K)=(關(guān)鍵字中第一個(gè)字母在字母表中的序號(hào))MOD 7,用線(xiàn)性探測(cè)法處理沖突,求構(gòu)造一個(gè)裝填因子為0.7的哈希表;并分別計(jì)算出在等概率情況下查找成功與不成功的平均查找長(zhǎng)度。(9分)5、 設(shè)一數(shù)組中原有數(shù)據(jù)如下:15,13,20,18,12,60。下面是一些常用排序方法進(jìn)行一遍排序后的結(jié)果,請(qǐng)問(wèn)分別是說(shuō)明排序方法。(4分)( )排序的結(jié)果為:12,13,15,18,20,60( )排序的結(jié)果為:13,15,18,12,20,60( )排序的結(jié)果為:13,15,20,18,12
7、,60( )排序的結(jié)果為:15,18,20,13,12,60五、算法設(shè)計(jì)題(20分)1、la,lb分別是帶頭結(jié)點(diǎn)的兩個(gè)單鏈表的頭指針,鏈表中的元素值按非遞減有序排列,本算法將兩鏈表合并成一個(gè)按元素值非遞增有序排列的單鏈表la,并要求利用原來(lái)兩個(gè)單鏈表的結(jié)點(diǎn)存放歸并后的單鏈表。(7分) LinkList Union(LinkList la,lb)2、編寫(xiě)一個(gè)函數(shù)判定兩棵二叉樹(shù)是否相似,所謂兩棵二叉樹(shù)p和q相似,即是要么它們都為空或都只有一個(gè)結(jié)點(diǎn),要么它們的左右子樹(shù)都相似。(5分)int Similar(BiTree p,q) 3、n個(gè)頂點(diǎn)的有向圖用鄰接矩陣array表示,下面是其拓?fù)渑判蛩惴?,?/p>
8、補(bǔ)充完整。(8分)注:(1)圖的頂點(diǎn)號(hào)從 0開(kāi)始計(jì); (2)indegree 是有n個(gè)分量的一維數(shù)組,放頂點(diǎn)的入度;(3)函數(shù) crein 用于算頂點(diǎn)入度; (4)有三個(gè)函數(shù)push(data),pop( ),check( )其含義為數(shù)據(jù) data進(jìn)棧,退棧和測(cè)試棧是否空(不空返回1,否則0)。 crein( array ,indegree,n) for (i=0;in;i+) indegreei= (1)_) for(i=0,in;i+) for (j=0;jn; j+) indegreei+=array(2)_(3)_; topsort (array,indegree,n) count=
9、(4)_) for (i=0;in;i+) if (5)_) push(i) while (check( ) vex=pop( ); printf(vex); count+; for (i=0;in;i+) k=array(6)_ if (7)_ ) indegreei-; if (8)_ ) push(i); if( countnext; pb=lb-next;pa,pb分別是鏈表la和lb的工作指針 1分 la-next=null; la作結(jié)果鏈表的頭指針,先將結(jié)果鏈表初始化為空。while(pa!=null & pb!=null) 當(dāng)兩鏈表均不為空時(shí)作 1分if(pa-datadata)
10、 1分 r=pa-next; 將pa 的后繼結(jié)點(diǎn)暫存于r。 1分 pa-next=la-next; 將pa結(jié)點(diǎn)鏈于結(jié)果表中,同時(shí)逆置。 1分la-next=pa; pa=r; 恢復(fù)pa為當(dāng)前待比較結(jié)點(diǎn)。 elser=pb-next; 將pb 的后繼結(jié)點(diǎn)暫存于r。pb-next=la-next; 將pb結(jié)點(diǎn)鏈于結(jié)果表中,同時(shí)逆置。la-next=pb;pb=r; 恢復(fù)pb為當(dāng)前待比較結(jié)點(diǎn)。while(pa!=null) 將la表的剩余部分鏈入結(jié)果表,并逆置。 1分 r=pa-next; pa-next=la-next; la-next=pa; pa=r; 1分while(pb!=null) r=pb-next; pb-next=la-next; la-next=pb; pb=r; return(la);2、(5分)編寫(xiě)一個(gè)函數(shù)判定兩棵二叉樹(shù)是否相似,所謂兩棵二叉樹(shù)p和q相似,即是要么它們都為空或都只有一個(gè)結(jié)點(diǎn),要么它們的左右子樹(shù)都相似。int Similar(BiTree p,q) /判斷二叉樹(shù)p和q是否相似 if(p=null & q=null) return (1); 1分elseif(!p & q |
溫馨提示
- 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶(hù)所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶(hù)上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶(hù)上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶(hù)因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 2025下半年廣東海珠區(qū)招聘事業(yè)單位人員筆試高頻重點(diǎn)提升(共500題)附帶答案詳解
- 2025下半年四川綿陽(yáng)經(jīng)開(kāi)區(qū)衛(wèi)生事業(yè)單位招聘12人高頻重點(diǎn)提升(共500題)附帶答案詳解
- 2025上海交通大學(xué)寧波人工智能研究院公開(kāi)招聘高層次人才1人高頻重點(diǎn)提升(共500題)附帶答案詳解
- 2025上半年江蘇省淮安事業(yè)單位招聘538人歷年高頻重點(diǎn)提升(共500題)附帶答案詳解
- 2025上半年山東高速建材集團(tuán)限公司社會(huì)招聘1人高頻重點(diǎn)提升(共500題)附帶答案詳解
- 2025上半年四川綿陽(yáng)涪城區(qū)事業(yè)單位公開(kāi)招聘152人歷年高頻重點(diǎn)提升(共500題)附帶答案詳解
- 2025上半年四川省廣安事業(yè)單位招聘考試工作高頻重點(diǎn)提升(共500題)附帶答案詳解
- 工業(yè)園區(qū)路面鋪設(shè)合同范本
- 地?zé)崮荛_(kāi)發(fā)勞務(wù)招標(biāo)文件
- 2024年私人借款清償協(xié)議版A版
- 工程力學(xué)智慧樹(shù)知到期末考試答案2024年
- 《瘋狂動(dòng)物城》全本臺(tái)詞中英文對(duì)照
- 年產(chǎn)2億袋板藍(lán)根顆粒劑車(chē)間工藝設(shè)計(jì)
- WEB開(kāi)發(fā)基礎(chǔ)-2021秋本-計(jì)算機(jī)科學(xué)與技術(shù)本復(fù)習(xí)資料-國(guó)家開(kāi)放大學(xué)2022年1月期末考試復(fù)習(xí)資料
- 基數(shù)詞-與序數(shù)詞PPT優(yōu)秀課件
- 雙壁波紋管出廠(chǎng)合格證(共4頁(yè))
- 學(xué)校校醫(yī)室常用藥物配備目錄及急救小常識(shí)
- 電子血壓計(jì)現(xiàn)況及發(fā)展前景的研究
- 鋼結(jié)構(gòu)專(zhuān)用超薄型防火漆檢驗(yàn)報(bào)告型式認(rèn)可證書(shū)
- 《小兒推拿》PPT課件(完整版)
- 硯北井田設(shè)計(jì)說(shuō)明書(shū)
評(píng)論
0/150
提交評(píng)論