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

1、广西工学院 2010 2011 学年第 1 学期考试试题考核课程 数据结构与算法 （ A 卷）考核班级 计y091096学生数 215 印数 230 考核方式 闭卷 考核时间 120 分钟【说明】试题满分共100分；考试时间为2个小时；一、选择题（每小题2分，共30分）1、设一序列为：1，2，3，4，5，6。通过栈操作不可能产生的序列为 B 。 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、，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 。A、3 B、4 C、5 D、6 考有

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

4、1234653、数组Q0.n-1作为一个环形队列，f为当前队头元素的前一位置，r 为队尾元素 的位置，假定队列中元素的个数总小于 n，计算队列中元素个数的公式是 D 。 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、2n

5、2+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 个结点。

6、A. 2i B. 2i-1 C. 2i+1 D. i考二叉树的特点：画一颗树来看看，结果自然就出来了，第i层结点个数的一般规律：第0层：20=1，第1层：21=2，第2层，22=4，因此，。第i层，2i7、对于n个节点的满二叉树，设叶节点数为m，分枝节点数为k，则 A 。 A. n=k+m B. k+m=2k C. m=k-1 D. n=2k-1考满二叉树的定义：满二叉树中，除了叶子结点，就是分支结点。答案为A8、在已知待排序文件已基本有序的前提下，效率最高的排序方法是（ A ） A直接插入排序 B直接选择排序C快速排序 D归并排序考排序的效率和特点：9、用某种排序方法对线性表（25，84，2

7、1，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

8、 Sort)1. 基本思想：每次将一个待排序的数据元素，插入到前面已经排好序的数列中的适当位置，使数列依然有序；直到待排序数据元素全部插入完为止。2. 排序过程： 【示例】：初始关键字 49 38 65 97 76 13 27 49J=2(38) 38 49 65 97 76 13 27 49J=3(65) 38 49 65 97 76 13 27 49J=4(97) 38 49 65 97 76 13 27 49J=5(76) 38 49 65 76 97 13 27 49J=6(13) 13 38 49 65 76 97 27 49J=7(27) 13 27 38 49 65 76 97

9、49J=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第六

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

11、：49 13 13 13 13 13 13 13 38 49 27 27 27 27 27 2765 38 49 38 38 38 38 3897 65 38 49 49 49 49 4976 97 65 49 49 49 49 4913 76 97 65 65 65 65 6527 27 76 97 76 76 76 7649 49 49 76 97 97 97 97 四、快速排序（Quick Sort）1. 基本思想：在当前无序区R1.H中任取一个数据元素作为比较的"基准"(不妨记为X)，用此基准将当前无序区划分为左右两个较小的无序区：R1.I-1和RI+1.H，且左边

12、的无序子区中数据元素均小于等于基准元素，右边的无序子区中数据元素均大于等于基准元素，而基准X则位于最终排序的位置上，即R1.I-1X.KeyRI+1.H(1IH)，当R1.I-1和RI+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向右扫描，位置不变，第四次交换后

13、 27 38 13 49 76 97 65 49J向左扫描 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 6576 97三趟排序之后 13 27 38 49 49 6576 97最后的排序结果 13 27 38 49 49 65 76 97 各趟排序之后的状态五、堆排序(Heap Sort)1. 基本思想：堆排序是一树形选择排序，在排序过程中，将R1.N看成是一颗完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和

14、孩子结点之间的内在关系来选择最小的元素。2. 堆的定义: N个元素的序列K1,K2,K3,.,Kn.称为堆，当且仅当该序列满足特性：KiK2i Ki K2i+1(1 I N/2)堆实质上是满足如下性质的完全二叉树：树中任一非叶子结点的关键字均大于等于其孩子结点的关键字。例如序列10,15,56,25,30,70就是一个堆，它对应的完全二叉树如上图所示。这种堆中根结点（称为堆顶）的关键字最小，我们把它称为小根堆。反之，若完全二叉树中任一非叶子结点的关键字均大于等于其孩子的关键字，则称之为大根堆。3. 排序过程：堆排序正是利用小根堆（或大根堆）来选取当前无序区中关键字小（或最大）的记录实现排序的。

15、我们不妨利用大根堆来排序。每一趟排序的基本操作是：将当前无序区调整为一个大根堆，选取关键字最大的堆顶记录，将它和无序区中的最后一个记录交换。这样，正好和直接选择排序相反，有序区是在原记录区的尾部形成并逐步向前扩大到整个记录区。【示例】：对关键字序列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 07C. 19 07 15 28 23 21 03 D. 03 07 15 19 21 23 28还是要熟悉快速排序的过程：D答案中13应改为0

