2010深圳大學(xué)專插本計算機科學(xué)與技術(shù)專業(yè)試題

1、2010年深大計算機組成原理（回憶版）一、填空題（10個空）1 .組成計算機的5個組成基本部件；2 .主儲存器的三個主要性能指標(biāo)；3 .浮點數(shù)加減運算的五個步驟；4 .三級存儲器結(jié)構(gòu)；5 .DMAE種工作方式；6 .五種數(shù)據(jù)傳送控制方式；小結(jié)A:以上從我腦海挖出大概，希望對大家有幫助。還有感覺我寫過一個填高速緩沖存儲器，哈哈?？傮w感覺比較簡單，我只有一個填空不確定。其實你可以上題目看到出得不會很難，要懂得歸納重點知識（報考時每一科目我都準(zhǔn)備一小本來歸納重要知識點和提綱），所以復(fù)習(xí)全面，我的意思至少看書兩三遍，應(yīng)該沒什么問題。二、選擇題一共10題，題字?jǐn)?shù)的特點就是很短、不多，不會冗長。最后選擇題

2、弄得我頭緒很亂，就是有幾個選項不確定。大概考了（我寫出可能類似題目，以此題目自己擴展）定點小數(shù)不定范圍；動態(tài)存儲器器件與靜態(tài)存儲器器件的比較與區(qū)別；虛擬存儲器概念等等。二、計算題1 .用補碼一位乘法Booth算法（其他要掌握加減乘除算法）2 .計算虛擬地址和物理地、頁表長度是多少？具體題目見計算機構(gòu)成與組成（第4版）P260題7.10小結(jié)B:可以看出做一做書后練習(xí)題，選擇做基礎(chǔ)的基本的題目，因為課后練習(xí)題有寫題目有點難。四、名詞解釋1 .控制存儲器2 .水平型微指令3 .微指令、微操作、微程序（印象考了其中一個）小結(jié)C:自己要懂得歸納每章主要的知識點，重點詞匯。最后兩個我是模棱兩可的大概的寫上

3、去，我的意思盡量憑自己理解答上去，不要空著。最后兩題好像不像提綱給例題，還是我記得不太清楚。五.綜合題1 .中斷請求排隊邏輯（考查詢法、串行排隊鏈法內(nèi)容，還要求畫圖，有2小題）具體參考書上P338339,還有課外書力推計算機組成原理習(xí)題與解析（徐愛萍）。嘻嘻，我發(fā)現(xiàn)很多題目跟這本書一模一樣。2 .中斷處理過程（這題太簡單，哈哈）總結(jié)：本人用了兩個星期看計算機組成原理，然后寒假又認(rèn)真學(xué)習(xí)幾遍。課本和計算機組成原理習(xí)題與解析（徐愛萍）相結(jié)合學(xué)習(xí)（還有其他課外書，這些書都是圖書館借來的，但是用的最多也是這本書），學(xué)習(xí)與復(fù)習(xí)要點是對照提綱（汗！深大出的提綱讓人難以理解，什么是要掌握，什么是了解，都是模

4、棱兩可,我想偷懶都不行。）總結(jié)本章主要知識點，寫在筆記本上。從試題看總體難度不會很深，要牢固知識點。2010年數(shù)據(jù)結(jié)構(gòu)深大題目（回憶版）題目類型不像以往出10個簡答題，當(dāng)時看到有填空題就傻了眼（最后冷靜下來還是可以做的，>.<|）一、填空題.1 .給個程序計算時間復(fù)雜度；2 .考隊的知識，列出一些條件，寫出循環(huán)隊結(jié)束條件。3 .記不清是二叉樹或圖的遍歷算法，例如告訴你元素之間關(guān)系，然后寫出其中一個（先、中、后）遍歷次序。以下題目6個簡答題（包括題中小題目），最后一道是寫程序（這個忘了，我也沒有寫，其實我知道我一定不會寫，哈）。二、簡答題1 .赫夫曼算法（今年考具體看數(shù)據(jù)結(jié)構(gòu)c語言版

5、嚴(yán)蔚敏P148例6-2）2 .哈希算法與解決沖突（1）開放定址法（2）拉鏈地址法3 .最小生成樹（普里姆prim）4 .最短路徑（迪杰斯特拉Dijkstra）5 .希爾排序算法6 .快速排序算法（包括計算平均查找長度）7 .歸并排序算法8 .關(guān)鍵路徑（搞清楚最早發(fā)生時間、最遲發(fā)生時間、最早開始時間和最早開始時間）9 .二叉排序樹的插入和刪除小結(jié)：以上排序不分先后，主要要理解算法，推薦網(wǎng)上找清華大學(xué)嚴(yán)蔚敏教學(xué)視頻，還有書上有例題可以理解后試試自己做一下，當(dāng)然不缺少課外輔導(dǎo)書，推薦數(shù)據(jù)結(jié)構(gòu)習(xí)題與解析李春葆里面有許多例題多做?！巨D(zhuǎn)】2008年深大數(shù)據(jù)結(jié)構(gòu)一共有10道大題。1 .二叉樹的中序遍歷順序（

