2018北京化工大學數據結構碩士研究生考試真題

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

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

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

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