云南曲靖市宣威市民族中学等校2025-2026学年高二下学期7月期末考试 信息技术试题

**基本信息** 以数据结构为核心，通过图书借阅系统、外卖配送等真实场景命题，考查信息意识与计算思维。 **题型特征** |题型|题量/分值|知识覆盖|命题特色| |----|-----------|----------|----------| |选择题|12题/36分|栈、队列、哈希表等数据结构基础|通过购物评价审核等场景考查概念理解| |非选择题|7题/64分|排序算法、DAG图应用等综合知识|外卖配送路线规划题融合数据结构特性分析与实际问题解决|

2025—2026学年高二年级信息技术下学期期末检测试卷 满分：100分 考试时间：60分钟 注意事项： 1.答卷前，考生务必将自己的姓名、准考证号填写在答题卡上。 2.选择题时，选出每小题答案后，用2B铅笔把答题卡上对应题目的答案标号涂黑。如需改动，用橡皮擦干净后，再选涂其他答案标号。 3.回答非选择题时，将答案写在答题卡上。写在本试卷上无效。 一、选择题：本题共12小题，每小题3分，共36分。在每小题给出的四个选项中，只有一项是符合题目要求的。 1.学校图书馆开发了一套图书借阅管理系统，每本书都有唯一的图书编号，读者借书时系统会记录借阅人信息和借阅时间。从数据结构的角度看，每本书的借阅记录最适合采用哪种数据结构来组织？（ ） A.数组，因为借阅记录数量固定 B.栈，因为借阅记录遵循后进先出原则 C.队列，因为借阅记录按照时间先后顺序处理 D.链表，因为借阅记录需要频繁插入和删除 2.某购物网站的商品评价系统中，用户提交评价后需要经过审核才能显示。审核人员按照提交时间的先后顺序处理评价，先提交的先审核。这种处理方式最符合以下哪种数据结构的特性？（ ） A.栈（先进后出） B.队列（先进先出） C.数组（随机存取） D.二叉树（层次遍历） 3.在Python中，表达式 "hello" + "world" 的结果是 "helloworld"，这里所体现的数据结构操作是（ ） A.字符串的拼接操作 B.列表的合并操作 C.元组的连接操作 D.字典的更新操作 4.某停车场管理系统使用栈来模拟车辆进出过程。车辆进入时执行入栈操作，车辆离开时执行出栈操作。若某时刻栈中从栈底到栈顶依次停放车辆A、B、C，则以下哪种出栈顺序是可能的？（ ） A.A、B、C B.C、B、A C.B、A、C D.A、C、B 5.在电商平台的商品搜索功能中，当用户输入关键词后，系统需要从海量商品信息中快速找到匹配的商品。以下哪种数据结构的应用最有助于提高搜索效率？（ ） A.使用链表存储所有商品信息 B.使用哈希表建立关键词到商品列表的映射 C.使用栈存储用户的搜索历史 D.使用队列存储待处理的搜索请求 6.某校排课系统需要为每个班级安排课程，每门课程有固定的教室和时间段，且同一教室同一时间段不能安排两门课程。这种约束关系最适合用以下哪种数据结构来建模？（ ） A.线性表 B.栈 C.队列 D.树或图 7.在公交刷卡系统中，乘客上车刷卡和下车刷卡的数据被实时记录。若某辆公交车上有50个座位，系统需要快速统计当前车上乘客人数，以下哪种数据结构的操作效率最高？（ ） A.使用栈记录乘客上下车 B.使用队列记录乘客上下车 C.使用一个整型变量记录当前人数 D.使用链表记录每个乘客的信息 8.以下关于递归算法的描述，正确的是（ ） A.递归算法一定比迭代算法效率高 B.递归算法必须有一个明确的终止条件 C.任何递归算法都可以转化为非递归算法 D.递归算法不需要使用栈 9.某社交平台的好友推荐功能中，系统需要计算用户之间的共同好友数量。从数据结构的角度看，每位用户的好友列表最适合存储为（ ） A.数组 B.栈 C.集合（Set） D.队列 10.在文件系统的目录结构中，根目录下包含多个子目录，每个子目录又可以包含文件或更下一级的子目录。这种层次化的组织结构与以下哪种数据结构最为相似？（ ） A.线性表 B.栈 C.队列 D.树 11.某在线文档编辑系统支持“撤销”（Undo）操作，用户每次编辑后都可以撤销到之前的状态。这种功能的实现最适合采用的数据结构是（ ） A.队列 B.栈 C.链表 D.二叉树 12.某快递分拣中心需要根据目的地将包裹分类，每个目的地对应一个存放区域。系统需要快速判断某个包裹应该放入哪个区域。以下哪种数据结构的应用最合适？（ ） A.使用栈存储待分拣的包裹 B.使用队列存储待分拣的包裹 C.使用哈希表建立目的地到区域的映射 D.使用链表存储所有包裹信息 二、非选择题：本题共7小题，共64分。 13.（8分）某外卖平台需要为骑手规划最优配送路线。平台上有多个订单需要配送，每个订单有取餐地址和送餐地址，骑手从配送站出发，需要依次完成所有订单的取餐和送餐。 （1）若平台按照订单生成时间的先后顺序安排骑手依次处理，先产生的订单先处理。这种处理方式体现的是哪种数据结构的特性？（2分） （2）在实际配送中，骑手有时需要临时调整配送顺序（比如先送距离近的订单）。如果用一个列表来存储待配送的订单，在列表中频繁进行插入和删除操作时，使用哪种数据结构效率更高？请说明理由。（3分） （3）配送完成后，系统需要记录骑手的历史配送记录以便后续查询和分析。若需要按照时间顺序快速查询某段时间内的配送记录，应该选择哪种数据结构来存储？请简要说明。（3分） 14.（10分）某学校教务处需要统计各班级的期末考试成绩。成绩数据以表格形式存储，每行包括学号、姓名、班级、语文、数学、英语、总分等字段。 （1）若要将所有学生的成绩按照总分从高到低排序，常用的排序算法有哪些？请至少写出两种，并简要说明其中一种的基本思路。（4分） （2）教务处需要根据学号快速查找某位学生的成绩。如果学生数量为1000人，使用顺序查找和二分查找在最坏情况下的查找次数分别是多少？（3分） （3）如果要进一步提高按学号查找的效率，除了二分查找外，还可以采用什么数据结构？请说明其原理。（3分） 15.（10分）某公司开发了一个“智能便签”应用，用户可以创建、编辑和删除便签。应用需要支持以下功能：①用户每次编辑后都可以撤销到之前的版本；②用户可以在任意位置插入或删除文本；③应用需要快速定位到某篇便签的特定位置。 （1）为了实现撤销功能，应该采用哪种数据结构来存储编辑历史？请说明理由。（3分） （2）便签的文本内容需要支持在任意位置插入和删除字符，使用数组和链表两种数据结构哪个更合适？请分析各自的优缺点。（4分） （3）若用户有大量便签，需要按照创建时间倒序显示便签列表，应该选择哪种数据结构来存储便签集合？请简要说明。（3分） 16.（8分）某电商平台在“双十一”大促期间，需要处理海量的用户请求。系统采用消息队列来缓冲请求，服务器从队列中依次取出请求进行处理。 （1）消息队列采用的是哪种数据结构的特性？这种特性在大促场景下有什么优势？（4分） （2）如果某个请求处理失败，系统需要将该请求重新放入队列等待重试。这种操作在队列中如何实现？（4分） 17.（10分）某在线学习平台提供了课程推荐功能。系统根据用户已学习的课程，推荐可能感兴趣的未学课程。平台将课程之间的先修关系组织成一个有向无环图（DAG）。 （1）什么是有向无环图？它在课程先修关系建模中有什么优势？（4分） （2）如果用户想学习某门课程，系统需要判断用户是否已经完成了所有先修课程。这个问题的本质是什么？（3分） （3）在课程推荐场景中，除了图结构外，还可以使用哪些数据结构来辅助实现推荐功能？请举例说明。（3分） 18.（8分）某音乐App的“每日推荐”功能需要根据用户的听歌历史推荐歌曲。系统记录了用户最近收听的100首歌曲。 （1）若需要记录用户最近收听的歌曲，并且当超过100首时自动淘汰最久未听的歌曲，应该采用什么数据结构？请说明理由。（4分） （2）推荐算法需要快速判断某首歌曲是否在用户的收听历史中，使用哪种数据结构可以提高判断效率？请简要说明。（4分） 19.（10分）某智慧校园项目需要设计一个“校园卡消费记录查询系统”。学生的校园卡每次消费都会生成一条记录，包括消费时间、金额、消费地点等信息。系统需要支持以下功能：①按时间顺序查询某学生的所有消费记录；②按消费地点统计消费总额；③快速查询某学生的最近一次消费记录。 （1）对于功能①，应该采用什么数据结构来存储单个学生的消费记录？请说明理由。（3分） （2）对于功能②，应该采用什么数据结构来组织各消费地点的消费数据？请说明理由。（3分） （3）对于功能③，如何设计数据结构才能高效地查询最近一次消费记录？（4分） 参考答案 一、选择题 1.D  2.B  3.A  4.B  5.B  6.D  7.C  8.B  9.C  10.D  11.B  12.C 二、非选择题 13.（8分） （1）队列的先进先出（FIFO）特性。（2分） （2）使用链表效率更高（1分）。因为链表在插入和删除元素时不需要移动其他元素，只需要修改指针即可，时间复杂度为O(1)（1分）；而数组在中间位置插入或删除元素时需要移动后续元素，时间复杂度为O(n)（1分）。 （3）使用链表或动态数组（如Python的列表）均可（1分）。因为这些结构支持按索引访问，可以方便地按时间顺序遍历和查询（1分）；同时可以根据需要动态扩展存储空间（1分）。（其他合理答案酌情给分） 14.（10分） （1）冒泡排序、选择排序、插入排序、快速排序、归并排序等（写出两种即可，各1分，共2分）。以冒泡排序为例：依次比较相邻的两个元素，如果顺序错误就交换位置，每一轮将最大（或最小）的元素“冒泡”到序列的一端，重复n-1轮完成排序（2分）。 （2）顺序查找最坏情况下需要查找1000次（1.5分）；二分查找最坏情况下需要查找log₂1000≈10次（1.5分）。 （3）可以采用哈希表（1分）。原理：通过哈希函数将学号映射到数组中的某个位置，实现O(1)时间复杂度的查找（2分）。 15.（10分） （1）采用栈（1分）。理由：撤销操作需要按照编辑的逆序进行恢复，符合栈的“后进先出”（LIFO）特性（2分）。 （2）链表更合适（1分）。数组的优点是支持随机访问，查找速度快（1分）；缺点是在中间位置插入或删除时需要移动大量元素，效率低（1分）。链表的优点是在任意位置插入和删除操作方便，只需修改指针（1分）；缺点是查找特定位置的元素需要遍历，效率较低（1分）。对于频繁在任意位置插入和删除的场景，链表更优。 （3）可以使用链表或动态数组（如Python的列表）（1分）。因为可以按照创建时间将便签组织成有序序列，便于按时间倒序遍历和显示（2分）。 16.（8分） （1）消息队列采用的是队列的先进先出（FIFO）特性（2分）。优势：在大促场景下，海量请求集中涌入，消息队列可以起到缓冲作用，防止服务器过载（1分）；保证请求按照到达顺序被公平处理（1分）。 （2）将失败的请求重新入队（2分），即执行队列的入队操作，将该请求添加到队列尾部，等待后续再次被取出处理（2分）。 17.（10分） （1）有向无环图（DAG）是由顶点和有向边组成的图结构，其中不存在任何环路（2分）。优势：可以清晰地表示课程之间的先后依赖关系，且无环保证了课程学习顺序的合理性，不会出现循环依赖（2分）。 （2）本质是判断在DAG中，从起点（已学课程）到目标课程是否存在一条路径，且目标课程的所有前驱节点（先修课程）是否都已被访问过（3分）。 （3）还可以使用哈希表记录用户已学课程，实现快速查询（1.5分）；使用优先队列（堆）对推荐课程按相关度进行排序，优先推荐相关度高的课程（1.5分）。（其他合理答案酌情给分） 18.（8分） （1）采用队列（1分）。理由：队列具有先进先出的特性，当队列长度超过100时，将队首元素（最久未听的歌曲）出队，新歌曲从队尾入队，正好满足“淘汰最久未听歌曲”的需求（3分）。 （2）使用哈希表（如Python的集合Set或字典Dict）（2分）。哈希表可以实现O(1)时间复杂度的查找，比遍历列表的O(n)效率高得多（2分）。 19.（10分） （1）采用链表或动态数组（如Python的列表）（1分）。理由：消费记录需要按时间顺序存储和查询，链表或动态数组可以方便地按顺序遍历（2分）。 （2）采用哈希表（字典）（1分）。以消费地点为键，以该地点的消费总额或消费记录列表为值（1分），可以实现按地点快速查询和统计（1分）。 （3）可以在学生记录中单独维护一个指针或引用，始终指向最近一条消费记录（2分）；每次产生新消费时更新该指针（1分）；查询时直接返回指针指向的记录，时间复杂度为O(1)（1分）。（其他合理答案酌情给分） 2/2 学科网（北京）股份有限公司 $