2019年北京化工大學(xué)842數(shù)據(jù)結(jié)構(gòu)考研考試樣題

1、第1頁(yè)共8頁(yè)北京化工大學(xué)北京化工大學(xué)2XXX年攻讀碩士學(xué)位研究生入學(xué)考試年攻讀碩士學(xué)位研究生入學(xué)考試數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)試題試題注意事項(xiàng)注意事項(xiàng)1.答案必須寫在答題紙上，寫在試卷上均不給分。2.答題時(shí)可不抄題，但必須寫清題號(hào)。3.答題必須用藍(lán)、黑墨水筆或圓珠筆，用紅色筆或鉛筆均不給分。一、單項(xiàng)選擇題：1~40小題，每小題2分，共80分。下列每題給出的選項(xiàng)中，只有一個(gè)選項(xiàng)是最符合題目要求的。請(qǐng)?jiān)诖痤}卡上將所選項(xiàng)的字母涂黑。1.設(shè)n是描述問題規(guī)

2、模的非負(fù)整數(shù)，下面程序片段的時(shí)間復(fù)雜度是x=2while(xn2)x=2xA.O(log2n)B.O(n)C.O(nlog2n)D.O(n2)2.設(shè)棧S和隊(duì)列Q的初始狀態(tài)均為空，元素abcdefg依次進(jìn)入棧S。若每個(gè)元素出棧后立即進(jìn)入隊(duì)列Q，且7個(gè)元素出隊(duì)的順序是bdcfeag，則棧S的容量至少是A.1B.2C.3D.43.若元素abcdef依次進(jìn)棧，允許進(jìn)棧、退棧操作交替進(jìn)行。但不允許連續(xù)三次進(jìn)行退棧工作，則不可能得到的出棧序列是A：

3、dcebfaB：cbdaefC：dbcaefD：afedcb4.某隊(duì)列允許在其兩端進(jìn)行入隊(duì)操作，但僅允許在一端進(jìn)行出隊(duì)操作，則不可能得到的順序是A：bacdeB：dbaceC：dbcaeD：ecbad5.元素abcde依次進(jìn)入初始為空的棧中，若元素進(jìn)棧后可停留、可出棧，直到所有元素都出棧，則在所有可能的出棧序列中，以第3頁(yè)共8頁(yè)父結(jié)點(diǎn)的父結(jié)點(diǎn)，則在原來的森林中，u和v可能具有的關(guān)系是I父子關(guān)系II.兄弟關(guān)系III.u的父結(jié)點(diǎn)與v的父結(jié)點(diǎn)

4、是兄弟關(guān)系A(chǔ).只有IIB.I和IIC.I和IIID.I、II和III11.下列線索二叉樹中（用虛線表示線索），符合后序線索樹定義的是12.在下列所示的平衡二叉樹中插入關(guān)鍵字48后得到一棵新平衡二叉樹，在新平衡二叉樹中，關(guān)鍵字37所在結(jié)點(diǎn)的左、右子結(jié)點(diǎn)中保存的關(guān)鍵字分別是A：13，48B：24，48C：24，53D：24，9013.在一棵度為4的樹T中，若有20個(gè)度為4的結(jié)點(diǎn)，10個(gè)度為3的結(jié)點(diǎn)，1個(gè)度為2的結(jié)點(diǎn)，10個(gè)度為1的結(jié)點(diǎn)，則樹