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

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

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

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

姓名: ____________________   日期: ____________

1.简单

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

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

什么是带权图？

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

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

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

Dijkstra 算法使用哪种抽象数据类型来选择下一个要处理的顶点？

  1. A栈
  2. B无序集合
  3. C最小优先队列
  4. DFIFO 队列
5.中等

为什么在实践中遍历数组往往比遍历同样长度的链表快得多？

  1. A数组遍历总共是 O(1)，而链表遍历是 O(n)
  2. B数组元素是连续存放的，因此能很好地利用 CPU 缓存
  3. C数组比较数值所用的指令更少
  4. D链表总是把元素存储在磁盘上
6.中等

在使用开放寻址法的哈希表中，可能的最大负载因子是多少？

  1. A0.5
  2. B2
  3. C1
  4. D没有最大值
7.困难

与有序链表相比，跳表（skip list）的主要优势是什么？

  1. A它以无序方式存储键
  2. B保证 O(1) 的查找，因为每个节点都存有指向其他所有节点的指针
  3. C利用多层前向指针，实现期望 O(log n) 的查找
  4. D它不占用额外内存
8.困难

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

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

答案

  1. 1. C · 在开头插入元素
  2. 2. B · 每条边都有一个数值（如代价或距离）的图
  3. 3. B · 栈（Stack）
  4. 4. C · 最小优先队列
  5. 5. B · 数组元素是连续存放的，因此能很好地利用 CPU 缓存
  6. 6. C · 1
  7. 7. C · 利用多层前向指针，实现期望 O(log n) 的查找
  8. 8. C · 从任一节点到其所有后代叶子的每条路径上，黑色节点的数量都相同

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