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

免费可打印的数据结构练习卷：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.中等

把键 50、30、70、20、40 按此顺序插入一棵空的二叉搜索树。30 的左子节点是什么？

  1. A40
  2. B70
  3. C20
  4. D50
5.中等

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

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

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

  1. A2
  2. B没有最大值
  3. C0.5
  4. D1
7.困难

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

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

红黑树的规则对含 n 个键的树的高度给出了什么保证？

  1. A高度至多为 2 log2(n + 1)
  2. B高度至多为 n / 2
  3. C高度恰好为 log2 n
  4. D高度至多为 log2 n + 1

答案

  1. 1. B · 与它相连的边数
  2. 2. B · 从根到该节点的边数
  3. 3. D · 拥有同一个父节点的节点
  4. 4. C · 20
  5. 5. B · 把它放在数组末尾，只要它违反堆性质就将其上浮（sift up）
  6. 6. D · 1
  7. 7. C · 利用多层前向指针，实现期望 O(log n) 的查找
  8. 8. A · 高度至多为 2 log2(n + 1)

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