《北京交通大学-925-2016-真题.pdf》由会员分享，可在线阅读，更多相关《北京交通大学-925-2016-真题.pdf（9页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、北京交通大学2016年硕士研究生入学考试试卷科目代码：竺主科目名称：数据结构共9页，第1页注意事项：答案一律写在答题纸上写在试卷上的不予装订和评分！一、单选题（本大题共15小题，每小题2分，共30分）I.下面程序段的时间复杂度是()。for(i=l;i=n；i+)x=O;forG=l;j=O 7荨三二三产D以上都才对8.一棵哈夫曼树共有上欢饮结点户对其进行哈夫曼编码，总共得到（）个不同的码字。A.78C.157D.1589.对千一个具有丫个顶点和e条边的无向图，若采用邻接表表示，则表头向量的大小为（），邻接表中的全部结点总数是().A.n+l 和2eB.n和2eC n+l和eD.n和e10.下
2、面哪一个方法可以判断出一个有向图是否有环（）A.求最小生成树B.拓扑排序C.求最短路径D.求关键路径各个学校计算机/软件专业考研真题 免费分享 h t t p s:/g i t h u b.co m/cs s e k y/cs k a o y a n获取 考研经验/复试资料/考研资讯 关注微信公众号 计算机与软件考研 微信公众号 计算机与软件考研北京交通大学2016年硕士研究生入学考试试卷科目代码：竺i科目名称：数据结构共9页，第2页注意事项：答案一律写在答题纸上写在试卷上的不予装订和评分！11.下列关于最小生成树的说法中，正确的是()。(1)最小生成树的代价唯一(2)权值最小的边一定会出现在
3、所有的最小生成树中(3)用Prim算法从不同顶点开始得到的最小生成树的形态一定相同(4)Prim算法 和Kruskal算法得到的最小生成树的形态总不相同A.仅（1)B.仅（2)C.仅(1)(3)D.仅（2)(4)12.如下有向带权图，若采用迪杰斯特拉(D ijkstra)算法求源点 a到其他各顶点的最短路径，得到的第一条最短路径的目标顶点是b,第二条最短路径的目标顶点是C,后续得到的其余各最短路径的目标顶点依次是().A.d,e,f 13.AVL树是一种平衡的二14.对序歹I15.若数据元素后的结果，则B.e,d,f C.f,d,e D.f,e,d 不超过1的高度3,6,33用希恳患萝珛闭产经
4、一趟排序后序列变为IO,3,6,序rO）尸厂C:3 D.47,8,9,23,4,5 是采用下列排序方法之一得到的第二趟排序A.起泡排序B.插入排序C.选择排序D.二路归并排序二、填空题（本大题共15小题，每小题2分，共30分）1.设a=4，b=2,c=1,d=2,e=2，则后缀表达式”abc-d*/e-”的值是2.一个循环队列存千长度为n的一维数组B(O,n-1中，假定队列满时，队列中有n-1 个元素，如果front指向队首元素在数组中的下标，rear指向队尾元素在数组中下一位置的下标，则求队列中元素个数的表达式为3.用S表示入栈操作，X表示出栈操作，若元素入栈的顺序为12345,，为了得到3
5、4251的出栈顺序，相应的S和X的操作串为各个学校计算机/软件专业考研真题 免费分享 h t t p s:/g i t h u b.co m/cs s e k y/cs k a o y a n获取 考研经验/复试资料/考研资讯 关注微信公众号 计算机与软件考研 微信公众号 计算机与软件考研北京交通大学2016年硕士研究生入学考试试卷科目代码：竺2科目名称：数据结构共9页，第3页注意事项：答案一律写在答题纸上写在试卷上的不予装订和评分！4.一个n阶对称矩阵可以压缩存储在长度为的一维数组中5.稀疏矩阵中的元素以三元组顺序表来表示，则三元组表中的矩阵元素(4,8,6)在相应转置矩阵中的三元组表示为6
6、.广义表E=(b，E)的长度是，深度是7.在只有度为0和度为K的结点的K叉树中，设度为0的结点有no个，度为K的结点有nk个，则nO与nk的关系是8.在结点个数为n(nl)的各棵树中，高度最小的树有层。9.一棵二叉树的后序遍历序列为FDBGECA,中序遍历序列为DFBAEGC,则先序遍历序列为10.若二叉树先序遍历的扩展序列为AB*CDE*F*，其中代表空链域，则一为11.由权值分别为 7,10,12,1,5 的叶子结点生成一棵哈夫曼树，它12.已知 3阶 B树结构如下图所示，当插入数据“80乙;，新的根是/U示14.快速排序在最坏情况下的时间性能是15.对关键字序列(742,87,53,13
7、4,9,91)采用链式基数排序方法由大到小降序排序，第一趟排序后的结果为各个学校计算机/软件专业考研真题 免费分享 h t t p s:/g i t h u b.co m/cs s e k y/cs k a o y a n获取 考研经验/复试资料/考研资讯 关注微信公众号 计算机与软件考研 微信公众号 计算机与软件考研北京交通大学2016年硕士研究生入学考试试卷科目代码：925科目名称：数据结构共9页，第4页注意事项：答案一律写在答题纸上写在试卷上的不予装订和评分！三、判断对错题（本大题共15题，每小题1分，共15分）1顺序表共有n个数据元素，要在第i(lin)个数据元素之后插入一个元素，共要
8、移动n-i+I个数据元素。()2.链表中访问结点和增加、删除结点的平均时间复杂度为O(n)和O(n)().3.一个n阶对称矩阵，矩阵元为生j，将其下三角部分以行序为主序存放在一维数组MO,n(n+l)/2-l中，设矩阵最左上角矩阵元为劲o,则矩阵元a86对应的位置为M42.()4.在一棵二叉树中，假定每个分支结点只有右子树，没有左子树，对它分别进行先序遍历和中序遍历，则具有相同的结果。(5.若有一个结点是某二叉树的中序遍历序列中的最后一个结点，则它必是的最后一个结点。()6.对于有n个结点的二叉树，其高度为log2n。(7.树的度是指根结点的最大子树数。.,）AOV网进凭拓才讨剕氛得到的拓扑有
9、序序列不一；平深：詈骂二孩二骂mgJJJ：；，的的：二二足(N=2x仙mJh-l.况13若采用开放定昙嘉fijl1除元素只需直接将该元素从哈希表中删去即可。（14.归并排序是稳方法，在最坏情况下时间复杂度是O(nlogn)。()、丿、丿15.就排序算法平均所用的辅助空间而言，堆排序、快速排序、归并排序的大小关系是堆排序快速排序归并排序。()四、综合题（本大题共7题，每小题5分，共35分）I.已知与树T对应的二叉树如右图所示，其二叉链表存储结构为：typedefstruct CSNodeElem data:struct CSNode*firstchild,*nextsibling;CSNode,
10、*CSTree;写出树T的所有从树根到叶子的路径，并给出判断叶子结点的条件。二各个学校计算机/软件专业考研真题 免费分享 h t t p s:/g i t h u b.co m/cs s e k y/cs k a o y a n获取 考研经验/复试资料/考研资讯 关注微信公众号 计算机与软件考研 微信公众号 计算机与软件考研北京交通大学2016年硕士研究生入学考试试卷科目代码：925 科目名称：数据结构共9页，第5页注意事项：答案一律写在答题纸上写在试卷上的不予装订和评分！2.已知广义表A按表头表尾分析法的存储结构如下图所示，请给出该广义表并求其深度和长度。A11 I/3.已知无向网G的邻接表
11、存储结构如下图所示。(I)画出无向(2)根据给出贷矗记从顶点A出发，求它的深度优先遍历序列；(3)以顶点A为起点根据普里姆(Prim)算法求它的最小生成树时，第一个被加入到生成树的顶点是B,写出第2个被加入的顶点。4.在右图所示的二叉树上添加线索（用虚线将前驱线索序线索二叉树。D)l G各个学校计算机/软件专业考研真题 免费分享 h t t p s:/g i t h u b.co m/cs s e k y/cs k a o y a n获取 考研经验/复试资料/考研资讯 关注微信公众号 计算机与软件考研 微信公众号 计算机与软件考研北京交通大学2016年硕士研究生入学考试试卷科目代码：925科目
12、名称：数据结构共9页，第6页注意事项：答案一律写在答题纸上写在试卷上的不予装订和评分！5.已知一组关键字序列为：（20,36,48,95,53,100,120,60,15,30,25)。(1)直接画出其构成的二叉排序树：(2)直接画出其构成的二叉平衡树。6.在地址空间为0-15的散列区中，对关键字序列(Jan,Feb,Mar,Apr,May,June,July,Aug,Sep,Oct,Nov,Dec)构造哈希表。设哈希函数为H(x)=t.i/2，其中i为关键字中第一个字母在字母表中的序号，用线性探测开放定址法处理冲突。(1)画出所构造的散列表；(2)计算等概率情况下查找成功以及查找不成功的平均
13、查找长度。7.已知序列167,87,12,35,113,100,20,70,38,58，请用堆排序法挑选出前2个最小元素。(1)直接画出建立的初始最小堆(2)直接画出筛选出第2个最小元素后的最小堆(3)求出通过筛选获得第2个最小元素时关键字的比较次数。五、算法题（本大题共4题，每小题10分，共40分）1.下面是实现折半查找的递归算法，low返回I,查找失败或其它错误则typedef struct KeyType key;InfOTyp th.nfo;伈呻叶祒阮冷List n+l;i孕；夕衍ypeK)尥nigh)return O;mid=_(2)_._:if(R mid.key=K)return
14、 _lll_:if(R mid.keyK).f();else f(?);各个学校计算机/软件专业考研真题 免费分享 h t t p s:/g i t h u b.co m/cs s e k y/cs k a o y a n获取 考研经验/复试资料/考研资讯 关注微信公众号 计算机与软件考研 微信公众号 计算机与软件考研北京交通大学2016年硕士研究生入学考试试卷科目代码：925科目名称：数据结构共9页，第7页注意事项：答案一律写在答题纸上，写在试卷上的不予装订和评2.下面算法的功能是从顶点u出发构造网G的最小生成树，请在处将算法补齐。（每空2分，共10分）typedef struct ArcC
15、ell VRType adj;InfoType*info;ArcCell,AdjMatrix MAX MAX;typedef struct VertexType vexsMAX；AdjMatrix arcs;int vexnum,arcnum;MGraph;typedef struct VertexType VRType closedge MAX;lffor归心Gvexn三五霆了-、，位置u,G.arcskO.adj;closedg嗅砂蜓t-=O;for(i=l;iG.vexnum;+i)_ill_=minimum(closedge);printf(closedgek)adjvex,G,vex
16、sk);ill for0=O;j#include typedef struct node int key;struct node*next;CHA邸；void Unknown I(CHAINH.*HTC)CHAINH*p;int i,j;i=O;scanf(%d,&i);while(i!=-99)j=j%7;p=(CHATNH*)mallo p-next=HTCO;p=HTCOJ;if(p！NULL)while(p-key!=k)&(p-next!=NULL)p=p-next;if(p-key=k)return 1;else return O;else return O;各个学校计算机/软件专
17、业考研真题 免费分享 h t t p s:/g i t h u b.co m/cs s e k y/cs k a o y a n获取 考研经验/复试资料/考研资讯 关注微信公众号 计算机与软件考研 微信公众号 计算机与软件考研北京交通大学2016年硕士研究生入学考试试卷科目代码：竺主科目名称：数据结构共9页，第9页注意事项：答案一律写在答题纸上写在试卷上的不予装订和评分！void Unknown3(CHAINH*HTC,int i)CHAINH*p;int j;j=i%7;p=(CHAINH*)malloc(sizeof(CHAINH);p-next=HTCj；p-key=i;HTCjp;ma
18、inO CHAINH*HTC7;inti,k;for(i=O;i7;i-H-)HTCi-NU Unknown!(HTC)覃气1221.l 16 25气夕2)(_/(贷芦 (HTC,i);-二叉树中所有叶结点的带权路径长度之和，例如下面的二叉。,（共10分）给定一，采用二叉链表存储，结点结构为：I weight I right 其中叶结点的weight域保存该结点的非负权值。设root为指向T的根结点的指针，设计求T的WPL的算法。关键之处给出注释。各个学校计算机/软件专业考研真题 免费分享 h t t p s:/g i t h u b.co m/cs s e k y/cs k a o y a n获取 考研经验/复试资料/考研资讯 关注微信公众号 计算机与软件考研 微信公众号 计算机与软件考研