西安工程大學《數(shù)據(jù)結(jié)構(gòu)與算法》2021-2022學年期末試卷

學校________________班級____________姓名____________考場____________準考證號學校________________班級____________姓名____________考場____________準考證號…………密…………封…………線…………內(nèi)…………不…………要…………答…………題…………第1頁，共3頁西安工程大學《數(shù)據(jù)結(jié)構(gòu)與算法》

2021-2022學年期末試卷題號一二三總分得分批閱人一、單選題（本大題共20個小題，每小題2分，共40分．在每小題給出的四個選項中，只有一項是符合題目要求的．）1、若要對一棵二叉排序樹進行中序遍歷，得到的序列是一個有序序列，這是因為二叉排序樹的定義具有什么特性？（）A.左子樹的值小于根節(jié)點，右子樹的值大于根節(jié)點B.左子樹和右子樹的深度相同C.每個節(jié)點的值都不同D.以上都不是2、若對線性表的操作只有兩種，即插入和刪除，且以鏈表作為存儲結(jié)構(gòu)，則插入和刪除操作的時間復雜度分別為：A.O(n)和O(n)B.O(1)和O(1)C.O(n)和O(1)D.O(1)和O(n)3、在一個具有n個元素的最大堆中，插入一個新元素后，為了恢復堆的性質(zhì)，需要進行的調(diào)整操作的時間復雜度為（）A.O(1)B.O(logn)C.O(n)D.O(nlogn)4、在數(shù)據(jù)結(jié)構(gòu)中，哈希表的負載因子對性能有很大影響。以下關(guān)于負載因子的描述，不正確的是（）A.負載因子越大，哈希沖突的可能性越大B.負載因子越小，存儲空間利用率越高C.負載因子通常在0.5到1之間D.可以通過調(diào)整負載因子來優(yōu)化哈希表性能5、以下關(guān)于哈夫曼樹的描述，正確的是：A.哈夫曼樹一定是完全二叉樹B.哈夫曼樹中不存在度為1的節(jié)點C.哈夫曼樹的帶權(quán)路徑長度是唯一的D.哈夫曼樹的構(gòu)建過程不需要進行節(jié)點的比較和交換6、在一個具有n個元素的循環(huán)雙鏈表中，若要在表頭插入一個新元素，以下關(guān)于插入操作的時間復雜度的描述，哪一項是準確的？A.O(1)B.O(logn)C.O(n)D.O(nlogn)7、在一棵完全二叉樹中，若節(jié)點個數(shù)為n，那么其葉子節(jié)點的個數(shù)大約為多少？（）A.n/2B.n/4C.(n+1)/2D.n/38、已知一個哈希表的長度為11，哈希函數(shù)為H(key)=key%11，采用二次探測法處理沖突。若依次插入關(guān)鍵字15、38、61、84，則在查找關(guān)鍵字61時需要進行幾次探測？（）A.1B.2C.3D.49、棧和隊列的實現(xiàn)可以使用數(shù)組或鏈表，以下關(guān)于它們的實現(xiàn)方式的說法中，錯誤的是？（）A.用數(shù)組實現(xiàn)棧和隊列時，需要考慮數(shù)組的大小和溢出問題。B.用鏈表實現(xiàn)棧和隊列時，插入和刪除操作的時間復雜度為O(1)。C.棧和隊列的實現(xiàn)方式只影響它們的性能，不影響它們的功能。D.棧和隊列可以同時使用數(shù)組和鏈表實現(xiàn)，以提高性能和靈活性。10、設(shè)有一個字符串S="helloworld"，要計算字符串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;}11、設(shè)有兩個串p和q，求q在p中首次出現(xiàn)的位置的運算稱為：A.連接B.模式匹配C.求子串D.求串長12、在一個鏈式存儲的棧中，若棧頂指針為top，要判斷棧是否為空，應判斷？（）A.top==NULLB.top->next==NULLC.top->data==NULLD.*top==NULL13、對于一個具有n個節(jié)點的AVL樹，插入一個新節(jié)點后，調(diào)整樹的平衡，其時間復雜度為？A.O(1)B.O(logn)C.O(n)D.O(nlogn)14、在一個哈希表中，解決沖突的方法不包括：A.開放定址法B.再哈希法C.建立索引表D.鏈地址法15、在一個具有n個節(jié)點的有向圖中，若存在環(huán)，則使用拓撲排序算法會出現(xiàn)什么情況？A.正常完成排序B.無法完成排序C.排序結(jié)果不準確D.以上都不對16、在一個具有n個元素的順序表中，要在中間位置插入一個新元素，平均移動元素的個數(shù)約為？A.n/2B.nC.lognD.117、以下關(guān)于哈希表沖突解決方法的描述，哪一項是不正確的？（）A.鏈地址法會增加存儲空間的開銷B.開放定址法的查找效率一定高于鏈地址法C.再哈希法可以減少沖突的發(fā)生D.建立公共溢出區(qū)可以存儲發(fā)生沖突的元素18、對于一個用數(shù)組實現(xiàn)的小根堆，進行刪除堆頂元素操作后，需要重新調(diào)整堆以保持堆的性質(zhì)。以下關(guān)于刪除操作的時間復雜度的描述，哪一個是正確的？A.O(1)B.O(logn)C.O(n)D.O(nlogn)19、在數(shù)據(jù)結(jié)構(gòu)中，字典樹在處理大量字符串時，可能會出現(xiàn)內(nèi)存占用過高的問題，以下解決方法錯誤的是（）A.壓縮節(jié)點B.限制字典樹的深度C.使用哈希表替代字典樹D.減少字符串的存儲20、在一個具有n個元素的順序表中，若要在第i個位置（1<=i<=n+1）插入一個新元素，需要移動的元素個數(shù)最少為（）。A.0B.i-1C.n-iD.n-i+1二、簡答題（本大題共4個小題，共40分)1、（本題10分）對于一個用鏈表實現(xiàn)的棧，如何實現(xiàn)獲取棧中元素的最小值操作，要求時間復雜度為O(1)，給出算法思路和實現(xiàn)代碼。2、（本題10分）詳細說明選擇排序算法的工作原理，分析其時間復雜度和空間復雜度，以及在實際應用中的優(yōu)缺點。3、（本題10分）數(shù)組的查找算法中，二分查找的實現(xiàn)條件和過程是怎樣的？時間復雜度是多少？4、（本題10分）深入分析在具有n個頂點的無向圖中，如何計算每個頂點的度，并給出時間復雜度和空間復雜度的分析。三、