2015年河南財(cái)經(jīng)政法大學(xué)數(shù)據(jù)結(jié)構(gòu)考研真題

》》》》》》2023年整理歷年要考研試題資料《《《《《《》》》》》》2023年整理歷年要考研試題資料《《《《《《/》》》》》》2023年整理歷年要考研試題資料《《《《《《2015年河南財(cái)經(jīng)政法大學(xué)數(shù)據(jù)結(jié)構(gòu)考研真題一、選擇題（本題共10個(gè)小題，每小題3分，共計(jì)30分）1．?dāng)?shù)據(jù)在計(jì)算機(jī)存儲(chǔ)器內(nèi)表示時(shí)，物理地址與邏輯地址相同并且是連續(xù)的，稱之為（）。（A）存儲(chǔ)結(jié)構(gòu)（B）邏輯結(jié)構(gòu)（C）順序存儲(chǔ)結(jié)構(gòu)（D）鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)2.一個(gè)向量第一個(gè)元素的存儲(chǔ)地址是100，每個(gè)元素的長度為2，則第5個(gè)元素的地址是（）。（A）110（B）108（C）100（D）1203.設(shè)有一個(gè)長度為n的順序表，要在第i個(gè)元素之前（也就是插入元素作為新表的第i個(gè)元素），則移動(dòng)元素個(gè)數(shù)為（）。A．n-i+1B．n-iC．n-i-1D．i4.向一個(gè)有127個(gè)元素的順序表中插入一個(gè)新元素并保持原來順序不變，平均要移動(dòng)（）個(gè)元素。（A）8（B）63.5（C）63（D）75判定一個(gè)隊(duì)列QU（最多元素為m0）為滿隊(duì)列的條件是（）。（A）QU->rear－QU->front==m0（B）QU->rear－QU->front－1==m0（C）QU->front==QU->rear（D）QU->front==QU->rear+16.鏈表是一種采用（）存儲(chǔ)結(jié)構(gòu)存儲(chǔ)的線性表。（A）順序（B）鏈?zhǔn)剑–）星式（D）網(wǎng)狀7.線性表若采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)時(shí)，要求內(nèi)存中可用存儲(chǔ)單元的地址（）（A）必須是連續(xù)的（B）部分地址必須是連續(xù)的（C）一定是不連續(xù)的（D）連續(xù)或不連續(xù)都可以8．線性表Ｌ在（）情況下適用于使用鏈?zhǔn)浇Y(jié)構(gòu)實(shí)現(xiàn)。（A）需經(jīng)常修改Ｌ中的結(jié)點(diǎn)值（B）需不斷對Ｌ進(jìn)行刪除插入（C）Ｌ中含有大量的結(jié)點(diǎn)（D）Ｌ中結(jié)點(diǎn)結(jié)構(gòu)復(fù)雜9.若已知一個(gè)棧的入棧序列是1，2，3，…，n，其輸出序列為p1，p2，p3，…，pn，若p1=n，則pi為（）。（A）i（B）n=i（C）n-i+1（D）不確定 10.設(shè)某無向圖中有n個(gè)頂點(diǎn)e條邊，則該無向圖中所有頂點(diǎn)的度之和為（）。 (A)n (B)e (C)2e (D)7二、填空題（本題共10個(gè)小題，每小題3分，共計(jì)30分）1.設(shè)有一個(gè)順序共享?xiàng)[0：n-1]，其中第一個(gè)棧項(xiàng)指針top1的初值為-1，第二個(gè)棧頂指針top2的初值為n，則判斷共享?xiàng)M的條件是____________________。2.在圖的鄰接表中用順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)表頭結(jié)點(diǎn)的優(yōu)點(diǎn)是____________________。3.設(shè)有一個(gè)n階的下三角矩陣A，如果按照行的順序?qū)⑾氯蔷仃囍械脑兀ò▽蔷€上元素）存放在n(n+1)個(gè)連續(xù)的存儲(chǔ)單元中，則A[i][j]與A[0][0]之間有_______個(gè)數(shù)據(jù)元素。4.設(shè)一棵完全二叉樹的順序存儲(chǔ)結(jié)構(gòu)中存儲(chǔ)數(shù)據(jù)元素為ABCDEF，則該二叉樹的后序遍歷序列為___________。5.設(shè)一組初始記錄關(guān)鍵字序列(k1，k2，……，kn)是堆，則對i=1，2，…，n/2而言滿足的條件為_______________________________。6.設(shè)關(guān)鍵字序列為(Kl，K2，…，Kn)，則用篩選法建初始堆必須從第______個(gè)元素開始進(jìn)行篩選。7.設(shè)有一組初始關(guān)鍵字序列為(24，35，12，27，18，26)，則第3趟直接插入排序結(jié)束后的結(jié)果的是________________________。8.設(shè)有一組初始關(guān)鍵字序列為(24，35，12，27，18，26)，則第3趟簡單選擇排序結(jié)束后的結(jié)果的是________________________。9.設(shè)一棵二叉樹的前序序列為ABC，則有______________種不同的二叉樹可以得到這種序列。10.設(shè)輸入序列為1、2、3，則經(jīng)過棧的作用后可以得到___________種不同的輸出序列。三、判斷題（本題共10個(gè)小題，每小題3分，共計(jì)30分）（請?jiān)谛☆}括號(hào)內(nèi)打√或×）()1．調(diào)用一次深度優(yōu)先遍歷可以訪問到圖中的所有頂點(diǎn)。()2．分塊查找的平均查找長度不僅與索引表的長度有關(guān)，而且與塊的長度有關(guān)。()3．冒泡排序在初始關(guān)鍵字序列為逆序的情況下執(zhí)行的交換次數(shù)最多。()4．滿二叉樹一定是完全二叉樹，完全二叉樹不一定是滿二叉樹。()5．設(shè)一棵二叉樹的先序序列和后序序列，則能夠唯一確定出該二叉樹的形狀。()6．層次遍歷初始堆可以得到一個(gè)有序的序列。()7．設(shè)一棵樹T可以轉(zhuǎn)化成二叉樹BT，則二叉樹BT中一定沒有右子樹。()8．線性表的順序存儲(chǔ)結(jié)構(gòu)比鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)更好。()9．中序遍歷二叉排序樹可以得到一個(gè)有序的序列。()10.快速排序是排序算法中平均性能最好的一種排序。四、簡答題（本題共2個(gè)小題，每小題15分，共計(jì)30分）1．設(shè)無向圖G（如圖1所示），給出該圖的最小生成樹上邊的集合并計(jì)算最小生成樹各邊上的權(quán)值之和。圖12．從空樹起，依次插入關(guān)鍵字37，50，42，18，48，12，56，30，23，構(gòu)造一棵二叉排序