2023年408计算机学科专业基础真题

一、单项选择题：1-40小题，每小题2分，共80分。下列每题给出的四个选项中，只有一个选项是符合题目要求的。

1、下列对顺序存储的有序表（长度为n）实现给定操作的算法中平均时间复杂度为O（1）的是（  ）。

A.查找包含指定值元素的值

B.插入包含指定值元素的算法

C.删除第i个元素的算法

D.获取第i个值的算法

2、现有非空双向链表L，其结点结构为

prer是指向直接前驱结点的指针，next是指向直接后继结点的指针。若要在L中指针p所指向的结点（非尾结点）之后插入指针s指向的新结点，则在执行了语句序列：“s->next=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;

3、若采用三元组表存储结构存储稀疏矩阵M，则除三元组外，下列数据中还需要保存的是（  ）。

I.M的行数

II.M中包含非零元素的行数

III.M的列数

IV.M中包含非零元素的列数

A.仅I、III

B.仅I、II

C.仅III、IV

D.I、II、III、IV

4、在有6个字符组成的字符集S中，各个字符出现的频次分别为3，4，5，6，8，10，为S构造的哈夫曼树的加权平均长度为（  ）。

A.2.4

B.2.5

C.2.67

D.2.75

5、已知一棵二叉树的树形如图，若其后序遍历为f，d，b，e，c，a，则其先序列为（  ）。

A.aedfbc

B.acebdf

C.cabefd

D.dfebac

6、已知无向连通图G中各边的权值均为1，下列算法中一定能够求出图G中从某顶点到其余各个顶点最短路径的是（  ）。

I.普利姆算法

II.克鲁斯卡尔算法

III.图的广度优先搜索

A.仅III

B.仅I、II

C.仅I、III

D.I、II、III

7、下列关于非空B树的叙述中，正确的是（  ）。

I.插入操作可能增加树的高度

II.删除操作一定会导致叶结点的变化

III.查找某关键字一定是要查找到叶结点

IV.插入的新关键字最终位于叶结点中

A.仅I

B.仅I、II

C.仅III、IV

D.仅I、II、IV

8、对含有600个元素的有序顺序表进行折半查找，关键字之间的比较次数最多是（  ）。

A.9

B.10

C.30

D.300

9、现有长度为5，初始为空的散列表HT，散列表函数H（K）=（k+4）%5，用线性探查再散列法解决冲突。若将关键字序列2022，12，25依次插入HT中，然后删除关键字25，则HT中查找失败的平均查找长度（  ）。

A.1

B.1.6

C.1.8

D.2.2

10、下列排序算法中，不稳定的是（  ）。

I.希尔排序

II.归并排序

III.快速排序

IV.堆排序

V.基数排序

A.仅I和II

B.仅II和V

C.仅I，III，IV

D.II，IV，V

11、使用快速排序算法对数据进行升序排序，若经过一次划分后得到的数据序列是68，11，70，23，80，77，48，81，93，88，则该次划分的轴枢（  ）。

A.11

B.70

C.80

D.81

12、运算型指令中有一个地址码是通用存储器编号，其对应的通用寄存器中存放的是操作数或操作数地址，CPU区分他们的依据是（  ）。

A.操作数的寻址方式

B.操作数的编码方式

C.通用寄存器编号

D.通用寄存器的内容

13、若short型变量x=-8190，则x的机器数为（  ）。

A.E002H

B.E001H

C.9FFFH

D.9FFEH

14、已知float型变量用IEEE754单精度浮点数格式表示。若float型变量x的机器数为8020000H，则x的值（  ）。

A.-2-128

B.-1.01×2-127

C. -1.01×2-128

D.非数NaN

15、某计算机的CPU有30根地址线，按字节编址，CPU和主存芯片连接时，要求主存芯片占满所有可能存储地址空间，并且RAM区和ROM区所分配的容量大小比为3：1，若RAM在连续低地址区，ROM在连续高地址区，则ROM的地址范围（  ）。

A.0000 0000H~0FFF FFFFH

B.1000 0000H~2FFF FFFFH

C.3000 0000H~3FFF FFFFH

D.4000 0000H~4FFF FFFFH

16、若机器M的主频为1.5GHz，在M上执行程序p的指令条数为5×105，p的平均CPI为1.2，则p在M上的指令执行速度和用户CPU时间分别为（  ）。

A.0.8GIPS、0.4ms

B.0.8GIPS、0.4μs

C.1.25GIPS、0.4ms

D.1.25GIPS、0.4μs

17、已知x、y为int类型，当x=100，y=200时，执行x-y指令的溢出标志OF和借位标志CF分别为0，1，那么当x=10，y=-20时，执行该指令得到的OF和CF分别是（  ）。

A.OF=0，CF=0

B.OF=0，CF=1

C.OF=1，CF=0

D.OF=1，CF=1

18、元件分为两类，组合逻辑元件（也称操作元件）和时序逻辑元件（也称状态元件）。以下是组合逻辑元件的是（  ）。

Ⅰ.算术逻辑部件

Ⅱ.程序计数器

