臨沂大學2015-2016學年度第一學期《數(shù)據(jù)結(jié)構(gòu)》平時測試試題一一、判斷題（共14題，每題1分，共14分）線性表的長度是線性表所占用的存儲空間的大小。（）順序存儲結(jié)構(gòu)只能用來存放線性結(jié)構(gòu)；鏈式存儲結(jié)構(gòu)只能用來存放非線性結(jié)構(gòu)。（）線性表采用鏈表方式和順序表方式存儲，執(zhí)行插入和刪除運算的時間復雜度都是O（N），因而兩種存儲方式的插入、刪除運算所花費的時間相同。（）雙循環(huán)鏈表中，任一個結(jié)點的后繼指針均指向其邏輯后繼。（）在鏈隊列中，即便不設(shè)置尾指針也能進行入隊列操作。（）在順序表中取出第i個元素所花費的時間與i成正比。（）已知指針P指向鏈表L中某結(jié)點，執(zhí)行語句P=P->next不會刪除該鏈表中結(jié)點。（）在帶頭結(jié)點的單循環(huán)鏈表中，任一結(jié)點的后繼指針均不空。（）完全二叉樹中，若一個結(jié)點沒有左孩子，則它必是樹葉。（）二叉樹的先序遍歷序列中，任意一個結(jié)點均處在其孩子結(jié)點的前面。（）設(shè)與一棵樹T所對應(yīng)的二叉樹為BT，則與T中的葉子結(jié)點所對應(yīng)的BT中的結(jié)點也一定是葉子結(jié)點。（）當一棵具有n個葉子結(jié)點的二叉樹的WPL值為最小時，稱其樹為Huffman樹，且其二叉樹的形狀必是唯一的。（）二叉樹的前序遍歷并不能唯一確定這棵樹，是因為我們不知道該樹的根結(jié)點是哪一個。（）對于有n個結(jié)點的二叉樹，其高度為log2n。（）二、選擇題（共40題，每題1分，共40分）通常從正確性、易讀性、健壯性、高效性等四個方面評價算法包括程序）的質(zhì)量。以下解釋錯誤的是（）A、正確性算法應(yīng)能正確地實現(xiàn)預(yù)定的功能（即處理要求）B、易讀性算法應(yīng)易于閱讀和理解以便于調(diào)試修改和擴充C、健壯性當環(huán)境發(fā)生變化時，算法能適當?shù)刈龀龇磻?yīng)或進行處理，不會產(chǎn)生不需要的運行結(jié)果D、高效性即達到所需要的時間性能數(shù)據(jù)的存儲結(jié)構(gòu)是指（）A、數(shù)據(jù)所占的存儲空間量C數(shù)據(jù)的存儲結(jié)構(gòu)是指（）A、數(shù)據(jù)所占的存儲空間量C、數(shù)據(jù)在計算機中的順序存儲方式下列屬于線性數(shù)據(jù)結(jié)構(gòu)的是（）A.隊列B.樹C.圖線性表是具有n個（）的有限序列B、數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機中的表示D、存儲在外存中的數(shù)據(jù)D.不確定A.表元素B.字符C.數(shù)據(jù)元素D.數(shù)據(jù)項對于順序表的優(yōu)缺點，以下說法錯誤的是（）A、無需為表示結(jié)點間的邏輯關(guān)系而增加額外的存儲空間B、可以方便地隨機存取表中的任一結(jié)點。、插入和刪除運算較方便D、容易造成一部分空間長期閑置而得不到充分利用對順序表上的插入、刪除算法的時間復雜性分析來說，通常以（）為標準操作A、結(jié)點移動B、條件判斷C、算術(shù)表達式D、賦值語句若線性表最常用的操作是存取第i個元素及其前驅(qū)的值，則采用（）存儲方式節(jié)省時間A.單鏈表8.雙向鏈表C.單循環(huán)鏈表D.順序表單鏈表的每個結(jié)點中包括一個指針link，它指向該結(jié)點的后繼結(jié)點。現(xiàn)要將指針q指向的新結(jié)點插入到指針p指向的結(jié)點之后，下面的操作序列中哪一個是正確的？（）A、p->link=q->link;q=p->link;B、p->link=q;q->link=p->link;C、q->link=p->link;p->link=q;D、q=p->link;p->link=q->link;在雙向循環(huán)鏈表中，在p指針所指向的結(jié)點前插入一個指針q所指向的新結(jié)點，其修改指針的操作是（）注:雙向鏈表的結(jié)點結(jié)構(gòu)為（prior,data,next）。供選擇的答案：p->prior=q；q->next=p；p->prior->next=q；q->prior=q；p->prior=q；p->prior->next=q；q->next=p；q->prior=p->prior；q->next=p；q->prior=p->prior；p->prior->next=q;p->prior=q;q->prior=p->prior；q->next=p；p->prior=q；p->prior->next=q；設(shè)有一順序棧S，元素s1,s2,s3,s4,s5,s6依次進棧，如果6個元素出棧的順序是s2,s3,s4,s6,s5,s1,則棧的容量至少應(yīng)該是（）

