數(shù)據(jù)結構與算法模擬題及答案

1、數(shù)據(jù)結構與算法模擬題及答案.關于素數(shù)描述正確的選項是（）OA:素數(shù)就是合數(shù)B:素數(shù)不能被本身整除C:素數(shù)又稱為質數(shù)只能被1和它本省整除（正確答案）D:素數(shù)不僅能被1和它本身整除，還能被其它數(shù)整除. for循環(huán)的（表達式1;表達式2;表達式3）中表達式3的作用是（）。A:循環(huán)的增量表達式（正確答案）B:循環(huán)的條件C:循環(huán)的初值D:循環(huán)體.哪一種排序，可能存在這種情況：“最后一趟開始之前，所有記錄均不在其 最終位置上” （）oA:快速排序B:冒泡排序C:直接插入排序（正確答案）D:簡單項選擇擇排序4簡單項選擇擇排序，按照從小到大排序，原始序列是：19 11 17 18 16 15,那么經過一趟排序

2、后的結果是（）oA:ll19 17 18 16 15（正確答案）B:ll15 16 17 18 19C:ll17 18 16 15 19D:19 11 1718 16 155、關于查找的效率問題，下面說法中正確的選項是（）oA :順序查找一定沒有折半查找快B:順序查找比折半查找快D: for語句是c語言所提供的功能更強，使用更廣泛的一種循環(huán)語句。（正確 答案）44、以下可用遞歸實現(xiàn)的是（）oA:求1-n的和（正確答案）B:求n的階乘（正確答案）C:斐波那契數(shù)列（正確答案）口：11%。表示幕）（正確答案）45.靜態(tài)查找表中，對順序表的查找方式有（）oA:順序查找（正確答案）B:折半查找（正確答案

3、）C:分塊查找D:隨機查找46、從排序大類上看，屬于選擇排序的是（）。A:簡單項選擇擇排序（正確答案）B:堆排序（正確答案）C:快速排序D:冒泡排序47、在簡單項選擇擇排序中，每一趟排序過程中最多進行1次記錄交換。對（正確答案）錯. for循環(huán)的思想是，先分析清楚循環(huán)的初始值，循環(huán)的控制條件，循環(huán)變 量的步長變化，然后直接把語句再寫到for的循環(huán)體里即可，這樣可以讓問題想的 很清楚，流程也很清楚。對（正確答案）錯.二叉排序樹的充要條件是樹中任何一個結點的左孩子的關鍵字要小于根結 點的關鍵字，右孩子的關鍵字要大于根節(jié)點的關鍵字。對錯（正確答案）.快速排序的時間復雜度低于冒泡排序的時間復雜度。對（

4、正確答案）錯.裝填因子越大，發(fā)生沖突的可能性就越大；當裝填因子減小到一定程度， 那么沖突是可以防止的。對錯（正確答案）.青蛙過河問題是一種用遞歸算法可以解決的問題，這種算法的特點是自身 調用自身。對（正確答案）錯排序算法中，第一趟排序后，任一元素都不能確定其最終位置的算法是插 入排序。對（正確答案）錯54青蛙過河案例中，如果河中有2根石柱，有3片荷葉，那么可以過24只青 蛙。對錯（正確答案）.穩(wěn)定排序是指排序前后相同關鍵字的記錄相對位置不變。對（正確答案）錯.希爾排序是一種選擇排序，也不穩(wěn)定排序，時間復雜度是0（n3/2）。對錯（正確答案）.冒泡排序和快速排序都是基于交換兩個逆序元素的排序方法

5、，冒泡排序算法 的最壞時間復雜性是O（nn）,而快速排序算法的最壞時間復雜性是0（nlog2n）,所以 快速排序比冒泡排序算法效率更高。對錯（正確答案）.把規(guī)模大的問題轉換為規(guī)模小的相似問題，這是遞歸的思想。對（正確答案）借.簡單項選擇擇排序每趟排序可能出現(xiàn)屢次記錄交換。對錯（正確答案）c:折半查找不一定比順序查找快（正確答案）D:就平均效率而言，順序查找的效率更高.青蛙過河案例中，如果河中沒有石柱，有y片荷葉的話，那么從左岸到右岸 可以過去（）只青蛙。y+1只（正確答案）y+2 只y+3 只y+4 只.青蛙過河案例中，如果河中有1根石柱，問最少有幾片荷葉就能過4只青蛙 （）01片（正確答案）

6、3片0片2片.某些排序存在不相鄰記錄之間的交換，因此是不穩(wěn)定排序，以下是不穩(wěn)定的 排序是（）oA:快速排序（正確答案）B:冒泡排序C:直接插入排序D:都不對.從算法的時間復雜度來看，0（nlog2n）是哪種排序的時間復雜度（）。A:快速排序（正確答案）B:直接插入排序C:簡單項選擇擇排序D：冒泡排序.簡單項選擇擇排序中，每一趟選擇最小的記錄的過程，那么每一趟排序的時間復 雜度是O o0（n）（正確答案）O（nn）0（1）0（nlog2n）. 10個記錄進行簡單項選擇擇排序，需要（）趟排序。9（正確答案）810D:都不對.采用簡單項選擇擇排序，共有N個記錄，每趟最多進行（）次交換。1（正確答案）

7、2N-2N-1.快速排序在（）情況下不利于發(fā)揮其長處或優(yōu)勢。A:記錄有相同的關鍵字時B:記錄完全亂序時C:記錄已經基本有序時（正確答案）D:記錄的關鍵字較大時.改進的順序查找方法比原來的順序查找法優(yōu)勢在于（）oA:查找次數(shù)減少B:比擬次數(shù)大量減少（正確答案）C:時間復雜度降低D:都不對.快速排序按照選擇第一個記錄當中軸，從小到大排序，原始序列是：25 17 39 42 22 19 30,那么經過一趟快速排序后的結果是（）。19 17 22 25 42 39 30（正確答案）17 19 22 25 30 39 42C: 17 19 22 25 42 39 30D: 19 17 22 25 30

