全国硕士硕士入学统一考试
计算机科学专业基础综合试題
一、单项选择題：1～40小題，每題2分，共80分。在每題給出的四个选项中，請选出一项最符合題目规定的。
1．若元素a、b、c、d、e、f依次进栈，容許进栈、退栈操作交替进行。但不容許持续三次进行退栈工作，则不也許得到的出栈序列是（D）
A.dcebfa
B.cbdaef
C.bcaefd
D.afedcb
2．某队列容許在其两端进行入队操作，但仅容許在一端进行出队操作，则不也許得到的次序是（C）
A.bacde
B.dbace
C.dbcae
D.ecbad
3．下列线索二叉树中（用虚线表达线索），符合后序线索树定义的是（B）
A.B.
C.D.
4.在下列所示的平衡二叉树中插入关键字48后得到一棵新平衡二叉树，在新平衡二叉树中，关键字37所在結点的左、右子結点中保留的关键字分别是（C）
A.13，48
B.24，48
C.24，53
D.24，90
5.在一棵度為4的树T中，若有20个度為4的結点，10个度為3的結点，1个度為2的結点，10个度為1的結点，则数T的叶节点个数是（B）
A.41
B.82
C.113
D.122
6.对n（n≥2）个权值均不相似的字符构成哈夫曼树，有关该树的论述中，錯误的是（B）
A.该树一定是一颗完全二叉树
B.树中一定没有度為1的結点
C.树中两个权值最小的結点一定是兄弟結点
D.树中任一非叶結点的权值一定不不不小于下一层任一結点的权值
7.若无向图G=（V.E）中含7个顶点，则保证图G在任何状况下都是连通的，则需要的边数至少是（A）
A.6
B.15
C.16
D.21
8.对下图进行拓扑排序，可以得到不一样的拓扑序列的个数是（B）
A.4
B.3
C.2
D.1
9.已知一种長度為16的次序表L，其元素按关键字有序排列，若采用折半查找法查找一种不存在的元素，则比较次数最多的是（A）
A.4
B.5
C.6
D.7
10.采用递归方式对次序表进行迅速排序，下列有关递归次数的论述中，对的的是（D）
A.递归次数与初始数据的排列次序无关
B.每次划分后，先处理较長的分区可以减少递归次数
C.每次划分后，先处理较短的分区可以减少递归次数
D.递归次数与每次划分后得到的分区处理次序无关
11.对一组数据（2，12，16，88，5，10）进行排序，若前三趟排序成果如下：（A）
第一趟：2，12，16，5，10，88
第二趟：2，12，5，10，16，88
第三趟：2，5，10，12，16，88
则采用的排序措施也許是
A.起泡排序
B.希尔排序
C.归并排序
D.基数排序
12.下列选项中，能缩短程序执行時间的措施是（D）
Ⅰ提高CPU時钟频率，Ⅱ优化数据通过构造，Ⅲ对程序进行编译优化
A.仅Ⅰ和Ⅱ
B.仅Ⅰ和Ⅲ
C.仅Ⅱ和Ⅲ
D.Ⅰ，Ⅱ，Ⅲ
13.假定有4个整数用8位补码分别表达r1=FEH，r2=F2H，r3=90H，r4=F8H，若将运算成果寄存在一种8位寄存器中，则下列运算会发生溢出的是（C）
A.r1×r2
B.r2×r3
C.r1×r4
D.r2×r4
14.假定变量i，f，d数据类型分别為int，float和double（int用补码表达，float和double分别用IEEE754单精度和双精度浮点数据格式表达），已知i=785，f=1.5678e3，d=1.5e100.若在32位机器中执行下列关系体現式，则成果為真是（C）
（Ⅰ）i==（int）（float）I（Ⅱ）f==（float）（int）f
（Ⅲ）f==（float）（double）f（Ⅳ）(d+f)-d==f
A.仅Ⅰ和Ⅱ
B.仅Ⅰ和Ⅲ
C.仅Ⅱ和Ⅲ
D.仅Ⅲ和Ⅳ
15.假定用若干个2k×4位芯片构成一种8k×8位存储器，则地址0B1FH所在芯片的最小地址是（D）
A.0000H
B.0600H
C.0700H
D.0800H
16.下列有关RAM和ROM的论述中，对的的是（A）
ⅠRAM是易失性存储器，ROM是非易失性存储器
ⅡRAM和ROM都采用随机存取方式进行信息访问
ⅢRAM和ROM都可用作Cache
ⅣRAM和ROM都需要进行刷新
A.仅Ⅰ和Ⅱ
B.仅Ⅱ和Ⅲ
C.仅Ⅰ，Ⅱ，Ⅲ
D.仅Ⅱ，Ⅲ，Ⅳ
17.下列命令组合状况中，一次访存过程中，不也許发生的是（D）
A.TLB未命中，Cache未命中，Page未命中
B.TLB未命中，Cache命中，Page命中
C.TLB命中，Cache未命中，Page命中
D.T