数据结构题库

第1章 绪论

一、选择题

1. 算法的计算量的大小称为计算的（ ）。

A．效率 B. 复杂性 C. 现实性 D. 难度 2. 算法的时间复杂度取决于（ ）

A．问题的规模 B. 待处理数据的初态 C. A和B 3. 计算机算法指的是（1），它必须具备（2） 这三个特性。

(1) A．计算方法 B. 排序方法 C. 解决问题的步骤序列 D. 调度方法

(2) A．可执行性、可移植性、可扩充性 B. 可执行性、确定性、有穷性

C. 确定性、有穷性、稳定性 D. 易读性、稳定性、安全性

4. 一个算法应该是（ ）。

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. 下述哪一条是顺序存储结构的优点？（ ）

A．存储密度大 B．插入运算方便 C．删除运算方便 D．可方便地用于各种逻辑结构的存储表示

2. 下面关于线性表的叙述中，错误的是哪一个？（ ）

A．线性表采用顺序存储，必须占用一片连续的存储单元。 B．线性表采用顺序存储，便于进行插入和删除操作。 C．线性表采用链接存储，不必占用一片连续的存储单元。 D．线性表采用链接存储，便于插入和删除操作。 3. 线性表是具有n个（ ）的有限序列（n>0）。

A．表元素 B．字符 C．数据元素 D．数据项 E．信息项 4. 若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则

利用（ ）存储方式最节省时间。

A．顺序表 B．双链表 C．带头结点的双循环链表 D．单循环链表 5. 某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采

用（ ）存储方式最节省运算时间。

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<=i<=n+1)。

2

A. 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<=i<=n）个

元素是（ ）。

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．nlog2n B．log2n C．?log2n?+1 D．不确定 15. 一棵具有 n个结点的完全二叉树的树高度（深度）是（ ）

A．?log2n?+1 B．log2n+1 C．?log2n? D．log2n-1 16. 高度为 K的二叉树最大的结点数为（ ）。

A．2 B．2 C．2 -1 D．2-1

k

k-1

k

k-1

17. 一棵高为K的完全二叉树至少有（ ）个结点

kk-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<=n) B．A[2i+1](2i+1<=n) C．A[i-2] D．条件不充分，无法确定 40. 从下列有关树的叙述中,选出5条正确的叙述（ ）。

A．二叉树中每个结点有两个子结点,而树无此限制,因此二叉树是树的特殊情况。

k-1

B．当K≥1时高度为K的二叉树至多有2个结点。 C．用树的前序遍历和中序遍历可以导出树的后序遍历。

D．线索二叉树的优点是便于查找某结点的前驱结点和后继结点。 E．将一棵树转换成二叉树后,根结点没有左子树。

F．一棵含有N个结点的完全二叉树,它的高度是?LOG2N?+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、 将下列由三棵树组成的森林转换为二叉树。

D G A

J H I E B C K L M N O

F P

17、 设T是一棵给定的查找树,试编写一个在树中删除根结点为a的子树的程序,要求

在删除的过程中释放该子树所有结点所占有的存储空间,这里假设树T中结点所占有的存储空间是通过动态存储分配取得的,其结点的形式为:（lchild,data,rchild）

18、 试编写算法，对一棵以孩子—兄弟链表表示的树统计叶子的个数。

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

冲突的方法，计算哈希函数是否简单高效。由于哈希函数是压缩映像，冲突难以避免。解决冲突的方法：

① 开放定址法 形成地址序列的公式是：Hi=（H（key）+di）% m，其中m是表长，di是增量。根据di取法不同，又分为三种：

a．di =1，2，?，m-1 称为线性探测再散列，其特点是逐个探测表空间，只要散列表中有空闲空间，就可解决碰撞，缺点是容易造成“聚集”，即不是同义词的关键字争夺同一散列地址。

b．d222，-22，? ，?k2

i =1，-1，2（k≤m/2） 称为二次探测再散列，它减少了聚集，但不容易探测到全部表空间，只有当表长为形如4j+3（j为整数）的素数时才有可能。

c．di =伪随机数序列，称为随机探测再散列。

② 再散列法 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。 3. 哈希表如下： 散列地址 0 1 2 3 4 5 6 7 8 9 关键字 14 01 9 23 84 27 55 20 比较次数 1 1 1 2 3 4 1 2 平均查找长度：ASLsucc=（1+1+1+2+3+4+1+2）/8=15/8

以关键字27为例：H（27）=27%7=6（冲突） H1=（6+1）=7（冲突）

H（6+22）=0（冲突） H3

2=3=（6+3）=5 所以比较了4次。 4. 按中序遍历序列将值1~9依次标上

6. 序列（2）不可能是二叉排序树中查到363的序列。查到501后，因363<501，后面

应出现小于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

本文来源：https://www.bwwdw.com/article/hshx.html