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

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

參考答案一、選擇題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、【答案】分配和釋放存儲(chǔ)空間；重組；對(duì)插入的記錄@16、【答案】a[j]=a[k]；low=stack[top][0]；stack[top][0]=k+1【解析】快速排序(quicksort)的基本思想是，通過(guò)一趟排序?qū)⒋庞涗浄指畛瑟?dú)立的兩部分，其中一部分記錄的關(guān)鍵字均比另一部分記錄的關(guān)鍵字小，則可分別對(duì)這兩部分記錄繼續(xù)進(jìn)行排序，以達(dá)到整個(gè)序列有序。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、【答案】√四、簡(jiǎn)答題29、答：數(shù)組占的存儲(chǔ)字節(jié)數(shù)=10*9*7*4=2520；A[5，0，7]的存儲(chǔ)地址=100+[4*9*7+2*7+5]*4=1184。30、答：兩棧共享一向量空間（一維數(shù)組），棧底設(shè)在數(shù)組的兩端，兩棧頂相鄰時(shí)為棧滿。設(shè)共享數(shù)組為S[MAX]，則一個(gè)棧頂指針為一l，另一個(gè)棧頂指針為MAX時(shí)，棧為空。用C語(yǔ)言寫的