青島理工大學(xué)軟件應(yīng)用基礎(chǔ)期末復(fù)習(xí)題及參考答案

一、選擇題1.下列正確的標識符是（）。A.-a1B.a[i]C.a2_iD.intt2.在帶有頭結(jié)點的單鏈表HL中，要向表頭插入一個由指針p指向的結(jié)點，則執(zhí)行()。A.p->next=HL->next;HL->next=p;B.p->next=HL;HL=p;C.p->next=HL;p=HL;D.HL=p;p->next=HL;3.以下哪一個不是棧的基本運算？（）A．從棧頂插入一個新元素B．從棧底刪除一個元素C．判斷一個棧是否為空D．讀取棧頂元素的值4.根據(jù)二叉樹的定義可知二叉樹共有（）種不同的形態(tài)。A.4 B.5 C.6 D.75.對一個算法的評價，不包括如下（）方面的內(nèi)容。A．健壯性和可讀性B．并行性C．正確性D．時空復(fù)雜度6.分別以下列序列構(gòu)造二叉排序樹，與用其它三個序列所構(gòu)造的結(jié)果不同的是（）。A.{100，80，90，60，120，110，130} B.{100，120，110，130，80，60，90}C.{100，60，80，90，120，110，130} D.{100，80，60，90，120，130，110}7.假設(shè)系統(tǒng)中所有進程是同時到達，則使進程平均周轉(zhuǎn)時間最短的是（）調(diào)度算法。A.先來先服務(wù) B.短進程優(yōu)先 C.時間片輪轉(zhuǎn) D.優(yōu)先級8.設(shè)屬性A是關(guān)系R的主屬性，則屬性A不能取空值（NULL）。這是（）A.實體完整性規(guī)則 B.參照完整性規(guī)則C.用戶定義完整性規(guī)則 D.域完整性規(guī)則9.關(guān)于DNS下列敘述錯誤的是（）。A.子節(jié)點能識別父節(jié)點的IP地址 B.DNS采用客戶服務(wù)器工作模式C.域名的命名原則是采用層次結(jié)構(gòu)的命名樹 D.域名不能反映計算機所在的物理地址10.以下哪個不是Spark的組件。A.SparkStreaming B.Mlib C.Graphx D.SparkR11.若有以下說明語句：structdate{intyear;intmonth;intday;}brithday;則下面的敘述不正確的是（）。A.struct是聲明結(jié)構(gòu)體類型時用的關(guān)鍵字B.structdate是用戶定義的結(jié)構(gòu)體類型名C.brithday是用戶定義的結(jié)構(gòu)體類型名D.year,day都是結(jié)構(gòu)體成員名12.下面關(guān)于線性表的敘述錯誤的是（）。A.線性表采用順序存儲必須占用一片連續(xù)的存儲空間 B.線性表采用鏈式存儲不必占用一片連續(xù)的存儲空間C.線性表采用鏈式存儲便于插入和刪除操作的實現(xiàn)13.設(shè)循環(huán)隊列中數(shù)組的下標范圍是0～m-1，其中頭尾指針分別是front和rear，則其元素個數(shù)是（）。A．rear-frontB．rear-front+1C．(rear-front)MODm+1D．(rear-front+m)MODm14.設(shè)n個元素進棧序列是1、2、3、…、n，其輸出序列是p1、p2、…、pn，若p1=3，則p2的值為（）。A.一定是2 B.一定是1 C.不可能是1 D.以上都不對15.設(shè)某棵二叉樹中只有度數(shù)為0和度數(shù)為2的結(jié)點且度數(shù)為0的結(jié)點數(shù)為n，則這棵二叉中共有（）個結(jié)點。A.2n B.n+l C.2n-1 D.2n+l16.設(shè)二叉排序樹中有n個結(jié)點，則在二叉排序樹的平均平均查找長度為（）。A.O(1) B.O(log2n) C.O(nlog2n) D.O(n2)17.下列關(guān)鍵字序列中（）是堆。A.16,72,31,23,94,53 B.94,23,31,72,16,53C.16,53,23,94，31,72 D.16,23,53,31,94,7218.某系統(tǒng)中有3個并發(fā)進程都需要4個同類資源，則該系統(tǒng)必然不會發(fā)生死鎖的最少資源是（）。A.9 B.10 C.11 D.1219.SELECT語句中，實現(xiàn)投影操作的是（）子句。A.Select B.from C.Where D.groupby20.路由選擇是（）的功能。A.網(wǎng)絡(luò)層 B.傳輸層 C.應(yīng)用層 D.數(shù)據(jù)鏈路層二、填空題1.軟件的發(fā)展歷史大致分為3個階段：軟件技術(shù)發(fā)展早期、_____________、______________。2.軟件定義：軟件=________+________+________。3.隊列的插入操作是在隊列的_______進行，刪除操作是在隊列的__________進行。4.用具有n個元素的一維數(shù)組存儲一個循環(huán)隊列，則其隊首指針總是指向隊首元素的___________，該循環(huán)隊列的最大長度為__________。5.在一個具有n個頂點的無向完全圖中，包含有________條邊，在一個具有n個頂點的有向完全圖中，包含有________條邊。6.二叉樹是指度為2的____________樹。一棵結(jié)點數(shù)為N的二叉樹，其所有結(jié)點的度的總和是____________。7.設(shè)要將序列（Q,H,C,Y,P,A,M,S,R,D,F,X）中的關(guān)鍵碼按字母序的升序重新排列，則：起泡排序一趟掃描的結(jié)果是____________。8.在哈希函數(shù)H（key）=key%p中，p值最好取____________。9.若對查找表只做“查詢某個特定的數(shù)據(jù)元素是否在查找表中”和“查詢某個特定的數(shù)據(jù)元素的各種屬性”操作，則稱此類查找表為___________。若在查找過程中同時插入查找表中不存在的數(shù)據(jù)元素，或者從查找表中刪除已存在的某個數(shù)據(jù)元素，則稱此類查找表為___________。10.在哈希存儲中，裝填因子的值越大，則___________；裝填因子的值越小，則___________。11.軟件定義：軟件=________+________+________。12.后綴算式923+-102/-的值為__________。中綴算式（3+4X）-2Y/3對應(yīng)的后綴算式為_______________________________。13.在一個具有n個頂點的無向完全圖中，包含有________條邊，在一個具有n個頂點的有向完全圖中，包含有________條邊。14.設(shè)要將序列（Q,H,C,Y,P,A,M,S,R,D,F,X）中的關(guān)鍵碼按字母序的升序重新排列，則：起泡排序一趟掃描的結(jié)果是。15.在哈希存儲中，裝填因子的值越大，則；裝填因子的值越小，則。16.實時系統(tǒng)的進程調(diào)度，通常采用_______________算法。17.設(shè)屬性A是關(guān)系R的主屬性，則屬性A不能取空值（NULL）。這是_________完整性規(guī)則。18.在實際使用的IP地址中，主機號不能為全“0”和全“1”，那么一個C類IP地址最多能容納的主機數(shù)目為__________。19.軟件工程學(xué)的三個要素是__________、__________和__________。20.HBase依靠_________保存底層數(shù)據(jù)。三、綜合應(yīng)用題1.軟件的生命周期包括哪些階段。2.設(shè)某商業(yè)集團關(guān)于商店銷售商品的數(shù)據(jù)庫中有三個基本表：商店SHOP（S#，SNAME，AREA，MGR_NAME）其屬性是商店編號，商店名稱，區(qū)域名，經(jīng)理姓名。銷售SALE（S#，G#，QUANTITY）其屬性是商店編號，商品編號，銷售數(shù)量。商品GOODS（G#，GNAME，PRICE）其屬性是商品編號，商品名稱，單價。（1）試寫出下列查詢的關(guān)系代數(shù)表達式、元組表達式和關(guān)系邏輯規(guī)則：檢索銷售“冰箱”的商店的編號和商店名稱。（2）試寫出上面第(1)問的SELECT語句表達形式。（3）試寫出下列操作的SQL語句：從SALE表中，把“開開商店”中銷售單價高于1000元的商品的銷售元組全部刪除。（4）寫一個斷言，要求區(qū)域名為“EAST”的商店里銷售商品的單價不能低于100元。（5）試寫出下列操作的SQL語句：統(tǒng)計區(qū)域名為“EAST”的所有商店銷售的每一種商品的總數(shù)量和總價值。要求顯示（G#，GNAME，SUM_QUANTITY，SUM_VALUE），其屬性為商品編號、商品名稱、銷售數(shù)量、銷售價值。3.在一個段式存儲管理系統(tǒng)中，其段表見表1。試求表2中的邏輯地址所對應(yīng)的物理地址。表1段表表2邏輯地址段號內(nèi)存起始地址段長02105001235020210090313505904193895段號段內(nèi)位移04301102500340041125324.給出關(guān)鍵字序列{4,5,1,2,8,6,7,3,10,9}的直接插入排序過程。5.設(shè)完全二叉樹的順序存儲結(jié)構(gòu)中存儲數(shù)據(jù)ABCDE，要求給出該二叉樹的鏈式存儲結(jié)構(gòu)并給出該二叉樹的前序、中序和后序遍歷序列。6.#include<stdio.h>main(){inti,a[10];for(i=9;i>=0;i--)a[i]=10-i;printf(“%d%d%d”,a[2],a[5],a[8]);}運行結(jié)果為：7.#include<stdio.h>main(){chars[]=”abcdefg”;char*p;p=s;printf(“ch=%c\n”,*(p+5));}運行結(jié)果為：8.設(shè)哈希（Hash）表的地址范圍為0～17，哈希函數(shù)為：H（K）＝KMOD16。K為關(guān)鍵字，用線性探測法再散列法處理沖突，輸入關(guān)鍵字序列：（10，24，32，17，31，30，46，47，40，63，49）造出Hash表，試回答下列問題：（1）畫出哈希表的示意圖；（2）若查找關(guān)鍵字63，需要依次與哪些關(guān)鍵字進行比較？（3）若查找關(guān)鍵字60，需要依次與哪些關(guān)鍵字比較？（4）假定每個關(guān)鍵字的查找概率相等，求查找成功時的平均查找長度。9.某博物館最多可容納500人同時參觀，有一個出入口，該出入口一次僅允許一個人通過。參觀者的活動描述如下：cobegin參觀者進程i:{...進門；...參觀；...出門； ...}coend請?zhí)砑拥谋匾男盘柫縋、V（或wait()、signal()）操作，以實現(xiàn)上述過程中的互斥與同步。要求寫出完整的過程，說明信號量的含義并賦初值。四、編程題1.試寫一個判別給定二叉樹是否為二叉排序樹的算法，設(shè)此二叉樹以二叉鏈表作存儲結(jié)構(gòu)。且樹中結(jié)點的關(guān)鍵字均不同。2.假設(shè)一個無向圖是非連通的，采用鄰接表作為存儲結(jié)構(gòu)，試設(shè)計一個算法，輸出圖中各連通分量的節(jié)點序列。3.已知在兩個鏈表A、B中均不存在相同元素，設(shè)計算法求出由僅在A中出現(xiàn)而不再B中出現(xiàn)的元素組成的鏈表?！盾浖夹g(shù)基礎(chǔ)》專業(yè)綜合課試卷B卷答案及評分標準選擇題（每題1分，共10分）1-5CABBB6-10CBAAD11-15.CADCC16-20.BDBAA填空題（每題1分，共10分）1.面向?qū)ο蠹夹g(shù)和結(jié)構(gòu)化程序發(fā)展時期軟件工程技術(shù)發(fā)展新時期2.程序數(shù)據(jù)文檔3.尾首4.前一個位置；n-15.n(n-1)/2n(n-1)6.有序n-17.HCQPAMSRDFXY8.小于等于表長的質(zhì)數(shù)（素數(shù)）9..靜態(tài)查找表動態(tài)查找表10.存取元素時發(fā)生沖突的可能性就越大存取元素時發(fā)生沖突的可能性就越小11..程序數(shù)據(jù)文檔12.-134X*+2Y*3/-13.n(n-1)/2n(n-1)14.HCQPAMSRDFXY15.存取元素時發(fā)生沖突的可能性就越大存取元素時發(fā)生沖突的可能性就越小16.搶占式的優(yōu)先級高者優(yōu)先17.實體18.25419..方法工具過程 20.HDFS綜合應(yīng)用題（每題10分，共60分）1.［答案］問題定義、可行性分析、概念設(shè)計、詳細設(shè)計、編碼、調(diào)試和測試、驗收與運行、維護升級到廢棄。2.［答案］(1)關(guān)系代數(shù)表達式：πS#，SNAME（σGNAME='冰箱'（SHOP?SALE?GOODS）） 元組表達式：{t|(u)(v)(w)(SHOP(u)∧SALE(v)∧GOODS(w)∧u[1]=v[1]∧v[2]=w[1]∧w[2]='冰箱'∧t[1]=u[1]∧t[2]=u[2])}關(guān)系邏輯規(guī)則：W(u1,u2)SHOP(u1,u2,u3,u4)∧SALE(u1,v2,v3)∧GOODS(v2,'冰箱',w3)(2)SELECT語句如下： SELECTA.S#，SNAME FROMSHOPA，SALEB，GOODSCWHEREA.S#=B.S#ANDB.G#=C.G#ANDGNAME='冰箱'；(3)DELETEFROMSALE WHERES#IN（SELECTS# FROMSHOP WHERESNAME='開開商店'） ANDG#IN（SELECTG#FROMGOODS WHEREPRICE>1000）；(4)CREATEASSERTIONASSE8CHECK （100<=ALL（SELECTPRICE FROMSHOPA，SALEB，GOODSC WHEREA.S#=B.S#ANDB.G#=C.G#ANDAREA='EAST'））； 或CREATEASSERTIONASSE8CHECK （NOTEXISTS（SELECT* FROMSHOPA，SALEB，GOODSC WHEREA.S#=B.S#ANDB.G#=C.G#ANDAREA='EAST'ANDPRICE<100））；(5)SELECTC.G#，GNAME，SUM（QUANTITY）ASSUM_QUANTITY，PRICE*SUM（QUANTITY）ASSUM_VALUE FROMSHOPA，SALEB，GOODSC WHEREA.S#=B.S#ANDB.G#=C.G#ANDAREA='EAST' GROUPBYC.G#，GNAME； （注：SELECT子句中的屬性C.G#，GNAME應(yīng)在分組子句中出現(xiàn)）3.［答案］由段表知，第0段內(nèi)存始址210，段長為500，故邏輯地址（0,430）是合法的，對應(yīng)的物理地址為210+430=640。由段表知，第1段內(nèi)存始址2350，段長為20，故邏輯地址（1,10）是合法的，對應(yīng)的物理地址為2350+10=2360。由段表知，第2段內(nèi)存始址100，段長為90，故邏輯地址（2,500）的段內(nèi)位移500已經(jīng)超過了段長，故為非法地址。由段表知，第3段內(nèi)存始址1350，段長為590，故邏輯地址（3,400）是合法的，對應(yīng)的物理地址為1350+400=1750。由段表知，第4段內(nèi)存始址1938，段長為95，故邏輯地址（4,112）的段內(nèi)位移112已經(jīng)超過了段長，故為非法地址。由段表知，不存在第5段，故邏輯地址（5,32）為非法地址。4.［答案］過程如下：第1趟：4,5,1,2,8,6,7,3,10,9第2趟：1,4,5,2,8,6,7,3,10,9第3趟：1,2,4,5,8,6,7,3,10,9第4趟：1,2,4,5,8,6,7,3,10,9第5趟：1,2,4,5,8,6,7,3,10,9第6趟：1,2,4,5,8,6,7,3,10,9第7趟：1,2,3,4,5,6,7,8,10,9第8趟：1,2,3,4,5,6,7,8,10,9第9趟：1,2,3,4,5,6,7,8,9,105.［答案］鏈式存儲結(jié)構(gòu)略，前序ABDEC，中序DBEAC，后序DEBCA。6.［答案］852[解析]首先定義整型變量i，整型數(shù)組a,a的長度為10，即a中包含10個整型元素（整型變量）執(zhí)行for循環(huán)語句初值i=9,使得循環(huán)條件i>=0成立，執(zhí)行循環(huán)體第1次循環(huán) 執(zhí)行a[i]=10-i等價于a[9]=10-9=1 計算表達式3，即i--，i為8，使得循環(huán)條件i>=0成立，繼續(xù)執(zhí)行循環(huán)體第2次循環(huán) 執(zhí)行a[i]=10-i等價于a[8]=10-8=2 計算表達式3，即i--，i為7，使得循環(huán)條件i>=0成立，繼續(xù)執(zhí)行循環(huán)體第3次循環(huán) 執(zhí)行a[i]=10-i等價于a[7]=10-7=3 計算表達式3，即i--，i為6，使得循環(huán)條件i>=0成立，繼續(xù)執(zhí)行循環(huán)體第4次循環(huán) 執(zhí)行a[i]=10-i等價于a[6]=10-6=4 計算表達式3，即i--，i為5，使得循環(huán)條件i>=0成立，繼續(xù)執(zhí)行循環(huán)體第5次循環(huán) 執(zhí)行a[i]=10-i等價于a[5]=10-5=5 計算表達式3，即i--，i為4，使得循環(huán)條件i>=0成立，繼續(xù)執(zhí)行循環(huán)體第6次循環(huán) 執(zhí)行a[i]=10-i等價于a[4]=10-4=6 計算表達式3，即i--，i為3，使得循環(huán)條件i>=0成立，繼續(xù)執(zhí)行循環(huán)體第7次循環(huán) 執(zhí)行a[i]=10-i等價于a[3]=10-3=7 計算表達式3，即i--，i為2，使得循環(huán)條件i>=0成立，繼續(xù)執(zhí)行循環(huán)體第8次循環(huán) 執(zhí)行a[i]=10-i等價于a[2]=10-2=8 計算表達式3，即i--，i為1，使得循環(huán)條件i>=0成立，繼續(xù)執(zhí)行循環(huán)體第9次循環(huán) 執(zhí)行a[i]=10-i等價于a[1]=10-1=9 計算表達式3，即i--，i為0，使得循環(huán)條件i>=0成立，繼續(xù)執(zhí)行循環(huán)體第10次循環(huán) 執(zhí)行a[i]=10-i等價于a[0]=10-0=10 計算表達式3，即i--，i為-1，使得循環(huán)條件i>=0不成立，跳出循環(huán)體7.［答案］ch=f[解析]首先定義一個字符型數(shù)組s，并用字符串a(chǎn)bcdefg對s進行初始化;然后定義一個字符型指針變量p;對p進行初始化，將數(shù)組s的地址賦給p。因此此時p中存放的數(shù)組s的首地址，即數(shù)組中第一個元素s[0]的地址。然后執(zhí)行printf語句，輸出表達式*(p+5)的值。p+5表示以p當前指向的位置起始，之后第5個元素的地址，即a[5]的地址。*(p+5)則表示該地址內(nèi)所存放的內(nèi)容，即a[5]的值f,因此輸出ch=f8.［答案］（1）畫表如下：0011223344556677889911011111211311411511611733211763492044010303146471111663311221111113333（2）查找63,首先要與H(63)=63%16=15號單元內(nèi)容比較，即63vs31,no;然后順移，與46,47,32,17,63相比，一共比較了6次。（3）查找60,首先要與H(60)=60%16=12號單元內(nèi)容比較，但因為12號單元為空（應(yīng)當有空標記），所以應(yīng)當只比較這一次即可。（4）ASL=1/11（6＋1*6+2＋3×3）＝23/11=2.099.［答案］出入口一次僅允許一個人通過，設(shè)置互斥信號量mutex，初值為1.博物館最多可同時容納500個人，故設(shè)置信號量empty，初值為500。Semaphoreempty=500;//博物館可容納的最多人數(shù)Semaphoremutex=1;//用于出入口資源的控制cobegin參觀者進程i:{...P(empty);//可容納人數(shù)減1P(mutex);//互斥使用門1進門;V(mutex);參觀;P(mutex);//互斥使用門出門；V(mutex);V(empty);//可容納人數(shù)增1...}coend編程題（每題10分，共20分）1.［答案］boolBisortTree(BiTreeT){//其中PRE為指向當前訪問結(jié)點的前驅(qū)的指針。intlast=0,flag=1;//last是全局變量，用來記錄前驅(qū)結(jié)點值，只要每個結(jié)點都比前驅(qū)大就行。BiTreepre;pre=null;Is_BSTree(T);}intIs_BSTree(BitreeT)//判斷二叉樹T是否二叉排序樹，是則返回1，否則返回0{if(T->lchild&&flag