计算机专业基础综合-试卷100_真题-无答案

计算机专业（基础综合）-试卷100

(总分130,考试时间90分钟)

1. 单项选择题

单项选择题1-40小题。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。

1. 在n个结点的线性表的数组表示中，以下算法的时间复杂度是O(1)的操作是( )。Ⅰ．访问第i个结点(1＜=i＜=n)和求第i个结点的直接前驱(2＜=i＜=n)Ⅱ．在最后一个结点后插入一个新的结点Ⅲ．删除第一个结点Ⅳ．在第i个结点后插入一个结点(1＜=i＜=n)

A. 仅Ⅰ B. 仅Ⅱ、Ⅲ

C. 仅Ⅰ、Ⅱ D. 仅Ⅰ、Ⅱ、Ⅲ

2. 中缀表达式a*(b+c)一d的后缀表达式是( )。

A. abcd*+—

B. abc+*d—

C. abc*+d—

D. —+*abcd

3. 设线性表有n个元素，以下操作中，( )在顺序表上实现比链表上实现效率更高。

A. 输出第i(1≤i≤n)个元素值

B. 交换第1个元素与第2个元素的值

C. 顺序输出这n个元素的值

D. 输出与给定值x相等的元素在线性表中的序号

4. 设k是中序线索二叉树中一个有左子女的结点，且k不是根结点，则k在中序序列下的直接前驱结点是( )。

A. k的左线索（指示中序前驱）所指示的结点

B. 从k父结点的左子女开始沿右子女链走到底的结点

C. 从k的左子女开始沿右子女链走到底的结点

D. 从k的左子女开始沿左子女链走到底的结点

5. 假定一组元素序列为{38，42，55，15，23，44，34，74，45，26}，按次序插入每个元素生成一棵平衡二叉树，那么最后得到的平衡二叉树中度为2的结点个数为( )。

A. 1 B. 3

C. 4 D. 5

6. 由23、12、45、36构成的二叉排序树有( )个，其中AVL树有( )个。

A. 13；4 B. 13；5

C. 14；5 D. 14；4

7. 对图4—1进行拓扑排序，可以得到不同的拓扑序列的个数是( )。

A. 4 B. 3

C. 2 D. 1

8. 无向图G有16条边，有3个度为4的顶点，4个度为3的顶点，其余顶点的度均小于3，则G至少有( )个顶点。

A. 10 B. 11

C. 12 D. 13

9. 以下有关m阶B—树的说法中正确的有( )。Ⅰ．每个结点至少有两棵非空子树Ⅱ．树中每个结点至多有m—1个关键字Ⅲ．所有叶子在同一层上Ⅳ．当插入一个数据项引起B—树结点分裂后，树长高一层

A. 仅Ⅰ、Ⅱ B. 仅Ⅱ、Ⅲ

C. 仅Ⅲ、Ⅳ D. 仅Ⅰ、Ⅱ、Ⅳ

10. 对以下关键字序列用快速排序进行排序，速度最慢的是( )。

A. {19，23，3，15，7，21，28}

B. {23，21，28，15，19，3，7}

C. {19，7，15，28，23，21，3}

D. {3，7，15，19，21，23，28}

11. 某个文件经内部排序得到80个初始归并段。如果操作系统要求一个程序同时可用的输入/输出文件的总数不超过15个，则按多路归并至少需要( )趟可以完成排序。

A. 2 B. 3

C. 4 D. 5

12. 考虑以下C语言代码：vc short si=—8196；unsingned short usi=si；执行上述程序段后，usi的值为( )。

A. 8196 B. 34572

C. 57339 D. 57340

13. 设浮点数的阶码用移码表示，尾数用补码表示，阶码的底数为2，阶码用3位表示（包含一位符号位），尾数用5位表示（包含1位符号位），则它能表示的最小负数为( )。

A. —8 B. —7．5

C. —128 D. —256

14. 硬盘平均寻道时间为12ms，传输速率为10MB/s，磁盘控制器延时为2ms，则一个转速为7200r/min的硬盘写1KB数据的时间为( )。

