顺序表与链表
顺序表中第一个元素的存储地址是 100，每个元素的长度为 2，则第 5 个元素的地址是（ ）
A.100 B.105 C.108 D.110
对于顺序存储的长度为 N 的线性表，访问结点和增加结点的时间复杂度为：(1 分)
A .O (1), O(1) B .O (1), O(N) C .O (N), O(1). D .O (N), O(N).
3. 在 N 个结点的顺序表中，算法的时间复杂度为 O(1)的操作是：
A. 访问第 i 个结点（1≤i≤N）和求第 i 个结点的直接前驱（2≤i≤N）
在第 i 个结点后插入一个新结点（1≤i≤N）
删除第 i 个结点（1≤i≤N）
将 N 个结点从小到大排序
4. 对于顺序表的优缺点，以下说法错误的是( )。
无需为表示结点间的逻辑关系而增加额外的存储空间
可以方便地随机存取表中的任一结点
插入和删除运算较方便
容易造成一部分空间长期闲置而得不到充分利用
若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用
（ ）存储方式最节省时间。
A.顺序表 B.双链表 C.带头节点的双循环链表 D.单链表循环
若线性表最常用的操作是存取第 i 个元素及其前驱的值，则采用( )存储方式节省时间。
A.单链表 B.双向链表 C.单循环链表 D.顺序表
以下错误的是（）（2 分）D
求表长、定位这两种运算在采用顺序存储结构时实现的效率不比采用链式存储结构时实现的效率低
顺序存储的线性表可以随机存取
由于顺序存储要求连续的存储区域，所以在存储管理上不够灵活
线性表的链式存储结构优于顺序存储结构
8. 下面的叙述正确的是( )
线性表在链式存储时，查找第 i 个元素的时间同 i 的值成反比
线性表在链式存储时，查找第 i 个元素的时间同 i 的值无关
线性表在顺序存储时，查找第 i 个元素的时间同 i 的值成正比
线性表在顺序存储时，查找第 i 个元素的时间同 i 的值无关
9. 下面的叙述正确的是（ ）
线性表在链式存储时，所有元素节点的存储单元是连续的
线性表在链式存储时，删除第 i 个元素的时间同 i 的值无关
线性表在顺序存储时，查找第 i 个元素的时间同 i 的值成正比
线性表在顺序存储时，所有元素的存储单元是连续的
10. 以下说法正确的是（ ）。
线性结构的基本特征是：每个结点有且仅有一个直接前趋和一个直接后继
线性表的各种基本运算在顺序存储结构上的实现均比在链式存储结构上的实现效率要低
在线性表的顺序存储结构中，插入和删除元素时，移动元素的个数与该元素位置有关
顺序存储的线性表的插入和删除操作不需要付出很大的代价，因为平均每次操作只有近一半的元素需要移动
答案：1～~5 CBACA 6~10 DDBDC
栈和队列
栈的基本定义、操作、后缀表达式
队列的基本定义、操作
判断
1. 若一个栈的输入序列为 1，2，3，…，N，输出序列的第一个元素是 i，则第 j 个输出元素是 j−i−1。
2. 通过对堆栈 S 操作：Push(S,1), Push(S,2), Pop(S), Push(S,3), Pop(S), Pop(S)。输出的序列为123。
3. 在用数组表示的循环队列中，front 值一定小于等于 rear 值。
4. 若一个栈的输入序列为{1, 2, 3, 4, 5}，则不可能得到{3, 4, 1, 2, 5}这样的出栈序列。
5. 所谓“循环队列”是指用单向循环链表或者循环数组表示的队列。
答案：1~5 FFFTF
1. 若栈采用顺序存储方式存储，现两栈共享空间 V[m]：top[i]代表第 i（i=1 或 2）个栈的栈顶；栈 1 的底在 V[0]，栈 2 的底在 V[m-1]，则栈满的条件是：
op[1]+top[2]==m
|top[2]-top[1]|==0
top[1]==top[2]
top[1]+1==top[2]
2.设一个栈的输入序列是 1、2、3、4、5，则下列序列中，是栈的合法输出序列的是？
A. 5 1 2 3 4 B.3 2 1 5 4 C. 4 5 1 3 2 D. 4 3 1 2 5
3.令 P 代表入栈，O 代表出栈。若利用堆栈将中缀表达式 3*2+8/4 转为后缀表达式，则相应的堆栈操作序列是：
A. PPOOPO B.PPPOOO C.POPOPO D.POPPOO
4．若采用带头、尾指针的单向链表表示一个堆栈，那么该堆栈的栈顶指针 top 应该如何设置？
A.将链表头设为 top B. 将链表尾设为 top C. 随便哪端作为 top 都可以 D. 链表头、尾都不适合作为 top
5．表达式 a*(b+c)-d 的后缀表达式是：
ａｂｃｄ＊＋－
ａｂｃ＊＋ｄ－
－＋＊ａｂｃｄ
ａｂｃ＋＊ｄ－
6．利用大小为 n 的数组（下标从 0 到 n-1）存储一个栈时，假定栈从数组另一头开始且 top==n 表示栈空，则向这个栈插入一个元素时，修改 top 指针应当执行：
A.TOP=0 B.TOP++ C.TOP- D.TOP不变
7. 若 top 为指向栈顶元素的指针，判定栈 S（最多容纳 m 个元素）为空的条件是：
A. S->top == -1 B. S->top == m-1 C. S->top == 0 D. S->top == m-1
8. 若元素 a、b、c、d、e、f 依次进栈，允许进栈、退栈操作交替进行，但不允许连续三次进行退栈工作，则不可能得到的出栈序列是？
A.ｃｂｄａｅｆ B.ｂｃａｅｆｄ C.ｄｃｅｂｆａ D.ａｆｅｄｃｂ
9 设栈 S 和队列 Q 的初始状态均为空，元素 a、b、c、d、e、f、g 依次进入栈 S。若每个元素出栈后立
即进入队列 Q，且 7 个元素出队的顺序是 b、d、c、f、e、a、g，则栈 S 的容量至少是：
A.１ B.２ C.３ D.４
10.从栈顶指针为 ST 的链栈中删除一个结点且用 X 保存被删结点的值，则执行：
X= ST; ST = ST->next;
ST = ST->next; X= ST->data;
X= ST->data;
D .X= ST->data; ST = ST->next;
11. 如果循环队列用大小为 m 的数组表示，且用队头指针 front 和队列元素个数 size 代替一般循环队列中的 front 和 rear 指针来表示队列的范围，那么这样的循环队列可以容纳的元素个数最多为： (2分)
A.m-1 B.m C.m+1 D.不确定
12. 有六个元素以 6、5、4、3、2、1 的顺序进栈，问哪个不是合法的出栈序列？
A.５４３６１２
B.２３４１５６
C.３４６５２１
D.４５３１２６
13. 为解决计算机主机与打印机之间速度不匹配问题，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是？
A.队列 B.树 C. 图D. 堆栈.
14. 现有队列 Q 与栈 S，初始时 Q 中的元素依次是{ 1, 2, 3, 4, 5, 6 }（1 在队头），S 为空。若允许下列
3 种操作：（1）出队并输出出队元素；（2）出队并将出队元素入栈；（3）出栈并输出出栈元素，则不
能得到的输出序列是：
A.３４５６１２ B.１２５６４３ C.２３４５６１ D.６５４３２１
15.假设有 5 个整数以 1、2、3、4、5 的顺序被压入堆栈，且出栈顺序为 3、5、4、2、1，那么为了获得这样的输出，堆栈大小至少为：
A.3 B.2 C.4 D.5
16.某队列允许在其两端进行入队操作，但仅允许在一端进行出队操作。若元素 a、b、c、d、e 依次入此队列后再进行出队操作，则不可能得到的出队序列是：
A.ｅｃｂａｄ B.ｂａｃｄｅ C.ｄｂａｃｅ D.ｄａｃａｅ
17. 若借助堆栈将中缀表达式 a+b*c+(d*e+f)*g 转换为后缀表达式，当读入 f 时，堆栈里的内容是什
（按堆栈自底向上顺序）？
A.abcde B.+(*+ C.+(+ D+(+.
18. 若用大小为 6 的数组来实现循环队列，且当前 front 和 rear 的值分别为 0 和 4。当从队列中删除两个元素，再加入两个元素后，front 和 rear 的值分别为多少？
A.2和2 B.2和4 C.2和0 D.2和6
19. 若已知一队列用单向链表表示，该单向链表的当前状态（含 3 个对象）是：1->2->3，其中 x->y 表示 x 的下一节点是 y。此时，如果将对象 4 入队，然后队列头的对象出队，则单向链表的状态是
A. 1->2->3 B. 2->3->4 C. 4->1->2 D.答案不唯一
20. 如果循环队列用大小为 m 的数组表示，队头位置为 front、队列元素个数为 size，那么队尾元素位置 rear 为：
A. (front+size)%m B. (front+size-1)%m C. front+size D. front+size-1
答案：1～５ＤＢＤＡＤ６～10ＢＣＤＣＤ 11～15ＢＣＡＡＣ16 ～20ＤＣＤ
ＢＢ
二叉树
叶节点、叶节点数、二叉树遍历、哈夫曼树、二叉搜索树
设每个 d 叉树的结点有 d 个指针指向子树，有 n 个结点的 d 叉树有多少空链域？
A.nd B.n(d-1) C. n(d−1)+1 D. 以上都不是
对 N（N≥2）个权值均不相同的字符构造哈夫曼树。下列关于该哈夫曼树的叙述中，错误的是： (2
分)
树中两个权值最小的结点一定是兄弟结点
树中任一非叶结点的权值一定不小于下一层任一结点的权值
树中一定没有度为 1 的结点
D.该树一定是一棵完全二叉树
3、具有 1102 个结点的完全二叉树一定有__个叶子结点。
A.551 B不确定 .C.79 D.1063
4.某二叉树的前序和后序遍历序列正好相反，则该二叉树一定是
A. 高度等于其结点数 B. 空或只有一个结点 C. 任一结点无左孩子 D. 任一结点无右孩子
5.将{5, 2, 7, 3, 4, 1, 6}依次插入初始为空的二叉搜索树。则该树的后序遍历结果是：
A.1, 4, 2, 6, 3, 7, 5 B. 1, 4, 3, 2, 6, 7, 5 C. 1, 2, 3, 4, 6, 7, 5 D. 5, 4, 3, 7, 6, 2, 1
6. 给定二叉树如下图所示。设 N 代表二叉树的根，L 代表根结点的左子树，R 代表根结点的右子树。若遍历后的结点序列为 3、1、7、5、6、2、4，则其遍历方式是：
A.NAL B.RNL C.LRN D.RLN
7. 设高为 h 的二叉树（规定叶子结点的高度为 1）只有度为 0 和 2 的结点，则此类二叉树的最少结点数和最多结点数分别为：
A. 2h−1, 2ℎ−1 B. 2h−1, 2ℎ−1−1 C. 2h, 2ℎ−1 D. 2ℎ−1+1, 2ℎ-1
8 有一个四叉树，度 2 的结点数为 4，度 3 的结点数为 4，度 4 的结点数为 3。问该树的叶结点个数是多少？
A.20 B.22 C.21 D.12
9. 在下述结论中，正确的是：
只有 2 个结点的树的度为 1；
二叉树的度为 2；
二叉树的左右子树可任意交换；
在最大堆（大顶堆）中，从根到任意其它结点的路径上的键值一定是按非递增有序排列的。
A. A.①②③ B.②③④ C. ①④ D. ②④
如果一棵非空 k（k≥2）叉树 T 中每个非叶子结点都有 k 个孩子，则称 T 为正则 k 叉树。若 T 的高度为 h（单结点的树 h=1），则 T 的结点数最多为：
A.(?ℎ−1-1)/(k-1) B.(?ℎ+1-1)/(k-1)C.无法确定 D.(?ℎ-1)/(k-1)
已知一棵完全二叉树的第 9 层（设根为第 1 层）有 100 个叶结点，则该完全二叉树的结点个数最多是：
A.1847 B.无法确定 C.311 D.823
12.一棵树有 n1 个孩子数为 1 的结点，n2 个孩子数为 2 的结点，……，nm 个孩子数为 m 的结点，则该树的叶结点数为：
A. 1+∑i=2m(i−1)ni B. 1+∑i=1m−1(i−1)ni C. 1+∑i=2m(i)ni D.∑i=2m(i−1)ni
13.要使一棵非空二叉树的先序序列与中序序列相同，其所有非叶结点须满足的条件是：
A. 只有右子树 B. 结点的度均为 1 C. 结点的度均为 2 D. 只有左子树
14. 设一段文本中包含 4 个对象{a,b,c,d}，其出现次数相应为{4,2,5,1}，则该段文本的哈夫曼编码比采用等长方式的编码节省了多少位数？
A.5 B.0 C.2 D.4
答案：１～５ＣＤＡＡ６～10 ＢＡＢＣＤ11～14 ＤＡＡＣ
图
1. 无向连通图所有顶点的度之和为偶数。 (1 分) 2. 无向连通图边数一定大于顶点个数减 1。 (1 分) 3. 用邻接表法存储图，占用的存储空间数只与图中结点个数有关，而与边数无关。 (1 分) 4. 用邻接矩阵法存储图，占用的存储空间数只与图中结点个数有关，而与边数无关。 (1 分) 5. 在一个有向图中，所有顶点的入度与出度之和等于所有边之和的 2 倍。 (1 分)
6. 用一维数组 G[]存储有 4 个顶点的无向图如下：G[] = { 0, 1, 0, 1, 1, 0, 0, 0, 1, 0 }
7. 则顶点 2 和顶点 0 之间是有边的。8. 如果无向图 G 必须进行两次广度优先搜索才能访问其所有顶点，则 G 中一定有回路。 9. 如果无向图 G 必须进行两次广度优先搜索才能访问其所有顶点，则 G 一定有 2 个连通分量。 10. 在一个有权无向图中，若 b 到 a 的最短路径距离是 12，且 c 到 b 之间存在一条权为 2 的边，则 c 到 a 的最短路径距离一定不小于 10。 (3 分)
11.Prim 算法是维护一个森林，每一步把两棵树合并成一棵。
12.Kruskal 算法是维护一个森林，每一步把两棵树合并成一棵。
13.Kruskal 算法是通过每步添加一条边及其相连的顶点到一棵树，从而逐步生成最小生成树。 (1 分) 14.Prim 算法是通过每步添加一条边及其相连的顶点到一棵树.成树。 (1 分)
1～5 ＴＦＦＦＦ 6～10ＴＴＦＴＴ 11～14 ＦＴＦＴ
1.具有 5 个顶点的有向完全图有多少条弧？
A.10 B.16 C.20 D.25
2.在 N 个顶点的无向图中，所有顶点的度之和不会超过顶点数的多少倍？
A.1 B.2 C.(N-1)/2 D.N-1
3.对于一个具有 N 个顶点的无向图，要连通所有顶点至少需要多少条边？
A.N-1 B.N C.N+1 D.N/2
4.对于有向图，其邻接矩阵表示比邻接表表示更易于：
A. 求一个顶点的入度 B. 求一个顶点的出边邻接点
C. 进行图的深度优先遍历 D. 进行图的广度优先遍历
5.对于一个具有 N 个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是： (1 分)
A.N-1 B.N C.(N-1)2 D.N2
6.若一个有向图用邻接矩阵表示，则第 i 个结点的入度就是： (1 分)
A.第 i 行的元素个数 B 第 i 行的非零元素个数
C. 第 i 列的非零元素个数 D 第 i 列的零元素个数.
7.下面关于图的存储的叙述中，哪一个是正确的？ (1 分)
A.用相邻矩阵法存储图，占用的存储空间数只与图中结点个数有关，而与边数无关
B.用相邻矩阵法存储图，占用的存储空间数只与图中边数有关，而与结点个数无关 C.
C.用邻接表法存储图，占用的存储空间数只与图中结点个数有关，而与边数无关
D.用邻接表法存储图，占用的存储空间数只与图中边数有关，而与结点个数无关
8.关于图的邻接矩阵，下列哪个结论是正确的？ (1 分)
A. 有向图的邻接矩阵总是不对称的 B. 有向图的邻接矩阵可以是对称的，也可以是不对称的
C. 无向图的邻接矩阵总是不对称的 D. 无向图的邻接矩阵可以是不对称的，也可以是对称的
9.在一个无向图中，所有顶点的度数之和等于所有边数的多少倍？
7A.1/2 B.1 C.2 D.4
10.在一个有向图中，所有顶点的入度与出度之和等于所有边之和的多少倍？
A.1/2 B.1 C.1 D.4
11.在任一有向图中，所有顶点的入度之和与所有顶点的出度之和的关系是： (1 分)
A.相等 B. 大于等于 C. 小于等于 D. 不确定
12.若要检查有向图中有无回路，除了可以利用拓扑排序算法外，下列哪种算法也可以用？
A. 深度优先搜索 B. 广度优先搜索 C. Dijkstra 算法 D.Prim 算法
13 下面给出的有向图中，有__个强连通分量。
A. 1 ({0,1,2,3,4}) B. 1 ({1,2,3,4}) C. 2 ({1,2,3,4}, {0}) D. 5 ({0}, {1}, {2}, {3}, {4})
14.下面给出的有向图中，各个顶点的入度和出度分别是：(1 分)
A. 入度: 0, 2, 3, 1, 2; 出度: 3, 2, 1, 1, 1 B. 入度: 3, 2, 1, 1, 1; 出度: 0, 2, 3, 1, 2
C. 入度: 3, 4, 4, 2, 3; 出度: 3, 4, 4, 2, 3 D.入度: 0, 1, 2, 1, 1; 出度: 3, 2, 1, 1, 1
15.如果 G 是一个有 15 条边的非连通无向图，那么该图顶点个数最少为多少？(3 分)
A.7 B.8 C.9 D.10
16.给定一个有向图的邻接表如下图，则该图有__个强连通分量。(3 分)
A.4 {{0, 1, 5}, {2}, {3}, {4}} B.3 {{2}, {4}, {0, 1, 3, 5}} C.1 {0, 1, 2, 3, 4, 5} D.1 {0, 5, 1, 3}
17 给定有向图的邻接矩阵如下：
顶点 2（编号从 0 开始）的出度和入度分别是：(1 分)
A.3,1 B.1,3 C.0,2 D.2,0
18.已知无向图 G 含有 16 条边，其中度为 4 的顶点个数为 3，度为 3 的顶点个数为 4，其他顶点的度均小于 3。图 G 所含的顶点个数至少是：(4 分)
A.10 B.11 C.13 D.15
19 下列说法不正确的是：
A.图的遍历是从给定的源点出发每一个顶点仅被访问一次
B.遍历的基本算法有两种：深度遍历和广度遍历
C.图的深度遍历是一个递归过程
D.图的深度遍历不适用于有向图
20.图的深度优先遍历类似于二叉树的： (1 分)
A.线序遍历 B.中序遍历 C.后序遍历 D.层次遍历
21.在用邻接表表示有 N 个结点 E 条边的图时，深度优先遍历算法的时间复杂度为：
A. O(N) B. O(N+E) C. O(N2) D. O(N2×E)
22.用 DFS 遍历一个无环有向图，并在 DFS 算法退栈返回时打印相应的顶点，则输出的顶点序列是？ (2
分)
A.无序的 B.拓扑排序 C.逆拓扑排序 D.以上都不对
23.在图中自 a 点开始进行深度优先遍历算法可能得到的结果为：
A. a, b, e, c, d, f B. a, c, f, e, b, d C. a, e, b, c, f, d D. a, e, d, f, c, b
24.给定无向图 G，从 V0 出发进行深度优先遍历访问的边集合为： {(V0,V1), (V0,V4), (V1,V2), (V1,V3), (V4,V5), (V5,V6)}。则下面哪条边不可能出现在 G 中？ (3 分)
A. (V0,V2) B. (V0,V6) C. (V1,V5) D. (V4,V6)
25.已知一个图的邻接矩阵如下，则从顶点 V1 出发按深度优先搜索法进行遍历，可能得到的一种顶点序列
为：
A. V1,V2,V3,V4,V5,V6 B. V1,V2,V4,V5,V6,V3 C. V1,V3,V5,V2,V4,V6 C. V1,V3,V5,V6,V4,V2
26.如果从无向图的任一顶点出发进行一次深度优先搜索可访问所有顶点，则该图一定是：
A. 连通图 B. 完全图 C. 有回路的图 D. 一棵树
27.给定一有向图的邻接表如下。从顶点 V1 出发按深度优先搜索法进行遍历，则得到的一种顶点序列
为：
A. V1,V5,V4,V7,V6,V2,V3 B. V1,V2,V3,V4,V7,V6,V5
C. V1,V5,V4,V7,V6,V3,V2 D. V1,V5,V6,V4,V7,V2,V3
28.下列选项中，不是下图深度优先搜索序列的是：
A. V1, V5, V4, V3, V2 B. V1, V3, V2, V5, V4 C. V1, V2, V5, V4, V3 D. V1, V2, V3, V4, V5
29.若某图的深度优先搜索序列是{V2, V0, V4, V3, V1}，则下列哪个图不可能对应该序列？
A. D.
B.
C.
30.在图中自 a 点开始进行广度优先遍历算法可能得到的结果为：
A. a, e, d, f, c, b B.a, c, f, e, b, d C.a, e, b, c, f, d D. a, b, e, c, d, f
31.给定一有向图的邻接表如下。从顶点 V1 出发按广度优先搜索法进行遍历，则得到的一种顶点序列
为：
A. V1,V2,V3,V4,V5 B. V1,V2,V3,V5,V4 C. V1,V3,V2,V4,V5 D. V1,V4,V3,V5,V2
32.已知一个图的邻接矩阵如下，则从顶点 V1 出发按广度优先搜索法进行遍历，可能得到的一种顶点序列为：
A. V1,V2,V3,V5,V4,V6 B. V1,V2,V4,V5,V6,V3 C. V1,V3,V5,V2,V4,V6 D. V1,V3,V5,V6,V4,V2
33.图的广度优先遍历类似于二叉树的：(1 分)
A.层次遍历 B.中序遍历 C.后序遍历 D.先序遍历
34.我们用一个有向图来表示航空公司所有航班的航线。下列哪种算法最适合解决找给定两城市间最经济的飞行路线问题？ (1 分)
A. Dijkstra 算法 B. Kruskal 算法 C. 深度优先搜索 D. 拓扑排序算法
35.数据结构中 Dijkstra 算法用来解决哪个问题？ (1 分)
A. 关键路径 B. 最短路径 C.拓扑排序 D. 字符串匹配
36 使用迪杰斯特拉（Dijkstra）算法求下图中从顶点 1 到其他各顶点的最短路径，依次得到的各最短路径的目标顶点是：
A.5,2,3,4,6 B.5,2,3,6,,4 C.5,2,4,3,6 D.5,2,6,3,4
37.任何一个带权无向连通图的最小生成树—— (1 分)
A. 是唯一的 B. 是不唯一的 C. 有可能不唯一 D.有可能不存在
38.给定有权无向图的邻接矩阵如下，其最小生成树的总权重是：(3 分)
A.20 B.22 C.8 D.15
39.在 AOE 网中，什么是关键路径？ (1 分)
A. 最短回路 B. 最长回路
C. 从第一个事件到最后一个事件的最短路径 D. 从第一个事件到最后一个事件的最短路径
40.如图所示的 AOE-网，求这个工程最早可能在什么时间结束。
A.33 B.18 C.43 D.23
41.对下图进行拓扑排序，可以得到不同的拓扑序列的个数是：
A.4 B.3 C.2 D.1
42.下图为一个 AOV 网，其可能的拓扑有序序列为：
A.ABCDFEG B.ADFCEBG C. ACDFBEG D. ABDCEFG 1~5ＣＤＡＡＤ 6~10ＣＡＢＣＣ 11~15ＡＡＣＡＡ 16~20ＢＣＢＤＡ 21~25ＢＡＤＣＢ 26~30 ＡＣＤＤＤ 31~35ＣＡＡＡＢ 36~40ＢＣＣＤＣ
41~42ＢＤ
| 查找 |
散列表
1. 在散列表中，所谓同义词就是具有相同散列地址的两个元素。 (1 分) 2. 2.在散列表中，所谓同义词就是被不同散列函数映射到同一地址的两个元素。 (1 分)
3. 将 M 个元素存入用长度为 S 的数组表示的散列表，则该表的装填因子为 M/S。 (1 分)
4.在散列中，函数“插入”和“查找”具有同样的时间复杂度。 (1 分)
5. 即使把 2 个元素散列到有 100 个单元的表中，仍然有可能发生冲突。 (1 分)
答案：１～５ＴＦＴＴＴ
已知一个长度为 16 的顺序表 L，其元素按关键字有序排列。若采用二分查找法查找一个 L 中不存在的元素，则关键字的比较次数最多是：
A.4 B.5 C.6 D.7
用二分查找从 100 个有序整数中查找某数，最坏情况下需要比较的次数是：
A.7 B.10 C.50 D.99
3. 在有 n（n>1000）个元素的升序数组 A 中查找关键字 x。查找算法的伪代码如下所示：
k=0; while(k<n且A[k]<x) k=k+3; if(k<n且A[k]==x) 查找成功; else if(k-1<n且A[k-1]==x) 查找成功; else if(k-n2<且A[k-2]==x) 查找成功; else 查找失败;
本算法与二分查找（折半查找）算法相比，有可能具有更少比较次数的情形是：
A. 当 x 不在数组中 B. 当 x 接近数组开头处 C. 当 x 接近数组结尾处 D. 当 x 位于数组中间位置
4.下列二叉树中，可能成为折半查找判定树（不含外部结点）的是：
A.
B.
C.
D.
5. 在散列表中，所谓同义词就是：
A.两个意义相近的单词 B. 具有相同散列地址的两个元素
C. 被映射到不同散列地址的一个元素 D. 被不同散列函数映射到同一地址的两个元素
在下列查找的方法中，平均查找长度与结点个数无关的查找方法是：
A.顺序查找 B.二分法 C.利用哈希表（散列） D.利用二叉搜索树
对包含 N 个元素的散列表进行查找，平均查找长度为：
A. O(1) B. O(????) C. O(N) D.不确定
8.将 M 个元素存入用长度为 S 的数组表示的散列表，则该表的装填因子为：
A.S+M B.M-S. C.M*S D.M/S
9. 散列冲突可以被描述为：
两个元素除了有不同键值，其它都相同
两个有不同数据的元素具有相同的键值
两个有不同键值的元素具有相同的散列地址
两个有相同键值的元素具有不同的散列地址
将 10 个元素散列到 100000 个单元的哈希表中，是否一定产生冲突？
A.一定会 B.可能会 C.一定不会 D.有万分之一的可能会
设散列表的地址区间为[0,16]，散列函数为 H(Key)=Key%17。采用线性探测法处理冲突，并将关键字序列{ 26，25，72，38，8，18，59 }依次存储到散列表中。元素 59 存放在散列表中的地址是： (2
分)
A.8 B.9 C.10 D.11
12.采用线性探测法解决冲突时所产生的一系列后继散列地址： (2 分
A.必须大于等于原散列地址 B. 必须小于等于原散列地址
C. 可以大于或小于但不等于原散列地址 D. 对地址在何处没有限制
13.将元素序列{18，23，11，20，2，7，27，33，42，15}按顺序插入一个初始为空的、大小为 11 的散列表中。散列函数为：H(Key)=Key%11，采用线性探测法处理冲突。问：当第一次发现有冲突时，散列表的装填因子大约是多少？
A.0.27 B.0.45 C.0.64 D.0.73
14. 从一个具有 N 个结点的单链表中查找其值等于 X 的结点时，在查找成功的情况下，需平均比较多少个结点？
A.N/2 B.N C.(N-1)/2 D.(N+1)/2
15. 给定输入序列 {4371, 1323, 6173, 4199, 4344, 9679, 1989} 以及散列函数 h(X)=X%10。如果用大小为 10 的散列表，并且用分离链接法解决冲突，则输入各项经散列后在表中的下标为：（-1 表示相应的插入无法成功）
A. 1, 3, 3, 9, 4, 9, 9 B. 1, 3, 4, 9, 7, 5, -1 C.1, 3, 4, 9, 5, 0, 8 D. 1, 3, 4, 9, 5, 0, 2
16. 设数字 {4371, 1323, 6173, 4199, 4344, 9679, 1989} 在大小为 10 的散列表中根据散列函数 h(X)=X%10 得到的下标对应为 {1, 3, 4, 9, 5, 0, 2}。那么继续用散列函数 “h(X)=X%表长”实施再散列
并用线性探测法解决冲突后，它们的下标变为：
A. 11, 3, 13, 19, 4, 0, 9 B. 1, 3, 4, 9, 5, 0, 2 C. 1, 12, 9, 13, 20, 19, 11 D. 1, 12, 17, 0, 13, 8, 14
17.若 N 个关键词被散列映射到同一个单元，并且用分离链接法解决冲突，则找到这 N 个关键词所用的比较次数为：
A.N(N+1)/2 B. N(N−1)/2 C. N+1 D.N
18. 若 N 个关键词被散列映射到同一个单元，并且用分离链接法解决冲突，则找到这 N 个关键词所用的比较次数为：
A. N(N−1)/2 B. N(N+1)/2 C.N D.N+1
19.现有长度为 7、初始为空的散列表 HT，散列函数 H(k)=k%7，用线性探测再散列法解决冲突。将关键字 22, 43, 15 依次插入到 HT 后，查找成功的平均查找长度是：
| A.1.5 B.1.6 | C.2 D.3 | ||
| 答案：1～5ＢＡＢＡＢ | 6～10ＣＤＤＣＢ | 11～15ＤＣＢＤＡ | 16～19ＣＡＢＣ |
排序
1-1 希尔排序是稳定的算法。 (1 分)
1-2 对 N 个不同的数据采用冒泡排序进行从大到小的排序，当元素基本有序时交换元素次数肯定最多。 (1 分) 1-3 对 N 个记录进行快速排序，在最坏的情况下，其时间复杂度是 O(NlogN)。 (1 分) 1-4 对 N 个记录进行简单选择排序，比较次数和移动次数分别为 O(N2)和 O(N)。 (1 分) 1-5 要从 50 个键值中找出最大的 3 个值，选择排序比堆排序快。 (1 分) 1-6 对 N 个记录进行堆排序，需要的额外空间为 O(N)。 (1 分) 1-7 对 N 个记录进行归并排序，归并趟数的数量级是 O(NlogN)。 (1 分) 答案：ＦＦＦＴＴＦＦ 2-1 排序方法中，从未排序序列中依次取出元素与已排序序列中的元素进行比较，将其放入已排序序列的正确位置的方法称为：
A. 插入排序 B. 选择排序 C. 快速排序 D. 归并排序
2-2 对于序列{ 49，38，65，97，76，13，27，50 }，按由小到大进行排序，下面哪一个是初始步长为
4 的希尔排序法第一趟的结果？
A. 13,27,38,49,50,65,76,97 B. 49,13,27,50,76,38,65,97
C. 49,76,65,13,27,50,97,38 D. 97,76,65,50,49,38,27,13
2-3 对一组包含 10 个元素的非递减有序序列，采用直接插入排序排成非递增序列，其可能的比较次数和移动次数分别是：
A. 100, 100 B. 100, 54 C.54, 63 D. 45, 44
2-4 设有 1000 个元素的有序序列，如果用二分插入排序再插入一个元素，则最大比较次数是：
1000 B. 999 C. 500 D. 10
2-5 给定初始待排序列{ 15，9，7，8，20，-1，4 }。如果希尔排序第一趟结束后得到序列为{ 15，-1， 4，8，20，9，7 }，则该趟增量为：
A.1 B.2 C.3 D.4
2-6 对初始数据序列{ 8, 3, 9, 11, 2, 1, 4, 7, 5, 10, 6 }进行希尔排序。若第一趟排序结果为（ 1, 3, 7, 5, 2, 6, 4, 9, 11, 10, 8 ），第二趟排序结果为（ 1, 2, 6, 4, 3, 7, 5, 8, 11, 10, 9 ），则两趟排序采用的增量
（间隔）依次是：
A.3,1 B.3,2 C5,2 D.5,3
2-7 对于 7 个数进行冒泡排序，需要进行的比较次数为：
A.7 B.14 C.21 D.49
2-8 对 N 个不同的数据采用冒泡算法进行从大到小的排序，下面哪种情况下肯定交换元素次数最多？
A. 从小到大排好的 B. 从大到小排好的 C. 元素无序 D. 元素基本有序
2-9 采用递归方式对顺序表进行快速排序，下列关于递归次数的叙述中，正确的是：
每次划分后，先处理较长的分区可以减少递归次数
每次划分后，先处理较短的分区可以减少递归次数
递归次数与每次划分后得到的分区处理顺序无关
递归次数与初始数据的排列次序无关
2-10 对 N 个记录进行快速排序，在最坏的情况下，其时间复杂度是：
A. O(N) B. O(NlogN) C. O(N2) D. O(N2logN)
2-11 有组记录的排序码为{46，79，56，38，40，84 }，采用快速排序（以位于最左位置的对象为基准而）得到的第一次划分结果为：
A. {38,46,79,56,40,84} B. {38,79,56,46,40,84} C. {38,46,56,79,40,84} D. {40,38,46,56,79,84}
2-12 对 N 个元素采用简单选择排序，比较次数和移动次数分别为：
A. O(N2), O(N) B. O(N), O(logN) C. O(logN), O(N2) D. O(NlogN), O(NlogN)
2-13 对于 10 个数的简单选择排序，最坏情况下需要交换元素的次数为：
A. 9 B.36 C.45 D.100
2-14 对 N 个记录进行堆排序，最坏的情况下时间复杂度是：
A. O(logN) B. O(N) C. O(NlogN) D. O(N2)
2-15 有组记录的排序码为{ 46，79，56，38，40，84 }，则利用堆排序的方法建立的初始堆为：
A. 79，46，56，38，40，80 B. 84，79，56，46，40，38
C. 84，56，79，40，46，38 D. 84，79，56，38，40，46
2-16 对 N 个记录进行堆排序，需要的额外空间为：
A. O(1) B. O(logN) C. O(N) D. O(NlogN)
2-17 对 N 个记录进行归并排序，空间复杂度为：
A. O(logN) B. O(N) C. O(NlogN) D. O(N2)
2-18 对 N 个记录进行归并排序，归并趟数的数量级是：
A. O(logN) B. O(N) C. O(NlogN) D. O(N2)
2-19 对给定序列{ 110，119，7，911，114，120，122 }采用次位优先（LSD）的基数排序，则两趟收集后的结果为：
A. 7, 110, 119, 114, 911, 120, 122 B. 7, 110, 119, 114, 911, 122, 120
C.7, 110, 911, 114, 119, 120, 122 D. 110, 120, 911, 122, 114, 7, 119
2-20 在基于比较的排序算法中，哪种算法的最坏情况下的时间复杂度不高于 O(NlogN)？
A. 冒泡排序 B. 归并排序 C. 希尔排序 D. 快速排序
2-21 下列排序算法中，哪种算法可能出现：在最后一趟开始之前，所有的元素都不在其最终的位置上？（设待排元素个数 N>2）
A. 冒泡排序 B. 插入排序 C. 堆排序 D. 快速排序
2-22 在对 N 个元素进行排序时，基于比较的算法中，其“最坏时间复杂度”中最好的是：
A. O(logN) B. O(N) C. O(NlogN) D. O(N2)
2-23 若数据元素序列{ 11，12，13，7，8，9，23，4，5 }是采用下列排序方法之一得到的第二趟排序后的结果，则该排序算法只能是：
A. 冒泡排序 B. 选择排序 C. 插入排序 D. 归并排序
2-24 数据序列{ 3，2，4，9，8，11，6，20 }只能是下列哪种排序算法的两趟排序结果？
A. 冒泡排序 B. 选择排序 C. 插入排序 D. 快速排序
2-25 对一组数据{ 2，12，16，88，5，10 }进行排序，若前三趟排序结果如下： 第一趟排序结果：2， 12，16，5，10，88 第二趟排序结果：2，12，5，10，16，88 第三趟排序结果：2，5，10，12， 16，88 则采用的排序方法可能是：
A. 冒泡排序 B. 希尔排序 C.归并排序 D. 基数排序
2-26 就排序算法所用的辅助空间而言，堆排序、快速排序、归并排序的关系是：
A. 堆排序 < 归并排序 < 快速排序 B.堆排序 > 归并排序 > 快速排序
C. 堆排序 < 快速排序 < 归并排序 D. 堆排序 > 快速排序 > 归并排序
2-27 下面四种排序算法中，稳定的算法是：
A.堆排序 B. 希尔排序 C. 归并排序 D. 快速排序
2-28 下列排序算法中，时间复杂度不受数据初始状态影响，恒为 O(NlogN)的是：
A. 冒泡排序 B. 直接选择排序 C. 堆排序 D. 快速排序
2-29{ 12，9，11，8，7，4，5，13，23 }是下列哪种方法第二趟排序后的结果？
A. 归并排序 B.堆排序 C. 插入排序 D. 基数排序
2-30 若数据元素序列{ 12, 13, 8, 11, 5, 16, 2, 9 }是采用下列排序方法之一得到的第一趟排序后的结果，则该排序算法只能是：
A. 快速排序 B. 选择排序 C.堆排序 D. 归并排序
2-31 输入 104 个只有一位数字的整数，可以用 O(N)复杂度将其排序的算法是：
A. 桶排序 B. 快速排序 C. 插入排序 D. 希尔 排序
2-32 将序列{ 2, 12, 16, 88, 5, 10, 34 }排序。若前 2 趟排序的结果如下：
第 1 趟排序后：2, 12, 16, 10, 5, 34, 88
第 2 趟排序后：2, 5, 10, 12, 16, 34, 88
则可能的排序算法是：
A. 冒泡排序 B.快速排序 C. 归并排序 D. 插入排序
2-33 数据序列{ 3, 1, 4, 11, 9, 16, 7, 28 }只能是下列哪种排序算法的两趟排序结果？
A. 冒泡排序 B. 快速排序 C. 插入排序 D. 堆排序
2-34.在内部排序时，若选择了归并排序而没有选择插入排序，则可能的理由是：
1. 归并排序的程序代码更短 2. 归并排序占用的空间更少
3. 归并排序的运行效率更高
| A.２ Ｂ.３ | C.1,2 D1,3 | ||
| 答案：1~5ＡＢＤＤＤ | 6~10ＤＣＡＣＣ | 11~15ＢＡＣＣＤ | 16~20 ＡＢＡＣＢ |
| 21~25ＢＣＣＤＡ | 26~30ＣＣＣＢＤ | 31~34ＢＣＢＢ |
点击数：406
