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

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

參考答案一、選擇題1、【答案】C2、【答案】A3、【答案】A4、【答案】D5、【答案】A6、【答案】A7、【答案】A8、【答案】A9、【答案】D10、【答案】A二、填空題11、【答案】（n+1）/212、【答案】n(n-1)/213、【答案】分配和釋放存儲空間；重組；對插入的記錄@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上最小生成樹邊的集合。算法從VT={u0}，ET開始，重復(fù)執(zhí)行下述操作：在所有u屬于VT，v屬于V-VT的邊（u，v）屬于E中找一條代價最小的邊（u0，v0）加入集合ET，同時將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、【答案】【解析】滿二叉樹沒有度為1的結(jié)點，度為0的結(jié)點等于度為2的結(jié)點個數(shù)+1。17、【答案】a[j]=a[k]；low=stack[top][0]；stack[top][0]=k+1【解析】快速排序(quicksort)的基本思想是，通過一趟排序?qū)⒋庞涗浄指畛瑟毩⒌膬刹糠郑渲幸徊糠钟涗浀年P(guān)鍵字均比另一部分記錄的關(guān)鍵字小，則可分別對這兩部分記錄繼續(xù)進行排序，以達到整個序列有序。18、【答案】stack[tp]=t；p=stack[tp--]；p；++tp【解析】本題主要使用堆棧完成了二叉樹左右子樹交換的操作。首先根結(jié)點進棧，然后判斷棧是否為空，如果不為空，則取棧頂元素，交換取出結(jié)點的左右指針。并將左右指針分別進棧，重復(fù)這一操作。完成二叉樹左右孩子的交換。三、判斷題19、【答案】×20、【答案】×21、【答案】×22、【答案】√23、【答案】√24、【答案】√25、【答案】×26、【答案】×27、【答案】√28、【答案】×四、簡答題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對，f（5）=55，執(zhí)行過程中，輸出結(jié)果為：30、答：賦值語句一共被執(zhí)