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

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