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

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

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

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

5、.D.解析：12. 具有 24 個記錄的序列，采用冒泡排序最少的比較次數是 ( )A. 1 B. 23 C. 24 D. 529(分數： 2.00 )A.B. VC.D.解析：13. 鄰接表存儲結構下圖的深度優先遍歷算法結構類似于于叉樹的 ( )A.先序遍歷B .中序遍歷C .后序遍歷D .按層遍歷(分數： 2.00 )A. VB.C.D.解析：14. 樹最適合用來表示 ( )A.有序數據元素 B .無序數據元素C.元素之間具有分支層次關系的數據D .元素之間無聯系的數據（分數： 2.00 ）A.B.C. VD.解析：15. 若用冒泡排序法對序列 18,14,6,27,8,12,16,52,1

6、0,26,47,29,41,24 從小到大進行排序，共要進行 （ ） 次比較。A33 B45 C70 D91（分數： 2.00 ）A.B.C. VD.解析：二、填空題（總題數： 10，分數： 20.00）16. 對于一個二維數組 Amn ，若按行序為主序存儲，則任一元素 Aij 相對于 A00 的地址為 1（分數： 2.00 ）填空項1: （正確答案：i Xj+i 全元素位置）解析：17. 已知 L 是無表頭結點的單鏈表， 且 P 結點既不是首元結點， 也不是尾元結點， 試從下列提供的答案中選 擇合適的語句序列。（1）在P結點之前插入S結點的語句序列是 ；（2）在表首插入 S 結點的語句序列是

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（分數： 2.00 ）填空項 1: （正確答案： figda ej）解析：18. 任意一棵具有n個結點的二叉樹，若它有 m個葉子，則該二叉樹上度數為1的結點為1個（分數：

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

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

10、鄰接表如下所示，其中邊表結點的結構為：依此鄰接表從頂點 C岀發進行深度優先遍歷。（1）畫岀由此得到的深度優先生成樹；（2）寫岀遍歷過程中得到的從頂點C到其他各頂點的帶權路徑及其長度。（分數：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;為便于刪除和插入圖的頂點的操作，可將鄰接表的表頭向量定義為鏈式結構，兩種定義的存儲表示實例如 下圖所示，請寫岀重新定義的類型說明。（分數：5.00 ） 正確答案：(typeclef struct ArcNodeVNode*adjvex; /該弧所指向的頂點的位置struct ArcNode*nextarc; /指向下一條弧的指針ArcNode;typedef struct VNodeVertexType data; /頂點信息struct VNode*nextVertex; /

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

13、 nodeKeyType key; /* 關鍵字項 */InfoType otherinfo; /*其它數據項 */struet node*lchild,*rchild; /*左、右孩子指針 */BSTNode,*BSTree;閱讀算法f33，并回答問題： 對如圖所示的二叉排序樹T，寫出f33(T,8)返回的指針所指結點的關鍵字;在哪些情況下算法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);（分數：15.00 ）填空項1: （正確答案：10）解析：正確答案：仃是空樹或T中所有結點的關鍵字均不大于給定值X時，返回空指針。）解析：while(P > next)P=P > next; P> next=Q;Q > next=NULL;return ok;)/A(分數： 5.00 )正確答案： （ 本程序實現的功能就是：如果 L 的長度不小于 2，則將首元結點刪去并插入到表尾。）解析：五、算法設計題 （ 總題數： 1，分數： 10.00）28. 假設以帶

15、頭結點的單鏈表表示有序表，單鏈表的類型定義如下：typedef struct nodeDataType data;struct node*nextLinkNode,*LinkList;編寫算法，從有序表 A 中刪除所有和有序表 B 中元素相同的結點。（分數： 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 表刪除相同的元素結點q=q> next; 參考答案二：void f34(LinkList ha,LinkList hb) /hb 和hb分