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