計算機軟件技術基礎課后答案

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