A. 13．11ms B. 14．13ms

C. 15．15ms D. 18．27ms

15. 下面关于各种存储器的说法中，正确的有( )。Ⅰ．静态RAM不是易失性存储器，而动态RAM是易失性存储器Ⅱ. PROM只能写录一次Ⅲ．EPROM是可改写的，并且也是随机存储器的一种Ⅳ．EEPROM存储器是可写存储器

A. 仅Ⅰ、Ⅱ B. 仅Ⅱ、Ⅳ

C. 仅Ⅰ、Ⅱ、Ⅲ D. 仅Ⅱ、Ⅲ、Ⅳ

16. —个Cache—主存系统，采用50MHz的时钟，存储器以每一个时钟周期传输一个字的速率，连续传输8个字，以支持块长为8个字的Cache，每个字4个字节。假设读操作所花的时间是：1个周期接受地址，3个周期延迟，8个传输周期传输8个字；写操作所花的时间是：1个周期接受地址，2个周期延迟，8个周期传输8个字，3个周期恢复和写入纠错码，则当系统以35％为读操作，65％为写操作的访问情况工作，则存储器最大带宽为( )。

A. 133．2MB/s B. 114．4MB/s

C. 126MB/s D. 120．3MB/s

17. 以下是一段指令序列：1 addi R1，20 (R1)←202 1w R2， R0，12

(R2)←M(12+(R0))3 add R3，R1，R2 (R3)←(R1)+(R2)以上指令序列中，假定采用“取指、译码/取数、执行、访存、写回”这种五段流水线方式，那么在采用“转发”技术时，需要在第3条指令之前至少加入( )条空操作(nop)指令，才能使这段程序不发生数据冒险。

A. 0 B. 1

C. 2 D. 3

18. 某计算机采用微程序控制，微指令字中操作控制字段共12位，下列说法正确的是( )。Ⅰ．若采用直接控制，则此时一条微指令最多可同时启动11个微操作Ⅱ．若采用字段直接编码控制，并要求一条微指令需同时启动3个微操作，则微指令字中的操作控制字段应分6段Ⅲ．若采用字段直接编码控制，并要求一条微指令需同时启动3个微操作，每个字段的微命令数相同，这样的微指令格式最多可包含45个微操作命令

A. 仅Ⅰ、Ⅱ B. 仅Ⅰ、Ⅲ

C. 仅Ⅱ、Ⅲ D. Ⅰ、Ⅱ和Ⅲ

19. 一条双字长直接寻址的子程序调用CALL指令，其第一个字为操作码和寻址特征，第二个字为地址码5000H。假设PC（程序计数器）当前值为1000H，SP的内容为0100H，栈顶内容为1234H，存储器按字编址，而且进栈操作是先(SP)—1→SP，后存入数据。则CALL指令执行后，SP及栈顶的内容分别为( )。

A. 00FFH，1000H B. 0101H，1000H

C. 00FEH，1002H D. 00FFH，1002H

20. 指令流水线将一条指令的执行过程分为4步，其中第1、2和4步的执行时间为△t，如图4—2所示。若该流水线顺序执行50条指令共用了203At（无需考虑相关问题），则该流水线的第3步的执行时间是( )。

A. 3△t B. 4△t

C. 5△t D. 6△t

21. 某总线总共有88根信号线，其中数据总线为32bit，地址总线为20bit，控制总线为36根，总线的工作频率为66MHz，则总线宽度为( )，传输速率为( )。

A. 32bit 264MB/s B. 20bit 264MB/s

C. 32bit 254MB/s D. 20bit 264MB/s

22. 指令( )从主存中读出。

A. 总是根据程序计数器(PC) B. 有时根据PC，有时根据转移指令

C. 根据地址寄存器 D. 有时根据PC，有时根据地址寄存器

23. 在操作系统中，用户在使用I/O设备时，通常采用( )。

A. 物理设备名 B. 逻辑设备名

C. 虚拟设备名 D. 设备序号

