广西工学院《数据结构与算法》考试试题2010(A)-答案解析最新

广西工学院 2010 — 2011 学年第 1 学期考试试题

考核课程 数据结构与算法 （ A 卷）考核班级 计y091~096 学生数 215 印数 230 考核方式 闭卷 考核时间 120 分钟

【说明】试题满分共100分；考试时间为2个小时；

一、选择题（每小题2分，共30分）

1、设一序列为：1，2，3，

4，

5，6。通过栈操作不可能产生的序列为。 A、3，2，5，6，4，1 B、1，5，4，6，2，3 C、2，4，3，5，1，6 D、4，5，3，6，2，1

这题考栈的性质:先进先出。进栈的序号是1最先6最后，但不规定要同时进，然后再出栈。可以1进去，1出来，然后2进去，2出来，也可以1进去，2进去，2出来，1出来。

按照这个原则，先看：A）是可能的，进出栈情况如下：1,2,3依次进栈，3出栈2出栈；4,5进栈，5出栈；6进栈，6出栈；4再出栈，最后是1出栈。

B）不可能：原因：1进栈1出栈；2,3,4,5进栈，5出栈4出栈；6再进栈，6出栈，此时3在栈顶，2不可能比3还要先出栈。其他的答案依此可以得出。

2、设有向图G=（V，E），V={1，2，3，4，5，6}；E={<1，2>，<2，1>，<6，3>，

<2，3>，<5，6>，<2，4>，<3，5>}。则其强连通分量个数为 A、3 B、4 C、5 D、6

考有向图中的强联通分量问题：首先要把强联通分量概念弄清楚：有向图强连通分量在有向图G中，如果两个顶点vi,vj间（vi<>vj）有一条从vi到vj的有向路径，同时还有一条从vj到vi的有向路径，则称两个顶点强连通(strongly connected)。如果有向图G的每两个顶点都强连通，称G是一个强连通图。非强连通图有向图的极大强连通子图，称为强连通分量(strongly connected components)。记主要特征：强联通分量图中两两都可达，也可见下图实例。按照这个定义，得到图G 中的强联通分量共3个： <1,2>,<3,5,6>,<4>

3、数组Q[0..n-1]作为一个环形队列，f为当前队头元素的前一位置，r 为队尾元素 的位置，假定队列中元素的个数总小于 n，计算队列中元素个数的公式是 。

A. r-f B. n+f-r C. n+r-f D. (n+r-f) mod n

考循环队列的定义、性质和特点：

所以，由于可以循环，f和r不一定哪个在前，哪个在后，需要用取余来判断。答案是最后一个。既然r和f不知道哪个大，那么，前3个答案都有可能得到非法数据：小于0或者大于n，因此，也可以排除前3个选项。

4、设一棵Huffman树中度为2的节点数为n2，则该树的总节点数为 D 。

A、2n2 B、n2+1 C、4n2 D、2n2+1

考Huffman树的特点和性质：首先是了解Huffman树的特点（也是一颗二叉树），如下图，其次，了解度的概念：结点的度指结点的孩子结点个数，例如度为2 就是有2个孩子结点的结点；叶子结点就是度为0的结点，没有孩子结点的结点.

按照这个概念，度为2的结点树为n2,即为非叶子结点，Huffman树中叶子结点个数是非结点个数+1，所以总结点个数：n2+n2+1

从左边的树例子中就可以看出来。

5、按照二叉树的定义，具有3个节点的二叉树有 C 种。 A. 3 B. 4 C. 5 D. 6

考二叉树的定义。

画一画就可以得出答案了：

6、有一棵非空的二叉树（第0层为根结点），其第i层上至多有 A 个结点。 A. 2i B. 2i-1 C. 2i+1 D. i

考二叉树的特点：画一颗树来看看，结果自然就出来了，第i层结点个数的一般规律：

012i

第0层：2=1，第1层：2=2，第2层，2=4，因此，。。。第i层，2

7、对于n个节点的满二叉树，设叶节点数为m，分枝节点数为k，则 A 。 A. n=k+m B. k+m=2k C. m=k-1 D. n=2k-1

考满二叉树的定义：满二叉树中，除了叶子结点，就是分支结点。答案为

A

8、在已知待排序文件已基本有序的前提下，效率最高的排序方法是（ A ） A．直接插入排序 B．直接选择排序

