(inplace)。所謂原地工作是指滿足有且只有一個(gè)根結(jié)點(diǎn)并且每一個(gè)結(jié)點(diǎn)最多有一個(gè)前件，也最多有一個(gè)后件的非空的數(shù)據(jù)結(jié)構(gòu)認(rèn)為是線性結(jié)構(gòu)，不滿足條件的結(jié)構(gòu)為非線性結(jié)構(gòu)?？諗?shù)據(jù)結(jié)構(gòu)可以是線性結(jié)構(gòu)也可以是非線性結(jié)構(gòu)。非空數(shù)據(jù)結(jié)構(gòu)可以沒有根結(jié)點(diǎn)，如非性線結(jié)構(gòu)“圖”就沒有根結(jié)點(diǎn)。

B=(D,R)，其中D={a,b,c,d,e,f}R={(f,a),(d,b),(e,d),(c,e),(a,abD（a,b）abbD={1,2,3,4,5}。下列數(shù)據(jù)結(jié)構(gòu)B=(D,R)中為非線性結(jié)構(gòu)的是R={(2,5),(5,4),(3,1),(4,3)R={(1,2),(2,3),(3,4),(4,5)R={(1,2),(2,3),(4,3),(3,5)R={(5,4),(4,3),(3,2),(2,1)Atop來指示棧頂?shù)奈恢?，用指針bottomtop動(dòng)態(tài)反應(yīng)了棧中元素的變化情況。在循環(huán)隊(duì)列中，隊(duì)頭指針和隊(duì)尾指針的動(dòng)態(tài)變化決定隊(duì)列的長度。鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，各數(shù)據(jù)結(jié)點(diǎn)的存儲(chǔ)序號是不連續(xù)的，并且各結(jié)點(diǎn)在存儲(chǔ)空間中的位置關(guān)系與邏輯關(guān)系

無法繼續(xù)入棧，topm+1。 B)19 0），經(jīng)過一系列正常的入棧與退棧操作后top=30，則空間（1:30）30 在棧底，1），入棧時(shí)棧頂指針是減操作top=m+1-xx=m-top+1。 入棧操作，top=0top0B) S(1:m)top=m+1。經(jīng)過一top m+1 50-20+1=31從外存的后備隊(duì)列中選取某些作業(yè)調(diào)入內(nèi)存分配資源并將新創(chuàng)建的進(jìn)程插入就緒隊(duì)列的過程。執(zhí)行程序中的過程調(diào)用一與隊(duì)列無關(guān)。執(zhí)行程序中的循環(huán)控制是指算法的基本控制結(jié)構(gòu)，包括對循環(huán)條件的判定與執(zhí)行循環(huán)體，與隊(duì)列無關(guān)。二叉樹是一個(gè)有限的結(jié)點(diǎn)集合，二叉樹的遍歷是指不重復(fù)地訪問二叉樹中的所有結(jié)點(diǎn)，與隊(duì)列無關(guān)。SQ，初始狀態(tài)均為空。首先依次將

A,B,C,D,E,FABCXYZ，退棧全部入隊(duì)后，隊(duì)列元素為在帶鏈的棧中，棧頂指針的動(dòng)態(tài)變化決定棧中元素的個(gè)數(shù)而在這種結(jié)構(gòu)中，各數(shù)據(jù)結(jié)點(diǎn)的存儲(chǔ)序號是不連續(xù)的，并且各結(jié)點(diǎn)在存儲(chǔ)空間中的位置關(guān)系與邏輯關(guān)系也不一致，故頭指針和尾指針或棧頂指針無法決定鏈表長度。循環(huán)隊(duì)列的存儲(chǔ)空間為Q(1:50)，初始狀態(tài)為1，或50且產(chǎn)生上溢錯(cuò) 列已滿(50循環(huán)隊(duì)列的存儲(chǔ)空間為Q(1:40)，初始狀態(tài)為 D)390front=rear=15時(shí)可知隊(duì)列空或者隊(duì)列滿，此后又退出一個(gè)元素，如果之前隊(duì)列為空，退出操作會(huì)產(chǎn)生錯(cuò)誤，隊(duì)列里有0個(gè)元素；如果退出之前隊(duì)列已滿(4039個(gè)元素。Q(1:50)，初始狀態(tài)為 2。 rear-front+mm-1<m，即mB)m-1C)11+1=2。

m-20為front=rear=m。經(jīng)過一系列正常的操作后，front=1， m-1-1=m-2。設(shè)循環(huán)隊(duì)列的存儲(chǔ)空間為Q(1:50)，初始狀態(tài)為front=rear=50。經(jīng)過一系列正常的操作后，front-1=rear。為了在該隊(duì)列中尋找值最大的元素，在最壞情況下需要的比較次數(shù)為48 -49-1=48。設(shè)循環(huán)隊(duì)列的存儲(chǔ)空間為Q(1:50)，初始狀態(tài)為front=rear=50。經(jīng)過一系列正常的操作后，front=rear-1。為了在該隊(duì)列中尋找值最大的元素，在最壞情況下需要的比較次數(shù)為 0。邏輯關(guān)系額外增加存儲(chǔ)空邏輯關(guān)系額外增加存儲(chǔ)空（1）存儲(chǔ)密度比順序表

top=-10或 A【解析】帶鏈棧就是沒有附加頭結(jié)點(diǎn)、運(yùn)算受限的單鏈表。棧頂指針就是鏈表的頭指針。如果棧底指針指向的存儲(chǔ)單元top=bottom1；如果棧底指針指向的存儲(chǔ)單元中沒有元素，則當(dāng)top=bottom時(shí)，棧中的元素個(gè)數(shù)為0。 NULL。 C)0或 C)1或 正常的入隊(duì)與退隊(duì)操作后，front=10,rear=5。該隊(duì)列中的 C)6D)

