數(shù)據(jù)結(jié)構(gòu)綜合練習(xí)試題

.../數(shù)據(jù)結(jié)構(gòu)〔一一、選擇題1．組成數(shù)據(jù)的基本單位是〔C。 <A>數(shù)據(jù)項 <B>數(shù)據(jù)類型 <C>數(shù)據(jù)元素 <D>數(shù)據(jù)變量2．設(shè)數(shù)據(jù)結(jié)構(gòu)A=<D,R>,其中D={1,2,3,4},R={r},r={<1,2>,<2,3>,<3,4>,<4,1>},則數(shù)據(jù)結(jié)構(gòu)A是〔C。 <A>線性結(jié)構(gòu) <B>樹型結(jié)構(gòu) <C>圖型結(jié)構(gòu) <D>集合3．?dāng)?shù)組的邏輯結(jié)構(gòu)不同于下列〔D的邏輯結(jié)構(gòu)。 <A>線性表 <B>棧 <C>隊列 <D>樹4．二叉樹中第i<i≥1>層上的結(jié)點數(shù)最多有〔C個。 <A>2i <B>2i <C>2i-1 <D>2i-15．設(shè)指針變量p指向單鏈表結(jié)點A,則刪除結(jié)點A的后繼結(jié)點B需要的操作為〔A。<A>p->next=p->next->next <B>p=p->next <C>p=p->next->next <D>p->next=p6．設(shè)棧S和隊列Q的初始狀態(tài)為空,元素E1、E2、E3、E4、E5和E6依次通過棧S,一個元素出棧后即進(jìn)入隊列Q,若6個元素出列的順序為E2、E4、E3、E6、E5和E1,則棧S的容量至少應(yīng)該是〔C。 <A>6 <B>4 <C>3 <D>27．將10階對稱矩陣壓縮存儲到一維數(shù)組A中,則數(shù)組A的長度最少為〔C。 <A>100 <B>40 <C>55 <D>808．設(shè)結(jié)點A有3個兄弟結(jié)點且結(jié)點B為結(jié)點A的雙親結(jié)點,則結(jié)點B的度數(shù)數(shù)為〔B。 <A>3 <B>4 <C>5 <D>19．根據(jù)二叉樹的定義可知二叉樹共有〔B種不同的形態(tài)。 <A>4 <B>5 <C>6 <D>7設(shè)有以下四種排序方法,則〔B的空間復(fù)雜度最大。 <A>冒泡排序 <B>快速排序 <C>堆排序 <D>希爾排序11、以下說法正確的是〔AA.連通圖的生成樹,是該連通圖的一個極小連通子圖。B.無向圖的鄰接矩陣是對稱的,有向圖的鄰接矩陣一定是不對稱的。C.任何一個有向圖,其全部頂點可以排成一個拓?fù)湫蛄小.有回路的圖不能進(jìn)行拓?fù)渑判颉?2、以下說法錯誤的是<D>A.一般在哈夫曼樹中,權(quán)值越大的葉子離根結(jié)點越近B.哈夫曼樹中沒有度數(shù)為1的分支結(jié)點C.若初始森林中共有n裸二叉樹,最終求得的哈夫曼樹共有2n-1個結(jié)點D.若初始森林中共有n裸二叉樹,進(jìn)行2n-1次合并后才能剩下一棵最終的哈夫曼樹13、如果從無向圖的任一頂點出發(fā)進(jìn)行一次深度優(yōu)先搜索即可訪問所有頂點,則該圖一定是<B>A.完全圖

B.連通圖

C.有回路

D.一棵樹14、將一棵有50個結(jié)點的完全二叉樹按層編號,則對編號為25的結(jié)點x,該結(jié)點<B>A.無左、右孩子

B.有左孩子,無右孩子C.有右孩子,無左孩子

