數(shù)據(jù)結(jié)構(gòu)(java)復(fù)習(xí)題及答案

數(shù)據(jù)結(jié)構(gòu)(java)復(fù)習(xí)題及答案數(shù)據(jù)結(jié)構(gòu)(java)復(fù)習(xí)題及答案數(shù)據(jù)結(jié)構(gòu)(java)復(fù)習(xí)題及答案數(shù)據(jù)結(jié)構(gòu)(java)復(fù)習(xí)題及答案編制僅供參考審核批準(zhǔn)生效日期地址：電話：傳真:郵編:選擇題1、數(shù)據(jù)結(jié)構(gòu)在計算機(jī)內(nèi)存中的表示是指____A__A．?dāng)?shù)據(jù)的存儲結(jié)構(gòu)B.數(shù)據(jù)結(jié)構(gòu)C.數(shù)據(jù)的邏輯結(jié)構(gòu)D.數(shù)據(jù)元素之間的關(guān)系2、若一個算法的時間復(fù)雜度用T(n)表示，其中n的含義是（A）A．問題規(guī)模B．語句條數(shù)C．循環(huán)層數(shù)D．函數(shù)數(shù)量3、下列選項中與數(shù)據(jù)存儲結(jié)構(gòu)無關(guān)的術(shù)語是（D）A.順序表 B.鏈表C.鏈隊列 D.棧4、已知循環(huán)隊列的存儲空間大小為m，隊頭指針front指向隊頭元素，隊尾指針rear指向隊尾元素的下一個位置，則向隊列中插入新元素時，修改指針的操作是（D）=(rear-1)%m; =(front+1)%m;=(front-1)%m; =(rear+1)%m;5、棧和隊列的共同點(diǎn)是__C______A.都是先進(jìn)后出B.都是先進(jìn)先出C.只允許在端點(diǎn)處插入和刪除元素D.沒有共同點(diǎn)6、已知一堆棧的進(jìn)棧序列為1234,則下列哪個序列為不可能的出棧序列______D__7、具有線性結(jié)構(gòu)的數(shù)據(jù)結(jié)構(gòu)是（C）A．樹 B．圖C．棧和隊列D．廣義表8、假設(shè)以數(shù)組A[60]存放循環(huán)隊列的元素，其頭指針是front=47，當(dāng)前隊列有50個元素，則隊列的尾指針值為（B）A．3 B．37C．50 D．979、若棧采用鏈?zhǔn)酱鎯Y(jié)構(gòu)，則下列說法中正確的是（B）A．需要判斷棧滿且需要判斷?？誃．不需要判斷棧滿但需要判斷?？誄．需要判斷棧滿但不需要判斷?？誅．不需要判斷棧滿也不需要判斷?？?0、若一棵具有n(n>0)個結(jié)點(diǎn)的二叉樹的先序序列與后序序列正好相反，則該二叉樹一定是（C）A.結(jié)點(diǎn)均無左孩子的二叉樹B.結(jié)點(diǎn)均無右孩子的二叉樹C.高度為n的二叉樹D.存在度為2的結(jié)點(diǎn)的二叉樹11、若一棵二叉樹中度為l的結(jié)點(diǎn)個數(shù)是3，度為2的結(jié)點(diǎn)個數(shù)是4，則該二叉樹葉子結(jié)點(diǎn)的個數(shù)是（B） 12、在n個結(jié)點(diǎn)的線索二叉樹中，線索的數(shù)目為_C_______A．n-1B.n+113、一棵完全二叉樹有1001個結(jié)點(diǎn),其中有____B_____葉子結(jié)點(diǎn)15、一個有n個頂點(diǎn)的無向圖最多有___C____條邊。A.nB.n(n-1)C.n(n-1)/2D.2n16、以v1為起始結(jié)點(diǎn)對下圖進(jìn)行深度優(yōu)先遍歷，正確的遍歷序列是（D）A．v1，v2，v3，v4，v5，v6，v7B．v1，v2，v5，v4，v3，v7，v6C．v1，v2，v3，v4，v7，v5，v6D．v1，v2，v5，v6，v7，v3，v4二、填空題1、一個算法具有5個特性：__有窮性_____、__可行性____、確定性、輸入和輸出隊列的存儲方式有__順序隊列__________和____鏈?zhǔn)疥犃衉______。遞歸過程或函數(shù)調(diào)用時，處理參數(shù)及返回地址，需要一種稱為__棧_____的數(shù)據(jù)結(jié)構(gòu)。7、在單鏈表中某結(jié)點(diǎn)后插入一個新結(jié)點(diǎn)，需要修改___2____________個結(jié)點(diǎn)指針域的值。8、設(shè)棧S的初始狀態(tài)為空，若元素a、b、c、d、e、f依次進(jìn)棧，得到的出棧序列是b、d、c、f、e、a，則棧S的容量至少是_____3___________。10、設(shè)一個順序循環(huán)隊列容量為60，當(dāng)front=47，rear=23時，該隊列有______36____個元素。11、已知二維數(shù)組a[10][8]采用行主序存儲，數(shù)組首地址是1000，每個元素占用4字節(jié)，則數(shù)組元素a[4][5]的存儲地址是____________1176______________。12、已知一棵完全二叉樹的根（第0個）結(jié)點(diǎn)層次為1，則第100個結(jié)點(diǎn)的層次為_____7___。中根遍歷序列和后根遍歷序列相反的二叉樹是_______________結(jié)構(gòu)均無左孩子的二叉樹____________________。13、由256個權(quán)值構(gòu)造一棵哈夫曼樹，則該二叉樹共有___256+255_______結(jié)點(diǎn)。14、用6個權(quán)值分別為6、13、18、30、7和16的結(jié)點(diǎn)構(gòu)造一棵哈夫曼(Huffman)樹，該樹的帶權(quán)路徑長度為_____219____。深度為5的二叉樹至多有___2^5-1___個結(jié)點(diǎn)。17、一個有n個頂點(diǎn)的無向連通圖，最少有______n-1__________條邊。18、交換排序法是對序列中的元素進(jìn)行一系列比較，當(dāng)被比較的兩元素逆序時，進(jìn)行交換。______和_____是基于這類方法的兩種排序方法。19、在長度為n的順序表L中查找指定元素值的元素，其時間復(fù)雜度為__________有一個有序表為{1,3,9,12,32,41,45,62,75,77,82,95,99},當(dāng)采用二分查找法查找關(guān)鍵字為82的元素時，_______次比較后查找成功。20、設(shè)用希爾排序?qū)98,36,-9,0,47,23,1,8,10,7}進(jìn)行排序，給出的步長（也稱增量序列）為5,則第一趟排序后的結(jié)果是__________________________________________。三、應(yīng)用題1、將下列稀疏矩陣的非零元素表示成三元組的形式。2、畫出下列廣義表的雙鏈表示：中國（北京，上海，江蘇（南京，蘇州），浙江（杭州），廣東（廣州））3、已知一棵二叉樹的中根和后根遍歷序列如下，畫出據(jù)此構(gòu)造的二叉樹。中根遍歷序列：DBHEIAFKCG后根遍歷序列：DHIEBKFGCA4.已知一棵二叉排序樹（結(jié)點(diǎn)值大小按字母順序）的前序遍歷序列為EBACDFHG，請回答下列問題：(1)畫出此二叉排序樹；(2)若將此二叉排序樹看作森林的二叉鏈表存儲，請畫出對應(yīng)的森林5、已知有向圖的鄰接表如圖所示，請回答下面問題：(1)給出該圖的鄰接矩陣；(2)從結(jié)點(diǎn)A出發(fā)，寫出該圖的深度優(yōu)先遍歷序列。6、設(shè)用于通信的電文僅由5個字母{A,B,C,D,E}組成，字母在電文中出現(xiàn)的次數(shù)分別是2，4，5，7，8。為這五個字母設(shè)計哈夫曼編碼。7、（1）分別以prim、kruscal算法構(gòu)造下圖的最小生成樹。（2）Dijkstra算法求下圖中頂點(diǎn)1到其他所有頂點(diǎn)的最短路徑及長度。四、程序閱讀題1、順序循環(huán)隊列中，出隊方法如下，請補(bǔ)全空出的部分。PublicEdequeue(){If(!isEmpty()){Etemp=(E)[];=___+1)%()________________;return_______temp____;}returnnull;}2、以下是順序棧類的聲明，其中成員變量Value數(shù)組存儲棧的數(shù)據(jù)元素，top表示當(dāng)前棧頂元素的下標(biāo)，請補(bǔ)充以下空白。importclassSeqStack<E>implementsSStack<E>{privateObjectvalue[];privateinttop;publicSeqStack(intcapacity){ =newObject[(capacity)]; =-1;}publicSeqStack(){this(10);} publicbooleanisEmpty(){//判斷棧是否為空，若空棧返回true return==-1________; } publicbooleanpush(Eelement){//元素element入棧，若操作成功返回true if(element==null) return