2015 年计算机学科专业基础综合全国联考卷

贡献者： xzllxls

1. 一、单项选择题

　　 1～40 小题，每小题 2 分，共 80 分。下列每题给出的四个选项中。只有一个选项符合题目要求。

　　 1。已知程序如下：

int S(int n)
{
    return(n<=0)?0：s(n-1)+n；
}

void main()
{ 
    cout<<S(1)；
}

　　 2。先序序列为 a，b，c，d 的不同二叉树的个数是
A。13 $$ B。14 $$ C。15 $$ D。16

　　 3。下列选项给出的是从根分别到达两个叶结点路径上的权值序列，能属于同一棵哈夫曼树的是
A。24，10，5 和 24，10，7 $$ B。24，10，5 和 24，12，7
C。24，10，10 和 24，14，11 $$ D。24，10，5 和 24，14，6

　　 4。现有一棵无重复关键字的平衡二叉树（AVL 树），对其进行中序遍历可得到一个降序序列。下列关于该平衡二叉树的叙述中，正确的是
A。根结点的度一定为 2 $$ B。树中最小元素一定是叶结点
C。最后插入的元素一定是叶结点 $$ D。树中最大元素一定无左子树

　　 5。设有向图 G=(V，E)，顶点集 V={v0，v1，v2，v3}，边集 E：{<v0，v1>，<v0，v2>，<v0，v3>，<v1，v3>}。若从顶点 v0。开始对图进行深度优先遍历，则可能得到的不同遍历序列个数是
A。2 $$ B。3 $$ C。4 $$ D。5

　　 6。求下面带权图的最小（代价）生成树时，可能是克鲁斯卡尔（Kruskal）算法第 2 次选中但不。是普里姆（Prim）算法（从 v4 开始）第 2 次选中的边是

　　 A。(v1，v3) $$ B。(v1，v4) $$ C。(v2，v3) $$ D。(v3，v4)

　　 7。下列选项中不能构成折半查找中关键字比较序列的是
A。500，200，450，180 $$ B。500，450，200，180
C。180，500，200，450 $$ D。180，200，500，450

　　 8。已知字符串 s 为 “abaabaabacacaabaabcc”，模式串 t 为 “abaabc5’。采用 KMP 算法进行匹配，第一次出现 “失配”(s[i]≠t[j])时，i=j=5，则下次开始匹配时，i 和 j 的值分别是
A。i=1，j=0 $$ B。i=5，j=0
C。i=5，j=2 $$ D。i=6，j=2

　　 9。下列排序算法中，元素的移动次数与关键字的初始排列次序无关的是
A。直接插入排序 $$ B。起泡排序
C。基数排序 $$ D。快速排序

　　 10。已知小根堆为 8，15，10，21，34，16，12，删除关键字 8 之后需重建堆，在此过程中，关键字之间的比较次数是
A。1 $$ B。2 $$ C。3 $$ D。4

　　 11。希尔排序的组内排序采用的是
A。直接插入排序 $$ B。折半插入排序
C。快速排序 $$ D。归并排序

　　 12。计算机硬件能够直接执行的是
Ⅰ。机器语言程序 $$ Ⅱ。汇编语言程序 $$ Ⅲ。硬件描述语言程序
A。仅Ⅰ $$ B。仅Ⅰ、Ⅱ
C。仅Ⅰ、Ⅲ $$ D。Ⅰ、Ⅱ、Ⅲ

　　 13。由 3 个 “1” 和 5 个 “0” 组成的 8 位二进制补码，能表示的最小整数是
A。-126 $$ B。-125
C。-32 $$ D。-3

　　 14。下列有关浮点数加减运算的叙述中，正确的是
Ⅰ。对阶操作不会引起阶码上溢或下溢
Ⅱ。右规和尾数舍入都可能引起阶码上溢
Ⅲ。左规时可能引起阶码下溢
Ⅳ。尾数溢出时结果不一定溢出
A。仅Ⅱ、Ⅲ $$ B。仅Ⅰ、Ⅱ、Ⅳ
C。仅Ⅰ、Ⅲ、Ⅳ $$ D。Ⅰ、Ⅱ、Ⅲ、Ⅳ

