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

2022年福州大學計算機科學與技術專業(yè)《數(shù)據(jù)結(jié)構(gòu)與算法》科目期末試卷A（有答案）一、選擇題1、下列排序算法中，占用輔助空間最多的是（）。A.歸并排序B.快速排序C.希爾排序D.堆排序2、哈希文件使用哈希函數(shù)將記錄的關鍵字值計算轉(zhuǎn)化為記錄的存放地址，因為哈希函數(shù)是一對一的關系，則選擇好的（）方法是哈希文件的關鍵。A.哈希函數(shù)B.除余法中的質(zhì)數(shù)C.沖突處理D.哈希函數(shù)和沖突處理3、若線性表最常用的操作是存取第i個元素及其前驅(qū)和后繼元素的值，為節(jié)省時間應采用的存儲方式（）。A.單鏈表B.雙向鏈表C.單循環(huán)鏈表D.順序表4、循環(huán)隊列A[0..m-1]存放其元素值，用front和rear分別表示隊頭和隊尾，則當前隊列中的元素數(shù)是（）。A.（rear-front+m）%mB.rear-front+1C.rear-front-1D.rear-front5、在用鄰接表表示圖時，拓撲排序算法時間復雜度為（）。A.O(n)B.O(n+e)C.O(n*n)D.O(n*n*n)6、已知字符串S為“abaabaabacacaabaabcc”，模式串t為“abaabc”，采用KMP算法進行匹配，第一次出現(xiàn)“失配”（s!＝t）時，i＝j＝5，則下次開始匹配時，i和j的值分別（）。A．i＝1，j＝0B．i＝5，j＝0C．i＝5，j＝2D．i＝6，j＝27、循環(huán)隊列放在一維數(shù)組A中，end1指向隊頭元素，end2指向隊尾元素的后一個位置。假設隊列兩端均可進行入隊和出隊操作，隊列中最多能容納M－1個元素。初始時為空，下列判斷隊空和隊滿的條件中，正確的是（）。A．隊空：end1＝＝end2；隊滿：end1＝＝（end2＋1）modMB．隊空：end1＝＝end2；隊滿：end2＝＝（end1＋1）mod（M－1）C．隊空：end2＝＝（end1＋1）modM；隊滿：end1＝＝（end2＋1）modMD．隊空：end1＝＝（end2＋1）modM；隊滿：end2＝＝（end1＋1）mod（M－1）8、下述二叉樹中，哪一種滿足性質(zhì)：從任一結(jié)點出發(fā)到根的路徑上所經(jīng)過的結(jié)點序列按其關鍵字有序（）。A.二叉排序樹B.哈夫曼樹C.AVL樹D.堆9、一棵哈夫曼樹共有215個結(jié)點，對其進行哈夫曼編碼，共能得到（）個不同的碼字。A.107B.108C.214D.21510、對{05，46，13，55，94，17，42}進行基數(shù)排序，一趟排序的結(jié)果是：A.05，46，13，55，94，17，42B.05，13，17，42，46，55.94C.42，13，94，05，55，46，17D.05，13，46，55，17，42，94二、填空題11、以下程序的功能是實現(xiàn)帶附加頭結(jié)點的單鏈表數(shù)據(jù)結(jié)點逆序連接，請?zhí)羁胀晟浦?2、在有n個頂點的有向圖中，每個頂點的度最大可達______。13、外排序的基本操作過程是______和______。14、文件可按其記錄的類型不同而分成兩類，即______和______文件。15、已知有序表為（12，18，24，35，47，50，62，83，90，115，134）當用二分法查找90時，需______次查找成功，查找47時______成功，查找100時，需______次才能確定不成功。16、設正文串長度為n，模式串長度為m，則串匹配的KMP算法的時間復雜度為______。17、在順序存儲的二叉樹中，編號為i和j的兩個結(jié)點處在同一層的條件是______。18、已知鏈隊列的頭尾指針分別是f和r，則將值x入隊的操作序列是______。三、判斷題19、對處理大量數(shù)據(jù)的外存介質(zhì)而言，索引順序存取方法是一種方便的文件組織方法。（）20、倒排序文件的優(yōu)點是維護簡單。（）21、廣義表（（（a，b，c），d，e，f））的長度是4。（）22、數(shù)組不適合作為任何二叉樹的存儲結(jié)構(gòu)。（）23、任何二叉樹的后序線索樹進行后序遍歷時都必須用棧。（）24、一棵樹中的葉子數(shù)一定等于與其對應的二叉樹的葉子數(shù)。（）25、順序存儲方式的優(yōu)點是存儲密度大，且插入、刪除運算效率高。（）26、排序算法中的比較次數(shù)與初始元素序列的排列無關。（）27、在索引順序表中，實現(xiàn)分塊查找，在等概率查找情況下，其平均查找長度不僅與表中元素個數(shù)有關，而且與每塊中元素個數(shù)有關。（）28、對大小均為n的有序表和無序表分別進行順序查找，在等概率查找的情況下，對于查找成功，它們的平均查找長度是相同的，而對于查找失敗，它們的平均查找長度是不同的。（）四、簡答題29、閱讀下面的算法，說明算法實現(xiàn)的功能。30、用一個數(shù)組S（設大小為MAX）作為兩個堆棧的共享空間。請說明共享方法，棧滿／?？盏呐袛鄺l件，并用C語言或PASCAL語言設計公用的入棧操作push（i，x），其中i為0或1，用于表示棧號，x為入棧值。31、二叉樹的帶權路徑長度（WPL）是二叉樹中所有葉結(jié)點的帶權路徑長度之和，給定一棵二叉樹T，采用二叉鏈表存儲，節(jié)點結(jié)構(gòu)為：其中葉節(jié)點的weight域保存該結(jié)點的非負權值。設root為指向T的根節(jié)點的指針，設計求T的WPL的算法。要求：（1）給出算法的基本設計思想。（2）使用C或C++語言，給出二叉樹結(jié)點的數(shù)據(jù)類型定義。（3）根據(jù)設計思想，采用C或C++語言描述算法，關鍵之處給出注釋。五、算法設計題32、給出以十字鏈表作存儲結(jié)構(gòu)，建立圖的算法，輸入(i，j，v)，其中i，j為頂點號，v為權值。33、已知二叉樹丁的結(jié)點形式為（llink，data，count，rlink），在樹中查找值為X的結(jié)點，若找到，則記數(shù)（count）加1；否則，作為一個新結(jié)點插入樹中，插入后仍為二叉排序樹，寫出其非遞歸算法。34、設二叉樹用二指針結(jié)構(gòu)存儲（可以是動態(tài)存儲結(jié)構(gòu)），元素值為整數(shù)，且元素值無重復，請編寫子程序，求出以元素值等于某個給定的整數(shù)的結(jié)點為根的子樹中的各個葉結(jié)點。35、在輸入數(shù)據(jù)無序的情況下，建立一個數(shù)據(jù)值為整型的遞增有序的順序存儲線性表L，且要求當輸入相同數(shù)據(jù)值時，線性表中不能存在數(shù)據(jù)值相同的數(shù)據(jù)元素，試寫出其算法。順序存儲結(jié)構(gòu)的線性表描述為：

