考研年院計(jì)算機(jī)軟件基礎(chǔ)試題

中國(guó)2007年招收攻讀入學(xué)統(tǒng)一考試試題考生須數(shù)據(jù)結(jié)構(gòu)部分（70一、選擇題（101分 A．O(n) B．O(n) C．O(1) D．O(1)2、對(duì)于一個(gè)頭指針為head的結(jié)點(diǎn)的單鏈表，判斷該表為空的條件是（ 3p所指的結(jié)點(diǎn)時(shí)需要修改指針（。A．pllinkrlink=prlink；prlinkllink=pllinkB．pllink=pllinkllink；pllinkrlink=p A．i-j- D．不確5、若度為m的樹(shù)中，其葉結(jié)點(diǎn)個(gè)數(shù)為n，則非葉結(jié)點(diǎn)的個(gè)數(shù)為 A．n- 6ABCDEFG，它的中序遍歷序列可能是（ 7、一棵左右都不空的二叉樹(shù)序線索化后，其中空的鏈域的個(gè)數(shù)為（ D．不確是（。A．二叉排序 B．Huffman C． Ｄ．二叉平衡 10要求在(nlog2 ) 的時(shí)間內(nèi)完成對(duì)數(shù)組的排序，且要求排序是穩(wěn)定的，則可選擇排序方法是（ 。A．快速排 B．堆排 Ｄ．直接插入排二、填空題（101分1、若對(duì)n階對(duì)稱矩陣A以行序?yàn)橹鲗⑵湎氯切蔚脑兀òㄖ鲗?duì)角線上的元素）依次存放于一維數(shù)組B[1..n(n+1)/2]中則A中的任一元素j1ijn在B中的位置 2節(jié)點(diǎn)的雙循環(huán)鏈表L中只有一個(gè)元素節(jié)點(diǎn)的條件 以 3、如果在105個(gè)記錄中找出兩個(gè)最小的記錄，為了找出最小的記錄一般需要比較（）次， 5、在完全二叉樹(shù)中，編號(hào)為i和j的兩個(gè)結(jié)點(diǎn)處于同一層的條件是（ 6設(shè)Q[0…N-1]為循環(huán)隊(duì)列其頭尾指針?lè)謩e為P和R則隊(duì)列Q中當(dāng)前元素個(gè)數(shù) 三、問(wèn)答題（4020分 a1,n 0 A

,

0

0 an,nAaij的下標(biāo)(i，j)B中下標(biāo)k下標(biāo)(i，j)定位B中元素的位置。四、寫(xiě)算法（10分編譯原理部分（40分一、選擇題（102分 編譯 D．匯編 A．SLR(1) B．LR(1)C．SLR(1) D．無(wú)二義文法 A．( C． （ 均不能以0開(kāi)頭)2（4分）C語(yǔ)言程序sizeof（求字節(jié)數(shù)運(yùn)算符）時(shí)，該運(yùn)算是在編譯程序時(shí)完成，還1123456789五、(8試為控制流語(yǔ)句：SifEthenS1elseS2|whileEdoS1寫(xiě)出相應(yīng)的語(yǔ)法制導(dǎo)定操作系統(tǒng)部分（40一、填空題（102分 二、簡(jiǎn)答題（164分3、在一個(gè)請(qǐng)求分頁(yè)系統(tǒng)中，CPUI/O設(shè)備，在基于時(shí)間的標(biāo)準(zhǔn)下，其20%，97%，5%。分析系統(tǒng)，說(shuō)明下列哪些辦法可以提高CPU的利用率：換一個(gè)更快的換一個(gè)更大的外減少多道程加大主換更快的外存，或者用磁4、有以下四種I/O設(shè)備應(yīng)用場(chǎng)景：機(jī)器人的傳感器，，普通電腦光驅(qū)，鍵盤(pán)。設(shè)計(jì)景中的I/O問(wèn)題。三、綜合題（147分1、在UNIX系統(tǒng)中，進(jìn)程有哪