A、2B、3C、5D、6設(shè)有六列火車，編號為1,2,3,4,5,6順序開進一個棧式結(jié)構(gòu)的站臺，問下列輸出序列中，哪個是不可能出現(xiàn)的（）A.1,2,3,4,5,6B.6,5,4,3,2,1C.3,1,2,6,5,4D.3,2,1,6,5,4一個隊列的入隊列順序是1,2,3,4,則隊列的輸出系列是（）A、4,3,2,1B、1,2,3,4C、1,4,3,2D、3,2,4,1將一棵有100個結(jié)點的完全二叉樹從根結(jié)點這一層開始，每一層上從左到右依次對結(jié)點編號，根結(jié)點的編號為1，則編號為49的結(jié)點的左孩子編號為（）A,98B.99C.50D.48二叉樹的第I層上最多含有結(jié)點數(shù)為（）A.2IB.2I-1-1C.2I-1D.2I-1設(shè)深度為k的二叉樹上只有度為0和度為2的結(jié)點，則這類二叉樹上所含結(jié)點總數(shù)最少()A.k+1B.2kC.2k-1D.2k+1A、2B、3C、5D、6()A.k+1B.2kC.2k-1D.2k+1下列有關(guān)二叉樹的說法正確的是（）A.二叉樹的度為2B.一棵二叉樹度可以小于2二叉樹中至少有一個結(jié)點的度為2二叉樹中任一個結(jié)點的度都為2將含有83個結(jié)點的完全二叉樹從根結(jié)點開始編號，根為1號，按從上到下、從左到右順序結(jié)點編號，那么編號為41的雙親結(jié)點編號為（A.42B.40C.21D.20A.42B.40C.21D.20一棵具有n個結(jié)點的完全二叉樹的深度是（D.log2n-1A.Llog2nJ+1B.log2n+1C.Llog2nJ設(shè)樹T的度為4，其中度為1,2,3和4的結(jié)點個數(shù)分別為4,2,1,1則T中的葉子數(shù)為（）A.5B.6C.7D.8設(shè)有13個值，用它們組成一棵哈夫曼樹，則該哈夫曼樹共有（）個結(jié)點.D.log2n-1A.5B.6C.7D.8A.13B.12C.26D.25

