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

word格-專升本)《據(jù)結(jié)》題(A)一單選題(從下列各四個備選答案中選出一個正確答案,將代號(A,B,C,D)寫在下表中答題寫在其它地方無效；每小題1分,共11分)題答

234678910111.數(shù)據(jù)的不可分割的基本單位是___。A.元素B.結(jié)點(diǎn)C.數(shù)據(jù)類D.數(shù)據(jù)項2.下列算法suanfa2的間復(fù)雜為____。intsuanfa2(intn){intt=1；while(t<=n)t=t*2；returnt；}A.O(logn)B.O(2)C.O(n)D.O(n)3.____又稱為表A.隊列B.散列表C.棧D.哈希表4.若6行列數(shù)組以列序為主順序存儲,基址為1000,每個元素占個存儲單元,則第5行3列的元素假定無第0行第0)地址是___。A.1086B.1032C.1068D.答案A,B,C都不5.廣義表a,((b,()),c),(d,(e)))深度是____A.5B.4C.3D.26.有個點(diǎn)的完全二叉樹深度是____。A.(n)C.(n+1)

B.(n)+1D.(n)+17.與中綴表達(dá)式a+b*c-d等的綴表達(dá)式是____。A.+a-*bcdB.*+-abcdC.-+a*bcdD.abcd+*-8.折半查找有序表6,15,30,37,65,68,70,72,89,99),若查找元素37,需依次較。A.65,15,37B.68,30,37C.65,15,30D.65,15,30,379.對長度為10的表作選擇簡選擇)序,共需比較____關(guān)鍵字。A.45B.90C.55D.11010.對n個素的表作快速排序,最壞情況下,算法的時間復(fù)雜度為___。A.O(logn)B.O(nlogn)C.O(nD.O(2

與表中元素___進(jìn)比共5頁1頁11.對長度為10的表作2_路歸排序,共移動___次個記。A.20B.45C.40D.30二填每空1分,共11分1.一個數(shù)據(jù)結(jié)構(gòu)在計算機(jī)中的表映象)稱為________________?。2.線性表中____________________________稱為表的長度。3.棧中元素的進(jìn)出原則為_____________________。

word格-4.設(shè)數(shù)組A[1..10,1..8]的基地為2000,每個元素占2個存儲單元若以行序為主序順序存儲則素A[4,5]的存儲地址為_____；以列序為主序順序存儲則元素A[4,5]的儲地址為______。5.一棵深度為的二叉樹有______非終端結(jié)點(diǎn)。6.若一棵二叉樹中有個為2結(jié)點(diǎn),則它有_____個葉子。7.順序查找個素的順序表當(dāng)用監(jiān)視哨時,若查找成功比較關(guān)鍵字的次數(shù)至少為___次,最為____次；若查找失敗比較關(guān)鍵字的次數(shù)為___次。8.對長度為400的表用分塊區(qū)查找,最理想的塊長為___三回下問(小題5,共分1.線性表的存儲結(jié)構(gòu),在什么情下采用順序結(jié)構(gòu)?為么?2.二叉樹有哪幾種基本形態(tài)畫說明之。四試出列儲構(gòu)(每小題4分共分1.數(shù)組A[1..2,0..2]的列序為主序的順序存儲結(jié)構(gòu)。共5頁2頁2.依次將元素A,C,D,B插入個初始狀態(tài)為空的鏈?zhǔn)綏Ｖ?試畫出所有插入完成之后的鏈?zhǔn)綏！?.二叉樹的順序存儲結(jié)構(gòu):4.圖的鄰接矩陣:

word格-5.有向圖的逆鄰接表:五、求解下列問題(每小題6分共分1.給定30個字符組成的電文:DDDDDAAABEEAAFDAACABBCCCBAADD試為字符A、C、D、E、F設(shè)哈夫曼(Huffman)編碼。(1)畫出相應(yīng)的哈夫曼樹；(2)分別列出A、C、D、F的夫曼碼；(3)計算該樹的帶權(quán)路徑長度WPL。共5頁3頁2.試按表10,8,9,12,20,5,6,15,19,25中素的排列次序?qū)⒂性夭迦胍豢贸跏紴榭盏亩判驑渲惺谷允且豢枚媾判驑洹?1)試畫出插入完成之后的二叉序樹；(2)若查找元素17,它將依次與叉排序樹中哪些元素比較大小?(3)假設(shè)每個元素的查找概率相試計算該樹的平均查找長度ASL。(4)對該樹進(jìn)行中序遍歷試出序遍歷序列。3.試將森林F={T1,T2,T3,T4}轉(zhuǎn)為一棵二叉樹。T1T2T3T4