6、只要寫出順序就行，不用寫算法，但算法也是要理解了才寫得出來）2 .構(gòu)造huffman樹（畫出一棵樹就行了，這題是不應(yīng)該扣分的）3 .二叉排序數(shù)的遍歷與結(jié)點刪除（寫出遍歷的順序和刪除后的二叉排序數(shù)）4 .哈稀表，解決沖突的算法；（這題我沒做，有12分，可惜了！，有好幾種解決沖突的算法，建議都要掌握，必考?。。? .排序（歸并排序，堆排序），每趟的排序結(jié)果；（只要寫出每趟的排序結(jié)果，重要啊，算法一定要理解才行，雖然這里不用寫具體算法。）6 .鄰接表的拓?fù)渑判蚪Y(jié)果；（寫出拓?fù)渑判虻慕Y(jié)果，拓?fù)渑判虻乃惴≒181）7 .最短路徑問題（這題具體怎樣就不記得了，自己看看書吧！離散數(shù)學(xué)那本書也有得說。）以下是

7、算法設(shè)計題：8 .將一數(shù)值插入到數(shù)組中9 .字符用模式匹配算法（課本P79,這個無論如何都要記下來，不只一年出了這道題）10 .求鄰接表入度的算法小結(jié)：感謝2008年師兄提高數(shù)據(jù)結(jié)構(gòu)回憶版，其實對于數(shù)據(jù)結(jié)構(gòu)試題深大并沒有給出，其實很郁悶，郁悶的是怎樣去考試，因為不知道他要怎樣考，如何掌握考試的“度”？所以我在百度苦苦地尋找。這些對我的備考很大幫助。這是學(xué)校內(nèi)師兄給的，但是不知道哪年的題目，大概是06、07年的題目吧。數(shù)據(jù)結(jié)構(gòu)：十幾道題，全是解答題，沒考填空跟選擇，跟研究生題型差不多難度也差不多（網(wǎng)上有得下），當(dāng)然難度難的比它低，考試范圍也沒那么廣，跟師兄說的去年所考題型不同，跟廣大的也不同。內(nèi)

8、容考了二叉排序樹建樹，二插歸并排序，堆排序過程，最短路徑拓?fù)渑判?，哈希排序（除余?shù)法，沖突線性探測再散列跟拉鏈法兩種）還有幾題忘了，最后兩道是要寫出代碼的，一道是模式匹配算法index,一道是輸出圖的入度?？傮w而言難度不是很大，如果方向正確跟復(fù)習(xí)到位，可以拿高分，可惜我復(fù)習(xí)方向不正確。這個深大專業(yè)網(wǎng)頁（類似精品課程）上找，這資料【贊】一、寫函數(shù)voidDelData(inta,intN),刪除有序表a中多余的相同元素。其中N為元素個數(shù)2007-09-18。intaN;voidDelData(inta,intN)inti,j;for(i=0,j=0;j<N;i+,j+)if(i<j)

9、ai=aj;while(ai=aj+1)j+;ai=aj;二、現(xiàn)有模式串a(chǎn)babaabbab,求其next值。請寫出每個next值的求取過程2007-09-27解：求nextj值的算法、j的初值為1,next1=0,i=0、While(j<模式串長度) .若i=0或者Ti=Tj,則i+,j+,nextj=i .否則，i=nexti設(shè)ababaabbab的次序為：12345678910則next(1)=0;next(2)=1;next(3)=1;因為P2=b!=Pnext(2)=P1=anext(4)=2;因為P3=a=Pnext(3)=P1=anext(5)=3;因為P4=b=Pnext

10、(4)=P2=bnext(6)=4;因為P5=a=Pnext(5)=P3=anext(7)=2;因為P6=a!=Pnext(6)=P4=b且!=Pnext(4)=P2=b且!=Pnext(2)=P1=anext(8)=3;因為P7=b=Pnext(7)=P2=bnext(9)=1;因為P8=b!=Pnext(8)=P3=a且!=Pnext(3)=P1=anext(10)=2;因為P9=b=Pnext(9)=P1=a、假設(shè)字符a,b,c,d,e的頻度分別為34%,14%,25%,12%,15%,計算Huffman編碼（要求Huffman樹的右子樹小于左子樹）.2007-10-16解：a: 00b

11、: 010c: 10d: 011e: 11四、請采用普里姆（Prim）算法（從頂點1開始）和克魯斯卡爾（Kruskal）算法分別生成下圖的最小生成樹（請畫出每一步的過程）。2007-10-25解：1、普里姆（Prim）算法是從指定點開始，連通分量不斷增長的過程其中：（4,5）和（4,6）兩條邊權(quán)值相等，因此哪個先做都可以。2、克魯斯卡爾（Kruskal）算法是從最小的邊開始，不斷將兩個連通分量變成一個連通分量的過程其中：（4,5）,（4,6）,（1,3）三條邊權(quán)值都為1,因此哪個先做都可以；然后，再做（2,4）,（1,4）兩條邊，當(dāng)然這兩條邊權(quán)值也相等，因此，哪個先做都可以。五.有向網(wǎng)N=V,