　　 15。假定主存地址为 32 位，按字节编址，主存和 Cache 之间采用直接映射方式，主存块大小为 4 个字，每字 32 位，采用回写（Write Back）方式，则能存放 4K 字数据的 Cache 的总容量的位数至少是
A。146K $$ B。147K
C。148K $$ D。158K

　　 16。假定编译器将赋值语句 “x=x+3；” 转换为指令 “add xaddr，3”，其中，xaddr 是 x 对应的存储单元地址。若执行该指令的计算机采用页式虚拟存储管理方式，并配有相应的 TLB，且 Cache 使用直写（Write Through）方式，则完成该指令功能需要访问主存的次数至少是
A。0 $$ B。1 $$ C。2 $$ D。3

　　 17。下列存储器中，在工作期间需要周期性刷新的是
A。SRAM $$ B。SDRAM $$ C。ROM $$ D。FLASH

　　 18。某计算机使用 4 体交叉编址存储器，假定在存储器总线上出现的主存地址（十进制）序列为 8005，8006，8007，8008，8001，8002，8003，8004，8000，则可能发生访存冲突的地址对是
A。8004 和 8008 $$ B。8002 和 8007
C。8001 和 8008 $$ D。8000 和 8004

　　 19。下列有关总线定时的叙述中，错误的是
A。异步通信方式中，全互锁协议的速度最慢
B。异步通信方式中，非互锁协议的可靠性最差
C。同步通信方式中，同步时钟信号可由各设备提供
D。半同步通信方式中，握手信号的采样由同步时钟控制

　　 20。若磁盘转速为 7200 转/分，平均寻道时间为 8ms，每个磁道包含 1000 个扇区，则访问一个扇区的平均存取时间大约是
A。8.1 ms $$ B。12.2 ms
C。16.3 ms $$ D。20.5 ms

　　 21。在采用中断 I/O 方式控制打印输出的情况下，CPU 和打印控制接口中的 I/O 端口之间交换的信息不可能是
A。打印字符 $$ B。主存地址
C。设备状态 $$ D。控制命令

　　 22。内部异常（内中断）可分为故障（fault）、陷阱（trap）和终止（abort）三类。下列有关内部异常的叙述中，错误的是
A。内部异常的产生与当前执行指令相关
B。内部异常的检测由 CPU 内部逻辑实现
C。内部异常的响应发生在指令执行过程中
D。内部异常处理后返回到发生异常的指令继续执行

　　 23。处理外部中断时，应该由操作系统保存的是
A。程序计数器(PC)的内容 $$ B。通用寄存器的内容
C。快表（TLB）中的内容 $$ D。Cache 中的内容

　　 24。假定下列指令已装入指令寄存器，则执行时不可能导致 CPU 从用户态变为内核态（系统态）的是
A。DIV R0，R1；(R0)/(R1)→R0
B。INT n；产生软中断
C。NOT R0；寄存器 R0 的内容取非
D。MOV R0，addr；把地址 addr 处的内存数据放入寄存器 R0 中

　　 25。下列选项中，会导致进程从执行态变为就绪态的事件是
A。执行 P(wait)操作 $$ B。申请内存失败
C。启动 I/O 设备 $$ D。被高优先级进程抢占

　　 26。若系统 S1 采用死锁避免方法，S2 采用死锁检测方法。下列叙述中，正确的是
Ⅰ。S1 会限制用户申请资源的顺序，而 S2 不会
Ⅱ。S1 需要进程运行所需资源总量信息，而 S2 不需要
Ⅲ。S1 不会给可能导致死锁的进程分配资源，而 S2 会
A。仅Ⅰ、Ⅱ $$ B。仅Ⅱ、Ⅲ $$ C。仅Ⅰ、Ⅲ $$ D。Ⅰ、Ⅱ、Ⅲ

　　 27。系统为某进程分配了 4 个页框，该进程已访问的页号序列为 2，0，2，9，3，4，2，8，2，4，8，4，5。若进程要访问的下一页的页号为 7，依据 LRU 算法，应淘汰页的页号是
A。2 $$ B。3 $$ C。4 $$ D。8