word格-4.找出下面網(wǎng)絡(luò)的最小生成樹。六填題(在算法中有下劃線____位置填空使成為完整、正確的算法)算說已知r[1..n]是n個記錄的遞增有序表用半找法查找關(guān)鍵字為k記錄,查找失敗,則輸出”Failure”,返零；否則輸出”Success”,返回該記錄的序號值。共8分算(C函)共5頁4頁intbin_search(structr[],intn,k:keytype)/*r[1..n]為n個記錄的遞增有表,k為關(guān)鍵字{intlow,mid,；low=1；hig=n；/*各變量始化*/while(_____){mid=___________________；if(k<r[mid].key)____________________；elseif(k==r[mid].key){_____________________；_____________________；}else_____________________；}__________________；__________________；}七算設(shè)算法中必須有注釋,每題8分,共16分1.設(shè)n個素的線性表順序存儲一維數(shù)組st[1..maxlen]前n個位置上試新元素e插入中第i-1個和第i個素之間寫算法。2.設(shè)為表頭結(jié)點(diǎn)的單鏈的頭指針,寫出算法:若非空表,則輸出首結(jié)點(diǎn)和尾結(jié)點(diǎn)的值data值；則輸出”Emptylist！。

word格-共5頁5頁專升)《數(shù)結(jié)》題(模B一單選題(從下列各四個備選答案中選出一個正確答案,將代號(A,B,C,D)寫在下表中答題寫在其它地方無效；每小題1,共11分題號答案

456789111.數(shù)據(jù)的基本單位是____。A.結(jié)點(diǎn)B.數(shù)據(jù)元素C.數(shù)類型D.據(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)/2B.n(n+1)/2C.nD.3.當(dāng)需要隨機(jī)查找線性表的元素宜采用____作存儲結(jié)構(gòu)。A.雙向鏈表B.循鏈表C.順序表D.鏈表4.若8行列數(shù)組以行序為主順序存儲,基址為2000,每個元素占個存儲單元則5行第3列的元素假無第0行第0列的址是____。A.2086B.2032C.2068D.答案A,B,C都不5.廣義表a,(b),c,(d,(e)))的尾是___A.(d,(e))B.(d,(e))C.(b),c,(d,(e))D.((b),c,(d,(e)))6.____是Yu**Jia**Shan"的串。A.YuB."jia"C."**Shan"D."YuJiaShan"7.無向完全圖的鄰接矩陣是___陣。A.對稱B.上角C.下角D.疏8.有個點(diǎn)的完全二叉樹深度是____。A.(n)+1C.(n)-1

B.(n)-1D.(n)+1

word格-9.與中綴表達(dá)式a-b/c+d等的綴表達(dá)式是____。A.-a+/bcdB./-+bcdC.+-/bcdD.abcd-/+10.對有個錄的索引順序表分塊表)進(jìn)行查找,最理想的塊長為___。A.1800B.60C.1200D.共5頁1頁11.對n個素的表作堆排序在壞情況下,算法的時間復(fù)雜度為___。A.O(logn)B.O(nlogn)C.O(nD.O(2二填題(每空1分,共分)1.一個算法具有個性__________________、__________________、________________、零個或多個輸入、有一個或多個輸出。2.設(shè)長度為的性表順序存貯,若它的第i-1第i個元之插入一個元素,共需移動_________個素1<i≤n)。3.一個字符串中__________________________稱為該串的子串。4.樹中結(jié)點(diǎn)的____________________稱結(jié)點(diǎn)A度。5.一棵深度為的叉樹最多有_______結(jié)點(diǎn)。6.具有10個頂點(diǎn)的無向圖邊總數(shù)最多為_____________。7.順序查找個素的順序表當(dāng)使用監(jiān)視哨時,若查找成功比較關(guān)鍵字的次數(shù)最多為____次；查找失敗,比較關(guān)鍵字的次數(shù)為_____次。8.折半查找有序表2,4,6,12,20,28,38,50,70,100),查找表中元素12,它依次與表中元素___________________比大小。三回下問(小題5,共分1.線性表的存儲結(jié)構(gòu),在什么情下采用鏈接表(:單鏈表結(jié)構(gòu)?為什么?2.空格串與空串有區(qū)別舉說之。共5頁2頁

word格-四試出列儲構(gòu)(每小題5分共分1.試畫出下列稀疏矩陣以列序為序的三元組表。稀疏矩陣2.試畫出下列二叉樹的中序線索叉樹存儲結(jié)構(gòu)圖。二叉樹3.試用孩子兄弟(左孩子右兄弟)示法畫出下列樹的存儲結(jié)構(gòu)圖。樹4.試畫出下列有向網(wǎng)的逆鄰接表有向網(wǎng)共5頁3頁五求下問(小題6,共分1.已知二叉樹的前序遍歷序列和序遍歷序列分別是：B,A,C,D,F,E,G和D,C,A,F,G,E,B,

word格-試畫出該二叉樹。2.試按表25,15,19,24,20,5,16,45,40,38)中元素的排列次序?qū)⑺性夭迦胍豢贸跏紴榭盏亩判驑渲惺谷允且豢枚媾判驑洹?1)畫出插入完成之后的二叉排序樹；若找元素17,將依次與二叉排序樹中哪些元素比較大小(3)假設(shè)每個元素的查找概率相等,試算該樹的平均查找長度ASL對該樹進(jìn)行中序遍,寫出中序遍歷序列。3.試用權(quán)集合4,6,5,12,2,1,13},造赫夫曼Huffman)樹(1)列出構(gòu)造過程,(2)分別計算該夫曼樹的路徑長度和帶權(quán)路徑長度。4.找出下面網(wǎng)絡(luò)的最小生成樹:共5頁4頁六執(zhí)下的C程,出出果。(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格-}main(){charch；structnode*q,*p,*f,*head=NULLfor(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=headhead=qf=headwhile(f->next!=NULL){link_list(head)；f=f->next->next；}}}七算設(shè)算法中必須有注釋,每題8分,共16分1.設(shè)n個素的線性表順序存儲一維數(shù)組st[1..maxlen]前n個位上試出算法刪表中第i(1≤i≤n)個元素。2.設(shè)為表頭結(jié)點(diǎn)的單鏈的頭指針,寫出算法:若非空表,則輸出:最結(jié)點(diǎn)和最小結(jié)點(diǎn)的值(data值；否則輸:”。共5頁第5頁專升)《數(shù)結(jié)》題(模)一選題(從下列各題的4個備選答案中選出1至個確答案將其代號(A,B,C,D)在下表中,答題寫在其它地方無效；每小題分共分)題號答案