C．快速排序 D．归并排序

考排序的效率和特点：

9、用某种排序方法对线性表（25，84，21，47，15，27，68，35，20）进行排序时， 各数据元素的变化情况如下：

（1） 25 84 21 47 15 27 68 35 20 （2） 20 15 21 25 47 27 68 35 84 （3） 15 20 21 25 35 27 47 68 84 （4） 15 20 21 25 27 35 47 68 84 那么，所采用的排序方法是 D 。

A. 选择排序 B. 希尔排序 C. 插入排序 D. 快速排序

了解常用排序算法的过程：

给出的过程，符合快速排序的特点。

把几种排序的特点都熟悉，对照一下，就得出答案了：不是插入，不是选择，不是冒泡，剩下的就是快速了。

一、插入排序(Insertion Sort) 1. 基本思想：

每次将一个待排序的数据元素，插入到前面已经排好序的数列中的适当位置，使数列依然有序；直到待排序数据元素全部插入完为止。 2. 排序过程： 【示例】：

[初始关键字] [49] 38 65 97 76 13 27 49 J=2(38) [38 49] 65 97 76 13 27 49 J=3(65) [38 49 65] 97 76 13 27 49 J=4(97) [38 49 65 97] 76 13 27 49 J=5(76) [38 49 65 76 97] 13 27 49 J=6(13) [13 38 49 65 76 97] 27 49 J=7(27) [13 27 38 49 65 76 97] 49 J=8(49) [13 27 38 49 49 65 76 97]

二、选择排序 1. 基本思想：

每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。 2. 排序过程： 【示例】：

初始关键字 [49 38 65 97 76 13 27 49] 第一趟排序后 13 ［38 65 97 76 49 27 49] 第二趟排序后 13 27 ［65 97 76 49 38 49] 第三趟排序后 13 27 38 [97 76 49 65 49] 第四趟排序后 13 27 38 49 [49 97 65 76] 第五趟排序后 13 27 38 49 49 [97 97 76] 第六趟排序后 13 27 38 49 49 76 [76 97] 第七趟排序后 13 27 38 49 49 76 76 [ 97] 最后排序结果 13 27 38 49 49 76 76 97

三、冒泡排序(BubbleSort) 1. 基本思想：

两两比较待排序数据元素的大小，发现两个数据元素的次序相反时即进行交换，直到没有反序的数据元素为止。 2. 排序过程：

设想被排序的数组R［1..N］垂直竖立，将每个数据元素看作有重量的气泡，根据轻气泡不能在重气泡之下的原则，从下往上扫描数组R，凡扫描到违反本原则的轻气泡，就使其向上"漂浮"，如此反复进行，直至最后任何两个气泡都是轻者在上，重者在下为止。 【示例】：

49 13 13 13 13 13 13 13 38 49 27 27 27 27 27 27 65 38 49 38 38 38 38 38 97 65 38 49 49 49 49 49 76 97 65 49 49 49 49 49 13 76 97 65 65 65 65 65 27 27 76 97 76 76 76 76 49 49 49 76 97 97 97 97

四、快速排序（Quick Sort） 1. 基本思想：

在当前无序区R[1..H]中任取一个数据元素作为比较的"基准"(不妨记为X)，用此基准将当前无序区划分为左右两个较小的无序区：R[1..I-1]和R[I+1..H]，且左边的无序子区中数据元素均小于等于基准元素，右边的无序子区中数据元素均大于等于基准元素，而基准X则位于最终排序的位置上，即R[1..I-1]≤X.Key≤R[I+1..H](1≤I≤H)，当R[1..I-1]和R[I+1..H]均非空时，分别对它们进行上述的划分过程，直至所有无序子区中的数据元素均已排序为止。

2. 排序过程： 【示例】：

