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

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

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

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

姓名: ____________________   日期: ____________

1.简单

向栈顶添加元素的栈操作叫什么？

  1. APop
  2. BPeek
  3. CEnqueue
  4. DPush
2.简单

什么是双端队列（deque）？

  1. A只允许在尾部删除的队列
  2. B按优先级排序的队列
  3. C允许在两端插入和删除的结构
  4. D共享一个数组的两个独立队列
3.简单

什么是有向图？

  1. A边具有从一个顶点指向另一个顶点的方向的图
  2. B每对不同顶点之间都有边相连的图
  3. C没有环的图
  4. D所有边都带权的图
4.中等

在用数组存储的二叉最小堆（索引从 0 开始）中，索引为 i 的节点的子节点位于：

  1. Ai + 1 和 i + 2
  2. Bi/2 和 i/2 + 1
  3. C2i + 1 和 2i + 2
  4. D2i 和 2i + 1
5.中等

后缀表达式 3 4 + 2 * 的值是多少？

  1. A24
  2. B14
  3. C11
  4. D10
6.中等

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

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

在简单均匀哈希假设下，在含 n 个键、m 个桶的拉链法哈希表中查找的期望时间是多少？

  1. AO(m)
  2. BO(log n)
  3. CO(n)
  4. DO(1 + α)，其中 α = n / m
8.困难

在循环缓冲区中，front == rear 既可能表示空，也可能表示满。区分它们的一种常见方法是什么？

  1. A每当 front 等于 rear 时就始终清空缓冲区，使其状态为空
  2. B把 front 和 rear 存储在同一个变量中
  3. C使缓冲区大小为 2 的幂
  4. D另外保存一个元素计数，或者始终留一个槽位不用

答案

  1. 1. D · Push
  2. 2. C · 允许在两端插入和删除的结构
  3. 3. A · 边具有从一个顶点指向另一个顶点的方向的图
  4. 4. C · 2i + 1 和 2i + 2
  5. 5. B · 14
  6. 6. B · 把它放在数组末尾，只要它违反堆性质就将其上浮（sift up）
  7. 7. D · O(1 + α)，其中 α = n / m
  8. 8. D · 另外保存一个元素计数，或者始终留一个槽位不用

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