24. 考虑下面的基于动态改变优先级的可抢占式优先权调度算法。大的优先权数代表高优先级。当一个进程在等待CPU时（在就绪队列中，但未执行），优先权以α速率改变；当它运行时，优先权以p速率改变。所有的进程在进入就绪队列被给定优先权数为O。参数a和p可以设定给许多不同的调度算法。下列( )设定可以实现进程FIFO (First In First Out)。

A. β＞α＞0 B. α＞β＞0

C. β＜α＜0 D. α＜β＜0

25. 假设系统有5个进程，A、B、C三类资源。某时刻进程和资源状态如表4—1所示。下面叙述正确的是( )。

A. 系统不安全

B. 该时刻，系统安全，安全序列为＜P1，P2，P3，P4，P5＞

C. 该时刻，系统安全，安全序列为＜P2，P3，P4，P5，P1＞

D. 该时刻，系统安全，安全序列为＜P4，P5，P1，P2，P3＞

26. 设有一个发送者进程和接收者进程，其流程图如图4—3所示。S是用于实现进程同步的信号量，mutex是用于实现进程互斥的信号量。试问流程图中的A、B、C、D4个框中应填写什么？假定缓冲区有无限多个且初始为空，S和mutex的初值应该是什么？( )

A. P(mutex)、V(mutex)、P(S)、P(mutex) S=缓冲区的个数 mutex=1

B. P(S)、V (mutex)、P(S)、P(mutex) S=0 mutex=1

C. P(mutex)、V(mutex)、P(S)、P(mutex) S=0 mutex=1

D. P(S)、V(mutex)、P(S)、P(mutcx) S=缓冲区的个数 mutex=0

27. 考虑在一个虚拟页式存储管理的系统中，在地址变换过程中，进程状态可能发生的变化有( )。Ⅰ．进程被撤销Ⅱ．进程变为阻塞

A. Ⅰ B. Ⅱ

C. Ⅰ和Ⅱ D. 都不可能

28. 在虚拟分页存储管理系统中，若进程访问的页面不在主存，且主存中没有可用的空闲帧时，系统正确的处理顺序为( )。

A. 决定淘汰页→页面调出→缺页中断→页面调入

B. 决定淘汰页→页面调入→缺页中断→页面调出

C. 缺页中断→决定淘汰页→页面调出→页面调入

D. 缺页中断→决定淘汰页→页面调入→页面调出

29. 下列关于Belady现象和工作集的说法正确的是( )。Ⅰ．先进先出(FIFO)页面置换算法会产生Belady现象Ⅱ．最近最少使用(LRU)页面置换算法会产生Belady现象Ⅲ．为了保证进程高效的运行，它的工作集页面需要都在虚拟存储器内，否则会出现频繁的页面调入/调出现象Ⅳ．为了保证进程高效的运行，它的工作集页面需要都在主存储器内，否则会出现频繁的页面调入/调出现象

A. Ⅰ、Ⅲ B. Ⅰ、Ⅳ

C. Ⅱ、Ⅲ D. Ⅱ、Ⅳ

30. 某文件系统物理结构采用三级索引分配方法，如果每个磁盘块的大小为1024B，每个盘块索引号占用4B，请问在该文件系统中，最大的文件大小最接近的是( )。

A. 8GB B. 16GB

C. 32GB D. 2TB

31. 信息在外存空间的排列也会影响存取等待时间。考虑几个逻辑记录A、B、C、…、J，它们被存放于磁盘上，每个磁道存放10个记录，安排如表4—2所示。假定要经常顺序处理这些记录，磁盘旋转速度为20ms/r，处理程序读出每个记录后花4ms进行处理。考虑对信息的分布进行优化，如表4—3所示，相比之前的信息分布，优化后的时间缩短了( )。

A. 60ms B. 104ms

C. 144ms D. 204ms

32. 考虑单用户计算机上的下列I/O操作，需要使用缓冲技术的是( )。Ⅰ．图形用户界面下使用鼠标Ⅱ．在多任务操作系统下的磁带驱动器（假设没有设备预分配）Ⅲ．包含用户文件的磁盘驱动器Ⅳ．使用存储器映射I/O，直接和总线相连的图形卡

