2016現(xiàn)代科技學(xué)院《軟件技術(shù)基礎(chǔ)》練習(xí)題+答案

1、軟件技術(shù)基礎(chǔ)練習(xí)題太原理工大學(xué)現(xiàn)代科技學(xué)院2016第一章算法一、選擇題1 .算法的復(fù)雜度包括【】。A、時(shí)間復(fù)雜度B、空間復(fù)雜度C、時(shí)間及空間復(fù)雜度D、以上都不對(duì)2 .若x在長(zhǎng)度為n的無(wú)序線(xiàn)性順序表中的概率為 50%,則在該表中查找x的平均查找次數(shù)（平均 性態(tài)分析）為【1A、（n*3+1）/4B、（n-1）/2C、（n+1）/2D、（n+1）*n/23 .若x在長(zhǎng)度為n的無(wú)序線(xiàn)性順序表中的概率為50%,則在該表中查找x的最壞情況分析為【】A、n/2B、（n-1）/2C、（n+1）/2D、n4 .已知基本運(yùn)算執(zhí)行次數(shù)與n的關(guān)系，則下列哪個(gè)時(shí)間復(fù)雜度最大：【】。A. f（n） = 1B. f（n）

2、= 2n - 1C. f（n） = 10000n+10000D. f（n） = n2-100005 .算法分析的目的是【】。A,找出數(shù)據(jù)結(jié)構(gòu)的合理性B.研究算法中的輸入和輸出的關(guān)系C.分析算法的效率以求改進(jìn)D.分析算法的易懂性和文檔性、填空題1 .常用算法包括? 和回溯法2 .算法的基本特征有 ?有窮性、輸入和輸出。3 .下列程序段的時(shí)間復(fù)雜度是 。for （i=1 ； i<=n ； i+）Ai, i=0；4 .下列程序段的時(shí)間復(fù)雜度是 s=0；for（i=1 ； i<=2n ； i+）for（j=1 ; j<=n； j+）s=s+Bij；sum=s；5 .下列程序段的時(shí)間復(fù)

3、雜度是 i=1 ；while （i<=n）i=i*2 ；6 .在下面的程序段中，s= s + p；語(yǔ)句的執(zhí)行次數(shù)為 , p= pxj語(yǔ)句的執(zhí)行次數(shù)為 ，該程序段的時(shí)間復(fù)雜度為 。int i=0, s=0, p=1;while( +i<=n )for(j=1； j<=i； j+ )p = p Ks = s + p;7.常見(jiàn)時(shí)間復(fù)雜度的量級(jí)有：常數(shù)階0()、對(duì)數(shù)階0()、線(xiàn)性階0()、平方階0(而指數(shù)階0()。三、判斷題1.算法和程序沒(méi)有區(qū)別，所以在數(shù)據(jù)結(jié)構(gòu)中二者是通用的。第二章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算、選擇題1 .數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)被形式地定義為（D,R）,其中口是【（1）的有限集

4、合，R是口上（2） 的有限集合。（1） A.算法B.數(shù)據(jù)元素C.數(shù)據(jù)操作D.邏輯結(jié)構(gòu)（2） A.操作B.映像C.存儲(chǔ)D.關(guān)系2 .在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為【1A.動(dòng)態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)B.緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)C,線(xiàn)性結(jié)構(gòu)和非線(xiàn)性結(jié)構(gòu)D,內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)3設(shè)進(jìn)棧的輸入序列是1,2,3,4,則【】不可能是其出棧序列。A. 1243B. 2134C. 1432D. 43124.設(shè)有一順序棧s,元素s1, s2,s3,s4,s5,s6依次入棧，如果6個(gè)元素出棧的順序是s2, s3,54, s6, s5, s1,則棧的容量至少應(yīng)該是【 JoA. 2 B. 3 C. 5 D. 65 .線(xiàn)性表

5、若采用鏈表存儲(chǔ)結(jié)構(gòu)，要求內(nèi)存中可用存儲(chǔ)單元的地址11A.必須是連續(xù)的B.部分必須是連續(xù)的C. 一定是不連續(xù)的D.連續(xù)不連續(xù)都可以6 .有如下定義struct Snode int data; struct Snode *next; *p, *q;則將新結(jié)點(diǎn)q插入到單鏈表的p結(jié)點(diǎn)之后，下面的操作【】是正確的。A. q=p-> next;p-> next =q-> next;B. p-> next =q-> next;q=p-> next;C. q-> next =p-> next;p-> next =q;D. p-> next =q;q-

6、> next =p-> next;7 . 一個(gè)線(xiàn)性順序表第一個(gè)元素的存儲(chǔ)地址是2000,每個(gè)元素長(zhǎng)度為4個(gè)字節(jié)，則第3個(gè)元素的起始存儲(chǔ)地址為【】。A. 2008B. 2000C. 2004D. 20128 .下列關(guān)于二叉樹(shù)的敘述中，正確的是【A.葉子結(jié)點(diǎn)總是比度為2的結(jié)點(diǎn)少一個(gè)B.葉子結(jié)點(diǎn)總是比度為2的結(jié)點(diǎn)多一個(gè)C.葉子結(jié)點(diǎn)數(shù)是度為2的結(jié)點(diǎn)數(shù)的兩倍D.度為2的結(jié)點(diǎn)數(shù)是度為1的結(jié)點(diǎn)數(shù)的兩倍9 .某二叉樹(shù)有5個(gè)度為2的結(jié)點(diǎn)，則該二叉樹(shù)中的葉子結(jié)點(diǎn)數(shù)是【A. 10B. 8C. 6D. 410 . 一棵二叉樹(shù)共有25個(gè)結(jié)點(diǎn)，其中5個(gè)是葉子結(jié)點(diǎn)，則度為1的結(jié)點(diǎn)數(shù)為【A. 16B. 10C.

