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

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

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

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

姓名: ____________________   日期: ____________

1.简单

图由什么组成？

  1. A只有根和叶子
  2. B由边（edge）连接的顶点（vertex，即节点）
  3. C只有键和哈希值
  4. D行和列
2.简单

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

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

树的根是什么？

  1. A值最大的节点
  2. B中间的任意节点
  3. C没有父节点的最顶端节点
  4. D没有子节点的节点
4.中等

循环缓冲区（环形缓冲区）通常用于实现：

  1. A二叉搜索树
  2. B图的遍历
  3. C哈希函数
  4. D固定大小的队列
5.中等

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

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

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

  1. A升序排列
  2. B层序
  3. C插入顺序
  4. D始终为降序
7.困难

对以邻接矩阵存储的、有 V 个顶点的图进行广度优先搜索，运行时间是多少？

  1. AO(V²)
  2. BO(V + E)
  3. CO(E log V)
  4. DO(V)
8.困难

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

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

答案

  1. 1. B · 由边（edge）连接的顶点（vertex，即节点）
  2. 2. B · 访问下标为 i 的元素
  3. 3. C · 没有父节点的最顶端节点
  4. 4. D · 固定大小的队列
  5. 5. A · 把它放在数组末尾，只要它违反堆性质就将其上浮（sift up）
  6. 6. A · 升序排列
  7. 7. A · O(V²)
  8. 8. A · 利用多层前向指针，实现期望 O(log n) 的查找

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