2016現(xiàn)代科技學院《軟件技術基礎》練習題+答案

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

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

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

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

5、若采用鏈表存儲結構，要求內存中可用存儲單元的地址11A.必須是連續(xù)的B.部分必須是連續(xù)的C. 一定是不連續(xù)的D.連續(xù)不連續(xù)都可以6 .有如下定義struct Snode int data; struct Snode *next; *p, *q;則將新結點q插入到單鏈表的p結點之后，下面的操作【】是正確的。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 . 一個線性順序表第一個元素的存儲地址是2000,每個元素長度為4個字節(jié)，則第3個元素的起始存儲地址為【】。A. 2008B. 2000C. 2004D. 20128 .下列關于二叉樹的敘述中，正確的是【A.葉子結點總是比度為2的結點少一個B.葉子結點總是比度為2的結點多一個C.葉子結點數(shù)是度為2的結點數(shù)的兩倍D.度為2的結點數(shù)是度為1的結點數(shù)的兩倍9 .某二叉樹有5個度為2的結點，則該二叉樹中的葉子結點數(shù)是【A. 10B. 8C. 6D. 410 . 一棵二叉樹共有25個結點，其中5個是葉子結點，則度為1的結點數(shù)為【A. 16B. 10C.

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

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

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

10、A. head=NULL B, head->next=NULL C, head->next=head D. head!=NULL23 .在一個單鏈表中，若刪除*p結點的后繼結點，則執(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)點是【】。A.不再需要頭指針了B.已知某個結點的位置后，容易找到它的直接前驅C.在進行插入、刪除操作時，能更好地保證鏈表不斷開D.從表中任一結點出發(fā)都能掃描到整個鏈表25 .在線性表的下列存儲結構中，讀取元素花費時間最少的是【1A .單鏈表 B.雙鏈表 C.循環(huán)鏈表D .順序表26 .設棧S和隊列Q的初始狀態(tài)為空，元素a1,a2,a3,a4,a5,a肱次通過棧S, 一個元素出棧后即進入 隊列Q,若出隊的順序為a2,a4,a3,a6,a5,a 1則棧S的容量至少應該為【A. 2 B. 3 C. 5 D. 627 .二維數(shù)組A11 , 6采用行序為主序方式存儲，每個數(shù)據(jù)元素占4個存儲單元，且

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

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

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

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

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

17、(及一切樹形結構)是一種結構。在樹中，結點沒有直接前驅。9 .二叉樹第i(i>0)層上至多有個結點。10 .深度為k(k>0)的二叉樹至多有 個結點。11 .二叉樹通常有 存儲結構和存儲結構兩類存儲結構。12 .對二叉鏈表的訪問只能從 指針開始。13 .對無向圖，其鄰接矩陣是一個關于 對稱的矩陣。14 .請?zhí)羁胀瓿删€性表在順序存儲下的插入運算程序：在線性表 v中第i個位置插入值為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("線性表已滿！ n" );elsefor( k = v.last; k >= i; k-) v.elemi = x;v.last+; 15 .請?zhí)羁胀瓿删€性表在順序存儲下的刪除運算程序：在線性表v中刪除第i個位置的元素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 .請?zhí)羁胀瓿蓷Ｔ陧樞虼鎯ο碌娜霔＿\算程序：將值為x的元素入棧sstruct stack int sDataMAXSIZE;int top;/棧頂指針，指向當前棧頂?shù)奈恢?void push(struct stack s, int x)/ 入棧運算if (s.top = MAXSIZE-1) printf("棧滿溢出 n''); elses.sDatatop=x;17 .請?zhí)羁胀瓿蓷Ｔ陧樞虼鎯ο碌某鰲?/p>

20、運算程序：棧 s出棧，并將出棧元素作為函數(shù)返回值返回 struct stack int sDataMAXSIZE;int top;/棧頂指針，指向當前棧頂?shù)奈恢?int pop(struct stack s) /退(出)棧運算 int x;if (s.top = -1)printf("棧空溢出 n'');exit(1); else x=s.sDatatop;return x;三、判斷題1 .順序存儲的線性表可以隨機存取。2 .順序存儲的線性表的插入和刪除操作不需要付出很大的代價，因為平均每次操作只有近一半的 元素需要移動。3 .在線性表的順序存儲結構中，邏輯上相鄰的兩

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

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

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

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

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

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

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

28、方法有關而與表的長度無關B.與處理沖突的方法無關而與表的長度有關C.與處理沖突的方法有關且與表的長度有關D.與處理沖突的方法無關且與表的長度無關11 .有數(shù)據(jù)(49,32,40,6,45,12,56),從空二叉樹開始依次插入數(shù)據(jù)形成二叉排序樹，若希望高度最小, 則應選擇下列【】輸入序列。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個元素的二叉排序樹中，查找所有元素的最長查找長度為【1A. n B. log2nC. (h+1)/2

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

30、排序樹上的查找長度不僅與 :有關，也與二叉排序樹的 號關。5 .折半查找方法僅適用于這樣的表：表中的記錄必須 ,其存儲結構必須是。6 .按照排序過程涉及的存儲設備的不同，排序可分為 排序和排序。7 .請?zhí)羁胀瓿身樞虿檎宜惴ǔ绦颍涸诰€性表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; /*查找成功，返回被查元素在表中相對位置*/return 0; /*查找失敗，返回0*/ 8 .請?zhí)?/p>