7、6D. 411 .某二叉樹(shù)共有7個(gè)結(jié)點(diǎn)，其中葉子結(jié)點(diǎn)只有1個(gè)，則該二叉樹(shù)的深度為（假設(shè)根結(jié)點(diǎn)在第1層） 【1 OA. 3 B. 4 C. 6 D. 712 .某二叉樹(shù)有7個(gè)度為2的結(jié)點(diǎn)，則該二叉樹(shù)中的葉子結(jié)點(diǎn)數(shù)是【】A.10B.8C.4D.613 . 一棵深度為k的滿(mǎn)二叉樹(shù)中結(jié)點(diǎn)的個(gè)數(shù)是【】A. 2kB. 2k-1C. 2k-1D. 2k-1-114 .在以下的敘述中，正確的是【A .線(xiàn)性表的線(xiàn)性存儲(chǔ)結(jié)構(gòu)優(yōu)于鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)B.二維數(shù)組是它的每個(gè)數(shù)據(jù)元素為一個(gè)線(xiàn)性表的線(xiàn)性表C.棧的操作方式是先進(jìn)先出D.隊(duì)列的操作方式是先進(jìn)后出15 .以下說(shuō)法正確的是【A.數(shù)據(jù)元素是數(shù)據(jù)的最小單位B.數(shù)據(jù)項(xiàng)是數(shù)據(jù)的

8、基本單位C.數(shù)據(jù)結(jié)構(gòu)是帶有結(jié)構(gòu)的各數(shù)據(jù)項(xiàng)的集合D.數(shù)據(jù)結(jié)構(gòu)是帶有結(jié)構(gòu)的數(shù)據(jù)元素的集合16 .線(xiàn)性表L=(a1, a2,，ai,，an),下列說(shuō)法正確的是【A .每個(gè)元素都有一個(gè)直接前驅(qū)和直接后繼B.線(xiàn)性表中至少要有一個(gè)元素C.表中諸元素的排列順序必須是由小到大或由大到小的D .除第一個(gè)元素和最后一個(gè)元素外其余每個(gè)元素都有一個(gè)且僅有一個(gè)直接前驅(qū)和直接后繼17 .對(duì)于順序線(xiàn)性表的優(yōu)缺點(diǎn)，以下說(shuō)法錯(cuò)誤的是【1A .無(wú)需為表示結(jié)點(diǎn)間的邏輯關(guān)系而增加額外的存儲(chǔ)空間B.可以方便地隨機(jī)存取表中的任一結(jié)點(diǎn)C.插入和刪除操作較方便D.由于順序表要求占用連續(xù)的空間，存儲(chǔ)分配只能預(yù)先進(jìn)行(靜態(tài)分配)18 .在含有n

9、個(gè)結(jié)點(diǎn)的順序存儲(chǔ)的線(xiàn)性表中，在任一結(jié)點(diǎn)i前插入一個(gè)結(jié)點(diǎn)所需移動(dòng)結(jié)點(diǎn)的次數(shù)為【1 0A. n/2B. iC. n-iD. n-i+119 .在含有n個(gè)結(jié)點(diǎn)的順序存儲(chǔ)的線(xiàn)性表中，刪除第i個(gè)結(jié)點(diǎn)所需移動(dòng)結(jié)點(diǎn)的次數(shù)為【1A. n/2B. iC. n-iD. n-i+120 .在含有n個(gè)結(jié)點(diǎn)的順序存儲(chǔ)的線(xiàn)性表中，在任一結(jié)點(diǎn)前插入一個(gè)結(jié)點(diǎn)所需移動(dòng)結(jié)點(diǎn)的平均次數(shù) 為【A. nB. n/2C. (n-1)/2D. (n+1)/221 .在含有n個(gè)結(jié)點(diǎn)的順序存儲(chǔ)的線(xiàn)性表中，刪除一個(gè)結(jié)點(diǎn)所需移動(dòng)結(jié)點(diǎn)的平均次數(shù)為【1A. nB. n/2C. (n-1)/2D. (n+1)/222 .帶頭結(jié)點(diǎn)的單鏈表為空的條件是【1

10、A. head=NULL B, head->next=NULL C, head->next=head D. head!=NULL23 .在一個(gè)單鏈表中，若刪除*p結(jié)點(diǎn)的后繼結(jié)點(diǎn)，則執(zhí)行【1A. q=p->next； p->next=q->next； free(q);B. p=p->next； p->next=p->next->next； free(p);C. p->next=p->next； free(p->next)；D. p=p->next->next； free(p->next)；24 .循環(huán)鏈表的

11、主要優(yōu)點(diǎn)是【】。A.不再需要頭指針了B.已知某個(gè)結(jié)點(diǎn)的位置后，容易找到它的直接前驅(qū)C.在進(jìn)行插入、刪除操作時(shí)，能更好地保證鏈表不斷開(kāi)D.從表中任一結(jié)點(diǎn)出發(fā)都能掃描到整個(gè)鏈表25 .在線(xiàn)性表的下列存儲(chǔ)結(jié)構(gòu)中，讀取元素花費(fèi)時(shí)間最少的是【1A .單鏈表 B.雙鏈表 C.循環(huán)鏈表D .順序表26 .設(shè)棧S和隊(duì)列Q的初始狀態(tài)為空，元素a1,a2,a3,a4,a5,a肱次通過(guò)棧S, 一個(gè)元素出棧后即進(jìn)入 隊(duì)列Q,若出隊(duì)的順序?yàn)閍2,a4,a3,a6,a5,a 1則棧S的容量至少應(yīng)該為【A. 2 B. 3 C. 5 D. 627 .二維數(shù)組A11 , 6采用行序?yàn)橹餍蚍绞酱鎯?chǔ)，每個(gè)數(shù)據(jù)元素占4個(gè)存儲(chǔ)單元，且

