一、单项选择题： 1-4小题 ，每小题2分，共80分。下列每题给出的四个选项中， 只有一个选项是符合题目要求的。
数据结构部分
l 、下列对顺序存储的有序表(长度为n) 实现给定操作的算法中平均时间复杂度为 0( 1 ) 的是 ( )。
A 查找包含指定但元索的值 B 插入包含指定但元素的算法
C 删除第1个元素的算法 D 获取第1个伯的算法
【参考答案】D
2、现有非空双向链表L, 其纠点结构为
prer是指向前自接前驱结点的指针， next是指向自接后继结点的指针。若要在L中指针p所指向的结点(非尾结点)之后插入指针s指向的新结点，则在执行了语句序列：
"s- > oext=p- > next;p-> next=s" , 后，还裳执行( )。
A.s->next->prer=p; s->prer=p;
B.p->next->prer=s;s->prer=p;
C.s->prer=s->next->prer; s->next->prer=s;
D.p->next->prer=s->prer;s->next->prer=p;
【参考答案】C
3、若采用三元组表存储结构存储系数矩阵M。 则除三元组外 ，下列数据中还需要保存的是( )。
I. M 的 行数 II M 中包含 非零元素的行数
111 . M 的列数 I V M 中包 含十巨零儿索的列数
A 仅I、II I
B. 仅 I、II
C. 仅 I II 、IV
D. I、II、III、IV
【参考答案】A
4、在有 6 个字符组成的字符集S 中，各个字符出现的频次分别为3,4, 5, 6, 8, 10 ,为S构造的哈夫曼树的加权平均长度为( )。
A. 2. 4
B. 2.5
C. 2.67
D. 2. 75
【参考答案】B
5 、已知一棵二叉树的树形如图 ，若其后序遍历为f,d,b,e,c,a, 则其先序列为( )。
A.aedfc
B.acebdf
C.cabefd
D.dfebac
参考答案：A
6、已知无向连通图G中各边的权伯均为1，下列算法中一定能够求出图G中从某顶点到其余各个顶点最短路径的是( )。
Ⅰ.普利姆纾法
Ⅱ.克鲁斯卡尔算法
Ⅲ. 图的广度优先搜索
A.仅 Ⅲ.
B.仅Ⅰ.Ⅱ.
C 仅Ⅰ.Ⅲ.
D.仅Ⅰ.Ⅱ.Ⅲ.
参考答案：A
7、下列关于非空B树的叙述中，正确的是( )。
I. 插入橾作可能增加树的高度
Ⅱ. 删除操作一定会导致叶结点的变化
Ⅲ. 查找某一关键字一定是要查找到叶结点
IV.插入的新关键字最终位于叶结点中
A 仅I
B 仅1、Ⅱ
C 仅III、IV
D 仅I、Il、IV
参考答案：B
8 、对含有600个元索的有序顺序表进行折半查找，关键字之间的比较次数最多是( )。
A.9
B.10
C.30
D.300
参考答案：B
9、现有长度为5，初始为空的散列表HT ,散列表函数H(K)=(k+4)%5用线性探查再散列法解决冲突。若将关键字序列2022,12 ,25依次插入HT中，然后删除关键字25,则HT中查找失败的平均查找长度( )。
A.l
B.l.6
C.l.8
D.2.2
参考答案：C
10、下列排序算法中，不稳定的是( )。
Ⅰ烯尔排序
Ⅱ 归并排序
Ⅲ 快速排序
Ⅳ 堆排序
V 基数排序
A 仅Ⅰ和Ⅱ
B 仅Ⅱ和V
C 仅 I,Ⅲ, IV
D. Ⅱ, TV, V
参考答案：C
11、使用快速排序算法对数据进行升序排序，若经过一次划分后得到的数据序列是68, 11,70,23,80,77,48,81,93,88, 则该次划分的轴枢( )。
A、11
B、70
C、80
D、81
参考答案：D
12、若机器M的主频为1.5hz ,在M上执行程序p的指令条数为5*10^5 , p的平均CPI为1.2,则p在M上的指令执行速度和用户CPU时间分别为( )。
A.0.8GIPS 、 0.4ms
B.0.8GIPS、0.4us
C.l.25GTPS 、 0.4ms
D. l.25GlPS、0.4us
参考答案：C
13、若short型变量x=-8190,则x的机器数为( )。
A. E002H
B. EOOlH
C. 9FFFH
D.9FFEH
参考答案：A
14、已知floal型变话用IEEE754单精度浮点数格式表示。若float型变量X的机器数为8020 000H，则x的值 ( )。
A. - 2^128
H. -1.01x2^-127
C. - 1.01x2^-126
D. 非数( NAN)
参考答案：A
15、某计算机的CPU有30根地址线 ，按字节编址，CPU和主存芯片连接时，要求主存芯片占满所有可能存储地址空间并且RAM区和ROM区所分配的容量大小比为3:1。若ROM在连续高地址区，则ROM的地址范围( )。
A. 0000000H ~ 0FFFFFFH
B. 10000000H ~ 2FFFFFH
C. 30000000H ~ 3FFFFFFH
D. 40000000H~4FFFFFFH
参考答案：C
16、已知x、y为int类型，当x=lOO, y=200时，执行x-y指令的到的溢出标志OF和借位标志CF分别为0,1, 那么当x=lO, y=-20时，执行该指令得到的OF和CF分别是( )
A. OF=O，CF=O
B. OF=O，CF=1
C. OF=1，CF=O
D. OF=l, CF=l
参考答案：B
17、某运算类型指令中有一个地址码为通用寄存器编号，对应通用寄存器中存放的是操作数或操作数地址，CPU区分两者的依据是( )。
A. 操作数的寻址方式
B 操作数的编码方式
D. 通用寄存器编号
D. 通用寄存器的内容
参考答案：A
18、数据迪路由逻辑元件和时序元件组成，。 以下是组合逻辑元件的是( )。
I 算术逻辑部件ALU
II 程序计数器PC
III 通用寄存器
IV 多路选择器MUX
A. I 、II
B. I、lV
C. II、III
ll.I、IV
参考答案：D
19、采用取指、解码，执行，存储，写入5段流水线，RISC处理器 ，SO, Sl, S2, S3, t2 为寄存器编号，
I1: add S2 Sl SO //[R[S2)] R(Sl)+R[SO)
I2 : add load(S3)0(S2) //[R[S2)) R(Sl)+R[SO)
I3 : beq t2 S3 L1 //if R[t2)==R[S3) jump to L1
I4: c1dd L2 L3 IO //[R[L2)] R(L2)+IO
如采用旁路技术处理数据相关，即采用专用数据通路技术处珅器， 则在 , 1~ 14执行过程中， 发生流水线阻塞的有( )。
A. 仅 I3
B. 仅 I2 和 I4
C. 仅 I2 和 I3
D. 仅I2，I3和 I4
参考答案：A [ 控制相关的流水线阻塞 ]
20、若有存储总线宽度为64位，总线时钟频率为1GHZ，在总线上传输一个数据支地址需要一个的时钟周期，不支持突发传送，若该总线连接CPU和主存，主存每次准备个64位数据斋6ns，主存块大小为32B，则读取一个主存块时间为( )。
A. 8ns
B. 11ns
C. 26ns
D. 32ns
参考答案：D
21、下列关于硬件和异常/中断关系的叙述中，错误的是( )。
A. CPU在执行一条指令过程中检测异常事件
H. CPU在执行完一条指令时检测中断请求信号
C. 开中断中CPU检测到中断请求后就进行中断响应
D. 外部设备通过中断控制器向CPU发中断结束信号
参考答案：D
22、下列关于I/0控制方式的叙述中错误的是( )。
A 程序全询方式通过CPU执行全询程序进行1/0操作
B.中断方式下，通过CPU执行中断服务程序进行I/0橾作
C.DMA方式下，通过CPU执行DMA传送和序进行I/0操作
0. 对千SSD、网络适配器等高速设备，采用DMA方式输入/输出
参考答案：C
23、与宏内核操作系统相比，下列特征中微内核操作系统具有的是( )。
I 较好的性能
II 较高的可靠性
III 较高的安全性
IV 较强的可扩展性
A. 仅 II 、IV
B. 仅I、II、IV
C. 仅I、III、IV
D. 仅II 、III、IV
参考答案：D
24、在操作系统内核中， 中断向量表适合采用的数据结构是( )。
A. 数组
B. 队列
C. 单向链表
D. 双向链表
参考答案：A
25、某系统采用页式存储管理，用位图管理空闲页框。若页大小为4kH, 物理内存大小为16GB, 则位图所占空间的大小是( )。
A. 128B
B. 128kB
C.512kB
D. 4MB
参考答案：C
26、下列操作完成时，导致CPU从内核态转为用户态的是( )。
A. 阻塞过程
B. 执行CPU调度
C. 唤醒进程
0. 执行系统调用
参考答案：D
27、下列出当前线程引起的事件或执行的抚作中， 可能导致该线程由执行形态变为就绪态的是( )。
A. 键盘输入
8. 缺页异常
C. 主动出让CPU
D. 执行信号量的wait（）操作
参考答案： C
28、对于采用虚拟内存管理方式的系统， 下列关于进程虚拟地址空间的叙述中，错误的是( )。
A. 每个进程都有白己独立的虚拟地址空间
B. C语言中malloc( )函数返回的足虚拟地址
C. 进程对数据段和代码段可以有不同的访问权限
ll. 虚拟地址的大小山主存和硬盘的大小决定
参考答案：D
29、进程Pl，P2和P3进入就绪队列的的时刻，优先值(越大优先权越高)以及CPU的执行时间如下表所示，
| 进程名 |
进入就绪队列的时刻 |
优先数 |
CPU的执行时间 |
| P1 |
Oms |
1 |
60ms |
| P2 |
20ms |
10 |
42ms |
| P3 |
30ms |
100 |
15ms |
系统采用基于优先权的抢占式CPU调度算法，从Oms时刻开始进行调度，则P1，P2，P3的平均周转时间为（）
A. 60ms
B. 61,ms
C. 70ms
D. 71ms
参考答案：B
30 、进程R和S共享数据data，若date在R和S中所在页的页号分别是P1和P2，两个页所对应的页框号分别为f1和f2，则下列叙述中正确的是（ ）
A. pl 和 p2 一定相等，f1和f2一定相等
B . pl 和 p2一定相等，f1和 f2不一定相等
C. pl和 p2 不一定相等，f1 和f2一定相等
D. pl和p2不一定相等，f1和f2不一定相等
参考答案：B
31、文件F仅有一个进程打开，当该进程关闭F时，必须的操作是( )。
A. 删除目录项
B 删除内存的文件目录
C. 删除外存的文件目录
D. 文件磁盘索引节点链接计数器减一
参考答案：B
32、设备分配问题
参考答案：全选
33.如图，2段链路的数据传输速率为100Mbps，时延带宽积( 即单向传播时延带宽)均为1000bit。若H1向H2发送1个大小为1MB的文件，分组长度为1000B,则从H1开始发送时刻起到H2收到文件全部数据时刻止，所需的时间至少是(注:M=10^5) ( )。
A.80.02ms
B.80.08ms
C.80.09ms
D.80.10ms
参考答案： D
34.某无噪声理想信道带宽为4MHz，采用QAM调制，若该信道的最大数据传输率是48Mbps，则该信道采用的QAM调制方案是( ) 。
A.QAM-16
B.QAM-32
C.QAM-64
D.QAM-128.
参考答案：C
35.假设通过同一信道，数据链路层分别采用停-等协议、GBN协议和SR协议(发送窗口和接收窗口相等)传输数据，三个协议数据帧长相同，忽略确认帧长度，帧序号位数为3比特。若对应三个协议的发送方最大信道利用率分别是U1、U2和U3，则U1、U2和U3满足的关系是( )。
A.U1<=U2<=U3
B.Ul<=U3<=U2
C.U2<=U3<=U1
D.U3<=U2<=U1
参考答案：B
36.已知10BaseT以太网的争用时间片为51.2us。若网卡在发送某帧时发生了连续4次冲突，则基于二进制指数退避算法确定的再次尝试重发该帧前等待的最长时间是( )
A.51.2us
B.204.8us
C.768us
D.819.2us
参考答案：C
37.若甲向乙发送数据时采用CRC校验，生成多项式为G(x)=x^4+x+1(即G=10011)，则乙接收到下列比特串时，可以断定共在传输过程中未发生错误的是( )。
A.101110000
B.101110100
C.101111000
D.101111100
参考答案： D
38.某网络拓扑如下图所示，其中路由器R2实现NAT功能。若主机H向Inernet发送一一个IP分组，则经过R2转发后，该IP分组的源IP地址是( ) 。
参考答案： 选NAT源地址33
39.主机168.16.84.24/20所在子网的最小可分配地址和最大可分配地址分别是( )。
A.168.16.80.1，168. 16.84.254
B.168.16.80.1，168. 16.95.254
C.168.16.84.1，168.16.84.254
D.168.16.84.1，168. 16.95.254
参考答案：B
40.下列关于ipv6和ipv4的叙述中，正确的是?
I ipv6地址空间是ipv4地址空间的96倍
II ipv4和ipv6的基本首部的长度均可变
III ipv4向ipv6 过渡可以采用双协议栈和隧道技术
IV ipv6首部的Hop-Limit等价于ipv4 首部的TTL字段
A仅I、II
B仅I、IV
C仅II、III
D仅III、IV
参考答案： D
二、综合应用题：41 ~47小题，共70分。
41. [13分]已知优先图G采用邻接矩阵存储是，其定义如下
Typedef struct{
Int numberVertices,numEgges;
Char VerticesList[maxV];
Int edge[maxV][maxV];
}MGraph;
将图中出度大于入度的顶点成为K顶点，如图，a和b都是k顶点
设计算法int printVertices(MGraph G)对给定任意非空有向图G,输出G中所有K顶点的算法，并返回K顶点的个数。
(1)给出算法的设计思想。
(2)根据算法思想，写出C/C++描述，并注释。
42. [ 10分 ]
对含有n (n>0)个记录的文件进行外部排序，采用置换-选择排序生成初始归并段时需要使用一个工作，工作区中能保存m个记录，请回答下列问题，
(1) 19记录51，94，37, 92，14，63，15，99，48，56，23，60， 31，17,
42，8，90，166， 100。 m>=4时，可生成几个初试归并段，各是什么？
(2)对任意m (n>>m>0)生成的第一个初试归并段长度max,min分别是？
43. [ 14分 ]
VA32bit，页4KB，请求调页
Cache4路组相联，块32B，数据区8KB
Int a[24][64],a*=0042 2000H，行优先存储
初始a不在内存，不会发生置换，按行访问a[ ] [ ]
for(i; 0-23)
for(j: 0-63)
a[i][]=10
(1) a分在在几个页面中?访问问a缺页几次 ? 页故障地址各是什么 ?
(2)不考虑i，j，是否有时间局部性 ?为什么 ?
(3) VA32bit中，块内地址哪几位? Cache组号? a[1][0]的VA是?对应Cache的组号是?
(4) a多少块 ? 访问aCache命中率是 ? 若i<->j对换，命中率是 ?
44. [9分]
题43中C程序段在计算机m上的部分,机器级代码如下，每个机器级代码行
中依次包含指令序号，虚拟地址，机器指令和汇编指令。
for(i=0;i<24;i++)
100401072 C7 45 F8 00 0000 00 mov[ebp-8],0
2 00401079 EB 09
jmp 00401084h
3 0040107B 8B 55 F8
mov eax[ebp-8]
700401088 7D 32
jge 004010bch
for(ji=0j<64j++)
8 0040108A C7 45 FC 00 00 00 00 mov[ebp-4],0
a[间[j]=10;
mov[ecx+ edx*4+ 00422000h],.oAh
==
....
19004010AEC78482002042000A000000
(1)第20条指令的虚拟地址是多少？
(2)已知第2条jmp和第7条jge都是跳转指令，其操作码分别是EBH和7DH，跳转地址分别为0040 1084、0040 10BCA这两条指令都采用什么寻址方式？给出第2条指令jmp的跳转目标地址计算过程。
(3)已知第19条mov指令的功能是“a[i][j]<-10"，其中ccx和edx为寄存器名，0042 20001是数组a的首地址，指令中源操作数采用什么寻址方式？已知edx中存放的是变量j，ecx 中存放的是？根据该指令的机器码判断计算机m采用的是大端还是小端方式。.
(4)第1次执行第19条指令时，取指令过程中是否会发生缺页异常？为什么？
45.[7分]现要求学生使用swap指令和布尔型变量lock, 实现临界区互斥。lock为线程间共存的变量。lock 的值为true时线程不能进入临界区。为false时线程能进入临界区。某同学编写的实现临界区互斥的伪代码如题45 (a) 所示
| 某同学写的伪代码 |
newswap( )的代码 |
|
bool lock=FALSE;//共享变量
//进入区
bool key=TRUE
if(key)=TRUE
swap key,lock;//交换key和lock的值
/临界区
lock =TRUE推出区 |
void n ewswap(bool*a,bool*b)
{
bool temp=*a;
*a=*b
*b=temp
} |
题45(a)图 题45(b)图
(1)题45 (a) 图中伪代码中哪些语句存在错误，进行改正，不增加语句条数。
(2)题45 (b)图中给出了两个变量值的函数newswap ()的代码是否可以用
函数调用语句“newswap(&key,&lock)”代替指令“swapkey,lock"以实现临界区的互斥？为什么？
46. [8 分] P系统调用getchar (键盘)
①P插入
②P阻塞
③字符从控制器->系统缓存
④启动中断处理程序
⑤P系统调用返回
⑥用户键盘输入字符
(1)①的前后?⑥的后
(2)几一-定CPU从P切换其他进程？几之后调度P？
(3)几是键盘驱动程序
(4) 中断时，P什么态？ CPU内核态还是用户态？
47. [9 分]如图，主机H登录FTP服务器后白服务器上估一个大小为18000B的文件F，假设H传输F建立数连接时，选择的初始序号为100，MTU=1000B，
拥塞控制初始阅值为4MSS，RTT=10ms, 忽略TCP的传输时延，在F的传过程中，H以MSS段向服务器发送数据，且未发生差错，去包和乱序。
(1) FTP的控制连接是持久的还是非持久的？FTP的数连接是持久的还是非持久的 ? H登录FTP服务器时，建立的TCP连接是控制连接还是数据连接？
(2) H通过数据连接发送F时，F的第一个字节序号是多少 ? 在断开数据连接的过程中，FTP发达的第二次挥手的ACK序号是 ？
(3) F发送过程中，当H收到确认序号为2101的确认时，H的拥塞调整为多少？收到确认序号为7101的确认段时，H的拥窗口调整为多少
(4) H从请求建立数据连接开始，到确认F已被服务全部接收为止，至少要多长时间？期间应用层数平均发送速率是多少？