A. Ⅰ、Ⅲ B. Ⅱ、Ⅳ

C. Ⅱ、Ⅲ、Ⅳ D. 全选

33. 假定运行发送窗口大小为5和接收窗口大小为3的滑动窗口算法，并且在传输过程中不会发生分组失序的问题，帧序号的编码至少有( )位。

A. 2 B. 3

C. 4 D. 5

34. 以下几种CSMA协议中，什么协议在监听到介质是空闲时一定发送( )。Ⅰ．1—持续CSMAⅡ.p一持续CSMAⅢ.非持续的CSMA

A. 只有Ⅰ B. Ⅰ、Ⅲ

C. Ⅰ、Ⅱ D. 只有Ⅱ

35. 10个站点连接到一个10Mbit/s的以太网交换机上，下面说法正确的是( )。

A. 每个站点共享10Mbit/s B. 每个站点都独享1Mbit/s

C. 每个站点共享1Mbit/s D. 每个站点都独享10Mbit/s

36. —个IPv6包中“通信量类”字段的值为0，表明( )。

A. 该包优先级最低，拥塞时可以被丢弃 B. 该包优先级最高，拥塞时不能被丢弃

C. 该包中没有用户数据，只有首部 D. 该包不可进行路由器转发

37. 以太网组播IP地址224．215，145．230应该映射到组播MAC地址( )。

A. 01—00—5E—57—91—E6

B. 01—00—5E—D7—91—E6

C. 01—00—5E—5B—91—E6

D. 01—00—5E—55—91—E6

38. 在IP首部的字段中，与分片和重组无关的字段是( )。Ⅰ．总长度Ⅱ．标识Ⅲ．标志域Ⅳ．片偏移

A. 仅Ⅰ B. 仅Ⅰ、Ⅱ、Ⅳ

C. 仅Ⅱ、Ⅲ D. 仅Ⅲ、Ⅳ

39. 以下字段中，TCP首部和UDP首部都有的字段为( )。Ⅰ．目标端口号Ⅱ．帧序号Ⅲ．源端口号Ⅳ．校验号

A. 仅Ⅰ、Ⅱ、Ⅳ B. 仅Ⅰ、Ⅱ、Ⅲ

C. 仅Ⅱ、Ⅲ D. 仅Ⅰ、Ⅲ、Ⅳ

40. 路由汇聚是把小的子网汇聚成大的网络，下面4个子网：172．16．193．0/24、172．16．194．0/24、172．16．196．0/24、172．16．198．0/24，进行路由汇聚后的网络地址是( )。

A. 172．16．192．0/21 B. 172．16．192．0/22

C. 172．16．200．0/22 D. 172．16．224．0/20

2. 综合应用题

综合应用题41-47小题。

表5—1给出了某工程各工序之间的优先关系和各工序所需的时间（其中“ ”表示无先驱工序），请完成以下各题：

1. 画出相应的AOE网。

2. 列出各事件的最早发生时间和最迟发生时间。

3. 求出关键路径并指明完成该工程所需的最短时间。

输入一个按升序排序过的整数数组{1、2、4、7、11、15}以及一个整数数字15，我们可以从该数组中找到两个数字，即4和11，使得4+11=15。请实现一个时间上尽可能高效率的算法，当输入一个已经按升序排序过的整数数组和一个整数数字，在数组中查找两个数，使得它们的和正好是输入的那个整数数字。如果有多对数字的和等于输入的整数数字，输出任意一对即可。要求：

4. 给出算法的基本设计思想。

5. 根据设计思想，采用C或C++或Java语言描述算法，关键之处给出注释。

6. 说明你所设计算法的时间复杂度。

某高级语言程序中的一个while语句为“while(save[i]=k) i+=1；”，若对其编译时，编译器将i和k分别分配在寄存器s3和s5中，数组save的基址存放在s6中，则生成的MIPS汇编代码如下：loop: sll t1，s3， 2 #R [ tl]←R [s3 ]＜＜2，即 R [t1]=i*4add t1， t1，

