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、無向圖G=(V，E)，其中：V={a，b，c，d，e，f}，E={(a，b)，(a，e)，(a，c)，(b，e)，(c，f)，(f，d)，(e，d)}，對該圖進(jìn)行深度優(yōu)先遍歷，得到的頂點(diǎn)序列正確的是（）。A.a，b，e，c，d，fB.a，c，f,e，b，dC.a，e，b，c，f,dD.a，e，d，f，c，b2、已知廣義表LS=（（a，b，c），（d，e，f）），用head和tail數(shù)取出LS中原子e的運(yùn)算是（）。A.head（tail（LS））B.tail（head（LS））C.head（tail（head（tail（LS））））D.head（tail（tail（head（LS））））3、連續(xù)存儲設(shè)計(jì)時，存儲單元的地址（）。A.一定連續(xù)B.一定不連續(xù)C.不一定連續(xù)D.部分連續(xù)，部分不連續(xù)4、向一個棧頂指針為h的帶頭結(jié)點(diǎn)的鏈棧中插入指針s所指的結(jié)點(diǎn)時，應(yīng)執(zhí)行（）。A.h->next=sB.s->next=hC.s->next=h;h->next=sD.s->next=h-next;h->next=s5、在下列表述中，正確的是（）A.含有一個或多個空格字符的串稱為空格串B.對n（n>0）個頂點(diǎn)的網(wǎng)，求出權(quán)最小的n-1條邊便可構(gòu)成其最小生成樹C.選擇排序算法是不穩(wěn)定的D.平衡二叉樹的左右子樹的結(jié)點(diǎn)數(shù)之差的絕對值不超過l6、若一棵二叉樹的前序遍歷序列為a，e，b，d，c，后序遍歷序列為b，c，d，e，a，則根結(jié)點(diǎn)的孩子結(jié)點(diǎn)（）。A．只有eB．有e、bC．有e、cD．無法確定7、下列敘述中，不符合m階B樹定義要求的是（）。A．根結(jié)點(diǎn)最多有m棵子樹B．所有葉結(jié)點(diǎn)都在同一層上C．各結(jié)點(diǎn)內(nèi)關(guān)鍵字均升序或降序排列D．葉結(jié)點(diǎn)之間通過指針鏈接8、有n（n>0）個分支結(jié)點(diǎn)的滿二叉樹的深度是（）。A.n2-1B.log2（n+1）+1C.log2（n+1）D.log2（n-l）9、每個結(jié)點(diǎn)的度或者為0或者為2的二叉樹稱為正則二叉樹。n個結(jié)點(diǎn)的正則二叉樹中有（）個葉子。A.log2nB.（n－1）/2C.log2n+1D.（n＋1）/210、分別以下列序列構(gòu)造二叉排序樹，與用其他三個序列所構(gòu)造的結(jié)果不同的是（）。A.（100，80，90，60，120，110，130）B.（100，120，110，130，80，60，90）C.（100，60，80，90，20，110，130）D.（100，80，60，90，120，130，110）二、填空題11、順序查找n個元素的順序表，若查找成功，則比較關(guān)鍵字的次數(shù)最多為______次；當(dāng)使用監(jiān)視哨時，若查找失敗，則比較關(guān)鍵字的次數(shù)為______。12、下面程序的功能是用遞歸算法將一個整數(shù)按逆序存放到一個字符數(shù)組中。如123存放成321。請?zhí)羁眨?3、VSAM系統(tǒng)是由______、______、______構(gòu)成的。14、一個算法具有5個特性：______、______、______、有零個或多個輸入、有一個或多個輸出。15、文件由______組成；記錄由______組成。16、閱讀下列程序說明和程序，填充程序中的______。【程序說明】本程序完成將二叉樹中左、右孩子交換的操作。交換的結(jié)果如下所示（編者略）。本程序采用非遞歸的方法，設(shè)立一個堆棧stack存放還沒有轉(zhuǎn)換過的結(jié)點(diǎn)，它的棧頂指針為tp。交換左、右子樹的算法為：（1）把根結(jié)點(diǎn)放入堆棧。（2）當(dāng)堆棧不空時，取出棧頂元素，交換它的左、右子樹，并把它的左、右子樹分別入棧。（3）重復(fù)（2）直到堆棧為空時為止。17、設(shè)正文串長度為n，模式串長度為m，則串匹配的KMP算法的時間復(fù)雜度為______。18、已知鏈隊(duì)列的頭尾指針分別是f和r，則將值x入隊(duì)的操作序列是______。三、判斷題19、對處理大量數(shù)據(jù)的外存介質(zhì)而言，索引順序存取方法是一種方便的文件組織方法。（）20、倒排文件的目的是為了多關(guān)鍵字查找。（）21、稀疏矩陣壓縮存儲后，必會失去隨機(jī)存取功能。（）22、KMP算法的特點(diǎn)是在模式匹配時指示主串的指針不會變小。（）23、中序遍歷一棵二叉排序樹的結(jié)點(diǎn)就可得到排好序的結(jié)點(diǎn)序列。（）24、一棵樹中的葉子數(shù)一定等于與其對應(yīng)的二叉樹的葉子數(shù)。（）25、在外部排序過程中，對長度為n的初始序列進(jìn)行“置換-選擇”排序時，可以得到的最大初始有序段的長度不超過n/2。（）26、數(shù)據(jù)的邏輯結(jié)構(gòu)是指數(shù)據(jù)的各數(shù)據(jù)項(xiàng)之間的邏輯關(guān)系。（）27、對大小均為n的有序表和無序表分別進(jìn)行順序查找，在等概率查找的情況下，對于查找成功，它們的平均查找長度是相同的，而對于查找失敗，它們的平均查找長度是不同的。（）28、有向圖中頂點(diǎn)V度等于其鄰接矩陣中第V行中的1的個數(shù)。（）四、簡答題29、下面程序段的時間復(fù)雜度是什么？30、請寫出應(yīng)填入下列敘述中（）內(nèi)的正確答案。排序有各種方法，如插入排序、快速排序、堆排序等。設(shè)一數(shù)組中原有數(shù)據(jù)如下：15，13，20，18，12，60。下面是一組用不同排序方法進(jìn)行一遍排序后的結(jié)果。（）排序的結(jié)果為：12，13，15，18，20，60（）排序的結(jié)果為：13，15，18，12，20，60（）排序的結(jié)果為：13，15，20，18，12，60（）排序的結(jié)果為：12，13，20，18，15，6031、用單鏈表保存m個整數(shù)，節(jié)點(diǎn)的結(jié)構(gòu)為（data，link），且|data|＜n（n為正整數(shù)）?，F(xiàn)要求設(shè)計(jì)一個時間復(fù)雜度盡可能高效地算法，對于鏈表中絕對值相等的節(jié)點(diǎn)，僅保留第一次出現(xiàn)的節(jié)點(diǎn)而刪除其余絕對值相等的節(jié)點(diǎn)。例如若給定的單鏈表head如下刪除節(jié)點(diǎn)后的head為要求（1）給出算法的基本思想（2）使用C或C＋＋語言，給出單鏈表節(jié)點(diǎn)的數(shù)據(jù)類型定義。（3）根據(jù)設(shè)計(jì)思想，采用C或C＋＋語言描述算法，關(guān)鍵之處給出注釋。說明所涉及算法的時間復(fù)雜度和空間復(fù)雜度。五、算法設(shè)計(jì)題32、假定用兩個一維數(shù)組L[N]和R[N]作為有N個結(jié)點(diǎn)1，2，…，N的二叉樹的存儲結(jié)構(gòu)。L[i]和R[i]分別指示結(jié)點(diǎn)i的左兒子和右兒子，L[i]=0（R[i]=0）表示i的左（右）兒子為空。試寫一個算法，由L和R建立一個一維數(shù)組T[n]，使T[i]存放結(jié)點(diǎn)i的父親；然后再寫一個判別結(jié)點(diǎn)u是否為結(jié)點(diǎn)V的后代的算法。33、若x和y是兩個采用順序結(jié)構(gòu)存儲的串，編寫一個比較兩個串是否相等的函數(shù)。34、已知無向圖采用鄰接表存儲方式，試寫出刪除邊（i，j）的算法。35、已知兩個定長數(shù)組，它們分別存放兩個非降序有序序列，請編寫程序把第二個數(shù)組序列中的數(shù)逐個插入到前一個數(shù)組序列中，完成后兩個數(shù)組中的數(shù)分別有序（非降序）并且第一數(shù)組中所有的數(shù)都不大于第二個數(shù)組中的任意一個數(shù)。注意，不能另開辟數(shù)組，也不能對任意一個數(shù)組進(jìn)行排序操作。例如：第一個數(shù)組為：4，12，28第二個數(shù)組為：1，7，9，29，45輸出結(jié)果為：l，4，7……第一個數(shù)組9，12，28，29，45……第二個數(shù)組