16、3，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(aj>aj+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(aj>aj+1)则F=1；交换

17、if(！f)break;/如果第一趟排序，发现已经是有序，则退出了，只比较了第一趟的11次 （这一题有争议，我的意见是看题目的意思，趋向于答案C）12、在一个有n（n1）个顶点的有向图中，边数最多为 C 。1245A、n-1 B、n C、n(n-1) D、n(n-1)/2有向图的特征：画一个图，就得到答案了。4个结点，12条边13、在有n个结点的二叉链表中，值为非空的链域的个数为 A 。A. n-l B. 2n-l C. nl D. 2n1二叉链表的特征：n个结点，则链指针有所指的为n-1,:2叉链表，则总链域个数2n，头指针指向根结点，其余n-1个结点，共需要n-1个指针域（非空），注意，空

18、链域个数：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的出度，列才为入度（原有答案出错）。FGAEDCB15、从下图中顶点A出发，采用深度优先遍历，则下列各顶点序列中，不是遍历结果的是 C 。A、ABCDEGF B、ABFDCGE C、AGDEBFC D、AFDGECB图的深度优先和广度优先都要弄清楚。深度优先为相连访问（注意退

19、回到还有连接结点没有访问过的那个结点上，广度优先为层次访问,先访问的结点其子树也先访问（子树访问无次序，仅对下层访问有影响）（最好先把层次图画出）。A->B->C->D->E>G(所有相连结点已访问)->退回E->退回D->FA->B->F->D->CàG->EA->G->D->E(所有相连结点已访问)-> 退回D->只能访问F或CA->F->D->G->E(所有相连结点已访问)->退回G->E->退回G->C->B 二、判

20、断题（每小题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+14已知完全二叉

21、树的第八层有8个结点，则其叶子结点数是68。（ ）注意是根结点为第1层，第7层该有26=64个结点，第八层有8个结点用去第7层的4个结点，所以叶子结点总数：64-4+8=68。有时间的话， 画一下图也可以 5有向图用邻接矩阵表示后，顶点i的出度等于第i行中非0且非的元素个数。（ ）6图G的某一最小生成树的代价一定小于其他生成树的代价。（ × ）最小生成树不止一颗，所以，。可以等于 7若一棵二叉树的任一非叶子结点的度为2，则该二叉树为满二叉树。（ × ） 画一下，就知道答案了： 8二叉树只能采用二又链表来存储。（ × ）顺序存储结构（数组形式）和链式存储结构（二叉链

22、表）9只有在初始数据为逆序时，冒泡排序所执行的比较次数最多。（ ）冒泡排序在最坏情况是初始序列为“逆序”，需要进行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，234567第1步第2步6712第4步9134510第3步192513151833第5步45

23、10第6步192342996712第7步2513151833586712第8步1518510234以上是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、一棵二叉树的先序、中序和后序序列分别如下，其中有一部分未显示出来，试求出空格处的内容，并画出该

24、二叉树。 先序： 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 B4） 从中序D B知道D是B的左孩子，K F I是B的右子树上结点5） 从后序F B知道F是B的右子树上根结点，根据中序K F I知道K是左，I是右先序序列

25、得出： 先序： A B D F K I（前为左和后为右） C E H J G6） 从先序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的右。BDFKICGEHJA注意下面的考法： 3、设有序列：11，30，5，6，23，

26、17，29，37，4，13，33，用希尔排序法进行排序，设d1=5，d2=3，d3=1。给出每一趟排序的结果。4、下列程序段中，语句（1），（2），（3）执行的次数为多少？ for (i=1; im; i+) x Ü x + 2; . .(1) for (j=1; jn; j+) y Ü y + 2; .(2) for (k=1; kj; j+) z Ü x + y; .(3) 5、请画出下面的无向带权图的最小生成树：6、下面是简单选择排序算法，效率不高，请给出优化后的算法。void SelectSort(int r, int n) for ( i Ü

27、1； i n-1； i+ ) for ( j Ü i+1； j n； j+ ) if ( rj < rk ) ri ÜÞ rk； 四、算法设计题（每小题15分，共30分，任选其中两题） 1、试写出计算二叉树节点数目的算法。 2、编写一个算法，从一给定的数组A中删除元素值在x到 y（xy）之间的所有元素（假定数组中有n个元素）。算法头部约定如下：void Delete( A, n, x, y ) 3、对于任意给定的一个线性表：L=(a1,a2,an),写出构造一个链表的算法。节点类型及其算法头部约定如下：struct node ElemType data； s

28、truct node *next； ； typedef struct node NODE；NODE *CreateLinkList(int n) 4、设有两个有序关键字表S1，S2。S1和S2存储在数组rlow,high中，Sl放在rlow，mid中，S2放在rmid+1，high中，如下图所示。现在要把S1，S2归并，请写出归并排序算法。算法头部约定为：void Merge(r, low, mid, high)low mid mid+1 high广西工学院 2010 2011 学年第 1 学期考试试题考核课程 数据结构与算法 （ A 卷）考核班级 计y091096学生数 215 印数 230

29、 考核方式 闭卷 考核时间 120 分钟参考答案一、选择题（每小题2分，共30分）BADAC AAADD CCCCC二、判断题：（每小题1分，共10分） ×××××三、简答题（每小题5分，共30分） 1、 带权路径长度WPL=299 100 42 58 19 23 25 33 9 10 12 13 15 18 4 5 6 7 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

30、A B C D F E G K I H J 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，374、（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 ( rj < rk ) k Ü j； if ( k i )ri ÜÞ rk； 四、算法设计题（每小题15分，共30分）1、算法如下：counter <= 0;void Numbers(NODE *tree) if (tree) counter+; Numbers(