計(jì)算機(jī)軟件基礎(chǔ)(考試試題講解)(自考本科)

1、計(jì)算機(jī) 軟件基礎(chǔ)2010年考試試題講解一、單項(xiàng)選擇題1. 已知int x = 17 , y = 5 ; , 則表達(dá)式 x / y 的值是（ ）A. 0 B. 2C. 3 D. 3.4 答題要點(diǎn)：兩個(gè)整數(shù)相除，商為整數(shù)。答 案：C一、單項(xiàng)選擇題2. 已知int x = 3 , y = 5 , z = 7 ; , 則表達(dá)式 x y ? x : ( y z ? y : z)的值是（ ）A. 0 B. 3C. 5 D. 7 答題要點(diǎn)：表達(dá)式1 ？表達(dá)式2 ：表達(dá)式3 ；答 案：D一、單項(xiàng)選擇題3. 執(zhí)行下列C語(yǔ)言程序段，循環(huán)體被執(zhí)行的次數(shù)是（ ）A. 2 B. 3C. 4 D. 無(wú)限 答 案：cfor

2、 ( i = 0 , j = 0 ; ( j != 4 ) | ( i 3 ) ; j+ , i+ )printf ( “ % d “ , j );一、單項(xiàng)選擇題答題要點(diǎn)：for ( 表達(dá)式1 ；表達(dá)式2 ；表達(dá)式3） 循環(huán)體；表達(dá)式1表達(dá)式2表達(dá)式3ij( j != 4 ) | ( i num B. * pp - numC. ( * pp ) - num D. ( * pp ) . num 則對(duì)結(jié)構(gòu)變量成員正確的引用是（ ）一、單項(xiàng)選擇題答題要點(diǎn)：結(jié)構(gòu)變量的引用問(wèn)題。(1) - 符號(hào)前面必須是某結(jié)構(gòu)類(lèi)型指針；(2) . 符號(hào)前面必須是某結(jié)構(gòu)類(lèi)型變量或某結(jié)構(gòu)類(lèi)型指針?biāo)傅淖兞?；一、單?xiàng)選擇題8

3、. 若入棧數(shù)據(jù)元素序列是 a , b , c , d , 則不可能的出棧序列是（ ）答 案：DA. a , b , c , d B. c , b , a , dC. d , c , b , a D. d , b , c , a 答題要點(diǎn)：原序列中最后一個(gè)元素最先出棧時(shí)，所有元素的出棧順序必須與原序列相反，否則，是不可能的。一、單項(xiàng)選擇題9. 對(duì)100個(gè)有序數(shù)據(jù)，若采用二分法查找某一個(gè)元素，比較次數(shù)最多是（ ）答 案：BA. 6 B. 7C. 8 D. 100 答題要點(diǎn)：構(gòu)建一棵判定樹(shù)層數(shù)節(jié)點(diǎn)數(shù)11223448516632737（64）一、單項(xiàng)選擇題10. 線性表采用鏈?zhǔn)絻?chǔ)時(shí)，其存儲(chǔ)空間（ ）答

4、 案：C必須是連續(xù) B. 一定是不連續(xù)的可連續(xù)，也可不連續(xù) D. 多個(gè)節(jié)點(diǎn)地址必須是連續(xù)的 一、單項(xiàng)選擇題11. 對(duì)順序存儲(chǔ)的線性表，其長(zhǎng)度為 n ，在等概率情況下，插入一個(gè)元素需要移動(dòng)元素的平均次數(shù)是（ ）答 案：AA. n/2 B. n-1C. (n+1)/2 D. (n-1)/2 一、單項(xiàng)選擇題12. 一個(gè)深度為k的完全二叉樹(shù)中節(jié)點(diǎn)數(shù)至少有（ ）答 案：BA. 2k B. 2k-1C. 2k+1 D. 2k -1答題要點(diǎn)：p160二叉樹(shù)的性質(zhì) 2 和滿二叉樹(shù)的定義。 一、單項(xiàng)選擇題13. 對(duì) n 個(gè)元素進(jìn)行直接插入排序時(shí)，最多需要進(jìn)行的趟數(shù)是（ ）答 案：BA. n B. n-1C. n