參考答案一、選擇題1、【答案】D2、【答案】C3、【答案】A4、【答案】D5、【答案】C6、【答案】A7、【答案】D8、【答案】C9、【答案】D10、【答案】C二、填空題11、【答案】n；n+112、【答案】a+1；n%10【解析】通過遞歸算法，首先找到最高位的值，將其放到str對應(yīng)的數(shù)組中，依次反向獲取從高位到地位的值，將其放到數(shù)組中，完成了將整數(shù)逆序放到一個字符數(shù)組中。13、【答案】索引集；順序集；數(shù)據(jù)集14、【答案】有窮性；確定性；可行性15、【答案】記錄；數(shù)據(jù)項(xiàng)16、【答案】stack[tp]=t；p=stack[tp--]；p；++tp【解析】本題主要使用堆棧完成了二叉樹左右子樹交換的操作。首先根結(jié)點(diǎn)進(jìn)棧，然后判斷棧是否為空，如果不為空，則取棧頂元素，交換取出結(jié)點(diǎn)的左右指針。并將左右指針分別進(jìn)棧，重復(fù)這一操作。完成二叉樹左右孩子的交換。17、【答案】O（m+n）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、答：賦值語句一共被執(zhí)行了m*n次，所以該程序段的時間復(fù)雜度是O（m*n）。30、答：①快速排序②起泡排序③直接插入排序④堆排序31、答：（1）算法思想：算法的核心思想是用空間換時間。定義一個大小為n的布爾數(shù)組flag，初始時所有的元素都賦值為false，用來標(biāo)識遍歷過程中是否出現(xiàn)元素絕對值為flag的節(jié)點(diǎn)。然后遍歷鏈表，遍歷過程中，每一個當(dāng)前