JavaDS——数据结构易错选择题总结

朱雀 2023-09-30 21:47 5阅读 0赞

> 1. 下列关于线性链表的叙述中，正确的是（ ）
> 
> A. 各数据结点的存储空间可以不连续，但它们的存储顺序与逻辑顺序必须一致
> 
> B. 各数据结点的存储顺序与逻辑顺序可以不一致，但它们的存储空间必须连续
> 
> C. 进行插入与删除时，不需要移动表中的元素
> 
> D. 以上说法均不正确

**答案：C**

**题目解析：**

链表和顺序表（数组）：

1. 元素的存储顺序和逻辑顺序

*  顺序表（数组）：元素之间既要逻辑连续，存储顺序也要连续。
 *  链表：元素之间逻辑连续，物理不连续（存储结点之间地址不连续）。

2. 存储空间是否连续

*  顺序表（数组）：存储空间一定连续。
 *  链表：存储空间不连续。

A：各数据结点的存储空间可以不连续，但它们的存储顺序与逻辑顺序必须一致（存储顺序可以不一致）

B：各数据结点的存储顺序与逻辑顺序可以不一致，但它们的存储空间必须连续（存储空间可以不连续）。

C：正确，链表进行插入与删除时，不需要移动表中元素，只需要更改结点的next引用；但顺序表进行插入与删除时，需要移动表中元素。

> 2. 假设你只有100Mb的内存，需要对1Gb的数据进行排序，最合适的算法是（）
> 
> A. 归并排序
> 
> B. 插入排序
> 
> C. 快速排序
> 
> D. 冒泡排序

**答案：A**

**题目解析：**

外部排序：内存中放不下所有要排序的数据，需要借助外部空间（磁盘）进行排序。

应用：多路归并排序。

所以可以将1GB分为大小相等的20份，每份大小为50MB，依次将每份数据读入内存中进行排序（内部排序：快速排序等），然后在外部空间进行这20份的归并过程。

综上所述选择A选项。

> 3. 若栈采用顺序存储方式存储，现两栈共享空间V\[1..m\]，top\[i\]代表第i个栈( i =1,2)栈顶，栈1的底在v\[1\]，栈2的底在V\[m\]，则栈满的条件是（ ）。3.28 2
> 
> A. top\[1\]+top\[2\]=m
> 
> B. top\[1\]+1=top\[2\]
> 
> C. top\[2\]-top\[1\]|=0
> 
> D. top\[1\]=top\[2\]

**答案：B**

**题目解析：**

栈还未满时：

![d3399592d7a14c219eec820e2f8c0e24.png][]

stack2再加入一个新元素n：

![fa1dcb4f888b41f6ae7d39c76ab316e0.png][]

观察此时下标的关系，得到：top\[1\]+1=top\[2\]，所以选择B选项。

> 4. 以下哪种排序算法对(1,3,2,4,5,6,7,8,9)进行的排序最快（）
> 
> A. 冒泡
> 
> B. 快排
> 
> C. 归并
> 
> D. 堆排

**答案：A**

**题目解析：**

冒泡：走两次就解决。

快排：会走多次。

归并，堆排：O(nlogn)。

近乎有序的数组中，冒泡排序是比较优秀的，当发现元素没有交换时，认为此时数组已经有序，排序退出，所以选A选项。

> 5. 下列叙述中错误的是（ ）
> 
> A. 二叉链表是二叉树的存储结构
> 
> B. 循环链表是循环队列的存储结构
> 
> C. 栈是线性结构
> 
> D. 循环队列是队列的存储结构

**答案：B**

**题目解析：**

A：Node left;

Node right;

二叉链表就是普通二叉树的存储结构，正确。

B：循环链表是循环队列的存储结构——错误，数组是循环队列的存储结构。

C：正确。

D：正确。

所以选择B选项。

> 6. 下述二叉树中，哪一种满足性质：从任一结点出发到根的路径上所经过的结点序列按其关键字有序（）7
> 
> A. 二叉排序树
> 
> B. 哈夫曼树
> 
> C. AVL树
> 
> D. 堆

**答案：D**

**题目解析：**

有序：升序或降序

A：二叉排序树和二叉搜索树是一个概念：二叉树，并且左子树上所有结点的值小于它根结点的值，右子树上所有结点的值大于它根节点的值。

B：哈夫曼树——带权值（与元素大小顺序无关）的树。B错误。

C：AVL树——平衡二分搜索树：首先是二叉搜索树，其次是平衡的，即它每一个结点的左子树的高度和右子树的高度差至多为1。

A，C：举例：如图，并没有有序，A，C错误。

![1065a361b6ea4ac6a3e4e675db40c1c7.png][]

D：堆：

以最大堆为例：

满足堆中所有结点：根结点大于左右孩子。——从最大堆的任意结点出发走到根结点都是递增序列。

所以选择D选项。

> 7. 将整数数组（7-6-3-5-4-1-2）按照堆排序的方式原地进行升序排列，请问在第一轮排序结束之后，数组的顺序是（）3.29 9
> 
> A. 2-6-3-5-4-1-7
> 
> B. 6-2-3-5-4-1-7
> 
> C. 6-5-3-2-4-1-7
> 
> D. 1-4-7-5-6-3-2

**答案：C**

**题目解析：**

因为原地进行升序排列

1. swap(0, arr, length - 1)——7，2做交换。

2. 得到最大值7。

3. 继续在剩下的元素中调整为最大堆重复上述过程。

