2022年長安大學計算機科學與技術專業《數據結構與算法》科目期末試卷A（有答案）一、選擇題1、有一個100*90的稀疏矩陣，非0元素有10個，設每個整型數占2字節，則用三元組表示該矩陣時，所需的字節數是（）。A.60B.66C.18000D.332、n個結點的完全有向圖含有邊的數目（）。A.n*nB.n(n+1)C.n/2D.n*(n-1)3、某線性表中最常用的操作是在最后一個元素之后插入一個元素和刪除第一個元素，則采用（）存儲方式最節省運算時間。A.單鏈表B.僅有頭指針的單循環鏈表C.雙鏈表D.僅有尾指針的單循環鏈表4、最大容量為n的循環隊列，隊尾指針是rear，隊頭：front，則隊空的條件是（）。A.（rear+1）MODn=frontB.rear=frontC.rear+1=frontD.（rear-1）MODn=front5、下列關于AOE網的敘述中，不正確的是（）。A.關鍵活動不按期完成就會影響整個工程的完成時間B.任何一個關鍵活動提前完成，那么整個工程將會提前完成C.所有的關鍵活動提前完成，那么整個工程將會提前完成D.某些關鍵活動若提前完成，那么整個工程將會提前完成6、已知字符串S為“abaabaabacacaabaabcc”，模式串t為“abaabc”，采用KMP算法進行匹配，第一次出現“失配”（s!＝t）時，i＝j＝5，則下次開始匹配時，i和j的值分別（）。A．i＝1，j＝0B．i＝5，j＝0C．i＝5，j＝2D．i＝6，j＝27、下列選項中，不能構成折半查找中關鍵字比較序列的是（）。A．500，200，450，180B．500，450，200，180C．180，500，200，450D．180，200，500，4508、設X是樹T中的一個非根結點，B是T所對應的二叉樹。在B中，X是其雙親的右孩子，下列結論正確的是（）。A.在樹T中，X是其雙親的第一個孩子B.在樹T中，X一定無右兄弟C.在樹T中，X一定是葉結點D.在樹T中，X一定有左兄弟9、已知一棵二叉樹的前序遍歷結果為ABCDEF，中序遍歷結果為CBAEDF，則后序遍歷結果為（）。A.CBEFDAB.FEDCBAC.CBEDFAD.不定10、若查找每個記錄的概率均等，則在具有n個記錄的連續順序文件中采用順序查找法查找一個記錄，其平均查找長度ASL為（）。A.(n-1)/2B.n/2C.(n+1)/2D.n二、填空題11、順序查找n個元素的順序表，若查找成功，則比較關鍵字的次數最多為______次；當使用監視哨時，若查找失敗，則比較關鍵字的次數為______。12、起始地址為480，大小為8的塊，其伙伴塊的起始地址是______；若塊大小為32，則其伙伴塊的起始地址為______。13、已知有序表為（12，18，24，35，47，50，62，83，90，115，134）當用二分法查找90時，需______次查找成功，查找47時______成功，查找100時，需______次才能確定不成功。14、在雙向循環鏈表中，向p所指的結點之后插入指針f所指的結點，其操作是______、______、______、______。15、VSAM（虛擬存儲存取方法）文件的優點是：動態地______，不需要文件進行______，并能較快地______進行查找。16、下列程序是快速排序的非遞歸算法，請填寫適當的語句，完成該功能。17、設正文串長度為n，模式串長度為m，則串匹配的KMP算法的時間復雜度為______。18、已知鏈隊列的頭尾指針分別是f和r，則將值x入隊的操作序列是______。三、判斷題19、倒排文件是對次關鍵字建立索引。（）20、直接訪問文件也能順序訪問，只是一般效率不高。（）21、數組不適合作為任何二叉樹的存儲結構。（）22、廣義表（（（a，b，c），d，e，f））的長度是4。（）23、對于有n個結點的二叉樹，其高度為log2n。（）24、一般來說，若深度為k的n個結點的二叉樹只有最小路徑長度，那么從根結點到第k-1層具有的最多結點數為2k-1-1，余下的n-2k-1+1個結點在第k層的任一位置上。（）25、數據元素是數據的最小單位。（）26、在用堆排序算法排序時，如果要進行增序排序，則需要采用“大根堆”。（）27、當改變網上某一關鍵路徑上任一關鍵活動后，必將產生不同的關鍵路徑。（）28、若一個有向圖的鄰接矩陣對角線以下元素均為零，則該圖的拓撲有序序列必定存在。（）四、簡答題29、三維數組A[1..10，-2..6，2..8]的每個元素的長度為4個字節，試問該數組要占多少個字節的存儲空間?如果數組元素以行優先的順序存儲，設第一個元素的首地址是100，試求元素A[5，0，7]的存儲首地址。30、用一個數組S（設大小為MAX）作為兩個堆棧的共享空間。請說明共享方法，棧滿／棧空的判斷條件，并用C語言或PASCAL語言設計公用的入棧操作push（i，x），其中i為0或1，用于表示棧號，x為入棧值。31、已知圖的鄰接矩陣為：當用鄰接表作為圖的存儲結構，且鄰接點都按序號從大到小排列時，試寫出：(1)以頂點V1為出發點的唯一的深度優先遍歷序列。當用鄰接表作為圖的存儲結構，且鄰接點都按序號從大到小排列時，試寫出：(1)以頂點V1為出發點的唯一的深度優先遍歷序列。(2)以頂點V1為出發點的唯一的廣度優先遍歷序列。(3)該圖唯一的拓撲有序序列。五、算法設計題32、假設一個僅包含二元運算符的算術表達式以鏈表形式存儲在二叉樹BT中，寫出計算該算術表達式值的算法。33、令G=(V，E)為一個有向無環圖，編寫一個給圖G中每一個頂點賦以一個整數序號的算法，并滿足以下條件：若從頂點i至頂點j有一條弧，則應使i<j。34、若x和y是兩個采用順序結構存儲的串，編寫一個比較兩個串是否相等的函數。35、已知一棵高度為K具有n個結點的二叉樹，按順序方式存儲。（1）編寫用前序遍歷樹中每個結點的非遞歸算法。（2）編寫將樹中最大序號葉結點的祖先結點全部打印輸出的算法。

參考答案一、選擇題1、【答案】B2、【答案】D3、【答案】D4、【答案】B5、【答案】B6、【答案】C7、【答案】A8、【答案】D9、【答案】A10、【答案】C二、填空題11、【答案】n；n+112、【答案】480+8=488；480-32=44813、【答案】2；4；3【解析】二分法查找元素次數列表查找100是找到115就停止了。14、【答案】f->next=p->next；f->prior=p；p->next->prior=f；p->next=f。15、【答案】分配和釋放存儲空間；重組；對插入的記錄@16、【答案】a[j]=a[k]；low=stack[top][0]；stack[top][0]=k+1【解析】快速排序(quicksort)的基本思想是，通過一趟排序將待排記錄分割成獨立的兩部分，其中一部分記錄的關鍵字均比另一部分記錄的關鍵字小，則可分別對這兩部分記錄繼續進行排序，以達到整個序列有序。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、答：數組占的存儲字節數=10*9*7*4=2520；A[5，0，7]的存儲地址=100+[4*9*7+2*7+5]*4=1184。30、答：兩棧共享一向量空間（一維數組），棧底設在數組的兩端，兩棧頂相鄰時為棧滿。設共享數組為S[MAX]，則一個棧頂指針為一l，另一個棧頂指針為MAX時，棧為空。用C語言寫的