數據結構自考題-2_第1頁
數據結構自考題-2_第2頁
數據結構自考題-2_第3頁
免費預覽已結束,剩余5頁可下載查看

下載本文檔

版權說明:本文檔由用戶提供并上傳,收益歸屬內容提供方,若內容存在侵權,請進行舉報或認領

文檔簡介

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分

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯系上傳者。文件的所有權益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網頁內容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
  • 4. 未經權益所有人同意不得將文件中的內容挪作商業或盈利用途。
  • 5. 人人文庫網僅提供信息存儲空間,僅對用戶上傳內容的表現方式做保護處理,對用戶上傳分享的文檔內容本身不做任何修改或編輯,并不能對任何下載內容負責。
  • 6. 下載文件中如有侵權或不適當內容,請與我們聯系,我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論