計算機考研真題數(shù)據(jù)結(jié)構(gòu)

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

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

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

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