計算機(jī)軟件技術(shù)基礎(chǔ)課后答案

計算機(jī)軟件技術(shù)基礎(chǔ)課后答案計算機(jī)軟件技術(shù)基礎(chǔ)課后答案【篇一：《計算機(jī)軟件技術(shù)基礎(chǔ)》復(fù)習(xí)題(含答案)】txt>1.線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)與順序存儲結(jié)構(gòu)相比優(yōu)點是a.所有的操作算法實現(xiàn)簡單c.便于插入和刪除b.便于隨機(jī)存取d.便于利用零散的存儲器空間2.線性表是具有n個的有限序列。a.表元素d.數(shù)據(jù)項b.字符c.數(shù)據(jù)元素e.信息項3.若長度為n的線性表采用順序存儲結(jié)構(gòu)，在其第i個位置插入一個新元素的算法的時間復(fù)雜度為c。（1≤i≤n+1）a.o(0)b.o(1)2c.o(n)d.o(n)4.設(shè)a是一個線性表(a1,a2,?,an)，采用順序存儲結(jié)構(gòu)，則在等概率的前提下，平均每插入一個元素需要移動的元素個數(shù)為b，平均每刪除一個元素需要移動的元素個數(shù)為a；若元素插在ai與ai+1之間(0≤i≤n-1)的概率為元素所要移動的元素個數(shù)為c；2(n?i)，則平均每插入一個n(n?1)n?122n?1c.3a.n23n?1d.4b.5.下列函數(shù)中，按它們在n??時的無窮大階數(shù)，最大的是d。a.lognb.nlognn/2c.2d.n!6.a.s-next=p+1;p-next=s;b.(*p).next=s;(*s).next=(*p).next;c.s-next=p-next;p-next=s-next;d.s-next=p-next;p-next=s;7.將兩個各有n個元素的有序表歸并為一個有序表時，其最少的比較次數(shù)是a。a.nc.n-1b.2n-1d.2n13.用單鏈表表示的鏈?zhǔn)疥犃械年狀^在鏈表的a位置。a.鏈頭b.鏈尾c.鏈中14.若用單鏈表表示隊列，則應(yīng)該選用。a.帶尾指針的非循環(huán)鏈表b.帶尾指針的循環(huán)鏈表c.帶頭指針的非循環(huán)鏈表d.帶頭指針的循環(huán)鏈表15.在解決計算機(jī)主機(jī)與打印機(jī)之間速度不匹配問題時，通常設(shè)置一個打印數(shù)據(jù)緩沖區(qū)，主機(jī)將要輸出的數(shù)據(jù)依次寫入該緩沖區(qū)，而打印機(jī)則從該緩沖區(qū)中取出數(shù)據(jù)打印，先放入打印緩沖區(qū)的數(shù)據(jù)先被打印。該緩沖區(qū)應(yīng)該是一個b結(jié)構(gòu)。a.堆棧b.隊列c.數(shù)組d.線性表待排序的序列中的相鄰元素兩兩比較，凡是逆序則進(jìn)行交換，這是(3)排序。如果整個排序過程都在內(nèi)存中進(jìn)行，稱為(4)排序。排序算法的復(fù)雜性與排序算法的(5)有關(guān)。供選答案：(1):(2):(3):(4):(5):a.選擇b.插入c.比較d.歸并a.選擇b.插入c.比較d.歸并a.冒泡b.交換c.比較d.散列a.外部b.內(nèi)部c.外存d.內(nèi)存a.運(yùn)算量大小與占用存儲多少b.運(yùn)算量大小與處理的數(shù)據(jù)量大小c.并行處理能力和占用存儲多少d.占用存儲多少和處理的數(shù)據(jù)量大小答案：baaba47.操作系統(tǒng)是對計算機(jī)資源進(jìn)行的(1)系統(tǒng)軟件，是(2)的接口。在處理機(jī)管理中，進(jìn)程是一個重要的概念，它由程序塊、(3)和數(shù)據(jù)塊三部分組成，它有3種基本狀態(tài)，不可能發(fā)生的狀態(tài)轉(zhuǎn)換是(4)。虛擬存儲器的作用是允許程序直接訪問比內(nèi)存更大的地址空間，它通常使用(5)作為它的一個主要組成部分。供選答案：(1):a.輸入和輸出b.鍵盤操作c.管理和控制d.匯編和執(zhí)行(2):a.軟件和硬件b.主機(jī)和外設(shè)c.高級語言和機(jī)器語言d.用戶和計算機(jī)(3):a.進(jìn)程控制塊b.作業(yè)控制塊c.文件控制塊d.設(shè)備控制塊(4):a.運(yùn)行態(tài)轉(zhuǎn)換為就緒態(tài)b.就緒態(tài)轉(zhuǎn)換為運(yùn)行態(tài)c.運(yùn)行態(tài)轉(zhuǎn)換為等待態(tài)d.等待態(tài)轉(zhuǎn)換為運(yùn)行態(tài)(5):a.軟盤b.硬盤c.cdromd.寄存器答案：cdadb48.a是信息的載體，它能夠被計算機(jī)識別、存儲和加工處理。a.數(shù)據(jù)b.數(shù)據(jù)元素c.結(jié)點d.數(shù)據(jù)項49.下列程序段的時間復(fù)雜度為c。for(i=1;in;i++){y=y+1;for(j=0;j=(2*n);j++)x++;}供選答案：2a.o(n-1)b.o(2n)c.o(n)d.o(2n+1)50.下面程序段的時間復(fù)雜度為d。i=1;while(i=n)i=i*2;供選答案：a.o(1)b.o(n)c.o(n2)d.o(log2n)51.下面程序段的時間復(fù)雜度為b。a=0;b=1;for(i=2;i=n;i++){s=a+b;b=a;a=s;}供選答案：2a.o(1)b.o(n)c.o(log2n)d.o(n)52.數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計算的程序設(shè)計問題中，計算機(jī)的a以及它們之間的關(guān)系和運(yùn)算等的學(xué)科。a.操作對象b.計算方法c.邏輯存儲d.數(shù)據(jù)映象53.在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分成c。a.動態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)b.緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)c.線性結(jié)構(gòu)和非線性結(jié)構(gòu)d.內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)54.算法分析的目的是c。a.找出數(shù)據(jù)結(jié)構(gòu)的合理性b.研究算法中輸入和輸出的關(guān)系c.分析算法的效率以求改進(jìn)d.分析算法的易懂性和文檔性55.算法分析的兩個主要方面是d。a.間復(fù)雜性和時間復(fù)雜性b.正確性和簡明性c.可讀性和文檔性d.數(shù)據(jù)復(fù)雜性和程序復(fù)雜性56.一個線性順序表第一個元素的存儲地址是100，每個元素的長度為2，則第5個元素的地址為b。a.110b.108c.100d.12057.若已知一個棧的入棧序列是1,2,3,?,n，其輸出序列為p1,p2,p3,?,pn，若p1=n，則pi為c。a.ib.n-ic.n-i+1d.不確定58.對于一個棧，給出輸入項a,b,c。如果輸入項序列由a,b,c所組成，則不可能產(chǎn)生的輸出序列是a。a.cabb.cbac.abcd.acb59.設(shè)有如下的單鏈表的按序號查找的算法，其時間復(fù)雜度為b。linknode*getnode(linklisthead,inti){intj;listnode*p;p=head;j=0;while(p-nextji){p=p-next;j++;}if(i==j)return(p);else【篇二：《計算機(jī)軟件技術(shù)基礎(chǔ)(第三版)》的課后答案】是信息？信息與數(shù)據(jù)的區(qū)別和聯(lián)系在何處？信息定義之一：信息是現(xiàn)實世界中存在的客觀實體、現(xiàn)象、關(guān)系進(jìn)行描述的數(shù)據(jù)。信息定義之二：信息是經(jīng)過加工后并對實體的行為產(chǎn)生影響的數(shù)據(jù)。與數(shù)據(jù)的區(qū)別和聯(lián)系：數(shù)據(jù)定義：數(shù)據(jù)是現(xiàn)實世界客觀存在的實體或事物的屬性值，即指人們聽到的事實和看到的景象。我們把這些數(shù)據(jù)收集起來，經(jīng)過處理后，即得到人們需要的信息。信息和數(shù)據(jù)的關(guān)系可以歸結(jié)為：1.信息是有一定含義的數(shù)據(jù)。2.信息是經(jīng)過加工（處理）后的數(shù)據(jù)。3.信息是對決策有價值的數(shù)據(jù)。1.2信息有哪些基本屬性？信息的基本屬性有：1.事實性。2.等級性。3.可壓縮性。4.可擴(kuò)散性。5.可傳輸性。6.共享性。7.增值性和再生性。8.轉(zhuǎn)換性。1.3計算機(jī)的主要特點是什么？計算機(jī)最主要的特點是：1.高速自動的操作功能。2.具有記憶的能力。3.可以進(jìn)行各種邏輯判斷。4.精確高速的計算能力。1.5完整的計算機(jī)系統(tǒng)應(yīng)該包括哪幾部分？目前最完整的計算機(jī)系統(tǒng)學(xué)說認(rèn)為由五部分組成：1.人員2.數(shù)據(jù)3.設(shè)備4.程序5.規(guī)程1.6什么是計算機(jī)硬件？什么是計算機(jī)軟件？硬件：泛指實際存在的物理設(shè)備，包括計算機(jī)本身及其外圍設(shè)備。微型計算機(jī)的硬件系統(tǒng)：主機(jī)、外存儲器、輸入設(shè)備、輸出設(shè)備、微機(jī)的系統(tǒng)總線。軟件：是指計算機(jī)程序、方法、規(guī)則的文檔以及在計算機(jī)上運(yùn)行它時所必須的數(shù)據(jù)。計算機(jī)軟件一般分為系統(tǒng)軟件和應(yīng)用軟件。1.8軟件技術(shù)發(fā)展的幾個階段各有什么特點？它與硬件的關(guān)系如何？第一階段：高級語言階段特點：這一時期，編譯技術(shù)代表了整個軟件技術(shù)，軟件工作者追求的主要目的是設(shè)計和實現(xiàn)在控制結(jié)構(gòu)和數(shù)據(jù)結(jié)構(gòu)方面表現(xiàn)能力強(qiáng)的高級語言。但在這一時期內(nèi)，編譯系統(tǒng)主要是靠手工編制，自動化程度很低。硬件關(guān)系：此時期計算機(jī)的硬件要求僅能用機(jī)器指令來編制可運(yùn)行的程序。第二階段：結(jié)構(gòu)程序設(shè)計階段特點：在程序的正確性方面，提出了結(jié)構(gòu)化程序設(shè)計思想使程序的可靠性提高了。程序設(shè)計方法論方面，提出由頂向下法和自底向上法。使程序模塊化，使問題的復(fù)雜性和人的思維統(tǒng)一起來了。出現(xiàn)了軟件生產(chǎn)管理。硬件關(guān)系：磁盤問世，操作系統(tǒng)發(fā)展，非數(shù)值計算應(yīng)用發(fā)展，通信設(shè)備完善，網(wǎng)絡(luò)發(fā)展，集成電路發(fā)展等使軟件復(fù)雜性增加產(chǎn)生軟件危機(jī)，在此背景下發(fā)展了軟件技術(shù)。第三階段：自動程序設(shè)計階段特點：向集成化、一體化發(fā)展。出現(xiàn)了軟件開發(fā)環(huán)境。程序設(shè)計基本方法進(jìn)一步改進(jìn)。硬件關(guān)系：集成電路迅速發(fā)展以及高分辨率終端的出現(xiàn)，為個人計算機(jī)發(fā)展提供了條件，再加上人工智能、專家系統(tǒng)研究的發(fā)展，使程序設(shè)計進(jìn)入成熟期。第二章2.1什么是數(shù)據(jù)結(jié)構(gòu)？它對算法有什么影響？數(shù)據(jù)結(jié)構(gòu)是指同一數(shù)據(jù)對象中各數(shù)據(jù)元素間存在的關(guān)系。對算法是影響：算法的實現(xiàn)必須借助程序設(shè)計語言中提供的數(shù)據(jù)類型及其運(yùn)算。一個算法的效率往往與數(shù)據(jù)的表達(dá)形式有關(guān)，因此數(shù)據(jù)結(jié)構(gòu)的選擇對數(shù)據(jù)處理的效率起著至關(guān)重要的作用。它是算法和程序設(shè)計的基本部分，它對程序的質(zhì)量影響很大。2.2何謂算法？它與程序有何區(qū)別？廣義地說，為解決一個問題而采取的方法和步驟，就稱為“算法”。計算機(jī)算法是通過計算機(jī)能執(zhí)行的算法語言來表達(dá)的。和程序的區(qū)別：一個程序包括兩個方面的內(nèi)容：（1）、對數(shù)據(jù)的描述，即數(shù)據(jù)結(jié)構(gòu)。（2）、對操作的描述，即算法。所以算法是程序的一個要素。2.3何謂頻度，時間復(fù)雜度，空間復(fù)雜度？說明其含義。頻度：在某個算法中某個語句被重復(fù)執(zhí)行的次數(shù)就是此語句的頻度。時間復(fù)雜度：是用來估算一個算法的執(zhí)行時間的量，以算法中頻度最大的語句來度量?？臻g復(fù)雜度：指在算法中所需的輔助空間的單元，而不包括問題的原始數(shù)據(jù)占用的空間。2.6數(shù)據(jù)的存儲結(jié)構(gòu)主要有哪兩種?它們之間的本質(zhì)區(qū)別是什么？數(shù)據(jù)的存儲結(jié)構(gòu)：向量和鏈表。本質(zhì)區(qū)別：向量是連續(xù)存放的，其存儲空間是靜態(tài)分配的，以存放順序來表達(dá)元素的前后件的關(guān)系。鏈?zhǔn)酱鎯Y(jié)果不需要一組連續(xù)的存儲單元，其數(shù)據(jù)元素可以分散存放在存儲空間中，其元素關(guān)系由指針來指向。2.16試比較順序表和鏈表的優(yōu)缺點。1.線性表的長度是否固定方面：由于向量的存儲空間是靜態(tài)分配的，鏈表的存儲空間是動態(tài)分配的，因此若表長不固定時采用線性鏈表較好。2.線性表的主要操作是什么：由于向量是連續(xù)存放的，所以適用于查找操作，不適用插入、刪除操作。由于線性鏈表只能順序存取，所以適用于插入、刪除操作，不適用于查找操作。3.采用的算法語言：線性鏈表要求所使用的語言工具提供指針類型變量。2.17試比較單向鏈表與雙向鏈表的優(yōu)缺點。1.單向鏈表只能單方向地尋找表中的結(jié)點，雙向鏈表具有對稱性，從表中某一給定的結(jié)點可隨意向前或向后查找。2.在作插入、刪除運(yùn)算時，雙向鏈表需同時修改兩個方向上的指針，單向鏈表則簡便些。2.23試畫出表達(dá)式a*(b-d)/d+c**(e*f)執(zhí)行過程中ns,os棧的變化情況。b-d=t1d/t1=t2t2*a=t3e*f=t4t4**c=t52.26用三元組和帶行輔助向量形式表示下列稀疏矩陣：800?1300026?1500220?15?0????0113000??1500600050??（1）：???0?30403000???000?600??（2）：200040??000000??000????000000??9100000??00?12?020000000????0028000?????000400000??700000000????12002060030??（1）：三元組帶行輔助向量2.27試說明樹與二叉樹有何不同？為何要將一般樹轉(zhuǎn)換為二叉樹？樹與二叉樹區(qū)別：樹是由n個（n=0）結(jié)點組成的有限集合t，其中有且僅有一個結(jié)點稱為根結(jié)點，在此類元素結(jié)點之間存在明顯的分支和層次關(guān)系。二叉樹是一種特殊的樹結(jié)構(gòu)，每一個結(jié)點最多只有兩個孩子，即最多只有兩個分支。為何要轉(zhuǎn)換：一般樹，樹中結(jié)點次序沒有要求，分支龐雜。而二叉樹，元素之間存在嚴(yán)謹(jǐn)?shù)那昂蟠P(guān)系，在對數(shù)據(jù)元素進(jìn)行刪除、查找、插入等運(yùn)算時更加有效率。2.28將下列（題圖2.3）的一般樹化為二叉樹。題圖2.3轉(zhuǎn)換后：2.30設(shè)一棵二叉樹其中序和后序遍歷為中序：bdceafhg后序：decbhgfa畫出這棵二叉樹的邏輯結(jié)構(gòu)，并寫出先序遍歷結(jié)果。先序遍歷：abcdefgh其邏輯結(jié)構(gòu)如下：【篇三：計算機(jī)軟件技術(shù)基礎(chǔ)習(xí)題一解答】正整數(shù),分析下列各程序段中加下劃線的語句的執(zhí)行次數(shù)。(1)for(inti=1;i=n;i++)for(intj=1;j=n;j++){c[i][j]=0.0;for(intk=1;k=n;k++)c[i][j]=c[i][j]+a[i][k]*b[k][j];}(2)x=0;y=0;for(inti=1;i=n;i++)for(intj=1;j=i;j++)for(intk=1;k=j;k++)x=x+y;(3)inti=1,j=1;while(i=nj=n){i=i+1;j=j+i;}(4)*inti=1;do{for(intj=1;j=n;j++)i=i+j;}while(i100+n);【解答】nnn3(1)???1?ni?1j?1k?1?(2)nijnin???1???i?1j?1k?1i?1j?1j??i?1?i(i?1)?1???2??2?2n?ii?12?1ni??2i?11n(n?1)(2n?1)261n(n?1)2?n(n?1)(n?2)6(3)i=1時，i=2，j=j+i=1+2=2+1，i=2時，i=3，j=j+i=(2+1)+3=3+1+2，i=3時，i=4，j=j+i=(3+1+2)+4=4+1+2+3，i=4時，i=5，j=j+i=(4+1+2+3)+5=5+1+2+3+4，??i=k時，i=k+1，j=j+i=(k+1)+(1+2+3+4+?+k)，?j??k?1????k?1??k?i?ni?1k?k?1?2?k?3k?322?n解出滿足上述不等式的k值，即為語句i=i+1的程序步數(shù)。(4)for語句每執(zhí)行一次，語句i=i+j將執(zhí)行n次，而i的值會增加因此，當(dāng)for語句執(zhí)行k次后，i的值將變?yōu)??kn(n?1)2n(n?1)2故最終for語句的執(zhí)行次數(shù)k為滿足1?kn(n?1)2?100?n的最小整數(shù)k，語句i=i+j的程序步數(shù)為n*k。4.試編寫一個函數(shù)計算n!*2的值，結(jié)果存放于數(shù)組a[arraysize]的第n個數(shù)組元素中，0?n?arraysize。若設(shè)計算機(jī)中允許的整數(shù)的最大值為maxint，則當(dāng)narraysize或者對于某一個k(0?k?n)，使得k!*2maxint時，應(yīng)按出錯處理?？捎腥缦氯N不同的出錯處理方式：(1)用printf顯示錯誤信息及exit(1)語句來終止執(zhí)行并報告錯誤；kn(3)在函數(shù)的參數(shù)表設(shè)置一個引用型的整型變量來區(qū)別是正常返回還是某種錯誤返回。試討論這三種方法各自的優(yōu)缺點，并以你認(rèn)為是最好的方式實現(xiàn)它。【解答】#includestdio.hconstintarraysize=100;constintmaxint=0x7fffffff;intcalc(intt[],intn){inti,value=1;t[0]=1;if(n!=0){}voidmain(){inta[arraysize];inti;for(i=0;iarraysize;i++)if(!calc(a,i)){printf(failedat%d.\n,i);break;intedge=maxint/n/2;for(i=1;in;i++){value*=i*2;t[i]=value;if(valueedge)return0;}value*=n*2;}t[n]=value;printf(a[%d]=%d\n”,n,t[n]);return1;}}/*---------順序表結(jié)構(gòu)的定義.為簡化起見，表元素我們使用整型數(shù)據(jù)----------------------數(shù)據(jù)元素從data[0]處開始存儲---------------------------------*/typedefstruct/*注意typedef的使用*/{intdata[maxsize];/*數(shù)據(jù)域*/intlength;/*表長*/}listtype;5.設(shè)有一個線性表(a0,a1,?,an-2,an-1)存放在一個一維數(shù)組a[arraysize]中的前n個數(shù)組元素位置。請編寫一個函數(shù)將這個線性表原地逆置，即將數(shù)組的前n個原址內(nèi)容置換為(an-1,an-2,?,a1,a0)。最后分析此算法的時間復(fù)雜度及空間復(fù)雜度?！窘獯稹縱oidinverse(listtype*a){inttmp;intn=a-length;for(inti=0;i=(n-1)/2;i++){tmp=a-data[i];a-data[i]=a-data[n-i-1];a-data[n-i-1]=tmp;}}時間復(fù)雜度：需進(jìn)行n/2次循環(huán)，因此時間復(fù)雜度為o(n)；空間復(fù)雜度：使用一個整形輔助存儲單元tmp，因此空間復(fù)雜度為o(1)。6.順序表的插入和刪除要求仍然保持各個元素原來的次序。設(shè)在等概率情形下,對有127個元素的順序表進(jìn)行插入,平均需要移動多少個元素?刪除一個元素,又平均需要移動多少個元素?【解答】若設(shè)順序表中已有n個元素。又設(shè)插入或刪除表中各個元素的概率相等，則在插入時因有n+1個插入位置(可以在表中最后一個表項后面追加)，每個元素位置插入的概率為1/(n+1)，但在刪除時只能在已有n個表項范圍內(nèi)刪除，所以每個元素位置刪除的概率為1/n。插入時平均移動元素個數(shù)amn(averagymovingnumber)為amn???n?i??n?1i?01n1n?1(n?(n?1)???1?0)?1n?1n(n?1)2?n2?63.51n?1刪除時平均移動元素個數(shù)amn為amn??ni?0(n?i?1)?1n((n?1)?(n?2)???1?0)?1(n?1)nn2?n?12?637.利用順序表的操作，實現(xiàn)以下的函數(shù)。并分析你所編制的函數(shù)的時間復(fù)雜度，并分析(2)與(3)的時間復(fù)雜度出現(xiàn)差異的原因。(1)從順序表中刪除具有給定值x的所有元素。(2)從順序表中刪除其值在給定值s與t之間（要求s小于t）的所有元素。(3)從有序順序表中刪除其值在給定值s與t之間（要求s小于t）的所有元素。(4)將兩個有序順序表la,lb合并成一個新的有序順序表lc。(5)從順序表中刪除所有其值重復(fù)的元素，使表中所有元素的值均不相同?！窘獯稹?1)從順序表中刪除具有給定值x的所有元素。voiddelvalue(listtype*l,intx){inti=0,j;while(il-length)if(l-data[i]==x){l-length--;}}elsei++;(2)實現(xiàn)刪除其值在給定值s與t之間（要求s小于t）的所有元素的函數(shù)如下：/*循環(huán),尋找具有值x的元素并刪除它*//*刪除具有值x的元素,后續(xù)元素前移*//*表長減1*/for(j=i;jl-length-1;j++)l-data[j]=l-data[j+1];voiddelvalue_s_to_t(listtype*l,ints,intt){inti,j;if(l-length==0||s=t){printf(“l(fā)istisemptyorparametersareillegal!\n”);exit(1);}i=0;while(il-length)/*循環(huán),尋找具有值x的元素并刪除它*/if(l-data[i]=sl-data[i]=t){/*刪除滿足條件的元素,后續(xù)元素前移*/for(j=i;jl-length-1;j++)l-data[j]=l-data[j+1];l-length--;}}elsei++;/*表長減1*/(3)實現(xiàn)從有序順序表中刪除其值在給定值s與t之間的所有元素的函數(shù)如下：voiddelvalue_s_to_t_1(listtype*l,intsintt){inti,j,k;if(l-length==0||s=t){printf(“l(fā)istisemptyorparametersareillegal!\n”);exit(1);}for(i=0;il-length;i++)if(l-data[i]=s)break;if(il-length){for(j=1;i+jl-length;j++)/*循環(huán),尋找值t的第一個元素*/if(l-data[i+j]t)break;/*退出循環(huán)時,i+j指向該元素*/}}for(k=i+j;kl-length;k++)/*刪除滿足條件的元素,后續(xù)元素前移*/l-data[k-j]=l-data[k];l-length-=j;/*表長減j*//*循環(huán),尋找值≥s的第一個