　　 28。在系统内存中设置磁盘缓冲区的主要目的是
A。减少磁盘 I/O 次数 $$ B。减少平均寻道时间 $$ C。提高磁盘数据可靠性 $$ D。实现设备无关性

　　 29。在文件的索引节点中存放直接索引指针 10 个，一级和二级索引指针各 1 个。磁盘块大小为 1KB，每个索引指针占 4 个字节。若某文件的索引节点已在内存中，则把该文件偏移量（按字节编址）为 1234 和 307400 处所在的磁盘块读入内存，需访问的磁盘块个数分别是
A。1、2 $$ B。1、3 $$ C。2、3 $$ D。2、4

　　 30。在请求分页系统中，页面分配策略与页面置换策略不。能组合使用的是
A。可变分配，全局置换 $$ B。可变分配，局部置换
C。固定分配，全局置换 $$ D。固定分配，局部置换

　　 31。文件系统用位图法表示磁盘空间的分配情况，位图存于磁盘的 32～127 号块中，每个盘块占 1024 个字节，盘块和块内字节均从 0 开始编号。假设要释放的盘块号为 409612，则位图中要修改的位所在的盘块号和块内字节序号分别是
A。81、1 $$ B。81、2 $$ C。82、1 $$ D。82、2

　　 32。某硬盘有 200 个磁道（最外侧磁道号为 0），磁道访问请求序列为：130，42，180，15，199，当前磁头位于第 58 号磁道并从外侧向内侧移动。按照 SCAN 调度方法处理完上述请求后，磁头移过的磁道数是
A。208 $$ B。287 $$ C。325 $$ D。382

　　 33。通过 POP3 协议接收邮件时，使用的传输层服务类型是
A。无连接不可靠的数据传输服务
B。无连接可靠的数据传输服务
C。有连接不可靠的数据传输服务
D。有连接可靠的数据传输服务

　　 34。使用两种编码方案对比特流 01100111 进行编码的结果如下图所示，编码 1 和编码 2 分别是

　　 A。NRZ 和曼彻斯特编码 $$ B。NRZ 和差分曼彻斯特编码
C。NRZI 和曼彻斯特编码 $$ D。NRZI 和差分曼彻斯特编码

　　 35。主机甲通过 128 kbps 卫星链路，采用滑动窗口协议向主机乙发送数据，链路单向传播延迟为 250ms，帧长为 1000 字节。不考虑确认帧的开销，为使链路利用率不小于 80％，帧序号的比特数至少是
A。3 $$ B。4 $$ C。7 $$ D。8

　　 36。下列关于 CSMA/CD 协议的叙述中，错误的是
A。边发送数据帧，边检测是否发生冲突
B。适用于无线网络，以实现无线链路共享
C。需要根据网络跨距和数据传输速率限定最小帧长
D。当信号传播延迟趋近 0 时，信道利用率趋近 100％

　　 37。下列关于交换机的叙述中，正确的是
A。以太网交换机本质上是一种多端口网桥
B。通过交换机互连的一组工作站构成一个冲突域
C。交换机每个端口所连网络构成一个独立的广播域
D。以太网交换机可实现采用不同网络层协议的网络互联

　　 38。某路由器的路由表如下表所示：

　　 若路由器收到一个目的地址为 169.96.40.5 的 IP 分组，则转发该 IP 分组的接口是
A。S1 $$ B。S2 $$ C。S3 $$ D。S4

　　 39。主机甲和主机乙新建一个 TCP 连接，甲的拥塞控制初始阈值为 32 KB，甲向乙始终以 MSS=1 KB 大小的段发送数据，并一直有数据发送；乙为该连接分配 16 KB 接收缓存，并对每个数据段进行确认，忽略段传输延迟。若乙收到的数据全部存入缓存，不被取走，则甲从连接建立成功时刻起，未发生超时的情况下，经过 4 个 RTT 后，甲的发送窗口是
A。1 KB $$ B。8KB $$ C。16KB $$ D。32KB