Ⅲ.通用寄存器组

Ⅳ.多路选择题

A.仅Ⅰ、Ⅱ

B.仅Ⅱ、Ⅳ

C.仅Ⅱ、Ⅲ

D.仅Ⅰ、Ⅳ

19、采用取指、解码、执行、存储、写入5段流水线，RISC处理器，S0，S1，S2，S3，t2为寄存器编号，

I1: add S2 S1 S0 //[R[S2]]= R[S1]+R[S0]

I2: add load(S3)0(S2) //[R[S3]] =R[S1]+R[S2]

I3: beq t2 S3 L1 //if R[t2]==R[S3] jump to L1

I4: add t2 S3 10 //[R[t2]] = R[S3]+10

如采用旁路技术处理数据相关，即采用专用数据通路技术处理器，则在I1~I4执行过程中，发生流水线阻塞的有（  ）。

A.仅I3

B.仅I2和I4

C.仅I2和I3

D.仅I3和I4

20、若有存储总线宽度为64位，总线时钟频率为1GHZ，在总线上传输一个数据的地址需要一个的时钟周期，不支持突发传送，若该总线连接CPU和主存，主存每次准备一个64位数据需要6ns，主存块大小为32B，则读取一个主存块时间为（  ）。

A.8ns

B.11ns

C.26ns

D.32ns

21、下列关于硬件和异常/中断关系的叙述中，错误的是（  ）。

A.指令执行过程中会检测是否有异常

B.指令执行结束会检测是否有中断

C.开中断时CPU检测到中断请求后就进行中断响应

D.由中断控制器向CPU报告中断结束

22、以下关于IO控制方法的说法错误的是（  ）。

A.程序查询方式是由CPU控制查询

B.中断方式是由CPU控制中断

C.DMA方式中CPU执行DMA程序控制数据传输

D.DMA方式常用于SSD和网络适配器

23、与宏内核操作系统相比，下列特征中微内核操作系统的优点是（  ）？

I.较好的性能

II.较高的可靠性

III.较高的安全性

IV.较强的可扩展性

A.仅II、IV

B.仅I、II、IV

C.仅I、III、IV

D.仅II、III、IV

24、中断向量表适合采用什么数据结构（  ）？

A.数组

B.队列

C.单向链表

D.双向链表

25、某系统采页式存储管理，用位图管理空闲页框。若页大小为4KB，物理内存大小为16GB，则位图所占空间大小是（  ）？

A.128B

B.128KB

C.512KB

D.4MB

26、下列操作完成时，导致CPU从内核态转为用户态的是（  ）？

A.阻塞进程

B.执行CPU调度

C.唤醒进程

D.执行系统调用

27、下列由当前线程引起的事件或执行的操作中，可能导致该线程由执行态变为就绪态的是（  ）？

A.键盘输入

B.缺页异常

C.主动出让CPU

D.执行信号量的wait()操作

28、进程P1，P2和P3进入就绪队列的时刻，优先值（越大优先权越高）以及CPU的执行时间如下表所示：

系统采用基于优先权的抢占式CPU调度算法，从0ms时刻开始进行调度，则P1，P2，P3的平均周转时间为（  ）？

A.60ms

B.61ms

C.80ms

D.81ms

29、进程R和S共享数据data，若date在R和S中所在页的页号分别为p1和p2，两个页所对应的页框号分别为f1和f2，则下列叙述中正确的是（  ）。

A.p1和p2不一定相同，f1和f2不一定相同  

B.p1和p2一定相同，f1和f2不一定相同  

C.p1和p2不一定相同，f1和f2一定相同  

D.p1和p2一定相同，f1和f2一定相同

30、文件F仅有一个进程打开，当该进程关团时，必须的操作是（  ）。

A.删除目录项  

B.删除内存的文件索引结点  

C.删除外存的文件索引结点  

D.文件磁盘索引节点链接计数器减一

31、对于采用虚拟内存管理方式的系统，下列关于进程虚拟地址空间的叙述中错误的是（  ）？

A.每个进程有自己独立的虚拟地址空间  

B.C语言中malloc()函数返回的是虚拟地址  

C.进程的数据段和代码段可以有不同的访问权限  

D.进程的虚拟地址空间由内存和外存的容量决定 

32、设备分配需要关注的是（  ）？

I.设备类型
II.设备使用状态

III.逻辑设备和物理设备的映射

IV.进程对设备的访问权限

A.I和II

B.I和III

C.I、III和IV

D.I、II、III和IV

