北京科技大学 计算机研究生入学考试 2002-2007真题答案
作者&投稿:敏姿 (若有异议请与网页底部的电邮联系)
好好准备下专业知识储备,面试时衣装整齐,彬彬有礼,回答要自信,中肯,忌模糊,胡编乱造。祝你面试成功。
国家线只是规定了工科最低复试标准,北京科技大学的计算机专业有自己的专业线,在国家工科线之上,往年一般在310分左右。
北京科技大学2002年招收攻读硕士学位研究生入学考试试题考试科目:数据结构
适用专业:计算机应用技术 计算机软件与理论 系统工程 计算机系统结构
说明:统考生做一~七题,单考生做一、二、三、五、六、八、九题。全部试题答案请务必写在答卷纸上。
一、(20分)回答下列各题:
1.数据的逻辑结构在计算机存储器中的映象(或表示)通常有哪几种方法?
2.请简述算法的确定性之含义。
3.线性结构和树型结构的特点分别是什么?
4.设单链表中结点的数据域为 data,指针域为 next,指针 p 为表中某一结点的地址,请写出在 p 结点之前插入一 s 结点的C语言描述语句。
5.请简述在你所进行的算法设计中运用到栈和队列的两个例子。
6.设一棵三叉树中叶结点数为 n0,度为2、3的结点数分别为 n2、n3,试给出 n0 与 n2、n3 之间的关系。
7.构造无向连通网的最小生成树通常有哪两个典型的算法?
8.在含有 n(n>=0) 个关键字的 m 阶 B-树 上查找时,查找路径上最多涉及多少个结点?
9.请指出三个稳定的和三个不稳定的内排序方法。
10.检索一个ISAM文件是按哪三级索引顺序进行的?一个VSAM文件由哪三部分组成?
二、(10分)算法填空:
求 Huffman 树的带权路径长度(WPL)的算法如下,其中 ht 为树根结点的指针,S 为工作栈,Clearstack(S)、Push(S,p)、Pos(S) 和 Emptystack(S) 分别为置栈空、指针 p 进栈、出栈和判栈空的函数。请填写算法中下画线的空白之处,完成其功能。
三、(10分)
设某单位职工工资表 ST 由 "工资"、"扣除" 和 "实发金额" 三项组成,其中工资项包括 "基本工资"、"津贴" 和 "奖金",扣除项包括 "水"、"电" 和 "煤气" 费用等。
1.请用广义表形式所描述的工资表 ST,并用 GetHead(ST) 和 GetTail(ST) 函数提取表中的奖金项;
2.用C语言描述广义表中的元素结构,并画出该工资表 ST 的存储结构。
四、(10分 此题统考生做)
设一棵二叉树 BT 如下:
1.请画出此二叉树 BT 的 "顺序" 及 "二叉链表" 式存储结构;
2.写出按 "先序"、"中序" 和 "后序" 方法遍历二叉树 BT 所得到的结果序列,并画出 BT 的一棵后序线索二叉树。
五、(15分)
设一个无向网 G 的邻接矩阵 A 如下:
1.请根据给定的邻接矩阵 A 画出网 G 的逻辑结构(G 中顶点用 v1~v8 表示);
2.写出从顶点 v1 出发、按 "深度优先" 和 "广度优先" 搜索方法遍历网 G 所得到的顶点序列;
3.从顶点 v1 出发,按照求最小生成树的 Prim 算法,画出网 G 的一棵最小生成树。
六、(15分)
设记录的关键字(key)集合 K={26, 36, 41, 44, 15, 68, 12, 6, 51, 25}
1.以 K 为权值集合,构造一棵 Huffman 树;依次取 K 中各值,构造一棵二叉排序树;
2.设 Hash 表表长 m=16,选取 Hash 函数的方法为 H(key)=key%13,处理冲突的方法为 "二次探测再散列",请依次取 K 中各值,构造出满足所给条件的 Hash 表结构;
3.设以 K 中第一个关键字(26)为枢轴,写出对 K 按 "快速排序" 方法排序时,第一趟排序结束时的结果,并将 K 调整成一个堆顶元素取最大值的堆。
七、(20分 此题统考生做)
算法设计:
1.设 L 为单向循环链表(不带头结点)第一结点的指针,结点编号分别为 1,2,...,n,从链表中编号为 k(1<=k<=n) 的结点开始计数,计到 m(1<=m<=n) 时的结点出列(删除),再从出列的下一结点从 1 开始计数,计到 m 时的结点又出列,...,依此类推,直到表中所有的结点都出列为止。请用C语言函数形式写出完成此任务的算法:Josephu(L, n, k, m);
2.设有 n 个顶点的向图 G 已用邻接表结构存储,顶点表指针为 g ,且图中各顶点的入度已记录在顶点的 id 域中(即 g->data[ i ].id=第i(1<=i<=n)个顶点的入度)。请用C语言函数形式写出判断图G是否存在回路的算法:Top_cycle(g, n) (注:此算法中可调用栈操作的基本算法)。
八、(10分 此题单考生做)
设森林 F={T1, T2, T3} 如下:
1.若按 "孩子兄弟表示法" 存储此森林 F,请画出其存储结构;
2.写出按 "先序" 和 "中序" 方法遍历森林 F 所得到的结果序列。
九、(20分 此题单考生做)
算法设计:
1.设两个带头结点单链表的头指针分别为 A 和 B ,链表中结点的数据域为 data(设为整形),指针域为 next。请用C语言函数形式写出将表 A 和表 B 合并为一个单链表 L 的算法:Union(A, B, L)(注:若表A和表B中有数据值相同的结点,只保留其中一个);
2.设记录的关键字集合 K={k1, k2,......,kn} 已存入整形数组 A[n] 中,请用C语言函数形式写出将数组 A[n] 调整成一个小根堆的算法:Creatheap(A[n])(注:若 K 中各值满足 ki<=k2i, ki<=k2i+1, i=1,2,......,n/2 时,将 K 视为一个小根堆)。
一、(20分)回答下列各题:
1.数据的逻辑结构在计算机存储器中的映象(或表示)通常有哪几种方法?
2.请简述算法的确定性之含义。
3.线性结构和树型结构的特点分别是什么?
4.设单链表中结点的数据域为 data,指针域为 next,指针 p 为表中某一结点的地址,请写出在 p 结点之前插入一 s 结点的C语言描述语句。
5.请简述在你所进行的算法设计中运用到栈和队列的两个例子。
6.设一棵三叉树中叶结点数为 n0,度为2、3的结点数分别为 n2、n3,试给出 n0 与 n2、n3 之间的关系。
7.构造无向连通网的最小生成树通常有哪两个典型的算法?
8.在含有 n(n>=0) 个关键字的 m 阶 B-树 上查找时,查找路径上最多涉及多少个结点?
9.请指出三个稳定的和三个不稳定的内排序方法。
10.检索一个ISAM文件是按哪三级索引顺序进行的?一个VSAM文件由哪三部分组成?
二、(10分)算法填空:
求 Huffman 树的带权路径长度(WPL)的算法如下,其中 ht 为树根结点的指针,S 为工作栈,Clearstack(S)、Push(S,p)、Pos(S) 和 Emptystack(S) 分别为置栈空、指针 p 进栈、出栈和判栈空的函数。请填写算法中下画线的空白之处,完成其功能。
三、(10分)
设某单位职工工资表 ST 由 "工资"、"扣除" 和 "实发金额" 三项组成,其中工资项包括 "基本工资"、"津贴" 和 "奖金",扣除项包括 "水"、"电" 和 "煤气" 费用等。
1.请用广义表形式所描述的工资表 ST,并用 GetHead(ST) 和 GetTail(ST) 函数提取表中的奖金项;
2.用C语言描述广义表中的元素结构,并画出该工资表 ST 的存储结构。
只看到这个 不知道能不能帮上
北京科技大学2002年招收攻读硕士学位研究生入学考试试题
考试科目:数据结构
适用专业:计算机应用技术 计算机软件与理论 系统工程 计算机系统结构
说明:统考生做一~七题,单考生做一、二、三、五、六、八、九题。全部试题答案请务必写在答卷纸上。
一、(20分)回答下列各题:
1.数据的逻辑结构在计算机存储器中的映象(或表示)通常有哪几种方法?
2.请简述算法的确定性之含义。
3.线性结构和树型结构的特点分别是什么?
4.设单链表中结点的数据域为 data,指针域为 next,指针 p 为表中某一结点的地址,请写出在 p 结点之前插入一 s 结点的C语言描述语句。
5.请简述在你所进行的算法设计中运用到栈和队列的两个例子。
6.设一棵三叉树中叶结点数为 n0,度为2、3的结点数分别为 n2、n3,试给出 n0 与 n2、n3 之间的关系。
7.构造无向连通网的最小生成树通常有哪两个典型的算法?
8.在含有 n(n>=0) 个关键字的 m 阶 B-树 上查找时,查找路径上最多涉及多少个结点?
9.请指出三个稳定的和三个不稳定的内排序方法。
10.检索一个ISAM文件是按哪三级索引顺序进行的?一个VSAM文件由哪三部分组成?
二、(10分)算法填空:
求 Huffman 树的带权路径长度(WPL)的算法如下,其中 ht 为树根结点的指针,S 为工作栈,Clearstack(S)、Push(S,p)、Pos(S) 和 Emptystack(S) 分别为置栈空、指针 p 进栈、出栈和判栈空的函数。请填写算法中下画线的空白之处,完成其功能。
三、(10分)
设某单位职工工资表 ST 由 "工资"、"扣除" 和 "实发金额" 三项组成,其中工资项包括 "基本工资"、"津贴" 和 "奖金",扣除项包括 "水"、"电" 和 "煤气" 费用等。
1.请用广义表形式所描述的工资表 ST,并用 GetHead(ST) 和 GetTail(ST) 函数提取表中的奖金项;
2.用C语言描述广义表中的元素结构,并画出该工资表 ST 的存储结构。
四、(10分 此题统考生做)
设一棵二叉树 BT 如下:
1.请画出此二叉树 BT 的 "顺序" 及 "二叉链表" 式存储结构;
2.写出按 "先序"、"中序" 和 "后序" 方法遍历二叉树 BT 所得到的结果序列,并画出 BT 的一棵后序线索二叉树。
五、(15分)
设一个无向网 G 的邻接矩阵 A 如下:
1.请根据给定的邻接矩阵 A 画出网 G 的逻辑结构(G 中顶点用 v1~v8 表示);
2.写出从顶点 v1 出发、按 "深度优先" 和 "广度优先" 搜索方法遍历网 G 所得到的顶点序列;
3.从顶点 v1 出发,按照求最小生成树的 Prim 算法,画出网 G 的一棵最小生成树。
六、(15分)
设记录的关键字(key)集合 K={26, 36, 41, 44, 15, 68, 12, 6, 51, 25}
1.以 K 为权值集合,构造一棵 Huffman 树;依次取 K 中各值,构造一棵二叉排序树;
2.设 Hash 表表长 m=16,选取 Hash 函数的方法为 H(key)=key%13,处理冲突的方法为 "二次探测再散列",请依次取 K 中各值,构造出满足所给条件的 Hash 表结构;
3.设以 K 中第一个关键字(26)为枢轴,写出对 K 按 "快速排序" 方法排序时,第一趟排序结束时的结果,并将 K 调整成一个堆顶元素取最大值的堆。
七、(20分 此题统考生做)
算法设计:
1.设 L 为单向循环链表(不带头结点)第一结点的指针,结点编号分别为 1,2,...,n,从链表中编号为 k(1<=k<=n) 的结点开始计数,计到 m(1<=m<=n) 时的结点出列(删除),再从出列的下一结点从 1 开始计数,计到 m 时的结点又出列,...,依此类推,直到表中所有的结点都出列为止。请用C语言函数形式写出完成此任务的算法:Josephu(L, n, k, m);
2.设有 n 个顶点的向图 G 已用邻接表结构存储,顶点表指针为 g ,且图中各顶点的入度已记录在顶点的 id 域中(即 g->data[ i ].id=第i(1<=i<=n)个顶点的入度)。请用C语言函数形式写出判断图G是否存在回路的算法:Top_cycle(g, n) (注:此算法中可调用栈操作的基本算法)。
八、(10分 此题单考生做)
设森林 F={T1, T2, T3} 如下:
1.若按 "孩子兄弟表示法" 存储此森林 F,请画出其存储结构;
2.写出按 "先序" 和 "中序" 方法遍历森林 F 所得到的结果序列。
九、(20分 此题单考生做)
算法设计:
1.设两个带头结点单链表的头指针分别为 A 和 B ,链表中结点的数据域为 data(设为整形),指针域为 next。请用C语言函数形式写出将表 A 和表 B 合并为一个单链表 L 的算法:Union(A, B, L)(注:若表A和表B中有数据值相同的结点,只保留其中一个);
2.设记录的关键字集合 K={k1, k2,......,kn} 已存入整形数组 A[n] 中,请用C语言函数形式写出将数组 A[n] 调整成一个小根堆的算法:Creatheap(A[n])(注:若 K 中各值满足 ki<=k2i, ki<=k2i+1, i=1,2,......,n/2 时,将 K 视为一个小根堆)。
网上没有答案的楼主,这不是英语政治等公共课,找师哥们要或者是自己总结吧!
如果不怕花钱,圣才考研网就可以一次买齐,前提有钱,呵呵!
鲜要眼氨: 还可以,北京好学校多 ,不过计算机也是北科大重点学科 ,有一定难度 ;但是比起 北理工 北航 北邮还是低不少;据往年分数,北京科技大学计算机研究生大概考340分有把握,再怎么着也是国家重点大学211,差不到那里去.
磁县13589107160: 北京科技大学考研是自主命题还是全国统考 - ?
鲜要眼氨: 计算机科学与技术专业,现在虽说是全国统考但传说有的好学校是自主命题.询问下北京科技大学,北邮,北理工,北交,北工大分别都是统考还是自主命题
磁县13589107160: 谁能告诉我北京科技大学和北京工业大学这两个学校的计算机专业哪个强点? - ?
鲜要眼氨: 研究生考试吗?论计算机方面都不错,北工的分低,国家线至国家线上10分左右就可以,北科大的分数线大概在国家线20分以上才能保证录取.计算机专业研究生入学考试4门课都是国家统一考试!
磁县13589107160: 关于北京科技大学考研计算机专业的一些疑问 - ?
鲜要眼氨: 楼主所说的工程硕士从2009年开始就可以招收应届毕业生.而且毕业时双证 毕业证 学位证 fengying_zr 说的工程硕士 是在职的 和你看到的是不同.在职的工程硕士不参见全国统考.也就是不参加每年1月的入学考试.现在你说的这两个工程硕士和学术型硕士没有任何区别.只是奖学金上可能不同,社会认可度现在还清楚 因为09年的第一批还没有毕业,但是从10年的分数线来看,我觉得不会比学术型的差.因为工程硕士也是和学术型硕士同意个国家线 A区 275 36 54 相比来说考的人少 但是招收的人也少,11年来说应该报考工程硕士的人数会增加.!
磁县13589107160: 计算机科学与技术专业考研 - ?
鲜要眼氨: 清华,北航,北大,北邮,北理工,最好的也是最难考的是清华,一般不建议考,招生人数太少,北航如果基础比较好可以考虑报考.不过据说虽说去年复试线为340,但360以下基本都被刷了.北大复试线也340,复试相对北航容易点,北邮虽然不是985,计算机那也是相当的强,去年复试线为300,不过前面是330,复试也是有点难度,上机要求严,笔试科目比较多,北理工是985,但是这几所学校中最容易的,复试相对简单,一般320可以上.望采纳
磁县13589107160: 2011年北京科技大学研究生入学考试计算机网络简答题:什么是双绞线的近端串扰? - ?
鲜要眼氨: 双绞线近端串扰是指在UTP电缆链路中一对线与另一对线之间的因信耦合效应而产生的串扰有时它也被称为线对间.由于5类UTP线缆由4个线对组成,依据排列组合的方法可知共有六种组合方式.
磁县13589107160: 北京科技大学计算机数学考研考数一还是数二 - ?
鲜要眼氨: 北科考研材料专业考数二;材料科学与工程专业考研的话,基本上高校都是考数二,考数二不考概率,特牛逼学校,清华和上交考数学一.
磁县13589107160: 085404考研考什么 - ?
鲜要眼氨: 085404专业是计算机技术,考研一般考下面四门课程,政治、英语还有两门专业课: 思想政治理论 (101) 英语(二) (204) 数学(一) (301) 计算机学科专业基础 (408) 补充: 1. 专业介绍:085404计算机技术(专业学位) 计算机...
磁县13589107160: 计算机技术考研,北工和北科哪个好 - ?
鲜要眼氨: 北京科2113技大学 北京科技大学(5261University of Science & Technology Beijing,USTB),简称“4102北科大1653”,是教育部直属全国重点专大学,为国属家“211工程”、“985工程优势学科创新平台”重点建设
磁县13589107160: 北邮,北理,北航,北科计算机考研 - ?
鲜要眼氨: 你这个专业是数学系的,就业不怎么样,一般这个专业的学生考研都考经济或者计算机等专业.你的想法很好.计算机专业的话,北航最好,北邮、北理也都不错.北科大最强的是材料、冶金等专业,计算机不太了解,应该很一般吧.要说最好...