2016年4月-2009年4月福建省自考07186軟件技術(shù)基礎(chǔ)試題及答案含評(píng)分標(biāo)準(zhǔn)10套

第1頁(yè)共5頁(yè)2009年4月高等教育自學(xué)考試福建省統(tǒng)一命題考試軟件技術(shù)基礎(chǔ)試卷(課程代碼7186)本試卷滿分100分，考試時(shí)間150分鐘。一、填空題(本大題共15小題，每小題2分，共30分)請(qǐng)?jiān)诿啃☆}的空格中填上正確答案。錯(cuò)填、不填均無(wú)分。1．?dāng)?shù)據(jù)結(jié)構(gòu)算法中，通常用空間復(fù)雜度和兩種方法綜合衡量算法的效率。2．順序存儲(chǔ)的線性表，若第l個(gè)元素的存儲(chǔ)地址是200，每個(gè)元素的長(zhǎng)度為4，則第11個(gè)元素的地址是。3．刪除長(zhǎng)度為n的順序表中的第k個(gè)元素(1≤k≤n)時(shí)，需要從前向后依次前移個(gè)元素。4．某二叉樹(shù)的前序遍歷序是abdgcefh，中序遍歷序是dgbaechf，則后序遍歷序是。5．二叉樹(shù)的三個(gè)基本組成單元是左子樹(shù)，右子樹(shù)和。6．對(duì)序列(1，3，5，8，l0，18，20，22，24，30，40)采用折半查找法查找元素24，需進(jìn)行次關(guān)鍵字比較。7．所謂進(jìn)程指的是程序的一次執(zhí)行過(guò)程。8．進(jìn)程三種基本狀態(tài)相互轉(zhuǎn)化中不能實(shí)現(xiàn)的是阻塞→運(yùn)行和。9．?dāng)?shù)據(jù)庫(kù)管理系統(tǒng)是幫助用戶創(chuàng)建、維護(hù)和使用數(shù)據(jù)庫(kù)的軟件系統(tǒng)，它是數(shù)據(jù)庫(kù)系統(tǒng)的。10．E—R圖中采用自考押題微信344647公眾號(hào)順通考試資料來(lái)表示屬性。11．面向?qū)ο箝_(kāi)發(fā)技術(shù)追求的是軟件系統(tǒng)對(duì)的直接模擬。12．在軟件設(shè)計(jì)階段首先要完成，然后進(jìn)行洋細(xì)設(shè)計(jì)。13．軟件維護(hù)一般分為校正性維護(hù)、適應(yīng)性維護(hù)、和預(yù)防性維護(hù)。14．面向?qū)ο箢I(lǐng)域中的UML不是一種具體的方法，而是一種語(yǔ)言。15．面向?qū)ο蠓治瞿Ｐ陀腥N，分別是：對(duì)象模型、和功能模型。二、單項(xiàng)選擇題(本大題共15小題，每小題2分，共30分)在每小題列出的四個(gè)備選項(xiàng)中只有一個(gè)是符合題目要求的，請(qǐng)將其代碼填寫(xiě)在題后的括號(hào)內(nèi)。錯(cuò)選、多選或未選均無(wú)分。16．若一個(gè)算法的運(yùn)行時(shí)間函數(shù)T(n)=n2+102n+102，則用O表示的時(shí)問(wèn)復(fù)雜度為【】A．O(n)B．O(n3)C．O(n2)D．O(n2+n)17．線性表順序存儲(chǔ)結(jié)構(gòu)的主要特性是能實(shí)現(xiàn)數(shù)據(jù)元素的【】A．順序存取B．隨機(jī)存取C．索引存取D．HASH存取18．線性鏈表不具有的特點(diǎn)是【】A．隨機(jī)存取B．不必事先估計(jì)所需存儲(chǔ)空間大小C．插入與刪除時(shí)不必移動(dòng)元素D．存儲(chǔ)空間與線性表長(zhǎng)度成正比19．對(duì)二維數(shù)組A[1．．20][1．．l5]以列優(yōu)先順序?qū)⑺性匾来未娣庞谝痪S數(shù)組B[1．．300]中，則A中元素A[1O][11]對(duì)應(yīng)B中的位置k為【】A．210B．2l1C．220D．23020．對(duì)線性表進(jìn)行折半查找時(shí)，要求線性表的組織構(gòu)造必須滿足【】A．關(guān)鍵字有序的鏈接表B．鏈按表但關(guān)鍵字不一定有序C．順序但關(guān)鍵字不一定有序D．關(guān)鍵字有序的順序表21．假設(shè)在有序表A[0．．．9]中進(jìn)行折半查找，比較三次查找成功的結(jié)點(diǎn)數(shù)為【】A．3B．4C．5D．622．從二叉排序樹(shù)中查找一個(gè)元素時(shí)，其時(shí)問(wèn)復(fù)雜度大致為【】A．O(n)B．O(long2n)C．O(n2)D．O(nlong2n)23．操作系統(tǒng)的兩個(gè)最基本特征是并發(fā)性和【】A．并行性B．共享性C．多態(tài)性D．虛擬性24．從操作系統(tǒng)的發(fā)展歷史看，最早出現(xiàn)的操作系統(tǒng)類型是【】A．分時(shí)操作系統(tǒng)B．實(shí)時(shí)操作系統(tǒng)C．批處理系統(tǒng)D．分布式操作系統(tǒng)25．以下對(duì)操作系統(tǒng)的敘述中不正確的是【】A．操作系統(tǒng)是一種大型的應(yīng)用軟件B．操作系統(tǒng)簡(jiǎn)稱OSC．操作系統(tǒng)是位于硬件之上的第一層軟件D．操作系統(tǒng)是用戶與硬件之間的接口26．構(gòu)成關(guān)系模型的三個(gè)部分是【】A．?dāng)?shù)據(jù)結(jié)構(gòu)、關(guān)系操作和關(guān)系完整性B．?dāng)?shù)據(jù)模型、關(guān)系操作和關(guān)系完整性C．?dāng)?shù)據(jù)結(jié)構(gòu)、關(guān)系語(yǔ)言和關(guān)系完整性D．?dāng)?shù)據(jù)模型、關(guān)系語(yǔ)言和約束27．確定待開(kāi)發(fā)系統(tǒng)的總體目標(biāo)和范圍，研究系統(tǒng)的可行性和可能解決方案，對(duì)資源、成本及進(jìn)度進(jìn)行合理的估算。這在軟件開(kāi)發(fā)的哪個(gè)階段完成?【】A．制定計(jì)劃B．需求分析C．軟件設(shè)計(jì)D．測(cè)試28．在軟件生命周期中，明確軟件系統(tǒng)功能，確定軟件系統(tǒng)必須做什么的階段是【】A．制定計(jì)劃B．需求分析C．概要設(shè)計(jì)D．詳細(xì)設(shè)計(jì)29．?dāng)?shù)據(jù)流圖中→符號(hào)表示【】A．?dāng)?shù)據(jù)加工B．?dāng)?shù)據(jù)存儲(chǔ)文件C．?dāng)?shù)據(jù)流D．?dāng)?shù)據(jù)源點(diǎn)30以下列對(duì)面向?qū)ο箝_(kāi)發(fā)方法的描述，不正確的是【】A．Booch最早描述了面向?qū)ο蟮能浖_(kāi)發(fā)方法的基礎(chǔ)問(wèn)題B．Cord／Yourdon方法比較系統(tǒng)地介紹了面向?qū)ο蠓治龊兔嫦驅(qū)ο笤O(shè)計(jì)C．Cord／Yourdon方法強(qiáng)調(diào)技術(shù)的創(chuàng)新性．以便提升可復(fù)用性D．OMT方法中的功能模型反映的是系統(tǒng)模塊的輸入值和輸出值三、簡(jiǎn)答題(本大題共5小題，每小題4分，共20分)31．簡(jiǎn)述后序遍歷二叉樹(shù)的基本過(guò)程。32．對(duì)于序列(5，3，10，18，1，2，6，7，9，4)，按照直接插入排序法給出第2趟、第4趟、第6趟、第8趟的排序新序列。33．請(qǐng)完成內(nèi)部排序方法的性能比較的表格。34．什么是操作系統(tǒng)?35．簡(jiǎn)述面向?qū)ο箝_(kāi)發(fā)方法中Booch方法的分析和設(shè)計(jì)的基本步驟。四、綜合應(yīng)用題（本大題共2小題，每小題10分，共20分)36．假設(shè)兩個(gè)完整型數(shù)組a[n]，b[n]表示兩個(gè)集合，求c=a∪b，假定c已經(jīng)分配足夠的空間；請(qǐng)依據(jù)以下函數(shù)聲明，完成上述問(wèn)題的類C語(yǔ)言算法描述，同時(shí)給出用O表述的時(shí)間復(fù)雜度。Voidgetc(inta[]，intb[]，intc[]，intn){}37．構(gòu)建超市商品銷(xiāo)售POS收銀系統(tǒng)用例圖。提示信息如下：人員有POS收銀員，系統(tǒng)管理員；前臺(tái)POS，后臺(tái)服務(wù)器提供數(shù)據(jù)支持。操作員掃描商品條形碼，讀取商品名稱、金額等信息，輸入購(gòu)買(mǎi)數(shù)量，告知客戶結(jié)賬。

