一、 单项选择题 绪论
1. 计算机中的算法一般具有输入、输出和（ C ）五个基本性质。
A．确定性、有穷性、稳定性 B．易读性、确定性、可行性
C．有穷性、确定性、可行性 D．可行性、可移植性、可扩展性
2. 数据的最小单位是(B )。
（A）数据元素 (B) 数据项 (C) 数据类型 (D) 数据变量 3. 以下数据结构中（D）属非线性结构。
A.栈 B.串 C.队列 D.平衡二叉树
4. 以下不属于存储结构是（B） 。
A.栈 B.线索树 C.哈希表 D.双链表
5. 算法的时间复杂度取决于（C）。
A. 问题的规模 B. 待处理数据的初始状态
C. A和B D. 计算机的配置 6. 在（D）中将会用到栈结构。
A. 递归调用 B. 函数调用 C. 表达式求值 D.以上场景都有
7. 某算法的空间复杂度为O(1)，则（B）。
1
A.该算法执行不需要任何辅助空间
B.该算法执行所需辅助空间大小与问题规模n无关 C.该算法执行不需要任何空间
D.该算法执行所需全部空间大小与问题规模n无关 8. 顺序表和链表相比存储密度较大，这是因为（B ）。
A.顺序表的存储空间是预先分配的
B.顺序表不需要增加指针来表示元素之间的逻辑关系 C.链表中所有节点的地址是连续的 D.顺序表中所有元素的存储地址是不连续的
9. 设n是描述问题规模的非负整数，下面程序片段的时间复杂度为（ A）。
x=1; while (x<=n) x=5*x;
A. O(log5n) B.O(n) C.O(nlog5n) D.O(n5) 10.
数据结构是指 （D） 。
A. 一种数据类型 C. 相互之间存在一种或多种特定关系的数据元素的集合
B. 数据的存储结构D. 一组性质相同的数据元素的集合 11.
以下算法的时间复杂度为 （A） 。 void fun(int n) { int i=1; while (i<=n)
2
i++; }
A. O(n) B. O(
n)
C. O(nlog2n) D. O(log2n) 12.
在存储数据时，通常不仅要存储各数据元素的值，而且还要存
储（C） 。
A. 数据的处理方法 B. 数据元素的类型 C. 数据元素之间的关系 D. 数据的存储方法 13.
以下数据结构中元素之间为非线性关系的是（D） 。
A.栈 B.队列 C.线性表 D.以上都不是 线性表 14.
设线性表有n个元素，以下操作中， A 在顺序表上实现比
在链表上实现效率更高。
A.输出第i（1≤i≤n）个元素值 B.交换第1个元素与第2个元素的值 C.顺序输出这n个元素的值
D.输出与给定值x相等的元素在线性表中的序号 15.
下面关于线性表的叙述，错误的是（ D ）。
A．线性表的顺序存储方式需要占用一块连续的存储空间 B．线性表的链式存储方式不必占用一块连续的存储空间 C．线性表采用链式存储便于插入和删除操作的实现 D．线性表采用顺序存储便于插入和删除操作的实现 16.
在含有n个节点的单链表中查找第i个节点的平均时间复杂度
是 （D）。
3
A.O(log2n) B.O(1) C.O(n2) D.O(n) 17.
设线性表中有n个元素，以下运算中，（A）在单链表上实现要
比在顺序表上实现效率更高。
A.删除指定位置元素的后一个元素
B.在最后一个元素的后面插入一个新元素 C.顺序输出前k个元素
D.交换第i个元素和第n-i+1个元素的值（i=1，2，…，n） 18.
在一个带头结点的循环单链表L中，删除元素值为x的结点，
算法的时间复杂度为 （A） 。
A. O(n) B. O(n) C. O(nlog2n) D. O(n2) 19.
双向链表中有两个指针域，prior和next，分别指向前驱和后
继，设p指向链表中的一个结点，q指向一待插入结点，现要求在p前插入q，则正确的插入为（ D ） A.
p->prior=q;
q->next=p;
p->prior->next=q; q->prior=p->prior; B.
q->prior=p->prior;
p->prior->next=q;
q->next=p;
p->prior=q->next;
C. q->next=p; p->next=q; p->prior->next=q; q->next=p; D. p->prior->next=q; q->next=p; q->prior=p->prior; p->prior=q; 20.
在一个双链表中，删除p所指节点（非首、尾节点）的操作是
(A) 。
A.p->prior->next=p->next;p->next->prior=p->prior;
4
B.p->prior=p->prior->prior;p->prior->prior=p; C.p->next->prior=p;p->next=p->next->next;
D.p->next=p->prior->prior;p->prior=p->prior->prior; 21.
在长度为n的顺序表中插入一个元素，对应算法的时间复杂度
为（C）。
A.O(1) B.O(log2n) C.O(n) D.O(n2) 栈和队列 22.
设n个元素进栈序列是1、2、3、…、n，其输出序列是若p1=3，
则p2的值为 C 。
A.一定是2 B.一定是1 C.不可能是1 D.以上都不对 23.
设n个元素进栈序列是p1，p2，p3，…，pn，其输出序列是p1、
p2、…、pn，若p3=3，则p1的值 A 。
A.可能是2 B.一定是2 C.不可能是1 D.一定是1
24. 设栈的输入序列是1、2、3、4，则（ D）不可能是其出栈序列。
A.1，2，4，3 B.2，1，3，4 C.1，4，3，2 D.4，3，1，2 25.
在数据处理过程中常需要保存一些中间数据，如果要实现后保
存的数据先处理，则应采用（B）来保存这些数据。
A.线性表 B.栈 C.队列 D.单链表 26.
在数据处理过程中常需要保存一些中间数据，如果先保存的数
据先处理，则使用（ B）来保存这些数据。
5
A.线性表 B. 队列 C. 栈 D.单链表 27.
在环形队列中，元素的排列顺序（C ）。
A.与队头和队尾指针的取值有关 B.与元素值的大小有关 28.
C.由元素进队的先后顺序确定 D.与存放队中元素的数
组大小有关设循环队列的最大容量是N，front是头指针，rear是尾指针，则队空的判定条件为（C）。
A. (rear+1)%N==front B. rear+1==front C. rear==front D. rear=0，且front=0 29.
若某循环队列有队首指针front和队尾指针rear，在队不满
时进队操作仅会改变指针（B）。
A.front B.rear C.front和rear D.以上都不队 30.
判定一个循环队列 Q(最多元素为 m)为满队列的条件是(C )。
(A) Q->front==Q->rear (B) Q->front!=Q->rear (C)Q->front==(Q->rear+1)%m (D)Q->front!= (Q->rear+1)%m 31.
栈和队列的共同特点是(A )。
(A)只允许在端点处插入和删除元素 (B)都是先进后出 (C)都是先进先出 (D)没有共同点 32.
设环形队列中数组的下标为0～N-1，其队头、队尾指针分别
为front和rear（front指向队列中队头元素的前一个位置，rear指向队尾元素的位置），则其元素个数为（D） 。
A. rear-front B. rear-front-1 C. (rear-front)％N+1 D. (rear-front+N)％N 33.
若用一个大小为6的数组来实现环形队列，队头指针front指
6
向队列中队头元素的前一个位置，队尾指针rear指向队尾元素的位置。若当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为(B)。 A. 1和5 B. 2和4 C. 4和2 D. 5和1 34.
中缀表达式a*(b+c)-d的对应的后缀表达式是 （B） 。 A. a b c d * + - B. a b c +* d - C. a b c * + d - D.- + * a b c d 35.
设输入序列为 a，b，c，d，借助一个栈规定a 最先输出，则
不可能的输出序列为（ C） A a，b，d，c B a，d，c，b C a，d，b，c D a，c，d，b 串数组和广义表 36.
在KMP算法中，串“ababaabab”的next数组值为（A）。 A. -1,0,0,1,2,3,1,2,3 B. -1,0,0,1,2,1,1,2,3 C. -1,0,0,1,2,3,4,1,2 D. -1,0,0,1,2,3,1,2,2 37.
设二维数组A[3][5]，每个数组元素占用2个存储单元，若按
列优先顺序进行存储，A[0][0]的存储地址为100，则A[2][3]的存储地址是 （A）。
A. 122 B. 126 C. 114 D. 116 38.
设数组A［0..5, 0..6］的每个元素占5个存储单元。则将其
按行优先存储在起始地址为1000的连续内存单元中，则元素A[5][5]的存储地址为（A ）。
7
A．1200 B．1180 C．1205 D．1175 39.
将10阶对称矩阵压缩存储到一维数组A中，则数组A的长度
最少为（D ）。
A.100 B.40 C.80 D. 40.
若一个栈采用数组s[0..n-1]存放其元素，初始时栈顶指针为
n，则以下元素x进栈的正确操作是（C） 。
A.top++;s[top]=x; B.s[top]=x;top++;
C.top--;s[top]=x; B.s[top]=x;top--; 41.
一个n×n的对称矩阵A，如果采用以列优先（即以列序为主
序）的压缩方式存放到一个一维数组B中，则B的容量为 C 。
A. n2 B.n C. n(n21) D.(n1)
2222树结构 42.
在下列存储形式中，_D__ 不是m叉树（m>2）的存储形式？
A．双亲表示法 B．孩子链表表示法 C．孩子兄弟表示法 D．顺序存储表示法 43.
若一棵3次树中有a个度为1的节点，b个度为2的节点，c
个度为3的节点，则该树中有（D） 个叶子节点。
A.1+2b+3c B.a+2b+3c C.2b+3c D.1+b+2c 44.
设树T的度为4，其中度为1、2、3、4的结点个数分别为4、
2、1、1，则T中的叶子结点个数是（D） 。
A.5 B.6 C.7 D.8 45.
一棵二叉树的后序遍历序列为DABEC，中序遍历序列为DEBAC，
则先序遍历序列为 D 。
8
A.ACBED B.DECAB C.DEABC D.CEDBA 46.
一棵深度为h（h≥1）的完全二叉树至少有（A）个结点。
A. 2h-1 B. 2h
C. 2h+1 D. 2h-1+1 47.
设森林F中有4棵树，第1、2、3、4棵树的结点个数分别为
a、b、c、d，将森林F转换为一颗二叉树B，则二叉树B根结点的左子树上的结点个数是（A） 。
A.a-1 B.a C. a+b+c D.b+c+d 48.
由权值分别为9、2、7、5的四个叶子节点构造一棵哈夫曼树，
该树的带权路径长度为（B ）。
A.23 B.44 C.37 D.27 49.
一棵含有n个结点的线索二叉树中，其线索个数为（C） 。
A. 2n B. n-1 C. n+1 D. n
50. 设给定权值总数有 n 个，其哈夫曼树的结点总数为（D ） A 不确定 B 2n C 2n+1 D 2n-1
第1次必定是2个叶子组成二叉树,产生1新结点,接下来有2种情况： 1.此新结点与原剩下的叶子再组成二叉树又产生1新结点,这样就只有第1次时由2个叶子产生1新结点,以后每次由1叶子与新结点产生新结点,故n个叶子共有2n-1个结点.
2.剩下的叶子中又有2个叶子(比第1次产生的新结点权小)结合产生新结点,其它类似,那么必然会由2个都是新结点再产生新结点,所以实际上数量与第1种一样,共有2n-1个. 图结构 51.
无向图的邻接矩阵是一个（ C）。
A．上三角矩阵 B．对角矩阵 C．对称矩阵 D．零矩阵
9
52. 如图所示有向图的一个拓扑序列是(B )。
(A)ABCDEF (B)FCBEAD (C) FEDCBA) (D) DAEBCF
53.
一个含有n个顶点的无向连通图采用邻接矩阵存储，则该矩阵
一定是（A）。
A. 对称矩阵 B. 非对称矩阵 C. 稀疏矩阵 D. 稠密矩阵 54.
设无向连通图有n个顶点e条边，若满足（A），则图中一定有
回路。
A. e≥n B. e A. 任何一个关键活动提前完成，则整个工程一定会提前完成 B. 完成整个工程的最短时间是从源点到汇点的最短路径长度 C. 一个AOE网的关键路径一定是唯一的 D. 任何一个活动持续时间的改变可能会影响关键路径的改变 56. 设完全无向图中有 n 个顶点，则该完全无向图中有（A ）条边。 (A) n(n-1)/2 (B) n(n-1) (C) n(n+1)/2 (D) (n-1)/2 57. 下列关于图的叙述中，正确的是（C）。 Ⅰ.回路是简单路径 Ⅱ.存储稀疏图，用邻接矩阵比邻接表更省空间 Ⅲ.若有向图中存在拓扑序列，则该图不存在回路 A. 仅Ⅱ B. 仅Ⅰ、Ⅱ C. 仅Ⅲ D. 仅 10 Ⅰ、Ⅲ 58. 对图1所示的无向图，从顶点1开始进行深度优先遍历；可得 到顶点访问序列 A 。 A.1 2 4 3 5 7 6 B.1 2 4 3 5 6 7 C.1 2 4 5 6 3 7 D.1 2 3 4 5 7 6 1 3 2 4 6 5 7 图1 一个无向图 59. 对于无向图的邻接矩阵来说，（C ）。 A.第i行上、第i列上非零元素总数等于顶点i的度数 B.矩阵中的非零元素个数等于图中的边数 C.第i行上的非零元素个数和第i列的非零元素个数一定相等 D.邻接矩阵中非全零行的行数等于图中的顶点数 60. 已知图G的邻接表如图1所示，则从顶点V0出发进行深度优 先遍历的结果是___A__。 0 1 2 3 4 v0 v1 v2 v3 v4 1 0 0 0 3 ∧ 2 2 1 2 ∧ 3 ∧ 3 4 ∧ ∧ 图图G的邻接表 A. 0,1,2,3,4 B. 0,1,2,4,3 C. 0,1,3,4,2 D. 0,1,4,2,3 61. 以下关于有向图的说法中，正确的是（B）。 A.强连通图是任何顶点到其他所有顶点都有边 B.完全有向图一定是强连通图 C.有向图中任一顶点的入度等于出度 11 D.有向图边集的子集和顶点集的子集可构成原有向图的子图 A.顶点2 B.顶点3 C.顶点4 D.顶点7 62. 一个表示工程的AOE网中的关键路径（B） 。 A.必须是唯一 的 B.可以有多条 C.可以没有 D.以上都不对 查找 63. 适用于折半查找的表的存储方式及元素排列要求为 ( C ) A．链接方式存储，元素无序 B．链接方式存储，元 素有序 C． 顺序方式存储，元素有序 D．顺序方式存储，元素无序 . 顺序查找，在等概率情况下，其平均查找长度为（ ） A n B 2n C n+1 D (n+1)/2 65. 关于m阶B-树说法错误的是(B) 。 A. m阶B-树是一棵平衡的m叉树 B. B-树中的查找无论是否成功都必须找到最下层结点 C. 根结点最多含有m棵子树 D. 根结点至少含有2棵子树 66. 哈希表中出现冲突是指 D 。 A. 两个元素具有相同的序号 B. 两个元素的关键字不同，而其他属性相同 C. 数据元素过多 D. 两个元素的关键字不同，而对应的哈希函数值（存储地址）相同 67. 对有n个记录的表进行直接插入排序，在最好情况下需比较 A 次关键字。 12 A.n-1 B.n+1 C.n/2 D.n(n-1)/2 68. 哈希查找方法一般适用于（D）情况下的查找。 A. 查找表为链表 B. 查找表为有序表 C. 关键字集合比地址集合大得多 D. 关键字集合与地址集合之间存在着某种对应关系。 69. 以下关于哈希查找的叙述中正确的是（D ）。 A.哈希查找中不需要任何关键字的比较 B.采用拉链法解决冲突时，查找每个元素的时间是相同的 C.哈希表在查找成功时的平均查找长度仅仅与表长有关 D.哈希表的装填因子等于表中填入的记录数除以哈希表的长度 排序 70. 设有5000个待排序的记录，如果需要用最快的方法选出其中 关键字最小的10个记录，则选用下列（ B）方法比较合适。 A. 快速排序 B. 堆排序 C. 归并排序 D. 插入排序若 71. 设有一组初始记录关键字序列为(34，76，45，18，26，54，92)，则由这组记录关键字生成的二叉排序树的深度为（C ）。 (A) 6 (B) 5 (C) 4 (D) 7 72. 设一组初始记录关键字序列(5，2，6，3，8)，以第一个记录 关键字5为基准进行一趟快速排序后的结果为（ C ）。 A. 2，3，5，8，6 B. 3，2，5，8，6 C. 3，2，5，6，8 D. 2，3，6，5，8 73. 时间复杂度恒为O(nlog2n)且不受数据初始状态影响的排序算法 是（A）。 A．归并排序 B．希尔排序 C．快速排序 D．简单选 13 择排序 74. 堆的形状是一棵__D_____。 A. 满二叉树 B. 二叉判定树 C. 平衡二叉树 D. 完全二叉树 75. 下列排序算法中，其中（D ）是稳定的。 A 堆排序，冒泡排序 B 快速排序，堆排序 C 直接选择排序，归并排序 D 归并排序，冒泡排序 76. 在下列排序方法中，( D )是不稳定的排序方法。 A．直接插入排序 B．归并排序 C．冒泡排序 D．直接选择排序 77. 以下序列是堆的是（C） 。 A. {75,65,30,15,25,45,20,10} B. {75,65,45,10,30,25,20,15} C. {75,45,65,30,15,25,20,10} D. {75,45,65,10,25,30,20,15} 78. 用某种排序方法对数据序列{24,88,21,48,15,27,69,35,20} 进行递增排序，元素序列的变化情况如下： （1）{24,88,21,48,15,27,69,35,20} （2）{20,15,21,24,48,27,69,35,88} （3）{15,20,21,24,35,27,48,69,88} （4）{15,20,21,24,27,35,48,69,88} 则所采用的排序方法是（A）。 A. 快速排序 B. 简单选择排序 C. 直接插入排序 D. 归并排序 79. 如要在1000个整数中找出前10个最小的整数，在以下排序方 法中最好采用（ B）。 A.直接插入排序 B. 冒泡排序 C.二路归并排序 D. 希尔排序 14 80. 对含有n个元素的顺序表采用直接插入排序方法进行排序，在 最好情况下算法的时间复杂度为（A）。 A. O(n) B. O(nlog2n) C. O(n2) D. O(n) 81. 下列四棵二叉树中，（ ）是一个堆。 82. 以下排序方法中， （C）不需要进行关键字的比较。 A.快速排序 B.归并排序 C.基数排序 D.堆排序 83. 在含有27个节点的二叉排序树上，查找关键字为35的节点，则依次比较的关键字有可能是（D）。 A.28,36,18,46,35 B.18,36,28,46,35 C.46,28,18,36,35 D.46,36,18,26,35 84. 对一组数据(84,47,25,15,21)排序，数据在排序过程中的变化如下： （1）84，47，25，15，21 （2）21，47，25，15，84 （3）15，21，25，47，84 （4）15，21，25，47，84 则所采用的排序方法是 C 。 A.冒泡排序 B.快速排序 C.堆排序 D.直接插入排序 二、填空题（每空2分，共20分） 绪论 1. 数据结构研究的内容包括数据的逻辑结构，数据的_存储结构_以 15 及对数据的运算。 线性表 2. 已知一有向图的邻接表存储结构如下：从顶点1出发，DFS遍历的输出序列是_(1, 3, 4, 5, 2)_，BFS遍历的输出序列是 (1, 3, 2, 4, 5) 或 0 1 2 3 4 v0 v1 v2 v3 v4 1 0 0 0 3 ∧ 2 2 1 2 ∧ 3 ∧ 3 4 ∧ ∧ 3. 在长度为n（n≥1）的循环双链表L中，在尾节点之后插入一个新节点的时间复杂度为（O(1) ）。 4. 在单链表 L 中，指针 P 所指结点有后继结点的条件是__ p->next!=NULL。 16 栈和队列 5. 设循环队列中数组的下标是0～N-1，其队头队尾指针分别为f和r（f指向队首元素的前一位置，r指向队尾元素），则其元素个数为 (r-f+N)％N 。 6. 设栈s和队列q的初始状态都为空，元素a、b、c、d、e和f依次通过栈s，一个元素出栈后即进入队列q，若6个元素出队的序列是b、d、c、f、e、a，则栈s的容量至少应该存 3 个元素？ 串和数组 7. 在KMP算法中，设模式串p=abcabaa，那么p的nextval数组为（[-1,0,0,-1,0,2,1]）。 8. 若将n阶上三角矩阵A按列优先顺序压缩存放在一维数组B[1..n(n+1)/2]中，A中第一个非零元素a1,1存于B数组的b1中，则应存放到bk中的非零元素ai,j（1≤i≤n，1≤j≤i）的下标i、j与k的对应关系是 j(j1)i 。 29. 设二维数组A[3][5]，每个数组元素占用2个存储单元，若按列优先顺序进行存储，A[0][0]的存储地址为100，则A[2][3]的存储地址是 。 10. 两个串是相等的，当且仅当两个串的长度相等且 各对应位置 上的___的字符都相同。 11. 对矩阵进行压缩是为了__节省存储空间_________。 17 树结构 12. 设某棵二叉树中度数为0的结点有m个，度数为1的结点数为 n，则这棵二叉有（2m+n-1）个结点。 13. 设某棵二叉树中有2000个结点，则该二叉树的最小高度为 __11__。 14. 一棵二叉树的先序遍历序列为ABCDEF，中序遍历序列为 CBAEDF，则后序遍历序列为 CBEFDA 。 15. 设森林F对应的二叉树为B，B中有m个节点，其根节点的右 子树的节点个数为n，森林F中第一棵树的节点个数是 m-n 。 16. 高度为 7 的完全二叉树至少有__32__个叶子结点。 图结构 17. 设完全无向图中有n个顶点，则该完全无向图有 （n(n-1)/2）条边。 18. 对于有n个顶点e条边的有向图，求单源最短路径的Dijkstra 算法的时间复杂度为 O(n2) 。 19. 在一个具有n个顶点的有向图中，构成强连通图时至少有 n 条边。 20. 如果从无向图的任一顶点出发进行一次广度优先遍历即可访 问所有顶点，则该图一定是 连通图 。 21. 拓扑排序 方法可以判断一个有向图是否存在回路。 18 22. 在无向图 G 的邻接矩阵 A 中，若 A［i］［j］等于 0，则 A ［j］［i］等于_____0___。 23. 在有n个顶点的有向图中，每个顶点的度最大可达 2(n-1) 。 查找 24. 对有序表A[1…20]按照二分查找方法进行查找，那么查找成 功时的最大查找长度为___5__。 25. 对含有n个元素的顺序表采用顺序查找方法，不成功时的比较 次数是（n ）。 26. 对有18个元素的有序表R[1..18]进行二分查找，则查找R[3]的比较序列的下标为 9、4、2、3 。 27. 对有序表 A[1…20]按二分查找方法进行查找，查找成功时的 最大查找长度为________3.7_____。 1 +2*2 + 4*3 + 8*4+ 5*5 = 74 平均长度是 74 /20 =3.7 排序 28. 设二叉排序树上有n个结点，则查找结点的平均时间复杂度为 （logn。 2）29. 30. 堆排序算法的时间复杂度最坏的情况下为（nlogn。 2）有一种排序方法，它每一趟都将未排序序列中的一个元素，插 入到已排序序列的合适位置，该排序方法是（插入排序 ）。 19 31. 对含有n元素的关键字序列进行直接选择排序时，所需进行的关键字之间的比较次数为 n(n-1)/2 。 32. 在一棵平衡二叉树中，每个节点的平衡因子的取值范围是（-1～1 ） 三、判断题(每题 1 分,共 5 分) 1. 线性表的特点是每个元素都有一个前驱和一个后继。 (Х) 2. 非空的双向循环链表中任何结点的前驱指针均不为空。 （ √ ） 3. 不论线性表采用顺序存储结构还是链式存储结构，删除值为X的结 点的时间复杂度均为O(n)。（ √ ） 4. 链队列执行出队操作不会改变头指针的值,但可能会改变尾 指针 的值。(Х) 5. 二维数组和数组均不是特殊的线性结构。（ Х ） 6. 稀疏矩阵的压缩存储可以用一个三元组表来表示稀疏矩阵中的非 0元素。（ √ ） 7. 所谓取广义表的表尾就是返回广义表中最后一个元素。 (Х) 8. 由二叉树的先序序列和中序序列可以惟一确定该二叉树 (√) 9. 中序遍历一棵二叉排序树可以得到一个有序的序列。 (√) 10. 满二叉树一定是完全二叉树,完全二叉树不一定是满二叉树。 (√) 11. 有向图的邻接表和逆邻接表中表结点的个数不一定相等。 (√) 20 12. 图的深度优先遍历算法中需要设置一个标志数组，以便区分图 中的每个顶点是否被访问过。（ √ ） 13. 如果某个有向图的邻接表中第i条单链表为空，则第i个顶点的 出度为零。（√ ） 14. 若一个无向图的以顶点1为起点的深度遍历序列唯一，则可唯 一确定该图（ √ ） 15. 如果两个关键字的值不等但哈希函数值相等,则称这两个关键 字为同义词。 (√) 16. 分块查找的基本思想是首先在索引表中进行查找，以便确定给 定的关键字可能存在的块号，然后再在相应的块内进行顺序查找。（ √ ） 17. 在采用线性探测法处理冲突的散列表中，所有同义词在表中相 邻。（X） 18. 直接选择排序算法在最好情况下的时间复杂度为 O(n)。 (X) 19. 设初始记录关键字基本有序，则快速排序算法的时间复杂度为 O(nlog2n)。（ Х ） 20. 向二叉排序树中插入一个结点需要比较的次数可能大于该二 叉树的高度。（ Х ） 21 四、综合应用题（） 线性表 1. 什么是ADT？并举例说明。 要点：ADT即抽象数据类型，是指用户进行软件系统设计时从问题的数学模型中抽象出来的逻辑数据结构和逻辑数据结构上的运算，不考虑计算机的具体结构和运算的具体实现算法。 举例：参见教材P10或P28。 2. 试说明顺序存储结构和链式存储结构的特点（5分） 答： a) 顺序存储结构：逻辑结构相邻的数据元素的存放地址也相邻 优点：存储密度大（=1），存储空间利用率高。能够随机存取 缺点：插入或删除元素不方便，需要移动大量的数据元素 b) 链式存储结构：逻辑结构相邻的数据元素的存放地址不一定相邻 优点：插入或删除元素时很方便，使用灵活。 缺点：存储密度小（<1），存储空间利用率低。不能够随机存 22 取 串、数组 3. 一棵完全二叉树上有1001个结点，其中叶结点的个数是多少？ （需写出推导过程，8分） 答：二叉树中度为1的结点个数只能是1或0。设n1=1，n=n0+n1+n2=n0+n2+1=1001，由性质1可知n0=n2+1，由两式可求n0=500.5，不成立；设n1=0，n=n0+n1+n2=n0+n2=1001，由性质1可知n0=n2+1，由两式可求n0=501。本题答案为：501。 评分标准：只给出结果给3分，推导过程占5分。 4. （8分）已知一棵二叉树的先序遍历序列为ABDGHCEIF，它的中 序遍历序列是BGDHAEICF，请构造出这棵二叉树，并给出其层次遍历序列 答:（8分）最后构造的二叉树如图1所示（4分），其层次遍历序列为ABCDEFGHI（4分）。 A B D G H E I C F 图1 一棵二叉树 树 5. 已知某二叉树的中序和后序遍历序列分别为BFDJGACHKEI和FJGDBKHIECA，请画出该二叉树，并给出该二叉树的先序遍历序列。 23 （8分） 二叉树如下图所示： 6分 先序遍历序列为：ABDFGJCEHKI 2分 6. 已知一棵度为m的树中有n1个度为1的节点，n2个度为2的节 点，…，nm个度为m的节点，问该树中有多少个叶子节点? 解：依题意，设n为总的节点个数，n0为叶子节点（即度为0的节点）的个数，则有： n=n0+n1+n2+…+nm 又有：n-1=度的总数，即，n-1=n1×1+n2×2+…+nm×m 两式相减得：1=n0-n2-2n3-…-(m-1)nm 则有：n0=1+n2+2n3+…+(m-1)nm=1(i1)n。 ii2m7. 已知一棵度为4的树中，其度为0、1、2、3的结点数分别为14、4、3、2，求该树的结点总数n和度为4的结点个数，并给出推导过程。 答：结点总数n=n0+n1+n2+n3+n4，即n=23+n4，又有：度之和=n-1=0×n0+1×n1+2×n2+3 ×n3+4×n4，即n=17+4n4，综合两式得：n4=2，n=25。所以，该树的结点总数为25，度为4的结点个数为2。 【评分说明】结果为4分，过程占6分。 8. 假设通信电文使用的字符集为{a,b,c,d,e,f,g,h},各字符在电文 24 中出现 的频度分别为: 7,19,2,6,32,3,21,10，试为这 8 个字符设计哈夫曼编 码。要求:(1). 画出你所构造的哈夫曼树 (要求树中左孩子结点的权值不大于右孩子结点的 权值);
(2). 按左分支为 0 和右分支为 1 的规则,分别写出与每个字符对应的编码。（3）问该字符串的编码至少有多少位 (2) 每个字符对应的编码 ： a: 1010 e:11 b: 00 f:10001 c: 10000 g:01 d: 1001 h:1011 (3) (2+3)*5+( 6+7+ 10)*4+*3+( 19+ 21+32 )*2=261 9. 画出与下图所示森林对应的二叉树。 25 图 10. 下图所示为一有向图，请给出该图的下述要求：（12 分） （1）每个顶点的入度和出度；（2）邻接表 11. 对于图1所示的带权有向图，采用Dijkstra算法求从顶点0 到其他顶点的最短路径，要求给出求解过程，包括邻接矩阵、每一步的S集合、dist和path数组元素。 2 0 6 9 4 3 1 2 1 2 2 7 3 图 一个有向图 答：该图对应的邻接矩阵如下： 26 069201202 0370在求最短路径时，S（存放顶点集），dist[]（存放最短路径长度）和path[]（存放最短路径）的变化如下： S dist[] path[] 0 1 2 3 4 0 1 2 3 4 {0} 0 6 9 ∞ 2 {0, 4} {0, 1 ,4} 0 5 9 9 2 {0,1,2,4} 0 5 6 7 2 {0,1,2,3,4} 最后得到的结果如下： 顶点0到顶点1的最短距离为5，最短路径为：0、4、1 顶点0到顶点2的最短距离为6，最短路径为：0、4、1、2 顶点0到顶点3的最短距离为7，最短路径为：0、4、1、3 顶点0到顶点4的最短距离为2，最短路径为：0、4。 12. （10分）对于如图1所示的带权无向图，直接给出利用普里 0 4 1 1 0 0 5 6 7 2 0 5 6 7 2 0 0 0 1 0 4 0 4 0 0 4 1 1 0 0 4 1 1 0 -0 姆算法（从顶点0开始构造）和克鲁斯卡尔算法构造出的最小生成树的结果（注意：按求解的顺序给出最小生成树的所有边，每条边用(i， j)表示）。 27 1 0 2 5 1 3 2 3 7 4 6 8 4 5 图 一个带权无向图G 利用普里姆算法从顶点0出发构造的最小生成树为：{(0,1)，(0,3)，(1,2)，(2,5)，(5,4)}，（5分）。 利用克鲁斯卡尔算法构造出的最小生成树为：{(0,1)，(0,3)，(1,2)，(5,4)，(2,5)} ，（5分）。 说明：顺序错误不给分。 13. 什么是最小生成树？有哪两种 主要求下列图 解最小生成树的算法？任选一种求解的最小生成树，要求给出求解过程。 最小生成树为： 或： 1 3 1 2 2 3 3 4 4 1 6 2 2 3 5 4 1 4 1 6 5 1 最小生成树：连通图的极小连通子图，含有全部n个顶点，只有n－1条边。 28 最小生成树算法： 普里姆（Prim）算法和 克鲁斯卡尔（Kruscal）算法 查找 14. 设有一组关键字{32,13,49,24,38,21,4,12}，其哈希函数为： H(key)=key % 7，采用开放地址法的线性探查法解决冲突，试在0～9的哈希地址空间中对该关键字序列构造哈希表，并求等概率下查找成功和查找失败的平均查找长度。（10分） key H(key) 最终地址 计算次数 哈6分 0 1 429 1 ASL2分 ASL2分 失 败 32 4 4 1 希13 6 6 1 49 0 0 1 表3 24 4 32 功 24 3 3 1 38 3 5 3 如5 38 6 13 21 0 1 2 下7 4 4 4 7 4 12 5 8 4 ： 8 12 9 2 成 =(1+1+1+1+3+2+4+4)/8=17/8 =(3+2+1+7+6+5+4)/7=4 29 排序 15. 对下面数据表，写出采用快速排序算法排序的每一趟结果，并 标出第一趟排序中的数据移动情况。（12 分） （25，101，22，34，15，44，76，66，100，8，54，20，2，5，18） 16. 不同的排序方法适应于不同的应用环境和要求，在实际应用中， 选择合适的排序方法一般应考虑哪些因素。 要点： （1）若排序对稳定性有要求，只能在稳定算法中选择； （2）若排序节点数较少，可在简单排序方法中选择，如直接插入和直接选择排序方法；若节点初始状态基本有序，选用直接插入或冒泡排序法； （3）若节点数较大，选用复杂度为O（nlog n）排序方法； （4）有序表的合并排序，最好的方法是归并排序方法，但该方法的空间复杂度为O（n）； （5）基数排序只适用于字符串和整数这类有明显结构特征的关键字排序。 17. 一棵二叉排序树的结构如图所示，其中各结点的关键字依次为 32～40，请标出各结点的关键字。 30 图 一棵二叉排序树的结构 得到如图2所示的二叉排序树（中序序列是递增的）。 36 32 35 33 34 37 38 40 18. 有一棵二叉排序树按先序遍历得到的序列为： 39 (12,5,2,8,6,10,16,15,18,20)。回答以下问题： （1）画出该二叉排序树。 （2）给出该二叉排序树的中序遍历序列。 （3）求在等概率下的查找成功和不成功情况下的平均查找长度。 答：（1）先序遍历得到的序列为：(12,5,2,8,6,10,16,15,18,20)，中序序列是一个有序序列，所以为：(2,5,6,8,10,12,15,16,18,20)，由先序序列和中序序列可以构造出对应的二叉树，如图2所示。 （2）中序遍历序列为：2,5,6,8,10,12,15,16,18,20。 （3）ASL成功=(1×1+2×2+4×3+3×4)/10=29/10。 ASL不成功=(5×3+6×4/11=39/11。 12 5 2 6 8 10 15 16 18 20 图2 【评分说明】（1）小题占6分，（2）（3）小题各占2分。 19. 有一组关键字序列{66,,8,123,9,44,55,37,200,127,98}： （1）请将其调整成初始大根堆，并画出初始大根堆的树型表示。（5分） 31 （2）采用堆排序实现按关键字递增排序，请画出当有1个最大的关键字已放置到最终位置时，剩余关键字构成的大根堆。（5分） （5分 1 ） 初 始 大 根 堆 : （2）1个元素放入其最终位置后，剩余元素构成的大根堆： 5分 20. （8分）一棵二叉排序树的结构如图1所示，其中各结点的关 键字依次为32～40，请标出各结点的关键字。 图1 一棵二叉排序树的结构 21. （8分）已知序列{15,5,16,2,25,8,20,9,18,12}，画出采用 32 二路归并排序法对该序列作升序排序时的每一趟的结果。 （8分）答案： 采用二路归并排序法排序的各趟结果如图3所示。（每趟2分） 排序前: 15,5, 16,2, 25,8, 20,9, 18,12 length=1:5, 15,2, 16,8, 25,9, 20,12,18 length=2:2, 5,15, 16,8, 9, 20,25,12,18 length=4:2, 5,8, 9, 15,16,20,25,12,18 length=8:2, 5,8, 9, 12,15,16,18,20,25 排序后: 2, 5,8, 9, 12,15,16,18,20,25 图3 各趟排序结果 22. 已知有十个待排序的记录,其关键字分别 为:256,301,751,129,937,863, 742,694,076,438,给出用快速排序法进行从小到大排序的过程。 五、算法设计题 1. （15分）有两个递增有序表，所有元素为整数，均采用带头结点的单链表存储，结点类型定义如下： typedef struct node { int data; struct node *next; } LinkNode; 设计一个尽可能高效的算法，将两个递增有序单链表ha、 hb合并为一个递减有序单链表hc，要求算法空间复杂度为O(1)。（参见书P59） 2. 分析下列程序段的执行过程,并写出程序段的输出结果 (栈的元素类型 QElemType为char)。 33 void main( ) {
Queue Q; InitQueue(Q); char x=’e’, y=’c’;
EnQueue(Q, ’h’); EnQueue(Q, ’r’); EnQueue(Q, y); DeQueue(Q, x); EnQueue(Q, x); DeQueue(Q, x); EnQueue(Q, ’a’); While(!QueueEmpty(Q)) { DeQueue(Q, y); Printf(y); } Printf(x) } 输出结果：char 3. 给出冒泡排序算法思路,并简单写出冒泡排序算法。 4. 设计一个算法，在带头结点的单链表中，删除某个值为X的所有 结点。要求： （1）描述数据的存储结构。（2分） 34 （2）描述算法思想。（2分） （3）编写算法，并给出适当的注释。（6分） 数据的存储结构： typedef struct Lnode { Elemtype data; struct Lnode * next; } LNode 5. 下面程序段的功能实现数据x进栈，要求在下划线处填上正确的语句。（5分） typedef struct { int s[100]; int top; } sqstack; void push(sqstack &stack, int x) { if (stack.top==m-1) printf(“overflow”); else { 35 ____stack.top ++_______; ___stack.s[stack.top] = x_; } } 36
因篇幅问题不能全部显示，请点此查看更多更全内容