C)二維表D)矩 個(gè)），325-7=18 點(diǎn)的度之和+14×1+3×2+2×3+1×4+n×0+1=21,則4，1，101 B) C) 3×（n-10）+2×3+1×1+0×6+1=nn=113n-10=11-10=1。53和+13×n+1×（m-n-5）+5×0+1=mn=2。3,4。則該樹中的葉子結(jié)點(diǎn)數(shù)為

的結(jié)點(diǎn)數(shù)=17+15+16=48199，199+200>350，故不存在這樣的二叉樹。116412-1

Bk2m2-1662+1=63個(gè)時(shí)，a+1+a-1=2na=nn。BDBGEAFHC。DGEBHFCA。DGHEBIJFCA。

ABCDE。ABCDEFGDCBAEFG，則該二叉樹的深度（1）為E、F、GB、C、DE、F、G4。HGFEDCBA。B【解析】該二叉樹的后序遍歷序列與中序遍歷序列均為ABCDEF，則根結(jié)點(diǎn)為F；根結(jié)點(diǎn)F只有左子樹，右子樹為空。即ABCDE是根結(jié)點(diǎn)F的左子樹集合。這樣問題就轉(zhuǎn)化為就后序遍歷序列與中序遍歷序列均為ABCDE的子樹，同理可得左子樹集合的根結(jié)點(diǎn)為EE次類推，該二叉樹除葉子結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)只有左子樹無右子樹，結(jié)構(gòu)如下：

B【解析】中序遍歷的次序是先遍歷左子樹，再遍歷根結(jié)點(diǎn)，n。故本題中二叉樹的深度為n。則平均比較次數(shù)：（1+2+

n ×1=3??+1，大約為3??2

或者說平均情況與最壞情況下的時(shí)間復(fù)雜度是相同的。而查找無論是對分查找還是順序查找，都與要找的數(shù)據(jù)和原始的數(shù)據(jù)排列情況有關(guān)，最好情況是第1次查看的一個(gè)數(shù)據(jù)恰好

D【解析】有序線性表的長度為n，設(shè)被查找元素為x，則二分查找的方法如下：將x與線性表的中間項(xiàng)比較：若中間項(xiàng)的值等于x，則說明查到，查找結(jié)束；若x小于中間項(xiàng)的值，則在線性表的前半部分（即中間項(xiàng)以前的部分）以相同的方法進(jìn)行查找；若x大于中間項(xiàng)的值，則在線性表的后半部分lognlog97，6<log97<7,7n-1logn。40×（40-1）÷2=780。TT的元素移

n(n-1)/2n(n-1)/2。n=16，16×（16-1）÷2=8×15=120。h≤hh≤hh≥hh≥h時(shí)為大根堆。Dh=95，h=96，h<hh=89，nlognO(nlogn)。n(n-1)/2nlognn(n-1)/2，希爾排序?yàn)锽n(1<r<2)次，快n(n-1)/2

n(1<r<2)次，快速排序、冒泡排序均需要比較n(n-1)/2A【解析】要形成良好的程序設(shè)計(jì)風(fēng)格，主要應(yīng)注意和考慮：源程序文檔化；數(shù)據(jù)說明的次序規(guī)范化，說明語句中變量安排有序化，使用注釋來說明復(fù)雜數(shù)據(jù)的結(jié)構(gòu)；程序編寫要做到清晰第一、效率第二，先保證程序正確再要求提高速度，避免不必要的轉(zhuǎn)移；對所有的輸入數(shù)據(jù)都要進(jìn)行檢驗(yàn)，確保輸入數(shù)據(jù)的合法性。goto

