2022年湖南工商大學計算機科學與技術專業(yè)《數(shù)據(jù)結構與算法》科目期末試卷A(有答案)

2022年湖南工商大學計算機科學與技術專業(yè)《數(shù)據(jù)結構與算法》科目期末試卷A（有答案）一、選擇題1、用有向無環(huán)圖描述表達式(A+B)*((A+B)／/A)，至少需要頂點的數(shù)目為（）。A.5B.6C.8D.92、下述文件中適合于磁帶存儲的是（）。A.順序文件B.索引文件C.哈希文件D.多關鍵字文件3、若某線性表最常用的操作是存取任一指定序號的元素和在最后進行插入和刪除運算，則利用（）存儲方式最節(jié)省時間。A.順序表B.雙鏈表C.帶頭結點的雙循環(huán)鏈表D.單循環(huán)鏈表4、在下列表述中，正確的是（）A.含有一個或多個空格字符的串稱為空格串B.對n（n>0）個頂點的網(wǎng)，求出權最小的n-1條邊便可構成其最小生成樹C.選擇排序算法是不穩(wěn)定的D.平衡二叉樹的左右子樹的結點數(shù)之差的絕對值不超過l5、已知串S='aaab'，其next數(shù)組值為（）。A.0123B.1123C.1231D.12116、若元素a，b，c，d，e，f依次進棧，允許進棧、退棧操作交替進行，但不允許連續(xù)三次進行退棧操作，則不可能得到的出棧序列是（）。7、排序過程中，對尚未確定最終位置的所有元素進行一遍處理稱為一趟排序。下列排序方法中，每一趟排序結束時都至少能夠確定一個元素最終位置的方法是（）。Ⅰ．簡單選擇排序Ⅱ．希爾排序Ⅲ．快速排序Ⅳ．堆排Ⅴ．二路歸并排序A．僅Ⅰ、Ⅲ、ⅣB．僅Ⅰ、Ⅱ、ⅢC．僅Ⅱ、Ⅲ、ⅣD．僅Ⅲ、Ⅳ、Ⅴ8、設X是樹T中的一個非根結點，B是T所對應的二叉樹。在B中，X是其雙親的右孩子，下列結論正確的是（）。A.在樹T中，X是其雙親的第一個孩子B.在樹T中，X一定無右兄弟C.在樹T中，X一定是葉結點D.在樹T中，X一定有左兄弟9、在下述結論中，正確的有（）。①只有一個結點的二叉樹的度為0。②二叉樹的度為2。③二叉樹的左右子樹可任意交換。④深度為K的完全二叉樹的結點個數(shù)小于或等于深度相同的滿二叉樹。A.①②③B.⑦③④C.②④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、以下程序的功能是實現(xiàn)帶附加頭結點的單鏈表數(shù)據(jù)結點逆序連接，請?zhí)羁胀晟浦?2、對單鏈表中元素按插入方法排序的C語言描述算法如下，其中L為鏈表頭結點指針。請?zhí)畛渌惴ㄖ袠顺龅目瞻滋?，完成其功能?3、按LSD進行關鍵字排序，除最次位關鍵字之外，對每個關鍵字進行排序時，只能用______的排序方法。14、在單鏈表L中，指針P所指結點有后繼結點的條件是______。15、關鍵碼序列（Q，H，C，Y，Q，A，M，S，R，D，F(xiàn)，X），要按照關鍵碼值遞增的次序進行排序，若采用初始步長為4的希爾排序法，則一趟掃描的結果是______；若采用以第一個元素為分界元素的快速排序法，則掃描一趟的結果是______。16、設有N個結點的完全二叉樹順序存放在向量A[1：N]中，其下標值最大的分支結點為______。17、模式串P=‘abaabcac’的next函數(shù)值序列為______。18、設有一個10階對稱矩陣A采用壓縮存儲方式（以行為主序存儲：a11=1），則a85的地址為______。三、判斷題19、倒排文件是對次關鍵字建立索引。（）20、文件系統(tǒng)采用索引結構是為了節(jié)省存儲空間。（）21、設棧采用順序存儲結構。若已有i-1個元素入棧，則將第i個元素入棧時，入棧算法的時間復雜性為O（i）。（）22、串是一種數(shù)據(jù)對象和操作都特殊的線性表。（）23、一個樹形的葉結點，在前序遍歷和后序遍歷下，皆以相同的相對位置出現(xiàn)。（）24、一般來說，若深度為k的n個結點的二叉樹只有最小路徑長度，那么從根結點到第k-1層具有的最多結點數(shù)為2k-1-1，余下的n-2k-1+1個結點在第k層的任一位置上。（）25、若中序遍歷平衡的二叉排序樹，可得到排好序的關鍵碼序列。（）26、在外部排序過程中，對長度為n的初始序列進行“置換-選擇”排序時，可以得到的最大初始有序段的長度不超過n/2。（）27、采用線性探測法處理散列時的沖突，當從哈希表刪除一個記錄時，不應將這個記錄的所在位置置空，因為這會影響以后的查找。（）28、若一個有向圖的鄰接矩陣對角線以下元素均為零，則該圖的拓撲有序序列必定存在。（）四、簡答題29、給出一組關鍵字：29，18，25，47，58，12，51，10，分別寫出按下列各種排序方法進行排序時的變化過程：（1） 歸并排序，每歸并一次書寫一個次序。（2） 快速排序，每劃分一次書寫一個次序。（3） 堆排序，先建成一個堆，然后每從堆頂取下一個元素后，將堆調整一次。30、將下列由三棵樹組成的森林轉換為二叉樹（只要求給出轉換結果）。31、用單鏈表保存m個整數(shù)，節(jié)點的結構為（data，link），且|data|＜n（n為正整數(shù)）?，F(xiàn)要求設計一個時間復雜度盡可能高效地算法，對于鏈表中絕對值相等的節(jié)點，僅保留第一次出現(xiàn)的節(jié)點而刪除其余絕對值相等的節(jié)點。例如若給定的單鏈表head如下刪除節(jié)點后的head為要求（1）給出算法的基本思想（2）使用C或C＋＋語言，給出單鏈表節(jié)點的數(shù)據(jù)類型定義。（3）根據(jù)設計思想，采用C或C＋＋語言描述算法，關鍵之處給出注釋。說明所涉及算法的時間復雜度和空間復雜度。五、算法設計題32、串以靜態(tài)存儲結構存儲，結構如下所述，試實現(xiàn)串操作equal算法。33、假設一個僅包含二元運算符的算術表達式以鏈表形式存儲在二叉樹BT中，寫出計算該算術表達式值的算法。34、假設以雙親表示法作樹的存儲結構，寫出雙親表示的類型說明，并編寫求給定的樹的深度的算法（注：已知樹中的結點數(shù)）。35、寫出按后序序列遍歷中序線索樹的算法。