　　 40。某浏览器发出的 HTTP 请求报文如下：

GET/index.html HTTP/1.1
Host: www.test.edu.cn
Connection : Close
Cookie: 123456

2. 二、综合应用题

　　 41～47 小题，共 70 分。

　　 41。(15 分)用单链表保存 m 个整数，结点的结构为：data,link，且|data|≤n(n 为正整数)。现要求设计一个时间复杂度尽可能高效的算法，对于链表中 data 的绝对值相等的结点，仅保留第一次出现的结点而删除其余绝对值相等的结点。例如，若给定的单链表 head 如下：

　　 则删除结点后的 head 为：

　　 要习之：
(1)给出算法的基本设计思想。
(2)使用 C 或 C++语言，给出单链表结点的数据类型定义。
(3)根据设计思想，采用 C 或 C++语言描述算法，关键之处给出注释。
(4)说明你所设计算法的时间复杂度和空间复杂度。

　　 42。(8 分)已知含有 5 个顶点的图 G 如下图所示。
请回答下列问题。
(1)写出图 G 的邻接矩阵 A(行、列下标均从 0 开始)。

　　 (2)求 $A^2$，矩阵 $A^2$ 中位于 $0$ 行 $3$ 列元素值的含义是什么？
(3)若已知具有 $n(n⩾2)$ 个顶点的图的邻接矩阵为 $B$，则 $B^m$ $(2⩽m⩽n)$ 中非零元素的含义是什么？

　　 43。(13 分)某 16 位计算机的主存按字节编址，存取单位为 16 位；采用 16 位定长指令字格式；CPU 采用单总线结构，主要部分如下图所示。图中 R0～R3 为通用寄存器；T 为暂存器；SR 为移位寄存器，可实现直送（mov）、左移一位（left）和右移一位（right）3 种操作，控制信号为 SRop，SR 的输出由信号 SRout 控制；ALU 可实现直送 A(mova)、A 加 B(add)、A 减 B(sub)、A 与 B(and)、A 或 B(or)、非 A(not)、A 加 l(ine)7 种操作，控制信号为 ALUop。
请回答下列问题。
(1)图中哪些寄存器是程序员可见的？为何要设置暂存器 T?
(2)控制信号 ALUop 和 SRop 的位数至少各是多少？

　　 (3)控制信号 SRout 所控制部件的名称或作用是什么？
(4)端点①～⑨中，哪些端点须连接到控制部件的输出端？
(5)为完善单总线数据通路，需要在端点①～⑨中相应的端点之间添加必要的连线。写出连线的起点和终点，以正确表示数据的流动方向。
(6)为什么二路选择器 MUX 的一个输入端是 2?

　　 44。(10 分)题 43 中描述的计算机，其部分指令执行过程的控制信号如题 44 图 a 所示。

　　 该机指令格式如题 44 图 b 所示，支持寄存器直接和寄存器间接两种寻址方式，寻址方式位分别为 0 和 1，通用寄存器 R0～R3 的编号分别为 0、1、2 和 3。

　　 请回答下列问题。 (1)该机的指令系统最多可定义多少条指令？
(2)假定 inc、shl 和 sub 指令的操作码分别为 01H、02H 和 03H，则以下指令对应的机器代码各是什么？
①inc R1；(R1)+1→R1
②sh1 R2，R1；(R1)<<1→R2
③sub R3，(R1)，R2；((R1))-(R2)→R3
(3)假设寄存器 x 的输入和输出控制信号分别记为 Xin 和 Xout，其值为 1 表示有效，为 0 表示无效（例如，PCout=1 表示 PC 内容送总线）；存储器控制信号为 MEMop，用于控制存储器的读（read）和写（write）操作。写出题 44 图 a 中标号①～⑧处的控制信号或控制信号取值。
(4)指令 “sub R1，R3，(R2)” 和 “inc R1” 的执行阶段至少各需要多少个时钟周期？