21.樹的后根遍歷序列等同于該樹對應(yīng)的二叉樹的（）A.先序序列B.中序序列C.后序序列D.層次序列為解決計算機與打印機之間速度不匹配的問題，通常設(shè)置一個打印數(shù)據(jù)緩沖區(qū)，主機將要輸出的數(shù)據(jù)依次寫入該緩沖區(qū)，而打印機則依次從該緩沖區(qū)中取出數(shù)據(jù)。該緩沖區(qū)的邏輯結(jié)構(gòu)應(yīng)該是（）A.棧B,隊列C,樹D.圖設(shè)棧S和隊列Q的初始狀態(tài)均為空，元素abcdefg依次進入棧$。若每個元素出棧后立即進入隊列Q，且7個元素出隊的順序是bdcfeag，則棧S的容量至少是（）A.1B.2C.3D.4給定二叉樹圖所示。設(shè)N代表二叉樹的根，L代表根結(jié)點的左子樹，R代表根結(jié)點的右子樹。若遍歷后的結(jié)點序列為3,1，7,5,6,2,4，則其遍歷方式是（）A.LRNB.NRLC.RLND.RNL已知一棵完全二叉樹的第6層（設(shè)根為第1層）有8個葉結(jié)點，則完全二叉樹的結(jié)點個數(shù)最多是（）A.39B.52C.111D.119將森林轉(zhuǎn)換為對應(yīng)的二叉樹，若在二叉樹中，結(jié)點u是結(jié)點v的父結(jié)點的父結(jié)點，則在原來的森林中，u和v可能具有的關(guān)系是I?父子關(guān)系II,兄弟關(guān)系III.u的父結(jié)點與v的父結(jié)點是兄弟關(guān)系（）A,只有IIB.I和IIC.I和IIID.I、II和III27、若元素a,b,c,d,e,f依次進棧，允許進棧、退棧操作交替進行。但不允許連續(xù)三次進行退棧工作，則不可能得到的出棧序列是（）A：dcebfaB：cbdaefC：dbcaefD：afedcb28、某隊列允許在其兩端進行入隊操作，但僅允許在一端進行出隊操作，則不可能得到的順序是（）A：bacdeB：dbaceC：dbcaeD：ecbad29、下列線索二叉樹中（用虛線表示線索），符合后序線索樹定義的是（）30、在下列所示的平衡二叉樹中插入關(guān)鍵字48后得到一棵新平衡二叉樹，在新平衡二叉樹中，關(guān)鍵字37所在結(jié)點的左、右子結(jié)點中保存的關(guān)鍵字分別是（）A：13，48B：24，48C：24，53D：24，9031、在一棵度為4的樹T中，若有20個度為4的結(jié)點，10個度為3的結(jié)點，1個度為2的結(jié)點，10個度為1的結(jié)點，則樹T的葉節(jié)點個數(shù)是（）A：41B：82C：113D：12232、對n（n大于等于2）個權(quán)值均不相同的字符構(gòu)成哈夫曼樹，關(guān)于該樹的敘述中，錯誤的是（）A：該樹一定是一棵完全二叉樹B：樹中一定沒有度為1的結(jié)點C：樹中兩個權(quán)值最小的結(jié)點一定是兄弟結(jié)點D：樹中任一非葉結(jié)點的權(quán)值一定不小于下一任一結(jié)點的權(quán)值33、求整數(shù)n（n>0）階乘的算法如下，其時問復雜度是（）intfact（intn）{if（n<一1）return1;returnn*fact（n一1）;}A.O(logzn)B.0(n)C.(nlogzn)D.0(n2)已知操作符包括‘+’、'一’、'*’、'/’、‘(’和‘)’。將中綴表達式a+b-a*((c+d)/e-f)+g轉(zhuǎn)換為等價的后綴表達式ab+acd+e/f-**-g+時，用棧來存放暫時還不能確定運算次序的操作符，若棧初始時為空，則轉(zhuǎn)換過程中同時保存棧中的操作符的最大個數(shù)是()A.5B.7C.8D.11若一顆二叉樹的前序遍歷序列為a,e,b,d,c，后續(xù)遍歷序列為b,c,d,e,a，則根節(jié)點的孩子節(jié)點()A.只有eB,有e、bC.有e、cD.無法確定已知兩個長度分別為m和n的升序鏈表，若將它們合并為一個長度為m+n的降序鏈表，則最壞情況下的時間復雜度是A.O(n)B.0(m*n)C.0(min(m,n))D.0(max(m,n))一個棧的入棧序列為1,2,3,...,n，其出棧序列是P1,P2,P3,...,Pn,。若P2=3,則P3可能取值的個數(shù)是A.n-3B.n-2C.n-1D.無法確定若將關(guān)鍵字1，2,3,4,5,6,7依次插入到初始為空的平衡二叉樹T中，則T中平衡因子為0的分支結(jié)點的個數(shù)是A.0B.1C.2D.3已知三叉樹T中6個葉結(jié)點的權(quán)分別是2,3,4,5,6,7,T的帶權(quán)(外部)路徑長度最小是A.27B.46C.54D.56若X是后序線索二叉樹中的葉結(jié)點，且X存在左兄弟結(jié)點Y，則X的右線索指向的是A.X的父結(jié)點B.以Y為根的子樹的最左下結(jié)點C.X的左兄弟結(jié)點YD.以Y為根的子樹的最右下結(jié)點三、構(gòu)造題(共2題，每題10分，共20分)1.已知某二叉樹的先序遍歷序列為：ABDGCEFH；中序遍歷序列為：DGBAECHF。試畫出該二叉樹。(4分)（2）求二叉樹的后序遍歷序列（2分）（3）試畫出該二叉樹對應(yīng)的森林。（2分）2.已知字符A-F的出現(xiàn)頻率依次為2，3，5，6，11，9，（1）給出上述字符最優(yōu)編碼對應(yīng)的Huffman樹，并在葉子旁標注相應(yīng)字符；（3分）（2）計算上述Huffman樹的帶權(quán)路徑長度。（2分）四、算法設(shè)計（26分）帶頭結(jié)點的單鏈表，其長度存放在頭結(jié)點的數(shù)據(jù)域中，設(shè)計一算法求倒數(shù)第k個結(jié)點的值，并且刪除該結(jié)點。要求：（1）用