5、+1 D. 2n一、單項(xiàng)選擇題14. 下列 C 語(yǔ)言程序段的時(shí)間復(fù)雜度是（ ） for ( i = 1 ; i = n ; i + ) y = y + 1 ; for ( j= 1 ; j = 2 *n ; j+ ) x = x + 1 ; 答 案：BA. O ( 2 n ) B. O ( n2 )C. O ( n3 ) D. O (n )答題要點(diǎn)：兩重for循環(huán)一、單項(xiàng)選擇題15. 軟件編碼屬于軟件生存周期的（ ）答 案：DA. 軟件定義時(shí)期 B. 軟件維護(hù)時(shí)期C. 軟件運(yùn)行時(shí)期 D. 軟件開(kāi)發(fā)時(shí)期 二、填空題16. 已知int a = 1 , b = 2 , d ; , 執(zhí)行語(yǔ)句d = a

6、 0b next = q - next ; q - next = s ;pP-nexts(1)s-next=p-next;(2)p-next=s;二、填空題22. 若循環(huán)隊(duì)列用數(shù)組 data m 存儲(chǔ)元素值，用front 和 rear 分別作為頭、尾指針，則判斷循環(huán)隊(duì)列空的條件是（ ）front=rear順序隊(duì)列循環(huán)隊(duì)列隊(duì)列空的條件rear=front=-1rear=front隊(duì)列滿的條件front=-1且rear=m-1front=(rear+1)%m隊(duì)列滿時(shí)，所存元素的個(gè)數(shù)m個(gè)m-1個(gè)隊(duì)列在一般情況下，所儲(chǔ)元素的個(gè)數(shù)rear-front（rear-front+m）%m二、填空題23.已知二

7、叉樹(shù)的后序遍歷序列是dabec,中序遍歷序列是debac，它的前序遍歷序列是（ ）cedba答題要點(diǎn)：記住口訣：先序后序定樹(shù)根；中序區(qū)分左和右。答題關(guān)鍵：由給定條件構(gòu)建二叉樹(shù)。cedba二、填空題24.一個(gè)無(wú)向連通圖G中頂點(diǎn)數(shù)為n，圖G的邊數(shù)最少是（ ）n-1答題要點(diǎn)：記住連通圖的必要條件：一個(gè)具有n個(gè)頂點(diǎn)的連通圖，則至少有n-1條邊。二、填空題25.在軟件設(shè)計(jì)時(shí)期，設(shè)計(jì)模塊獨(dú)立性的一般度量準(zhǔn)則是耦合和（ ）內(nèi)聚答題要點(diǎn)：課本P217三、解答題26.已知下圖所示的二叉樹(shù)，要求： （1）將該二叉樹(shù)還原成森林； （2）寫(xiě)出森林的先序（先根）遍歷序列和后序（后根）遍歷序列abdgcefhij解（1）

8、將該二叉樹(shù)還原成森林:abdgcefhij解（1）將該二叉樹(shù)還原成森林（續(xù)）：abdgcefhijabdgcefhij豎線變成左子樹(shù)，橫線變成右子樹(shù)解（1）將該二叉樹(shù)還原成森林（續(xù)）：abdgcefhijabdgcefhij口訣：豎線連接左孩子，橫線連接親兄弟。解（2）先序遍歷序列：abdgcefhijabdcgefhij后序遍歷序列：bgdaecihjf森林的先序遍歷=對(duì)應(yīng)二叉樹(shù)的先序遍歷;森林的后序遍歷=對(duì)應(yīng)二叉樹(shù)的中序遍歷;注意：三、解答題27.如下圖所示的無(wú)向圖，從頂點(diǎn)1開(kāi)始，分別按鄰接頂點(diǎn)序號(hào)由小到大順序給出廣度優(yōu)先遍歷和深度優(yōu)先遍歷的頂點(diǎn)序號(hào)。 1247365廣度優(yōu)先遍歷結(jié)果：1，

9、2，3，7，4，5，6深度優(yōu)先遍歷結(jié)果：1，2，4，5，6，3，7三、解答題28.已知一組關(guān)健字 49，31，12，68，27，要求對(duì)其按升序排序，寫(xiě)出使用直接選擇排序的每趟結(jié)果。原始493112682711231496827212274968313122731685941227315968三、解答題29.某大學(xué)圖書(shū)館對(duì)讀者借閱讀書(shū)制定有關(guān)規(guī)定如下：（1）本科學(xué)生可以借閱5本； （2）研究生：碩士研究生可以借閱7本，博士研究生可以借閱10本； （3）教職工：教授、副教授職稱(chēng)的教師可以借閱15本，其他教職工可以借閱12本。 用判定樹(shù)表示上述算法。讀者借書(shū)其他教職工研究生教職工碩士生博士生教授、副

