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

《《数据结构》期末考试卷-B卷》由会员分享，可在线阅读，更多相关《《数据结构》期末考试卷-B卷（11页珍藏版）》请在装配图网上搜索。

1、东莞理工学院城市学院（本科）试卷（ B卷）2016 -2017学年第二学期开课单位：计信系 ，考试形式: 闭 卷，允许带入场科目： 数据结构 班级:15级软件工程1s6班，姓名: 学号： 题序-一-二三四总分得分评卷人、填空题（每题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 (xn ext=q _next；free(p);(B)p_next=q_next ; free(q)(C)q_n ext=p-next；fre

3、e(p);(D)q_next=p-next ; free(q);栈和队列的共同点时()。(A)都是先进先出(B)都疋后进先出(C)只允许在端点处插入和删除兀素(D)没有共冋点4、线性表若米用链式存储结构，要求内存中可用存储单兀的地址是()。6、设有一个栈顶指针为top的顺序栈S,top为0时表示栈空,则向堆栈S中压入一个元素5、x执行的操作是(8、(A) Stop+=x ;(C)S-top=x ;(B)(D)设循环队列Q的最多元素个数为 m,S+top=x ;Stop-=x ;队尾指针是rear，队首指针是front,则队列为满可编辑范本可编辑范本的条件是(可编辑范本可编辑范本(A) Q.re

4、ar=Q.fro nt;Q.rear!=Q.fro nt ;可编辑范本可编辑范本(B) (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, 4可编辑范本10、有一个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） 若顶点v在顶点数组中的存储位置为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） 不一定都是同义词（B） 一定都是同

8、义词（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, 79三、分析题（每题8分，共40分）1、设有一棵二叉树的顺序存储结

9、构如下。画出该二叉树分别写出该二叉树的中序遍历序列和后序遍历序列;1234567891011121314151617181920 212223ABCDEFG?HIJK?LM可编辑范本2、 若以7, 9, 13, 6, 5, 3, 17, 10作为叶子结点的权值，请构造对应的Huffman 树，然后求出其带权路径长度 WPL 。可编辑范本3、设有带权的无向图的顺序存储结构如下：画出该图； 给出用普里姆（Prime）算法从顶点V2出发的最小生成树。vexs0Vo1Vi2V23V34V45V55336OO4810OOOO4OOOO5OOOO5 o 6 o 3 oOO38OOOO7QOOOO1057O

10、O丿可编辑范本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，共有= key MOD 11 ， 采用链地址法处理冲突，请给出对13个元素，已知散列函数为： H （ key） 应的散列表结构。可编辑范本四、编写算法（ 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）可编辑范本