12、A0 , 0的存儲(chǔ)地址是1000,則A8, 4的存儲(chǔ)地址是【】。A. 1208 B. 1212 C. 1368 D. 136428 .對(duì)矩陣壓縮存儲(chǔ)是為了【】。A.方便運(yùn)算 B.節(jié)省空間 C.方便存儲(chǔ)D.提高運(yùn)算速度29 .以下說(shuō)法錯(cuò)誤的是【】。A.樹(shù)形結(jié)構(gòu)的特點(diǎn)是一個(gè)結(jié)點(diǎn)可以有多個(gè)直接前驅(qū)B.線(xiàn)性結(jié)構(gòu)中的一個(gè)結(jié)點(diǎn)至多只有一個(gè)直接后繼C.二叉樹(shù)與樹(shù)是兩種不同的數(shù)據(jù)結(jié)構(gòu)D.樹(shù)(及一切樹(shù)形結(jié)構(gòu))是一種“分支層次結(jié)構(gòu)30 .以下說(shuō)法錯(cuò)誤的是【】。A.二叉樹(shù)可以是空集B.二叉樹(shù)的任一結(jié)點(diǎn)都有兩棵子樹(shù)C.二叉樹(shù)與樹(shù)具有相同的樹(shù)形結(jié)構(gòu)D、二叉樹(shù)中任一結(jié)點(diǎn)的兩棵子樹(shù)有次序之分31 . 一棵二叉樹(shù)滿(mǎn)足下列條件

13、：對(duì)任意結(jié)點(diǎn)，若存在左、右子樹(shù)，則其值都小于它的左子樹(shù)上所有 結(jié)點(diǎn)的值，而大于右子樹(shù)上所有結(jié)點(diǎn)的值?，F(xiàn)采用【】遍歷方式就可以得到這棵二叉樹(shù)所有結(jié)點(diǎn)的遞減序列。A .前序 B .中序 C.后序 D.層次32 .對(duì)含有】個(gè)結(jié)點(diǎn)的非空二叉樹(shù)，采用任何一種遍歷方式，其結(jié)點(diǎn)訪(fǎng)問(wèn)序列均相同。A. 0 B. 1C. 2 D.不存在這樣的二叉樹(shù)33 .已知某二叉樹(shù)的后序遍歷序列是 deacb),中序遍歷序列是deabG它的前序遍歷序列是【】。A. acbed B. baedcC. dceab D. cedba34 .某二叉樹(shù)的前序遍歷的結(jié)點(diǎn)訪(fǎng)問(wèn)順序是abdgcefh,中序遍歷的結(jié)點(diǎn)訪(fǎng)問(wèn)順序是 dgbaechf

14、,則其后序遍歷的結(jié)點(diǎn)訪(fǎng)問(wèn)順序是11A. bdgcefha B. gdbecfha C. bdgechfa D. gdbehfca35 .在圖6-2中的二叉樹(shù)中，【】不是完全二叉樹(shù)。36 .樹(shù)最適合用來(lái)表示【】。A.有序數(shù)據(jù)元素B.無(wú)序數(shù)據(jù)元素C.元素之間具有分支層次關(guān)系的數(shù)據(jù)D.元素之間無(wú)聯(lián)系的數(shù)據(jù)37 .在計(jì)算遞歸函數(shù)時(shí)，如不使用遞歸過(guò)程，則一般情況下必須借助于【】數(shù)據(jù)結(jié)構(gòu)。A.棧 B.樹(shù)C.雙向隊(duì)列 D.順序表38 .對(duì)于一個(gè)具有N個(gè)頂點(diǎn)的無(wú)向圖，若采用鄰接矩陣表示，則該矩陣的大小是【1A. N B. (N-1)*(N-1) C. N-1 D. N*N39 .以下說(shuō)法錯(cuò)誤的是【】。A.用鄰

15、接矩陣法存儲(chǔ)圖時(shí)，在不考慮壓縮存儲(chǔ)的情況下，所占用的存儲(chǔ)空間大小只與圖中結(jié) 點(diǎn)個(gè)數(shù)有關(guān)，而與圖的邊數(shù)無(wú)關(guān)B.鄰接表法只能用于有向圖的存儲(chǔ)，而鄰接矩陣法對(duì)于有向圖和無(wú)向圖的存儲(chǔ)都適用C.存儲(chǔ)無(wú)向圖的鄰接矩陣是對(duì)稱(chēng)的，因此也可以只存儲(chǔ)鄰接矩陣的下(或上)三角部分D.用鄰接矩陣A表示圖，判定任意兩個(gè)結(jié)點(diǎn) Vi和Vj之間是否有長(zhǎng)度為m的路徑相連，則只 要檢查Am的第i行第j列的元素是否為0即可、填空題1 .通常，數(shù)據(jù)在計(jì)算機(jī)中的存儲(chǔ)結(jié)構(gòu)有 存儲(chǔ)2構(gòu)、存儲(chǔ)2構(gòu)、存儲(chǔ)結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)四種基本存儲(chǔ)結(jié)構(gòu)。2 .設(shè)循環(huán)隊(duì)列的容量為70 (序號(hào)為170),現(xiàn)經(jīng)過(guò)一系列的入隊(duì)與退隊(duì)運(yùn)算后，有： .front= 14,

