1、( ) 對應(yīng)的判定樹( ) 個結(jié)點(diǎn)數(shù)據(jù)結(jié)構(gòu)自考題 -2( 總分： 105.00 ，做題時間： 90 分鐘 )一、單項(xiàng)選擇題 ( 總題數(shù)： 15，分?jǐn)?shù)： 30.00)1. 用二分查找法對具有 n 個結(jié)點(diǎn)的線性表查找一個結(jié)點(diǎn)所需的平均比較次數(shù)為 ( ) 2A O(n2) B O(nlog 2n) C O(n) D O(log 2n)(分?jǐn)?shù)： 2.00 )A.B.VC.D.V解析：2. 如果我們采用二分查找法查找一個長度為 n 的有序表，則查找每個元素的平均比較次數(shù) 的高度(假設(shè)樹高h(yuǎn)>2)。A. 大于B .小于C 等于D .無法確定(分?jǐn)?shù)： 2.00 )A.B. VC.D.解析：3. 對一棵

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

3、 h 的滿二叉樹中的結(jié)點(diǎn)個數(shù)是 ( )A2h B 2h-1 C 2h-1 D 2h+1-1(分?jǐn)?shù)： 2.00 )A.B.C.D. V解析：7. 下面的查找方式中，可以對無序表進(jìn)行查找的是 ( )A. 順序查找B .二分查找C .二叉排序樹D . B-樹上的查找(分?jǐn)?shù)： 2.00 )A. VB.C.D.解析：8. 具有 12 個記錄的序列，采用冒泡排序最少的比較次數(shù)是 ( )A1 B144 C11 D66(分?jǐn)?shù)： 2.00 )A.B.C. VD.解析：9. 線性結(jié)構(gòu)中的一個結(jié)點(diǎn)代表一個數(shù)據(jù)元素，通常要求同一線性結(jié)構(gòu)的所有結(jié)點(diǎn)所代表的數(shù)據(jù)元素具有相 同的特性，這意味著 ( )A. 每個結(jié)點(diǎn)所代表的

4、數(shù)據(jù)元素都一樣B. 每個結(jié)點(diǎn)所代表的數(shù)據(jù)元素包含的數(shù)據(jù)項(xiàng)的個數(shù)要相等C. 不僅數(shù)據(jù)元素所包含的數(shù)據(jù)項(xiàng)的個數(shù)要相同，而且對應(yīng)數(shù)據(jù)項(xiàng)的類型要一致D. 結(jié)點(diǎn)所代表的數(shù)據(jù)元素有同一特點(diǎn)分?jǐn)?shù)： 2.00 )A.B.D.解析：10. 下列排序算法中，其時間復(fù)雜度和記錄的初始排列無關(guān)的是 ( )A.插入排序B 堆排序C 快速排序D 冒泡排序(分?jǐn)?shù)： 2.00 )A.B. VC.D.解析：11. 若用鄰接矩陣表示一個有向圖，則其中每一列包含的 "1" 的個數(shù)為 ( )A.圖中每個頂點(diǎn)的入度B .圖中每個頂點(diǎn)的出度B. 圖中弧的條數(shù) D 圖中連通分量的數(shù)目(分?jǐn)?shù)： 2.00 )A. VB.C

5、.D.解析：12. 具有 24 個記錄的序列，采用冒泡排序最少的比較次數(shù)是 ( )A. 1 B. 23 C. 24 D. 529(分?jǐn)?shù)： 2.00 )A.B. VC.D.解析：13. 鄰接表存儲結(jié)構(gòu)下圖的深度優(yōu)先遍歷算法結(jié)構(gòu)類似于于叉樹的 ( )A.先序遍歷B .中序遍歷C .后序遍歷D .按層遍歷(分?jǐn)?shù)： 2.00 )A. VB.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. VD.解析：15. 若用冒泡排序法對序列 18,14,6,27,8,12,16,52,1

6、0,26,47,29,41,24 從小到大進(jìn)行排序，共要進(jìn)行 （ ） 次比較。A33 B45 C70 D91（分?jǐn)?shù)： 2.00 ）A.B.C. VD.解析：二、填空題（總題數(shù)： 10，分?jǐn)?shù)： 20.00）16. 對于一個二維數(shù)組 Amn ，若按行序?yàn)橹餍虼鎯Γ瑒t任一元素 Aij 相對于 A00 的地址為 1（分?jǐn)?shù)： 2.00 ）填空項(xiàng)1: （正確答案：i Xj+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)的語句序列是

7、 。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=P> nexth while（P > next!=NULL）P=P > nexti P=L j L=S（分?jǐn)?shù)： 2.00 ）填空項(xiàng) 1: （正確答案： figda ej）解析：18. 任意一棵具有n個結(jié)點(diǎn)的二叉樹，若它有 m個葉子，則該二叉樹上度數(shù)為1的結(jié)點(diǎn)為1個（分?jǐn)?shù)：

