《北京交通大学-925-2016-真题》由会员分享，可在线阅读，更多相关《北京交通大学-925-2016-真题（9页珍藏版）》请在金锄头文库上搜索。
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+
2、l和eD. n和e10.下面哪一个方法可以判断出一个有向图是否有环（）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)最小生成树的代
3、价唯一(2)权值最小的边一定会出现在所有的最小生成树中(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
4、 D. f, e, d 不超过1的高度3, 6, 33用希恳患萝珛闭产经一趟排序后序列变为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指向队尾元素在数组中下一位置的下标，则求队列中元
5、素个数的表达式为3.用S表示入栈操作，X表示出栈操作，若元素入栈的顺序为12345,，为了得到34251的出栈顺序，相应的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
6、.稀疏矩阵中的元素以三元组顺序表来表示，则三元组表中的矩阵元素(4, 8, 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树结构如下图
7、所示，当插入数据“80乙;，新的根是/U示14. 快速排序在最坏情况下的时间性能是15. 对关键字序列(742, 87, 53, 134, 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页注意事项：答案一律写在答题纸上写在试卷上的
8、不予装订和评分！三、 判断对错题（本大题共15题， 每小题1分， 共15分）1顺序表共有n个数据元素，要在第i(lin)个数据元素之后插入一个元素，共要移动n-i+I个数据元素。() 2.链表中访问结点和增加、删除结点的平均时间复杂度为O(n)和O(n)( ). 3.一个n阶对称矩阵，矩阵元为生j，将其下三角部分以行序为主序存放在一维数组MO,n(n+l)/2-l中，设矩阵最左上角矩阵元为劲o,则矩阵元a86对应的位置为M42. ( ) 4.在一棵二叉树中，假定每个分支结点只有右子树，没有左子树，对它分别进行先序遍历和中序遍历， 则具有相同的结果。(5.若有一个结点是某二叉树的中序遍历序列中的
9、最后一个结点，则它必是的最后一个结点。()6.对于有n个结点的二叉树，其高度为log2n。(7.树的度是指根结点的最大子树数。.,） AOV网进凭拓才讨剕氛得到的拓扑有序序列不一；平深：詈骂二孩二骂mgJJJ：；，的的：二二足(N=2x仙mJh-l. 况13若采用开放定昙嘉fijl1除元素只需直接将该元素从哈希表中删去即可。（14.归并排序是稳方法，在最坏情况下时间复杂度是O(nlogn)。() 、丿、丿15.就排序算法平均所用的辅助空间而言，堆排序、快速排序、归并排序的大小关系是堆排序快速排序归并排序。() 四、综合题（本大题共7题， 每小题5分，共35分）I.已知与树T对应的二叉树如右图所
10、示，其二叉链表存储结构为：typedefstruct CSNodeElem data: struct CSNode *firstchild, *nextsibling; CSNode, *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 科目名称： 数据
11、结构共9页，第5页注意事项：答案一律写在答题纸上写在试卷上的不予装订和评分！2.已知广义表A按表头表尾分析法的存储结构如下图所示，请给出该广义表并求其深度和长度。A11 I / 3.已知无向网G的邻接表存储结构如下图所示。(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 /c
12、s s e k y /cs k a o y a n获取 考研经验/复试资料/考研资讯 关注微信公众号 计算机与软件考研 微信公众号 计算机与软件考研北京交通大学2016年硕士研究生入学考试试卷科目代码：925科目名称：数据结构共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,
13、Aug,Sep,Oct, Nov, Dec)构造哈希表。 设哈希函数为H(x)=t.i/2， 其中i为关键字中第一个字母在字母表中的序号， 用线性探测开放定址法处理冲突。(1) 画出所构造的散列表；(2)计算等概率情况下查找成功以及查找不成功的平均查找长度。7.已知序列167,87,12,35,113,100,20,70,38,58，请用堆排序法挑选出前2个最小元素。(1)直接画出建立的初始最小堆(2)直接画出筛选出第2个最小元素后的最小堆(3)求出通过筛选获得第2个最小元素时关键字的比较次数。五、算法题（本大题共4题， 每小题10分，共40分） 1.下面是实现折半查找的递归算法，low返回I
14、, 查找失败或其它错误则typedef struct KeyType key; InfOTyp th.nfo; 伈呻叶祒阮冷List n+l ;i孕；夕衍ypeK) 尥nigh)return O; mid=_ (2) _. _ : if (R mid.key=K) return _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获取 考研经验/复试资料/考研资讯 关注微信公众号 计算机与软件考研 微信公众
15、号 计算机与软件考研北京交通大学2016年硕士研究生入学考试试卷科目代码：925科目名称：数据结构共9页，第7页注意事项：答案一律写在答题纸上， 写在试卷上的不予装订和评2.下面算法的功能是从顶点u出发构造网G的最小生成树，请在处将算法补齐。（每空2分，共10分）typedef struct ArcCell VRType adj; InfoType *info; ArcCell, AdjMatrix MAX MAX; typedef struct VertexType vexsMAX；AdjMatrix arcs; int vexnum, arcnum; MGraph; typedef str
16、uct 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,vexsk); ill for0=O;j#include typedef struct node int key; struct node *next; CHA邸；void Unknown I (CHAINH. *HTC) CHAINH *p; int i, j;
17、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; 各个学校计算机/软件专业考研真题 免费分享 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获取 考研经验/复试资料/考研资
18、讯 关注微信公众号 计算机与软件考研 微信公众号 计算机与软件考研北京交通大学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; mainO CHAINH *HTC7; inti, k; for (i = O; i7; i-H-) HTCi-NU Unkn
19、own!(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获取 考研经验/复试资料/考研资讯 关注微信公众号 计算机与软件考研 微信公众号 计算机与软件考研
