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

2022年東北大學(xué)計算機(jī)科學(xué)與技術(shù)專業(yè)《數(shù)據(jù)結(jié)構(gòu)與算法》科目期末試卷A（有答案）一、選擇題1、已知廣義表LS=（（a，b，c），（d，e，f）），用head和tail數(shù)取出LS中原子e的運算是（）。A.head（tail（LS））B.tail（head（LS））C.head（tail（head（tail（LS））））D.head（tail（tail（head（LS））））2、下列說法不正確的是（）。A.圖的遍歷是從給定的源點出發(fā)每個頂點僅被訪問一次B.遍歷的基本方法有兩種：深度遍歷和廣度遍歷C.圖的深度遍歷不適用于有向圖D.圖的深度遍歷是一個遞歸過程3、靜態(tài)鏈表中指針表示的是（）。A.下一元素的地址B.內(nèi)存儲器的地址C.下一元素在數(shù)組中的位置D.左鏈或右鏈指向的元素的地址4、最大容量為n的循環(huán)隊列，隊尾指針是rear，隊頭：front，則隊空的條件是（）。A.（rear+1）MODn=frontB.rear=frontC.rear+1=frontD.（rear-1）MODn=front5、循環(huán)隊列A[0..m-1]存放其元素值，用front和rear分別表示隊頭和隊尾，則當(dāng)前隊列中的元素數(shù)是（）。A.（rear-front+m）%mB.rear-front+1C.rear-front-1D.rear-front6、下列關(guān)于無向連通圖特性的敘述中，正確的是（）。Ⅰ．所有的頂點的度之和為偶數(shù)Ⅱ．邊數(shù)大于頂點個數(shù)減1Ⅲ．至少有一個頂點的度為1A．只有ⅠB．只有ⅡC．Ⅰ和ⅡD．Ⅰ和Ⅲ7、下列敘述中，不符合m階B樹定義要求的是（）。A．根結(jié)點最多有m棵子樹B．所有葉結(jié)點都在同一層上C．各結(jié)點內(nèi)關(guān)鍵字均升序或降序排列D．葉結(jié)點之間通過指針鏈接8、一棵非空的二叉樹的前序序列和后序序列正好相反，則該二叉樹一定滿足（）。A.其中任意一個結(jié)點均無左孩子B.其中任意一個結(jié)點均無右孩子C.其中只有一個葉結(jié)點D.其中度為2的結(jié)點最多為一個9、下述二叉樹中，哪一種滿足性質(zhì)：從任一結(jié)點出發(fā)到根的路徑上所經(jīng)過的結(jié)點序列按其關(guān)鍵字有序（）。A.二叉排序樹B.哈夫曼樹C.AVL樹D.堆10、對序列{15，9，7，8，20，-1，4}用希爾排序方法排序，經(jīng)一趟后序列變?yōu)閧15，-1，4，8，20，9，7}則該次采用的增量是（）。A.1B.4C.3D.2二、填空題11、閱讀下列程序，指出其功能，并寫出空格處應(yīng)填上的語句。12、無用單元是指______，例______13、應(yīng)用Prim算法求解連通網(wǎng)絡(luò)的最小生成樹問題。（1）針對如圖所示的連通網(wǎng)絡(luò)，試按如下格式給出在構(gòu)造最小生成樹過程中順序選出的各條邊。（2）下面是Prim算法的實現(xiàn)，中間有5個地方缺失，請閱讀程序后將它們補(bǔ)上。14、在一棵m階B-樹中，若在某結(jié)點中插入一個新關(guān)鍵字而引起該結(jié)點分裂，則此結(jié)點中原有的關(guān)鍵字的個數(shù)是______；若在某結(jié)點中刪除一個關(guān)鍵字而導(dǎo)致結(jié)點合并，則該結(jié)點中原有的關(guān)鍵字的個數(shù)是______。15、設(shè)T是一棵結(jié)點值為整數(shù)的二叉排序樹，A是一個任意給定的整數(shù)。在下面的算法中，free_tree（T）在對二叉排序樹丁進(jìn)行后序遍歷時釋放二又排序樹T的所有結(jié)點；delete_subtree（T，A），首先在二叉排序樹T中查找值為A的結(jié)點，根據(jù)查找情況分別進(jìn)行如下處理：（1）若找不到值為A的結(jié)點，則返回根結(jié)點的地址（2）若找到值為A的結(jié)點，則刪除以此結(jié)點為根的子樹，并釋放此子樹中的所有結(jié)點，若值為A的結(jié)點是查找樹的根結(jié)點，刪除后變成空的二叉樹，則返null；否則返回根結(jié)點的地址。16、一棵有n個結(jié)點的滿二叉樹有______個度為1的結(jié)點、有______個分支（非終端）結(jié)點和______個葉子，該滿二叉樹的深度為______。17、當(dāng)兩個棧共享一存儲區(qū)時，棧利用一維數(shù)組stack（1，n）表示，兩棧頂指針為top[1]與top[2]，則當(dāng)棧1空時，top[1]為______，棧2空時，top[2]為______，棧滿時為______。18、已知鏈隊列的頭尾指針分別是f和r，則將值x入隊的操作序列是______。三、判斷題19、對磁帶機(jī)而言，ISAM是一種方便的文件組織方法（）20、倒排文件的目的是為了多關(guān)鍵字查找。（）21、廣義表（（（a，b，c），d，e，f））的長度是4。（）22、二維以上的數(shù)組其實是一種特殊的廣義表。（）23、一般來說，若深度為k的n個結(jié)點的二叉樹只有最小路徑長度，那么從根結(jié)點到第k-1層具有的最多結(jié)點數(shù)為2k-1-1，余下的n-2k-1+1個結(jié)點在第k層的任一位置上。（）24、一個樹形的葉結(jié)點，在前序遍歷和后序遍歷下，皆以相同的相對位置出現(xiàn)。（）25、在一個設(shè)有頭指針和尾指針的單鏈表中，執(zhí)行刪除該單鏈表中最后一個元素的操作與鏈表的長度無關(guān)。（）26、為提高排序速度，進(jìn)行外排序時，必須選用最快的內(nèi)排序算法。（）27、若一個有向圖的鄰接矩陣對角線以下元素均為零，則該圖的拓?fù)溆行蛐蛄斜囟ù嬖?。（?8、對兩棵具有相同關(guān)鍵字集合的而形狀不同的二叉排序樹，按中序遍歷它們得到的序列的順序卻是一致的。（）四、簡答題29、對于具有n個葉結(jié)點且所有非葉結(jié)點都有左、右孩子的二叉樹。(1)試問這種二叉樹的結(jié)點總數(shù)是多少?(2)試證明2-（li-1）=1。其中：li表示第i個葉結(jié)點所在的層號（設(shè)根結(jié)點所在層號為1）。30、設(shè)目標(biāo)為t=‘a(chǎn)bcaabbabcabaacbacba’，模式為P=‘a(chǎn)bcabaa’（1）計算模式p的nextval函數(shù)值。（2）不寫出算法，只畫出利用KMP算法進(jìn)行模式匹配時每一趟的匹配過程。31、對下面的關(guān)鍵字集{30，15，21，40，25，26，36，37}若查找表的裝填因子為0.8，采用線性探測再哈希方法解決沖突，做：（1）設(shè)計哈希函數(shù)；（2）畫出哈希表；（3）計算查找成功和查找失敗的平均查找長度；（4）寫出將哈希表中某個數(shù)據(jù)元素刪除的算法。五、算法設(shè)計題32、假定用兩個一維數(shù)組L[N]和R[N]作為有N個結(jié)點1，2，…，N的二叉樹的存儲結(jié)構(gòu)。L[i]和R[i]分別指示結(jié)點i的左兒子和右兒子，L[i]=0（R[i]=0）表示i的左（右）兒子為空。試寫一個算法，由L和R建立一個一維數(shù)組T[n]，使T[i]存放結(jié)點i的父親；然后再寫一個判別結(jié)點u是否為結(jié)點V的后代的算法。33、假設(shè)以雙親表示法作樹的存儲結(jié)構(gòu)，寫出雙親表示的類型說明，并編寫求給定的樹的深度的算法（注：已知樹中的結(jié)點數(shù)）。34、圖G有n個點，利用從某個源點到其余各點最短路徑算法思想，設(shè)計一產(chǎn)生G的最小生成樹的算法。35、從鍵盤上輸入一串正整數(shù)，最后輸入-l作為結(jié)束標(biāo)志。如：8，7，l，22，98，46，…，75，-l。請設(shè)計一個非遞歸程序，創(chuàng)建一棵二叉排序樹，并且該二叉排序樹也必須是中序線索二叉樹。設(shè)該二叉排序樹上的結(jié)點結(jié)構(gòu)為（teft，ltag，data，rtag，right）。其中：data域為結(jié)點的數(shù)據(jù)場。ltag=0，那么left域中存在的是該結(jié)點的左兒子結(jié)點的地址。ltag=1，那么left域中存放的是該結(jié)點的按中序遍歷次序的前驅(qū)結(jié)點的地址rtag=0，那么right域中存放的是該結(jié)點的右兒子結(jié)點的地址。rtag=1，那么right域中存放的是該結(jié)點的按中序遍歷次序的后繼結(jié)點地址。

