專升本數(shù)據(jù)結(jié)構(gòu)試題三套

word格式-可編輯-感謝下載支持(專升本)《數(shù)據(jù)結(jié)構(gòu)》試題(模A)一、單項選擇題(從下列各題四個備選答案中選出一個正確答案，將其代號(A,B,C,D)寫在下表中,答題寫在其它地方無效；每小題1分，共11分)題號1234567891011答案1.數(shù)據(jù)的不可分割的基本單位是A.元素B.結(jié)點 C.數(shù)據(jù)類型 D.數(shù)據(jù)項.下列算法suanfa2的時間復(fù)雜度為—。intsuanfa2(intn){intt=1；while(t<=n)t=t*2；returnt；)A.O(log2n) B.O(2n) C.O(n2) D.O(n).又稱為FIFO表。A.隊列B.散列表C.棧D.哈希表.若6行8列的數(shù)組以列序為主序順序存儲,基地址為1000,每個元素占2個存儲單元,則第5行第3列的元素(假定無第0行第0列U)的地址是一。A.1086 B.1032 C.1068D.答案A,B,C都不對.廣義表(a,((b,()),c),(d,(e)))的深度是一。A.5 B.4 C.3 D.2.有n(n>0)個結(jié)點的完全二叉樹的深度是。A.「logjn)] B.「logJn)+1]C.|_log2(n+1)」 D.|_log2(n)+1」.與中綴表達式a+b*c-d等價的前綴表達式是一。A.+a-*bcd B.*+-abcdC.-+a*bcd D.abcd+*-.折半查找有序表(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(log2n) B.O(nlog2n) C.O(n2) D.O(2n)2 2 共5頁第1頁11.對長度為10的表作2.路歸并排序,共需移動一次(個)記錄。A.20 B.45 C.40 D.30二、填空(每空1分，共11分).一個數(shù)據(jù)結(jié)構(gòu)在計算機中的表示(映象)稱為。.線性表中稱為表的長度。.棧中元素的進出原則為。

word格式-可編輯-感謝下載支持.設(shè)數(shù)組A[1..10,1..8]的基地址為2000,每個元素占2個存儲單元,若以行序為主序順序存儲,則元素word格式-可編輯-感謝下載支持.一棵深度為6的滿二叉樹有個非終端結(jié)點。.若一棵二叉樹中有8個度為2的結(jié)點,則它有個葉子。.順序查找n個元素的順序表,當使用監(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分）.數(shù)組A[1..2,0..2]的以列序為主序的順序存儲結(jié)構(gòu)。共5頁第2頁.依次將元素A,C,D,B插入一個初始狀態(tài)為空的鏈式棧中，試畫出所有插入完成之后的鏈式棧。.二叉樹的順序存儲結(jié)構(gòu):.圖的鄰接矩陣:

word格式word格式-可編輯-感謝下載支持.有向圖的逆鄰接表：(!&)五、求解下列問題(每小題6分，共24分).給定30個字符組成的電文：DDDDDAAABEEAAFCDAACABBCCCBAADD試為字符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)中元素的排列次序，將所有元素插入一棵初始為空的二叉排序樹中，使之仍是一棵二叉排序樹。(1)試畫出插入完成之后的二叉排序樹；(2)若查找元素17,它將依次與二叉排序樹中哪些元素比較大小？(3)假設(shè)每個元素的查找概率相等,試計算該樹的平均查找長度ASL。(4)對該樹進行中序遍歷,試寫出中序遍歷序列。3.試將森林F={T1,T2,T3,T4}轉(zhuǎn)換為一棵二叉樹。T1T2T33.試將森林F={T1,T2,T3,T4}轉(zhuǎn)換為一棵二叉樹。T1T2T3T4word格式-可編輯-感謝下載支持4.找出下面網(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è)計(算法中必須有注釋,每小題8分，共16分).設(shè)n個元素的線性表順序存儲在一維數(shù)組st[1..maxlen]的前n個位置上,試將新元素e插入表中第i-1個和第i個元素之間，寫出算法。.設(shè)Head為帶表頭結(jié)點的單鏈表的頭指針,試寫出算法:若為非空表,則輸出首結(jié)點和尾結(jié)點的值(data值)；否則輸出："Emptylist!”。word格式-可編輯-感謝下載支持共5頁第5頁(專升本)《數(shù)據(jù)結(jié)構(gòu)》試題(模B、單項選擇題(從下列各題四個備選答案中選出一個正確答案，將其代號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 C.n2 D.「nlogj].當需要隨機查找線性表的元素時,宜采用―作存儲結(jié)構(gòu):兒雙向鏈表 B.循環(huán)鏈表C.順序表D.單鏈表.若8行6列的數(shù)組以行序為主序順序存儲,基地址為2000,每個元素占2個存儲單元,則第5行第3列的元素(假定無第0行第0列U)的地址是一。A.2086 B.2032 C.2068D.答案A,B,C都不對.廣義表(a,(b),c,(d,(e)))的表尾是一。A.(d,(e)) B.(d,(e)))C.(b),c,(d,(e)) D.((b),c,(d,(e))).是"Yu**Jia**Shan”的子串。A.YuB."jia"C.”**Shan"D."YuJiaShan”.無向完全圖的鄰接矩陣是—矩陣。A.對稱8.上三角^下三角D.稀疏.有n(n>0)個結(jié)點的完全二叉樹的深度是。A.「log2(n)+1] B.「log2(n)-1]C.Llog2(n)-1J D.]log2(n)+1」word格式-可編輯-感謝下載支持.與中綴表達式a-b/c+d等價的前綴表達式是一。A.-a+/bcd B./-+bcdC.+-/bcd D.abcd-/+.對有3600個記錄的索引順序表(分塊表)進行查找,最理想的塊長為―。A.1800 B.60C.1200 D.「log2360012 共5頁第1頁11.對n個元素的表作堆排序,在最壞情況下,算法的時間復(fù)雜度為―。A.O(log2n) B.O(nlog2n) C.O(n2) D.O(2n)二、填空題(每空1分，共11分).一個算法具有5個特性:、、、有零個或多個輸入、有一個或多個輸出。.設(shè)長度為n的線性表順序存貯,若在它的第i-1和第i個元素之間插入一個元素，共需移動個元素(1<iWn)。.一個字符串中稱為該串的子串。.樹中結(jié)點A的稱為結(jié)點A的度。.一棵深度為4的二叉樹最多有個結(jié)點。.具有10個頂點的無向圖,邊的總數(shù)最多為。.順序查找n個元素的順序表，當不使用監(jiān)視哨時，若查找成功，比較關(guān)鍵字的次數(shù)最多為一次；若查找失敗，比較關(guān)鍵字的次數(shù)為次。.折半查找有序表(2,4,6,12,20,28,38,50,70,100),若查找表中元素12,它依次與表中元素 比較大小。三、回答下列問題(每小題5分，共10分).線性表的存儲結(jié)構(gòu),在什么情況下采用鏈接表(如:單鏈表)結(jié)構(gòu)?為什么？.空格串與空串有區(qū)別？舉例說明之。共5頁第2頁word格式-可編輯-感謝下載支持四、試畫出下列存儲結(jié)構(gòu)圖（每小題5分，共20分）.試畫出下列稀疏矩陣以列序為主序的三元組表。TOC\o"1-5"\h\z0 C ：X 03 C 。 CC C （［24（：：（：：（：：（：：L（：： （：： 66 。稀疏矩陣.試畫出下列二叉樹的中序線索二叉樹存儲結(jié)構(gòu)圖。二叉樹.試用孩子兄弟（左孩子右兄弟）表示法畫出下列樹的存儲結(jié)構(gòu)圖。樹4.試畫出下列有向網(wǎng)的逆鄰接表。有向網(wǎng)共5頁第3頁五、求解下列問題（每小題6分，共24分）.已知二叉樹的前序遍歷序列和中序遍歷序列分別是:B,A,C,D,F,E,G和D,C,A,F,G,E,B,

