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