本文格式為Word版，下載可任意編輯——算法與數(shù)據(jù)結(jié)構(gòu)試卷B福州大學(xué)2023～2023學(xué)年其次學(xué)期考試B卷

課程名稱(chēng)算法與數(shù)據(jù)結(jié)構(gòu)考試日期2023.7.3考生姓名學(xué)號(hào)專(zhuān)業(yè)或類(lèi)別

題號(hào)題分得分考生本卷須知：1、本試卷共8頁(yè)，請(qǐng)查看試卷中是否有缺頁(yè)。2、考試終止后，考生不得將試卷、答題紙和草稿紙帶出考場(chǎng)。一30二13三10四47總分累分人簽名100一、單項(xiàng)選擇題(每題2分，共30分)得分評(píng)卷人1、在含n個(gè)元素的順序表中插入一個(gè)元素，設(shè)插入每個(gè)位置的概率一致，則平均需移動(dòng)元素的次數(shù)為（）。A、nB、n/2C、(n-1)/2D、(n+1)/22、設(shè)在帶哨兵結(jié)點(diǎn)的單鏈表中，鏈結(jié)點(diǎn)的指針域?yàn)閚ext。若要?jiǎng)h除指針p所指結(jié)點(diǎn)，設(shè)指針q指向其前驅(qū)結(jié)點(diǎn)，應(yīng)使用的語(yǔ)句為（）。A、deletep;q->next=p->next;B、deletep;p->next=q->next;C、q->next=p->next;deletep;D、p->next=q->next;deletep;3、以下關(guān)于靜態(tài)鏈表的說(shuō)法正確的是（）。A、靜態(tài)鏈表中的每個(gè)元素都有一個(gè)指針域，存放下一元素在內(nèi)存中的存儲(chǔ)地址B、一個(gè)數(shù)組空間只能存放一條靜態(tài)鏈表C、靜態(tài)鏈表的擴(kuò)展受到數(shù)組空間的局限D(zhuǎn)、在靜態(tài)鏈表中插入和刪除元素需要移動(dòng)數(shù)組空間中的元素4、若用數(shù)組stack實(shí)現(xiàn)棧，讓棧向數(shù)組下標(biāo)增大方向增長(zhǎng)，設(shè)置整型變量top指向當(dāng)前棧頂元素所在數(shù)組單元下標(biāo)。則將元素x入棧，應(yīng)執(zhí)行的語(yǔ)句為（）。A、stack[++top]=x；B、stack[top++]=x；C、stack[--top]=x；D、stack[top--]=x；第1頁(yè)共8頁(yè)