試畫出該二叉樹。word試畫出該二叉樹。word格式-可編輯-感謝下載支持.試按表(25,15,19,24,20,5,16,45,40,38)中元素的排列次序,將所有元素插入一棵初始為空的二叉排序樹中，使之仍是一棵二叉排序樹。(1)試畫出插入完成之后的二叉排序樹；(2)若查找元素17,它將依次與二叉排序樹中哪些元素比較大??？(3)假設(shè)每個元素的查找概率相等，試計算該樹的平均查找長度ASL；(4)對該樹進行中序遍歷，試寫出中序遍歷序列。.試用權(quán)集合{4,6,5,12,2,1,13},構(gòu)造赫夫曼(Huffman)樹，(1)列出構(gòu)造過程，(2)分別計算該赫夫曼樹的路徑長度和帶權(quán)路徑長度。4.找出下面網(wǎng)絡(luò)的最小生成樹:4.找出下面網(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〃)；

word格式word格式-可編輯-感謝下載支持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分).設(shè)n個元素的線性表順序存儲在一維數(shù)組st[1..maxlen]的前n個位置上，試寫出算法:刪除表中第i(1WiWn)個元素。.設(shè)Head為帶表頭結(jié)點的單鏈表的頭指針,試寫出算法:若為非空表,則輸出：最大結(jié)點和最小結(jié)點的值（data值）；否則，輸出：“Emptylist”。共5頁第5頁（專升本）《數(shù)據(jù)結(jié)構(gòu)》試題（模C）A.不同類型的數(shù)據(jù)項C.相同類型的數(shù)據(jù)項.一是線性表。A.（孔子,諸葛亮,曹雪芹）C.{10,11,12,13,14}.一是表示線性數(shù)據(jù)結(jié)構(gòu)的。A.不同類型的數(shù)據(jù)項C.相同類型的數(shù)據(jù)項.一是線性表。A.（孔子,諸葛亮,曹雪芹）C.{10,11,12,13,14}.一是表示線性數(shù)據(jù)結(jié)構(gòu)的。A.循環(huán)鏈表B.鄰接多重表B.不同類型的數(shù)據(jù)元素D.相同類型的數(shù)據(jù)元素B.{A,B,C,D}D.（1,2,3,...）C.孩子鏈表 D.單鏈表4.將線性表的數(shù)據(jù)元素以結(jié)構(gòu)存放，查找一個數(shù)據(jù)元素所需word格式word格式-可編輯-感謝下載支持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,dB.a,d,c,bC.b,a,d,cD.c,d,a,b.又是一棵滿二叉樹。A.二叉排序樹 B.深度為5有31個結(jié)點的二叉樹C.有15個結(jié)點的完全二叉樹 D.哈夫曼(Huffman)樹.深度為k的滿二叉樹有一個分枝結(jié)點。A.2k-1 B.2k-1-1 C.2k+1 D.2k-1+1.具有n(n>0)個結(jié)點的完全二叉樹的深度為。A.「log?(n)] B.Llog2(n)J+1C.「log?(n+1)] D.Llog2(n+1)J.折半查找20個記錄的有序表,若查找失敗，比較關(guān)鍵字的次數(shù)—。A.最多為6 B.最多為5 C.最少為3 D.最少為4.折半查找有序表(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)表,解決沖突的的方法有。A.除留余數(shù)法 B.線性探測再散列法 C.直接地址法 D.鏈地址法共5頁第1頁.對有10個記錄的表作簡單選擇排序,需要比較一次關(guān)鍵字。A.100 B.45 C.50 D.90.對有n個記錄的表作快速排序,在最壞情況下,算法的時間復(fù)雜度是—。A.O(n) B.O(n2) C.O(nlog2n) D.O(n3).一個排序算法時間復(fù)雜度的大小—二有關(guān)。A.與所需比較關(guān)鍵字的次數(shù) B.與該算法的穩(wěn)定性C.不與所需移動記錄的數(shù)目 D.與所需輔助存儲空間的大小二、畫圖題(每小題4分，共20分).依次輸入元素X,Y,Z,插入到一個初始狀態(tài)為空的鏈式棧中,試畫出空的鏈式棧和每插入一個元素之后的鏈式棧示意圖。.試用雙親表示法畫出下列樹T的存儲結(jié)構(gòu)圖。word格式-可編輯-感謝下載支持.試畫出有3行4列元素的二維數(shù)組B的以列序為主序的順序存儲結(jié)構(gòu)圖。4.試畫出下列圖的鄰接表。圖共5頁第2頁5.已知一棵二叉樹的前序遍歷序列和中序遍歷序列分別是：I,A,B,E,F,G,C,H,D和A,E,F,B,I,G,H,C,D試畫出該二叉樹。三、求解問題（每小題7分，共28分）.用算符優(yōu)先法求下列算術(shù)表達式的值,試簡要說明求值過程,畫出操作數(shù)棧和運算符棧的主要變化過程。12+20/(10-2*3).給定電文（文本）:word格式-可編輯-感謝下載支持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）試畫出描述折半查找過程的判定樹；（2）若每個記錄的查找概率相等,試計算查找成功時的平均查找長度。四、分