【正文】 }}Int Binsch(ElemType A[ ],int n,KeyType K){int low=0。while (low=high){int mid=_______________________________；if (K==A[mid].key) return mid。 //在左子表上繼續(xù)查找 else __________________________________。 //查找失敗，返回1}ElemType DeleFront(LNode * amp。2. 2. 圖8如圖8所示。 閱讀算法（每題7分，共14分）1. 1. (1) 判斷n是否是素數(shù)（或質(zhì)數(shù)） （2）O（）2. 2. 功能為：從初始點vi出發(fā)廣度優(yōu)先搜索由鄰接表GL所表示的圖。 算法填空（8 分） (low+high)/2 high=mid1 low=mid+1 六、 六、 HL){if (HL==NULL){ cerr空表endl。}LNode* p=HL。ElemType temp=pdata。return temp。 2. 2. 用鏈接方式存儲的隊列，在進行插入運算時( ). A. 僅修改頭指針 　 B. 頭、尾指針都要修改 C. 僅修改尾指針 、尾指針可能都要修改3. 3. 以下數(shù)據(jù)結(jié)構(gòu)中哪一個是非線性結(jié)構(gòu)？( ) A. 隊列 　　 B. 棧 C. 線性表 　　 D. 二叉樹4. 4. 設(shè)有一個二維數(shù)組A[m][n]，假設(shè)A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每個元素占一個空間，問A[3][3](10)存放在什么位置？腳注(10)表示用10進制表示。 6. 6. 二叉樹的第k層的結(jié)點數(shù)最多為( ). A．2k1 +1 　　　D. 2k17. 7. 若有18個元素的有序表存放在一維數(shù)組A[19]中，第一個元素放A[1]中，現(xiàn)進行二分查找，則查找A［3］的比較序列的下標(biāo)依次為( ) A. 1，2，3 B. 9，5，2，3 C. 9，5，3 D. 9，4，2，38. 8. 對n個記錄的文件進行快速排序，所需要的輔助存儲空間大致為 A. O（1） 　　B. O（n）　　 C. O（1og2n） D. O（n2）9. 9. 對于線性表（7，34，55，25，64，46，20，10）進行散列存儲時，若選用H（K）=K %9作為散列函數(shù)，則散列地址為1的元素有（ ）個， A．1 B．2 C．3 D．410. 10. 設(shè)有6個結(jié)點的無向圖，該圖至少應(yīng)有( )條邊才能確保是一個連通圖。二、 二、 填空題（每空1分，共26分）1. 1.2. 2.3. 3.4. 4.中綴算式（3+4X）2Y/3對應(yīng)的后綴算式為_______________________________。 若用鏈表存儲一棵二叉樹時，每個結(jié)點除數(shù)據(jù)域外，還有指向左孩子和右孩子的兩個指針。6. 6.7. 7.8. 8.9. 9.10. 10.11. 11.12. 12. 在如下數(shù)組A中鏈接存儲了一個線性表，表頭指針為A [0].next，試寫出該線性表。605078903412. 2.3. 3. E={(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15,(3,5)12,(3,6)9,(4,6)4,(4,7)20,(5,6)18,(6,7)25}。4. 4.amp。2. 2. void ABC(BTNode * BT){ if BT { ABC (BTleft)。 coutBTdata39。 } } 該算法的功能是： item){ if (BST==NULL) return false。//查找成功 return ___________。 else return Find(_______________,item)。六、 六、 編寫算法（共8分）統(tǒng)計出單鏈表HL中結(jié)點的值等于給定值X的結(jié)點數(shù)。 單選題（每題2分，共20分） 二、 二、 增加111. 11. 歸并三、 三、 閱讀算法（每題7分，共14分）1. 1. （1）查詢鏈表的尾結(jié)點（2）將第一個結(jié)點鏈接到鏈表的尾部，作為新的尾結(jié)點 （3）返回的線性表為（a2,a3,…,an,a1） 2. 2. 遞歸地后序遍歷鏈?zhǔn)酱鎯Φ亩鏄洹?算法填空（每空2分，共8 分）true BSTleft BSTright 六、 六、 LNode* p=HL。 p=pnext。 }//CountX 單選題（每小題2分，共8分） 在一個長度為n的順序線性表中順序查找值為x的元素時，查找成功時的平均查找長度（即x與元素的平均比較次數(shù)，假定查找每個元素的概率都相等）為 ( )。 A s→link=p→link。 B p→link=s。 C p→link=s→link。 D q →link=s。 A 棧頂 B 棧底 C 任意位置 D 指定位置 填空題（每空1分，共32分） 數(shù)據(jù)的邏輯結(jié)構(gòu)被分為__________、 ___________ 、________和________四種。 在下面的數(shù)組a中鏈接存儲著一個線性表，表頭指針為a[o].next，則該線性表為_________________________________________________。 60 56 42 38 4 3 7 6 2 0 1 在以HL為表頭指針的帶表頭附加結(jié)點的單鏈表和循環(huán)單鏈表中，判斷鏈表為空的條件分別為________________和____________________。 當(dāng)堆棧采用順序存儲結(jié)構(gòu)時，棧頂元素的值可用———————表示；當(dāng)堆棧采用鏈接存儲結(jié)構(gòu)時，棧頂元素的值可用_______________表示。 在圖的鄰接表中，每個結(jié)點被稱為____________，通常它包含三個域：一是_____________；二是___________；三是_____________。 1 11 1 運算題（每小題6分，共24分） 已知一組記錄的排序碼為（46，79，56，38，40，80, 95，24），寫出對其進行快速排序的每一次劃分結(jié)果。 一個線性表為B=（12，23，45，57，20，03，78，31，15，36），設(shè)散列表為HT[0..12]，散列函數(shù)為H（key）= key % 13并用線性探查法解決沖突，請畫出散列表，并計算等概率情況下查找成功的平均查找長度。 已知一棵二叉樹的前序遍歷的結(jié)果序列是ABECKFGHIJ，中序遍歷的結(jié)果是EBCDAFHIGJ，試寫出這棵二叉樹的后序遍歷結(jié)果。假定每個頂點鄰接表中的結(jié)點是按頂點序號從大到小的次序鏈接的。 閱讀算法，回答問題（每小題8分，共16分） include include consst int stackmaxsize = 30。struct stack {elemtype stack [stackmaxsize]。}。 initstack(a)。 cin x。 cin x。cout end1。Template calss type void BinTree Type ：：unknown (BinTreeNodeType*t) { BinTreeNode Type *p =t, *temp。 p→leftchild = p→rightchild。 unknown(p→leftchild)。 }}該算法的功能是：________________________________ 算法填空，在畫有橫線的地方填寫合適的內(nèi)容（10分） int Binsch( ElemType A[ ],int low ,int high,KeyType K ) {if (low = high){ int mid = 1 if ( K= = A[ mid ].key ) return mid。六、 六、編寫算法，將一個結(jié)點類型為Lnode的單鏈表按逆序鏈接，即若原單鏈表中存儲元素的次序為a1，……an1，an，則逆序鏈接后變?yōu)? an，an1，……a1。 HL)數(shù)據(jù)結(jié)構(gòu)試題（答案） 一、單選題（每小題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： []。7： 5 318： 邊結(jié)點、鄰接點域、權(quán)域、鏈域；9： 索引值域、開始位置域；10： B、I和J；11： O（log2n）、O(nlog2n)。 0 1 2 3 4 5 6 7 8 9 10 11 127857452031查找成功的平均查找長度：ASL SUCC=14/10= 此二叉樹的后序遍歷結(jié)果是：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分） 該算法的功能是：交換二叉樹的左右子樹的遞歸算法。 2是： Binsch(A,low,mid–1,K)。 4是： 1；六、編寫算法（10分）根據(jù)編程情況，酌情給分。HL=NULL。 P=p→next。 HL=q。一、 一、項選擇題（本大題共15小題，每小題2分，共30分）在每小題列出的四個選項中只有一個選項是符合題目要求的，請將正確選項前的字母填在題后的括號內(nèi)。第二部分 非選擇題（共70分）二、填空題（本大題共10小題，每小題2分，若有兩個空格，每個空格1分，共20分）不寫解答過程，將正確的答案寫在每小題的空格內(nèi)。16．?dāng)?shù)據(jù)的邏輯結(jié)構(gòu)是從邏輯關(guān)系上描述數(shù)據(jù)，它與數(shù)據(jù)的 無關(guān)，是獨立于計算機的。18．棧頂?shù)奈恢檬请S著 操作而變化的。20．假設(shè)一個9階的上三角矩陣A按列優(yōu)先順序壓縮存儲在一維數(shù)組B中，其中B[0]存儲矩陣中第1個元素a1,1,則B[31]中存放的元素是 。 22．已知一個圖的廣度優(yōu)先生成樹如右圖所示，則與此相 應(yīng)的廣度優(yōu)先遍歷序列為 。 24．在有序表（12，24，36，48，60，72，84）中二分查找關(guān)鍵字72時所需進行的關(guān)鍵字比較次數(shù)為 。