一、 单项选择题。
1. 下列程序段的时间复杂度是 1 。
count =0;
for(k=1; k<=n; k*=2)
for(j=1; j<=n; j++)
count++;
a. o(log2n)
b. o(n)
c. o(nlog2n)
d. o(n2)
2. 假设栈初始为空，将中缀表达式a/b+(c*d-e*f)/g转换为等价的后缀表达式的过程中，当扫描到f时，栈中的元素依次是 2 。
a. +b. +
c. /d. /
3. 循环队列放在一维数组a[0…m-1]中，end1指向队头元素，end2指向队尾元素的后一个位置。假设队列两端均可进行入队和出队操作，队列中最多能容纳m-1个元素。
初始时为空。下列判断队空和队满的条件中，正确的是 3 。
a. 队空：end1 ==end2队满：end1 ==end2+1)mod m
b. 队空：end1 ==end2队满：end2 ==end1+1)mod (m-1)
c. 队空：end1 ==end1+1)mod m; 队满：end1 ==end2+1)mod m
d. 队空：end1 ==end2+1)mod m; 队满：end2 ==end1+1)mod (m-1)
4. 若对如下的二叉树进行中序线索化，则结点x的左、右线索指向的结点分别是 4 。
a. e、c
b. e、a
c. d、c
d. b、a
5. 将森林f转换为对应的二叉树t，f中叶子的个数等于 5 。
a. t中叶结点的个数。
b. t中度为1的结点个数。
c. t中左孩子指针为空的结点个数。
d. t中右孩子指针为空的结点个数。
6. 5个字符有如下4种编码方案，不是前缀编码的是 6 。
a. 01,0000,0001,001,1
b. 011,000,001,010,1
c. 000,001,010,011,100
d. 0,100,110,1110,1100
7. 对如下所示的有向图进行拓扑排序，得到的拓扑序列可能是 7 。
a. 3,1,2,4,5,6
b. 3,1,2,4,6,5
c. 3,1,4,2,5,6
d. 3,1,4,2,6,5
8. 用哈希（散列）方法处理冲突（碰撞）时可能出现堆积（聚焦）现象，下列选项中，会受堆积现象直接影响的是 8 。
a. 存储效率。
b. 散列函数。
c. 装填（装载）因子）
d. 平均查找长度。
9. 在一颗具有15个关键字的4阶b树中，含关键字的结点个数最多的是 9 。
a. 5b. 6
c. 10d. 15
10. 用希尔排序方法对一个数据序列进行排序时，若第1趟排序结果为9,1,4,13,7,8,20,23,15，则该趟排序采用的增量（间隔）可能是 10 。
a. 2b. 3
c. 4d. 5
11. 下列选项中，不可能是快速排序第2趟排序结果的是 11 。
a. 2,3,5,4,6,7,9
b. 2,7,5,6,4,3,9
c. 3,2,5,4,7,6,9
d. 4,2,3,5,7,6,9
12. 程序p在机器m上的执行时间是20秒，编译优化后，p执行的指令数减少到原来的70%，而cpi增加到原来的1.2倍，则p在m上的执行时间是 12 。
a. 8.4秒。
b. 11.7秒。
c. 14秒。
d. 16.8秒。
13. 若x=102,y=-25，则下列表达式采用8位定点补码运算实现时，会发送溢出的是 13 。
a. x+y
b. –x+y
c. x-y
d. –x-y
14. float型数据常用ieee754单精度浮点格式表示。假设两个float型变量x和y分别存放在32位寄存器f1和f2中，若(f1)=cc90 0000h,(f2)=b0c0 0000h，则x和y之间的关系为 14 。
a. xb. xc. x>y且符号相同。
d. x>y且符号不同。
15. 某容量为256mb的存储器由若干4m*8位的dram芯片构成，该dram芯片的地址引脚和数据引脚总数是 15 。
a. 19b. 22
c. 30d. 36
16. 采用指令cache与数据cache分离的主要目的是 16 。
a. 降低cache的缺失损失。
b. 提高cache的命中率。
c. 降低cpu平均访存时间。
d. 减少指令流水线资源冲突。
17. 某计算机有16个通用寄存器，采用32位定长指令字，操作码字段（含寻址方式位）为8位，store指令的源操作数和目的操作数分别采用寄存器直接寻址和基址寻址方式。若基址寄存器可使用任一通用寄存器，且偏移量用补码表示，则store指令中偏移量的取值范围是 17 。
a. -32768~+32767
b. -32767-~32768
c. -65536~+65535
d. -65535~+65536
18. 某计算机采用微程序控制器，共有32条指令，公共的取指令微程序包含条微指令，各指令对应的微程序平均由4条微指令组成，采用断定法（下地址字段法）确定下条微指令地址，则微指令中下地址字段的位数至少是 18 。
a. 5b. 6
c. 8d. 9
19. 某同步总线采用数据线和地址线复用方式，其中地址/数据线有32根，总线时钟频率为66mhz，每个时钟周期传送两次数据（上升沿和下降沿各传送一次数据），该总线的最大数据传输率（总线带宽）是 19 。
a. 132mb/s
b. 264mb/s
c. 528mb/s
d. 1056mb/s
20. 一次总线事务中，主设备只需给出一个首地址，从设备就能从首地址开始的若干连续单元读出或写入多个数据。这种总线事务方式称为 20 。
a. 并行传输。
b. 串行传输。
c. 突发传输。
d. 同步传输。
21. 下列有关i/o接口的叙述中，错误的是 21 。
a. 状态端口和控制端口可以合用同一个寄存器。
b. i/o接口中cpu可访问的寄存器称为i/o端口。
c. 采用独立编址方式时，i/o端口地址和主存地址可能相同。
d. 采用统一编址方式时，cpu不能用访存指令访问i/o端口。
22. 若某设备中断请求的响应和处理时间为100ns，每400ns发出一次中断请求，中断响应所允许的最长延迟时间为50ns，则在该设备持续工作过程中，cpu用于该设备的i/o时间占整个cpu时间的百分比至少是 22 。
a. 12.5%
b. 25%
c. 37.5%
d. 50%
23. 下列调度算法中，不可能导致饥饿现象的是 23 。
a. 时间片轮转。
b. 静态优先数调度。
c. 非抢占短作业优先。
d. 抢占式短作业优先。
24. 某系统有n台互斥使用的同类设备，三个并发进程分别需要3，4，5台设备，可确保系统不发生死锁的设备数n最小为 24 。
a. 9b. 10
c. 11d. 12
25. 下列指令中，不能在用户态执行的是 25 。
a. trap指令。
b. 跳转指令。
c. 压栈指令。
d. 关中断指令。
26. 一个进程的读磁盘操作完成后，操作系统针对该进程必做的是 26 。
a. 修改进程状态为就绪态。
b. 降低进程优先级。
c. 给进程分配用户内存空间。
d. 增加进程时间片大小。
27. 现有一个容量为10gb的磁盘分区，磁盘空间以簇（cluster）为单位进行分配，簇的大小为4kb，若采用位图法管理该分区的空闲空间，即用一位（bit）标识一个簇是否被分配，则存放该位图所需簇的个数为 27 。
a. 80b. 320
c. 80k
d. 320k
28. 下列措施中，能加快虚实地址转换的是 28 。
i.增大块表（tlb）容量。
ii.让页表常驻内存。
iii.增大交换区（swap）
a. 仅ib. 仅ii
c. 仅i、ii
d. 仅ii、iii
29. 在一个文件被用户进程首次打开的过程中，操作系统需做的是 29 。
a. 将文件内容读到内存中。
b. 将文件控制块读到内存中。
c. 修改文件控制块中的读写权限。
d. 将文件的数据缓冲区首指针返回给用户进程。
30. 在页式虚拟存储管理系统中，采用某此页面转换算法，会出现belady异常现象，即进程的缺页次数会随着分配给该进程的页框个数的增加而增加。下列算法中，可能现出belady异常现象的是 30 。
算法。算法。
算法。a. 仅ii
b. 仅i、ii
c. 仅i、iii
d. 仅ii、iii
31. 下列关于管道（pipe）通信的叙述中，正确的是 31 。
a. 一个管道可实现双向数据传输。
b. 管道的容量仅受磁盘容量大小限制。
c. 进程对管道进行读操作和写操作都可能被阻塞。
d. 一个管道只能有一个读进程或一个写进程对其操作。
32. 下列选项中，属于多级页表优点的是 32 。
a. 加快地址变换速度。
b. 减少缺页中断次数。
c. 减少页表所占字节数。
d. 减少所点的连续内存空间。
33. 在osi参考模型中，直接为会话层提供服务的是 33 。
a. 应用层。
b. 表示层。
c. 传输层。
d. 网络层。
34. 某以太网拓扑及交换机当前**表如下图所示，主机00-e1-d5-00-23-a1向主机00-e1-d5-00-23-c1发送1个数据帧，主机00-e1-d5-00-23-c1收到该帧后，向主机00-e1-d5-00-23-a1发送一个确认帧，交换机对这两个帧的**端口分别是 34 。
a. 和。b. 和。
c. 和。d. 和。
35. 下列因素中，不会影响信道数据传输速率的是 35 。
a. 信噪比。
b. 频率宽带。
c. 调制速率。
d. 信号传播速度。
36. 主机甲与主机乙之间使用后退n帧协议（gbn）传输数据，甲和窗口尺寸为1000，数据帧为节，信道带宽为100mbps，乙每收到一个数据帧立即利用一个短帧（忽略其传输延迟）进行确认，若甲、乙之间的单向传播延迟是50ms，则甲可以达到的最大平均数据传输速率约为 36 。
a. 10mbps
b. 20mbps
c. 80mbps
d. 100mbps
37. 站点a、b、c通过cdma共享链路，a、b、c的码片序列（chipping sequence）分别是(1,1,1,1)、(1,-1,1,-1)和(1,1,-1,-1)。若c从链路上收到的序列是(2,0,2,0,-2,0,-2,0,2,0,2)，则c收到a发送的数据是 37 。
a. 000
b. 101
c. 110
d. 111
38. 主机甲和主机乙建立了tcp连接，甲始终以mss=kb大小的段发送数据，并一直有数据发送：乙每收到一个数据段都会发出一个接收窗口为10kb的确认段，若用在t时刻发生超时时拥塞窗口为8kb，则从t时刻起，不再发生超时的情况下，经过10个rtt后，甲的发送窗口是 38 。
a. 10kb
b. 12kb
c. 14kb
d. 15kb
39. 下列关于udp协议的叙述中，正确的是 39 。
i.提供无连接服务。
ii.提供复用/分用服务。
iii.通过差错校验，保障可靠数据传输。
a. 仅ib. 仅i、ii
c. 仅ii、iii
d. 仅i、ii、iii
40. 使用浏览器访问某大学web**主页时，不可能使用到的协议是 40 。
a. ppp
b. arp
c. udp
d. smtp
二、 综合应用题。
41. 二叉树的带权路径长度（wpl）是二叉树中所有叶结点的带权路径长度之和。给定一棵二叉树t，采用二叉链表存储，结点结构为：
其中叶结点的weight域保存该结点的非负权值。设root为指向t的根结点的指针，请设计求t的wpl的算法，要求：
1) 给出算法的基本设计思想；
2) 使用c或c++语言，给出二叉树结点的数据类型定义；
3) 根据设计思想，采用c或c++语文描述算法，关键之处给出注释。
42. 某网络中的路由器运行ospf路由协议，题42表是路由器r1维护的主要链路状态信息（lsi），题42图是根据题42表的接口名构造出来的网络拓扑。
题42图 r1构造的网络拓扑。
请回答下列问题。
1) 本题中的网络可抽象为数据结构中的哪种结构？
2) 针对题42表中的内容，设计合理的链式存储结构，以保存题42表中的链路状态信息（lsi）。要求给出链式存储结构的数据定义，并画出对应题42表的链式存储结构示意图（示意图中仅以id标识结点）。
2023年考研计算机统考408真题
一 单项选择题。1.求整数n n 0 阶乘的算法如下，其时间复杂度是 1 int fact int n record 若record变量的首地址为0xc008，则地址0xc008中内容及的地址分别为15 a.0x xc00d b.0x xc00e c.0x xc00d d.0x xc00e 16.下...
2023年考研计算机统考408真题
一 单项选择题。1.为解决计算机主机与打印机之间速度不匹配问题，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是 1 a.栈。b.队列。c.树。d.图。2.设栈s和队列q的初始状态均为空，元素a,b,c,d,e,f,g依次进...
06计算机考研统考大纲计算机组成原理考点分析
存储器的层次结构。这一章中我们建立存储器体系的 cache 内存 外存 三层结构，要掌握存储器的分类以及各类存储器的基本工作原理和主存储器 内存 与cpu的连接和数据交换 双口ram和多模块存储器。关于外存的知识点主要放在了输入输出系统一章考查。这一章中两个必须要掌握的地方就是高速缓冲存储器 cac...