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ù)據(jù)元素進(jìn)行擴(kuò)充，允許帶結(jié)構(gòu)的線性表是（）。A.串B.樹C.廣義表D.棧2、將兩個(gè)各有N個(gè)元素的有序表歸并成一個(gè)有序表，其最少的比較次數(shù)是（）。A.NB.2N-1C.2ND.N-13、單鏈表中，增加一個(gè)頭結(jié)點(diǎn)是為了（）。A.使單鏈表至少有一個(gè)結(jié)點(diǎn)B.標(biāo)識(shí)表結(jié)點(diǎn)中首結(jié)點(diǎn)的位置C.方便運(yùn)算的實(shí)現(xiàn)D.說明單鏈表是線性表的鏈?zhǔn)酱鎯?chǔ)4、下列關(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ì)提前完成5、用不帶頭結(jié)點(diǎn)的單鏈表存儲(chǔ)隊(duì)列，其隊(duì)頭指針指向隊(duì)頭結(jié)點(diǎn)，隊(duì)尾指針指向隊(duì)尾結(jié)點(diǎn)，則在進(jìn)行出隊(duì)操作時(shí)（）。A.僅修改隊(duì)頭指針B.僅修改隊(duì)尾指針C.隊(duì)頭、隊(duì)尾指針都可能要修改D.隊(duì)頭、隊(duì)尾指針都要修改6、若一棵二叉樹的前序遍歷序列為a，e，b，d，c，后序遍歷序列為b，c，d，e，a，則根結(jié)點(diǎn)的孩子結(jié)點(diǎn)（）。A．只有eB．有e、bC．有e、cD．無法確定7、循環(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、一棵哈夫曼樹共有215個(gè)結(jié)點(diǎn)，對(duì)其進(jìn)行哈夫曼編碼，共能得到（）個(gè)不同的碼字。A.107B.108C.214D.21510、一組記錄的關(guān)鍵碼為（46，79，56，38，40，84），則利用快速排序的方法，以第一個(gè)記錄為基準(zhǔn)得到的一次劃分結(jié)果為（）。A.（38，40，46，56，79，84）B.（40，38，46，79，56，84）C.（40，38，46，56，79，84）D.（40，38，46，84，56，79）二、填空題11、在哈希函數(shù)H（key）=key%p中，p值最好取______。12、分別采用堆排序，快速排序，起泡排序和歸并排序，對(duì)初態(tài)為有序的表，則最省時(shí)間的是______算法，最費(fèi)時(shí)間的是______算法。13、設(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í)行以下語句：______14、在基于關(guān)鍵字比較且時(shí)間為O（nlog2n）的排序中，若要求排序是穩(wěn)定的，則可選用______排序；若要求就地排序（及輔助空間為O（1）），則可選用______排序。15、數(shù)據(jù)結(jié)構(gòu)中評(píng)價(jià)算法的兩個(gè)重要指標(biāo)是______。16、下列程序是快速排序的非遞歸算法，請(qǐng)?zhí)顚戇m當(dāng)?shù)恼Z句，完成該功能。17、模式串P=‘a(chǎn)baabcac’的next函數(shù)值序列為______。18、每一棵樹都能唯一地轉(zhuǎn)換為它所對(duì)應(yīng)的二叉樹。若已知一棵二叉樹的前序序列是BEFCGDH，中序序列是FEBGCHD，則它的后序序列是______。設(shè)上述二叉樹是由某棵樹轉(zhuǎn)換而成，則該樹的前序序列是______。三、判斷題19、倒排文件的目的是為了多關(guān)鍵字查找。（）20、倒排文件是對(duì)次關(guān)鍵字建立索引。（）21、循環(huán)隊(duì)列也存在空間溢出問題。（）22、在鏈隊(duì)列中，即使不設(shè)置尾指針也能進(jìn)行入隊(duì)操作。（）23、任何二叉樹的后序線索樹進(jìn)行后序遍歷時(shí)都必須用棧。（）24、哈夫曼樹度為1的結(jié)點(diǎn)數(shù)等于度為2和0的結(jié)點(diǎn)數(shù)之差。（）25、在外部排序過程中，對(duì)長(zhǎng)度為n的初始序列進(jìn)行“置換-選擇”排序時(shí)，可以得到的最大初始有序段的長(zhǎng)度不超過n/2。（）26、算法的優(yōu)劣與算法描述語言無關(guān)，但與所用計(jì)算機(jī)有關(guān)。（）27、若一個(gè)有向圖的鄰接矩陣對(duì)角線以下元素均為零，則該圖的拓?fù)溆行蛐蛄斜囟ù嬖?。（?8、無環(huán)有向圖才能進(jìn)行拓?fù)渑判颉＃ǎ┧?、?jiǎn)答題29、對(duì)于具有n個(gè)葉結(jié)點(diǎn)且所有非葉結(jié)點(diǎn)都有左、右孩子的二叉樹。(1)試問這種二叉樹的結(jié)點(diǎn)總數(shù)是多少?(2)試證明2-（li-1）=1。其中：li表示第i個(gè)葉結(jié)點(diǎn)所在的層號(hào)（設(shè)根結(jié)點(diǎn)所在層號(hào)為1）。30、將下列由三棵樹組成的森林轉(zhuǎn)換為二叉樹（只要求給出轉(zhuǎn)換結(jié)果）。31、設(shè)二叉樹BT的存儲(chǔ)結(jié)構(gòu)如表：其中BT為樹根結(jié)點(diǎn)的指針，其值為6，Lchild、Rchild分別為結(jié)點(diǎn)的左、右孩子指針域data為結(jié)點(diǎn)的數(shù)據(jù)域。試完成下列各題：（1）畫出二叉樹BT邏輯結(jié)構(gòu)。（2）寫出按前序、中序、后序遍歷該二叉樹所得到的結(jié)點(diǎn)序列。（3）畫出二叉樹的后序線索樹。五、算法設(shè)計(jì)題32、設(shè)A[1..100]是一個(gè)記錄構(gòu)成的數(shù)組，B[1..100]是一個(gè)整數(shù)數(shù)組，其值介于l～100之間，現(xiàn)要求按B[1..100]的內(nèi)容調(diào)整A中記錄的次序，比如當(dāng)B[1]=11時(shí)，則要求將A[1]的內(nèi)容調(diào)整到A[11]中去。規(guī)定可使用的附加空間為O（1）。33、已知二叉樹丁的結(jié)點(diǎn)形式為（llink，data，count，rlink），在樹中查找值為X的結(jié)點(diǎn)，若找到，則記數(shù)（count）加1；否則，作為一個(gè)新結(jié)點(diǎn)插入樹中，插入后仍為二叉排序樹，寫出其非遞歸算法。34、按圖的寬度優(yōu)先搜索法寫一算法判別以鄰接矩陣存儲(chǔ)的有向圖中是否存在由頂點(diǎn)Vi到頂點(diǎn)Vj的路徑(i≠j)35、在二叉排序樹的結(jié)構(gòu)中，有些數(shù)據(jù)元素值可能是相同的，設(shè)計(jì)一個(gè)算法實(shí)現(xiàn)按遞增有序打印結(jié)點(diǎn)的數(shù)據(jù)域，要求相同的數(shù)據(jù)元素僅輸出一個(gè)，算法還應(yīng)能報(bào)出最后被濾掉而未輸出的數(shù)據(jù)元素個(gè)數(shù)，對(duì)如圖所示的二叉排序樹，輸出為：10，12，13，15，18，21，27，35，42．濾掉3個(gè)元素。

