?數(shù)據(jù)結(jié)構(gòu)自考2015年10月真題

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

本試卷為單選題型，填空題，算法閱讀，算法設(shè)計(jì)等題型。

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

1.下列選項(xiàng)中，不屬于線性結(jié)構(gòu)的是(　　)

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

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

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

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

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

4.若一個(gè)棧以數(shù)組V[0..n-1]存儲(chǔ)，初始棧頂指針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]中：每個(gè)數(shù)組元素占用3個(gè)存儲(chǔ)空間，從首地址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.一棵左子樹為空的二叉樹在前序線索化后，其空指針域個(gè)數(shù)為(　　)

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

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

A.用n個(gè)結(jié)點(diǎn)構(gòu)造的哈夫曼樹是唯一的
B.哈夫曼樹中只有度為0或度為2的結(jié)點(diǎn)
C.樹中兩個(gè)權(quán)值最小的結(jié)點(diǎn)可能是兄弟結(jié)點(diǎn)
D.同一結(jié)點(diǎn)集構(gòu)造的二叉樹中，哈夫曼樹的WPL最小

9.6個(gè)頂點(diǎn)的強(qiáng)連通圖中，含有的邊數(shù)至少是(　　)

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

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

A.

B.

C.

D.

11.下列選項(xiàng)中，能構(gòu)成題10圖中一條路徑的是(　　)

A.

B.

C.

D.

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

A.對(duì)應(yīng)頂點(diǎn)v的度
B.對(duì)應(yīng)頂點(diǎn)v的出度
C.對(duì)應(yīng)頂點(diǎn)v的入度
D.依附于對(duì)應(yīng)頂點(diǎn)v的邊數(shù)

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

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.已知關(guān)鍵字序列為{66，82，25，51，98，108}，利用快速排序方法，以第一個(gè)元素為基準(zhǔn)得到的一趟排序結(jié)果為(　　)

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.下列選項(xiàng)中，其平均查找性能與基于二叉排序樹的查找相當(dāng)?shù)氖?　　)

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

二、填空題(本大題共10小題，每小題2分，共20分) 請(qǐng)?jiān)诿啃☆}的空格中填上正確答案。錯(cuò)填、不填均無分。

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

12.指針P指向單鏈表中某個(gè)結(jié)點(diǎn)，在P所指結(jié)點(diǎn)后插入指針s所指的結(jié)點(diǎn)，正確的操作序列是_______。

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

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

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

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

17.在有n個(gè)頂點(diǎn)的無向圖中，任一頂點(diǎn)的度不大于_______。

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

19. 若有向圖中存在拓?fù)渑判蛐蛄?，則該圖一定不存在_______。

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

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

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

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

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

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

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

31.請(qǐng)寫出下列程序段的輸出結(jié)果。

32.己知存儲(chǔ)稀疏矩陣三元組表的類型定義如下：#define MAX 100typedef struct{            int i, j;                //非零元素的行號(hào)、列號(hào)(下標(biāo))            int v;                 //非零元素值} TriTupleNode;typedef struct{      TriTupleNode data[ MAX];           //存儲(chǔ)三元組的數(shù)組       int m, n, t;                   //矩陣的行數(shù)、列數(shù)和非零元素個(gè)數(shù)      }TSMatrix;               //稀疏矩陣類型函數(shù)f31的功能是將a所表示的矩陣轉(zhuǎn)置后保存在*b中。請(qǐng)?jiān)诳瞻滋幪顚戇m當(dāng)內(nèi)容，使其完成指定功能。

33.已知二叉樹的二叉鏈表類型定義如下：為完成指定功能，請(qǐng)?jiān)诳瞻滋幪顚戇m當(dāng)內(nèi)容，使其功能完整。

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

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

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