(九月度)數(shù)據(jù)結(jié)構(gòu)與算法月考測(cè)試1[復(fù)制]您的姓名：[填空題]*_________________________________1.12個(gè)待排記錄，使用直接插入排序需要（）趟能完成全部排序。[單選題]*A:11(正確答案)B:12C:10D:都不對(duì)2.折紙問題是一種（）問題。[單選題]*A:迭代問題(正確答案)B:遞歸問題C:分治問題D:窮舉問題3.在各種查找方法中，平均查找長度ASL與結(jié)點(diǎn)個(gè)數(shù)n無關(guān)的查找方法是（）。[單選題]*A:順序查找B:折半查找C:哈希查找(正確答案)D:分塊查找4.數(shù)據(jù)結(jié)構(gòu)與算法內(nèi)，設(shè)fun(n)表示斐波那契數(shù)列的第n項(xiàng)的值，fun是函數(shù)名，n是整型參數(shù)，那么根據(jù)遞歸思想它應(yīng)等于（）。[單選題]*A:fun(n)+fun(n-1)B:fun(n-1)+fun(n-2)(正確答案)C:fun(n-1)*fun(n-2)D:fun(n-2)+fun(n-3)5.漢諾塔問題是是一類（）問題。[單選題]*A:遞歸(正確答案)B:分治C:窮舉D:迭代6.對(duì)于二叉樹的遍歷：先訪問根結(jié)點(diǎn)，再訪問左子樹，最后訪問右子樹，則是（）。[單選題]*A:中序遍歷B:先序遍歷(正確答案)C:后序遍歷D:按層次遍歷7.青蛙過河案例中，如果河中有1根石柱，有1片荷葉的話，那么從左岸到右岸可以過去（）只青蛙。[單選題]*A:3只B:4只(正確答案)C:2只D:1只8.關(guān)于二叉樹樹，某完全二叉樹按層次編號(hào)后，某結(jié)點(diǎn)是i，若有左孩子，則左孩子的編號(hào)是（）。[單選題]*A:2i(正確答案)B:2i+1C:2i-1D:i/29.荷蘭國旗算法的時(shí)間復(fù)雜度是（）。[單選題]*A:O(1)B:O(n)(正確答案)C:O(nlog2n)D:O(n*n)10.下面程序執(zhí)行后的結(jié)果是(

)。[單選題]

#include"stdio.h"

voidmain()

{

intarr[4][4]={{2,2,3,4},{5,6,7,8},{9,10,11,12},{13,14,15,15}},i,sum=0;

for(i=0;i<4;i++

{

sum=sum+arr[i][i];

}

printf("%d",sum);

}[單選題]*A28B34(正確答案)C40D1011.單鏈表中刪除p指針指向結(jié)點(diǎn)的后繼(假設(shè)存在)的語句序列正確的是（）。[單選題]*A:p->next=p->next;B:p->next=p->next->next;(正確答案)C:p->next=p;D:p=p->next;12.變量height要比原來少15，則應(yīng)寫成（）。[單選題]*A:height-15B:height=15C:height=-15D:height-=15(正確答案)13.下列選項(xiàng)中關(guān)于棧和隊(duì)列理解正確的是（）。[單選題]*A:棧和隊(duì)列是操作受限的線性結(jié)構(gòu)(正確答案)B:棧和隊(duì)列是先進(jìn)先出的線性結(jié)構(gòu)C:棧和隊(duì)列是后進(jìn)先出的線性結(jié)構(gòu)D:棧和隊(duì)列是先進(jìn)后出的線性結(jié)構(gòu)14.順序表刪除元素的時(shí)間復(fù)雜度是（）。[單選題]*A:O(1)B:O(n)(正確答案)C:O(n*n)D:都不對(duì)15.雞兔同籠算法具有算法的每一步都是確定沒有二義性，這是（）。[單選題]*A:有窮性B:確定性(正確答案)C:可行性D:正確性16.C結(jié)點(diǎn)有3個(gè)堂兄弟(不算自己)，B是C的雙親，則B的度是（）。[單選題]*A:0B:4C:3D:不確定，至少大于等于1(正確答案)17.在樹的術(shù)語中，某結(jié)點(diǎn)掛接的子樹的數(shù)目稱為（）。[單選題]*A:結(jié)點(diǎn)的度(正確答案)B:樹的度C:樹的深度D:無正確答案18.裝填因子又稱為（）。[單選題]*A:負(fù)載因子(正確答案)B:平衡因子C:外力因子D:合力因子19.二叉樹的遍歷算法可以用（）算法來實(shí)現(xiàn)，因?yàn)槠涠x是遞歸定義的。[單選題]*A:遞歸(正確答案)B:逆推C:回溯D:分治20.直接插入排序的穩(wěn)定性和希爾排序的穩(wěn)定性是（）。[單選題]*A:一樣的B:不一樣(正確答案)C:可能一樣也可能不一樣D:不確定21.快速排序的特性描述正確的是（）。*A:快速排序是穩(wěn)定排序B:快速排序不穩(wěn)定排序(正確答案)C:快速排序的時(shí)間復(fù)雜度是O(nlog2n)(正確答案)D:快速排序的時(shí)間復(fù)雜度是O(n*n)22.二叉樹轉(zhuǎn)換為樹需要哪些步驟（）。*A:去線(正確答案)B:加線(正確答案)C:調(diào)整角度(正確答案)D:遍歷一遍23.數(shù)據(jù)結(jié)構(gòu)與算法里，順序表的查找有_和_（）。*A:順序查找(正確答案)B:折半查找(正確答案)C:隨機(jī)查找D:索引查找24.有以下程序main()

