北京交通大學(xué)2025年信息與通信工程（軌道交通通信）專業(yè)編程試題及答案考試時間：______分鐘總分：______分姓名：______一、編寫一個函數(shù)，實現(xiàn)快速排序算法。該函數(shù)應(yīng)接受一個整數(shù)數(shù)組和一個表示數(shù)組長度的整數(shù)作為輸入，并原地修改數(shù)組，使其按升序排列。要求在函數(shù)內(nèi)部實現(xiàn)快速排序的核心邏輯，包括選擇基準值、分區(qū)操作和遞歸調(diào)用。請?zhí)峁┩暾暮瘮?shù)定義。二、定義一個類`TrainSchedule`，用于表示列車時刻表。該類應(yīng)包含至少三個私有成員變量：`trainNumber`（字符串，表示列車車次）、`departureStation`（字符串，表示出發(fā)站）和`arrivalStation`（字符串，表示到達站）。同時，為該類提供以下公有成員函數(shù)：1.一個帶參構(gòu)造函數(shù)，用于初始化所有成員變量。2.一個`display()`函數(shù)，用于輸出列車時刻表的信息，格式為：“車次:[車次],出發(fā)站:[出發(fā)站],到達站:[到達站]”。3.一個`getTrainNumber()`函數(shù)，用于返回列車車次。4.一個`setArrivalStation(stringnewStation)`函數(shù)，用于修改列車的到達站。請?zhí)峁┩暾念惗x。三、假設(shè)你需要處理一段包含列車運行狀態(tài)的數(shù)據(jù)，數(shù)據(jù)以逗號分隔的文本形式給出，每個狀態(tài)記錄包含：列車編號、當前速度（整數(shù)）、當前方向（'前進'或'后退'）。請編寫一個函數(shù)，該函數(shù)接受一個包含這些狀態(tài)記錄的字符串，并返回一個`vector`，其中包含每個狀態(tài)對應(yīng)的`TrainStatus`結(jié)構(gòu)體實例。`TrainStatus`結(jié)構(gòu)體應(yīng)包含`trainNumber`（字符串）、`speed`（整數(shù)）和`direction`（字符串）三個成員。四、編寫一個程序，實現(xiàn)以下功能：1.從標準輸入讀取一個正整數(shù)`n`，表示接下來要讀取的列車時刻表數(shù)量。2.接著，讀取`n`個`TrainSchedule`對象的信息。每個對象的信息按以下格式依次輸入：車次、出發(fā)站、到達站。3.將所有讀取的`TrainSchedule`對象存儲在一個`vector`中。4.對`vector`中的`TrainSchedule`對象按`arrivalStation`（到達站）進行升序排序。5.最后，遍歷排序后的`vector`，調(diào)用每個對象的`display()`函數(shù)，依次輸出所有列車時刻表的信息。五、下面給出一段C++代碼，其中包含了一個函數(shù)`processSignal`的定義，該函數(shù)用于模擬處理列車信號。請閱讀并分析該函數(shù)的功能。注意，函數(shù)中可能存在一些注釋標記為`TODO`，表示需要根據(jù)實際情況補充或修改的部分。分析完成后，請描述該函數(shù)的主要功能，并說明`TODO`部分需要做什么。```cpp#include<string>voidprocessSignal(stringsignalType,intsignalStrength,bool&trackIsClear){//根據(jù)信號類型和強度處理信號if(signalType=="Green"){trackIsClear=true;//TODO:處理綠燈信號的具體邏輯，例如記錄信號通過時間等}elseif(signalType=="Yellow"){trackIsClear=false;//TODO:處理黃燈信號的具體邏輯，例如發(fā)出警告等}elseif(signalType=="Red"){trackIsClear=false;//TODO:處理紅燈信號的具體邏輯，例如立即停止列車等}else{//未知信號類型，保持當前狀態(tài)不變//TODO:處理未知信號類型的邏輯，例如記錄錯誤信息等}}```六、編寫一個函數(shù)，該函數(shù)接受一個整數(shù)數(shù)組和一個整數(shù)`threshold`作為輸入。函數(shù)需要找到數(shù)組中所有連續(xù)的子數(shù)組（子序列，元素在原數(shù)組中順序不變），使得子數(shù)組中所有元素的和小于`threshold`。函數(shù)應(yīng)返回一個`vector`，其中包含所有符合條件的子數(shù)組的起始和結(jié)束索引（以`pair<int,int>`形式表示），索引從0開始。例如，對于數(shù)組`[1,2,3,4,2]`和`threshold=5`，符合條件的子數(shù)組有`[1,2]`（和為3）、`[2,3]`（和為5，不滿足嚴格小于）、`[4,2]`（和為6，不滿足）和`[1,2,3]`（和為6，不滿足），因此返回的`vector`應(yīng)包含`[(0,1),(2,2)]`。請?zhí)峁┩暾暮瘮?shù)定義。試卷答案一、```cppvoidquickSort(intarr[],intleft,intright){if(left>=right)return;intpivot=arr[left];//選擇基準值，這里選擇最左端inti=left,j=right;while(i<j){while(i<j&&arr[j]>=pivot)j--;//從右向左找小于基準值的元素if(i<j)arr[i++]=arr[j];//將找到的元素放到左邊while(i<j&&arr[i]<=pivot)i++;//從左向右找大于基準值的元素if(i<j)arr[j--]=arr[i];//將找到的元素放到右邊}arr[i]=pivot;//將基準值放到正確的位置quickSort(arr,left,i-1);//遞歸排序基準值左邊的子數(shù)組quickSort(arr,i+1,right);//遞歸排序基準值右邊的子數(shù)組}//調(diào)用示例：quickSort(arr,0,n-1);```解析思路：快速排序是分治算法的經(jīng)典代表。其核心思想是：選擇一個基準值（pivot），將數(shù)組劃分為兩部分，使得左邊的所有元素都不大于基準值，右邊的所有元素都不小于基準值，然后分別對左右兩部分遞歸地進行快速排序。本題要求實現(xiàn)快速排序的核心邏輯，即選擇基準值、分區(qū)操作和遞歸調(diào)用。分區(qū)操作通過雙指針從兩端向中間掃描，將小于基準值的元素移到左邊，大于基準值的元素移到右邊，最終將基準值放置在正確的位置。遞歸調(diào)用則是對基準值左右兩邊的子數(shù)組進行同樣的操作。二、```cpp#include<string>classTrainSchedule{private:std::stringtrainNumber;std::stringdepartureStation;std::stringarrivalStation;public:TrainSchedule(std::stringnumber,std::stringdep,std::stringarr):trainNumber(number),departureStation(dep),arrivalStation(arr){}voiddisplay()const{std::cout<<"車次:"<<trainNumber<<",出發(fā)站:"<<departureStation<<",到達站:"<<arrivalStation<<std::endl;}std::stringgetTrainNumber()const{returntrainNumber;}voidsetArrivalStation(conststd::string&newStation){arrivalStation=newStation;}};```解析思路：定義一個`TrainSchedule`類來表示列車時刻表。首先聲明私有成員變量`trainNumber`、`departureStation`和`arrivalStation`，用于存儲列車車次、出發(fā)站和到達站信息。然后提供公有成員函數(shù)：帶參構(gòu)造函數(shù)用于初始化成員變量；`display()`函數(shù)用于格式化輸出列車信息；`getTrainNumber()`函數(shù)用于獲取列車車次；`setArrivalStation()`函數(shù)用于設(shè)置新的到達站。類定義需要包含成員變量的聲明、構(gòu)造函數(shù)、成員函數(shù)的定義（包括函數(shù)聲明和實現(xiàn)）。三、```cpp#include<vector>#include<string>#include<sstream>structTrainStatus{std::stringtrainNumber;intspeed;std::stringdirection;};std::vector<TrainStatus>parseTrainStatuses(conststd::string&input){std::vector<TrainStatus>statuses;std::istringstreamiss(input);std::stringtoken;while(iss>>token){//讀取每個逗號分隔的tokenTrainStatusstatus;//假設(shè)格式為"編號:123,速度:50,方向:前進"size_tpos1=token.find(":");if(pos1!=std::string::npos){std::stringkey=token.substr(0,pos1);std::stringvalue=token.substr(pos1+1);if(key=="編號"){status.trainNumber=value;}elseif(key=="速度"){status.speed=std::stoi(value);}elseif(key=="方向"){status.direction=value;}}}returnstatuses;}//調(diào)用示例：vector<TrainStatus>result=parseTrainStatuses("編號:123,速度:50,方向:前進;編號:456,速度:70,方向:后退");```解析思路：首先定義一個`TrainStatus`結(jié)構(gòu)體，包含`trainNumber`、`speed`和`direction`三個成員，用于存儲列車狀態(tài)信息。然后編寫`parseTrainStatuses`函數(shù)，接受一個包含狀態(tài)記錄的字符串`input`。函數(shù)內(nèi)部使用`istringstream`和`>>`運算符按逗號分割字符串，得到每個狀態(tài)記錄的片段。對于每個片段，假設(shè)其格式為"key:value"形式（如"編號:123"），使用`find`和`substr`找到`:`的位置，提取鍵（key）和值（value）。根據(jù)鍵的名稱（"編號"、"速度"、"方向"）將值賦給`TrainStatus`結(jié)構(gòu)體的對應(yīng)成員。最后，將解析得到的每個`TrainStatus`實例添加到`vector`中，并返回該`vector`。四、```cpp#include<iostream>#include<vector>#include<string>#include<algorithm>#include"TrainSchedule.h"http://假設(shè)TrainSchedule類已在TrainSchedule.h中定義intmain(){intn;std::cin>>n;std::vector<TrainSchedule>schedules(n);for(inti=0;i<n;++i){std::stringnumber,dep,arr;std::cin>>number>>dep>>arr;schedules[i]=TrainSchedule(number,dep,arr);}std::sort(schedules.begin(),schedules.end(),[](constTrainSchedule&a,constTrainSchedule&b){returna.getArrivalStation()<b.getArrivalStation();});for(constauto&schedule:schedules){schedule.display();}return0;}```解析思路：程序首先從標準輸入讀取一個整數(shù)`n`，表示列車時刻表的數(shù)量。然后，創(chuàng)建一個包含`n`個`TrainSchedule`對象的`vector`。使用循環(huán)讀取`n`組列車信息（車次、出發(fā)站、到達站），并創(chuàng)建對應(yīng)的`TrainSchedule`對象，存儲到`vector`中。接下來，使用`std::sort`對`vector`進行排序。排序時需要提供一個比較函數(shù)，該函數(shù)根據(jù)`TrainSchedule`對象的`arrivalStation`（到達站）成員進行升序比較。最后，使用范圍`for`循環(huán)遍歷排序后的`vector`，調(diào)用每個`TrainSchedule`對象的`display()`函數(shù)，依次輸出所有列車時刻表的信息。注意，需要包含`TrainSchedule`類的定義和相關(guān)頭文件。五、主要功能：該函數(shù)`processSignal`用于根據(jù)輸入的信號類型(`signalType`)和信號強度(`signalStrength`)處理列車信號，并更新`trackIsClear`變量以指示軌道是否清空，可用于判斷是否可以發(fā)送列車。函數(shù)通過判斷信號類型是綠燈、黃燈還是紅燈，來決定軌道狀態(tài)(`trackIsClear`)以及執(zhí)行特定的附加操作（由`TODO`標記）。`TODO`部分需要做什么：1.`TODO:處理綠燈信號的具體邏輯，例如記錄信號通過時間等`：當信號為綠燈時，除了將`trackIsClear`設(shè)置為`true`，可能還需要執(zhí)行其他操作，如記錄信號通過的時間戳、啟動信號燈計時器、允許列車進入軌道等。2.`TODO:處理黃燈信號的具體邏輯，例如發(fā)出警告等`：當信號為黃燈時，除了將`trackIsClear`設(shè)置為`false`，通常需要執(zhí)行警告操作，如向司機發(fā)出警示、啟動緊急制動預(yù)準備、在顯示屏上顯示注意信息等。3.`TODO:處理紅燈信號的具體邏輯，例如立即停止列車等`：當信號為紅燈時，除了將`trackIsClear`設(shè)置為`false`，必須執(zhí)行強制停止操作，如觸發(fā)緊急制動、關(guān)閉道岔、在控制中心顯示紅燈告警等。4.`TODO:處理未知信號類型的邏輯，例如記錄錯誤信息等`：當遇到未知的`signalType`時，不應(yīng)默認保持狀態(tài)不變，因為這可能導(dǎo)致危險。應(yīng)該記錄一個錯誤或告警信息，例如在日志中記錄“收到未知信號類型：[signalType]”，并可能需要將`trackIsClear`設(shè)置為`false`或采取其他安全措施。六、```cpp#include<vector>#include<utility>//forstd::pairstd::vector<std::pair<int,int>>findSubarraysWithSumLessThan(conststd::vector<int>&arr,intthreshold){std::vector<std::pair<int,int>>result;intleft=0,currentSum=0;for(intright=0;right<arr.size();++right){currentSum+=arr[right];while(currentSum>=threshold&&left<=right){currentSum-=arr[left];//縮小窗口left++;}//如果當前窗口[left,right]的和小于閾值，則添加到結(jié)果中//注意：這里記錄的是以right結(jié)尾的子數(shù)組if(currentSum<threshold){result.emplace_back(left,right);}}returnresult;}//備注：此函數(shù)返回所有滿足條件的子數(shù)組，其中每個子數(shù)組的和小于threshold。//例如，對于arr=[1,2,3,4,2],threshold=5，返回的將是[(0,1),(2,2),(2,3),(3,3),(4,4)]//其中(2,3)的和為5，不滿足嚴格小于，但(2,2)的和為3滿足，(3,3)的和為4滿足，(4,4)的和為2滿足。//如果嚴格要求嚴格小于threshold，需要在添加前增加判斷currentSum<threshold```解析思路：這個問題可以使用滑動窗口（SlidingWindow）技術(shù)來解決?；瑒哟翱谑且环N在數(shù)組中尋找滿足特定條件的子數(shù)組或子序列的常用方法，特別適用