一、选择题
1. 下面关于算法的说法中正确的是（）
A. 算法最终必须由计算机程序实现
B. 为解决某问题的算法与为该问题编写的程序的含义是相同的
C. 算法的可行性是指指令不能有二义性
D. 以上都是错误的
2. 具有线性结构的数据结构是（）
A. 栈
B. 树
C. 图
D. 哈夫曼树
3. 一个有n个顶点的无向连通图所包含的连通分量的个数为（）
A. 0
B. 1
C. n
D. n+1
4. 已知串S='abc'，其next数组值为（）
A. 011
B. 112
C. 123
D. 121
5. 在散列存储中，装填因子的值越大，则（）
A. 存取元素时发生冲突的可能性就越大
B. 存取元素时发生冲突的可能性就越小
C. 对发生冲突的可能性没有影响
D. 查找效率就越低
6. 对于顺序表的优缺点，以下说法错误的是（）
A. 无须为表示结点间逻辑关系而增加额外的存储空间
B. 可以方遍地随机存取表中任一结点
C. 插入和删除运算较为方便
D. 由于要求占用连续空间，因此存储分配只能预先进行（静态分配）
7. 具有n(n>0)个结点的完全二叉树的深度为（）
A. ⌈logn⌉
B. ⌊logn⌋
C. ⌊logn⌋+1
D. ⌈logn⌉+1
8. 在有向图的邻接表中，每个顶点邻接表链接着该顶点所有（）邻接点
A. 入弧
B. 出弧
C. 入弧和出弧
D. 不是入弧也不是出弧
9. 若某二叉树中有30个叶子结点，另有30个结点只有一个子节点，则该二叉树中共有（）个结点
A. 80
B. 89
C. 90
D. 79
10. 有一个序列{4,5,6,…}，当生成平衡二叉树时，插入值为6的结点时应做（）类型的平衡调整
A. LL
B. LR
C. RL
D. RR
11. 在线性表的散列存储中，若用m表示散列表的长度，n表示待散列存储元素的个数，则装填因子等于（）
A. n/m
B. m/n
C. n/(m+n)
D. m/(n+m)
12. 设有500个无序的元素，希望用最快的速度挑选出其中前10个最大的元素，最好用（）排序法
A. 堆排序
B. 快速排序
C. 插入排序
D. 基数排序
13. 用顺序存储的方法将完全二叉树中所有结点按层逐个从左到右的顺序放在一维数组R[1..n]中，若结点R[i]有左孩子，则其左孩子是（）
A. R[2i-1]
B. R[2i]
C. R[2i+1]
D. R[i/2]
14. 设单链表中，已知指针q所指结点是指针p所指结点的直接前驱，若在q与p之间插入结点s，则应执行（）操作
A. s->next=p->next;p->next=s;
B. q->next=s;s->next=p;
C. p->next=s->next;s->next=p;
D. p->next=s;s->next=q;
15. 一组记录的序列为{46,79,56,38,40,84}，则利用堆排序的方法建立的初始堆为（）
A. 79,46,56,38,40,84
B. 84,79,56,38,40,46
C. 84,79,56,46,40,38
D. 84,56,79,40,46,38
16. 下列哪种图的邻接矩阵是对称的（）
A. 有向图
B. 无向图
C. AOV网
D. AOE网
17. 简单无向图的邻接矩阵是对称的，可以对其进行压缩存储。若无向图G有n个节点，其邻接矩阵A[1..n,1..n]，且压缩存储在B[1..k]种，则k的值至少为（）
A. n(n+1)/2
B. n*n/2
C. (n-1)(n+1)/2
D. n(n-1)/2
18. 拓扑排序是指有向图中的所有顶点排成一个线性序列的过程。若在有向图中从顶点Vi到Vj有一条路径，则在该线性序列中，顶点Vi必然在Vj之前，因此，若不能得到全部顶点的拓扑排序，则说明该图一定是（）
A. 包含回路
B. 强连通图
C. 完全图
D. 有向图
19. 在对查找表的查找过程中，若被查找的数据元素不存在，则把该数据元素插入到集合中。这种方式主要适合于（）
A. 静态查找表
B. 动态查找表
C. 静态查找表与动态查找表
D. 静态查找表或动态查找表
20. 已知单链表A的长度为m，单链表B的长度为n，若将B连接在A的末尾，其时间复杂度是（）
A. O(1)
B. O(m)
C. O(n)
D. O(m+n)
答案：1~5：D A B A A 6~10：C C B B D 11~15：A A B B B 16~20：B A A B B
二、填空题
1. 对稀疏矩阵进行压缩存储，常用的两种方法是 三元组法 和 十字链表 。
2. 若对二叉排序树进行遍历，保证输出的所有结点序列按键值递增排序，对二叉排序树应进行 中序遍历 。
3. 队列的特点是 先进先出 ，栈的特点是 后进先出 。
三、判断题
1. 完全二叉树的某个结点若无左孩子，则必然是叶结点。
2. 折半查找方法可以用于按键值有序的线性链表的查找。
3. KMP算法的最大特点是指示主串的指针不需要回溯。
4. 广义表中最大子表的深度即为广义表的深度。
5. 邻接表只能用于存储有向图，而邻接矩阵则可存储有向图和无向图。
答案：√ × √ × ×
转载：https://blog.csdn.net/m0_68111267/article/details/128370494