2025年大學(xué)《信息與計(jì)算科學(xué)》專(zhuān)業(yè)題庫(kù)——信息與計(jì)算科學(xué)專(zhuān)業(yè)實(shí)踐活動(dòng)考試時(shí)間：______分鐘總分：______分姓名：______一、選擇題1.下列數(shù)據(jù)結(jié)構(gòu)中，最適合表示先進(jìn)先出（FIFO）特性的是？A.棧(Stack)B.隊(duì)列(Queue)C.鏈表(LinkedList)D.樹(shù)(Tree)2.設(shè)定一個(gè)算法的時(shí)間復(fù)雜度為O(nlogn)，下列哪個(gè)選項(xiàng)的時(shí)間復(fù)雜度可能低于O(nlogn)？A.O(n^2)B.O(nlogn)C.O(n^2logn)D.O(n)3.在排序算法中，快速排序在平均情況下的時(shí)間復(fù)雜度是？A.O(n)B.O(nlogn)C.O(n^2)D.O(logn)4.對(duì)于給定的無(wú)向圖G(V,E)，若要判斷圖G是否包含環(huán)，以下哪種數(shù)據(jù)結(jié)構(gòu)和算法組合通常效率較高？A.廣度優(yōu)先搜索(BFS)+鄰接矩陣B.深度優(yōu)先搜索(DFS)+鄰接表C.Dijkstra算法+鄰接矩陣D.Floyd-Warshall算法+鄰接表5.在面向?qū)ο缶幊讨?，封裝的主要目的是什么？A.提高代碼的重用性B.隱藏對(duì)象的內(nèi)部實(shí)現(xiàn)細(xì)節(jié)，提供公共接口C.提高代碼的執(zhí)行效率D.簡(jiǎn)化類(lèi)的繼承關(guān)系二、填空題6.在二叉搜索樹(shù)中，對(duì)于任何節(jié)點(diǎn)，其左子樹(shù)中所有節(jié)點(diǎn)的值都小于該節(jié)點(diǎn)的值，其右子樹(shù)中所有節(jié)點(diǎn)的值都大于該節(jié)點(diǎn)的值。這種特性稱(chēng)為_(kāi)_______性質(zhì)。7.算法的________是指算法執(zhí)行所需要的基本操作次數(shù)隨輸入規(guī)模n增長(zhǎng)的變化趨勢(shì)。8.在設(shè)計(jì)算法時(shí)，如果一個(gè)問(wèn)題可以分解為若干個(gè)相互獨(dú)立的子問(wèn)題，并且原問(wèn)題的解可以由各子問(wèn)題的解組合而成，這種算法設(shè)計(jì)方法通常稱(chēng)為_(kāi)_______技術(shù)。9.對(duì)于一個(gè)n階矩陣A，計(jì)算其所有元素之和，至少需要________次基本運(yùn)算（如加法或乘法）。10.在Python中，用于處理數(shù)據(jù)序列和數(shù)據(jù)的強(qiáng)大標(biāo)準(zhǔn)庫(kù)是________。三、判斷題11.()哈希表的平均查找時(shí)間復(fù)雜度可以達(dá)到O(1)。12.()冒泡排序是一種穩(wěn)定的排序算法。13.()遞歸算法一定比循環(huán)算法效率低。14.()在有向圖中，如果存在一條從頂點(diǎn)u到頂點(diǎn)v的路徑，那么一定存在一條從u到v的有向路徑。15.()類(lèi)和對(duì)象是面向?qū)ο缶幊讨械膬蓚€(gè)基本概念，類(lèi)是對(duì)象的實(shí)例。四、算法設(shè)計(jì)題編寫(xiě)一個(gè)算法，找出一個(gè)無(wú)重復(fù)元素的整數(shù)數(shù)組中的所有“三元組”（a,b,c），使得a+b+c等于一個(gè)給定的目標(biāo)值target。要求：輸出所有不同的三元組，且三元組內(nèi)的元素順序不同視為不同的組合（例如，(a,b,c)和(b,a,c)視為不同）。請(qǐng)描述你的算法思路，并用偽代碼或C/C++/Java/Python語(yǔ)言（選擇其中一種）實(shí)現(xiàn)該算法的核心部分（即找出所有三元組的代碼塊）。不需要考慮時(shí)間復(fù)雜度優(yōu)化，但要保證邏輯正確。五、編程實(shí)現(xiàn)題編寫(xiě)一個(gè)程序，實(shí)現(xiàn)以下功能：1.從標(biāo)準(zhǔn)輸入讀取一個(gè)正整數(shù)n（1≤n≤100），表示要處理的數(shù)字的個(gè)數(shù)。2.接著讀取n個(gè)浮點(diǎn)數(shù)，存儲(chǔ)在一個(gè)數(shù)組（或列表）中。3.計(jì)算并輸出這n個(gè)浮點(diǎn)數(shù)的平均值。4.找出數(shù)組中的最大值和最小值，并輸出它們及其在數(shù)組中的索引位置（如果多個(gè)相同，輸出第一個(gè)出現(xiàn)的索引）。5.對(duì)數(shù)組中的所有元素進(jìn)行升序排序，可以使用你前面在算法設(shè)計(jì)題中實(shí)現(xiàn)的三元組查找算法的排序部分（假設(shè)可用且適用于此場(chǎng)景，或直接使用內(nèi)置排序方法），然后輸出排序后的數(shù)組。要求：*使用結(jié)構(gòu)化的編程風(fēng)格。*代碼需包含必要的注釋?zhuān)f(shuō)明主要代碼塊的功能。*假設(shè)輸入數(shù)據(jù)格式正確。六、綜合應(yīng)用題假設(shè)你需要分析一組學(xué)生的考試成績(jī)數(shù)據(jù)。數(shù)據(jù)以如下格式給出：每行一個(gè)學(xué)生的記錄，包含學(xué)號(hào)（字符串）、姓名（字符串）和成績(jī)（浮點(diǎn)數(shù)，范圍0到100）。數(shù)據(jù)有多行，以特定的結(jié)束標(biāo)志（如"END"）表示數(shù)據(jù)結(jié)束。編寫(xiě)程序代碼，實(shí)現(xiàn)以下分析任務(wù)：1.讀取輸入數(shù)據(jù)，直到遇到"END"標(biāo)志。2.計(jì)算所有學(xué)生的平均成績(jī)，并輸出。3.找出成績(jī)最高的學(xué)生和成績(jī)最低的學(xué)生，輸出他們的姓名和成績(jī)。4.定義一個(gè)函數(shù)，用于計(jì)算成績(jī)?cè)诮o定分?jǐn)?shù)段（如90-100分）的學(xué)生比例，并在主程序中調(diào)用該函數(shù)，分析成績(jī)?cè)?0分以上的學(xué)生比例。5.將所有學(xué)生的成績(jī)按降序排列，并輸出排序后的學(xué)生列表（包含學(xué)號(hào)、姓名、成績(jī)）。注意：可以假設(shè)輸入數(shù)據(jù)是逐行提供的，例如通過(guò)文件讀取或標(biāo)準(zhǔn)輸入。在代碼中明確如何處理輸入結(jié)束。試卷答案一、選擇題1.B2.D3.B4.B5.B二、填空題6.二叉搜索7.時(shí)間復(fù)雜度8.分治9.n10.Pandas三、判斷題11.√12.√13.×14.√15.√四、算法設(shè)計(jì)題思路解析:該問(wèn)題為經(jīng)典的“三數(shù)之和”問(wèn)題。基本思路是固定一個(gè)數(shù)，然后使用雙指針?lè)ㄔ谑Ｓ嗟臄?shù)中尋找另外兩個(gè)數(shù)，使得它們的和加上固定數(shù)等于目標(biāo)值。具體步驟如下：1.對(duì)數(shù)組進(jìn)行排序（排序有助于使用雙指針）。2.遍歷排序后的數(shù)組，對(duì)于每個(gè)元素nums[i]，設(shè)置兩個(gè)指針：left指向i+1，right指向數(shù)組末尾。3.當(dāng)left<right時(shí)，計(jì)算當(dāng)前三數(shù)之和sum=nums[i]+nums[left]+nums[right]。*如果sum等于target，記錄下這個(gè)三元組，然后left右移，right左移，繼續(xù)尋找其他可能的三元組。*如果sum小于target，left右移，以增大sum。*如果sum大于target，right左移，以減小sum。4.避免重復(fù)：在遍歷和雙指針移動(dòng)過(guò)程中，需要跳過(guò)重復(fù)的元素，以避免輸出重復(fù)的三元組。偽代碼實(shí)現(xiàn):```functionfindThreeSum(nums,target):sort(nums)n=length(nums)forifrom0ton-3:ifi>0andnums[i]==nums[i-1]:continueleft=i+1right=n-1whileleft<right:current_sum=nums[i]+nums[left]+nums[right]ifcurrent_sum==target:output(nums[i],nums[left],nums[right])whileleft<rightandnums[left]==nums[left+1]:left=left+1whileleft<rightandnums[right]==nums[right-1]:right=right-1left=left+1right=right-1elseifcurrent_sum<target:left=left+1else:right=right-1#示例C++代碼核心部分#include<vector>#include<algorithm>#include<iostream>usingnamespacestd;voidfindThreeSum(vector<int>&nums,inttarget){sort(nums.begin(),nums.end());intn=nums.size();for(inti=0;i<n-2;++i){if(i>0&&nums[i]==nums[i-1])continue;intleft=i+1,right=n-1;while(left<right){intcurrent_sum=nums[i]+nums[left]+nums[right];if(current_sum==target){cout<<"("<<nums[i]<<","<<nums[left]<<","<<nums[right]<<")"<<endl;while(left<right&&nums[left]==nums[left+1])left++;while(left<right&&nums[right]==nums[right-1])right--;left++;right--;}elseif(current_sum<target)left++;elseright--;}}}```五、編程實(shí)現(xiàn)題思路解析:1.讀取輸入:使用標(biāo)準(zhǔn)輸入流讀取整數(shù)n，然后讀取n個(gè)浮點(diǎn)數(shù)，存儲(chǔ)在動(dòng)態(tài)數(shù)組或列表中。2.計(jì)算平均值:遍歷數(shù)組，累加所有元素，除以n得到平均值。3.找最大最小值及索引:初始化max_value為數(shù)組的第一個(gè)元素，min_value為數(shù)組的第一個(gè)元素，max_index=0,min_index=0。遍歷數(shù)組，更新max_value/min_value及其索引。4.排序:可以調(diào)用語(yǔ)言?xún)?nèi)置的排序函數(shù)（如Python的list.sort()或sorted()，C++的std::sort，Java的Collections.sort或Arrays.sort），也可以使用前面算法設(shè)計(jì)題中實(shí)現(xiàn)的三元組查找算法的排序部分（假設(shè)可用）。這里假設(shè)使用內(nèi)置排序。5.輸出結(jié)果:按照要求格式輸出平均值、最大值及其索引、最小值及其索引、排序后的數(shù)組。示例Python代碼核心部分:```pythonimportsys#讀取第一行，獲取ninput=sys.stdin.read().splitlines()n=int(input[0].strip())ifn<1orn>100:print("noutofrange")sys.exit()#讀取接下來(lái)的n行浮點(diǎn)數(shù)numbers=[]index=1foriinrange(n):line=input[index+i].strip()ifline=="":continue#忽略空行try:num=float(line)numbers.append(num)exceptValueError:print(f"Invalidnumberformat:{line}")sys.exit()#1.計(jì)算平均值total=sum(numbers)average=total/nprint(f"{average:.2f}")#2.找最大最小值及索引ifnotnumbers:print("Nonumberstoprocess.")sys.exit()max_value=numbers[0]min_value=numbers[0]max_index=0min_index=0foriinrange(n):ifnumbers[i]>max_value:max_value=numbers[i]max_index=iifnumbers[i]<min_value:min_value=numbers[i]min_index=iprint(f"{max_value:.2f}{max_index}")print(f"{min_value:.2f}{min_index}")#3.排序(使用內(nèi)置排序)numbers.sort()#4.輸出排序后的數(shù)組fornuminnumbers:print(f"{num:.2f}")```六、綜合應(yīng)用題思路解析:1.讀取數(shù)據(jù):循環(huán)讀取輸入，直到遇到"END"。對(duì)于每行，分割字符串獲取學(xué)號(hào)、姓名、成績(jī)，并將這些信息存儲(chǔ)在一個(gè)列表（或自定義對(duì)象）中。2.計(jì)算平均成績(jī):遍歷存儲(chǔ)學(xué)生信息的列表，累加所有學(xué)生的成績(jī)，計(jì)算平均值。3.找最高最低分學(xué)生:初始化最高分學(xué)生和最低分學(xué)生信息，遍歷列表，更新最高分和最低分學(xué)生。4.定義函數(shù)計(jì)算比例:定義一個(gè)函數(shù)`calculate_ratio(data,low_score,high_score)`，該函數(shù)接收學(xué)生數(shù)據(jù)列表和分?jǐn)?shù)段（low_score,high_score），遍歷列表統(tǒng)計(jì)在此分?jǐn)?shù)段內(nèi)的學(xué)生數(shù)量，計(jì)算并返回該比例。5.降序排序并輸出:根據(jù)成績(jī)對(duì)學(xué)生列表進(jìn)行降序排序（可以按成績(jī)字段排序），然后遍歷排序后的列表，輸出每個(gè)學(xué)生的學(xué)號(hào)、姓名、成績(jī)。示例Python代碼核心部分:```python#假設(shè)輸入通過(guò)標(biāo)準(zhǔn)輸入逐行提供importsysstudents=[]end_flag="END"#讀取輸入數(shù)據(jù)forlineinsys.stdin:line=line.strip()ifline==end_flag:breakparts=line.split()iflen(parts)!=3:print(f"Invalidstudentrecordformat:{line}")continuetry:student_id=parts[0]name=parts[1]score=float(parts[2])students.append({'id':student_id,'name':name,'score':score})exceptValueError:print(f"Invalidscoreformatinrecord:{line}")continue#1.計(jì)算平均成績(jī)ifnotstudents:print("Nostudentdataavailable.")sys.exit()total_score=sum(student['score']forstudentinstudents)average_score=total_score/len(students)print(f"{average_score:.2f}")#2.找最高最低分學(xué)生max_student=students[0]min_student=students[0]forstudentinstudents:ifstudent['score']>max