大學(xué)本科計(jì)算機(jī)科學(xué)基礎(chǔ)期末考試試卷考試時(shí)長(zhǎng)：120分鐘滿分：100分班級(jí)：__________姓名：__________學(xué)號(hào)：__________得分：__________大學(xué)本科計(jì)算機(jī)科學(xué)基礎(chǔ)期末考試試卷考核對(duì)象：計(jì)算機(jī)科學(xué)專業(yè)本科二年級(jí)學(xué)生題型分值分布：-單選題（10題，每題2分，共20分）-填空題（10題，每題2分，共20分）-判斷題（10題，每題2分，共20分）-簡(jiǎn)答題（3題，每題4分，共12分）-應(yīng)用題（2題，每題9分，共18分）總分：100分一、單選題（每題2分，共20分）1.在二叉樹中，若某節(jié)點(diǎn)的度為2，則該節(jié)點(diǎn)稱為（）。A.葉節(jié)點(diǎn)B.內(nèi)節(jié)點(diǎn)C.根節(jié)點(diǎn)D.鏈接節(jié)點(diǎn)2.下列排序算法中，時(shí)間復(fù)雜度最壞情況下為O(n2)的是（）。A.快速排序B.歸并排序C.堆排序D.插入排序3.在SQL中，用于刪除表中數(shù)據(jù)的語(yǔ)句是（）。A.UPDATEB.DELETEC.INSERTD.SELECT4.下列數(shù)據(jù)結(jié)構(gòu)中，適合用于實(shí)現(xiàn)棧的是（）。A.鏈表B.堆棧C.隊(duì)列D.哈希表5.TCP協(xié)議與UDP協(xié)議的主要區(qū)別在于（）。A.傳輸速度B.連接模式C.報(bào)文格式D.應(yīng)用場(chǎng)景6.在面向?qū)ο缶幊讨?，封裝的目的是（）。A.提高代碼可讀性B.減少代碼重復(fù)C.隱藏實(shí)現(xiàn)細(xì)節(jié)D.增強(qiáng)代碼可維護(hù)性7.下列操作系統(tǒng)中，屬于分布式操作系統(tǒng)的是（）。A.Windows10B.UnixC.LinuxD.Amoeba8.在計(jì)算機(jī)網(wǎng)絡(luò)中，IP地址與MAC地址的關(guān)系是（）。A.IP地址用于路由，MAC地址用于局域網(wǎng)識(shí)別B.IP地址用于局域網(wǎng)識(shí)別，MAC地址用于路由C.兩者完全無(wú)關(guān)D.兩者相同9.下列算法中，屬于動(dòng)態(tài)規(guī)劃的是（）。A.分治法B.貪心法C.回溯法D.動(dòng)態(tài)規(guī)劃10.在數(shù)據(jù)庫(kù)設(shè)計(jì)中，范式最高的關(guān)系模式是（）。A.第一范式（1NF）B.第二范式（2NF）C.第三范式（3NF）D.BCNF二、填空題（每題2分，共20分）1.數(shù)據(jù)結(jié)構(gòu)中的“遞歸”是指函數(shù)調(diào)用自身的現(xiàn)象。2.在二叉搜索樹中，左子樹的所有節(jié)點(diǎn)值均小于根節(jié)點(diǎn)值。3.SQL中，用于創(chuàng)建表的語(yǔ)句是CREATETABLE。4.棧的特點(diǎn)是“后進(jìn)先出”（LIFO）。5.TCP協(xié)議是一種面向連接的協(xié)議。6.在面向?qū)ο缶幊讨?，繼承是指一個(gè)類繼承另一個(gè)類的屬性和方法。7.計(jì)算機(jī)網(wǎng)絡(luò)中的“OSI模型”共有七層。8.堆排序是一種基于堆數(shù)據(jù)結(jié)構(gòu)的排序算法。9.數(shù)據(jù)庫(kù)中的“外鍵”用于維護(hù)表之間的關(guān)聯(lián)關(guān)系。10.算法的“時(shí)間復(fù)雜度”描述了算法執(zhí)行時(shí)間隨輸入規(guī)模增長(zhǎng)的變化趨勢(shì)。三、判斷題（每題2分，共20分）1.快速排序的平均時(shí)間復(fù)雜度為O(n2)。（×）2.堆是一種完全二叉樹。（√）3.SQL中的“INNERJOIN”只返回兩個(gè)表中匹配的記錄。（√）4.棧和隊(duì)列都是線性數(shù)據(jù)結(jié)構(gòu)。（√）5.TCP協(xié)議比UDP協(xié)議更高效。（×）6.封裝、繼承和多態(tài)是面向?qū)ο缶幊痰娜筇匦?。（√?.分布式操作系統(tǒng)必須運(yùn)行在同一物理機(jī)器上。（×）8.IP地址和MAC地址都是全球唯一的。（×）9.動(dòng)態(tài)規(guī)劃適用于解決最優(yōu)問題。（√）10.第三范式（3NF）消除了非主屬性對(duì)候選鍵的傳遞依賴。（√）四、簡(jiǎn)答題（每題4分，共12分）1.簡(jiǎn)述二叉樹與線性表的異同。答案：-相同點(diǎn)：都是數(shù)據(jù)結(jié)構(gòu)，用于存儲(chǔ)數(shù)據(jù)元素。-不同點(diǎn)：二叉樹是非線性結(jié)構(gòu)，支持層次關(guān)系；線性表是線性結(jié)構(gòu)，元素依次排列。2.解釋SQL中“視圖”的概念及其作用。答案：-視圖是數(shù)據(jù)庫(kù)中虛擬表，基于SQL查詢定義。-作用：簡(jiǎn)化復(fù)雜查詢、增強(qiáng)數(shù)據(jù)安全性、邏輯數(shù)據(jù)抽象。3.描述TCP協(xié)議三次握手的過程。答案：1.客戶端發(fā)送SYN包，請(qǐng)求連接。2.服務(wù)器回復(fù)SYN+ACK包，確認(rèn)連接。3.客戶端發(fā)送ACK包，完成連接。五、應(yīng)用題（每題9分，共18分）1.設(shè)計(jì)一個(gè)簡(jiǎn)單的學(xué)生信息管理系統(tǒng)，包含以下功能：-添加學(xué)生信息（學(xué)號(hào)、姓名、年齡）。-查詢學(xué)生信息（按學(xué)號(hào)）。-刪除學(xué)生信息（按學(xué)號(hào)）。要求：用偽代碼描述核心邏輯。答案：```//添加學(xué)生信息functionaddStudent(id,name,age){if(studentExists(id))return"ID已存在";students[id]={name,age};return"添加成功";}//查詢學(xué)生信息functiongetStudent(id){returnstudents[id]||"學(xué)生不存在";}//刪除學(xué)生信息functiondeleteStudent(id){if(!studentExists(id))return"學(xué)生不存在";deletestudents[id];return"刪除成功";}functionstudentExists(id){returnidinstudents;}```2.假設(shè)有一個(gè)無(wú)重復(fù)元素的數(shù)組`arr=[3,1,4,1,5,9,2,6,5,3,5]`，請(qǐng)用Python代碼實(shí)現(xiàn)快速排序，并輸出排序后的數(shù)組。答案：```pythondefquickSort(arr):iflen(arr)<=1:returnarr;pivot=arr[len(arr)//2];left=[xforxinarrifx<pivot];middle=[xforxinarrifx==pivot];right=[xforxinarrifx>pivot];returnquickSort(left)+middle+quickSort(right);arr=[3,1,4,1,5,9,2,6,5,3,5];sorted_arr=quickSort(arr);print(sorted_arr);//輸出：[1,1,2,3,3,4,5,5,5,6,9]```標(biāo)準(zhǔn)答案及解析一、單選題1.B-內(nèi)節(jié)點(diǎn)指度為2的節(jié)點(diǎn)，葉節(jié)點(diǎn)度為0，根節(jié)點(diǎn)是樹的起始節(jié)點(diǎn)。2.D-插入排序最壞情況O(n2)，快速排序、歸并排序、堆排序最壞O(nlogn)。3.B-DELETE用于刪除數(shù)據(jù)，UPDATE修改數(shù)據(jù)，INSERT插入數(shù)據(jù)。4.A-鏈表可高效實(shí)現(xiàn)棧的LIFO特性。5.B-TCP面向連接，UDP無(wú)連接。6.C-封裝隱藏實(shí)現(xiàn)細(xì)節(jié)，提高安全性。7.D-Amoeba是分布式操作系統(tǒng)，其余為單機(jī)系統(tǒng)。8.A-IP用于路由，MAC用于局域網(wǎng)硬件識(shí)別。9.D-動(dòng)態(tài)規(guī)劃通過子問題求解最優(yōu)解。10.D-BCNF比3NF更嚴(yán)格，消除所有傳遞依賴。二、填空題1.是2.是3.是4.是5.是6.是7.是8.是9.是10.是三、判斷題1.×-快速排序平均O(nlogn)，最壞O(n2)。2.√-堆是完全二叉樹。3.√-INNERJOIN返回匹配記錄。4.√-棧（LIFO）、隊(duì)列（FIFO）都是線性結(jié)構(gòu)。5.×-TCP可靠性高但開銷大，UDP更快但不可靠。6.√-封裝、繼承、多態(tài)是三大特性。7.×-分布式系統(tǒng)可跨機(jī)器。8.×-MAC地址局域網(wǎng)內(nèi)唯一，IP地址全球唯一。9.√-動(dòng)態(tài)規(guī)劃適用于最優(yōu)問題。10.√-3NF消除非主屬性對(duì)候選鍵的傳遞依賴。四、簡(jiǎn)答題1.二叉樹與線性表的異同-相同點(diǎn)：都是數(shù)據(jù)結(jié)構(gòu)，存儲(chǔ)數(shù)據(jù)元素。-不同點(diǎn)：二叉樹非線性，支持層次關(guān)系；線性表線性，元素依次排列。2.SQL視圖的概念及作用-視圖是虛擬表，基于SQL查詢定義。-作用：簡(jiǎn)化復(fù)雜查詢、增強(qiáng)數(shù)據(jù)安全性、