8、2.00 ）填空項(xiàng) 1: （正確答案： n-2m+1）解析：19. 存儲在直接存儲器上的順序文件可以用順序查找法存取，也可以用 和進(jìn)行查找（分?jǐn)?shù):2.00 ）填空項(xiàng)1： （正確答案：二分查找法分塊查找）解析：20. 由權(quán)值為1,2,3,4,5,6的六個葉子結(jié)點(diǎn)構(gòu)成一棵哈夫曼樹，則帶權(quán)的路徑的長度為1（分?jǐn)?shù):2.00）填空項(xiàng)1： （正確答案：55）解析：21. 數(shù)組A1.10，-2.6 ，2.8以行優(yōu)先順序存儲，設(shè)第一個元素的首地址是100，每個元素占3個存儲長度的存儲空間，則元素A5,0,7的存儲地址為1。（分?jǐn)?shù)：2.00）填空項(xiàng)1: （正確答案：913）解析：22. 如果一個圖中有n條邊，則

9、此圖的生成樹含有 條邊，所以生成樹是圖的邊數(shù) 的連通圖（分?jǐn)?shù)：2.00）填空項(xiàng)1: （正確答案：n-1最少）解析：23. 在二叉排序樹中，其左子樹中任何一個結(jié)點(diǎn)的關(guān)鍵字一定1其右子樹的各結(jié)點(diǎn)的關(guān)鍵字。（分?jǐn)?shù)：2.00）填空項(xiàng)1： （正確答案：小于）解析：24. 在線性結(jié)構(gòu)中，1決定了它的遍歷路線只有一條。（分?jǐn)?shù)：2.00）填空項(xiàng)1: （正確答案：線性結(jié)構(gòu)中后繼的惟一性）解析：25. 在按照順序存儲方式存儲的數(shù)組中，元素aj的存儲地址應(yīng)該是數(shù)組的 1加上排在aj前面的元素所占用的單元數(shù)。（分?jǐn)?shù)：2.00）填空項(xiàng)1: （正確答案：基地址）解析：三、解答題（總題數(shù)：3,分?jǐn)?shù)：25.00）已知帶權(quán)圖的

10、鄰接表如下所示，其中邊表結(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)路徑及其長度。（分?jǐn)?shù)：10.00）正確答案：（ 解析:26. 圖的鄰接表的類型定義如下所示: #define MaxVertexNum 50 typedef struct nodeint adjvex;struct node*next;EdgeNode;typedef structVertexType vertex;EdgeNode*firstedge;VertexNode;typedef VertexNode A djList

11、MaxVertexNum;typedef structAdjList adjiist;int n,e;ALGraph;為便于刪除和插入圖的頂點(diǎn)的操作，可將鄰接表的表頭向量定義為鏈?zhǔn)浇Y(jié)構(gòu)，兩種定義的存儲表示實(shí)例如 下圖所示，請寫岀重新定義的類型說明。（分?jǐn)?shù)：5.00 ） 正確答案：(typeclef struct ArcNodeVNode*adjvex; /該弧所指向的頂點(diǎn)的位置struct ArcNode*nextarc; /指向下一條弧的指針ArcNode;typedef struct VNodeVertexType data; /頂點(diǎn)信息struct VNode*nextVertex; /

12、指向下一個頂點(diǎn)的指針ArcNode*firstarc; / 指向第一條依附該頂點(diǎn)的弧VNode.*AdjList;typedef structAdjList adjList;int n,e;ALGraph;)解析：從空樹起，依次插入關(guān)鍵字37,50,42,18,48,12,56,30,23，構(gòu)造一棵二叉排序樹(1)畫出該二叉排序樹； 畫出從 所得樹中刪除關(guān)鍵字為 37的結(jié)點(diǎn)之后的二叉排序樹。（分?jǐn)?shù)：10.00）正確答案：（解析:正確答案：（解析：四、算法閱讀題（總題數(shù)：2,分?jǐn)?shù)：20.00）二叉排序樹的存儲結(jié)構(gòu)定義為以下類型：typedef int KeyType;typedef struct

13、 nodeKeyType key; /* 關(guān)鍵字項(xiàng) */InfoType otherinfo; /*其它數(shù)據(jù)項(xiàng) */struet node*lchild,*rchild; /*左、右孩子指針 */BSTNode,*BSTree;閱讀算法f33，并回答問題： 對如圖所示的二叉排序樹T，寫出f33(T,8)返回的指針?biāo)附Y(jié)點(diǎn)的關(guān)鍵字;在哪些情況下算法f33返回空指針？簡述算法f33的功能。BSTNode*f33(BSTree T,KeyType x)BSTNode*P;if(T=NULL)return NULL;p=f33(T > lehild,x);if(p!=NULL)return p;

14、if(T > key > x)return T;return f33(T> rchild,x);（分?jǐn)?shù)：15.00 ）填空項(xiàng)1: （正確答案：10）解析：正確答案：仃是空樹或T中所有結(jié)點(diǎn)的關(guān)鍵字均不大于給定值X時，返回空指針。）解析：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 的長度不小于 2，則將首元結(jié)點(diǎn)刪去并插入到表尾。）解析：五、算法設(shè)計題 （ 總題數(shù)： 1，分?jǐn)?shù)： 10.00）28. 假設(shè)以帶

15、頭結(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> next; 參考答案二：void f34(LinkList ha,LinkList hb) /hb 和hb分