当前位置：问答库＞考研试题

一、填空题

1． 在双向循环链表中，向P 所指的结点之后插入指针f 所指的结点，其操作是_____、_____、_____、_____。

【答案】

2． 对单链表中元素按插入方法排序的C 语言描述算法如下，其中L 为链表头结点指针。请填充算法中标出的空白处，完成其功能。

【答案】（1）（2）（3）（4）（5）

置空链表，然后将原链表结点逐个插入到有序表中

当链表尚未到尾，p 为工作指针

查P 结点在链表中的插入位置，这时q 是工作指针

将P 结点链入链表中

是q 的前驱，u 是下个待插入结点的指针

3． N 个顶点的连通图用邻接矩阵表示时，该矩阵至少有_____个非零元素。

【答案】2（N-1）

【解析】所谓连通图一定指的是无向图，有向图会称作强连通图。连接N 个顶点，至少需要N-1条边就可 以了。由于无向图的每一条边同时关联了两个顶点。因此用邻接矩阵表示时，该矩阵至少有2（N-1）个非零元素。

4． 属于不稳定排序的有_____。

【答案】希尔排序、简单选择排序、快速排序、堆排序等

5． 若用n 表示图中顶点数目，则有_____条边的无向图成为完全图。

【答案】n （n-l ）/2

【解析】无向完全图中任意一个顶点都和其他n-1个顶点都有一条边，即为n （n-l ）。又因为每条边重复出现两次，所有无向完全图的边数为n （n-l ）/2。 6． 分别采用堆排序，快速排序，起泡排序和归并排序，对初态为有序的表，则最省时间的是_____算法，最费时间的是_____算法。

【答案】起泡；快速

，【解析】当初态为有序表时，冒泡排序只需要进行一趟比较即可，此时时间复杂度为〇（n ）而快速排序算法需要比较的次数达到最大，时间复杂度为

7． 组成串的数据元素只能是_____。

【答案】字符

8． 克鲁斯卡尔算法的时间复杂度为_____，它对_____图较为适合。

【答案】O （eloge ）; 边稀疏

9． 二叉树由_____，_____，_____三个基本单元组成。

【答案】根结点；左子树；右子树

10．—棵左子树为空的二叉树在前序线索化后，其中的空链域的个数为 _____。

【答案】2

【解析】只有根结点的做指针为空和最右边的叶结点的右指针为空。

二、选择题

11．下列排序算法中，占用辅助空间最多的是（ ）。

A. 归并排序 B. 快速排序 C. 希尔排序 D. 堆排序 【答案】A

【解析】

归并排序的辅助空间为

快速排序所占用的辅助空间为

堆排序所占

用的辅助空间为

12． 在子网192.168.4.0/30中，能接收目的地址为192.168.4.3的IP 分组的最大主机数是（ ）。

A.0 B.1 C.2 D.4

【答案】C

【解析】每个子网中忽略子网内全为0和全为1的地址剩下的就是有效主机地址，本题中由

于子网的比特数是30, 因此用于主机的只有2位，即00, 01, 10, 11，有效主机地址是2个，这里192.168.4.3显然是其广播地址，因此答案是C 。

13．主机甲与主机乙之间使用后退N 帧协议（GBN ）传输数据，甲的发送窗口尺寸为1000, 数据帧长为1000字节，信道宽带为100Mbps ，乙每收到一个数据帧立即利用一个短帧（忽略其传输延迟）进行确认，若甲乙之间 的单向传播延迟是50ms ，则甲可以达到的最大平均数据传输速率约为（ ）

A .10 Mbps B. 20 Mbps C.80 Mbps D.100 Mbps 【答案】C

【解析】

14．某系统有n 台互斥使用的同类设备，3个并发进程需要3, 4, 5台设备，可确保系统不发生死锁的设备数n 最小为（ ）

A.9 B.10 C.11 D.12

【答案】B

【解析】2+3+4+1 = 10

15．下列选项中，在用户态执行的是（ ）。

A. 命令解释程序 B. 缺页处理程序 C. 进程调度程序 D. 时钟中断处理程序 【答案】A

【解析】题目是问用户态执行，可见是有关操作系统基本概念的问题。四个选项中，用户唯一能面对的是命令解释程序，缺页处理程序和时钟中断都属于中断，在核心态执行，而进城调度属于系统调用在核心态执行。只有命令解释程序属于命令接口，可以运行在用户态，接受用户的命令操作控制。

16．若某通信链路的数据传输速率为

A.600波特 B.1200波特 C.4800波特 D.9600波特

采用4相位调制，则该链路的波特率是（ ）。