16、 rear = 21,循環(huán)隊(duì)列中有 個(gè)元素 .front = 23, rear = 12,循環(huán)隊(duì)列中有 個(gè)元素3 .單鏈表表示法的基本思想是用 表示結(jié)點(diǎn)間的邏輯關(guān)系。4 .棧的邏輯特點(diǎn)是,隊(duì)列的邏輯特點(diǎn)是5 . :可以作為實(shí)現(xiàn)遞歸函數(shù)調(diào)用的一種數(shù)據(jù)結(jié)構(gòu)。6 .在隊(duì)列中，新插入的結(jié)點(diǎn)只能添加到 o7 .設(shè)用一維數(shù)組An來(lái)表示一個(gè)棧，令 A0為棧底。用整型變量t來(lái)指示當(dāng)前棧頂?shù)奈恢?，At 為棧頂元素。往棧中壓入一個(gè)新元素時(shí)，變量 t的值,從棧中彈出一個(gè)元素時(shí)，變量 t的值。設(shè)空棧時(shí)，輸入序列a, b, c經(jīng)過(guò)push, pop, push, push, pop操作后，從棧中彈出的元 素是。8 .樹(shù)

17、(及一切樹(shù)形結(jié)構(gòu))是一種結(jié)構(gòu)。在樹(shù)中，結(jié)點(diǎn)沒(méi)有直接前驅(qū)。9 .二叉樹(shù)第i(i>0)層上至多有個(gè)結(jié)點(diǎn)。10 .深度為k(k>0)的二叉樹(shù)至多有 個(gè)結(jié)點(diǎn)。11 .二叉樹(shù)通常有 存儲(chǔ)結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)兩類(lèi)存儲(chǔ)結(jié)構(gòu)。12 .對(duì)二叉鏈表的訪(fǎng)問(wèn)只能從 指針開(kāi)始。13 .對(duì)無(wú)向圖，其鄰接矩陣是一個(gè)關(guān)于 對(duì)稱(chēng)的矩陣。14 .請(qǐng)?zhí)羁胀瓿删€(xiàn)性表在順序存儲(chǔ)下的插入運(yùn)算程序：在線(xiàn)性表 v中第i個(gè)位置插入值為x的元素 struct sqlistint elemMAXSIZE;int last;void insert(sqlist v, int i, int x)int k;if (i<1 | i>v

18、.last+1)printf(''插入位置不合適！ n” );else if (v.last>= MAXSIZE -1) printf("線(xiàn)性表已滿(mǎn)！ n" );elsefor( k = v.last; k >= i; k-) v.elemi = x;v.last+; 15 .請(qǐng)?zhí)羁胀瓿删€(xiàn)性表在順序存儲(chǔ)下的刪除運(yùn)算程序：在線(xiàn)性表v中刪除第i個(gè)位置的元素struct sqlistint elemMAXSIZE;int last;void delete(sqlist v, int i) int k;if (i<1 | i>v.last)p

19、rintf("刪除位置不合適！n”);else for( k = i+1; k <= v.last; k+ )v.elemk-1 = v.elemk;16 .請(qǐng)?zhí)羁胀瓿蓷Ｔ陧樞虼鎯?chǔ)下的入棧運(yùn)算程序：將值為x的元素入棧sstruct stack int sDataMAXSIZE;int top;/棧頂指針，指向當(dāng)前棧頂?shù)奈恢?void push(struct stack s, int x)/ 入棧運(yùn)算if (s.top = MAXSIZE-1) printf("棧滿(mǎn)溢出 n''); elses.sDatatop=x;17 .請(qǐng)?zhí)羁胀瓿蓷Ｔ陧樞虼鎯?chǔ)下的出棧

20、運(yùn)算程序：棧 s出棧，并將出棧元素作為函數(shù)返回值返回 struct stack int sDataMAXSIZE;int top;/棧頂指針，指向當(dāng)前棧頂?shù)奈恢?int pop(struct stack s) /退(出)棧運(yùn)算 int x;if (s.top = -1)printf("?？找绯?n'');exit(1); else x=s.sDatatop;return x;三、判斷題1 .順序存儲(chǔ)的線(xiàn)性表可以隨機(jī)存取。2 .順序存儲(chǔ)的線(xiàn)性表的插入和刪除操作不需要付出很大的代價(jià)，因?yàn)槠骄看尾僮髦挥薪话氲?元素需要移動(dòng)。3 .在線(xiàn)性表的順序存儲(chǔ)結(jié)構(gòu)中，邏輯上相鄰的兩

21、個(gè)元素在物理位置上不一定相鄰。4 .在線(xiàn)性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，邏輯上相鄰的元素在物理位置上不一定相鄰。5 .在單鏈表中，可以從頭結(jié)點(diǎn)開(kāi)始查找任何一個(gè)元素。6 .線(xiàn)性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)優(yōu)于順序存儲(chǔ)結(jié)構(gòu)。7 .在線(xiàn)性表的順序存儲(chǔ)結(jié)構(gòu)中，插入和刪除元素時(shí)，移動(dòng)元素的個(gè)數(shù)與該元素的位置有關(guān)。8 .在單鏈表中，要取得某個(gè)元素，只要知道該元素的指針即可，因此，單鏈表是隨機(jī)存取的存儲(chǔ) 結(jié)構(gòu)。9 .順序存儲(chǔ)方式只能用于存儲(chǔ)線(xiàn)性結(jié)構(gòu)。10 .循環(huán)隊(duì)列中元素個(gè)數(shù)為rear-front。11 . 一個(gè)棧的輸入序列是1,2,3,4,則在棧的輸出序列中可以得到 4,3,1212 .若以鏈表作為棧的存儲(chǔ)結(jié)構(gòu)，則入棧需要判斷

