2025年大學(xué)《信息與計(jì)算科學(xué)》專業(yè)題庫(kù)——信息與計(jì)算科學(xué)專業(yè)實(shí)驗(yàn)室實(shí)踐教學(xué)指導(dǎo)考試時(shí)間：______分鐘總分：______分姓名：______一、選擇題（每小題2分，共10分）1.在單鏈表中，刪除一個(gè)非尾節(jié)點(diǎn)p時(shí)，需要找到其前驅(qū)節(jié)點(diǎn)q，然后執(zhí)行的操作是（）。A.q->next=p->next;deletep;B.q->data=p->data;deletep;C.p->next=q->next;deleteq;D.p->data=q->data;deleteq;2.對(duì)于給定的數(shù)據(jù)集{8,3,6,2,9,1}，使用快速排序（以第一個(gè)元素為基準(zhǔn)），第一次劃分后，基準(zhǔn)元素左側(cè)的子序列可能為（）。A.{8,3,6}B.{2,1}C.{3,2,1}D.{6,2,9}3.在二分查找算法中，查找成功或失敗時(shí)，比較次數(shù)（）。A.一定相同B.一定不同C.可能相同也可能不同D.取決于數(shù)據(jù)元素的數(shù)量4.數(shù)值計(jì)算中，用對(duì)角占優(yōu)或嚴(yán)格對(duì)角占優(yōu)的矩陣作為系數(shù)矩陣的線性方程組，其主要優(yōu)點(diǎn)是（）。A.計(jì)算速度快B.數(shù)值穩(wěn)定性好C.存儲(chǔ)空間小D.易于編程實(shí)現(xiàn)5.對(duì)一個(gè)包含n個(gè)頂點(diǎn)的無(wú)向連通圖進(jìn)行廣度優(yōu)先搜索（BFS），其遍歷序列唯一性（）。A.總是唯一B.總是唯一，當(dāng)且僅當(dāng)圖為樹(shù)C.可能不是唯一D.取決于起始頂點(diǎn)的選擇二、填空題（每空2分，共10分）1.在冒泡排序算法中，若要使得元素按從小到大排列，每次遍歷數(shù)組時(shí)，應(yīng)將當(dāng)前未排序部分中相對(duì)靠后的較大元素“______”到前面去。2.給定線性方程組Ax=b，其中系數(shù)矩陣A為3階方陣，若其行簡(jiǎn)化階梯形矩陣有2個(gè)零行，則該方程組解的情況是______。3.使用插值方法擬合一組離散數(shù)據(jù)點(diǎn)，其主要目的是通過(guò)已知數(shù)據(jù)點(diǎn)構(gòu)造一個(gè)函數(shù)，使得該函數(shù)在數(shù)據(jù)點(diǎn)處取得______，并在這些點(diǎn)之間提供連續(xù)（或光滑）的估計(jì)。4.在RSA公鑰密碼體制中，選擇兩個(gè)大素?cái)?shù)p和q，計(jì)算它們的乘積n=p*q，n被稱為_(kāi)_____。5.計(jì)算機(jī)浮點(diǎn)數(shù)表示中，由于精度限制，一個(gè)數(shù)可能存在多個(gè)______表示。三、簡(jiǎn)答題（每題5分，共15分）1.簡(jiǎn)述線性表兩種基本存儲(chǔ)結(jié)構(gòu)（順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)）的主要區(qū)別。2.什么是算法的時(shí)間復(fù)雜度？簡(jiǎn)述其常用的表示方法（大O表示法）。3.在進(jìn)行數(shù)值積分時(shí)，為什么通常需要考慮積分步長(zhǎng)或區(qū)間劃分？過(guò)大的步長(zhǎng)或過(guò)小的步長(zhǎng)各可能帶來(lái)什么問(wèn)題？四、編程題（每題15分，共30分）1.編寫一個(gè)函數(shù)，實(shí)現(xiàn)單鏈表的反轉(zhuǎn)。函數(shù)的輸入?yún)?shù)為指向單鏈表頭節(jié)點(diǎn)的指針，函數(shù)的輸出參數(shù)為指向反轉(zhuǎn)后單鏈表頭節(jié)點(diǎn)的指針。（假設(shè)鏈表節(jié)點(diǎn)定義如下：structNode{intdata;Node*next;}）2.編寫一個(gè)函數(shù)，實(shí)現(xiàn)快速排序算法。函數(shù)的輸入?yún)?shù)為一個(gè)整數(shù)數(shù)組`arr`和兩個(gè)整數(shù)`low`,`high`，表示排序的區(qū)間（`arr[low]`到`arr[high]`）。函數(shù)不需要返回值，但需在輸入數(shù)組`arr`上完成排序。（提示：可參考快速排序的劃分過(guò)程）五、分析題（每題10分，共20分）1.假設(shè)你要設(shè)計(jì)一個(gè)簡(jiǎn)單的圖書(shū)管理系統(tǒng)，需要存儲(chǔ)圖書(shū)信息（書(shū)號(hào)、書(shū)名、作者、價(jià)格）。請(qǐng)簡(jiǎn)述若使用數(shù)組存儲(chǔ)1000本圖書(shū)信息，在需要根據(jù)書(shū)號(hào)快速查找某本書(shū)時(shí)，你會(huì)選擇哪種數(shù)據(jù)結(jié)構(gòu)（不考慮排序），并說(shuō)明理由。2.在進(jìn)行科學(xué)實(shí)驗(yàn)測(cè)量時(shí)，得到一組數(shù)據(jù)：[10.2,10.5,10.3,10.7,10.4]。若已知真實(shí)值約為10.0，請(qǐng)計(jì)算這組數(shù)據(jù)的平均值、標(biāo)準(zhǔn)差，并簡(jiǎn)單說(shuō)明標(biāo)準(zhǔn)差反映了數(shù)據(jù)的什么特性。---試卷答案一、選擇題1.A2.C3.A4.B5.C二、填空題1.移動(dòng)2.無(wú)窮多解3.準(zhǔn)確值4.模數(shù)（Modulus）5.近似值（或等價(jià)表示）三、簡(jiǎn)答題1.順序存儲(chǔ)：所有元素存儲(chǔ)在連續(xù)的內(nèi)存空間，通過(guò)下標(biāo)訪問(wèn)元素，插入和刪除操作（尤其是在中間位置）可能需要移動(dòng)大量元素。鏈?zhǔn)酱鎯?chǔ)：元素存儲(chǔ)在節(jié)點(diǎn)中，節(jié)點(diǎn)通過(guò)指針相連，不要求連續(xù)內(nèi)存空間，插入和刪除操作相對(duì)方便（只需修改指針），但訪問(wèn)元素需要從頭節(jié)點(diǎn)逐個(gè)遍歷，且需要額外的存儲(chǔ)空間存儲(chǔ)指針。2.算法的時(shí)間復(fù)雜度是描述算法執(zhí)行時(shí)間隨輸入規(guī)模增長(zhǎng)而變化趨勢(shì)的度量。它關(guān)注的是算法執(zhí)行基本操作（如比較、賦值）的次數(shù)，并使用大O表示法（OrderofGrowth）給出一個(gè)上界，忽略常數(shù)項(xiàng)和低階項(xiàng)，以反映算法在規(guī)模增大時(shí)的增長(zhǎng)速率。例如，冒泡排序的時(shí)間復(fù)雜度為O(n^2)，快速排序平均情況為O(nlogn)。3.考慮積分步長(zhǎng)或區(qū)間劃分是因?yàn)閿?shù)值積分方法（如梯形法則、辛普森法則）通常需要將積分區(qū)間分割成多個(gè)小區(qū)間，在每個(gè)小區(qū)間上應(yīng)用插值或求和公式來(lái)近似整個(gè)區(qū)間的積分。過(guò)大的步長(zhǎng)可能導(dǎo)致精度不足，無(wú)法準(zhǔn)確捕捉被積函數(shù)的局部特征，造成較大誤差。過(guò)小的步長(zhǎng)雖然能提高精度，但會(huì)增加計(jì)算量，可能導(dǎo)致舍入誤差累積，反而使結(jié)果不準(zhǔn)確，且計(jì)算效率低下。四、編程題1.//函數(shù)聲明：Node*reverseList(Node*head)//思路：使用迭代法反轉(zhuǎn)單鏈表。設(shè)置三個(gè)指針：prev為空，current為head，next為臨時(shí)指針。//遍歷鏈表：在訪問(wèn)當(dāng)前節(jié)點(diǎn)current之前，保存下一個(gè)節(jié)點(diǎn)next=current->next。//反轉(zhuǎn)鏈接：將當(dāng)前節(jié)點(diǎn)的next指向前一個(gè)節(jié)點(diǎn)：current->next=prev。//移動(dòng)指針：更新prev為當(dāng)前節(jié)點(diǎn)current，current為下一個(gè)節(jié)點(diǎn)next，繼續(xù)遍歷。//結(jié)束條件：當(dāng)current為空時(shí)，prev即為反轉(zhuǎn)后的頭節(jié)點(diǎn)。Node*reverseList(Node*head){Node*prev=nullptr;Node*current=head;Node*next=nullptr;while(current!=nullptr){next=current->next;//保存下一個(gè)節(jié)點(diǎn)current->next=prev;//反轉(zhuǎn)當(dāng)前節(jié)點(diǎn)的指針prev=current;//移動(dòng)prev到當(dāng)前節(jié)點(diǎn)current=next;//移動(dòng)current到下一個(gè)節(jié)點(diǎn)}returnprev;//prev成為新的頭節(jié)點(diǎn)}2.//函數(shù)聲明：voidquickSort(intarr[],intlow,inthigh)//思路：實(shí)現(xiàn)快速排序。核心是劃分（Partition）操作和遞歸。劃分操作選擇一個(gè)基準(zhǔn)元素（pivot），重新排列數(shù)組，使得基準(zhǔn)元素左邊的所有元素都不大于它，右邊的所有元素都不小于它，最終返回基準(zhǔn)元素的最終位置。遞歸地對(duì)基準(zhǔn)元素左右兩邊的子數(shù)組進(jìn)行快速排序。voidquickSort(intarr[],intlow,inthigh){if(low<high){//調(diào)用劃分函數(shù)，獲取基準(zhǔn)元素的最終位置pivotintpivot=partition(arr,low,high);//遞歸排序基準(zhǔn)元素左邊的子數(shù)組quickSort(arr,low,pivot-1);//遞歸排序基準(zhǔn)元素右邊的子數(shù)組quickSort(arr,pivot+1,high);}}//劃分函數(shù)輔助實(shí)現(xiàn)intpartition(intarr[],intlow,inthigh){intpivot=arr[high];//選擇最后一個(gè)元素作為基準(zhǔn)inti=low-1;//i指向小于基準(zhǔn)的元素的最后一個(gè)for(intj=low;j<high;j++){if(arr[j]<=pivot){//發(fā)現(xiàn)小于等于基準(zhǔn)的元素i++;//i向后移動(dòng)swap(&arr[i],&arr[j]);//交換arr[i]和arr[j]}}swap(&arr[i+1],&arr[high]);//將基準(zhǔn)元素交換到正確的位置returni+1;//返回基準(zhǔn)元素的最終索引}//輔助交換函數(shù)voidswap(int*a,int*b){inttemp=*a;*a=*b;*b=temp;}五、分析題1.選擇數(shù)據(jù)結(jié)構(gòu)：哈希表（或哈希映射）。//理由：哈希表通過(guò)計(jì)算書(shū)號(hào)的哈希值來(lái)確定存儲(chǔ)位置，可以實(shí)現(xiàn)平均情況下接近O(1)的查找時(shí)間復(fù)雜度。對(duì)于根據(jù)書(shū)號(hào)快速查找的需求，哈希表提供了極高的效率，遠(yuǎn)優(yōu)于順序訪問(wèn)數(shù)組（O(n)）或二分查找（O(logn)，前提是數(shù)組已排序）。即使不考慮排序，哈希表也能直接通過(guò)鍵（書(shū)號(hào)）快速定位到數(shù)據(jù)。當(dāng)然，需要考慮哈希函數(shù)的設(shè)計(jì)、沖突處理以及哈希表的負(fù)載因子問(wèn)題。2.計(jì)算平均值：平均值=(10.2+10.5+10.3+10.7+10.4)/5=52.1/5=10.42計(jì)算標(biāo)準(zhǔn)差：a.計(jì)算各數(shù)據(jù)與平均值的差的平方：(10.2-10.42)^2=(-0.22)^2=0.0484(10.5-10.42)^2=(0.08)^2=0.0064(10.3-10.42)^2=(-0.12)^2=0.0144(10.7-10.42)^2=(0.28)^2=0.0784(10.4-10.42)^2=(-0.02)^2=0.0004b.計(jì)算這些平方差的平均值（方差）：方差s^2=(0.0484+0.0064+0.0144+