武汉科技大学2019年全国硕士研究生招生考试初试自命题856 数据结构（C语言版）-2019（A卷）.doc

《武汉科技大学2019年全国硕士研究生招生考试初试自命题856 数据结构（C语言版）-2019（A卷）.doc》由会员分享，可在线阅读，更多相关《武汉科技大学2019年全国硕士研究生招生考试初试自命题856 数据结构（C语言版）-2019（A卷）.doc（5页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、姓名：报考专业：准考证号码：密封线内不要写题2019年全国硕士研究生招生考试初试自命题试题科目名称：数据结构（C语言版）（A卷B卷）科目代码：856考试时间：3小时 满分150分可使用的常用工具：无 计算器 直尺 圆规（请在使用工具前打）注意：所有答题内容必须写在答题纸上，写在试题或草稿纸上的一律无效；考完后试题随答题纸交回。一、选择题(共15小题，每小题2分，共30分)1. 计算算法的时间复杂度是属于一种（ ）的方法。A）事前统计 B）事前分析估算 C）事后统计 D）事后分析估算2. 数据的逻辑结构可以分为（ ）。A）静态结构和动态结构 B）物理结构和存储结构C）线性结构和非线性结构 D）虚

2、拟结构和抽象结构3. 线性表若采用链式存储结构时，要求内存中可用存储单元的地址（ ）。A）必须是连续的 B）部分地址必须是连续的C）一定是不连续的 D）连续不连续都可以4. 线性表既可以用带头结点的链表表示，也可以用不带头结点的链表表示，前者最主要的好处是（ ）。A）使空表和非空表的处理统一 B）可以加快对表的遍历C）节省存储空间 D）可以提高存取表元素的速度5. 若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3。当从队列中删除一个元素，再加入两个元素后， rear 和front的值分别为（ ）。A）1和5 B）2和4 C）4和2 D）5和16. 对二叉树T中的

3、某个结点x，它在先根序列、中根序列、后根序列中的序号分别为pre（x），in（x）、post（x），a和b是T中的任意两个结点，下列选项一定错误的是（ ）。A）a是b的后代且pre（a）post（b）C）a是b的后代且in（a）in（b） D）a在b的左边且in（a）in（b）7. 若二叉树的前序序列和后序序列正好相反，则该二叉树一定是（ ）的二叉树。A）空或只有一个结点 B）任一结点无左子树C）任一结点无右子树 D）高度等于其结点数8. 下面几个符号串编码集合中，不是前缀编码的是（ ）。A）0,10,110,1111 B）11,10,001,101,0001C）00,010,0110,100

4、0 D）b,c,aa,ac,aba,abb,abc9. 一个n个顶点的连通无向图,其边数至少为（ ）。A）n-1 B）n C）n+1 D）n*logn10. 下面（ ）方法可以判断出一个有向图中是否有环（回路）？ A）深度优先遍历 B）求最短路径 C）拓朴排序 D）求关键路径 11. 下列关于无向连通图特性的叙述中，正确的是（ ）。 （1）所有顶点的度数之和为偶数。 （2）边数比顶点个数减1要大。 （3）至少有1个顶点的度为1。A）只有（1） B）只有（2） C）（1）和（2） D）（1）和（3）12. 静态查找表与动态查找表二者的根本差别在于（ ）。A）它们的逻辑结构不一样 B）施加在其上的

5、操作不同C）包含的数据元素的类型不一样 D）存储实现不一样13. 设有100个结点,用二分法查找时,最大比较次数是（ ）。A）25 B）50 C）10 D）714. 对初始数据序列8，3，9，11，2，1，4，7，5，10，6进行希尔排序。若第一趟排序结果为1，3，7，5，2，6，4，9，11，10，8，第二趟排序结果为1，2，6，4，3，7，5，8，11，10，9，则两趟排序采用的增量分别是（ ）。A）3，1 B）3，2 C）5，2 D）5，315. 下列排序算法中，（ ）算法可能会出现下面情况：初始数据有序时，花费时间反而更多。A）堆排序 B）冒泡排序 C）快速排序 D）希尔排序二、填空题

