数据结构期末试卷

1、承诺：我将严格遵守考场纪律，知道考试违纪、作弊的严重性，还知道请他人代考或代他人考者将被开除学籍和因作弊受到记过及以上处分将不授予学士学位，愿承担由此引起的一切后果。专业 班级 学号 学生签名： 试卷编号：（A）卷 数据结构 课程 课程类别：必 开卷(范围)（ A4纸一张 ）：考试日期： 题号一二三四五六七八九十总分累分人签名题分30203812100得分考生注意事项：1、本试卷共 7 页，总分100分，考试时间120 分钟。2、考试结束后，考生不得将试卷、答题纸和草稿纸带出考场。得分评阅人 一、 选择题(每题 2 分，共30分)1. 假设某算法语句总的执行次数为T(n)=6n4+n+n2,那么该算法的时间复杂性量级为( C )。A) O(2) B) O(n5) C) O(n4) D) O(1)2. 线性表采用顺序存储结构时，其地址( A )。A) 必须是连续的 B) 部分地址必须是连续的C) 一定是不连续的 D) 连续与否均可以3. 从物理结构上可以把数据结构分为（ B ）两大类。A动态结构、静态结构 B顺序结构、链式结构 C线性结构、非线性结构 D初等结构、构造型结构4. 在顺序线

2、性表（a1,a2,a29,a30）中，在a20之前插入一个新的结点，需要将( A )个结点后移。A) 11 B) 20 C) 19 D) 105. 带头结点的单循环链表为空的条件是( C )。A) head-next=NULL B) head=NULLC) head-next=head D) head!=NULL6. 栈S最多能容纳4个元素。现在6个元素按A、B、C、D、E、F的顺序进栈，下列哪一个序列是不可能的出栈序列？( B ) A) A、B、C、D、E、F B) A、F、E、D 、C、B C) C、B、E、D、A、F D) C、D、B、F、 E、 A7. 深度为K的二叉树最多有( C )个结点。A) 2K B) 2K1 C) 2K 1 D) 2K +18. n个顶点的无向完全图的弧数为( D )。A) n (n-1) B) nn C) 2n D) n (n-1) /29. 在一个图中，图的边数等于所有顶点的度数之和的( A )倍。 A) 1/2 B) 1 C) 2 D) 4 10. 图的广度优先遍历类似于二叉树的（ C ）A) 先序遍历 B) 中序遍历 C) 层次遍历 D) 后序

3、遍历11. 在有n个叶子结点的哈夫曼树中，其结点总数为 ( C ) 。A) 不确定 B) 2n C) 2n+1 D) 2n-112. 将一棵有100个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，根结点编号为1，则编号为36的结点的左孩子的编号为( B )A) 71 B) 72 C) 73 D) 3713. 利用逐点插入法建立序列(50，72，43，85，75，20，35，45，65，30)对应的二叉排序树以后，查找元素35要进行（ A ）元素间的比较。A) 4次 B) 5次 C) 7次 D) 10次14. 在顺序表 ( 3, 6, 8, 10, 12, 15, 16, 18, 21, 25, 30 ) 中，用折半法查找关键码值11，所需的关键码比较次数为：(B) A) 2 B) 3 C) 4 D) 515. 链表适用于（ A ）查找(备注：上次有同学问过我这个题目，上次给的答案是错误的)A) 顺序 B) 二分法 C) 顺序，也能二分法 D) 随机二、 填空题（每空1分,共20分）1. 通常是以算法执行所耗费的 时间 和所占用的空间来判断一个算法的优劣。2. 队列中

4、允许进行删除的一端为 队头 。3. 在顺序队列中，虽然仍有空闲，但不能进行入队操作，这被称为是 假溢出 。4. n个顶点的连通图的生成树有 n-1 条边。5. 后缀算式79 2 20 + - 6 2 / *的值为_ 171 _。中缀算式（8-X*Y）-4*Y/7对应的后缀算式为_8 X Y* - 4 Y*7/- 。6. 若要求一个稀疏图G的最小生成树，最好用 克鲁斯卡尔 算法来求解。A1A2A4A5A6A7A3图17. 若进栈序列为a, b, c，则通过入出栈操作可能得到的a, b, c的不同排列个数为: 5 （备注：abc acb cba bac bca） 8. 有一棵树如图1所示，回答下面的问题：（1） 这棵树的根结点是 （9）A1 ;（2） 这棵树的叶子结点是 （10）A2,A4,A5,A7 （3） 结点A3的度是 （11） 2 （4） 这棵树的度是 （12） 3 （5） 这棵树的深度是 （13） 4 （6） 结点A3的子女是 （14） A5,A6 （7） 结点A3的父结点是 （15） A1 9. 设一棵完全二叉树有678个结点，则共有 （16）339 个叶子结点。10. 假定一