2009年10月高等教育自學(xué)考試福建省統(tǒng)一命題考試軟件技術(shù)基礎(chǔ)試卷(課程代碼07186)一、填空題(本大題共15小題，每小題2分，共30分)請(qǐng)?jiān)诿啃☆}的空格中填上正確答案。錯(cuò)填、不填均無(wú)分。

2010年4月高等教育自學(xué)考試福建省統(tǒng)一命題考試軟件技術(shù)基礎(chǔ)試卷(課程代碼07186)一、填空題(本大題共15小題，每空2分，共30分)請(qǐng)?jiān)诿啃☆}的空格中填上正確答案。錯(cuò)填、不填均不得分。1．一個(gè)算法通常是由控制結(jié)構(gòu)和構(gòu)成。2．非空的線性表(a1,a2,…an-1,an)，元索ai(1<i≤n)的直接前驅(qū)是。3．typedefstructnode{Datatypedata;structnode*next;}LinkList；定義的不帶頭結(jié)點(diǎn)的單鏈表L，將初值為L(zhǎng)的指針P移到尾結(jié)點(diǎn)的語(yǔ)句是。4．若二叉樹(shù)的前序遍歷和后序遍歷序列正好相反，則該二叉樹(shù)的度為2的結(jié)點(diǎn)數(shù)=。5．一棵含有n個(gè)結(jié)點(diǎn)的k叉樹(shù)(0<k<n)，可能達(dá)到的最大深度是。6．對(duì)某二叉排序樹(shù)進(jìn)行遍歷，且保證輸出所有結(jié)點(diǎn)的值序列按增序排列，對(duì)該二叉排序樹(shù)應(yīng)采用遍歷法。7．排序是將一組任意排列的數(shù)據(jù)元素按的值遞增或遞減重新排列成有序的序列。8．操作系統(tǒng)中資源共事的主要方式有同時(shí)訪問(wèn)和。9．文件的邏輯結(jié)構(gòu)就是從所看到的文件結(jié)構(gòu)形式。10．進(jìn)程的基本狀態(tài)包括就緒狀態(tài)、運(yùn)行狀態(tài)和。11．目前常用的數(shù)據(jù)組織層模型包括層次模型、網(wǎng)狀模型、面向?qū)ο竽Ｐ秃汀?2．軟件模塊內(nèi)部的越高則模塊的獨(dú)立性越強(qiáng)。13．維護(hù)對(duì)軟件非常重要，應(yīng)當(dāng)在設(shè)計(jì)和階段充分考慮軟件的可維護(hù)性。14．面向?qū)ο笾械南⒅傅氖菍?duì)象發(fā)出的。15．UML中的狀態(tài)圖所包含的基本元素有狀態(tài)和。二、單項(xiàng)選擇題。(本大題共15小題，每小題2分，共30分)在每小題列出的四個(gè)備選項(xiàng)中只有一個(gè)是符合題目要求的，請(qǐng)將其代碼填寫(xiě)在題后的括號(hào)內(nèi)。錯(cuò)選、多選或未選均不得分。16．以下選項(xiàng)中不屬于算法特性的是【】A．輸入/輸出B．可行性C．完成性D．有窮性17．如果某二叉樹(shù)的前序遍歷為abcdef，后序遍歷為efdcba，則其中序遍歷為【】A．ecdfbaB．edfcbaCedfbcaD．a(chǎn)cbedf18．以下選項(xiàng)中正確的是【】A．串的邏輯結(jié)構(gòu)和線性表相同B．串的長(zhǎng)度必須大于零c．串中元索只能是字母和數(shù)字D．空串就是空白串19．在長(zhǎng)度為n的順序表的第k個(gè)位置(1≤k≤n+1)前插入一個(gè)新元素時(shí)，需要從后向前依次后移的元素個(gè)數(shù)為【】A．n-kB．kC．n-k-1D．n-k+120．適于對(duì)動(dòng)態(tài)查找表進(jìn)行高效率查找的組織結(jié)構(gòu)是【】A．二叉排序樹(shù)B．分塊有序表C．有序表D．線性鏈表21．以下哪種排序法的平均時(shí)間復(fù)雜度數(shù)越級(jí)最小【】A．直接插入排序B．冒泡排序C．簡(jiǎn)單選擇排序D．希爾排序22．以下敘述正確的是【】A．直接插入排序是不穩(wěn)定的排序法B．冒泡排序是不穩(wěn)定的排序法C．希爾排序是穩(wěn)定的排序法D．簡(jiǎn)單選擇排序是不穩(wěn)定的排序法23．操作系統(tǒng)為實(shí)現(xiàn)設(shè)備無(wú)關(guān)性，將設(shè)備管理軟件分成I/O控制系統(tǒng)和【】A．用戶程序?qū)覤．物理設(shè)備層C．硬件抽象層D．設(shè)備驅(qū)動(dòng)程序?qū)?4．操作系統(tǒng)提供的用戶接口不包括【】A．命令接口B．圖形用戶GUI接口C．系統(tǒng)調(diào)用命令D．注冊(cè)表接口25．對(duì)數(shù)據(jù)庫(kù)管理系統(tǒng)的特點(diǎn)敘述中，不正確的是【】A．?dāng)?shù)據(jù)結(jié)構(gòu)化B．?dāng)?shù)據(jù)冗余度大C．提高了系統(tǒng)的靈活性D．?dāng)?shù)據(jù)獨(dú)立性強(qiáng)26．若一個(gè)工廠只有一個(gè)廠長(zhǎng)，則工廠和廠長(zhǎng)之間的聯(lián)系是【】A．一對(duì)一B．一對(duì)多C．多對(duì)多D．不確定27．軟件開(kāi)發(fā)中結(jié)構(gòu)化方法的基本要點(diǎn)不包括【】A．自頂向下B．自底向上C．逐步求精D．模塊化設(shè)計(jì)28．軟件測(cè)試方法中，白盒測(cè)試主要用于測(cè)試【】A．模塊接口B．軟件功能C．程序正確性D．程序內(nèi)部邏輯29．軟件工程中僅根據(jù)程序的功能說(shuō)明而不關(guān)心程序內(nèi)部的邏輯結(jié)構(gòu)的測(cè)試方法，稱為【】A．白盒法B．黑盒法C．綜合法D．灰盒法30．UML的模型圖中有一大類是屬于動(dòng)態(tài)圖，以下選項(xiàng)中不屬于動(dòng)態(tài)圖的是【】A．狀態(tài)圖B．活動(dòng)圖C．構(gòu)件圖D．順序圖三、簡(jiǎn)答題(本大題共5小題，每小題4分，共20分)31．設(shè)二叉樹(shù)后序遍歷結(jié)果為BAC，畫(huà)出所有可能的二叉樹(shù)。32．簡(jiǎn)述折半查找的基本思想。33．在操作系統(tǒng)中，文件的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)指什么?34．簡(jiǎn)述軟件工程中需求分析的主要任務(wù)。35．請(qǐng)依據(jù)測(cè)試順序列出軟件測(cè)試一般要經(jīng)歷的幾個(gè)階段。四、應(yīng)用題(本大題共2小題，每小題10分，共20分)36．當(dāng)給定a，b，c三個(gè)整數(shù)時(shí)，判定一元二次方程ax2+bx+c=0實(shí)根的個(gè)數(shù)，如果不是二次方程也不是一次方程則返回-1，如果元實(shí)根返回0，如果有2個(gè)相等實(shí)根或1個(gè)實(shí)根則返回1，如果有2個(gè)不相等實(shí)根則返回2；請(qǐng)依據(jù)以下函數(shù)聲明，完成上述問(wèn)題的類C語(yǔ)言算法描述，同時(shí)給出用O表述的時(shí)間復(fù)雜度。introotnum(inta,intb,intc){}37.typedefstruct{keytypekey[N];intlen}LineTable;//順序查找表類型，N為最大值，已定義針對(duì)上述順序表定義，完成順序表的順序查找算法，要求如下：將監(jiān)視哨設(shè)在下標(biāo)值的高端，若找到第一個(gè)關(guān)鍵字值等于k，則返回其對(duì)應(yīng)的下標(biāo)，否則返回-1。intsearch_in_linetable(keytypek,LineTablest){intindex;}