22、棧是否滿(mǎn).13 .數(shù)組是同類(lèi)型值的集合。14 .數(shù)組是一組連續(xù)的內(nèi)存單元。15 .數(shù)組是一種復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，數(shù)組元素之間的關(guān)系既不是線(xiàn)性的也不是樹(shù)形的。16 .插入和刪除操作是數(shù)據(jù)結(jié)構(gòu)中最基本的兩種操作，所以這兩種操作在數(shù)組中也經(jīng)常使用。17 .使用三元組表示稀疏矩陣的元素，有時(shí)并不能節(jié)省存儲(chǔ)空間。18 .二叉樹(shù)是樹(shù)的特殊形式。19 .樹(shù)和二叉樹(shù)之間最主要的差別是：二叉樹(shù)的結(jié)點(diǎn)的子樹(shù)要區(qū)分為左右子樹(shù)，即使在結(jié)點(diǎn)只有一 棵子樹(shù)的情況下也要明確指出該子樹(shù)是左子樹(shù)還是右子樹(shù)。20 .用鄰接矩陣法存儲(chǔ)圖時(shí)，所占用的存儲(chǔ)空間大小僅與圖中結(jié)點(diǎn)個(gè)數(shù)有關(guān)。21 .存儲(chǔ)有向圖的鄰接矩陣一定是對(duì)稱(chēng)的。四、簡(jiǎn)答應(yīng)用

23、題1 .有三個(gè)元素的進(jìn)棧序列是 1,2, 3,舉出此三個(gè)元素可能的出棧序列，并寫(xiě)出相應(yīng)的進(jìn)棧和出 棧操作序列（假設(shè)以I和。表示進(jìn)棧和出棧操作）。2 .試將下列稀疏矩陣A用三元組（三列二維表格）形式來(lái)表示，并寫(xiě)出對(duì)應(yīng)的輔助向量POS和NUM。400000300000006500003 .試寫(xiě)出對(duì)下圖所示的二叉樹(shù)分別按前序、中序和后序遍歷時(shí)得到的結(jié)點(diǎn)序列。4 .畫(huà)出下圖所示的樹(shù)對(duì)應(yīng)的二叉樹(shù)。5 .請(qǐng)寫(xiě)出下圖對(duì)應(yīng)的關(guān)聯(lián)矩陣R及求值矩陣V,結(jié)點(diǎn)A,B,C,D,E分別用1,2,3,4,5編號(hào)6 .邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)是什么關(guān)系？7 .描述以下三個(gè)概念的區(qū)別：頭指針，頭結(jié)點(diǎn)，首元結(jié)點(diǎn)（第一個(gè)元素結(jié)點(diǎn)）。8

24、.何時(shí)選用順序表，何時(shí)選用鏈表作為線(xiàn)性表的存儲(chǔ)結(jié)構(gòu)為宜？9 .如果有n個(gè)線(xiàn)性表同時(shí)共存，并且在處理過(guò)程中各表的長(zhǎng)度會(huì)發(fā)生動(dòng)態(tài)變化，線(xiàn)性表的總長(zhǎng)度 也會(huì)自動(dòng)地改變。在此情況下，應(yīng)選擇哪一種存儲(chǔ)結(jié)構(gòu)？為什么？10 .若線(xiàn)性表的總數(shù)基本穩(wěn)定，且很少進(jìn)行插入、刪除操作，但要求以最快的方式存取線(xiàn)性表的元 素，應(yīng)該用哪種存儲(chǔ)結(jié)構(gòu)？為什么？11 .設(shè)計(jì)算法并寫(xiě)出程序，實(shí)現(xiàn)“計(jì)算帶頭結(jié)點(diǎn)的單鏈表的結(jié)點(diǎn)個(gè)數(shù)”。12 .已知一棵二叉樹(shù)的中序序列和后序序列分別為 BDCEAFHG和DECBHGFA，試畫(huà)出這棵二叉樹(shù), 并寫(xiě)出其前序遍歷序列。第三章查找與排序、選擇題1.對(duì)采用折半查找法進(jìn)行查找操作的查找表，要求按【】

25、方式進(jìn)行存儲(chǔ)。A .順序存儲(chǔ)B.鏈?zhǔn)酱鎯?chǔ)C .順序存儲(chǔ)且結(jié)點(diǎn)按關(guān)鍵字有序D.鏈?zhǔn)酱鎯?chǔ)且結(jié)點(diǎn)按關(guān)鍵字有序2 .設(shè)有序表的關(guān)鍵字序列為(1, 4, 6, 10, 18, 35, 42, 53, 67, 71, 78, 84, 92, 99),當(dāng)用折 半查找法查找鍵值為35的結(jié)點(diǎn)時(shí)，經(jīng)【 】次比較后查找成功。A. 2 B. 3 C. 4 D. 63 .分塊查找的時(shí)間性能1A .低于折半查找B.高于順序查找而低于折半查找C.高于順序查找D .低于順序查找而高于折半查找4 .設(shè)哈希函數(shù)為H(key尸key%7, 一組關(guān)鍵字為(37, 21, 9, 20, 30, 19, 46),哈希表T的地址 空間為0

26、.6,用線(xiàn)性探測(cè)法解決沖突，依次將這組關(guān)鍵字插入T中，得到的哈希表為【1A. 012 342120 37 9 46 30 196206206B. 0123452146379301921 19 937 30 46D. 012345C. 01234520 37 3021 46 195 .設(shè)有一個(gè)用線(xiàn)性探測(cè)法解決沖突得到的哈希表：0123456789101325801617614哈希函數(shù)為H(key)=key%11,若要查找元素14,探測(cè)的次數(shù)是【A. 3 B. 6 C. 7 D. 96 .在哈希函數(shù)H(key)=key %m中，一般來(lái)講，m應(yīng)取【A .奇數(shù) B .偶數(shù) C.素?cái)?shù) D.充分大的數(shù)7

