數(shù)據(jù)結(jié)構(gòu)自考題-2

1、數(shù)據(jù)結(jié)構(gòu)自考題 -2( 總分： 105.00 ，做題時(shí)間： 90 分鐘 )一、 單項(xiàng)選擇題 ( 總題數(shù)： 15，分?jǐn)?shù)： 30.00)1. 用二分查找法對(duì)具有n 個(gè)結(jié)點(diǎn)的線性表查找一個(gè)結(jié)點(diǎn)所需的平均比較次數(shù)為( )2（分?jǐn)?shù)： 2.00 ）A.B.C.D.解析：2. 如果我們采用二分查找法查找一個(gè)長(zhǎng)度為的高度 ( 假設(shè)樹高 h2) 。A大于 B 小于 C 等于 D 無法確定n 的有序表，則查找每個(gè)元素的平均比較次數(shù)( ) 對(duì)應(yīng)的判定樹（分?jǐn)?shù)： 2.00 ）A.B. C.D.解析：3. 對(duì)一棵非空二叉樹進(jìn)行中序遍歷，則根結(jié)點(diǎn)的左邊 ( ) A只有左子樹上的所有結(jié)點(diǎn) B 只有右子樹上的所有結(jié)點(diǎn)C只有左

2、子樹上的部分結(jié)點(diǎn)D 只有右子樹上的部分結(jié)點(diǎn)（分?jǐn)?shù)： 2.00 ）A. B.C.D.解析：4. 在按層次遍歷二叉樹的算法中，需要借助的輔助數(shù)據(jù)結(jié)構(gòu)是( )A隊(duì)列 B 棧 C 線性表 D 有序表（分?jǐn)?shù)：A.2.00 ）B.C.D.解析：5. 從具有 n 個(gè)結(jié)點(diǎn)的單鏈表中查找值等于A n B n/2 C (n-1)/2 D(n+1)/2x 的結(jié)點(diǎn)時(shí)，在查找成功的情況下，平均需比較( )個(gè)結(jié)點(diǎn)。（分?jǐn)?shù)： 2.00 ）A.B.C.D. 解析：6. 設(shè)二叉樹根結(jié)點(diǎn)的層次為 0，一棵高度為 h 的滿二叉樹中的結(jié)點(diǎn)個(gè)數(shù)是 ( ) A 2h B 2h-1 C 2h-1 D 2h+1 -1（分?jǐn)?shù)： 2.00 ）A

3、.B.C.D. 解析：7. 下面的查找方式中，可以對(duì)無序表進(jìn)行查找的是( )A順序查找B 二分查找C 二叉排序樹D B-樹上的查找（分?jǐn)?shù)： 2.00 ）A. B.C.D.解析：8. 具有 12 個(gè)記錄的序列，采用冒泡排序最少的比較次數(shù)是( )A1 B144 C 11 D66（分?jǐn)?shù)： 2.00 ）A.B.C. D.解析：9. 線性結(jié)構(gòu)中的一個(gè)結(jié)點(diǎn)代表一個(gè)數(shù)據(jù)元素，通常要求同一線性結(jié)構(gòu)的所有結(jié)點(diǎn)所代表的數(shù)據(jù)元素具有相同的特性，這意味著 ( )A每個(gè)結(jié)點(diǎn)所代表的數(shù)據(jù)元素都一樣B每個(gè)結(jié)點(diǎn)所代表的數(shù)據(jù)元素包含的數(shù)據(jù)項(xiàng)的個(gè)數(shù)要相等C不僅數(shù)據(jù)元素所包含的數(shù)據(jù)項(xiàng)的個(gè)數(shù)要相同，而且對(duì)應(yīng)數(shù)據(jù)項(xiàng)的類型要一致D結(jié)點(diǎn)所

4、代表的數(shù)據(jù)元素有同一特點(diǎn)（分?jǐn)?shù)： 2.00 ）A.B.C. D.解析：10. 下列排序算法中，其時(shí)間復(fù)雜度和記錄的初始排列無關(guān)的是( )A插入排序B 堆排序 C 快速排序 D 冒泡排序（分?jǐn)?shù)：2.00 ）A.B.C.D.解析：11. 若用鄰接矩陣表示一個(gè)有向圖，則其中每一列包含的"1"的個(gè)數(shù)為( )A圖中每個(gè)頂點(diǎn)的入度B 圖中每個(gè)頂點(diǎn)的出度C圖中弧的條數(shù)D 圖中連通分量的數(shù)目（分?jǐn)?shù)： 2.00 ）A. B.C.D.解析：12. 具有 24 個(gè)記錄的序列，采用冒泡排序最少的比較次數(shù)是( )A1 B23 C24 D529（分?jǐn)?shù)：2.00 ）A.B.C.D.解析：13. 鄰接表存

