2018年武汉科技大学考研专业课A卷-856-数据结构(C语言版)及答案.doc

1、姓名：报考专业：准考证号码：密封线内不要写题2018年全国硕士研究生招生考试初试自命题试题科目名称：数据结构（C语言版）（A卷B卷）科目代码：856考试时间：3小时 满分 150 分可使用的常用工具：无 计算器 直尺 圆规（请在使用工具前打）注意：所有答题内容必须写在答题纸上，写在试题或草稿纸上的一律无效；考完后试题随答题纸交回。一、选择题(共10小题，每小题2分，共20分)1. 当顺序栈ST（最多元素为MaxSize）为空时，其栈顶指针top的值为-1，那么判断栈ST栈满的条件是（）。A）ST.top != -1 B）ST.top = -1 C）ST.top != MaxSize 1 D）S

2、T.top = MaxSize 12. 已知单链表中结点 q是结点 p的直接前趋，若在 q与 p之间插入结点*s，则应执行以下（）操作。A）s-link=p-link; p-link=s; B）q-link=s; s-link=p;C）p-link=s-link; s-link=p; D）p-link=s; s-link=q；3. 非空的循环单链表head的尾结点（由p所指向）满足（）。A）p-next=head B）p=NULL C）p-next=NULL D）p=head4. 设x和y是二叉树中的任意两个结点，若在先序遍历中x在y之前，而在后序遍历中x在y之后，则x和y的关系是（）。A）x

3、是y的左兄弟 B）x是y的右兄弟C）x是y的祖先 D）x是y的子孙5. 哈夫曼树是n个带权叶子结点构成的（）最小的二叉树。A）权值 B）高度 C）带权路径长度 D）度6. 有向图G包含6个顶点（编号从1到6）8条弧（, ,，权值依次为2,15,10,19,4,11,6,5）。图G的关键路径为（）。A） B）C） D）7. 在一个有权无向图中，如果顶点b到顶点a的最短路径长度是10，顶点c与顶点b之间存在一条长度为3的边。那么下列说法中有几句是正确的？（1）c与a的最短路径长度是13 （2）c与a的最短路径长度是7（3）c与a的最短路径长度不超过13 （4）c与a的最短路径不小于7A）1句 B）

4、2句 C）3句 D）4句8. 二分查找法所需的平均比较次数为（）。A）O(n2) B）O(nlog2n) C）O(n) D）O(log2n)9. 在Hash函数H(k)=k MOD m中，一般来讲m应取（）。A）奇数 B）偶数 C）素数 D）充分大的数10.用二分插入排序法进行排序，被排序的表应采用的数据结构是（）。A）数组 B）单链表 C）双向链表 D）散列表二、填空题(共10小题，每小题2分，共20分)1. 一个栈的入栈序列为1,2,3,n，其出栈序列是p1,p2,p3,pn 。若p2 = 3，则p3可能取值的个数是（）。2. 已知单链表A长度为m，单链表B长度为n，若将B连接在A的末尾，

5、在没有链尾指针的情形下，算法的时间复杂度应为（）。3. 从一个具有n个结点的有序单链表中查找其值等于x的结点时，在查找成功的情况下，需要平均比较（）个结点。4. 对于一个有N个结点、K条边的森林，共有（）棵树。 5. 若以4，5，6，3，8作为叶子节点的权值构造哈夫曼树，则带权路径长度是（）。6. 有向图包含5个顶点（编号从1到5）6条弧（, ）。该图进行拓扑排序，可以得到（）个拓扑序列。7. 对于一个有向图，若一个顶点的入度为k1,出度为k2，则对应邻接表中该顶点邻接点单链表中的结点数为（）。8. 设哈希函数H（K）=3 K mod 11，哈希地址空间为010，对关键字序列（32，13，49

6、，24，38，21，4，12）按线性探测法解决冲突的方法构造哈希表，则该哈希表等概率下查找成功的平均查找长度为（）。 9. 对于长度为n的线性表，若进行顺序查找，则时间复杂度为（）。10. 排序方法中，从未排序序列中依次取出元素与已排序序列（初始为空）中的元素进行比较，将其放入已排序序列的正确位置上的方法称为（）。三、判断题(对的答错的答，共10小题，每小题2分，共20分)1. 不论是入队列还是入栈，在顺序存储结构上都需要考虑“溢出”情况。2. 在顺序表中取出第i个元素所花费的时间与i成正比。3. 线性表的插入、删除总是伴随着大量数据的移动。4. 二叉树通常有顺序存储结构和链式存储结构。5.

7、对N（2）个权值均不相同的字符构造哈夫曼树，则树中任一非叶结点的权值一定不小于下一层任一结点的权值。6. Prim 算法通过每步添加一条边及相连顶点到一棵树，从而生成最小生成树。7. 用邻接矩阵存储图，占用的存储空间只与图中结点数有关，而与边数无关。8. 散列查找主要解决的问题是找一个好的散列函数和有效解决冲突的办法。9. 对长度为10的排好序的表用二分法检索，若检索不成功，至少需比较10次。10. 对5个不同的数排序至少需要比较4次。四、综合应用题(第1小题15分，第2，3，4小题各10分，共45分)1. 分别给出在先序线索二叉树、中序线索二叉树和后序线索二叉树中结点p的直接后继结点所在位置

