2025年沒收到港大ds筆試及答案

一、單項選擇題（總共10題，每題2分）1.在數(shù)據(jù)結(jié)構(gòu)中，下列哪一種結(jié)構(gòu)是線性結(jié)構(gòu)？A.樹B.圖C.隊列D.圖2.下列哪種排序算法的平均時間復(fù)雜度是O(nlogn)？A.冒泡排序B.選擇排序C.快速排序D.插入排序3.在數(shù)據(jù)庫中，關(guān)系模型中的主鍵是指？A.唯一標識元組的屬性或?qū)傩越M合B.非常重要的屬性C.可以重復(fù)的屬性D.長度較長的屬性4.下列哪種數(shù)據(jù)壓縮方法是無損壓縮？A.Huffman編碼B.LZW編碼C.JPEG壓縮D.MP3壓縮5.在計算機網(wǎng)絡(luò)中，TCP協(xié)議是一種？A.無連接的協(xié)議B.有連接的協(xié)議C.無狀態(tài)的協(xié)議D.有狀態(tài)的協(xié)議6.下列哪種算法是用于解決最短路徑問題的？A.Dijkstra算法B.Floyd-Warshall算法C.Kruskal算法D.Prim算法7.在機器學(xué)習(xí)中，下列哪種模型是用于分類問題的？A.線性回歸模型B.決策樹模型C.神經(jīng)網(wǎng)絡(luò)模型D.支持向量機模型8.在數(shù)據(jù)挖掘中，關(guān)聯(lián)規(guī)則挖掘的常見算法是？A.Apriori算法B.K-Means算法C.KNN算法D.SVM算法9.在操作系統(tǒng)內(nèi)核中，下列哪種機制用于管理進程的調(diào)度？A.驅(qū)動程序B.中斷C.進程調(diào)度算法D.內(nèi)存管理10.在軟件工程中，下列哪種方法學(xué)強調(diào)迭代和增量開發(fā)？A.瀑布模型B.V模型C.敏捷開發(fā)D.精益開發(fā)二、填空題（總共10題，每題2分）1.數(shù)據(jù)結(jié)構(gòu)中的棧是一種______結(jié)構(gòu)，遵循______原則。2.快速排序算法的平均時間復(fù)雜度是______。3.數(shù)據(jù)庫中的事務(wù)具有ACID特性，其中A代表______。4.無損壓縮方法能夠______原始數(shù)據(jù)的壓縮版本。5.TCP協(xié)議是一種面向______的協(xié)議。6.Dijkstra算法用于解決______問題。7.決策樹模型在機器學(xué)習(xí)中常用于______問題。8.數(shù)據(jù)挖掘中的Apriori算法用于發(fā)現(xiàn)數(shù)據(jù)項之間的______規(guī)則。9.操作系統(tǒng)內(nèi)核中的中斷機制用于______外部事件。10.敏捷開發(fā)方法強調(diào)______和快速響應(yīng)變化。三、判斷題（總共10題，每題2分）1.棧和隊列都是線性結(jié)構(gòu)，但棧是先進先出，隊列是后進先出。2.冒泡排序算法的時間復(fù)雜度在最好情況下是O(n)。3.數(shù)據(jù)庫中的外鍵用于保證參照完整性。4.JPEG壓縮是一種有損壓縮方法。5.TCP協(xié)議是無連接的協(xié)議。6.Floyd-Warshall算法用于解決所有頂點對之間的最短路徑問題。7.線性回歸模型主要用于分類問題。8.K-Means算法是一種聚類算法。9.進程調(diào)度算法用于決定哪個進程在何時使用CPU。10.精益開發(fā)方法強調(diào)一次性完成所有開發(fā)任務(wù)。四、簡答題（總共4題，每題5分）1.簡述棧和隊列的區(qū)別。2.解釋數(shù)據(jù)庫中的參照完整性的概念。3.描述TCP協(xié)議與UDP協(xié)議的主要區(qū)別。4.簡述Apriori算法的基本原理。五、討論題（總共4題，每題5分）1.討論快速排序算法在不同數(shù)據(jù)分布下的性能表現(xiàn)。2.分析Dijkstra算法的優(yōu)缺點及其適用場景。3.討論機器學(xué)習(xí)中決策樹模型的優(yōu)缺點。4.討論敏捷開發(fā)方法在軟件開發(fā)中的應(yīng)用及其優(yōu)勢。答案和解析一、單項選擇題1.C2.C3.A4.B5.B6.A7.D8.A9.C10.C二、填空題1.線性，后進先出2.O(nlogn)3.原子性4.完全恢復(fù)原始數(shù)據(jù)5.連接6.單源最短路徑7.分類8.關(guān)聯(lián)9.處理10.迭代三、判斷題1.正確2.正確3.正確4.正確5.錯誤6.正確7.錯誤8.正確9.正確10.錯誤四、簡答題1.棧是一種后進先出（LIFO）的線性結(jié)構(gòu)，而隊列是一種先進先出（FIFO）的線性結(jié)構(gòu)。棧的操作僅限于棧頂，而隊列的操作可以在隊頭和隊尾進行。2.參照完整性是指在數(shù)據(jù)庫中，外鍵約束確保了關(guān)系之間的引用完整性，即一個表中的外鍵值必須在另一個表的主鍵中存在。這保證了數(shù)據(jù)的邏輯一致性。3.TCP協(xié)議是一種面向連接的、可靠的協(xié)議，通過三次握手建立連接，并確保數(shù)據(jù)的順序和完整性。而UDP協(xié)議是一種無連接的、不可靠的協(xié)議，數(shù)據(jù)傳輸速度快但不對數(shù)據(jù)的順序和完整性進行保證。4.Apriori算法是一種用于關(guān)聯(lián)規(guī)則挖掘的算法，其基本原理是基于頻繁項集的性質(zhì)。算法通過生成候選項集，然后通過支持度進行剪枝，最終找到滿足最小支持度的頻繁項集，并生成關(guān)聯(lián)規(guī)則。五、討論題1.快速排序算法在不同數(shù)據(jù)分布下的性能表現(xiàn)差異較大。在最佳情況下，即數(shù)據(jù)分布均勻時，其時間復(fù)雜度為O(nlogn)。但在最壞情況下，即數(shù)據(jù)已經(jīng)排序或接近排序時，其時間復(fù)雜度會退化到O(n^2)。因此，實際應(yīng)用中常采用隨機化快速排序來提高算法的魯棒性。2.Dijkstra算法的優(yōu)點是能夠高效地找到單源最短路徑，適用于稀疏圖。但其缺點是只能處理非負權(quán)重的邊，且在處理大規(guī)模圖時可能會遇到性能問題。Dijkstra算法適用于需要找到最短路徑的場景，如網(wǎng)絡(luò)路由和交通導(dǎo)航。3.決策樹模型的優(yōu)點是易于理解和解釋，能夠處理混合類型的數(shù)據(jù)，且對缺失值不敏感。但其缺點是容易過擬合，對噪聲數(shù)據(jù)敏感，且在處理高維數(shù)據(jù)時可能會出現(xiàn)性能問題。決策樹模型適用于分類和回歸問題，尤其是在