5、儲(chǔ)結(jié)構(gòu)下圖的深度優(yōu)先遍歷算法結(jié)構(gòu)類似于于叉樹的( )A先序遍歷B 中序遍歷C 后序遍歷D 按層遍歷（分?jǐn)?shù)： 2.00 ）A. B.C.D.解析：14. 樹最適合用來表示 ( )A有序數(shù)據(jù)元素B 無序數(shù)據(jù)元素C元素之間具有分支層次關(guān)系的數(shù)據(jù)D 元素之間無聯(lián)系的數(shù)據(jù)（分?jǐn)?shù)：2.00 ）A.B.C.D.解析：15. 若用冒泡排序法對(duì)序列18,14,6,27,8,12,16,52,10,26,47,29,41,24從小到大進(jìn)行排序，共要進(jìn)行( )次比較。A 33 B 45 C 70 D91（分?jǐn)?shù)： 2.00 ）A.B.C. D.解析：二、 填空題 ( 總題數(shù)： 10，分?jǐn)?shù)： 20.00)16. 對(duì)于一

6、個(gè)二維數(shù)組Amn ，若按行序?yàn)橹餍虼鎯?chǔ)，則任一元素Aij相對(duì)于 A00的地址為 1 。（分?jǐn)?shù)： 2.00 ）填空項(xiàng) 1:_（正確答案： i ×j+i全元素位置）解析：17. 已知 L 是無表頭結(jié)點(diǎn)的單鏈表， 且 P 結(jié)點(diǎn)既不是首元結(jié)點(diǎn)， 也不是尾元結(jié)點(diǎn)， 試從下列提供的答案中選擇合適的語句序列。(1) 在 P 結(jié)點(diǎn)之前插入 S 結(jié)點(diǎn)的語句序列是 _；(2) 在表首插入 S 結(jié)點(diǎn)的語句序列是 _。a P nex=S b P next=P next nextc P next=S next d S next=P nexte S next=L f Q=Pg while(P next!=Q P

7、=P nexth while(P next!=NULL)P=P nexti P=L j L=S（分?jǐn)?shù)： 2.00 ）填空項(xiàng) 1:_（正確答案：解析：18. 任意一棵具有n 個(gè)結(jié)點(diǎn)的二叉樹，若它有f i gda e j ）m個(gè)葉子，則該二叉樹上度數(shù)為1 的結(jié)點(diǎn)為1 個(gè)。（分?jǐn)?shù)：2.00 ）填空項(xiàng)1:_（正確答案：n-2m+1）解析：19. 存儲(chǔ)在直接存儲(chǔ)器上的順序文件可以用順序查找法存取，也可以用_和進(jìn)行查找。（分?jǐn)?shù)： 2.00 ）填空項(xiàng) 1:_ （正確答案：二分查找法分塊查找）解析：20. 由權(quán)值為 1,2,3,4,5,6的六個(gè)葉子結(jié)點(diǎn)構(gòu)成一棵哈夫曼樹，則帶權(quán)的路徑的長(zhǎng)度為1 。（分?jǐn)?shù)：2.0

8、0 ）填空項(xiàng)1:_（正確答案：55）解析：21. 數(shù)組 A1.10 ，-2.6長(zhǎng)度的存儲(chǔ)空間，則元素，2.8以行優(yōu)先順序存儲(chǔ)，設(shè)第一個(gè)元素的首地址是A5,0,7的存儲(chǔ)地址為1 。100 ，每個(gè)元素占3 個(gè)存儲(chǔ)（分?jǐn)?shù)： 2.00 ）填空項(xiàng) 1:_（正確答案： 913 ）解析：22. 如果一個(gè)圖中有n 條邊，則此圖的生成樹含有_條邊，所以生成樹是圖的邊數(shù)_的連通圖。（分?jǐn)?shù)： 2.00 ）填空項(xiàng) 1:_（正確答案： n-1最少）解析：23. 在二叉排序樹中，其左子樹中任何一個(gè)結(jié)點(diǎn)的關(guān)鍵字一定1 其右子樹的各結(jié)點(diǎn)的關(guān)鍵字。（分?jǐn)?shù)： 2.00 ）填空項(xiàng) 1:_（正確答案：小于）解析：24. 在線性結(jié)構(gòu)中

9、， 1 決定了它的遍歷路線只有一條。2.00填空項(xiàng)1:_（正確答案：線性結(jié)構(gòu)中后繼的惟一性）解析：25. 在按照順序存儲(chǔ)方式存儲(chǔ)的數(shù)組中，元素aij的存儲(chǔ)地址應(yīng)該是數(shù)組的1 加上排在aij前面的元素所占用的單元數(shù)。（分?jǐn)?shù)： 2.00 ）填空項(xiàng) 1:_（正確答案：基地址）解析：三、 解答題 ( 總題數(shù)： 3，分?jǐn)?shù)： 25.00)已知帶權(quán)圖的鄰接表如下所示，其中邊表結(jié)點(diǎn)的結(jié)構(gòu)為：依此鄰接表從頂點(diǎn)C 出發(fā)進(jìn)行深度優(yōu)先遍歷。(1) 畫出由此得到的深度優(yōu)先生成樹；(2) 寫出遍歷過程中得到的從頂點(diǎn) C 到其他各頂點(diǎn)的帶權(quán)路徑及其長(zhǎng)度。（分?jǐn)?shù)： 10.00 ）_正確答案：()解析：_正確答案：()解析：2

