2022年長安大學計算機科學與技術專業(yè)《數據結構與算法》科目期末試卷A(有答案)

2022年長安大學計算機科學與技術專業(yè)《數據結構與算法》科目期末試卷A〔有答案〕一、選擇題1、有一個100*90的稀疏矩陣，非0元素有10個，設每個整型數占2字節(jié)，那么用三元組表示該矩陣時，所需的字節(jié)數是〔〕。A.60B.66C.18000D.332、n個結點的完全有向圖含有邊的數目〔〕。A.n*nB.n(n+1)C.n/2D.n*(n-1)3、某線性表中最常用的操作是在最后一個元素之后插入一個元素和刪除第一個元素，那么采用〔〕存儲方式最節(jié)省運算時間。A.單鏈表B.僅有頭指針的單循環(huán)鏈表C.雙鏈表D.僅有尾指針的單循環(huán)鏈表4、最大容量為n的循環(huá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個記錄的連續(xù)順序文件中采用順序查找法查找一個記錄，其平均查找長度ASL為〔〕。A.(n-1)/2B.n/2C.(n+1)/2D.n二、填空題11、順序查找n個元素的順序表，假設查找成功，那么比擬關鍵字的次數最多為______次；當使用監(jiān)視哨時，假設查找失敗，那么比擬關鍵字的次數為______。12、起始地址為480，大小為8的塊，其伙伴塊的起始地址是______；假設塊大小為32，那么其伙伴塊的起始地址為______。13、有序表為〔12，18，24，35，47，50，62，83，90，115，134〕當用二分法查找90時，需______次查找成功，查找47時______成功，查找100時，需______次才能確定不成功。14、在雙向循環(huán)鏈表中，向p所指的結點之后插入指針f所指的結點，其操作是______、______、______、______。15、VSAM〔虛擬存儲存取方法〕文件的優(yōu)點是：動態(tài)地______，不需要文件進行______，并能較快地______進行查找。16、以下程序是快速排序的非遞歸算法，請?zhí)顚戇m當的語句，完成該功能。17、設正文串長度為n，模式串長度為m，那么串匹配的KMP算法的時間復雜度為______。18、鏈隊列的頭尾指針分別是f和r，那么將值x入隊的操作序列是______。三、判斷題19、倒排文件是對次關鍵字建立索引?！病?0、直接訪問文件也能順序訪問，只是一般效率不高?！病?1、數組不適合作為任何二叉樹的存儲結構?！病?2、廣義表〔〔〔a，b，c〕，d，e，f〕〕的長度是4?！病?3、對于有n個結點的二叉樹，其高度為log2n?！病?4、一般來說，假設深度為k的n個結點的二叉樹只有最小路徑長度，那么從根結點到第k-1層具有的最多結點數為2k-1-1，余下的n-2k-1+1個結點在第k層的任一位置上。〔〕25、數據元素是數據的最小單位?！病?6、在用堆排序算法排序時，如果要進行增序排序，那么需要采用“大根堆”?！病?7、當改變網上某一關鍵路徑上任一關鍵活動后，必將產生不同的關鍵路徑。〔〕28、假設一個有向圖的鄰接矩陣對角線以下元素均為零，那么該圖的拓撲有序序列必定存在。〔〕四、簡答題29、三維數組A[1..10，-2..6，2..8]的每個元素的長度為4個字節(jié)，試問該數組要占多少個字節(jié)的存儲空間?如果數組元素以行優(yōu)先的順序存儲，設第一個元素的首地址是100，試求元素A[5，0，7]的存儲首地址。30、用一個數組S〔設大小為MAX〕作為兩個堆棧的共享空間。請說明共享方法，棧滿／?？盏呐袛鄺l件，并用C語言或PASCAL語言設計公用的入棧操作push〔i，x〕，其中i為0或1，用于表示棧號，x為入棧值。31、圖的鄰接矩陣為：當用鄰接表作為圖的存儲結構，且鄰接點都按序號從大到小排列時，試寫出：(1)以頂點V1為出發(fā)點的唯一的深度優(yōu)先遍歷序列。當用鄰接表作為圖的存儲結構，且鄰接點都按序號從大到小排列時，試寫出：(1)以頂點V1為出發(fā)點的唯一的深度優(yōu)先遍歷序列。(2)以頂點V1為出發(fā)點的唯一的廣度優(yōu)先遍歷序列。(3)該圖唯一的拓撲有序序列。五、算法設計題32、假設一個僅包含二元運算符的算術表達式以鏈表形式存儲在二叉樹BT中，寫出計算該算術表達式值的算法。33、令G=(V，E)為一個有向無環(huán)圖，編寫一個給圖G中每一個頂點賦以一個整數序號的算法，并滿足以下條件：假設從頂點i至頂點j有一條弧，那么應使i<j。34、假設x和y是兩個采用順序結構存儲的串，編寫一個比擬兩個串是否相等的函數。35、一棵高度為K具有n個結點的二叉樹，按順序方式存儲。〔1〕編寫用前序遍歷樹中每個結點的非遞歸算法?！?〕編寫將樹中最大序號葉結點的祖先結點全部打印輸出的算法。參考答案一、選擇題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)的根本思想是，通過一趟排序將待排記錄分割成獨立的兩局部，其中一局部記錄的關鍵字均比另一局部記錄的關鍵字小，那么可分別對這兩局部記錄繼續(xù)進行排序，以到達整個序列有序。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、答：數組占的存儲字節(jié)數=10*9*7*4=2520；A[5，0，7]的存儲地址=100+[4*9*7+2*7+5]*4=1184。30、答：兩棧共享一向量空間〔一維數組〕，棧底設在數組的兩端，兩棧頂相鄰時為棧滿。設共享數組為S[MAX]，那么一個棧頂指針為一l，另一個棧頂指針為MAX時，棧為空。用C語言寫的入