浙工大数据结构期末试卷.doc

浙江工业大学20062007年数据结构试卷A 浙江工业大学2006/2007学年数据结构试卷B(注意：所有的答案写在答题纸上，否则成绩无效)班级: 学号: 姓名: 1. 单选题. (20 * 1 = 20分)(1) 数据结构是指（）A) 数据的组织形式 B) 数据类型 C) 数据存储结构 D) 数据定义(2) 在一个具有n个元素的有序向量表中插入一个新结点并依然有序的时间复杂度是（）A) O(1) B) O(n) C) O(n2) D) O(nlogn)(3) 表达式 f+(a+b)/(d-e)*2 的后缀是 （）.A) ab+f+de-/2* B) ab+de-/f+2* C) fab+de-2*/+ D) fab+de-/2*+(4) 以下的数据结构中，不是线性结构的是（） A) 栈 B) 队列 C) 图 D) 字符串(5) 栈和队列的共同特点是() .A) 都是先进后出 B) 都是先进先出 C) 只允许在端点处插入和删除 D) 没有共同点(6) 二分法查找适合 ( ) .A) 有序序列 B) 无序序列 C) A和B D) 既不是A也不是B(7) 根据二叉树的定义，已知3个结点的前序序列，刚该树有几种可能( ).A) 6 B) 5 C) 4 D) 3(8) 下列应用中，需使用队列的是（ ）A）实现递归算法 B）实现广度优先搜索C）实现表达式计算 D）实现深度优先搜索(9) 用某种排序方法对线性表( 25, 38, 21, 47, 15, 27, 68, 35, 20) 进行排序，元素序列的变化情况如下 (1) 25, 38, 21, 47, 15, 27, 68, 35, 20 (2) 20, 15, 21, 25, 47, 27, 68, 35, 38(3) 15, 20, 21, 25, 38, 27, 35, 47, 68 (4) 15, 20, 21, 25, 35, 27, 38, 47, 68则采用的排序方法是（）A) 选择排序 B) 冒泡排序 C) 归并排序 D) 快速排序(10) 以下的四个二叉树中，( ) 是二叉排序树.67328829816732582931A) B)FGAHEC) DFBDAZ)(11) 在以下的序列中，（ ） 是最大堆 A)86, 67, 34, 72, 56, 53, 29 B) 86, 72, 34, 48, 56, 53, 29 C)92, 72, 50, 48, 56, 53, 29 D) 86, 72, 53, 48, 56, 29, 34(12) 散列表长 m = 15, 散列函数hash(key) = key % 13, 表中已经有了4个结点, 关键字分别是18, 32, 59, 73, 其余地址为空，如是采用开地址散列处理冲突，那么关键字109的结点地址为（ ）A) 8 B) 9 C) 5 D) 4(13) 有一个有序表为( 5,7,11,19,37,41,45,62,75,77,93,95,100),当采用二分法查找值为93的结点时，（ ）次比较后查找成功。 A) 1 B) 2. C) 4. D) 8(14)如果遍历的方式是根，右子树，左子树，那么遍历图的二叉树序列为（ ）.A) 5, 1, 7, 4, 9 B) 5, 1, 4, 7, 9 C) 5, 7, 9, 1, 4 D) 4, 1, 5, 9, 75 71 94(15) 将一棵有99个结点的完全二叉树按顺序编号，根结点的编号为0,那么编号为49的结点的右子结点的编号为( ) . A) 98 B) 99 C) 100 D) 不存在(16) 已知如下的两种序列，则不可能确定一棵二叉树( )A) 先序序列和后序序列 B) 先序序列和中序序列 C) 中序序列和后序序列 D) 以上都不对(17) 下列排序法中最稳定的是（ ）（A）堆排序法（B）插入排序法（C）选择排序法 （D）快速排序法(18) 如下图，从顶点1出发，按照深度优先规则遍历，可能得到的序列为( ) 7216453A) 1352467 B) 146275 C) 126347 D) 1354672(19) 设无向图G中顶点数为n, 则图G最多有( ) 条边A) n. B) n-1 C) n(n-1)/2 D) n(n-1)(20) 已知有向图G = (V, E), 其中 V = V1, V2, V3, V4, V5, V6, V7， E=, , , , , , , ,，G的拓扑序列是( ) A) V1, V3, V4, V6, V2, V5, V7 B) V1, V3, V5, V6, V4, V2, V7 C) V1, V3, V4, V5, V2, V6, V7 D) V1, V2, V5, V3, V4, V6, V72. 填空题 (1) 如图所示的二叉树，写出不同的遍历顺序的结果 (3分)A) 中序遍历. _ (21)_ B) 先序遍历. _ (22)_ C) 后序遍历. _ (23)_ (2) 求如下程序段的时间复杂度，采用大O表示。_(24)_ (2 分) int i,j,k; for( i = 0;in;i+) for (j = 0;jn;j+) cij = 0.0; for (k = 0; kn; k+) cij = Aik * Bkj; (3) 如下图AVL树，请分别插入关键字的结点V_(25)_, 插入Y _(26)_. 注意：两个结点是是单独插入的。 (6分)CBWUX(4) 设要将序列(Q, H, C, Y, P, A, M, S, R, D, F, X) 中关键字按字母序的升序重新排序，则冒泡排序第二趟排序的结果是_(27)_, 建立初始最大堆的结果是_(28)_,采用归并排序，第二趟排序的结果是_(29)_ . (6分)(5) 某图的邻按矩阵如下图，从邻接矩阵可以看出，该图有_(30)_个顶点，如果是有向图，该图有_(31)_条边，如果是无向图，则有_(32)_条边. (3分)0 1 01 0 10 1 0A = 3、求解题：已知带权图如图所示，画出它的邻接表（5分）4、设待排序的关键码序列为12，2，16，30，28，10，20，6，18，试写出使用插入排序的前5趟结果。（5分） 5、已知某二叉树前序序列为ABECDFGHIJ，中序序列是EBCDAFHIGJ，试画出该二叉树。（5分）6. 将关键码序列为C, B, X, W, U, V, Y依次插入到一个空的二叉排序树中，画出每次插入完成后的二叉排序树 （5分）7. 有7个关键码的开地址散列向量 32,13,49,55,22,39,20，散列函数为取余运算（即%7,如关键码32的向量地址为32%7 = 4），采用线性开地址散列解决冲突，试完成按以上关键码顺序插入到散列向量之后的结果。（5分）01234568. 已经带权的无向图如下，请模拟用克鲁斯卡尔 (Kruskal) 算法生成最小生成树的详细结果。（5分）28101610145182625241243229. 对于上图，试模拟Dijkstra算法，给出从编号为0的顶点出发到其它各个结点的最短路径的过程。（10分）10. 一个栈的入栈序列是a,b,c,d, 给出所有可能的出栈顺序. （5分）11. 程序题。(15 分) 给出向量的模板类如下template class vector protected: T *data;/ 数据 unsigned size;/分配空间的大小 public: / 构造和析构函数 vector (unsigned numElements); vector(); T & operator (unsigned index ) const; / 通过下标访问 vector & operator = (const vector &); /赋值 unsigned length() const; unsigned SetSize(unsigned numOfElements); / 动态改变向量大小的值;按照向量的定义，若两个向量的数据元素是有序的，试编写函数，将这两个向量合并到一个新的向量中，并保持新的向量有序。函数声明如下：template void (vector &v1, vector &v2, vector &result)/ 将从小到大排序好的向量v1 和 v2 合并到新的向量 result中试编写程序完成这个函数，可以调用向量的模板类函数。( 15 分)浙江工业大学2006/2007学年数据结构A卷 答案及评分标准1.选择题 (每题1分) (1) A (2) B (3) D (4) C (5) C(6) A (7) B (8) B (9) D (10) B(11) D (12) B (13) C (14) C (15) D(16) A (17) B (18) D (19) C (20) A2. 填空题. (21) DBEHAIFCJG (1分) (22) ABDEHCFIGJ (1分) (23) DHEBIFJGCA (1分) (24) O（n3） (2分)(25) (3分) (26) (3 分) 将 V 插入到 原AVL 树 将Y插入到原AVL 树 WCXUYBUCWVXB(27) C, H, P, A, M, Q, R, D, F, S,X, Y (2 分)(28) Y, S, X, R, P, C, M, H, Q, D, F, A （2分）(29)C, H, Q, Y, A, M, P, S, D, F, R, X (2 分)(30) 3 (1 分)(31) 4 (1 分)(32) 2 (1 分)3.6234553661122334455664. 12，2，16，30，28，10，20，6，18 第一趟的结果：2，12，16，30，28，10，20，6，18第二趟 2，12，16，30，28，10，20，6，18第三趟 2，12，16，30，28，10，20，6，18第四趟 2，12，16，28，30，10，20，6，18第五趟 2，10，12，16，28，30，20，6，18每错一个结果扣一分5. 5分6 过程如下, 每错一个图扣1分，扣完为止 共5分WXBCXBCXBCBCCWVUWXBCUWXBCUUWXBCYV7每错一个扣1分，扣完为止 共5分0123456495522203239138. 以下每错一个扣一分，扣完为止 (1) 选最小边10, (2) 选最小边 12 (3) 选最小边 14, 16 (4) 选最小边 22 (5) 选最小边 2514161026453101214221625102645310129. 过程如下：(1) 给定点的集合 U=0，0到其它顶点的最短路径分别为 28, , , ,10, (2) 选取最小的权的顶点5,于是 U=0, 5 , 0到其它顶点的最短路径修改为28, , , , 10, （3） 在V-U中选取最小权值顶点1, U=0, 5, 1 到其它顶点的最短路径修改为 28, 44, 35,10, 42 (4) 在V-U中选取最小权值顶点4, U=0, 5, 1, 4 其它顶点的最短路径修改为 28, 44, 57, 35, 10, 42 (5) 在V-U中选取最小权值顶点6, U=0, 5, 1, 4, 6其它顶点的最短路径修改为 28, 44, 56, 35, 10, 42 (6) 在V-U中选取最小权值顶点2, U=0, 5, 1, 4, 6, 2 其它顶点的最短路径修改为 28, 44, 56, 35, 10, 42 (7) 在V-U中选取最小权值顶点3, U=0, 5, 1,4, 6, 2,3 其它顶点的最短路径修改为 28, 44, 56, 35, 10, 42 步骤6,7为 2分，其它小题结果1分。最后结果正确 1 分。 10分。10. 共有14种可能a b c d b a c d c b a d d c b a a b d c b a d c c b d a a c b d b c a d c d b a a c d b b c d a a d c b b d c a每3种情况得1分，共5分。11. 程序题 15分template void (vector &v1, vector &v2, vector &result)/ 将从小到大排序好的向量v1 和 v2 合并到新的向量 result中 unsigned size1 = v1.length(); unsigned size2 = v2.length(); result.setSize(size1+size2); int p1,p2,