參考答案一、選擇題1、【答案】C2、【答案】C3、【答案】C4、【答案】B5、【答案】A6、【答案】A7、【答案】D8、【答案】C9、【答案】D10、【答案】B二、填空題11、【答案】trai->link=ptr；ht[hash_value]=ptr【解析】本題是在哈希表ht[]中插入值為item的元素，如該元素已在哈希表中，報告出錯。12、【答案】用戶不再使用而系統(tǒng)沒有回收的結(jié)構(gòu)和變量；p=ma11oc（size）;…,p=nu1113、【答案】(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為止。14、【答案】【解析】m階B-樹除根結(jié)點和葉子結(jié)點外，結(jié)點中關(guān)鍵字個數(shù)最多是m1，最少15、【答案】free（T）；q&&q->data!=A；q=q->rchild；p->lchild=null；p->rchild=null16、【答案】【解析】滿二叉樹沒有度為1的結(jié)點，度為0的結(jié)點等于度為2的結(jié)點個數(shù)+1。17、【答案】0；n+1；top[1]+1=top[2]18、【答案】s=（LinkedList*）ma11oc（sizeof（LNode））；s->data=x；s->next=r->next；r->next=s；r=s。三、判斷題19、【答案】×20、【答案】√21、【答案】×22、【答案】√23、【答案】√24、【答案】√25、【答案】×26、【答案】×27、【答案】√28、【答案】√四、簡答題29、答：（1）根據(jù)二叉樹中度為2的結(jié)點個數(shù)等于葉結(jié)點個數(shù)減1的性質(zhì)，故具有n個葉結(jié)點且非葉子結(jié)點均有左子樹的二叉樹的結(jié)點數(shù)是2n-1。（2）證明：當(dāng)i=1時，2-（1-1）=20=1，公式成立。設(shè)當(dāng)i=n-1時公式成立，證明當(dāng)i=n時公式仍成立。設(shè)某葉結(jié)點的層號為t，當(dāng)將該結(jié)點變?yōu)閮?nèi)部結(jié)點，從而再增加兩個葉結(jié)點時，這兩個葉結(jié)點的層號都是t+1，對于公式的變化，是減少了一個原來的葉結(jié)點，增加了兩個新葉結(jié)點，反映到公式中，因為2-（t-1）=2-（t+1-1）+2-（t+1-1），所以結(jié)果不變，這就證明當(dāng)i=n時公式仍成立。證畢。30、答：（1）p的nextval函數(shù)值為0110132（p的next函數(shù)值為0111232）。（2）利用KMP（改進(jìn)的nextval）算法，每趟匹配