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

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

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

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

姓名: ____________________   日期: ____________

1.简单

哪种数据结构最适合实现文本编辑器中的"撤销"（undo）功能？

  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.中等

AVL 树在每个节点上维持什么平衡条件？

  1. A每个节点的两棵子树包含完全相同数量的节点
  2. B左右子树的高度之差至多为 1
  3. C每个节点都被着成红色或黑色
  4. D所有叶子都恰好位于同一深度
5.中等

对于有 V 个顶点、E 条边的图，邻接表占用多少内存？

  1. AO(V²)
  2. BO(V + E)
  3. CO(V × E)
  4. DO(E²)
6.中等

AVL 树和红黑树保证：

  1. A通过再平衡使高度为 O(log n)
  2. B没有节点拥有两个子节点
  3. C键按插入顺序存储
  4. D在任何情况下查找都是常数时间
7.困难

在含 n 个元素的二叉最小堆中查找任意一个键需要多长时间？

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

如何只用 O(1) 的额外内存检测一个单链表中是否有环？

  1. A计数节点，直到计数超过链表的长度字段
  2. B对链表排序并寻找重复元素
  3. C让一个指针每次走一步，另一个每次走两步，检查它们是否相遇
  4. D把每个访问过的节点存入一个哈希集合

答案

  1. 1. C · 栈
  2. 2. B · 动态数组可以通过移到更大的内存块来增长
  3. 3. A · 通过哈希函数定位的键值对
  4. 4. B · 左右子树的高度之差至多为 1
  5. 5. B · O(V + E)
  6. 6. A · 通过再平衡使高度为 O(log n)
  7. 7. A · O(n)
  8. 8. C · 让一个指针每次走一步，另一个每次走两步，检查它们是否相遇

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