【文章內容簡介】 個元素的概率都相等）為 ( B )。A n B n/2 C (n+1)/2 D (n1)/2 在一個單鏈表中,若q所指結點是p所指結點的前驅結點,若在q與p之間插入一個s所指的結點,則執(zhí)行( A )。 A s→link=p→link。 p→link=s。 B p→link=s。 s→link=q。 C p→link=s→link。 s→link=p。 D q →link=s。 s→link =p。 棧的插入和刪除操作在（ ）進行。A 棧頂 B 棧底 C 任意位置 D 指定位置 由權值分別為11，8，6，2，5的葉子結點生成一棵哈夫曼樹，它的帶權路徑長度為（ ） A 24 B 71 C 48 D 53二、 二、 填空題（每空1分，共32分） 數(shù)據(jù)的邏輯結構被分為__________、 ___________ 、________和________四種。 一種抽象數(shù)據(jù)類型包括______________和_____________兩個部分。 在下面的數(shù)組a中鏈接存儲著一個線性表，表頭指針為a[o].next，則該線性表為_________________________________________________。 a 0 1 2 3 4 5 6 7 8 60 56 42 38 74 25 4 3 7 6 2 0 1datanext 在以HL為表頭指針的帶表頭附加結點的單鏈表和循環(huán)單鏈表中，判斷鏈表為空的條件分別為________________和____________________。 用具有n個元素的一維數(shù)組存儲一個循環(huán)隊列，則其隊首指針總是指向隊首元素的___________，該循環(huán)隊列的最大長度為__________。 當堆棧采用順序存儲結構時，棧頂元素的值可用———————表示；當堆棧采用鏈接存儲結構時，棧頂元素的值可用_______________表示。 一棵高度為5的二叉樹中最少含有_________個結點，最多含有________個結點；一棵高度為5的理想平衡樹中，最少含有_________個結點，最多含有_________個結點。 在圖的鄰接表中，每個結點被稱為____________，通常它包含三個域：一是_____________；二是___________；三是_____________。 在一個索引文件的索引表中，每個索引項包含對應記錄的_________和___________兩項數(shù)據(jù)。 假定一棵樹的廣義表表示為A（B（C，D（E，F(xiàn)，G），H（I，J））），則樹中所含的結點數(shù)為_________個，樹的深度為_________,樹的度為________, 結點H的雙親結點為________,孩子結點為_______________ 。1 1 在堆排序的過程中，對任一分支結點進行篩運算的時間復雜度為_________,整個堆排序過程的時間復雜度為________________。1 1 在對m階的B_樹插入元素的過程中，每向一個結點插入一個索引項（葉子結點中的索引項為關鍵字和空指針）后，若該結點的索引項數(shù)等于______個，則必須把它分裂為_______個結點。三、 三、 運算題（每小題6分，共24分） 已知一組記錄的排序碼為（46，79，56，38，40，80, 95，24），寫出對其進行快速排序的每一次劃分結果。 一個線性表為B=（12，23，45，57，20，03，78，31，15，36），設散列表為HT[0..12]，散列函數(shù)為H（key）= key % 13并用線性探查法解決沖突，請畫出散列表，并計算等概率情況下查找成功的平均查找長度。 已知一棵二叉樹的前序遍歷的結果序列是ABECKFGHIJ，中序遍歷的結果是EBCDAFHIGJ，試寫出這棵二叉樹的后序遍歷結果。 已知一個圖的頂點集V各邊集G如下：V = {0，1，2，3，4，5，6，7，8，9}；E = {（0，1），（0，4），（1，2），（1，7），（2，8），（3，4），（3 ，8），（5，6），（5，8），（5，9），（6，7），（7，8），（8，9）}當它用鄰接矩陣表示和鄰接表表示時，分別寫出從頂點V0出發(fā)按深度優(yōu)先搜索遍歷得到的頂點序列和按廣度優(yōu)先搜索遍歷等到的頂點序列。假定每個頂點鄰接表中的結點是按頂點序號從大到小的次序鏈接的。圖深度優(yōu)先序列廣度優(yōu)先序列鄰接矩陣表示時鄰接表表示時 四、 四、 閱讀算法，回答問題（每小題8分，共16分）假定從鍵盤上輸入一批整數(shù)，依次為：78 63 45 30 91 34 –1，請寫出輸出結果。 include include consst int stackmaxsize = 30。typedef int elemtype。struct stack {elemtype stack [stackmaxsize]。 int top。}。 include “”Void main ( ){ stack a。 initstack(a)。 int x。 cin x。 while (x! = 1) { push (a, x )。 cin x。}while (!stackempty (a)) cout pop (a) ”” 。cout end1。}該算法的輸出結果為：__________________________________________________________. 閱讀以下二叉樹操作算法，指出該算法的功能。Template calss type void BinTree Type ：：unknown (BinTreeNodeType*t) { BinTreeNode Type *p =t, *temp。 if (p!=NULL) { temp = p→leftchild。 p→leftchild = p→rightchild。 p→rightchild = temp。 unknown(p→leftchild)。 undnown(p→rightchild)。 }}該算法的功能是：________________________________ 五、 五、 算法填空，在畫有橫線的地方填寫合適的內容（10分）對順序存儲的有序表進行二分查找的遞歸算法 。 int Binsch( ElemType A[ ],int low ,int high,KeyType K ) {if (low = high){ int mid = 1 if ( K= = A[ mid ].key ) return mid。 else if ( K A[mid].key) return 2 else return 3}else return 4六、 六、 編寫算法（10分）編寫算法，將一個結點類型為Lnode的單鏈表按逆序鏈接，即若原單鏈表中存儲元素的次序為a1，……an1，an，則逆序鏈接后變?yōu)? an，an1，……a1。Void contrary (Lnode * amp。 HL)數(shù)據(jù)結構試題（答案） 一、單選題（每小題2分，共8分）題 號 1 2 3 4答 案 C D A B二、填空題（每空1分，共32分）1： 集合、線性、樹、圖；2： 數(shù)據(jù)描述、操作聲名；3： （38，56，25，60，42，74）；4： HL→next =NULL； HL=HL→next；5： 前一個位置； n1；6： []。 HS→data。7： 5 318： 邊結點、鄰接點域、權域、鏈域；9： 索引值域、開始位置域；10： B、I和J；11： O（log2n）、O(nlog2n)。12： m 、 m 1三、運算題（每小題6分，共24分）劃分次序劃分結果第一次[38 24 40] 46 [56 80 95 79]第二次24 [38 40] 46 [56 80 95 79]第三次24 38 40 46 [56 80 95 79]第四次24 38 40 46 56 [80 95 79]第五次24 38 40 46 56 79 [80 95]第六次24 38 40 46 56 79 80 95 0 1 2 3 4 5 6 7 8 9 10 11 1278150357452031233612查找成功的平均查找長度：ASL SUCC=14/10= 此二叉樹的后序遍歷結果是：EDCBIHJGFA圖深度優(yōu)先序列廣度優(yōu)先序列鄰接矩陣表示時0，1，2，8，3，4，5，6，7，90，1，4，2，7，3，8，6，5，9鄰接表表示時0，4，3，8，9，5，6，7，1，20，4，1，3，7，2，8，6，9，5四、閱讀算法，回答問題（每小題8分，共16分） 該算法的輸入結果是：34 91 30 45 63 78 該算法的功能是：交換二叉樹的左右子樹的遞歸算法。五、算法填空，在畫有橫線的地方填寫合適的內容（10分）1是：（low + high）/2。 2是： Binsch(A,low,mid–1,K)。 3是： Binsch(A,mid+1,high,K)。 4是： 1；六、編寫算法（10分）根據(jù)編程情況，酌情給分。 {Lnode *P=HL。HL=NULL。While (p!=null) { Lnode*q=p。 P=p→next。 q→next=HL。 HL=q。 }}第一部分 選擇題(30分)一、 一、項選擇題（本大題共15小題，每小題2分，共30分）在每小題列出的四個選項中只有一個選項是符合題目要求的，請將正確選項前的字母填在題后的括號內。1．算法指的是（ ） A．計算機程序 B．解決問題的計算方法 C．排序算法 D．解決問題的有限運算序列2．線性表采用鏈式存儲時，結點的存儲地址（ ） A．必須是不連續(xù)的 B．連續(xù)與否均可 C．必須是連續(xù)的 D．和頭結點的存儲地址相連續(xù)3．將長度為n的單鏈表鏈接在長度為m的單鏈表之后的算法的時間復雜度為（ ） 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ù)組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．若目標串的長度為n，模式串的長度為[n/3]，則執(zhí)行模式匹配算法時，在最壞情況下的時間復雜度是（ ） A．O（） B．O（n） C．O（n2） D．O（n3）8．一個非空廣義表的表頭（ ） A．不可能是子表 B．只能是子表 C．只能是原子 D．可以是子表或原子9．假設以帶行表的三元組表表示稀疏矩陣，則和下列行表02335 對應的稀疏矩陣是（ ） 10．在一棵度為3的樹中,度為3的結點個數(shù)為2,度為2 的結點個數(shù)為1,則度為0的結點個數(shù)為( ) A．4 B．5 C．6 D．711．在含n個頂點和e條邊的無向圖的鄰接矩陣中,零元素的個數(shù)為( ) A．e B．2e C．n2－e D．n2－2e12．假設一個有n個頂點和e條弧的有向圖用鄰接表表示,則刪除與某個頂點vi相關的所有弧的時間復雜度是( ) A．O(n) B．O(e) C．O(n+e) D．O(n*e)13．