33、如图，2段链路的数据传输速率为100Mbps，时延带宽积(即单向传播时延*带宽）均为1000bit。若H1向H2发送1个大小为1MB 的文件，分组长度为 1000B，则从H1开始发送时刻起到H2收到文件全部数据时刻止，所需的时间至少是(注:M=10⁶)?

A.80.02ms

B.80.08ms

C.80.09ms

D.80.10ms

34、某无噪声理想信道带宽为4MHz，采用QAM调制，若该信道的最大数据传输率是48Mbps，则该信道采用的QAM调制方案是（  ）。

A.QAM-16

B.QAM-32

C.QAM-64

D.QAM-128

35、假设通过同一信道，数据链路层分别采用停-等协议、GBN 协议和 SR 协议(发送窗口和接收窗口相等）传输数据，三个协议数据帧长相同，忽略确认帧长度，帧序号位数为3比特。若对应三个协议的发送方最大信道利用率分别是U1、U2 和 U3，则 U1、U2 和 U3 满足的关系是（  ）。

A.U1≤U2<U3

B.U1<U3<U2

C.U2≤U3<U1

D.U3<U2<U

36、已知10BaseT以太网的争用时间片为51.2μs。若网卡在发送某帧时发生了连续4次冲突，则基于二进制指数退避算法确定的再次尝试重发该帧前等待的最长时间是（ ）。

A.51.2μs

B.204.8μs

C.768μs

D.819.2μs

37、若甲向乙发送数据时采用CRC校验，生成多项式为G(x)=x4+x+1（即G=10011），则乙接收到下列比特串时，可以断定其在传输过程中未发生错误的是（  ）。

A.101110000

B.101110100

C.101111000

D.101111100

38、某网络拓扑如下图所示，其中路由器R2实现NAT功能。若主机H向Internet发送一个IP分组，则经过R2转发后，该IP分组的源IP地址是（  ）。

A.192.168.0.33

B.192.168.0.35

C.192.168.0.1

D.192.168.0.3

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

40、下列关于ipv6和ipv4的叙述中，正确的是（  ）。

I.ipv6地址空间是ipv4地址空间的96倍

II.ipv4和ipv6的基本首部的长度均可变

III.ipv4向ipv6过渡可以采用双协议栈和隧道技术

IV.ipv6首部的Hop-Limit等价于ipv4首部的TTL字段

A.仅I、Ⅱ

B.仅I、IV

C.仅Ⅱ、Ⅲ

D.仅Ⅲ、IV

二、综合应用题：41~47小题，共70分。

41、（13分）对于有向图，如果一个顶点的出度大于入度，则这个顶点称为K顶点。有向图用邻接矩阵存储，数据结构定义如下：

Typedef struct{//图的定义

int numVertices，numEdges;//图中实际的顶点数和边数

char VerticesList[MAXV];//顶点表，MAXV为已定义常量

int Edge[MAXV][MAXV];//邻接矩阵

}MGraph;

设计算法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），生成的第一个初始归并段最大可能长度，最小可能长度分别是？

43、(14分) 某机器字长为32位的计算机M，采用请求调页存储管理。虚拟地址32位，页面大小4KB。Cache采用4路组相联映射，内存块大小为32B，Cache数据区大小为8KB。 二维数组int a[24][64]按行优先存储，数组的起始虚拟地址为0042 2000H。数组a的数据初始时未调入内存，按如下方式访问数组a：

for(int i=0;i<24;i++)

for(int j=0;j<64;j++)

a[i][j]=10;

（1）数组a分为几个页面存储？访问数组a缺页几次？页故障地址各是什么？

（2）考虑对变量i，j的访问，访问数组a的过程是否具有时间局部性？为什么？

（3）在计算机M的32位地址中，块内地址是哪几位？Cache组号是哪几位？数组元素a[1][0]的虚拟地址是什么？对应的Cache组号是什么？

（4）数组a总共占多少块？访问a的Cache命中率是多少？若采用如下方式访问数组a，则命中率又是多少？

for(int j=0;j<64;j++)

    for(int i=0;i<24;i++)

a[i][j]=10;

44、（9分）题43中C程序段在计算机M上的部分机器级代码如下，每个机器级代码行中依次包含指令序号，虚拟地址，机器指令和汇编指令，请回答问题。

（1）第20条指令的虚拟地址是多少？

（2）已知第2条jmp和第7条jge都是跳转指令，其操作码分别是EBH和7DH，跳转地址分别为0040 1084、0040 10BC，这两条指令都采用什么寻址方式？给出第2条指令jmp的跳转目标地址计算过程。

（3）已知第19条mov指令的功能是“a[i][j]←10”，其中ecx和edx为寄存器名，00422000H是数组a 的首地址，指令中源操作数采用什么寻址方式？己知edx中存放的是变量j，ecx 中存放的是？根据该指令的机器码判断计算机M采用的是大端还是小端方式。

（4）第1次执行第19条指令时，取指令过程中是否会发生缺页异常？为什么？

45、（7分）现要求学生使用swap指令和布尔型变量lock，实现临界区互斥。lock为线程间共存的变量。lock的值为true时线程不能进入临界区，为false时线程能进入临界区。某同学编写的实现临界区互斥的伪代码如下所示：

（1）请修改代码，正确实现互斥（不增加语句条数）。

（2）请问是否可以用函数newSwap (&a, &b) 代替swap指令以实现临界区的互斥？为什么？

46、（8分）进程P通过系统调用请求从键盘读入一个字符。题目乱序给出6个处理步骤：

① 将进程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已被服务器全部接收为止，至少需要多长时间，期间应用层数据平均发送速率是多少？