{

inta[2][4]={1,12,3,4,5,6,7,9};

printf("%d",a[1][3]);

}則程序的輸出結(jié)果不可能是（）。[多選題]*A:6(正確答案)B:9C:7(正確答案)D:5(正確答案)25.while循環(huán)小括號(hào)的表達(dá)式類型可以是（）。*A:整型表達(dá)式(正確答案)B:關(guān)系表達(dá)式(正確答案)C:邏輯表達(dá)式(正確答案)D:算術(shù)表達(dá)式(正確答案)26.串是一種特殊的線性結(jié)構(gòu)，串的操作可以有（）。*A:截取字串(正確答案)B:串判空(正確答案)C:連接字符串(正確答案)D:定位子串在主串中的位置(正確答案)27.下列選項(xiàng)中關(guān)于二叉樹的遍歷和恢復(fù)說法正確的是（）。*A:先序序列和中序序列已知，可以恢復(fù)二叉樹(正確答案)B:中序序列和后序序列已知，可以恢復(fù)二叉樹(正確答案)C:先序序列和后序序列已知，可以恢復(fù)二叉樹D:無正確答案28.完全二叉樹中，結(jié)點(diǎn)個(gè)數(shù)為n，則編號(hào)最大的分支結(jié)點(diǎn)的編號(hào)不可能為（）。*A:n/2向下取整B:n/2向下取整+1(正確答案)C:n/2向下取整+2(正確答案)D:n/2向下取整-1(正確答案)29.排序是穩(wěn)定排序或不穩(wěn)排序的插入排序是（）。*A:希爾排序(正確答案)B:直接插入排序(正確答案)C:堆排序D:快速排序30.按照排序中具有相同關(guān)鍵字的記錄在排序前后的相對(duì)位置是否發(fā)生改變，排序分為（）。*A:穩(wěn)定排序(正確答案)B:不穩(wěn)定排序(正確答案)C:外部排序D:內(nèi)部排序31.荷蘭國旗算法的時(shí)間復(fù)雜度是O(n)。[判斷題]*對(duì)(正確答案)錯(cuò)32.簡(jiǎn)單選擇排序在一趟排序，找到最小值后最多進(jìn)行一次交換。[判斷題]*對(duì)(正確答案)錯(cuò)33.棧的使用很廣泛，它的特性是先進(jìn)先出。[判斷題]*對(duì)錯(cuò)(正確答案)34.while語句是先計(jì)算表達(dá)式的值，再執(zhí)行循環(huán)體，do…while是執(zhí)行完一次循環(huán)體，再計(jì)算表達(dá)式的值。[判斷題]*對(duì)(正確答案)錯(cuò)35.快速排序和希爾排序都是不穩(wěn)定的排序，即排序前后關(guān)鍵字相同的記錄的相對(duì)位置發(fā)生了改變。[判斷題]*對(duì)(正確答案)錯(cuò)36.鏈表的每個(gè)結(jié)點(diǎn)由數(shù)據(jù)域和指針域，指針域只有一個(gè)的鏈表稱為單鏈表。[判斷題]*對(duì)(正確答案)錯(cuò)37.C語言中，do-while語句和while語句完全可以互相替換。[判斷題]*對(duì)(正確答案)錯(cuò)38.對(duì)不同的關(guān)鍵字可能得到同一哈希地址