10、6. 圖的鄰接表的類型定義如下所示：#define MaxVertexNum 50typedef struct nodeint adjvex;struct node*next;EdgeNode;typedef structVertexType vertex;EdgeNode*firstedge;VertexNode;typedef VertexNode A djListMaxVertexNum;typedef structAdjList adjiist;int n,e;ALGraph;為便于刪除和插入圖的頂點(diǎn)的操作，可將鄰接表的表頭向量定義為鏈?zhǔn)浇Y(jié)構(gòu)，兩種定義的存儲(chǔ)表示實(shí)例如下圖所示，請(qǐng)寫出重

11、新定義的類型說明。（分?jǐn)?shù)： 5.00 ）_正確答案： (typeclef struct ArcNodeVNode*adjvex; /該弧所指向的頂點(diǎn)的位置struct ArcNode*nextarc; /指向下一條弧的指針ArcNode;typedef struct VNodeVertexType data; /頂點(diǎn)信息struct VNode*nextVertex; /指向下一個(gè)頂點(diǎn)的指針ArcNode*firstarc; /指向第一條依附該頂點(diǎn)的弧VNode.*AdjList;typedef structAdjList adjList;int n,e;ALGraph;)解析：從空樹起，依次

12、插入關(guān)鍵字37,50,42,18,48,12,56,30,23，構(gòu)造一棵二叉排序樹。(1) 畫出該二叉排序樹；(2) 畫出從 (1) 所得樹中刪除關(guān)鍵字為37 的結(jié)點(diǎn)之后的二叉排序樹。（分?jǐn)?shù)： 10.00 ）_正確答案： ()解析：_正確答案： ()解析：四、 算法閱讀題 ( 總題數(shù)： 2，分?jǐn)?shù)： 20.00)二叉排序樹的存儲(chǔ)結(jié)構(gòu)定義為以下類型：typedef int KeyType;typedef struct nodeKeyType key; /*關(guān)鍵字項(xiàng) */InfoType otherinfo; /* struet node*lchild,*rchild; /*其它數(shù)據(jù)項(xiàng) */左、右孩

13、子指針*/BSTNode,*BSTree;閱讀算法 f33 ，并回答問題：(1) 對(duì)如圖所示的二叉排序樹 T，寫出 f33(T,8) 返回的指針?biāo)附Y(jié)點(diǎn)的關(guān)鍵字；(2) 在哪些情況下算法 f33 返回空指針 ?(3) 簡(jiǎn)述算法 f33 的功能。BSTNode*f33(BSTree T,KeyType x)BSTNode*P;if(T=NULL)return NULL;p=f33(T lehild,x);if(p!=NULL)return p;if(T key x)return T;return f33(T rchild,x);（分?jǐn)?shù)： 15.00 ）填空項(xiàng) 1:_（正確答案： 10）解析：_正

14、確答案： (T 是空樹或T 中所有結(jié)點(diǎn)的關(guān)鍵字均不大于給定值X 時(shí)，返回空指針。)解析：_正確答案： ( 如果二叉排序樹T 中存在含有關(guān)鍵字大于給定值X 的結(jié)點(diǎn)，則返回指針指向它們中關(guān)鍵字最小的結(jié)點(diǎn)，否則返回空指針。)解析：27. 簡(jiǎn)述一下算法的功能：status A (1inkedlist L)/L是無表頭結(jié)點(diǎn)的單鏈表if (L&&L next)Q=L;L=L next;P=L;while(P next)P=P next;P next=Q;Q next=NULL;return ok;)/A（分?jǐn)?shù)： 5.00 ）_正確答案： ( 本程序?qū)崿F(xiàn)的功能就是：如果L 的長(zhǎng)度不小于2，則

15、將首元結(jié)點(diǎn)刪去并插入到表尾。)解析：五、 算法設(shè)計(jì)題 ( 總題數(shù)： 1，分?jǐn)?shù)： 10.00)28. 假設(shè)以帶頭結(jié)點(diǎn)的單鏈表表示有序表，單鏈表的類型定義如下：typedef struct nodeDataType data;struct node*nextLinkNode,*LinkList;編寫算法，從有序表A 中刪除所有和有序表B 中元素相同的結(jié)點(diǎn)。（分?jǐn)?shù)： 10.00 ）_正確答案： ( 參考答案一：void f34(LinkList ha,LinkList hb) /hb 和 hb 分剮為存放 A 和 B 有序鏈表的頭指針LinkList p,q,r;p=ha;q=hb next;while(p next&&q)if(p next data q- data)p=p next;elseif(p next data=q data)r=p next;p next=r next;free(r); / 從 A 表刪除相同的元素結(jié)點(diǎn)q=q ne