考研计算机学科专业基础综合-44 (总分149,考试时间90分钟)
一、单项选择题
下列每题给出的四个选项中，只有一个选项最符合试题要求。
1. 在具有n个结点的顺序表，算法的时间复杂度是O(1)的操作是______。 A．访问某个结点 B．插入一个新结点
C．删除一个已经存在的结点 D．将顺序表从大到小排序
2. 若线性表最常用的运算是查找第i个元素及其前驱的值，则下列存储方式最节省时间的是______。
A．单链表 B．双链表 C．单循环链表 D．顺序表
3. 已知循环队列存储在一维数组A[0，…，n-1]中，且队列非空时front和rear。分别指向对头和队尾。若初始时队列为空，且要求第一个进入队列的元素存储在A[0]处，则初始时front，和rear的值分别为______。
A．0，0 B．0，n-1 C．n-1，0 D．n-1，n-1
4. 某二叉树的高度为50，树中只有度为0和度为2的结点，那么此二叉树中所包含的结点数最少为______。
A．88 B．90 C．99 D．100
5. 在线索化二叉树中，t所指结点没有左子树的充要条件是______。 A．t-＞left=NULL B．t-＞ltag=1
C．t-＞ltag=1且t-＞left=NULL D．以上都不对
6. 在含有15个结点的平衡二叉树上，查找关键字为28(存在该结点)的结点，则依次比较的关键字有可能是______。
A．30．36 B．38，48，28
C．48，18，38，28 D．60，30，50，40，38，36
7. 以下关于图的说法正确的是______。
Ⅰ．一个有向图的邻接表和逆邻接表中的结点个数一定相等
Ⅱ．用邻接矩阵存储图，所占用的存储空间大小只与图中结点个数有关，而与图的边数无关
Ⅲ．无向图的邻接矩阵一定是对称的，有向图的邻接矩阵一定是不对称的 A．Ⅰ，Ⅱ B．Ⅱ，Ⅲ C．Ⅰ，Ⅲ D．仅有Ⅱ
8. 存在一个由8个结点组成的图，结点从0～7编号，图中有13条有向边，分别是：0-7 0-1 1-4 1-6 2-3 3-4 4-2 5-2 6-0 6-3 6-5 7-1 7-3，下面选项中哪个是该图的强连通分量______。 A．0-1-4 B．3-5-6 C．0-1-6-7 D．1-4-3
9. 有一个长度为12的有序表，按二分查找法对该表进行查找，在表内各元素等概率情况下，查找失败时所需的平均比较次数是______。
A．37/12 B．62/13 C．39/12 D．49/13
10. 通过一趟排序，将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，再分别对这两部分记录进行下一趟排序，以达到整个序列有序，这种排序算法称作______。
A．直接插入排序 B．基数排序 C．快速排序 D．归并排序
11. 数据序列F=2，1，4，9，8，10，6，20只能是下列排序算法中______的两趟排序后的结果。
A．快速排序 B．胃泡排序 C．选择排序 D．插入排序
12. 在计算机的不同发展阶段，操作系统最先出现在______。
A．第一代计算机 B．第二代计算机 C．第三代计算机 D．第四代计算机
13. 浮点加减运算结果满足______时，应作“机器零”处理。
A．尾数为“全0” B．阶码上溢 C．阶码下溢 D．A或者C
14. 补码定点小数除法中，被除数和除数应满足______。 A．0≤|被除数|≤|除数| B．0＜|被除数|≤|除数| C．0＜|除数|≤|被除数| D．0＜|被除数|＜|除数|
15. 已知Cache命中率H=0.98，主存比Cache慢4倍，已知主存储取周期为200ns，平均访
问时间是______。
A．125ns B．75ns C．55ns D．53ns
16. 某8位机的地址码为16位，主存按字节编址，该机所允许的最大主存空间是______。 A．16KB B．24KB C．48KB D．64KB
17. 下面的寻址方式中，指令中包含操作数的地址的是______。 A．直接寻址 B．立即寻址 C．寄存器寻址 D．间接寻址
18. 在基址寻址方式中，若基址寄存器BR的内容为2D3CH，形式地址A的内容为53H，则有效地址EA为______。
A．53H B．2D3CH C．2D8FH D．803CH
19. 中央处理器中不包括______。
A．指令寄存器 B．指令译码器 C．数据寄存器 D．地址寄存器
20. 某指令流水线由5段组成，第1、3、5段所需时间为，第2、4段所需时间分别为，如下图所示那么连续输入n条指令时的吞吐率(单位时间内执行的指令个数)TP是。
A． B． C． D．
21. 某机采用计数器定时查询方式来进行总线判优控制，共有4个主设备竞争总线使用权，当计数器初值恒为102(二进制)时，4个主设备的优先级顺序为______。
A．设备0＞设备1＞设备2＞设备3 B．设备2＞设备1＞设备0＞设备3 C．设备2＞设备3＞设备0＞设备1 D．设备2=设备3=设备0=设备1
22. CPU在响应中断的过程中，保护现场的工作由______完成。 A．中断隐指令 B．中断服务程序 C．A或B D．A和B共同
23. 操作系统提供给用户的接口方式包括______。
A．命令方式和函数方式 B．命令方式和系统调用方式
C．命令方式和文件管理方式 D．设备管理方式和系统调用方式
24. 下面选项中，不能实现进程之间通信的是______。
A．数据库 B．共享内存 C．消息传递机制 D．管道
25. 为了实现进程之间的同步和互斥，我们使用PV操作，从本质上讲PV操作是______。 A．机器指令 B．系统调用命令
C．作业控制命令 D．低级进程通信原语
26. 避免死锁是指在资源的动态分配过程中，防止系统进入______状态。 A．死锁 B．安全 C．不安全 D．循环
27. 操作系统对内存的管理方式中，______不会产生内部碎片。 A．分页式存储管理 B．分段式存储管理
C．固定分区式存储管理 D．段页式存储管理
28. 某个页式存储管理系统，接收了一个大小一共7页的程序，其依次访问的页为：1，2，3，4，2，1，5，6，2，1，2，3，7。若分配给该程序的内存空间为4页，并一次预装入。用LRU调度算法，首先淘汰的页面是______。 A．1 B．2 C．3 D．4
29. 位示图可用于磁盘空间的管理。设某系统磁盘共有500块，块号从0到499；第0字的第0位表示第0块，第0字的第1位表示第1块，依次类推。若用位示图法管理这500块的磁盘空间，当字长为32位时，第i个第j位对应的块号是______。 A．32i+j B．32i+j-1 C．32i+j-32 D．32i+j-32-1
30. 某操作系统的文件管理采用直接索引和多级索引混合方式，文件索引表共有10项，其中前8项是直接索引项，第9项是一次间接索引项，第10项是二次间接索引项。假定物理块的大小是1K，每个索引项占用4个字节，则该文件系统中最大的文件可以达到______。 A．65536K B．32768K C．65793K D．34000K
31. 设备管理中，设备映射表(DMT)的作用是______。 A．管理物理设备 B．管理逻辑设备
C．实现输入/输出 D．建立逻辑设备与物理设备的对应关系
32. 在一个磁盘上，有1000个柱面，编号从0～999，假设最后服务的请求是在磁道345上，并且读写头正在朝磁道0移动。按FIFO顺序排列的队列中包含了如下磁道上的请求：123、874、692、475、105、376。利用SCAN调度算法满足系统请求，那么磁盘臂必须移过的磁道的数目为______。
A．1298 B．2013 C．1219 D．1967
33. ______是一个事实的网络工业标准。
A．TCP/IP B．OSI/ISO C．IEEE802.11 D．以上均不正确
34. RS232-C接口规范所处的层次是______。
A．物理层 B．数据链路层 C．网络层 D．传输层
35. 若数据链路的发送窗口尺寸WT=4，在发送3号帧、并接到2号帧的确认帧后，发送方还可连续发送的帧数是______。
A．2帧 B．3帧 C．4帧 D．1帧
36. 一个大型跨国公司的管理者从网络管理中心获得一个A类IP地址121.0.0.0，需要划分1000个子网，选择子网号的位长为______。 A．11 B．10 C．12 D．13
37. 一台主机的IP地址为11.1.1.100，子网掩码为255.0.0.0。现在用户需要配置该主机的默认路由。经过观察发现，与该主机直接相连的路由器具有如下4个IP地址和子网掩码： Ⅰ．IP地址：11.1.1.1，子网掩码：255.0.0.0 Ⅱ．IP地址：11.1.2.1，子网掩码：255.0.0.0 Ⅲ．IP地址：12.1.1.1，子网掩码：255.0.0.0 Ⅳ．IP地址：13.1.2.1，子网掩码：255.0.0.0
那么IP地址和子网屏蔽码可能是该主机的默认路由的是______。 A．Ⅰ和Ⅱ B．Ⅰ和Ⅱ C．Ⅰ，Ⅲ和Ⅳ D．Ⅲ和Ⅳ
38. TCP是采用______来控制流量的。
A．设定拥塞窗口 B．TCP首部中的接收窗口 C．设定拥塞阀值 D．通过标志位来通知
39. 在TCP/IP模型中，主机采用______标识，运行在主机上的应用程序采用______标识。 A．端口号，主机地址 B．主机地址，IP地址 C．IP地址，主机地址 D．IP地址，端口号
40. 一个门P的用户，发送了LIST命令来获取服务器的文件列表，这时候服务器应该通过______端口来传输该列表。
A．21 B．20 C．22 D．19
二、综合应用题
设一段正文由字符集A，B，C，D，E，F中的字母组成，这6个字母在正文中出现的次数分别为12，18，26，6，4，34。
1. 为这6个编码设计哈夫曼编码；
2. 设每个字节由8位二进制位组成，试计算按哈夫曼编码压缩存储这段正文共需多少个字节；
3. 若这段正文开始部分的二进制编码序列为：XX11010100，请按(1)的哈夫曼编码将其译为正文。
已知一个线性表，其中的数据元素类型均为整型。现有两个单链表La和Lb，其中La只能存储偶数而Lb只能存储奇数。现想利用La和Lb来存储此线性表。请完成以下问题：
4. 给出算法的主要思想； 5. 写出算法的实现函数；
6. 总结所用算法的时间和空间复杂度。
已知4位有效信息为1010，试根据下列要求进行编码。
7. 按配偶原则将其编码为扩展的海明码，要求能发现两位错并纠正一位错。 8. 将其编码为循环冗余校验码，生成多项式G(x)=1011。 9. 一台计算机有分离的数据和指令Cache。同时该计算机还采用了页式虚拟存储器技术。这里假定页面和Cache块具有大小相同。已知Cache的存取速度为10ns，主存的存取速度为60ns，磁盘的存取速度为12ms。该计算机的时钟周期为10ns。如果指令和数据的提取均命中Cache，指令的执行需要1个时钟周期。Cache采用的是直接映射并使用写回策略。在Cache中平均50%的块是修改过的。对于主存，同样采用写回策略，主存中平均30%的页面已经被修改。
我们假定指令在Cache和主存中的命中率均为95%，而数据在Cache和主存中的命中率为90%，我们还知道一般情况下35%的指令存取数据，求这种情况下的最大CPI。该题必须写出计算过程，并对每一步作必要的说明，否则不给分。
关于分页系统，回答下列问题：
10. 在页表中，哪些数据项是为实现换页而设置的?
11. 设某系统为每个作业进程分配3个内存块，某作业进程在运行访问中的轨迹为1，4，3，1，6，8，1，且每一页都是按请求装入的。问：先进先出页面置换算法(FIFO)和最近未使用页面置换算法(LRU)下，产生缺页的次数各是多少?(画出必要的数据图) 12. 在什么情况下，上述两种页面淘汰算法执行效果是一样的?为什么?
13. 现有A，B两队人要过河，河上有船，但是每次只能乘坐4个人，并且每次乘客满员才能开船，到河对岸后空船返回。由于某种原因，过河时船上不能同时有三个A队人员、一个B队人员或者一个A队人员、三个B队人员的组合(即其他组合是安全的)。请编写程序，用PV操作正确解决A，B两队人过河的问题，并说明所设置的信号量及其初值。
已知一个局域网连接图如下图：
主机A的IP地址为192.168.48.19，物理地址为DE.24.E4.EF.C5.B2；主机B的IP地址为192.168.48.12，主机C的IP地址为192.168.48.21。 请回答下列问题：
14. 主机A如何得知主机B的物理地址(指出所使用的协议名称和协议工作原理)? 15. 一个IP包的源地址和目的地址分别是192.168.48.19和192.168.48.21，为了发送该IP包，源主机应该先发送什么帧?
16. 该分组的以太网帧的源地址、目的地址和协议类型域各是什么?(用16进制表示)
因篇幅问题不能全部显示，请点此查看更多更全内容