華南理工大學(xué)考研真題-計算機專業(yè)綜合

朽木易折，金石可鏤。千里之行，始于足下。PAGE第頁/共頁更多考研資料，登陸1數(shù)據(jù)結(jié)構(gòu)選挑選題（每題惟獨一個答案準(zhǔn)確，每題2分，共26分）以下圖的講述中，準(zhǔn)確的是_______。A．圖與樹的區(qū)別在于圖的邊數(shù)大于或等于頂點數(shù)B．假設(shè)有圖G=(V,{E}),頂點集V’V，E’E，則V’和{E’}構(gòu)成G的子圖C．無向圖的連通分量指無向圖中的極大連通子圖D.圖的遍歷就是從圖中某一頂點出發(fā)訪遍圖中其余頂點下列判斷中，______是準(zhǔn)確的。A.深度為k的二叉樹最多有2k-1個結(jié)點(k≥1)，最少有k個結(jié)點二叉樹中不存在度大于2的結(jié)點對二叉樹遍歷是指先序、中序或后序遍歷中的一種構(gòu)造線索二叉樹是為能方便找到每個結(jié)點的雙親對各種內(nèi)部排序主意來說，__________。A.迅速排序時光性能最佳 B.基數(shù)排序和歸并排序是穩(wěn)定的排序主意C.迅速排序是一種挑選排序 D.堆排序所用的輔助空間比較大稀疏矩陣的三元組存儲主意_______。A．實現(xiàn)轉(zhuǎn)置運算很容易，只需將每個三元組中的行標(biāo)和列標(biāo)交換B．是一種鏈?zhǔn)酱鎯χ饕釩．矩陣的非零元個數(shù)和位置在操作過程中變化不大時較有效D．比十字鏈表法更高效對于二叉排序樹，下面的說法_______是準(zhǔn)確的。A．二叉排序樹是動態(tài)樹表，尋找不勝利時插入新結(jié)點時，會引起樹的重新分裂和組合B．對二叉排序樹舉行層序遍歷可得到有序序列C．用逐點插入法構(gòu)造二叉排序樹時，若先后插入的關(guān)鍵字有序，二叉排序樹的深度最大D．在二叉排序樹中舉行尋找，關(guān)鍵字的比較次數(shù)不超過結(jié)點數(shù)的1/2在構(gòu)造哈希表方面，下面的說法_________是準(zhǔn)確的。A．再哈希法在處理矛盾時不會產(chǎn)生聚攏B．哈希表的裝填因子越大說明空間利用率越好，因此應(yīng)使裝填因子盡量大C．哈希函數(shù)選的好可減少矛盾現(xiàn)象D．對任何詳細(xì)關(guān)鍵字集都不可能找到不產(chǎn)生矛盾的哈希函數(shù)已知廣義表((),(a),(b,c,(d),((d,f))))，則以下說法準(zhǔn)確的是__________。A．表長為3，表頭為空表，表尾為((a),(b,c,(d),((d,f))))B．表長為3，表頭為空表，表尾為(b,c,(d),((d,f)))C．表長為4，表頭為空表，表尾為((d,f))D．表長為3，表頭為，表尾為((a),(b,c,(d),((d,f))))已知一棵5階B樹有53個關(guān)鍵字，并且每個結(jié)點的關(guān)鍵字都達(dá)到最少狀態(tài)，則它的深度是________。A.3 B.4 C.5 D.6一個有向圖，共有n條弧，則所有頂點的度的總和為_______。A．2nB.nC.n-1D.n/2對鄰接表的講述中，_____是準(zhǔn)確的。A．無向圖的鄰接表中，第i個頂點的度為第i個鏈表中結(jié)點數(shù)的二倍B．鄰接表比鄰接矩陣的操作更簡便C．鄰接矩陣比鄰接表的操作更簡便D．求有向圖結(jié)點的度，必須遍歷囫圇鄰接表一棵二叉樹中序序列為FEABDC，后序序列為FBADCE，則層序序列為_____。A.ABCDEF B.EFCDBA C.FECDAB D.EFCDAB以下說法中，________是準(zhǔn)確的。A.徹低二叉樹中，葉結(jié)點的雙親的左兄弟（倘若存在）一定不是葉結(jié)點B.任何一棵二叉樹，終端結(jié)點數(shù)為度為2的結(jié)點數(shù)減1C.二叉樹不相宜用順序結(jié)構(gòu)存儲D.結(jié)點按層序編號的二叉樹，第i個結(jié)點的左孩子（倘若存在）的編號為2i給定一組關(guān)鍵字{4，26，46，12，9，33}，哈希函數(shù)為H(key)=keyMOD6，則用線性探測再散列主意來處理矛盾，則構(gòu)造此哈希表共需要比較關(guān)鍵字____次。A.4 B.5C.6D.7解答題（每題4分，共36分）線性表的雙向鏈表的存儲結(jié)構(gòu)為：typedefstructDNode{TEleminfo;structDNode*left;structDNode*right;};并假設(shè)已建立頭指針為head的雙向鏈表，p指向其中某個結(jié)點，寫一個程序段，從該循環(huán)鏈表中刪除p所指向結(jié)點的前一個結(jié)點(假設(shè)該結(jié)點存在)。簡述在AOV網(wǎng)中求拓?fù)渑判虻倪^程，并寫出下面AOV網(wǎng)中的兩個拓?fù)溆行蛐蛄小BDACEFGHIJ3.給出下面有向圖的鄰接矩陣、鄰接表及逆鄰接表。v1v4v1v4v3v2v54.假定字符集{a,b,c,d,e,f}中的字符在通信網(wǎng)絡(luò)中浮上的頻率見下表，請設(shè)計赫夫曼編碼。字符abcdef頻率55．對n個頂點的無向圖G，采用鄰接矩陣表示，如何判別下列問題；(1)圖中有多少條邊？(2)隨意兩個結(jié)點i和j是否有邊相連？(3)隨意一個頂點的度是多少？6．對下圖所示的AOE網(wǎng)，回答：工程完成的最短時光是多少？寫出關(guān)鍵路徑（不需過程），是否有某些活動提高速度后能導(dǎo)致囫圇工程縮短工期？v1v1v5v2v4v6v7v8v95622314134456v37.已知Q是一個非空隊列，S是一個空棧。僅用隊列和棧的ADT函數(shù)，用C語言偽碼編寫一個算法，將隊列Q中的所有元素逆置。棧的ADT函數(shù)有：

