当前位置：文档之家 › 浙工大数据结构期末试卷

浙工大数据结构期末试卷

  • 格式：doc
  • 大小：227.49 KB
  • 文档页数：11

浙江工业大学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) 以下的四个二叉树中，( ) 是二叉排序树.A) B)C) D)(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的结点时，（ ）次比较后查找成功。

67 325829316732882981 F B DAZFG A HEA) 1 B) 2. C) 4. D) 8(14)如果遍历的方式是根，右子树，左子树，那么遍历图的二叉树序列为（ ）.(15) 将一棵有99个结点的完全二叉树按顺序编号，根结点的编号为0,那么编号为49的结点的右子结点的编号为( ) .A) 98 B) 99 C) 100 D) 不存在(16) 已知如下的两种序列，则不可能确定一棵二叉树( ) A) 先序序列和后序序列 B) 先序序列和中序序列 C) 中序序列和后序序列 D) 以上都不对(17) 下列排序法中最稳定的是（ ）（A ）堆排序法 （B ）插入排序法（C ）选择排序法（D ）快速排序法(18) 如下图，从顶点1出发，按照深度优先规则遍历，可能得到的序列为( ) A) 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={<v1, v2>, <v1, v3>, <v1, v4>, <v2, v5>, <v3, v5>, <v3, v6>,<v4, v6>, <v5, v7>,<v6, v7>}，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, V751 749 A) 5, 1, 7, 4, 9 B) 5, 1, 4, 7, 9 C) 5, 7, 9, 1, 4 D) 4, 1, 5, 9, 71 2 7 35462. 填空题(1) 如图所示的二叉树，写出不同的遍历顺序的结果(3分)A) 中序遍历. __ (21)__B) 先序遍历. __ (22)__C) 后序遍历. _ (23)__(2) 求如下程序段的时间复杂度，采用大O表示。

__(24)___ (2 分)int i,j,k;for( i = 0;i<n;i++)for (j = 0;j<n;j++){c[i][j] = 0.0;for (k = 0; k<n; k++)c[i][j] = A[i][k] * B[k][j];}(3) 如下图A VL树，请分别插入关键字的结点V__(25)____, 插入Y __(26)____. 注意：两个结点是是单独插入的。

(6分)CB WU X(4) 设要将序列(Q, H, C, Y, P, A, M, S, R, D, F, X) 中关键字按字母序的升序重新排序，则冒泡排序第二趟排序的结果是______(27)________________, 建立初始最大堆的结果是______(28)_________,采用归并排序，第二趟排序的结果是_____(29)_______ . (6分)(5) 某图的邻按矩阵如下图，从邻接矩阵可以看出，该图有__(30)__个顶点，如果是有向图，该图有__(31)___条边，如果是无向图，则有__(32)___条边. (3分)A =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分）6154231001055020106040150 1 0 1 0 1 0 1 07. 有7个关键码的开地址散列向量{ 32,13,49,55,22,39,20}，散列函数为取余运算（即%7,如关键码32的向量地址为32%7 = 4），采用线性开地址散列解决冲突，试完成按以上关键码顺序插入到散列向量之后的结果。

（5分）0 1 234568. 已经带权的无向图如下，请模拟用克鲁斯卡尔 (Kruskal) 算法生成最小生成树的详细结果。

（5分）9. 对于上图，试模拟Dijkstra 算法，给出从编号为0的顶点出发到其它各个结点的最短路径的过程。

（10分）10. 一个栈的入栈序列是a,b,c,d, 给出所有可能的出栈顺序. （5分）11. 程序题。