D.有左、右孩子15、深度為6的二叉樹最多有<B>個結(jié)點A.64B.63C.3216、一個有序順表有255個對象,采用順序搜索法查表,搜索長度為〔A。A、128B、127C、126D、25517、在有向圖中每個頂點的度等于該頂點的〔C。A.入度B.出度C.入度與出度之和 D.入度與出度之差18、具有n個頂點的有向無環(huán)圖最多可包含<D>條有向邊。A．n-1B．nC．n<n-1>/2D．n<n-1>19、用鄰接表作為有向圖G的存儲結(jié)構(gòu)。設(shè)有n個頂點、e條弧,則拓?fù)渑判虻臅r間復(fù)雜度為<B>A.O<n>B.O<n+e>C.O<e>D.O<n*e>

20、一個有序順表有255個對象,采用順序搜索法查表,搜索長度為〔A。A、128B、127C、126D、25521、在有向圖中,所有頂點的入度之和是所有頂點出度之和的〔B倍。A.0.5B.22、以下說法錯誤的是〔BA.用相鄰矩陣法存儲一個圖時,在不考慮壓縮存儲的情況下,所占用的存儲空間大小只與圖中結(jié)點個數(shù)有關(guān),而與圖的邊數(shù)無關(guān)。B.鄰接表法只能用于有向圖的存儲,而相鄰矩陣法對于有向圖和無向圖的存儲都適用。C.存儲無向圖的相鄰矩陣是對稱的,因此只要存儲相鄰矩陣的下〔或上三角部分就可以了D.用相鄰矩陣A表示圖,判定任意兩個結(jié)點Vi和Vj之間是否有長度為m的路徑相連,則只要檢查A的第i行第j列的元素是否為0即可。23、在圖的鄰接表存儲結(jié)構(gòu)上執(zhí)行深度優(yōu)先搜索遍歷類似于二叉樹上的〔AA.先根遍歷B.中根遍歷C.后根遍歷D按層次遍歷24、在一個無向圖中,所有頂點的度數(shù)之和等于所有邊數(shù)的〔B倍。A．3B．2C．1D．1/225、在無向圖中,所有頂點的度數(shù)之和是所有邊數(shù)的〔C倍。A.0.5B26、設(shè)有6個結(jié)點的無向圖,該圖至少應(yīng)有〔B條邊能確保是一個連通圖。A.5B.6C.7D.827、以下說法正確的是〔DA.連通分量是無向圖中的極小連通子圖。B.強連通分量是有向圖中的極大強連通子圖。C.在一個有向圖的拓?fù)湫蛄兄?若頂點a在頂點b之前,則圖中必有一條弧<a,b>。D.對有向圖G,如果從任意頂點出發(fā)進(jìn)行一次深度優(yōu)先或廣度優(yōu)先搜索能訪問到每個頂點,則該圖一定是完全圖。二、填空題設(shè)順序循環(huán)隊列Q[0：m-1]的隊頭指針和隊尾指針分別為F和R,其中隊頭指針F指向當(dāng)前隊頭元素的前一個位置,隊尾指針R指向當(dāng)前隊尾元素所在的位置,則出隊列的語句為F=____________;。設(shè)線性表中有n個數(shù)據(jù)元素,則在順序存儲結(jié)構(gòu)上實現(xiàn)順序查找的平均時間復(fù)雜度為___________,在鏈?zhǔn)酱鎯Y(jié)構(gòu)上實現(xiàn)順序查找的平均時間復(fù)雜度為___________。設(shè)一棵二叉樹中有n個結(jié)點,則當(dāng)用二叉鏈表作為其存儲結(jié)構(gòu)時,該二叉鏈表中共有________個指針域,__________個空指針域。設(shè)指針變量p指向單鏈表中結(jié)點A,指針變量s指向被插入的結(jié)點B,則在結(jié)點A的后面插入結(jié)點B的操作序列為______________________________________。設(shè)無向圖G中有n個頂點和e條邊,則其對應(yīng)的鄰接表中有_________個表頭結(jié)點和_________個表結(jié)點。設(shè)無向圖G中有n個頂點e條邊,所有頂點的度數(shù)之和為m,則e和m有______關(guān)系。設(shè)一棵二叉樹的前序遍歷序列和中序遍歷序列均為ABC,則該二叉樹的后序遍歷序列為__________。設(shè)一棵完全二叉樹中有21個結(jié)點,如果按照從上到下、從左到右的順序從1開始順序編號,則編號為8的雙親結(jié)點的編號是___________,編號為8的左孩子結(jié)點的編號是_____________。下列程序段的功能實現(xiàn)子串t在主串s中位置的算法,要求在下劃線處填上正確語句。intindex<chars[],chart[]>{i=j=0;while<i<strlen<s>&&j<strlen<t>>if<s[i]==t[j]>{i=i+l;j=j+l;}else{i=_______;j=______;}if<j==strlen<t>>return<i-strlen<t>>;elsereturn<-1>;}設(shè)一個連通圖G中有n個頂點e條邊,則其最小生成樹上有________條邊。三、應(yīng)用題1．設(shè)完全二叉樹的順序存儲結(jié)構(gòu)中存儲數(shù)據(jù)ABCDE,要求給出該二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)并給出該二叉樹的前序、中序和后序遍歷序列。2．設(shè)給定一個權(quán)值集合W=<3,5,7,9,11>,要求根據(jù)給定的權(quán)值集合構(gòu)造一棵哈夫曼樹并計算哈夫曼樹的帶權(quán)路徑長度WPL。3．設(shè)一組初始記錄關(guān)鍵字序列為<19,21,16,5,18,23>,要求給出以19為基準(zhǔn)的一趟快速排序結(jié)果以及第2趟直接選擇排序后的結(jié)果。4．設(shè)一組初始記錄關(guān)鍵字集合為<25,10,8,27,32,68>,散列表的長度為7,散列函數(shù)H<k>=kmod7,要求用線性探測法作為解決沖突的方法設(shè)計哈希表。5．設(shè)無向圖G〔所右圖所示,要求給出該圖的深度優(yōu)先和廣度優(yōu)先遍歷的序列,并畫給相應(yīng)的生成樹〔一參考答案二、填空題<F+1>%mO<n>,O<n>2n,n+1s->next=p->next;s->next=sn,2em=2eCBA4,16i-j+1,0n-1三、應(yīng)用題鏈?zhǔn)酱鎯Y(jié)構(gòu)略,前序ABDEC,中序DBEAC,后序DEBCA。哈夫曼樹略,WPL=78<18,5,16,19,21,23>,<5,16,21,19,18,23>線性探測：數(shù)據(jù)結(jié)構(gòu)〔二一、選擇題1．下面關(guān)于線性表的敘述錯誤的是〔。 <A>線性表采用順序存儲必須占用一片連續(xù)的存儲空間 <B>線性表采用鏈?zhǔn)酱鎯Σ槐卣加靡黄B續(xù)的存儲空間<C>線性表采用鏈?zhǔn)酱鎯Ρ阌诓迦牒蛣h除操作的實現(xiàn)<D>線性表采用順序存儲便于插入和刪除操作的實現(xiàn)2．設(shè)哈夫曼樹中的葉子結(jié)點總數(shù)為m,若用二叉鏈表作為存儲結(jié)構(gòu),則該哈夫曼樹中總共有〔個空指針域。 <A>2m-1 <B>2m <C>2m+1 <D>4m3．設(shè)順序循環(huán)隊列Q[0：M-1]的頭指針和尾指針分別為F和R,頭指針F總是指向隊頭元素的前一位置,尾指針R總是指向隊尾元素的當(dāng)前位置,則該循環(huán)隊列中的元素個數(shù)為〔。 <A>R-F <B>F-R <C><R-F+M>％M <D><F-R+M>％M4．設(shè)某棵二叉樹的中序遍歷序列為ABCD,前序遍歷序列為CABD,則后序遍歷該二叉樹得到序列為〔。 <A>BADC <B>BCDA <C>CDAB <D>CBDA5．設(shè)某完全無向圖中有n個頂點,則該完全無向圖中有〔條邊。 <A>n<n-1>/2 <B>n<n-1> <C>n2 <D>n2-16．設(shè)某棵二叉樹中有2000個結(jié)點,則該二叉樹的最小高度為〔。 <A>9 <B>10 <C>11 <D>127．設(shè)某有向圖中有n個頂點,則該有向圖對應(yīng)的鄰接表中有〔個表頭結(jié)點。 <A>n-1 <B>n <C>n+1 <D>2n-18．設(shè)一組初始記錄關(guān)鍵字序列<5,2,6,3,8>,以第一個記錄關(guān)鍵字5為基準(zhǔn)進(jìn)行一趟快速排序的結(jié)果為〔。 <A>2,3,5,8,6 <B>3,2,5,8,6 <C>3,2,5,6,8 <D>2,3,6,5,8二、填空題為了能有效地應(yīng)用HASH查找技術(shù),必須解決的兩個問題是____________________和__________________________。下面程序段的功能實現(xiàn)數(shù)據(jù)x進(jìn)棧,要求在下劃線處填上正確的語句。typedefstruct{ints[100];inttop;}sqstack;voidpush<sqstack&stack,intx>{if<stack.top==m-1>printf<"overflow">;else{____________________;_________________;}}中序遍歷二叉排序樹所得到的序列是___________序列〔填有序或無序?？焖倥判虻淖顗臅r間復(fù)雜度為___________,平均時間復(fù)雜度為__________。設(shè)某棵二叉樹中度數(shù)為0的結(jié)點數(shù)為N0,度數(shù)為1的結(jié)點數(shù)為N1,則該二叉樹中度數(shù)為2的結(jié)點數(shù)為_________；若采用二叉鏈表作為該二叉樹的存儲結(jié)構(gòu),則該二叉樹中共有_______個空指針域。設(shè)某無向圖中頂點數(shù)和邊數(shù)分別為n和e,所有頂點的度數(shù)之和為d,則e=_______。設(shè)一組初始記錄關(guān)鍵字序列為<55,63,44,38,75,80,31,56>,則利用篩選法建立的初始堆為___________________________。設(shè)某無向圖G的鄰接表為,則從頂點V1開始的深度優(yōu)先遍歷序列為___________；廣度優(yōu)先遍歷序列為____________。三、應(yīng)用題設(shè)一組初始記錄關(guān)鍵字序列為<45,80,47,40,20,78>,則分別給出第4趟簡單選擇排序和第4趟直接插入排序后的結(jié)果。設(shè)指針變量p指向雙向鏈表中結(jié)點A,指針變量q指向被插入結(jié)點B,要求給出在結(jié)點A的后面插入結(jié)點B的操作序列〔設(shè)雙向鏈表中結(jié)點的兩個指針域分別為llink和rlink。設(shè)一組有序的記錄關(guān)鍵字序列為<13,18,24,35,47,50,62,83,90>,查找方法用二分查找,要求計算出查找關(guān)鍵字62時的比較次數(shù)并計算出查找成功時的平均查找長度。設(shè)一棵樹T中邊的集合為{<A,B>,<A,C>,<A,D>,<B,E>,<C,F>,<C,G>},要求用孩子兄弟表示法〔二叉鏈表表示出該樹的存儲結(jié)構(gòu)并將該樹轉(zhuǎn)化成對應(yīng)的二叉樹。設(shè)有無向圖G〔如右圖所示,要求給出用普里姆算法構(gòu)造最小生成樹所走過的邊的集合。設(shè)有一組初始記錄關(guān)鍵字為<45,80,48,40,22,78>,要求構(gòu)造一棵二叉排序樹并給出構(gòu)造過程。7、給出如圖所示的無向圖G的鄰接矩陣和鄰接表兩種存儲結(jié)構(gòu)。8、簡單選擇排序、快速排序和堆排序是不穩(wěn)定的排序方法,試舉例說明。9、給出下圖鄰接矩陣和鄰接表兩種存儲結(jié)構(gòu)；寫出圖的拓?fù)湫蛄?。V2V2V1V3V6V5V41〔二參考答案一、選擇題1.D 2.B 3.C 4.A 5.A 6.C 7.B 8.C二、填空題構(gòu)造一個好的HASH函數(shù),確定解決沖突的方法stack.top++,stack.s[stack.top]=x有序O<n2>,O<nlog2n>N0-1,2N0+N1d/2<31,38,54,56,75,80,55,63><1,3,4,2>,<1,3,2,4>三、應(yīng)用題<20,40,45,47,80,78>,<40,45,47,80,20,78>q->llink=p;q->rlink=p->rlink;p->rlink->llink=q;p->rlink=q;2,ASL=91*1+2*2+3*4+4*2>=25/9樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)略,二叉樹略E={<1,3>,<1,2>,<3,5>,<5,6>,<6,4>}略8、簡單選擇排序、快速排序和堆排序是不穩(wěn)定的排序方法,試舉例說明。[解答] <2>簡單選擇排序 {275 275*512 061}i=1{061275*512 275}i=2{061 275*512 275}i=3{061 275*275 512} <3>快速排序 {512 275 275*}{275* 275 512} <4>堆排序 {275275*061170}已經(jīng)是最大堆,交換275與170{170275*061275}對前3個調(diào)整{275*170061275}前3個最大堆,交換275*與061{061170275*275}對前2個調(diào)整{170061275*275}前2個最大堆,交換170與061{061170275*275}數(shù)據(jù)結(jié)構(gòu)〔三一、選擇題1．設(shè)某無向圖有n個頂點,則該無向圖的鄰接表中有〔個表頭結(jié)點。 <A>2n <B>n <C>n/2 <D>n<n-1>2．設(shè)無向圖G中有n個頂點,則該無向圖的最小生成樹上有〔條邊。 <A>n <B>n-1 <C>2n <D>2n-13．設(shè)一組初始記錄關(guān)鍵字序列為<60,80,55,40,42,85>,則以第一個關(guān)鍵字45為基準(zhǔn)而得到的一趟快速排序結(jié)果是〔。 <A>40,42,60,55,80,85 <B>42,45,55,60,85,80 <C>42,40,55,60,80,85 <D>42,40,60,85,55,804．〔二叉排序樹可以得到一個從小到大的有序序列。 <A>先序遍歷 <B>中序遍歷 <C>后序遍歷 <D>層次遍歷5．設(shè)按照從上到下、從左到右的順序從1開始對完全二叉樹進(jìn)行順序編號,則編號為i結(jié)點的左孩子結(jié)點的編號為〔。<A>2i+1 <B>2i <C>i/2 <D>2i-16．程序段s=i=0；do{i=i+1；s=s+i；}while<i<=n>；的時間復(fù)雜度為〔。 <A>O<n> <B>O<nlog2n> <C>O<n2> <D>O<n3/2>7．設(shè)帶有頭結(jié)點的單向循環(huán)鏈表的頭指針變量為head,則其判空條件是〔。<A>head==0<B>head->next==0 <C>head->next==head <D>head!=08．設(shè)某棵二叉樹的高度為10,則該二叉樹上葉子結(jié)點最多有〔。 <A>20 <B>256 <C>512 <D>10249．設(shè)一組初始記錄關(guān)鍵字序列為<13,18,24,35,47,50,62,83,90,115,134>,則利用二分法查找關(guān)鍵字90需要比較的關(guān)鍵字個數(shù)為〔。<A>1 <B>2 <C>3 <D>410.設(shè)指針變量top指向當(dāng)前鏈?zhǔn)綏５臈ｍ?則刪除棧頂元素的操作序列為〔。 <A>top=top+1; <B>top=top-1; <C>top->next=top; <D>top=top->next;二、判斷題1、數(shù)據(jù)的最小單位是數(shù)據(jù)項?！?<√>2、多重表文件中主索引為非稠密索引,次索引為稠密索引?！?<√>3、通常數(shù)據(jù)結(jié)構(gòu)在計算機中有四種不同的表示方法分為順序存儲結(jié)構(gòu)、鏈?zhǔn)酱鎯Y(jié)構(gòu)、索引存儲、文件存儲?！?…….<×>4、算法具有輸入、輸出、可行性、穩(wěn)定性、有窮性五個特性。……………….<×>5、數(shù)據(jù)的基本單位是數(shù)據(jù)項。………….<×>6、算法的復(fù)雜度分為時間復(fù)雜度和效率復(fù)雜度?！?<×>7、性質(zhì)相同的數(shù)據(jù)元素的集合成為數(shù)據(jù)對象?！?<√>8、所有結(jié)點按1對1的鄰接關(guān)系構(gòu)成的整體就是集合結(jié)構(gòu)。……….<×>9、散列文件不能順序存取、只能按關(guān)鍵字隨機存取?！?<√>10、數(shù)據(jù)的基本單位是數(shù)據(jù)元素。………….<√>11．不論是入隊列操作還是入棧操作,在順序存儲結(jié)構(gòu)上都需要考慮"溢出"情況?！病?2．當(dāng)向二叉排序樹中插入一個結(jié)點,則該結(jié)點一定成為葉子結(jié)點?！病?3．由樹轉(zhuǎn)化成二叉樹,該二叉樹的右子樹不一定為空?！病?4．線性表中的所有元素都有一個前驅(qū)元素和后繼元素?！病?5.帶權(quán)無向圖的最小生成樹是唯一的?！病?6.具有12個結(jié)點的完全二叉樹有5個度為2的結(jié)點?！?7.關(guān)鍵路徑是事件結(jié)點網(wǎng)絡(luò)中的從源點到匯點的最短路徑?！?8.由樹轉(zhuǎn)化成二叉樹,該二叉樹的右子樹不一定為空?！?9.堆排序是不穩(wěn)定的排序方法。〔√20.查找表是由同一類型的數(shù)據(jù)元素<或記錄>構(gòu)成的集合<√>三、填空題設(shè)指針變量p指向雙向鏈表中的結(jié)點A,指針變量s指向被插入的結(jié)點X,則在結(jié)點A的后面插入結(jié)點X的操作序列為_________=p；s->right=p->right；__________=s；p->right->left=s；〔設(shè)結(jié)點中的兩個指針域分別為left和right。設(shè)完全有向圖中有n個頂點,則該完全有向圖中共有________條有向條；設(shè)完全無向圖中有n個頂點,則該完全無向圖中共有________條無向邊。設(shè)關(guān)鍵字序列為<Kl,K2,…,Kn>,則用篩選法建初始堆必須從第______個元素開始進(jìn)行篩選。解決散列表沖突的兩種方法是________________和__________________。設(shè)一棵三叉樹中有50個度數(shù)為0的結(jié)點,21個度數(shù)為2的結(jié)點,則該二叉樹中度數(shù)為3的結(jié)點數(shù)有______個。高度為h的完全二叉樹中最少有________個結(jié)點,最多有________個結(jié)點。設(shè)有一組初始關(guān)鍵字序列為<24,35,12,27,18,26>,則第3趟直接插入排序結(jié)束后的結(jié)果的是__________________________________。設(shè)有一組初始關(guān)鍵字序列為<24,35,12,27,18,26>,則第3趟簡單選擇排序結(jié)束后的結(jié)果的是__________________________________。設(shè)一棵二叉樹的前序序列為ABC,則有______________種不同的二叉樹可以得到這種序列。下面程序段的功能是實現(xiàn)一趟快速排序,請在下劃線處填上正確的語句。structrecord{intkey;datatypeothers;};voidquickpass<structrecordr[],ints,intt,int&i>{intj=t;structrecordx=r[s];i=s;while<i<j>{while<i<j&&r[j].key>x.key>j=j-1;if<i<j>{r[i]=r[j];i=i+1;}while<____________________>i=i+1;if<i<j>{r[j]=r[i];j=j-1;}}_________________;}數(shù)據(jù)結(jié)構(gòu)〔三一、選擇題1．B 2．B 3．C 4．B 5．B6．A 7．C 8．C 9．B 10．D三、填空題s->left=p,p->rightn<n-1>,n<n-1>/2n/2開放定址法,鏈地址法142h-1,2h-1<12,24,35,27,18,26><12,18,24,27,35,26>5i<j&&r[i].key<x.key,r[i]=x數(shù)據(jù)結(jié)構(gòu)〔四一、選擇題1．設(shè)輸入序列是1、2、3、……、n,經(jīng)過棧的作用后輸出序列的第一個元素是n,則輸出序列中第i個輸出元素是〔c。 <A>n-i <B>n-1-i <C>n+1-i <D>不能確定2.為查找某一特定單詞在文本中出現(xiàn)的位置,可應(yīng)用的串運算是<