初始关键字 [49 38 65 97 76 13 27 49］

第一次交换后 ［27 38 65 97 76 13 49 49］ 第二次交换后 ［27 38 49 97 76 13 65 49］

J向左扫描，位置不变，第三次交换后 ［27 38 13 97 76 49 65 49］ I向右扫描，位置不变，第四次交换后 ［27 38 13 49 76 97 65 49］ J向左扫描 ［27 38 13 49 76 97 65 49］ （一次划分过程）

初始关键字 ［49 38 65 97 76 13 27 49］

一趟排序之后 ［27 38 13］ 49 ［76 97 65 49］

二趟排序之后 ［13］ 27 ［38］ 49 ［49 65］76 ［97］ 三趟排序之后 13 27 38 49 49 ［65］76 97 最后的排序结果 13 27 38 49 49 65 76 97 各趟排序之后的状态

五、堆排序(Heap Sort) 1. 基本思想：

堆排序是一树形选择排序，在排序过程中，将R[1..N]看成是一颗完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系来选择最小的元素。

2. 堆的定义: N个元素的序列K1,K2,K3,...,Kn.称为堆，当且仅当该序列满足特性： Ki≤K2i Ki ≤K2i+1(1≤ I≤ [N/2])

堆实质上是满足如下性质的完全二叉树：树中任一非叶子结点的关键字均大于等于其孩子结点的关键字。例如序列10,15,56,25,30,70就是一个堆，它对应的完全二叉树如上图所示。这种堆中根结点（称为堆顶）的关键字最小，我们把它称为小根堆。反之，若完全二叉树中任一非叶子结点的关键字均大于等于其孩子的关键字，则称之为大根堆。 3. 排序过程：

堆排序正是利用小根堆（或大根堆）来选取当前无序区中关键字小（或最大）的记录实现排序的。我们不妨利用大根堆来排序。每一趟排序的基本操作是：将当前无序区调整为一个大根堆，选取关键字最大的堆顶记录，将它和无序区中的最后一个记录交换。这样，正好和直接选择排序相反，有序区是在原记录区的尾部形成并逐步向前扩大到整个记录区。 【示例】：对关键字序列42，13，91，23，24，16，05，88建堆

10、对以下四组原始数据用快速排序法排序， D 组的情况速度最慢。

A. 19 23 03 15 07 21 28 B. 23 21 28 15 19 03 07 C. 19 07 15 28 23 21 03 D. 03 07 15 19 21 23 28

还是要熟悉快速排序的过程：D答案中13应改为03，4组都一样的数据，序列不一样。

11、对于已排好序的、具有12个数据元素的线性表，采用冒泡排序方法排序时最少需

要 比较。

A. 1 B. 144 C. 11 D. 66

考冒泡排序法：熟悉算法过程（最好是把程序写出来），就得出答案了。

For(i=0;i<n-1;i++) For(j=0;j<n-1-I;j++) If(a[j]>a[j+1]则交换

注意：如果按照一般的冒泡排序，则答案是：D：11+10+。。。+1=66 但稍微优化一下冒泡排序法，答案是C Int f=0;

For(i=0;i<n-1;i++) { For(j=0;j<n-1-I;j++)

If(a[j]>a[j+1])则{F=1；交换} if(！f)break;

//如果第一趟排序，发现已经是有序，则退出了，只比较了第一趟的11次

}

（这一题有争议，我的意见是看题目的意思，趋向于答案C）

12、在一个有n（n≥1）个顶点的有向图中，边数最多为

A、n-1 B、n n(n-1)/2

有向图的特征：画一个图，就得到答案了。 4个结点，12条边

C、n(n-1) D、

13、在有n个结点的二叉链表中，值为非空的链域的个数为 A 。

A. n-l B. 2n-l C. n＋l D. 2n＋1

二叉链表的特征：n个结点，则链指针有所指的为n-1,:2叉链表，则总链域个数2n，头指针指向根结点，其余n-1个结点，共需要n-1个指针域（非空），注意，空链域个数：2n-（n-1）=n+1 (原有答案出错)

14、带权有向图G用邻接矩阵A存储，则顶点i的入度等于A中 D 。 A. 第i行非∞的元素之和 B. 第i列非∞的元素之和

C. 第i行非∞且非0的元素个数 D. 第i列非∞且非O的元素个数

有向图中，结点i的入度就是指向 i结点的弧的条数,而邻接矩阵是行数据中非0非无穷元素个数为i的

出度，列才为入度（原有答案出错）。

15、从下图中顶点A出发，采用深度优先遍历，则下列各顶点序列中，不是遍历结果的

是

A、ABCDEGF B、ABFDCGE C、AGDEBFC D、AFDGECB

图的深度优先和广度优先都要弄清楚。深度优先为相连访问（注意退回到还有连接结点没有访问过的那个结点上，广度优先为层次访问,先访问的结点其子树也先访问（子树访问无次序，仅对下层访问有影响）（最好先把层次图画出）。

A->B->C->D->E>G(所有相连结点已访问)->退回E->退回D->F A->B->F->D->C G->E

A->G->D->E(所有相连结点已访问)-> 退回D->只能访问F或C

A->F->D->G->E(所有相连结点已访问)->退回G->E->退回G->C->B

二、判断题（每小题1分，共10分）√√√√√ ×××××

1．在循环队列中，若尾指针Rear大于头指针Front，则其元素个数为Rear - Front。（ √ ）

首先是队列特点：先进先出，队头出，队尾进，当队尾大于队头时，说明进的比出的多，此时元素个数为Rear – Front，大家可以画图帮助理解。

2．将一棵树转换为二叉树表示后,该二叉树的根结点没有右子树。（ √ ）

要了解树转换为二叉树的步骤，

3． 在用k叉链表示的n个结点的k叉树中,空的链指针有n*(k-1)+1个。（ √ ）

总共kn个链域，n个结点,非空链域n-1个，则空的为：kn-(n-1)=kn-n+1

4．已知完全二叉树的第八层有8个结点，则其叶子结点数是68。（√ ） 注意是根结点为第1层，第7层该有26=64个结点，第八层有8个结点用去第7层的4个结点，所以叶子结点总数：64-4+8=68。有时间的话， 画一下图也可以

5．有向图用邻接矩阵表示后，顶点i的出度等于第i行中非0且非∞的元素个数。（ √ ）

6．图G的某一最小生成树的代价一定小于其他生成树的代价。（ × ） 最小生成树不止一颗，所以，。。。可以等于 7．若一棵二叉树的任一非叶子结点的度为2，则

该二叉树为满二叉树。（ × ）

画一下，就知道答案了：

8．二叉树只能采用二又链表来存储。（ × ） 顺序存储结构（数组形式）和链式存储结构（二叉链表）

冒泡排序在最坏情况是初始序列为

“逆序”，需要进行N-1次排序，进行的比较次数为：∑（i-1），下标从n

到2，即 n(n-1)/2.

10．堆排序中，在输出一个根之后的调整操作中，“临时根”结点的值将被调到“叶

子结点”上。（ × ） 了解堆排序过程

三、简答题（每小题5分，共30分）

1、对下面给出的数据序列，构造一棵哈夫曼树，并求出其带权路径长度。 4，5，6，7，1O，12，15，18，23

4，5，6，7，1O，12，15，18，

23

9

第1步

第2步

第5步

第8步

以上是Huffman树的构造过程，考试时需要先在草稿上一步一步构造，只需要把最后的Huffman树写出来就可以。每个叶子结点的路径长度就是从根结点开始到叶子结点的树枝条数，如4的路径长度是4,23的是2等。 叶子的带权路径长度=权值*路径长度

树的带权路径长度=所有叶子结点的带权路径长度之和 WPL=4*4+5*4+10*3+23*2+6*4+7*4+12*3++15*3+18*3=。。。。 算一下，就知道结果了。

2、一棵二叉树的先序、中序和后序序列分别如下，其中有一部分未显示出来，试求

出空格处的内容，并画出该二叉树。

先序： A B D F K I（前为左和后为右） C E H J G 中序：D B K F I (左) A（右） E J C G 后序： D K I F B H J E G C A(根)

步骤：先序（根-左-右）， 中序（左-根-右）， 后序（左-右-根）： 1） 从后序 K F B H J G A（根），知道A是根结点

2） 从中序，知道左子树和右子树D K F I （左）A（右） E J C 3） 从先序知道B是左子树的根结点A B

4） 从中序D B知道D是B的左孩子，K F I是B的右子树上结点

5） 从后序F B知道F是B的右子树上根结点，根据中序K F I知道K是左，I是右 先序序列得出：

先序： A B D F K I（前为左和后为右） C E H J G

6） 从先序C E知道A的右子树根结点是C，从中序得知C只有一个右结点。 从先序C E H J G得知必为G，再结合先序，中序序列得出 中序: D B K F I (左) A（右） H E J C G 然后，后序序列得出：

后序： D K I F B H J E G C A(根) 这树就出来了:

B为A左子树的根，D为B的左子树，F为B的右子树的根，K为F的左，I为F的右。 C为A右子树的根，G为C的右子树，E为C的左子树的根，H为E的左，J为E的右。

A

F

H

J G

K

注意下面的考法：

3、设有序列：{11，30，5，6，23，17，29，37，4，13，33}，用希尔排序法进行

排序，设d1=5，d2=3，d3=1。给出每一趟排序的结果。

4、下列程序段中，语句（1），（2），（3）执行的次数为多少？ for (i=1; i≤m; i++) {

x x + 2; ............................. .(1) for (j=1; j≤n; j++) {

y y + 2; ........................(2) for (k=1; k≤j; j++)

z x + y; ...................(3) } }

5、请画出下面的无向带权图的最小生成树：

6、下面是简单选择排序算法，效率不高，请给出优化后的算法。

void SelectSort(int r[], int n) {

for ( i 1； i ≤ n-1； i++ )

for ( j i+1； j ≤ n； j++ ) if ( r[j] < r[k] )

r[i] r[k]；

}

四、算法设计题（每小题15分，共30分，任选其中两题） 1、试写出计算二叉树节点数目的算法。

2、编写一个算法，从一给定的数组A[]中删除元素值在x到 y（x≤y）之间的所有

元素（假定数组中有n个元素）。算法头部约定如下：

void Delete( A[], n, x, y )

3、对于任意给定的一个线性表：L=(a1,a2, ,an),写出构造一个链表的算法。节点

类型及其算法头部约定如下：

struct node

{

ElemType data； struct node *next； }；

typedef struct node NODE；

NODE *CreateLinkList(int n)

4、设有两个有序关键字表S1，S2。S1和S2存储在数组r[low,high]中，Sl放在r［low，

mid］中，S2放在r［mid+1，high］中，如下图所示。现在要把S1，S2归并，请写出归并排序算法。算法头部约定为：void Merge(r[], low, mid, high)

广西工学院 2010 — 2011 学年第 1 学期考试试题

考核课程 数据结构与算法 （ A 卷）考核班级 计y091~096 学生数 215 印数 230 考核方式 闭卷 考核时间 120 分钟

参考答案

一、选择题（每小题2分，共30分）

BADAC AAADD CCCCC 二、判断题：（每小题1分，共10分） √√√√√ ××××× 三、简答题（每小题5分，共30分） 1、 带权路径长度WPL=299

2、 先序： A B D F K I C E H J G 或者：A D K J

中序： D B K F I A H E J C G 或者：B H G

后序： D K I F B H J E G C A 或者：D I E C

3、 11，29，5，4，13，17，30，37，6，23，33 4，13，5，11，29，6，23，33，17，30，37 4，5，6， 11，17，13，23，30，29，33，37 4、（1）m （2）m*n （3）m*n*n*（n+1）/2 5、答：该图的最小生成树为：

6、答：该算法经优化后的形式如下：

void SelectSort(int r[], int n)

{

for ( i 1； i ≤ n-1； i++ ) {

k i；

for ( j i+1； j ≤ n； j++ ) if ( r[j] < r[k] ) k j； if ( k ≠ i )

r[i] r[k]；

} }

四、算法设计题（每小题15分，共30分）

1、算法如下：

counter <= 0;

void Numbers(NODE *tree) {

if (tree) {

counter++;

Numbers(tree->Lsubtree); Numbers(tree->Rsubtree); } }

2、本题的算法思想是：先将A[]中所有元素值在x≤y之间的元素置成一个特殊的

值（如0），并不立即删除它们，然后从最后向前依次扫描，对于该特殊值的元素便移动其后面的元素将其删除，这种算法比每删除一个元素后立即移动其后元素效率要高一些。实现本题功能的过程如下： void Delete( A[], n, x, y )

{

for ( i 1; i ≤ n; i++ )

if ( A[i] ≥ x && A[i] ≤ y ) A[i] 0;

for ( i n; i ≥ 1; i-- ) if ( A[i] == 0 ) {

for ( k j; k ≤(n-1); k++ ) A[k] A[k+1]; n n - 1; } } 3、算法如下：

NODE *CreateLinkList(int n) {

q (NODE *)malloc(sizeof(NODE));

scanf( an );

q -> data an; q -> next NULL;

for (i=n-1; i≥1; i--) {

p (NODE *)malloc(sizeof(NODE));

scanf( ai );

p -> data ai; p -> next q;

q p;

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