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

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

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

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

姓名: ____________________   日期: ____________

1.简单

树中节点的深度是：

  1. A从根到该节点的边数
  2. B其子树中的节点个数
  3. C从该节点到最深叶子的边数
  4. D该节点的子节点个数
2.简单

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

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

哪种操作对数组是 O(1)，对单链表却是 O(n)？

  1. A在头部插入
  2. B读取第一个元素
  3. C删除头元素
  4. D访问下标为 i 的元素
4.中等

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

  1. A20
  2. B40
  3. C50
  4. D70
5.中等

一个道路网络有 100,000 个路口，每个路口大约与另外 4 个路口相连。哪种表示方法最合适？

  1. A一个有序的顶点数组
  2. B邻接表
  3. C一个由边组成的二叉堆
  4. D邻接矩阵
6.中等

在一个有 n 个元素的数组中间插入一个元素，代价是多少？

  1. AO(1)，因为下标已知
  2. BO(n²)，因为每个元素要移动 n 次
  3. CO(n)，因为后面的元素必须移动
  4. DO(log n)，因为使用二分查找
7.困难

在一棵根为 50、左子树为 30（子节点 20、40）、右子树为 70（子节点 60、80）的 BST 中，用中序后继删除根。哪个键成为新的根？

  1. A70
  2. B60
  3. C40
  4. D80
8.困难

哪种结构能以总共 O(n) 的时间求出数组中每个大小为 k 的窗口的最大值？

  1. A为每个窗口重建的最小堆
  2. B一个按值递减顺序保存下标的双端队列
  3. C通过移动元素来更新的有序数组
  4. D由窗口元素组成的单链表

答案

  1. 1. A · 从根到该节点的边数
  2. 2. A · 通过哈希函数定位的键值对
  3. 3. D · 访问下标为 i 的元素
  4. 4. A · 20
  5. 5. B · 邻接表
  6. 6. C · O(n)，因为后面的元素必须移动
  7. 7. B · 60
  8. 8. B · 一个按值递减顺序保存下标的双端队列

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