234678910111212141.由___組成的集合是一個數(shù)據(jù)對象。A.不同類型的數(shù)據(jù)項B.同類型的數(shù)據(jù)元素C.相同類型的數(shù)據(jù)項D.同類型的數(shù)據(jù)元素2.____是線性表。A.(孔子諸葛亮曹芹B.{A,B,C,D}C.{10,11,12,13,14}D.(1,2,3,...)3.____是示線性數(shù)據(jù)結(jié)構(gòu)的。A.循環(huán)鏈表B.鄰接多重表C.孩子鏈表D.單表4.將線性表的數(shù)據(jù)元素以____結(jié)存放,找一個數(shù)據(jù)元素所需

word格-的時間不依賴于表的長度。A.循環(huán)雙鏈表B.哈希Hash)C.一維數(shù)組D.鏈表5.設(shè)數(shù)組[1..8,1..10]的地為4000,每個素占個存儲單元若以列序為主序順序存儲則素A[4,7]的存儲地址是_。(定無第行第列元素)A.4072B.4104C.4102D.40746.設(shè)依次進(jìn)入一個棧的元素序列c,a,b,d,不可得到出棧的元素序列有____。A.a.b,c,dB.a,d,c,bC.b,a,d,cD.c,d,a,b7.___又一棵滿二叉樹。A.二叉排序樹B.度為5有31個結(jié)點(diǎn)的二叉樹C.有5個結(jié)點(diǎn)的完全二叉樹D.哈夫曼(Huffman)樹8.深度為的二叉樹有_個枝結(jié)點(diǎn)。A.2-1B.2-1C.2+1D.2+19.具有個點(diǎn)的完全二叉樹的深度為____。A.(n)C.(n+1)