參考答案一、選擇題1、【答案】A2、【答案】D3、【答案】D4、【答案】A5、【答案】B6、【答案】C7、【答案】A8、【答案】D9、【答案】B10、【答案】C二、填空題11、【答案】（1）p!=NULL//鏈表未到尾就一直進行（2）q//將當前結(jié)點作為頭結(jié)點后的第一元素結(jié)點插入12、【答案】2(n-1)13、【答案】生成有序歸并段（順串）；歸并14、【答案】操作系統(tǒng)文件；數(shù)據(jù)庫15、【答案】2；4；3【解析】二分法查找元素次數(shù)列表查找100是找到115就停止了。16、【答案】O（m+n）17、【答案】++a*b3*4-cd；18【解析】中綴式相當于中序遍歷，前綴式相當于前序遍歷，后綴式相當于后序遍歷。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、答：本算法功能是將兩個無頭結(jié)點的循環(huán)鏈表合并為一個循環(huán)鏈表。head1最后一個結(jié)點的鏈域指向head2，head2最后一個結(jié)點的鏈域指向head1，head1為結(jié)果循環(huán)鏈表的指針。30、答：兩棧共享一向量空間（一維數(shù)組），棧底設在數(shù)組的兩端，兩棧頂相鄰時為棧滿。設共享數(shù)組為S[MAX]，則一個棧頂指針為一l，另一個棧頂指針為MAX時，棧為空。用C語言寫的入棧操作push（i，x）如下：31、答：