12、E,V=0,1,2,3,4,E=<0,1,1>,<0,3,3>,<0,4,10>,<1,2,5>,<2,4,1>,<3,2,2>,<3,4,6>,E中每個元組的第三個元素表示權(quán)。、畫出該網(wǎng)。、用Dijkstra算法求最短路徑，寫出頂點0到其它各頂點的最短路徑長度、路徑及產(chǎn)生過程。、求關(guān)鍵路徑，寫出計算過程。2007-11-01解：、有向網(wǎng)N如右圖所示Di10,1OO60,1,250,3,230,330,3100,4100,1090,3,460,3,2,40,10,1,30,1,3,20,1,3,2,4、用Dij

13、kstra算法求最短路徑過程如下1234S、關(guān)鍵路徑求解過程如下先求出拓?fù)渑判驗椋?,1,3,2,400011426933441010VEiVLi最短路徑<0,1><0,3><0,4><1,2><2,4><3,2><3,4>03010014693734EiLi由上表可以看出，只有弧<0,4>（即活動）的關(guān)鍵路徑E和L相等（皆為0）,因此,弧<0,4>是六.畫出在初始為空的AVL樹中依次插入2,1,3,5,8,4,7,6并在有“旋轉(zhuǎn)”時說出“旋轉(zhuǎn)”的類型。2007-11-13時該樹的生長全

14、過程,解:、七、假設(shè)關(guān)鍵字輸入順序為5,55,67,21,44,12,3,53,23,已知散列函數(shù)為：H（Key）=Key%11、用拉鏈法解決沖突，畫出插入所有關(guān)鍵字后的鏈表結(jié)構(gòu)（假設(shè)鏈表頭插入）。、計算該表查找成功的平均查找長度（ASD。2007-11-22012345678910、ASL=(1/9)X(1X6+2X2+3X1)=13/9八、分別用直接插入排序、起泡排序、快速排序、堆排序、歸并排序、鏈?zhǔn)交鶖?shù)排序算法對整數(shù)序列43,17,12,8,70,89,75,65,77,9進(jìn)行升序排序，、寫出直接插入排序、起泡排序、歸并排序每一趟的排序結(jié)果；、寫出快速排序第一趟的排序結(jié)果；、寫出堆排序建

15、初始堆和輸出最大兩個關(guān)鍵字記錄的排序過程；、寫出鏈?zhǔn)交鶖?shù)排序的每一趟分配和收集的結(jié)果。2007-12-11解：1、直接插入排序43,17,12,8,70,89,75,65,77,943,17,12,8,70,89,75,65,77,917,43,12,8,70,89,75,65,77,912,17,43,8,70,89,75,65,77,98,12,17,43,70,89,75,65,77,98,12,17,43,70,89,75,65,77,98,12,17,43,70,89,75,65,77,98,12,17,43,70,75,89,65,77,98,12,17,43,65,70,75,8

16、9,77,98,12,17,43,65,70,75,77,89,98,9,12,17,43,65,70,75,77,892、起泡排序43,17,12,8,70,89,75,65,77,917,12,8,43,70,75,65,77,9,8912,8,17,43,70,65,75,9,77,898,12,17,43,65,70,9,75,77,898,12,17,43,65,9,70,75,77,898,12,17,43,9,65,70,75,77,898,12,17,9,43,65,70,75,77,898,12,9,17,43,65,70,75,77,898,9,12,17,43,65,70

17、,75,77,898,9,12,17,43,65,70,75,77,898,9,12,17,43,65,70,75,77,89歸并排序43,17,12,8,70,89,75,65,77,917,43,8,12,70,89,65,75,9,778,12,17,43,65,70,75,89,9,778,12,17,43,65,70,75,89,9,778,9,12,17,43,65,70,75,77,894、快速排序第一趟的排序結(jié)果4317127089756577取pivotkey=4317127089756577highlow9與pivotkey（43）交換之后，low+,且向右比較1712畢l

18、ow89756577high70與pivotkey（43）交換之后,high-,且向左比較171289756577highlowpivotkey(43)放到low,high指向的位置17128975657770lowhigh43快速排序第一趟結(jié)束。5、堆排序建初始堆先將序列43,17,12,8,70,從70開始做篩選，由于70>9,因此，完全二叉樹沒有變化。從8開始做篩選，由于77>65>8,因此，77代替8,得：17122010年5月9日母親節(jié)快樂（77）70897565從12開始做篩選,由于89>75>12,從17開始做篩選，由于77>70>70,因此，77代替17,由于65>17>8,因此，65代替17,得：從43開始做篩選，由于89>77>43,因此，89代替43,由于75>43>12,因此，75代替43,得：輸出最大值89,將9放到根上，由于77>7