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

(專升本)《數(shù)據(jù)結(jié)構(gòu)》試題(模A)、單項(xiàng)選擇題(從下列各題四個(gè)備選答案中選出一個(gè)正確答案,將其代號(A,B,C,D)寫在下表中，答題寫在其它地方無效；每小題1分，共11分)題號1234567891011答案1.數(shù)據(jù)的不可分割的基本單位是_A.元素B.結(jié)點(diǎn)C.數(shù)據(jù)類型D.數(shù)據(jù)項(xiàng)下列算法suanfa2的時(shí)間復(fù)雜度為。intsuanfa2(intn){intt=1；while(t<=n)t=t*2；returnt；}A.O(logn)B.O(2n)C.O(n2)D.O(n)又稱為FIFO表。A.隊(duì)列B.散列表C.棧D.哈希表若6行8列的數(shù)組以列序?yàn)橹餍蝽樞虼鎯?基地址為1000,每個(gè)元素占2個(gè)TOC\o"1-5"\h\z存儲單元,則第5行第3列的元素(假定無第0行第0列)的地址是。A.1086B.1032C.1068答案A,B,C都不對廣義表(a,((b,()),c),(d,(e))的深度是。A.5B.4C.3D.26?有n(n〉0)個(gè)結(jié)點(diǎn)的完全二叉樹的深度是___。A.「log2(n)]B.「log2(n)+1]C.,log(n+1)_|D.,log(n)+1_|與中綴表達(dá)式a+b*c-d等價(jià)的前綴表達(dá)式。A.+a-*bcdB.*+-abcdC.-+a*bcdD.abcd+*-折半查找有序表(6,15,30,37,65,68,70,72,89,99)若,查找元素37,需依次與表中元素進(jìn)行比較,。A.65,15,37B.68,30,37C.65,15,30D.65,15,30,37對長度為10的表作選擇(簡單選擇)排序,共需比較次關(guān)鍵字。A.45B.90C.55D.110對n個(gè)元素的表作快速排序，在最壞情況下,算法的時(shí)間復(fù)雜度為_。A.O(logn)B.O(nlogn)C.O(n2)D.O(2n)共5頁第1頁對長度為10的表作2_路歸并排序,共需移動次(個(gè))記錄。A.20B.45C.40D.30二、填空(每空1分,共11分)一個(gè)數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的表示(映象)稱為?。線性表中稱為表的長度。TOC\o"1-5"\h\z棧中元素的進(jìn)出原則為。設(shè)數(shù)組A[1..10,1..8]的基地址為2000,每個(gè)元素占2個(gè)存儲單元,若以行序?yàn)橹餍蝽樞虼鎯?則元素A[4,5]的存儲地址為；若以列序?yàn)橹餍蝽樞虼鎯?則元素A[4,5]的存儲地址為。一棵深度為6的滿二叉樹有個(gè)非終端結(jié)點(diǎn)。若一棵二叉樹中有8個(gè)度為2的結(jié)點(diǎn),則它有個(gè)葉子。7?順序查找n個(gè)元素的順序表，當(dāng)使用監(jiān)視哨時(shí),若查找成功，比較關(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]的以列序?yàn)橹餍虻捻樞虼鎯Y(jié)構(gòu)。共5頁第2頁依次將元素A,C,D,B插入一個(gè)初始狀態(tài)為空的鏈?zhǔn)綏Ｖ?試畫出所有插入完成之后的鏈?zhǔn)綏?。二叉樹的順序存儲結(jié)構(gòu):