27、.以下說(shuō)法錯(cuò)誤的是【A.哈希法存儲(chǔ)的基本思想是由關(guān)鍵字的值決定數(shù)據(jù)的存儲(chǔ)地址8 .哈希表的結(jié)點(diǎn)中只包含數(shù)據(jù)元素自身的信息，不包含任何指針C.哈希表的基本思想與順序查找、對(duì)分查找和分塊查找都不同D .哈希表的查找效率主要取決于哈希表造表時(shí)選取的哈希函數(shù)和處理沖突的方法8 .在關(guān)鍵字隨機(jī)分布的情況下，用二叉排序樹(shù)的方法進(jìn)行查找，具平均查找長(zhǎng)度與【】查找方法量級(jí)相當(dāng)。A .分塊 B .順序 C .折半D.散列9 .在具有n個(gè)結(jié)點(diǎn)的二叉排序樹(shù)中查找一個(gè)元素時(shí)，最壞情況下的時(shí)間復(fù)雜度為【A. O(n)B. O(1) C. O(log2n)D. O(n2)10 .哈希表的平均查找長(zhǎng)度()。A.與處理沖突的

28、方法有關(guān)而與表的長(zhǎng)度無(wú)關(guān)B.與處理沖突的方法無(wú)關(guān)而與表的長(zhǎng)度有關(guān)C.與處理沖突的方法有關(guān)且與表的長(zhǎng)度有關(guān)D.與處理沖突的方法無(wú)關(guān)且與表的長(zhǎng)度無(wú)關(guān)11 .有數(shù)據(jù)(49,32,40,6,45,12,56),從空二叉樹(shù)開(kāi)始依次插入數(shù)據(jù)形成二叉排序樹(shù)，若希望高度最小, 則應(yīng)選擇下列【】輸入序列。A. 45,12,49,6,40,56,32B. 40,12,6,32,49,45,56C. 6, 12, 32,40,45,49,56D. 32,12,6,40,45,56,4912 .在一棵深度為h的具有n個(gè)元素的二叉排序樹(shù)中，查找所有元素的最長(zhǎng)查找長(zhǎng)度為【1A. n B. log2nC. (h+1)/2

29、D. h13.1 方法是從未排序序列中依次取出元素與已經(jīng)排序序列中的元素進(jìn)行比較，將其放人已經(jīng) 排序序列的正確位置上。A.雙向冒泡排序B .插入排序C.冒泡排序D.選擇排序14.1】方法是從未排序序列中挑選元素，并將其依次放入已經(jīng)排序序列的一端。A.雙向冒泡排序B .插入排序C.冒泡排序D.選擇排序二、填空題1 .索引順序表上的查找分兩個(gè)階段：一、 ;二、該查找方法稱(chēng)為 查找。2 .二叉排序樹(shù)是一種特殊的、增加了限制條件的二叉樹(shù)，其限制條件是任一結(jié)點(diǎn)的鍵值 于其左 孩子(及其子孫)的鍵值且 于其右孩子(及其子孫)的鍵值。3 .中序遍歷一棵二叉排序樹(shù)所得到的結(jié)點(diǎn)訪(fǎng)問(wèn)序列是鍵值的 序列。4 .二叉

30、排序樹(shù)上的查找長(zhǎng)度不僅與 :有關(guān)，也與二叉排序樹(shù)的 號(hào)關(guān)。5 .折半查找方法僅適用于這樣的表：表中的記錄必須 ,其存儲(chǔ)結(jié)構(gòu)必須是。6 .按照排序過(guò)程涉及的存儲(chǔ)設(shè)備的不同，排序可分為 排序和排序。7 .請(qǐng)?zhí)羁胀瓿身樞虿檎宜惴ǔ绦颍涸诰€(xiàn)性表v中查找值為k的元素struct sqlist int elemMAXSIZE;int last;int seqsearch (struct sqlist v, int k) int i；for(i=1;i<=v.last;i+)if()return i; /*查找成功，返回被查元素在表中相對(duì)位置*/return 0; /*查找失敗，返回0*/ 8 .請(qǐng)?zhí)?/p>

31、空完成改進(jìn)型的順序查找算法程序：在線(xiàn)性表v中查找值為k的元素struct sqlistint elemMAXSIZE;int last;；int seqsearch (struct sqlist v, int k) int i;v.elem0=k;while()i-;return i;/*返回被查元素在表中相對(duì)位置，0為失敗，其他為成功*/9 .請(qǐng)?zhí)羁胀瓿蓪?duì)分查找算法程序：在線(xiàn)性表v中查找值為x的元素struct sqlistint elemMAXSIZE;int last;；int search (struct sqlist v, int x ) int low, high, mid;low

32、 = 1; high = v.last;while () mid = (low + high )/2;中間位置元素下標(biāo)if ()return mid;/返回被查元素在表中相對(duì)位置if ()high=mid - 1; 取前半部分 else /取后半部分 return (-1); /查找失敗，返回-110 .請(qǐng)?zhí)羁胀瓿蛇x擇排序算法程序：在具有 n個(gè)元素的線(xiàn)性表R按關(guān)鍵字進(jìn)行排序 struct record int key;int otheritem;void selectsort(struct record R口,int n)/*注意待排記錄放在R1到Rn中*/int i,j,k; struct

