# 面试 **Repository Path**: codechengzzc/interview ## Basic Information - **Project Name**: 面试 - **Description**: 面试面试面试面试面试面试面试面试面试 - **Primary Language**: Unknown - **License**: Not specified - **Default Branch**: master - **Homepage**: None - **GVP Project**: No ## Statistics - **Stars**: 0 - **Forks**: 1 - **Created**: 2026-06-14 - **Last Updated**: 2026-06-14 ## Categories & Tags **Categories**: Uncategorized **Tags**: None ## README # 网页式网盘项目介绍 该项目是一个基于**HTTP**协议的文件管理系统，旨在为公司提供稳定可靠高效的文件上传和下载功能，并应用于云服务器环境 在项目中，为了处理高并发和可扩展性，我采用了**Proactor**模型，并结合开源框架**Workflow**构建了高性能的文件管理服务端。 基于**wfrest**框架，开发了一套RESTful API，支持用户注册、登录、个人中心、文件上传、分片上传和下载等功能 为了实现多用户独立的虚拟文件系统，我设计了一个虚拟文件表来存储用户的文件信息，实现了如文件存储和目录管理等主流文件系统的基本功能。 同时，我利用**Redis**存储用户登录Token以及用户文件的**MD5**码，实现用户登录功能与文件**秒传**功能 为了实现异步上传功能和提高系统的响应性，我集成了RabbitMQ消息队列。通过消息队列，可以将文件上传任务异步处理，提高系统的并发处理能力和可靠性。 为了确保文件的安全性和可靠性，我使用阿里云OSS作为系统的容灾备份方案。这样可以将文件备份到云端，确保文件的安全存储和可靠性。 为了实现微服务架构，我将不同的功能模块拆分成独立的服务，并使用RPC机制实现服务间的通信和协作。为了管理和发现这些微服务，我使用了注册中心Consul，确保微服务的高可用性和动态扩展能力。 综上所述，该项目是一个基于HTTP协议的文件管理系统，通过使用多种技术和组件，实现了稳定可靠的文件上传和下载功能，同时具备高并发、可扩展、安全可靠的特性。 # 搜索引擎项目介绍 该项目是一个基于C++开发的C/S模式多功能网页搜索引擎，旨在应用于公司网站的搜索模块。该搜索引擎能够支持大量客户端的并发访问，并根据用户输入的关键词返回相关的联想词和网页结果。 在项目中，服务端采用了Reactor模型，并结合线程池和epoll多路复用技术，实现了高性能和高并发的检索系统。这种架构能够有效处理大量的并发请求，提高系统的响应速度和并发能力。 在语料处理方面，我们使用了开源库CppJieba对语料进行分词，并进行停用词过滤，建立了词频字典、索引库、网页库和偏移库。这些数据结构能够帮助我们快速检索和定位相关的网页。 为了实现网页去重功能，我们使用了开源库Simhash，并根据TF-IDF算法计算单词的权重，建立了倒排索引库。这样可以有效地去重网页，并根据关键词的权重快速定位相关网页。 为了提供关键词联想功能，我们采用了最小编辑距离算法，根据用户输入的关键字，实现了智能的关键词联想。 此外，我们还使用了余弦相似度算法，对用户输入的关键字进行分析，找出相似度最高的网页并返回给用户。 为了提高检索效率，我们还实现了基于Redis和定时器的多线程缓存系统。将关键词和网页结果存入缓存，并通过定时更新保持数据的最新性。 综上所述，该项目是一个基于C++开发的多功能网页搜索引擎，通过使用多种技术和算法，实现了高性能、高并发的检索系统，并提供了关键词联想、相似度匹配等功能。 # 2023.10.13 尚米网络-珠海（已挂） ## 一面：（20min） 自我介绍 介绍一下你做的两个项目 Workflow介绍一下 为什么用这个 微服务怎么实现的 RPC机制是什么 有没有遇到过Redis缓存击穿 怎么解决 ### MySQL慢查询 > MySQL慢查询是指执行时间长或者性能较差的查询语句。慢查询可能会影响数据库的性能和响应时间，因此需要进行优化。以下是一些常见的处理慢查询的方法： > > 1. 使用索引：确保查询涉及的列上有适当的索引。通过创建适当的索引，可以加快查询的速度。使用`EXPLAIN`语句来分析查询计划，确定是否使用了索引。 > > 2. 优化查询语句：检查慢查询的语句，尽可能简化查询，避免不必要的关联或子查询。使用合适的查询条件，避免全表扫描。 > > 3. 避免使用通配符查询：通配符查询（如`LIKE '%value%'`）会导致全表扫描，性能较差。如果可以，尽量避免使用通配符查询，或者考虑使用全文搜索引擎。 > > 4. 优化表结构：根据查询需求和数据访问模式，优化表的结构，考虑表的范式化和反范式化，以提高查询性能。 > > 5. 分析和监控工具：使用MySQL的性能分析和监控工具，如`EXPLAIN`、`SHOW PROFILE`、`SHOW STATUS`等，可以帮助了解查询的执行计划、资源消耗和瓶颈。 > > 6. 查询缓存：MySQL的查询缓存可以缓存查询结果，提高重复查询的性能。但是在高并发环境下，查询缓存可能会导致性能问题，因此需要根据实际情况进行配置和优化。 > > 7. 数据库优化：确保MySQL服务器的配置和参数设置合理，如合适的缓冲区大小、线程连接数、查询缓存大小等。根据服务器的硬件资源和负载情况进行调整。 > > 8. 定期清理历史数据：如果表中包含大量历史数据，可以考虑定期清理或者归档旧数据，以减少查询的数据量和提高性能。 > > 以上是一些处理MySQL慢查询的一般方法。具体的处理方法取决于查询语句、表结构、数据量和服务器配置等因素。在优化慢查询时，可以结合实际情况进行分析和测试，逐步寻找性能瓶颈并进行改进。 有没有用过智能指针 shared_ptr怎么实现的 平时用到哪些排序算法（平时一般都是用的STL的sort，只有在做算法题的时候会根据题目的类型可能会用到归并排序或者快速排序的思想去解题） 算法题-字符串的最长公共子序列 怎么做 时间复杂度是多少 C和C++的区别 函数调用怎么实现的？过程 调用子函数怎么样获取到函数的返回值？ ### 链接的过程 > 在 Linux 系统中，链接的过程主要涉及以下步骤： > > 1. 预处理（Preprocessing）：在编译源代码之前，预处理器会处理源文件中的预处理指令，例如宏展开、头文件包含等。预处理器将生成经过预处理的代码文件。 > > 2. 编译（Compilation）：编译器将预处理后的代码文件转换为汇编语言代码，即将高级语言代码转换为机器语言指令。编译器将生成汇编语言文件。 > > 3. 汇编（Assembly）：汇编器将汇编语言文件转换为机器语言的目标文件。目标文件中包含机器指令的二进制表示形式。 > > 4. 链接（Linking）：链接器将目标文件与其他必要的库文件进行合并，生成最终的可执行文件。链接器执行以下几个主要的任务： > > - 符号解析（Symbol Resolution）：链接器解析目标文件中使用的符号（例如函数、变量等），并在其他目标文件或库文件中找到这些符号的定义。 > - 符号重定位（Symbol Relocation）：链接器根据目标文件中符号的引用和定义，对目标文件的地址进行重定位。这确保了不同目标文件中的符号引用正确地指向其定义的位置。 > - 符号合并（Symbol Merging）：如果多个目标文件或库文件中有相同的符号定义，链接器会将它们合并为一个符号，以避免重复定义。 > - 库文件链接（Library Linking）：链接器将所需的库文件与目标文件进行链接，以提供程序所需的额外功能。 > > 5. 加载（Loading）：最终生成的可执行文件被加载到内存中，并由操作系统执行。加载器将可执行文件映射到进程的地址空间，并执行程序的入口点，使程序开始运行。 > > 这些步骤通常由编译器和链接器自动完成，通过执行编译命令（如`gcc`）或构建工具（如`make`）来触发整个过程。 ### 符号找不到怎么办？ > 如果在链接过程中出现符号找不到的错误，可以考虑以下几个解决方法： > > 1. 检查头文件和库文件路径：确保需要的头文件和库文件路径正确配置。可以使用编译选项 `-I` 和 `-L` 来指定额外的头文件和库文件搜索路径。 > > 2. 检查库文件名：确认使用了正确的库文件名。库文件名通常以 `lib` 开头，并以 `.so`（共享库）或 `.a`（静态库）结尾。某些库文件可能需要添加版本号等后缀。 > > 3. 检查库文件链接顺序：如果链接多个库文件，确保将依赖的库文件放在引用它们的库文件之后。链接器是按照顺序查找符号的，所以符号引用应在符号定义之后。 > > 4. 检查符号命名和作用域：确保符号的名称和作用域在源代码和库文件中正确匹配。符号的名称和作用域需要保持一致，否则链接过程无法找到正确的定义。 > > 5. 检查库文件是否正确编译：如果使用的库是自己编译的，确保库文件已经正确地编译和生成。 > > 6. 检查依赖关系：如果使用的库文件依赖其他库文件，确保这些依赖的库文件已经正确地安装和链接。 > > 7. 检查编译选项和链接选项：确认编译和链接时使用的选项是否正确，例如是否包含了必要的编译选项和链接选项。 > > 8. 检查编译器和链接器版本：有时，不同的编译器和链接器版本之间可能存在差异。确保使用的编译器和链接器版本与库文件兼容。 > > 9. 检查符号导出和可见性：如果符号是从库文件导出的，确保符号的可见性设置正确。有些符号可能需要使用特定的导出修饰符或设置来确保其可见性。 > > 如果仍然无法解决符号找不到的问题，可以进一步查看链接器的错误输出和日志，以获取更详细的信息。 有什么问题想问我的 - Redis缓存击穿 MySQL慢查询一般在公司是怎么实现的？ - 这个是看到你的简历上写了才问你的，公司中的工作和这个关系不大，， - 函数调用过程怎么实现的？ - 有一个栈顶指针 然后函数调用会进行压栈 参数存入寄存器中balabala （听不懂） - 链接过程 - 静态链接会在编译阶段进行一个符号绑定balabala （听不懂） ### 函数调用过程 > 函数调用过程是指在程序中调用函数时，程序的执行流程从当前位置跳转到函数的代码块，并在函数执行完毕后返回到调用点的过程。以下是一般的函数调用过程： > > 1. 保存现场：在调用函数之前，当前函数的执行现场需要保存起来，包括函数的返回地址、调用函数时的局部变量和寄存器的值等。这样在函数执行完毕后可以恢复到调用点继续执行。 > > 2. 参数传递：将调用函数时传递的参数按照约定传递给被调用函数。参数可以通过栈、寄存器或其他方式进行传递。 > > 3. 跳转到函数代码块：程序执行跳转到被调用函数的代码块，开始执行函数内的语句。 > > 4. 函数执行：被调用函数按照定义的顺序执行其中的语句，包括局部变量的声明和赋值、执行函数体内的语句等。 > > 5. 返回值：如果函数有返回值，函数执行完毕后将返回值传递给调用函数。返回值可以通过寄存器、栈或其他方式传递。 > > 6. 恢复现场：在函数执行完毕后，需要恢复调用点的执行现场。这包括恢复返回地址、恢复局部变量和寄存器的值等。 > > 7. 返回到调用点：程序跳转回调用点，继续执行调用点后面的语句。 > > 这是简化的函数调用过程示意图，实际的函数调用过程可能受编程语言、编译器和操作系统等因素的影响而有所差异。例如，不同的编程语言和编译器可能使用不同的参数传递方式、调用约定和寄存器分配策略等。但上述过程提供了一个一般的理解框架。 ### 函数调用过程中，参数是如何传递给被调用函数的？ > 参数的传递方式可以根据编程语言、编译器和操作系统的不同而有所差异。下面介绍几种常见的参数传递方式： > > 1. 寄存器传递：某些编程语言和编译器会将函数的参数传递给一些特定的寄存器。通常，寄存器的数量是有限的，因此只有少量的参数可以通过寄存器传递。常见的例子是 x86 架构的 cdecl 调用约定中，前几个参数会通过寄存器传递。 > > 2. 栈传递：栈传递是一种常见的参数传递方式。参数被依次压入调用栈，被调用函数从栈中获取参数的值。栈传递允许传递多个参数，并且对于参数数量没有限制。在栈传递中，参数的顺序通常是从右向左或从左向右。 > > 3. 寄存器+栈传递混合：有时候，参数既可以通过寄存器传递，又可以通过栈传递。例如，某些编程语言和编译器规定前几个参数使用寄存器传递，而剩下的参数使用栈传递。 > > 4. 静态链接库传递：在使用静态链接库时，参数传递的方式可能与上述方式略有不同。静态链接库可能有自己的函数调用约定和参数传递方式，需要遵循库的规范进行参数传递。 > > 需要注意的是，对于大型的数据结构或对象，参数传递方式可能会略有不同。一般情况下，较小的参数（如整数、指针等）会直接传递给被调用函数，而较大的参数（如结构体、数组等）可能会通过指针或引用的方式传递，以避免复制大量数据。 > > 总之，具体的参数传递方式取决于编程语言、编译器和操作系统的约定，开发者在编写代码时应该参考相关文档或规范来确定参数传递的方式。 # 2023.10.13 软牛科技-深圳（已挂） ## 一面：（30min） 自我介绍 介绍一下你做的两个项目（这里很关键，基本回答用到了什么技术 后面就会接着问为什么用这个 怎么实现的） 微服务 RPC机制 为什么要用微服务 怎么实现的 protobuf Reactor是什么？怎么实现的 第二个项目的线程池是用来干嘛的 怎么实现的 任务队列？怎么保证线程之间竞争资源 条件变量怎么实现的 epoll是什么技术 还有哪些IO多路复用技术 区别是什么 epoll的边缘触发和水平触发，使用场景？ 平时会用到哪些智能指针 unique_ptr和shared_ptr的实现原理是什么 哈希表如果发生哈希冲突怎么解决 快速排序（口述）选取基准值怎么选取？一定要选第一个吗？刚刚提到了快速排序在有序的时候效率比较差，那么在这个最坏情况下，快速排序等同于哪个排序？时间复杂度是多少 单例模式（口述） 还知道哪些设计模式？策略模式知道吗 TCP/IP四层网络模型是哪四层？TCP的三次握手流程 为什么2次握手不行 C和C++的区别？刚刚提高了多态，那么静态多态和动态多态分别是怎么实现的 进程间通信机制有哪些？（首先刚刚提到的RPC就是进程间通信方式的一种，然后是socket、管道、消息队列、信号量、共享内存）（这里有说的技巧，就是先说项目中用到的RPC，如果前面没问RPC，这里说出来很可能面试官就让你说RPC是怎么实现的，然后说socket，这样就扯到了网络编程，这样继续说到connect和accept的话就可以扯到TCP三次握手，如果前面没问，这里就可能面试官就会问到，再接着说最简单的进程间通信方式是管道-匿名管道、有名管道，这里面试官让我说了一下两者的区别，以及使用场景，然后说最快的进程间通信方式是共享内存，这里面试官就问了我共享内存怎么实现的） 共享内存是怎么实现的 C/C++编译后的代码在内存中的布局（从高地址到低地址分别是内核空间、栈区、堆区、全局静态区、常量区、代码区）栈、堆的扩展方向？ 项目中使用什么工具进行代码管理？Git 项目中使用什么工具进行编译？CMake和Makefile 好 那问你Makefile怎么解决参数传递的问题 - 不会 文件系统有了解吗？（因为这家公司是做文件修复、数据恢复的，需要有文件系统方面的知识） 有什么问题要问我的？ - 刚刚的文件系统可以说一下吗 - Windows的文件系统是NTFS，然后Linux的文件系统是ext，可以下去了解一下 - 进去是使用C++ 做开发吗？ - 是，除了一些脚本可以使用Python和Java 大部分是C++ ## 二面：（挂） ### std::string的优化策略 算法题： - 快速排序 - 层次遍历 - 给你一个数组，大小是10000，内容都是26个小写字母，将他们排序 > 快速排序，时间O(nlogn) > > 桶排序，char barrel[26]，时间O(n)， 空间O(1) 问题基本答出来了也挂，， # 2023.10.13 贝格迈思（深圳）技术有限公司 笔试 一道改错题 三道算法题： [53. 最大子数组和](https://leetcode.cn/problems/maximum-subarray/) [15. 三数之和](https://leetcode.cn/problems/3sum/) [LCP 34. 二叉树染色](https://leetcode.cn/problems/er-cha-shu-ran-se-UGC/) 改错题： ![image-20231013200446146](README.assets/image-20231013200446146.png) ```c #define INIT_NAME "xyz" #define EMPLOYEE_COUNT 100 #define NAME_LEN 31 typedef struct employee { char sex; int age; char szName[NAME_LEN]; } employee_st; int main() { employee_st* pstEm; unsigned int uiCount = EMPLOYEE_COUNT; char* pcName = INIT_NAME; int iNameLen = 0; iNameLen = strlen(INIT_NAME); pstEm = malloc(EMPLOYEE_COUNT * sizeof(employee_st)); while (uiCount > 0) { pstEm->sex = 'm'; pstEm->age = 25; memcpy(pstEm->szName, INIT_NAME, iNameLen); uiCount--; pstEm++; } free(pstEm); return 0; } ``` 错误1：没有包含头文件 错误2：malloc返回的是空指针，需要进行强制类型转换，并且如果内存不足，malloc可能会返回空指针，需要进行判断 错误3：strlen只会求出字符串的长度，不包括`\0`，所以memcpy需要+1 错误4：pstEm进行了移动，此时pstEm指向的是最后一个元素的后一个位置，最后free的时候free一个非法空间。使用 `free(pstEm - EMPLOYEE_COUNT)`，将指针还原到初始分配的地址，然后再释放整个内存块。 修改后的代码： ```c #include // for printf #include // for malloc, free #include // for strlen, memcpy #define INIT_NAME "xyz" #define EMPLOYEE_COUNT 100 #define NAME_LEN 31 typedef struct employee { char sex; int age; char szName[NAME_LEN]; } employee_st; int main() { employee_st* pstEm; unsigned int uiCount = EMPLOYEE_COUNT; char* pcName = INIT_NAME; // 注意：这样写，如果通过这个指针去修改字符串的内容的话是对的 #if 0 printf("%s\n", pcName); // 正常输出xyz，只读是运行的，相当于这个指针指向常量区的这个常量字符串 pcName[0] = 'a'; // 修改的话就是错误的 printf("%s\n", pcName); // 发生段错误 #endif int iNameLen = 0; iNameLen = strlen(INIT_NAME); pstEm = (employee_st*)malloc(EMPLOYEE_COUNT * sizeof(employee_st)); if (pstEm == NULL) { printf("Memory allocation failed.\n"); return 1; } while (uiCount > 0) { pstEm->sex = 'm'; pstEm->age = 25; memcpy(pstEm->szName, INIT_NAME, iNameLen + 1); uiCount--; pstEm++; } free(pstEm - EMPLOYEE_COUNT); return 0; } ``` ## 一面（电话面） ## 二面（腾讯会议） ### 如果要你设计一个MySQL的表，应该需要考虑哪些因素？ > 设计一个MySQL的表时，可以考虑以下因素： > > 1. 数据完整性：确定表中的数据类型、约束（如主键、唯一性约束、外键等）以及默认值，以确保数据的完整性和一致性。 > > 2. 数据规模：根据预期数据量和访问模式，选择适当的数据类型和字段长度，以避免浪费存储空间或者限制数据容量。 > > 3. 数据关系：根据业务需求，定义表之间的关系，包括主键和外键的关联，以确保数据的一致性和引用完整性。 > > 4. 性能考虑：根据预期的数据访问模式和需求，设计合适的索引（如单列索引、组合索引等），以提高查询性能和加快数据检索速度。 > > 5. 数据范式：根据数据的特性和业务需求，选择合适的范式级别，以避免数据冗余和更新异常。 > > 6. 数据操作频率：根据数据的读写比例和频率，考虑是否需要分区表、分表或者分库，以提高并发性能和扩展性。 > > 7. 安全性考虑：根据敏感性数据的需求，设计合适的访问权限和安全措施，如使用用户认证、权限控制等，以确保数据的安全性和保密性。 > > 8. 数据备份和恢复：考虑定期备份表数据和事务日志，以及灾难恢复策略，以保障数据的可靠性和可恢复性。 > > 9. 性能监控和优化：设计合适的监控指标和工具，以及性能优化策略，以及时发现和解决潜在的性能问题。 > > 10. 未来扩展性：预测未来的需求和数据增长趋势，设计表结构和索引，以便于扩展和适应未来的变化。 > > 以上是设计MySQL表时需要考虑的一些因素，具体的设计取决于具体的业务需求和数据特性。 怎样实现一个无锁队列？ # 2023.10.13 天融信科技 笔试（部分） - 改错 ```cpp #define INIT_NAME "xyz" #define EMPLOYEE_COUNT 100 #define NAME_LEN 31 typedef struct employee { char sex; int age; char szName[NAME_LEN]; } employee_st; int main() { employee_st* pstEm; unsigned int uiCount = EMPLOYEE_COUNT; char* pcName = INIT_NAME; int iNameLen = 0; iNameLen = strlen(INIT_NAME); pstEm = malloc(EMPLOYEE_COUNT * sizeof(employee_st)); while (uiCount > 0) { pstEm->sex = 'm'; pstEm->age = 25; memcpy(pstEm->szName, INIT_NAME, iNameLen); uiCount--; pstEm++; } free(pstEm); return 0; } ``` 修改上述代码的所有错误 - 以下关于TCP协议说法正确的是？ A. TCP报文数据段的最大长度可以大于MSS B. TCP三次握手的第一个syn报文的序列号一定是0 C. TCP窗口的最大大小是65536 D. 不考虑丢包的情况下，完成TCP三次握手只可能有3个报文 - 从后台启动进程，应在命令的结尾加上___符号 - void\*可以转化为任何指针？任何指针都可以转为void*？ - 路由器在路由数据包时，必须知道的信息有 A. 数据包源IP B. 数据包的目的MAC C. 路由器的IP地址 D. 数据包的目的IP - 以下指令哪些可以为文件增加可执行权限 A. chmod a+x file B. chmod a-x file C. chmod a+w file - fp=open("file","w") 写操作结束之后可以从头开始读吗 - 关于寄存器变量，以下选项描述错误的是 A. register声明告诉编译器，它所声明的变量在程序中使用频率较高 B. 过量的寄存器声明有害 C. 寄存器变量地址可以访问 D. 编译器可以忽略部分register声明 E. 形式参数可以使用register声明 F. 自动变量可以使用register声明 - 可以通过编译器命令行选项增加搜索路径？ - 计算下面strlen的值 ```cpp char a[]={'a','b','c','\0','d','e'} char b[6]={'a','b','c','d','e'}; char* str="abcde"; ``` - 冒泡排序算法的时间复杂度 - sizeof(name2) = ```cpp struct name2{ char std; int num; short x; }; ``` - 列举4种进程调度算法 - 写出一个代码段，判断系统443端口是否被占用 - 编写一个C函数，该函数在一个字符串中找到可能的最长的字符串，且该字符串由同一个字符组成 # 2023.10.14 剑心互娱 【24秋招】10.12剑心互娱网测-程序A卷 （已挂） - **第一题：** 求奇序列数 若有一组最小值大于0，数目大于1的连续的奇数的和等于指定正整数数字，那么此连续的奇数序列称为此正整数数字的一个奇序列。如数字12，总共能找出一个奇序列（5,7），数字16能找出两个奇序列（1,3,5,7）和（7,9），数字17找不出，那么12的奇序列数为1,16的奇序列数为2,17的奇序列数为0，实现函数求指定数字的奇序列数 - **第二题：** 在一个坐标均为正数的地图上，每1个坐标单位划线，把地图切割成许多格子，如图所示。 玩家A处于坐标PA（X ，Y），该坐标必定在某个格子中心。地图上的敌人在投放N个范围伤害技能，技能的伤害范围有两种形状：矩形和圆形。 矩形：由两个点来表示，起始点P1为矩形左上角的顶点，结束点P2为矩形右下角的顶点。 圆形：由半径和圆心点来表示。 命中判定：地图上的格子与表示伤害范围的图形存在重叠的面积，则在这个格子里的玩家算作被命中。若格子与图形只重叠了一个点或一根线不算有重叠面积。玩家只能通过水平和垂直方向来移动，求玩家要躲避所有技能，至少需要移动几个格子的距离？ **输入描述：**X Y 玩家所在的坐标（必定落在格子中央，无需考虑格子边界问题） N 存在地图上的技能数量（1<=N<5） a b c d 每4个数值表示一个技能范围，若a > 0，则范围为矩形，（a，b）为左上角顶点，（c，d）为右下角顶点。若a<=0，则范围为矩形，b为半径（c，d）为圆心。abcd均为float，且<1000 **输出描述：**需要移动的格子数 **测试用例：** **输入：** ``` 9.5 7.5 3 4.25 10.75 10.75 4.25 -1 3.75 13 10.5 10.25 4.75 16.75 1.25 ``` **输出：** ``` 4 ``` - **第三题：** 序列化代码理解反推 在某些情况下，需要将int数组转存为字符串进行存储，以提高效率。以下是int数组转换为string的代码。请根据以下这段代码，完成string还原回int数组的代码。 ```cpp string GetIntArryString(vector& Data) { string strRet = ""; const char* szIndex = "0123456789ABCDEF"; int nZeroCount = 0; int nMask = 0xF; for(int i = 0; i < Data.size() * 8; ++i){ int nPos = (7 - i % 8) * 4; uint8_t uValue = (Data[i / 8] & (nMask << nPos)) >> nPos; if((nValue && nZeroCount) || (nZeroCount == ('z' - 'a' + 2))){ strRet.push_back((nZeroCount > 1 ? ('a' + nZeroCount - 2) : '0')); nZeroCount = 0; } if (!uValue){ nZeroCount++; } else { strRet.push_back(szIndex[uValue]); } } if (nZeroCount > 0) { strRet.push_back((nZeroCount > 1 ? ('a' + nZeroCount - 2) : '0')); } return strRet; } ``` 示例1： 输入： ``` "f1fA" ``` 输出： ``` [1,10] ``` # 2023.10.15 字节跳动2024秋招研发第八场笔试【后端方向】 - 小红拿物资 坐标轴上有n个人，位置分别是a1，a2，...，an，有n个物资，位置分别是b1，b2，...，bn，每个人可以拿走一个物资，每个物资只能被一个人拿走，然后走到终点p，每个人走一步需要花费1的时间，每个人拿走物资的时间为0，问最终每个物资都运送到终点时，每个人所花费时间总和的最小值。 输入描述： ``` 一行两个整数n，p，表示人数和终点位置。 一行n个整数a1，a2，...，an，表示每个人的位置。 一行n个整数b1，b2，...，bn，表示每个物资的位置。 1<=n<=10^5 1<=p,ai,bi<=10^9 ``` 输出描述： ``` 输出一个整数，表示最短时间 ``` 示例： 输入： ``` 3 3 1 4 3 2 5 6 ``` 输出： ``` 11 ``` 说明： ``` 第一个人拿第一个物品花费时间1，走到终点花费时间1 第二个人拿第三个物品花费时间2，走到终点花费时间3 第三个人拿第二个物品花费时间2，走到终点花费时间2 ``` - 小红摘叶子 小红是一名科学家，她正在研究一种植物的叶子。这种植物的叶子有两个特征：颜色和形状。小红一共有n片叶子需要研究，她按照顺序依次摘取。然而，小红的研究假设是，研究一片叶子时，如果发现曾经已经研究过相同颜色和形状的叶子，那么本次研究的知识减半（向下取整）。现在问题是，小红可以自由排序，选择研究的顺序，最多可以获得多少知识。 输入描述： ``` 第一行一个正整数n，表示叶子的数量 第二行n个正整数a1，a2，...，an，表示每片叶子的颜色。 第三行n个正整数b1，b2，...，bn，表示每片叶子的形状。 第四行n个正整数c1，c2，...，cn，表示第一次研究可以获得知识，如果之前见过相同颜色和形状的叶子，则获得的知识是ci / 2（向下取整） 1<=n<=10^5 1<=ai,bi<=10^9 1<=ci<=10^4 ``` 输出描述： ``` 一个整数，表示最多获得的知识 ``` 示例： 输入： ``` 4 1 2 2 2 1 2 3 2 2 3 4 5 ``` 输出： ``` 12 ``` 说明： ``` 按照1,4,3,2的顺序研究，获得知识2+5+4+(3/2)，第二片叶子之前看过，获得的知识减半 ``` - 小红卖瓜 小红准备卖n个西瓜，已知每个西瓜的品质为ai。小红可以设置一个品质标准x，品质不小于x的西瓜为优质品。小红希望设置完品质标准x后，当顾客从左到右依次买瓜时，每个人买到的优质品的概率都不小于p（顾客不知道哪个瓜是优质品，只知道剩下的瓜数量以及剩下的优质品数量）。小红想知道，x的最大值是多少？ 输入描述： ``` 第一行输入一个正整数n和一个正实数p，含义如题意描述 第二行输入n个正整数ai，分别代表每个瓜的品质。 1<=n<=200000 1<=ai<=10^9 0> processTasks(vector& tasks) { } ``` 测试用例： ``` 输入：3 3 3 4 1 1 7 输出： 2 5 1 7 3 12 输入：2 5 2 3 1 输出： 2 4 1 7 ``` - 主观题1 大学的课余时间是如何安排的，投入最多的是什么？为什么愿意花时间去做，取得了什么结果 - 主观题2 列举大学四年定的1-2个目标，都为了目标付出了什么努力？你觉得你实现了自己的目标了吗 # 2023.10.17 美团 履约技术-算法工程C/C++研发工程师 ## 一面 ### vector是怎样清理内存的 > `vector`的析构函数的源码实现会因不同的C++标准库实现而有所差异。以下是一个典型的`vector`析构函数的伪代码示例，用于说明其工作原理： > > ```cpp > ~vector() > { > // 销毁容器中的元素 > for (每个元素 in 容器) > { > 销毁元素; > } > > // 释放内存 > 释放内存空间; > } > ``` > > 在这个示例中，`~vector()`是`vector`的析构函数。当一个`vector`对象被销毁时（例如，超出其作用域、被删除或存储在另一个容器中），该析构函数会被自动调用。 > > 在析构函数的实现中，首先需要遍历容器中的每个元素，并逐个调用其析构函数来销毁元素。这确保了元素所占用的资源（如内存、打开的文件句柄等）被正确释放。具体销毁元素的方式取决于元素的类型和定义。 > > 接下来，析构函数会释放容器所占用的内存空间。内存的释放通常是通过调用动态内存分配的相关函数（如`delete[]`或`free()`）来实现。这样，已分配的内存将被返回给操作系统，以便将来的内存分配请求可以使用它。 > > 需要注意的是，上述示例是一个简化的伪代码示例，实际的析构函数实现可能会更加复杂，以处理异常安全性、特殊情况和优化等方面的问题。此外，具体的`vector`实现可能会使用其他技术来提高性能和内存管理，例如使用分配器（allocator）来管理内存分配和释放。 > > 总之，`vector`的析构函数负责销毁容器中的元素并释放内存空间，以确保资源的正确释放和内存的回收。 > > > > 在C++标准库中，`allocator`是一个泛型的内存分配器，用于分配和释放内存空间。`vector`等容器类可以使用`allocator`来管理其内部元素的内存分配和释放。 > > `allocator`的工作原理如下： > > 1. 内存分配：`allocator`通过调用`allocate`函数来分配内存空间。`allocate`函数接收一个表示分配的对象数量的参数，并返回指向分配内存起始位置的指针。例如，`allocator::allocate(10)`会分配能够容纳10个`int`类型对象的内存空间，并返回指向该内存空间起始位置的指针。 > > 2. 对象构造：一旦内存空间被分配，`allocator`可以使用`construct`函数在已分配的内存空间上构造对象。`construct`函数接收一个指向内存空间的指针和传递给对象构造函数的参数，以在指定的内存位置上构造对象。 > > 3. 对象销毁：当需要释放内存空间时，`allocator`使用`destroy`函数来销毁对象。`destroy`函数接收一个指向对象的指针，在该指针指向的位置上调用对象的析构函数来销毁对象。 > > 4. 内存释放：最后，`allocator`通过调用`deallocate`函数来释放先前分配的内存空间。`deallocate`函数接收一个指向先前分配内存空间起始位置的指针和分配的对象数量作为参数，以释放内存空间。 > > 使用`allocator`的示例代码如下： > > ```cpp > #include > #include > #include > > int main() { > std::allocator myAllocator; > > // 分配内存空间 > int* ptr = myAllocator.allocate(5); > > // 构造对象 > for (int i = 0; i < 5; ++i) { > myAllocator.construct(ptr + i, i); > } > > // 使用对象 > for (int i = 0; i < 5; ++i) { > std::cout << *(ptr + i) << " "; > } > std::cout << std::endl; > > // 销毁对象 > for (int i = 0; i < 5; ++i) { > myAllocator.destroy(ptr + i); > } > > // 释放内存空间 > myAllocator.deallocate(ptr, 5); > > return 0; > } > ``` > > 在上述示例中，`std::allocator`是一个`int`类型的内存分配器。首先，使用`allocate`函数分配了5个`int`类型对象的内存空间。然后，使用`construct`函数在分配的内存空间上构造了`0`到`4`的五个对象。接下来，使用这些对象进行操作，并打印它们的值。然后，使用`destroy`函数销毁这些对象。最后，使用`deallocate`函数释放先前分配的内存空间。 > > 通过使用`allocator`，`vector`等容器可以更灵活地管理内存分配和释放的过程，以满足不同的需求和优化要求。 ### malloc的底层实现 > `malloc`是C语言中用于动态分配内存的函数，它的底层实现机制可以涉及到操作系统的内存管理和堆的数据结构。下面是一个简要的描述： > > 1. 内存管理单元： > 在操作系统中，内存被划分为多个内存页，通常是以4KB为单位。内存管理单元（Memory Management Unit，MMU）负责管理这些内存页，包括将物理地址映射到虚拟地址、分配未使用的内存页等。 > > 2. 堆的数据结构： > 堆是一块用于动态分配内存的区域。它可以分为两个部分：已分配的内存块和空闲的内存块。已分配的内存块用于存储已经由`malloc`等函数分配的内存，而空闲的内存块则是可以被分配给新的内存请求。 > > 3. `malloc`的底层实现机制： > 当调用`malloc`函数时，它会执行以下步骤： > > - 1. 检查堆的空闲链表（free list），该链表记录了空闲内存块的信息，包括大小和地址。 > - 2. 遍历空闲链表，查找一个足够大的内存块来满足请求。通常会选择一个大小略微超过请求大小的内存块，以便将剩余空间添加到空闲链表中，以备后续的内存分配请求。 > - 3. 如果找到合适的内存块，则将其从空闲链表中移除，并返回该内存块的地址给调用者。如果没有找到合适的内存块，则需要执行内存的分配和管理策略，通常是通过操作系统的系统调用（如`sbrk`或`mmap`）来向操作系统申请更多的内存空间。 > - 4. 对返回的内存块进行必要的内存对齐和标记，以确保满足程序的要求。 > - 5. 返回分配的内存块的地址给调用者。 > > 4. 内存释放： > 当使用`free`函数释放由`malloc`分配的内存时，它会将该内存块添加到空闲链表中，以便后续的内存分配可以重复使用它。 > > 需要注意的是，不同的操作系统和C库可能会有不同的实现机制和算法来管理内存。上述描述只是一种常见的实现方式，并不能代表所有情况。此外，现代的C++语言通常推荐使用更高级的内存管理方式，如RAII（资源获取即初始化）和智能指针（如`std::shared_ptr`和`std::unique_ptr`），以减少手动内存管理的复杂性和风险。 ### 算法题：有20个硬币 一个是假的 重一些 怎么称 称多少次找出这个假币 > 要找出这个假币，可以使用天平来进行称重。以下是一种方法，最多只需要称重4次就能找出假币： > > 1. 将20个硬币分成两组，分别放在天平的两端，称重一次： > - 如果两组重量相等，说明假币不在这两组中，假币在剩下的未称重的硬币中。进入步骤2。 > - 如果两组重量不等，说明假币在较重的那一组中。进入步骤3。 > > 2. 将剩下的20个硬币分成两组，分别放在天平的两端，称重一次： > - 如果两组重量相等，说明假币不在这两组中，假币是未称重的那个硬币。进入步骤4。 > - 如果两组重量不等，说明假币在较重的那一组中。进入步骤4。 > > 3. 将较重的一组中的硬币继续分成两组，分别放在天平的两端，称重一次： > - 如果两组重量相等，说明假币就是剩下的那个未称重的硬币。进入步骤4。 > - 如果两组重量不等，说明假币在较重的那一组中。进入步骤4。 > > 4. 将较重的一组中的硬币中的硬币分成两组，分别放在天平的两端，称重一次： > - 如果两组重量相等，说明假币就是剩下的那个未称重的硬币。 > - 如果两组重量不等，说明假币是较重的那一组中的那个硬币。 > > 通过以上的步骤，最多需要称重4次就可以找出这个假币。 ### 进程、线程、协程的区别，优缺点 > 进程、线程和协程是计算机程序执行的不同方式，它们具有不同的特点、优缺点和适用场景。 > > 1. 进程（Process）： > - 定义：进程是正在运行的程序的实例。每个进程都有自己独立的内存空间和系统资源，包括代码、数据、打开的文件、网络连接等。 > - 特点： > - 进程之间相互独立，拥有独立的内存空间和资源。 > - 进程切换开销较大，需要保存和恢复整个进程的上下文信息。 > - 进程通信需要使用操作系统提供的机制，如管道、消息队列、共享内存等。 > - 优点： > - 进程之间的隔离性强，一个进程崩溃不会影响其他进程。 > - 利用多核处理器的能力，可以实现并行处理。 > - 缺点： > - 进程切换开销大，频繁的进程创建和销毁会消耗较多的系统资源。 > - 进程间通信复杂，需要使用操作系统提供的机制。 > > 2. 线程（Thread）： > - 定义：线程是进程中的执行单元，一个进程可以包含多个线程。所有线程共享进程的内存空间和系统资源。 > - 特点： > - 线程之间共享进程的内存空间和资源。 > - 线程切换开销相对较小，只需要保存和恢复线程的上下文信息。 > - 线程通信直接读写共享内存，比进程通信更高效，但需要注意同步和互斥问题。 > - 优点： > - 线程切换开销小，适合处理并发任务。 > - 可以共享数据，方便线程间的通信和协作。 > - 缺点： > - 线程之间共享资源，需要注意同步和互斥，避免竞态条件和死锁等问题。 > - 一个线程的崩溃可能会导致整个进程的崩溃。 > > 3. 协程（Coroutine）： > - 定义：协程是一种用户态的轻量级线程，也被称为非抢占式的线程。协程可以在执行过程中主动让出控制权，并通过协程调度器进行切换。 > - 特点： > - 协程是在用户态上实现的，不需要操作系统的介入，切换开销较小。 > - 协程可以进行主动调度，可以在代码中显式地控制切换点。 > - 协程之间可以共享数据，但需要注意同步和互斥。 > - 优点： > - 协程切换开销小，适合处理高并发的任务。 > - 控制权交给用户，更灵活地管理任务的执行流程。 > - 缺点： > - 协程的调度和同步需要由开发者自己管理，编程模型相对复杂。 > - 无法利用多核处理器的能力，无法实现真正的并行。 > > 综上所述，进程拥有独立的资源空间，适合隔离和并行处理；线程共享资源，适合处理并发任务；协程是一种轻量级的线程，切换开销小，适合高并发和灵活的任务调度。在选择使用进程、线程或协程时，需要根据具体的应用场景和需求来权衡它们的优缺点。 ### 引用和指针的区别，使用场景 > 引用和指针是C++语言中用于处理对象间的间接访问的两种机制，它们有一些区别和适用场景。 > > 1. 定义和声明： > - 引用：引用是一个别名，用于给已存在的对象起一个新的名称。在声明时，必须立即初始化，并且不能再引用其他对象。 > - 指针：指针是一个变量，用于存储对象的内存地址。在声明时，可以不初始化，并且可以指向不同的对象。 > > 2. 内存管理： > - 引用：引用不拥有内存，它只是给已存在的对象提供一个别名，因此不需要进行内存分配和释放。 > - 指针：指针可以通过动态内存分配（如`new`）来创建对象，并通过`delete`来释放内存。 > > 3. 空值（null）： > - 引用：引用必须在声明时初始化，并且不能引用空值。引用总是指向一个有效的对象。 > - 指针：指针可以被初始化为`nullptr`或者空指针，表示指向空地址或者无效的对象。 > > 4. 重新赋值： > - 引用：一旦引用被初始化为引用某个对象，就不能再引用其他对象。对引用的赋值实际上是修改了所引用对象的值。 > - 指针：指针可以被重新赋值，可以指向不同的对象。 > > 5. 空间占用： > - 引用：引用不占用额外的空间，它只是已存在对象的别名。 > - 指针：指针占用一定的空间，通常是机器字长的大小。 > > 使用场景： > - 引用适合用于函数参数传递和返回值，可以避免对象的拷贝，并且具有更直观的语义。引用还常用于用作函数的别名参数。 > - 指针适合用于动态分配内存、数组的访问和引用多个对象。指针具有更大的灵活性，可以在运行时进行动态的指向和修改。 > > 总的来说，引用和指针在C++中具有不同的语义和使用方式。引用是一个别名，用于简化对已存在对象的访问和操作，而指针则是一个变量，用于存储对象的内存地址，具有更多的灵活性和功能。在选择使用引用还是指针时，应根据具体的需求和情况来进行选择。 ### 网页式网盘新增服务 ![image-20231018213448195](README.assets/image-20231018213448195.png) ![image-20231018213505631](README.assets/image-20231018213505631.png) # 2023.10.18 猫眼娱乐 iOS开发工程师 校招 ## 一面 ### 介绍Workflow ### 大文件分片上传怎么实现的 算法题： - 翻转字符串 www.maoyan.com -> moc.nayoam.www - 只翻转每个部分 www.maoyan.com -> www.nayoam.moc ### 左值引用和右值引用 > 左值引用（L-value reference）和右值引用（R-value reference）是C++中引用类型的两种形式。 > > 左值引用（L-value reference）： > - 左值引用是通过使用`&`符号声明的引用类型，例如`int&`、`const T&`等。 > - 左值引用绑定到**具名对象**（左值），例如变量、表达式的结果等。 > - 左值引用可以被修改，并且具有生命周期，可以用作函数参数、返回值等。 > - 左值引用**不能绑定到临时对象**（右值）。 > > 右值引用（R-value reference）： > - 右值引用是通过使用`&&`符号声明的引用类型，例如`int&&`、`T&&`等。 > - 右值引用绑定到**临时对象**（右值），例如**字面量**、**表达式的结果**等。 > - 右值引用通常用于移动语义和完美转发，以提高性能和避免不必要的对象拷贝。 > - 右值引用可以被修改，并且具有生命周期，可以用作函数参数、返回值等。 > - 右值引用**只能绑定到临时对象（右值）**，不能绑定到具名对象（左值）。 > > 使用左值引用和右值引用可以实现不同的语义和操作，例如： > > ```cpp > void foo(int& lvalueRef) { > // 左值引用参数 > lvalueRef = 42; > } > > void bar(int&& rvalueRef) { > // 右值引用参数 > // ... > } > > int main() { > int x = 10; > foo(x); // 传递左值给左值引用参数 > > foo(20); // 错误，无法将右值绑定到左值引用参数 > > bar(30); // 传递右值给右值引用参数 > return 0; > } > ``` > > 在上面的示例中，`foo()`函数接受一个左值引用参数，因此可以将具名变量`x`作为参数传递给它。而在`main()`函数中，尝试将右值传递给左值引用参数时会导致编译错误。另一方面，`bar()`函数接受一个右值引用参数，可以接受临时对象作为参数。 > > 右值引用在C++11中引入，并为移动语义和完美转发提供了强大的支持，允许开发者更有效地管理资源和减少不必要的拷贝操作。 ### 单例模式和工厂模式 ### OSI七层网络模型和TCP/IP四层网络模型分别是什么？对应 ### GET与POST的区别 > GET和POST是HTTP协议中常用的两种请求方法，它们之间有以下区别： > > 1. 参数位置： > - GET请求：参数以查询字符串的形式附加在URL的末尾，例如`http://example.com/path?param1=value1¶m2=value2`。 > - POST请求：参数作为请求的主体内容发送，在请求头中指定参数的数据类型和长度。 > > 2. 参数长度限制： > - GET请求：由于参数附加在URL中，URL的长度会受到限制，不同的浏览器和服务器对URL长度的限制不同，通常在几千个字符左右。 > - POST请求：没有特定的长度限制，但是服务器和应用程序可能有其自己的限制。 > > 3. 数据安全： > - GET请求：参数以明文形式附加在URL中，可以被缓存、浏览器历史记录、代理服务器等记录和获取，因此不适合传输敏感信息。 > - POST请求：参数在请求主体中发送，不会直接暴露在URL中，相对于GET请求更安全，适合传输敏感信息。 > > 4. 可见性： > - GET请求：参数会出现在URL中，可以在浏览器地址栏中直接看到，可被书签保存，可被用户收藏。 > - POST请求：参数不会出现在URL中，对用户不可见。 > > 5. 幂等性： > - GET请求：通常是幂等的，即多次重复请求不会产生不同的结果，不会对服务器产生副作用。 > - POST请求：不一定是幂等的，多次重复请求可能会产生不同的结果，可以对服务器产生副作用。 > > 6. 缓存： > - GET请求：可以被缓存，可以利用浏览器缓存机制，进行页面的快速加载和节省带宽。 > - POST请求：不会被缓存，每次请求都会向服务器发送请求。 > > 根据上述区别，一般来说： > - GET请求适合获取资源，不对服务器产生影响，且参数较少且不敏感的情况。 > - POST请求适合提交数据、修改服务器状态，参数较多或者包含敏感信息的情况。 > > 需要根据具体的业务需求和安全性要求选择适当的请求方法。在实际应用中，GET和POST请求可以根据需要进行灵活选择。 ### HTTPS？SSL握手过程？CA证书？ > https://xiaolincoding.com/network/2_http/https_rsa.html#tls-%E6%8F%A1%E6%89%8B%E8%BF%87%E7%A8%8B ### TCP三次握手，四次挥手状态？为什么需要三次握手，为什么需要四次挥手？ ### 进程间通信方式？RPC机制？ ### MySQL的delete和drop的区别 > MySQL中的`DELETE`和`DROP`是两个不同的操作： > > 1. `DELETE`操作用于从表中删除行（记录）。它的语法如下： > ````sql > DELETE FROM table_name WHERE condition; > ``` > - `table_name`是要删除行的表名。 > - `condition`是一个可选的条件，用于指定要删除的行。如果省略条件，则将删除表中的所有行。 > > ``DELETE`操作是非破坏性操作，它只删除表中的行，而不删除表本身。删除操作可以回滚（如果在事务中使用），也可以使用`ROLLBACK`命令撤消。 > > 2. `DROP`操作用于删除整个表（包括表结构和数据）。它的语法如下： > ````sql > DROP TABLE table_name; > ``` > - `table_name`是要删除的表名。 > > ``DROP`操作是破坏性操作，它会永久删除表及其数据，且无法回滚。删除后的表无法恢复，除非有备份。 > > 总结： > - `DELETE`操作是删除表中的行，保留表结构。 > - `DROP`操作是删除整个表，包括表结构和数据。 > > 根据具体的需求，选择适合的操作。如果只需要删除部分数据，使用`DELETE`操作；如果需要完全删除表，使用`DROP`操作。在执行任何删除操作之前，务必谨慎，并确保备份重要数据。 # 2023.10.21 天纵游戏2024届校招笔试 Golang服务端 ## 1. 若要求排序是稳定的,且关键字为实数,则在下列排序方法中应选()排序为宜。 ==**A. 直接插入排序**== B. 选择排序 C. 基数排序 D. 快速排序 ## 2. 在含有n个结点的二叉排序树中查找某个关键字的结点时，最多进行（ ）次比较。 A．n／2 B．log2n C．log2n+1 ==**D．n**== > 当输入序列是一个有序序列，构造的二叉排序树是一个单支树，当查找一个不存在的关键字值或最后一个结点的关键字值时，需要n次比较。 ## 3. 为了避免传输过程中帧的丢失，数据链路层采用（）方法。 A.发送帧编号 B.循环冗余码 C.海明码 ==**D.计时器超时重发**== > 为了防止在传输过程中帧丢失，在可靠的数据链路层协议中，发送方对发送的每一个数据帧设计一个定时器，当计时器到期而该帧的确认帧仍没有到达时，发送方将重发该帧。为了保证接收方不会接收到重复帧，需要对每个发送的帧进行编号；汉明码和循环冗余校验码都用于差错控制。 ## 4. 顺序表的插入算法中,当n个空间已满时,可再申请增加分配m个空间。若申请失败,则说明系统没有（）可分配的存储空间 A.m个 B.m个连续的 C.n+m个 ==**D.n+m个连续的**== ## 5. 设有一个10阶的对称矩阵A\[10][10],采用压缩存储方式按行优先将矩阵中下三角部分的元素存入一维数组B中,A\[0][0]存入B[0]中,则A\[8][5]在B中的位置是()。 A. 32 ==**B. 41**== C. 53 D. 65 > 解析:设有一个10阶的对称矩阵A[10][10],采用压缩存储方式按行将矩阵中下三角部分的元素存入一维数组B[]中,A[0][0]存入B[0]中,则A[8][5]在B[]中41=1+2+3+4+ 5+6+7+8+5位置。 ## 6. 以下关于Cache的叙述中,正确的是()。 A. CPU中的Cache容量应大于CPU之外的Cache容量 ==**B. Cache的设计思想是在合理成本下提高命中率**== C. Cache的设计目标是容量尽可能与主存容量相等 D. 在容量确定的情况下,替换算法的时间复杂度是影响Cache命中率的关键因素 ## 7. 下列关于一个类的静态成员的描述中，不正确的是()。 A．该类的对象共享其静态成员变量的值 B．静态成员变量可被该类的所有方法访问 C．该类的静态方法只能访问该类的静态成员变量 ==**D．该类的静态数据成员变量的值不可修改**== > [分析] 本题考查面向对象开发中静态成员的基本知识。 面向对象开发方法中，静态成员的含义是所修饰的成员是属于类的，而不是属于某对象的。静态数据成员对该类只有一份，该类的所有对象共享静态数据成员，可被该类的所有方法访问，其值可以修改，但是不论是通过对象还是类对静态数据成员值的修改，都会反应到整个类。类的静态方法只能访问该类的静态数据成员。 ## 8. abcdef依次进栈,若在进栈操作时,允许出栈操作,则不可能得到的序列为() A．fedcba B．bcafed C．dcefba ==**D．cabdef**== > 根据栈“先进后出”的特点，并且在进栈操作的同时允许出栈操作，显然，答案D中C最先出栈，则此时栈内必定为a和b，但由于a先于b进栈，故要晚出栈。对于某个出栈的元素，在它之前进栈却晚出栈的元素必定是按逆序出栈的，其余答案均是可能出现的情况。 ## 9. 以下属于逻辑结构的是 A.顺序表 B.散列表 ==**C.有序表**== D.单链表 ![image-20231021112116897](README.assets/image-20231021112116897.png) ## 10. 表达式a*(b+c)-d的后缀表达式是（） A.abcd*+- ==**B.abc+\*d-**== C.abc*+d- D.-+*abcd ## 11. 请写出以下算法的时间复杂度： ```cpp for (m = 1; m < n; m++){ i = 1; while(i < n) { i = i * 2; } } ``` > 这段代码中有两层循环嵌套，外层循环使用变量 `m`，从 1 循环到 `n`。内层循环使用变量 `i`，从 1 开始，每次乘以 2，直到 `i` 大于等于 `n`。 > > 外层循环的迭代次数是 `n - 1`，因为 `m` 的取值范围是从 1 到 `n-1`。 > > 对于内层循环，初始值是 1，每次乘以 2，直到 `i` 大于等于 `n`。可以通过求解 `2^x >= n` 来得到内层循环的迭代次数，其中 `x` 是满足条件的最小整数。解这个不等式可以得到 `x = log2(n)`。因此，内层循环的迭代次数是 `log2(n)`。 > > 综上所述，这段代码的时间复杂度可以表示为： > > ``` > O((n - 1) * log2(n)) > ``` > > 在大 O 表示法中，忽略常数因子和低阶项，因此最终的时间复杂度为： > > ``` > O(n * log n) > ``` > > 因此，这段代码的时间复杂度为 `O(n * log n)`。 ## 12. C++实现 点是否在多边形内的判定方法 > 在C++中，可以使用射线法（Ray Casting）或点在多边形边界上的奇偶性判断方法来确定一个点是否在多边形内部。下面分别介绍这两种方法的实现。 > > 1. 射线法（Ray Casting）： > > ```cpp > #include > #include > > struct Point { > double x, y; > }; > > bool isPointInPolygon(const Point& point, const std::vector& polygon) { > int count = 0; > int n = polygon.size(); > > for (int i = 0, j = n - 1; i < n; j = i++) { > if (((polygon[i].y > point.y) != (polygon[j].y > point.y)) && > (point.x < (polygon[j].x - polygon[i].x) * (point.y - polygon[i].y) / (polygon[j].y - polygon[i].y) + polygon[i].x)) { > count++; > } > } > > return (count % 2 == 1); > } > > int main() { > Point point = {2.5, 3.5}; > std::vector polygon = {{1, 1}, {4, 1}, {4, 4}, {1, 4}}; > > if (isPointInPolygon(point, polygon)) { > std::cout << "Point is inside the polygon" << std::endl; > } else { > std::cout << "Point is outside the polygon" << std::endl; > } > > return 0; > } > ``` > > 在上述代码中，`isPointInPolygon`函数接受一个点和一个多边形的顶点集合作为参数，使用射线法判断点是否在多边形内部。函数内部使用一个计数器 `count`，并遍历多边形的边。如果点在边的两个端点的 y 坐标之间，并且点的 x 坐标小于边的延长线与点的交点的 x 坐标，那么将 `count` 值加1。最后，如果 `count` 值为奇数，则点在多边形内部，返回 `true`，否则返回 `false`。 > > 2. 奇偶性判断方法： > > ```cpp > #include > #include > > struct Point { > double x, y; > }; > > bool isPointInPolygon(const Point& point, const std::vector& polygon) { > int n = polygon.size(); > bool inside = false; > > for (int i = 0, j = n - 1; i < n; j = i++) { > if (((polygon[i].y > point.y) != (polygon[j].y > point.y)) && > (point.x < (polygon[j].x - polygon[i].x) * (point.y - polygon[i].y) / (polygon[j].y - polygon[i].y) + polygon[i].x)) { > inside = !inside; > } > } > > return inside; > } > > int main() { > Point point = {2.5, 3.5}; > std::vector polygon = {{1, 1}, {4, 1}, {4, 4}, {1, 4}}; > > if (isPointInPolygon(point, polygon)) { > std::cout << "Point is inside the polygon" << std::endl; > } else { > std::cout << "Point is outside the polygon" << std::endl; > } > > return 0; > } > ``` > > 这段代码与射线法方法类似，但不需要计数器。在每个边的交点处，通过改变 `inside` 变量的值来切换奇偶性。如果 `inside` 最终为 `true`，则点在多边形内部，返回 `true`，否则返回 `false`。 > > 这两种方法都可以用于简单的多边形判定。但对于复杂的多边形，还需要考虑特殊情况和边界条件。此外，对于浮点数比较，需要注意数值精度问题。