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

篇一：《計(jì)算機(jī)軟件技術(shù)基礎(chǔ)》復(fù)習(xí)題(含答案)】txt>1■線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)與順序存儲(chǔ)結(jié)構(gòu)相比優(yōu)點(diǎn)是所有的操作算法實(shí)現(xiàn)簡(jiǎn)單c.便于插入和刪除b.便于隨機(jī)存取d.便于利用零散的存儲(chǔ)器空間2■線性表是具有n個(gè)的有限序列。a.表元素d.數(shù)據(jù)項(xiàng)b.字符c.數(shù)據(jù)元素e.信息項(xiàng)3■若長(zhǎng)度為n的線性表采用順序存儲(chǔ)結(jié)構(gòu)，在其第i個(gè)位置插入一個(gè)新元素的算法的時(shí)間復(fù)雜度為c°(1SiSn+1)o(0)b.o(1)2c.o(n)d.o(n)4■設(shè)a是一個(gè)線性表(a1,a2,?,an),采用順序存儲(chǔ)結(jié)構(gòu)，貝恠等概率的前提下，平均每插入一個(gè)元素需要移動(dòng)的元素個(gè)數(shù)為b,平均每刪除一個(gè)元素需要移動(dòng)的元素個(gè)數(shù)為a；若元素插在ai與ai+1之間(0SiSn-1)的概率為元素所要移動(dòng)的元素個(gè)數(shù)為c；2(n?i),則平均每插入一個(gè)n(n?1)n?122n?1c.3a.n23n?1d.4b.5■下列函數(shù)中，按它們?cè)趎??時(shí)的無窮大階數(shù)，最大的是dolognb.nlognn/2c.2d.n!6.s-next=p+1;p-next=s;(*p).next=s;(*s).next=(*p).next;s-next=p-next;p-next=s-next;s-next=p-next;p-next=s;7■將兩個(gè)各有n個(gè)元素的有序表歸并為一個(gè)有序表時(shí)，其最少的比較次數(shù)是aonc.n-12n-1d.2n13.用單鏈表表示的鏈?zhǔn)疥?duì)列的隊(duì)頭在鏈表的a位置a.鏈頭b.鏈尾c.鏈中14■若用單鏈表表示隊(duì)列，則應(yīng)該選用。帶尾指針的非循環(huán)鏈表b.帶尾指針的循環(huán)鏈表c.帶頭指針的非循環(huán)鏈表d.帶頭指針的循環(huán)鏈表15.在解決計(jì)算機(jī)主機(jī)與打印機(jī)之間速度不匹配問題時(shí)，通常設(shè)置一個(gè)打印數(shù)據(jù)緩沖區(qū)，主機(jī)將要輸出的數(shù)據(jù)依次寫入該緩沖區(qū)，而打印機(jī)則從該緩沖區(qū)中取出數(shù)據(jù)打印，先放入打印緩沖區(qū)的數(shù)據(jù)先被打印。該緩沖區(qū)應(yīng)該是一個(gè)b結(jié)構(gòu)。a.堆棧b.隊(duì)列c.數(shù)組d.線性表16.若用一個(gè)大小為6的數(shù)組來實(shí)現(xiàn)循環(huán)隊(duì)列，且當(dāng)前rear和front的值分別為0和3。當(dāng)從隊(duì)列中刪除一個(gè)元素，再加入兩個(gè)元素后，rear和front的值分別為b。a.1和5b.2和44和2d.5和117■設(shè)棧的輸入序列為1,2,?,10，輸出序列為a,a,?,a,若a=10,則a為c。121057（未要求一次性全部輸入或輸出）a.4b.8c?不確定d?718■設(shè)棧的輸入序列是1,2,3,4，貝Qd不可能是其出棧序列。a．1243b.2134c.1432d.431219■以下abd是c語言中”abcd321abcd”的子串。a.abcdb.321abc.“abcabc”d.“21ab”20■若串s=”software”，其子串的數(shù)目是。a.8b.37c.36d.922■設(shè)高為h的二叉樹只有度為0和2的結(jié)點(diǎn)，則此類二叉樹的結(jié)點(diǎn)數(shù)至少為b，至多為f。高為h的完全二叉樹的結(jié)點(diǎn)數(shù)至少為e至多為f。a．2hb.2h-1c.2h+1d.h+1h-1hh+1he.2f.2-1g.2-1h.2+123■—棵有124個(gè)葉結(jié)點(diǎn)的完全二叉樹，最多有b個(gè)結(jié)點(diǎn)。a.247b.248c.249d.251若從二叉樹的任一結(jié)點(diǎn)出發(fā)到根的路徑上所經(jīng)過的結(jié)點(diǎn)序列按其關(guān)鍵字有序，則該二叉樹是c。（記）a.滿二叉樹c.堆b.哈夫曼樹d.二叉查找樹前序遍歷和中序遍歷結(jié)果相同的二叉樹為；前序遍歷和后序遍歷結(jié)果相同的二叉樹為b。a.一般二叉樹b.只有根結(jié)點(diǎn)的二叉樹c.根結(jié)點(diǎn)無左孩子的二叉樹d.根結(jié)點(diǎn)無右孩子的二叉樹e.所有結(jié)點(diǎn)只有左孩子的二叉樹f.所有結(jié)點(diǎn)只有右孩子的二叉樹29■假定有k個(gè)關(guān)鍵字互為同義詞，若用線性探測(cè)法把這k個(gè)關(guān)鍵字存入散列表中，至少要進(jìn)行d次探測(cè)。a.k-1次b.k次c.k+1次d.k(k+1)/2次30■在n個(gè)記錄的有序順序表中進(jìn)行折半查找，最大的比較次數(shù)是?log2n??1。,=J在下述排序算法中，所需輔助存儲(chǔ)空間最多的是b，所需輔助存儲(chǔ)空間最小的是c，平均速度最快的是a。,=Ja?快速排序b.歸并排序c.堆排序在文件局部有序或文件長(zhǎng)度較小的情況下，最佳內(nèi)部排序的方法a.直接插入排序b.冒泡排序c.簡(jiǎn)單選擇排序快速排序在最壞情況下時(shí)間復(fù)雜度是o(n),比a的性能差。2a.堆排序b.冒泡排序c.簡(jiǎn)單選擇排序若需在o(nlogn)的時(shí)間內(nèi)完成對(duì)數(shù)組的排序，且要求排序是穩(wěn)定的，則可選擇的排序方法是c。a.快速排序b.堆排序c.歸并排序d.希爾排序如果只想得到1000個(gè)元素組成的序列中第5個(gè)最小元素之前的部分排序的序列，用b方法最快。a.冒泡排序b.快速排序c.希爾排序d.堆排序e.簡(jiǎn)單選擇排序以下結(jié)點(diǎn)序列是堆的為a。100,90,80,60,85,75,20,25,10,70,65,50100,70,50,20,90,75,60,25,10,85,65,80若要盡可能快地完成對(duì)實(shí)數(shù)數(shù)組的排序，且要求排序是穩(wěn)定的，則應(yīng)選c。a.快速排序b.堆排序歸并排序d.希爾排序從未排序序列中依次取出一個(gè)元素與已排序序列中的元素依次進(jìn)行比較，然后將其放在已排序序列的合適位置，該排序方法稱為a排序法。a.插入排序b.交換排序c.選擇排序d.歸并排序直接插入排序在最好情況下的時(shí)間復(fù)雜度為b。a.o(logn)b.o(n)2c.o(nlogn)d.o(n)從未排序的序列中，依次取出元素，與已排序序列的元素比較后，放入已排序序列中的恰當(dāng)位置上，這是(1)排序。從未排序的序列中，挑選出元素，放在已排序序列的某一端位置，這是(2)排序。逐次將待排序的序列中的相鄰元素兩兩比較，凡是逆序則進(jìn)行交換，這是(3)排序。如果整個(gè)排序過程都在內(nèi)存中進(jìn)行，稱為(4)排序。排序算法的復(fù)雜性與排序算法的(5)有關(guān)。供選答案：::::(5):a.選擇b.插入c.比較d.歸并a.選擇b.插入c.比較d.歸并冒泡b.交換c.比較d.散列a.外部b.內(nèi)部c.外存d.內(nèi)存a.運(yùn)算量大小與占用存儲(chǔ)多少運(yùn)算量大小與處理的數(shù)據(jù)量大小并行處理能力和占用存儲(chǔ)多少占用存儲(chǔ)多少和處理的數(shù)據(jù)量大小答案：baaba操作系統(tǒng)是對(duì)計(jì)算機(jī)資源進(jìn)行的(1)系統(tǒng)軟件，是(2)的接口。在處理機(jī)管理中，進(jìn)程是一個(gè)重要的概念，它由程序塊、(3)和數(shù)據(jù)塊三部分組成，它有3種基本狀態(tài)，不可能發(fā)生的狀態(tài)轉(zhuǎn)換是(4)虛擬存儲(chǔ)器的作用是允許程序直接訪問比內(nèi)存更大的地址空間，它通常使用(5)作為它的一個(gè)主要組成部分。供選答案：(1):a.輸入和輸出b.鍵盤操作c.管理和控制d.匯編和執(zhí)行⑵:a.軟件和硬件b.主機(jī)和外設(shè)c.高級(jí)語言和機(jī)器語言d.用戶和計(jì)算機(jī)⑶: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.硬盤cdromd.寄存器答案：cdadb48?a是信息的載體，它能夠被計(jì)算機(jī)識(shí)別、存儲(chǔ)和加工處理。a.數(shù)據(jù)b.數(shù)據(jù)元素c.結(jié)點(diǎn)d.數(shù)據(jù)項(xiàng)下列程序段的時(shí)間復(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)下面程序段的時(shí)間復(fù)雜度為d。i=1;while(i=n)i=i*2;供選答案：a.o(1)b.o(n)c.o(n2)d.o(log2n)下面程序段的時(shí)間復(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)數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計(jì)算的程序設(shè)計(jì)問題中，計(jì)算機(jī)的a以及它們之間的關(guān)系和運(yùn)算等的學(xué)科。a■操作對(duì)象b.計(jì)算方法c.邏輯存儲(chǔ)d.數(shù)據(jù)映象在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分成c。a.動(dòng)態(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)算法分析的目的是c。找出數(shù)據(jù)結(jié)構(gòu)的合理性研究算法中輸入和輸出的關(guān)系分析算法的效率以求改進(jìn)分析算法的易懂性和文檔性算法分析的兩個(gè)主要方面是d。a.間復(fù)雜性和時(shí)間復(fù)雜性b.正確性和簡(jiǎn)明性c.可讀性和文檔性d.數(shù)據(jù)復(fù)雜性和程序復(fù)雜性一個(gè)線性順序表第一個(gè)元素的存儲(chǔ)地址是100，每個(gè)元素的長(zhǎng)度為2，則第5個(gè)元素的地址為b。a.110b.108c.100d.12057■若已知一個(gè)棧的入棧序列是1,2,3,?,n,其輸出序列為p1,p2,p3,?,pn，若p1=n，則pi為c。a.ib.n-ic.n-i+1d■不確定58■對(duì)于一個(gè)棧，給出輸入項(xiàng)a,b,c。如果輸入項(xiàng)序列由a,b,c所組成,則不可能產(chǎn)生的輸出序列是a。a.cabb.cbac.abcd.acb59.設(shè)有如下的單鏈表的按序號(hào)查找的算法，其時(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ì)算機(jī)軟件技術(shù)基礎(chǔ)(第三版)》的課后答案】是信息？信息與數(shù)據(jù)的區(qū)別和聯(lián)系在何處？信息定義之一：信息是現(xiàn)實(shí)世界中存在的客觀實(shí)體、現(xiàn)象、關(guān)系進(jìn)行描述的數(shù)據(jù)。信息定義之二：信息是經(jīng)過加工后并對(duì)實(shí)體的行為產(chǎn)生影響的數(shù)據(jù)。與數(shù)據(jù)的區(qū)別和聯(lián)系：數(shù)據(jù)定義：數(shù)據(jù)是現(xiàn)實(shí)世界客觀存在的實(shí)體或事物的屬性值，即指人們聽到的事實(shí)和看到的景象。我們把這些數(shù)據(jù)收集起來，經(jīng)過處理后，即得到人們需要的信息。信息和數(shù)據(jù)的關(guān)系可以歸結(jié)為：1.信息是有一定含義的數(shù)據(jù)。2.信息是經(jīng)過加工(處理)后的數(shù)據(jù)。3.信息是對(duì)決策有價(jià)值的數(shù)據(jù)。1.2信息有哪些基本屬性？信息的基本屬性有：1.事實(shí)性。2.等級(jí)性。3.可壓縮性。4.可擴(kuò)散性。5.可傳輸性。6.共享性。7.增值性和再生性。8.轉(zhuǎn)換性。1.3計(jì)算機(jī)的主要特點(diǎn)是什么？計(jì)算機(jī)最主要的特點(diǎn)是：1.高速自動(dòng)的操作功能。2.具有記憶的能力。3.可以進(jìn)行各種邏輯判斷。4.精確高速的計(jì)算能力。完整的計(jì)算機(jī)系統(tǒng)應(yīng)該包括哪幾部分？目前最完整的計(jì)算機(jī)系統(tǒng)學(xué)說認(rèn)為由五部分組成：1.人員2.數(shù)據(jù)3.設(shè)備4.程序5.規(guī)程什么是計(jì)算機(jī)硬件？什么是計(jì)算機(jī)軟件？硬件：泛指實(shí)際存在的物理設(shè)備，包括計(jì)算機(jī)本身及其外圍設(shè)備。微型計(jì)算機(jī)的硬件系統(tǒng)：主機(jī)、外存儲(chǔ)器、輸入設(shè)備、輸出設(shè)備、微機(jī)的系統(tǒng)總線。軟件：是指計(jì)算機(jī)程序、方法、規(guī)則的文檔以及在計(jì)算機(jī)上運(yùn)行它時(shí)所必須的數(shù)據(jù)。計(jì)算機(jī)軟件一般分為系統(tǒng)軟件和應(yīng)用軟件。1.8軟件技術(shù)發(fā)展的幾個(gè)階段各有什么特點(diǎn)？它與硬件的關(guān)系如何？第一階段：高級(jí)語言階段特點(diǎn)：這一時(shí)期，編譯技術(shù)代表了整個(gè)軟件技術(shù)，軟件工作者追求的主要目的是設(shè)計(jì)和實(shí)現(xiàn)在控制結(jié)構(gòu)和數(shù)據(jù)結(jié)構(gòu)方面表現(xiàn)能力強(qiáng)的高級(jí)語言。但在這一時(shí)期內(nèi)，編譯系統(tǒng)主要是靠手工編制，自動(dòng)化程度很低。硬件關(guān)系：此時(shí)期計(jì)算機(jī)的硬件要求僅能用機(jī)器指令來編制可運(yùn)行的程序。第二階段：結(jié)構(gòu)程序設(shè)計(jì)階段特點(diǎn)：在程序的正確性方面，提出了結(jié)構(gòu)化程序設(shè)計(jì)思想使程序的可靠性提高了。程序設(shè)計(jì)方法論方面，提出由頂向下法和自底向上法。使程序模塊化，使問題的復(fù)雜性和人的思維統(tǒng)一起來了。出現(xiàn)了軟件生產(chǎn)管理。硬件關(guān)系：磁盤問世，操作系統(tǒng)發(fā)展，非數(shù)值計(jì)算應(yīng)用發(fā)展，通信設(shè)備完善，網(wǎng)絡(luò)發(fā)展，集成電路發(fā)展等使軟件復(fù)雜性增加產(chǎn)生軟件危機(jī)，在此背景下發(fā)展了軟件技術(shù)。第三階段：自動(dòng)程序設(shè)計(jì)階段特點(diǎn)：向集成化、一體化發(fā)展。出現(xiàn)了軟件開發(fā)環(huán)境。程序設(shè)計(jì)基本方法進(jìn)一步改進(jìn)。硬件關(guān)系：集成電路迅速發(fā)展以及高分辨率終端的出現(xiàn)，為個(gè)人計(jì)算機(jī)發(fā)展提供了條件，再加上人工智能、專家系統(tǒng)研究的發(fā)展，使程序設(shè)計(jì)進(jìn)入成熟期。第二章2.1什么是數(shù)據(jù)結(jié)構(gòu)？它對(duì)算法有什么影響？數(shù)據(jù)結(jié)構(gòu)是指同一數(shù)據(jù)對(duì)象中各數(shù)據(jù)元素間存在的關(guān)系。對(duì)算法是影響：算法的實(shí)現(xiàn)必須借助程序設(shè)計(jì)語言中提供的數(shù)據(jù)類型及其運(yùn)算。一個(gè)算法的效率往往與數(shù)據(jù)的表達(dá)形式有關(guān)，因此數(shù)據(jù)結(jié)構(gòu)的選擇對(duì)數(shù)據(jù)處理的效率起著至關(guān)重要的作用。它是算法和程序設(shè)計(jì)的基本部分，它對(duì)程序的質(zhì)量影響很大。2.2何謂算法？它與程序有何區(qū)別？廣義地說，為解決一個(gè)問題而采取的方法和步驟，就稱為“算法”。計(jì)算機(jī)算法是通過計(jì)算機(jī)能執(zhí)行的算法語言來表達(dá)的。和程序的區(qū)別：一個(gè)程序包括兩個(gè)方面的內(nèi)容：（1）、對(duì)數(shù)據(jù)的描述，即數(shù)據(jù)結(jié)構(gòu)。（2）、對(duì)操作的描述，即算法。所以算法是程序的一個(gè)要素。2.3何謂頻度，時(shí)間復(fù)雜度，空間復(fù)雜度？說明其含義。頻度：在某個(gè)算法中某個(gè)語句被重復(fù)執(zhí)行的次數(shù)就是此語句的頻度。時(shí)間復(fù)雜度：是用來估算一個(gè)算法的執(zhí)行時(shí)間的量，以算法中頻度最大的語句來度量?？臻g復(fù)雜度：指在算法中所需的輔助空間的單元，而不包括問題的原始數(shù)據(jù)占用的空間。數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)主要有哪兩種?它們之間的本質(zhì)區(qū)別是什么？數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)：向量和鏈表。本質(zhì)區(qū)別：向量是連續(xù)存放的，其存儲(chǔ)空間是靜態(tài)分配的，以存放順序來表達(dá)元素的前后件的關(guān)系。鏈?zhǔn)酱鎯?chǔ)結(jié)果不需要一組連續(xù)的存儲(chǔ)單元，其數(shù)據(jù)元素可以分散存放在存儲(chǔ)空間中，其元素關(guān)系由指針來指向。2.16試比較順序表和鏈表的優(yōu)缺點(diǎn)。線性表的長(zhǎng)度是否固定方面：由于向量的存儲(chǔ)空間是靜態(tài)分配的，鏈表的存儲(chǔ)空間是動(dòng)態(tài)分配的，因此若表長(zhǎng)不固定時(shí)采用線性鏈表較好。線性表的主要操作是什么：由于向量是連續(xù)存放的，所以適用于查找操作，不適用插入、刪除操作。由于線性鏈表只能順序存取，所以適用于插入、刪除操作，不適用于查找操作。采用的算法語言：線性鏈表要求所使用的語言工具提供指針類型變量。2.17試比較單向鏈表與雙向鏈表的優(yōu)缺點(diǎn)。1.單向鏈表只能單方向地尋找表中的結(jié)點(diǎn)，雙向鏈表具有對(duì)稱性，從表中某一給定的結(jié)點(diǎn)可隨意向前或向后查找。2.在作插入、刪除運(yùn)算時(shí)，雙向鏈表需同時(shí)修改兩個(gè)方向上的指針單向鏈表則簡(jiǎn)便些。2.23試畫出表達(dá)式a*(b-d)/d+c**(e*f)執(zhí)行過程中ns,os棧的變化情況。b-d=t1d/t1=t2t2*a=t3e*f=t4t4**c=t5用三元組和帶行輔助向量形式表示下列稀疏矩陣：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）：三元組帶行輔助向量試說明樹與二叉樹有何不同？為何要將一般樹轉(zhuǎn)換為二叉樹？樹與二叉樹區(qū)別：樹是由n個(gè)（n=0）結(jié)點(diǎn)組成的有限集合t,其中有且僅有一個(gè)結(jié)點(diǎn)稱為根結(jié)點(diǎn)，在此類元素結(jié)點(diǎn)之間存在明顯的分支和層次關(guān)系。二叉樹是一種特殊的樹結(jié)構(gòu),每一個(gè)結(jié)點(diǎn)最多只有兩個(gè)孩子,即最多只有兩個(gè)分支。為何要轉(zhuǎn)換：一般樹,樹中結(jié)點(diǎn)次序沒有要求,分支龐雜。而二叉樹,元素之間存在嚴(yán)謹(jǐn)?shù)那昂蟠P(guān)系,在對(duì)數(shù)據(jù)元素進(jìn)行刪除、查找、插入等運(yùn)算時(shí)更加有效率。將下列（題圖2.3）的一般樹化為二叉樹。題圖2.3轉(zhuǎn)換后：2.30設(shè)一棵二叉樹其中序和后序遍歷為中序：bdceafhg后序：decbhgfa畫出這棵二叉樹的邏輯結(jié)構(gòu),并寫出先序遍歷結(jié)果。先序遍歷：【篇三：計(jì)算機(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⑶i=1時(shí)，i=2,j=j+i=1+2=2+1,i=2時(shí)，i=3，j=j+i=(2+1)+3=3+1+2，i=3時(shí)，i=4,j=j+i=(3+1+2)+4=4+1+2+3,i=4時(shí)，i=5，j=j+i=(4+1+2+3)+5=5+1+2+3+4,??=k時(shí)，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?3?n解出滿足上述不等式的k值，即為語句i=i+1的程序步數(shù)。⑷for語句每執(zhí)行一次，語句i=i+j將執(zhí)行n次，而i的值會(huì)增加因此，當(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?n1=/的最小整數(shù)k，語句i=i+j的程序步數(shù)為n*k。1=/4■試編寫一個(gè)函數(shù)計(jì)算n!*2的值，結(jié)果存放于數(shù)組a[arraysize]的第n個(gè)數(shù)組元素中，0?n?arraysize。若設(shè)計(jì)算機(jī)中允許的整數(shù)的最大值為maxint，則當(dāng)narraysize或者對(duì)于某一個(gè)k(0?k?n)，使得k!*2maxint時(shí)，應(yīng)按出錯(cuò)處理。可有如下三種不同的出錯(cuò)處理方式：(1)用printf顯示錯(cuò)誤信息及exit(1)語句來終止執(zhí)行并報(bào)告錯(cuò)誤;kn在函數(shù)的參數(shù)表設(shè)置一個(gè)引用型的整型變量來區(qū)別是正常返回還是某種錯(cuò)誤返回。試討論這三種方法各自的優(yōu)缺點(diǎn),并以你認(rèn)為是最好的方式實(shí)現(xiàn)它。【解答】#includestdio.h

constintarraysize=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)的定義.為簡(jiǎn)化起見，表元素我們使用整型數(shù)據(jù)-- 數(shù)據(jù)元素從data[0]處開始存儲(chǔ) —*/typedefstruct/*注意typedef的使用*/{intdata[maxsize];/*數(shù)據(jù)域*/intlength;/*表長(zhǎng)*/}listtype;5.設(shè)有一個(gè)線性表(a0,a1,?,an-2,an-1)存放在一個(gè)一維數(shù)組a[arraysize]中的前n個(gè)數(shù)組元素位置。請(qǐng)編寫一個(gè)函數(shù)將這個(gè)線性表原地逆置，即將數(shù)組的前n個(gè)原址內(nèi)容置換為(an-1,an-2,?,a1,inverse(listtype*a){a0)。a0)。最后分析此算法的時(shí)間復(fù)雜度及空間復(fù)雜度。解答】voidinttmp;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;}}時(shí)間復(fù)雜度：需進(jìn)行n/2次循環(huán)，因此時(shí)間復(fù)雜度為o(n)；空間復(fù)雜度：使用一個(gè)整形輔助存儲(chǔ)單元tmp，因此空間復(fù)雜度為o(1)。6.順序表的插入和刪除要求仍然保持各個(gè)元素原來的次序。設(shè)在等概率情形下,對(duì)有127個(gè)元素的順序表進(jìn)行插入,平均需要移動(dòng)多少個(gè)元素?刪除一個(gè)元素,又平均需要移動(dòng)多少個(gè)元素?【解答】若設(shè)順序表中已有n個(gè)元素。又設(shè)插入或刪除表中各個(gè)元素的概率相等，則在插入時(shí)因有n+1個(gè)插入位置(可以在表中最后一個(gè)表項(xiàng)后面追加)，每個(gè)元素位置插入的概率為1/(n+1),但在刪除時(shí)只能在已有n個(gè)表項(xiàng)范圍內(nèi)刪除，所以每個(gè)元素位置刪除的概率為1/n。插入時(shí)平均移動(dòng)元素個(gè)數(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í)平均移動(dòng)元素個(gè)數(shù)amn為amn??ni?0(n?i?1)?1n((n?1)?(n?2)???1?0)?1(n?1)nn2?n?12?637.利用順序表的操作，實(shí)現(xiàn)以下的函數(shù)。并分析你所編制的函數(shù)的時(shí)間復(fù)雜度，并分析(2)與(3)的時(shí)間復(fù)雜度出現(xiàn)差異的原因。(1)從順序表中刪除具有給定值x的所有元素。(2)從順序表中刪除其值在給定值s與t之間(要求s小于t)的所有元素。⑶從有序順序表中刪除其值在給定值s與t之間(要求s小于t)的所有元素。(4)將兩個(gè)有序順序表la,lb合并成一個(gè)新的有序順序表lc。(5)從順序表中刪除所有其值重復(fù)的元素，使表中所有元素的值均不相同?！窘獯稹?1)從順序表中刪除具有給定值x的所有元素。voiddelvalue(listtype*l,intx){inti=0,j;while(il-length)if(l-data[i]==x){l-length--;}}elsei++;⑵實(shí)現(xiàn)刪除其值在給定值s與t之間(要求s小于t)的所有元素的函數(shù)如下：/*循環(huán),尋找具有值X的元素并刪除它*//*刪除具有值x的元素，后續(xù)元素前移*//*表長(zhǎng)減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++;/*表長(zhǎng)減1*/(3)實(shí)現(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的第一個(gè)元素*/if(l-data[i+j]