計(jì)算機(jī)科學(xué)基礎(chǔ)知識(shí)期末測(cè)試題前言本測(cè)試旨在全面考察學(xué)生對(duì)計(jì)算機(jī)科學(xué)核心基礎(chǔ)知識(shí)的掌握程度，涵蓋計(jì)算機(jī)系統(tǒng)構(gòu)成、數(shù)據(jù)結(jié)構(gòu)與算法、操作系統(tǒng)、計(jì)算機(jī)網(wǎng)絡(luò)、數(shù)據(jù)庫(kù)原理等關(guān)鍵領(lǐng)域。題目設(shè)計(jì)注重理論與實(shí)踐的結(jié)合，既檢驗(yàn)對(duì)基本概念的理解，也考察分析問(wèn)題和解決問(wèn)題的初步能力。希望通過(guò)本次測(cè)試，能夠幫助學(xué)生梳理知識(shí)體系，發(fā)現(xiàn)學(xué)習(xí)中的薄弱環(huán)節(jié)，為后續(xù)深入學(xué)習(xí)奠定堅(jiān)實(shí)基礎(chǔ)。請(qǐng)考生在規(guī)定時(shí)間內(nèi)獨(dú)立完成，字跡工整，答案清晰。---一、計(jì)算機(jī)系統(tǒng)構(gòu)成(共20分)（一）簡(jiǎn)答題(每題5分，共10分)1.請(qǐng)簡(jiǎn)述馮·諾依曼體系結(jié)構(gòu)的核心思想，并列舉其主要組成部分。2.解釋計(jì)算機(jī)中“指令”與“程序”的概念，并說(shuō)明它們之間的關(guān)系。（二）分析題(10分)3.比較內(nèi)存（主存）與外存（輔存）在計(jì)算機(jī)系統(tǒng)中的作用、主要特點(diǎn)及典型類型。請(qǐng)結(jié)合一個(gè)程序的執(zhí)行過(guò)程（例如，從雙擊圖標(biāo)到程序運(yùn)行），說(shuō)明內(nèi)存與外存是如何協(xié)同工作的。---二、數(shù)據(jù)結(jié)構(gòu)與算法基礎(chǔ)(共30分)（一）選擇題(每題3分，共9分)(注：每題可能有一個(gè)或多個(gè)正確答案，請(qǐng)選出所有正確答案)4.下列關(guān)于線性表的描述中，正確的是：A.數(shù)組在內(nèi)存中是連續(xù)存儲(chǔ)的，因此隨機(jī)訪問(wèn)效率高。B.鏈表的節(jié)點(diǎn)在內(nèi)存中可以不連續(xù)，因此插入和刪除操作不需要移動(dòng)大量元素。C.棧和隊(duì)列是特殊的線性表，其操作遵循特定的規(guī)則。D.對(duì)于一個(gè)有序線性表，使用二分查找法總能比順序查找法獲得更高的效率。5.關(guān)于二叉樹，以下說(shuō)法錯(cuò)誤的是：A.一棵二叉樹的度可以為2。B.滿二叉樹一定是完全二叉樹。C.在任意一棵二叉樹中，葉子節(jié)點(diǎn)的數(shù)量總是比度為2的節(jié)點(diǎn)數(shù)量多一個(gè)。D.二叉查找樹（BST）的中序遍歷結(jié)果是一個(gè)有序序列。6.算法的時(shí)間復(fù)雜度是指：A.算法執(zhí)行過(guò)程中所需要的基本運(yùn)算次數(shù)。B.算法程序的長(zhǎng)度。C.算法執(zhí)行過(guò)程中所需要的存儲(chǔ)空間。D.算法執(zhí)行的平均時(shí)間。（二）簡(jiǎn)答題(每題7分，共14分)7.什么是棧？什么是隊(duì)列？請(qǐng)各舉一個(gè)它們?cè)趯?shí)際計(jì)算機(jī)應(yīng)用中的例子，并簡(jiǎn)述其在該例子中所起的作用。8.簡(jiǎn)述排序算法的穩(wěn)定性概念。請(qǐng)列舉至少兩種穩(wěn)定的排序算法和兩種不穩(wěn)定的排序算法。（三）算法設(shè)計(jì)與分析(7分)9.假設(shè)有一個(gè)包含n個(gè)整數(shù)的無(wú)序數(shù)組，請(qǐng)?jiān)O(shè)計(jì)一個(gè)算法找出其中第二大的元素。要求：*描述算法的基本思想。*分析該算法的時(shí)間復(fù)雜度和空間復(fù)雜度。---三、操作系統(tǒng)核心概念(共15分)（一）簡(jiǎn)答題(每題5分，共10分)10.什么是進(jìn)程？進(jìn)程與程序的主要區(qū)別是什么？進(jìn)程的基本狀態(tài)有哪些？11.簡(jiǎn)述操作系統(tǒng)中“死鎖”的概念，并列舉至少兩種預(yù)防或避免死鎖的常用策略。（二）論述題(5分)12.請(qǐng)簡(jiǎn)述分頁(yè)存儲(chǔ)管理和分段存儲(chǔ)管理的基本原理，并比較它們的主要異同點(diǎn)。---四、計(jì)算機(jī)網(wǎng)絡(luò)基礎(chǔ)(共15分)（一）選擇題(每題3分，共6分)13.在TCP/IP協(xié)議簇中，負(fù)責(zé)將數(shù)據(jù)從源主機(jī)通過(guò)網(wǎng)絡(luò)送達(dá)目的主機(jī)的協(xié)議是：B.IPC.TCPD.UDP14.關(guān)于TCP和UDP協(xié)議，以下說(shuō)法錯(cuò)誤的是：A.TCP是面向連接的，UDP是無(wú)連接的。B.TCP提供可靠的數(shù)據(jù)傳輸服務(wù)，UDP不保證數(shù)據(jù)的可靠交付。D.由于TCP需要建立連接，因此其數(shù)據(jù)傳輸速率一定比UDP慢。（二）簡(jiǎn)答題(9分)15.請(qǐng)解釋IP地址和MAC地址的概念，并說(shuō)明它們?cè)谟?jì)算機(jī)網(wǎng)絡(luò)通信中的作用及區(qū)別。為什么需要進(jìn)行ARP協(xié)議（地址解析協(xié)議）的操作？---五、數(shù)據(jù)庫(kù)原理入門(共20分)（一）名詞解釋(每題3分，共9分)16.關(guān)系數(shù)據(jù)庫(kù)17.主鍵(PrimaryKey)18.SQL(StructuredQueryLanguage)（二）簡(jiǎn)答題(6分)19.什么是數(shù)據(jù)庫(kù)事務(wù)？事務(wù)的ACID特性指的是什么？（三）SQL語(yǔ)句編寫(5分)20.假設(shè)有一個(gè)學(xué)生表`Student`，結(jié)構(gòu)如下：*Sno(CHAR,學(xué)生學(xué)號(hào)，主鍵)*Sname(VARCHAR,學(xué)生姓名)*Sage(INT,學(xué)生年齡)*Sdept(VARCHAR,學(xué)生所在系)請(qǐng)寫出一條SQL查詢語(yǔ)句，查詢出“計(jì)算機(jī)系”（假設(shè)系名為'CS'）所有年齡大于20歲的學(xué)生姓名和年齡，并按年齡降序排列。---參考答案與評(píng)分標(biāo)準(zhǔn)（簡(jiǎn)要提示）（注：完整的參考答案與詳細(xì)評(píng)分標(biāo)準(zhǔn)將在測(cè)試結(jié)束后提供給教師用于閱卷。此處僅為簡(jiǎn)要提示，幫助學(xué)生了解答題方向。）*一、計(jì)算機(jī)系統(tǒng)構(gòu)成：*馮·諾依曼核心思想：存儲(chǔ)程序、五大組成部分（運(yùn)算器、控制器、存儲(chǔ)器、輸入設(shè)備、輸出設(shè)備）。*指令是計(jì)算機(jī)能執(zhí)行的基本操作命令，程序是指令的有序集合。*內(nèi)存速度快、容量小、斷電易失；外存速度慢、容量大、斷電非易失。程序執(zhí)行時(shí)從外存加載到內(nèi)存。*二、數(shù)據(jù)結(jié)構(gòu)與算法基礎(chǔ)：*選擇題注意細(xì)節(jié)辨析。*棧：后進(jìn)先出（LIFO）；隊(duì)列：先進(jìn)先出（FIFO）。舉例合理即可。*穩(wěn)定性：相同關(guān)鍵字元素相對(duì)順序是否保持。穩(wěn)定排序如冒泡、插入；不穩(wěn)定如選擇、快速。*找第二大元素算法：可遍歷一次記錄最大和次大，時(shí)間復(fù)雜度O(n)。*三、操作系統(tǒng)核心概念：*進(jìn)程是程序的一次執(zhí)行過(guò)程，動(dòng)態(tài)的?；緺顟B(tài)：就緒、運(yùn)行、阻塞。*死鎖：多個(gè)進(jìn)程因競(jìng)爭(zhēng)資源而無(wú)限等待。預(yù)防策略如有序資源分配法、銀行家算法等。*分頁(yè)與分段的區(qū)別：頁(yè)是物理單位，段是邏輯單位；頁(yè)大小固定，段大小可變等。*四、計(jì)算機(jī)網(wǎng)絡(luò)基礎(chǔ)：*IP協(xié)議負(fù)責(zé)路由和尋址。*TCP可靠但開銷大，UDP不可靠但高效。*IP地址是邏輯地址，MAC是物理地址。ARP用于IP地址到MAC地址的映射。*五、數(shù)據(jù)庫(kù)原理入門：*關(guān)系數(shù)據(jù)庫(kù)基于關(guān)系模型（二維表）。主鍵唯一標(biāo)識(shí)元組。SQL是關(guān)系數(shù)據(jù)庫(kù)標(biāo)準(zhǔn)查詢語(yǔ)言。*事務(wù)ACID：原子性、一致性、隔離性、持久性。*SQL查詢：SELECTSname,SageFROMStudentWHERESdept='CS'ANDSage>20