?數(shù)據(jù)結構自考2015年10月真題

數(shù)據(jù)結構自考2015年10月真題及答案解析

本試卷為單選題型，填空題，算法閱讀，算法設計等題型。

一、單項選擇題(本大題共15小題，每小題2分，共30分) 在每小題列出的四個備選項中只有一個是符合題目要求的，請將其代碼填寫在題后的括號內。錯選、多選或未選均無分。

1.下列選項中，不屬于線性結構的是(　　)

A.網(wǎng)
B.棧
C.隊列
D.線性表

2.長度為n的順序表，刪除位置i上的元素(0≤i≤n-1)，需要移動的元素個數(shù)為(　　)

A.n-i
B.n-i-1
C.i
D.i+1

3.棧采用不同的存儲方式時，下列關于出棧過程的敘述中，正確的是(　　)

A.順序棧需要判定棧空，鏈棧也需要判定
B.順序棧需要判定?？眨湕２恍枰卸?br/>C.順序棧不需要判定?？?，而鏈棧需要判定
D.順序棧不需要判定?？?，鏈棧也不需要判定

4.若一個棧以數(shù)組V[0..n-1]存儲，初始棧頂指針top為n，則x入棧的正確操作是(　　)

A.top=top+1;V[top]=x
B.V[top]=x;top=top+1
C.top=top-1;V[mp]=x
D.V[top]=x;top=top-1

5.在二維數(shù)組a[9][10]中：每個數(shù)組元素占用3個存儲空間，從首地址SA開始按行優(yōu)先連續(xù)存放，則元素a[8][5]的起始地址是(　　)

A.SA+141
B.SA+144
C.SA+222
D.SA+255

6.廣義表A=(x，((y)，((a))，A))的深度是(　　)

A.2
B.3
C.4
D.∞

7.一棵左子樹為空的二叉樹在前序線索化后，其空指針域個數(shù)為(　　)

A.0
B.1
C.2
D.不確定

8.下列關于哈夫曼樹的敘述中，錯誤的是(　　)

A.用n個結點構造的哈夫曼樹是唯一的
B.哈夫曼樹中只有度為0或度為2的結點
C.樹中兩個權值最小的結點可能是兄弟結點
D.同一結點集構造的二叉樹中，哈夫曼樹的WPL最小

9.6個頂點的強連通圖中，含有的邊數(shù)至少是(　　)

A.4
B.5
C.6
D.7

10.對題10圖進行深度優(yōu)先搜索遍歷，下列選項中，正確的遍歷序列是(　　)

A.

B.

C.

D.

11.下列選項中，能構成題10圖中一條路徑的是(　　)

A.

B.

C.

D.

12.有向圖采用鄰接矩陣存儲，某一行中非零元素的個數(shù)等于(　　)

A.對應頂點v的度
B.對應頂點v的出度
C.對應頂點v的入度
D.依附于對應頂點v的邊數(shù)

13.下列選項中，符合堆定義的是(　　)

A.{102，24，55，60，89，93}
B.{24，89，55，60，93，102}
C.{102，93，55，60，89，24}
D.{102，60，89，93，55，24}

14.已知關鍵字序列為{66，82，25，51，98，108}，利用快速排序方法，以第一個元素為基準得到的一趟排序結果為(　　)

A.{25，51，66，82，98，108}
B.{25，51，66，98，82，108}
C.{51，25，66，108，98，82}
D.{51，25，66，82，98，108}

15.下列選項中，其平均查找性能與基于二叉排序樹的查找相當?shù)氖?　　)

A.二分查找
B.順序查找
C.分塊查找
D.索引順序查找

二、填空題(本大題共10小題，每小題2分，共20分) 請在每小題的空格中填上正確答案。錯填、不填均無分。

11.線性表(a1，a2，…，an)中，除_______外，每個元素都有唯一的直接前趨。

12.指針P指向單鏈表中某個結點，在P所指結點后插入指針s所指的結點，正確的操作序列是_______。

13.設Push，、Pop分別表示人棧和出棧操作，x=10，y=20，z=30。依次進行下列操作：Push(y)、Push(z)、Push(z)、X=Pop()、Y=Pop()，x,y的值分別是_______。

14.廣義表L=(a，(b，e，(e，f，g，h)))，head(L)= _______。

15.設樹T的度為3，其中度為1、2和3的結點個數(shù)分別為3、2和1，則T中葉子結點的個數(shù)為_______。

16.由一棵二叉樹的后序遍歷序列和_______遍歷序列可以唯一確定該二叉樹。

17.在有n個頂點的無向圖中，任一頂點的度不大于_______。

18.借助于一個棧來實現(xiàn)的圖的遍歷算法是_______。

19. 若有向圖中存在拓撲排序序列，則該圖一定不存在_______。

110.已知關鍵字序列為{66，82，25，51，98，108}，一趟二路歸并排序的結果為_______。

三、解答題(本大題共4小題，每小題5分，共20分)

21.已知n階對稱矩陣A的元素為(0≤i，j≤n-1)，采用“按行優(yōu)先”將下三角部分的元素(含主對角線)保存在一維數(shù)組sa中，且約定元素,0保存在sa[0]中，元素(≤i，j≤n-1)保存在sa[k]中，請給出由下標i，j計算下標k的計算公式。

22.己知二又樹T如題27圖所示。請問答下列問題：(1)畫出該二叉樹對應的森林。(2)寫出對森林進行前序遍歷的遍歷序列i

23.題28圖所示為一棵含2個關鍵字的3階B樹T?，F(xiàn)將關鍵字序列{40，60，70，20，10}依次插入到T中，畫出每插入一個關鍵字后得到的樹型。

24.給定無向帶權連通圖G如題29圖所示，從頂點v0開始，使用普里姆(Prim)算法，求G的最小生成樹T。請回答下列問題。(1)畫出最小生成樹T。(2)計算T中各邊權值之和。

四、算法閱讀題(本大題共4小題，每小題5分，共20分)

31.請寫出下列程序段的輸出結果。

32.己知存儲稀疏矩陣三元組表的類型定義如下：#define MAX 100typedef struct{            int i, j;                //非零元素的行號、列號(下標)            int v;                 //非零元素值} TriTupleNode;typedef struct{      TriTupleNode data[ MAX];           //存儲三元組的數(shù)組       int m, n, t;                   //矩陣的行數(shù)、列數(shù)和非零元素個數(shù)      }TSMatrix;               //稀疏矩陣類型函數(shù)f31的功能是將a所表示的矩陣轉置后保存在*b中。請在空白處填寫適當內容，使其完成指定功能。

33.已知二叉樹的二叉鏈表類型定義如下：為完成指定功能，請在空白處填寫適當內容，使其功能完整。

34.函數(shù)f33的參數(shù)t指向題33圖所示的二叉排序樹的根，閱讀程序，回答下列問題。(1)若連續(xù)3次調用函數(shù)f33，參數(shù)K的值依次取10、25、10，寫出每次調用后函數(shù)的輸出結果;(2)說明函數(shù)f33的功能。

五、算法設計題(本大題共1小題，共10分)

41.已知順序表SeqList定義如下：typedef struct{    KeyType key;    InfoType otherinf0;  }RecType：typedef RecType SeqList[MAXSIZE+1];編寫函數(shù)，用冒泡排序法將n個元素的待排序列R按關鍵字降序排序。函數(shù)原型為：int f34(SeqList R，int n)。