計算機(jī)軟件基礎(chǔ)

1、計 算 機(jī) 軟 件 基 礎(chǔ)一、填空題1程序設(shè)計的關(guān)鍵在于設(shè)計出一個好的算法 。2數(shù)據(jù)、數(shù)據(jù)節(jié)點和數(shù)據(jù)項構(gòu)成了數(shù)據(jù)組織的三個層次。其中數(shù)據(jù)項 是具有獨立含義的最小標(biāo)識單位。3數(shù)據(jù)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)之間的相互運(yùn)算是通過算法 來實現(xiàn)的。4所有節(jié)點按1對1的鄰接關(guān)系構(gòu)成的整體就是線性 結(jié)構(gòu)。5表長為0的線性表稱為 空 表。6直接插入排序最好情況的時間復(fù)雜度為 O(n) 。7程序段“i=l；while(i<=n)i=i*2”的時間復(fù)雜度為 O(log2n) 。8c語言屬于計算機(jī)高級語言，既可以用來寫系統(tǒng)軟件，也可以用來寫應(yīng)用軟件 。9算法是有窮的，而程序可以是 無窮的 。10實型常量在一般微型機(jī)

2、中占用 4 個字節(jié)。11char型和int型的運(yùn)算結(jié)果為int 型。12Getchar()和putchar()函數(shù)只能輸入、輸出 1 個字符。13源程序必須翻譯成機(jī)器指令即機(jī)器語言，這一工作由編譯系統(tǒng) 來完成。14字符串的長度為串中字符的個數(shù)，但在內(nèi)存中所占的字節(jié)數(shù)應(yīng)比長度多1 。15執(zhí)行：a=3，b=4，a=a+b，b=a+b后，則a和b的值分別為 7 和11。16對于scanf(“2d3d4d”，&a，&b，&c)語句，若鍵入：l 23456789，則變量b的值為345 。17設(shè)intx=10,y,z；執(zhí)行y=z=x；x=y=-Z后，變量x的結(jié)果是 1 。18若有說

