版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認(rèn)領(lǐng)
文檔簡介
wordword格式-可編輯-感謝下載支持(專升本)《數(shù)據(jù)結(jié)構(gòu)》試題(模A)題號答案1題號答案1234567891011數(shù)據(jù)的不可分割的基本單位是 。元素 B.結(jié)點 C.數(shù)據(jù)類型 D.數(shù)據(jù)項下列算法suanfa2的時間復(fù)雜度為 intsuanfa2(intn){intt=1;while(t<=n)t=t*2;returnt;}A.O(logn) B.O(2n) C.O(n2) D.O(n)2 FIFO隊列 B.散列表 C.棧 D.哈希表681000,2存儲單元,則第5行第3列的元素(假定無第0行第0列)的地址是 A.1086 B.1032 C.1068 D.答案A,B,C都不對5.廣義表(a,((b,()),c),(d,(e)))的深度是 。A.5 B.4 C.3 D.2有n(n>0)個結(jié)點的完全二叉樹的深度是 A.log(n) B.log(n)+12 2C.log(n+1) D.log(n)+12 2與中綴表達式a+b*c-d等價的前綴表達式是 A.+a-*bcd B.*+-abcdC.-+a*bcd D.abcd+*-8.折半查找有序表(6,15,30,37,65,68,70,72,89,99),若查找元素37,需依次與表中元素 進行較,。A.65,15,37 B.68,30,37C.65,15,30 D.65,15,30,37對長度為10的表作選擇(簡單選擇)排序,共需比較 次關(guān)鍵字A.45 B.90 C.55 D.110對n個元素的表作快速排序,在最壞情況下,算法的時間復(fù)雜度為 。A.O(logn) B.O(nlogn) C.O(n2) D.O(2n)2 2共5頁第1頁對長度為10的表作2_路歸并排序,共需移動 次(個)記錄A.20 B.45 C.40 D.30二、填空(每空1分,共11分)一個數(shù)據(jù)結(jié)構(gòu)在計算機中的表示(映象)稱為 。線性表中 稱為表的長度。棧中元素的進出原則為 。A[1..10,1..8]2000,2A[4,5]的存儲地址為 ;若以列序為主序順序存儲,則元素A[4,5]的存儲地址為 5.一棵深度為6的滿二叉樹有 個非終端結(jié)點。若一棵二叉樹中有8個度為2的結(jié)點,則它有 個葉子。順序查找n個元素的順序表,當(dāng)使用監(jiān)視哨時,若查找成功,比較關(guān)鍵字的次數(shù)至少為 次,最多為 次;若查找失敗,比較關(guān)鍵字的次數(shù)為 次。對長度為400的表采用分塊(區(qū))查找,最理想的塊長為 。三、回答下列問題(每小題5分,共10分)線性表的存儲結(jié)構(gòu),在什么情況下采用順序結(jié)構(gòu)?為什么?二叉樹有哪幾種基本形態(tài)?畫圖說明之。四、試畫出下列存儲結(jié)構(gòu)圖(每小題4分,共20分)A[1..2,0..2]的以列序為主序的順序存儲結(jié)構(gòu)。共5頁第2頁依次將元素A,C,D,B插入一個初始狀態(tài)為空的鏈?zhǔn)綏V?試畫出所有插入完成之后的鏈?zhǔn)綏?。二叉樹的順序存儲結(jié)構(gòu):圖的鄰接矩陣:word格式-可編輯-感謝下載支持有向圖的逆鄰接表:五、求解下列問題(每小題6分,共24分)30DDDDDAAABEEAAFCDAACABBCCCBAADD試為字符A、B、C、D、E、F設(shè)計哈夫曼(Huffman)編碼。(1)畫出相應(yīng)的哈夫曼樹;(2)分別列出A、B、C、D、E、F的哈夫曼碼;(3)計算該樹的帶權(quán)路徑長度WPL。共5頁第3頁試按表(10,8,9,12,20,5,6,15,19,25序樹中,使之仍是一棵二叉排序樹。試畫出插入完成之后的二叉排序樹;17,它將依次與二叉排序樹中哪些元素比較大小?假設(shè)每個元素的查找概率相等,試計算該樹的平均查找長度ASL(4)對該樹進行中序遍歷,試寫出中序遍歷序列。試將森林F={T1,T2,T3,T4}轉(zhuǎn)換為一棵二叉樹。T1 T2 T3 T4wordword格式-可編輯-感謝下載支持找出下面網(wǎng)絡(luò)的最小生成樹。六、填空題(在算法中有下劃線 的位置填空,使之成為完整、正確的算法)算法說明:已知r[1..n]是n個記錄的遞增有序表,用折半查找法查找關(guān)鍵字為k的記錄,若查找失敗,則輸出”Failure”,返回零;否則輸出”Success”,并返回該記錄的序號值。(共8分)算法(C函數(shù)):共5頁第4頁intbin_search(structarecordr[],intn,k:keytype)/*r[1..n]為n個記錄的遞增有序表,k為關(guān)鍵字*/{intlow,mid,hig;low=1;hig=n; /*各變量初始化while( ){mid= ;if(k<r[mid].key) elseif(k==r[mid].key){ ; ;}else ;} ; ;}七、算法設(shè)計816nst[1..maxlen]nei-1i設(shè)Head為帶表頭結(jié)點的單鏈表的頭指針,試寫出算法:若為非空表,則輸出首結(jié)點和尾結(jié)點的值值);否則輸出:”Emptylist!”。共5頁第5頁(專升本)《數(shù)據(jù)結(jié)構(gòu)》試題(模B題號答案12345題號答案1234567891011數(shù)據(jù)的基本單位是 。A.結(jié)點 B.數(shù)據(jù)元素 C.數(shù)據(jù)類型 D.數(shù)據(jù)項2.下列算法suanfa1中語句"x=x*2;"的執(zhí)行次數(shù)是 voidsuanfa1(intn){inti,j,x=1;for(i=1;i<=n;i++)for(j=i;j<=n;j++)x=x*2;printf("%d",x);}A.n(n-1)/2 B.n(n+1)/2
D.nlogn2當(dāng)需要隨機查找線性表的元素時,宜采用 作存儲結(jié)構(gòu)。A.雙向鏈表 B.循環(huán)鏈表 C.順序表 D.單鏈862000,253的元素(假定無第0行第0列)的地址是 。A.2086 B.2032 C.2068 DA,B,C廣義表(a,(b),c,(d,(e)))的表尾是 。A.(d,(e)) B.(d,(e)))C.(b),c,(d,(e)) 是"Yu**Jia**Shan"的子串。A.Yu B."jia" C."**Shan" 7.無向完全圖的鄰接矩陣是 矩陣。A.對稱 B.上三角 C.下三角 D.稀8.有n(n>0)個結(jié)點的完全二叉樹的深度是 。A.log2(n)+1 C.log2(n)-1 與中綴表達式a-b/c+d等價的前綴表達式是 。A.-a+/bcd B./-+bcdC.+-/bcd D.abcd-/+對有3600個記錄的索引順序表(分塊表)進行查找,最理想的塊長為 A.1800 B.60C.1200 D.log36002共5頁第111.對n個元素的表作堆排序,在最壞情況下,算法的時間復(fù)雜度為 。A.O(logn) B.O(nlogn) C.O(n2) D.O(2n)2 2二、填空題(每空1分,共11分)一個算法具有5個特性: 、 、 、有零個多個輸入、有一個或多個輸出。ni-1i 個元素(1<i≤n)。一個字符串中 稱為該串的子串。樹中結(jié)點A的 稱為結(jié)點A的度。一棵深度為4的二叉樹最多有 個結(jié)點。具有10個頂點的無向圖,邊的總數(shù)最多為 。順序查找n個元素的順序表,當(dāng)不使用監(jiān)視哨時,若查找成功,比較關(guān)鍵字的次數(shù)最多為 次;查找失敗,比較關(guān)鍵字的次數(shù)為 次。8.折半查找有序表(2,4,6,12,20,28,38,50,70,100),若查找表中元素12,它依次與表中元素 比較大小。三、回答下列問題(每小題5分,共10分)線性表的存儲結(jié)構(gòu),在什么情況下采用鏈接表(如:單鏈表)結(jié)構(gòu)?為什么?空格串與空串有區(qū)別?舉例說明之。共5頁第2頁四、試畫出下列存儲結(jié)構(gòu)圖(每小題5分,共20分)試畫出下列稀疏矩陣以列序為主序的三元組表。稀疏矩陣試畫出下列二叉樹的中序線索二叉樹存儲結(jié)構(gòu)圖。二叉樹試用孩子兄弟(左孩子右兄弟)表示法畫出下列樹的存儲結(jié)構(gòu)圖。樹試畫出下列有向網(wǎng)的逆鄰接表。有向網(wǎng)共5頁第3頁五、求解下列問題(每小題6分,共24分)1.已知二叉樹的前序遍歷序列和中序遍歷序列分別是:B,A,C,D,F,E,G和D,C,A,F,G,E,B,試畫出該二叉樹。2.試按表(25,15,19,24,20,5,16,45,40,38)序樹中,使之仍是一棵二叉排序樹。(1)試畫出插入完成之后的二叉排序樹;(2)若查找元素17,它將依次與二叉排序樹中哪些元素比較大小?(3)度ASL;(4)對該樹進行中序遍歷,試寫出中序遍歷序列。試用權(quán)集合{4,6,5,12,2,1,13},構(gòu)造赫夫曼(Huffman)樹,(1)列出構(gòu)造過程,(2)曼樹的路徑長度和帶權(quán)路徑長度。找出下面網(wǎng)絡(luò)的最小生成樹:共5頁第4頁六、執(zhí)行下面的C程序,指出輸出結(jié)果。(8分)#include<stdio.h>#include<stdlib.h>structnode{chardata;structnode*next;};voidlink_list(structnode*p){while(p!=NULL){printf("%c",p->data);p=p->next;}printf("\n");}main(){charch;structnode*q,*p,*f,*head=NULL;for(ch='A';ch<'F';ch++){p=(structnode*)malloc(sizeof(structnode));p->data=ch;p->next=head;head=p;link_list(p);}p=head;head=NULL;while(p!=NULL){q=p;p=p->next;q->next=head;head=q;f=head;while(f->next!=NULL){link_list(head);f=f->next->next;}}}七、算法設(shè)計(算法中必須有注釋,每小題8分,共16分)nst[1..maxlen]的前ni(1≤i≤n)個元素。設(shè)Head(dataEmptylist”。共5頁第5頁(專升本)《數(shù)據(jù)結(jié)構(gòu)》試題(模C)題號答案12題號答案123456789101112121415由 組成的集合是一個數(shù)據(jù)對象。不同類型的數(shù)據(jù)項 B.不同類型的數(shù)據(jù)元C.相同類型的數(shù)據(jù)項 D.相同類型的數(shù)據(jù)元 是線性表。A.(孔子,諸葛亮,曹雪芹) B.{A,B,C,D}C.{10,11,12,13,14} 是表示線性數(shù)據(jù)結(jié)構(gòu)的。循環(huán)鏈表 B.鄰接多重表 C.孩子鏈表 D.單鏈4.將線性表的數(shù)據(jù)元素以 結(jié)構(gòu)存放,查找一個數(shù)據(jù)元素所的時間不依賴于表的長度。A.循環(huán)雙鏈表 B.哈希(Hash)表 C.一維數(shù)組 D.單鏈表設(shè)數(shù)組A[1..8,1..10]的基地址為4000,每個元素占2個存儲單元,若以列序為主序順序存儲,則元A[4,7]的存儲地址是 。(假定無第0行第0列元素)A.4072 B.4104 C.4102 D.4074設(shè)依次進入一個棧的元素序列為c,a,b,d,不可得到出棧的元素序列有 A.a.b,c,d B.a,d,c,b C.b,a,d,c D.c,d,a,b 又是一棵滿二叉樹。二叉排序樹 B.深度為5有31個結(jié)點的二叉C.有15個結(jié)點的完全二叉樹 D.哈夫曼(Huffman)樹深度為k的滿二叉樹有 個分枝結(jié)點。A.2k-1 B.2k-1-1 C.2k+1 具有n(n>0)個結(jié)點的完全二叉樹的深度為 。log(n) B.log(n)+12 2C.log(n+1) D.log(n+1)2 2折半查找20個記錄的有序表,若查找失敗,比較關(guān)鍵字的次數(shù) A.最多為6 B.最多為5 C.最少為3 D.最少為411.折半查找有序表(2,5,8,20,25,36,40,60),若查找元素60,需依次表中元素 進行比較。A.25,40,60 B.25,40 C.20,36,40,60 D.20,36,40查找哈希(Hash)表,解決沖突的的方法有 。除留余數(shù)法 B.線性探測再散列法 C.直接地址法 D.鏈地址
共5頁第1頁對有10個記錄的表作簡單選擇排序,需要比A.100 B.45 C.50 D.90
次關(guān)鍵字。對有n個記錄的表作快速排序,在最壞情況下,算法的時間復(fù)雜度是 。A.O(n) B.O(n2) C.O(nlogn) D.O(n3)2一個排序算法時間復(fù)雜度的大小 有關(guān)。與所需比較關(guān)鍵字的次數(shù) B.與該算法的穩(wěn)定性C.不與所需移動記錄的數(shù)目 D.與所需輔助存儲空間的大小二、畫圖題(每小題4分,共20分)依次輸入元素X,Y,Z,后的鏈?zhǔn)綏J疽鈭D。T34B試畫出下列圖的鄰接表。圖共5頁第2頁I,A,B,E,F,G,C,H,DA,E,F,B,I,G,H,C,D試畫出該二叉樹。三、求解問題(每小題7分,共28分)過程。12+20/(10-2*3)給定電文(文本):FFAAABBBAAABBCCCDEGGG試為字符A、B、C、D、E、F、G設(shè)計哈夫曼(Huffman)編碼:(1)畫出相應(yīng)的哈夫曼樹,列出各字符的哈夫曼碼;(2)計算該哈夫曼樹的帶權(quán)路徑長度。共5頁第3頁假定后序遍歷二叉樹的結(jié)果是A,C,B,(1)試畫出所有可得到這一結(jié)果的不同形態(tài)的二叉樹;(2)寫出這些二叉樹的中序遍歷序列。假定對20個記錄的表作折半查找
溫馨提示
- 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)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 2025年度公益慈善晚會活動策劃與實施合同4篇
- 2025年度互聯(lián)網(wǎng)內(nèi)容提供商ICP證年審全權(quán)委托服務(wù)合同3篇
- 二零二五年度生物科技研發(fā)農(nóng)民工就業(yè)服務(wù)合同4篇
- 電子商務(wù)平臺消費者權(quán)益保護2025年度國際協(xié)調(diào)合同2篇
- 2025年度牛肝菌有機認(rèn)證與市場拓展合同
- 二零二五版昆明滇池度假區(qū)酒店管理合同3篇
- 二零二五年度農(nóng)業(yè)種植勞務(wù)作業(yè)承包合同范本3篇
- 2025年度塑料管材國際貿(mào)易爭端解決合同
- 2025年度私立學(xué)校校長任期教育科研成果轉(zhuǎn)化合同
- 二零二五年度企業(yè)員工期權(quán)激勵合同范本
- 廣東省佛山市2025屆高三高中教學(xué)質(zhì)量檢測 (一)化學(xué)試題(含答案)
- 人教版【初中數(shù)學(xué)】知識點總結(jié)-全面+九年級上冊數(shù)學(xué)全冊教案
- 四川省成都市青羊區(qū)成都市石室聯(lián)合中學(xué)2023-2024學(xué)年七上期末數(shù)學(xué)試題(解析版)
- 2024-2025學(xué)年人教版七年級英語上冊各單元重點句子
- 2025新人教版英語七年級下單詞表
- 公司結(jié)算資金管理制度
- 2024年小學(xué)語文教師基本功測試卷(有答案)
- 未成年入職免責(zé)協(xié)議書
- 項目可行性研究報告評估咨詢管理服務(wù)方案1
- 5歲幼兒數(shù)學(xué)練習(xí)題
- 2024年全國體育單招英語考卷和答案
評論
0/150
提交評論