5、棵二叉树的结点数为18，则它的最小深度为_5 ，最大深度为_18 。11. 若要求一个稠密图G的最小生成树，最好用 普里姆 算法来求解。12. n个顶点e条边的图，若采用邻接矩阵存储，则空间复杂度为 n2 。已知数据结构DS的定义如下，请给出其逻辑结构图示。（5分）DS = (D, R) D = a, b, c, d, e, f R = T T = , , , , , , 已知二叉树的中序序列为DBGEAFC，后序序列为DGEBFCA，给出对应的二叉树。（5分）1. 已知叶子结点值7，17，5，6，9，23，构造哈夫曼树，计算其带权路径长度.（10分）2. 已知无向图如图2所示，（10分）（1）给出图的邻接矩阵。（2）根据邻接矩阵从0开始，给出一棵广度优先生成树。图2图3 3. 给定网G 如图3所示 ，找出网G的最小生成树，画出其逻辑结构图；（4分）三、 编程题（共16分）1、 写一算法，从顺序表中插入自第i个元素开始的k个元素。（已知给定抽象数据类型及算法参数，k个元素值放在数组a中，请补充完成下面算法）typedef Struct Sqlist int *elem; int len

6、gth; int listsize; Sqlist;Status Insert(Sqlist &L,int i, int k，int a) 2、 写算法输出二叉树中所有叶子结点。已知二叉树抽象数据类型为：Typedef Struct Node int data;struct node *lchild,*rchild; Node,*BitNode;承诺：我将严格遵守考场纪律，知道考试违纪、作弊的严重性，还知道请他人代考或代他人考者将被开除学籍和因作弊受到记过及以上处分将不授予学士学位，愿承担由此引起的一切后果。专业 班级 学号 学生签名： 试卷编号：（B)卷 数据结构 课程 课程类别：必 闭卷 考试日期： 题号一二三四五六七八九十总分累分人签名题分2030301010100得分考生注意事项：1、本试卷共 8 页，总分100分，考试时间120分钟。2、考试结束后，考生不得将试卷、答题纸和草稿纸带出考场。3、所有答案必须写在答题纸上，写在试卷上无效。一、选择题(每题2分，共20分) 1单链表的一个存储结点包含（D）。 A数据域或指针域 B指针域或链域 C指针域和链域 D数据域和指针域2. 线

7、性表是具有n个（ C ）的有限序列（n0）。 A表元素 B字符 C数据元素 D数据项 3对顺序表上的插入、删除算法的时间复杂性分析来说，通常以（ B ）为标准操作来考虑。 A条件判断 B结点移动 C算术表达式 D赋值语句4循环链表主要优点是 （ D ）A不再需要头指针了B已知某个结点的位置后，能够容易找到它的直接前趋C在进行插入、删除运算时，能更好地保证链表不断开D从表中任一结点出发都能扫描到整个链表5栈和队都是（ C ）A顺序存储的线性结构 B. 链式存储的非线性结构C限制存取点的线性结构 D限制存取点的非线性结构6下列哪一种图的邻接矩阵是对称矩阵（ B ）A有向图 B无向图 CAOV网 DAOE网7. 二维数组A68采用行优先的存储方法，若每个元素各占10个存储单元，且第1个元素的A00地址为1000，则元素A47的地址为( B )A. 1282 B. 1390C. 1270 D. 12768. 在深度为6的完全二叉树中 （ D ）A.最少有31个结点，最多有64个结点B.最少有32个结点，最多有64个结点C.最少有31个结点，最多有63个结点D.最少有32个结点，最多有63个结点9具有n个顶点的连通图至少有（ A ）条边。 A. n-1 B. n C. n+1 D. 2n10具有3个结点的二叉树的有（ B ）种不同形态。A. 6 B. 5 C. 3

《数据结构期末试卷》由会员人***分享，可在线阅读，更多相关《数据结构期末试卷》请在金锄头文库上搜索。