2016年山東青島大學(xué)數(shù)據(jù)結(jié)構(gòu)考研真題

》》》》》》2023年整理歷年要考研試題資料《《《《《《》》》》》》2023年整理歷年要考研試題資料《《《《《《/》》》》》》2023年整理歷年要考研試題資料《《《《《《2016年山東青島大學(xué)數(shù)據(jù)結(jié)構(gòu)考研真題一、單項(xiàng)選擇題（本大題共10道小題，每小題2分，共20分）1．一個(gè)算法具有（）等特點(diǎn)。A．快速性B．至少有一個(gè)輸入量C．確定性D．健壯性2．下列函數(shù)中漸近時(shí)間復(fù)雜度T(n)最小的是（）。A．T(n)=B．T(n)=C．T(n)=D．T(n)=3．在計(jì)算機(jī)的存儲(chǔ)器中表示時(shí)，物理地址和邏輯地址相同并且是連續(xù)的，稱之為（）。A．邏輯結(jié)構(gòu)B．順序存儲(chǔ)結(jié)構(gòu)C．鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)D．以上都對(duì)4．若讓元素1，2，3，4，5依次進(jìn)棧，則出棧次序不可能出現(xiàn)在（）種情況。A．5，4，3，2，1B．2，1，5，4，3C．4，3，1，2，5D．2，3，5，4，15．設(shè)棧S用順序存儲(chǔ)結(jié)構(gòu)表示，則棧S為空的條件是（）。A．S.top-S.base!=0B．S.top-S.base==0C．S.top-S.base!=nD．S.top-S.base==n6．一棵完全二叉樹上有1001個(gè)結(jié)點(diǎn)，其中葉子結(jié)點(diǎn)的個(gè)數(shù)是（）。A．500B．501C．250D．2517．任何一棵二叉樹的葉子結(jié)點(diǎn)在先序、中序和后序遍歷中的相對(duì)次序（）。A．不發(fā)生改變B．發(fā)生改變C．不能確定D．以上都不對(duì)8．用鄰接表表示圖進(jìn)行廣度優(yōu)先遍歷時(shí)，通常借助（）來實(shí)現(xiàn)算法。A．棧B.隊(duì)列C.樹D．圖9．折半查找法和二叉排序樹的時(shí)間性能（）。A．與處理數(shù)據(jù)量有關(guān)B．相同C．不相同D．不確定10．對(duì)n個(gè)不同的關(guān)鍵字由小到大進(jìn)行冒泡排序，在下列（）情況下比較的次數(shù)最多。A．從小到大排列好的B．從大到小排列好的C．元素?zé)o序D．元素基本有序二、簡(jiǎn)答題（本大題共6道小題，每題5分，共30分）1．一般情況下，線性表可以采用哪幾種存儲(chǔ)結(jié)構(gòu)？請(qǐng)分別敘述每一種存儲(chǔ)結(jié)構(gòu)的構(gòu)造原理與特點(diǎn)。2．內(nèi)存中一片連續(xù)空間（不妨假設(shè)地址從0到m-1）提供給兩個(gè)棧S1與S2使用，怎樣分配這部分存儲(chǔ)空間，使得對(duì)任一個(gè)棧僅當(dāng)這部分空間全滿時(shí)才發(fā)生上溢。3．簡(jiǎn)述遍歷二叉樹的含義及常見的方法。4．簡(jiǎn)要說明圖的鄰接表的構(gòu)成。5．簡(jiǎn)述二叉排序樹的插入算法思想（步驟）。6．簡(jiǎn)要說明快速排序的基本思想。三、綜合應(yīng)用題（本大題共5道小題，每題10分，共50分）1．給定二叉樹的先序遍歷序列和后序遍歷序列，能否重構(gòu)該二叉樹？若能，試證明之，否則給出反例。2．有4個(gè)頂點(diǎn)A、B、C、D的無向連通圖。按廣度優(yōu)先和深度優(yōu)先搜索遍歷結(jié)果都為A、B、C、D，畫出所有可能的結(jié)構(gòu)圖。3．設(shè)有一組關(guān)鍵字{17，13，14，153，29，35}需插入到表長(zhǎng)為12的Hash表中，請(qǐng)回答以下問題：(1)設(shè)計(jì)一個(gè)適合該Hash表的Hash函數(shù)；(2)使用你所設(shè)計(jì)的Hash函數(shù)將上述關(guān)鍵字插入到Hash表中，畫出其結(jié)構(gòu)（使用線性探測(cè)法解決沖突）。4．某整型數(shù)組A的10個(gè)元素值依次為：{6、2、9、7、3、8、4、5、0、10}，用下列各排序方法，將A中元素由小到大排序。(1)取第一個(gè)元素6作為樞軸，試寫出快速排序第一趟排序的結(jié)果。(2)用堆排序（用大根堆，即堆頂元素取最大值），試寫出將第一個(gè)選出的數(shù)據(jù)放在A的最后位置上，將A調(diào)整成堆后的A中結(jié)果。5．已知信息為“OPQRPQRQPRPOQP”，請(qǐng)按此信息構(gòu)造哈夫曼樹，求出每個(gè)字符的最優(yōu)編碼。四、算法分析題（本大題共3道小題，每題10分，共30分）1．下面的算法是對(duì)在順序線性表L的第i個(gè)元素之前插入新的元素e，請(qǐng)?jiān)诳瞻滋幪钊胝_的語(yǔ)句。

2．閱讀下面的代碼，試說明算法的功能。

3．對(duì)于給定的二叉排序樹T，對(duì)于給出的正整數(shù)x，下面算法實(shí)現(xiàn)了將data域之值小于等于x的結(jié)點(diǎn)全部刪除掉。請(qǐng)?jiān)诳瞻滋幪钊胝_的語(yǔ)句。五、算法設(shè)計(jì)題（本大題共2道小題，每題10分，共20分）1．將一帶頭結(jié)點(diǎn)的單鏈表hea