(15 分) 给出向量的模板类如下 template <class T> class vector { protected: T *data;// 数据unsigned size; //分配空间的大小public:// 构造和析构函数vector (unsigned numElements);~vector();T & operator [] (unsigned index ) const; // 通过下标访问1213546 21025281618221424vector <T> & operator = (const vector<T> &); //赋值unsigned length() const;unsigned SetSize(unsigned numOfElements); // 动态改变向量大小的值};按照向量的定义，若两个向量的数据元素是有序的，试编写函数，将这两个向量合并到一个新的向量中，并保持新的向量有序。

函数声明如下：template <class T>void (vector<T> &v1, vector<T> &v2, vector<T> &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 树(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.WC XU Y BUC WV X B1 12 23 34 45 5 ∧6 6 23 ∧455 ∧3 ∧6 ∧6 ∧6 ∧4.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分AG ECFIHJDB6 过程如下, 每错一个图扣1分，扣完为止 共5分7每错一个扣1分，扣完为止 共5分123456CCBC B XC BX WCBX WUC BX WUCB XW UV CB X W U V Y49 55 22 20 32 39 138. 以下每错一个扣一分，扣完为止(1) 选最小边10, (2) 选最小边 12 (3) 选最小边 14, 16 (4) 选最小边 22 (5) 选最小边 259. 过程如下：(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分。

合集下载

数据结构期末试题及答案

数据结构期末试题及答案

数据结构期末试题及答案一、单项选择题（每题2分，共20分）1. 在数据结构中，线性表的顺序存储结构和链式存储结构的主要区别在于：A. 数据元素的存储关系B. 数据元素的存储空间C. 数据元素的存储顺序D. 数据元素的存储位置答案：A2. 下列关于栈的描述中，错误的是：A. 栈是一种后进先出（LIFO）的数据结构B. 栈只能进行插入和删除操作C. 栈顶元素可以被访问D. 栈可以进行顺序存储和链式存储答案：B3. 在二叉树的遍历算法中，不使用递归算法的遍历方式是：A. 前序遍历B. 中序遍历C. 后序遍历D. 层序遍历答案：D4. 哈希表的冲突解决方法中，不包括以下哪种：A. 开放定址法B. 链地址法C. 线性探测法D. 排序法答案：D5. 在图的遍历算法中，深度优先搜索（DFS）和广度优先搜索（BFS）的主要区别在于：A. 搜索的顺序B. 存储结构C. 遍历的深度D. 遍历的宽度答案：A6. 快速排序算法的时间复杂度最坏情况下为：A. O(n)B. O(nlogn)C. O(n^2)D. O(n^3)答案：C7. 下列关于二叉搜索树的描述中，正确的是：A. 每个节点的左子树只包含小于该节点的键值B. 每个节点的右子树只包含大于该节点的键值C. 以上两个选项都正确D. 以上两个选项都不正确答案：C8. 在非递归的二叉树遍历算法中，通常需要使用的数据结构是：A. 栈B. 队列C. 链表D. 数组答案：A9. 一个有n个顶点的无向图，其边数最多为：A. nB. n(n-1)/2C. n(n+1)/2D. n^2答案：B10. 一个长度为n的数组进行归并排序时，需要的辅助空间大小为：A. O(1)B. O(n)C. O(nlogn)D. O(n^2)答案：B二、填空题（每题2分，共10分）1. 在数据结构中，______是一种特殊的线性表，它的元素个数是固定的。

答案：数组2. 链表中，每个节点包含数据域和______。

2021年浙江工业大学数据科学与大数据技术专业《计算机组成原理》科目期末试卷A(有答案)

2021年浙江工业大学数据科学与大数据技术专业《计算机组成原理》科目期末试卷A(有答案)

2021年浙江工业大学数据科学与大数据技术专业《计算机组成原理》科目期末试卷A（有答案）一、选择题1、局部性原理是一个持久的概念，对硬件和软件系统的设计和性能都有着极大的影响。

局部性通常有两种不同的形式：时间局部性和空间局部性。

程序员是否编写出高速缓存友好的代码，就取决于这两方面的问题。

对于下面这个函数，说法正确的是（）。

int sumvec(int v[N]){int i, sum=0;for(i=0;i<N;i++)sum+= v[i]eturn sum;}A.对于变量i和sum，循环体具有良好的空间局部性B.对于变量i、sum和v[N]，循环体具有良好的空间局部性C.对于变量i和sum，循环体具有良好的时间局部性D.对于变量i、sum和v[N]，循环体具有良好的时间局部性22、设存储器容量为32字，字长为64位。

模块数m=4，采用低位交叉方式。

存储周期T=200ns，数据总线宽度为64位，总线传输周期r=50ns。

该交叉存储器的带宽是（）。

A.32×107bit/sB.8×107bit/sC.73×107bit/sD.18×107bit/s3、下列关于定点数原码一位乘算法的描述正确的是（）。

I.符号位不参加运算，根据数值位的乘法运算结果确定结果的符号位II.在原码一位乘算法过程中，所有移位均是算术移位操作Ⅲ.假设两个n位数进行原码一位乘，部分积至少需要使用n位奇存器A.II，III C.只有IIIB.只有Ⅲ D.全错4、假设在网络中传送采用偶校验码，当收到的数据位为10101010时，则可以得出结论（）A.传送过程中未出错B.出现偶数位错C.出现奇数位错D.未出错或出现偶数位错5、为了表示无符号十进制整数，下列哪些是合法的8421BCD码？（）I.01111001 Ⅱ.11010110 Ⅲ.00001100 Ⅳ.1000010lA.I、IⅡB.Ⅱ、ⅢC.I、ⅣD.I、Ⅱ、Ⅲ6、内部总线（又称片内总线）是指（）。

《数据结构》期末考试试卷试题及答案

《数据结构》期末考试试卷试题及答案

《数据结构》期末考试试卷试题及答案第一部分：选择题（每题2分，共20分）1. 下面哪个数据结构是线性结构？A. 树B. 图C. 队列D. 网络流2. 下面哪个数据结构用于实现广度优先搜索算法？A. 栈B. 队列C. 散列表D. 堆3. 下面哪个数据结构用于实现深度优先搜索算法？A. 栈B. 队列C. 散列表D. 堆4. 下面哪个数据结构用于实现快速排序算法？A. 栈B. 队列C. 散列表D. 堆5. 下面哪个数据结构用于实现优先队列？A. 栈B. 队列C. 散列表D. 堆6. 下面哪个数据结构用于实现哈希表？A. 栈B. 队列C. 散列表D. 堆7. 下面哪个数据结构用于实现最小树算法？A. 栈B. 队列C. 散列表D. 堆8. 下面哪个数据结构用于实现拓扑排序算法？A. 栈B. 队列C. 散列表D. 堆9. 下面哪个数据结构用于实现最短路径算法？A. 栈B. 队列C. 散列表D. 堆10. 下面哪个数据结构用于实现并查集算法？A. 栈B. 队列C. 散列表D. 堆第二部分：填空题（每题2分，共20分）1. 链表是一种______数据结构。

2. 二叉树的节点最多有______个子节点。

3. 堆是一种特殊的______。

4. 散列表的查找效率取决于______。

5. 图的遍历算法包括______和______。

6. 快速排序算法的平均时间复杂度为______。

7. 哈希表中的冲突解决方法有______和______。

8. 最小树算法包括______和______。

9. 最短路径算法包括______和______。

10. 并查集算法用于解决______问题。

第三部分：简答题（每题10分，共50分）1. 请简述栈和队列的区别。

2. 请简述二叉搜索树的特点。

3. 请简述哈希表的原理。

4. 请简述图的深度优先搜索算法。

5. 请简述最小树算法的原理。

第四部分：编程题（每题20分，共50分）1. 编写一个函数，实现链表的插入操作。

《数据结构》期末考试试卷试题及答案

《数据结构》期末考试试卷试题及答案

《数据结构》期末考试试卷试题及答案一、选择题（每题5分，共20分）1. 下列哪个不是线性结构？A. 栈B. 队列C. 图D. 数组2. 下列哪个不是栈的基本操作？A. 入栈B. 出栈C. 查找D. 判断栈空3. 下列哪个不是队列的基本操作？A. 入队B. 出队C. 查找D. 判断队列空4. 下列哪个不是图的基本概念？A. 顶点B. 边C. 路径D. 环二、填空题（每题5分，共20分）5. 栈是一种______结构的线性表，队列是一种______结构的线性表。

6. 图的顶点集记为V(G)，边集记为E(G)，则无向图G=(V(G),E(G))，有向图G=(______，______)。

7. 树的根结点的度为______，度为0的结点称为______。

8. 在二叉树中，一个结点的左子结点是指______的结点，右子结点是指______的结点。

三、简答题（每题10分，共30分）9. 简述线性表、栈、队列、图、树、二叉树的基本概念。

10. 简述二叉树的遍历方法。

11. 简述图的存储结构及其特点。

四、算法题（每题15分，共30分）12. 编写一个算法，实现栈的入栈操作。

13. 编写一个算法，实现队列的出队操作。

五、综合题（每题20分，共40分）14. 已知一个无向图G=(V,E)，其中V={1,2,3,4,5}，E={<1,2>,<1,3>,<2,4>,<3,4>,<4,5>}，画出图G，并给出图G的邻接矩阵。

15. 已知一个二叉树，其前序遍历序列为ABDCE，中序遍历序列为DBACE，请画出该二叉树，并给出其后序遍历序列。

答案部分一、选择题答案1. C2. C3. C4. D二、填空题答案5. 后进先出先进先出6. V(G),E(G)7. 0 叶结点8. 左孩子右孩子三、简答题答案9. （1）线性表：一个线性结构，其特点是数据元素之间存在一对一的线性关系。