s6 #R [ t1]←R [ t1]+R [s6] ，即 R [t1] =Address of save [i]t0， 0 (t1) #R [t0]←M [R

[t1] +0]， gp R[t0] =save [i]bne . t0，s5f exit #if R[t0]≠R[s5] then goto exitaddi s3，

s3，1 #R [s3]←R [s3]+1，即 i=i+lj loop #goto loopexit；假设从loop处开始的指令序列存放在内存80000处，则上述循环对应的MIPS机器码如图5—1所示。根据上述叙述，回答下列问题，要求说明理由或给出计算过程。

7. MIPS的编址单位是多少？数组save每个元素占几个字节？

8. 为什么指令“sll t1，s3，2”能实现4*i的功能？

9. t0和s6的编号各为多少？

10. 指令“jloop”的操作码是什么？（用二进制表示）

11. 标号exit的值是多少？如何根据指令计算得到？

12. 标号loop的值是多少？如何根据指令计算得到？

假设某计算机的主存地址空间大小为64KB，采用字节编址方式。其Cache数据区容量为4KB，采用4路组相联映射方式、LRU替换和回写(write back)策略，块大小为64B，并且每块设置了1位有效位。请问：

13. 主存地址字段如何划分？要求说明每个字段的含义、位数和在主存地址中的位置。

14. 该Cache的总容量有多少位？

15. 若Cache初始为空，CPU依次从0号地址单元顺序访问到4344号单元，重复按此序列共访问16次。若Cache命中时间为20ns，主存存取时间为200ns，试估计CPU访存的平均时间。

在下列代码中，有3个进程Pl、P2和P3，它们使用了字符输出函数putc来进行输出（每次输出一个字符），并使用了两个信号量L和R来进行进程间的同步。请问：

16. 这组进程在运行时，最后打印出来了多少个“D”字符？

17. 当这组进程在运行的时候，在何种情形下，打印出来的字符“A"的个数是最少的，最少的个数是多少？

18. 当这组进程在运行的时候，“CABABDDCABCABD”是不是一种可能的输出序列，为什么？

19. 当这组进程在运行的时候，“CABACDBCABDD”是不是一种可能的输出序列，为什么？semaphore L=3，R=0； /*初始化*//*进程P1*/ /+进程P2*/ /*进程P3*/while(1)

while (1) while (1){ { {P(L)； P(R)； P(R)；putc('C')；

putc('A')； putc('D')；V (R)； putc('B')； }}

V(R)；}

某操作系统支持页式虚拟存储管理，其中央处理器的周期是1μs。当不是处于同一页面时，访问另一个页面耗时1μs。一个页面含1K字。使用磁盘作为外存，其转速为3 000r/min，传输率1M字/s。还测得下列数据：磁盘平均寻道时间为19ms，1％的指令要访问不处于同一页面的其他页面内容，这当中，80％的被访问页已经在内存中。需要新页面时，50％的被换出页面已经修改过了。

20. 如果磁盘设备要连续传输10K字的数据，请计算出平均情况下总的访问时间。

21. 请计算该系统的有效指令时间，假设系统只有一个CPU，而且它在磁盘传输数据时是空闲的。（假设逻辑相邻的页面在磁盘上都不相邻。）

某单位有1个总部和6个分部，各个部门都有自己的局域网。该单位申请了6个C类IP地址202．115 ．10．0/24～202．115．15．0/24，其中总部与分部4共用一个C类地址。网络采用R1～R7共7台路由器，采用动态路由协议OSPF，并划分了3个OSPF区域。网络拓扑图如图5—2所示，路由器的lP地址分配见表5—2。

22. 请指出本网中哪个区域为主干区域，以及指出主干区域中的区域边界路由器及区域内路由器。

23. R3路由器各端口IP地址如何设置？

24. 如部门4共有110台计算机，通过交换机连接路由器R5接入网络。其中一台计算机IP地址为202．115．13．5，试给出其子网掩码和网关地址。