第1章 绪论
一、选择题
1. 算法的计算量的大小称为计算的（ B ）。
A ．效率 B. 复杂性 C. 现实性 D. 难度
2. 算法的时间复杂度取决于（C ）
A ．问题的规模 B. 待处理数据的初态 C. A和B
3. 计算机算法指的是（1），它必须具备（2） 这三个特性。
(1) A．计算方法 B. 排序方法 C. 解决问题的步骤序列 D. 调度方法
(2) A．可执行性、可移植性、可扩充性 B. 可执行性、确定性、有穷性
C. 确定性、有穷性、稳定性 D. 易读性、稳定性、安全性
4. 一个算法应该是（ C ）。
A．程序 B．问题求解步骤的描述
C ．数据结构+程序 D．以上都不对.
5. 下面关于算法说法错误的是（ ）
A ．算法最终必须由计算机程序实现
B. 为解决某问题的算法同为该问题编写的程序含义是相同的
C. 算法的可行性是指指令不能有二义性 D. 以上几个都是错误的
6. 下面说法错误的是（ ）
(1）算法原地工作的含义是指不需要任何额外的辅助空间
n （2）在相同的规模n 下，复杂度O(n)的算法在时间上总是优于复杂度O(2) 的算法
（3）所谓时间复杂度是指随问题规模的增大，算法执行时间的增长率。
（4）空间复杂度是算法所需存储空间的量度。
A．(1) B.(1),(2) C.(1),(4) D.(3)
7. 从逻辑上可以把数据结构分为（ ）两大类。
A ．动态结构、静态结构 B．顺序结构、链式结构
C ．线性结构、非线性结构 D．初等结构、构造型结构
8. 以下与数据的存储结构无关的术语是（ ）。
A ．循环队列 B. 链表 C. 哈希表 D. 栈
9. 连续存储设计时，存储单元的地址（ ）。
A ．一定连续 B．一定不连续 C．不一定连续 D．部分连续，部分不连续
10. 以下属于逻辑结构的是（ ）。
A ．顺序表 B. 哈希表 C.有序表 D. 单链表
第2章 线性表
一、选择题
1. 下述哪一条是顺序存储结构的优点？（D ）
A ．存储密度大 B．插入运算方便 C．删除运算方便 D．可方便地用于各种逻辑结构的存储表示
2. 下面关于线性表的叙述中，错误的是哪一个？（B ）
A ．线性表采用顺序存储，必须占用一片连续的存储单元。
B ．线性表采用顺序存储，便于进行插入和删除操作。
C ．线性表采用链接存储，不必占用一片连续的存储单元。
D ．线性表采用链接存储，便于插入和删除操作。
3. 线性表是具有n 个（C ）的有限序列（n>0）。
A ．表元素 B．字符 C．数据元素 D．数据项 E．信息项
4. 若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（A ）存储方式最节省时间。
A ．顺序表 B．双链表 C．带头结点的双循环链表 D．单循环链表
5. 某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（A ）存储方式最节省运算时间。
A ．单链表 B．仅有头指针的单循环链表 C．双链表 D．仅有尾指针的单循环链表
6. 设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用( )最节省时间。
A. 单链表 B.单循环链表 C. 带尾指针的单循环链表 D.带头结点的双循环链表
7. 若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点。则采用（ ）存储方式最节省运算时间。
A ．单链表 B．双链表 C．单循环链表 D．带头结点的双循环链表
8. 链表不具有的特点是（ ）
A ．插入、删除不需要移动元素 B．可随机访问任一元素
C．不必事先估计存储空间 D．所需空间与线性长度成正比
9. 下面的叙述不正确的是（ ）
A ．线性表在链式存储时，查找第i 个元素的时间同i 的值成正比
B. 线性表在链式存储时，查找第i 个元素的时间同i 的值无关
C. 线性表在顺序存储时，查找第i 个元素的时间同i 的值成正比
D. 线性表在顺序存储时，查找第i 个元素的时间同i 的值无关
10. 若长度为n 的线性表采用顺序存储结构，在其第i 个位置插入一个新元素的算法的时间复杂度为（ ）(1
2A. O(0) B. O(1) C. O(n) D. O(n)
11. 对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为（ ）。
A ．O(n) O(n) B. O(n) O(1) C. O(1) O(n) D. O(1) O(1)
12. 线性表（ a1,a2,„,an ）以链接方式存储时，访问第i 位置元素的时间复杂性为（ ）
A ．O （i ） B．O （1） C．O （n ） D．O （i-1）
13. 非空的循环单链表head 的尾结点p 满足（ ）。
A ．p.next=head B．p.next=NULL C．p=NULL D．p= head
14. 在单链表指针为p 的结点之后插入指针为s 的结点，正确的操作是：（ ）。
A ．p->next=s;s->next=p->next; B． s->next=p->next;p->next=s;
C ．p->next=s;p->next=s->next; D． p->next=s->next;p->next=s;
15. 对于一个头指针为head 的带头结点的单链表，判定该表为空表的条件是（ ）
A ．head==NULL B．head->next==NULL
C ．head->next==head D．head!=NULL
二、综合应用题
1. 已知线性表（a1 a2 a3 „an ）按顺序存于内存，每个元素都是整数，试设计用最少时
间把所有值为负数的元素移到全部正数值元素前边的算法：例：（x,-x,-x,x,x,-x „x ）变为（-x,-x,-x „x,x,x ）。
2. 设单链表的表头指针为h ，结点结构由data 和next 两个域构成，其中data 域为字符
型。写出算法dc(h,n),判断该链表的前n 个字符是否中心对称。例如 xyx, xyyx都是中心对称。
3. 已知非空线性链表由list 指出，链结点的构造为（data,link ）. 请写一算法，将链表
中数据域值最小的那个链结点移到链表的最前面。要求：不得额外申请新的链结点。
4. 试编写在带头结点的单链表中删除（一个）最小值结点的（高效）算法。
void delete（Linklist &L）
5. 设有一头指针为L 的带有表头结点的非循环双向链表，其每个结点中除有pred （前驱
指针），data （数据）和next （后继指针）域外，还有一个访问频度域freq 。在链表被起用前，其值均初始化为零。每当在链表中进行一次Locate(L,x)运算时，令元素值为x 的结点中freq 域的值增1，并使此链表中结点保持按访问频度非增（递减）的顺序排列，同时最近访问的结点排在频度相同的结点的最后，以便使频繁访问的结点总是靠近表头。试编写符合上述要求的Locate(L,x)运算的算法，该运算为函数过程，返回找到结点的地址，类型为指针型。
6. 已知长度为n 的线性表A 采用顺序存储结构，请写一时间复杂度为0(n)、空间复杂度
为0(1)的算法，该算法删除线性表中所有值为item 的数据元素。（O （1）表示算法的辅助空间为常量）。
第3章 栈和队列
一、选择题
1. 对于栈操作数据的原则是（ ）。
A. 先进先出 B. 后进先出 C. 后进后出 D. 不分顺序
2. 一个栈的输入序列为123„n ，若输出序列的第一个元素是n ，输出第i （1
A. 不确定 B. n-i+1 C. i D. n-i
3. 若一个栈的输入序列为1,2,3, „,n ，输出序列的第一个元素是i ，则第j 个输出元素是（ ）。
A. i-j-1 B. i-j C. j-i+1 D. 不确定的
4. 一个栈的输入序列为1 2 3 4 5，则下列序列中不可能是栈的输出序列的是（ ）。
A. 2 3 4 1 5 B. 5 4 1 3 2
C. 2 3 1 4 5 D. 1 5 4 3 2
5. 输入序列为ABC ，可以变为CBA 时，经过的栈操作为（ ）
A. push,pop,push,pop,push,pop
B. push,push,push,pop,pop,pop
C. push,push,pop,pop,push,pop
D. push,pop,push,push,pop,pop
6. 若一个栈以向量V[1..n]存储，栈为空时栈顶指针top 为n+1，则下面x 进栈的正确操作是( )。
A ．top:=top+1; V [top]:=x
B. V [top]:=x; top:=top+1
C. top:=top-1; V [top]:=x
D. V [top]:=x; top:=top-1
7. 栈在（ ）中应用。
A. 递归调用 B. 子程序调用 C. 表达式求值 D. A，Ｂ，Ｃ
8. 一个递归算法必须包括（ ）。
A. 递归部分 B. 终止条件和递归部分 C. 迭代部分 D.终止条件和迭代部分
9. 用不带头结点的单链表存储队列时, 其队头指针指向队头结点, 其队尾指针指向队尾结点，则在进行删除操作时( )。
A ．仅修改队头指针 B. 仅修改队尾指针
C. 队头、队尾指针都要修改 D. 队头, 队尾指针都可能要修改
10. 递归过程或函数调用时，处理参数及返回地址，要用一种称为（ ）的数据结构。
A ．队列 B．多维数组 C．栈 D. 线性表
11. 假设以数组A[m]存放循环队列的元素, 其头尾指针分别为front 和rear ，则当前队列中的元素个数为（ ）。
A ．(rear-front+m)%m B．rear-front+1 C．(front-rear+m)%m D．(rear-front)%m
12. 循环队列存储在数组A[0..m]中，则入队时的操作为（ ）。
A. rear=rear+1 B. rear=(rear+1) mod (m-1)
C. rear=(rear+1) mod m D. rear=(rear+1)mod(m+1)
13. 若用一个大小为6的数组来实现循环队列，且当前rear 和front 的值分别为0和3，
当从队列中删除一个元素，再加入两个元素后，rear 和front 的值分别为多少？( )
A. 1和 5 B. 2和4 C. 4和2 D. 5和1
14. 栈的特点是（ ① ）, 队列的特点是（ ② ）, 栈和队列都是（ ③ ）。若进栈序
列为1,2,3,4 则（ ④ ）不可能是一个出栈序列（不一定全部进栈后再出栈）；若进队列的序列为1,2,3,4 则（ ⑤ ）是一个出队列序列。
①, ②: A. 先进先出 B. 后进先出 C. 进优于出 D. 出优于进 ③: A.顺序存储的线性结构 B.链式存储的线性结构
C. 限制存取点的线性结构 D.限制存取点的非线性结构
④, ⑤: A. 3,2,1,4 B. 3,2,4,1 C. 4,2,3,1 D. 4,3,2,1 F. 1,2,3,4 G. 1,3,2,4
15. 栈和队列的共同点是（ ）。
A. 都是先进先出 B. 都是先进后出
C. 只允许在端点处插入和删除元素 D. 没有共同点
16. 设栈S 和队列Q 的初始状态为空，元素e1，e2，e3，e4,e5和e6依次通过栈S ，一个
元素出栈后即进队列Q ，若6个元素出队的序列是e2，e4，e3,e6,e5,e1则栈S 的容量至少应该是( )。
A ． 6 B. 4 C. 3 D. 2
17. 用单链表表示的链式队列的队头在链表的（ ）位置。
A ．链头 B．链尾 C．链中
二、综合应用题
1. 有5 个元素，其入栈次序为：A ，B ，C ，D ，E ，在各种可能的出栈次序中，以元素C ，D
最先出栈（即C 第一个且D 第二个出栈）的次序有哪几个？
2. 设从键盘输入一整数的序列：a1, a2, a3，„，an, 试编写算法实现：用栈结构存储输
入的整数，当ai ≠-1时，将ai 进栈；当ai=-1时，输出栈顶整数并出栈。算法应对异常情况（栈空等）给出相应的信息。
3. 设表达式以字符形式已存入数组E[n]中，‘#’为表达式的结束符，试写出判断表达式
中括号（‘（’和‘）’）是否配对的C 语言描述算法; (注：算法中可调用栈操作的基本算法。)
第4章 树和二叉树
一、选择题
1. 设树T 的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1 则T 中的叶子数为（ ）
A ．5 B．6 C．7 D．8
2. 在下述结论中，正确的是（ ）
①只有一个结点的二叉树的度为0; ②二叉树的度为2； ③二叉树的左右子树可任意交换;
④深度为K 的完全二叉树的结点个数小于或等于深度相同的满二叉树。
A ．①②③ B．②③④ C．②④ D．①④
3. 设森林F 对应的二叉树为B ，它有m 个结点，B 的根为p,p 的右子树结点个数为n, 森林F 中第一棵树的结点个数是（ ）
A ．m-n B．m-n-1 C．n+1 D．条件不足，无法确定
4. 若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（ ）
A ．9 B．11 C．15 D．不确定
5. 设森林F 中有三棵树，第一，第二，第三棵树的结点个数分别为M1，M2和M3。与森林F 对应的二叉树根结点的右子树上的结点个数是（ ）。
A ．M1 B．M1+M2 C．M3 D．M2+M3
6. 具有10个叶结点的二叉树中有（ ）个度为2的结点，
A ．8 B．9 C．10 D．ll
7. 若一棵二叉树有126个节点，在第7层（根节点在第1层）至多有（ ）个节点。
A ． 32 B． 64 C．63 D．不存在第7层
8. 设给定权值总数有n 个，其哈夫曼树的结点总数为( )
A ．不确定 B．2n C．2n+1 D．2n-1
9. 下列关于哈夫曼树的 说法中最准确的是（ ）。
A ．最优树 B．叶子节点带有权值的二叉树 C.最优二叉树 D．叶子节点带有权值的树
10. 有关二叉树下列说法正确的是（ ）
A ．二叉树的度为2 B．一棵二叉树的度可以小于2
C ．二叉树中至少有一个结点的度为2 D．二叉树中任何一个结点的度都为2
11. 二叉树的第I 层上最多含有结点数为（ ）
I I-1I-1I A ．2 B． 2-1 C． 2 D．2 -1
12. 一个具有1025个结点的二叉树的高h 为（ ）
A ．11 B．10 C．11至1025之间 D．10至1024之间
13. 一棵二叉树高度为h, 所有结点的度或为0，或为2，则这棵二叉树最少有( )结点
A ．2h B．2h-1 C．2h+1 D．h+1
14. 对于有n 个结点的二叉树, 其高度为（ ）
A ．nlog 2n B．log 2n C．⎣log 2n ⎦+1 D．不确定
15. 一棵具有 n个结点的完全二叉树的树高度（深度）是（ ）
A ．⎣log 2n ⎦+1 B．log 2n+1 C．⎣log 2n ⎦ D．log 2n-1
16. 高度为 K的二叉树最大的结点数为（ ）。
A ．2 B．2 C．2 -1 D．2-1 k k-1k k-1
17. 一棵高为K 的完全二叉树至少有（ ）个结点
k k-1k-1k A ．2 –1 B. 2 –1 C. 2 D. 2
18. 对于先序遍历和中序遍历结果相同的二叉树是（ ）。
A ． 无左子树的二叉树 B．无右子树的二叉树 C．所有节点只有左子树的二叉树 D．所有节点只有右子树的二叉树
19. 对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，
同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采用( )次序的遍历实现编号。
A ．先序 B. 中序 C. 后序 D. 从根开始按层次遍历
20. 树的后根遍历序列等同于该树对应的二叉树的( ).
A. 先序序列 B. 中序序列 C. 后序序列
21. 在下列存储形式中，哪一个不是树的存储形式？（ ）
A ．双亲表示法 B．孩子链表表示法 C．孩子兄弟表示法 D．顺序存储表示法
22. 一棵二叉树的前序遍历序列为ABCDEFG ，它的中序遍历序列可能是（ ）
A ．CABDEFG B．ABCDEFG C．DACEFBG D．ADCFEG
23. 已知一棵二叉树的前序遍历结果为ABCDEF, 中序遍历结果为CBAEDF, 则后序遍历的结果
为（ ）。
A ．CBEFDA B． FEDCBA C． CBEDFA D．不定
24. 某二叉树中序序列为A,B,C,D,E,F,G ，后序序列为B,D,C,A,F,G,E 则前序序列是
（ ）。
A ．E,G,F,A,C,D,B B．E,A,C,B,D,G,F C．E,A,G,C,F,B,D D．上面的都不对
25. 二叉树的先序遍历和中序遍历如下： 先序遍历：EFHIGJK ；中序遍历: HFIEJKG 。该二
叉树根的右子树的根是（ ）。
A 、 E B、 F C、 G D、 H
26. 某二叉树T 有n 个结点，设按某种顺序对T 中的每个结点进行编号，编号为1，2，„ ，
n ，且有如下性质：T 中任一结点V ，其编号等于左子树上的最小编号减1，而V 的右子树的结点中，其最小编号等于V 左子树上结点的最大编号加1。这时是按( )编号的。
A. 中序遍历序列 B.前序遍历序列 C.后序遍历序列 D.层次顺序
27. 一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足
（ ）。
A ．完全二叉树 B．只有两个结点的二叉树 C. 二叉排序树 D. 任一节点只有一个孩子结点
28. 任何一颗二叉树的叶子结点在先序序列，中序序列和后序序列中的相对次序（ ）。
A ．不 发生改变 B ．发生改变 C．不能确定 D ．以上都不对
29. 若对二叉树进行中序遍历，具有左、右子树的结点，其后继是该结点的（ ）。
A ． 双亲结点 B．其左子树中最右下角元素 C．其右孩子 D．其右子树中最左下角元素
30. 在完全二叉树中，若一个结点是叶结点，则它没（ ）。
A．左子结点 B．右子结点 C．左子结点和右子结点 D．左子结点，右子结点和兄弟结点
31. 一棵左子树为空的二叉树在先序线索化后，其中空的链域的个数是：( )。
A ．不确定 B. 0 C. 1 D. 2
32. 一棵左右子树均不空的二叉树在先序线索化后，其中空的链域的个数是：( )。
A. 0 B. 1 C. 2 D. 不确定
33. 若X 是二叉中序线索树中一个有左孩子的结点，且X 不为根，则x 的前驱为( ) 。
A. X的双亲 B. X的右子树中最左的结点 C. X的左子树中最右结点 D. X的左子树中最右叶结点
34. 引入线索二叉树的目的是（ ）
A ．加快查找结点的前驱或后继的速度 B．为了能在二叉树中方便的进行插入与删除
C ．为了能方便的找到双亲 D．使二叉树的遍历结果唯一
35. n 个结点的线索二叉树上含有的线索数为（ ）
A ．2n B．n －l C．n ＋l D．n
36. 设F 是一个森林，B 是由F 变换得的二叉树。若F 中有n 个非终端结点，则B 中右指针
域为空的结点有（ ）个。
A ． n-1 B．n C． n+1 D． n+2
37. 在叶子数目和权值相同的所有二叉树中，最优二叉树一定是完全二叉树，该说法（ ）。
A．正确 B．错误
38. 下述编码中哪一个不是前缀码（ ）。
A ．（00，01，10，11） B．（0，1，00，11） C．（0，10，110，111） D．（1，01，000，001）
39. 一棵有n 个结点的二叉树，按层次从上到下，同一层从左到右顺序存储在一维数组
A[1..n]中，则二叉树中第i 个结点（i 从1开始用上述方法编号）的右孩子在数组A 中的位置是（ ）
A ．A[2i](2i
40. 从下列有关树的叙述中, 选出5条正确的叙述（ ）。
A ．二叉树中每个结点有两个子结点, 而树无此限制, 因此二叉树是树的特殊情况。
k-1B ．当K ≥1时高度为K 的二叉树至多有2个结点。
C ．用树的前序遍历和中序遍历可以导出树的后序遍历。
D ．线索二叉树的优点是便于查找某结点的前驱结点和后继结点。
E ．将一棵树转换成二叉树后, 根结点没有左子树。
F ．一棵含有N 个结点的完全二叉树, 它的高度是⎣LOG 2N ⎦+1。
G ．在二叉树中插入结点, 该二叉树便不再是二叉树。
H ．采用二叉树链表作树的存储结构, 树的前序遍历和其相应的二叉树的前序遍历的结果是一样的。
I ．哈夫曼树是带权路径最短的树, 路径上权值较大的结点离根较近。
J ．用一维数组存储二叉树时, 总是以前序遍历存储结点。
二、综合应用题
1、 一棵高度为 5 的二叉树中最少含有 _________ 个结点，最多含有 ________ 个结点。
2、 具有65个结点的完全二叉树的高度为_________。（根的层次号为1）.
3、 假设一棵二叉树的前序序列为 EBADCFHGIKJ 和中序序列为 ABCDEFGHIJK 。请画出
该树。
4、 已知一棵完全二叉树中共有768结点，则该树中共有______个叶子结点。
5、 有n 个结点并且其高度为n 的二叉树的数目是多少?
6、 试找出分别满足下列条件的所有二叉树。
1）先序序列和中序序列相同 2）中序序列和后序序列相同
3）先序序列和后序序列相同
7、 设A 、B 、C 、D 、E 、F 六个字母出现的概率分别为7,19,2,6,32,3。试写出为这六个字母
设计的HUFFMAN 编码，并求出对应HUFFMAN 树的带权路径长度。
8、 已知一棵树的先序序列和后序序列如下，请构造出该树。
先序序列：ABCDEFGHIJ
后序序列：CDEBFHIJGA
9、 一棵二叉树的先序、中序和后序序列分别如下，其中有一部分为显示出来。试求出空格
处的内容，并画出该二叉树。
先序序列: _ B F I C E H G
中序序列：D K F I A E J C
后序序列： K F B H J G A
10、 如在内存中存放一个完全二叉树，在树上只进行下面两个操作：
（1）寻找某个结点双亲 （2）寻找某个结点的儿子；
请问应该用何种结构来存储该二叉树？
11、 将二叉树bt 中每一个结点的左右子树互换。请分别用递归和非递归算法实现。
12、 二叉树采用二叉链表存储，编写计算二叉树最大宽度的算法（二叉树的最大宽度是
指二叉树所有层中结点个数的最大值）。 13、 试写出一递归函数，判别两棵树是否相等 14、 请设计一个算法，要求该算法把二叉树的叶子结点按从左到右的顺序连成一个单链
表，表头指针为head 。 二叉树按二叉链表方式存储，链接时用叶子结点的右指针域来存放单链表指针。
15、 下面是求二叉树高度的类C 写的递归算法，试补充完整
[说明]二叉树的两指针域为lchild 与rchild, 算法中p 为二叉树的根，lh 和rh 分别为以p 为根的二叉树的左子树和右子树的高，hi 为以p 为根的二叉树的高，hi 最后返回。
height(p)
{if ((1)___)
{if(p->lchild==null) lh=(2)_______; else lh=(3)_______;
if(p->rchild==null) rh=(4)_______; else rh=(5)_______;
if (lh>rh) hi=(6)__；else hi=(7)_______;
}
else hi=(8)_______;
return hi;
}
16、 将下列由三棵树组成的森林转换为二叉树。
17、 设T 是一棵给定的查找树, 试编写一个在树中删除根结点为a 的子树的程序, 要求
在删除的过程中释放该子树所有结点所占有的存储空间, 这里假设树T 中结点所占有的存储空间是通过动态存储分配取得的, 其结点的形式为:（lchild,data,rchild ）
18、 试编写算法，对一棵以孩子—兄弟链表表示的树统计叶子的个数。
第5章 图
一、选择题
1. 图中有关路径的定义是（ ）。
A ．由顶点和相邻顶点序偶构成的边所形成的序列 B．由不同顶点所形成的序列
C ．由不同边所形成的序列 D．上述定义都不是
2. 设无向图的顶点个数为n ，则该图最多有（ ）条边。
A ．n-1 B．n(n-1)/2
2C ． n(n+1)/2 D．0 E．n
3. 一个n 个顶点的连通无向图，其边的个数至少为（ ）。
A ．n-1 B．n C．n+1 D．nlogn ；
4. n 个结点的完全有向图含有边的数目（ ）。
A ．n*n Ｂ．n （n ＋１） C．n ／2 D．n*（n －l ）
5. 一个有n 个结点的图，最少有（ ）个连通分量，最多有（ ）个连通分量。
A ．0 B．1 C．n-1 D．n
6. 在一个无向图中，所有顶点的度数之和等于所有边数（ ）倍，在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的（ ）倍。
A ．1/2 B．2 C．1 D．4
7. 用DFS 遍历一个无环有向图，并在DFS 算法退栈返回时打印相应的顶点，则输出的顶点序列是( )。
A ．逆拓扑有序 B．拓扑有序 C．无序的
8. 无向图G 是 一个连通图，有9条边，则该图至少有（ ）个顶点。
A ．4 B．5 C．6 D．7
9. 下列哪一种图的邻接矩阵是对称矩阵？（ ）
A ．有向图 B．无向图 C．AOV 网 D．AOE 网
10. 下列说法不正确的是（ ）。
A ．图的遍历是从给定的源点出发每一个顶点仅被访问一次
B ．遍历的基本算法有两种：深度遍历和广度遍历
C ．图的深度遍历不适用于有向图
D ．图的深度遍历是一个递归过程
11. 无向图G=(V,E),其中：V={a,b,c,d,e,f}, E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)}，对该图进行深度优先遍历，得到的顶点序列正确的是（ ）。
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
12. 下面哪些方法可以判断出一个有向图是否有环（回路）： （ ）
A ．深度优先遍历 B. 拓扑排序 C. 求最短路径 D. 求关键路径
13. 在图采用邻接表存储时，求最小生成树的 Prim 算法的时间复杂度为( )。
23A. O(n) B. O(n+e) C. O(n) D. O(n)
14. 当各边上的权值( )时，广度优先遍历算法可用来解决单源最短路径问题。
A ．均相等 B．均互不相等 C．不一定相等
15. 已知有向图G=(V,E)，其中V={V1,V2,V3,V4,V5,V6,V7}，E={,,,,,,,,},G 的拓扑序列是（ ）。
A ．V 1,V 3,V 4,V 6,V 2,V 5,V 7 B．V 1,V 3,V 2,V 6,V 4,V 5,V 7
C ．V 1,V 3,V 4,V 5,V 2,V 6,V 7 D．V 1,V 2,V 5,V 3,V 4,V 6,V 7
16. 若一个有向图的邻接距阵中, 主对角线以下的元素均为零, 则该图的拓扑有序序列
（ ）。
A ．存在 B．不存在
17. 一个有向无环图的拓扑排序序列（ ）是唯一的。
A ．一定 B．不一定
18. 在有向图G 的拓扑序列中，若顶点Vi 在顶点Vj 之前，则下列情形不可能出现的是
（ ）。
A ．G 中有弧 B ．G 中有一条从Vi 到Vj 的路径
C ．G 中没有弧 D．G 中有一条从Vj 到Vi 的路径
19. 关键路径是事件结点网络中（ ）。
A ．从源点到汇点的最长路径 B．从源点到汇点的最短路径
C ．最长回路 D．最短回路
20. 下面关于求关键路径的说法不正确的是（ ）。
A ．求关键路径是以拓扑排序为基础的
B ．一个事件的最早开始时间与以该事件为尾的弧的活动最早开始时间相同
C ．一个事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间与该活动的持续时间的差
D ．关键活动一定位于关键路径上
21. 下列关于AOE 网的叙述中，不正确的是（ ）。
A ．关键活动不按期完成就会影响整个工程的完成时间
B ．任何一个关键活动提前完成，那么整个工程将会提前完成
C ．所有的关键活动提前完成，那么整个工程将会提前完成
D ．某些关键活动提前完成，那么整个工程将会提前完成
二、综合应用题
1. 请计算下图中的强连通分量的个数
2. 考虑下图：
（1）．画出G 的邻接表表示图；
（2）．根据你画出的邻接表，以顶点①为根，
画出G 的深度优先生成树和广度优先生成树。
3. 在什么情况下，Prim 算法与Kruskual 算法生成不同的MST ？
在有相同权值边时生成不同的MST ，在这种情况下，用Prim 或Kruskal 也会生成不
同的MST 。
4. 考虑下图：根据普利姆(Prim) 和Kruskal 算法分别求它的最小生成树。
5. 已知一图如下图所示：
（1）．写出该图的邻接矩阵；
（2）．写出全部拓扑排序；
（3）．以v1为源点, 以v8为终点，给出所有事件允许发生的最早时间和最晚时间，并给出关键路径；
（4）．求V1结点到各点的最短距离。
第6章 查找
一、选择题
1. 若查找每个记录的概率均等，则在具有n 个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL 为( )。
A ． (n-1)/2 B. n/2 C. (n+1)/2 D. n
2. 下面关于二分查找的叙述正确的是 ( )
A. 表必须有序，表可以顺序方式存储，也可以链表方式存储
B. 表必须有序且表中数据必须是整型，实型或字符型
C. 表必须有序，而且只能从小到大排列
D. 表必须有序，且表只能以顺序方式存储
3. 当在一个有序的顺序存储表上查找一个数据时，即可用折半查找，也可用顺序查找，但前者比后者的查找速度( ) 。
A ．必定快 B.不一定 C. 在大部分情况下要快 D. 取决于表递增还是递减
4. 折半查找的时间复杂性为（ ）
2A. O（n ） B. O（n ） C. O（nlogn ） D. O（logn ）
5. 当采用分块查找时，数据的组织方式为 ( )。
A ．数据分成若干块，每块内数据有序
B ．数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大（或最小）的数据组成索引块
C. 数据分成若干块，每块内数据有序，每块内最大（或最小）的数据组成索引块
D. 数据分成若干块，每块（除最后一块外）中数据个数需相同
6. 二叉排序树的查找效率与二叉树的( （1）) 有关, 在 (（2）) 时其查找效率最低
(1): A. 高度 B. 结点的多少 C. 树型 D. 结点的位置
(2): A. 结点太多 B. 完全二叉树 C. 呈单枝树 D. 结点太复杂。
7. 对大小均为n 的有序表和无序表分别进行顺序查找, 在等概率查找的情况下, 对于查找失败, 它们的平均查找长度是((1)) ,对于查找成功, 他们的平均查找长度是((2))供选择的答案:
A. 相同的 B.不同的
8. 分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是( )。
A ．（100，80， 90， 60， 120，110，130）
B. （100，120，110，130，80， 60， 90）
C. （100，60， 80， 90， 120，110，130）
D. (100，80， 60， 90， 120，130，110)
9. 设有一组记录的关键字为{19，14，23，1，68，20，84，27，55，11，10，79}，用链地址法构造散列表，散列函数为H （key ）=key MOD 13,散列地址为1的链中有（ ）个记录。
A ．1 B. 2 C. 3 D. 4
10. 若采用链地址法构造散列表，散列函数为H （key ）=key MOD 17，则需 (（1）) 个链表。这些链的链首指针构成一个指针数组，数组的下标范围为 (（2）)
（1） A．17 B. 13 C. 16 D. 任意
（2） A．0至17 B. 1至17 C. 0至16 D. 1至16
11. 关于哈希查找说法不正确的有几个( )
（1）采用链地址法解决冲突时，查找一个元素的时间是相同的
（2）采用链地址法解决冲突时，若插入规定总是在链首，则插入任一个元素的时间是
相同的
（3）用链地址法解决冲突易引起聚集现象
（4）再哈希法不易产生聚集
A. 1 B. 2 C. 3 D. 4
12. 设哈希表长为14，哈希函数是H(key)=key%11,表中已有数据的关键字为15，38，61，
84共四个，现要将关键字为49的结点加到表中，用二次探测再散列法解决冲突，则放入的位置是( )
A．8 B．3 C．5 D．9
13. 假定有k 个关键字互为同义词，若用线性探测法把这k 个关键字存入散列表中，至少要
进行多少次探测？( )。
A ．k-1次 B. k次 C. k+1次 D. k（k+1）/2次
14. 散列函数有一个共同的性质，即函数值应当以( )取其值域的每个值。
A. 最大概率 B. 最小概率 C. 平均概率 D. 同等概率
15. 将10个元素散列到100000个单元的哈希表中，则（ ）产生冲突。
A. 一定会 B. 一定不会 C. 仍可能会
二、综合应用题
1、如何衡量hash 函数的优劣？简要叙述hash 表技术中的冲突概念，并指出三种解决冲突的方法。
2、在采用线性探测法处理冲突的散列表中，所有同义词在表中是否一定相邻？
3、设有一组关键字{9,01,23,14,55,20,84,27}，采用哈希函数：H （key ）=key mod 7 ，表长为10，用开放地址法的二次探测再散列方法Hi=(H(key)+di) mod 10(di=12,22,32,„,) 解决冲突。要求：对该关键字序列构造哈希表，并计算查找成功的平均查找长度。
4、一棵二叉排序树结构如下, 各结点的值从小到大依次为1-9，请标出各结点的值。
5、依次输入表(30,15,28,20,24,10,12,68,35,50,46,55)中的元素，生成一棵二叉排序树
(1) 试画出生成之后的二叉排序树; (2) 对该二叉排序树作中序遍历，试写出遍历序列;
(3) 假定每个元素的查找概率相等，试计算该二叉排序树的平均查找长度。
6、设二叉排序树中关键字由1到1000的整数组成，现要查找关键字为363的结点，下述关键字序列哪一个不可能是在二叉排序树中查到的序列？说明原因。
（1）51，250，501，390，320，340，382，363 （2）24，877，125，342，501，623，421，363
7、有一个长度为12的有序表，按对半查找法对该表进行查找，在表内各元素等概率情况下，查找成功所需的平均比较次数是多少？
8、假定对有序表：(3,4,5,7,24,30,42,54,63,72,87,95)进行折半查找，试回答下列问题：
(1).画出描述折半查找过程的判定树；
(2).若查找元素54，需依次与那些元素比较?
(3).若查找元素90，需依次与那些元素比较?
(4).假定每个元素的查找概率相等，求查找成功时的平均查找长度。
第7章 排序
一、选择题
1. 某内排序方法的稳定性是指( )。
A ．该排序算法不允许有相同的关键字记录
B ．该排序算法允许有相同的关键字记录
C ．平均时间为0（n log n）的排序方法
D ．以上都不对
2. 下面给出的四种排序法中( )排序法是不稳定性排序法。
A. 插入 B. 冒泡 C. 二路归并 D. 堆排序
3. 若需在O(nlog2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（ ）。
A. 快速排序 B. 堆排序 C. 归并排序 D. 直接插入排序
4. 在希尔排序中，最后一趟排序的增量必须为（ ）。
A ．1 B.3 C. 5 D. 7
5. 排序趟数与序列的原始状态有关的排序方法是( )排序法。
A．插入 B. 选择 C. 冒泡 D. 快速
6. 对下列四种排序方法，在排序中关键字比较次数同记录初始排列无关的是( )。
A ．直接插入 B. 二分法插入
C. 快速排序 D. 归并排序
7. 数据序列（2，1，4，9，8，10，6，20）只能是下列排序算法中的( )的两趟排序后的结果。
A. 快速排序 B. 冒泡排序 C. 选择排序 D. 插入排序
8. 对一组数据（84，47，25，15，21）排序，数据的排列次序在排序的过程中的变化为（1） 84 47 25 15 21 （2） 15 47 25 84 21 （3） 15 21 25 84 47 （4） 15 21 25 47 84 ，则采用的排序是 ( )。
A. 选择 B. 冒泡 C. 快速 D. 插入
9. 对序列{15，9，7，8，20，-1，4}进行排序，进行一趟后数据的排列变为{4，9，-1，8，20，7，15}；则采用的是（ ）排序。
A. 选择 B. 快速 C. 希尔 D. 冒泡
10. 对序列{15，9，7，8，20，-1，4}进行排序，进行一趟后数据的排列变为{9，15，7，8，20，-1，4}，则采用的是（ ）排序。
A ．选择 B. 堆 C. 直接插入 D. 冒泡
11. 下列排序算法中( )不能保证每趟排序至少能将一个元素放到其最终的位置上。
A. 快速排序 B. shell排序 C. 堆排序 D.冒泡排序
12. 下列序列中，（ ）是执行第一趟快速排序后所得的序列。
A. [68，11，18，69] [23，93，73]
B. [68，11，69，23] [18，93，73]
C. [93，73] [68，11，69，23，18]
D. [68，11，69，23，18] [93，73]
13. 有一组数据（15，9，7，8，20，-1，7，4） 用快速排序的划分方法进行一趟划分后数据的排序为 ( )（按递增序）。
A ．下面的B ，C ，D 都不对。 B．9，7，8，4，-1，7，15，20
C ．20，15，8，9，7，-1，4，7 D. 9，4，7，8，7，-1，15，20
14. 在下面的排序方法中，辅助空间为O （n ）的是( ) 。
A．希尔排序 B. 堆排序 C. 选择排序 D. 归并排序
15. 下列排序算法中，在待排序数据已有序时，花费时间反而最多的是( )排序。
A． 冒泡 B. 希尔 C. 快速 D. 堆
16. 对初始状态为递增序列的表按递增顺序排序，最省时间的是（ ）算法，最费时间的
是（ ）算法。
A. 堆排序 B. 快速排序 C. 插入排序 D. 归并排序
17. 就平均性能而言，目前最好的内排序方法是( )排序法。
A. 冒泡 B. 希尔插入 C. 交换 D. 快速
18. 如果只想得到1000个元素组成的序列中第5个最小元素之前的部分排序的序列，用
（ ）方法最快。
A ．起泡排序 B．快速排列 C．Shell 排序 D．堆排序 E．简单选择排序
19. 从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在
已排序序列的合适位置，该排序方法称为( )排序法。
A. 插入 B. 选择 C. 希尔 D. 二路归并
20. 在排序算法中，每次从未排序的记录中挑出最大关键码字的记录，加入到已排序记录的
末尾，该排序方法是（ ）。
A. 选择 B. 冒泡 C. 插入 D. 堆
21. 用直接插入排序方法对下面四个序列进行排序（由小到大），元素比较次数最少的是
（ ）。
A ． 94,32,40,90,80,46,21,69 B． 32,40,21,46,69,94,90,80
C ． 21,32,46,40,80,69,90,94 D． 90,69,80,46,21,32,94,40
22. 直接插入排序在最好情况下的时间复杂度为（ ）
2 A． O(logn) B． O(n) C． O(n*logn) D． O(n)
23. 对序列{15，9，7，8，20，-1，4，} 用希尔排序方法排序，经一趟后序列变为{15，-l ，
4，8，20，9，7}则该次采用的增量是 ( )
A. l B. 4 C. 3 D. 2
24. 对关键码序列28，16，32，12，60，2，5，72快速排序，从小到大一次划分结果为（ ）。
A. (2,5,12,16)26(60,32,72) B. (5,16,2,12)28(60,32,72)
C. (2,16,12,5)28(60,32,72) D. (5,16,2,12)28(32,60,72)
25. 在对n 个元素的序列进行排序时，堆排序所需要的附加存储空间是（ ）。
A. O(log2n) B. O(1) C. O(n) D. O(nlog2n)
二、综合应用题
1、判断下列序列是否是堆（可以是小堆，也可以是大堆，若不是堆，请将它们调整为堆）。
（1）100，85，98，77，80，60，82，40，20，10，66
（2）100，98，85，82，80，77，66，60，40，20，10
（3）100，85，40，77，80，60，66，98，82，10，20
（4）10，20，40，60，66，77，80， 82，85，98，100
2、给出一组关键字：29，18，25，47，58，22，51，10，分别写出按下列各种排序方法进行排序时的变化过程：
(1) 归并排序 每归并一次书写一个次序。
(2) 快速排序 每划分一次书写一个次序。
(3) 堆排序 先建成一个堆，然后每从堆顶取下一个元素后，将堆调整一次。
第1章 绪论
一、选择题
1.B 2.C 3.1C 3.2B 4.B 5.D 6.B 7.C 8.D 9..A 10.C
第2章 线性表
一、选择题
1.A 2.B 3.C 4.A 5.D 6.D 7.D 8.B 9.B,C 10.C
11.C 12.C 13.A 14.B 15.B
第3章 栈和队列
一、选择题
1.B 2.B 3.D 4.B 5.B 6.C 7.D 8.B 9.D 10.C
11.A 12.C 13.B 14.1B 14.2A 14.3C 14.4C 14.5F 15.C 16.C 17.A
第4章 树和二叉树
一、选择题
1.D 2.D 3.A 4.B 5.D 6.B 7.C 8.D 9.C 10.B
11.C 12.C 13.B 14.D 15.A 16.C 17.C 18.D 19.C 20.B
21.D 22.B 23.A 24.B 25.C 26.B 27.D 28.A 29.D 30.C
31.D 32.B 33.C 34.A 35.C 36.C 37.B 38.B
39.D 40.1C 40.2D 40.3F 40.4H 40.5I
第5章 图
一、选择题
1.A 2.B 3.A 4.D 5.1B 5.2D 6.1B 6.2C 7.A 8.B
11.D 12.A,B 13.B 14.A 15.A 16.A 17.B 18.D 19.A 20.C
21.B
第6章 查找
一、选择题
1.C 2.D 3.C 4.D 5.B 6.1C 6.2C 7.1B
7.2A 8.C 9.D 10.1A 10.2C 11.B 12.D 13.D
14.D 15.C
二、综合应用题
1. 评价哈希函数优劣的因素有：能否将关键字均匀影射到哈希空间上，有无好的解决9.B 10.C
冲突的方法，计算哈希函数是否简单高效。由于哈希函数是压缩映像，冲突难以避免。解决冲突的方法：
① 开放定址法 形成地址序列的公式是：H i =（H （key ）+di ）% m ，其中m 是表长，d i 是增量。根据d i 取法不同，又分为三种：
a ．d i =1，2，„，m-1 称为线性探测再散列，其特点是逐个探测表空间，只要散列表中有空闲空间，就可解决碰撞，缺点是容易造成“聚集”，即不是同义词的关键字争夺同一散列地址。
b ．d 222，-22，„ ， k 2
i =1，-1，2（k ≤m/2） 称为二次探测再散列，它减少
了聚集，但不容易探测到全部表空间，只有当表长为形如4j+3（j 为整数）的素数时才有可能。
c ．d i =伪随机数序列，称为随机探测再散列。
② 再散列法 Hi=RHi（key ） i=1，2，„，k ，是不同的散列函数，即在同义词产生碰撞时，用另一散列函数计算散列地址，直到解决碰撞。该方法不易产生“聚集”，但增加了计算时间。
③ 链地址法 将关键字为同义词的记录存储在同一链表中，散列表地址区间用H[0..m-1]表示，分量初始值为空指针。凡散列地址为i （0≤i ≤m-1）的记录均插在以H[i]为头指针的链表中。这种解决方法中数据元素个数不受表长限制，插入和删除操作方便，但增加了指针的空间开销。这种散列表常称为开散列表，而①中的散列表称闭散列表，含义是元素个数受表长限制。
2. 不一定相邻。哈希地址为i （0≤i ≤m-1）的关键字，和为解决冲突形成的探测序列
i 的同义词，都争夺哈希地址i 。
平均查找长度：ASL succ =（1+1+1+2+3+4+1+2）/8=15/8
以关键字27为例：H （27）=27%7=6（冲突） H1=（6+1）%10=7（冲突） H （6+22）%10=0（冲突） H3
2=3=（6+3）%10=5 所以比较了4次。
4. 按中序遍历序列将值1~9依次标上
6. 序列（2）不可能是二叉排序树中查到363的序列。查到501后，因363
应出现小于501的数，但序列中出现了623，故不可能
7. 37/12
第7章 排序
一、选择题
1.D 2.D 3.C
4.A 5.C,D 6.B,D 7.A 8.A 9.C 10.C 11.B
12.C 13.A 14.D 15.C 16.1C 16.2B 17.D 18.D 19.A
21.C 22.B 23.B 24.B 25.B
二、综合应用题
1. (1)是大堆； (2)是大堆；（4）是小堆；
(3)不是堆，调成大堆 100，98，66，85，80，60，40，77，82，10，20
20.A
第1章 绪论
一、选择题
1. 算法的计算量的大小称为计算的（ B ）。
A ．效率 B. 复杂性 C. 现实性 D. 难度
2. 算法的时间复杂度取决于（C ）
A ．问题的规模 B. 待处理数据的初态 C. A和B
3. 计算机算法指的是（1），它必须具备（2） 这三个特性。
(1) A．计算方法 B. 排序方法 C. 解决问题的步骤序列 D. 调度方法
(2) A．可执行性、可移植性、可扩充性 B. 可执行性、确定性、有穷性
C. 确定性、有穷性、稳定性 D. 易读性、稳定性、安全性
4. 一个算法应该是（ C ）。
A．程序 B．问题求解步骤的描述
C ．数据结构+程序 D．以上都不对.
5. 下面关于算法说法错误的是（ ）
A ．算法最终必须由计算机程序实现
B. 为解决某问题的算法同为该问题编写的程序含义是相同的
C. 算法的可行性是指指令不能有二义性 D. 以上几个都是错误的
6. 下面说法错误的是（ ）
(1）算法原地工作的含义是指不需要任何额外的辅助空间
n （2）在相同的规模n 下，复杂度O(n)的算法在时间上总是优于复杂度O(2) 的算法
（3）所谓时间复杂度是指随问题规模的增大，算法执行时间的增长率。
（4）空间复杂度是算法所需存储空间的量度。
A．(1) B.(1),(2) C.(1),(4) D.(3)
7. 从逻辑上可以把数据结构分为（ ）两大类。
A ．动态结构、静态结构 B．顺序结构、链式结构
C ．线性结构、非线性结构 D．初等结构、构造型结构
8. 以下与数据的存储结构无关的术语是（ ）。
A ．循环队列 B. 链表 C. 哈希表 D. 栈
9. 连续存储设计时，存储单元的地址（ ）。
A ．一定连续 B．一定不连续 C．不一定连续 D．部分连续，部分不连续
10. 以下属于逻辑结构的是（ ）。
A ．顺序表 B. 哈希表 C.有序表 D. 单链表
第2章 线性表
一、选择题
1. 下述哪一条是顺序存储结构的优点？（D ）
A ．存储密度大 B．插入运算方便 C．删除运算方便 D．可方便地用于各种逻辑结构的存储表示
2. 下面关于线性表的叙述中，错误的是哪一个？（B ）
A ．线性表采用顺序存储，必须占用一片连续的存储单元。
B ．线性表采用顺序存储，便于进行插入和删除操作。
C ．线性表采用链接存储，不必占用一片连续的存储单元。
D ．线性表采用链接存储，便于插入和删除操作。
3. 线性表是具有n 个（C ）的有限序列（n>0）。
A ．表元素 B．字符 C．数据元素 D．数据项 E．信息项
4. 若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（A ）存储方式最节省时间。
A ．顺序表 B．双链表 C．带头结点的双循环链表 D．单循环链表
5. 某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（A ）存储方式最节省运算时间。
A ．单链表 B．仅有头指针的单循环链表 C．双链表 D．仅有尾指针的单循环链表
6. 设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用( )最节省时间。
A. 单链表 B.单循环链表 C. 带尾指针的单循环链表 D.带头结点的双循环链表
7. 若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点。则采用（ ）存储方式最节省运算时间。
A ．单链表 B．双链表 C．单循环链表 D．带头结点的双循环链表
8. 链表不具有的特点是（ ）
A ．插入、删除不需要移动元素 B．可随机访问任一元素
C．不必事先估计存储空间 D．所需空间与线性长度成正比
9. 下面的叙述不正确的是（ ）
A ．线性表在链式存储时，查找第i 个元素的时间同i 的值成正比
B. 线性表在链式存储时，查找第i 个元素的时间同i 的值无关
C. 线性表在顺序存储时，查找第i 个元素的时间同i 的值成正比
D. 线性表在顺序存储时，查找第i 个元素的时间同i 的值无关
10. 若长度为n 的线性表采用顺序存储结构，在其第i 个位置插入一个新元素的算法的时间复杂度为（ ）(1
2A. O(0) B. O(1) C. O(n) D. O(n)
11. 对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为（ ）。
A ．O(n) O(n) B. O(n) O(1) C. O(1) O(n) D. O(1) O(1)
12. 线性表（ a1,a2,„,an ）以链接方式存储时，访问第i 位置元素的时间复杂性为（ ）
A ．O （i ） B．O （1） C．O （n ） D．O （i-1）
13. 非空的循环单链表head 的尾结点p 满足（ ）。
A ．p.next=head B．p.next=NULL C．p=NULL D．p= head
14. 在单链表指针为p 的结点之后插入指针为s 的结点，正确的操作是：（ ）。
A ．p->next=s;s->next=p->next; B． s->next=p->next;p->next=s;
C ．p->next=s;p->next=s->next; D． p->next=s->next;p->next=s;
15. 对于一个头指针为head 的带头结点的单链表，判定该表为空表的条件是（ ）
A ．head==NULL B．head->next==NULL
C ．head->next==head D．head!=NULL
二、综合应用题
1. 已知线性表（a1 a2 a3 „an ）按顺序存于内存，每个元素都是整数，试设计用最少时
间把所有值为负数的元素移到全部正数值元素前边的算法：例：（x,-x,-x,x,x,-x „x ）变为（-x,-x,-x „x,x,x ）。
2. 设单链表的表头指针为h ，结点结构由data 和next 两个域构成，其中data 域为字符
型。写出算法dc(h,n),判断该链表的前n 个字符是否中心对称。例如 xyx, xyyx都是中心对称。
3. 已知非空线性链表由list 指出，链结点的构造为（data,link ）. 请写一算法，将链表
中数据域值最小的那个链结点移到链表的最前面。要求：不得额外申请新的链结点。
4. 试编写在带头结点的单链表中删除（一个）最小值结点的（高效）算法。
void delete（Linklist &L）
5. 设有一头指针为L 的带有表头结点的非循环双向链表，其每个结点中除有pred （前驱
指针），data （数据）和next （后继指针）域外，还有一个访问频度域freq 。在链表被起用前，其值均初始化为零。每当在链表中进行一次Locate(L,x)运算时，令元素值为x 的结点中freq 域的值增1，并使此链表中结点保持按访问频度非增（递减）的顺序排列，同时最近访问的结点排在频度相同的结点的最后，以便使频繁访问的结点总是靠近表头。试编写符合上述要求的Locate(L,x)运算的算法，该运算为函数过程，返回找到结点的地址，类型为指针型。
6. 已知长度为n 的线性表A 采用顺序存储结构，请写一时间复杂度为0(n)、空间复杂度
为0(1)的算法，该算法删除线性表中所有值为item 的数据元素。（O （1）表示算法的辅助空间为常量）。
第3章 栈和队列
一、选择题
1. 对于栈操作数据的原则是（ ）。
A. 先进先出 B. 后进先出 C. 后进后出 D. 不分顺序
2. 一个栈的输入序列为123„n ，若输出序列的第一个元素是n ，输出第i （1
A. 不确定 B. n-i+1 C. i D. n-i
3. 若一个栈的输入序列为1,2,3, „,n ，输出序列的第一个元素是i ，则第j 个输出元素是（ ）。
A. i-j-1 B. i-j C. j-i+1 D. 不确定的
4. 一个栈的输入序列为1 2 3 4 5，则下列序列中不可能是栈的输出序列的是（ ）。
A. 2 3 4 1 5 B. 5 4 1 3 2
C. 2 3 1 4 5 D. 1 5 4 3 2
5. 输入序列为ABC ，可以变为CBA 时，经过的栈操作为（ ）
A. push,pop,push,pop,push,pop
B. push,push,push,pop,pop,pop
C. push,push,pop,pop,push,pop
D. push,pop,push,push,pop,pop
6. 若一个栈以向量V[1..n]存储，栈为空时栈顶指针top 为n+1，则下面x 进栈的正确操作是( )。
A ．top:=top+1; V [top]:=x
B. V [top]:=x; top:=top+1
C. top:=top-1; V [top]:=x
D. V [top]:=x; top:=top-1
7. 栈在（ ）中应用。
A. 递归调用 B. 子程序调用 C. 表达式求值 D. A，Ｂ，Ｃ
8. 一个递归算法必须包括（ ）。
A. 递归部分 B. 终止条件和递归部分 C. 迭代部分 D.终止条件和迭代部分
9. 用不带头结点的单链表存储队列时, 其队头指针指向队头结点, 其队尾指针指向队尾结点，则在进行删除操作时( )。
A ．仅修改队头指针 B. 仅修改队尾指针
C. 队头、队尾指针都要修改 D. 队头, 队尾指针都可能要修改
10. 递归过程或函数调用时，处理参数及返回地址，要用一种称为（ ）的数据结构。
A ．队列 B．多维数组 C．栈 D. 线性表
11. 假设以数组A[m]存放循环队列的元素, 其头尾指针分别为front 和rear ，则当前队列中的元素个数为（ ）。
A ．(rear-front+m)%m B．rear-front+1 C．(front-rear+m)%m D．(rear-front)%m
12. 循环队列存储在数组A[0..m]中，则入队时的操作为（ ）。
A. rear=rear+1 B. rear=(rear+1) mod (m-1)
C. rear=(rear+1) mod m D. rear=(rear+1)mod(m+1)
13. 若用一个大小为6的数组来实现循环队列，且当前rear 和front 的值分别为0和3，
当从队列中删除一个元素，再加入两个元素后，rear 和front 的值分别为多少？( )
A. 1和 5 B. 2和4 C. 4和2 D. 5和1
14. 栈的特点是（ ① ）, 队列的特点是（ ② ）, 栈和队列都是（ ③ ）。若进栈序
列为1,2,3,4 则（ ④ ）不可能是一个出栈序列（不一定全部进栈后再出栈）；若进队列的序列为1,2,3,4 则（ ⑤ ）是一个出队列序列。
①, ②: A. 先进先出 B. 后进先出 C. 进优于出 D. 出优于进 ③: A.顺序存储的线性结构 B.链式存储的线性结构
C. 限制存取点的线性结构 D.限制存取点的非线性结构
④, ⑤: A. 3,2,1,4 B. 3,2,4,1 C. 4,2,3,1 D. 4,3,2,1 F. 1,2,3,4 G. 1,3,2,4
15. 栈和队列的共同点是（ ）。
A. 都是先进先出 B. 都是先进后出
C. 只允许在端点处插入和删除元素 D. 没有共同点
16. 设栈S 和队列Q 的初始状态为空，元素e1，e2，e3，e4,e5和e6依次通过栈S ，一个
元素出栈后即进队列Q ，若6个元素出队的序列是e2，e4，e3,e6,e5,e1则栈S 的容量至少应该是( )。
A ． 6 B. 4 C. 3 D. 2
17. 用单链表表示的链式队列的队头在链表的（ ）位置。
A ．链头 B．链尾 C．链中
二、综合应用题
1. 有5 个元素，其入栈次序为：A ，B ，C ，D ，E ，在各种可能的出栈次序中，以元素C ，D
最先出栈（即C 第一个且D 第二个出栈）的次序有哪几个？
2. 设从键盘输入一整数的序列：a1, a2, a3，„，an, 试编写算法实现：用栈结构存储输
入的整数，当ai ≠-1时，将ai 进栈；当ai=-1时，输出栈顶整数并出栈。算法应对异常情况（栈空等）给出相应的信息。
3. 设表达式以字符形式已存入数组E[n]中，‘#’为表达式的结束符，试写出判断表达式
中括号（‘（’和‘）’）是否配对的C 语言描述算法; (注：算法中可调用栈操作的基本算法。)
第4章 树和二叉树
一、选择题
1. 设树T 的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1 则T 中的叶子数为（ ）
A ．5 B．6 C．7 D．8
2. 在下述结论中，正确的是（ ）
①只有一个结点的二叉树的度为0; ②二叉树的度为2； ③二叉树的左右子树可任意交换;
④深度为K 的完全二叉树的结点个数小于或等于深度相同的满二叉树。
A ．①②③ B．②③④ C．②④ D．①④
3. 设森林F 对应的二叉树为B ，它有m 个结点，B 的根为p,p 的右子树结点个数为n, 森林F 中第一棵树的结点个数是（ ）
A ．m-n B．m-n-1 C．n+1 D．条件不足，无法确定
4. 若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（ ）
A ．9 B．11 C．15 D．不确定
5. 设森林F 中有三棵树，第一，第二，第三棵树的结点个数分别为M1，M2和M3。与森林F 对应的二叉树根结点的右子树上的结点个数是（ ）。
A ．M1 B．M1+M2 C．M3 D．M2+M3
6. 具有10个叶结点的二叉树中有（ ）个度为2的结点，
A ．8 B．9 C．10 D．ll
7. 若一棵二叉树有126个节点，在第7层（根节点在第1层）至多有（ ）个节点。
A ． 32 B． 64 C．63 D．不存在第7层
8. 设给定权值总数有n 个，其哈夫曼树的结点总数为( )
A ．不确定 B．2n C．2n+1 D．2n-1
9. 下列关于哈夫曼树的 说法中最准确的是（ ）。
A ．最优树 B．叶子节点带有权值的二叉树 C.最优二叉树 D．叶子节点带有权值的树
10. 有关二叉树下列说法正确的是（ ）
A ．二叉树的度为2 B．一棵二叉树的度可以小于2
C ．二叉树中至少有一个结点的度为2 D．二叉树中任何一个结点的度都为2
11. 二叉树的第I 层上最多含有结点数为（ ）
I I-1I-1I A ．2 B． 2-1 C． 2 D．2 -1
12. 一个具有1025个结点的二叉树的高h 为（ ）
A ．11 B．10 C．11至1025之间 D．10至1024之间
13. 一棵二叉树高度为h, 所有结点的度或为0，或为2，则这棵二叉树最少有( )结点
A ．2h B．2h-1 C．2h+1 D．h+1
14. 对于有n 个结点的二叉树, 其高度为（ ）
A ．nlog 2n B．log 2n C．⎣log 2n ⎦+1 D．不确定
15. 一棵具有 n个结点的完全二叉树的树高度（深度）是（ ）
A ．⎣log 2n ⎦+1 B．log 2n+1 C．⎣log 2n ⎦ D．log 2n-1
16. 高度为 K的二叉树最大的结点数为（ ）。
A ．2 B．2 C．2 -1 D．2-1 k k-1k k-1
17. 一棵高为K 的完全二叉树至少有（ ）个结点
k k-1k-1k A ．2 –1 B. 2 –1 C. 2 D. 2
18. 对于先序遍历和中序遍历结果相同的二叉树是（ ）。
A ． 无左子树的二叉树 B．无右子树的二叉树 C．所有节点只有左子树的二叉树 D．所有节点只有右子树的二叉树
19. 对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，
同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采用( )次序的遍历实现编号。
A ．先序 B. 中序 C. 后序 D. 从根开始按层次遍历
20. 树的后根遍历序列等同于该树对应的二叉树的( ).
A. 先序序列 B. 中序序列 C. 后序序列
21. 在下列存储形式中，哪一个不是树的存储形式？（ ）
A ．双亲表示法 B．孩子链表表示法 C．孩子兄弟表示法 D．顺序存储表示法
22. 一棵二叉树的前序遍历序列为ABCDEFG ，它的中序遍历序列可能是（ ）
A ．CABDEFG B．ABCDEFG C．DACEFBG D．ADCFEG
23. 已知一棵二叉树的前序遍历结果为ABCDEF, 中序遍历结果为CBAEDF, 则后序遍历的结果
为（ ）。
A ．CBEFDA B． FEDCBA C． CBEDFA D．不定
24. 某二叉树中序序列为A,B,C,D,E,F,G ，后序序列为B,D,C,A,F,G,E 则前序序列是
（ ）。
A ．E,G,F,A,C,D,B B．E,A,C,B,D,G,F C．E,A,G,C,F,B,D D．上面的都不对
25. 二叉树的先序遍历和中序遍历如下： 先序遍历：EFHIGJK ；中序遍历: HFIEJKG 。该二
叉树根的右子树的根是（ ）。
A 、 E B、 F C、 G D、 H
26. 某二叉树T 有n 个结点，设按某种顺序对T 中的每个结点进行编号，编号为1，2，„ ，
n ，且有如下性质：T 中任一结点V ，其编号等于左子树上的最小编号减1，而V 的右子树的结点中，其最小编号等于V 左子树上结点的最大编号加1。这时是按( )编号的。
A. 中序遍历序列 B.前序遍历序列 C.后序遍历序列 D.层次顺序
27. 一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足
（ ）。
A ．完全二叉树 B．只有两个结点的二叉树 C. 二叉排序树 D. 任一节点只有一个孩子结点
28. 任何一颗二叉树的叶子结点在先序序列，中序序列和后序序列中的相对次序（ ）。
A ．不 发生改变 B ．发生改变 C．不能确定 D ．以上都不对
29. 若对二叉树进行中序遍历，具有左、右子树的结点，其后继是该结点的（ ）。
A ． 双亲结点 B．其左子树中最右下角元素 C．其右孩子 D．其右子树中最左下角元素
30. 在完全二叉树中，若一个结点是叶结点，则它没（ ）。
A．左子结点 B．右子结点 C．左子结点和右子结点 D．左子结点，右子结点和兄弟结点
31. 一棵左子树为空的二叉树在先序线索化后，其中空的链域的个数是：( )。
A ．不确定 B. 0 C. 1 D. 2
32. 一棵左右子树均不空的二叉树在先序线索化后，其中空的链域的个数是：( )。
A. 0 B. 1 C. 2 D. 不确定
33. 若X 是二叉中序线索树中一个有左孩子的结点，且X 不为根，则x 的前驱为( ) 。
A. X的双亲 B. X的右子树中最左的结点 C. X的左子树中最右结点 D. X的左子树中最右叶结点
34. 引入线索二叉树的目的是（ ）
A ．加快查找结点的前驱或后继的速度 B．为了能在二叉树中方便的进行插入与删除
C ．为了能方便的找到双亲 D．使二叉树的遍历结果唯一
35. n 个结点的线索二叉树上含有的线索数为（ ）
A ．2n B．n －l C．n ＋l D．n
36. 设F 是一个森林，B 是由F 变换得的二叉树。若F 中有n 个非终端结点，则B 中右指针
域为空的结点有（ ）个。
A ． n-1 B．n C． n+1 D． n+2
37. 在叶子数目和权值相同的所有二叉树中，最优二叉树一定是完全二叉树，该说法（ ）。
A．正确 B．错误
38. 下述编码中哪一个不是前缀码（ ）。
A ．（00，01，10，11） B．（0，1，00，11） C．（0，10，110，111） D．（1，01，000，001）
39. 一棵有n 个结点的二叉树，按层次从上到下，同一层从左到右顺序存储在一维数组
A[1..n]中，则二叉树中第i 个结点（i 从1开始用上述方法编号）的右孩子在数组A 中的位置是（ ）
A ．A[2i](2i
40. 从下列有关树的叙述中, 选出5条正确的叙述（ ）。
A ．二叉树中每个结点有两个子结点, 而树无此限制, 因此二叉树是树的特殊情况。
k-1B ．当K ≥1时高度为K 的二叉树至多有2个结点。
C ．用树的前序遍历和中序遍历可以导出树的后序遍历。
D ．线索二叉树的优点是便于查找某结点的前驱结点和后继结点。
E ．将一棵树转换成二叉树后, 根结点没有左子树。
F ．一棵含有N 个结点的完全二叉树, 它的高度是⎣LOG 2N ⎦+1。
G ．在二叉树中插入结点, 该二叉树便不再是二叉树。
H ．采用二叉树链表作树的存储结构, 树的前序遍历和其相应的二叉树的前序遍历的结果是一样的。
I ．哈夫曼树是带权路径最短的树, 路径上权值较大的结点离根较近。
J ．用一维数组存储二叉树时, 总是以前序遍历存储结点。
二、综合应用题
1、 一棵高度为 5 的二叉树中最少含有 _________ 个结点，最多含有 ________ 个结点。
2、 具有65个结点的完全二叉树的高度为_________。（根的层次号为1）.
3、 假设一棵二叉树的前序序列为 EBADCFHGIKJ 和中序序列为 ABCDEFGHIJK 。请画出
该树。
4、 已知一棵完全二叉树中共有768结点，则该树中共有______个叶子结点。
5、 有n 个结点并且其高度为n 的二叉树的数目是多少?
6、 试找出分别满足下列条件的所有二叉树。
1）先序序列和中序序列相同 2）中序序列和后序序列相同
3）先序序列和后序序列相同
7、 设A 、B 、C 、D 、E 、F 六个字母出现的概率分别为7,19,2,6,32,3。试写出为这六个字母
设计的HUFFMAN 编码，并求出对应HUFFMAN 树的带权路径长度。
8、 已知一棵树的先序序列和后序序列如下，请构造出该树。
先序序列：ABCDEFGHIJ
后序序列：CDEBFHIJGA
9、 一棵二叉树的先序、中序和后序序列分别如下，其中有一部分为显示出来。试求出空格
处的内容，并画出该二叉树。
先序序列: _ B F I C E H G
中序序列：D K F I A E J C
后序序列： K F B H J G A
10、 如在内存中存放一个完全二叉树，在树上只进行下面两个操作：
（1）寻找某个结点双亲 （2）寻找某个结点的儿子；
请问应该用何种结构来存储该二叉树？
11、 将二叉树bt 中每一个结点的左右子树互换。请分别用递归和非递归算法实现。
12、 二叉树采用二叉链表存储，编写计算二叉树最大宽度的算法（二叉树的最大宽度是
指二叉树所有层中结点个数的最大值）。 13、 试写出一递归函数，判别两棵树是否相等 14、 请设计一个算法，要求该算法把二叉树的叶子结点按从左到右的顺序连成一个单链
表，表头指针为head 。 二叉树按二叉链表方式存储，链接时用叶子结点的右指针域来存放单链表指针。
15、 下面是求二叉树高度的类C 写的递归算法，试补充完整
[说明]二叉树的两指针域为lchild 与rchild, 算法中p 为二叉树的根，lh 和rh 分别为以p 为根的二叉树的左子树和右子树的高，hi 为以p 为根的二叉树的高，hi 最后返回。
height(p)
{if ((1)___)
{if(p->lchild==null) lh=(2)_______; else lh=(3)_______;
if(p->rchild==null) rh=(4)_______; else rh=(5)_______;
if (lh>rh) hi=(6)__；else hi=(7)_______;
}
else hi=(8)_______;
return hi;
}
16、 将下列由三棵树组成的森林转换为二叉树。
17、 设T 是一棵给定的查找树, 试编写一个在树中删除根结点为a 的子树的程序, 要求
在删除的过程中释放该子树所有结点所占有的存储空间, 这里假设树T 中结点所占有的存储空间是通过动态存储分配取得的, 其结点的形式为:（lchild,data,rchild ）
18、 试编写算法，对一棵以孩子—兄弟链表表示的树统计叶子的个数。
第5章 图
一、选择题
1. 图中有关路径的定义是（ ）。
A ．由顶点和相邻顶点序偶构成的边所形成的序列 B．由不同顶点所形成的序列
C ．由不同边所形成的序列 D．上述定义都不是
2. 设无向图的顶点个数为n ，则该图最多有（ ）条边。
A ．n-1 B．n(n-1)/2
2C ． n(n+1)/2 D．0 E．n
3. 一个n 个顶点的连通无向图，其边的个数至少为（ ）。
A ．n-1 B．n C．n+1 D．nlogn ；
4. n 个结点的完全有向图含有边的数目（ ）。
A ．n*n Ｂ．n （n ＋１） C．n ／2 D．n*（n －l ）
5. 一个有n 个结点的图，最少有（ ）个连通分量，最多有（ ）个连通分量。
A ．0 B．1 C．n-1 D．n
6. 在一个无向图中，所有顶点的度数之和等于所有边数（ ）倍，在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的（ ）倍。
A ．1/2 B．2 C．1 D．4
7. 用DFS 遍历一个无环有向图，并在DFS 算法退栈返回时打印相应的顶点，则输出的顶点序列是( )。
A ．逆拓扑有序 B．拓扑有序 C．无序的
8. 无向图G 是 一个连通图，有9条边，则该图至少有（ ）个顶点。
A ．4 B．5 C．6 D．7
9. 下列哪一种图的邻接矩阵是对称矩阵？（ ）
A ．有向图 B．无向图 C．AOV 网 D．AOE 网
10. 下列说法不正确的是（ ）。
A ．图的遍历是从给定的源点出发每一个顶点仅被访问一次
B ．遍历的基本算法有两种：深度遍历和广度遍历
C ．图的深度遍历不适用于有向图
D ．图的深度遍历是一个递归过程
11. 无向图G=(V,E),其中：V={a,b,c,d,e,f}, E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)}，对该图进行深度优先遍历，得到的顶点序列正确的是（ ）。
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
12. 下面哪些方法可以判断出一个有向图是否有环（回路）： （ ）
A ．深度优先遍历 B. 拓扑排序 C. 求最短路径 D. 求关键路径
13. 在图采用邻接表存储时，求最小生成树的 Prim 算法的时间复杂度为( )。
23A. O(n) B. O(n+e) C. O(n) D. O(n)
14. 当各边上的权值( )时，广度优先遍历算法可用来解决单源最短路径问题。
A ．均相等 B．均互不相等 C．不一定相等
15. 已知有向图G=(V,E)，其中V={V1,V2,V3,V4,V5,V6,V7}，E={,,,,,,,,},G 的拓扑序列是（ ）。
A ．V 1,V 3,V 4,V 6,V 2,V 5,V 7 B．V 1,V 3,V 2,V 6,V 4,V 5,V 7
C ．V 1,V 3,V 4,V 5,V 2,V 6,V 7 D．V 1,V 2,V 5,V 3,V 4,V 6,V 7
16. 若一个有向图的邻接距阵中, 主对角线以下的元素均为零, 则该图的拓扑有序序列
（ ）。
A ．存在 B．不存在
17. 一个有向无环图的拓扑排序序列（ ）是唯一的。
A ．一定 B．不一定
18. 在有向图G 的拓扑序列中，若顶点Vi 在顶点Vj 之前，则下列情形不可能出现的是
（ ）。
A ．G 中有弧 B ．G 中有一条从Vi 到Vj 的路径
C ．G 中没有弧 D．G 中有一条从Vj 到Vi 的路径
19. 关键路径是事件结点网络中（ ）。
A ．从源点到汇点的最长路径 B．从源点到汇点的最短路径
C ．最长回路 D．最短回路
20. 下面关于求关键路径的说法不正确的是（ ）。
A ．求关键路径是以拓扑排序为基础的
B ．一个事件的最早开始时间与以该事件为尾的弧的活动最早开始时间相同
C ．一个事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间与该活动的持续时间的差
D ．关键活动一定位于关键路径上
21. 下列关于AOE 网的叙述中，不正确的是（ ）。
A ．关键活动不按期完成就会影响整个工程的完成时间
B ．任何一个关键活动提前完成，那么整个工程将会提前完成
C ．所有的关键活动提前完成，那么整个工程将会提前完成
D ．某些关键活动提前完成，那么整个工程将会提前完成
二、综合应用题
1. 请计算下图中的强连通分量的个数
2. 考虑下图：
（1）．画出G 的邻接表表示图；
（2）．根据你画出的邻接表，以顶点①为根，
画出G 的深度优先生成树和广度优先生成树。
3. 在什么情况下，Prim 算法与Kruskual 算法生成不同的MST ？
在有相同权值边时生成不同的MST ，在这种情况下，用Prim 或Kruskal 也会生成不
同的MST 。
4. 考虑下图：根据普利姆(Prim) 和Kruskal 算法分别求它的最小生成树。
5. 已知一图如下图所示：
（1）．写出该图的邻接矩阵；
（2）．写出全部拓扑排序；
（3）．以v1为源点, 以v8为终点，给出所有事件允许发生的最早时间和最晚时间，并给出关键路径；
（4）．求V1结点到各点的最短距离。
第6章 查找
一、选择题
1. 若查找每个记录的概率均等，则在具有n 个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL 为( )。
A ． (n-1)/2 B. n/2 C. (n+1)/2 D. n
2. 下面关于二分查找的叙述正确的是 ( )
A. 表必须有序，表可以顺序方式存储，也可以链表方式存储
B. 表必须有序且表中数据必须是整型，实型或字符型
C. 表必须有序，而且只能从小到大排列
D. 表必须有序，且表只能以顺序方式存储
3. 当在一个有序的顺序存储表上查找一个数据时，即可用折半查找，也可用顺序查找，但前者比后者的查找速度( ) 。
A ．必定快 B.不一定 C. 在大部分情况下要快 D. 取决于表递增还是递减
4. 折半查找的时间复杂性为（ ）
2A. O（n ） B. O（n ） C. O（nlogn ） D. O（logn ）
5. 当采用分块查找时，数据的组织方式为 ( )。
A ．数据分成若干块，每块内数据有序
B ．数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大（或最小）的数据组成索引块
C. 数据分成若干块，每块内数据有序，每块内最大（或最小）的数据组成索引块
D. 数据分成若干块，每块（除最后一块外）中数据个数需相同
6. 二叉排序树的查找效率与二叉树的( （1）) 有关, 在 (（2）) 时其查找效率最低
(1): A. 高度 B. 结点的多少 C. 树型 D. 结点的位置
(2): A. 结点太多 B. 完全二叉树 C. 呈单枝树 D. 结点太复杂。
7. 对大小均为n 的有序表和无序表分别进行顺序查找, 在等概率查找的情况下, 对于查找失败, 它们的平均查找长度是((1)) ,对于查找成功, 他们的平均查找长度是((2))供选择的答案:
A. 相同的 B.不同的
8. 分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是( )。
A ．（100，80， 90， 60， 120，110，130）
B. （100，120，110，130，80， 60， 90）
C. （100，60， 80， 90， 120，110，130）
D. (100，80， 60， 90， 120，130，110)
9. 设有一组记录的关键字为{19，14，23，1，68，20，84，27，55，11，10，79}，用链地址法构造散列表，散列函数为H （key ）=key MOD 13,散列地址为1的链中有（ ）个记录。
A ．1 B. 2 C. 3 D. 4
10. 若采用链地址法构造散列表，散列函数为H （key ）=key MOD 17，则需 (（1）) 个链表。这些链的链首指针构成一个指针数组，数组的下标范围为 (（2）)
（1） A．17 B. 13 C. 16 D. 任意
（2） A．0至17 B. 1至17 C. 0至16 D. 1至16
11. 关于哈希查找说法不正确的有几个( )
（1）采用链地址法解决冲突时，查找一个元素的时间是相同的
（2）采用链地址法解决冲突时，若插入规定总是在链首，则插入任一个元素的时间是
相同的
（3）用链地址法解决冲突易引起聚集现象
（4）再哈希法不易产生聚集
A. 1 B. 2 C. 3 D. 4
12. 设哈希表长为14，哈希函数是H(key)=key%11,表中已有数据的关键字为15，38，61，
84共四个，现要将关键字为49的结点加到表中，用二次探测再散列法解决冲突，则放入的位置是( )
A．8 B．3 C．5 D．9
13. 假定有k 个关键字互为同义词，若用线性探测法把这k 个关键字存入散列表中，至少要
进行多少次探测？( )。
A ．k-1次 B. k次 C. k+1次 D. k（k+1）/2次
14. 散列函数有一个共同的性质，即函数值应当以( )取其值域的每个值。
A. 最大概率 B. 最小概率 C. 平均概率 D. 同等概率
15. 将10个元素散列到100000个单元的哈希表中，则（ ）产生冲突。
A. 一定会 B. 一定不会 C. 仍可能会
二、综合应用题
1、如何衡量hash 函数的优劣？简要叙述hash 表技术中的冲突概念，并指出三种解决冲突的方法。
2、在采用线性探测法处理冲突的散列表中，所有同义词在表中是否一定相邻？
3、设有一组关键字{9,01,23,14,55,20,84,27}，采用哈希函数：H （key ）=key mod 7 ，表长为10，用开放地址法的二次探测再散列方法Hi=(H(key)+di) mod 10(di=12,22,32,„,) 解决冲突。要求：对该关键字序列构造哈希表，并计算查找成功的平均查找长度。
4、一棵二叉排序树结构如下, 各结点的值从小到大依次为1-9，请标出各结点的值。
5、依次输入表(30,15,28,20,24,10,12,68,35,50,46,55)中的元素，生成一棵二叉排序树
(1) 试画出生成之后的二叉排序树; (2) 对该二叉排序树作中序遍历，试写出遍历序列;
(3) 假定每个元素的查找概率相等，试计算该二叉排序树的平均查找长度。
6、设二叉排序树中关键字由1到1000的整数组成，现要查找关键字为363的结点，下述关键字序列哪一个不可能是在二叉排序树中查到的序列？说明原因。
（1）51，250，501，390，320，340，382，363 （2）24，877，125，342，501，623，421，363
7、有一个长度为12的有序表，按对半查找法对该表进行查找，在表内各元素等概率情况下，查找成功所需的平均比较次数是多少？
8、假定对有序表：(3,4,5,7,24,30,42,54,63,72,87,95)进行折半查找，试回答下列问题：
(1).画出描述折半查找过程的判定树；
(2).若查找元素54，需依次与那些元素比较?
(3).若查找元素90，需依次与那些元素比较?
(4).假定每个元素的查找概率相等，求查找成功时的平均查找长度。
第7章 排序
一、选择题
1. 某内排序方法的稳定性是指( )。
A ．该排序算法不允许有相同的关键字记录
B ．该排序算法允许有相同的关键字记录
C ．平均时间为0（n log n）的排序方法
D ．以上都不对
2. 下面给出的四种排序法中( )排序法是不稳定性排序法。
A. 插入 B. 冒泡 C. 二路归并 D. 堆排序
3. 若需在O(nlog2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（ ）。
A. 快速排序 B. 堆排序 C. 归并排序 D. 直接插入排序
4. 在希尔排序中，最后一趟排序的增量必须为（ ）。
A ．1 B.3 C. 5 D. 7
5. 排序趟数与序列的原始状态有关的排序方法是( )排序法。
A．插入 B. 选择 C. 冒泡 D. 快速
6. 对下列四种排序方法，在排序中关键字比较次数同记录初始排列无关的是( )。
A ．直接插入 B. 二分法插入
C. 快速排序 D. 归并排序
7. 数据序列（2，1，4，9，8，10，6，20）只能是下列排序算法中的( )的两趟排序后的结果。
A. 快速排序 B. 冒泡排序 C. 选择排序 D. 插入排序
8. 对一组数据（84，47，25，15，21）排序，数据的排列次序在排序的过程中的变化为（1） 84 47 25 15 21 （2） 15 47 25 84 21 （3） 15 21 25 84 47 （4） 15 21 25 47 84 ，则采用的排序是 ( )。
A. 选择 B. 冒泡 C. 快速 D. 插入
9. 对序列{15，9，7，8，20，-1，4}进行排序，进行一趟后数据的排列变为{4，9，-1，8，20，7，15}；则采用的是（ ）排序。
A. 选择 B. 快速 C. 希尔 D. 冒泡
10. 对序列{15，9，7，8，20，-1，4}进行排序，进行一趟后数据的排列变为{9，15，7，8，20，-1，4}，则采用的是（ ）排序。
A ．选择 B. 堆 C. 直接插入 D. 冒泡
11. 下列排序算法中( )不能保证每趟排序至少能将一个元素放到其最终的位置上。
A. 快速排序 B. shell排序 C. 堆排序 D.冒泡排序
12. 下列序列中，（ ）是执行第一趟快速排序后所得的序列。
A. [68，11，18，69] [23，93，73]
B. [68，11，69，23] [18，93，73]
C. [93，73] [68，11，69，23，18]
D. [68，11，69，23，18] [93，73]
13. 有一组数据（15，9，7，8，20，-1，7，4） 用快速排序的划分方法进行一趟划分后数据的排序为 ( )（按递增序）。
A ．下面的B ，C ，D 都不对。 B．9，7，8，4，-1，7，15，20
C ．20，15，8，9，7，-1，4，7 D. 9，4，7，8，7，-1，15，20
14. 在下面的排序方法中，辅助空间为O （n ）的是( ) 。
A．希尔排序 B. 堆排序 C. 选择排序 D. 归并排序
15. 下列排序算法中，在待排序数据已有序时，花费时间反而最多的是( )排序。
A． 冒泡 B. 希尔 C. 快速 D. 堆
16. 对初始状态为递增序列的表按递增顺序排序，最省时间的是（ ）算法，最费时间的
是（ ）算法。
A. 堆排序 B. 快速排序 C. 插入排序 D. 归并排序
17. 就平均性能而言，目前最好的内排序方法是( )排序法。
A. 冒泡 B. 希尔插入 C. 交换 D. 快速
18. 如果只想得到1000个元素组成的序列中第5个最小元素之前的部分排序的序列，用
（ ）方法最快。
A ．起泡排序 B．快速排列 C．Shell 排序 D．堆排序 E．简单选择排序
19. 从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在
已排序序列的合适位置，该排序方法称为( )排序法。
A. 插入 B. 选择 C. 希尔 D. 二路归并
20. 在排序算法中，每次从未排序的记录中挑出最大关键码字的记录，加入到已排序记录的
末尾，该排序方法是（ ）。
A. 选择 B. 冒泡 C. 插入 D. 堆
21. 用直接插入排序方法对下面四个序列进行排序（由小到大），元素比较次数最少的是
（ ）。
A ． 94,32,40,90,80,46,21,69 B． 32,40,21,46,69,94,90,80
C ． 21,32,46,40,80,69,90,94 D． 90,69,80,46,21,32,94,40
22. 直接插入排序在最好情况下的时间复杂度为（ ）
2 A． O(logn) B． O(n) C． O(n*logn) D． O(n)
23. 对序列{15，9，7，8，20，-1，4，} 用希尔排序方法排序，经一趟后序列变为{15，-l ，
4，8，20，9，7}则该次采用的增量是 ( )
A. l B. 4 C. 3 D. 2
24. 对关键码序列28，16，32，12，60，2，5，72快速排序，从小到大一次划分结果为（ ）。
A. (2,5,12,16)26(60,32,72) B. (5,16,2,12)28(60,32,72)
C. (2,16,12,5)28(60,32,72) D. (5,16,2,12)28(32,60,72)
25. 在对n 个元素的序列进行排序时，堆排序所需要的附加存储空间是（ ）。
A. O(log2n) B. O(1) C. O(n) D. O(nlog2n)
二、综合应用题
1、判断下列序列是否是堆（可以是小堆，也可以是大堆，若不是堆，请将它们调整为堆）。
（1）100，85，98，77，80，60，82，40，20，10，66
（2）100，98，85，82，80，77，66，60，40，20，10
（3）100，85，40，77，80，60，66，98，82，10，20
（4）10，20，40，60，66，77，80， 82，85，98，100
2、给出一组关键字：29，18，25，47，58，22，51，10，分别写出按下列各种排序方法进行排序时的变化过程：
(1) 归并排序 每归并一次书写一个次序。
(2) 快速排序 每划分一次书写一个次序。
(3) 堆排序 先建成一个堆，然后每从堆顶取下一个元素后，将堆调整一次。
第1章 绪论
一、选择题
1.B 2.C 3.1C 3.2B 4.B 5.D 6.B 7.C 8.D 9..A 10.C
第2章 线性表
一、选择题
1.A 2.B 3.C 4.A 5.D 6.D 7.D 8.B 9.B,C 10.C
11.C 12.C 13.A 14.B 15.B
第3章 栈和队列
一、选择题
1.B 2.B 3.D 4.B 5.B 6.C 7.D 8.B 9.D 10.C
11.A 12.C 13.B 14.1B 14.2A 14.3C 14.4C 14.5F 15.C 16.C 17.A
第4章 树和二叉树
一、选择题
1.D 2.D 3.A 4.B 5.D 6.B 7.C 8.D 9.C 10.B
11.C 12.C 13.B 14.D 15.A 16.C 17.C 18.D 19.C 20.B
21.D 22.B 23.A 24.B 25.C 26.B 27.D 28.A 29.D 30.C
31.D 32.B 33.C 34.A 35.C 36.C 37.B 38.B
39.D 40.1C 40.2D 40.3F 40.4H 40.5I
第5章 图
一、选择题
1.A 2.B 3.A 4.D 5.1B 5.2D 6.1B 6.2C 7.A 8.B
11.D 12.A,B 13.B 14.A 15.A 16.A 17.B 18.D 19.A 20.C
21.B
第6章 查找
一、选择题
1.C 2.D 3.C 4.D 5.B 6.1C 6.2C 7.1B
7.2A 8.C 9.D 10.1A 10.2C 11.B 12.D 13.D
14.D 15.C
二、综合应用题
1. 评价哈希函数优劣的因素有：能否将关键字均匀影射到哈希空间上，有无好的解决9.B 10.C
冲突的方法，计算哈希函数是否简单高效。由于哈希函数是压缩映像，冲突难以避免。解决冲突的方法：
① 开放定址法 形成地址序列的公式是：H i =（H （key ）+di ）% m ，其中m 是表长，d i 是增量。根据d i 取法不同，又分为三种：
a ．d i =1，2，„，m-1 称为线性探测再散列，其特点是逐个探测表空间，只要散列表中有空闲空间，就可解决碰撞，缺点是容易造成“聚集”，即不是同义词的关键字争夺同一散列地址。
b ．d 222，-22，„ ， k 2
i =1，-1，2（k ≤m/2） 称为二次探测再散列，它减少
了聚集，但不容易探测到全部表空间，只有当表长为形如4j+3（j 为整数）的素数时才有可能。
c ．d i =伪随机数序列，称为随机探测再散列。
② 再散列法 Hi=RHi（key ） i=1，2，„，k ，是不同的散列函数，即在同义词产生碰撞时，用另一散列函数计算散列地址，直到解决碰撞。该方法不易产生“聚集”，但增加了计算时间。
③ 链地址法 将关键字为同义词的记录存储在同一链表中，散列表地址区间用H[0..m-1]表示，分量初始值为空指针。凡散列地址为i （0≤i ≤m-1）的记录均插在以H[i]为头指针的链表中。这种解决方法中数据元素个数不受表长限制，插入和删除操作方便，但增加了指针的空间开销。这种散列表常称为开散列表，而①中的散列表称闭散列表，含义是元素个数受表长限制。
2. 不一定相邻。哈希地址为i （0≤i ≤m-1）的关键字，和为解决冲突形成的探测序列
i 的同义词，都争夺哈希地址i 。
平均查找长度：ASL succ =（1+1+1+2+3+4+1+2）/8=15/8
以关键字27为例：H （27）=27%7=6（冲突） H1=（6+1）%10=7（冲突） H （6+22）%10=0（冲突） H3
2=3=（6+3）%10=5 所以比较了4次。
4. 按中序遍历序列将值1~9依次标上
6. 序列（2）不可能是二叉排序树中查到363的序列。查到501后，因363
应出现小于501的数，但序列中出现了623，故不可能
7. 37/12
第7章 排序
一、选择题
1.D 2.D 3.C
4.A 5.C,D 6.B,D 7.A 8.A 9.C 10.C 11.B
12.C 13.A 14.D 15.C 16.1C 16.2B 17.D 18.D 19.A
21.C 22.B 23.B 24.B 25.B
二、综合应用题
1. (1)是大堆； (2)是大堆；（4）是小堆；
(3)不是堆，调成大堆 100，98，66，85，80，60，40，77，82，10，20
20.A