計(jì)算機(jī)系《數(shù)據(jù)結(jié)構(gòu)》平時(shí)測(cè)試試題二

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

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

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