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

)。[單選題]

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

{

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

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

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