2010年10月高等教育自學(xué)考試福建省統(tǒng)一命題考試軟件技術(shù)基礎(chǔ)試卷（課程代碼07186）一、填空題(本大題共15小題，每小題2分，共30分)請(qǐng)?jiān)诿啃☆}的空格中填上正確答案。錯(cuò)填、不填均不得分。1．在數(shù)據(jù)結(jié)構(gòu)中，數(shù)據(jù)的基本單位是。2．隊(duì)列的特點(diǎn)是先進(jìn)先出，為此隊(duì)列僅在插入元素。3．任何一棵二叉樹(shù)，如果n1,n2,n3，分別是度為0，1，2的結(jié)點(diǎn)的個(gè)數(shù)，則，n1=。4．樹(shù)的度是樹(shù)內(nèi)各結(jié)點(diǎn)度的。5．由判定樹(shù)可知，折半查找法查找結(jié)點(diǎn)F的過(guò)程中和關(guān)鍵字比較的次數(shù)恰好等于結(jié)點(diǎn)F在判定樹(shù)中的。6．二叉排序樹(shù)中任意一個(gè)結(jié)點(diǎn)的關(guān)鍵字小于其中的所有結(jié)點(diǎn)的關(guān)鍵字。7．關(guān)鍵字值相等的不同記錄排序前后相對(duì)次序的排序方法稱為穩(wěn)定的排序方法。8．進(jìn)程是操作系統(tǒng)進(jìn)行獨(dú)立運(yùn)行及調(diào)度的基本單位，也是的基本單位。9．文件的物理結(jié)構(gòu)指的是文件在的存儲(chǔ)形式。10．常用的概念模型有語(yǔ)義對(duì)象模型和。11．關(guān)系的完整性包括用戶自定義完整性、實(shí)體完整性和。12．結(jié)構(gòu)化設(shè)計(jì)以為基礎(chǔ)，采用自頂向下，逐步求精和模塊化的過(guò)程得到軟件結(jié)構(gòu)圖。13．可行性研究通常從操作可行性、社會(huì)可行性、經(jīng)濟(jì)可行性和四方面進(jìn)行分析。14．軟件系統(tǒng)的模塊層次結(jié)構(gòu)是，它反映了整個(gè)系統(tǒng)的功能實(shí)現(xiàn)。15．面向?qū)ο笾械睦^承指的是子類可以自動(dòng)擁有父類的全部。二、單項(xiàng)選擇題(本大題共15小題，每小題2分，共30分)在每小題列出的四個(gè)備選項(xiàng)中只有一個(gè)是符合題目要求的，請(qǐng)將其代碼填寫(xiě)在題后的括號(hào)內(nèi)。錯(cuò)選、多選或未選均不得分。16．對(duì)于合法的輸入，算法必須在執(zhí)行有限次后在有限的時(shí)間內(nèi)完成，這體現(xiàn)了算法特性中的【】A．可行性B．確定性C．有窮性D．健壯性17．在線性結(jié)構(gòu)中，數(shù)據(jù)元素之間存在的關(guān)系是【】A．同屬一個(gè)集合B．一個(gè)對(duì)一個(gè)C．一個(gè)對(duì)多個(gè)D．多個(gè)對(duì)多個(gè)18．一個(gè)棧的入棧序列是H，I，J，K，L，則該棧不可能的輸出序列是【】A．HIJKLB．LKJIHC．JKLIHD．KLIJH19．假設(shè)以行優(yōu)先存儲(chǔ)的二維數(shù)組A[1…100，1…100]，設(shè)每個(gè)數(shù)據(jù)元素占2個(gè)存儲(chǔ)單元，基地址為100，則LOC(A[5，5])=【】A．808B．818C．908D．91820．已知一棵二叉樹(shù)中度為0的結(jié)點(diǎn)個(gè)數(shù)為11個(gè)，則度為2的結(jié)點(diǎn)個(gè)數(shù)為【】A．5B．6C．10D．2221．有一個(gè)有序表{1，2，4，8，12，22，32，45，48，50，72，80}，用折半法查找關(guān)鍵字為50的結(jié)點(diǎn)時(shí)，需要幾次比較才能成功?【】A．2B．3C．4D．522．直接插入排序法是從第幾個(gè)元素開(kāi)始，逐個(gè)插入前邊適當(dāng)位置的排序方法?【】A．1B．2C．n／2D．n23．簡(jiǎn)單選擇排序每趟在n-i+1個(gè)記錄中選取關(guān)鍵字最小的記錄放在有序序列的哪個(gè)位置?【】A．n-i+lB．i-1C．iD．i+124．下列不屬于操作系統(tǒng)的基本類型的類型是【】A．分時(shí)操作系統(tǒng)B．個(gè)人計(jì)算機(jī)操作系統(tǒng)C．批處理系統(tǒng)D．實(shí)時(shí)操作系統(tǒng)25．在操作系統(tǒng)文件的物理結(jié)構(gòu)中，哪個(gè)結(jié)構(gòu)必須要求一批相鄰的外存塊?【】A．鏈接結(jié)構(gòu)B．索引結(jié)構(gòu)C．連續(xù)結(jié)構(gòu)D．記錄式結(jié)構(gòu)26．?dāng)?shù)據(jù)庫(kù)概念中模型如果是面向計(jì)算機(jī)的，則稱該模型為【】A．?dāng)?shù)據(jù)層模型B．概念層模型C．概念模型D．信息模型27．實(shí)體內(nèi)部的聯(lián)系通常指的是【】A．組成實(shí)體的各屬性之間的聯(lián)系B．實(shí)體之間的聯(lián)系C．實(shí)體內(nèi)各屬性與候選碼之間的聯(lián)系D．各實(shí)體主碼之間的聯(lián)系28．結(jié)構(gòu)化程序設(shè)計(jì)的概念是由誰(shuí)最先提出來(lái)的?【】A．美國(guó)IBM公司研究人員B．WinstonRoyceC．B．W．BoehmD．E．W．Dijkstra29．畫(huà)某軟件系統(tǒng)的數(shù)據(jù)流圖時(shí)，其頂層圖設(shè)計(jì)有【】A．0張B．1張C．1個(gè)模塊1張D．2張或2張以上30．模塊獨(dú)立性最強(qiáng)的耦合是【】A．?dāng)?shù)據(jù)耦合B．非直接耦合C．標(biāo)記耦合D．外部耦合三、簡(jiǎn)答題(本大題共5小題，每小題4分，共20分)31．簡(jiǎn)述數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)的基本類型及主要特點(diǎn)。32．簡(jiǎn)要分析串順序存儲(chǔ)結(jié)構(gòu)的不足。33．已知某二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)如下圖所示，畫(huà)出該二叉樹(shù)。34．假定對(duì)有序表(5，7，30，54，63，72)進(jìn)行折半查找，畫(huà)出其對(duì)應(yīng)的二叉判定樹(shù)，并計(jì)算查找成功時(shí)的平均查找次數(shù)。35．簡(jiǎn)述數(shù)據(jù)庫(kù)管理系統(tǒng)相對(duì)文件管理系統(tǒng)的主要特點(diǎn)。四、應(yīng)用題(本大題共2小題，每小題10分，共20分)36．#defineN100typedefstruct{intdata[N]；intlen；}QList；根據(jù)以上定義的線性表，寫(xiě)出一個(gè)函數(shù)：對(duì)兩個(gè)線性表La，Lb，實(shí)現(xiàn)La=La-Lb，即去掉La表中與Lb表中相同的元素，最后的結(jié)果依然以La表返回。voidLa-Lb(QListLa，QListLb){inti，i，k；37．對(duì)于序列R(14，12，51，8．42，35，15，6)，請(qǐng)給出簡(jiǎn)單選擇排序的每一趟排序結(jié)果。第l趟=第2趟=第3趟=第4趟=第5趟=第6趟=第7趟=

