遼寧石油化工大學(xué)《數(shù)據(jù)結(jié)構(gòu)語言》2021-2022學(xué)年期末試卷

自覺遵守考場紀(jì)律如考試作弊此答卷無效密自覺遵守考場紀(jì)律如考試作弊此答卷無效密封線第1頁，共3頁遼寧石油化工大學(xué)

《數(shù)據(jù)結(jié)構(gòu)語言》2021-2022學(xué)年期末試卷院(系)_______班級_______學(xué)號_______姓名_______題號一二三總分得分批閱人一、單選題（本大題共20個(gè)小題，每小題2分，共40分．在每小題給出的四個(gè)選項(xiàng)中，只有一項(xiàng)是符合題目要求的．）1、設(shè)有一個(gè)帶權(quán)無向圖，采用Prim算法生成最小生成樹。在算法執(zhí)行過程中，每次選擇的邊都是權(quán)值最小的邊。以下關(guān)于Prim算法的時(shí)間復(fù)雜度的描述，哪一項(xiàng)是準(zhǔn)確的？A.O(n)B.O(n^2)C.O(nlogn)D.O(elogv)（其中n為頂點(diǎn)數(shù)，e為邊數(shù)）2、以下關(guān)于圖的遍歷算法的描述，哪一項(xiàng)是正確的？（）A.深度優(yōu)先遍歷和廣度優(yōu)先遍歷都能訪問到圖中的所有節(jié)點(diǎn)B.深度優(yōu)先遍歷適合用于求解最短路徑問題C.廣度優(yōu)先遍歷的空間復(fù)雜度低于深度優(yōu)先遍歷D.兩種遍歷算法的時(shí)間復(fù)雜度都與圖的邊數(shù)成正比3、在一棵度為4的樹中，若有20個(gè)度為4的節(jié)點(diǎn)，10個(gè)度為3的節(jié)點(diǎn)，1個(gè)度為2的節(jié)點(diǎn)，10個(gè)葉子節(jié)點(diǎn)，那么這棵樹的總節(jié)點(diǎn)數(shù)是多少？A.82B.81C.79D.784、對于一個(gè)具有n個(gè)節(jié)點(diǎn)的完全二叉樹，若按照層次遍歷的順序?qū)⒐?jié)點(diǎn)編號為1到n，已知編號為i的節(jié)點(diǎn)有左孩子，則其左孩子的編號為？A.2iB.2i+1C.i*2D.i/25、圖的存儲方式和遍歷方式可以用于解決很多實(shí)際問題，以下關(guān)于它們的應(yīng)用的說法中，錯誤的是？（）A.圖的鄰接矩陣可以用于表示網(wǎng)絡(luò)中的連接關(guān)系，適用于社交網(wǎng)絡(luò)分析和交通網(wǎng)絡(luò)規(guī)劃等。B.圖的鄰接表可以用于表示稀疏圖，適用于地圖繪制和電路圖設(shè)計(jì)等。C.圖的遍歷方式可以用于解決路徑規(guī)劃、網(wǎng)絡(luò)流問題和最小生成樹問題等，適用于物流配送和通信網(wǎng)絡(luò)優(yōu)化等。D.圖的存儲方式和遍歷方式只適用于理論研究，在實(shí)際應(yīng)用中沒有實(shí)際價(jià)值。6、數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)科學(xué)中重要的基礎(chǔ)課程，它研究數(shù)據(jù)的組織、存儲和管理方式。以下關(guān)于數(shù)據(jù)結(jié)構(gòu)的說法中，錯誤的是？（）A.數(shù)據(jù)結(jié)構(gòu)可以分為線性結(jié)構(gòu)和非線性結(jié)構(gòu)兩大類。B.線性結(jié)構(gòu)包括數(shù)組、鏈表、棧和隊(duì)列等。C.非線性結(jié)構(gòu)包括樹、圖和集合等。D.數(shù)據(jù)結(jié)構(gòu)只與編程語言有關(guān)，與實(shí)際應(yīng)用場景無關(guān)。7、在一個(gè)具有n個(gè)元素的最小堆中，插入一個(gè)新元素并調(diào)整為最小堆，其時(shí)間復(fù)雜度為？A.O(1)B.O(logn)C.O(n)D.O(nlogn)8、對于一個(gè)循環(huán)隊(duì)列，若隊(duì)頭指針為front，隊(duì)尾指針為rear，隊(duì)列最大容量為MAX_SIZE，那么判斷隊(duì)空的條件是？（）A.front==rearB.(rear+1)%MAX_SIZE==frontC.rear==MAX_SIZE-1D.front==MAX_SIZE-19、在一棵平衡二叉樹中，插入一個(gè)新結(jié)點(diǎn)后，可能需要進(jìn)行的調(diào)整操作是：A.左旋B.右旋C.左旋和右旋D.不需要調(diào)整10、在數(shù)據(jù)結(jié)構(gòu)中，使用隊(duì)列來實(shí)現(xiàn)廣度優(yōu)先遍歷圖，以下關(guān)于遍歷過程的描述，錯誤的是（）A.從起始節(jié)點(diǎn)開始入隊(duì)B.隊(duì)列為空時(shí)結(jié)束遍歷C.訪問節(jié)點(diǎn)時(shí)將其未訪問的鄰接節(jié)點(diǎn)入隊(duì)D.節(jié)點(diǎn)不會被重復(fù)訪問11、在圖的存儲結(jié)構(gòu)中，鄰接多重表主要用于存儲無向圖，以下關(guān)于鄰接多重表的特點(diǎn)，描述錯誤的是（）A.可以方便地刪除邊B.存儲空間比鄰接矩陣節(jié)省C.對于判斷兩點(diǎn)之間是否有邊，效率較高D.不適合用于有向圖的存儲12、設(shè)有一個(gè)字符串S="helloworld"，要計(jì)算字符串S的長度（不包括結(jié)束符'\0'），以下函數(shù)正確的是？（）A.intlength(char*s){intcount=0;while(*s!='\0'){count++;s++;}returncount;}B.intlength(char*s){intcount=0;for(;*s!='\0';s++){count++;}returncount;}C.intlength(char*s){intcount=0;do{count++;s++;}while(*s!='\0');returncount;}D.intlength(char*s){intcount=0;while(s[count]!='\0'){count++;}returncount;}13、在一個(gè)具有n個(gè)頂點(diǎn)和e條邊的無向圖中，使用鄰接矩陣存儲，進(jìn)行深度優(yōu)先遍歷，其時(shí)間復(fù)雜度為？A.O(n)B.O(n+e)C.O(n^2)D.O(e^2)14、在一個(gè)具有n個(gè)頂點(diǎn)和e條邊的有向圖中，采用鄰接表存儲，求頂點(diǎn)的入度的時(shí)間復(fù)雜度為？（）A.O(n)B.O(e)C.O(n+e)D.O(n2)15、隊(duì)列也是一種常見的數(shù)據(jù)結(jié)構(gòu)，遵循先進(jìn)先出的原則。對于一個(gè)循環(huán)隊(duì)列，以下說法不正確的是（）A.隊(duì)頭指針和隊(duì)尾指針的移動需要考慮循環(huán)的情況B.當(dāng)隊(duì)頭指針等于隊(duì)尾指針時(shí)，隊(duì)列為空C.可以通過犧牲一個(gè)存儲單元來區(qū)分隊(duì)列空和隊(duì)列滿的情況D.循環(huán)隊(duì)列可以避免假溢出的問題16、在一個(gè)具有n個(gè)頂點(diǎn)的無向圖中，若采用鄰接矩陣存儲，則矩陣中非零元素的個(gè)數(shù)至少為？（）A.nB.n-1C.2(n-1)D.n(n-1)/217、設(shè)有一個(gè)具有n個(gè)頂點(diǎn)的有向圖，采用鄰接表存儲。若要計(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)18、在一個(gè)具有n個(gè)元素的鏈表中，若要在表頭插入一個(gè)新元素，平均需要修改幾個(gè)指針？（）A.1B.2C.nD.n+119、對于一個(gè)具有n個(gè)頂點(diǎn)的無向圖，若其邊的集合為{(1,2),(1,3),(2,3),(2,4),(3,4)}，則該圖的鄰接表存儲中，頂點(diǎn)2的鏈表中包含的頂點(diǎn)有：A.1,3,4B.1,3C.3,4D.1,420、棧和隊(duì)列的操作可以用棧和隊(duì)列的基本操作來實(shí)現(xiàn)，以下關(guān)于它們的操作實(shí)現(xiàn)的說法中，錯誤的是？（）A.可以用兩個(gè)棧實(shí)現(xiàn)一個(gè)隊(duì)列，也可以用兩個(gè)隊(duì)列實(shí)現(xiàn)一個(gè)棧。B.用棧實(shí)現(xiàn)隊(duì)列時(shí)，需要考慮隊(duì)列的先進(jìn)先出特性，可能需要使用輔助棧。C.用隊(duì)列實(shí)現(xiàn)棧時(shí)，需要考慮棧的后進(jìn)先出特性，可能需要使用輔助隊(duì)列。D.棧和隊(duì)列的操作只能用棧和隊(duì)列的基本操作來實(shí)現(xiàn)，不能用其他數(shù)據(jù)結(jié)構(gòu)來輔助實(shí)現(xiàn)。二、簡答題（本大題共4個(gè)小題，共40分)1、（本題10分）詳細(xì)闡述B樹中如何進(jìn)行節(jié)點(diǎn)的查找操作。2、（本題10分）在一個(gè)鏈表中，如何實(shí)現(xiàn)鏈表的復(fù)制操作？3、（本題10分）論述如何使用動態(tài)規(guī)劃算法解決最長公共子序列問題，給出狀態(tài)轉(zhuǎn)移方程和代碼實(shí)現(xiàn)。4