軟件技術(shù)基礎(chǔ)2006-2007第一學(xué)期期末試卷B.doc

南昌大學(xué) 20062007學(xué)年第 1 學(xué)期期末考試試卷 試卷編號(hào)： 信9 (B )卷課程編號(hào)： X61050001 課程名稱： 計(jì)算機(jī)軟件技術(shù)基礎(chǔ) 考試形式： 閉卷 適用班級(jí)： 生物醫(yī)學(xué)04級(jí) 姓名： 學(xué)號(hào)： 班級(jí)： 學(xué)院： 專業(yè)： 考試日期： 2007.01.15 題號(hào)一二三四五六七八九十總分累分人 簽名題分2020202020 100得分一、 單項(xiàng)選擇題 (每小題1分，共20分) 得分評(píng)閱人 1. 一個(gè)向量第一個(gè)元素的存儲(chǔ)地址是1000，每個(gè)元素的長(zhǎng)度為2，則第4個(gè)元素的地址是 。A. 1010 B. 1008 C. 1004 D. 10122下列選項(xiàng)中，不是算法基本特征的是 。 A可行性 B. 有窮性 C. 確定性 D.高效率 3在一個(gè)單鏈表中，若p結(jié)點(diǎn)不是最后一結(jié)點(diǎn)。在p結(jié)點(diǎn)之后插入s結(jié)點(diǎn)的正確是 。 A. s-next=p; p-next=s; B. s-next=p; p=p C. s-next=p-next ; p-next=s; D. p-next=s; s-next=p; 4. 設(shè)有1000個(gè)無(wú)序的元素，希望用最快的速度挑選出其中前10個(gè)最大的元素，最好選用 排序法。 A. 冒泡排序 B. 快速排序 C. 堆排序 D.選擇排序5描述數(shù)據(jù)庫(kù)全體數(shù)據(jù)的全局邏輯結(jié)構(gòu)和特性的是 。 A. 模式 B. 內(nèi)模式 C. 外模式 D. 用戶模式6. 在一棵二叉樹中有30個(gè)葉子結(jié)點(diǎn)，僅有一個(gè)孩子的結(jié)點(diǎn)有20個(gè)，則該二叉樹共有 個(gè)結(jié)點(diǎn)A、79 B、76 C、56 D、817. 對(duì)于下三角矩陣A，若采用一個(gè)一維數(shù)組B以行為主順序存放壓縮矩陣A，則A43存放在 中A. B7B. B8C. B9D. B108. 順序查找適合于存儲(chǔ)結(jié)構(gòu)為 的線性表。 A. 散列存儲(chǔ) B. 順序存儲(chǔ)或鏈?zhǔn)酱鎯?chǔ) C. 壓縮存儲(chǔ) D. 索引存儲(chǔ) 第 6 頁(yè) 共 6頁(yè)9. 排序方法中，從未排序序列中挑選元素最小的記錄，并將其順序放在已排序序列的末端的方法，稱為 。A. 希爾排序 B. 冒泡排序 C. 插入排序 D. 選擇排序10. SQL是一種 語(yǔ)言。A. 高級(jí)算法 B. 人工智能 C. 關(guān)系數(shù)據(jù)庫(kù) D. 函數(shù)型 11. 目前較有影響的數(shù)據(jù)庫(kù)，如Oracle 、SQL Server、Visual Foxpro等，基于的數(shù)據(jù)模型是 。 試A. 層次模型 B. 關(guān)系模型 C. 網(wǎng)狀模型 D. 混合型12對(duì)任何一棵二叉樹，若n0，n1，n2分別是度為0，1，2的結(jié)點(diǎn)的個(gè)數(shù)，則n0= 。A、n1+1 B、n1+n2 C、n2+1 D、2n1+113設(shè)關(guān)鍵碼序列為（16，9，4，25，15，2，13，18，17，5，8，24），要按關(guān)鍵碼值遞增的次序排列，采用直接選擇排序法，一趟排序后的結(jié)果是 。 A.（15，2，4，18，16，5，8，24，17，9，13，25） B.（2，9，4，25，15，16，13，18，17，5，8，24） C.（9，4，16，15，2，13，18，17，5，8，24，25） D.（9，16，4，25，21，5，13，18，5，17，8，24） 14對(duì)于深度為4的完全二叉樹，則該二叉樹葉結(jié)點(diǎn)數(shù)是 。A. 16 B. 31 C. 32 D. 815下列關(guān)于時(shí)間片輪轉(zhuǎn)法的敘述中，錯(cuò)誤的是 。A、如果時(shí)間片長(zhǎng)度很小，則調(diào)度程序剝奪CPU的次數(shù)頻繁，加重系統(tǒng)開銷B、當(dāng)時(shí)間片結(jié)束時(shí)，運(yùn)行進(jìn)程自動(dòng)讓出CPU，該進(jìn)程進(jìn)入等待隊(duì)列C、就緒隊(duì)列中的諸進(jìn)程輪流上CPU運(yùn)行，每次最多運(yùn)行一個(gè)時(shí)間片D、 在時(shí)間片輪轉(zhuǎn)法中，系統(tǒng)將CPU的處理時(shí)間劃分成若干個(gè)時(shí)間段16用鏈表表示線性表的優(yōu)點(diǎn)是 。 A、花費(fèi)的存儲(chǔ)空間比順序表少 B、便于隨機(jī)存取C、數(shù)據(jù)元素的物理順序與邏輯順序相同 D、便于插入與刪除17實(shí)體間的聯(lián)系方式是 。A、 1：1 B、1：N C、M:N D、前三種圴可18假設(shè)學(xué)生關(guān)系S（S，SNAME，SEX），課程關(guān)系C（C，CNAME），學(xué)生選課關(guān)系SC（S，C，GRADE）。要查詢選修“Computer”課的男生姓名，將涉及到關(guān)系 。 A. S B. S，SC C. C，SC D. S，C，SC 19. 專門的關(guān)系運(yùn)算不包括下列中的 。A. 連接運(yùn)算 B. 選擇運(yùn)算 C. 投影運(yùn)算 D. 交運(yùn)算20. n 個(gè)頂點(diǎn)的連通圖至少有 條邊。 A、n-1 B、n C、n+1 D、0二、 填空題 (每空1分，共20分) 得分評(píng)閱人 1.算法的復(fù)雜度包括 和 兩個(gè)方面。2.棧是一種 的線性表；而隊(duì)列是一種 的線性表。3.數(shù)據(jù)庫(kù)中三種基本的數(shù)據(jù)模型是： 、 和 。4. 在線性表的散列存儲(chǔ)中，處理沖突有 和 兩種方法。5. 操作系統(tǒng)中利用P/V操作可實(shí)現(xiàn)進(jìn)程的 和 。6. 數(shù)據(jù)的 結(jié)構(gòu)與數(shù)據(jù)元素本身的內(nèi)容、形式、個(gè)數(shù)和相對(duì)位置無(wú)關(guān)。7.一個(gè)無(wú)向圖采用鄰接矩陣存儲(chǔ)方法，其鄰接矩陣一定是一個(gè)_ _。8、數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)有四種基本的存儲(chǔ)映射方式：順序 、索引和 存儲(chǔ)方式。9、進(jìn)程具有 、并發(fā)性和 三個(gè)基本特征。10、死鎖的四個(gè)必要條件是_、_、不可搶奪資源和_ _ 。三、 簡(jiǎn)答題 (每小題5分，共20分) 得分評(píng)閱人 1. 關(guān)系代數(shù)中包括哪些集合運(yùn)算和專門的關(guān)系運(yùn)算。2.簡(jiǎn)述快速排序的基本思想。3.什么是虛擬存儲(chǔ)技術(shù)？4. 從宏觀上看，操作系統(tǒng)有哪幾個(gè)主要功能？。四、 應(yīng)用題 (每小題5分，共20分) 得分評(píng)閱人 1.求右圖所示二叉樹的前序和中序遍歷的結(jié)點(diǎn)序列。2.一座山上有一個(gè)隧道，規(guī)定每次只允許一輛汽車通過(guò)，現(xiàn)在遂道兩端都有車輛要過(guò)遂道。如果把每輛過(guò)遂道的汽車看作一個(gè)進(jìn)程，為保證安全，請(qǐng)用PV操作實(shí)現(xiàn)正確管理。（同時(shí)說(shuō)明信號(hào)量的初值）3. 輸入一個(gè)正整數(shù)序列40，28，6，72，100，3，54，1，80，91，38, 建立一棵二叉排序樹，然后刪除結(jié)點(diǎn)80，分別畫出該二叉排序樹和刪除結(jié)點(diǎn)80后的二叉排序樹。4. 根據(jù)如下的“教師”表，用SQL語(yǔ)句完成下面的問(wèn)題：職工號(hào)姓名職稱年齡工資11020011102002110200311020041102005肖海天王遠(yuǎn)劉星李名玉孫明山副教授教授講師教授教授354030455520003000120035004000（1）用SQL語(yǔ)句向教師表中插入一條記錄：（1102006，張平，副教授，38，1500）（2）查詢所有職稱為教授的教師信息（3）用SQL語(yǔ)句完成：將所有職稱為教授的教師的工資