華東理工大學(xué)數(shù)據(jù)結(jié)構(gòu)（本）期末復(fù)習(xí)題及參考答案

數(shù)據(jù)結(jié)構(gòu)(本)(網(wǎng)教)202301-模擬卷注：找到所考試題直接看該試題所有題目和答案即可。查找按鍵：Ctrl+F超越高度一、單選題(共10題，20分)1、設(shè)循環(huán)隊(duì)列中數(shù)組的下標(biāo)范圍是「n,其頭尾指針?lè)謩e尾f、r,則隊(duì)列中元素的個(gè)數(shù)為().A、r-fr-f+1(r-f+1)modn(r-f+n)modn正確答案：D2、以下哪一個(gè)不是隊(duì)列的基本運(yùn)算？A、從隊(duì)尾插入一個(gè)新元素B、從隊(duì)列中刪除第i個(gè)元素C、判斷一個(gè)隊(duì)列是否為空D、讀取隊(duì)頭元素的值正確答案：B3、有一個(gè)有序表{1,3,9,12,32,41,62,75,77,86,95,100},當(dāng)二分查找值為86的關(guān)鍵字時(shí)，需要比較的次數(shù)是()。A、2B、3C、4D、5正確答案：C4、棧S最多能容納4個(gè)元素?，F(xiàn)有6個(gè)元素按A、B、C、D、E、F的順序進(jìn)棧，問(wèn)下列哪一個(gè)序列是可能的出棧序列？E、D、C、B、A、FB、C、E、F、A、DC、B、E、D、A、FA、D、F、E、B、C正確答案：C5、n個(gè)頂點(diǎn)的無(wú)向連通圖至少有()條邊。n-lnn+1D、2n正確答案：A6、設(shè)有10000個(gè)無(wú)序元素,希望用較快速度挑選出其中前15個(gè)最大元素,采用()方法最好.A、直接插入排序B、堆排序C、快速排序D、歸并排序正確答案：B7、已知一棵二叉排序樹(shù)，通過(guò)()可以得到結(jié)點(diǎn)的有序序列。A、前序遍歷B、中序遍歷C、后序遍歷D、線索化正確答案：B8、S="A;/document/Mary.doc"，則“/”的字符定位的位置為().A、2B、3C、1211正確答案：B9、假設(shè)有60行70列的二維數(shù)組a[l-60,1-70]以列序?yàn)橹餍蝽樞虼鎯?chǔ),其基地址為10000,每個(gè)元素占2個(gè)存儲(chǔ)單元,那么第32行第58列的元素a[32,58]的存儲(chǔ)地址為()。(無(wú)第。行第0列元素)169021690414454D、答案A,B,C均不對(duì)正確答案：A10、具有36個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為()。A、5B、6C、7D、8正確答案：B二、填空題(共10題，10分)1、進(jìn)棧序列為a,b,c,則通過(guò)出棧和進(jìn)棧操作可能得到的a,b,c的不同的排列序列有一種。(1.0)正確答案:第1空:52、廣義表((a,b),c,d)的表頭是一，表尾是—o(1.0)正確答案：第1空：(a,b)|(c,cl)3、假設(shè)用循環(huán)單鏈表實(shí)現(xiàn)隊(duì)列,若隊(duì)列非空,且隊(duì)尾指針為R,則將新結(jié)點(diǎn)S加入隊(duì)列時(shí),需執(zhí)行下面語(yǔ)句:；；。(1.0)正確答案：第1空：S->next二R->next第2空：R->next=S第3空：R=S4、具有8個(gè)頂點(diǎn)的有向完全圖有條弧。(1.0)正確答案：第1空:565、判定一個(gè)棧ST(最多元素為m0)為空的條件是—為滿的條件是一。(1.0)正確答案：第1空：ST->top=0第2空：ST->top=mO6、若對(duì)線性表進(jìn)行的主要操作是按照下標(biāo)存取而不是插入和刪J除,則該線性表宜采用一存儲(chǔ)結(jié)構(gòu);如果需要頻繁的插入和剜除操作,則該線性表宜采用—存儲(chǔ)結(jié)構(gòu)。(1.0)止確答案：第1空:順序第2空:鏈?zhǔn)?、圖的廣度優(yōu)先遍歷類似于樹(shù)的一遍歷。（1.0）正確答案：第1空:層次8、一個(gè)有n個(gè)葉子結(jié)點(diǎn)的哈夫曼樹(shù)中,其結(jié)點(diǎn)總數(shù)為一o（1.0）正確答案：第1空:2nT9、一棵具有35個(gè)結(jié)點(diǎn)的完全二叉樹(shù)，它的深度為—o（1.0）正確答案：第1空:610、設(shè)目標(biāo)串T="cdbccadcdccbaa“，模式P=“cade”，則第次匹配成功。（1.0）正確答案：第1空:5三、判斷題（共10題，10分）1、鏈?zhǔn)酱鎯?chǔ)是一種隨機(jī)存取的數(shù)據(jù)結(jié)構(gòu)。（1.0）正確答案：錯(cuò)誤2、線性表的邏輯順序與存儲(chǔ)順序總是一致的。（1.0）正確答案：錯(cuò)誤3、拓?fù)渑判驎r(shí),總是在有向圖中選擇入度為0的頂點(diǎn)輸出。（1.0）正確答案：正確4、二叉樹(shù)中所有結(jié)點(diǎn)，如果不存在非空左子樹(shù)，則不存在非空右子樹(shù)。（1.0）正確答案：錯(cuò)誤5、用二叉鏈表法（link-rlink）存儲(chǔ)包含n個(gè)結(jié)點(diǎn)的二叉樹(shù),結(jié)點(diǎn)的2n個(gè)指針區(qū)域中有n+1個(gè)為空指針。（1.0）正確答案：正確6、平衡二叉排序樹(shù)具有的特點(diǎn)是左子樹(shù)與右子樹(shù)的高度差的絕對(duì)值不超過(guò)1。（1.0）正確答案：正確7、圖的深度優(yōu)先遍歷類似于樹(shù)的層次遍歷。（1.0）正確答案：錯(cuò)誤8、在一個(gè)圖中，所有頂點(diǎn)的度數(shù)之和等于圖的邊數(shù)的2倍。（1.0）正確答案：正確9、棧和隊(duì)列是一種非線性數(shù)據(jù)結(jié)構(gòu)。（1.0）正確答案：錯(cuò)誤10、順序存儲(chǔ)結(jié)構(gòu)只能用來(lái)存放線性結(jié)構(gòu);鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)只能用來(lái)存放非線性結(jié)構(gòu)。（1.0）正確答案：錯(cuò)誤四、簡(jiǎn)答題（共2題，10分）1、順序隊(duì)列的“假溢出”是怎樣產(chǎn)生的?如何解決？（5.0）正確答案：一般的一維數(shù)組隊(duì)列的尾指針已經(jīng)到了數(shù)組的上界，不能再有入隊(duì)操作，但其實(shí)數(shù)組中還有空位置，這就叫“假溢出”。采用循環(huán)隊(duì)列是解決假溢出的途徑。另外，解決循環(huán)隊(duì)滿與隊(duì)空的辦法是浪費(fèi)一個(gè)元素空間，用于區(qū)別隊(duì)滿還是隊(duì)空。判斷循環(huán)隊(duì)列隊(duì)空標(biāo)志是：front二rear隊(duì)滿標(biāo)志是：front：（rear+l）%N,N為數(shù)組的長(zhǎng)度。2、寫出下列程序段的輸出結(jié)果（隊(duì)列中的元素類型QElemType為char）。voidmain()QueueQ;InitQueue(Q);Charx=，e，;y=，c，;EnQueue(Q,'h');EnQueue(Q,'r');EnQueue(Q,y);DeQueue(Q,x);EnQueue(Q,x);DeQueue(Q,x);EnQueue(Q,'a');While(!QueueEmpty(Q)){DeQueue(Q,y);printf(y);;Printf(x);該程序段的功能是(5.0).正確答案：char五、算法設(shè)計(jì)題(共2題，20分)1、把單鏈表A和B合并為C,A和B的元素間隔排列,且使用原存儲(chǔ)空間。(10.0)正確答案：voidmerge(LinklistA;LinklistB){p=A->next;q=B->next;C=A;while(p&q){s=p->next;p->next=q;//將B的元素插入if(s){t=q->next;q->next=s;〃如A非空，將A的元素插入p=s;q=t;}//while//merge)2、設(shè)計(jì)一遞歸算法，將以二叉鏈表為存儲(chǔ)結(jié)構(gòu)的二叉樹(shù)中的葉子結(jié)點(diǎn)全部刪除。二叉排序樹(shù)的存儲(chǔ)結(jié)構(gòu)如下：正確答案：voidcoutnode(BSTreeT)/*T為樹(shù)根指針{if(T){if(1->IchiId二NULL)&&(T->rchild==NULL)Free(T);/刪除度為0的結(jié)點(diǎn)；count_node(T->lchild);/遞歸刪除左子樹(shù)中度為0的結(jié)點(diǎn)數(shù)count_node(T->rchild);/遞歸刪除右子樹(shù)中度為0的結(jié)點(diǎn)數(shù))六、計(jì)算題(共3題，30分)1、已知某通訊系統(tǒng)使用8種字符，其概率分布分別為：0.06,0.28,0.07,0.08,0.14,0.22,0.03,0.12,試設(shè)計(jì)其哈夫曼編碼(10.0)正確答案：哈夫曼不唯一，其對(duì)應(yīng)編碼