33、record temp;for(i=1;i<n;i+) k=i;for(;j<=n;j+) if(Rj.keyvRk.key)if(i!=k)/*交換元素，設(shè)結(jié)構(gòu)體變量可以整體賦值*/temp=Rk; Rk=Ri; Ri=temp;三、判斷題1 .分塊查找方法的平均查找長(zhǎng)度低于順序查找，高于折半查找。2 .在任一二叉排序樹(shù)上查找某個(gè)結(jié)點(diǎn)的查找時(shí)間都小于用順序查找法查找同樣結(jié)點(diǎn)的線(xiàn)性表的查 找時(shí)間。3 .雖然關(guān)鍵字序列的順序不一樣，但依次生成的二叉排序樹(shù)卻是一樣的四、簡(jiǎn)答應(yīng)用題1 .將關(guān)鍵字序列26,25,3,38, 6,7,12,24依次填入長(zhǎng)度為n=12的線(xiàn)性哈希表中，哈希碼為i

34、=INT(k / 4)+ 1,并指出各關(guān)鍵字元素在插入過(guò)程中的沖突次數(shù)。2 .依次輸入以下元素序列：12,6,3,20,18,346請(qǐng)按照輸入的順序構(gòu)造一棵二叉排序樹(shù)，并計(jì)算出要在這棵二叉排序樹(shù)中查找18,需要比較多少次？3 .有如下序列：12,6,20,18,34,10,請(qǐng)分別寫(xiě)出用冒泡法、選擇法、插入法對(duì)該序列進(jìn)行排序的過(guò) 程，并作出適當(dāng)?shù)臉?biāo)示。第四章資源管理技術(shù)一、選擇題1 .操作系統(tǒng)是計(jì)算機(jī)系統(tǒng)的一種【A.應(yīng)用軟件 B.系統(tǒng)軟件 c.通用軟件 D.工具軟件2 .允許多個(gè)用戶(hù)以交互方式使用計(jì)算機(jī)的操作系統(tǒng)是【1A.分時(shí)操作系統(tǒng)B .批處理單道系統(tǒng) C.實(shí)時(shí)操作系統(tǒng)D .批處理多道系統(tǒng)3

35、.下列系統(tǒng)中【】是實(shí)時(shí)系統(tǒng)。A.計(jì)算機(jī)圖像處理系統(tǒng)B.辦公自動(dòng)化系統(tǒng)C.化學(xué)反應(yīng)堆控制系統(tǒng)D .計(jì)算機(jī)輔助設(shè)計(jì)系統(tǒng)4 .操作系統(tǒng)是一種系統(tǒng)軟件，它【A .控制程序的執(zhí)行B.管理計(jì)算機(jī)系統(tǒng)的資源C.方便用戶(hù)使用計(jì)算機(jī)D.管理計(jì)算機(jī)系統(tǒng)的資源和控制程序的執(zhí)行5 .實(shí)時(shí)操作系統(tǒng)對(duì)可靠性和安全性要求極高，它【A.十分注重系統(tǒng)資源的利用率B.不強(qiáng)調(diào)響應(yīng)速度C.不強(qiáng)求系統(tǒng)資源的利用率 D.不必向用戶(hù)反饋信息1.1 】為用戶(hù)分配主存空間，保護(hù)主存中的程序和數(shù)據(jù)不被破壞，提高主存空間的利用率。A,處理器管理B.存儲(chǔ)管理C.文件管理 D .作業(yè)管理7 .財(cái)務(wù)管理軟件是一種專(zhuān)用程序，它屬于【】A.系統(tǒng)軟件B.應(yīng)用

36、軟件 C.接口軟件D.支援軟件8 .在多道程序設(shè)計(jì)技術(shù)的計(jì)算機(jī)系統(tǒng)中，中央處理器【1A.只能被一個(gè)程序占用B.可以被多個(gè)程序同時(shí)占用C.可以被多個(gè)程序交替占用 D.可以被操作系統(tǒng)和另一個(gè)程序同時(shí)占用二、填空題1.計(jì)算機(jī)是由硬件系統(tǒng)和 系統(tǒng)組成。2,使計(jì)算機(jī)系統(tǒng)使用方便和 是操作系統(tǒng)的兩個(gè)主要設(shè)計(jì)目標(biāo)。3 .批處理操作系統(tǒng)、和實(shí)時(shí)操作系統(tǒng)是基本的操作系統(tǒng)。4 .用戶(hù)要求計(jì)算機(jī)系統(tǒng)中進(jìn)行處理的一個(gè)計(jì)算機(jī)問(wèn)題稱(chēng)為 o5 .在多道操作系統(tǒng)控制下，允許多個(gè)作業(yè)同時(shí)裝入 ,使中央處理器輪流地執(zhí)行各個(gè)作業(yè)。6 .批處理操作系統(tǒng)提高了計(jì)算機(jī)系統(tǒng)的 ，但在作業(yè)執(zhí)行時(shí)用戶(hù)不能直接干預(yù)作業(yè)的執(zhí)行。7 .在分時(shí)系統(tǒng)中

