文档介绍：2012年考研计算机统考408真题
单项选择题
求整数n(n〉＝0)阶乘的算法如下,其时间复杂度是ﻩ1 。
Iｎt faｃt（inｔ　n）｛
ﻩIｆ（ｎ＜=１）ｒetｕrn 1；
Return n*faｃｔ（n—1）；
O(lｏg2n)
O（ｎ)
O(ｎlｏｇ2n)
O（n2)
已知操作符包括’+’、’—‘、’＊’、’／’、’（‘和'）’。将中缀表达式a+ｂ—a*（(ｃ＋d/ｅ—ｆ）+g转换为等价的后缀表达式ab+acd+e／f-＊-g+时，用栈来存放暂时还不能确定运算次序的操作符，若栈初始为空,则转换过程中同时保存在栈中的操作符的最大个数是 2ﻩ.
5
7
8
11
若一棵二叉树的前序遍历序列为a，e,b，d，ｃ，后序遍历序列为b，c，d,ｅ，a，则根结点的孩子结点ﻩ 3ﻩ.
只有e
有e，b
有e，c
无法确定
若平衡二叉的高度为6，且所有非叶结点的平衡因子均为1，则该平衡二叉树的结点总数为 4ﻩ。
1０
2０
3２
３3
对有n个结点、e条边且使用邻接表存储的有向图进行广度优先遍历,其算法时间复杂度是ﻩ ５ﻩ。
O(ｎ）
O(e)
O（n+e）
Ｏ（n＊ｅ）
若用邻接矩阵存储有向图，矩阵中主对角线以下的元素均为零，则关于该图拓扑序列的结论是 6 。
存在，且唯一
存在，且不唯一
存在，可能不唯一
无法确定是否存在
对如下有向图带权图,若采用迪杰斯特位（Dｉjksｔｒa）算法求从源点ａ到其他各顶点的最短路径，则得到的第一条最短路径的目标顶点是b，第二条最短路径的目标顶点是c,后续得到的其余最短路径的目标顶点依次是 7
.
ｄ,e，f
e，d，f
ｆ,ｄ，e
f，ｅ，d
下列关于最小生成树的叙述中,正确的是 8 。
Ｉ。最小生成树的代价唯一。
。
III．使用普里姆（Ｐrim)算法从不同顶点开始得到的最小生成树一定相同。
IＶ。使用普里姆算法和克鲁斯卡尔(Kruskaｌ）算法得到的最小生成树总不同。
仅I
仅IＩ
仅I、III
仅II、IV
已知一颗３阶B—树，如下图所示。删除关键字78得到一颗新B－树，其最右叶结点中的关键字是 3ﻩ。
60
６0,62
62，65
65
在内部排序过程中,,每一趟排序结束都至少能够确定一个元素最终位置的方法是 ﻩ 10ﻩ.
Ｉ。简单选择排序

IIＩ．快速排序
ＩV．堆排序

仅I、ＩII、ＩV
仅I、III、V
仅II、III、IＶ
仅IＩI、IV、V
对一待排序序列分别进行折半插入排序和直接插入排序,两者之间可能的不同之处是 11ﻩ.
排序的总趟数
元素的移动次数
使用辅助空间的数量
元素之间的比较次数
假定基准程序A在某计算机上的运行时间为1０0秒，其中90秒为CPU时间，其余为I/％,I/O速度不变，则运行基准程序A所超耗费的时间是ﻩ12 。
55秒
60秒
65秒
70秒
假定编译器规定int和shｏrt型长度分别为3２位和1６位,执行下列Ｃ语言语句:
unsiｇｎed　ｓhorｔ x=６5530；
unsiｇｎｅd int　ｙ=ｘ;
得到ｙ的机器数为ﻩ 13 .
0000 7FFＡH
０00０ FFＦAＨ
FFＦＦ 7FFAH
ＦFＦF FFＦAH
float类型（即ＩＥEE754单精度浮点数格式)能表示的最大正整数是ﻩ１４。
2126—２103
２１2７—21０4
2127－２10３
2１28—２１０４
某计算机存储器按字节编址，采用小端方式存放数据。假定编译器规定iｎt型和ｓhorｔ型长度分别为32位和１6位，:
strｕct{
ﻩ inｔａ；
ﻩ chａr ｂ；
ﻩsｈoｒt c;
}record；
record．ａ=273;
若recｏrｄ变量的首地址为0ｘC008, 15ﻩ。
0x０0、0ｘC00D
0x０0、０ｘＣ０0Ｅ
０x11、０ｘC0０D
0x11、0xC0０E
下列关于内存（flash　memoｒｙ)的叙述中，错误的是ﻩ16 .
信息可读可写,并且读、写速度一样快
存储元由MＯS管组成,是一种半导体存储器
掉电后信息不丢失,是一种易失性存储器
采用随机访问方式,可替代计算机外部存储器
假设某计算机按字编址，Cachｅ有４个行