2022年首都師范大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)《數(shù)據(jù)結(jié)構(gòu)與算法》科目期末試卷A(有答案)

2022年首都師范大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)《數(shù)據(jù)結(jié)構(gòu)與算法》科目期末試卷A（有答案）一、選擇題1、將線性表的數(shù)據(jù)元素進(jìn)行擴(kuò)充，允許帶結(jié)構(gòu)的線性表是（）。A.串B.樹(shù)C.廣義表D.棧2、將兩個(gè)各有N個(gè)元素的有序表歸并成一個(gè)有序表，其最少的比較次數(shù)是（）。A.NB.2N-1C.2ND.N-13、連續(xù)存儲(chǔ)設(shè)計(jì)時(shí)，存儲(chǔ)單元的地址（）。A.一定連續(xù)B.一定不連續(xù)C.不一定連續(xù)D.部分連續(xù)，部分不連續(xù)4、向一個(gè)棧頂指針為h的帶頭結(jié)點(diǎn)的鏈棧中插入指針s所指的結(jié)點(diǎn)時(shí)，應(yīng)執(zhí)行（）。A.h->next=sB.s->next=hC.s->next=h;h->next=sD.s->next=h-next;h->next=s5、已知串S='aaab'，其next數(shù)組值為（）。A.0123B.1123C.1231D.12116、已知關(guān)鍵字序列5，8，12，19，28，20，15，22是小根堆（最小堆），插入關(guān)鍵字3，調(diào)整后的小根堆是（）。A．3，5，12，8，28，20，15，22，19B．3，5，12，19，20，15，22，8，28C．3，8，12，5，20，15，22，28，19D．3，12，5，8，28，20，15，22，197、若一棵二叉樹(shù)的前序遍歷序列為a，e，b，d，c，后序遍歷序列為b，c，d，e，a，則根結(jié)點(diǎn)的孩子結(jié)點(diǎn)（）。A．只有eB．有e、bC．有e、cD．無(wú)法確定8、已知一棵二叉樹(shù)的前序遍歷結(jié)果為ABCDEF，中序遍歷結(jié)果為CBAEDF，則后序遍歷結(jié)果為（）。A.CBEFDAB.FEDCBAC.CBEDFAD.不定9、在下述結(jié)論中，正確的有（）。①只有一個(gè)結(jié)點(diǎn)的二叉樹(shù)的度為0。②二叉樹(shù)的度為2。③二叉樹(shù)的左右子樹(shù)可任意交換。④深度為K的完全二叉樹(shù)的結(jié)點(diǎn)個(gè)數(shù)小于或等于深度相同的滿二叉樹(shù)。A.①②③B.⑦③④C.②④D.①④10、在文件“局部有序”或文件長(zhǎng)度較小的情況下，最佳內(nèi)部排序的方法是（）。A.直接插入排序B.起泡排序C.簡(jiǎn)單選擇排序D.快速排序二、填空題11、如果按關(guān)鍵碼值遞增的順序依次將關(guān)鍵碼值插入到二叉排序樹(shù)中，則對(duì)這樣的二叉排序樹(shù)檢索時(shí)，平均比較次數(shù)為_(kāi)_____。12、若用n表示圖中頂點(diǎn)數(shù)目，則有______條邊的無(wú)向圖成為完全圖。13、VSAM（虛擬存儲(chǔ)存取方法）文件的優(yōu)點(diǎn)是：動(dòng)態(tài)地______，不需要文件進(jìn)行______，并能較快地______進(jìn)行查找。14、應(yīng)用Prim算法求解連通網(wǎng)絡(luò)的最小生成樹(shù)問(wèn)題。（1）針對(duì)如圖所示的連通網(wǎng)絡(luò)，試按如下格式給出在構(gòu)造最小生成樹(shù)過(guò)程中順序選出的各條邊。（2）下面是Prim算法的實(shí)現(xiàn)，中間有5個(gè)地方缺失，請(qǐng)閱讀程序后將它們補(bǔ)上。15、以下是用類C語(yǔ)言寫(xiě)出的算法，該算法將以二叉鏈表存儲(chǔ)的二叉樹(shù)中的葉結(jié)點(diǎn)按從左到右的順序鏈成一個(gè)帶頭結(jié)點(diǎn)的雙向循環(huán)鏈表，鏈接時(shí)，結(jié)點(diǎn)的Lchild域作為前鏈域，指向結(jié)點(diǎn)的直接前驅(qū)，結(jié)點(diǎn)的Rchild域作為后鏈域，指向結(jié)點(diǎn)的直接后繼。算法中，使用一個(gè)順序棧stack，棧頂指針為top，p，t為輔助指針，head為雙向循環(huán)鏈表的頭指針。試填充算法中的空格，使算法完整。16、一棵有n個(gè)結(jié)點(diǎn)的滿二叉樹(shù)有______個(gè)度為1的結(jié)點(diǎn)、有______個(gè)分支（非終端）結(jié)點(diǎn)和______個(gè)葉子，該滿二叉樹(shù)的深度為_(kāi)_____。17、下列程序是快速排序的非遞歸算法，請(qǐng)?zhí)顚?xiě)適當(dāng)?shù)恼Z(yǔ)句，完成該功能。18、閱讀下列程序說(shuō)明和程序，填充程序中的______?！境绦蛘f(shuō)明】本程序完成將二叉樹(shù)中左、右孩子交換的操作。交換的結(jié)果如下所示（編者略）。本程序采用非遞歸的方法，設(shè)立一個(gè)堆棧stack存放還沒(méi)有轉(zhuǎn)換過(guò)的結(jié)點(diǎn)，它的棧頂指針為tp。交換左、右子樹(shù)的算法為：（1）把根結(jié)點(diǎn)放入堆棧。（2）當(dāng)堆棧不空時(shí)，取出棧頂元素，交換它的左、右子樹(shù)，并把它的左、右子樹(shù)分別入棧。（3）重復(fù)（2）直到堆棧為空時(shí)為止。三、判斷題19、哈希表與哈希文件的唯一區(qū)別是哈希文件引入了“桶”的概念。（）20、對(duì)磁帶機(jī)而言，ISAM是一種方便的文件組織方法（）21、數(shù)組不適合作為任何二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)。（）22、設(shè)模式串的長(zhǎng)度為m，目標(biāo)串的長(zhǎng)度為n，當(dāng)n≈m且處理只匹配一次的模式時(shí)，樸素的匹配（即子串定位函數(shù)）算法所花的時(shí)間代價(jià)可能會(huì)更為節(jié)省。（）23、樹(shù)形結(jié)構(gòu)中元素之間存在一對(duì)多的關(guān)系。（）24、一個(gè)樹(shù)形的葉結(jié)點(diǎn)，在前序遍歷和后序遍歷下，皆以相同的相對(duì)位置出現(xiàn)。（）25、順序存儲(chǔ)方式的優(yōu)點(diǎn)是存儲(chǔ)密度大，且插入、刪除運(yùn)算效率高。（）26、歸并排序輔助存儲(chǔ)為O（1）。（）27、B-樹(shù)中所有結(jié)點(diǎn)的平衡因子都為零。（）28、有向圖中頂點(diǎn)V度等于其鄰接矩陣中第V行中的1的個(gè)數(shù)。（）四、簡(jiǎn)答題29、調(diào)用下列C函數(shù)f（n），回答下列問(wèn)題：（1）試指出f（n）值的大小，并寫(xiě)出，f（n）值的推導(dǎo)過(guò)程。（2）假定n=5，試指出，f（5）值的大小和執(zhí)行，f（5）時(shí)的輸出結(jié)果。C函數(shù)：30、下面程序段的時(shí)間復(fù)雜度是什么？31、已知世界六大城市為：北京(Pe)、紐約(N)、巴黎(Pa)、倫敦(L)、東京(T)、墨西哥(M)，下表給定了這六大城市之間的交通里程：世界六大城市交通里程表(單位：百公里)（1）畫(huà)出這六大城市的交通網(wǎng)絡(luò)圖。（2）畫(huà)出該圖的鄰接表表示法。（3）畫(huà)出該圖按權(quán)值遞增的順序來(lái)構(gòu)造的最?。ù鷥r(jià)）生成樹(shù)。五、算法設(shè)計(jì)題32、在一棵以二叉鏈表表示的二叉樹(shù)上，試寫(xiě)出按層次順序遍歷二叉樹(shù)的方法，統(tǒng)計(jì)樹(shù)中具有度為1的結(jié)點(diǎn)數(shù)目的算法。33、試編寫(xiě)一算法對(duì)二叉樹(shù)按前序線索化。34、請(qǐng)用流程圖或高級(jí)語(yǔ)言表示算法。已知有向圖有n個(gè)頂點(diǎn)，請(qǐng)寫(xiě)算法，根據(jù)用戶輸入的數(shù)對(duì)建立該有向圖的鄰接表。即接受用戶輸入的<vi，vj>(以其中之一為0標(biāo)志結(jié)束)，對(duì)于每條這樣的邊，申請(qǐng)一個(gè)結(jié)點(diǎn)，并插入到的單鏈表中，如此反復(fù)，直到將圖中所有邊處理完畢。提示：先產(chǎn)生鄰接表的n個(gè)頭結(jié)點(diǎn)(其結(jié)點(diǎn)數(shù)值域從1到n)。35、已知兩個(gè)定長(zhǎng)數(shù)組，它們分別存放兩個(gè)非降序有序序列，請(qǐng)編寫(xiě)程序把第二個(gè)數(shù)組序列中的數(shù)逐個(gè)插入到前一個(gè)數(shù)組序列中，完成后兩個(gè)數(shù)組中的數(shù)分別有序（非降序）并且第一數(shù)組中所有的數(shù)都不大于第二個(gè)數(shù)組中的任意一個(gè)數(shù)。注意，不能另開(kāi)辟數(shù)組，也不能對(duì)任意一個(gè)數(shù)組進(jìn)行排序操作。例如：第一個(gè)數(shù)組為：4，12，28第二個(gè)數(shù)組為：1，7，9，29，45輸出結(jié)果為：l，4，7……第一個(gè)數(shù)組9，12，28，29，45……第二個(gè)數(shù)組

