》》》》》》2023年整理歷年要考研試題資料《《《《《《》》》》》》2023年整理歷年要考研試題資料《《《《《《/》》》》》》2023年整理歷年要考研試題資料《《《《《《2017年山東煙臺(tái)大學(xué)數(shù)據(jù)結(jié)構(gòu)考研真題一、單項(xiàng)選擇題(本大題共20小題，每小題2分，共計(jì)40分)1.數(shù)據(jù)結(jié)構(gòu)被形式的定義為(D,R),其中D是數(shù)據(jù)元素的有限集合，R是D上（）的有限集合。A.操作B.映象C.存儲(chǔ)D.關(guān)系2.下面關(guān)于算法說法錯(cuò)誤的是（）。A.算法最終必須由計(jì)算機(jī)程序?qū)崿F(xiàn)B.為解決某問題的算法同為該問題編寫的程序含義是相同的C.算法的可行性是指指令不能有二義性D.以上幾個(gè)都是錯(cuò)誤的3.線性表采用鏈?zhǔn)酱鎯?chǔ)時(shí)，其地址（）。A.必須是連續(xù)的 B.部分地址必須是連續(xù)的C.一定是連續(xù)的 D.連續(xù)與否均可4.在含有n個(gè)結(jié)點(diǎn)的順序存儲(chǔ)的線性表中，刪除一個(gè)結(jié)點(diǎn)所需移動(dòng)結(jié)點(diǎn)的平均次數(shù)為（）。A.nB.n/2C.(n-1)/2D.(n+1)/25.對(duì)于一個(gè)頭指針為head的帶頭結(jié)點(diǎn)的單鏈表，判定該表為空表的條件是（）。A.head==NULLB.head→next==NULLC.head→next==headD.head!=NULL6.若一個(gè)棧的輸入序列為1,2,3,…,n,輸出序列的第一個(gè)元素是i,則第j個(gè)輸出元素是（）。A.i-j-1B.i-jC.j-i+1D.不確定的7.順序存儲(chǔ)的循環(huán)隊(duì)列，存儲(chǔ)空間大小為n,隊(duì)頭結(jié)點(diǎn)下標(biāo)為front,隊(duì)尾結(jié)點(diǎn)下標(biāo)為rear。則此循環(huán)隊(duì)列中的元素個(gè)數(shù)為（）。A.n+front-rear B.rear-front+1C.(rear-front)%n D.(n+rear-front+1)%n8.判斷一個(gè)表達(dá)式中左右括號(hào)是否匹配，采用（）實(shí)現(xiàn)較為方便。A.線性表的順序存儲(chǔ)B.隊(duì)列C.線性表的鏈?zhǔn)酱鎯?chǔ)D.棧9.串是一種特殊的線性表，其特殊性表現(xiàn)在（）A.可以順序存儲(chǔ)B.數(shù)據(jù)元素是一個(gè)字符C.可以鏈接存儲(chǔ)D.數(shù)據(jù)元素可以是多個(gè)字符10.串‘a(chǎn)babaaababaa’的next數(shù)組為（）。A.012345678999B.012121111212C.011234223456D.012301232234511.對(duì)稀疏矩陣進(jìn)行壓縮存儲(chǔ)目的是（）。A.便于進(jìn)行矩陣運(yùn)算B.便于輸入和輸出C.節(jié)省存儲(chǔ)空間D.降低運(yùn)算的時(shí)間復(fù)雜度12.設(shè)廣義表L=((a,b,c)),則L的長(zhǎng)度和深度分別為（）。A.1和1B.1和3C.1和2D.2和313.若一棵二叉樹具有10個(gè)度為2的結(jié)點(diǎn)，5個(gè)度為1的結(jié)點(diǎn)，則度為0的結(jié)點(diǎn)個(gè)數(shù)是（）。A.9B.11C.15D.不確定14.設(shè)森林P中有三棵樹，第一，第二，第三棵樹的結(jié)點(diǎn)個(gè)數(shù)分別為M1,M2和M3。與森林F對(duì)應(yīng)的二叉樹根結(jié)點(diǎn)的右子樹上的結(jié)點(diǎn)個(gè)數(shù)是（）。A.M1B.M1+M2C.M3D.M2+M315.樹的后根遍歷序列等同于該樹對(duì)應(yīng)的二叉樹的（）。A.先序遍歷序列B.中序遍歷序列C.后序遍歷序列D.層次遍歷序列16.要連通具有n個(gè)頂點(diǎn)的有向圖，至少需要（）條邊。A.n1B.nC.n+1D.2n17.設(shè)使用的鄰接表表示某有向圖，則頂點(diǎn)vj在表結(jié)點(diǎn)中出現(xiàn)的次數(shù)等于（）。A.頂點(diǎn)vj的度B.頂點(diǎn)vj的出度C.頂點(diǎn)vj的入度D.無法確定18.對(duì)有n個(gè)結(jié)點(diǎn)、e條邊且使用鄰接表存儲(chǔ)的有向圖進(jìn)行廣度優(yōu)先遍歷，其算法時(shí)間復(fù)雜度是（）。A.0(n)B.O(e)C.0(n+e)D.0(n*e)19.對(duì)N個(gè)元素的表做順序查找時(shí)，若查找每個(gè)元素的概率相同，則查找成功前提下的平均查找長(zhǎng)度為（）。A.(N+1)/2B.N/2C.ND.[(1+N)*N]/220.若需在0(nloggn)的時(shí)間內(nèi)完成對(duì)數(shù)組的排序，且要求排序是穩(wěn)定的，則可選擇的排序方法是（）。A.快速排序B.堆排序C.歸并排序D.直接插入排序二、判斷題(本大題共10小題，每小題1分，共計(jì)10分)1.順序存儲(chǔ)方式的優(yōu)點(diǎn)是存儲(chǔ)密度大，且插入、刪除運(yùn)算效率高。（）2.一棵有n個(gè)結(jié)點(diǎn)的二叉樹，從上到下，從左到右用自然數(shù)依次給予編號(hào)，則編號(hào)為i的結(jié)點(diǎn)的左兒子的編號(hào)為2i(2i<n),右兒子是2i+1(2i+1<n)。（）3.在二叉樹中插入結(jié)點(diǎn)，此二叉樹便不再是二叉樹。（）4.已知二叉樹的前序遍歷和后序遍歷序列不能唯一地確定這棵樹。（）5.連通分量是無向圖中極大連通子圖。（）6.數(shù)據(jù)的邏輯結(jié)構(gòu)隨數(shù)據(jù)值的變化而改變。（）7.數(shù)據(jù)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)是一對(duì)一的關(guān)系。（）8.KMP算法較BF算法的改進(jìn)主要是消除了主串的指針的回溯。（）9.二分查找既可以在順序存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)，也可以在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上實(shí)現(xiàn)。（）10.存儲(chǔ)稀疏圖，用鄰接矩陣比鄰接表更省空間。（）三、填空題(本大題共15小題，每小題2分，共30分)1.存儲(chǔ)結(jié)構(gòu)是邏輯結(jié)構(gòu)的（）實(shí)現(xiàn)。2.順序存儲(chǔ)的線性表可以（）存取。3.所有結(jié)點(diǎn)按1對(duì)1的鄰接關(guān)系構(gòu)成的整體就是（）結(jié)構(gòu)。4.鏈隊(duì)列在一定范圍內(nèi)不會(huì)出現(xiàn)（）的情況。當(dāng)lq.front==lq.rear時(shí)，隊(duì)中無元素，此時(shí)（）（）。5.（）可以作為實(shí)現(xiàn)遞歸函數(shù)調(diào)用的一種數(shù)據(jù)結(jié)構(gòu)。6.空串是（）,其長(zhǎng)度等于（）。7.將數(shù)組A[1..8,1..8]按行優(yōu)先次序存儲(chǔ)在起始地址為1000的連續(xù)的內(nèi)存單元中，其中每個(gè)元素占用2字節(jié)，則元素A[7,3]的地址是：（）。8.當(dāng)廣義表中的每個(gè)元素都是原子時(shí)，廣義表便成了（）。9.滿二叉樹上各層的節(jié)點(diǎn)數(shù)已達(dá)到了二叉樹可以容納的（）。滿二叉樹也是（）二叉樹，但反之不然。10.二叉樹通常有（）存儲(chǔ)結(jié)構(gòu)和（）存儲(chǔ)結(jié)構(gòu)兩類存儲(chǔ)結(jié)構(gòu)。11.如果結(jié)點(diǎn)a有三個(gè)兄弟，而且b是a的雙親，則b的度是（）12.遍歷圖的基本方法有（）優(yōu)先搜索和（）優(yōu)先搜索兩種。13.若G為有向圖，有n個(gè)頂點(diǎn)，則圖至少有（）條弧，最多有（）條弧。14.動(dòng)態(tài)查找表和靜態(tài)查找表的重要區(qū)別在于前者包含有（）和（）運(yùn)算，而后者不包含這兩種運(yùn)算。15.按照排序過程涉及的存儲(chǔ)設(shè)備的不同，排序可分為（）排序和（）排序。四、綜合題(本大題共10小題，每小題6分，共60分)1.已知一個(gè)棧的進(jìn)棧序列是1,2,3,…,n,其輸出序列是pl,p2,…,pn,若pl=n,求pi的值。2.已知KMP串匹配算法中子串為“abcabcaaa”,寫出其next值。3.求下列廣義表操作的結(jié)果：(1)GetHead((a,b,c)),（）（）(2)GetHead(GetTail((a,b),(c,d)))4.設(shè)森林F中有3棵樹A、B、C,其結(jié)點(diǎn)個(gè)數(shù)分別為11、8和12,計(jì)算與森林F對(duì)應(yīng)的二叉樹Bf根節(jié)點(diǎn)A的左子樹上的結(jié)點(diǎn)的個(gè)數(shù)，并畫出該二叉樹結(jié)構(gòu)圖。5.已知某二叉樹按中序遍歷次序是BDCEAFHG,按后序遍歷次序是DECBHGFA,試畫出該二叉樹的形狀，并寫出它的前序遍歷序列。6.給出下圖(1),寫出采用克魯斯卡爾算法構(gòu)造最小生成樹的過程。7.對(duì)于關(guān)鍵字序列{55,73,11,80,20,41,28,52,34,67},寫出使用直接插入法進(jìn)行排序的過程。8.對(duì)數(shù)據(jù)序列(4,3,8,9,11,10),請(qǐng)構(gòu)造相應(yīng)的哈夫曼樹，并求出帶權(quán)路徑長(zhǎng)度WPL。9.已知一組關(guān)鍵字為{22,18,51,2,53,38,32,4,69,