科目组合
数据结构 、计算机组成原理 、操作系统 、计算机网络
已知头指针h 指向一个带头结点的非空单循环链表,结点结构为
已知初始为空的队列Q 的一端仅能进行入队操作,另外一端既能进行入队操作又能进行出队操作。若 Q 的入队序列是1,2, 3, 4, 5 , 则不能得到的出队序列是( )。
A、5,4,3, 1,2 B、5,3, 1,2,4 C、4, 2, 1,3,5 D、4, 1,3, 2, 5
已知二维数组A 按行优先方式存储,每个元素占用1 个存储单元。若元素A[0][0]的存储地址是100, A[3][3]的存储地址是220 ,则元素A[5][5]的存储地址是( )
某森林F 对应的二叉树为T , 若 T 的先序遍历序列是a, b, d, c, e, g, f , 中序遍历序列是b, d, a, e, g, c, f , 则 F 中树的棵数是( )
使用 Dijkstra 算法求下图中从顶点1 到其余各顶点的最短路径,将当前找到的从顶点1 到顶点2, 3, 4, 5 的最短路径长保存在数组dist中,求出第二条最短路径后,dist中的内容更新为( )
A、26,3,14,6
B、25, 3, 14, 6
C、21,3, 14,6
D、15,3, 14,6
设数组 S[] = {93, 946, 372, 9, 146,151, 301, 485, 236, 327, 43, 892}, 采用最低位优先(LSD) 基数排序将S 排列成升序序列。第 1 趟分配、收集后,元素372之前、之后紧邻的元素分别是 ( )
将关键字 6, 9, 1,5, 8, 4, 7 依次插入到初始为空的大根堆H中,得到的H 是 ( )。
2017年公布的全球超级计算机TOP500排名中,我国“神威·太湖之光”超级计算机蝉联第一,其浮点运算速度为93.0146PFLOPS,说明该计算机每秒钟完成的浮点操作次数为( )。
A. 9.3×10^13 次
B. 9.3×10^15 次
C. 9.3千万亿次
D. 9.3亿亿次
已知带符号整数用补码表示,变量x,y,z的机器数分别为FFFDH,FFDFH,7FFCH,下列结论中,正确的是( )。
A. 若x、y和z为无符号整数,则z<x<y
B. 若x、y和z为无符号整数,则x<y<z
C. 若x、y和z为带符号整数,则x<y<z
D. 若x、y和z为带符号整数,则y<x<z
某计算机的存储器总线中有24位地址线和32位数据线,按字编址,字长为32位。若000000H~3FFFFFH为RAM区,则需要512K×8位的RAM芯片数为( )。
A. 8
B. 16
C. 32
D. 64
若计算机主存地址为32位,按字节编址,Cache数据区大小为32KB,主存块大小为32B,采用直接映射方式和回写(Write Back)策略,则Cache行的位数至少是( )。
A. 275
B. 274
C. 258
D. 257
下列存储器中,汇编语言程序员可见的是( )。
Ⅰ. 指令寄存器
Ⅱ. 微指令寄存器
Ⅲ. 基址寄存器
Ⅳ. 标志状态寄存器
A. 仅Ⅰ、Ⅱ
B. 仅Ⅰ、IV
C. 仅Ⅱ、Ⅳ
D. 仅Ⅲ、Ⅳ
下列关于数据通路的叙述中,错误的是( )。
A. 数据通路包含ALU等组合逻辑(操作)元件
B. 数据通路包含寄存器等时序逻辑(状态)元件
C. 数据通路不包含用于异常事件检测及响应的电路
D. 数据通路中的数据流动路径由控制信号进行控制
下列关于总线的叙述中,错误的是( )。
A. 总线是在两个或多个部件之间进行数据交换的传输介质
B. 同步总线由时钟信号定时,时钟频率不一定等于工作频率
C. 异步总线由握手信号定时,一次握手过程完成一位数据交换
D. 突发(Burst)传送总线事务可以在总线上连续传送多个数据
异常事件在当前指令执行过程中进行检测,中断请求则在当前指令执行后进行检测。下列事件中。下列事件中,相应处理程序执行后,必须回到当前指令重新执行的是( )。
A. 系统调用
B. 页缺失
C. DMA传送结束
D. 打印机缺纸
下列是关于多重中断系统中CPU响应中断的叙述,其中错误的是( )。
A. 仅在用户态(执行用户程序)下,CPU才能检测和响应中断
B. CPU只有在检测到中断请求信号后,才会进入中断响应周期
C. 进入中断响应周期时,CPU一定处于中断允许(开中断)状态
D. 若CPU检测到中断请求信号,则一定存在未被屏蔽的中断源请求信号
下列操作中,操作系统在创建新进程时,必须完成的是( )。
I.申请空白的进程控制块
II. 初始化进程控制块
III.设置进程状态为执行态
A、仅I
B、仅I、II
C、仅I、III
D、仅II、III
下列内核的数据结构或程序中,分时系统实现时间片轮转调度需要使用的是( )。
I.进程控制块
II.时钟中断处理程序
III. 进程就绪队列
IV.进程阻塞队列
A、仅II、III
B、仅I、IV
C、仅I、 II、III
D、仅I、II、IV
某系统中磁盘的磁道数为200 (0~199),磁头当前在184号磁道上。用户进程提出的磁盘访问请求对应的磁道号依次为184, 187, 176, 182, 199。若采用最短寻道时间优先调度算法(SSTF)完成磁盘访问,则磁头移动的距离(磁道数)是( )。
A、37
B、38
C、41
D、42
下列事件中,可能引起进程调度程序执行的是( )。
I.中断处理结束
II. 进程阻塞
III.进程执行结束
IV.进程的时间片用完
A、仅I、III
B、仅II、IV
C、仅III、IV
D、I、II、III、 IV
某请求分页存储系统的页大小为4KB, 按字节编址。系统给进程P分配2个固定的页框并采用改进型Clock置换算法,进程P页表的部分内容如下表所示:
若P访问虚拟地址为02A01H的存储单元,则经地址变换后得到的物理地址是()。
A、00A01H
B、20A01H
C、60A01H
D、80A01H
在采用二级页表的分页系统中,CPU页表基址寄存器中的内容是( )。
A、当前进程的一级 页表的起始虚拟地址
B、当前进程的一级页表的起始物理地址
C、当前进程的二级页表的起始虚拟地址
D、当前进程的二级页表的起始物理地址
若目录dir下有文件filel,则为删除该文件内核不必完成的工作是( )。
A、删除file1的快捷方式
B、释放file1的文件控制块
C、释放filel占用的磁盘空间
D、删除目录dir中与filel 对应的目录项
已知无向连通图G由顶点集V和边集E组成,|E| > 0,当G中度为奇数的顶点个数为不大于2的偶数时,G存在包含所有边且长度为|E|的路径(称为EL路径)。设图G采用邻接矩阵存储,类型定义如下:
typedef struct { // 图的定义
int numVertices, numEdges; // 图中实际的顶点数和边数
char VerticesList[MAXV]; // 顶点表,MAXV为已定义常量
int Edge[MAXV][MAXV]; // 邻接矩阵
}MGraph;
请设计算法int IsExistEL(MGraph G),判断G是否存在EL路径,若存在,则返回1 ,否则返回0。要求:
⑴ 给出算法的基本设计思想。
⑵ 根据设计思想,采用C或C++语言描述算法,关键之处给出注释。
⑶ 说明你所设计算法的时间复杂度和空间复杂度。
已知某排序算法如下:
void cmpCountSort(int a[],int b[],int n) {
int i, j, *count;
count = (int *)malloc(sizeof(int) * n); //C++语言: count = new int[n];
for (i = 0; i < n; i++) count[i] = 0;
for (i = 0; i < n - 1; i++)
for (j = i + 1; j < n; j++)
if (a[i] < a[j]) count[j]++;
else count[i]++;
for (i = 0; i < n; i++) b[count[i]]= a[i];
free(count); // C++语言: delete count;
}
请回答下列问题。
⑴ 若有int a[] = {25, -10, 25, 10, 11, 19}, b[6]; ,则调用cmpCountSort(a, b, 6)后数组b中的内容是什么?
⑵ 若a中含有n个元素,则算法执行过程中,元素之间的比较次数是多少?
⑶ 该算法是稳定的吗?若是,则阐述理由;否则,修改为稳定排序算法。
假定计算机M字长为16位,按字节编址,连接CPU和主存的系统总线中地址线为20位、数据线为8位,采用16位定长指令字,指令格式及其说明如下:
其中,op1~op3为操作码,rs、rt和rd为通用寄存器编号,R[r]表示寄存器r的内容,imm为立即数,target为转移目标的形式地址。请回答下列问题。
(1) ALU的宽度是多少位?可寻址主存空间大小为多少字节?指令寄存器、主存地址寄存器(MAR)和主存数据寄存器(MDR)分别应有多少位?
(2) R型格式最多可定义多少种操作?I型和J型格式总共最多可定义多少种操作?通用寄存器最多有多少个?
(3) 假定op1为0010和0011时,分别表示带符号整数减法和带符号整数乘法指令,则指令01B2H的功能是什么(参考上述指令功能说明的格式进行描述)?若1、2、3号通用寄存器当前内容分别为B052H、0008H、0020H,则分别执行指令01B2H和01B3H后,3号通用寄存器内容各是什么?各自结果是否溢出?
(4) 若采用I型格式的访存指令中imm(偏移量)为带符号整数,则地址计算时应对imm进行零扩展还是符号扩展?
(5) 无条件转移指令可以采用上述哪种指令格式?
假设计算机M的主存地址为24位,按字节编址;采用分页存储管理方式,虚拟地址为30位,页大小为4KB;TLB采用2路组相联方式和LRU替换策略,共8组。请回答下列问题。
(1) 虚拟地址中哪几位表示虚页号?哪几位表示页内地址?
(2) 已知访问TLB时虚页号高位部分用作TLB标记,低位部分用作TLB组号,M的虚拟地址中哪几位是TLB标记?哪几位是TLB组号?
(3) 假设TLB初始时为空,访问的虚页号依次为10、12、16、7、26、4、12和20,在此过程中,哪一个虚页号对应的TLB表项被替换?说明理由。
(4) 若将M中的虚拟地址位数增加到32位,则TLB表项的位数增加几位?
下表给出了整型信号量S的wait()和signal()操作的功能描述,以及采用开/关中断指令实现信号量操作互斥的两种方法。
// 功能描述
Semaphore S;
wait(S){
while(S <= 0);
S = S-1;
}
signal(S){
S = S+1;
}
// 方法1
Semaphore S;
wait(S){
关中断;
while(S <= 0);
S = S-1;
开中断;
}
signal(S){
关中断;
S = S+1;
开中断;
}
// 方法2
Semaphore S;
wait(S){
关中断;
while(S <= 0){
开中断;
关中断;
}
S = S-1;
开中断;
}
signal(S){
关中断;
S = S+1;
开中断;
}
请回答下列问题。
(1) 为什么在wait()和signal()操作中对信号量S的访问必须互斥执行?
(2) 分别说明方法1和方法2是否正确。若不正确,请说明理由。
(3) 用户程序能否使用开/关中断指令实现临界区互斥?为什么?
某计算机用硬盘作为启动盘,硬盘第一个扇区存放主引导记录,其中包含磁盘引导程序和分区表。磁盘引导程序用于选择要引导哪个分区的操作系统,分区表记录硬盘上各分区的位置等描述信息。硬盘被划分成若干个分区,每个分区的第一个扇区存放分区引导程序,用于引导该分区中的操作系统。系统采用多阶段引导方式,除了执行磁盘引导程序和分区引导程序外,还需要执行ROM中的引导程序。请回答下列问题。
(1) 系统启动过程中操作系统的初始化程序、分区引导程序、ROM中的引导程序、磁盘引导程序的执行顺序是什么?
(2) 把硬盘制作为启动盘时,需要完成操作系统的安装、磁盘的物理格式化、逻辑格式化、对磁盘进行分区,执行这4个操作的正确顺序是什么?
(3) 磁盘扇区的划分和文件系统根目录的建立分别是在第 (2) 问的哪个操作中完成的?
某网络拓扑如题47图所示,以太网交换机S通过路由器R 与Internet互联。路由器部分接口、本地域名服务器、H1、H2的IP地址和MAC地址如图中所示。在t0时刻H1的 ARP表和S的交换表均为空,H1在此刻利用浏览器通过域名 www.abc.com请求访问Web服务器,在t1时刻(t1>t0)S 第一次收到了封装HTTP请求报文的以太网帧,假设从t0到t1期间网络未发生任何与此次Web访问无关的网络通信。
请回答下列问题。
1)从t0到t1期间,H1除了HTTP之外还运行了哪个应用层协议?从应用层到数据链路层,该应用层协议报文是通过哪些协议进行逐层封装的?
2)若S的交换表结构为<MAC地址,端口>,则t1时刻S交换表的内容是什么?
3)从t0到t1期间,H2至少会接收到几个与此次Web访问相关的帧?接收到的是什么帧?帧的目的MAC地址是什么?