>

A.插入

B.刪除

C.串聯(lián)接

D.子串定位3．設(shè)有序表中有1000個元素,則用二分查找查找元素X最多需要比較〔次。 <A>25<B>10<C>7<D>14.對于只在表的首、尾兩端進(jìn)行插入操作的線性表,宜采用的存儲結(jié)構(gòu)為<

>

A.順序表

B.用頭指針表示的單循環(huán)鏈表

C.用尾指針表示的單循環(huán)鏈表

D.單鏈表5．設(shè)某完全無向圖中有n個頂點,則該完全無向圖中有〔條邊。 <A>n<n-1>/2 <B>n<n-1> <C>n2 <D>n2-16．設(shè)某棵二叉樹中有2000個結(jié)點,則該二叉樹的最小高度為〔。 <A>9 <B>10 <C>11 <D>127．在數(shù)據(jù)結(jié)構(gòu)中,從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為<>A.動態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)B.緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)C.內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)D.線性結(jié)構(gòu)和非線性結(jié)構(gòu)8．已知圖的鄰接表如下所示,根據(jù)算法,則從頂點V0出發(fā)按廣度優(yōu)先遍歷的結(jié)點序列是<>A．0321B.0123C.0132D.03129．若進(jìn)棧序列為a,b,c,d,e,則棧的不可能的輸出序列是<>A.edcbaB.dceabC.decbaD.abcde10．把一棵樹轉(zhuǎn)換為二叉樹后,這棵二叉樹的形態(tài)是<>。A.唯一的B.有多種C.有多種,但根結(jié)點都沒有左孩子D.有多種,但根結(jié)點都沒有右孩子11.為查找某一特定單詞在文本中出現(xiàn)的位置,可應(yīng)用的串運算是<

