数据结构期末考试卷B卷.docx

《数据结构期末考试卷B卷.docx》由会员分享，可在线阅读，更多相关《数据结构期末考试卷B卷.docx（8页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、东莞理工学院城市学院本科试卷B卷2021 -2021 学年第二学期开课单位： 计信系 ，考试形式： 闭 卷，允许带 入场科目： 数据构造 班级：15级软件工程16班，姓名： 学号： 题序一二三四总 分得分评卷人一、填空题每题2分，共12分1、 数据构造在计算机中根本存储方式有 构造和 构造 。2、栈(又称为堆栈)是操作受限的线性构造，其操作的根本原那么是 ，插入和删除元素的一端称为 。3、深度为k根的深度为1的完全二叉树至少有_ _个结点，至多有 _ _个结点。4、 对于一个有n个顶点的完全无向图，具有 条边；而对于一个有n个顶点的完全有向图，具有 条弧。5、 在进展排序时，最根本的操作是 和

2、 。6、 哈希函数是一种映象，是从 到 的一种映象。二、单项选择题请将答案写在题目后的括号中。每题2分，共40分1、 下面构造中，不属于数据逻辑构造的是 。A 线性链表 B 树形构造 C 线性构造 D 网状构造2、 下面说法正确的选项是 。A 数据元素是数据的最小单位 B 数据项是数据的根本单位C 数据构造是带有构造的各数据项的集合D 上述说法都是错误的3、 有以下算法，其时间复杂度是 。x=1 ;while (xnext=q-next；free(p) ; B p-next=q-next；free(q) ;C q-next=p-next；free(p) ; D q-next=p-next；fr

3、ee(q) ; 6、 栈和队列的共同点时 。A 都是先进先出 B 都是后进先出C 只允许在端点处插入和删除元素 D 没有共同点7、 设有一个栈顶指针为top的顺序栈S，top为0时表示栈空，那么向堆栈S中压入一个元素x执行的操作是 。A Stop+=x； B S+top=x；C S-top=x； D Stop-=x； 8、 设循环队列Q的最多元素个数为m，队尾指针是rear，队首指针是front，那么队列为满的条件是 。A Q.rear=Q.front ； B Q.rear!=Q.front ；C (Q.rear+1)%m!=Q.front； D (Q.rear+1)%m=Q.front；9、

4、 广义表(a),(b),c),(d,e),(a,b)的长度是 ，深度是 。 A 4, 4 B 4, 5 C 3, 5 D 3, 410、有一个12阶下三角矩阵A，上三角的所有元素均为0， A00的地址是BA，假设每个元素占3个存储单元，采用行优先压缩存储，那么A65的地址是 。A BA+75 B BA+78 C BA+81 D BA+8411、 在二叉树中，指针P所指的结点是非叶子结点的条件是 。A P-Lchild =NULL& P-Rchild=NULL ； B P-Lchild !=NULL& P-Rchild !=NULL ；C P-Lchild =NULL &P-Rchild !=N

5、ULL ； D P-Lchild !=NULL |P-Rchild !=NULL ；12、 将一棵一般的树转换为二叉树后，这棵二叉树的形态是 。A 唯一的 B 有多种，但根结点都没有左子结点C 有多种 D 有多种，但根结点都没有右子结点13、 设由nn2个权值都互不一样的字符构成的哈夫曼树，关于该树的表达中，错误的选项是 。A 该树一定是一棵完全二叉树B 树中一定没有度为1的结点C 树中两个权值最小的结点一定是兄弟结点D 树中任一非叶子结点的权值一定不小于下一层任一结点的权值14、 以下描述中，关于无向图邻接矩阵的特性不正确的选项是 。A 邻接矩阵是对称方阵。B 假设顶点vi在顶点数组中的存储

6、位置为i，那么其度数是第i行的非0元素的个数。C 无向图的边数是上(或下)三角形矩阵中非0元素个数。D图的度是矩阵中非0元素个数。15、 对于有向图，下述关于图、顶点的度、入度、出度的论述中，错误的选项是 。A 顶点的度是顶点的入度、出度之和B 图的度是图的入度、出度之和C 顶点的入度等于顶点的出度D 图的入度等于图的出度16、 对于有n个顶点e(en)条边的带权无向图，以下关于该图的最小生成树的描述正确的选项是 。A 最小生成树是唯一的。B 最小生成树中所有边上的权值之和是唯一的。C 最小生成树有n条边。D 最小生成树有n个顶点e-1条边。17、 适用于折半查找的表的存储方式以及元素排列要求

7、是 。A顺序存储方式，元素有序 B顺序存储方式，元素无序C 链接存储方式，元素无序 D链接存储方式，元素有序18、 采用线性探测法解决冲突，可能要探测多个位置，在查找成功的情况下，所探测的这些位置上的关键字 。A 不一定都是同义词 B 一定都是同义词 C 一定都不是同义词 D 都一样19、 从未排序序列中依次取出元素与已排序序列初始时为空中的元素进展比拟，将其放入已排序序列的正确位置上的方法，这种排序方法称为 。A 归并排序 B 冒泡排序 C 选择排序 D 插入排序20、 假设一组记录的排序码为46，79，56，38，40，84，那么采用快速排序法，以第一个记录为基准得到的依次划分结果是 。A

8、 38，40，46，56，79，84 B 40，38，46，79，56，84 C 40，38，46，56，79， 84 D 40，38，46，84，56，79三、分析题每题8分，共40分1、 设有一棵二叉树的顺序存储构造如下。 画出该二叉树 ； 分别写出该二叉树的中序遍历序列和后序遍历序列； A B C D E F G H I J K L M1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 232、 假设以7, 9, 13, 6, 5, 3, 17, 10作为叶子结点的权值，请构造对应的Huffman树，然后求出其带权路径长度WP

9、L。3、 设有带权的无向图的顺序存储构造如下： 画出该图； 给出用普里姆(Prime)算法从顶点V2出发的最小生成树。vexs012345V0V1V2V3V4V5 5 3 5 6 3 3 6 4 8 10 4 5 3 8 7 10 5 7 4、 将关键字序列29，33，23，43，38，27，31，25，21依次插入到初态为空的二叉排序树中，请画出所得到的树T；然后画出删除23之后的二叉排序树T1；最后再画出在T1中插入23之后的二叉排序树T2。5、 线性表的关键字集合31，25，18，29，42，36，73，53，17，16，47，94，43，共有13个元素，散列函数为：Hkey = key MOD 11，采用链地址法处理冲突，请给出对应的散列表构造。四、编写算法8分设单链表的结点构造定义如下，试写一个函数Delete_linkList实现通过一趟遍历删除以L为头结点的单链表中值在x到y(x的大小任意y)之间的所有结点。typedef struct Lnode int data; /*数据域，保存结点的值 */struct Lnode *next; /*指针域*/LNode; /*结点的类型 */函数的原型为：void Delete_linkList(LNode *L, int x, int y)