北航2011年硕士研究生入学考试数据结构与C语言试题与答案

4星(超过85%的资源)
所需积分/C币:15 2013-01-02 21:42:47 132KB PDF
6
收藏 收藏
举报

2011 年硕士研究生入学考试 “数据结构与C语言程序设计”(科目代码:991)试题与答案 一、单项选择题(本题共20分,每小题各2分) 1.下列关于线性表的存储结构的叙述中,错误的是。 A.线性表的顺序存储结构中隐式地存储了数据元素之间的逻辑关系 B.线性表的顺序存储结构一定需要占用一片地址连续的存储空间 C.线性表的链式存储结构通过指针来反映数据元素之间的逻辑关系 D.线性表的链式存储结构占用的存储空间一定不连续 2.若front 和rear 分别表示链接队列的队头指针与队尾指针,则向队列中插入一个由p 指的新元素的过程是依次执行。 A.rear=p; front=p; B.front=p; rear=p; C.rear->link=p; rear=p; D.front->link=p; rear=p;
请分别写岀对数据元素序列 按从小到大进行谢尔)排 序时每一趟的结果。设排序的间隔数也称为增量依次为 四、算法设计题本题分 凵知某哈夫曼树采用二叉链表存储,结点构造为 其中,叶 结点的域中已经存放了该叶结点对应的权值。请写一非递归算法,该算法的功能是计算 根结点指针为的哈夫曼树的带权峰径长度 要求 用文字简要给出算法的基本思想;(分) 根据算法的基本思想写出相应算法。(分) 五、程序阅读题本题共分,每小题各分 下列程序的输出结果是。 下列程序段的输出结果是。 下列程序的输出结果是 下列程序的输出结果是 卜列程序的输出结果是 .下列程序的输出结果是 下列程序的输出结果是 卜列程序的输出结果是 下列程序的输出结果是。 执行下列程序后,文件 中的内容是 六、填空题本题共分,每小题各分 对」下列程序,为了使输出结果为,输入量和应该满足的条件是」 若己有下列定义,则表达式 的值是①,表达式 的值是 ②,表达式 的值是③。 下列程序段的功能是计算!的末尾含有多少个零。请在程序段的空白处填上必 要的内容,使程序段完整。(提示:只要计算出!中含有因数的个数即可) 卜列程序的功能是通过指针操作,找岀并输岀三个整数中的最小者。请在程序的空白 处填上必要的内容,使程序完整。 下列程序的功能是先由用户通过键盘输入一个文件名,然后向此文件输入一串字符 假设输入以字符“”结束,最后再将当前日期写到文件的尾部。请在程序的空白处填上 必要的内容,使程序完整。 七程序设计题本题分 请编写一语言程序,该程序的功能是先通过键盘输入一个整数,然后调用一个递归 函数 计算 ,最后输出计算结果 八、程序设计题本题分 请设计一语言函数注:只须写出函数,不必写出完整稈序,该函数的功能是用尽可 能高的时间效率与空间效率将·个类型的数组 的所有元素依次循环右移个位 例如,对于某数组,当时即把数组所有元素循环右移个位置,是将 转换为 参考答案 单项选择题 、简答题 答:在等概率情况下,在长度为的顺序表中插入一个数据元素需要平均移动 个元索,删除一个数据元素需要平均移动 个元素。具体移动的元素个数主要取决」 表的长度以及插入或删除的位置,位置越接近,做需要移动的元素就越少。 答:只设置一个队尾指针更合适。因为对于采用循环单链表作为存储结构的队列而 言,可以通过队尾指针在的时间内找到队头指针,而只设置队头指针要在的时间 内才能找到队尾指针。因此,只设萓队尾指针,进队和出队操作的时间复杂度均为 而只设置队头指针,出队操作的时间复杂度为,但进队操作的时间复杂度为。 答:一般情况下,采用邻接矩阵存储图需要一个一维数组存储顶点的数据信息和 个二维数组称之为邻接矩阵存储边或弧的信息,因此,空间复杂度为,与图中边或弧 的数量无关,可见邻接矩阵适合存储稠密图;而采用邻接表需要分别将以某顶点为出发点的 所有边对应的边结点链接为一个线性链表,同时用一个一维数组存储图中顶点的数据信以及 指向以该顶点为出发点的第·条边对应的边结点的指针,因此,空间复杂度为,可见 佟中边或弧数越少需要的存储空间就越少,因此,邻接表适合存储稀疏图。 答:如果借助二叉树来描述,小顶堆积是一棵完仝二叉树,二叉树中任意分支结点 的值均小于或等于其左孩子和右孩子若右孩子存在的值。堆积中值最大的元素对应的结点 定是叶结点,否则,该结点必定有大于它的孩子结点,这与小顶堆积的定义相矛盾;凼此, 值最人的元素对应的结点只能作为叶结点出现在二叉树的最下面两层中的一层中。 、综合题 趟序间隔数 各趟排序结果 初始 第趟 第趟 四、算法设计题 ()算法的基本思想: 本题宜采用二叉树的后序遍历的非递归算法完成。在遍历过程中,访问一个叶结点时, 将该叶结点的数据域值该叶结点的权值与该叶结点的路径长度即当前栈顶指针值加相 乘,并进行值的累加。遍历结束时便求的该哈夫曼树的 ()算 定义二叉树中结点最人数目 为二叉树根结点所在链结点的地址 当前指结点的地址进栈 标志进栈 将移到其左孩子结点 退栈 当前指结点的地址再次进栈 标志进栈 将移到其右孩子结点 指结点为叶结点 五、程序阅读题 六、填空题 七、程序设计题 八、程序设计题 ()算法的基本思想 根据值将数组 分成前后两个部分,其中,前一部分为数组的前个元素 后一部分为数组的后个元素;然后先将后一部分中的个元素进行逆置即前后对应位置的 元素依次颠倒位置,接着将前一部分中的个元素进行逆置,最后将整个数组的所有元素 再进行一次逆置,即得到所需要的结果。 ()程序 逆置数组的后个元素 逆置数组的前个元素 逆置数组的所有元素 逆置下标为到之间的所有元素 交换元素 的位置 效率分析:第次调用 函数的时间复杂度为,第次调用 函数 的时间复杂度为,第次调用 函数的时间复杂度为,因此,整个程序的 时间复杂度为。只用了个数组元素的辅助空间 建议选用年月 第次印刷的书 指定参考书: 《数据结构教程第二版》唐发根编著北京航空航天大学出版社 《程序设计第三版》谭浩强编著清华大学出版社

...展开详情
试读 9P 北航2011年硕士研究生入学考试数据结构与C语言试题与答案
立即下载 低至0.43元/次 身份认证VIP会员低至7折
一个资源只可评论一次,评论内容不能少于5个字
Darren_chen 北航考研真题,没问题
2014-01-15
回复
您会向同学/朋友/同事推荐我们的CSDN下载吗?
谢谢参与!您的真实评价是我们改进的动力~
  • 领英

  • GitHub

  • 脉脉勋章

  • 签到王者

  • 技术圈认证(专家版)

关注 私信
上传资源赚钱or赚积分
最新推荐
北航2011年硕士研究生入学考试数据结构与C语言试题与答案 15积分/C币 立即下载
1/9
北航2011年硕士研究生入学考试数据结构与C语言试题与答案第1页
北航2011年硕士研究生入学考试数据结构与C语言试题与答案第2页

试读结束, 可继续读1页

15积分/C币 立即下载