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

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

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

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

姓名: ____________________   日期: ____________

1.简单

树的高度通常定义为：

  1. A树中节点的总数，包括根和每个叶子
  2. B树中叶子的个数
  3. C从根到叶子的最长路径上的边数
  4. D根的子节点个数
2.简单

什么是带权图？

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

哈希表的负载因子是什么？

  1. A从磁盘加载表所需的时间
  2. B迄今为止的冲突次数
  3. C已存储元素的个数除以桶的个数
  4. D桶的个数除以所存储键的平均长度
4.中等

如果按已排序的顺序插入键，含 n 个节点的二叉搜索树在最坏情况下的高度是多少？

  1. An（退化为链表）
  2. B√n
  3. Clog₂ n
  4. D1
5.中等

链表中哨兵（哑）节点的作用是什么？

  1. A防止链表增长超过固定的最大节点数
  2. B存储元素的个数
  3. C使链表有序
  4. D通过消除头部或尾部的特殊情况来简化代码
6.中等

在二叉最小堆中，extract-min 是如何工作的？

  1. A删除数组的最后一个元素
  2. B删除根，并把所有元素左移一位
  3. C在所有叶子中查找新的最小值
  4. D把最后一个元素移到根上，再将其下沉
7.困难

双重哈希主要减轻了线性探测的哪个问题？

  1. A需要哈希函数
  2. B读取键值需要 O(n) 的代价
  3. C一次聚集，即形成长串的被占用槽位
  4. D需要在表中存储键
8.困难

伸展树（splay tree）在每次访问之后做什么？

  1. A把被访问的节点移到叶子
  2. B把整棵树重建成平衡形式
  3. C对查找路径上的节点重新着色
  4. D通过旋转把被访问的节点移到根

答案

  1. 1. C · 从根到叶子的最长路径上的边数
  2. 2. D · 每条边都有一个数值（如代价或距离）的图
  3. 3. C · 已存储元素的个数除以桶的个数
  4. 4. A · n（退化为链表）
  5. 5. D · 通过消除头部或尾部的特殊情况来简化代码
  6. 6. D · 把最后一个元素移到根上，再将其下沉
  7. 7. C · 一次聚集，即形成长串的被占用槽位
  8. 8. D · 通过旋转把被访问的节点移到根

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