　　 45。(9 分)有 A、B 两人通过信箱进行辩论，每个人都从自己的信箱中取得对方的问题，将答案和向对方提出的新问题组成一个邮件放人对方的信箱中。假设 A 的信箱最多放 M 个邮件，B 的信箱最多放Ⅳ个邮件。初始时 A 的信箱中有 x 个邮件（0<x<M），B 的信箱中有 y 个邮件（0<y<N）。辩论者每取出一个邮件，邮件数减 1。A 和 B 两人的操作过程描述如下：

CoBegin
A {
  while(TRUE) {
    从A的信箱中取出一个邮件；
    回答问题并提出一个新问题；
    将新邮件放人B的信箱；
  }
}
B {
  while(TRUE) {
    从B的信箱中取出一个邮件；
    回答问题并提出一个新问题；
    将新邮件放人A的信箱；
  }
}
CoEnd

3. 参考答案

一、单项选择题

　　 1。A $$ 2。B $$ 3。D $$ 4。D $$ 5。D
6。C $$ 7。A $$ 8。C $$ 9。C $$ 10。C
11。A $$ 12。A $$ 13。B $$ 14。D $$ 15。C
16。B $$ 17。B $$ 18。D $$ 19。C $$ 20。B
21。B $$ 22。D $$ 23。B $$ 24。C $$ 25。D
26。B $$ 27。A $$ 28。A $$ 29。B $$ 30。C
31。C $$ 32。C $$ 33。D $$ 34。A $$ 35。B
36。B $$ 37。A $$ 38。C $$ 39。A $$ 40。C

二、综合应用题

　　 41。【答案要点】
$$ (1)算法的基本设计思想
算法的核心思想是用空间换时间。使用辅助数组记录链表中已出现的数值，从而只需对链表进行一趟扫描。
$$ 因为|data|≤n，故辅助数组 q 的大小为 n+1，各元素的初值均为 0。依次扫描链表中的各结点，同时检查 q[|data|]的值，如果为 0，则保留该结点，并令 q[|data|]=1；否则，将该结点从链表中删除。
$$ (2)使用 C 语言描述的单链表结点的数据类型定义

typedef struct node {
  int 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+1)); // 申请n+1个位置的辅助空间
  for(int i=0;i<n+1;i++)  // 数组元素初值置0
    *(q+i)= 0;
  while(p->link!=NULL)
  { m=p->link->data>0 ? p->link->data：-p->link一>data;
    if(*(q+m)==0) //判断该结点的data是否已出现过
    { 
      *(q+m)=1； //首次出现
      p=p->link； //保留
    }
    else //重复出现
    { r=p->link; //删除
      p->link=r->link;
      free(r);
    }
  }
  free(q);
}

　　 ②若在算法的基本设计思想描述中因文字表达没有清晰反映出算法思路，但在算法实现中能够表达出算法思想且正确的，可参照①的标准给分。
③若算法的基本设计思想描述或算法实现中部分正确，可参照①中各种情况的相应给分标准酌情给分。
④若考生给出的单链表结点的数据类型定义与题目中所给的结点形式不完全相同，酌情给分。
⑤参考答案中只给出了使用 C 语言的版本，使用 C++语言的答案视同使用 C 语言。
$$ (4)参考答案所给算法的时间复杂度为 O(m)，空间复杂度为 O(n)。 【评分说明】若考生所估计的时间复杂度和空间复杂度与考生实现的算法一致，可给分。

　　 42。【答案要点】
$$ (1)图 G 的邻接矩阵 A 如下：