5、若用循環(huán)數(shù)組實(shí)現(xiàn)隊(duì)列，隊(duì)首游標(biāo)front指向隊(duì)首元素的前一單元，隊(duì)尾游標(biāo)rear指向隊(duì)尾元素所在單元，設(shè)循環(huán)數(shù)組的單元個(gè)數(shù)為MaxSize。若使用總剩一個(gè)單元不利用的方法區(qū)分滿(mǎn)空狀態(tài)，則front和rear滿(mǎn)足關(guān)系（）時(shí)隊(duì)列為空。A、front==(rear+1)%MaxSizeB、front==rearC、front==(rear+2)%MaxSizeD、front==(rear-1)%MaxSize6、以下關(guān)于樹(shù)的表示法說(shuō)法正確的是（）。A、父結(jié)點(diǎn)數(shù)組表示法可以快速找到某結(jié)點(diǎn)的子結(jié)點(diǎn)，但查詢(xún)父結(jié)點(diǎn)和兄弟結(jié)點(diǎn)可能要遍歷整個(gè)數(shù)組B、若采用兒子表示法，并使用定長(zhǎng)結(jié)點(diǎn)的多重鏈表結(jié)構(gòu)，則表示一棵有n個(gè)結(jié)點(diǎn)度為d的樹(shù)必有nd-n個(gè)空鏈域C、左兒子右兄弟表示法便利查找父結(jié)點(diǎn)和兄弟結(jié)點(diǎn)，但不便利查找子結(jié)點(diǎn)D、兒子鏈表表示法適合于查找子結(jié)點(diǎn)，但不適合于查找父結(jié)點(diǎn)和兄弟結(jié)點(diǎn)7、利用前序線索鏈表進(jìn)行二叉樹(shù)的前序遍歷時(shí)，若當(dāng)前遍歷結(jié)點(diǎn)存在右子樹(shù)，則（）。A、由當(dāng)前結(jié)點(diǎn)的后繼線索可找到后繼結(jié)點(diǎn)B、若當(dāng)前結(jié)點(diǎn)有左子樹(shù)，則后繼結(jié)點(diǎn)為左子樹(shù)中最左下結(jié)點(diǎn)C、若當(dāng)前結(jié)點(diǎn)有左子樹(shù)，則后繼結(jié)點(diǎn)為左子樹(shù)中最右下結(jié)點(diǎn)D、若當(dāng)前結(jié)點(diǎn)無(wú)左子樹(shù)，則后繼結(jié)點(diǎn)為右子結(jié)點(diǎn)8、以下說(shuō)法錯(cuò)誤的是（）。A、具有n個(gè)頂點(diǎn)，n-1條邊的無(wú)向圖一定是生成樹(shù)B、生成樹(shù)是無(wú)向連通圖的微小連通子圖C、具有n個(gè)頂點(diǎn)，少于n-1條邊的無(wú)向圖一定是非連通圖D、在生成樹(shù)中每?jī)蓚€(gè)頂點(diǎn)間有且僅有一條路徑9、以下說(shuō)法正確的是（）。A、無(wú)向圖鄰接矩陣第i行非零元素的個(gè)數(shù)是第i個(gè)頂點(diǎn)的度B、通過(guò)鄰接表可以便利快速地判定兩個(gè)頂點(diǎn)間是否有邊或弧相連C、通過(guò)有向圖的鄰接表，可以便利地求出頂點(diǎn)的入度D、鄰接表適用于表示稠密圖10、圖的廣度優(yōu)先探尋類(lèi)似于樹(shù)的（）。A、先序遍歷B、中序遍歷C、后序遍歷D、層次遍歷11、假使從無(wú)向圖的任一頂點(diǎn)出發(fā)進(jìn)行一次深度優(yōu)先探尋即可訪問(wèn)所有頂點(diǎn)，則該圖一定是（）。A、完全圖B、連通圖C、有回路D、一棵樹(shù)12、平衡二叉樹(shù)中結(jié)點(diǎn)的平衡因子不可能是（）。A、0B、-1C、1D、-2第2頁(yè)共8頁(yè)

