算法分析與設(shè)計(jì)2022年春學(xué)期在線作業(yè)2題目
試卷總分:100 得分:100
一、單選題 (共 20 道試題,共 40 分)
1.將f=1+1/2+1/3+…+1/n轉(zhuǎn)化成遞歸函數(shù)，其遞歸體是()。
A.f(1)=0
B.f(1)=1
C.f(0)=1
D.f(n)=f(n-1)+1/n
2.在長(zhǎng)度為64的有序線性表中進(jìn)行順序查找，最壞情況下需要比較的次數(shù)為()。
A.63
B.64
C.6
D.7
3.下面說(shuō)法錯(cuò)誤的是()。
A.遞推和遞歸同屬于迭代解法的兩種不同實(shí)現(xiàn)方式
B.遞推：知道第一個(gè)，推出下一個(gè)，直到達(dá)到目的；遞歸：要知道第一個(gè)，需要先知道下一個(gè)，直到一個(gè)已知的，再反回來(lái)，得到上一個(gè)，直到第一個(gè)
C.算法執(zhí)行效率不同：遞推效率和速度高于遞歸。
D.算法執(zhí)行效率不同：遞歸效率和速度高于遞推
4.算法流程圖由一些圖框和流程線組成，下面表示處理的圖框是()。
A.圓形
B.菱形
C.圓角矩形
D.矩形
5.輸出單個(gè)字符時(shí)使用（）格式符。
A.%c
B.%s
C.%d
D.%e
6.在下面的排序方法中，輔助空間為O（n）的是() 。
A.希爾排序
B.堆排序
C.選擇排序
D.歸并排序
7.遞推法的基本思想()。
A.不斷用變量的舊值遞推新值的過(guò)程
B.把全部可行的解空間不斷分割為越來(lái)越小的子集（稱為分支），并為每個(gè)子集內(nèi)的解的值計(jì)算一個(gè)下界或上界
C.將原問(wèn)題分解為相似的子問(wèn)題，在求解的過(guò)程中通過(guò)子問(wèn)題的解求出原問(wèn)題的解
D.一種用若干步可重復(fù)的簡(jiǎn)運(yùn)算（規(guī)律）來(lái)描述復(fù)雜問(wèn)題的方法
8.strstr（）函數(shù)用來(lái)（）。
A.字符串連接
B.比較字符
C.求字符位置
D.求子串位置
9.不屬于C語(yǔ)言字符常量的是（）。
A.‘65'
B.'\027'
C.'A'
D.'\n'
10.下面敘述中正確的是（ ）
A.棧是“先進(jìn)先出”的線性表
B.隊(duì)列是“先進(jìn)后出”的線性表
C.循環(huán)隊(duì)列是非線性結(jié)構(gòu)
D.有序線性表既可以采用順序存儲(chǔ)結(jié)構(gòu)，也可以采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)
11.一個(gè)算法中的語(yǔ)句的()被稱為語(yǔ)句頻度或時(shí)間頻度。
A.執(zhí)行時(shí)間
B.占用空間
C.執(zhí)行速度
D.執(zhí)行次數(shù)
12.n個(gè)結(jié)點(diǎn)的完全有向圖含有邊的數(shù)目（）。
A.n*n
B.n（n＋１）
C.n／2
D.n*（n－l）
13.()命令用來(lái)顯示ASCII碼文件的內(nèi)容。
A.dir
B.cd
C.type
D.fc
14.能正確進(jìn)行字符串賦值、賦初值的語(yǔ)句組是（）。
A.char s[5]={'a','e','i','o','u'};
B.char *s; s="good!";
C.char s[5]="good!";
D.char s[5]="good!";
15.十進(jìn)制，就表示某一位置上的數(shù)運(yùn)算時(shí)是逢（）進(jìn)一位。
A.2
B.8
C.9
D.10
16.變量名=屬性 + 類型 + 對(duì)象描述，其中每個(gè)對(duì)象的名稱都要有明確含義，可以取對(duì)象的名字全稱或名字的一部分，這種命名規(guī)則是()。
A.匈牙利命名法
B.駱駝命名法
C.下劃線命名法
D.帕斯卡命名法
17.數(shù)制是人們利用( )進(jìn)行計(jì)數(shù)的一種科學(xué)方法。
A.數(shù)字
B.符號(hào)
C.字母
D.圖形
18.遺傳算法主要模擬生物中的()。
A.遺傳、復(fù)制、傳遞和分裂
B.遺傳、突變、選擇和雜交
C.遺傳、突變、傳遞和轉(zhuǎn)錄
D.遺傳、復(fù)制、轉(zhuǎn)錄和逆轉(zhuǎn)錄
19.有以下程序，執(zhí)行后的輸出結(jié)果是()。 fun(int x) { int p; if(x==0||x==1) return (3); p=x-fun(x-2); return p; } main() { printf(“%d\n”,fun(7)); }
A.7
B.3
C.2
D.0
20.分枝定界法的基本思想()。
A.不斷用變量的舊值遞推新值的過(guò)程
B.把全部可行的解空間不斷分割為越來(lái)越小的子集（稱為分支），并為每個(gè)子集內(nèi)的解的值計(jì)算一個(gè)下界或上界
C.將原問(wèn)題分解為相似的子問(wèn)題，在求解的過(guò)程中通過(guò)子問(wèn)題的解求出原問(wèn)題的解
D.一種用若干步可重復(fù)的簡(jiǎn)運(yùn)算（規(guī)律）來(lái)描述復(fù)雜問(wèn)題的方法
二、多選題 (共 4 道試題,共 16 分)
21.字符串有關(guān)的格式字符有（ ）。
A."%c"
B."%d"
C."%f"
D."%s"
22.遞歸算法的執(zhí)行過(guò)程分()和()兩個(gè)階段。
A.遞歸
B.遞推
C.回歸
D.回溯
23.設(shè)計(jì)遞歸算法有兩點(diǎn)最為關(guān)鍵()和()。
A.確定遞推公式
B.確定邊界（終了）條件（遞歸出口）
C.每次遞歸調(diào)用，都必須向基本條件前進(jìn)
D.如果結(jié)果已知，那么，不用再重復(fù)調(diào)用遞歸
24.順序結(jié)構(gòu)、選擇結(jié)構(gòu)、循環(huán)結(jié)構(gòu)三種結(jié)構(gòu)共同特點(diǎn)是()
A.只有一個(gè)入口
B.只有一個(gè)出口
C.結(jié)構(gòu)內(nèi)的每一部分都有機(jī)會(huì)被執(zhí)行到（不存在死語(yǔ)句）
D.結(jié)構(gòu)內(nèi)不存在死循環(huán)（永遠(yuǎn)執(zhí)行不完的循環(huán)）。
三、判斷題 (共 22 道試題,共 44 分)
25.歸并排序是一種穩(wěn)定的排序方法。
26.算法的空間復(fù)雜度是指算法需要消耗的空間資源。
27.在深度為7的滿二叉樹(shù)中，度為2的結(jié)點(diǎn)個(gè)數(shù)為64。
28.注釋內(nèi)容太多會(huì)影響程序的執(zhí)行效率。
29.字符數(shù)組要求其最后一個(gè)元素是‘\0’。
30.編輯與編譯是一回事。
31.一棵二叉樹(shù)有10個(gè)度為1的結(jié)點(diǎn)，7個(gè)度為2的結(jié)點(diǎn)，則該二叉樹(shù)共有24個(gè)結(jié)點(diǎn)。
32.含有空格字符的串稱為空格串，其長(zhǎng)度為0。
33.在順序表中進(jìn)行結(jié)點(diǎn)的刪除操作平均須移動(dòng)一半結(jié)點(diǎn)。
34.在前序遍歷二叉樹(shù)的序列中，任何結(jié)點(diǎn)的子樹(shù)上的所有結(jié)點(diǎn)，都是直接跟在該結(jié)點(diǎn)之后。
35.在有n個(gè)頂點(diǎn)的有向圖中，每個(gè)頂點(diǎn)的度最大可達(dá)2*（n-1）。
36.遞推就是在函數(shù)里調(diào)用自身。
37.棧和隊(duì)列都是線性結(jié)構(gòu)。
38.遞推利用已知或已求出的結(jié)果迭代出下一步的結(jié)果；而遞歸則反之，要求出這一步的結(jié)果需要先去求上一步或上幾步的結(jié)果（即多重迭代），往往會(huì)重復(fù)計(jì)算大量的子問(wèn)題。并且遞推省去了遞歸的棧操作。
39.某二叉樹(shù)由5個(gè)度為2的結(jié)點(diǎn)以及3個(gè)度為1的結(jié)點(diǎn)，則該二叉樹(shù)中共有15個(gè)結(jié)點(diǎn)。
40.C程序執(zhí)行的入口是main()函數(shù)，所以main函數(shù)必須放在程序的開(kāi)頭。
41.在使用遞歸策略時(shí)，必須有一個(gè)明確的遞歸結(jié)束條件，稱為遞歸入口。
42.能采用遞歸描述的算法通常有這樣的特征：為求解規(guī)模為N的問(wèn)題，設(shè)法將它分解成規(guī)模較小的問(wèn)題，然后從這些小問(wèn)題的解很容易構(gòu)造出大問(wèn)題的解，并且這些規(guī)模較小的問(wèn)題也能采用同樣的分解和綜合方法，分解成規(guī)模更小的問(wèn)題，并從這些更小問(wèn)題的解構(gòu)造出規(guī)模較大問(wèn)題的解。特別地，當(dāng)規(guī)模N=1時(shí)，能直接得解。
43.遞推中的順推法是指從已知條件出發(fā)，逐步推出要解決的問(wèn)題。
44.scanf()、printf()可以輸入輸出幾個(gè)字符串。
45.快速排序的時(shí)間復(fù)雜度為O(n*n)。
46.排序的關(guān)鍵操作是：一是比較兩個(gè)關(guān)鍵字大小，二是將記錄從一個(gè)位置移動(dòng)到另一個(gè)位置。
