科目组合

数据结构 、计算机组成原理 、操作系统 、计算机网络

请问：以下代码的时间复杂度是多少？

int count = 0;
for (int i=O; i*i<n; i++)
    for (int j=0; j<i; j++)

A. logn    B.n    C.nlogn    D.n^2

对于括号匹配问题，符号栈初始为空，容量为3，哪个表达式不能实现?

A. (a+[b+(c+d)e]+f)+g-h

B.[a*((b+c)/(d-e)+f/g)]-h

C.[a*(b-(c-d)*e/(f+g))-h]

D.[a-(b+[c*(d+e)-f]+g+h)]

以下数组不能作为完全二叉树的是?

D.17，20,35,-1,18，45,-1，-1，29,2
 

以下说法正确的是?

B.任意一个森林可以转换为一棵二叉树。

哈夫曼编码长度大于等于3的结点数有多少个

A.2
B.3
C.4
D.5

以下说法正确的是?

B.有向无环图的拓扑排序存在且唯一的

C.各顶点的度均大于等于2的无向图必有回路

400个元素，分块，问每块分多少个

A.8
B.10
C.20
D.25
 

7个关键字的4 阶B树有多少种?

A.7

B.8

C.9

D.10
 

下面关于散列表的说法正确的是?

A.只要线性表不满，线性探查再散列—定能戈到一个空闲位置。

B.只要线性表不满，二次探查再散列一定能找到一个空闲位置。

C.线性探测法的冲突一定是同义词和同义词比较。

D.二次探测法的冲突一定是同义词和同义词比较。
 

在最坏情况下，移动次数最少的是

A.冒泡排序

B.直接插入排序

C.快速排序

D.简单选择排序
 

初始序列为{ 8, 3, 9, 11, 2, 1, 4, 7, 5, 10, 6 }第二趟排序之后的结果为{1, 2, 6, 4, 3, 7, 5, 8, 11, 10, 9}，请问是用的哪种排序?

A.希尔排序

B.基数排序

C.归并排序

D.折半插入排序
 

short si=-32767

unsigned int ui = si;

A.2^15 - 1

B.2^15 + 1

C.2^32 - 2^15 - 1

D.2^32 - 2^15 + 1

IEEE754，float类型是4730 0000H，请问真值是多少?

A. 0.375×2^14

B. 1.375×2^14

C.0.375×2^15

D. 1.375×2^15

x=A3H, y=75H，计算x-y，求真值和OF标志?

A.24, 0

B.24, 1

C.46, 0

D.46, 1

struct record{
    int id;
    char name[10];
    int salary;
}employee[200];

数组employee的起始地址为000OAOBOH,employee[1].id 的机器数为12345678H，问56H的地址是多少?

A. 0000 A0C3H

B. 0000 A0C4H

C. 0000 A0C5H

D. 0000 A0C6H

ISA 规定了以下哪个?

A. 阵列乘法器

B. 定长指令字

C. 微程序控制器

D. 单总线数据通路
 

关于RISC说法错误的是?

A.硬连线方式

B. load/store

C.难以采用流水线数据通路实现微架构

D.寄存器传递过程调用函数
 

关于CPI和CPU说法错误的是?

A.

B.程序的CPI与Cache缺失率无关

C.微程序控制器

D.单总线数据通路

关于数据通路说法错误的是?

A.通用寄存器包含PC

C.单周期指令时钟周期按照最耗时的指令确定时钟周期

D.流水线cpu按照最长的流水段确定时钟周期长度
 

处理机总线，同步方式，并行传输方式。每个总线时钟周期传4次数据(quad-pumped)，总线工作频率1333MHz

A. 10.665 GB/s

B. 42.66 GB/s

C. 85.31 GB/s

D. 341.25 GB/s

适合DMA的设备

l.键盘

ll.网卡

Ⅲ.固态硬盘

IV.针十式打印机

A.l、ll    B.II、Ⅲ   C.II、IV    D.III、IV

会触发外中断的事件

A.DMA传送结束

B.总线事务结束

C.页故障处理结束

D.执行断点指令
 

虚拟页式管理系统中，进程上下文切换时，不用更新的是

A.通用寄存器

B.页表基址寄存器

C.程序计数器

D.内核中断向量表基址寄存器
 

关于虚拟化技术，错误的是

A.操作系统可以在虚拟机上运行

B.一台主机可以支持多个虚拟机

C. VMM与操作系统特权级相同

D.通过虚拟机技术，可以用一台主机上模拟多种ISA
 

优先权调度，采用单链表保存进程就绪队列，高优先级进程在队头。就绪队列长度为n，问插入进程、选出进程的时间复杂度