31、空完成改進型的順序查找算法程序：在線性表v中查找值為k的元素struct sqlistint elemMAXSIZE;int last;；int seqsearch (struct sqlist v, int k) int i;v.elem0=k;while()i-;return i;/*返回被查元素在表中相對位置，0為失敗，其他為成功*/9 .請?zhí)羁胀瓿蓪Ψ植檎宜惴ǔ绦颍涸诰€性表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;中間位置元素下標if ()return mid;/返回被查元素在表中相對位置if ()high=mid - 1; 取前半部分 else /取后半部分 return (-1); /查找失敗，返回-110 .請?zhí)羁胀瓿蛇x擇排序算法程序：在具有 n個元素的線性表R按關鍵字進行排序 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)/*交換元素，設結構體變量可以整體賦值*/temp=Rk; Rk=Ri; Ri=temp;三、判斷題1 .分塊查找方法的平均查找長度低于順序查找，高于折半查找。2 .在任一二叉排序樹上查找某個結點的查找時間都小于用順序查找法查找同樣結點的線性表的查 找時間。3 .雖然關鍵字序列的順序不一樣，但依次生成的二叉排序樹卻是一樣的四、簡答應用題1 .將關鍵字序列26,25,3,38, 6,7,12,24依次填入長度為n=12的線性哈希表中，哈希碼為i

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

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

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

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

38、簡述程序和進程的區(qū)別。5 .簡述進程的三種狀態(tài)及其轉化過程參考答案第一章一、選擇題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.順序、鏈式、索引、散列2.7、593 .指針4 .后進先出、先進先出5 .棧6 .隊尾7 .力口 1、減 1、c8 .層次、根9 . 2i-110 . 2k-111 .順序、鏈式12 .根13 .主對角線14 . v

39、.elemk+1 = v.elemk;15 . v.last-;16 . s.top+;17 . s.top-;三、判斷題vxxw xvxxxBCDCB CBADD BABABDBBDCxxvvx xvxw四、簡答應用題1.出棧序列I口Z2132313212.操作序列TOI_OiIO1IOIIOOIIIOIOIIIOO行號域列號域值域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ù)結構中，邏輯結構與存儲結構是密切相關的，存儲結構不僅將數(shù)據(jù)元素存儲到計算 機中，而且還要表示各數(shù)據(jù)元素之間的邏輯關系。邏輯結構與計算機無關，存儲結構是數(shù)據(jù)元素之 間的關系在計算機中的表示。7 .答：首元結點是指鏈表中存儲的線性表中的第一個數(shù)據(jù)元素的結點。為了操作方便，通常在鏈 表的首元結點之前附設一個結點，稱為頭結點。頭指針是指向鏈表中的第一個結點的指針。8 .答：從空間上來看，當線性表的長度變化較大、難以估計其規(guī)模時，選用動態(tài)的鏈表作為存儲結構比較合適，但鏈表除了需要設置數(shù)據(jù)域外

41、，還要額外設置指針域，因此當線性表長度變化不大、 易于事先確定規(guī)模時，為了節(jié)約存儲空間，宜采用順序存儲結構。從時間上來看，若線性表的操作 主要是查找，很少進行插入和刪除操作時，應選用順序表。對于頻繁進行插入和刪除操作的線性表， 宜采用鏈表作為存儲結構。9 .答：應選用鏈式存儲結構。因為順序表是靜態(tài)存儲結構，只能預先分配，不能隨著線性表長度 的改變而變化。而鏈表則可根據(jù)需要動態(tài)地申請空間，因此適用于動態(tài)變化表長的線性表。10 .答：應選用順序存儲結構。因為順序存儲結構存取元素操作的時間復雜度為0(1)。11 .答：int number(Linkedlist *head)/計算單鏈表中結點的個數(shù)p=head >next；i=0 ；wh