4.圖的鄰接矩陣:5.有向圖的逆鄰接表:五、求解下列問題(每小題6分,共24分)給定30個(gè)字符組成的電文:DDDDDAAABEEAAFCDAACABBCCCBAADD試為字符A、B、C、D、E、F設(shè)計(jì)哈夫曼(Huffman)編碼。畫出相應(yīng)的哈夫曼樹；分別列出A、B、C、D、E、F的哈夫曼碼；計(jì)算該樹的帶權(quán)路徑長度WPL。共5頁第3頁試按表(10,8,9,12,20,5,6,15,19,25中)元素的排列次序,將所有元素插入一棵初始為空的二叉排序樹中,使之仍是一棵二叉排序樹。試畫出插入完成之后的二叉排序樹；若查找元素17,它將依次與二叉排序樹中哪些元素比較大小?假設(shè)每個(gè)元素的查找概率相等,試計(jì)算該樹的平均查找長度ASL。對該樹進(jìn)行中序遍歷,試寫出中序遍歷序列。}}}}3?試將森林F={T1,T2,T3,T4}轉(zhuǎn)換為一棵二叉樹。AT1T2T3T44.找出下面網(wǎng)絡(luò)的最小生成樹。G):HT1T2T3T44.找出下面網(wǎng)絡(luò)的最小生成樹。六、填空題(在算法中有下劃線的位置填空,使之成為完整、正確的算法)算法說明：已知r[l..n]是n個(gè)記錄的遞增有序表用折半查找法查找關(guān)鍵字為k的記錄,若查找失敗，則輸出”Failure”，返回零；否則輸出”Success”，并返回該記錄的序號值。(共8分)算法(C函數(shù))：共5頁第4頁intbin_search(structarecordr[],intn,k：keytype)/*r[l..n]為n個(gè)記錄的遞增有序表k為關(guān)鍵字*/{intlow,mid,hig；low=1；hig=n；/*各變量初始化*/TOC\o"1-5"\h\zwhile(){mid=；if(k<r[mid].key)；elseif(k==r[mid].key){；1}else；

七、算法設(shè)計(jì)（算法中必須有注釋,每小題8分,共16分）設(shè)n個(gè)元素的線性表順序存儲在一維數(shù)組st[l..maxlen]的前n個(gè)位置上，試將新元素e插入表中第i-1個(gè)和第i個(gè)元素之間，寫出算法。2?設(shè)Head為帶表頭結(jié)點(diǎn)的單鏈表的頭指針試寫出算法:若為非空表,則輸出首結(jié)點(diǎn)和尾結(jié)點(diǎn)的值（data值）；否則輸出：”Emptylist!”。共5頁第5頁（專升本）《數(shù)據(jù)結(jié)構(gòu)》試題（模B、單項(xiàng)選擇題（從下列各題四個(gè)備選答案中選出一個(gè)正確答案，將其代號（A,B,C,D）寫在下表中，答題寫在其它地方無效；每小題1分，共11分）題號1234567891011答案數(shù)據(jù)的基本單位是。結(jié)點(diǎn)B.數(shù)據(jù)元素C.數(shù)據(jù)類型D.數(shù)據(jù)項(xiàng)下列算法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）；}}n(n-l)/2B.n(n+l)/2C.n2D.€nlognl當(dāng)需要隨機(jī)查找線性表的元素時(shí),宜采用作存儲結(jié)構(gòu)。A.雙向鏈表B.循環(huán)鏈表C.順序表D.單鏈表若8行6列的數(shù)組以行序?yàn)橹餍蝽樞虼鎯?基地址為2000,每個(gè)元素占2個(gè)存儲單元,則第5行第3列的元素(假定無第0行第0列)的地址是。A.2086B.2032C.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.對稱B.上三角C.下三角D.稀疏TOC\o"1-5"\h\z&有n(n〉O)個(gè)結(jié)點(diǎn)的完全二叉樹的深度是。A.€log(n)+11B.€log(n)-llC.,log2(n)-ljD.,log2(n)+lj與中綴表達(dá)式a-b/c+d等價(jià)的前綴表達(dá)式是。A.-a+/bcdB./-+bcdC.+-/bcdD.abcd-/+對有3600個(gè)記錄的索引順序表(分塊表)進(jìn)行查找,最理想的塊長為。A.1800B.60C.1200D.€log36001共5頁第1頁11?對n個(gè)元素的表作堆排序，在最壞情況下,算法的時(shí)間復(fù)雜度為_。A.O(logn)B.O(nlogn)C.O(n2)D.O(2n)二、填空題(每空1分,共11分)一個(gè)算法具有5個(gè)特性:、、、有零個(gè)或多個(gè)輸入、有一個(gè)或多個(gè)輸出。設(shè)長度為n的線性表順序存貯若在它的第i-1和第i個(gè)元素之間插入一個(gè)元素共需移動個(gè)元素(1〈iWn)。一個(gè)字符串中稱為該串的子串。4?樹中結(jié)點(diǎn)A的稱為結(jié)點(diǎn)A的度。一棵深度為4的二叉樹最多有個(gè)結(jié)點(diǎn)。具有10個(gè)頂點(diǎn)的無向圖,邊的總數(shù)最多為。7?順序查找n個(gè)元素的順序表，當(dāng)不使用監(jiān)視哨時(shí)，若查找成功,比較關(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頁四、試畫出下列存儲結(jié)構(gòu)圖（每小題5分,共20分）1?試畫出下列稀疏矩陣以列序?yàn)橹餍虻娜M表。r0018LTOC\o"1-5"\h\z3000000240000.00660稀疏矩陣試畫出下列二叉樹的中序線索二叉樹存儲結(jié)構(gòu)圖。二叉樹試用孩子兄弟（左孩子右兄弟）表示法畫出下列樹的存儲結(jié)構(gòu)圖。樹4.試畫出下列有向網(wǎng)的逆鄰接表。有向網(wǎng)共5頁第3頁五、求解下列問題(每小題6分,共24分)1.已知二叉樹的前序遍歷序列和中序遍歷序列分別是：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)假設(shè)每個(gè)元素的查找概率相等，試計(jì)算該樹的平均查找長度ASL；(4)對該樹進(jìn)行中序遍歷試寫出中序遍歷序列。試用權(quán)集合｛4,6,5,12,2,1,13,構(gòu)造赫夫曼(Huffman)樹，(1)列出構(gòu)造過程,(2)分別計(jì)算該赫夫曼樹的路徑長度和帶權(quán)路徑長度。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")；}main(){charch；structnode*q，*p，*f，*head=NUL；Lfor(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è)計(jì)（算法中必須有注釋，每小題8分，共16分）9.具有n（n>0）個(gè)結(jié)點(diǎn)的完全二叉樹的深度為9.具有n（n>0）個(gè)結(jié)點(diǎn)的完全二叉樹的深度為}}設(shè)n個(gè)元素的線性表順序存儲在一維數(shù)組st[l..maxlen]的前n個(gè)位置上,試寫出算法:刪除表中第i（1WiWn）個(gè)元素。2?設(shè)Head為帶表頭結(jié)點(diǎn)的單鏈表的頭指針，試寫出算法:若為非空表，則輸出：最大結(jié)點(diǎn)和最小結(jié)點(diǎn)的值（data值）；否則，輸出：“Emptylist”。共5頁第5頁（專升本）《數(shù)據(jù)結(jié)構(gòu)》試題（模C）、選擇題（從下列各題的4個(gè)備選答案中選出1至2個(gè)正確答案，將其代號（A,B,C,D）寫在下表中，答題寫在其它地方無效；每小題1分，共15分）題號123456789101112121415答案1.由組成的集合是一個(gè)數(shù)據(jù)對象。B.不同類型的數(shù)據(jù)元素D.B.不同類型的數(shù)據(jù)元素D.相同類型的數(shù)據(jù)元素B.{A，B，C，D}D.（1，2，3，...）C.孩子鏈表D.單鏈表相同類型的數(shù)據(jù)項(xiàng)是線性表。A.（孔子，諸葛亮，曹雪芹）C.{10,11,12,13,14}是表示線性數(shù)據(jù)結(jié)構(gòu)的A.循環(huán)鏈表B.鄰接多重表將線性表的數(shù)據(jù)元素以結(jié)構(gòu)存放，查找一個(gè)數(shù)據(jù)元素所需的時(shí)間不依賴于表的長度。A.循環(huán)雙鏈表B.哈希（Hash）表C.一維數(shù)組D.單鏈表設(shè)數(shù)組A[1..8,1..10]的基地址為4000,每個(gè)元素占2個(gè)存儲單元,若以列序?yàn)橹餍蝽樞虼鎯?則元素A[4,7]的存儲地址是____。（假定無第0行第0列元素）A.4072B.4104C.4102D.4074設(shè)依次進(jìn)入一個(gè)棧的元素序列為c,a,b,d,不可得到出棧的元素序列有A.a.b,c,dB.a,d,c,b___A.a.b,c,dB.a,d,c,b___又是一棵滿二叉樹。A.二叉排序樹C.有15個(gè)結(jié)點(diǎn)的完全二叉樹C.b,a,d,cD.c,d,a,b深度為5有31個(gè)結(jié)點(diǎn)的二叉樹哈夫曼（Huffman）樹9.具有n（n>0）個(gè)結(jié)點(diǎn)的完全二叉樹的深度為9.具有n（n>0）個(gè)結(jié)點(diǎn)的完全二叉樹的深度為}}&深度為k的滿二叉樹有個(gè)分枝結(jié)點(diǎn)。A.2k-1B.2k-1-1C.2k+1D.2k-1+1}}A.€log2(n)]B.,log2(n)」+1€log(n+1)]D.,log(n+1)」折半查找20個(gè)記錄的有序表,若查找失敗,比較關(guān)鍵字的次數(shù)。A.最多為6B.最多為5C.最少為3D.最少為4折半查找有序表(2,5,8,20,25,36,40,60),若查找元素60,需依次與表中元素進(jìn)行比較。A.25,40,60B.25,40C.20,36,40,60D.20,36,40查找哈希(Hash)表,解決沖突的的方法有。A.除留余數(shù)法B.線性探測再散列法C.直接地址法D.鏈地址法共5頁第1頁對有10個(gè)記錄的表作簡單選擇排序,需要比較___次關(guān)鍵字。A.100B.45C.50D.90對有n個(gè)記錄的表作快速排序，在最壞情況下,算法的時(shí)間復(fù)雜度是_。A.O(n)B.O(n2)C.O(nlogn)D.O(n3)一個(gè)排序算法時(shí)間復(fù)雜度的大小有關(guān)。A.與所需比較關(guān)鍵字的次數(shù)B.與該算法的穩(wěn)定性C.不與所需移動記錄的數(shù)目D.與所需輔助存儲空間的大小二、畫圖題(每小題4分,共20分)依次輸入元素X,Y,Z,插入到一個(gè)初始狀態(tài)為空的鏈?zhǔn)綏Ｖ性嚠嫵隹盏逆準(zhǔn)綏：兔坎迦胍粋€(gè)元素之后的鏈?zhǔn)綏Ｊ疽鈭D。2?試用雙親表示法畫出下列樹T的存儲結(jié)構(gòu)圖。?①)???樹T試畫出有3行4列元素的二維數(shù)組B的以列序?yàn)橹餍虻捻樞虼鎯Y(jié)構(gòu)圖。試畫出下列圖的鄰接表。

共5頁第2頁已知一棵二叉樹的前序遍歷序列和中序遍歷序列分別是I,A,B,E,F,G,C,H,D和A,E,F,B,I,G,H,C,D試畫出該二叉樹。三、求解問題(每小題7分,共28分)1.用算符優(yōu)先法求下列算術(shù)表達(dá)式的值,試簡要說明求值過程,畫出操作數(shù)棧和運(yùn)算符棧的主要變化過程。12+20/(10-2*3)給定電文(文本):FFAAABBBAAABBCCCDEGGG試為字符A、B、C、D、E、F、G設(shè)計(jì)哈夫曼(Huffman)編碼：(1)畫出相應(yīng)的哈夫曼樹,列出各字符的哈夫曼碼；(2)計(jì)算該哈夫曼樹的帶權(quán)路徑長度。共5頁第3頁3?假定后序遍歷二叉樹的結(jié)果是A,C,B,(1)試畫出所有可得到這一結(jié)果的不同形態(tài)的二叉樹；(2)分別寫出這些二叉樹的中序遍歷序列。假定對20個(gè)記錄的表作折半查找,(1)試畫出描述折半查找過程的判定樹；(2)若每個(gè)記錄的查找概率相等,試計(jì)算