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

2022年廣東海洋大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)《數(shù)據(jù)結(jié)構(gòu)與算法》科目期末試卷A（有答案）一、選擇題1、用數(shù)組r存儲(chǔ)靜態(tài)鏈表，結(jié)點(diǎn)的next域指向后繼，工作指針j指向鏈中結(jié)點(diǎn)，使j沿鏈移動(dòng)的操作為（）。A.j=r[j].nextB.j=j+lC.j=j->nextD.j=r[j]->next2、已知廣義表LS=（（a，b，c），（d，e，f）），用head和tail數(shù)取出LS中原子e的運(yùn)算是（）。A.head（tail（LS））B.tail（head（LS））C.head（tail（head（tail（LS））））D.head（tail（tail（head（LS））））3、若某線性表最常用的操作是存取任一指定序號(hào)的元素和在最后進(jìn)行插入和刪除運(yùn)算，則利用（）存儲(chǔ)方式最節(jié)省時(shí)間。A.順序表B.雙鏈表C.帶頭結(jié)點(diǎn)的雙循環(huán)鏈表D.單循環(huán)鏈表4、動(dòng)態(tài)存儲(chǔ)管理系統(tǒng)中，通常可有（）種不同的分配策略。A.1B.2C.3D.45、已知有向圖G=(V，E)，其中V={V1，V2，V3，V4，V5，V6，V7}，E=｛<V1，V2>，<V1，V3>，<V1，V4>，<V2，V5>，<V3，V5>，<V3，V6>，<V4，V6>，<V5，V7>，<V6，V7>｝，G的拓?fù)湫蛄惺牵ǎ?。A.V1，V3，V4，V6，V2，V5，V7B.V1，V3，V2，V6，V4，V5，V7C.V1，V3，V5，V2，V6，V7D.V1，V2，V5，V3，V4，V6，V76、已知字符串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、循環(huán)隊(duì)列放在一維數(shù)組A中，end1指向隊(duì)頭元素，end2指向隊(duì)尾元素的后一個(gè)位置。假設(shè)隊(duì)列兩端均可進(jìn)行入隊(duì)和出隊(duì)操作，隊(duì)列中最多能容納M－1個(gè)元素。初始時(shí)為空，下列判斷隊(duì)空和隊(duì)滿的條件中，正確的是（）。A．隊(duì)空：end1＝＝end2；隊(duì)滿：end1＝＝（end2＋1）modMB．隊(duì)空：end1＝＝end2；隊(duì)滿：end2＝＝（end1＋1）mod（M－1）C．隊(duì)空：end2＝＝（end1＋1）modM；隊(duì)滿：end1＝＝（end2＋1）modMD．隊(duì)空：end1＝＝（end2＋1）modM；隊(duì)滿：end2＝＝（end1＋1）mod（M－1）8、每個(gè)結(jié)點(diǎn)的度或者為0或者為2的二叉樹稱為正則二叉樹。n個(gè)結(jié)點(diǎn)的正則二叉樹中有（）個(gè)葉子。A.log2nB.（n－1）/2C.log2n+1D.（n＋1）/29、設(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一定有左兄弟10、對(duì)n個(gè)記錄的線性表進(jìn)行快速排序?yàn)闇p少算法的遞歸深度，以下敘述正確的是（）。A.每次分區(qū)后，先處理較短的部分B.每次分區(qū)后，先處理較長(zhǎng)的部分C.與算法每次分區(qū)后的處理順序無(wú)關(guān)D.以上三者都不對(duì)二、填空題11、N個(gè)頂點(diǎn)的連通圖用鄰接矩陣表示時(shí)，該矩陣至少有______個(gè)非零元素。12、設(shè)用希爾排序?qū)?shù)組{98，36，-9，0，47，23，1，8，10，7}進(jìn)行排序，給出的步長(zhǎng)（也稱增量序列）依次是4，2，1則排序需______趟，寫出第一趟結(jié)束后，數(shù)組中數(shù)據(jù)的排列次序______。13、以下是用類C語(yǔ)言寫出的算法，該算法將以二叉鏈表存儲(chǔ)的二叉樹中的葉結(jié)點(diǎn)按從左到右的順序鏈成一個(gè)帶頭結(jié)點(diǎn)的雙向循環(huán)鏈表，鏈接時(shí)，結(jié)點(diǎn)的Lchild域作為前鏈域，指向結(jié)點(diǎn)的直接前驅(qū)，結(jié)點(diǎn)的Rchild域作為后鏈域，指向結(jié)點(diǎn)的直接后繼。算法中，使用一個(gè)順序棧stack，棧頂指針為top，p，t為輔助指針，head為雙向循環(huán)鏈表的頭指針。試填充算法中的空格，使算法完整。14、設(shè)單鏈表的結(jié)點(diǎn)結(jié)構(gòu)為（data，next），next為指針域，已知指針px指向單鏈表中data為x的結(jié)點(diǎn)，指針py指向data為y的新結(jié)點(diǎn)，若將結(jié)點(diǎn)y插入結(jié)點(diǎn)x之后，則需要執(zhí)行以下語(yǔ)句：______15、文件可按其記錄的類型不同而分成兩類，即______和______文件。16、設(shè)有N個(gè)結(jié)點(diǎn)的完全二叉樹順序存放在向量A[1：N]中，其下標(biāo)值最大的分支結(jié)點(diǎn)為______。17、設(shè)數(shù)組a[1..50，1..80]的基地址為2000，每個(gè)元素占2個(gè)存儲(chǔ)單元，若以行序?yàn)橹餍蝽樞虼鎯?chǔ)，則元素a[45，68]的存儲(chǔ)地址為______；若以列序?yàn)橹餍蝽樞虼鎯?chǔ)，則元素a[45，68]的存儲(chǔ)地址為______。18、當(dāng)兩個(gè)棧共享一存儲(chǔ)區(qū)時(shí)，棧利用一維數(shù)組stack（1，n）表示，兩棧頂指針為top[1]與top[2]，則當(dāng)棧1空時(shí)，top[1]為______，棧2空時(shí)，top[2]為______，棧滿時(shí)為______。三、判斷題19、倒排文件是對(duì)次關(guān)鍵字建立索引。（）20、對(duì)磁帶機(jī)而言，ISAM是一種方便的文件組織方法（）21、隊(duì)列和棧都是運(yùn)算受限的線性表，只允許在表的兩端進(jìn)行運(yùn)算。（）22、循環(huán)隊(duì)列也存在空間溢出問(wèn)題。（）23、若從二叉樹的任一結(jié)點(diǎn)出發(fā)，到根的路徑上所經(jīng)過(guò)的結(jié)點(diǎn)序列按其關(guān)鍵字有序，則該二叉樹一定是哈夫曼樹。（）24、二叉樹是一般樹的特殊情形。（）25、為提高排序速度，進(jìn)行外排序時(shí)，必須選用最快的內(nèi)排序算法。（）26、外部排序是把外存文件調(diào)入內(nèi)存，可利用內(nèi)部排序的方法進(jìn)行排序，因此排序所花的時(shí)間取決于內(nèi)部排序的時(shí)間。（）27、對(duì)大小均為n的有序表和無(wú)序表分別進(jìn)行順序查找，在等概率查找的情況下，對(duì)于查找成功，它們的平均查找長(zhǎng)度是相同的，而對(duì)于查找失敗，它們的平均查找長(zhǎng)度是不同的。（）28、無(wú)環(huán)有向圖才能進(jìn)行拓?fù)渑判?。（）四、?jiǎn)答題29、假定對(duì)有序表：（3，4，5，7，24，30，42，54，63，72，87，95）進(jìn)行折半查找，試回答下列問(wèn)題：（1）畫出描述折半查找過(guò)程的判定樹。（2）若查找元素54，需依次與哪些元素比較?（3）若查找元素90，需依次與哪些元素比較?（4）假定每個(gè)元素的查找概率相等，求查找成功時(shí)的平均查找長(zhǎng)度。30、將下列由三棵樹組成的森林轉(zhuǎn)換為二叉樹（只要求給出轉(zhuǎn)換結(jié)果）。31、設(shè)將n（n＞1）個(gè)整數(shù)存放到一維數(shù)組R中。試設(shè)計(jì)一個(gè)在時(shí)間和空間兩方面都盡可能高效的算法，將R中存有的序列循左移P（0＜P＜n）個(gè)位置，即將R中的數(shù)據(jù)由（X0，X1，…，Xn－1）變換為（xp，xp＋1，…，xn－1，x0，x1，…，xp－1）。要求：（1） 給出算法的基本設(shè)計(jì)思想。（2） 根據(jù)設(shè)計(jì)思想，采用C或C＋＋或JAVA語(yǔ)言描述算法，關(guān)鍵之處給出注釋。說(shuō)明你所設(shè)計(jì)算法的時(shí)間復(fù)雜度和空間復(fù)雜度。五、算法設(shè)計(jì)題32、若x和y是兩個(gè)采用順序結(jié)構(gòu)存儲(chǔ)的串，編寫一個(gè)比較兩個(gè)串是否相等的函數(shù)。33、給定一個(gè)整數(shù)數(shù)組b[0..N-1]，b中連續(xù)的相等元素構(gòu)成的子序列稱為平臺(tái)。試設(shè)計(jì)算法，求出b中最長(zhǎng)平臺(tái)的長(zhǎng)度。34、在一個(gè)循環(huán)鏈隊(duì)中只有尾指針（記為rear，結(jié)點(diǎn)結(jié)構(gòu)為數(shù)據(jù)域data，指針域next），請(qǐng)給出這種隊(duì)列的入隊(duì)和出隊(duì)操作的實(shí)現(xiàn)過(guò)程。35、編寫對(duì)有序表進(jìn)行順序查找的算法，并畫出對(duì)有序表進(jìn)行順序查找的判定樹。假設(shè)每次查找時(shí)的給定值為隨機(jī)值，又查找成功和不成功的概率也相等，試求進(jìn)行每一次查找時(shí)和給定值進(jìn)行比較的關(guān)鍵字個(gè)數(shù)的期望值。

