2016年武汉科技大学856数据结构(C语言版)考研真题(A卷)

2016年武汉科技大学856数据结构（C语言版）考研真题（A卷）(总分：150.00，做题时间：180分钟)一、选择题(总题数：10，分数：20.00)1.以下说法正确的是（）。（分数：2.00）A.数据元素是数据的最小单位B.数据项是数据的基本单位C.数据结构是带有结构的各数据项的集合D.一些表面上很不相同的数据可以有相同的逻辑结构√解析：2.在顺序表（长度为127）中插入一个元素平均要移动（）个元素。（分数：2.00）A.8B.63.5√C.63D.7解析：3.若完全二叉树的结点总数为1001，则度为1的结点有（）个。（分数：2.00）A.0√B.1C.500D.501解析：4.二叉树先序遍历x在y之前，后序遍历x在y之后，则x是y的（）。（分数：2.00）A.左兄弟B.右兄弟C.祖先√D.后裔解析：5.二叉树在线索化后，仍不能有效求解的问题是（）。（分数：2.00）A.前序线索二叉树中求前序后继B.中序线索二叉树中求中序后继C.中序线索二叉树中求中序前驱D.后序线索二叉树中求后序后继√解析：6.下列关于AOE网的叙述中，不正确的是（）。（分数：2.00）A.某些关键活动提前，则整个工程将会提前完成√B.任一关键活动提前，则整个工程将会提前完成C.所有关键活动提前，则整个工程将会提前完成D.关键活动不按期完成会影响整个工程的完成时间解析：7.12个数据有序顺序存储，采用二分查找，查找失败时的ASL值是（）。（分数：2.00）A.37/12B.63/13C.39/12D.49/13√解析：8.二叉查找树的查找效率与二叉树的（）有关。（分数：2.00）A.高度B.结点的多少C.树型√D.结点的位置解析：9.用函数H(k)=key%17构造散列表，则链地址法解决冲突需（）个链表。（分数：2.00）A.17√B.13C.16D.任意解析：10.在快速排序过程中，下列结论正确的是（）。（分数：2.00）A.左、右两个子表都已各自排好序B.左边的元素都不大于右边的元素√C.左边子表长度小于右边子表长度D.左、右两边元素的平均值相等解析：二、填空题(总题数：10，分数：20.00)11.数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的（）等的学科。（分数：2.00）填空项1:__________________（正确答案：关系和操作）解析：12.在单链表（长度为n）给定值x的结点后插入新结点的时间复杂度为（）。（分数：2.00）填空项1:__________________（正确答案：O(n)）解析：13.判断表达式中左右括号是否配对的算法采用（）数据结构最佳。（分数：2.00）填空项1:__________________（正确答案：栈）解析：14.设广义表L=((a,b,c))，则L的长度为（）。（分数：2.00）填空项1:__________________（正确答案：1）解析：15.由4个结点可以构造出（）种不同的二叉树。（分数：2.00）填空项1:__________________（正确答案：14）解析：16.用数组A[0…n-1]存储完全二叉树，则A[i]的右子女是结点（）。（分数：2.00）填空项1:__________________（正确答案：A[2i+2]）解析：17.在一个图中，所有顶点的度数之和等于所有边数的（）倍。（分数：2.00）填空项1:__________________（正确答案：2）解析：18.为了实现图的广度优先搜索，除了一个标志数组标志已访问的结点外，还需（）存放被访问的结点以实现遍历。（分数：2.00）填空项1:__________________（正确答案：队列）解析：19.求图中一个顶点到其它各个顶点最短路径的算法是（）算法。（分数：2.00）填空项1:__________________（正确答案：Dijkstra）解析：20.具有12个记录的序列，采用冒泡排序最少的比较次数是（）。（分数：2.00）填空项1:__________________（正确答案：11）解析：三、综合应用题(总题数：7，分数：70.00)将三对角矩阵A[1..n，1..n]的非零元素逐行存放于数组B[0..3n-3]中，使得B[k］=A[i，j］，求：（分数：10）(1).用i，j表示ｋ的变换公式（分数：5）__________________________________________________________________________________________正确答案：(k=2i+j-3)解析：(2).用ｋ表示i，j的变换公式（分数：5）__________________________________________________________________________________________正确答案：(i=(k+1)/3+1j=(k+1)/3+(k+1)%3)解析：设二叉树的顺序存储结构如下：012345678910111213141516171819eafdgcjhib（分数：10.0）(1).画出该二叉树的逻辑结构（分数：2.5）__________________________________________________________________________________________正确答案：()解析：(2).写出其先序、中序、后序序列（分数：2.5）__________________________________________________________________________________________正确答案：(先序：eadcbjfghi中序：abcdjefhgi后序：bcjdahigfe)解析：(3).画出其后序线索二叉树（分数：2.5）__________________________________________________________________________________________正确答案：()解析：(4).把它转换成对应的森林（分数：2.5）__________________________________________________________________________________________正确答案：()解析：给定序列（26,25,20,33,21,24,45,204,42,38,29,31），要用散列法进行存储，散列函数采用除留余数法，用线性探测法解决冲突，负载因子为0.6。（分数：10）(1).设计哈希函数（分数：3）__________________________________________________________________________________________正确答案：(散列函数H(k)=k%19)解析：(2).画出哈希表（分数：3）__________________________________________________________________________________________正确答案：(0123456789101112131415161718193820214224252345293133204111111121112)解析：(3).计算等概率情况下查找成功和失败的平均查找长度（分数：4）__________________________________________________________________________________________正确答案：(成功：ASL=14/12=7/6不成功：ASL=(4+3+2+1+6+5+4+3+2+1+2+1+2+1+3+2+1+1+1+1)/20=46/20=2.3)解析：对有序表(31,34,45,57,64,70,72,84,88,91,97,105,124)折半查找，要求（分数：10.0）(1).画出描述折半查找过程的判定树；（分数：2.5）__________________________________________________________________________________________正确答案：()解析：(2).若查找元素91，需依次与那些元素比较?（分数：2.5）__________________________________________________________________________________________正确答案：(72、91)解析：(3).若查找元素30，需依次与那些元素比较?（分数：2.5）__________________________________________________________________________________________正确答案：(72、45、31)解析：(4).分别求等概率情况下查找成功和不成功时的平均查找长度。（分数：2.5）__________________________________________________________________________________________正确答案：(查找成功的平均查找长度：（1+2*2+4*3+6*4）/13=41/13不成功时的平均查找长度：(2*3+12*4)/14=54/14=27/7)解析：已知关键字序列（40，35，61，87，72，16，25，50），（分数：10）(1).写出用快速排序方法升序排列该序列一趟后的结果（分数：2）__________________________________________________________________________________________正确答案：(快速排序一趟后的结果：2535164072876150)解析：(2).写出用堆排序进行升序排列时的初始堆（分数：2）__________________________________________________________________________________________正确答案：(堆排序进行升序初始堆：8772615040162535)解析：(3).写出堆排序1趟以后（交换与调整之后）的结果（分数：2）__________________________________________________________________________________________正确答案：(堆排序1趟以后的结果：7250613540162587)解析：(4).写出1趟冒泡排序后的结果（分数：2）__________________________________________________________________________________________正确答案：(1趟冒泡排序后的结果：3540617216255087)解析：(5).写出1趟归并排序后的结果（分数：2）__________________________________________________________________________________________正确答案：(1趟归并排序后的结果：3540618716722550)解析：有以下AOE网：（分数：10.0）(1).求各事件的最早/迟发生时间（分数：2.5）__________________________________________________________________________________________正确答案：(事件V1V2V3V4V5V6V7V8V9V10V11最早发生时间01510655080160190220250270最迟发生时间015156520580160205220250270)解析：(2).求各活动的最早