数据结构练习卷（附答案）

免费可打印的数据结构练习卷：8 道题，从简单到考试水平，附答案。可打印或另存为 PDF。

新练习卷在线练习，附提示

教师请注意： 可免费打印、复印并在课堂上使用。每份新练习题都有新的数值和独立的答案。欢迎在课程页面添加指向 ExamProblems 的链接。

姓名: ____________________   日期: ____________

1.简单

哪种操作在数组中很慢，但在链表头部却很快？

  1. A通过索引读取最后一个元素
  2. B求定长数组的长度
  3. C在开头插入元素
  4. D访问第 5 个元素
2.简单

映射（map，字典）存储什么？

  1. A按大小排序的值
  2. B仅按插入顺序存储值
  3. C由相等的键组成的对
  4. D键唯一的键值对
3.简单

什么是带权图？

  1. A存储在磁盘上的图
  2. B每条边都有一个数值（如代价或距离）的图
  3. C边数多于顶点数的图
  4. D有些顶点因为边更多而比其他顶点更重的图
4.中等

在平衡二叉搜索树中查找一个键的时间复杂度是多少？

  1. AO(log n)
  2. BO(n log n)
  3. CO(1)
  4. DO(n)
5.中等

用两个栈实现一个队列：入队时压入 "in" 栈，出队时从 "out" 栈弹出，"out" 栈为空时从 "in" 栈重新填充。每次操作的均摊代价是多少？

  1. AO(1)
  2. BO(log n)
  3. CO(n²)
  4. DO(n)
6.中等

后缀表达式 3 4 + 2 * 的值是多少？

  1. A14
  2. B11
  3. C10
  4. D24
7.困难

在没有按秩合并和路径压缩的情况下，含 n 个元素的并查集结构中一次 find 操作的最坏代价是多少？

  1. AO(log n)
  2. BO(n)
  3. CO(α(n))
  4. DO(1)
8.困难

在简单均匀哈希假设下，在含 n 个键、m 个桶的拉链法哈希表中查找的期望时间是多少？

  1. AO(1 + α)，其中 α = n / m
  2. BO(m)
  3. CO(n)
  4. DO(log n)

答案

  1. 1. C · 在开头插入元素
  2. 2. D · 键唯一的键值对
  3. 3. B · 每条边都有一个数值（如代价或距离）的图
  4. 4. A · O(log n)
  5. 5. A · O(1)
  6. 6. A · 14
  7. 7. B · O(n)
  8. 8. A · O(1 + α)，其中 α = n / m

完整分步解答：请在 examproblems.com 上练习本主题。