京东集团游戏程序员笔试编程考试题集含答案

2026年京东集团游戏程序员笔试编程考试题集含答案一、编程基础（共3题，每题10分，总分30分）1.（10分）编写一个函数，接收一个正整数`n`，返回`n`的阶乘值。要求使用递归方式实现。2.（10分）给定一个字符串`s`，编写代码将其反转并返回。例如，输入`"hello"`，输出`"olleh"`。3.（10分）实现一个函数，判断一个整数是否为素数。若为素数，返回`true`；否则返回`false`。二、数据结构（共4题，每题12分，总分48分）1.（12分）编写代码实现二叉树的前序遍历（根-左-右）。假设二叉树节点定义如下：cppstructTreeNode{intval;TreeNodeleft;TreeNoderight;TreeNode(intx):val(x),left(nullptr),right(nullptr){}};2.（12分）实现一个函数，检查链表是否存在环。若存在环，返回`true`；否则返回`false`。假设链表节点定义如下：cppstructListNode{intval;ListNodenext;ListNode(intx):val(x),next(nullptr){}};3.（12分）编写代码实现快速排序算法，对给定数组进行排序。要求使用原地排序方式。4.（12分）实现一个函数，找出数组中的中位数。假设数组长度为奇数，返回中间元素；若为偶数，返回中间两个元素的平均值。三、算法设计（共3题，每题15分，总分45分）1.（15分）设计一个算法，找出字符串中的最长回文子串。例如，输入`"babad"`，输出`"bab"`或`"aba"`。2.（15分）编写代码实现二叉搜索树（BST）的中序遍历，并返回遍历结果。假设BST节点定义如下：cppstructBSTNode{intval;BSTNodeleft;BSTNoderight;BSTNode(intx):val(x),left(nullptr),right(nullptr){}};3.（15分）实现一个函数，计算给定字符串的最长有效括号长度。例如，输入`"(()"`，输出`2`。四、系统设计（共2题，每题20分，总分40分）1.（20分）设计一个简单的聊天室系统，要求支持多用户实时消息传递。说明主要的数据结构和算法。2.（20分）假设需要为一个大型游戏服务器设计数据库缓存机制，说明如何选择合适的缓存策略（如LRU、LFU等），并解释原因。答案与解析一、编程基础1.阶乘递归实现（10分）cppintfactorial(intn){if(n==0||n==1)return1;returnnfactorial(n-1);}解析：递归的核心是基准条件和递归调用。基准条件为`n==0||n==1`，返回`1`。否则，返回`nfactorial(n-1)`，逐步分解问题。2.字符串反转（10分）cppstringreverseString(strings){intleft=0,right=s.size()-1;while(left<right){swap(s[left],s[right]);left++;right--;}returns;}解析：使用双指针法，`left`从左向右移动，`right`从右向左移动，交换字符直至`left>=right`。3.判断素数（10分）cppboolisPrime(intn){if(n<=1)returnfalse;for(inti=2;i<=sqrt(n);i++){if(n%i==0)returnfalse;}returntrue;}解析：素数定义是大于1且只能被1和自身整除。遍历从`2`到`sqrt(n)`，若存在除数则不是素数。二、数据结构1.二叉树前序遍历（12分）cppvoidpreorderTraversal(TreeNoderoot,vector<int>&result){if(!root)return;result.push_back(root->val);preorderTraversal(root->left,result);preorderTraversal(root->right,result);}解析：前序遍历顺序为根-左-右，递归实现时先访问根节点，再递归左子树，最后递归右子树。2.判断链表环（12分）cppboolhasCycle(ListNodehead){ListNodeslow=head,fast=head;while(fast&&fast->next){slow=slow->next;fast=fast->next->next;if(slow==fast)returntrue;}returnfalse;}解析：快慢指针法。快指针每次移动两步，慢指针每次移动一步，若有环则快慢指针会相遇。3.快速排序（12分）cppvoidquickSort(vector<int>&arr,intleft,intright){if(left>=right)return;intpivot=arr[(left+right)/2];intl=left,r=right;while(l<=r){while(arr[l]<pivot)l++;while(arr[r]>pivot)r--;if(l<=r){swap(arr[l],arr[r]);l++;r--;}}quickSort(arr,left,r);quickSort(arr,l,right);}解析：快速排序的核心是分治思想。选择枢轴（pivot），将数组分为左小右大两部分，递归排序。4.数组中位数（12分）cppdoublefindMedian(vector<int>&arr){sort(arr.begin(),arr.end());intn=arr.size();if(n%2==0){return(arr[n/2-1]+arr[n/2])/2.0;}else{returnarr[n/2];}}解析：中位数是排序后位于中间的数。若数组长度为奇数，返回中间元素；若为偶数，返回中间两个元素的平均值。三、算法设计1.最长回文子串（15分）cppstringlongestPalindrome(strings){if(s.empty())return"";intstart=0,end=0;for(inti=0;i<s.size();i++){intlen1=expandAroundCenter(s,i,i);intlen2=expandAroundCenter(s,i,i+1);intlen=max(len1,len2);if(len>end-start){start=i-(len-1)/2;end=i+len/2;}}returns.substr(start,end-start+1);}intexpandAroundCenter(strings,intleft,intright){while(left>=0&&right<s.size()&&s[left]==s[right]){left--;right++;}returnright-left-1;}解析：扩展中心法。遍历每个字符，分别以该字符为中心（奇数长度）和字符为中心（偶数长度）扩展，记录最长回文子串。2.二叉搜索树中序遍历（15分）cppvector<int>inorderTraversal(BSTNoderoot){vector<int>result;stack<BSTNode>st;BSTNodenode=root;while(node!=nullptr||!st.empty()){while(node!=nullptr){st.push(node);node=node->left;}node=st.top();st.pop();result.push_back(node->val);node=node->right;}returnresult;}解析：中序遍历顺序为左-根-右。使用栈模拟递归，先遍历左子树，访问节点，再遍历右子树。3.最长有效括号（15分）cppintlongestValidParentheses(strings){intmaxLen=0;vector<int>dp(s.size(),0);for(inti=1;i<s.size();i++){if(s[i]==')'){if(s[i-1]=='('){dp[i]=(i>=2?dp[i-2]:0)+2;}elseif(i-dp[i-1]>0&&s[i-dp[i-1]-1]=='('){dp[i]=dp[i-1]+((i-dp[i-1])>=2?dp[i-dp[i-1]-2]:0)+2;}maxLen=max(maxLen,dp[i]);}}returnmaxLen;}解析：动态规划法。`dp[i]`表示以`i`结尾的最长有效括号长度。若`s[i]==')'`，分两种情况：前一个字符是`'('`或前一个字符是`')'`。四、系统设计1.聊天室系统设计（20分）主要数据结构和算法：-数据结构：-用户信息（ID、在线状态、会话列表）-消息队列（按时间排序）-实时消息缓存（如LRU缓存）-算法：-WebSocket协议实现实时通信-消息广播（单播/群播）-状态同步（用户上线/下线）解析：聊天室需要支持多用户实时交互，核心是消息的快速传递和状态同步。WebSocket协议适合实时通信，消息广播可采用树形或洪泛算法。2.游戏服务器数据库缓存设计（20分）缓存策略选择及原因：-LRU（Least