東軟數(shù)據(jù)結(jié)構(gòu),樹(shù)和二叉樹(shù)復(fù)習(xí)題

精選文庫(kù)樹(shù)和二叉樹(shù)：紙質(zhì)作業(yè)一、已知二叉樹(shù)T邏輯結(jié)構(gòu)如下圖所示，請(qǐng)分別用順序存儲(chǔ)和二叉鏈表存儲(chǔ)法表示此樹(shù)。二、將下面的森林F=T1，T2，T3轉(zhuǎn)換為對(duì)應(yīng)的二叉樹(shù)，并寫(xiě)出相應(yīng)二叉樹(shù)的先根遍歷序列。三、將下列由三棵樹(shù)組成的森林轉(zhuǎn)換為二叉樹(shù)，并寫(xiě)出相應(yīng)二叉樹(shù)的中根遍歷序列NPGHJMOLIKEDFBAC四、已知樹(shù)T的孩子鏈表存儲(chǔ)結(jié)構(gòu)如圖所示，試畫(huà)出此樹(shù)邏輯結(jié)構(gòu)，以及此樹(shù)轉(zhuǎn)換成的二叉樹(shù)邏輯結(jié)構(gòu)，并寫(xiě)出二叉樹(shù)的后根遍歷序列五、設(shè)一棵二叉樹(shù)的先序序列為：A B D F C E G H 中序遍歷序列為： B F D A G E H C（1）畫(huà)出這棵二叉樹(shù)。（2）將這棵二叉樹(shù)轉(zhuǎn)換成對(duì)應(yīng)的樹(shù)（或森林）。六、給定集合15,3,14,2,6,9,16,17（1）構(gòu)造相應(yīng)的huffman樹(shù)（規(guī)定：二叉樹(shù)中兩個(gè)結(jié)點(diǎn)，權(quán)值小的結(jié)點(diǎn)居左）（2）計(jì)算它的帶權(quán)路徑長(zhǎng)度（3）寫(xiě)出它的huffman編碼：（規(guī)定：左子樹(shù)編碼為0，右子樹(shù)編碼為1,左小右大）七、假設(shè)通信電文使用的字符集為a,b,c,d,e,f，各字符在電文中出現(xiàn)的頻度分別為：0.34，0.05，0.12，0.23，0.08，0.18，試為這6個(gè)字符設(shè)計(jì)哈夫曼編碼。請(qǐng)先畫(huà)出你所構(gòu)造的哈夫曼樹(shù)(要求樹(shù)中左孩子節(jié)點(diǎn)的權(quán)值小于右孩子節(jié)點(diǎn)的權(quán)值，左分支表示字符“0”，右分支表示字符“1”)，然后分別寫(xiě)出每個(gè)字符對(duì)應(yīng)的編碼。八、假定教室中有A、B、C、D、E五個(gè)設(shè)備，需編寫(xiě)一套指令集對(duì)五個(gè)設(shè)備進(jìn)行自動(dòng)開(kāi)關(guān)控制，五個(gè)設(shè)備一天中的使用次數(shù)分別是7，5，2，4，9次。為使得指令集長(zhǎng)度最短，請(qǐng)對(duì)五個(gè)設(shè)備進(jìn)行編碼，要求畫(huà)出哈夫曼樹(shù)，并寫(xiě)出五個(gè)設(shè)備所對(duì)應(yīng)的哈夫曼編碼。九、假定用于通訊的電文僅有8個(gè)字母C1，C2，C8組成，各個(gè)字母在電文中出現(xiàn)的頻率分別為5，25，3，6，10，11，36，4，試為這8個(gè)字母設(shè)計(jì)哈夫曼編碼樹(shù)，并寫(xiě)出8個(gè)字符的哈夫曼編碼十、A,B,C,D,E的權(quán)值為3, 2, 4, 5, 1，用此權(quán)值構(gòu)造哈夫曼（Huffman）樹(shù)，并求此哈夫曼（Huffman）樹(shù)和各個(gè)字符的哈夫曼編碼（左分支為0，右分支為1）紙質(zhì)作業(yè)2：排序一、初始關(guān)鍵字序列如下：49，38， 65，97，76，13，27，49，55 04，請(qǐng)寫(xiě)出它們的希爾排序的全過(guò)程(其中d=5,3,1）二、給定的關(guān)鍵字序列21，22，27，78，40，05，47，69，12，99，要按升序排序，請(qǐng)寫(xiě)出采用冒泡排序法前3趟的結(jié)果，和用堆排序法選擇出最大和次大關(guān)鍵字的結(jié)果（圖）三、已知某文件的記錄關(guān)鍵字集為50，10，75，40，45，85，80，寫(xiě)出快速排序方法進(jìn)行排序的前2次劃分的結(jié)果四、已知某文件的記錄關(guān)鍵字集為50，10，30，40，45，85，80，要從小到大進(jìn)行排序，請(qǐng)分別寫(xiě)出直接插入排序的前2趟結(jié)果和直接選擇排序的前3趟結(jié)果。五、設(shè)要將序列（17,8,3,25,16,1,13,19,18,4,6,24）中的關(guān)鍵字按升序重新排列，請(qǐng)給出對(duì)該序列進(jìn)行冒泡排序的第一趟排序結(jié)果、及以第一個(gè)元素為樞軸的快速排序的第一次劃分的結(jié)果。紙質(zhì)作業(yè)3：查找一、設(shè)哈希（Hash）表的地址范圍為013，哈希函數(shù)為：H（K）K MOD 13。K為關(guān)鍵字，用線性探測(cè)法再散列法處理沖突，輸入關(guān)鍵字序列： （23，24，32，4，31，30，46，47）造出Hash表，試回答下列問(wèn)題：（1） 畫(huà)出哈希表的示意圖；（2） 若查找關(guān)鍵字30，需要依次與哪些關(guān)鍵字進(jìn)行比較？（3） 若查找關(guān)鍵字14，需要依次與哪些關(guān)鍵字比較？假定每個(gè)關(guān)鍵字的查找概率相等，求查找成功時(shí)的平均查找長(zhǎng)度。二、請(qǐng)用序列（45，24，53，12，37，93）建立一棵二叉排序樹(shù)，畫(huà)出該樹(shù)，并求在等概率情況下，查找成功的平均查找長(zhǎng)度。三、選取哈希函數(shù)H(key)key Mod 11，用線性探測(cè)再散列開(kāi)放定址法解決沖突。試在010的散列地址空間內(nèi)對(duì)關(guān)鍵字序列19、11、31、23、17、27、41、13、91、61構(gòu)造哈希表，并計(jì)算在等概率下成功查找的平均查找長(zhǎng)度。四、設(shè)有一組關(guān)鍵字9,1,23,14,55,20,84,27，采用哈希函數(shù)：H（key）=key mod 7 ，表長(zhǎng)為10，用開(kāi)放地址法的線性探測(cè)再散列方法解決沖突。要求：對(duì)該關(guān)鍵字序列構(gòu)造哈希表，并計(jì)算查找成功的平均查找長(zhǎng)度。五、設(shè)哈希（Hash）表的地址范圍為017，哈希函數(shù)為：H （K）=K MOD 16，K為關(guān)鍵字，用線性探測(cè)再散列法處理沖突，輸入關(guān)鍵字序列：10，24，32，17，31，30，46，47，40，63，49造出哈希表，試回答下列問(wèn)題： （1） 畫(huà)出哈希表示意圖； （2） 若查找關(guān)鍵字63，需要依次與哪些關(guān)鍵字比較?（3） 若查找關(guān)鍵字60，需要依次與哪些關(guān)鍵字比較?（4） 假定每個(gè)關(guān)鍵字的查找概率相等，求查找成功時(shí)的平均查找長(zhǎng)度。六、對(duì)于序列：12，16，23，34，45，57，78，91，95，100，112進(jìn)行二分法查找：（1）畫(huà)出二分查找判定樹(shù)（2）求出等概率情況下，該二分查找的ASL？ （3）查找元素95需要經(jīng)過(guò)幾次比較？和哪些元素比較？ （4）查找元素20需要經(jīng)過(guò)幾次比較確定找不到？和哪些元素比較？ 七、已知如下所示長(zhǎng)度為12的表(34,25,68,72,21,15,49,29,77,8,19,102)（1）按表中元素的順序依次插入一棵初始為空的二叉排序樹(shù)，畫(huà)出插入完成之后的二叉排序樹(shù)（2）并求其在等概率的情況下查找成功的平均查找長(zhǎng)度。習(xí)題一參考答案2試述數(shù)據(jù)結(jié)構(gòu)研究的3個(gè)方面的內(nèi)容。參考答案: 數(shù)據(jù)結(jié)構(gòu)研究的3個(gè)方面分別是數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)和數(shù)據(jù)的運(yùn)算（操作）。3試述集合、線性結(jié)構(gòu)、樹(shù)型結(jié)構(gòu)和圖型結(jié)構(gòu)四種常用數(shù)據(jù)結(jié)構(gòu)的特性。參考答案: 集合結(jié)構(gòu)：集合中數(shù)據(jù)元素之間除了“同屬于一個(gè)集合”的特性外，數(shù)據(jù)元素之間無(wú)其它關(guān)系，它們之間的關(guān)系是松散性的。 線性結(jié)構(gòu)：線性結(jié)構(gòu)中數(shù)據(jù)元素之間存在“一對(duì)一”的關(guān)系。即若結(jié)構(gòu)非空，則它有且僅有一個(gè)開(kāi)始結(jié)點(diǎn)和終端結(jié)點(diǎn)，開(kāi)始結(jié)點(diǎn)沒(méi)有前趨但有一個(gè)后繼，終端結(jié)點(diǎn)沒(méi)有后繼但有一個(gè)前趨，其余結(jié)點(diǎn)有且僅有一個(gè)前驅(qū)和一個(gè)后繼。 樹(shù)形結(jié)構(gòu)：樹(shù)形結(jié)構(gòu)中數(shù)據(jù)元素之間存在“一對(duì)多”的關(guān)系。即若結(jié)構(gòu)非空，則它有一個(gè)稱為根的結(jié)點(diǎn)，此結(jié)點(diǎn)無(wú)前驅(qū)結(jié)點(diǎn)，其余結(jié)點(diǎn)有且僅有一個(gè)前驅(qū)，所有結(jié)點(diǎn)都可以有多個(gè)后繼。 圖形結(jié)構(gòu)：圖形結(jié)構(gòu)中數(shù)據(jù)元素之間存在“多對(duì)多”的關(guān)系。即若結(jié)構(gòu)非空，則在這種數(shù)據(jù)結(jié)構(gòu)中任何結(jié)點(diǎn)都可能有多個(gè)前驅(qū)和后繼。4設(shè)有數(shù)據(jù)的邏輯結(jié)構(gòu)的二元組定義形式為B=(D,R)，其中D=a1,a2,an，R=| i=1,2,，n-1，請(qǐng)畫(huà)出此邏輯結(jié)構(gòu)對(duì)應(yīng)的順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的示意圖。參考答案: 順序存儲(chǔ)結(jié)構(gòu)示意圖如下： 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)示意圖如下：5設(shè)一個(gè)數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)如圖1.9所示，請(qǐng)寫(xiě)出它的二元組定義形式。圖1.9 第5題的邏輯結(jié)構(gòu)圖參考答案: 它的二元組定義形式為B=（D，R），其中D=k1,k2,k3,k4,k5,k6,k7,k8,k9，R=, 。6設(shè)有函數(shù)f (n)=3n2-n+4，請(qǐng)證明f (n)=O(n2)。習(xí)題二參考答案一、選擇題1. 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的最大優(yōu)點(diǎn)是（ ）。A.便于隨機(jī)存取B.存儲(chǔ)密度高 C.無(wú)需預(yù)分配空間D.便于進(jìn)行插入和刪除操作 2. 假設(shè)在順序表a0,a1,an1中，每一個(gè)數(shù)據(jù)元素所占的存儲(chǔ)單元的數(shù)目為4，且第0個(gè)數(shù)據(jù)元素的存儲(chǔ)地址為100，則第7個(gè)數(shù)據(jù)元素的存儲(chǔ)地址是（）。A. 106 B. 107 C.124 D.1283. 在線性表中若經(jīng)常要存取第i個(gè)數(shù)據(jù)元素及其前趨，則宜采用（ ）存儲(chǔ)方式。A.順序表B. 帶頭結(jié)點(diǎn)的單鏈表C.不帶頭結(jié)點(diǎn)的單鏈表D. 循環(huán)單鏈表4. 在鏈表中若經(jīng)常要?jiǎng)h除表中第一個(gè)結(jié)點(diǎn)或在最后一個(gè)結(jié)點(diǎn)之后插入一個(gè)新結(jié)點(diǎn)，則宜采用（ ）存儲(chǔ)方式。A. 順序表B. 用頭指針標(biāo)識(shí)的循環(huán)單鏈表C. 用尾指針標(biāo)識(shí)的循環(huán)單鏈表D. 雙向鏈表5. 在一個(gè)單鏈表中的p和q兩個(gè)結(jié)點(diǎn)之間插入一個(gè)新結(jié)點(diǎn)，假設(shè)新結(jié)點(diǎn)為S,則修改鏈的java語(yǔ)句序列是（ ）。A. s.setNext(p); q.setNext(s); B. p.setNext(s.getNext(); s.setNext(p);C. q.setNext(s.getNext(); s.setNext(p); D. p.setNext(s); s.setNext(q);6. 在一個(gè)含有n個(gè)結(jié)點(diǎn)的有序單鏈表中插入一個(gè)新結(jié)點(diǎn)，使單鏈表仍然保持有序的算法的時(shí)間復(fù)雜度是（ ）。A. O(1) B. O(log2n) C. O(n) D. O(n2)7. 要將一個(gè)順序表a0,a1,an-1中第i個(gè)數(shù)據(jù)元素ai(0in-1)刪除，需要移動(dòng)（ ）個(gè)數(shù)據(jù)元素。A. i B. n-i-1 C. n-i D. n-i+18. 在帶頭結(jié)點(diǎn)的雙向循環(huán)鏈表中的p結(jié)點(diǎn)之后插入一個(gè)新結(jié)點(diǎn)s，其修改鏈的java語(yǔ)句序列是（ ）。A. p.setNext(s); s.setPrior(p); p.getNext().setPrior(s); s.setNext(p.getPrior();B. p.setNext(s); p.getNext().setPrior(s); s.setPrior(p); s.setNext(p.getNext();C. s.setPrior(p); s.setNext(p.getNext(); p.setNext(s); p.getNext().setPrior(s);D. s.setNext(p.getNext(); s.setPrior(p); p.getNext().setPrior(s); p.setNext(s);9. 順序表的存儲(chǔ)密度是（ ），而單鏈表的存儲(chǔ)密度是（ ）。A小于1 B. 等于1 C. 大于1 D. 不能確定10. 對(duì)于圖2.29所示的單鏈表，下列表達(dá)式值為真的是（ ）。ABCE headDP1P2圖2.29 單鏈表head的存儲(chǔ)結(jié)構(gòu)圖A. head.getNext().getData()=C B. head.getData()=BC. P1.getData()=D D. P2.getNext()=null二、填空題1. 線性表是由n（n0）個(gè)數(shù)據(jù)元素所構(gòu)成的有限序列 ，其中n為數(shù)據(jù)元素的個(gè)數(shù)，稱為線性表的長(zhǎng)度 ，n=0的線性表稱為空表 。2. 線性表中有且僅有一個(gè)開(kāi)始結(jié)點(diǎn)和終端結(jié)點(diǎn)，除開(kāi)始結(jié)點(diǎn)和終端結(jié)點(diǎn)之外，其它每一個(gè)數(shù)據(jù)元素有且僅有一個(gè)前驅(qū) ，有且僅有一個(gè) 后繼。3. 線性表通常采用順序存儲(chǔ) 和鏈?zhǔn)酱鎯?chǔ) 兩種存儲(chǔ)結(jié)構(gòu)。若線性表的長(zhǎng)度確定或變化不大，則適合采用順序 存儲(chǔ)結(jié)構(gòu)進(jìn)行存儲(chǔ)。4. 在順序表a0,a1,an-1中的第i(0in-1)個(gè)位置之前插入一個(gè)新的數(shù)據(jù)元素，會(huì)引起n-i 個(gè)數(shù)據(jù)元素的移動(dòng)操作。5. 在線性表的單鏈表存儲(chǔ)結(jié)構(gòu)中，每一個(gè)結(jié)點(diǎn)有兩個(gè)域，一個(gè)是數(shù)據(jù)域，用于存儲(chǔ)數(shù)據(jù)元素值本身，另一個(gè)是指針域 ，用于存儲(chǔ)后繼結(jié)點(diǎn)的地址。6. 在線性表的順序存儲(chǔ)結(jié)構(gòu)中可實(shí)現(xiàn)快速的隨機(jī)存取，而在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中則只能進(jìn)行順序 存取。7. 順序表中邏輯上相鄰的數(shù)據(jù)元素，其物理位置一定 相鄰，而在單鏈表中邏輯上相鄰的數(shù)據(jù)元素，其物理位置不一定 相鄰。8. 在僅設(shè)置了尾指針的循環(huán)鏈表中，訪問(wèn)第一個(gè)結(jié)點(diǎn)的時(shí)間復(fù)雜度是o（1） 。9. 在含有n個(gè)結(jié)點(diǎn)的單鏈表中，若要?jiǎng)h除一個(gè)指定的結(jié)點(diǎn)p，則首先必須找到指針結(jié)點(diǎn)的前驅(qū) ，其時(shí)間復(fù)雜度為o（n） 。10. 若將單鏈表中的最后一個(gè)結(jié)點(diǎn)的指針域值改為單鏈表中頭結(jié)點(diǎn)的地址值，則這個(gè)鏈表就構(gòu)成了循環(huán)單鏈表 。一、單項(xiàng)選擇題1. 下面描述錯(cuò)誤的是 （ ）A HTML文件由開(kāi)頭，標(biāo)記結(jié)束。B 文檔頭信息包含在與之間。C 在和之間可以包含和等信息。D 文檔體包含在和標(biāo)記之間2. 是標(biāo)題標(biāo)記。 （ ） A標(biāo)記 B標(biāo)記 C標(biāo)記 D3. 超級(jí)鏈接是互聯(lián)網(wǎng)的靈魂，下面哪個(gè)是正確的鏈接標(biāo)記 （ ）A新浪網(wǎng) B新浪網(wǎng) C http:/wwwsinacom Dhttp:/wwwsinacom4. 下面不屬于標(biāo)記中的 type 屬性取值的是 （ ）Apassword Btext Csubmit Dtextarea 5. 標(biāo)記中的 type 屬性為 時(shí)表示單選按鈕 （ ）Apassword Bsubmit Cradio Dtext 6. 在html標(biāo)記中，哪個(gè)標(biāo)記用于設(shè)置當(dāng)前頁(yè)面的標(biāo)題。 （ ）A. head B. name C. title D. html7. 下列標(biāo)簽中沒(méi)有自動(dòng)換行作用的是 （ ）A. a B h1 C. p D li8. HTML語(yǔ)言中，表格標(biāo)記符是 （ ）A B.C. D.9. CSS是 的縮寫(xiě)。 （ ）A. Computer Style Sheets B.Cascading Style Sheets C. Creative Style Sheets D.Colorful Style Sheets10. 能在瀏覽器的地址欄中看到提交數(shù)據(jù)的表單提交方式是 （ B ）Asubmit Bget Cpost Dout11. CSS 選擇器通過(guò)被規(guī)則指定的標(biāo)記，對(duì)文檔中使用該標(biāo)記的內(nèi)容進(jìn)行統(tǒng)一的 外觀控制。下面那些不是 CSS 選擇器。 （ ）A 標(biāo)簽選擇器 BClass選擇器 CID 選擇器 D名稱選擇器 12. 引用外部樣式表的格式是（）。ABCmystyle.cssD13. 引用外部樣式表的元素應(yīng)該放在（）。AHTML文檔的開(kāi)始的位置BHTML文檔的結(jié)束的位置C在head元素中D在body元素中14. 下列哪一項(xiàng)是css正確的語(yǔ)法構(gòu)成Abody:color=black Bbody;color:black Cbody color: black; Dbody:color=black(body15. 下列哪種方式是用類(lèi)選擇符定義樣式Apcolor:red;B.onecolor:red;C#twocolor:red;Dp,h1color:red;16. 如果要在不同的網(wǎng)頁(yè)中應(yīng)用相同的樣式表定義，應(yīng)該（）。A直接在HTML的元素中定義樣式表B在HTML的標(biāo)簽中定義樣式表C通過(guò)一個(gè)外部樣式表文件定義樣式表D以上都可以17. 在網(wǎng)頁(yè)元素內(nèi)部定義樣式表時(shí)使用的屬性名是（）。AstyleBclassCstylesDfont18. 超級(jí)鏈接的功能是從一個(gè)頁(yè)面鏈接到另一個(gè)頁(yè)面，屬性 用來(lái)定義具體鏈接到那一頁(yè)。（ ） Aanchor B src Chref DAddress19. 在HTML中，表格的基本標(biāo)記是 。 （ ） A table B border Ctr D td20. 在HTML中，圖片的基本標(biāo)記是 。 （ ） A img B image Cpicture D pic21. 當(dāng)表單各項(xiàng)添寫(xiě)完畢，鼠標(biāo)單擊提交按鈕時(shí)可以觸發(fā)_事件。 （ ）A. onenter B. onsubmit C. onmouseDrag D. onmouseOver22. 下面可以作為客戶端腳本語(yǔ)言的是 。 （ ） A. java B. c# C. PHP D. JavaScript23. JavaScript是弱類(lèi)型語(yǔ)言，變量定義時(shí)使用下列哪個(gè)關(guān)鍵字。 （ ）A. define B. var C. variant D. 以上都不是24. JavaScript中函數(shù)的定義使用下列哪個(gè)關(guān)鍵字。 （ ）A. method B. var C. function D. 以上都不是25. JavaScript中，window的哪個(gè)方法可以彈出一個(gè)警告消息框。 （ ）A. alert B. confirm C. prompt D. write26. JavaScript中，當(dāng)元素獲得焦點(diǎn)時(shí)激發(fā)的事件是 。 （ ）A. load B. click C. mouseover D. focus習(xí)題三參考答案?jìng)渥? 紅色字體標(biāo)明的是與書(shū)本內(nèi)容有改動(dòng)的內(nèi)容。一、選擇題9. 在棧中存取數(shù)據(jù)的原則是（ ）。A 先進(jìn)先出 B. 先進(jìn)后出 C. 后進(jìn)后出 D. 沒(méi)有限制2若將整數(shù)1、2、3、4依次進(jìn)棧，則不可能得到的出棧序列是（ ）。A1234 B. 1324 C. 4321 D. 14233在鏈棧中，進(jìn)行出棧操作時(shí)（ ）。A需要判斷棧是否滿 B. 需要判斷棧是否為空C. 需要判斷棧元素的類(lèi)型 D. 無(wú)需對(duì)棧作任何差別4在順序棧中，若棧頂指針top指向棧頂元素的下一個(gè)存儲(chǔ)單元，且順序棧的最大容量是maxSize，則順序棧的判空條件是（ ）。 Atop=0 B.top=-1 C. top=maxSize D.top=maxSize-15在順序棧中，若棧頂指針top指向棧頂元素的下一個(gè)存儲(chǔ)單元，且順序棧的最大容量是maxSize。則順序棧的判滿的條件是（ ）。 Atop=0 B.top=-1 C. top=maxSize D.top=maxSize-16在隊(duì)列中存取數(shù)據(jù)元素的原則是（ ）。A先進(jìn)先出 B. 先進(jìn)后出 C. 后進(jìn)先出 D. 沒(méi)有限制7在循環(huán)順序隊(duì)列中，假設(shè)以少用一個(gè)存儲(chǔ)單元的方法來(lái)區(qū)分隊(duì)列判滿和判空的條件，front和rear分別為隊(duì)首和隊(duì)尾指針，它們分別指向隊(duì)首元素和隊(duì)尾元素的下一個(gè)存儲(chǔ)單元，隊(duì)列的最大存儲(chǔ)容量為maxSize，則隊(duì)列的判空條件是（ ）。 Afront=rear B. front!=rearC. front=rear+1 D. front=(rear+1)% maxSize 8在循環(huán)順序隊(duì)列中，假設(shè)以少用一個(gè)存儲(chǔ)單元的方法來(lái)區(qū)分隊(duì)列判滿和判空的條件，front和rear分別為隊(duì)首和隊(duì)尾指針，它們分別指向隊(duì)首元素和隊(duì)尾元素的下一個(gè)存儲(chǔ)單元，隊(duì)列的最大存儲(chǔ)容量為maxSize，則隊(duì)列的判滿條件是（ ）。 Afront=rear B. front!=rearC. front=rear+1 D. front=(rear+1)% maxSize9. 在循環(huán)順序隊(duì)列中，假設(shè)以少用一個(gè)存儲(chǔ)單元的方法來(lái)區(qū)分隊(duì)列判滿和判空的條件，front和rear分別為隊(duì)首和隊(duì)尾指針，它們分別指向隊(duì)首元素和隊(duì)尾元素的下一個(gè)存儲(chǔ)單元，隊(duì)列的最大存儲(chǔ)容量為maxSize，則隊(duì)列的長(zhǎng)度是（ ）。 Arear-front B. rear-front+1C. (rear-front+maxSize)%maxSize D. (rear-front+1)%maxSize10.設(shè)長(zhǎng)度為n的鏈隊(duì)列采用單循環(huán)鏈表加以表示，若只設(shè)一個(gè)頭指針指向隊(duì)首元素，則入隊(duì)操作的時(shí)間復(fù)雜度為（ ）。 AO(1) BO(n) CO(log2n) DO(n2)二、填空題1. 棧是一種操作受限的特殊線性表，其特殊性體現(xiàn)在其插入和刪除操作都限制在表尾進(jìn)行。允許插入和刪除操作的一端稱為棧頂 ，而另一端稱為棧底 。棧具有 先進(jìn)后出的特點(diǎn)。2. 棧也有兩種存儲(chǔ)結(jié)構(gòu)，一種是順序存儲(chǔ) ，另一種是鏈?zhǔn)酱鎯?chǔ) ；以這兩種存儲(chǔ)結(jié)構(gòu)存儲(chǔ)的棧分別稱為順序棧 和鏈棧。3. 在順序棧中，假設(shè)棧頂指針top是指向棧頂元素的下一個(gè)存儲(chǔ)單元，則順序棧判空的條件是 top=0 ; 棧頂元素的訪問(wèn)形式是stacktop-1 ;4. 在不帶表頭結(jié)點(diǎn)的鏈棧中，若棧頂指針top直接指向棧頂元素，則將一個(gè)新結(jié)點(diǎn)p入棧時(shí)修改鏈的兩個(gè)對(duì)應(yīng)語(yǔ)句為top.next=p ；top=p; 。5. 在不帶表頭結(jié)點(diǎn)的鏈棧中，若棧頂指針top直接指向棧頂元素，則棧頂元素出棧時(shí)的修改鏈的對(duì)應(yīng)語(yǔ)句為top=top.next 。6.7. 隊(duì)列也是一種操作受限的線性表，它與棧不同的是，隊(duì)列中所有的插入操作均限制在表的一端進(jìn)行，而所有的刪除操作都限制在表的另一端進(jìn)行，允許插入的一端稱為 對(duì)首，允許刪除的一端稱為隊(duì)尾 。隊(duì)列具有先進(jìn)先出 的特點(diǎn)。8. 由于隊(duì)列的刪除和插入操作分別在隊(duì)首和隊(duì)尾進(jìn)行，因此，在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)描述中分別需要設(shè)置兩個(gè)指針?lè)謩e指向?qū)κ捉Y(jié)點(diǎn) 和隊(duì)尾結(jié)點(diǎn) ，這兩個(gè)指針又分別稱為隊(duì)首指針和隊(duì)尾指針 。8. 循環(huán)順序隊(duì)列是將順序隊(duì)列的存儲(chǔ)區(qū)域看成是一個(gè)首尾相連的環(huán)，首尾相連的狀態(tài)是通過(guò)數(shù)學(xué)上的求模 運(yùn)算來(lái)實(shí)現(xiàn)的。9. 在循環(huán)順序隊(duì)列中，若規(guī)定當(dāng)front=rear時(shí)，循環(huán)隊(duì)列為空；當(dāng)front=(rear+1)%maxSize時(shí)，循環(huán)隊(duì)列為滿，則入隊(duì)操作時(shí)的隊(duì)尾指針變化的相應(yīng)語(yǔ)句是 rear=(rear+1)% maxSize ；出隊(duì)操作時(shí)的隊(duì)首指針變化的相應(yīng)語(yǔ)句是 front=(front+1)%maxSize 。無(wú)論是順序棧還是順序隊(duì)列，插入元素時(shí)必須先進(jìn)行驗(yàn)滿 判斷，刪除元素時(shí)必須先進(jìn)行驗(yàn)空判斷；而鏈?；蜴滉?duì)列中，插入元素?zé)o需進(jìn)行?；蜿?duì)列是否為滿的判斷，只要在刪除元素時(shí)先進(jìn)行驗(yàn)空 判斷。第3章1. 指令標(biāo)識(shí)通常以“”標(biāo)記結(jié)束。 （ 對(duì) ）2. JavaScript代碼的執(zhí)行必須要有Tomcat服務(wù)器支持。 （ 錯(cuò) ）3. Servlet是服務(wù)器端技術(shù)。 （ 對(duì) ）4. out 對(duì)象可以向客戶端的瀏覽器輸出數(shù)據(jù)，與表達(dá)式的作用基本相同。 （ 對(duì) ）5. JSP腳本中的表達(dá)式末尾必須用分號(hào);結(jié)束。 （ 錯(cuò) ）6. 如果頁(yè)面處理了exception對(duì)象，那么該頁(yè)面的isErrorPage屬性值為true。 （ ）二 單選題紅色為正確答案1. JSP源文件的后綴名是（ ）。 Ajava Bjsp Cclass Dhtml2. 能夠用來(lái)聲明全局變量的是（ ）。 A B C D 3. 能夠在網(wǎng)頁(yè)源代碼顯示的注釋是（ ）。AJSP注釋 BHTML注釋CJSP注釋和HTML注釋 DJAVA注釋4. （ ）可在JSP頁(yè)面出現(xiàn)該指令的位置處，靜態(tài)插入一個(gè)文件。Apage指令標(biāo)簽 Bpage指令的import屬性Cinclude指令標(biāo)簽 Dinclude動(dòng)作標(biāo)簽5. JSP程序段的基本語(yǔ)法是（ ）。AVBScript語(yǔ)言語(yǔ)法 BJavaScript語(yǔ)言語(yǔ)法CJava語(yǔ)法語(yǔ)言 DC語(yǔ)言語(yǔ)法6. JSP的英文單詞全稱是 。 A. Java Servlet B. Java Server Pages C. JavaScript D.Java Bean7. 下列哪一種不是JSP頁(yè)面的組成元素.（ D ）。AJSP標(biāo)簽，如指令標(biāo)簽 B普通的HTML標(biāo)記符CJava表達(dá)式 DC語(yǔ)言程序8. Page 指令用于定義 JSP 文件中的全局屬性，下列關(guān)于該指令用法的描述不正確的是：（D ） A. 作用于整個(gè) JSP 頁(yè)面。 B. 可以在一個(gè)頁(yè)面中使用多個(gè)指令。 C. 為增強(qiáng)程序的可讀性，建議將指令放在 JSP 文件的開(kāi)頭，但不是必須的。 D. 指令中的屬性只能出現(xiàn)一次。 9. 不是 JSP 運(yùn)行必須的是（D. A.操作系統(tǒng) B.JavaJDK C.支持 Jsp 的 Web 服務(wù)器 D.數(shù)據(jù)庫(kù) 10. 在JSP中如果要導(dǎo)入 java.io.* 包，應(yīng)該使用page指令的 屬性 。 （ ）A. language B. session C. import D. info11. 可以在以下哪個(gè)（ ）標(biāo)記之間插入 Java 程序片？（A. A. B. C. D. 12. JSP 的 Page 編譯指令的屬性 Language 的默認(rèn)值是：（A. A.Java B.C C.C D.SQL 13. 可以在以下哪個(gè)（ ）標(biāo)記之間插入變量與方法聲明？（B. A. B. C. D.14. 能在瀏覽器的地址欄中看到提交數(shù)據(jù)的表單提交方式是（ B ） A.submit B.get C.post D.out 15. 給定JSP程序源碼如下： 以下（B.語(yǔ)句可以在下劃線處插入，并且運(yùn)行后輸出結(jié)果是：1。 A: B: C: D:三 簡(jiǎn)答題1. 請(qǐng)簡(jiǎn)述JSP運(yùn)行原理。2. 請(qǐng)簡(jiǎn)述include指令與include動(dòng)作之間的區(qū)別。3. JSP中可以有哪些種注釋？請(qǐng)寫(xiě)出具體格式。4. 請(qǐng)列出三個(gè)JSP標(biāo)準(zhǔn)動(dòng)作，并說(shuō)明這些動(dòng)作完成的功能.第四章選擇題1. 以下對(duì)象中的（ ）不是JSP的內(nèi)置對(duì)象。Arequest BsessionCapplication Dbean2. 在JSP中，內(nèi)置對(duì)象（ ）封裝了用戶提交的信息，使用該對(duì)象可以獲取用戶提交的信息。Asession BrequestCresponse Dout3. request對(duì)象可以使用（ ）方法獲取表單中某輸入框提交的信息。AgetParameter(String s) BgetValue(String s)CgetParameterNames(String s) DgetParameterValue(String s)4. JSP的內(nèi)置對(duì)象中（ ）對(duì)象可對(duì)客戶的請(qǐng)求作出動(dòng)態(tài)響應(yīng)，向客戶端發(fā)送數(shù)據(jù)。Aresponse BrequestCapplication Dout5. 以下方法，哪個(gè)可使session無(wú)效？（ ）。Asession.removeAttribute(String key)Bsession.invalidate()Csession.setAttribute(String key)Dsession.getAttribute(String key)6. application對(duì)象能在（ ）間共享。A某個(gè)訪問(wèn)者所訪問(wèn)的當(dāng)前頁(yè)面B某個(gè)訪問(wèn)者所訪問(wèn)的網(wǎng)站的各個(gè)頁(yè)面之間C該服務(wù)器上的所有的訪問(wèn)者的所有jsp頁(yè)面D該服務(wù)器上的所有的訪問(wèn)者的所有jsp頁(yè)面和Java程序7. request.getRemoteAddr()方法的作用是：（ ）。A獲取客戶提交的信息 B獲取客戶的IPC獲取客戶機(jī)的名稱 D獲取服務(wù)器的IP8. 下面不屬于 JSP 內(nèi)置對(duì)象的是（D） A）out 對(duì)象 B）respone 對(duì)象 C）application 對(duì)象 D）page 對(duì)象 9. 調(diào)用 getCreationTime（）可以獲取 session 對(duì)象創(chuàng)建的時(shí)間，該時(shí)間的單位 是（C）。 A）秒 B）分秒 C）毫秒 D）微秒 10. 可以利用 JSP 動(dòng)態(tài)改變客戶端的響應(yīng)，使用的語(yǔ)法是（A）A）response.setHeader() B）response.outHeader()C）response.writeHeader()D）response.handlerHeader()11. 頁(yè)面程序片中可以使用下列哪個(gè)方法將 strNumx=request.getParamter(“ix”) JSP 得到的數(shù)據(jù)類(lèi)型轉(zhuǎn)換為 Double 類(lèi)型（ ）A）Double.parseString(strNumx) B） Double.parseDouble(strNumx) C) Double.parseInteger(strNumx) D）Double.parseFloat(strNumx)簡(jiǎn)答題1. JSP的內(nèi)置對(duì)象方法、作用。2. 運(yùn)行session1.jsp，寫(xiě)出其運(yùn)行結(jié)果！s1.jsps2.jsp 您的信息為：用戶名：密碼：3. 用戶在reg.html中輸入：用戶名Tom；密碼123；選擇愛(ài)好為游泳、閱讀，請(qǐng)寫(xiě)出程序的運(yùn)行結(jié)果。reg.html user:psw:愛(ài)好：游泳音樂(lè)閱讀register.jsp user:psw:hobby：%String h=request.getParameterValues(h); for(int i=0;i 習(xí)題五參考答案?jìng)渥? 紅色字體標(biāo)明的是與書(shū)本內(nèi)容有改動(dòng)的內(nèi)容 一、選擇題1對(duì)一棵樹(shù)進(jìn)行后根遍歷操作與對(duì)這棵樹(shù)所對(duì)應(yīng)的二叉樹(shù)進(jìn)行（ ）遍歷操作相同。B 先根 B. 中根 C. 后根 D. 層次2在哈夫曼樹(shù)中，任何一個(gè)結(jié)點(diǎn)它的度都是（ ）。C 0或1 B. 1或2 C. 0或2 D. 0或1或23對(duì)一棵深度為h的二叉樹(shù)，其結(jié)點(diǎn)的個(gè)數(shù)最多為（ ）。A 2h B. 2h-1 C. 2h-1 D. 2h-14一棵非空二叉樹(shù)的先根遍歷與中根遍歷正好相同，則該二叉樹(shù)滿足（ ）A 所有結(jié)點(diǎn)無(wú)左孩子 B. 所有結(jié)點(diǎn)無(wú)右孩子 C. 只有一個(gè)根結(jié)點(diǎn) D. 任意一棵二叉樹(shù)5一棵非空二叉樹(shù)的先根遍歷與中根遍歷正好相反，則該二叉樹(shù)滿足（ ）B 所有結(jié)點(diǎn)無(wú)左孩子 B. 所有結(jié)點(diǎn)無(wú)右孩子 C. 只有一個(gè)根結(jié)點(diǎn) D. 任意一棵二叉樹(shù)6假設(shè)一棵二叉樹(shù)中度為1的結(jié)點(diǎn)個(gè)數(shù)為5，度為2的結(jié)點(diǎn)個(gè)數(shù)為3，則這棵二叉樹(shù)的葉結(jié)點(diǎn)的個(gè)數(shù)是（ ）A2 B. 3 C. 4 D. 57若某棵二叉樹(shù)的先根遍歷序列為ABCDEF，中根遍歷序列為CBDAEF，則這棵二叉樹(shù)的后根遍歷序列為（ ）。AFEDCBA B. CDBFEA C. CDBEFA D. DCBEFA8若某棵二叉樹(shù)的后根遍歷序列為DBEFCA，中根遍歷序列為DBAECF，則這棵二叉樹(shù)的先根遍歷序列為（ ）。AABCDEF B. ABDCEF C. ABCDFE D. ABDECF9根據(jù)以權(quán)值為2，5，7，9，12構(gòu)造的哈夫曼樹(shù)所構(gòu)造的哈夫曼編碼中最大的長(zhǎng)度為（ ）A2 B. 3 C. 4 D. 510在有n個(gè)結(jié)點(diǎn)的二叉樹(shù)的二叉鏈表存儲(chǔ)結(jié)構(gòu)中有（ ）個(gè)空的指針域。An-1 B. n C. n+1 D. 0二、填空題1. 在一棵度為m的樹(shù)中，若度為1的結(jié)點(diǎn)有n1個(gè)，度為2的結(jié)點(diǎn)有n2個(gè)，度為m的結(jié)點(diǎn)有nm個(gè)，則這棵樹(shù)中的葉結(jié)點(diǎn)的個(gè)數(shù)為 。2. 一棵具有n個(gè)結(jié)點(diǎn)的二叉樹(shù)，其深度最多為 ，最少為 。3. 一棵具有100個(gè)結(jié)點(diǎn)的完全二叉樹(shù)，其葉結(jié)點(diǎn)的個(gè)數(shù)為 。4. 以5，9，12，13，20，30為葉結(jié)點(diǎn)的權(quán)值所構(gòu)造的哈夫曼樹(shù)的帶權(quán)路徑長(zhǎng)度是 。5. 有m個(gè)葉結(jié)點(diǎn)的哈夫曼樹(shù)中，結(jié)點(diǎn)的總數(shù)是 。6. 若一棵完全二叉樹(shù)的第4層(根結(jié)點(diǎn)在第0層)有7個(gè)結(jié)點(diǎn)，則這棵完全二叉樹(shù)的結(jié)點(diǎn)總數(shù)是 。7. 在深度為k的完全二叉樹(shù)中至少有個(gè)結(jié)點(diǎn)，至多有 個(gè)結(jié)點(diǎn)。8. 對(duì)一棵樹(shù)轉(zhuǎn)換成的二叉樹(shù)進(jìn)行先根遍歷所得的遍歷序列為ABCDEFGH,則對(duì)這棵樹(shù)進(jìn)行先根遍歷所得的遍歷序列為 。9. 二叉樹(shù)常用的存儲(chǔ)結(jié)構(gòu)是 ，樹(shù)常用的存儲(chǔ)結(jié)構(gòu)是 。10. 對(duì)森林進(jìn)行后根遍歷操作等同于從左到右對(duì)森林中的每一棵樹(shù)進(jìn)行 遍歷操作，并且對(duì)森林的后根遍歷序列與對(duì)森林所對(duì)應(yīng)的二叉樹(shù)的 遍歷序列相同。習(xí)題七 參考答案一、選擇題1內(nèi)部排序算法的穩(wěn)定性是指( D )。A該排序算法不允許有相同的關(guān)鍵字記錄B該排序算法允許有相同的關(guān)鍵字記錄C平均時(shí)間為0（n log n）的排序方法D以上都不對(duì)2下面給出的四種排序算法中，( B )是不穩(wěn)定的排序。 A插入排序 B堆排序 C二路歸并排序 D冒泡排序3. 在下列排序算法中，哪一種算法的時(shí)間復(fù)雜度與初始排序序列無(wú)關(guān)（ D ）。 A直接插入排序 B冒泡排序 C快速排序 D直接選擇排序4關(guān)鍵字序列（8，9，10，4，5，6，20，1，2）只能是下列排序算法中( C )的兩趟排序后的結(jié)果。A選擇排序 B.冒泡排序 C.插入排序 D.堆排序5下列排序方法中，( D )所需的輔助空間最大。A選擇排序 B希爾排序 C快速排序 D歸并排序6一組記錄的關(guān)鍵字為（46，79，56，38，40，84），則利用快速排序的方法，以第一個(gè)記錄為支點(diǎn)得到的一次劃分結(jié)果為（ C ）。 A(38,40,46,56,79,84) B(40,38,46,79,56,84)C(40,38,46,56,79,84) D(40,38,46,84,