常州大學(xué)《數(shù)據(jù)結(jié)構(gòu)》2021-2022學(xué)年期末試卷

裝訂線裝訂線PAGE2第1頁，共3頁常州大學(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、對(duì)于一個(gè)有向圖，使用鄰接矩陣存儲(chǔ)，判斷是否存在從頂點(diǎn)i到頂點(diǎn)j的邊的時(shí)間復(fù)雜度為（）A.O(1)B.O(n)C.O(logn)D.O(n^2)2、對(duì)于單鏈表，若要訪問鏈表中的第i個(gè)元素，必須從鏈表的頭指針開始依次遍歷，平均時(shí)間復(fù)雜度為O(n)。那么如果要在鏈表的末尾添加一個(gè)新元素，時(shí)間復(fù)雜度是多少？（）A.O(1)B.O(n)C.O(logn)D.O(nlogn)3、在一棵平衡二叉樹中，插入一個(gè)新節(jié)點(diǎn)后可能導(dǎo)致失衡，需要進(jìn)行調(diào)整。以下哪種調(diào)整操作可能涉及到旋轉(zhuǎn)次數(shù)最多？（）A.LL型調(diào)整B.RR型調(diào)整C.LR型調(diào)整D.RL型調(diào)整4、在一個(gè)具有n個(gè)節(jié)點(diǎn)的帶權(quán)有向圖中，若存在負(fù)權(quán)邊，以下哪種最短路徑算法可能不適用？A.迪杰斯特拉算法B.貝爾曼-福特算法C.弗洛伊德算法D.以上都適用5、對(duì)于一個(gè)采用鏈表存儲(chǔ)的棧，若要獲取棧的大?。ㄔ?cái)?shù)量），以下關(guān)于操作的時(shí)間復(fù)雜度的描述，哪一個(gè)是準(zhǔn)確的？A.O(1)B.O(logn)C.O(n)D.O(nlogn)6、樹是一種非線性數(shù)據(jù)結(jié)構(gòu)，它由節(jié)點(diǎn)和邊組成。以下關(guān)于樹的說法中，錯(cuò)誤的是？（）A.樹中的每個(gè)節(jié)點(diǎn)都有一個(gè)父節(jié)點(diǎn)（除了根節(jié)點(diǎn)）和零個(gè)或多個(gè)子節(jié)點(diǎn)。B.二叉樹是一種特殊的樹，每個(gè)節(jié)點(diǎn)最多有兩個(gè)子節(jié)點(diǎn)。C.樹可以用于實(shí)現(xiàn)文件系統(tǒng)、數(shù)據(jù)庫索引等。D.樹的遍歷方式只有前序遍歷、中序遍歷和后序遍歷三種。7、在一個(gè)哈希表中，若采用線性探測(cè)法解決哈希沖突，當(dāng)發(fā)生沖突時(shí)，新元素會(huì)存儲(chǔ)在什么位置？A.沖突位置的下一個(gè)位置B.沖突位置C.隨機(jī)位置D.以上都不對(duì)8、設(shè)有一個(gè)廣義表L=(a,(b,c),d)，其長度和深度分別為？（）A.3和2B.3和3C.4和2D.4和39、棧和隊(duì)列在計(jì)算機(jī)科學(xué)中有很多應(yīng)用，以下關(guān)于它們的應(yīng)用場(chǎng)景的說法中，錯(cuò)誤的是？（）A.?？梢杂糜趯?shí)現(xiàn)表達(dá)式求值、括號(hào)匹配等。B.隊(duì)列可以用于實(shí)現(xiàn)任務(wù)調(diào)度、消息隊(duì)列等。C.棧和隊(duì)列可以用于實(shí)現(xiàn)圖的深度優(yōu)先搜索和廣度優(yōu)先搜索。D.棧和隊(duì)列只能在編程語言的底層實(shí)現(xiàn)中使用，不能在實(shí)際應(yīng)用中直接使用。10、在一個(gè)鏈?zhǔn)酱鎯?chǔ)的隊(duì)列中，進(jìn)行入隊(duì)和出隊(duì)操作時(shí)，指針的移動(dòng)方向分別是（）A.入隊(duì)向前，出隊(duì)向后B.入隊(duì)向后，出隊(duì)向前C.均向前D.均向后11、在一棵平衡二叉樹中，插入一個(gè)新結(jié)點(diǎn)后，可能需要進(jìn)行的調(diào)整操作是：A.左旋B.右旋C.左旋和右旋D.不需要調(diào)整12、設(shè)有一個(gè)具有n個(gè)頂點(diǎn)的有向圖，采用鄰接表存儲(chǔ)。若要計(jì)算每個(gè)頂點(diǎn)的出度，以下關(guān)于操作的時(shí)間復(fù)雜度的描述，哪一項(xiàng)是恰當(dāng)?shù)?？A.O(n)B.O(n+e)C.O(n^2)D.O(e)13、對(duì)于一個(gè)用鏈表實(shí)現(xiàn)的棧，若要獲取棧中元素的個(gè)數(shù)，以下哪種方法效率較高？A.遍歷鏈表B.維護(hù)一個(gè)計(jì)數(shù)器C.以上效率相同D.以上都不對(duì)14、在一個(gè)具有n個(gè)節(jié)點(diǎn)的無向圖中，若邊的數(shù)量遠(yuǎn)遠(yuǎn)小于n(n-1)/2，則適合使用哪種存儲(chǔ)方式？A.鄰接矩陣B.鄰接表C.十字鏈表D.以上都可以15、在一個(gè)具有n個(gè)節(jié)點(diǎn)的二叉樹中，若采用后序遍歷得到的節(jié)點(diǎn)序列是ABC，中序遍歷序列是BAC，則先序遍歷序列是什么？A.CABB.ABCC.ACBD.無法確定16、在一個(gè)具有n個(gè)節(jié)點(diǎn)的無向圖中，若要判斷兩個(gè)節(jié)點(diǎn)之間是否存在路徑，可以使用哪種算法？A.深度優(yōu)先搜索B.廣度優(yōu)先搜索C.普里姆算法D.克魯斯卡爾算法17、對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的無向圖，采用鄰接表存儲(chǔ)，若要?jiǎng)h除一條邊，平均需要修改多少個(gè)指針？（）A.1B.2C.eD.2e18、以下哪種排序算法在平均情況下的時(shí)間復(fù)雜度最優(yōu)？A.冒泡排序B.快速排序C.插入排序D.選擇排序19、在一個(gè)鏈?zhǔn)酱鎯?chǔ)的隊(duì)列中，若隊(duì)頭指針為front，隊(duì)尾指針為rear，要?jiǎng)h除隊(duì)頭元素，需要進(jìn)行的操作是？（）A.front=front->next;B.rear=front;C.rear=rear->next;D.front=NULL;20、對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的無向圖，若采用鄰接表存儲(chǔ)，則其空間復(fù)雜度為：A.O(n)B.O(n+e)C.O(n^2)D.O(e^2)二、簡答題（本大題共4個(gè)小題，共40分)1、（本題10分）深入解釋在鏈表中，如何實(shí)現(xiàn)頭插法和尾插法創(chuàng)建鏈表，并比較它們?cè)诓煌瑘?chǎng)景下的優(yōu)缺點(diǎn)。2、（本題10分）解釋如何在一個(gè)帶權(quán)無向圖中計(jì)算任意兩個(gè)頂點(diǎn)之間路徑的最大權(quán)值和最小值之差。3、（本題10分）詳細(xì)論述在利用二叉樹進(jìn)行后序線索化的過程中，如何建立線索和遍歷線索二叉樹，并給出相應(yīng)的算法步驟和代碼示例。4、（本題10分）解釋在鏈表中刪除一個(gè)節(jié)點(diǎn)時(shí)，如何正確更新指針以保持鏈表的完整性，并舉例說明。三、設(shè)計(jì)題（本大