參考答案一、選擇題1、【答案】C2、【答案】A3、【答案】A4、【答案】D5、【答案】A6、【答案】A7、【答案】A8、【答案】A9、【答案】D10、【答案】A二、填空題11、【答案】（n+1）/212、【答案】n(n-1)/213、【答案】分配和釋放存儲(chǔ)空間；重組；對(duì)插入的記錄@14、【答案】(1)(0，3，1)；(3，5，4)；(5，2，2)；(3，1，5)；(1，4，3)(2)①T[k]；toVex=i②min=MaxInt;③mispos=i④exit(0)⑤T[i]；fromVex=v【解析】Prim算法的執(zhí)行類似于尋找圖的最短路徑的Dijkstra算法。假設(shè)N={V，E}是連通圖，ET是N上最小生成樹(shù)邊的集合。算法從VT={u0}，ET開(kāi)始，重復(fù)執(zhí)行下述操作：在所有u屬于VT，v屬于V-VT的邊（u，v）屬于E中找一條代價(jià)最小的邊（u0，v0）加入集合ET，同時(shí)將v0并入VT，直到VT=V為止。15、【答案】p->Rchild=t；t->Lchild=p；p=t；t->Rchild!=null；t->Rchild；t->Lchild!=null；t->Lchild；p->Rchild=head；head->Lchild=p16、【答案】【解析】滿二叉樹(shù)沒(méi)有度為1的結(jié)點(diǎn)，度為0的結(jié)點(diǎn)等于度為2的結(jié)點(diǎn)個(gè)數(shù)+1。17、【答案】a[j]=a[k]；low=stack[top][0]；stack[top][0]=k+1【解析】快速排序(quicksort)的基本思想是，通過(guò)一趟排序?qū)⒋庞涗浄指畛瑟?dú)立的兩部分，其中一部分記錄的關(guān)鍵字均比另一部分記錄的關(guān)鍵字小，則可分別對(duì)這兩部分記錄繼續(xù)進(jìn)行排序，以達(dá)到整個(gè)序列有序。18、【答案】stack[tp]=t；p=stack[tp--]；p；++tp【解析】本題主要使用堆棧完成了二叉樹(shù)左右子樹(shù)交換的操作。首先根結(jié)點(diǎn)進(jìn)棧，然后判斷棧是否為空，如果不為空，則取棧頂元素，交換取出結(jié)點(diǎn)的左右指針。并將左右指針?lè)謩e進(jìn)棧，重復(fù)這一操作。完成二叉樹(shù)左右孩子的交換。三、判斷題19、【答案】×20、【答案】×21、【答案】×22、【答案】√23、【答案】√24、【答案】√25、【答案】×26、【答案】×27、【答案】√28、【答案】×四、簡(jiǎn)答題29、答：（1）第一層for循環(huán)判斷n+1次，往下執(zhí)行n次，第二層for執(zhí)行次數(shù)為（n+（n-1）+（n-2）+…+1），第三層循環(huán)體受第一層循環(huán)和第二層循環(huán)的控制，其執(zhí)行次數(shù)如表1-1所示。執(zhí)行次數(shù)為f(n)=（1+2+…+，n）+（2+3+…+，n）+…+n=n*n（n+1）/2-n（n2-1）/6。（2）在n=5對(duì)，f（5）=55，執(zhí)行過(guò)程中，輸出結(jié)果為：30、答：賦值語(yǔ)句一共被執(zhí)