




已閱讀5頁,還剩2頁未讀, 繼續(xù)免費閱讀
版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認領(lǐng)
文檔簡介
姓名: 學(xué)號: 系別: 年級專業(yè): ( 密 封 線 內(nèi) 不 答 題 )密封線線東莞理工學(xué)院(本科)試卷(A 卷)2009 -2010 學(xué)年第二學(xué)期算法與數(shù)據(jù)結(jié)構(gòu)試卷(A 卷)一、填空題(每小題2分,共18分)1、 對于給定的n個元素,可以構(gòu)造出的邏輯結(jié)構(gòu)有集合, , 和 四種。2、 數(shù)據(jù)結(jié)構(gòu)中評價算法的兩個重要指標(biāo)是 和 。3、 在順序存儲結(jié)構(gòu)中,邏輯上相鄰的數(shù)據(jù)元素,其物理位置 ,在單鏈表中,邏輯上相鄰的數(shù)據(jù)元素,其物理位置 。4、 棧是操作受限的線性表,其操作數(shù)據(jù)的基本原則是 ,允許進行插入和刪除操作的一端稱為 。5、 設(shè)有一個二維數(shù)組A1010,若每個元素占6個基本存儲單元,A00的地址是1000,若按行優(yōu)先(以行為主)順序存儲,則元素A68的存儲地址是 ;若按列優(yōu)先(以列為主)順序存儲,則元素A68的存儲地址是 。6、 設(shè)有一棵深度為n的完全二叉樹,該二叉樹至少有 個結(jié)點,至多有 個結(jié)點。7、 若采用鄰接矩陣存儲一個圖所需要的存儲單元取決于圖的 ;無向圖的鄰接矩陣一定是 。8、 在進行排序時,最基本的操作是 和 。9、 在查找時,若采用折半查找,要求線性表 ,而哈希表的查找,要求線性表 。二、單項選擇題(請將答案寫在題目后的括號中。每題2分,共18分)1、設(shè)有長度為n的數(shù)組a,假設(shè)已經(jīng)賦值,下面程序段的時間復(fù)雜度是( )。for (i=0; in-1; i+) k=i ;for (j=i+1; jaj) k=j ; if (k!=i) temp=ai; ai=ak ; ak=temp ; (A) O(n) (B) O(n2) (C) O(2n) (D) O(n2n)2、 設(shè)有以head為頭結(jié)點的非空單循環(huán)鏈表,鏈表中只有一個結(jié)點條件是( )。(A) head-next=head ; (B) head-next=head-next ;(C) head-next-next=head ; (D) head-next-next=head-next; 3、設(shè)有一個大小為Max的循環(huán)隊列Q,判斷該隊列為滿的條件是( )。(A) Q.rear-Q.front=Max (B) Q.rear-Q.front-1=Max(C) Q.rear=Q.front (D) (Q.rear+1)%Max=Q.front 4、二叉樹是非線性結(jié)構(gòu),因此( )(A) 不能用順序存儲結(jié)構(gòu)存儲 (B) 不能用鏈?zhǔn)酱鎯Y(jié)構(gòu)存儲 (C) 既能用鏈?zhǔn)酱鎯Y(jié)構(gòu)存儲,也能用順序存儲結(jié)構(gòu)存儲 (D) 既不能用鏈?zhǔn)酱鎯Y(jié)構(gòu)存儲,也不能用順序存儲結(jié)構(gòu)存儲5、設(shè)有一棵二叉樹,其先序遍歷序列是acdgehibfkj,中序遍歷序列是dgcheiabkfj,則該二叉樹的后序遍歷序列是( )。(A) gdehickjfba (B) gdhiecfkjba (C) dghieckjfba (D) gdhieckjfba6、 在一個有向圖中,所有頂點的出度之和等于所有頂點的入度之和的 倍,所有頂點的度之和等于所有頂點的出度之和的 倍。( )(A) 1/2,1 (B) 1,2 (C) 2,1 (D) 1,47、對于有n個頂點e(en)條邊的帶權(quán)無向圖,以下關(guān)于該圖的最小生成樹的描述正確的是( )。姓名: 學(xué)號: 系別: 年級專業(yè): ( 密 封 線 內(nèi) 不 答 題 )密封線線(A) 最小生成樹是唯一的。(B) 最小生成樹中所有邊上的權(quán)值之和是唯一的。(C) 最小生成樹有n條邊。(D) 最小生成樹有n個頂點e-1條邊。8、 設(shè)有關(guān)鍵集合21,12,46,40,32,29,65,53,采用冒泡排序法進行一趟排序操作后的結(jié)果是( )。(A)12,21,46,40,32,29,53,65 (B) 12,21,40,46,32,29,53,65(C)12,21,40,32,46,29,53,65 (D) 12,21,40,32,29,46,53,659、設(shè)有一組記錄的關(guān)鍵字為19, 41, 23, 38, 28, 54, 84, 27,用鏈地址法構(gòu)造哈希表,哈希函數(shù)為H(key)=key MOD 13,哈希地址為2的鏈表中有 個記錄。( )(A) 3 (B) 4 (C) 2 (D) 1三、分析題(每題6分,共30分)1、 設(shè)有一棵樹,采用雙親表示法的存儲結(jié)構(gòu)如右圖,請解決以下問題:01234567891011A -1B 0C 0D 0E 1F 1G 2H 2I 2J 3K 4M 4 畫出該樹的邏輯結(jié)構(gòu) (2分) 給出對該樹進行先序遍歷的遍歷序列 (1分) 畫出將該樹轉(zhuǎn)換的二叉樹 (2分) 給出對轉(zhuǎn)換后的二叉樹的后序遍歷序列 (1分)2、 對于下圖中的帶權(quán)無向圖,請解決以下問題: 畫出該圖的鄰接鏈表; (2分) 根據(jù)您畫出的鄰接鏈表寫出其廣度優(yōu)先搜索生成樹(假設(shè)從頂點3出發(fā)); (2分) 給出按Kruskal算法得到的最小生成樹。 (2分)152435710334983、 將關(guān)鍵字序列(18,22,13,37,4,9,25,15,20)插入到初態(tài)為空的二叉排序樹中,請畫出建立二叉排序樹T;然后畫出刪除13之后的二叉排序樹T1;再畫出插入13之后的二叉排序樹T2。姓名: 學(xué)號: 系別: 年級專業(yè): ( 密 封 線 內(nèi) 不 答 題 )密封線線4、 線性表的關(guān)鍵字集合51,25,18,39,42,69,35,33,17,56,47,13,8,共有13個元素,已知散列函數(shù)為:H(k) = k MOD 11,采用鏈地址處理沖突,請給出對應(yīng)的散列表結(jié)構(gòu)。5、 已知關(guān)鍵字集合15,29,33,40,17,39,18,21,12,45,52,43,9,請給出采用增量序列為5, 3, 1的希爾排序法,對該序列做非遞減排序時的每一趟結(jié)果。四、算法填空(每空2分,共20分)請在下面各算法的空白處填上相應(yīng)語句以實現(xiàn)算法功能。每個空白只能填一個語句。1、設(shè)有鏈隊列,其數(shù)據(jù)結(jié)構(gòu)定義如下。然后進行出隊操作,將出隊的隊首元素的數(shù)據(jù)通過指針變量x帶回。typedef struct Qnode ElemType data ;struct Qnode *next ;QNode ;typedef struct link_queue QNode *front , *rear ;Link_Queue ;int Delete_LinkQueue(LinkQueue *Q, ElemType *x) QNode *p ;if (Q-front=Q-rear) return 0 ; /* 隊空 */p=Q-front-next ; /* 取隊首結(jié)點 */ ; Q-front-next=p-next ; if (p=Q-rear) ; free(p) ; return 1 ; 2、設(shè)T是指向二叉樹根結(jié)點的指針變量,對二叉樹進行中序遍歷的非遞歸算法。數(shù)據(jù)結(jié)構(gòu)定義如下:typedef struct BTNode ElemType data ;struct BTNode *Lchild , *Rchild ;BTNode ; #define MAX_NODE 50void InorderTraverse( BTNode *T) BTNode *StackMAX_NODE ,*p=T ; int top=0 , bool=1 ; if (T=NULL) printf(“ Binary Tree is Empty!n”) ; else do姓名: 學(xué)號: 系別: 年級專業(yè): ( 密 封 線 內(nèi) 不 答 題 )密封線線 while (p!=NULL) ; p=p-Lchild ; if (top=0) bool=0 ; else p=stacktop ; top- ; visit( p-data ) ; ; ; 3、 圖的鄰接鏈表的結(jié)點結(jié)構(gòu)如下圖所示。下面算法是從頂點v出發(fā),遞歸地深度優(yōu)先搜索圖G。adjvex info nextarc表結(jié)點data firstarc頂點結(jié)點typedef emnu FALSE , TRUE BOOLEAN ;#define MAX_VEX_NUM 30 /* 最大頂點數(shù) */BOOLEAN VisitedMAX_VEX_NUM ;void DFS(ALGraph *G , int v) LinkNode *p ; Visitedv=TRUE ; Visitv ; /* 置訪問標(biāo)志,訪問頂點v */ ; while (p!=NULL) if (!Visitedp-adjvex) ; ; 4、 冒泡排序算法。#define FALSE 0#define TRUE 1Void Bubble_Sort(Sqlist *L) int j ,k ,flag ; for (j=0; jlength; j+) /* 共有n-1趟排序 */ flag=TRUE ; for (k=1; klength-j; k+) /* 一趟排序 */ if ( ) flag=FALSE ; L-R0=L-Rk ; L-Rk=L-Rk+1 ; L-Rk+1=L-R0 ; if ( ) break ; 五、編寫算法(共14分)1、用頭插入法創(chuàng)建單鏈表,以輸入最大整數(shù)32767作為結(jié)束,鏈表的頭結(jié)點head作為返回值的算法函數(shù)。 (6分)數(shù)據(jù)結(jié)構(gòu)定義如下:typedef struct Lnode int data; /*數(shù)
溫馨提示
- 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)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 海南省??谑斜灸甓龋?025)小學(xué)一年級數(shù)學(xué)統(tǒng)編版期末考試((上下)學(xué)期)試卷及答案
- 2025-2030年中國數(shù)控鋸床行業(yè)發(fā)展監(jiān)測及投資形勢預(yù)測研究報告
- 船舶建造標(biāo)準(zhǔn)與法規(guī)遵循考核試卷
- 殘疾人座車燃油經(jīng)濟性分析考核試卷
- 電工儀表的模塊化生產(chǎn)考核試卷
- 紡織品的印染與花紋設(shè)計考核試卷
- 稀土金屬冶煉的政府采購考核試卷
- 玻璃保溫容器生產(chǎn)過程監(jiān)測與故障診斷技術(shù)實踐探索分析考核試卷
- 美容儀器原理與應(yīng)用考核試卷
- 編織品的結(jié)構(gòu)設(shè)計原理考核試卷
- 2025年無人機駕駛員職業(yè)技能考核試卷(無人機操控技術(shù))
- 2025-2030中國延緩衰老食品行業(yè)深度調(diào)研及市場需求與投資研究報告
- 頌缽療愈師培訓(xùn)課程大綱
- 2025年中國汽車零部件市場研究報告-2025-04-零部件
- 2025年關(guān)于美發(fā)學(xué)員合同
- 2025-2030中國改性塑料市場盈利能力預(yù)測及發(fā)展機遇規(guī)模研究報告
- 2024-2025年部編版語文小學(xué)二年級下冊全冊單元測試題(共8個單元附答案)
- 一年級下冊口算題卡大全(50套直接打印版)
- (高清版)JTG D81-2017 公路交通安全設(shè)施設(shè)計規(guī)范
- SpaceClaim.中文教程完整版
評論
0/150
提交評論