參考答案一、選擇題1、【答案】A2、【答案】C3、【答案】A4、【答案】C5、【答案】A6、【答案】C7、【答案】A8、【答案】D9、【答案】D10、【答案】A二、填空題11、【答案】2(N-1)12、【答案】3；（10，7，-9，0，47，23，1，8，98，36）@13、【答案】p->Rchild=t；t->Lchild=p；p=t；t->Rchild!=null；t->Rchild；t->Lchild!=null；t->Lchild；p->Rchild=head；head->Lchild=p14、【答案】py->next=px->next；px->next=py15、【答案】操作系統(tǒng)文件；數(shù)據(jù)庫(kù)16、【答案】【解析】最大的分支結(jié)點(diǎn)是最后一個(gè)葉子結(jié)點(diǎn)的父結(jié)點(diǎn)。17、【答案】9174；878818、【答案】0；n+1；top[1]+1=top[2]三、判斷題19、【答案】√20、【答案】×21、【答案】×22、【答案】√23、【答案】×24、【答案】×25、【答案】×26、【答案】×27、【答案】√28、【答案】√四、簡(jiǎn)答題29、答：（1）判定樹如圖所示：（2） 若查找元素54，需依次和元素30、63、42、54比較，查找成功。（3） 若查找元素90，需依次和元素30、63、87、95比較，查找失敗。（4）30、答：森林轉(zhuǎn)換為二叉樹分以下三步：連線（將兄弟結(jié)點(diǎn)相連，各樹的根看作兄弟）。切線（保留最左邊子女為獨(dú)生子女，將其他子女分支切掉）。旋轉(zhuǎn)（以最左邊樹的根為軸，順時(shí)針向下旋轉(zhuǎn)45度）。所以由上面三棵樹轉(zhuǎn)換得到的二叉樹如圖所示：31、答：（1）算法的基本設(shè)計(jì)思想：先將n個(gè)數(shù)據(jù)由x0，x1，…，xp，…，xn－1原地逆置，得到xn－1，…，xp，xp－1，…，x0然后再將數(shù)組R中的前n－P個(gè)數(shù)和后P個(gè)數(shù)分別原地逆置，最終得到結(jié)果xp，xp＋1，…，xn－1，x0，x1，…，xp－1。（2）用C語(yǔ)言算法描述如下：（3）說(shuō)明算法的復(fù)雜性：上述算法中3個(gè)Reverse函數(shù)的時(shí)間復(fù)雜度分別為O（p/2）、