《数据结构与算法》考试试题.doc
广西工学院 2010 2011 学年第 1 学期考试试题考核课程 数据结构与算法 （ B 卷）考核班级 计y091096学生数 215 印数 230 考核方式 闭卷 考核时间 120 分钟【说明】试题满分共100分；考试时间为2个小时；一、选择题（每小题2分，共30分）1、数据的基本组成单位是 C 。 A、数据项 B、数据类型 C、数据元素 D、数据变量2、若进栈序列为1,2,3,4,假定进栈和出栈可以穿插进行，则可能的出栈序列是 D 。 A. 2,4,1,3 B. 3,1,4,2 C. 3,4,1,2 D. 1,2,3,43、循环队列用数组A0.m-1存放其元素值，已知其头尾指针分别是front和rear，则当前队列中的元素个数是 A 。 A. (rear-front+m) MOD m B. rear front + 1 C. rear-front-1 D. rear-front4、已知某二叉树的后序遍历序列是dabec,中序遍历序列是debac,它的前序遍历序列是 D 。 A. acbed B. deabc C. decab D.cedba5、已知某二叉树中，有n0个叶节点，n1个度为1的节点，n2个度为2的节点。则： n0= B 。A、n1+1 B、n2+1C、n1+n2 D、n1+2n26、高度为5的二叉树至多有 C 个节点。 A. 16 B. 32 C. 31 D. 107、设某程序的执行时间T(n)=3n2 + log2n + (2/3)n，则其时间复杂度为 B 。A、T(n)=O(3n2) B、T(n)=O(n2)C、T(n)=O (log2n) D、T(n)=O (2/3)n8、下面的序列中， A 是堆。 A、1，2，8，4，3，9，10，5 B、1，5，10，6，7，8，9，2C、9，8，7，6，4，8，2，1 D、9，8，7，6，5，4，3，79、用某种排序方法对线性表（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 。 A. 选择排序 B. 冒泡排序 C. 插入排序 D. 快速排序10、对于希尔排序来说，给定的一组原始数据为：49，38，65，97，76，13，27，49，55，04则第二趟排序后的结果为 C 。A. 04 13 27 49 49 38 55 65 76 97B. 04 13 27 38 49 49 55 65 76 97C. 04 27 13 49 38 55 49 65 97 76D. 13 27 49 55 04 49 38 65 97 7611、若一无向图是连通的，且其中有n个顶点和e条边，则必满足 C 。A、en B、en+1C、en-1 D、e2n+112、将一棵有100个节点的完全二叉树从根这一层开始，每一层上从左到右依次对节点进行编号，根节点的编号为1，则编号为49的节点的左孩子的编号为 A 。 A. 98 B. 99 C. 50 D. 4813、折半查找法使用于存储结构为 A 且按关键字排好序的线性表。 A. 顺序存储 B. 链式存储 C. 顺序存储或链式存储 D. 索引存储14、设有向图G有n个顶点，m条弧，则其邻接表中链上的节点个数为 B 。A、n B、mC、n+m D、n*m15、下列关于图的遍历的描述中，正确的是 C 。A、广度优先遍历序列是唯一的，而深度优先遍历序列是不唯一的。B、深度优先遍历序列是唯一的，而广度优先遍历序列是不唯一的。C、广度优先和深度优先遍历序列均可能是不唯一的。D、广度优先和深度优先遍历序列均是唯一的。二、判断题：（每小题1分，共10分）1、线性表采用链表方式和顺序表方式存储，执行插入和删除运算的时间复杂度都是O（n），因而两种存储方式的插入、删除运算所花费的时间相同。（ 错 ）2、数组可以看成是线性结构的一种推广，因此可以对它进行插入、删除等运算。（ 错 ）3、在顺序表中取出第i 个元素所花费的时间与i 成正比。（ 错 ）4、在栈满的情况下，不能作进栈运算，否则产生“上溢”。（ 对 ）5、线性表的唯一存储形式是链表。（ 错 ）6、对任意一个图，从它的某个顶点出发进行一次深度优先或广度优先搜索遍历可访问到该图的每个顶点。（ 错 ）7、由于希尔排序的最后一趟与直接插入排序过程相同，因此前者一定比 后者花费的时间多。（ 错 ）8、二叉排序树或者是一棵空树，或者是具有下列性质的二叉树：若它的左子树非空，则根节点的值大于其左孩子的值；若它的右子树非空，则根节点的值小于其右孩子的值。（ 错 ）9、在索引顺序表上实现分块查找，在等概率查找情况下，其平均查找长度不仅与表的个数有关，而且与每一块中的元素个数有关。（ 对 ）10、在执行某个排序算法的过程中，出现了待排序的值朝着最终排序序列位置相反的方向移动，则该算法是不稳定的。（ 错 ）三、简答题（每小题5分，共30分）1、 设散列函数为H（K）= K mod 7，散列表的地址空间为 O，6，开始时散列表为空，用线性探测法解决冲突，请画出依次插入键值23，14，9，6，30，12，18后的散列表。1、 0 1 2 3 4 5 61418239301262、 对下面两棵二叉树，分别画出它们的顺序存储结构。2、ABCDEFGIJKABCDEFIJ3、 给定一个整数集合3，5，6，9，12，画出其对应的一棵Huffman树。4、 设二叉树的顺序存储结构如下：1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20EAFDHCGIB 据其存储结构，画出该二叉树。 写出按前序、中序、后序遍历该二叉树所得的节点序列。5、 求下面无向带权图中从顶点V0到V7的最短路径和距离。6、 下面是冒泡排序算法，效率不高，请给出优化后的算法。void BubbleSort (int r, int n) for ( i = 1； i < n； i+ ) for (j = 1； j n-1； j+ ) if ( rj > rj+1 ) rj ÜÞ rj+1； 四、算法设计题（每小题15分，共30分，任选其中两题）1有一个单链表（不同结点的数据域值可能相同），其头指针为head，编写一个函数计算数据域为x的结点个数。链表节点结构定义如下：datanext2、设二叉树的根节点的指针为tree，每个节点的结构为：LsubtreedataRsubtree试写一算法，用于输出该二叉树中最大的节点值。3、编写一个算法从一给定的顺序存储结构的线性表A中删除元素值在x到 y（xy）之间的所有元素，要求以较高的效率来实现。 4、写出折半查找算法。广西工学院 2010 2011 学年第 1 学期考试试题考核课程 数据结构与算法 （ B 卷）考核班级 计y091096学生数 215 印数 230 考核方式 闭卷 考核时间 120 分钟参考答案一、选择题（每小题2分，共30分） CDADB CBAAC CAABC二、判断题：（共10分）×××× ××××三、简答题（每小题5分，共30分） 1、 0 1 2 3 4 5 6141823930126 2、ABCDEFGIJKABCDEFIJ3、 35 14 21 6 8 9 12 3 5 4、先序：EADCBFHGI； 中序：ABCDEFGHI； 后序：BCDAGIHFEEAFDCBHGI5、答：最短路径如下图所示： 从V0到V7的最短距离为：1+3+1+2+1=86、答：优化后的算法如下：void BubbleSort (int r, int n) exchange Ü TRUE; k Ü n 1; while ( exchange ) exchange Ü FALSE; for (i = 1； i k； i+ ) if ( ri > ri+1 ) ri ÜÞ ri+1； exchange Ü TRUE; k Ü k 1; 四、算法设计题（每小题15分，共30分） 1、解：遍历该链表的每个结点，每遇到一个结点，判断其值是否为x，是的话就计数。结点个数存储在变量n中。算法如下：int Counter(head, x) int n = 0; p <= head; while ( p != NULL ) if (p->data = x )n <= n + 1; p <= p -> next; return ( n ); 2、算法如下： max <= 0; void MaxNode(NODE *tree) if (tree) if (tree->data > max) max <= tree->data; MaxNode(tree->Lsubtree); MaxNode(tree->Rsubtree); 或者： max <= 0; void MaxNode(NODE *tree) if (tree) x <= tree->data; y <= MaxNode(tree->Lsubtree); z <= MaxNode(tree->Rsubtree); reyurn (max(x，y，z); else return (-); 3、算法如下：void Del(A, int n, x, y ) int i, k; for ( i = 1; i <= n; i+ ) if ( Ai >= x && Ai <= y ) Ai = 0; for ( i = n; i >= 1; i- ) if ( Ai = 0 ) for ( k=j; k <=(n-1); k+ ) Ak = Ak+1; n = n - 1; 4、算法如下：int BinSearch (sqlist r, int k, int n ) low Ü 1；high Ü n；find Ü 0; while ( low high and not find ) mid Ü (low + high) / 2 ; if (k < rmid. key) high Ü mid - 1; else if ( k > rmid. key ) low Ü mid + 1; else i Ü mid; find Ü 1; if ( not find ) i Ü 0; return ( i );