2011年4月高等教育自學(xué)考試福建省統(tǒng)一命題考試軟件技術(shù)基礎(chǔ)試卷（課程代碼07186）一、填空題(本大題共15小題，每小題2分，共30分)請(qǐng)?jiān)诿啃☆}的空格中填上正確答案。錯(cuò)填、不填均不得分。1．?dāng)?shù)據(jù)元素存儲(chǔ)結(jié)構(gòu)一般采用順序存儲(chǔ)結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)。2．樹(shù)中度數(shù)為0的結(jié)點(diǎn)，即沒(méi)有子樹(shù)的結(jié)點(diǎn)叫作葉子結(jié)點(diǎn)或結(jié)點(diǎn)。3．typedefstructnode{Datatypedata；structnode*next；}LinkList；定義的單鏈表中節(jié)點(diǎn)a，b前后相鄰且b為非尾節(jié)點(diǎn)，則刪除結(jié)點(diǎn)b的操作為。4．若順序隊(duì)列的隊(duì)頭和隊(duì)尾指針?lè)謩e是fro和rea，則判斷隊(duì)列為空的條件為。5．二維數(shù)組A按行順序存儲(chǔ)，其中每個(gè)元素占2個(gè)存儲(chǔ)單元。若A[1][1]的存儲(chǔ)地址為100，A[3][3]的存儲(chǔ)地址為l40，則A[5][5]的存儲(chǔ)地址為。6．深度為k的二叉樹(shù)的最大結(jié)點(diǎn)數(shù)為。7．二叉排序樹(shù)中任何一棵子樹(shù)是一棵。8．內(nèi)部排序是指待排序記錄全部存儲(chǔ)在計(jì)算機(jī)的中進(jìn)行的排序。9．進(jìn)程的主要特征包括獨(dú)立性、動(dòng)態(tài)性和。10．操作系統(tǒng)提供的用戶接口主要包括命令接口、GUI、JCL和。11．在E—R方法中實(shí)體之間的聯(lián)系主要有一對(duì)一聯(lián)系、一對(duì)多聯(lián)系和。12．軟件工程是從——和方法兩方面研究如何更好地開(kāi)發(fā)和維護(hù)軟件的學(xué)科。13．結(jié)構(gòu)化分析采用數(shù)據(jù)流圖作為分析工具，其中的長(zhǎng)方形圖形表示。14．軟件測(cè)試的主要目的在于。15．面向?qū)ο箝_(kāi)發(fā)方法是研究面向?qū)ο蠓治龊偷姆椒?。二、單?xiàng)選擇題(本大題共15小題，每小題2分，共30分)在每小題列出的四個(gè)備選項(xiàng)中只有一個(gè)是符合題目要求的，請(qǐng)將其代碼填寫(xiě)在題后的括號(hào)內(nèi)。錯(cuò)選、多選或未選均不得分。16．下列程序段的時(shí)間復(fù)雜度為for(inti=0；i<m；i++)for(intj=0；j<n；j++)mat[i][j]=i*j；【】A．0(mn)B．D(m2)C．0(n17．線性表采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)時(shí)，表中各個(gè)數(shù)據(jù)元素的存儲(chǔ)地址【】A．必須是連續(xù)的B．部分地址必須是連續(xù)的C．一定是不連續(xù)的D．連續(xù)與否均可以18．棧和隊(duì)列作為特殊的線性表，它們的共同點(diǎn)是【】A．都是先進(jìn)后出B．都是先進(jìn)先出C．無(wú)共同點(diǎn)D．僅允許在端點(diǎn)處插入和刪除元素19．若二叉樹(shù)的前序遍歷和后序遍歷序列正好相反，則該二叉樹(shù)必定是【】A．空或者只有一個(gè)結(jié)點(diǎn)B．高度等于其結(jié)點(diǎn)數(shù)C．任一結(jié)點(diǎn)無(wú)左孩子D．任一結(jié)點(diǎn)無(wú)右孩子20．下列敘述不正確的是【】A．直接插入排序是穩(wěn)定的排序法B．冒泡排序是穩(wěn)定的排序法C．直接插入排序的時(shí)間復(fù)雜度為0(n)D．簡(jiǎn)單選擇排序是不穩(wěn)定的排序法21．順序逐個(gè)檢索一個(gè)具有n個(gè)數(shù)據(jù)元素的線性表，其時(shí)間復(fù)雜度為【】A．O(n)B．O(log2n)C．D(n222．用冒泡排序法對(duì)ll個(gè)數(shù)據(jù)元素進(jìn)行排序，第一趟共比較多少對(duì)關(guān)鍵字【】A．1B．2C．n-lD．n23．下列敘述不正確的是【】A．直接插入排序僅需1個(gè)輔助空間B．冒泡排序僅需1個(gè)輔助空間C．希爾排序僅需1個(gè)輔助空間D．簡(jiǎn)單選擇排序至少需要2個(gè)輔助空間24．唯一標(biāo)志進(jìn)程存在的數(shù)據(jù)結(jié)構(gòu)是【】A．JCBB．PCBC．TCBD．DCB25．下列關(guān)于進(jìn)程基本狀態(tài)轉(zhuǎn)化敘述中不正確的是【】A．就緒→運(yùn)行B．運(yùn)行→就緒C．阻塞→就緒D．就緒→阻塞26．用來(lái)描述概念模型信息結(jié)構(gòu)的最常用的方法是【】A．語(yǔ)義對(duì)象模型B．E—R模型C．關(guān)系模型D．層次模型27．在對(duì)軟件分類中，下列不屬于應(yīng)用領(lǐng)域型軟件的是【】A．系統(tǒng)軟件B．嵌入式軟件C．大型軟件D．商業(yè)軟件28．面向?qū)ο蠓椒ㄗ钤绯霈F(xiàn)在哪個(gè)語(yǔ)言中【】A．SmallTlalk80B．Simula67C．C++D．Pascal29．軟件開(kāi)發(fā)周期中對(duì)軟件質(zhì)量保證工作最關(guān)鍵的環(huán)節(jié)是【】A．軟件開(kāi)發(fā)B．需求分析C．軟件維護(hù)D．軟件測(cè)試30.下列對(duì)面向?qū)ο笾械念愃鞯谋硎霾徽_的是【】A.類代表抽象的事物B．類具有封裝性C.對(duì)象是類的實(shí)例D．對(duì)象是類的模版三、簡(jiǎn)答題(本大題共5小題，每小題4分，共20分)31.簡(jiǎn)述算法的主要特征。32.簡(jiǎn)述先序遍歷二叉樹(shù)的基本過(guò)程。33.對(duì)于關(guān)鍵字序列(55，24，12，30，60，58，70)，從空樹(shù)開(kāi)始，請(qǐng)畫(huà)出其二叉排序樹(shù)。34.簡(jiǎn)述數(shù)據(jù)庫(kù)中常用的組織層模型的主要類型及其數(shù)據(jù)組織形式。35.簡(jiǎn)述軟件危機(jī)的主要表現(xiàn)。四、應(yīng)用題(本大題共2小題，每小題10分，共20分)37．有一個(gè)學(xué)生成績(jī)處理系統(tǒng)，功能要求如卜：1．基本信息管理：導(dǎo)入教務(wù)處學(xué)生選課信息，提取教師、課程、學(xué)生三者的對(duì)應(yīng)關(guān)系；2．成績(jī)錄入：分配人員錄入成績(jī)，做好錄入日志登記，進(jìn)度控制；3．成績(jī)查詢：學(xué)生只能查自己的成績(jī)；教師可以查所授班級(jí)的成績(jī)；教學(xué)領(lǐng)導(dǎo)可以獲得全部成績(jī)的各種統(tǒng)計(jì)報(bào)表、可以查詢每個(gè)班級(jí)、每個(gè)教師的成績(jī)情況；4．成績(jī)處理：系統(tǒng)依據(jù)學(xué)生平時(shí)成績(jī)、期中成績(jī)和期末成績(jī)總和給出學(xué)生的最終成績(jī)；5．成績(jī)提交：依據(jù)教務(wù)處格式，將最終成績(jī)提交給教務(wù)處。根據(jù)要求畫(huà)出該系統(tǒng)的頂層數(shù)據(jù)流圖。

