2024年4月27日发(作者：)

一、单项选择题

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

复杂度为O(1)的是（ ）。

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

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

C、删除第i(1≤i≤n)个元素的算法

D、获取第i(1≤i≤n)个值的算法

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

指向直接前驱结点的指针，next是指向直接后继结点的指针。若要在L中指针p

所指向的结点（非尾结点）之后插入指针s指向的新结点，则在执行了语句序列：

“s->next=p->next;p->next=s;”，后，还要执行（ ）。

A、s->next->prev=p;s->prev=p;

B、p->next->prev=s;s->prev=p;

C、s->prev=s->next->prev; s->next->prev=s;

D、p->next->prev=s->prev;s->next->prev=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

注：

每个关键字的查找长度为：

图片

加权平均长度为 ：

(3×3+3×4+3×5+3×6+2×8+2×10)/(3+4+5+6+8+10)=2.5。

如果不考虑权重，会错误计算为

(3+3+3+3+2+2)/6≈2.67，从而误选C。

5、已知一棵二叉树的树形如下图所示，若其后序遍历为fdbeca，则其先序

列为（ ）。

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

注：无向连通图 G 中各边的权值均为 1 ，G 可以视为无权图，可用广度优

先搜索求单源最短路径，在求无权图的单源最短路径问题中，广度优先搜索比

Dijkstra算法更加高效。III正确。I 和 II 是最小生成树算法，也可直接排

除。

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

I.插入操作可能增加树的高度；II.删除操作一定会导致叶结点的变化；III.

查找某关键字一定是要查找到叶结点；IV.插入的新关键字最终位于叶结点中。

A、仅I

B、仅I、II

C、仅III、IV

D、仅I、II、IV

解答：I. 插入操作可能会导致关键字上溢，关键字上溢到根结点，树的高

度加一。I 正确。

II. 如果删除的关键字位于叶结点，则该B树叶结点一定发生变化。如果删

除的关键字位于非叶结点，叶结点也会发生变化。II 正确。

III. B树中所有结点均可以存储关键字，若查找的关键字位于非叶结点，

则不需要查找到叶结点。III错误。

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

注：经过上述操作后，散列表为：

如果查找的关键字散列函数值为0，查找1次失败。

如果是1，查找3次才能判断失败。

如果是2，查找2次才能判断失败。

如果是3，查找1次才能判断失败。

如果是4，查找2次才能判断失败。

所以，失败的平均查找长度为：(1+3+2+1+2)/5 = 1.8

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

I. 希尔排序；II. 归并排序；III. 快速排序；IV. 堆排序；V. 基数排序

A. 仅 I 和 II

B. 仅 II 和 V

C. 仅 I、III 和 IV

D. 仅 III 、 IV 和 V

注：稳定的排序有：插入排序、冒泡排序、归并排序、基数排序。

不稳定的排序有：选择排序、希尔排序、快速排序、堆排序。

11. 使用快速排序算法对数据进行升序排序， 若经过一次划分后得到的数

据序列是 68, 11, 70, 23, 80, 77, 48, 81, 93, 88，则该次划分的轴枢是

（ ）。

A. 11

B. 70

C. 80

D. 81

23. 与宏内核操作系统相比，下列特征中微内核操作系统具有的是（ ）。

Ⅰ. 较好的性能；Ⅱ. 较高的可靠性；Ⅲ. 较高的安全性；Ⅳ. 较强的可扩

展性

A. Ⅱ、Ⅳ

B. Ⅰ、Ⅱ、Ⅲ

C. Ⅰ、Ⅲ、Ⅳ

D. Ⅱ、Ⅲ、Ⅳ

24. 在操作系统内核中，中断向量表适合采用的数据结构是（ ）。

A. 数组

B. 队列

C. 单向链表

D. 双向链表

25. 某系统采用页式存储管理，用位图管理空闲页框。若页大小为4 KB，

物理内存大小为16GB，则位图所占空间的大小是（ ）。

A. 128 B

B. 128 KB

C. 512 KB

D. 4 MB

注：16GB/4KB = 4M。

4Mbit/8 = 512KB.

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

A. 阻塞过程

B. 执行 CPU 调度

C. 唤醒进程

D. 执行系统调用

注：A错误。阻塞过程完成时，会去调用进程调度程序。

B错误。执行CPU调度完成时，要进行上下文切换。

C错误。唤醒进程后有可能引起进程调度。

D正确。系统调用执行完后回到用户态执行。

27. 下列由当前线程引起的事件或执行的操作中，可能导致该线程由执行态

变为就绪态的是（ ）。

A. 键盘输入

B. 缺页异常

C. 主动出让CPU

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

28. 对于采用虚拟内存管理方式的系统，下列关于进程虚拟地址空间的叙述

中，错误的是（ ）。

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

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

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

D. 虚拟地址的大小由主存和硬盘的大小决定

注：C语言中malloc()函数用于动态内存分配，返回的是一个指向分配内存

的虚拟地址。