北京城市學院《數(shù)據(jù)結(jié)構(gòu)課程設(shè)計》2021-2022學年期末試卷

裝訂線裝訂線PAGE2第1頁，共3頁北京城市學院《數(shù)據(jù)結(jié)構(gòu)課程設(shè)計》

2021-2022學年期末試卷院(系)_______班級_______學號_______姓名_______題號一二三總分得分一、單選題（本大題共20個小題，每小題2分，共40分．在每小題給出的四個選項中，只有一項是符合題目要求的．）1、在一個具有n個頂點的無向圖中，若要判斷兩個頂點之間是否存在路徑，使用哪種算法較為合適？A.迪杰斯特拉算法B.弗洛伊德算法C.深度優(yōu)先遍歷或廣度優(yōu)先遍歷D.拓撲排序2、對于一個具有n個元素的循環(huán)隊列，隊頭指針為front，隊尾指針為rear，隊列滿的條件是？（）A.(rear+1)%MaxSize==frontB.rear==frontC.rear+1==frontD.(rear-1)%MaxSize==front3、對于一個具有n個頂點的無向圖，若其邊的集合為{(1,2),(1,3),(2,3),(2,4),(3,4)}，則該圖的鄰接表存儲中，頂點2的鏈表中包含的頂點有：A.1,3,4B.1,3C.3,4D.1,44、對于一個具有n個節(jié)點的線索二叉樹，若n個節(jié)點中有m個空指針域，則線索的數(shù)量為？A.mB.m/2C.n+1D.n-15、對于一棵二叉樹，先序遍歷序列為ABC，中序遍歷序列為BAC，則其后序遍歷序列為？A.BCAB.CBAC.ACBD.ABC6、在一個鏈式存儲的棧中，若要在棧頂插入一個元素，需要的時間復(fù)雜度為（）A.O(1)B.O(logn)C.O(n)D.O(nlogn)7、在一個具有n個元素的線性表中，采用順序查找法查找一個特定元素，若查找成功，平均查找長度為？（）A.(n+1)/2B.n/2C.lognD.n8、對于一個具有n個頂點的無向圖，若采用鄰接矩陣表示，則矩陣中非零元素的個數(shù)至少為：A.n-1B.nC.2(n-1)D.2n9、一個具有n個頂點和e條邊的無向圖，采用鄰接表存儲，其空間復(fù)雜度為？（）A.O(n+e)B.O(n^2)C.O(e^2)D.O(n^2+e)10、在一個具有n個元素的循環(huán)鏈表中，查找第i個元素（1<=i<=n），平均需要比較的次數(shù)為（）。A.nB.n/2C.(n+1)/2D.(n-1)/211、在一個具有n個元素的循環(huán)隊列中，若隊頭指針為front，隊尾指針為rear，且rear<front，則隊列中的元素個數(shù)為？A.rear-frontB.front-rearC.(rear-front+n)%nD.(front-rear+n)%n12、對于一個具有n個節(jié)點的二叉樹，若度為0的節(jié)點有n0個，度為1的節(jié)點有n1個，度為2的節(jié)點有n2個，則n0與n1、n2之間的關(guān)系為？A.n0=n1+n2B.n0=n2-1C.n0=n1-1D.n0=n2+113、對于一個棧，若入棧序列為1、2、3、4、5，在入棧過程中可以出棧，則下列不可能的出棧序列是：A.54321B.45321C.12345D.3142514、在二叉搜索樹中，每個節(jié)點的值都大于其左子樹中所有節(jié)點的值，小于其右子樹中所有節(jié)點的值。以下關(guān)于二叉搜索樹的操作，不正確的是（）A.插入操作需要按照節(jié)點值的大小找到合適的位置B.查找操作的時間復(fù)雜度在最壞情況下為O(n)C.刪除節(jié)點時，如果該節(jié)點有兩個子節(jié)點，可以選擇其左子樹中的最大節(jié)點或右子樹中的最小節(jié)點進行替換D.二叉搜索樹總是平衡的，即左右子樹的高度差不超過115、在一個具有n個元素的棧中，若要獲取棧底元素但不刪除，需要進行多少次操作？（）A.1B.n-1C.nD.n+116、對于一個具有n個頂點和e條邊的有向圖，采用鄰接表存儲，進行深度優(yōu)先遍歷。以下關(guān)于遍歷的時間復(fù)雜度的描述，哪一個是恰當?shù)?？A.O(n+e)B.O(n^2)C.O(e^2)D.O(n^3)17、二叉樹是一種重要的數(shù)據(jù)結(jié)構(gòu)，具有多種遍歷方式。對于先序遍歷、中序遍歷和后序遍歷，以下描述錯誤的是（）A.先序遍歷先訪問根節(jié)點，然后遞歸遍歷左子樹和右子樹B.中序遍歷先遞歸遍歷左子樹，然后訪問根節(jié)點，最后遞歸遍歷右子樹C.后序遍歷先遞歸遍歷左子樹和右子樹，最后訪問根節(jié)點D.這三種遍歷方式的結(jié)果總是相同的18、在一個具有n個節(jié)點的二叉樹中，若采用后序遍歷得到的節(jié)點序列是ABC，中序遍歷序列是BAC，則先序遍歷序列是什么？A.CABB.ABCC.ACBD.無法確定19、在一個帶頭結(jié)點的循環(huán)鏈表中，若要判斷鏈表是否為空，應(yīng)檢查？（）A.頭結(jié)點的指針是否為空B.頭結(jié)點的下一個結(jié)點的指針是否指向頭結(jié)點C.尾結(jié)點的指針是否為空D.尾結(jié)點的下一個結(jié)點的指針是否指向頭結(jié)點20、對于一個具有n個頂點和e條邊的無向圖，采用鄰接表存儲時，其空間復(fù)雜度為？（）A.O(n)B.O(e)C.O(n+e)D.O(n2)二、簡答題（本大題共4個小題，共40分)1、（本題10分）解釋數(shù)據(jù)結(jié)構(gòu)中棧的應(yīng)用場景，如表達式的前綴、中綴、后綴轉(zhuǎn)換等，并說明其原理。2、（本題10分）論述在一個具有n個元素的鏈表中，如何將兩個有序鏈表合并為一個有序鏈表。3、（本題10分）鏈表的雙向鏈表的插入和刪除操作與單向鏈表有何不同？請詳細描述其實現(xiàn)過程。4、（本題10分）鏈表的循環(huán)鏈表有哪些特點和應(yīng)用場景？如何判斷一個鏈表是否為