A.O(1) O(1)

B.O(1) O(n)

C.O(n) O(1)

D.O(n) O(n)
 

LRU算法，固定分配局部置换，已为进程分配3个页框，页面访问序列为{0，1，2，0，5，1，4，3，0，2，3，2，0}，其中0，1，2已调入内存。问缺页次数

A. 5

B.6(待核实)

C.7

D.8
 

确定进程运行所需的最少页框数时，要考虑的指标是(  )

A.代码段长

B.虚拟地址空间大小

C.物理地址空间大小

D.指令系统支持的寻址方式
 

关于虚拟文件系统，正确的是(  )

A.虚拟文件系统是运行在虚拟内存的文件系统

B. VFS 可以加快文件系统的访问速度

C. VFS定义了可访问不同文件系统的统一接口

D. VFS 只能访问本地文件系统，不能访问网络文件系统
 

某文件系统采用索引节点方式。用户在目录中新建文件F时，文件系统不会做的是(  )

A.初始化文件F的索引节点

B.在目录文件中写入F的索引节点号

C.在目录文件中写入F的访问权限信息

D.在目录文件中增加一条文件F对应的目录项

关于内存映射文件，正确的是(  )

I.可实现进程间通信

ll.实现了页面到磁盘块的映射

Ⅲ.将文件映射到进程的虚拟地址空间

Ⅳ.将文件映射到系统的物理地址空间

A.I、Ⅲ

B.I、IV

C.II、Ⅲ

D.I、ll、Ⅲ

可用于记外存空间使用情况的是 ()

A.目录

B.系统打开文件表

C.文件分配表(FAT)

D.进程控制块
 

文件系统要为温彻斯特硬盘、固态硬盘都提供的功能是(  )

A.划分扇区

B.确定盘块大小

C.降低寻道时间

D.实现均衡磨损
 

H1、H2之间按电路交换方式、报文交换方式、分组交换方式传送2MB(1M=10^6）文件。接收文件全部内容所需时间记为 Tcs、Tms、Tps 问这三个耗时的大小关系是(  )

A.Tcs>Tms>Tps

B.Tms>Tpg>Tcs

C.Tms>Tcs>Tps

D.Tps>Tws>Tcs
 

某差错编码的编码集为{10011010，01011100，11110000，00001111}，其检错、纠错能力是(  )

A.可以检测不超过2位错，检错率100%;可纠正不超过1位错

B.可以检测不超过2位错，检错率100%;可纠正不超过2位错

C.可以检测不超过3位错，检错率100%;可纠正不超过1位错

D.可以检测不超过3位错，检错率100%;可纠正不超过2位错
 

10BaseT 以太网，甲乙处于同一个冲突域，连续发生11次冲突，甲再次发送的最大时间间隔为(  )

A.0.512ms

B.0.5632ms

C.52.3776ms

D.104.8064ms
 

DHCP协议的REQUEST报文，目的IP、源IP为(  )

A

B

C.255.255.255.255, 0.0.0.0

D.
 

NAT路由器从内网转发一个IP分组到外网，IP分组内携带UDP 数据报，问UDP首部被修改的是(  )

l.源端口号

Ⅱ目的端口号

Ⅲ总长度

Ⅳ校验和

A. ll、Ⅲ

B. l、IV

C. lI、Ⅲ

D. II、IV
 

t0时刻，甲的ssthresh=8，拥塞窗口=2，发送窗口=2，MSS=1000B。在t1时刻，甲可以再给乙发送(  )个TCP段

A.2

B.3

C.4

D.5
 

Time服务器采用C/S模型，RTT=8ms。采用UDP、TCP请求时间服务器，最短耗时为(  )

A. 8ms 8ms

B. 8ms 16ms

C. 16ms 8ms

D.16ms 16ms

关于POP3，正确的是(  )

Ⅰ支持用户代理从邮件服务器读取邮件

lI支持用户代理向邮件服务器发送邮件

Ⅲ支持邮件服务器之间发送与接收邮件

Ⅳ支持一条TCP连接收取多封邮件

A l、IV

B lI、Ⅲ

C l、II、Ⅲ

Dl、Ⅲ、IV

有两个长度均为n的一维整型数组An]、res[n]，计算A[i]与A[i](0≤i≤j≤n-1)乘积的最大值，并将其保存到res[i]中。若A[]={1，4,-9,6}，则得到res[]={6，24，81，36}。现给定数组A，请设计时间空间上尽可能高效的算法CalMulMax，求res中各元素的值。函数原型为: void CallMulMax(int A[], int res[],int n)。

1)给出算法的基本思想。(4分)