2012年4月高等教育自學(xué)考試福建省統(tǒng)一命題考試軟件技術(shù)基礎(chǔ)試題課程代碼：07186本試卷滿分100分，考試時(shí)間150分鐘?？忌痤}注意事項(xiàng)：本卷所有試卷必須在答題卡上作答。答在試卷和草稿紙上的無(wú)效。第一部分為選擇題。必須對(duì)應(yīng)試卷上的題號(hào)使用2B鉛筆將“答題卡”的相應(yīng)代碼涂黑。第二部分為非選擇題。必須注明大、小題號(hào)，使用0.5毫米黑色字跡簽字筆作答。合理安排答題空間，超出答題區(qū)域無(wú)效。第一部分選擇題一、單項(xiàng)選擇題(本大題共15小題，每小題2分，共30分)在每小題列出的四個(gè)備選項(xiàng)中只有一個(gè)是符合題目要求的，請(qǐng)將其選出并將“答題卡”的相應(yīng)代碼涂黑。未涂、錯(cuò)涂或多涂均無(wú)分。1．下列描述中不正確的是A．?dāng)?shù)據(jù)元素是數(shù)據(jù)的基本單位B．?dāng)?shù)據(jù)元素是數(shù)據(jù)不可分割的最小單位C．?dāng)?shù)據(jù)元素通常又稱為記錄D．?dāng)?shù)據(jù)元素通常作為一個(gè)整體進(jìn)行處理2．下列有關(guān)線性表的敘述中，正確的是A．同一線性表中的元素具有相同特性B．線性表中任一元素有且僅有一個(gè)直接后繼C．線性表中任一元素有且僅有一個(gè)直接前趨D．線性表至少包含一個(gè)元素3．一個(gè)隊(duì)列的入列序列是L，M，N，O，則隊(duì)列的輸出序列是A．O，N，M，LB．L，M，N，OC．L，O，N，MD．N，M，O，L4．假設(shè)以行優(yōu)先存儲(chǔ)的二維數(shù)組A[1．．100，1．．200]，設(shè)每個(gè)數(shù)據(jù)元素占2個(gè)存儲(chǔ)單元，基地址為100，則LOC(A[6，6])=A．1005B．1105C．2100D．21105．含有3個(gè)2度結(jié)點(diǎn)和4個(gè)葉結(jié)點(diǎn)的共7個(gè)結(jié)點(diǎn)的二叉樹(shù)含1度結(jié)點(diǎn)A．0個(gè)B．1個(gè)C．2個(gè)D．3個(gè)6．對(duì)于n個(gè)記錄的序列最多經(jīng)過(guò)幾趟冒泡排序就可以變成按關(guān)鍵字有序的順序序列?A．n/2B．n-lC．nD．n+17．下列對(duì)冒泡排序法敘述正確的是A．外部排序法B．不穩(wěn)定排序法C．穩(wěn)定排序法D．時(shí)間復(fù)雜度為O(n)8．設(shè)一個(gè)順序表有128個(gè)元素，用折半查找法進(jìn)行查找時(shí)，最大比較次數(shù)是A．7B．8C．16D．329．進(jìn)程作為操作系統(tǒng)的一種重要實(shí)體具有較多特性，但不包括A．并發(fā)性B．動(dòng)態(tài)性C．獨(dú)立性D．虛擬性10．一個(gè)剛剛創(chuàng)建的進(jìn)程，通常呈現(xiàn)的基本狀態(tài)是A．就緒態(tài)B．運(yùn)行態(tài)C．阻塞態(tài)D．掛起態(tài)11．下列不屬于數(shù)據(jù)庫(kù)常用的組織層模型的是A．關(guān)系模型B．信息模型C．網(wǎng)狀模型D．層次模型12．下列類型表體現(xiàn)了關(guān)系類型中的虛表概念的是A．基本關(guān)系B．基本表C．查詢表D．視圖表13．結(jié)構(gòu)化程序設(shè)計(jì)的基本要點(diǎn)不包括A．使用goto語(yǔ)言實(shí)現(xiàn)靈活跳轉(zhuǎn)B．單一入口，單一出口C．自頂向下，逐步求精D．主程序員組14．檢查軟件產(chǎn)品是否符合用戶需求的測(cè)試過(guò)程稱為A．單元測(cè)試B．集成測(cè)試C．系統(tǒng)測(cè)試D．確認(rèn)測(cè)試15．面向?qū)ο笾袠?gòu)成對(duì)象的基本要素是A．實(shí)體和服務(wù)B．屬性和服務(wù)C．實(shí)體和關(guān)系D．實(shí)體和屬性第二部分非選擇題二、填空題(本大題共15小題，每小題2分，共30分)請(qǐng)?jiān)诖痤}卡上作答。16．一個(gè)算法的執(zhí)行次數(shù)表示為(5n2+2nlog2n+4n)/(4n)，則其時(shí)間復(fù)雜度表示為_(kāi)_________。17．?dāng)?shù)據(jù)的存儲(chǔ)結(jié)構(gòu)包括數(shù)據(jù)元素的表示和__________的表示。18．線性表L=(α1,α2，…,αn)采用順序存儲(chǔ)結(jié)構(gòu)，假定在每個(gè)可能的位置上插入元素的概率都相等，則插入一個(gè)新元素平均需要移動(dòng)的元素個(gè)數(shù)是__________。19．有三個(gè)結(jié)點(diǎn)的二叉樹(shù)，最多有__________種形狀。20．樹(shù)中結(jié)點(diǎn)的__________稱為樹(shù)的深度或高度。21．由判定樹(shù)可知，折半查找法查找結(jié)點(diǎn)D的過(guò)程恰好走了一條從__________到結(jié)點(diǎn)D的路徑。22．二叉排序樹(shù)中任意一個(gè)結(jié)點(diǎn)的關(guān)鍵字大于其__________中的所有結(jié)點(diǎn)的關(guān)鍵字。23．在直接插入排序中，已經(jīng)進(jìn)行到要將第i個(gè)記錄插入時(shí)，此時(shí)前i-1個(gè)記錄必定是__________的。24．操作系統(tǒng)的虛擬性指的是使用虛擬技術(shù)把__________映射成虛擬的邏輯設(shè)備。25．為實(shí)現(xiàn)設(shè)備無(wú)關(guān)性，操作系統(tǒng)采用了分層技術(shù)，即將設(shè)備管理軟件分成上層__________和下層設(shè)備驅(qū)動(dòng)程序。26．E-R方法中主要有實(shí)體、屬性和__________三個(gè)概念。27．軟件的概念可以簡(jiǎn)單地概括為軟件=程序+__________+文檔。28．需求分析的基本任務(wù)是確定系統(tǒng)的目標(biāo)，即回答系統(tǒng)必須“__________”的問(wèn)題。29．在軟件的詳細(xì)設(shè)計(jì)中使用最廣泛的一個(gè)描述工具是__________。30．面向?qū)ο笾械姆庋b在信息處理領(lǐng)域可以說(shuō)是一種很好的__________技術(shù)。三、簡(jiǎn)答題(本大題共5小題，每小題4分，共20分)請(qǐng)?jiān)诖痤}卡上作答。31．簡(jiǎn)述棧、隊(duì)列和串的共同點(diǎn)及它們的特殊性。32．簡(jiǎn)述數(shù)據(jù)元素之間的四種基本關(guān)系及基本結(jié)構(gòu)。33．簡(jiǎn)述面向?qū)ο蠹夹g(shù)的基本觀點(diǎn)。34．簡(jiǎn)述二叉排序樹(shù)插入的基本過(guò)程。35．簡(jiǎn)述軟件與硬件的本質(zhì)上的區(qū)別以及軟件的主要特點(diǎn)表現(xiàn)。四、綜合應(yīng)用題(本大題共2小題，每小題10分，共20分)請(qǐng)?jiān)诖痤}卡上作答。36．對(duì)于有序表(2,4,6,8,15,20,40,80,100,120,150)進(jìn)行折半查找，完成如下問(wèn)題：(1)畫(huà)出對(duì)應(yīng)的二叉判定樹(shù)；(2)若查找元素80，則需要依次與哪些元素進(jìn)行比較?按順序給出這些元素；(3)計(jì)算查找成功所需的平均比較次數(shù)。給出求長(zhǎng)度為n的一維數(shù)值型數(shù)組平均值的PAD圖。

