(專升本)《數(shù)據(jù)結構》試題三套

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

234678910111.數(shù)據(jù)的不可分割的基本單位是___。A.元素B.結點C.數(shù)據(jù)類D.數(shù)據(jù)項2.下列算法suanfa2的間復雜為____。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.有個點的完全二叉樹深度是____。A.(n)C.(n+1)

B.(n)+1D.(n)+17.與中綴表達式a+b*c-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的表作選擇簡選擇)序,共需比較____關鍵字。A.45B.90C.55D.11010.對n個素的表作快速排序,最壞情況下,算法的時間復雜度為___。A.O(logn)B.O(nlogn)C.O(nD.O(2

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

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

word格-5.有向圖的逆鄰接表:五、求解下列問題(每小題6分共分1.給定30個字符組成的電文:DDDDDAAABEEAAFDAACABBCCCBAADD試為字符A、C、D、E、F設哈夫曼(Huffman)編碼。(1)畫出相應的哈夫曼樹；(2)分別列出A、C、D、F的夫曼碼；(3)計算該樹的帶權路徑長度WPL。共5頁3頁2.試按表10,8,9,12,20,5,6,15,19,25中素的排列次序將有元素插入一棵初始為空的二排序樹中使仍是一棵二叉排序樹。(1)試畫出插入完成之后的二叉序樹；(2)若查找元素17,它將依次與叉排序樹中哪些元素比較大小?(3)假設每個元素的查找概率相試計算該樹的平均查找長度ASL。(4)對該樹進行中序遍歷試出序遍歷序列。3.試將森林F={T1,T2,T3,T4}轉為一棵二叉樹。T1T2T3T4

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

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

456789111.數(shù)據(jù)的基本單位是____。A.結點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.當需要隨機查找線性表的元素宜采用____作存儲結構。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.有個點的完全二叉樹深度是____。A.(n)+1C.(n)-1

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

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

word格-四試出列儲構(每小題5分共分1.試畫出下列稀疏矩陣以列序為序的三元組表。稀疏矩陣2.試畫出下列二叉樹的中序線索叉樹存儲結構圖。二叉樹3.試用孩子兄弟(左孩子右兄弟)示法畫出下列樹的存儲結構圖。樹4.試畫出下列有向網的逆鄰接表有向網共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)中元素的排列次序將所有元素插入一棵初始為空的二排序樹中使仍是一棵二叉排序樹。(1)畫出插入完成之后的二叉排序樹；若找元素17,將依次與二叉排序樹中哪些元素比較大小(3)假設每個元素的查找概率相等,試算該樹的平均查找長度ASL對該樹進行中序遍,寫出中序遍歷序列。3.試用權集合4,6,5,12,2,1,13},造赫夫曼Huffman)樹(1)列出構造過程,(2)分別計算該夫曼樹的路徑長度和帶權路徑長度。4.找出下面網絡的最小生成樹:共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；}}}七算設算法中必須有注釋,每題8分,共16分1.設n個素的線性表順序存儲一維數(shù)組st[1..maxlen]前n個位上試出算法刪表中第i(1≤i≤n)個元素。2.設為表頭結點的單鏈的頭指針,寫出算法:若非空表,則輸出:最結點和最小結點的值(data值；否則輸:”。共5頁第5頁專升)《數(shù)結》題(模)一選題(從下列各題的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ù)結構的。A.循環(huán)鏈表B.鄰接多重表C.孩子鏈表D.單表4.將線性表的數(shù)據(jù)元素以____結存放,找一個數(shù)據(jù)元素所需

word格-的時間不依賴于表的長度。A.循環(huán)雙鏈表B.哈希Hash)C.一維數(shù)組D.鏈表5.設數(shù)組[1..8,1..10]的地為4000,每個素占個存儲單元若以列序為主序順序存儲則素A[4,7]的存儲地址是_。(定無第行第列元素)A.4072B.4104C.4102D.40746.設依次進入一個棧的元素序列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個結點的二叉樹C.有5個結點的完全二叉樹D.哈夫曼(Huffman)樹8.深度為的二叉樹有_個枝結點。A.2-1B.2-1C.2+1D.2+19.具有個點的完全二叉樹的深度為____。A.(n)C.(n+1)

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

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

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