8、39 42直接插入排序，按照從小到大排序，原始序列是：18 19 20 16 14 13,那么 經過一趟排序后的結果是O 0n個記錄，使用改進的冒泡排序，即按照一趟排序之內假設不存在記錄交 換，那么停止排序的方法，按從小到大排序，最壞情況比擬次數(shù)為O on（n-1）/2（正確答案）n-1nnn（n-1）n個記錄，使用改進的冒泡排序，即按照一趟排序之內假設不存在記錄交 換，那么停止排序的方法，按從小到大排序，最好情況比擬次數(shù)為O on（n-l）/2nT （正確答案）nnn（n-1）.快速排序與冒泡排序是（）排序。A:同一類（正確答案）B:不同類C:不確定D:都不對.改進的冒泡排序的任一趟排序過程

9、中，如果沒有發(fā)生（），那么說明已經有 序；排序完畢。A:數(shù)據(jù)交換（正確答案）B:數(shù)據(jù)刪除C:數(shù)據(jù)增加D:數(shù)據(jù)修改N個記錄進行冒泡排序最多需要()趟排序，可以完成排序。NT (正確答案)NN-2(N+D/222.ttinclude stdio.h;int fun(int i)if (i=l)return 1;elsereturn ifun(i-1);void main ()(int n;n=fun(3);printf (%d, n);子程序的遞歸邊界是i是幾的時候()。單項選擇題A:是0B:是1(正確答案)C:是2D:是323青蛙過河案例中，如果河中有1根石柱，問最少有幾片荷葉就能過4只青 蛙(

10、)。A: 1片(正確答案)B:3片C:0片D:2片24程序調用自身的編程技巧，稱為（）。A:數(shù)組B:函數(shù)C:遞歸（正確答案）D:排序25某些排序存在不相鄰記錄之間的交換，因此是不穩(wěn)定排序，以下是不穩(wěn)定 的排序是（）oA:快速排序（正確答案）B:冒泡排序C:直接插入排序D:都不對.一趟快速排序是選擇一個中軸，將小于中軸位置記錄的調到它的左邊，大 于的調到它的O oA:右邊（正確答案）B:左邊C:兩邊D:都不對. 10個記錄進行簡單項選擇擇排序，需要（）趟排序。A: 9（正確答案）B:8C:10D:都不對28.采用簡單項選擇擇排序，共有N個記錄，每趟最多進行（）次交換。1（正確答案）B:2C:N-

11、2D:N-129.快速排序按照選擇第一個記錄當中軸，從小到大排序，原始序列是：25 1739 42 2239 42 221930,那么經過一趟快速排序后的結果是（）oA:19172225423930（正確答案）B:17192225303942C:17192225423930D:1917222530394230.直接插入排序,30.直接插入排序,按照從小到大排序,原始序列是：18 19 20 16 14 13,那么經過一趟排序后的結果是（）oA:13A:131416181920B:181920161413（正確答案）C:181920141613D:13181920141631 .快速排序在情況下

12、不利于發(fā)揮其長處或優(yōu)勢。A:記錄有相同的關鍵字時B:記錄完全亂序時C:記錄已經基本有序時（正確答案）D:記錄的關鍵字較大時32冒泡排序最壞的情況是，記錄完全逆序，20個記錄待排序需要比擬（）次 才能完成排序。A: 2019C: 18D: 190（正確答案）33、簡單項選擇擇排序中，每一趟選擇最小的記錄的過程，那么每一趟排序的時間復 雜度是O oA:0（n）（正確答案）B:O（nn）C:O（1）D:0（nlog2n）.二叉排序是應用于動態(tài)查找的，其特點正確的選項是（）0A:左子樹上的關鍵字小于根結點的關鍵字（正確答案）B:右子樹上的關鍵字大于根結點的關鍵字（正確答案）C:右子樹上的關鍵字大于左子

13、樹上的關鍵字（正確答案）D:左右子樹都是二叉排序樹（正確答案）.從排序的大的分類上講，屬于交換排序的是（）oA:簡單項選擇擇排序B:堆排序C:快速排序（正確答案）D:冒泡排序（正確答案）.從待排記錄是否都在內存中的角度看，屬于內排序的是（）。A:簡單項選擇擇排序（正確答案）B:堆排序（正確答案）C:快速排序（正確答案）D:冒泡排序（正確答案）. 30個記錄的序列進行冒泡排序，那么有可能（）oA: 29次比擬就完成排序（正確答案）B:進行29趟排序才結束排序（正確答案）C:不能完成排序D:可能10趟就結束了排序。（正確答案）38.冒泡排序的改進之處說法不對的是（）oA:增加了比擬的次數(shù)（正確答案）B:增加了比擬的趟數(shù)（正確答案）C:盡可能的減少比擬次數(shù)和趟數(shù)D: 一定會減少比擬的次數(shù)和趟數(shù)（正確答案）.青蛙過河問題要剛好過4只青蛙，那么情況可以是（）oA:沒有石柱，荷葉有3片的情況（正確答案）B:石柱有1個，荷葉有1片的情況（正確答案）C:石柱有1個荷葉有2片的情況D:石柱有2個，荷葉有1片的情況.關于快速排序描述不正確的選項是（）。A:快速排序是穩(wěn)定排序（正確答案）B:快速排序的時間復雜度是。（nlog2n）C:快速排序不存在不相鄰的記錄之間的交換（正確答案）D:快速排序的時間復雜度是O（nn）（正確答案）.青蛙跳河游戲中，假設有2個荷葉，2