8、。线索二叉树中结点的结构包括数据域data、左孩子域left、右孩子域right、左标志域ltag和右标志域rtag，标志域为0表示没有孩子，孩子域为线索。2. 已知一棵树的先序序列（ABEFIGCDHJKLNOM）和后序序列（EIFGBCJKNOLMHDA）。（1）请画出该树的逻辑结构（2）写出该树的层次遍历序列（3）如果采用孩子链表表示法来存储该树，画出其存储示意图（4）画出对应的二叉树3. 给定关键字序列（36,23,51,6,58,48,39,8,88,76,63,17）（1）按表中顺序建立一颗初始为空的二叉排序树，画出该二叉排序树。（2）求上述二叉排序树中等概率情况下的查找成功的平均

9、查找长度。（3）对上述关键字按从小到大的顺序排序，画出其折半查找判定树。（4）采用折半查找，求等概率情况下查找不成功的平均查找长度。4. 下面程序采用快速排序算法对数组按从小到大排序。将空白处填写完整。int Partion(int a,int low,int high) while(lowhigh)while(low=temp) high-; while(lowhigh&alow=high) return;pivotloc=Partion(a,low,high);QSort(a,low,pivotloc-1); 五、算法设计(共3小题，每小题15分，共45分)1. 某仓库中有一批设备（都有唯

10、一的商品编号），已按照商品编号从小到大的顺序构成一个带头结点的单链表，每个结点有商品编号、数量（均大于0）和链指针三个域。现在仓库管理员新购进n台商品编号为x的商品，请设计一个算法对上述单链表的数据进行更新。2. 二叉树采用二叉链表存储，设计算法，打印出由根结点T出发到达每一个叶子结点的路径。3. 图G采用邻接表作为存储结构，请设计一个算法对图G进行广度优先遍历。参考答案(A)一、选择题（共10小题，每题2分，共20分）DBACC BBDCA二、填空题（共10小题，每题2分，共20分）1. n-1 2. O(m) 3. (n+1)/2 4. N-K 5. 59 6. 3 7. K2 8. 11

11、/8 9. O（n） 10. 插入排序三、判断题(对的答错的答，共10小题，每小题2分，共20分) 四、综合应用题(第1小题15分，第2，3，4小题各10分，共45分)1. （1）先序线索二叉树中结点p的直接后继结点就是其左孩子指针指向的结点p-left（5分）（2）中序线索二叉树中结点p的直接后继结点所在位置（5分）如果p-rtag=0，p的直接后继结点就是p-right；否则，p的直接后继结点s就是p的右子树上中序的第一个结点，s通过如下方法求得 s=p-right; while(s-ltag=1) s=s-left;（3）后序线索二叉树中结点p的直接后继结点所在位置（5分） 如果结点p为

12、树根结点，则其直接后继结点为NULL 如果结点p是其双亲f的右孩子或者p是其双亲f的左孩子但其双亲无右孩子，则其直接后继结点为其双亲结点f； 如果结点p是其双亲f的左孩子且其双亲f有右孩子，则结点p的直接后继结点s为双亲右子树上后序遍历的第一个结点，s通过如下方法求得s=f-right; while(s-ltag) s=s-left;2. （1）3分 （2）1分 （3）3分 （4）3分层次遍历：ABCDEFGHIJKLMNO3. （1）3分 （2）2分 （3）3分 （4）2分ASL=（1*1+2*2+3*3+3*4+2*5+1*6）/12=42/12=7/2 ASL=（3*3+10*4）/12

13、=49/124.（1）int temp=alow; （2）alow = ahigh; （3）ahigh=alow; （4）low; （5）QSort(a, pivotloc+1,high);五、算法设计(共3小题，每小题15分，共45分)1. Typedef struct nodeInt no;/商品编号Int num; /数量Struct node *next;*LinkList;void UpdataList(LinkList &L, int x, int n)p=L;while(p-next) if(p-next-no=x) p-num+=n; break; else if(p-next

14、-nox) q=(LinkList)malloc(sizeof(struct node); q-no=x; q-num=n; q-next=p-next; p-next=q; break; else p=p-next;2void PrintPath (BiTree T) /非递归后续遍历，找到指定节点后，栈中结点即路径 BiTree Stackmaxsize; int top; top=0; /初始化栈 p=T; while(p) /左结点入栈,tag=0表示其左子树已入栈，tag=1表示其右子树已入栈 tagtop=0; Stacktop+=p; p=p-lchild; while(top0

15、) /栈不为空 p=Stacktop-1; /取栈顶结点 if(p-lchild=NULL&p-rchild=NULL) printf(“根结点T到s之间路径为：”); for(i=0;idata); printf(“n”); if(p-rchild=NULL|tagtop-1=1) /不存在右子树或右子树已访问 p=Stack-top; /出栈并访问 else /栈顶结点的右子树存在且未入栈 tagtop-1=1; /该结点的右子树已入栈 p=p-rchild; p=p-rchild; while(p) /左结点入栈,tag=0表示其左子树已入栈，tag=1表示其右子树已入栈 tagtop=0; Stacktop+=p; p=p-lchild; 3void BFS(Graph G)for(v=0;vG.vexnum;v+) visitedv=FALSE;InitQueue(Q);for(v=0;vnextarc) k=p-adjvex; if(!visitedk) visitedk=true; visit(k); EnQueue(Q,k); 第 7 页 共 7 页