2025年大學(xué)計算機(jī)程序設(shè)計試卷及答案一、單項(xiàng)選擇題（每題2分，共20分）1.以下關(guān)于C++指針的描述中，正確的是（）。A.指針變量存儲的是對象的值B.空指針（nullptr）可以解引用C.指向數(shù)組的指針進(jìn)行+1操作時，移動的字節(jié)數(shù)等于數(shù)組元素類型的大小D.指針數(shù)組與數(shù)組指針的定義完全相同2.Python中，執(zhí)行以下代碼后，輸出結(jié)果是（）。```pythondeff(x):return[lambday:yiforiinx]res=f([1,2,3])print([func(2)forfuncinres])```A.[2,4,6]B.[6,6,6]C.[2,2,2]D.[3,3,3]3.對長度為n的有序數(shù)組進(jìn)行二分查找，最壞情況下的時間復(fù)雜度為（）。A.O(n)B.O(nlogn)C.O(logn)D.O(n2)4.已知某二叉樹的后序遍歷序列為DABEC，中序遍歷序列為DEBAC，則該二叉樹的前序遍歷序列為（）。A.CEDBAB.ACBEDC.DECABD.ECDAB5.以下哈希沖突解決方法中，屬于開放定址法的是（）。A.鏈地址法B.再哈希法C.公共溢出區(qū)法D.雙哈希法6.遞歸函數(shù)計算斐波那契數(shù)列F(n)=F(n-1)+F(n-2)（F(0)=0,F(1)=1）時，計算F(5)需要調(diào)用函數(shù)的次數(shù)為（）。A.9次B.15次C.19次D.25次7.動態(tài)規(guī)劃解決最長公共子序列（LCS）問題時，若兩個序列長度分別為m和n，則狀態(tài)表的大小為（）。A.m×nB.(m+1)×(n+1)C.2^(m+n)D.max(m,n)8.無向圖的鄰接矩陣中，若存在i到j(luò)的邊，則矩陣中元素G[i][j]和G[j][i]的值（）。A.一定相等B.一定不相等C.可能相等D.無法確定9.C++中，關(guān)于虛函數(shù)的描述錯誤的是（）。A.虛函數(shù)可以在子類中被重寫B(tài).含有純虛函數(shù)的類是抽象類C.虛函數(shù)的調(diào)用在編譯時確定（靜態(tài)綁定）D.基類指針指向子類對象時，通過指針調(diào)用虛函數(shù)會執(zhí)行子類的實(shí)現(xiàn)10.Python提供器（generator）的主要優(yōu)點(diǎn)是（）。A.提高代碼運(yùn)行速度B.減少內(nèi)存占用C.支持多線程D.強(qiáng)制類型檢查二、填空題（每題3分，共15分）1.補(bǔ)全C++代碼，實(shí)現(xiàn)單鏈表逆置。假設(shè)鏈表節(jié)點(diǎn)定義為：```cppstructListNode{intval;ListNodenext;ListNode(intx):val(x),next(nullptr){}};```逆置函數(shù)部分代碼如下：```cppListNodereverseList(ListNodehead){ListNodeprev=nullptr,curr=head;while(curr!=nullptr){ListNodenextTemp=curr->next;curr->next=prev;prev=curr;curr=nextTemp;}return______;}```2.歸并排序?qū)﹂L度為8的數(shù)組進(jìn)行排序時，遞歸調(diào)用的總次數(shù)為______（包括最頂層調(diào)用）。3.若二叉樹的前序遍歷序列為ABCDE，后序遍歷序列為CDEBA，則該二叉樹的形態(tài)______（填“能”或“不能”）唯一確定。4.補(bǔ)全Python代碼，實(shí)現(xiàn)大根堆的調(diào)整函數(shù)（siftdown）。假設(shè)堆存儲為列表heap，當(dāng)前需要調(diào)整的節(jié)點(diǎn)索引為i，堆的大小為n：```pythondefsift_down(heap,i,n):largest=ileft=2i+1right=2i+2ifleft<nandheap[left]>heap[largest]:largest=leftifright<nandheap[right]>heap[largest]:largest=rightiflargest!=i:heap[i],heap[largest]=heap[largest],heap[i]______```5.字符串"abacab"的KMP算法部分匹配表（部分匹配值數(shù)組）為______（按順序?qū)懗雒總€字符對應(yīng)的部分匹配值）。三、編程題（共65分）1.（20分）給定一個由括號和其他字符組成的字符串s，找出其中最長的有效括號子串的長度。有效括號子串需滿足：①括號正確匹配（每個左括號有對應(yīng)的右括號，且順序正確）；②子串連續(xù)，其他字符不影響匹配。例如，輸入s="a(bc)d)ef(gh)"，最長有效子串為"(bc)"，長度為3；輸入s=")()())"，最長有效子串為"()()"，長度為4。要求用C++實(shí)現(xiàn)，時間復(fù)雜度O(n)。2.（25分）設(shè)計一個算法，計算無向圖中兩個節(jié)點(diǎn)之間的所有簡單路徑（路徑中無重復(fù)節(jié)點(diǎn)）。輸入為鄰接表表示的圖（節(jié)點(diǎn)用整數(shù)標(biāo)識）、起始節(jié)點(diǎn)start和終止節(jié)點(diǎn)end，輸出所有簡單路徑的列表（路徑按節(jié)點(diǎn)順序存儲為列表，順序不限）。例如，輸入鄰接表{0:[1,2],1:[0,3],2:[0,3],3:[1,2]}，start=0，end=3，輸出應(yīng)為[[0,1,3],[0,2,3]]。要求用Python實(shí)現(xiàn)，遞歸或回溯法。3.（20分）給定一個整數(shù)數(shù)組nums和目標(biāo)值target，找出兩個不重疊的子數(shù)組（子數(shù)組指連續(xù)元素），使得它們的和均為target，且兩個子數(shù)組的長度之和最小。若不存在這樣的兩個子數(shù)組，返回-1。例如，輸入nums=[1,2,3,4,5]，target=7，可能的子數(shù)組組合有[1,2,4]（和為7，長度3）與[3,4]（和為7，長度2），但需不重疊，故最小長度和為3+2=5；輸入nums=[-1,3,1,-3,2]，target=3，可能的組合有[3]（長度1）與[1,-3,2]（長度3），或[3,1,-3,2]（和為3，長度4）與無，故最小長度和為1+3=4。要求用動態(tài)規(guī)劃或滑動窗口方法，C++或Python實(shí)現(xiàn)。答案一、單項(xiàng)選擇題1.C2.B3.C4.A5.B6.B7.B8.A9.C10.B二、填空題1.prev2.15（歸并排序遞歸次數(shù)為2n-1，n=8時為15）3.不能（前序和后序無法唯一確定二叉樹結(jié)構(gòu)，可能存在不同形態(tài)）4.sift_down(heap,largest,n)5.[0,0,1,0,1,2]（部分匹配值為最長相等前綴后綴的長度，"a"→0；"ab"→0；"aba"→1（前綴"a"和后綴"a"）；"abac"→0；"abaca"→1（前綴"a"和后綴"a"）；"abacab"→2（前綴"ab"和后綴"ab"））三、編程題1.C++實(shí)現(xiàn)：```cppinclude<string>include<stack>usingnamespacestd;intlongestValidParentheses(strings){stack<int>stk;stk.push(-1);//初始棧底為-1，處理邊界intmaxLen=0;for(inti=0;i<s.size();++i){if(s[i]=='('){stk.push(i);}else{stk.pop();if(stk.empty()){stk.push(i);//無效右括號，更新棧底}else{maxLen=max(maxLen,istk.top());}}}returnmaxLen;}```解析：使用棧記錄未匹配的左括號索引，初始棧底為-1處理邊界。遍歷字符串，遇到左括號壓棧，遇到右括號彈棧后，若棧非空則計算當(dāng)前索引與棧頂?shù)牟睿ㄓ行чL度），更新最大值。時間復(fù)雜度O(n)。2.Python實(shí)現(xiàn)：```pythondeffind_all_paths(graph,start,end):paths=[]defbacktrack(current_path,visited):ifcurrent_path[-1]==end:paths.append(current_path.copy())returnforneighboringraph[current_path[-1]]:ifneighbornotinvisited:visited.add(neighbor)current_path.append(neighbor)backtrack(current_path,visited)current_path.pop()visited.remove(neighbor)visited=set([start])backtrack([start],visited)returnpaths```解析：回溯法遍歷所有可能路徑。使用visited集合記錄已訪問節(jié)點(diǎn)避免重復(fù)，current_path記錄當(dāng)前路徑。當(dāng)路徑末尾為end時，將路徑加入結(jié)果列表。時間復(fù)雜度取決于路徑數(shù)量，最壞為O(n!)（n為節(jié)點(diǎn)數(shù)），但實(shí)際中通過剪枝優(yōu)化。3.Python實(shí)現(xiàn)（滑動窗口）：```pythondefminSumOfLengths(nums,target):n=len(nums)left=0current_sum=0min_len=float('inf')dp=[float('inf')]ndp[i]表示前i個元素中長度最小的和為target的子數(shù)組result=float('inf')forrightinrange(n):current_sum+=nums[right]左指針右移，縮小窗口whilecurrent_sum>targetandleft<=right:current_sum-=nums[left]left+=1找到和為target的子數(shù)組ifcurrent_sum==target:current_length=rightleft+1若左邊存在有效子數(shù)組，更新結(jié)果ifleft>0:result=min(result,dp[left1]+current_leng