3、明：Int a5=1,2,3,4,5,6,7,8,9,10)，則數(shù)組第一維的大小為2 。19在函數(shù)定義中，若沒有返回值，其類型定義為 空類型 。20c語言規(guī)定不能嵌套定義函數(shù)，但可以嵌套調(diào)用 函數(shù)。21程序中出現(xiàn)的/*.*表示注釋，可以出現(xiàn)在程序的任何 地方。22c語言的數(shù)據(jù)結(jié)構(gòu)是以 數(shù)據(jù)類型 的形式描述出來的。23運(yùn)算符的運(yùn)算對象就為 整數(shù) 。24getchar()函數(shù)只能出現(xiàn)在 表達(dá)式 的位置，接收該函數(shù)的值時可以用字符型或整型變量。25請將xa，寫成一個邏輯表達(dá)式： x<=a&&x>=-a 。26在結(jié)構(gòu)化程序的三種基本結(jié)構(gòu)是指 順序結(jié)構(gòu) 、選擇結(jié)構(gòu)和循環(huán)結(jié)構(gòu)。

4、27在c語言中，二維數(shù)組在內(nèi)存中的排列順序是按 行 存入。28一個完整的c程序可由1個主函數(shù)或由1個主函數(shù)和 若干個 子函數(shù)組成。29在c語言中，變量的使用一般遵守 “先定義，而使用 ”的原則。30c語言中有兩個專門的指針運(yùn)算符*和&，它們都是 單 目運(yùn)算符。31在計算機(jī)的數(shù)據(jù)處理中，將字符、聲音、 光 、圖形和圖像均稱為數(shù)據(jù)。32在線性表的順序存儲結(jié)構(gòu)中，其相鄰的數(shù)據(jù)節(jié)點在物理位置上也是 相鄰 的。33若在數(shù)據(jù)處理中，需要經(jīng)常對數(shù)據(jù)進(jìn)行插入、刪除運(yùn)算，則宜將該數(shù)據(jù)設(shè)置為 鏈?zhǔn)?存儲。34二叉樹的遍歷方法有：先序遍歷、后序遍歷和 中序遍歷 。35單鏈表表示法的基本思想是用指針 表示結(jié)點

5、間的邏輯關(guān)系。36C語言規(guī)定，數(shù)組元素的下標(biāo)從 0 開始，最大值為長度減1。37在C語言中，引用數(shù)組元素時，其數(shù)組下標(biāo)的數(shù)據(jù)類型允許是整型常量或整型 表達(dá)式。38一個變量的作用域是指該變量在程序中的有效范圍，局部變量的作用域就是其所在的 函數(shù) 。39C語言中訪問地址的方式有兩種即直接存取方式和 間接存取 方式。40運(yùn)行下列語句：int*p，*q，x5；p=x；q=p+3；則q指向數(shù)值元素 x3 。41若某問題的空間復(fù)雜度為o(1)，則認(rèn)為該問題所耗空間與問題的 規(guī)模 無關(guān)。42在線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)中，單鏈表中每個節(jié)點是一個 結(jié)構(gòu)類型 。43在三對角陣的壓縮存儲中，已知Aij=Bk，試建立k與

6、i，j之間的關(guān)系為： k=2i+j 。44在軟件的開發(fā)模型中，螺旋模型是一種 風(fēng)險驅(qū)動 模型，它將瀑布模型和原型模型結(jié)合起來。45設(shè)有100個元素，用折半查找法進(jìn)行查找時，最大比較次數(shù)是7 。二、選擇題1下列是C語言正確的標(biāo)識符的是【 D 】A? a Ba=2 Ca.3 Da_32下列表達(dá)式中，值為1的表達(dá)式是 【 D 】 A35 B3/5.0 C3/5 D3<53設(shè)變量a,b,c,d依次為字符型、整型、單精度型、雙精度型，則表達(dá)式“a+bc*d”的數(shù)據(jù)類型為【 D 】 A整型 B字符型 C單精度型 D雙精度型4能正確表達(dá)“0a10”的表達(dá)式是【 A 】 A10>=a&&a

7、mp;a>=0 B (10>=a)ll(a>=0) C0<=a<=10 D(!a<0)&&(!a>10)5在C語言中，main()函數(shù)的位置 【 C 】 A必須作為第一個函數(shù) B必須作為最后一個函數(shù)C可以任意，但必須要在函數(shù)之外 D必須放在它所調(diào)用的函數(shù)之后6對于輸入語句“scanf(“d,d”,&a,&b)”，下面正確的輸入方法是【 A 】 A1,2回車 B12回車 C1回車2回車 D1;2回車7下列程序段“int i=j=10；printf(“&d,dn”，-I,j-)；”的輸出結(jié)果是【 B 】 A11,10

8、 B9,10 C11,9 D10,98下面有關(guān)for循環(huán)正確的描述是【 D 】 Afor循環(huán)只能用語句循環(huán)次數(shù)已經(jīng)確定的情況 Bfor循環(huán)是先執(zhí)行循環(huán)體語句，后判定表達(dá)式 C在for循環(huán)中，不能用break語句跳出循環(huán)體 Dfor語句的循環(huán)體中，可以包含多條語句，但要用花括號括起來9設(shè)有定義“int x5=l,2,3)；”，則數(shù)組x占用的內(nèi)存字節(jié)數(shù)是【 D 】 A3 B5 C6 D1010若有定義語句“int m, n=2, *p=&m；”，則能完成m=n功能的語句為 【 B 】 Am=*p； B*p=*&n； Cm=&n Dm=&p11數(shù)據(jù)在計算機(jī)存儲器內(nèi)表示

9、時，物理地址與邏輯地址不相同的，稱之為【 C 】 A存儲結(jié)構(gòu) B邏輯結(jié)構(gòu) C鏈?zhǔn)酱鎯Y(jié)構(gòu) D順序存儲結(jié)構(gòu)12單鏈表的一個存儲結(jié)點包含 【 D 】 A數(shù)據(jù)域或指針域 B指針域或鏈域 C指針域和鏈域 D數(shù)據(jù)域和鏈域13循環(huán)隊列的隊滿條件為【 C 】 Asq.rear+1)maxsize=(sq.front+1)maxsize B(sq.rear+1)maxsize=sq.front+l C(sq.rear+1)maxsize=sq.front Dsq.rear=sq.front14深度為6的二叉樹最多有( )個結(jié)點【 B 】 A64 B63 C32 D3115用順序查找法對具有n個結(jié)點的線性表查找

10、的時間復(fù)雜性量級為【 C 】 AO(n2) BO(nlog2n) CO(n) DO(log2n)16設(shè)有語句“intx6=5,4,3,2,1,0)，*p=x；”，則值2的表達(dá)式為【 A 】 A*(p+4) B*(p+5) C*p+4 D*p+517算法分析的兩個主要方面是【 A 】 A空間復(fù)雜度和時間復(fù)雜度 B正確性和簡明性 C可讀性和文檔性 D數(shù)據(jù)復(fù)雜性和程序復(fù)雜性18帶頭結(jié)點的單鏈表Head為空的判定條件是【 B 】 AHead=NULL； BHead->next=NULL： CHead->next=Head； D均不正確；19一個隊列的輸入列序為1,2,3,4，則該隊列的輸出

11、序列是【 B 】 A4,3,2,l B1,2,3,4 C1,4,3,2 D3,2,4,120堆(Heap)是 【 B 】 A完全二叉樹 B線性表 C滿二叉樹 D都不正確21在表長為n的順序表中，實施順序查找，在查找不成功時，與關(guān)鍵字比較的次數(shù)為【 C 】 An B1 Cn+1 Dn-122下列選項中，合法的C語言保留字是【 C 】 AAUTO BSWIT Celse Dinteger23下列選項中非法的實型常數(shù)是【 A 】 A3E1.0 B1.0E3 C.3E-2 D3E-224設(shè)有定義“float a=5.0，b=2.5；”，則表達(dá)式(int)b+a/b的值是 【 D 】 A3 B4 C3.

12、0 D4.025設(shè)int a=10，b=20，c=30；條件表達(dá)式a<b?a=15：c的值是【 B 】 A10 B15 C20 D3026一個C程序是由【 B 】 A一個主程序和若干子程序組成 B一個或多個函數(shù)組成 C若干過程組成 D若干子程序組成27下列給出的符號串中，可以作為C語言標(biāo)識符是的【 C 】 Aprintf Bdo CGOTO Dwhile28在c語言中，合法的字符常量是【 B 】 A/A/ B/x10/ C/0a/ Da29以下表達(dá)式中與表達(dá)式“m=n+”功能完全相同的是 【 A 】 Am=n，n=n+l Bn=n+l，m=n Cm=+n Dm+=n+130若變量a, i

13、已正確定義，且i已正確賦值，非法的表達(dá)式是 【 C 】 Aa= =1 B+i Ca=a+=5 Da= (int)(i)32當(dāng)調(diào)用函數(shù)時，實參是一個數(shù)組名，則向?qū)?yīng)形參傳送的是【 B 】 A數(shù)組的長度 B數(shù)組的首地址C數(shù)組中每一個元素的地址 D數(shù)組中每個元素的值33假定的數(shù)據(jù)定義語句“floatx；”，能為x輸入數(shù)據(jù)的正確語句是【 D 】 Ascanf(“f，3.5)； Bscanf(“x=f ”)； Cscanf(“4.2f”，&X)； Dscanf(“f'”，&x)；34下列程序段的輸出結(jié)果是【 D 】 int x=2; do prinff(“d,”，x一)； whi

14、le(!(-x)； A2， B1,0， C2，1， D2，0，35選用數(shù)組元素下標(biāo)時，可能造成程序運(yùn)行出錯的下標(biāo)是【 B 】 A0 B-1 C正實數(shù) D整型變量36設(shè)有語句“char a=“123”，b=1，2，3)；”，下列說法正確的是 【 D 】 Aa3是不可知的任意字符 B數(shù)組a,b的長度相同 Cb3的值為0 D數(shù)組a的長度大于數(shù)組b的長度37執(zhí)行程序段“int x=8；while(-x>6)sprintf(“*”)后的輸出結(jié)果是【 A 】 A* B* C* D*38設(shè)有定義語句：int a=l，b=2，c=3，d=4；執(zhí)行下列程序段后x的值是 【 A 】 if(a<b)if

15、(c<d)x=10； else if(a<c)if(b<d)x=20； else x=30； else x=40； else x=50； A10 B 20 C 30 D 4039C語言中【 C 】 A不能使用dowhile語句構(gòu)成循環(huán)體。Bdo-while語句構(gòu)成的循環(huán)必須用break語句才能退出。 Cdo-while語句構(gòu)成的循環(huán)，當(dāng)while語句中的表達(dá)式值為零時結(jié)束循環(huán)。 Ddowhile語句構(gòu)成的循環(huán)，當(dāng)while語句中的表達(dá)式值為非零時結(jié)束循環(huán)。40以下數(shù)組語句中，正確的是【 C 】 Aint a3； Bint b3=0,l,2,3； Cint c1010= 0；

16、Dint d3=l,2, 1,3,0), l；41設(shè)有語句“int x8=5,4,3,2,1，*p=x；”，則*(p+3)的值為【 C 】 A5 B4 C3 D242計算機(jī)內(nèi)部數(shù)據(jù)處理的基本單位是【 B 】 A數(shù)據(jù) B數(shù)據(jù)元素 C數(shù)據(jù)項 D數(shù)據(jù)庫43在一個具有n個結(jié)點的有序順序表中插入一個新結(jié)點并仍然有序的時間復(fù)雜度是【 B 】AO(1) BO(n2) CO(n) DO(nlog2n)44設(shè)C語言數(shù)組Datam+1作為循環(huán)隊列SQ的存儲空間，front為隊頭指針，real為隊尾指針，則執(zhí)行出隊操作的語句為【 D 】 Afrint=front+1；， Bfront=(front+1)m： Cre

17、ar=(rear+1)m； Dfront= (front+1)(m+1)；45樹最適合用( )來表示【 C 】 A有序數(shù)據(jù)元素 B無序數(shù)據(jù)元素 C元素之間具有分支層次關(guān)系的數(shù)據(jù) D元素之間無聯(lián)系的數(shù)據(jù)46長度為12的有序表：Apt, Aug, Dec, Feb, Jan, Jul, Jun, Mar, May, Nov, Oct, Sep，按對半查找法對該表進(jìn)行查找。在表內(nèi)各元素等概率情況下查找成功所需要的平均比較次數(shù)為 【 B 】A 35/12 B 37/12 C 39/12 D 43/12三、簡答題1軟件維護(hù)工作可分為哪幾類維護(hù)工作? 答：軟件維護(hù)工作可分如下四類維護(hù)工作：1)改正性維護(hù)；

18、2)適應(yīng)性維護(hù)；3)完善性維護(hù)；4)預(yù)防性維護(hù)。2良好的程序設(shè)計風(fēng)格除了將程序文檔化和格式化以外，還需要遵循哪些準(zhǔn)則?答：良好的程序設(shè)計風(fēng)格除了將程序文檔化和格式化以外，還需要遵循以下準(zhǔn)則：1)節(jié)儉化；2)模塊化；3)簡單化；4)結(jié)構(gòu)化3用文字簡述數(shù)據(jù)x進(jìn)棧和退棧操作的基本步驟。答：進(jìn)棧操作的基本步驟為：1)先判斷棧是否已滿，若滿，則進(jìn)行上溢處理，否則進(jìn)行2)。2)棧項指針上移1個節(jié)點。3)將x加入到top所指位置。 退棧操作的基本步驟為：1)檢查棧是否為空，若?？?，則進(jìn)行下溢處理，否則進(jìn)行2)。2)保留被刪除元素到變量x中(若不需要保存，則舍去這一步)。3)棧頂指針下移1個節(jié)點。4軟件測試時

19、，程序中尚未發(fā)現(xiàn)的錯誤的數(shù)量往往與在該段程序中己發(fā)現(xiàn)的錯誤的數(shù)量成正比。所以軟件測試時，除盡早地、不斷地進(jìn)行軟件測試外，還應(yīng)遵循的其它基本原則是什么?答：軟件測試時，還應(yīng)遵循的其它基本原則是：1)設(shè)計測試用例時，要給出測試的預(yù)期結(jié)果。2)開發(fā)小組和測試小組分開。3)要設(shè)計非法輸入的測試用例。4)在對程序修改之后要進(jìn)行回歸測試。5簡述哈夫曼樹的性質(zhì)。答：由哈夫曼樹的生成過程可得如下性質(zhì)：1)給定權(quán)值的哈夫曼樹不唯一，但是WPL，為定值。2)權(quán)值越大的節(jié)點離根節(jié)點就越近。3)哈夫曼樹中無度為l的節(jié)點。4)哈夫曼樹節(jié)點總個數(shù)刀=2×葉子節(jié)點個數(shù)一1=2×權(quán)值個數(shù)1=2n,一1。6

20、用文字簡述將內(nèi)容為x節(jié)點加入順序隊列和出隊操作的基本步驟。答：將內(nèi)容為x節(jié)點加入順序隊列的基本步驟為：1)先判斷隊列是否已滿，若滿則退出，否則進(jìn)行2)。2)隊尾指針下移1個節(jié)點位置。3)在隊尾指針位置加入x。出隊操作的基本步驟為：1)先判斷隊列是否己空，若空則退出，否則進(jìn)行2)。2)保留隊頭元素到x變量中。3)隊頭指針下移1個節(jié)點位置。四、程序分析題1下列程序運(yùn)行后的輸出結(jié)果是 m=3 Main（） int k，m=0； for(k=0；k<2；k+) m+； if(m/2)continue； m+： printf(/m=%dn/,m);2下列程序運(yùn)行后的輸出結(jié)果是 1,6 #inlcu

21、de<stdio.h> Main() int a=l,2,3,4,5,6, *p； p=a； *(p+3)+=2； printf(/d, %dn/, *p, *(p+3);3下列程序運(yùn)行后的輸出結(jié)果是s=55 #inlcude<stdio.h> Main() int S, i=l，sum()； for(; i<=10;)i+，s=sum(i)； printf(/S=%dn/，s)； sum(int k)int x=0；return(x+=k); 4下列程序運(yùn)行后的輸出結(jié)果是abcd main() char sl()=/ abcdABCD/，s210； int k=

22、0，j=0； while (s lk!=/A/)s2j+=s 1k+； s2j=0； printf(/sn”，s2);5下列程序運(yùn)行后的輸出結(jié)果是DCBAEF void fun(char*pl，int n) chart，*p2； p2=pl+n-1； while(p1<p2) 1=*pl；*p1+=*p2；*p2-=t Main() char*p=/ABCDEF/； fun(p,4)； printfsn/,p); 6下列程序運(yùn)行后的輸出結(jié)果是 13 Main() intx=11； while(x>10&&x<50) x+ if(x/3)x+; break; e

23、lse continue; printf(/dn/，x); 7下列程序運(yùn)行后的輸出結(jié)果是 6 int b=l； int f(int*a) b+=*a; return(b); main() int a=2，b=3： a+=f(&b)； printf(/%dn/,a); 8下列程序運(yùn)行后的輸出結(jié)果是23 Main() int x4=1,2,3,4,5,6,7,8,3,9,10,2,4,2,9,6，s=0，k=0； for(；k<4; k+) s+=xkk； printf(/dn/, s) ;9下列程序段的功能是： 計算單鏈表的表長 int L_lklist(1klist head)

24、p=head； j=0； while(p->next!=NULL) p=p->next； j+； return(j)；10下列程序運(yùn)行后的輸出結(jié)果是 1,6,3,2,3 #include<stdio.h> main() int j=1 j=3； printf(/%d,/，i+)； int i=0； I+=j*2； printf(/d,d,/,i,j); printf(/d,d/,i,j);11下列程序運(yùn)行后的輸出結(jié)果是 10 int f(int n) if(n=1)return(1)； else return(f(n-1)+1)； main() int i,j=0； f

25、or(i=1；i<5；i+)j+=f(i)； printf(/dn/,j); 12閱讀下列算法，寫出其完成的功能是 借助棧將一個帶頭結(jié)點的單鏈表倒置 void list(LinkedListTP*head) LStackTPIs,p； DataType x； InitStack(&ls)； p=head->next； while(p!=NULL) Push(&ls,p->data);p=p->next; p=head->next； while(!EmptyStaek(&JS) Pop(&ls,&x)；p->data=x

26、；p=p->next; 五、程序填空題1下面程序是從輸入3個數(shù)中找出最大數(shù)，并輸出最大數(shù)。 int max(intx, int y, int z) int t； t=x>y? x:y )； retum(t>z? t:z ) main() int a,b,c； scanf(/d,d,d/，&a,&b,&c)； prinf(/max=dn",max( a,b,c )； 2以下為冒泡排序的算法，請分析算法，并在 處填充適當(dāng)?shù)恼Z句。 void bubblesort(int n, list r) for(i=l；i<= n-1 ；i+) flag

27、=1 ； for(j=l；j<=n-1 ；j+) if(rj+1.key<rj.key)flag=0;p=rj;rj=rj+1;rj+1=p；) if(flag)return； 3下列程序的功能是將輸入的10個整型數(shù)存入一維數(shù)組中，并求其中所有素數(shù)之和并輸出。 main() int x10，sum=0,flag,k,j； for(k=0；k<10；k+)scanf(/d /，&xk)； for(k=0；k<l0；k+) if(xk=1) continue ； flag=l； for(j=2；j<= xk/2 ；j+) if(xkj= =0) flag=0

28、；break； if(flag=1) sum+=xk； printf(/d n/，s)；4下面程序的功能是輸入10個字符和1個字符X，從10個字符中查找x，找到則輸出其序號，找不到則輸出0。 main() char str10,x,*p； int flag=0； for(p=str；p<str+10；p+)scanf(/c/，p)； scanf(/c/，&x)； for( p=str ；p<str+10；p+) if(*p=x) flag=1 ；break； if(flag) prinf(/0n/， p-str+1 )； else prinf(/0n/)5以下運(yùn)算實現(xiàn)在循環(huán)隊上的出隊列，請在 處用適當(dāng)?shù)恼Z句予以填充。 int OutCyeQueue(Cycqueue Tp*sq，DataType*x) if(sq->fron=sq->rear )error(/隊空/)；return(o); elsesq->front=(sq->front+1)maxsize ； *x=sq->da