北京邮电大学809数据结构2027考研真题模拟含答案

北京邮电大学硕士研究生入学考试模拟卷

科目代码及名称：809　数据结构

适用专业：计算机科学与技术、软件工程等

本试卷满分 150 分　·　考试时间 180 分钟

答题须知　注意事项：1.答案一律写在答题纸上，写在试题纸或草稿纸上无效；2.算法设计题可用类 C/伪代码描述，并分析时间复杂度。

『第一部分　试　题』

一、单项选择题（每小题 2 分，共 30 分）

（1）在长度为 n 的顺序表中，等概率地将新元素插入到 n+1 个可能位置之一时，需向后移动元素的期望次数为？

A. n-i+1

B. (n-i+1)/2

C. n/2

D. n-i

二、填空题（每小题 2 分，共 20 分）

（16）在含 n 个元素的顺序表中进行按值查找（仅考虑查找成功且各位置等概率），平均比较次数为 ____。

三、简答题（每小题 10 分，共 40 分）

（26）试比较线性表的顺序存储结构与链式存储结构（单链表）的优缺点，并说明各自适用的场景。

四、算法设计题（每小题 15 分，共 60 分）

（30）设顺序表 L 用数组 data[0..n-1] 存放，元素为整数。请设计算法删除其中所有值等于给定值 x 的元素，要求时间复杂度 O(n)、辅助空间 O(1)，并保持其余元素相对次序不变。给出算法思路、类 C 伪代码并分析时间复杂度。

『第二部分　参考答案与解析』

1.【单项选择题】在长度为 n 的顺序表中，等概率地将新元素插入到 n+1 个可能位置之一时，需向后移动元素的期望次数为？

答案：C

解析：等概率插入到 n+1 个位置，移动次数分别为 n, n-1, ..., 0，平均值 = (n+(n-1)+...+0)/(n+1) = n(n+1)/(2(n+1)) = n/2。选项 B 表示插入到第 i 个位置的确切移动次数，并非平均情况。