6、(共10小题，每小题2分，共20分)1. 将两个各有n个元素的有序表归并成一个有序表，其最少比较次数是（ ）次。2. 在无表头结点的单链表L的表头插入s结点的语句序列是（ ）。3. 循环队列存储在数组A0.m中，尾指针为rear，则数据元素x入队时,首先将x放到队尾所在位置，然后队尾后移，其中队尾后移的操作语句为（ ）。4. 由5个结点可以构造出（ ）种不同的树。5. 已知一棵完全二叉树的第6层(设根为第1层)有8个叶结点,则完全二叉树的结点个数最多是（ ）。6. 设森林F中有3棵树，三棵树的结点个数依次是n1，n2和n3，则与森林F相对应二叉树的根结点的右子树上的结点个数是（ ）个。7. 有

7、n个结点，e条边的无向图采取邻接表存储，求最小生成树的Kruskal算法的时间复杂度是（ ）。8. 已知一无向图G=（V，E），其中V=a,b,c,d,e E=(a,b),(a,d),(a,c),(d,c),(b,e)现用某一种图遍历方法从顶点a开始遍历图，得到的序列为abecd，则采用的是（ ）遍历方法。9. 有序表包含16个数据，顺序组织。若采用二分查找方法，则在等概率情况下，查找成功时的ASL值是（ ）。10. 一组记录的排序码为（46，79，56，38，40，84），则利用堆排序的方法建立的初始堆（大顶堆）中第2，3，4个排序码分别为（ ）。三、判断题(对的答错的答，共10小题，每小题

8、2分，共20分)1. 数据元素是数据的最小单位。2. 一般认为，随问题规模n的增大，算法执行时间的增长速度较快的算法最优。3. 在一个长度为n的线性表的第i个位置（1in+1）插入一个元素时，需要向后移动n+1-i个元素。4. 用链接方式存储的队列，在进行出队运算时仅需修改头指针。5. 对于任何一颗二叉树，如果其叶子结点数为n0，则度为2的结点数为n01。6. 如果给定二叉树的先序遍历序列和后序遍历序列，则该二叉树是唯一的。7. 一颗有n个顶点的生成树有且仅有n1条边。8. 对AOV网进行拓扑排序时，结束后如果还有顶点没有被输出，且这些顶点的入度均0，则该网必定有环存在。9. 采用线性探测法处

9、理冲突，在查找成功的情况下，可能要探测的这些位置上的关键字一定都是同义词。10. 堆排序不是稳定的排序方法。四、综合应用题(共5小题，每小题各8分，共40分)1. 将如下图所示矩阵的非零元素逐行存放于数组B中（下标从0开始存放，即A11存放在B0中），使得Bk=Ai，j，求：（1）用i，j表示的变换公式。（2）用表示i，j的变换公式。2. 已知AOV网的邻接表如下图所示，要求：（1）画出该AOV网。（2）给出基于该AOV网邻接表的从顶点V1出发的DFS序列。（3）给出基于该AOV网邻接表的从顶点V1出发的BFS序列。（4）写出对该AOV网按照上述邻接表进行拓扑排序得到的拓扑序列。3. 根据下列

10、二叉树，要求：（1）写出其先序遍历序列、中序遍历序列和后序遍历序列。（2）顺序存储该二叉树，画出其存储示意图。4. 如果一颗非空k叉树T（k2）中每个非叶子结点都有k个孩子。请回答下列问题并给出推导过程。（1）若T有m个非叶子结点，则T的叶子节点有多少个？（2）若T的高度为h，则T的结点数最多是多少个？最少是多少个？5. 散列表长度是13，散列函数H(K)=k % 13，解决冲突用线性探测再散列法。给定的关键字序列为19,14,23,1,68,20,84,27,55,11,10,79，要求：（1）画出哈希表。（2）求出等概率下查找成功的平均查找长度。（3）求出等概率下查找失败的平均查找长度。五

11、、算法设计题(共4小题，每小题10分，共40分)1. 用带头结点的双向循环链表（结点结构为（Left，Data，Right）表示的线性表为L=（a1,a2, an）。试设计如下算法Fun实现将L改造成：L=（a1,a3,an,a4,a2）。void Fun(DbLinkList &L);2. 若表达式以字符形式已存入数组s中，#为表达式的结束符，试设计如下算法Match判断表达式中括号（()）是否配对，如果配对，则返回1，否则返回0。int Match(char *s);3. 树采用孩子兄弟链表作为存储结构（结点结构CSTree为（firstchild，data，nextsibling），试设计如下非递归算法Leaf计算树的叶子节点数。int Leaf(CSTree *T); /函数返回值就是树的叶子节点数4. 已知无向图采用邻接表存储方式，试设计如下算法DeletEdge删除图中(i,j)边。void DeletEdge(AdjList g,int i,int j);第 5 页 共 5 页