2013年4月高等教育自學(xué)考試福建省統(tǒng)一命題考試軟件技術(shù)基礎(chǔ)試題課程代碼：07186本試卷滿分100分，考試時(shí)間150分鐘考生答題注意事項(xiàng)：本卷所有試卷必須在答題卡上作答。答在試卷和草稿紙上的無(wú)效。第一部分為選擇題。必須對(duì)應(yīng)試卷上的題號(hào)使用2B鉛筆將“答題卡”的相應(yīng)代碼涂黑。第二部分為非選擇題。必須注明大、小題號(hào)，使用0.5毫米黑色字跡筆作答。合理安排答題空間，超出答題區(qū)域無(wú)效。第一部分選擇題一、單項(xiàng)選擇題(本大題共15小題，每小題2分，共30分)在每小題列出的四個(gè)備選項(xiàng)中只有一個(gè)是符合題目要求的，請(qǐng)將其選出并將“答題卡”的相應(yīng)代碼涂黑。未涂、錯(cuò)涂或多涂均無(wú)分。1．在數(shù)據(jù)結(jié)構(gòu)中，若數(shù)據(jù)元素之間存在一個(gè)對(duì)多個(gè)的關(guān)系，則該結(jié)構(gòu)是A．集合B．線性結(jié)構(gòu)C．圖狀結(jié)構(gòu)D．樹(shù)狀結(jié)構(gòu)2．在一個(gè)單鏈表中，若節(jié)點(diǎn)P不是尾結(jié)點(diǎn)，則在P之后插入S結(jié)點(diǎn)，需執(zhí)行A．S－>next=p;p－>next=s；B．S－>next=P－>next；p－>next=s；C．S－>next=P－>next；p=s；D．P－>next=s；s－>next=p；3．鏈?zhǔn)綏Ｅc順序棧相比，一個(gè)比較明顯的優(yōu)點(diǎn)是A．插入操作更方便B.一般不會(huì)出現(xiàn)棧滿的情況C．不會(huì)出現(xiàn)?？盏那闆rD．刪除操作更方便4．高度為h的二叉樹(shù)上只有度為0和度為2的結(jié)點(diǎn)，則此類二叉樹(shù)中所包含的結(jié)點(diǎn)數(shù)至少為A．h+1B．2h—lC．2hD．2h+15．采用順序查找法查找長(zhǎng)度為n的線性表，則成功查找時(shí)每個(gè)元素的平均查找長(zhǎng)度為A．nB．n／2C．(n+1)／2D．(n-1)／26．穩(wěn)定的排序方法是指在排序中，關(guān)鍵字值相等的不同記錄在排序前后的相對(duì)次序A．保持不變B．保持相反C．不定D．正好相鄰7．希爾排序法的時(shí)間復(fù)雜度通常表示為A．o(n)B．o(nlogn)C．o(n2logn)D．o(n2)8．操作系統(tǒng)作為最底層的系統(tǒng)軟件，它的主要功能是資源管理和提供A．軟件開(kāi)發(fā)B．硬件維護(hù)C．系統(tǒng)維護(hù)D．用戶接口9．操作系統(tǒng)中文件的物理結(jié)構(gòu)不包括A．連續(xù)結(jié)構(gòu)B．記錄式結(jié)構(gòu)C．串聯(lián)結(jié)構(gòu)D．索引結(jié)構(gòu)10．E-R圖中用來(lái)表示實(shí)體的圖形是A．菱形B．矩形C．橢圓形D．圓形11．關(guān)系數(shù)據(jù)庫(kù)的標(biāo)準(zhǔn)語(yǔ)言是A．HTMLB．SQLC．DCLD．DDL12．軟件危機(jī)的主要表現(xiàn)不包括A．開(kāi)發(fā)軟件的成本和進(jìn)度難以控制B．軟件的可維護(hù)性差C．軟件產(chǎn)品的質(zhì)量不可靠D．軟件的可移植性差13．結(jié)構(gòu)化分析方法是一種A．面向數(shù)據(jù)流的分析方法B．面向過(guò)程的分析方法C．面向?qū)ο蟮姆治龇椒―．系統(tǒng)分析方法14．在軟件設(shè)計(jì)階段應(yīng)提供的規(guī)格文檔是A．軟件需求規(guī)格說(shuō)明書(shū)B(niǎo)．概要及詳細(xì)設(shè)計(jì)規(guī)格說(shuō)明書(shū)C．?dāng)?shù)據(jù)字典及流程圖D．源程序以及源程序的說(shuō)明書(shū)15．UML動(dòng)態(tài)建模采用的狀態(tài)圖中，終態(tài)對(duì)應(yīng)的圖形是A．實(shí)心圓B．空心圓C．帶邊界的實(shí)心圓D．圓角框．第二部分非選擇題二、填空題(本大題共15小題，每小題2分，共30分)請(qǐng)?jiān)诖痤}卡上作答。16．設(shè)有一個(gè)遞歸算法如下intfa(intn)／／n大于等于0{if(n(=0)return1；elsereturnn*fa(n-1);}則計(jì)算fa(n)需要調(diào)用該函數(shù)的次數(shù)為次。17．鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中的結(jié)點(diǎn)包含數(shù)據(jù)域和域。18．棧的特點(diǎn)是后進(jìn)先出，因此棧只能在插入和刪除元素。19．求串T在主串S中首次出現(xiàn)的位置的操作稱為。20．已知某二叉樹(shù)的后序遍歷序列是dabec，中序遍歷序列是debac，則前序遍歷序列是。21．樹(shù)中結(jié)點(diǎn)所擁有的稱為結(jié)點(diǎn)的度。22．分塊查找中的索引表一定是按照有序的。23．操作系統(tǒng)充當(dāng)?shù)慕巧饕ㄓ脩艚涌?、、?yīng)用軟件的開(kāi)發(fā)平臺(tái)和運(yùn)行環(huán)境。24．從微觀角度講，操作系統(tǒng)中的并發(fā)性指的是多道程序在極短的時(shí)間間隔內(nèi)執(zhí)行。25．如果進(jìn)程只需要獲得CPU就可以進(jìn)行運(yùn)行態(tài)，則表明該進(jìn)程處于態(tài)。26．?dāng)?shù)據(jù)模型如果是面向用戶的，則稱該模型為。27．軟件生存周期模型是對(duì)軟件的建模。28．結(jié)構(gòu)化分析方法總的指導(dǎo)思想是和逐步求精。29．白盒測(cè)試主要針對(duì)程序邏輯，而黑盒測(cè)試主要針對(duì)。30．UML語(yǔ)言中的用例圖包括的模型元素有用例和。三、簡(jiǎn)答題(本大題共5小題，每小題4分，共20分)請(qǐng)?jiān)诖痤}卡上作答。32．對(duì)右圖所示的二叉樹(shù)，給出先序、中序、后序遍歷的結(jié)果序列。33．簡(jiǎn)述操作系統(tǒng)如何實(shí)現(xiàn)設(shè)備無(wú)關(guān)性?34．軟件工程是一門(mén)實(shí)踐學(xué)科，請(qǐng)寫(xiě)出它要達(dá)到的主要目標(biāo)。35．簡(jiǎn)述軟件生存周期模型中的瀑布模型的主要特點(diǎn)。