參考答案一、選擇題1、【答案】C2、【答案】A3、【答案】C4、【答案】B5、【答案】C6、【答案】A7、【答案】A8、【答案】D9、【答案】B10、【答案】C二、填空題11、【答案】小于等于表長(zhǎng)的最大素?cái)?shù)或不包含小于20的質(zhì)因子的合數(shù)12、【答案】起泡；快速13、【答案】py->next=px->next；px->next=py14、【答案】歸并；堆15、【答案】算法的時(shí)間復(fù)雜度和空間復(fù)雜度16、【答案】a[j]=a[k]；low=stack[top][0]；stack[top][0]=k+1【解析】快速排序(quicksort)的基本思想是，通過一趟排序?qū)⒋庞涗浄指畛瑟?dú)立的兩部分，其中一部分記錄的關(guān)鍵字均比另一部分記錄的關(guān)鍵字小，則可分別對(duì)這兩部分記錄繼續(xù)進(jìn)行排序，以達(dá)到整個(gè)序列有序。17、【答案】0112231218、【答案】FEGHDCB；BEF【解析】樹的前序序列對(duì)應(yīng)二叉樹的前序序列，該二叉樹轉(zhuǎn)換成森林時(shí)含三棵樹，其第一棵樹的前序是BEF。三、判斷題19、【答案】√20、【答案】√21、【答案】√22、【答案】√23、【答案】×24、【答案】×25、【答案】×26、【答案】×27、【答案】√28、【答案】√四、簡(jiǎn)答題29、答：（1）根據(jù)二叉樹中度為2的結(jié)點(diǎn)個(gè)數(shù)等于葉結(jié)點(diǎn)個(gè)數(shù)減1的性質(zhì)，故具有n個(gè)葉結(jié)點(diǎn)且非葉子結(jié)點(diǎn)均有左子樹的二叉樹的結(jié)點(diǎn)數(shù)是2n-1。（2）證明：當(dāng)i=1時(shí)，2-（1-1）=20=1，公式成立。設(shè)當(dāng)i=n-1時(shí)公式成立，證明當(dāng)i=n時(shí)公式仍成立。設(shè)某葉結(jié)點(diǎn)的層號(hào)為t，當(dāng)將該結(jié)點(diǎn)變?yōu)閮?nèi)部結(jié)點(diǎn)，從而再增加兩個(gè)葉結(jié)點(diǎn)時(shí)，這兩個(gè)葉結(jié)點(diǎn)的層號(hào)都是t+1，對(duì)于公式的變化，是減少了一個(gè)原來的葉結(jié)點(diǎn)，增加了兩個(gè)新葉結(jié)點(diǎn)，反映到公式中，因?yàn)?-（t-1）=2-（t+1-1）+2-（t+1-1），所以結(jié)果不變，這就證明當(dāng)i=n時(shí)公式仍成立。證畢。30、答：森林轉(zhuǎn)換為二叉樹分以下三步：連線（將兄弟結(jié)點(diǎn)相連，各樹的根看作兄弟）。切線（保留最左邊子女為獨(dú)生子女，將其他子女分支切掉）。旋轉(zhuǎn)（以最左邊樹的根為