37、，每個(gè)終端用戶(hù)每次可以使用一個(gè)由 規(guī)定的CPU時(shí)間。8 .分時(shí)系統(tǒng)具有同時(shí)性、獨(dú)立性、及時(shí)性和 等特點(diǎn)。9 .若干個(gè)進(jìn)程均因互相等待對(duì)方所占有的資源而無(wú)限地等待，使計(jì)算機(jī)系統(tǒng)無(wú)法繼續(xù)正常運(yùn)行的現(xiàn)象，稱(chēng)之為 010 .當(dāng)多個(gè)進(jìn)程需要對(duì)系統(tǒng)中的同一個(gè)數(shù)據(jù)塊進(jìn)行操作時(shí)，進(jìn)程之間常用的通信方式有兩種：當(dāng)多 個(gè)進(jìn)程共享數(shù)據(jù)塊或其他排他性使用的資源時(shí)，不能同時(shí)進(jìn)入存取或使用，這種稱(chēng)為 ;進(jìn)程之間為了合作完成一個(gè)任務(wù)，而需要互相等待和互相交換信息的相互制約關(guān)系稱(chēng)為 三、簡(jiǎn)答題1 .計(jì)算機(jī)系統(tǒng)的資源包括哪些？2 .為計(jì)算機(jī)設(shè)計(jì)操作系統(tǒng)要達(dá)到什么目的 ？設(shè)計(jì)時(shí)應(yīng)考慮哪些目標(biāo)？3 .簡(jiǎn)述操作系統(tǒng)的五大功能。4 .

38、簡(jiǎn)述程序和進(jìn)程的區(qū)別。5 .簡(jiǎn)述進(jìn)程的三種狀態(tài)及其轉(zhuǎn)化過(guò)程參考答案第一章一、選擇題DADDC二、填空題1. 列舉法、歸納法、遞推法、遞歸法、減半遞推法2. 可行性、確定性3. O(n)24. O(n2)5. O(log2n)6. n、n(n+1)/2、O(n2)7. 1、log2n、n、n2、2n三、判斷題X第二章一、選擇題BDCDBD CABCA DBBBDCADB二、填空題1.順序、鏈?zhǔn)?、索引、散?.7、593 .指針4 .后進(jìn)先出、先進(jìn)先出5 .棧6 .隊(duì)尾7 .力口 1、減 1、c8 .層次、根9 . 2i-110 . 2k-111 .順序、鏈?zhǔn)?2 .根13 .主對(duì)角線(xiàn)14 . v

39、.elemk+1 = v.elemk;15 . v.last-;16 . s.top+;17 . s.top-;三、判斷題vxxw xvxxxBCDCB CBADD BABABDBBDCxxvvx xvxw四、簡(jiǎn)答應(yīng)用題1.出棧序列I口Z2132313212.操作序列TOI_OiIO1IOIIOOIIIOIOIIIOO行號(hào)域列號(hào)域值域14542114332343465445k1234POS2335NUM10213.前序遍De DEABC 中序遍歷：EDBAC 后序遍歷：DACBE5.0 110 010 0 11R=1 0 0 1 00 110 00 10 0 001 0 1 1-卜1 00 -

40、 1 1 3V = 1 1 - 101 2-1 1 3 1 2 0 -1 8 -1-1 018116 .答：在數(shù)據(jù)結(jié)構(gòu)中，邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)是密切相關(guān)的，存儲(chǔ)結(jié)構(gòu)不僅將數(shù)據(jù)元素存儲(chǔ)到計(jì)算 機(jī)中，而且還要表示各數(shù)據(jù)元素之間的邏輯關(guān)系。邏輯結(jié)構(gòu)與計(jì)算機(jī)無(wú)關(guān)，存儲(chǔ)結(jié)構(gòu)是數(shù)據(jù)元素之 間的關(guān)系在計(jì)算機(jī)中的表示。7 .答：首元結(jié)點(diǎn)是指鏈表中存儲(chǔ)的線(xiàn)性表中的第一個(gè)數(shù)據(jù)元素的結(jié)點(diǎn)。為了操作方便，通常在鏈 表的首元結(jié)點(diǎn)之前附設(shè)一個(gè)結(jié)點(diǎn)，稱(chēng)為頭結(jié)點(diǎn)。頭指針是指向鏈表中的第一個(gè)結(jié)點(diǎn)的指針。8 .答：從空間上來(lái)看，當(dāng)線(xiàn)性表的長(zhǎng)度變化較大、難以估計(jì)其規(guī)模時(shí)，選用動(dòng)態(tài)的鏈表作為存儲(chǔ)結(jié)構(gòu)比較合適，但鏈表除了需要設(shè)置數(shù)據(jù)域外

41、，還要額外設(shè)置指針域，因此當(dāng)線(xiàn)性表長(zhǎng)度變化不大、 易于事先確定規(guī)模時(shí)，為了節(jié)約存儲(chǔ)空間，宜采用順序存儲(chǔ)結(jié)構(gòu)。從時(shí)間上來(lái)看，若線(xiàn)性表的操作 主要是查找，很少進(jìn)行插入和刪除操作時(shí)，應(yīng)選用順序表。對(duì)于頻繁進(jìn)行插入和刪除操作的線(xiàn)性表， 宜采用鏈表作為存儲(chǔ)結(jié)構(gòu)。9 .答：應(yīng)選用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。因?yàn)轫樞虮硎庆o態(tài)存儲(chǔ)結(jié)構(gòu)，只能預(yù)先分配，不能隨著線(xiàn)性表長(zhǎng)度 的改變而變化。而鏈表則可根據(jù)需要?jiǎng)討B(tài)地申請(qǐng)空間，因此適用于動(dòng)態(tài)變化表長(zhǎng)的線(xiàn)性表。10 .答：應(yīng)選用順序存儲(chǔ)結(jié)構(gòu)。因?yàn)轫樞虼鎯?chǔ)結(jié)構(gòu)存取元素操作的時(shí)間復(fù)雜度為0(1)。11 .答：int number(Linkedlist *head)/計(jì)算單鏈表中結(jié)點(diǎn)的個(gè)數(shù)p=head >next；i=0 ；wh