數(shù)據(jù)結(jié)構(gòu)與算法模擬題及答案

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

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

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

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

5、，冒泡排序算法 的最壞時(shí)間復(fù)雜性是O（nn）,而快速排序算法的最壞時(shí)間復(fù)雜性是0（nlog2n）,所以 快速排序比冒泡排序算法效率更高。對(duì)錯(cuò)（正確答案）.把規(guī)模大的問題轉(zhuǎn)換為規(guī)模小的相似問題，這是遞歸的思想。對(duì)（正確答案）借.簡單項(xiàng)選擇擇排序每趟排序可能出現(xiàn)屢次記錄交換。對(duì)錯(cuò)（正確答案）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:都不對(duì).從算法的時(shí)間復(fù)雜度來看，0（nlog2n）是哪種排序的時(shí)間復(fù)雜度（）。A:快速排序（正確答案）B:直接插入排序C:簡單項(xiàng)選擇擇排序D：冒泡排序.簡單項(xiàng)選擇擇排序中，每一趟選擇最小的記錄的過程，那么每一趟排序的時(shí)間復(fù) 雜度是O o0（n）（正確答案）O（nn）0（1）0（nlog2n）. 10個(gè)記錄進(jìn)行簡單項(xiàng)選擇擇排序，需要（）趟排序。9（正確答案）810D:都不對(duì).采用簡單項(xiàng)選擇擇排序，共有N個(gè)記錄，每趟最多進(jìn)行（）次交換。1（正確答案）

7、2N-2N-1.快速排序在（）情況下不利于發(fā)揮其長處或優(yōu)勢。A:記錄有相同的關(guān)鍵字時(shí)B:記錄完全亂序時(shí)C:記錄已經(jīng)基本有序時(shí)（正確答案）D:記錄的關(guān)鍵字較大時(shí).改進(jìn)的順序查找方法比原來的順序查找法優(yōu)勢在于（）oA:查找次數(shù)減少B:比擬次數(shù)大量減少（正確答案）C:時(shí)間復(fù)雜度降低D:都不對(duì).快速排序按照選擇第一個(gè)記錄當(dāng)中軸，從小到大排序，原始序列是：25 17 39 42 22 19 30,那么經(jīng)過一趟快速排序后的結(jié)果是（）。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,那么 經(jīng)過一趟排序后的結(jié)果是O 0n個(gè)記錄，使用改進(jìn)的冒泡排序，即按照一趟排序之內(nèi)假設(shè)不存在記錄交 換，那么停止排序的方法，按從小到大排序，最壞情況比擬次數(shù)為O on（n-1）/2（正確答案）n-1nnn（n-1）n個(gè)記錄，使用改進(jìn)的冒泡排序，即按照一趟排序之內(nèi)假設(shè)不存在記錄交 換，那么停止排序的方法，按從小到大排序，最好情況比擬次數(shù)為O on（n-l）/2nT （正確答案）nnn（n-1）.快速排序與冒泡排序是（）排序。A:同一類（正確答案）B:不同類C:不確定D:都不對(duì).改進(jìn)的冒泡排序的任一趟排序過程

9、中，如果沒有發(fā)生（），那么說明已經(jīng)有 序；排序完畢。A:數(shù)據(jù)交換（正確答案）B:數(shù)據(jù)刪除C:數(shù)據(jù)增加D:數(shù)據(jù)修改N個(gè)記錄進(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是幾的時(shí)候()。單項(xiàng)選擇題A:是0B:是1(正確答案)C:是2D:是323青蛙過河案例中，如果河中有1根石柱，問最少有幾片荷葉就能過4只青 蛙(

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

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

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

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