2014年4月高等教育自學(xué)考試福建省統(tǒng)一命題考試軟件技術(shù)基礎(chǔ)試卷（課程代碼07186）本試卷滿分100分，考試時(shí)間150分鐘?？忌痤}注意事項(xiàng)：1．本卷所有試題必須在答題卡上作答。答在試卷上無(wú)效，試卷空白處和背面均可作草稿紙。2．第一部分為選擇題。必須對(duì)應(yīng)試卷上的題號(hào)使用2B鉛筆將“答題卡”的相應(yīng)代碼涂黑。3．第二部分為非選擇題。必須注明大、小題號(hào)，使用0.5毫米黑色字跡簽字筆作答。4．合理安排答題空間，超出答題區(qū)域無(wú)效。第一部分選擇題一、單項(xiàng)選擇題（本大題共15小題，每小題2分，共30分）在每小題列出的四個(gè)備選項(xiàng)中只有一個(gè)是符合題目要求的，請(qǐng)將其選出并將“答題卡”的相應(yīng)代碼涂黑。未涂、錯(cuò)涂或多涂均無(wú)分。1．算法指的是A．計(jì)算機(jī)程序B．解決問(wèn)題的計(jì)算方法C．?dāng)?shù)值方法D．解決問(wèn)題的有限運(yùn)算序列2．線性表若采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)時(shí)，要求內(nèi)存中可用存儲(chǔ)單元的地址A．必須連續(xù)B．部分地址必須連續(xù)C．一定是不連續(xù)的D．連續(xù)與否都可以3．判定一個(gè)順序棧stack（棧中元素個(gè)數(shù)最多為N）滿的條件是A.Stack→top!=0B.Stack→top==0C.Stack→top!=ND.Stack→top==N4。按照二叉樹(shù)的定義，具有3個(gè)結(jié)點(diǎn)的二叉樹(shù)共有幾種？A．3B．4C．5D．65．在有序表A[O10]中折半查找每個(gè)元素（等概率查找），則平均查找長(zhǎng)度為A．2B．3C．4D．5.56．排序是根據(jù)下列哪個(gè)選項(xiàng)值的大小重新安排各數(shù)據(jù)元素的順序？A．記錄B．關(guān)鍵字C．元素D．結(jié)點(diǎn)7．直接插入排序法的時(shí)間復(fù)雜度是A.o（n）B.o(nlogn)C.o(n2logn)D.o(n2)8．操作系統(tǒng)的特性之一是并發(fā)性，下列理解不正確的是A．并發(fā)指n個(gè)(n>1)事件在同一時(shí)間間隔內(nèi)發(fā)生B．多道程序在同一時(shí)間間隔內(nèi)同時(shí)執(zhí)行C．多道程序在極短的時(shí)間間隔內(nèi)交替執(zhí)行D．多道程序在同一時(shí)間點(diǎn)同時(shí)執(zhí)行9．文件的邏輯結(jié)構(gòu)主要采用字符流文件和A．連續(xù)文件B．記錄式文件C．串聯(lián)文件D．索引文件10.E-R圖中用來(lái)表示屬性的圖形是A．菱形B．矩形C．橢圓形D．圓形11.關(guān)系完整性中下列哪項(xiàng)是關(guān)系的不變性？A．實(shí)體完整性B．參照完整性和用戶自定義完整性c．實(shí)體完整性和用戶自定義完整性D．實(shí)體完整性和參照完整性12.系統(tǒng)設(shè)計(jì)人員依據(jù)軟件需求規(guī)格說(shuō)明書(shū)確定軟件的體系結(jié)構(gòu)，進(jìn)而確定每個(gè)模塊的實(shí)現(xiàn)算法等，這項(xiàng)工作在下列的哪個(gè)階段完成？A．制定計(jì)劃B．編碼實(shí)現(xiàn)C．測(cè)試階段D．軟件設(shè)計(jì)13.軟件生存周期中時(shí)間最長(zhǎng)的階段是A．需求分析B．軟件設(shè)計(jì)C．編碼實(shí)現(xiàn)D．軟件維護(hù)14.PAD圖（ProblemAnalysisDiagram，問(wèn)題分析圖）主要用于哪個(gè)階段？A．概要設(shè)計(jì)B．詳細(xì)設(shè)計(jì)C．編碼實(shí)現(xiàn)D．軟件測(cè)試15.下列對(duì)UML的特點(diǎn)表述，不正確的是A．用例圖來(lái)自O(shè)OSEB．類圖來(lái)自O(shè)MT方法C．構(gòu)件圖和配置圖來(lái)自Booch的模塊圖和過(guò)程圖D．UML是一種面向?qū)ο蠓椒ǖ诙糠址沁x擇題二、填空題（本大題共15小題，每小題2分，共30分）請(qǐng)?jiān)诖痤}卡上作答。16.算法：for(i=O;i<n;i++)x=x+sqr(i);的時(shí)間復(fù)雜度的數(shù)量級(jí)表示為。17.鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中數(shù)據(jù)元素之間的邏輯關(guān)系是通過(guò)結(jié)點(diǎn)中的來(lái)指示的。18.鏈棧和順序棧相比，在存儲(chǔ)元素方面最大的區(qū)別是鏈棧沒(méi)有問(wèn)題。19.串中任意個(gè)連續(xù)的字符組成的子序列稱為該串的。20.若結(jié)點(diǎn)A有三個(gè)兄弟（不含A），而結(jié)點(diǎn)B是A的雙親結(jié)點(diǎn)，則結(jié)點(diǎn)B的度是。21．樹(shù)的結(jié)點(diǎn)包含一個(gè)數(shù)據(jù)元素及若干指向其的分支。22.在分塊查找法中，應(yīng)根據(jù)待查值首先查找，然后再查找相應(yīng)的子塊。23.操作系統(tǒng)區(qū)別于其他軟件的基本特征有共享、虛擬和。24.分時(shí)操作系統(tǒng)是把一個(gè)時(shí)間段分成若干個(gè)，使多個(gè)用戶程序輪流使用CPU并運(yùn)行。25.操作系統(tǒng)存儲(chǔ)管理的主要方式包括分區(qū)式、分段式、段頁(yè)式和一。26.數(shù)據(jù)模型如果是面向計(jì)算機(jī)的，則稱該模型為。27.結(jié)構(gòu)化方法的基本要點(diǎn)包括自頂向下、逐步求精和。28.耦合性是對(duì)模塊之間互相連接的的度量。29.構(gòu)成對(duì)象的兩個(gè)基本要素是屬性和。30.在UML語(yǔ)言中，類圖顯示了一組類以及類之間的關(guān)系，圖中采用表示類。三、簡(jiǎn)答題（本大題共5小題，每小題4分，共20分）請(qǐng)?jiān)诖痤}卡上作答。 2015年4月高等教育自學(xué)考試福建省統(tǒng)一命題考試軟件技術(shù)基礎(chǔ)試卷(課程代碼07186)本試卷滿分100分，考試時(shí)間l50分鐘。考生答題注意事項(xiàng)：1．本卷所有試題必須在答題卡上作答。答在試卷上無(wú)效，試卷空白處和背面均可作草稿紙。2．第一部分為選擇題。必須對(duì)應(yīng)試卷上的題號(hào)使用2B鉛筆將“答題卡”的相應(yīng)代碼涂黑。3．第二部分為非選擇題。必須注明大、小題號(hào)，使用0．5毫米黑色字跡簽字筆作答。4．合理安排答題空間，超出答題區(qū)域無(wú)效。第一部分選擇題一、單項(xiàng)選擇題(本大題共l5小題。每小題2分，共30分)在每小題列出的四個(gè)備選項(xiàng)中只有一個(gè)是符合題目要求的，請(qǐng)將其選出并將“答題卡”的相應(yīng)代碼涂黑。未涂、錯(cuò)涂或多涂均無(wú)分。1．算法分析的目的主要是A．找出數(shù)據(jù)結(jié)構(gòu)的合理性B．研究算法中的輸入和輸出的關(guān)系C．分析算法的易懂性和文檔性D．分析算法的效率以求改進(jìn)2．在單鏈表中，若刪除結(jié)點(diǎn)P的后續(xù)結(jié)點(diǎn)，則執(zhí)行3．設(shè)某個(gè)順序棧S，元素A，B，C，D，E，F(xiàn)，G依次進(jìn)棧，如果7個(gè)元素的出棧順序?yàn)镃，D，E，G，F(xiàn)，B，A，則該順序棧的容量最小為A．2B．3C.4D.74．如果某二叉樹(shù)的前序?yàn)閍bcde，中序?yàn)閏dbea，那么該二叉樹(shù)的后序?yàn)锳．cdebaB．edcbaC．dcebaD．dcbae5．下列對(duì)直接插入排序法描述正確的是A．是穩(wěn)定排序法B．是不穩(wěn)定排序法C．是外部排序法D．時(shí)間復(fù)雜度為O(n)6．內(nèi)部排序是指在排序的整個(gè)過(guò)程中，全部待排序的數(shù)據(jù)元素都位于計(jì)算機(jī)的A．內(nèi)存儲(chǔ)器B．外存儲(chǔ)器C．內(nèi)存儲(chǔ)器和外存儲(chǔ)器D．寄存器7．簡(jiǎn)單選擇排序法的平均時(shí)間復(fù)雜度是A．o(n)B．o(n2)C．o(nlogn)D．o(n2logn)8．操作系統(tǒng)區(qū)別于其它軟件的基本特征中不包括A．并發(fā)B．共享C．管理D．虛擬9．進(jìn)程的狀態(tài)中不包括A．結(jié)束狀態(tài)B．就緒狀態(tài)C．阻塞狀態(tài)D．運(yùn)行狀態(tài)10．E—R圖中用來(lái)表示聯(lián)系的圖形是A．菱形B．矩形C．橢圓形D．圓形11．若一個(gè)工廠有若干職工，而每個(gè)職工只在一個(gè)工廠工作，則工廠和職工之間的聯(lián)系是A．一對(duì)一B．一對(duì)多C．多對(duì)多D．不確定12．瀑布模型的主要特點(diǎn)是A．軟件開(kāi)發(fā)過(guò)程被嚴(yán)格的劃分為一系列有序的活動(dòng)B．提供了有效的管理模式C．軟件開(kāi)發(fā)過(guò)程分解為幾個(gè)獨(dú)立階段D．缺乏靈活性13．結(jié)構(gòu)化程序設(shè)計(jì)的一種基本方法是A．自頂向下逐步求精B．逐步迭代法C．逐步排除法D．遞歸法14．在數(shù)據(jù)流圖中，圓形代表A．?dāng)?shù)據(jù)源點(diǎn)B．?dāng)?shù)據(jù)終點(diǎn)C．?dāng)?shù)據(jù)加工D．?dāng)?shù)據(jù)流15．UML的模型圖中有一大類是屬于靜態(tài)圖，下列不屬于靜態(tài)圖的是A．類圖B．對(duì)象圖C．包圖D．用例圖第二部分非選擇題二、填空題(本大題共l5小題，每小題2分，共30分)請(qǐng)?jiān)诖痤}卡上作答。16．通常根據(jù)算法中描述核心問(wèn)題的______重復(fù)執(zhí)行的次數(shù)來(lái)作為算法的時(shí)間量度。17．非空的線性表(a1，a2，…，an-1，an)，元素ai(1≤i<n)的直接后繼是______。18．對(duì)于鏈棧stack而言，判定?？盏臈l件是______。19．一棵含有n個(gè)結(jié)點(diǎn)的k叉樹(shù)(0<k<n)，可能達(dá)到的最小深度是______。20．在二叉樹(shù)的第k層上至多有______個(gè)結(jié)點(diǎn)。21．假設(shè)在有序表A[0…l9]中進(jìn)行折半查找，比較2次即查找成功的結(jié)點(diǎn)為_(kāi)_____。22．二叉排序樹(shù)查找成功的平均查找長(zhǎng)度和二叉排序樹(shù)的形態(tài)及______有關(guān)。23．操作系統(tǒng)是用戶和計(jì)算機(jī)硬件之間的______。24．所謂通用操作系統(tǒng)指的是一個(gè)操作系統(tǒng)兼顧分時(shí)、實(shí)時(shí)和______的全部或兩種功能。25．操作系統(tǒng)存儲(chǔ)管理中的分頁(yè)存儲(chǔ)的管理方法是將內(nèi)存空間按照固定大小劃分為若干大小相等的頁(yè)面，這些頁(yè)面稱為_(kāi)_____。26．?dāng)?shù)據(jù)層模型描述了數(shù)據(jù)的______，故又稱為組織層模型。27．結(jié)構(gòu)化設(shè)計(jì)中采用模塊化設(shè)計(jì)的主要目的是降低程序的______，使程序設(shè)計(jì)、調(diào)試和維護(hù)操作更簡(jiǎn)單。28．軟件模塊之間耦合性越強(qiáng)則模塊的______越差。29．類是具有相同屬性和服務(wù)的一組______的集合。30．UML中的狀態(tài)圖用來(lái)描述一個(gè)實(shí)體基于______的動(dòng)態(tài)行為。三、簡(jiǎn)答題(本大題共5小題，每小題4分，共20分)請(qǐng)?jiān)诖痤}卡上作答。31．#defineNl00typedefstruct{indata[N]；intlens；}QList；請(qǐng)補(bǔ)充完整關(guān)于順序表中查找元素X的操作，若找到則返回基于下標(biāo)0開(kāi)始的位置，否則返回-l。intfind(QListL，intX){intj=0；while(①____________________________________){②____________________________________if(③____________________________________)elsereturn-1}}32．對(duì)關(guān)鍵字序列(27，21，66，15，45，36，27，10)采用簡(jiǎn)單選擇排序，給出第2，4，5，6四趟的排序結(jié)果。33．簡(jiǎn)述操作系統(tǒng)中分區(qū)存儲(chǔ)管理的基本思想和特點(diǎn)。34．簡(jiǎn)述軟件工程中軟件測(cè)試的基本任務(wù)。35．簡(jiǎn)述軟件開(kāi)發(fā)計(jì)劃的主要內(nèi)容。四、應(yīng)用題(共2題。每小題10分，共20分)請(qǐng)?jiān)诖痤}卡上作答。36．采用帶頭結(jié)點(diǎn)的鏈隊(duì)列實(shí)現(xiàn)對(duì)鍵盤(pán)上輸入的字符進(jìn)行隊(duì)列管理：1.如果輸入的是A…W，則從隊(duì)尾入隊(duì)2．如果輸入的是Y，則隊(duì)頭元素出隊(duì)3．如果輸入的是Z，則顯示隊(duì)列中剩余元素，然后退出算法37．建立學(xué)生成績(jī)管理系統(tǒng)的用例模型。管理人員負(fù)責(zé)成績(jī)管理；學(xué)生查詢成績(jī)。成績(jī)管理包括：錄入成績(jī)，修改成績(jī)，給出成績(jī)單，學(xué)生信