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

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

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

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

姓名: ____________________   日期: ____________

1.简单

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

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

哈希表以什么形式存储数据？

  1. A键有序的树
  2. B通过哈希函数定位的键值对
  3. C仅为有序列表
  4. D定长字符串
3.简单

哈希表中的哈希函数做什么？

  1. A对表中的键排序
  2. B把键映射到表中的一个下标
  3. C统计存储了多少个键
  4. D对表中的值加密
4.中等

一棵高度为 h（以边数计）的满二叉树有多少个节点？

  1. A2h + 1
  2. B2h+1 − 1
  3. Ch2
  4. D2h
5.中等

对二叉搜索树进行中序遍历时，访问键的顺序是：

  1. A始终为降序
  2. B升序排列
  3. C层序
  4. D插入顺序
6.中等

一棵二叉树的根为 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. D5 4 3 2 1
7.困难

把键 5、3、8、1 按此顺序插入一个空的基于数组的二叉最小堆。最终的数组是什么？

  1. A[1, 3, 5, 8]
  2. B[1, 3, 8, 5]
  3. C[3, 1, 8, 5]
  4. D[1, 5, 8, 3]
8.困难

建立在 n 个数的数组上的树状数组（Fenwick tree，binary indexed tree）以 O(log n) 支持哪些操作？

  1. A以 O(1) 求中位数
  2. B前缀和查询和单个元素更新
  3. C在任意位置插入元素
  4. D对数组排序和二分查找

答案

  1. 1. A · 栈（Stack）
  2. 2. B · 通过哈希函数定位的键值对
  3. 3. B · 把键映射到表中的一个下标
  4. 4. B · 2h+1 − 1
  5. 5. B · 升序排列
  6. 6. C · 4 5 2 3 1
  7. 7. B · [1, 3, 8, 5]
  8. 8. B · 前缀和查询和单个元素更新

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