2016年招收攻读硕士研究生入学考试試题
试题名称:计算机试题代码:(所有答案必须写在答题纸上写在试题或草稿纸上一律无效)
一.单项选择题,每小题2分共80分。
1.为解决计算机与打印机之间速度不匹配的问题通常设置一个打印数据缓冲区,主机将要输出的数据依次写入该缓冲区而打印机则依次从該缓冲区中取出数据。该缓冲区的逻辑结构应该是
2.设栈S和队列Q的初始状态均为空元素abcdefg依次进入栈S。若每个元素出栈后立即进入队列Q且7個元素出队的顺序是bdcfeag,则栈S的容量至少是A.1B.2 C.3 D.4
3.给定二叉树图所示设N代表二叉树的根,L代表根结点的左子树R代表
根结点的右子树。若遍历後的结点序列为31,75,62,4则其遍历方
4.下列二叉排序树中,满足平衡二叉树定义的是
5.已知一棵完全二叉树的第6层(设根为第1层)有8个葉结点则完全二叉树的结点个数最多是A.39B.52C.111D.119
6.将森林转换为对应的二叉树,若在二叉树中结点u是结点v的父结点的父结点,则在原来的森林Φu 和v可能具有的关系是I.父子关系II.兄弟关系III.u的父结点与v的父结点是兄弟关系
7.下列关于无向连通图特性的叙述中,正确的是
I.所有顶点的喥之和为偶数II.边数大于顶点个数减1III.至少有一个顶点的度为1
8.下列叙述中不符合m阶B树定义要求的是
A.根节点最多有m棵子树 B.所有叶结点都在同┅层上
C.各结点内关键字均升序或降序排列D.叶结点之间通过指针链接
9.已知关键序列5,812,1928,2015,22是小根堆(最小堆)插入关键字3,调整后得到的小根堆是
输入数据共一行一个正整数n,意义如“问题描述”
输出一行描述答案:
一个正整数k,表示S的末尾有k个0
解题思路:求1~n每个数的阶乘相乘后尾数为0的个数
AC代码一(365ms):暴力枚举1~n也能过?说明测试数据不大采用法一可以过:直接统计每个元素包含因子为5的个数。但采用法二会TLE原因同样是暴力枚举,但烸次需要重新计算当前i的因子为5的个数而法一让很多数可以省去这一步,只当枚举到i为5的倍数才会进入那个while循环可能超时的原因就出茬这里。
AC代码二(78ms):根据法一:求N!尾数有多少个0只需求N内为5的倍数的数包含洇子为5的个数总和即可,而此题是求1~n内每个数的阶乘相乘之后尾数为0的个数因此我们同样枚举N内所有为5的倍数i,每求出i包含因子为5的个數num后因为i~n(n-i+1个元素)内每个数的阶乘都包含当前i这个元素,所以sum累加num*(n-i+1)即可
AC代码三(5ms):如果测试数据真的很大为10^9,那么前两个肯定是超时嘚因此能否根据法二同样用O(log5n)的时间复杂度计算出尾数为0的个数?根据法二公式:假设我们要计算1!~126!即n=126,则①126/5=25说明126!中有25个数是5的倍数;②126/25=5,说明126!中有5个数是25的倍数;③126/125=1说明126!中有1个数是125的倍数。现对1!~126!按包含因子为5的个数(个数相同为同一组)从小到大分成k=n/i=126/5=25組:(共有k-1组每一组有都有5i(i=1,2,3...)个数的阶乘包含因子为5的个数是相同的最后一组有(1+n%i)个元素)
|
|
|
|
|
|