2)用CIC++描述算法关键之处给出注释。(7分)

3)说明时间、空间复杂度。(2分)

AOE网，描述12个工程活动及持续时间

(1）完成该工程的最短时间是多少?哪些是关键活动?

(2）若以最短时间完成工程，则与活动e同时进行的活动可能有哪些?

(3）时间余量最大的活动是哪个?其时间余量是多少?

(4)假设工程从时刻0启动，因某种原因，活动b在时刻6开始，为保证工程不延期,在其它活动持续时间保持不变的情况下， b的持续时间最多是多少?若不改变b的持续时间，则压缩哪个活动的持续时间也能保证工程不延期?

计算机M字长为32位，按字节编址，数据cache的数据区大小为32KB，采8路组相联，主存块大小为64B，cache命中时间为2个时钟周期，缺失损失为200个时钟周期，采用页式虚拟存储，页大小为4KB。数组d的起始地址为0180 0020H(VA31 ~VA0)

1)主存地址中的Cache组号，块内地址分别占几位? VA中哪些位可以作为Cache索引。

2) d[100]的VA是多少? d[100]所在主存块中对应的 Cache 组号是多少?

3)设代码已经在cache 中, i,x已装入内存,但不在cache，则 d[0]在其主存块内
的偏移量是多少?执行for 的过程中，访问d的Cache 缺失率和数组元素的平均访问时间分别是多少?(缺失率用百分比表示，保留两位小数)

4) d分布在几个页中?若代码已在主存,d不在主存，则执行for的过程中，访问d
所引起的缺页次数是?

int x,d[2048],i;
for(i=0;i<2048;i++)
    d[i]=d [i]/x;

接上题，R0~R4为通用寄存器，SEXT表示按符号扩展，M中补码除法器，逻辑结构图如下:

机器级代码:
//x在R2中，i在R4中
//数组d的首地址在R3中
mov R1,(R3+R4*4) //R1<-d [ i ]
scov R1 // {R0,R1}<-SEXT(R1)
idiv R1 //R1<-({R0,R1}/R2)

1)若执行idiv指令时, d[i]=ox87654321,x=0xff，则补码除法器中R,Q，Y的初始值分别为多少，(用十六进制表示)?图b中哪个部分包含计数器?在补码除法器执行过程中，ALUop所控制的ALU运算有哪几种?

2)假设idiv执行过程中会检测并触发除法异常,则执行idiv指令时,哪些情况下会发生除法异常（要求给出此时d[i]和x的十六进制机器数)?发生除法异常时，在异常响应过程中，CPU需要完成哪些操作?

三个人一起植树，甲挖坑，乙放树苗入坑并填土，丙负责为新种树苗浇水。步骤依次为:挖树坑，放树苗，填土和浇水。现在有铁锹和水桶各一个，铁锹用于挖树坑,填土。水桶用于浇水。当树坑数量小于3时，甲才可以挖树坑。设初始坑=0，铁锹水桶均可用，定义尽可能少的信号量，用wait ()和signal ()操作描述植树过程中三人的同步互斥关系，并说明所用信号量的作用及其初值。
 

某进程的虚拟地址空间如图，阴影部分为未占用区域，有C程序:
char * ptr;
void main() {
int length;
ptr=(char* ) malloc (100) ;
scanf( "%s" , ptr);
length=strlen (ptr) ;
printf ( "length= %d\n" , length) ;
free(ptr) ;
}

1)上述程序执行时，PCB位于哪个区域，执行scanf ()等待键盘输入时，该进程处于什么状态?

2) main ()函数的代码位于哪个区域?其直接调用的哪些函数的功能需要通过执行驱动程序实现?

3）变量ptr被分配在哪个区域?若变量length没有被分配在寄存器中，则会被分配在哪个区域? ptr 指向的字符串位于哪个区域?

(1）忽略卫星信号中继，TR1，TR2调制解调开销，则R1到R2之间的卫星链路单向传播时延是多少?主机H向总部服务器传输数据时可达到的最大吞吐量是多少?若忽略各层协议首部开销，以及以太网的传播时延，则H-〉sever上传一个4000B的文件，至少需要多长时间?

(2）基于GBN为卫星链路设计单向可靠的链路层协议SLP，支持R1->R2'发送数据。SLP数据帧长1500B，忽略ACK帧长度，要求SLP单向信道利用率不低于80%，则发送窗口至少为?SLP帧序号至少为多少?

(3)总部给工程部分配IP地址空间10.10.10.0/24，再划分为3个子网，生活区子网不少于120个，作业子网，管理区子网IP均不少于60个，H已正确配置IP。问作，管，生子网地址各是多少?