![df3eed203e0544e5a5723feef4cc8d43.png][]

此时不满足最大堆的性质，调整。

![5e3b2e53073144efa6b8af88477e8aaa.png][]

调整后如图，得到第一轮排序的结果：6，5，3，2，4，1，7。

![3574008271b14beaa0e94326f0cacd93.png][]

所以本题选择C选项。

> 8. 下列各排序法中，最坏情况下的时间复杂度最低的是（ ）
> 
> A. 希尔排序
> 
> B. 快速排序
> 
> C. 堆排序
> 
> D. 冒泡排序

**答案：C**

**题目解析：**

A：插入排序的优化，时间复杂度基本上是O(![n^\{2\}][n_2])，至少是比O(nlogn)大

B：当出现大量重复·元素或者数组几乎有序时，递归树退化为链表，O(![n^\{2\}][n_2])

C：堆排序是一个非常稳定的O(nlogn)

D：O(![n^\{2\}][n_2])

所以选择C选项。

> 9. 若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（）存储方式最节省时间。
> 
> A. 顺序表
> 
> B. 双链表
> 
> C. 带头结点的双循环链表
> 
> D. 单循环链表

**答案：A**

**题目解析：**

A：顺序表（数组）取元素——O(1)，在数组末尾进行插入和删除——O(1)

所以选择A选项。

> 10. 下列数据结构具有记忆功能的是？
> 
> A. 队列
> 
> B. 循环队列
> 
> C. 栈
> 
> D. 顺序表

**答案：C**

**题目解析：**

记忆功能应用举例：浏览器的回退功能，文本编辑器的撤销操作。

栈的LIFO（先进后出）特性，也是具有记忆功能的。

所以选择C选项。

> 11. 对递归程序的优化的一般的手段为（）
> 
> A. 尾递归优化
> 
> B. 循环优化
> 
> C. 堆栈优化
> 
> D. 停止值优化

**答案：A**

**题目解析：**

比如快速排序和归并排序：

> //终止条件
> 
> (l >= r)\{ 
> 
>  return;
> 
> \}
> 
> //在递归终止条件处进行优化
> 
> //当区间个数较小时，采用插入排序来优化，(r - l <= 15)—>采用插入排序

这就是尾递归优化，选择A选项。

> 12. 下列说法中错误的是（）
> 
> A. 红黑树插入操作的平均时间复杂度为O(logn)，最坏时间复杂度为O(logn)
> 
> B. B+树插入操作的平均时间复杂度为O(logn)，最坏时间复杂度为O(logn)
> 
> C. Hash表插入操作的平均时间复杂度为O(logn)，最坏时间复杂度为O(n)
> 
> D. 排序链表插入操作的平均时间复杂度为O(n)，最坏时间复杂度为O(n)

**答案：C**

**题目解析：**

C：Hash表插入操作的平均时间复杂度为O(logn)**O(1)**，最坏时间复杂度为O(n)。

> 13. 大小为MAX的循环队列中，f 为当前队头元素位置，r 为当前队尾元素位置(最后一个元素的位置)，则任意时刻，队列中的元素个数为（）
> 
> A. r-f
> 
> B. (r-f+MAX+1)%MAX
> 
> C. r-f+1
> 
> D. (r-f+MAX)%MAX

**答案：B**

**题目解析：**

数组长度 = MAX - 1（判断队列满，浪费一个空间）

r 为当前队尾元素位置(最后一个元素的位置)——>队尾的下一个位置

代入举例：

![5b74d2f710c84acd851d333f36f8f51b.png][]

所以本题选择B。

> 14. 下列选项中，不可能是快速排序第2趟排序结果的是 （）
> 
> A. 2,3,5,4,6,7,9
> 
> B. 2,7,5,6,4,3,9
> 
> C. 3,2,5,4,7,6,9
> 
> D. 4,2,3,5,7,6,9

**答案：C**

**题目解析：**

快速排序特点：每进行一次快排，标定点一定在最终位置。

本题进行了两次快排，则至少有两个元素到达最终位置。

C选项，只有9到达最终位置（只有一个元素到达最终位置），所以C选项是不可能的。

如有建议或者想法欢迎一起讨论学习~

[d3399592d7a14c219eec820e2f8c0e24.png]: https://img-blog.csdnimg.cn/d3399592d7a14c219eec820e2f8c0e24.png
[fa1dcb4f888b41f6ae7d39c76ab316e0.png]: https://img-blog.csdnimg.cn/fa1dcb4f888b41f6ae7d39c76ab316e0.png
[1065a361b6ea4ac6a3e4e675db40c1c7.png]: https://img-blog.csdnimg.cn/1065a361b6ea4ac6a3e4e675db40c1c7.png
[df3eed203e0544e5a5723feef4cc8d43.png]: https://img-blog.csdnimg.cn/df3eed203e0544e5a5723feef4cc8d43.png
[5e3b2e53073144efa6b8af88477e8aaa.png]: https://img-blog.csdnimg.cn/5e3b2e53073144efa6b8af88477e8aaa.png
[3574008271b14beaa0e94326f0cacd93.png]: https://img-blog.csdnimg.cn/3574008271b14beaa0e94326f0cacd93.png
[n_2]: https://latex.csdn.net/eq?n%5E%7B2%7D
[5b74d2f710c84acd851d333f36f8f51b.png]: https://img-blog.csdnimg.cn/5b74d2f710c84acd851d333f36f8f51b.png