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

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