


下載本文檔
版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報或認(rèn)領(lǐng)
文檔簡介
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分
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 創(chuàng)業(yè)設(shè)備分配方案
- 定制沙盤設(shè)計方案
- 建筑公司項(xiàng)目跟進(jìn)方案
- 泰州監(jiān)控安裝服務(wù)方案
- 廠房樓面修補(bǔ)方案(3篇)
- 商用爐臺改造方案
- 航道挖機(jī)清淤方案
- 國企改制實(shí)施方案
- 特殊群體服務(wù)管理方案
- 種植南瓜管理辦法視頻
- 2025年陜西、山西、青海、寧夏高考物理試卷真題(含答案解析)
- 2025年心理咨詢師資格考試試題及答案
- 2025年 呼倫貝爾農(nóng)墾集團(tuán)公司招聘筆試試卷附答案
- 基礎(chǔ)護(hù)理學(xué)練習(xí)題庫(含參考答案)
- 內(nèi)蒙古自治區(qū)赤峰市2023-2024學(xué)年高二下學(xué)期7月期末聯(lián)考數(shù)學(xué)試題 含解析
- 2022-2023學(xué)年廣東省廣州市番禺區(qū)四年級下學(xué)期期末語文真題及答案
- 葉酸培訓(xùn)考試題及答案
- 大慶護(hù)理面試題及答案
- 成人用品的購買渠道分析
- 粉店合伙合同協(xié)議書范本
- 南京師范大學(xué)古代漢語教案
評論
0/150
提交評論