參考答案一、選擇題1、【答案】A2、【答案】A3、【答案】A4、【答案】C5、【答案】A6、【答案】D7、【答案】A8、【答案】D9、【答案】D10、【答案】B二、填空題11、【答案】（1）p!=NULL//鏈表未到尾就一直進行（2）q//將當前結點作為頭結點后的第一元素結點插入12、【答案】（1）L->next=NULL//置空鏈表，然后將原鏈表結點逐個插入到有序表中（1） p!=NULL//當鏈表尚未到尾，p為工作指針（2） q!=NULL//查P結點在鏈表中的插入位置，這時q是工作指針（4）p->next=r->next//將P結點鏈入鏈表中（5）r->next=p//r是q的前驅，u是下個待插入結點的指針13、【答案】穩(wěn)定14、【答案】P->next!=NULL15、【答案】（Q，A，C，S，Q，D，F(xiàn)，X，R，H，M,Y）；（F，H，C，D，a，A，M，Q，R，S，Y，X）16、【答案】【解析】最大的分支結點是最后一個葉子結點的父結點。17、【答案】0112231218、【答案】33三、判斷題19、【答案】√20、【答案】×21、【答案】×22、【答案】√23、【答案】√24、【答案】√25、【答案】√26、【答案】×27、【答案】√28、【答案】√四、簡答題29、答：（1）2一路歸并第一趟：18，29，25，47，12，58，10，51。第二趟：18，25，29，47，10，12，51，58。第三趟：10，12，18，25，29，47，51，58。（2）快速排序第一趟：10，18，25，12，29，58，51，47。第二趟：10，18，25，12，29，47，51，88。第三趟：10，12，18，25，29，47，51，88。（3）堆排序建大堆：58，47，51，29，18，12，25，10。51，47，25，29，18，12，10，58。47，29，25，10，18，12，51，58。29，18，25，10，12，47，51，58。25，18，12，10，29，47，51，58。18，10，12，25，29，47，51，58。12，10，18，25，29，47，51，58。10，12，18，25，29，47，51，58。30、答：森林轉換為二叉樹分以下三步：連線（將兄弟結點相連，各樹的根看作兄弟）。切線（保留最左邊子女為獨生子女，將其他子女分支切掉）。旋轉（以最左邊樹的根為軸，順時針向下旋轉45度）。所以由上面三棵樹轉換得到的二叉樹如圖所示：31、答：（1）算法思想：算法的核心思想是用空間換時間。定義一個大小為n的布爾數(shù)組flag，初始時所有的元素都賦值為false，用來標識遍歷過程中是否出現(xiàn)元素絕對值為flag的節(jié)點。然后遍歷鏈表，遍歷過程中，每一個當前結點da