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

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

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

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

姓名: ____________________   日期: ____________

1.简单

哈希表中的哈希函数做什么？

  1. A把键映射到表中的一个下标
  2. B对表中的键排序
  3. C对表中的值加密
  4. D统计存储了多少个键
2.简单

哪种数据结构遵循"后进先出"（LIFO）原则？

  1. A栈（Stack）
  2. B链表（Linked list）
  3. C队列（Queue）
  4. D哈希表（Hash table）
3.简单

在单链表中，最后一个节点的 next 指针包含什么？

  1. A链表中节点的个数
  2. B前一个节点的地址
  3. C第一个节点的地址
  4. DNull（没有节点）
4.中等

字典树（Trie，前缀树）特别适合用于：

  1. A求最短路径
  2. B对数字排序
  3. C存储矩阵
  4. D自动补全等前缀查找
5.中等

哈希表在负载因子超过阈值后进行再哈希（rehash）时会发生什么？

  1. A对现有的键原地排序
  2. B只把发生冲突的键移到表末尾的新溢出链表中
  3. C分配一个更大的表，并把每个键重新插入
  4. D删除最旧的键以腾出空间
6.中等

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

  1. AO(1)
  2. BO(log n)
  3. CO(n²)
  4. DO(n)
7.困难

为什么服务器可能会从一个通用哈希函数族中随机选择其哈希函数？

  1. A保证任何两个键永远不会发生冲突，无论攻击者发送什么键
  2. B使哈希表有序
  3. C使攻击者极难选出许多全部发生冲突的键
  4. D免去对表进行扩容的需要
8.困难

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

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

答案

  1. 1. A · 把键映射到表中的一个下标
  2. 2. A · 栈（Stack）
  3. 3. D · Null（没有节点）
  4. 4. D · 自动补全等前缀查找
  5. 5. C · 分配一个更大的表，并把每个键重新插入
  6. 6. A · O(1)
  7. 7. C · 使攻击者极难选出许多全部发生冲突的键
  8. 8. A · O(1 + α)，其中 α = n / m

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