1、2009年統(tǒng)考計算機考研真題一單項選擇題一單項選擇題1.為解決計算機與打印機之間速度不匹配的問題，通常設置一個打印數據緩沖區(qū)，主機將要輸出的數據依次寫入該緩沖區(qū)，而打印機則依次從該緩沖區(qū)中取出數據。該緩沖區(qū)的邏輯結構應該是A.棧B.隊列C.樹D.圖2.設棧S和隊列Q的初始狀態(tài)均為空，元素abcdefg依次進入棧S。若每個元素出棧后立即進入隊列Q，且7個元素出隊的順序是bdcfeag，則棧S的容量至少是A1B.2C.3D.43.給定二叉樹

2、圖所示。設N代表二叉樹的根，L代表根結點的左子樹，R代表根結點的右子樹。若遍歷后的結點序列為3，1，7，5，6，2，4，則其遍歷方式是ALRNB.NRLC.RLND.RNL4.下列二叉排序樹中，滿足平衡二叉樹定義的是5.已知一棵完全二叉樹的第6層（設根為第1層）有8個葉結點，則完全二叉樹的結點個數最多是A39B.52C.111D.1196.將森林轉換為對應的二叉樹，若在二叉樹中，結點u是結點v的父結點的父結點，則在原來的森林中，u和v可

3、能具有的關系是I父子關系II.兄弟關系III.u的父結點與v的父結點是兄弟關系A.只有IIB.I和IIC.I和IIID.I、II和III7.下列關于無向連通圖特性的敘述中，正確的是I所有頂點的度之和為偶數II.邊數大于頂點個數減1III.至少有一個頂點的度為1A.只有IB.只有IIC.I和IID.I和III8.下列敘述中，不符合m階B樹定義要求的是A根節(jié)點最多有m棵子樹B.所有葉結點都在同一層上41.該方法求得的路徑不一定是最短路徑。例

4、如，對于下圖所示的帶權圖，如果按照題中的原則，從A到C的最短路徑為A→B→C，事實上其最短路徑為A→D→C。42.（1）算法基本思想如下：從頭至尾遍歷單鏈表，并用指針P指向當前節(jié)點的前K個節(jié)點。當遍歷到鏈表的最后一個節(jié)點時，指針P所指向的節(jié)點即為所查找的節(jié)點。（2）詳細實現步驟：增加兩個指針變量和一個整型變量，從鏈表頭向后遍歷，其中指針P1指向當前遍歷的節(jié)點，指針P指向P1所指向節(jié)點的前K個節(jié)點，如果P1之前沒有K個節(jié)點，那么P指向表頭