makeEmpty(stacks);

置空棧

push(stacks，datatypevalue);新元素value進(jìn)棧

datatypepop(stacks)

出棧，返回棧頂值

booleanisEmpty(stacks)

判?？辗?/p>

隊列的ADT函數(shù)有

enQueue(queueq,datatypevalue)元素value進(jìn)隊

datatypedeQueue(queueq)

出隊列，返回隊頭值

booleanisEmpty(queueq)

判隊列空否8．你所知道的排序主意有幾類？簡述各類主意的原理。9．在為一個實際應(yīng)用設(shè)計數(shù)據(jù)結(jié)構(gòu)時，主要應(yīng)考慮哪些方面的內(nèi)容？算法設(shè)計。做出簡要分析并寫函數(shù)。（共13分）以二叉鏈表作存儲結(jié)構(gòu)，試編寫非遞規(guī)的前序遍歷算法。(5分)2.無向圖用鄰接表存儲，寫出鄰接表定義，給出求圖中頂點Vi到Vj的最短路徑的函數(shù)。（8分）操作系統(tǒng)一、名詞解釋：（18分）進(jìn)程Spooling技術(shù)系統(tǒng)調(diào)用死鎖并發(fā)缺頁中斷二、有3個并發(fā)進(jìn)程R、M、P，它們分享同一個緩沖區(qū)，假定緩沖區(qū)只能存放一條記錄。進(jìn)程R負(fù)責(zé)從輸入設(shè)備讀信息，每讀入一個記錄后，就把它放進(jìn)緩沖區(qū)；進(jìn)程M在緩沖區(qū)中加工讀入的記錄；進(jìn)程P把加工后的記錄打印輸出。讀入的記錄經(jīng)加工輸出后，緩沖區(qū)又可以存放下一個記錄。試寫出他們能夠準(zhǔn)確執(zhí)行的并發(fā)程序。（10分）三、在某頁式管理系統(tǒng)中，假定主存為64K,分成16塊，塊號為0，1，2，…，15。設(shè)某進(jìn)程有４頁，其頁號為0，1，2，3，被分離裝入主存的第9、0、1、14塊。試問：（10分）該進(jìn)程的總長度是多大？寫出該進(jìn)程每一頁在主存中的起始地址。３）若給出邏輯地址［0，0］、［1，72］、［2，1023］、［3，99］，請計算出相應(yīng)的內(nèi)存地址。（方括號內(nèi)的第一個數(shù)為頁號，第二個數(shù)為頁內(nèi)地址，題目中的數(shù)字均為10進(jìn)制）。四、I/O控制可用哪幾種方式，各有什么優(yōu)缺點？（8分）五、某軟盤有40個磁道，磁頭從一個磁道移到另一個磁道需要6ms。文件在磁盤上非延續(xù)存放，邏輯上相鄰的數(shù)據(jù)塊的平均距離為13個磁道，每塊的旋轉(zhuǎn)延遲時光及傳輸時光分離為100ms和25ms。問：（8分）讀取一個100塊的文件需要多少時光？倘若對磁盤舉行收拾使得同一文件的磁盤塊盡可能靠攏，從而使邏輯上相鄰的數(shù)據(jù)塊的平均距離降為2個磁道，這時讀取100塊的文件有需要多少時光？六、兩個進(jìn)程A和B，每一個進(jìn)程都需要讀取數(shù)據(jù)庫中的記錄1、2、3倘若這兩個進(jìn)程都以1、2、3的次序哀求讀取記