B.(n)D.(n+1)10.折半查找20個記錄的有序表,查找失敗,比較關(guān)鍵字的次數(shù)___。A.最多為B.最多為5C.最為3D.最少為11.折半查找有序表2,5,8,20,25,36,40,60),若查找元素60,需依次與表中元素____進(jìn)比較。A.25,40,60B.25,40C.20,36,40,60D.20,36,4012.查找哈希(Hash)表,解決沖突的方法有____。A.除留余數(shù)法B.線性探測再列法C.接地址法D.地址法共頁第13.對有10個記錄的表作簡單選排序,需比較__次關(guān)鍵字。A.100B.45C.50D.9014.對有n個記錄的表作快速排序在最壞情況下,算法的時間復(fù)雜度是____。A.O(n)B.O(n)C.O(nlogn)D.O(n)15.一個排序算法時間復(fù)雜度的小___有關(guān)。A.與所需比較關(guān)鍵字的次數(shù)B.該算法的穩(wěn)定性C.不與所需移動記錄的數(shù)目D.所需輔助存儲空間的大小二畫題(每小題4分,共20)1.依次輸入元素插到個初始狀態(tài)為空的鏈?zhǔn)綏Ｖ?試畫出空的鏈?zhǔn)綏：兔坎迦胍粋€元之后的鏈?zhǔn)綏Ｊ疽鈭D。2.試用雙親表示法畫出下列樹T的存儲結(jié)構(gòu)圖。

word格-3.試畫出有行4列素的二維數(shù)組B以列序為主序的順序存儲結(jié)構(gòu)圖。4.試畫出下列圖的鄰接表。圖共5頁2頁5.已知一棵二叉樹的前序遍歷序和中序遍歷序列分別是：和試畫出該二叉樹。三求問每小題7分,共28分1.用算符優(yōu)先法求下列算術(shù)表達(dá)的值試簡要說明求值過程畫出操作數(shù)棧和算符棧的主要變化過程。12+20/(10-2*3)2.給定電文(文本):

word格-FAAABBBAAABBCCCDEGGG試為字符A設(shè)計夫曼(Huffman)編:(1)畫相應(yīng)的哈夫曼樹列各符的哈夫曼碼；(2)計該哈夫曼樹帶權(quán)路徑長度。共5頁3頁3.假定后序遍歷二叉樹的結(jié)果是A,C,B,(1)試畫出所有可得到這一結(jié)果的不同形態(tài)的二叉樹；分別寫出這些二叉樹的中序遍歷序列。4.假定對20個記錄的表作折半找,(1)試