打印整理2010年全國(guó)研究生入學(xué)統(tǒng)一考試計(jì)算機(jī)學(xué)科專業(yè)基礎(chǔ)綜合.doc

打印整理2010年全國(guó)研究生入學(xué)統(tǒng)一考試計(jì)算機(jī)學(xué)科專業(yè)基礎(chǔ)綜合 ，打印整理2010年全國(guó)研究生入學(xué)統(tǒng)一考試計(jì)算機(jī)學(xué)科專業(yè)基礎(chǔ)綜合。
歡迎下載！
2010年全國(guó)研究生入學(xué)統(tǒng)一考試計(jì)算機(jī)學(xué)科專業(yè)基礎(chǔ)綜合
一、單項(xiàng)選擇題1.【正確選項(xiàng)】 D【解析】本題考查棧的基本概念。
快速解題：選項(xiàng)所給序列中出現(xiàn)長(zhǎng)度大于等于3的連續(xù)逆序 子序列，即為不符合要求的出棧序列。
四個(gè)選項(xiàng)所給序列的進(jìn)出棧操作序列分別為： A.Push,Push,Push,Push,Pop,Pop,Push,Pop,Pop,Push,Pop,Pop; B.Push,Push,Push,Pop,Pop,Push,Pop,Pop,Push,Pop,Push,Pop; C.Push,Push,Pop,Push,Pop,Pop,Push,Push,Pop,Push,Pop,Pop; D.Push,Pop,Push,Push,Push,Push,Push,Pop,Pop,Pop,Pop,Pop; 按照題設(shè)要求，選項(xiàng)D所給序列即為不可能得到的出棧順序。
2.【正確選項(xiàng)】 C【解析】本題考查隊(duì)列的基本概念。
快速解題：無(wú)論哪種入隊(duì)序列，a和b都應(yīng)該相鄰，這是出 隊(duì)序列合理的必要條件。
只有選項(xiàng)C所給序列中a與b不相鄰，可以確定正確選項(xiàng)為C。
四個(gè)選 項(xiàng)所給序列的進(jìn)隊(duì)操作序列分別為（L代表左入，R代表右入）：A.aL(或aR),bL,cR,dR,eR B.aL(或aR),bL,cR,dL,eRC.不可能出現(xiàn)D.aL(或aR),bL,cR,dR,eL 3.【正確選項(xiàng)】 D【解析】本題考查線索二叉樹(shù)的基本概念和構(gòu)造。
線索二叉樹(shù)利用二叉鏈表的空鏈域來(lái)存放 結(jié)點(diǎn)的前驅(qū)和后繼信息。
題中所給二叉樹(shù)的后序序列為dbca 。
結(jié)點(diǎn)d無(wú)前驅(qū)和左子樹(shù)，左鏈域空，無(wú)右子樹(shù)，右鏈域指向其后繼結(jié)點(diǎn)b；結(jié)點(diǎn)b無(wú)左子樹(shù)，左 鏈域指向其前驅(qū)結(jié)點(diǎn)d；結(jié)點(diǎn)c無(wú)左子樹(shù)，左鏈域指向其前驅(qū)結(jié)點(diǎn)b，無(wú)右子樹(shù)，右鏈域指向其 后繼結(jié)點(diǎn)a。
正確選項(xiàng)為D。
4.【正確選項(xiàng)】 C【解析】本題考查平衡二叉樹(shù)。
1插入48以后，該二叉樹(shù)根結(jié)點(diǎn)的平衡因子由-1變?yōu)? 2，失去平衡，需進(jìn)行兩次旋轉(zhuǎn)（先右旋后左旋）操作，如下所示：（圖略） 5.【正確選項(xiàng)】 B【解析】本題考查樹(shù)的基本概念