呼倫貝爾學(xué)院《數(shù)據(jù)結(jié)構(gòu)》2021-2022學(xué)年期末試卷

裝訂線裝訂線PAGE2第1頁(yè)，共3頁(yè)呼倫貝爾學(xué)院

《數(shù)據(jù)結(jié)構(gòu)》2021-2022學(xué)年期末試卷院(系)_______班級(jí)_______學(xué)號(hào)_______姓名_______題號(hào)一二三總分得分批閱人一、單選題（本大題共20個(gè)小題，每小題2分，共40分．在每小題給出的四個(gè)選項(xiàng)中，只有一項(xiàng)是符合題目要求的．）1、在一個(gè)具有n個(gè)頂點(diǎn)的無(wú)向圖中，若存在從頂點(diǎn)i到頂點(diǎn)j的路徑，同時(shí)也存在從頂點(diǎn)j到頂點(diǎn)i的路徑，則該圖被稱為？（）A.強(qiáng)連通圖B.弱連通圖C.連通圖D.非連通圖2、已知一個(gè)有序表為{5,10,15,20,25,30,35,40,45,50}，使用折半查找法查找值為35的元素，需要比較的次數(shù)是（）。A.1B.2C.3D.43、以下關(guān)于線性表的描述，正確的是：A.線性表的元素在邏輯上和存儲(chǔ)上都必須是連續(xù)的B.線性表只能采用順序存儲(chǔ)結(jié)構(gòu)C.線性表的長(zhǎng)度是固定不變的D.線性表可以是空表，即不含任何元素4、在一個(gè)順序存儲(chǔ)的循環(huán)隊(duì)列中，隊(duì)頭指針front和隊(duì)尾指針rear都指向同一個(gè)位置時(shí)，隊(duì)列的狀態(tài)可能是？（）A.隊(duì)滿B.隊(duì)空C.既不滿也不空D.以上都有可能5、以下哪種數(shù)據(jù)結(jié)構(gòu)可以方便地實(shí)現(xiàn)字典操作（添加、刪除、查找），且平均時(shí)間復(fù)雜度較低？A.數(shù)組B.鏈表C.二叉搜索樹(shù)D.哈希表6、以下哪種數(shù)據(jù)結(jié)構(gòu)常用于實(shí)現(xiàn)圖的廣度優(yōu)先遍歷的輔助隊(duì)列？A.循環(huán)隊(duì)列B.鏈隊(duì)列C.優(yōu)先隊(duì)列D.雙端隊(duì)列7、對(duì)于一個(gè)具有n個(gè)頂點(diǎn)的無(wú)向完全圖，其邊的數(shù)量為多少？（）A.n(n-1)/2B.n(n-1)C.n2D.2n8、在一個(gè)具有n個(gè)元素的順序表中，若要在第i個(gè)元素之前插入一個(gè)新元素，平均需要移動(dòng)多少個(gè)元素？（）A.n/2B.nC.iD.n-i9、在一個(gè)用數(shù)組實(shí)現(xiàn)的最大堆中，若要增加一個(gè)元素并調(diào)整堆，以下操作正確的是？（）A.將元素放在堆尾，然后從堆尾向上調(diào)整B.將元素放在堆頂，然后從堆頂向下調(diào)整C.將元素插入任意位置，然后重新構(gòu)建堆D.以上都不對(duì)10、數(shù)據(jù)結(jié)構(gòu)的抽象數(shù)據(jù)類型（ADT）是一種定義數(shù)據(jù)結(jié)構(gòu)的方式，它包括數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)和操作集合。以下關(guān)于ADT的說(shuō)法中，錯(cuò)誤的是？（）A.ADT使得數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)與使用分離，提高了代碼的可維護(hù)性和可擴(kuò)展性。B.ADT可以用多種編程語(yǔ)言實(shí)現(xiàn)，不同的實(shí)現(xiàn)方式可能會(huì)有不同的性能和特點(diǎn)。C.ADT的操作集合包括插入、刪除、查找、遍歷等基本操作。D.ADT只適用于線性數(shù)據(jù)結(jié)構(gòu)，不適用于非線性數(shù)據(jù)結(jié)構(gòu)。11、在一個(gè)具有n個(gè)頂點(diǎn)的有向圖中，若所有頂點(diǎn)的出度之和為m，入度之和為k，則m和k之間的關(guān)系是？（）A.m=kB.m>kC.m<kD.m+k=n12、在一個(gè)具有n個(gè)元素的無(wú)序數(shù)組中，采用冒泡排序進(jìn)行排序，在最壞情況下，需要比較的次數(shù)為（）。A.n-1B.n(n-1)/2C.n(n+1)/2D.n^213、在一個(gè)具有n個(gè)頂點(diǎn)的無(wú)向完全圖中，邊的數(shù)量為？（）A.n(n-1)/2B.n(n-1)C.n2D.2n(n-1)14、在循環(huán)鏈表中，尾指針rear指向鏈表的尾節(jié)點(diǎn)，若要在鏈表中插入一個(gè)新的節(jié)點(diǎn)，使其成為新的尾節(jié)點(diǎn)，以下操作正確的是？（）A.rear->next=new_node;new_node->next=rear;rear=new_node;B.new_node->next=rear;rear->next=new_node;rear=new_node;C.rear=new_node;new_node->next=rear->next;rear->next=new_node;D.new_node->next=rear->next;rear->next=new_node;15、在一個(gè)具有n個(gè)節(jié)點(diǎn)的二叉樹(shù)中，若采用后序遍歷得到的節(jié)點(diǎn)序列是ABC，中序遍歷序列是BAC，則先序遍歷序列是什么？A.CABB.ABCC.ACBD.無(wú)法確定16、若對(duì)一棵二叉排序樹(shù)進(jìn)行中序遍歷，得到的節(jié)點(diǎn)序列是一個(gè)遞增序列，則該二叉排序樹(shù)（）。A.沒(méi)有左子樹(shù)B.沒(méi)有右子樹(shù)C.左子樹(shù)均為空D.右子樹(shù)均為空17、一棵哈夫曼樹(shù)中，葉子節(jié)點(diǎn)的編碼長(zhǎng)度一定（）非葉子節(jié)點(diǎn)的編碼長(zhǎng)度。A.大于B.等于C.小于D.不小于18、在一個(gè)循環(huán)鏈表中，若要?jiǎng)h除鏈表中的最后一個(gè)節(jié)點(diǎn)，需要的時(shí)間復(fù)雜度為（）A.O(1)B.O(logn)C.O(n)D.O(nlogn)19、在數(shù)據(jù)結(jié)構(gòu)中，對(duì)于一個(gè)具有n個(gè)元素的有序數(shù)組，使用二分查找算法查找一個(gè)特定元素，其平均時(shí)間復(fù)雜度為（）A.O(n)B.O(logn)C.O(nlogn)D.O(n^2)20、以下哪種數(shù)據(jù)結(jié)構(gòu)能夠高效地支持區(qū)間查詢操作？（）A.線段樹(shù)B.二叉搜索樹(shù)C.堆D.鏈表二、簡(jiǎn)答題（本大題共4個(gè)小題，共40分)1、（本題10分）深入解釋在鏈表中，如何實(shí)現(xiàn)頭插法和尾插法創(chuàng)建鏈表，并比較它們?cè)诓煌瑘?chǎng)景下的優(yōu)缺點(diǎn)。2、（本題10分）在數(shù)據(jù)結(jié)構(gòu)中，闡述如何使用樹(shù)狀數(shù)組進(jìn)行區(qū)間查詢和單點(diǎn)更新，給出算法步驟和實(shí)現(xiàn)代碼，并分析其性能優(yōu)勢(shì)。3、（本題10分）解釋什么是塊狀數(shù)組數(shù)據(jù)結(jié)構(gòu)，說(shuō)明其特點(diǎn)和應(yīng)用場(chǎng)景，并闡述如何進(jìn)行訪問(wèn)和修改操作。4、（本題10分）深入探討在一個(gè)具有n個(gè)元素的循環(huán)隊(duì)列中，如何有效地判斷隊(duì)列是否已滿。三、設(shè)計(jì)題（本大題共2個(gè)小題，共20分)1、（本題