# 课堂测验

## 一、 单选题（共8题，40分）
1. 数据结构通常是研究数据的（  ）及它们之间的相互联系。
2. 线性表采用链式存储时，其地址（  ）
3. 在双向链表存储结构中，删除p所指的结点时须修改指针（  ）
4. 若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若pn 是n，则Pi为（ ）
5. 在一个链队列中，若f、r分别为队首、队尾指针，则插入p所指结点的操作为（ ）。
6. 以下论述正确的是（  ）。
7. 假设在一棵二叉树中，双分支结点数为15，单分支结点数为30个，则叶子结点数为（  ）个。
8. 某二叉树的后序遍历序列为DABEC，中序遍历序列为DEBAC，则先序遍历序列为（  ）
## 二、 判断题（共6题，30分）
9. 数据的逻辑结构与数据元素本身的内容和形式无关。
10. 对任何数据结构链式存储结构一定优于顺序存储结构。
11. 循环队列通常用指针来实现队列的头尾相接。
12. 串中任意个字符组成的子序列称为该串的子串
13. 根据任意一种遍历序列即可唯一确定对应的二叉树。
14. 折半查找法要求待查表的关键字必须有序。
# 一、单选题（共31题）
1. 在单链表中，增加头结点的目的是（  ）。
2. 在顺序表中，只要知道（  ），就可以求出任意一个结点的存储地址。
3. 下面关于线性表的叙述，错误的是（  ）。
4. 在单链表指针为p的结点之后插入指针为s结点，正确的操作是（  ）。
5. 链表中最常用的操作是在最后一个元素之后插入一个元素和删除最后一个元素，则采用（  ）存储方式最节省运算时间。
6. 链表不具备的特点是（  ）。
7. 在（  ）的运算中，使用顺序表比链表好。
8. 能在O(1)时间内访问线性表的第i个元素的结构是（  ）。
9. 在一棵二叉树上第3层上的结点数最多为（  ）。
10. 在完全二叉树中，如果一个结点是叶子结点，则它没有（  ）。
11. 若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若pn是n，则Pi为（  ）。
12. 在一个链队列中，若f、r分别为队首、队尾指针，则插入p所指结点的操作为（  ）。
13. 假设在一棵二叉树中，双分支结点数为15，单分支结点数为30个，则叶子结点数为（  ）个。
14. 树最适合用来表示（ ）。
15. 一个栈的入栈序列是a，b，c，d，e，则栈的不可能的输出序列是（ ）。
16. 计算机算法必须具备输入、输出、（  ）等5个特性。
17. 一个三元组表用于表示一个（ ）。
18. 深度为4的满二叉树有（  ）个结点。
19. 边数很多的稠密图，适宜用（  ）表示。
20. 数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的（  ）和运算的学科。
21. 算法在发生非法操作时可以作出处理的特性称为（  ）。
22. 将一棵有100个结点的完全二叉树从上到下，从左到右依次进行编号，根结点的编号为1，则编号为25的结点的左孩子编号为（  ）。
23. 设三个函数f，g，h分别为f(n)=100n³+n²+100，g(n)=25n³+4000n，h(n)=n¹.⁵+100nlog₂n，则以下关系式中错误的是（  ）。
24. 一个队列的入队序列是1，2，3，4，则队列的输出序列是（ ）。
25. 线性表L在（  ）情况下适用于使用链式结构实现。
26. 一个三元组表用于表示一个（  ）。
27. 深度为5的满二叉树有（  ）个分支结点。
28. 边数很多的稠密图，适宜用（  ）表示。
29. 若从二叉树的任一结点出发到根的路径上所经过的结点序列按其关键字有序，则该二叉树是（  ）。
30. 算法在发生非法操作时可以作出处理的特性称为（  ）。
31. 将一棵有100个结点的完全二叉树从上到下，从左到右依次进行编号，根结点的编号为1，则编号为49的结点的右孩子编号为（  ）。
# 二、判断题（共30题）
1. 线性表的链式存储结构优于顺序存储结构。
2. 链表的每个结点都恰好包含一个指针域。
3. 顺序表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。
4. 在图的遍历中，广度优先搜索可以找到从起点到终点的最短路径。
5. 带权图最小生成树是唯一的。
6. 数据的逻辑结构和数据的存储结构是相同的。
7. 串是n个字母的有限序列（n≥0）。
8. 从逻辑关系上讲，数据结构主要分为线性结构和非线性结构两类。
9. 图可以没有边，但不能没有顶点。
10. 插入和删除操作是数据结构中最基本的两种操作，所以这两种操作在数组中也经常使用。
11. 在图的遍历中，深度优先搜索使用栈来存储待访问的节点。
12. 任何一个递归过程都可以转换成非递归过程。
13. 串中任意个字符组成的子序列称为该串的子串。
14. 数据结构的抽象操作的定义与具体实现有关。
15. 若输入序列为1,2,3,4,5,6，则通过一个栈可以输出序列1,3,5,4,2,6。
16. 数据的物理结构是指数据在计算机内的实际存储形式。
17. 在二叉搜索树中，左子树的所有节点的值都小于根节点的值。
18. 哈希表的平均查找时间复杂度为O(1)。
19. 快速排序算法的时间复杂度总是O(n²)。
20. 在图的深度优先搜索中，每个节点最多被访问一次。
21. 广度优先搜索算法使用队列来存储待访问的节点。
22. 二叉树的前序遍历顺序是先访问根节点，然后左子树，最后右子树。
23. 在堆排序中，父节点的值总是大于其子节点的值。
24. 动态规划算法通常用于解决具有重叠子问题和最优子结构的问题。
25. 图的邻接矩阵表示法的空间复杂度为O(V+E)，其中V是顶点数，E是边数。
26. AVL树是一种自平衡二叉搜索树，其任意节点的两个子树的高度差最多为2。
27. 归并排序算法的时间复杂度为O(nlogn)。
28. 二分查找算法可以在无序数组中有效运行。
29. 在哈希表中，冲突可以通过链地址法解决。
30. 二叉树的后序遍历顺序是先访问左子树，然后右子树，最后根节点。
更多问卷 复制此问卷