UNIXERPUNIX系統(tǒng)屬于操作系統(tǒng)，故屬于系統(tǒng)軟件。ERP系統(tǒng)、辦公自動(dòng)化系統(tǒng)、學(xué)生成績管理系統(tǒng)屬于應(yīng)用軟件。D【解析】應(yīng)用軟件是為解決特定領(lǐng)域的應(yīng)用而開發(fā)的軟件。Android應(yīng)用軟件，Studio.NET

N-S數(shù)據(jù)流程圖(DFD圖加工（轉(zhuǎn)換）：輸入數(shù)據(jù)經(jīng)加工變換產(chǎn)生輸出。存儲(chǔ)文件：表示處理過程中存放各種數(shù)據(jù)的文件。

a是上級模塊，b是從屬模塊。2.22.3n.1n.231133535n。

3.12.33”2n.112n”3n3n.1”。 n.1nn。123”32.3”3333。n。5。

數(shù)據(jù)流程圖(DFD圖)C【解析】測試用例（TestCase）是為測試設(shè)計(jì)的數(shù)據(jù)，由

DBSDBDBSDBDBDBSDBMSDBDBSDBDBMS。D【解析】數(shù)據(jù)庫表的一行稱為一個(gè)記錄，一列稱一個(gè)字段。文件管理階段不能保證相同數(shù)據(jù)重復(fù)存儲(chǔ)。在數(shù)據(jù)庫系統(tǒng)階段使用數(shù)據(jù)庫管理數(shù)據(jù)，可大大減少相同數(shù)據(jù)重復(fù)存儲(chǔ)。

D)DBMSD【解析】數(shù)據(jù)庫系統(tǒng)已經(jīng)發(fā)展了三個(gè)階段：第一代的網(wǎng)狀、層次型數(shù)據(jù)庫系統(tǒng)，第二代的關(guān)系型數(shù)據(jù)庫系統(tǒng)，第三代的面向?qū)ο蟮臄?shù)據(jù)庫系統(tǒng)。 DDL（數(shù)據(jù)定義語言）定義。

3個(gè)B)2C)1個(gè)D) 物理數(shù)據(jù)模型又稱物理模型，它是一種面向計(jì)算機(jī)物理表示

AC 類型（1:1、1:nn:n）。 112

Dl D#S（碼）。書(書號,類別,書名,出版社,年份,作者,價(jià)格,總藏書量, Rπ(R)，其中，ARTRRσ(R) C) 式S(S#,Sn,Sg,Sd,Sa)S#、Sn、Sg、Sd、SaC)(S))

A)B)C)D)SC（σ操作，σ(SC)），兩個(gè)條所以在篩選后再做投影操作只取“學(xué)號”列π(σ(SC))TRS通過（） C)選擇D)RSR∩STRS，故為交運(yùn)算。RS，故為并運(yùn)算。選擇B)差C)交D)TRS，故為差運(yùn)算。交B)并C)投影D)并且進(jìn)行等值連接，在結(jié)果中還要把重復(fù)的屬性列去掉。本題屬于自然連接，隱含條件是R.A=S.A。

R2D學(xué)號，C#為課程號，GT=π(SC)/CCC1C2SS(S#,Sn,Sd,Sa)（其屬性分別為學(xué)號、姓名、所在系、年A)B)只要“學(xué)號”列π(σ(SC))，得到查詢結(jié)果的一個(gè)小π(π(σ(SC))∞S)。P#為患者編號，PnPgBy日期，Tr(P#，D#，Date，Rt)D#為醫(yī)生編號，Date為就診日期，Rt1BPPnTrD#=1

(Tr)），（πS(S#,Sn,Sd,Sa)（其屬性分別為學(xué)號、姓名、所在系、D)C在“90分以上（含90分）”需要在SC表中查找，“學(xué)生姓名”需要在S表中查找，所以必須對上述三個(gè)表進(jìn)行連接后再進(jìn)行操作。具體操作是：先從C表中選出課程名是“操作系統(tǒng)”的行σ(C)，但是只要“課程”列π(σ(C))，得到篩選結(jié)果的一個(gè)小表；在SC表中找出“90分以上（含90分）”的行σ(SC)，得到第二個(gè)小表；兩π(π(σ(C))∞σ(SC))；這樣得到的結(jié)果再與S表連接并從結(jié)果中只取“姓名”列π(π(π(σ(C))∞σ(SC))∞S)。 E-R消除存儲(chǔ)異常，使數(shù)據(jù)冗余盡量小，便于插入、刪除和更新等操作。 RAXY→A 部門總經(jīng)理D)

BCNFS齡）；C（C#,Cn,P#）（其屬性