2017 年考研计算机统考 一、 单项选择题
408 真题
1. 以下函数的时间复杂度是 1 。
int func(int n)
{ int i = 0; sum = 0;
while( sum < n) sum += ++i;
return i;
}
A. O(logn)
B. O(n1/2)
C. O(n)
D. O(nlogn)
2. 以下对于栈的表达中，错误的选项是 2
。
I.采纳非递归方式重写递归途序时一定使用栈
II.函数调用时，系统要用栈保留必需的信息
III.只需确立了入栈的序次，即可确立出栈序次
IV.栈是一种受限的线性表，同意在其两头进行操作
A. 仅 I
B. 仅 I、 II、III
C. 仅 I、 III、IV
D. 仅 II、 III、 IV
3. 合用于压缩储存稀少矩阵的两种储存构造是 3 。
A. 三元组表和十字链表
B. 三元组表和毗邻矩阵 C. 十字链表和二叉链表
D. 毗邻矩阵和十字链表
4. 要使一棵非空二叉树的先序序列与中序序列同样， 其全部非叶结点须知足的条件是
4 。
A. 只有左子树
B. 只有右子树 C. 结点的度均为 1
D. 结点的度均为 2
5. 已知一棵二叉树的树形以以下图所示，后来序序列为
的结点是 5 。
e,a,c,b,d,g,f，树中与结点
a 同层
A. c B. d 优选文库
C. f D. g
6. 已 知 字 符 集 {a,b,c,d,e,f,g,h} ， 若 各 字 符 的 哈 夫 曼 编 码 依 次 是
0100,10,0000,0101,001,011,11,0001 ，则编码序列的译码结果是6。 A. a c g a b f h B. a d b a g b b C. a f b e a g d D. a f e e f g d
20131~402801.mnm+n
A.()OnB.()OmnC.(min(,))OmnD.(max(,))Omn2.1,2,3,,n123,,,,npppp23p3p
A.3nB.2nC.1nD.3.1234567TT0
A.0B.1C.2D.34.T6234567T
A.27B.46C.54D.56
5.XXYX
A.XB.Y
C.XYD.Y6.T1vT2vT2T3T1T3I.vT1T1T3II.vT1T1T3III.vT1T1T3IV.vT1T1T3A.IIIIB.IIVC.IIIIID.IIIV7.A0101
0011
0100
1000A
A.1212B.2211C.3423D.44228.
A.hcabdegfB.eafgbhcd
C.dbcahefgD.abcdhefg9.AOE8A.ceB.deC.fdD.fh10.25B
A.5B.7C.8D.1411.1101190079111141201222
A.007110119114911120122B.007110119114911122120
C.007110911114119120122D.11012091112211400711912.1.2 GHz4CPICPI
A50%2
B20%3
C10%4D20%5
MIPS
A.100B.200C.400D.600
13.IEEE 754
C640 0000H2 4 c=9
2 4 2 4 g=6a=3
d=4e=6
b=8h=9
f=10a
b
c d e
f g
h A.-1.5213B.-1.5212C.-0.5x213D.-0.521214.8xy[x]=1 1110100[y]=10110000z=2*x+y/2z
A.11000000B.0 0100100C.1 0101010D.15.8/
A.2B.3C.4D.516.256 MB4 GB
4 KBTLB4
0FF180H0002H
13FFF1H0035H
002FF3H0351H
2019考研北大软微867专业课大题简要回忆
数据结构4个题
1. 给了一个二叉树的图，具体记不清了，中序反正是ABCDEFGHIJ ，要求写出前序，中序，后续遍历序列。10分
2. 要求根据查找频率设计排列顺序，并且计算查找长度。（这个题在王道真题分析上面的原题）。这个题我从真题分析上抄下来给大家看看，是2013年408统考真题第42题。原题如下：
设计包含4个元素的集合S={“do” ”for” ”repeat” “while”}各元素的查找概率为p1=0.35p2=0.15 p3=0.15 p4=0.35 将S保存在一个长度为4的顺序表中，采用折半查找算法，查找成功时的平均查找长度为2.2，请回答：
（1）若采用顺序存储结构保存S，且要求平均查找长度更短，则元素应该如何排列？应使用何种查找方法？查找成功时的平均查找长度是多少？
（2）若采用链式存储结构保存S，切要求平均查找长度更短，则元素应该如何排列？应使用何种查找方法？查找成功时的平均查找长度是多少？
3. 给了ABCDEFGH 8个字母，并且给了使用频率，0.020.03 0.06，... ，0.32 要求对其进行哈夫曼编码。
4. 给出了一个有向图，要求使用Dijstra最短路径算法求出V0到V1，V2，V3，V4的距离和路径，要求写出过程。
操作系统3个题
1. （1）请求分页的知识考察以及逻辑地址到物理地址的变换
（2）画出内存地址变换的机构【我有话要说: 这个图，平时看了N遍，但是让你考试的时候手画出来还真不好画，我花了很多时间雕琢这幅画....】
（3）根据LRU和FIFO置换算法，分别列出一个内存访问序列的缺页次数。【15分】
2. 给出了3个进程，P0P1P2三类资源X0X1X2，给出了最大需求矩阵和已分配资源矩阵，即Max矩阵，Allocation矩阵，问能不能给 P1分配其请求的（021）资源请求？【10分】
3. （1）文件目录和目录文件的区别是什么？【4分】
2016靠全国顶士研究生招生考试
计篝机件学与技术学科嵌萃，
计.q障科专业基碰悻台试E
一、总顶逸~.'I-H小题!每小姐2分，其创分下列每犀输出的四个选项中只有一
个造项符合试姐要求1 已知衰头元素为<~，鼻随褒在内存中的存储状态!11ft'"褒所示.
地址元素链簇地蛙
>OOOH
'OO
l008H
I町
IOHlH
1014日2 b
C
d , 10]OH
1配H
1阳
NULL
1剧H
二现将f在2负于\1)14日处并插入到尊慢褒咿若，a逻绳上i盒子a和e之间则a.e. m~键簇地
址切依次是
A. 10]四1014H.lOO4H B. 1010H. 100m. 1014日巳10]4H.HlIO日1∞4HD. 1014日1ω4H.Hl1ωf 2 已知个倍有袤头结点的双向循环键褒L结点结构为压~I <1:11" I nexl I
Jt.和prev相皿划分别是指向其重援前雹和直拨后
罐铺票是的捕tt…观事例除..，叶p所捕的编蔚蓝躏俐通甸序列是
A.p->nut->伊"V-P--~;P-冲rev->缸Xf-]>->p=<;fr，键时
B. p->lleXt->p .. "，恒p->mXI;p->伊"主'""xr叮》岱e:
C. p->nut->pRv-p-->缸XI;p->伊~->oex同日pfev;fr使(P);D. p-> "":<1-> p"'y于?扮'句，p->伊=~~眩目'-'>'世xt:fr使ω)
3 设有如下因所示的火李车缸入口到出口之闭有.~轨道列享的仔边方向均为从左至
右到'"可侵入任意一条轨道.现自偏号为>-0的，列列革破入的次序依次是8.4.2.5.3
9.1.6.1.着期组'自出的次序依次为]-9....凰至少是
'现.
A.2 D.J C嗡D.,
4有个1∞阶的三对角~阵M其元素m;J1~1∞1型1∞)孩仔优先次序压缩存入「恃
从0开始的一维敏组W略1元贫困强却在N的下标是
A. 86 B. 87 C. 88 D. 89