13、對(duì)二叉探尋樹(shù)進(jìn)行（）可得到元素的遞增序列。A、先序遍歷B、中序遍歷C、后序遍歷D、層次遍歷14、對(duì)一個(gè)有向圖進(jìn)行拓?fù)渑判?，并判斷有向圖中是否存在回路，可以使用（）。A、無(wú)前趨頂點(diǎn)優(yōu)先算法B、深度優(yōu)先遍歷算法C、廣度優(yōu)先遍歷算法D、求最短路徑的Dijkstra算法15、以下有關(guān)平衡二叉樹(shù)的說(shuō)法錯(cuò)誤的是（）。A、平衡二叉樹(shù)左子樹(shù)和右子樹(shù)高度之差的絕對(duì)值不大于1B、在平衡二叉樹(shù)上執(zhí)行插入操作，對(duì)離新插入結(jié)點(diǎn)最近的失衡祖先結(jié)點(diǎn)為根的子樹(shù)進(jìn)行平衡旋轉(zhuǎn)后，一定能使二叉樹(shù)恢復(fù)平衡C、在平衡二叉樹(shù)上執(zhí)行刪除操作，對(duì)離被刪結(jié)點(diǎn)最近的失衡祖先結(jié)點(diǎn)為根的子樹(shù)進(jìn)行平衡旋轉(zhuǎn)后，一定能使二叉樹(shù)恢復(fù)平衡D、在含有n個(gè)結(jié)點(diǎn)的平衡二叉樹(shù)上執(zhí)行查找操作的時(shí)間繁雜度為O(logn)二、填空題（每空1分，共13分）得分評(píng)卷人1、在帶哨兵結(jié)點(diǎn)的單循環(huán)鏈表中，設(shè)鏈結(jié)點(diǎn)的后繼指針域?yàn)閚ext，指針last指向表尾結(jié)點(diǎn)，則判斷該鏈表是否為空的表達(dá)式為。2、隊(duì)列的操作原則為。3、若用循環(huán)數(shù)組實(shí)現(xiàn)隊(duì)列，隊(duì)首游標(biāo)front指向隊(duì)首元素前一單元，隊(duì)尾游標(biāo)rear指向隊(duì)尾元素所在單元，設(shè)循環(huán)數(shù)組名為queue，循環(huán)數(shù)組的單元個(gè)數(shù)為MaxSize。則將隊(duì)頭元素出隊(duì)并保存在x中，應(yīng)執(zhí)行的語(yǔ)句為；。4、不考慮樹(shù)結(jié)點(diǎn)所存放的元素值，由3個(gè)結(jié)點(diǎn)可組成種不同形態(tài)的樹(shù)。5、具有35個(gè)結(jié)點(diǎn)的二叉樹(shù)的最小高度為，最大高度為。（設(shè)僅含一個(gè)結(jié)點(diǎn)的二叉樹(shù)的高度為1）6、若采用三叉鏈表作為二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)，在含有n個(gè)結(jié)點(diǎn)的二叉樹(shù)對(duì)應(yīng)的三叉鏈表中，空鏈域總數(shù)為。7、具有24個(gè)頂點(diǎn)的有向完全圖具有條弧。第3頁(yè)共8頁(yè)8、對(duì)序列32262442462935進(jìn)行第一趟二路歸并排序后得到的序列為。9、堆排序是一種的排序方法。（填穩(wěn)定或不穩(wěn)定）10、設(shè)在高度為h的二叉樹(shù)（設(shè)僅有一個(gè)結(jié)點(diǎn)的二叉樹(shù)高度為1）中只有葉結(jié)點(diǎn)和度為2的結(jié)點(diǎn)（沒(méi)有度為1的結(jié)點(diǎn)），則該二叉樹(shù)至多有個(gè)結(jié)點(diǎn)，至少有個(gè)結(jié)點(diǎn)。三、判斷題（每題1分，共10分）得分評(píng)卷人1、度為2的樹(shù)一定是二叉樹(shù)。（）2、在完全二叉樹(shù)中，最下層的葉結(jié)點(diǎn)一定集中在該層的左端。（）3、無(wú)向圖中所有頂點(diǎn)的度數(shù)之和等于圖中邊數(shù)的2倍。（）4、有向圖的鄰接矩陣一定是對(duì)稱(chēng)的。（）5、若有向圖中存在環(huán)，則拓?fù)湫蛄斜夭话许旤c(diǎn)。（）6、從某頂點(diǎn)出發(fā)進(jìn)行深度優(yōu)先遍歷，最先退出dfs過(guò)程的是拓?fù)湫蛄械牡谝粋€(gè)頂點(diǎn)。（）7、縮短關(guān)鍵活動(dòng)的持續(xù)時(shí)間能提高整個(gè)工程的進(jìn)度。（）8、二部圖的完全匹配一定是最大匹配。（）9、左偏高樹(shù)的右子樹(shù)的高度一定大于左子樹(shù)的高度。（）10、具有n個(gè)結(jié)點(diǎn)的非空二叉樹(shù)必有n-1個(gè)分支。（）四、應(yīng)用題（共47分）得分評(píng)卷人第4頁(yè)共8頁(yè)

1、已知一棵二叉樹(shù)的中序遍歷序列為DIGBEACHF，后序遍歷序列為IGDEBHFCA，畫(huà)出這棵二叉樹(shù)并寫(xiě)出它的先序遍歷序列。（8分）（1）、二叉樹(shù)為：（2）、該二叉樹(shù)的先序遍歷序列為：2、寫(xiě)出以頂點(diǎn)1為源點(diǎn)遍歷