【正文】 (i1)/211. 11. 快速 歸并三、 三、exit(1)。一、 一、 樹最適合用來表示( )。40next357204 圖10請畫出圖10的鄰接矩陣和鄰接表。 已知一個圖的頂點集V和邊集E分別為： V={1,2,3,4,5,6,7}。 算法填空（共8分）二叉搜索樹的查找——遞歸算法:bool Find(BTreeNode* BST,ElemTypeamp。 }//while, 出循環(huán)時i中的值即為x結(jié)點個數(shù) return i。A n B n/2 C (n+1)/2 D (n1)/2 在一個單鏈表中,若q所指結(jié)點是p所指結(jié)點的前驅(qū)結(jié)點,若在q與p之間插入一個s所指的結(jié)點,則執(zhí)行( A )。 s→link =p。 一種抽象數(shù)據(jù)類型包括______________和_____________兩個部分。 用具有n個元素的一維數(shù)組存儲一個循環(huán)隊列，則其隊首指針總是指向隊首元素的___________，該循環(huán)隊列的最大長度為__________。 假定一棵樹的廣義表表示為A（B（C，D（E，F(xiàn)，G），H（I，J））），則樹中所含的結(jié)點數(shù)為_________個，樹的深度為_________,樹的度為________, 結(jié)點H的雙親結(jié)點為________,孩子結(jié)點為_______________ 。 在對m階的B_樹插入元素的過程中，每向一個結(jié)點插入一個索引項（葉子結(jié)點中的索引項為關(guān)鍵字和空指針）后，若該結(jié)點的索引項數(shù)等于______個，則必須把它分裂為_______個結(jié)點。鄰接表表示時 include “”Void main ( ){ stack a。}該算法的輸出結(jié)果為：__________________________________________________________. 閱讀以下二叉樹操作算法，指出該算法的功能。五、 五、 HS→data。233612 {Lnode *P=HL。1．算法指的是（ ） A．計算機程序 B．解決問題的計算方法 C．排序算法 D．解決問題的有限運算序列2．線性表采用鏈?zhǔn)酱鎯r，結(jié)點的存儲地址（ ） A．必須是不連續(xù)的 B．連續(xù)與否均可 C．必須是連續(xù)的 D．和頭結(jié)點的存儲地址相連續(xù)3．將長度為n的單鏈表鏈接在長度為m的單鏈表之后的算法的時間復(fù)雜度為（ ） A．O（1） B．O（n） C．O（m） D．O（m+n）4．由兩個棧共享一個向量空間的好處是：（ ） A．減少存取時間，降低下溢發(fā)生的機率 B．節(jié)省存儲空間，降低上溢發(fā)生的機率 C．減少存取時間，降低上溢發(fā)生的機率 D．節(jié)省存儲空間，降低下溢發(fā)生的機率5．設(shè)數(shù)組data[m]作為循環(huán)隊列SQ的存儲空間，front為隊頭指針，rear為隊尾指針，則執(zhí)行出隊操作后其頭指針front值為（ ） A．front=front+1 B．front=(front+1)%(m1) C．front=(front1)%m D．front=(front+1)%m6．如下陳述中正確的是（ ） A．串是一種特殊的線性表 B．串的長度必須大于零 C．串中元素只能是字母 D．空串就是空白串7．若目標(biāo)串的長度為n，模式串的長度為[n/3]，則執(zhí)行模式匹配算法時，在最壞情況下的時間復(fù)雜度是（ ） A．O（） B．O（n） C．O（n2） D．O（n3）8．一個非空廣義表的表頭（ ） A．不可能是子表 B．只能是子表 C．只能是原子 D．可以是子表或原子9．假設(shè)以帶行表的三元組表表示稀疏矩陣，則和下列行表02335 對應(yīng)的稀疏矩陣是（ ） 10．在一棵度為3的樹中,度為3的結(jié)點個數(shù)為2,度為2 的結(jié)點個數(shù)為1,則度為0的結(jié)點個數(shù)為( ) A．4 B．5 C．6 D．711．在含n個頂點和e條邊的無向圖的鄰接矩陣中,零元素的個數(shù)為( ) A．e B．2e C．n2－e D．n2－2e12．假設(shè)一個有n個頂點和e條弧的有向圖用鄰接表表示,則刪除與某個頂點vi相關(guān)的所有弧的時間復(fù)雜度是( ) A．O(n) B．O(e) C．O(n+e) D．O(n*e)13．用某種排序方法對關(guān)鍵字序列（25，84，21，47，15，27，68，35，20）進行排序時，序列的變化情況如下： 20，15，21，25，47，27，68，35，84 15，20，21，25，35，27，47，68，84 15，20，21，25，27，35，47，68，84 則所采用的排序方法是（ ） A．選擇排序 B．希爾排序 C．歸并排序 D．快速排序14．適于對動態(tài)查找表進行高效率查找的組織結(jié)構(gòu)是（ ）A．有序表 B．分塊有序表 C．三叉排序樹 D．線性鏈表15．不定長文件是指（ ）A．文件的長度不固定 B．記錄的長度不固定C．字段的長度不固定 D．關(guān)鍵字項的長度不固定21．已知一棵完全二叉樹中共有768結(jié)點，則該樹中共有 個葉子結(jié)點。 29．已知一個散列表如下圖所示：59 0 1 2 3 4 5 6 7 8 9 10 11 12 其散列函數(shù)為h(key)=key%13, 處理沖突的方法為雙重散列法，探查序列為： hi=(h(key)+*h1(key))%m =0,1,…，m－1其中 h1(key)=key%11+1回答下列問題：（1）對表中關(guān)鍵字35，20，33和48進行查找時，所需進行的比較次數(shù)各為多少？（2）該散列表在等概率查找時查找成功的平均查找長度為多少？四、算法閱讀題（本大題共4小題，每小題5分，共20分）30．下列算法的功能是比較兩個鏈串的大小，其返回值為： str(s1,s2)= 請在空白處填入適當(dāng)?shù)膬?nèi)容。 int EnQueue (Queue2*Q,int i,DateType x) {//若第 i個隊列不滿，則元素x入隊列，并返回1；否則返回0 if(i0||i1)return 0； if(Q－rear[i]==Q－front[ ① ]return0； Q－data[ ② ]=x； Q－rear[i]=[ ③ ]。amp。數(shù)據(jù)結(jié)構(gòu)試題參考答案一、 一、 圖1 圖2 27．H (A) pnext=pnextnext (B) p=pnext (C) p=pnextnext (D) pnext=p6．設(shè)棧S和隊列Q的初始狀態(tài)為空，元素EEEEE5和E6依次通過棧S，一個元素出棧后即進入隊列Q，若6個元素出列的順序為EEEEE5和E1，則棧S的容量至少應(yīng)該是（ ）。amp。5．設(shè)無向圖G（所右圖所示），要求給出該圖的深度優(yōu)先和廣度優(yōu)先遍歷的序列并給出該圖的最小生成樹。 2n，n+14. 4. snext=s5. 5. for(p=head。 return(1)。 設(shè)計在鏈?zhǔn)酱鎯Y(jié)構(gòu)上建立一棵二叉樹的算法。ch)。 createbitree(btrchild)。 設(shè)計判斷一棵二叉樹是否是二叉排序樹的算法。 inorder(btrchild)。 (A) n(n1)/2 (B) n(n1) (C) n2 (D) n216．設(shè)某棵二叉樹中有2000個結(jié)點，則該二叉樹的最小高度為（ ）。} sqstack。6. 6. 設(shè)某無向圖中頂點數(shù)和邊數(shù)分別為n和e，所有頂點的度數(shù)之和為d，則e=_______。3． 3．一、選擇題 構(gòu)造一個好的HASH函數(shù)，確定解決沖突的方法2. 2. qllink=p。 略 樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)略，二叉樹略5. 5. prlinkllink=q。三、應(yīng)用題1. 1. (31，38，54，56，75，80，55，63)8. 8.4． 4． 設(shè)某無向圖G的鄰接表為，則從頂點V1開始的深度優(yōu)先遍歷序列為___________；廣度優(yōu)先遍歷序列為____________。8. 8.stack,int x){if (==m1) printf(“overflow”)。 (A) n1 (B) n (C) n+1 (D) 2n18．設(shè)一組初始記錄關(guān)鍵字序列(5，2，6，3，8)，以第一個記錄關(guān)鍵字5為基準(zhǔn)進行一趟快速排序的結(jié)果為（ ）。數(shù)據(jù)結(jié)構(gòu)試卷（二）typedef struct node{int key。39。typedef struct node {datatype data。p=pnext) {++。typedef struct {int s[100]。 深度：125364，廣度：123456，最小生成樹T的邊集為E={(1，4)，(1，3)，(3，5)，(5，6)，(5,6)}四、算法設(shè)計題1. 1. (F+1) % m2. 2.數(shù)據(jù)結(jié)構(gòu)試卷參考答案3. 3.2. 2.四、算法設(shè)計題(20分) 1. 1. 設(shè)一個連通圖G中有n個頂點e條邊，則其最小生成樹上有________條邊。 j=j+l。 (A) 100 (B) 40 (C) 55 (D) 808．設(shè)結(jié)點A有3個兄弟結(jié)點且結(jié)點B為結(jié)點A的雙親結(jié)點，則結(jié)點B的度數(shù)數(shù)為（ ）。G深度優(yōu)先遍歷序列為：abdce廣度優(yōu)先遍歷序列為：abedc29．（１）對關(guān)鍵字333和48進行查找的比較次數(shù)為３、２、１、１； （２）平均查找長度四、算法閱讀題（本大題共4小題，每小題5分，共20分）30． ①S1=S1－next ②s2=s2－next ③s2(或s2!=NULL或s2amp。 typedef struct node { DateType data； Struct node * next； }ListNode； typedef ListNode * LinkList ； LinkList Leafhead=NULL； Void Inorder (BinTree T) { LinkList s； If(T){ Inorder(T－lchild)； If ((!T－lchild)amp。amp。35 錯填或不填均無分。While (p!=null) { Lnode*q=p。 該算法的輸入結(jié)果是：34 91 30 45 63 78 12： m 、 m 1三、運算題（每小題6分，共24分）劃分次序劃分結(jié)果第一次[38 24 40] 46 [56 80 95 79]第二次24 [38 40] 46 [56 80 95 79]第三次24 38 40 46 [56 80