　　 43。【答案要点】
(1)程序员可见寄存器为通用寄存器（R0～R3）和 PC。因为采用了单总线结构，因此，若无暂存器 T，则 ALU 的 A、B 端口会同时获得两个相同的数据，使数据通路不能正常工作。
【评分说明】回答通用寄存器（R0～R3），给分；回答 PC，给分；部分正确，酌情给分。设置暂存器 T 的原因若回答用于暂时存放端口 A 的数据，则给分，其他答案，酌情给分。
(2)ALU 共有 7 种操作，故其操作控制信号 ALUop 至少需要 3 位；移位寄存器有 3 种操作，其操作控制信号 SRop 至少需要 2 位。
(3)信号 SRout 所控制的部件是一个三态门，用于控制移位器与总线之间数据通路的连接与断开。
【评分说明】只要回答出三态门或者控制连接/断开，即给分。
(4)端口①、②、③、⑤、⑧须连接到控制部件输出端。
【评分说明】答案包含④、⑥、⑦、⑨中任意一个，不给分；答案不全酌情给分。
(5)连线 1，⑥→⑨；连线 2，⑦→④。
【评分说明】回答除上述连线以外的其他连线，酌情给分。
(6)因为每条指令的长度为 16 位，按字节编址，所以每条指令占用 2 个内存单元，顺序执行时，下条指令地址为(PC)+2。MUX 的一个输入端为 2，可便于执行(PC)+2 操作。

　　 44。【答案要点】
(1)指令操作码有 7 位，因此最多可定义 27=128 条指令。
(2)各条指令的机器代码分别如下：
①“inc R1” 的机器码为：0000001 0 01 0 00 0 00，即 0240H。
②“sh1 R2，R1” 的机器码为：0000010 0 10 0 01 0 00，即 0488H。
③“sub R3，(R1)，R2” 的机器码为：0000011 0 11 1 01 0 10，即 06EAH。
(3)各标号处的控制信号或控制信号取值如下：
①0；②mov；③mova；④left；⑤read；⑥sub；⑦mov；⑧SRout。
【评分说明】答对两个给分。
$$ (4)指令 “sub R1，R3，(R2)” 的执行阶段至少包含 4 个时钟周期；
指令 “inc R1” 的执行阶段至少包含 2 个时钟周期。

　　 45。【答案要点】

semaphore Full_A = x ;    //Fuu_A表示A的信箱中的邮件数量
semaphore Empty_A = M-x;  //Empty_A表示A的信箱中还可存放的邮件数量
semaphore Full_B = y ;    //Full_B表示B的信箱中的邮件数量
semaphore Empty_B = N-y;  //Empty_B表示B的信箱中还可存放的邮件数量
semaphore mutex_A = 1 ;   //mutex_A用于A的信箱互斥
semaphore mutex_B = 1 ;   //mutex_B用于B的信箱互斥

CoBegin
A{
while(TRUE){
P(Full_A)；
P(mutex_A)；
从A的信箱中取出一个邮件；
V(mutex_A)；
V(Empty_A)；
回答问题并提出一个新问题；
P(Empty_B)；
P(mutex_B)；
将新邮件放入B的信箱；
V(mutex_B)；
V(Full_B)；
}
}
CoEnd

CoBegin
B{
while(TRUE){
P(Full_B)；
P(mutex_B)；
从B的信箱中取出一
个邮件；
V(mutex_B)；
V(Empty_B)；
回答问题并提出一个
新问题；
P(Empty_A)；
P(mutex_A)；
将新邮件放入A的
信箱；
V(mutex_A)；
V(Full_A)；
}
}
CoEnd

　　 46。【答案要点】
(1)页和页框大小均为 4 KB。进程的虚拟地址空间大小为 232/212=220 页。
(2)$(2^{10}\times 4)/2^{12}$(页目录所占页数)+($2^{20}\times 4$)/$2^{12}$(页表所占页数)=$1025$ 页。
(3)需要访问一个二级页表。因为虚拟地址 0100 0000H 和 0111 2048H 的最高 10 位的值都是 4，访问的是同一个二级页表。
【评分说明】用其他方法计算，思路和结果正确同样给分。

　　 47。【答案要点】
(1)DHCP 服务器可为主机 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-al-al-al-al。
$$ (3)主机 1 能访问 WWW 服务器，但不能访问 Internet。由于主机 1 的子网掩码配置正确而默认网关 IP 地址被错误地配置为 111.123.15.2(正确 IP 地址是 111.123.15.1)，所以主机 1 可以访问在同一个子网内的 WWW 服务器，但当主机 1 访问 Internet 时，生机 1 发出的 IP 分组会被路由到错误的默认网关（111.123.15.2），从而无法到达目的主机。