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

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

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

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

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