10、教授本科生借書(shū)5本借書(shū)7本借書(shū)10本借書(shū)15本借書(shū)12本四、程序分析題30.寫(xiě)出下列C語(yǔ)言程序的運(yùn)行結(jié)果 main ( ) int a = 7 ; do switch ( a % 2 ) case 1 : a- ; break ; case 0 : a+ ; break ; a- ; printf ( “ % 5d n ” , a ) ; while ( a 0 ) ; 表達(dá)式非0？ 循環(huán)體 結(jié)束循環(huán)，執(zhí)行下面的語(yǔ)句YN四、程序分析題30.解：aa%2a-(1)a+a-(2)a(print)a0716x551514X331312X111110X-1-10四、程序分析題31.運(yùn)行下列C語(yǔ)言程序，

11、從健盤(pán)上輸入數(shù)字5，寫(xiě)出程序的輸出結(jié)果int fun ( int n ) static int f = 1 ; int k; for ( k = 1 ; k = n ; k+ ) f *= k ; return f ;main( ) int n , i ; scanf ( “ %d “ , & n ) ; for ( i = 1 ; i n ; i+ ) printf ( “ i = %d , r = %d n “ , i , fun ( i ) ) ;四、程序分析題31.解：ii5i(p)nfkk=nf=f*kK+i+1111111121202212211112121232303四、程序分析

12、題31.解：ii5i(p)nfkk=nf=f*kK+i+313321122221434311241240441441211122四、程序分析題31.解：ii5i(p)nfkk=nf=f*kK+i+414412111221221243243172472412885288505四、程序分析題31.解：ii5i(p)nfkk=nf=f*kK+i+5031、答題要點(diǎn)autoregisterstatic類(lèi) 型自動(dòng)型寄存器型靜態(tài)型存儲(chǔ)區(qū)內(nèi)存的堆棧區(qū)CPU的寄存器區(qū)內(nèi)存的數(shù)據(jù)區(qū)特 點(diǎn)在調(diào)用函數(shù)時(shí),分配一個(gè)臨時(shí)的存儲(chǔ)空間，而且調(diào)用結(jié)束時(shí)將所分配的臨時(shí)存儲(chǔ)空間收回；如果不賦初值，則其中是一個(gè)不確定的值。訪問(wèn)效率

13、高；調(diào)用函數(shù)結(jié)束時(shí)，所占用的寄存器被回收。函數(shù)調(diào)用結(jié)束時(shí)，所占用的存儲(chǔ)區(qū)不會(huì)被回收，即變量的值不會(huì)因?yàn)楹瘮?shù)調(diào)用結(jié)束而消失。四、程序分析題32. 下列程序是求一個(gè)有規(guī)律的數(shù)值序列：1，1，2，4，7，13，從第4個(gè)數(shù)開(kāi)始，每一個(gè)數(shù)都是它前邊3個(gè)數(shù)的和，一直求到該數(shù)列的第n（4n18）個(gè)數(shù)，填空完成程序 main () int i=3, n, a=1,b=1,c=2,d; scanf(“%d”,&n); printf (“%d %d %d”, a,b,c); do i+; d=a+b+c; printf (“%d, d); a=b; b=c; ; while ( ) ; c =din四、程序分析題

14、33. 已知順序棧的結(jié)構(gòu)為： #define N 100 struct char data N; int top; s ; 利用順序棧的基本操作（設(shè)push (s, x)和pop (s)函數(shù)已存在，pop (s)函數(shù)返回棧頂元素），設(shè)計(jì)一個(gè)算法如下，判斷一個(gè)字符串是否具有中心對(duì)稱(chēng)（即構(gòu)成回文），若是則返回1，否則返回0。如：ababbaba、abcba都是中心對(duì)稱(chēng)的字符串。填空完成算法。四、程序分析題 int symmetry (char str ) int i, j, k; i=strlen (str); for (j=0; ji/2; j+) ; if ( i % 2 ! = 0 ) k= ( i+1) /2 else k=i/2; for (j=k; j 10時(shí) 當(dāng) | x | 10時(shí) 當(dāng) x -10時(shí)四、程序設(shè)計(jì)題 34. 解：#include float f ( float x )float y ;if ( x 10 )y = sin ( x ) * sin ( x ) + 3 * cos ( x )