文档内容
2015 年计算机学科专业基础综合试题参考答案
一、单项选择题
BCDBAD ACABD ABABD BBBAC DDCCA CBCAC BCCC
1. A 2. 3. 4. 5. 6. 7. 8.
9. C 10. 11. 12. 13. 14. 15. 16.
17. B 18. 19. 20. 21. 22. 23. 24.
25. D 26. 27. 28. 29. 30. 31. 32.
33. D 34. 35. 36. 37. 38. 39. 40.
1. 解析：
递归调用函数时，在系统栈里保存的函数信息需满足先进后出的特点，依次调用了 main(),
S(l), S(O), 故栈底到栈顶的信息依次是 main(), S(1), S(O)。
2. 解析：
根据二叉树前序遍历和中序遍历的递归算法中递归工作栈的状态变化得出：前序序列和中
序序列的关系相当于以前序序列为入栈次序，以中序序列为出栈次序。因为前序序列和中序序
列可以唯一地确定一棵二叉树，所以题意相当千“以序列 a, b, c, d 为入栈次序，则出栈序列的
个数为多少“，对于 n 个不同元素进栈，出栈序列的个数为—-c;n= 14。
n+l
3. 解析：
在哈夫曼树中，左右孩子权值之和为父结点权值。仅以分析选项 A 为例：若两个 10 分别
属千两棵不同的子树，根的权值不等于其孩子的权值和，不符；若两个 10 属于同棵子树，其权
值不等千其两个孩子（叶结点）的权值和，不符。 B、 C 选项的排除方法一样。
4. 解析：
只有两个结点的平衡二叉树的根结点的度为 1, A 错误。中序遍历后可以得到一个降序序
列，树中最大元素一定无左子树（可能有右子树），因此不一定是叶结点， B 错误。最后插入的
结点可能会导致平衡调整，而不一定是叶结点， C 错误。
5. 解析：
画出该有向图图形如下。
采用图的深度优先遍历，共 5 种可能： , , , , , 选 D。
6. 解析：
从 V4 开始， Kruskal 算法选中的第一条边一定是权值最小的(V1,V4), B 错误。由于 V1 和V 4 已经可达，第二条边含有V和 1 V 4 的权值为8 的一定符合Prim算法，排除
A、D。
7. 解析：
画出查找路径图，因为折半查找的判定树是一棵二叉排序树，看其是否满足二叉排序树的
要求。 ＾
500
450
180 450
显然，选项A的查找路径不满足。
8. 解析：
由题中 “失配s[]i :/; 玵］时，i=j=S", 可知题中的主串和模式串 的位序都是从0开始的（要
注意灵活应变）。按照next数组生成算法，对于t有
编号 。 1 2 3 4 5
-
b
t a b a a c
一
next 一1
-
o 0
-
1 2
-
依据KMP算法 ”当失配时，不i 变，j回退到next[j]的位置并重新比较”，当失配si[]f; t[j]
时，=i j =5, 由上表不难得出next[j]=n ext5[ ]= 2 (位序从0开始）。从而最后结果应为i= 5 (i
保持不变），j=2。
9. 解析：
基数排序的元素移动次数与关键字的初始排列次序无关，而其他三种排序都是与关键字的
初始排列明显相关的。
10. 解析：
删除8后，将12 移动到堆顶，第一次是15和10比较，第二次是10和12比较并交换，
第三次还需比较12和16, 故比较次数为3次。
--、
，矗 全、
I
,/
\
\
/
�
\
;! -
1
- - -
5
、 \
)
／ (、 1 � 2 . � J , .1
(1
- - -
0
- ·
£(1
夕 －
5 -
／
\ )
( 气 1 、一 0 -- ) �
.--< i'1
-
2
- -
， .
j�; i� 气 芒＼、巴 ( ＼ 21) , ( 、 3 、j 4) ( , 1 _6 _)令 (v21 ,- ' , 3 _ _j 4 i : \ 1 � 6) i
11. 解析：
希尔排序的思想是： 先将待排元素序列分割成若干子序列（由相隔某个 “增量 ” 的元素组
成），分别进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序（增
量足够小）时，再对全体元素进行一次直接插入排序。
12. 解析：
硬件能直接执行的只能是机器语言（二进制编码），汇编语言是为了增强机器语言的可诙
性和记忆性的语言，经过汇编后才能被执行。
13. 解析：
补码整数表示时，负数的符号位为I, 数值位按位取反，末位加I, 因此剩下的2个"I "在最低位时，表示的是最小整数，为10000011, 转换成真值为-125。
14. 解析：
对阶是较小的阶码对齐至较 大的阶码，I正确。右规和尾数舍入过程，阶码加1而可能上
溢，II正确，同理III也正确。尾数溢出时可能仅产生误差，结果不一定溢出，IV正确。
15 .. 解析：
直接映射的 地址结构如下：
I
I 1
主存字块标记 Cache字块标记 字块内地址
按字节编址，块大小为4x32bit=1 6B= 2 4B, 则 “字块内 地址” 占4位；“能存放4K字数
据的Cache"即Cache的存储容量为4K字（注意单位），则Cache共有IK= 210 个Cache行，
Cache字块标记占10位；主存字块标记占32-10-4=1 8位。
Cache的总容量包括：存储容量和标记阵列容量（有效位、 标记位、 一致性维护位和替换
算法 控制位）。标记阵列中的有效位和标记位是一定有的，而一致性维护位（脏位） 和替换算法
控制位的 取舍 标准是看题眼，题目中，明确说明了采用写回法，因此一定包含一致性维护位，
而关于替换算法的词眼题目中未提及，所以不予考虑。
从而每个Cache行 标记项包含18+ 1 + 1= 2 0位， 标记阵列容量为： 210x20位=20K位，
存储容量为： 4Kx32位=128K位，则总容量为128K+ 20K= 1 48K位。
16. 解析：
上述指令的执行过程可划分为取数、 运算和写回过程， 取数时读取xaddr可能不需要访问
主存而直接访问Cache, 而 写直通方式需要把数据 同时 写入Cache和主存，因此至少访问 1次。
17. 解析：
DRAM使用电容存储，所以必须隔一段时间刷新一次，如果存储单元没有被刷新，存储的
信息就会丢失。SDRAM表示同步动态随机存储器。
18. 解析：
每个访存地址对应的存储模块序号(0,I, 2, 3)如下所示。
访存地址 I 8005 I 8006 I 8007 l 8008 I 8001 I 8002 I 8003 I 8004 I 8000
模块序号 2 3 。 2 3 。 。
其中，模块序号＝访存地址％存储器交叉模块数。
判断可能发生访存冲突的规则是：给定的访存地址在相邻的四次访问中出现在同 一个存储
o,
模块内。据此，根据上表可知8004和8000对应的模块号都为 即表明这两次的访问出现在
同一模块内且在相邻的访问请求中，满足发生冲突的条件。
19. 解析：
在同步通信方式中，系统采用一个统一的时钟信号，而不是由各设备提供，否则没法实现
统一的时钟。
20. 解析：
存取时间＝寻道时间＋延迟时间＋传输时间。存取一个扇区的平均延迟时间为旋转半
周的时间，即为(60/7200)/2=4 . l 7ms, 传输时间为(60/7200)/1000=O .Olms, 因此访问一个扇区
的平均存取时间为4.17+ O.Ql + 8= 1 2.18ms, 保留一位小数则为12.2ms。
21. 解析：
在程序中断I/0方式中，CPU和打印机直接交换，打印字符直接传输到打印机的 I/0端口，
不会涉及主存地址，而 CPU和打印机通过I/0端口中状态口和控制口来实现交互。22. 解析：
内中断是指来自CUP 和内存内部产生的中断，包括程序运算引起的各种错误，如地址非法、
校验错、页面失效、非法指令、用户程序执行特权指令自行中断(INT)和除数为零等，以上
中断都在指令的执行过程中产生的，故A正确。这种检测 异常的工作肯定是由CUP (包括控制
器和运算器）实现的，故B正确。内中断不能被屏蔽，一旦出现应立即处理，C正确。对于D,
考虑到特殊情况， 如除数为零和自行中断(INT) 都会自动跳过中断指令， 所以不会返回到发
生异常的指令继续执行，故错误。
23. 解析：
外部中断处理过程，PC值由中断隐指令自动保存，而通用寄存器 内容由操作系统保存。
24. 解析：
考虑到部分指令可能出现异常（导致中断），从而转到核心态。指令A有除零异常的可能，
指令B为中断指令，指令D有缺页异常的可能，指令C不会发生异常。
25. 解析：
(P wait)操作表示进程请求某一资源，A、B和C都 因为请求某一资源会进入阻塞态，而D
只是被剥夺了处理机资源，进入就绪态，一旦得到处理机即可运行。
26. 解析：
死锁的处理采用三种策略：死锁预防、死锁避免、死锁检测和解除。
死锁预防，采用破坏产生死锁的四个必要条件中的一个或几个，以防止发生死锁。其中之
一的 “ 破坏循环等待条件 ” ，一般采用顺序资源分配法，首先给系统的资源编号，规定每个进程
必须按编号递增的顺序请求资源，也就是限制了用户申请资源的顺序，故I的前半句属于死锁
预防的范畴。
银行家算法是最著名的死锁避免算法，其中的最大需求矩阵M心”迁义了每 一个进程对m
类资源的最大需求量，系统在执行安全性算法中都会检查此次资源试分配后，系统是否处于安
全状态，若不安全则将本次的试探分配作废。
在死锁的检测和解除中，在系统为进程分配资源时不采取任何措施，但提供死锁的检测和
解除的手段。故II、III正确。
27. 解析：
可以采用书中常规的解法思路，也可以采用便捷法。对页号序列从后往前计数，直到数到
4 (页框数）个不同的数字为止，这个停止的数字就是要淘汰的页号（最近最久未使用的页），
题中为页号2。
28. 解析：
磁盘和内存的速度差异，决定了可以将内存经常访问的文件调入磁盘缓冲区，从高速缓存
中复制的访问比磁盘I/0的机械操作要快很多。
29. 解析：
10个直接索引指针指向的数据块大小为lOxlK.B= 10KB。
每个索引指针占4B, 则每个磁盘块可存放1KB/4B = 256个索引指针，一级索引指针指向
的数据块大小为256x1KB= 256KB, 二级索引指针指向的数据块大小为256x256x1K.B= i6K.B =
64MB。
按字节编址，偏移量为1234 时，因1234B< 10KB, 则由直接索引指针可得到其所在的磁
盘块地址。文件的索引结点已在内存中，则地址可直接得到，故仅需l次访盘即可。
偏移量为307400时，因10KB+ 256KB < 307400B < 64MB_, 可知该偏移量的内容在二级索引指针所指向 的某个磁盘块中，索引结点已在内存中， 故先访盘2次得到文件所在的磁盘块地
址，再访盘 1次即可读出内容，故共需3次访盘。
30. 解析：
对各进程进行固定分配时页面数不变，不可能出现全局置换。而A、B、D是现代操作系
统中常见的3种策略。
31. 解析：
盘块号＝起始块号+L盘块号/(1024x8)」=32 +L 4o96121(1024x8)」=·32+ 50 = 82, 这里问的
是块内字节号而不是位号， 因此还需要除以8(1字节=8位）， 块内字节号=L(盘块号％
(1024x8))/8」=1。
32. 解析：
SCAN算法就是电梯调度算法。顾名思义，如果开始时磁头向外移动就一直要到最外侧，
然后再返回向内侧移动，就像电梯若往下则一直要下到最底层需求才会再上升一样。当期磁头
位于58号并从外侧向内侧移动，先依次访问130和199, 然后再返回向外侧移动，依次访问42
和15, 故磁头移过的磁道数是：(199-58)+ (199-15)= 325。
33. 解析：
POP3建立在TCP连接上，使用的是有连接可靠的数据传输服务。
34. 解析：
NRZ是最简单的串行编码技术，用两个电压来代表两个二进制数，如高电平表示1, 低电
平表示 o, 题中编码1符合。NRZI则是用电平的一次翻转来表示1, 与前一个NRZI 电平相同
的电平表示0。曼彻斯特编码将一个码元分成两个相等的间隔，前一个间隔为低电平后一个间
隔为高电平表示l; 0的表示正好相反，题中编码2符合。
35. 解析：
不考虑确认帧的开销，一个帧发送完后经过一个单程传播时延到达接收方， 再经过一个单
程传播时延发送方收到应答，从而继续发送。要使得传输效率最大化，就是不用等确认也可以
连续发送多个帧。设连续发送n个帧，一个帧的发送时 延为1000B/128kbps= 62.5ms。对于采用
滑动窗口协议的流水线机制，我们有如下公式：链路利用率=(nx发送时延）/(RTT +发送时延）。
依题意，有(nx62.5ms)/(62.5ms+ 250msx2)�80%, 得n�7.2, 帧序号的比特数K需要满足
2k�n+ 1。从而，帧序号的比特数至少为4。
36. 解析：
CSM幻CD适用于有线网络， 而CSMA/CA则广泛应用于无线局域网。其他选项关于
CSMA/CD的描述都是正确的。
37. 解析：
从本质上说，交换机就是一个多端口的网桥CA正确），工作在数据链路层（因此不能实现
不同网络层协议的网络互联，D错误），交换机能经济地将网络分成小的冲突域CB错误）。广
播域属千网络层概念，只有网络层设备（如路由器）才能分割广播域CC错误）。
38. 解析：
根据“最长前缀匹配原则" 169.96.40.5与169.96.40.0前27位匹配最长 ，故选C。选项D
为默认路由，只有当前面的所有目的网络都不能和分组的目的IP地址匹配时才使用。
39. 解析：
发送窗口的上限值=min[接收窗口，拥塞窗口］。4个RTT后，乙收到的数据全部存入缓存，
不被取走，接收窗口只剩下1KB (16-1-2-4-8= 1)缓存，使得甲的发送窗口为1KB。40. 解析：
Connection: 连接方式， Close表明为非持续连接方式， keep-alive表示持续连接方式。 Cookie
值是由服务器产生的，HTTP请求报文中有Cookie报头表示曾经访问过www.test.edu.cn服务器。
二、 综合应用题
41. 解答：
1)算法的基本设计思想
算法的核心思想是用空间换时间。 使用辅助数组记录链表中已出现的数值， 从而只需对链
表进行一趟扫描。
因为ldatal�n, 故辅助数组q的大小为n + 1, 各元素的初值均为0。依次扫描链表中的各
o,
结点， 同时检查 q[ldatal]的值， 如果为 则保留该结点， 并令 q[jdatal] = 1; 否则，将该结点从
链表中删除。
2) 使用C语言描述的单链表结点的数据类型定义
typedef struct node {
1.nt data;
struct node *link;
}NODE;
Typedef NODE *PNODE;
3)算法实现
void func (PNODE h,int n)
PNODE p=h,r;
int *q,m;
q=(int *)malloc(sizeof(int)*(n+l)); //申请n+l 个位置的辅助空间
for(int i=O;ilink!=NULL)
｛
m=p->link->data>O? p->link->data:-p->link->data;
if(*(q+m)==O) II判断该结点的data是否已出现过
｛
*(q+m)=l; II首次出现
p=p->link; ／／保留
else ／／重复出现
r=p->link; ／／删除
p->link=r->link
free (r);
fre.e (q);
【评分说明】若考生设计的算法满足题目的功能要求且正确， 则酌情给分。
4)参考答案所给算法的时间复杂度为O(m), 空间复杂度为 O(n)。
【评分说明】若考生所估计的时间复杂度和空间复杂度与考生实现的算法一致， 可给分。
42. 解答：
1)图 G的邻接矩阵A 如下：O l O l
l O 0 l l
A ＝l O 0 l O
．
O l 1 O l
l l 0 l O
2)A 2如下：
3 l 0 3 l
1 3 2 1 2
A2
＝0 2 2 0 2
3 1 0 3 1
l 2 2 1 3
0行
3
列的元素值
3
表示从顶点 0到顶点
3
之间长度为
2
的路径共有
3
条。
3)B m (2:::;m::;,;n)中位于i行j列 co 雨 ，j::;; n- 1)的非零元素的含义是： 图中从顶点i到
顶点j长度为m的路径条数。
43.
解答：
1)程序员可见寄存器为通用寄存器 和PC。 因为采用了单总线结构，因此，若
(RO-R3)
无暂存器 则 的 、 端口会同时获得两个相同的数据， 使数据通路不能正常工作。
T, ALU A B
【评分说明】回答通用寄存器 给分；回答PC, 给分；部分正确，酌情给分。
CRO-R3),
设置暂存器T的原因若回答用千暂时存放端口A的数据， 则给分；其他答案，酌情给分。
2)ALU 共有7种操作，故其操作控制信号 ALUop 至少需要 3 位；移位寄存器有 3 种操作，
其操作控制信号 SRop 至少需要 2 位。
3)
信号
SRout
所控制的部件是一个三态门， 用于控制移位器与总线之间数据通路的连接
与断开。
【评分说明】只要回答出三态门或者控制连接I断开， 即给分。
4)端口＠、＠、 ＠、 ＠、＠须连接到控制部件输出端。
【评分说明】答案包含＠、＠、 ©、 ＠中任意一个， 不给分；答案不全酌情给分。
5)
连线
1, ®-®;
连线
2,
(J)-@。
【评分说明】回答除上述连线以外的其他连线，酌情给分。
因为每条指令的长度为 位， 按字节编址， 所以每条指令占用 个内存单元， 顺序执
6) 16 2
行时，下条指令地址为 。 的一个输入端为 可便千执行 操作。
(PC)+2 MUX 2, (PC)+2
44. 解答：
1)指令操作码有7位， 因此最多可定义 2 7= 128 条指令。
2)各条指令的机器代码分别如下：
CD "incR l" 的机器码为 00000010 01 0 00 0 00, 即 0240H。
@ "shl R2, Rl" 的机器码为 00000100 10 0 01000, 即 0488H。
@ "sub R3, (Rl), R2" 的机器码为 00000110 11 1 01 0 10, 即 06EAH。
3)各标号处的控制信号或控制信号取值如下：
CD 0; ®mov; @ mova; ©left; @ read; ®sub; CT) mov; ®Srout
【评分说明】答对两个给分。
4) 指令 "subRl, R3, (R2)" 的执行阶段至少包含 4个时钟周期；指令 "incRl" 的执行阶
段至少包含2个时钟周期。
45.
解答：
semaphore Full_A = x; //Full_A 表示 A 的信箱中的邮件数量semaphore Empty_A = M-x; //Empty_A表示A的信箱中还可存放的邮件数量
semaphore Full_B = y; //Full_B表示B的信箱中的邮件数量
semaphore Emp七y_B = N-y; //Empty_B表示B的信箱中还可存放的邮件数量
semaphore mutex_A = l; //mutex_A用于A的信箱互斥
semaphore mu七ex_B = l; //mutex_B用千B的信箱互斥
Cobegin
A( B{
while (TRUE) ( while (TRUE) {
P (Full_A); P (Full_B);
P(mutex_A); P (mutex_B);
从A的信箱中取出一个邮件； 从B的信箱中取出一个邮件；
V(mutex_A); V(mutex_B);
V(Empty_A); V(Empty_B);
回答问题并提出一个新问题； 回答问题并提出一个新问题；
P(Empty_B); P (Empty_A);
P (mutex_B); P (mutex_A);
将新邮件放入B的信箱； 将新邮件放入A的信箱；
V(mutex_B); V(mu七ex_A);
V( Full_B); V( Full_A);
【评分说明】
1)每对信号量的定义及初值正确， 给分。
2)每个互斥信号量的P、 V操作使用正确， 各给分。
3)每个同步信号量的P、 V操作使用正确， 各给分。
4)其他答案酌情给分。
46. 解答：
“ ”
1)在分页存储管理方式中， 将用户程序的地址空间分为 若干固定大小的区域， 称为 页
或 “ 页面 ” 。 相应地， 将内存空间分为若干物理块或页框(frame)页, 和页框大小相同。 因此，
页和页框大小均为212 B=4KB。 进程的虚拟地址空间大小为i32;212= 220 页。
2)(i 0x4)/i2 (页目录所占页数） + (220x4)/i2 (页表所占页数） = 1025页。
3)需要访问一个二级页表。 因为虚拟地址0100OOOOH和01112048H的最高10位的值都
是4页, 目录号相同，访问的是同一个二级页表。
【评分说明】用其他方法计算， 思路和结果正确同样给分。
47. 解答：
1)D HCP服务器可为主机 2� 主机N动态分配IP地址的最大范围是： 111.123.15.5�
111.123.15.254; 主机2发送的封装DHCPDiscover报文的IP分组的源IP地址和目的IP地址分
别是0.0.0.0 和255.255.255.255。
2)主机2发出的第一个以太网帧的目的MAC地址是ff-ff-ff-ff-ff-ff; 封装主机2发往Internet
的IP分组的以太网帧的目的MAC地址是00-al-la -la -la -。la
3)主机l能访问WWW服务器，但不能访问Interne。t 由于主机1 的子网掩码配置正确而
默认网关IP地址被错误地配置为111.123.15.2C正确IP地址是111.123.15.1),所以主机l 可以
｀ 访问在同一个子网内的WWW服务器，但当主机l访问Internet时， 主机l发出的IP分组会被
路由到错误的默认网关C111.123.15.2), 从而无法到达目的主机。