>

A.插入

B.刪除

C.串聯(lián)接

D.子串定位12.ALV樹是一種平衡的二叉樹,樹中任一結(jié)點的<

>

A.左、右子樹的高度均相同

B.左、右子樹高度差的絕對值不超過1

C.左子樹的高度均大于右子樹的高度

D.左子樹的高度均小于右子樹的高度13.對于只在表的首、尾兩端進(jìn)行插入操作的線性表,宜采用的存儲結(jié)構(gòu)為<

>

A.順序表

B.用頭指針表示的單循環(huán)鏈表

C.用尾指針表示的單循環(huán)鏈表

D.單鏈表14.二叉樹是非線性數(shù)據(jù)結(jié)構(gòu),所以<>。Ａ.它不能用順序存儲結(jié)構(gòu)存儲;B.它不能用鏈?zhǔn)酱鎯Y(jié)構(gòu)存儲;C.順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)都能存儲;D.順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)都不能使用15.用鄰接表表示圖進(jìn)行廣度優(yōu)先遍歷時,通常是采用<>來實現(xiàn)算法的。A．棧B.隊列C.樹D.圖16．?dāng)?shù)據(jù)的最小單位是〔。 <A>數(shù)據(jù)項 <B>數(shù)據(jù)類型 <C>數(shù)據(jù)元素 <D>數(shù)據(jù)變量17．設(shè)某棵二叉樹中有2000個結(jié)點,則該二叉樹的最小高度為〔。 <A>9 <B>10 <C>11 <D>1218．函數(shù)substr<"DATASTRUCTURE",5,9>的返回值為〔。 <A>"STRUCTURE" <B>"DATA" <C>"ASTRUCTUR" <D>"DATASTRUCTURE"19．設(shè)某完全無向圖中有n個頂點,則該完全無向圖中有〔條邊。 <A>n<n-1>/2 <B>n<n-1> <C>n2 <D>n2-120．深度為k的完全二叉樹中最少有〔個結(jié)點。 <A>2k-1-1 <B>2k-1<C>2k-1+1 <D>2k-121．設(shè)連通圖G中的邊集E={<a,b>,<a,e>,<a,c>,<b,e>,<e,d>,<d,f>,<f,c>},則從頂點a出發(fā)可以得到一種深度優(yōu)先遍歷的頂點序列為〔。 <A>abedfc <B>acfebd <C>aebdfc <D>aedfcb22．下面關(guān)于線性表的敘述錯誤的是〔。<A>線性表采用順序存儲必須占用一片連續(xù)的存儲空間 <B>線性表采用鏈?zhǔn)酱鎯Σ槐卣加靡黄B續(xù)的存儲空間<C>線性表采用鏈?zhǔn)酱鎯Ρ阌诓迦牒蛣h除操作的實現(xiàn)<D>線性表采用順序存儲便于插入和刪除操作的實現(xiàn)23．設(shè)哈夫曼樹中的葉子結(jié)點總數(shù)為m,若用二叉鏈表作為存儲結(jié)構(gòu),則該哈夫曼樹中總共有〔個空指針域。<A>2m-1 <B>2m <C>2m+1 <D>24．設(shè)順序循環(huán)隊列Q[0：M-1]的頭指針和尾指針分別為F和R,頭指針F總是指向隊頭元素的前一位置,尾指針R總是指向隊尾元素的當(dāng)前位置,則該循環(huán)隊列中的元素個數(shù)為〔。<A>R-F <B>F-R <C><R-F+M>％M <D><F-R+M>％M25．設(shè)某棵二叉樹的中序遍歷序列為ABCD,前序遍歷序列為CABD,則后序遍歷該二叉樹得到序列為〔。<A>BADC <B>BCDA<C>CDAB <D>CBDA二、填空題1．1．for<i=1,t=1,s=0；i<=n；i++>{t=t*i；s=s+t；}的時間復(fù)雜度為。2．下面程序段的功能是實現(xiàn)冒泡排序算法,請在下劃線處填上正確的語句。voidbubble<intr[n]>{for<i=1;i<=n-1;i++>{for<exchange=0,j=0;j<;j++>if<r[j]>r[j+1]>{temp=r[j+1];;r[j]=temp;exchange=1;}if<exchange==0>return；}}3．下面程序段的功能是實現(xiàn)二分查找算法,請在下劃線處填上正確的語句。structrecord{intkey;intothers;};intbisearch<structrecordr[],intk>{intlow=0,mid,high=n-1;while<low<=high>{;if<r[mid].key==k>return<mid+1>;elseif<>high=mid-1;elselow=mid+1;}return<0>;}3．根據(jù)二叉樹的定義可知二叉樹共有種不同的形態(tài)。 4．快速排序的最壞時間復(fù)雜度為,平均時間復(fù)雜度為。5．設(shè)某棵二叉樹中度數(shù)為0的結(jié)點數(shù)為N0,度數(shù)為1的結(jié)點數(shù)為N1,則該二叉樹中度數(shù)為2的結(jié)點數(shù)為；若采用二叉鏈表作為該二叉樹的存儲結(jié)構(gòu),則該二叉樹中共有個空指針域。6．設(shè)某無向圖中頂點數(shù)和邊數(shù)分別為n和e,所有頂點的度數(shù)之和為d,則e=。7.設(shè)一棵完全二叉樹中有21個結(jié)點,如果按照從上到下、從左到右的順序從1開始順序編號,則編號為8的雙親結(jié)點的編號是___________,編號為8的左孩子結(jié)點的編號是____