day19—选择题
文章目录
1.下列关于线性链表的叙述中，正确的是（C ）
A 各数据结点的存储空间可以不连续，但它们的存储顺序与逻辑顺序必须一致
B 各数据结点的存储顺序与逻辑顺序可以不一致，但它们的存储空间必须连续
C 进行插入与删除时，不需要移动表中的元素
D 以上说法均不正确
思路：对顺序表（数组）来说，元素之间既要逻辑连续，存储顺序也要连续，并且它的存储空间一定是连续的；对链表来说，链表是元素之间逻辑连续，物理不连续（也就是存储结点之间的地址不连续），链表的存储空间也不连续
2.下列数据结构中，不能采用顺序存储结构的是（ A）
A 非完全二叉树
B 堆
C 队列
D 栈
思路：二叉树中只有完全二叉树可以使用顺序存储，非完全二叉树只能采用链式存储；堆是一个完全二叉树，可以采用顺序存储
3.递归函数最终会结束，那么这个函数一定（B）
A 使用了局部变量
B 有一个分支不调用自身
C 使用了全局变量或者使用了一个或多个参数
D 没有循环调用
思路：本题考察递归函数的终止条件，递归函数的出口：函数调用过程中有一个分支会return，不会一直调用下去（也就是有一个分支不调用自身）
4.以下序列不是堆的是（D）
A (100,85,98,77,80,60,82,40,20,10,66)
B (100,98,85,82,80,77,66,60,40,20,10)
C (10,20,40,60,66,77,80,82,85,98,100)
D (100,85,40,77,80,60,66,98,82,10,20)
思路：堆是一棵完全二叉树；每棵二叉树的根结点比左右孩子都小，称为小根堆；每棵二叉树的根结点比左右孩子都大，称为大根堆
5.假设你只有100Mb的内存，需要对1Gb的数据进行排序，最合适的算法是（A）
A 归并排序
B 插入排序
C 快速排序
D 冒泡排序
思路：当内存中放不下所有要排序的数据的时候，就需要借助外部空间进行排序，称为外部排序，一般采用多路归并排序；例如：将1GB的数据分为大小相等的20份，每份大小为50MB，依次将每份数据读入内存中进行内部排序，然后在外部空间进行归并