《数据结构》期末考试卷 -B卷

1、【精品文档】如有侵权，请联系网站删除，仅供学习与交流数据结构期末考试卷 -B卷.精品文档.东莞理工学院城市学院（本科）试卷（B卷）2016 -2017 学年第二学期开课单位： 计信系 ，考试形式： 闭 卷，允许带 入场科目： 数据结构 班级：15级软件工程16班，姓名： 学号： 题序一二三四总 分得分评卷人一、填空题（每题2分，共12分）1、 数据结构在计算机中基本存储方式有 结构和 结构 。2、栈(又称为堆栈)是操作受限的线性结构，其操作的基本原则是 ，插入和删除元素的一端称为 。3、深度为k（根的深度为1）的完全二叉树至少有_ _个结点，至多有 _ _个结点。4、 对于一个有n个顶点的完全

2、无向图，具有 条边；而对于一个有n个顶点的完全有向图，具有 条弧。5、 在进行排序时，最基本的操作是 和 。6、 哈希函数是一种映象，是从 到 的一种映象。二、单项选择题（请将答案写在题目后的括号中。每题2分，共40分）1、 下面结构中，不属于数据逻辑结构的是（ ）。（A） 线性链表 （B） 树形结构 （C） 线性结构 （D） 网状结构2、 下面说法正确的是（ ）。（A） 数据元素是数据的最小单位 （B） 数据项是数据的基本单位（C） 数据结构是带有结构的各数据项的集合（D） 上述说法都是错误的3、 有下列算法，其时间复杂度是（ ）。x=1 ;while (xnext=q-next；free(

3、p) ; （B） p-next=q-next；free(q) ;（C） q-next=p-next；free(p) ; （D） q-next=p-next；free(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，则

4、队列为满的条件是（ ）。（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、 广义表(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、

5、在二叉树中，指针P所指的结点是非叶子结点的条件是（ ）。（A） P-Lchild =NULL& P-Rchild=NULL ； （B） P-Lchild !=NULL& P-Rchild !=NULL ；（C） P-Lchild =NULL &P-Rchild !=NULL ； （D） P-Lchild !=NULL |P-Rchild !=NULL ；12、 将一棵一般的树转换为二叉树后，这棵二叉树的形态是 （ ）。（A） 唯一的 （B） 有多种，但根结点都没有左子结点（C） 有多种 （D） 有多种，但根结点都没有右子结点13、 设由n（n2）个权值都互不相同的字符构成的哈夫曼树，关于该树的

6、叙述中，错误的是 （ ）。（A） 该树一定是一棵完全二叉树（B） 树中一定没有度为1的结点（C） 树中两个权值最小的结点一定是兄弟结点（D） 树中任一非叶子结点的权值一定不小于下一层任一结点的权值14、 以下描述中，关于无向图邻接矩阵的特性不正确的是（ ）。（A） 邻接矩阵是对称方阵。（B） 若顶点vi在顶点数组中的存储位置为i，则其度数是第i行的非0元素的个数。（C） 无向图的边数是上(或下)三角形矩阵中非0元素个数。（D）图的度是矩阵中非0元素个数。15、 对于有向图，下述关于图、顶点的度、入度、出度的论述中，错误的是（ ）。（A） 顶点的度是顶点的入度、出度之和（B） 图的度是图的入度、

7、出度之和（C） 顶点的入度等于顶点的出度（D） 图的入度等于图的出度16、 对于有n个顶点e(en)条边的带权无向图，以下关于该图的最小生成树的描述正确的是（ ）。（A） 最小生成树是唯一的。（B） 最小生成树中所有边上的权值之和是唯一的。（C） 最小生成树有n条边。（D） 最小生成树有n个顶点e-1条边。17、 适用于折半查找的表的存储方式以及元素排列要求是（ ）。（A）顺序存储方式，元素有序 （B）顺序存储方式，元素无序（C） 链接存储方式，元素无序 （D）链接存储方式，元素有序18、 采用线性探测法解决冲突，可能要探测多个位置，在查找成功的情况下，所探测的这些位置上的关键字（ ）。（A）

8、 不一定都是同义词 （B） 一定都是同义词 （C） 一定都不是同义词 （D） 都相同19、 从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放入已排序序列的正确位置上的方法，这种排序方法称为（ ）。（A） 归并排序 （B） 冒泡排序 （C） 选择排序 （D） 插入排序20、 若一组记录的排序码为（46，79，56，38，40，84），则采用快速排序法，以第一个记录为基准得到的依次划分结果是（ ）。（A） 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，7

9、9三、分析题（每题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树，然后求出其带权路径长度WPL。3、 设有带权的无向图的顺序存储结构如下： 画出该图； 给出用普里姆(Prime)算法从顶点V2出发的最小生成树。vexs012345V0V1V2V3

10、V4V5 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个元素，已知散列函数为：H（key） = key MOD 11，采用链地址法处理冲突，请给出对应的散列表结构。四、编写算法（8分）设单链表的结点结构定义如下，试写一个函数Delete_linkList实现通过一趟遍历删除以L为头结点的单链表中值在x到