数据结构与算法考点解析：二分查找、快速排序、图论、树、链表、二维数组

若有 18 个元素的有序表存放在一维数组 A 中，第一个元素放 A[1] 中，现进行二分查找，则查找 A[3] 的比较序列的下标依次为 ( )。

A. 1，2，3 B. 9，5，2，3 C. 9，5，3 D. 9，4，2，3

对 n 个记录的顺序表进行快速排序，所需要的辅助存储空间大致为（）。

A. O（1） B. O（n） C. O（log2n） D. O（n2）

设有 6 个结点的无向图，该图至少应有 ( ) 条边才能确保是一个连通图。

A. 5 B. 6 C. 7 D. 8

设哈夫曼树中的叶子结点总数为 m，若用二叉链表作为存储结构，则该哈夫曼树中总共有（）个空指针域。

A. 2m-1 B. 2m C. 2m+1 D. 4m

设某棵二叉树中有 2000 个结点，则该二叉树的最小高度为（）。

A. 9 B. 10 C. 11 D. 12

一个二叉树的先序序列和后序序列正好相反，则该二叉树一定是（）的二叉树（树中结点个数大于 1）。

A. 空或只有一个结点 B. 高度等于其结点数 C. 任一结点无左孩子 D. 任一结点无右孩子

若删除单链表中的数据 a，a 所在的结点为 A，设指针变量 p 指向结点 A，完成删除操作则需要修改指针的操作序列为（）。

A. q=p->next；p->data=q->data；p->next=q->next；free(q)； B. q=p->next；q->data=p->data；p->next=q->next；free(q)； C. q=p->next；p->next=q->next；free(q)； D. q=p->next；p->data=q->data；free(q)；

二维数组 A[1:5,1:6] 的每个元素占 5 个单元，将其按行优先次序储存在起始地址为 1000 的连续的内存单元中，则元素 A[5，5] 的地址为（）。

A. 1140 B. 1145 C. 1120 D. 1125

设无向图 G 中有 n 个顶点 e 条边，则其对应的邻接表中的表头结点和表结点的个数分别为（）。

A. n，e B. e，n C. 2n，e D. n，2e

设某强连通图中有 n 个顶点，则该强连通图中至少有（）条边。

A. n(n-1) B. n+1 C. n D. n(n+1)

解释内容：1. C 二分查找的过程中每次比较都会将查找区间缩小一半，因此比较序列的下标应该是逐步减小的，故选 C。

C 快速排序需要用到递归调用，每次调用都需要额外的存储空间来保存递归返回时需要恢复的信息，因此辅助存储空间的大小与递归树的深度成正比，而递归树的深度为 O(log2n)，故选 C。
C 由于是无向图，所以边数应当是顶点数的平方级别，而连通图的最小边数为 n-1，因此至少需要 7 条边才能确保连通。
D 用二叉链表作为哈夫曼树的存储结构时，每个结点需要两个指针域，而叶子结点数为 m，非叶子结点数为 m-1，因此总共需要 4m 个指针域，即 2m 个空指针域，故选 D。
B 对于一棵有 n 个结点的二叉树，其最小高度为 log2(n+1)-1，将 2000 代入可得最小高度为 10。
C 一个二叉树的先序序列和后序序列正好相反，意味着先序遍历时每个结点的左孩子都为空，后序遍历时每个结点的右孩子都为空，因此该二叉树一定是任一结点无左孩子的二叉树。
B 删除单链表中的数据 a，可以通过修改指针的方式来完成，首先需要将指针 p 指向结点 A，然后将 p->next 赋值给一个临时指针变量 q，最后修改 q 的值并释放其空间即可，因此选 B。
B 二维数组 A[1:5,1:6] 中，元素 A[i,j] 的地址为 1000+5*((i-1)*6+(j-1))，将 i=5，j=5 代入可得地址为 1145。
D 无向图 G 的邻接表中，每个顶点对应一个表头结点，每条边对应一个表结点，因此表头结点的个数为 n，表结点的个数为 2e，故选 D。
A 强连通图中至少有 n 个顶点和 n(n-1) 条边，因此至少需要 n(n-1) 条边才能确保强连通。