2025年大學(xué)《信息與計(jì)算科學(xué)》專(zhuān)業(yè)題庫(kù)——信息與計(jì)算科學(xué)專(zhuān)業(yè)實(shí)驗(yàn)技術(shù)培訓(xùn)計(jì)劃考試時(shí)間：______分鐘總分：______分姓名：______一、選擇題（每小題2分，共20分）1.下列數(shù)據(jù)結(jié)構(gòu)中，適合表示稀疏矩陣的是（）。A.順序表B.鏈隊(duì)列C.稀疏矩陣壓縮存儲(chǔ)（三元組表）D.完全二叉樹(shù)2.設(shè)有排序序列{12,38,25,87,94,69,75,32}，若采用快速排序，則進(jìn)行第一輪劃分后，基準(zhǔn)元素左邊的序列可能為（）。A.{12,38,25,87,94,69,75,32}B.{32,25,12,38,87,94,69,75}C.{38,87,94,69,75,32,25,12}D.{87,94,69,75,32,25,12,38}3.在關(guān)系數(shù)據(jù)庫(kù)中，“選擇”操作對(duì)應(yīng)于關(guān)系中的（）。A.排序B.連接C.投影D.查詢4.下列關(guān)于算法時(shí)間復(fù)雜度T(n)=O(f(n))的說(shuō)法中，正確的是（）。A.算法執(zhí)行時(shí)間隨問(wèn)題規(guī)模n的增長(zhǎng)而無(wú)限增長(zhǎng)B.算法執(zhí)行時(shí)間隨問(wèn)題規(guī)模n的增長(zhǎng)有界C.算法執(zhí)行次數(shù)正好是f(n)D.算法執(zhí)行次數(shù)小于f(n)5.若向量線性相關(guān)，則下列說(shuō)法中錯(cuò)誤的是（）。A.其中至少有一個(gè)向量可以用其余向量線性表示B.其秩小于向量的個(gè)數(shù)C.加減任意向量后仍然線性相關(guān)D.其行列式（若為方陣）為零6.在以下數(shù)據(jù)結(jié)構(gòu)中，插入和刪除操作最有效率的是（）。A.順序表B.雙向鏈表C.堆棧D.隊(duì)列7.設(shè)有函數(shù)`voidfun(int*arr,intn)`，其中`arr`是一個(gè)整型數(shù)組，`n`是數(shù)組的長(zhǎng)度。若調(diào)用`fun(a,5)`，則關(guān)于`arr`的說(shuō)法正確的是（）。A.`arr`代表一個(gè)長(zhǎng)度為5的整型數(shù)組B.`arr`是一個(gè)指向整型變量的指針C.`arr`中存儲(chǔ)的是數(shù)組`a`的地址D.需要事先知道數(shù)組`a`的地址8.下列關(guān)于遞歸函數(shù)的說(shuō)法中，錯(cuò)誤的是（）。A.遞歸函數(shù)必須調(diào)用自身B.遞歸函數(shù)必須有一個(gè)明確的終止條件C.遞歸函數(shù)可以提高代碼的可讀性D.遞歸函數(shù)總是比循環(huán)結(jié)構(gòu)更有效率9.在計(jì)算機(jī)中，浮點(diǎn)數(shù)0.15625用二進(jìn)制科學(xué)計(jì)數(shù)法表示為（）。A.1.1101×2^(-4)B.1.101×2^(-3)C.0.1101×2^(-2)D.1.101×2^(-5)10.下列關(guān)于操作系統(tǒng)進(jìn)程狀態(tài)的描述中，錯(cuò)誤的是（）。A.就緒態(tài)：進(jìn)程已準(zhǔn)備好運(yùn)行，等待CPU調(diào)度B.運(yùn)行態(tài)：進(jìn)程正在占用CPU執(zhí)行C.等待態(tài)：進(jìn)程因等待某個(gè)事件（如I/O）而暫停執(zhí)行D.創(chuàng)建態(tài)：進(jìn)程正在被創(chuàng)建，尚未進(jìn)入就緒隊(duì)列二、填空題（每空2分，共20分）1.在深度為k的二叉樹(shù)中，最多有______個(gè)結(jié)點(diǎn)。2.對(duì)于一個(gè)具有n個(gè)頂點(diǎn)的無(wú)向圖，其邊數(shù)最多為_(kāi)_____。3.算法的空間復(fù)雜度是指算法執(zhí)行過(guò)程中臨時(shí)占用的存儲(chǔ)空間的大小，其時(shí)間復(fù)雜度通常用______表示。4.在關(guān)系代數(shù)中，從關(guān)系中選擇滿足給定條件的元組的操作稱為_(kāi)_____。5.若一個(gè)向量組包含零向量，則該向量組一定______。6.冒泡排序在最壞情況下的時(shí)間復(fù)雜度為_(kāi)_____。7.在C語(yǔ)言中，用于動(dòng)態(tài)分配內(nèi)存的函數(shù)是______和______。8.數(shù)據(jù)的壓縮編碼方法可以分為無(wú)損壓縮和有損壓縮兩種，其中______壓縮能完全恢復(fù)原始數(shù)據(jù)。9.在隊(duì)列中，元素插入的一端稱為_(kāi)_____端，刪除的一端稱為_(kāi)_____端。10.計(jì)算機(jī)網(wǎng)絡(luò)按照覆蓋范圍可以分為局域網(wǎng)（LAN）、城域網(wǎng)（MAN）和______。三、判斷題（每小題2分，共10分）1.線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)優(yōu)于順序存儲(chǔ)結(jié)構(gòu)，因?yàn)殒湵砜梢詫?shí)現(xiàn)隨機(jī)訪問(wèn)。（）2.在快速排序中，每次劃分都能將基準(zhǔn)元素放到它最終排序的位置上。（）3.關(guān)系數(shù)據(jù)庫(kù)中的視圖是基于基本表建立的虛表。（）4.任何遞歸函數(shù)都可以用循環(huán)結(jié)構(gòu)來(lái)改寫(xiě)。（）5.堆排序是一種基于堆數(shù)據(jù)結(jié)構(gòu)的效率很高的排序算法，它的平均時(shí)間復(fù)雜度和最壞時(shí)間復(fù)雜度都是O(nlogn)。（）四、簡(jiǎn)答題（每小題5分，共20分）1.簡(jiǎn)述棧和隊(duì)列的主要區(qū)別。2.解釋什么是算法的“時(shí)間復(fù)雜度”和“空間復(fù)雜度”。3.什么是數(shù)據(jù)庫(kù)的“規(guī)范化”？規(guī)范化有什么好處？4.簡(jiǎn)述冒泡排序算法的基本思想。五、編程題（共30分）1.（15分）編寫(xiě)一個(gè)C語(yǔ)言函數(shù)，實(shí)現(xiàn)查找數(shù)組`intarr[]={8,3,6,2,9,1,5,4,7}`中最大元素的下標(biāo)，并將該下標(biāo)通過(guò)指針參數(shù)返回。函數(shù)原型如下：`voidfindMaxIndex(intarr[],intn,int*index);`在主函數(shù)中調(diào)用該函數(shù)，輸出最大元素的下標(biāo)。2.（15分）編寫(xiě)一個(gè)Python函數(shù)，實(shí)現(xiàn)將一個(gè)非負(fù)整數(shù)`num`轉(zhuǎn)換為其二進(jìn)制表示的字符串，不使用Python內(nèi)置的`bin()`函數(shù)。函數(shù)原型如下：`defintToBinaryString(num):`示例：調(diào)用`intToBinaryString(13)`應(yīng)返回字符串`'1101'`。六、數(shù)學(xué)題（共20分）1.（10分）計(jì)算行列式D的值：```123D=|456|789```2.（10分）設(shè)向量α=(1,2,3),β=(0,1,1)。求向量α+β和α·β(向量點(diǎn)積)。---試卷答案一、選擇題1.C解析：稀疏矩陣壓縮存儲(chǔ)（如三元組表）能有效節(jié)省存儲(chǔ)空間，適用于稀疏矩陣表示。2.B解析：快速排序以基準(zhǔn)元素（通常取第一個(gè)元素）進(jìn)行劃分，基準(zhǔn)元素左邊的序列包含所有小于基準(zhǔn)的元素。選項(xiàng)B{32,25,12,38,87,94,69,75}中，32,25,12都小于38。3.D解析：“選擇”操作在關(guān)系代數(shù)中對(duì)應(yīng)于對(duì)關(guān)系（表）進(jìn)行條件篩選，提取滿足特定條件的元組。4.B解析：時(shí)間復(fù)雜度O(f(n))描述的是算法執(zhí)行時(shí)間隨問(wèn)題規(guī)模n增長(zhǎng)的增長(zhǎng)趨勢(shì)，表示執(zhí)行時(shí)間有界，但不一定無(wú)限增長(zhǎng)。5.C解析：向量線性相關(guān)意味著存在不全為零的系數(shù)，使得這些向量的線性組合為零向量。加減任意一個(gè)非零向量會(huì)改變向量組，不一定保持線性相關(guān)。6.B解析：雙向鏈表在鏈表任意位置進(jìn)行插入或刪除操作，只需修改相鄰節(jié)點(diǎn)的指針，平均時(shí)間復(fù)雜度為O(1)。順序表插入刪除需移動(dòng)元素，平均時(shí)間復(fù)雜度為O(n)。7.C解析：在函數(shù)調(diào)用`fun(a,5)`中，`arr`是一個(gè)指針，它接收的是主調(diào)函數(shù)中數(shù)組`a`的首地址。8.D解析：遞歸函數(shù)不總是比循環(huán)結(jié)構(gòu)更有效率。遞歸可能導(dǎo)致函數(shù)調(diào)用棧過(guò)深，且存在重復(fù)計(jì)算，有時(shí)循環(huán)結(jié)構(gòu)更優(yōu)。9.A解析：將0.15625轉(zhuǎn)換為二進(jìn)制：0.15625=1*(2^-1)+1*(2^-2)+0*(2^-3)+1*(2^-4)=1.101×2^(-3)，再調(diào)整為科學(xué)計(jì)數(shù)法1.1101×2^(-4)。10.D解析：創(chuàng)建態(tài)是指進(jìn)程正在被創(chuàng)建的過(guò)程中，尚未成為操作系統(tǒng)管理的獨(dú)立進(jìn)程。進(jìn)程的狀態(tài)通常是在就緒、運(yùn)行、等待之間轉(zhuǎn)換。二、填空題1.2^(k+1)-1解析：根據(jù)二叉樹(shù)性質(zhì)，深度為k的二叉樹(shù)最多有2^(k+1)-1個(gè)結(jié)點(diǎn)。2.n*(n-1)/2解析：無(wú)向圖邊是雙向的，完全無(wú)向圖包含所有可能的頂點(diǎn)對(duì)，邊數(shù)為組合數(shù)C(n,2)=n*(n-1)/2。3.大O表示法(或用BigOnotation)解析：算法復(fù)雜度通常用大O表示法（BigOnotation）來(lái)描述其增長(zhǎng)趨勢(shì)，忽略常數(shù)項(xiàng)和低階項(xiàng)。4.選擇(Selection)解析：關(guān)系代數(shù)中的選擇操作對(duì)應(yīng)于SQL中的`WHERE`子句，用于從關(guān)系中選出滿足特定條件的元組。5.線性相關(guān)(Linearlydependent)解析：包含零向量的向量組，零向量可以看作是其他向量（系數(shù)為0）的線性組合，因此該組向量線性相關(guān)。6.O(n^2)解析：冒泡排序最壞情況發(fā)生在數(shù)組完全逆序時(shí)，需要進(jìn)行n*(n-1)/2次比較和交換，時(shí)間復(fù)雜度為O(n^2)。7.malloc,free解析：在C語(yǔ)言中，`malloc`用于動(dòng)態(tài)分配內(nèi)存，`free`用于釋放先前分配的內(nèi)存。8.無(wú)損壓縮(Losslesscompression)解析：無(wú)損壓縮算法在壓縮數(shù)據(jù)后，能夠通過(guò)解壓縮算法完全恢復(fù)原始數(shù)據(jù)，沒(méi)有信息損失。9.頭(Front),尾(Rear)解析：在隊(duì)列這種先進(jìn)先出（FIFO）結(jié)構(gòu)中，元素從頭部入隊(duì)，從尾部出隊(duì)。10.廣域網(wǎng)(WAN)解析：計(jì)算機(jī)網(wǎng)絡(luò)按覆蓋范圍分為局域網(wǎng)(LAN)、城域網(wǎng)(MAN)和廣域網(wǎng)(WAN)。三、判斷題1.錯(cuò)誤解析：鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)通過(guò)指針實(shí)現(xiàn)，插入刪除效率高（O(1)），但無(wú)法像順序表那樣進(jìn)行隨機(jī)訪問(wèn)（O(n)）。順序表支持隨機(jī)訪問(wèn)，但不擅長(zhǎng)插入刪除。2.正確解析：快速排序的單次劃分過(guò)程就是將基準(zhǔn)元素與其最終排序位置兩邊的元素分開(kāi)，基準(zhǔn)元素最終停留在其排序后的正確位置。3.正確解析：視圖是數(shù)據(jù)庫(kù)中基于一個(gè)或多個(gè)基本表（或其他視圖）創(chuàng)建的虛表，不存儲(chǔ)數(shù)據(jù)本身，查詢視圖時(shí)仍是對(duì)底層數(shù)據(jù)進(jìn)行操作。4.正確解析：遞歸函數(shù)通?？梢酝ㄟ^(guò)引入循環(huán)和棧來(lái)模擬，將遞歸調(diào)用轉(zhuǎn)換為循環(huán)迭代。雖然實(shí)現(xiàn)可能更復(fù)雜，但理論上是等價(jià)的。5.正確解析：堆排序依賴于堆這種數(shù)據(jù)結(jié)構(gòu)。建堆過(guò)程時(shí)間復(fù)雜度為O(n)，調(diào)整堆和排序過(guò)程總時(shí)間復(fù)雜度為O(nlogn)。其最壞、平均時(shí)間復(fù)雜度均為O(nlogn)。四、簡(jiǎn)答題1.答：棧是先進(jìn)后出（LIFO）的數(shù)據(jù)結(jié)構(gòu)，只允許在棧頂進(jìn)行插入和刪除操作；隊(duì)列是先進(jìn)先出（FIFO）的數(shù)據(jù)結(jié)構(gòu)，允許在隊(duì)尾插入（enqueue），在隊(duì)頭刪除（dequeue）。2.答：時(shí)間復(fù)雜度描述算法執(zhí)行時(shí)間隨輸入規(guī)模n增長(zhǎng)的變化趨勢(shì)，通常用大O表示法；空間復(fù)雜度描述算法執(zhí)行過(guò)程中臨時(shí)占用的存儲(chǔ)空間大小，也用大O表示法。3.答：數(shù)據(jù)庫(kù)規(guī)范化是消除關(guān)系模式中數(shù)據(jù)冗余和異常，將關(guān)系模式分解為多個(gè)滿足特定范式的子模式（關(guān)系）的過(guò)程。好處包括：減少數(shù)據(jù)冗余，節(jié)省存儲(chǔ)空間；避免更新異常（插入、刪除、修改異常）；保證數(shù)據(jù)一致性；簡(jiǎn)化數(shù)據(jù)查詢。4.答：冒泡排序的基本思想是：通過(guò)比較相鄰元素的值，將較大的元素逐步“冒泡”到數(shù)組的后面（或前面）。具體步驟通常是從數(shù)組第一個(gè)元素開(kāi)始，依次比較相鄰兩個(gè)元素，若順序錯(cuò)誤（如前大后?。?，則交換它們的位置；每一輪比較可以將當(dāng)前未排序部分的最大元素移動(dòng)到其最終位置。重復(fù)此過(guò)程，直到?jīng)]有需要交換的元素，排序完成。五、編程題1.```cvoidfindMaxIndex(intarr[],intn,int*index){if(n<=0||index==NULL)return;*index=0;for(inti=1;i<n;i++){if(arr[i]>arr[*index]){*index=i;}}}//在主函數(shù)中調(diào)用示例：//intarr[]={8,3,6,2,9,1,5,4,7};//intn=sizeof(arr)/sizeof(arr[0]);//intmaxIndex;//findMaxIndex(arr,n,&maxIndex);//printf("Maxelementindex:%d\n",maxIndex);```2.```pythondefintToBinaryString(num):ifnum==0:return"0"binary_str=""whilenum>0:remainder=num%2binary_str=str(remainder)+binary_strnum=num//2returnbinary_str#示例調(diào)用：#print(