【文章內(nèi)容簡介】 。五、算法填空，在畫有橫線的地方填寫合適的內(nèi)容。（12分）從一維數(shù)組A[n]中二分查找關(guān)鍵字為K的元素的遞歸算法，若查找成功則返回對應元素的下標，否則返回1。int Binsch( ElemType A[] , int low , int high , KeyType K ){ if ( low=high ){int mid = (low+high)/2。if ( K==A[mid].key) 。 else if (KA[mid].key ) 。 else 。}else return 1。 }六、編寫算法（14分）編寫在以BST為樹根指針的二叉搜索樹上進行查找值為item的結(jié)點的非遞歸算法，若查找成功則由item帶回整個結(jié)點的值并返回true，否則返回false。 bool Find( BTreeNode * BST , ElemType amp。 item )數(shù)據(jù)結(jié)構(gòu)作業(yè)題（四）一、選擇題（每題2分，共20分）1．從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為（ ）兩大類。A．動態(tài)結(jié)構(gòu)、靜態(tài)結(jié)構(gòu) B．順序結(jié)構(gòu)、鏈式結(jié)構(gòu) C．線性結(jié)構(gòu)、非線性結(jié)構(gòu) D．初等結(jié)構(gòu)、構(gòu)造型結(jié)構(gòu)2．以下數(shù)據(jù)結(jié)構(gòu)中，哪一個是線性結(jié)構(gòu)（ ）？ A．廣義表 B. 二叉樹 C. 稀疏矩陣 D. 串3．連續(xù)存儲設計時，存儲單元的地址（ ）。A．一定連續(xù) B．一定不連續(xù) C．不一定連續(xù) D．部分連續(xù)，部分不連續(xù)4．若長度為n的線性表采用順序存儲結(jié)構(gòu)，在其第i個位置插入一個新元素的算法的時間復雜度為（ ）。A. O(0) B. O(1) C. O(n) D. O(n2) 5．在雙向鏈表指針p的結(jié)點前插入一個指針q的結(jié)點操作是（ ）。A. pLlink=q。qRlink=p。pLlinkRlink=q。qLlink=q；B. pLlink=q。pLlinkRlink=q。qRlink=p。qLlink=pLlink。C. qRlink=p。qLlink=pLlink。pLlinkRlink=q。pLlink=q。D. qLlink=pLlink。qRlink=q。pLlink=q。pLlink=q。6．若一個棧的輸入序列為1,2,3,…,n，輸出序列的第一個元素是i，則第j個輸出元素是（ ）。 A. ij1 B. ij C. ji+1 D. 不確定的7．有六個元素6，5，4，3，2，1 的順序進棧，問下列哪一個不是合法的出棧序列？（ ）A. 5 4 3 6 1 2 B. 4 5 3 1 2 6 C. 3 4 6 5 2 1 D. 2 3 4 1 5 6 8．用鏈接方式存儲的隊列，在進行刪除運算時（ ）。A. 僅修改頭指針 B. 僅修改尾指針 C. 頭、尾指針都要修改 D. 頭、尾指針可能都要修改9．若用一個大小為6的數(shù)組來實現(xiàn)循環(huán)隊列，且當前rear和front的值分別為0和3，當從隊列中刪除一個元素，再加入兩個元素后，rear和front的值分別為多少？( ) A. 1和 5 B. 2和4 C. 4和2 D. 5和1 10．棧和隊列的共同點是（ ）。A. 都是先進先出 B. 都是先進后出 C. 只允許在端點處插入和刪除元素 D. 沒有共同點二、填空題（每空2分，共30分）1．數(shù)據(jù)結(jié)構(gòu)中評價算法的兩個重要指標是 和 。2．一個算法具有5個特性: 、 、 ，有零個或多個輸入、有一個或多個輸出。3．在一個長度為n的順序表中第i個元素（1=i=n）之前插入一個元素時，需向后移動________個元素。4．對于雙向鏈表,在兩個結(jié)點之間插入一個新結(jié)點需修改的指針共 ______個，單鏈表為_______個。5．設數(shù)組a[1..50,1..80]的基地址為2000，每個元素占2個存儲單元，若以行序為主序順序存儲，則元素a[45,68]的存儲地址為_ _。若以列序為主序順序存儲，則元素a[45,68]的存儲地址為_ _。6．所謂稀疏矩陣指的是_______。7．廣義表的_______ 定義為廣義表中括弧的重數(shù)。8．具有256個結(jié)點的完全二叉樹的深度為______。9．已知一棵度為3的樹有2個度為1的結(jié)點，3個度為2的結(jié)點，4個度為3的結(jié)點，則該樹有______個葉子結(jié)點。10．高度為8的完全二叉樹至少有______個葉子結(jié)點。三、計算題（每題6分，共30分）1．如果輸入序列為1 2 3 4 5 6,試問能否通過棧結(jié)構(gòu)得到以下兩個序列:4 3 5 6 1 2和1 3 5 4 2 6。請說明為什么不能或如何才能得到。2．假定一棵二叉樹廣義表表示為a(b(c),d(e,f))，分別寫出對它進行先序、中序、后序、按層遍歷的結(jié)果。先序：中序：后序：按層：3．已知一個圖的頂點集V和邊集G分別為：V={0,1,2,3,4,5,6,7}。　E={(0,1)8,(0,2)5,(0,3)2,(1,5)6,(2,3)25,(2,4)13,(3,5)9,(3,6)10, (4,6)4,(5,7)20,(6,7)30}。　　按照普里姆算法從頂點0出發(fā)得到最小生成樹，試寫出在生成最小生成樹的過程中依次得到的各條邊?！　_______, ________, ________, ________, ________, ________, ________。4. 已知一個圖的頂點集V和邊集G分別為：　V={0,1,2,3,4,5,6,7,8}?！={0,2,1,3,1,4,2,4,2,5,3,6,3,7,4,7,4,8,5,7,6,7,7,8}。若存儲它采用鄰接表，并且每個頂點鄰接表中的邊結(jié)點都是按照終點序號從小到大的次序鏈接的，則按主教材中介紹的進行拓撲排序的算法，寫出得到的拓撲序列（提示：先畫出對應的圖形，然后再運算）。拓撲序列：5．假定一組記錄的排序碼為(46,79,56,38,40,80,25,34)，則對其進行快速排序的第一次劃分后的結(jié)果為________________。四、算法填空（10分）1． 五、編程（10分）1．設計算法以求解從集合{1..n}中選取k（k=n）個元素的所有組合。例如，從集合{1..4}中選取2個元素的所有組合的輸出結(jié)果為：1 2，1 3，1 4，2 3， 2 4，3 4。數(shù)據(jù)結(jié)構(gòu)作業(yè)題（五）一、選擇題（每題2分，共20分）1．若需要利用形參直接訪問實參，則應把形參變量說明為（ ）參數(shù)。A指針 B引用 C值2．在一個單鏈表HL中，若要在指針q所指結(jié)點的后面插入一個由指針p所指向的結(jié)點，則執(zhí)行（ ）。A q一next=p一next；p一next=q；B p一next=q一next；q=p；C 9一next=p一next；p一next=q；D p一next=q一next；q一next=p；3．在一個順序隊列中，隊首指針指向隊首元素的（ ）位置。A前一個 B后一個 C當前4．向二叉搜索樹中插入一個元素時，其時間復雜度大致為（ ）。A O（1） B O（1og2n）C O（n） D O（nlog2n）5．假設有兩個串A和B，求B在A中首次出現(xiàn)的位置的操作，我們稱為（ ）。 6．我們對記錄進行排序的目的是（ ）。 7．在最壞的情況下，冒泡排序法的時間復雜度為（ ）。(lgn) (nlgn) (n2) (n)8．廣義表(A,B,E,F,G)的表尾是（ ）。A.(B, E , F, G) B.( ) C.（A，B， E，F(xiàn)，G) D.（G）9．線性表如果采用鏈式存儲結(jié)構(gòu)，要求內(nèi)存中的存儲單元的地址（ ）。，也可以是不連續(xù)的10．在數(shù)據(jù)結(jié)構(gòu)中，從邏輯結(jié)構(gòu)上，我們可以把數(shù)據(jù)結(jié)構(gòu)分為（ ）。 二、填空題（每空1分，共2