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

2022年唐山師范學院計算機科學與技術(shù)專業(yè)《數(shù)據(jù)結(jié)構(gòu)與算法》科目期末試卷A（有答案）一、選擇題1、若需在O（nlog2n）的時間內(nèi)完成對數(shù)組的排序，且要求排序是穩(wěn)定的，則可選擇的排序方法是（）。A.快速排序B.堆排序C.歸并排序D.直接插入排序2、將兩個各有N個元素的有序表歸并成一個有序表，其最少的比較次數(shù)是（）。A.NB.2N-1C.2ND.N-13、算法的計算量的大小稱為計算的（）。A.效率B.復雜性C.現(xiàn)實性D.難度4、動態(tài)存儲管理系統(tǒng)中，通常可有（）種不同的分配策略。A.1B.2C.3D.45、有六個元素6，5，4，3，2，1順序入棧，下列不是合法的出棧序列的是（）。A.543612B.453126C.346521D.2341566、已知關(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，b，c，d，e，f依次進棧，允許進棧、退棧操作交替進行，但不允許連續(xù)三次進行退棧操作，則不可能得到的出棧序列是（）。8、一棵哈夫曼樹共有215個結(jié)點，對其進行哈夫曼編碼，共能得到（）個不同的碼字。A.107B.108C.214D.2159、有n（n>0）個分支結(jié)點的滿二叉樹的深度是（）。A.n2-1B.log2（n+1）+1C.log2（n+1）D.log2（n-l）10、對關(guān)鍵碼序列28，16，32，12，60，2，5，72快速排序，從小到大一次劃分結(jié)果為（）。A.（2，5，12，16）26（60，32，72）B.（5，16，2，12）28（60，32，72）C.（2，16，12，5）28（60，32，72）D.（5，16，2，12）28（32，60，72）二、填空題11、對n個記錄的表r[1..n]進行簡單選擇排序，所需進行的關(guān)鍵字間的比較次數(shù)為______。12、有向圖G=(V，E)，其中V(G)={0，1，2，3，4，5｝，用<a，b，d>三元組表示弧<a，b>及弧上的權(quán)d。E(G)為E(G)=｛<0，5，100>，<0，2，10>，<1，2，5>，<0，4，30>，<4，5，60>，<3，5，10>，<2，3，50>，<4，3，20>｝，則從源點0到頂點3的最短路徑長度是______，經(jīng)過的中間頂點是______。13、在單鏈表L中，指針P所指結(jié)點有后繼結(jié)點的條件是______。14、數(shù)據(jù)結(jié)構(gòu)是研討數(shù)據(jù)的______和______以及它們之間的相互關(guān)系，并對與這種結(jié)構(gòu)定義相應的______，設計出相應的______。15、文件可按其記錄的類型不同而分成兩類，即______和______文件。16、當兩個棧共享一存儲區(qū)時，棧利用一維數(shù)組stack（1，n）表示，兩棧頂指針為top[1]與top[2]，則當棧1空時，top[1]為______，棧2空時，top[2]為______，棧滿時為______。17、設正文串長度為n，模式串長度為m，則串匹配的KMP算法的時間復雜度為______。18、假設一個15階的上三角矩陣A按行優(yōu)先順序壓縮存儲在一維數(shù)組B中，則非零元素A9.9在B中的存儲位置k=______。（注：矩陣元素下標從1開始）三、判斷題19、對處理大量數(shù)據(jù)的外存介質(zhì)而言，索引順序存取方法是一種方便的文件組織方法。（）20、倒排文件的目的是為了多關(guān)鍵字查找。（）21、在鏈隊列中，即使不設置尾指針也能進行入隊操作。（）22、二維以上的數(shù)組其實是一種特殊的廣義表。（）23、若從二叉樹的任一結(jié)點出發(fā)，到根的路徑上所經(jīng)過的結(jié)點序列按其關(guān)鍵字有序，則該二叉樹一定是哈夫曼樹。（）24、樹形結(jié)構(gòu)中元素之間存在一對多的關(guān)系。（）25、在一個設有頭指針和尾指針的單鏈表中，執(zhí)行刪除該單鏈表中最后一個元素的操作與鏈表的長度無關(guān)。（）26、歸并排序輔助存儲為O（1）。（）27、對兩棵具有相同關(guān)鍵字集合的而形狀不同的二叉排序樹，按中序遍歷它們得到的序列的順序卻是一致的。（）28、有向圖中頂點V度等于其鄰接矩陣中第V行中的1的個數(shù)。（）四、簡答題29、請寫出應填入下列敘述中（）內(nèi)的正確答案。排序有各種方法，如插入排序、快速排序、堆排序等。設一數(shù)組中原有數(shù)據(jù)如下：15，13，20，18，12，60。下面是一組用不同排序方法進行一遍排序后的結(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，6030、用一個數(shù)組S（設大小為MAX）作為兩個堆棧的共享空間。請說明共享方法，棧滿／?？盏呐袛鄺l件，并用C語言或PASCAL語言設計公用的入棧操作push（i，x），其中i為0或1，用于表示棧號，x為入棧值。31、已知一個整數(shù)序列A＝（a0，a1，…，an－1），其中0≤ai＜n（0≤i≤n），若存在ap1＝ap2＝…＝apm＝x且m＞n/2（0≤pk≤n，1≤k≤m），則稱x為A的主元素。例如A＝（0，5，5，3，5，7，5，5），則稱5為主元素；又如A＝（0，5，5，3，5，1，5，7）則A中沒有主元素。假設A中的n個元素保存在一個一維數(shù)組中，請設計一個盡可能高效的算法，找出A的主元素。若存在主元素，則輸出該元素；否則輸出－1。要求：（1）給出算法的基本設計思想。（2）根據(jù)設計思想，采用C或C＋＋或Java語言描述算法，關(guān)鍵之處給出注釋。說明你所設計算法的時間復雜度和空間復雜度。五、算法設計題32、已知指針p指向帶表頭的中根次序線索二叉樹中的某結(jié)點，試寫一算法FFA（p，q），該算法尋找結(jié)點p的父親結(jié)點q。設線索二叉樹的結(jié)點結(jié)構(gòu)、表頭結(jié)點結(jié)構(gòu)和空樹結(jié)構(gòu)分別為（LTAG，LLINK，INFO，RLlNK，RTAG），且規(guī)定線索樹的最左下結(jié)點的LLINK域和最右下結(jié)點的RLINKt域指向表頭。33、設二叉樹用二指針結(jié)構(gòu)存儲（可以是動態(tài)存儲結(jié)構(gòu)），元素值為整數(shù)，且元素值無重復，請編寫子程序，求出以元素值等于某個給定的整數(shù)的結(jié)點為根的子樹中的各個葉結(jié)點。34、若x和y是兩個采用順序結(jié)構(gòu)存儲的串，編寫一個比較兩個串是否相等的函數(shù)。35、試為二叉樹寫出一個建立三叉鏈表的算法，并在此三叉鏈表中刪去每一個元素值為x的結(jié)點，以及以它為根的子樹，且釋放相應存儲空間。二叉樹的三叉鏈表的描述為：

參考答案一、選擇題1、【答案】C2、【答案】A3、【答案】B4、【答案】C5、【答案】C6、【答案】A7、【答案】D8、【答案】B9、【答案】C10、【答案】B二、填空題11、【答案】n（n-1）/212、【答案】50；413、【答案】P->next!=NULL14、【答案】邏輯結(jié)構(gòu)；物理結(jié)構(gòu)；操作（運算）；算法15、【答案】操作系統(tǒng)文件；數(shù)據(jù)庫16、【答案】0；n+1；top[1]+1=top[2]17、【答案】O（m+n）18、【答案】93三、判斷題19、【答案】×20、【答案】√21、【答案】√22、【答案】√23、【答案】×24、【答案】√25、【答案】×26、【答案】×27、【答案】√28、【答案】×四、簡答題29、答：①快速排序②起泡排序③直接插入排序④堆排序30、答：兩棧共享一向量空間（一維數(shù)組），棧底設在數(shù)組的兩端，兩棧頂相鄰時為棧滿。設共享數(shù)組為S[MAX]，則一個棧頂指針為一l，另一個棧頂指針為MAX時，棧為空。用C語言寫的入棧操作push（i，x）如下：31、答：（1）算法的策略是從前向后掃描數(shù)組元素，標記出一個可能成為主元素的元素Num。然后重新計數(shù)，確認Num是否是主元素。算法可分為以下兩步：①選取候選的主元素：依次掃描所給數(shù)組中的每個整數(shù)，將第一個遇到的整數(shù)Num保存到c中，記錄Num的出現(xiàn)次數(shù)為1；若遇到的下一個整數(shù)仍等于Num，則計數(shù)加1，否則計數(shù)減1；當計數(shù)減到0時，將遇到的下一個整數(shù)保存到c中，計數(shù)重新