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

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

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

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

姓名: ____________________   日期: ____________

1.简单

图由什么组成？

  1. A只有根和叶子
  2. B行和列
  3. C只有键和哈希值
  4. D由边（edge）连接的顶点（vertex，即节点）
2.简单

作为抽象数据类型，集合（set）的定义性特征是什么？

  1. A它存储元素且没有重复
  2. B它按有序方式存储元素
  3. C它只允许在一端访问
  4. D它存储键值对
3.简单

双向链表中的每个节点包含什么？

  1. A两份数据和一个指针
  2. B数据、指向下一个节点的指针和指向前一个节点的指针
  3. C数据和两个指针，一个指向下一个节点，一个指向再下一个节点
  4. D只有数据和指向下一个节点的指针
4.中等

一棵二叉树的根为 1，左子节点为 2，右子节点为 3；节点 2 的子节点为 4（左）和 5（右）。前序遍历的结果是什么？

  1. A1 2 4 5 3
  2. B4 2 5 1 3
  3. C4 5 2 3 1
  4. D1 2 3 4 5
5.中等

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

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

如何向二叉堆中插入一个新元素？

  1. A把它放在根上，再将其下沉（sift down）
  2. B从头重建整个堆
  3. C把它放在数组末尾，只要它违反堆性质就将其上浮（sift up）
  4. D通过把所有更大的元素右移一位，将它插入到有序位置
7.困难

红黑树必须满足哪条性质？

  1. A每个红色节点的子节点必须是红色，因此红色节点总是沿着通向叶子的路径连成不间断的链
  2. B从任一节点到其所有后代叶子的每条路径上，黑色节点的数量都相同
  3. C根节点必须是红色
  4. D每个节点都必须是红色
8.困难

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

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

答案

  1. 1. D · 由边（edge）连接的顶点（vertex，即节点）
  2. 2. A · 它存储元素且没有重复
  3. 3. B · 数据、指向下一个节点的指针和指向前一个节点的指针
  4. 4. A · 1 2 4 5 3
  5. 5. A · O(log n)
  6. 6. C · 把它放在数组末尾，只要它违反堆性质就将其上浮（sift up）
  7. 7. B · 从任一节点到其所有后代叶子的每条路径上，黑色节点的数量都相同
  8. 8. A · O(n)

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