北京邮电大学1999年数据结构试题
来自免费考研网www.freekaoyan.com
1.;2.答案卷应字迹清楚、语义确切;3.算法应说明基本思路,应对主要数据类型、变量给出说明,所写算法应结构清晰、简明易懂,应加上必要的注释; 4.算法可用(类)PASCAL语言、C语言等你所熟悉的高级语言编写,但要注明语种。
来自免费考研网www.freekaoyan.com
1 (10分) 选择填空
① 字符串’ababaabab’的nextval为
A.(0,1,0,1,0,4,1,0,1) B.(0,1,0,1,0,2,1,0,1,) C.(0,1,0,1,0,0,0,1,1,) D.(0,1,0,1,0,1,0,1,1)
②广义表A=(a,b,(c,d),(e,(f,g))),则下面式子的值为 ; Head(Tail(Head(Tail(Tail(A)))))
A.(g) B.(d) C.c D.d
③ 输入序列为(A,B,C,D),不可能得到的输出序列有 ;
A.(A,B,C,D) B.(D,C,B,A) C.(A,C,D,B) D.(C,A,B,D)
④ 散列函数有一个共同性质,即函数值应按 取其值域的每一个值; A.最大概率 B.最小概率 C.同等概率 D.平均概率
⑤ 直接插入排序在最好情况下的时间复杂度为 。 A. O(logn) B. O(n) C. O(n*logn) D(n2)
免费考研网www.freekaoyan.com
2 (10分) 判断下列叙述是否正确 ①(101,88,46,70,34,39,45,58,66,10)是堆; ② 将一棵树转换成二叉树后,根结点没有左子树; ③ 用树的前序遍历和中序遍历可以导出树的后序遍历; ④ 即使对不含相同元素的同一输入序列进行两组不同的、合法的入栈和出栈组合操作,所得的输出序列也一定相同; ⑤ 哈夫曼树是带权路径长度最短的树,路径上权值较大的结点离很较近。
来自免费考研网www.freekaoyan.com
3 (10分) 有一高个比他人都至少高出一头,找他的人都说“根本不用与别人比较,一眼就能找到他”,你认为此话正确吗?为什么?请简要描述两种求N个数中最大值的方法,并给出所需的最少比较次数。
来自免费考研网www.freekaoyan.com
4 (10分) 图1是用邻接表存储的图,画出此图,并写出从C点开始按深度优先遍历该图的结果。
图1 题4图
免费考研网www.freekaoyan.com
5(10分) 下面是求无向连通图的最小代价生成 树的一种算法: 将图中所有边按权重从大到小排序为(e1,e2,…,em) i:=1;
While (所剩边数≥顶点数)
Begin 从图中删去ei 若图不再连通,则恢复ei i:=i+1 End
试证明这个算法所得的图是原图的最小代价生成树。
来自免费考研网www.freekaoyan.com
6 (10分) 已知无向图G和G’互为补图(结点相同、边不重叠、两图合起来为完全图),试证明G或G’是连通的。
免费考研网www.freekaoyan.com
7 (10分) 用序列(46,88,45,39,70,58,101,10,66,34)建立一个排序二叉树,画出该树,并求在等概率情况下查找成功的平均查找长度。
来自免费考研网www.freekaoyan.com
10 (10分) 试写出以带头结点单链表为存储结构实现简单选择排序的算法。
北京邮电大学1999年考研真题-数据结构
本站小编 FreeKaoyan/2018-01-22
相关话题/北京邮电大学 考研真题 数据结构
北京邮电大学1999年考研真题-政治经济学
专业课考研经验 本站小编 FreeKaoyan 2018-01-22北京邮电大学1999年考研真题-电子电路
数字部分:(50分) 1 简答题(30分)① 写出函数F=AB+C的最大项表达式。② 已有逻辑电路如图1所示,请画出其对应的真值表。图1③ 已知四变量函数,试用卡诺图化简,求出最简与-或式。④ 有一简单时序逻辑电路如图2所示,试写出当C=1和C=0时电路的下一状态方程Qn+1,并说出各自实现的功能 ...专业课考研经验 本站小编 FreeKaoyan 2018-01-22北京邮电大学1999年考研真题-物理学
专业课考研经验 本站小编 FreeKaoyan 2018-01-22北京邮电大学1999年考研真题-邮电经济与管理
专业课考研经验 本站小编 FreeKaoyan 2018-01-22北京邮电大学1999年考研真题-理论力学
专业课考研经验 本站小编 FreeKaoyan 2018-01-22北京邮电大学1999年考研真题-通信原理
专业课考研经验 本站小编 FreeKaoyan 2018-01-22北京邮电大学1999年考研真题-微机原理
专业课考研经验 本站小编 FreeKaoyan 2018-01-22北京邮电大学1999年考研真题-机械原理
专业课考研经验 本站小编 FreeKaoyan 2018-01-22北京邮电大学1999年考研真题-控制工程基础
专业课考研经验 本站小编 FreeKaoyan 2018-01-22北京邮电大学1999年考研真题-工程数学
专业课考研经验 本站小编 FreeKaoyan 2018-01-22北京邮电大学1999年考研真题-工业企业管理
工业企业管理一、简答题 (每题6分,共36分) l、什么是产品多样化发展战略?选择此战略有何优点、难点? 选择时应注意哪些要点? 2、影响消费资料购买力的几个因素,它们的具体内容是什么? 3、说出进行市场潜力分析的步骤。 (包括步骤中的公式) 4、在开发计算机管理信息系统的过程中,为什么要进行代码 ...专业课考研经验 本站小编 FreeKaoyan 2018-01-22北京邮电大学1999年考研真题-概率论
专业课考研经验 本站小编 FreeKaoyan 2018-01-22北京邮电大学1999年考研真题-高等代数
专业课考研经验 本站小编 FreeKaoyan 2018-01-22北京邮电大学1999年考研真题-电磁场理论
专业课考研经验 本站小编 FreeKaoyan 2018-01-22北京邮电大学1999年考研真题-电子技术
专业课考研经验 本站小编 FreeKaoyan 2018-01-22