当前位置：问答库＞考研信息

一、选择题

1． 输入序列为ABC ，可以变为CBA 时，经过的栈操作为（ ）。

【答案】B

【解析】根据输入序列和输出序列可知，输入序列全部进栈，然后再出栈。从中可以看出，push 的数目始终大于等于pop 的数目。

2． 主机甲通过1个路由器个路由器（存储转发方式）与主机乙互联，两段链路的数据传输速率均为10Mbps ，主机甲分别采用报文交换和组大小为10kb 的分组交换向主机乙发送1

个大小为

的报文。若忽略链路传播延迟、分组头开销和拆装时间，则两种交换方式完成该

报文传输所需的总时间分别为（ ）

A.800ms> 1600ms B.801ms 、1600ms

C.1600ms 、800ms D.1600ms 、801ms 【答案】D

【解析】不进行分组时，发送一个报文的时延是

的时延也是800ms 共计1600ms 。进行分组后发送一个报文的时延是总时间为801 ms。

3． 对如下所示的有向图进行拓扑排序，得到的拓扑序列可能是（ ）

A. B. C. D.

在接收端接收此报文件

接收一个报

文的时延也是1ms ，但是在发送第二个报文时，第一个报文已经开始接收。共计有800个分组，

【答案】D

【解析】拓扑排序方法如下：

（1）从有向图中选择一个没有前驱（即入度为0）的顶点并且输出它； （2）从图中删去该顶点，并且删去从该顶点发出的全部有向边； （3）重复上述两步，直到剩余的网中不再存在没有前趋的顶点为止。

对于此有向图进行拓扑排序所有序列为：和所以选D

4． 主机甲与乙之间已建立一个TCP 连接，双方持续有数据传输，且无差错与丢失。若甲收到1个来自乙的TCP 段，该段的序号为1913、确认序号为2046、有效载荷为100字节，则甲立即发送给乙的TCP 段的序号和确认分别是（ ）

A.2046、 2012 B.2046、 2013 C.2047、 2012 D.2047、 2012 【答案】B

【解析】若甲收到1个来自乙的TCP 段，该段的序号seq=1913、确认序号ack=2046、有效载荷为100字节，则甲立即发送给乙的TCP 段的序号seql=ack=2046和确认序号ackl =seq+100=2013, 答案为B 。

5． 假设某系统总线在一个总线周期中并行传输4字节信息，一个总线周期占用2个时钟周期，总线时钟频率为10MHz , 则总线带宽是（ ）。

A.lOMB/s B.20MB/S C.40MB/S D.80MB/S 【答案】B

【解析】因为一个总线周期占用2个时钟周期，完成一个32位数据的传送。总线时钟频率为10MHz , 时钟周期为0.1押，总线周期占用2个时钟周期，为0.2两。一个总线周期中并行传输4=20MB/s。 字节信息, 则总线带宽是4B ÷

6． 当系统发生抖动（thrashing ）时，可以采取的有效措施是（ ）。

I. 撤销部分进程

II. 增加磁盘交换区的容量 III. 提高用户进程的优先级 A. 仅I B. 仅 II C. 仅III D. 仅 I 、II 【答案】A

【解析】“抖动”现象是指刚刚被换出的页很快又要被访问，为此，又要换出其他页，而该页

必须换入，又很快被访问，如此频繁地置换页面，以致操作系统的大部分时间都花在页面置换上，引起系统性能下降甚至崩溃。 引起系统抖动现象的原因是对换的信息量过大，内存容量不足，置换算法选择不当。所以解决的办法就是降低交 换页面数量，加大内存容量，改变置换选择算法。但是降低交换页面数量和改变置换选择算法对于一个应用系统 来讲是不可能的，只能增加内存容量。増加内存容量可以是直接添加物理内存（大型计算机都可以在不关机的情 况下增加物理内存，或者，降低进程数量，相对地增加内存。而増加交换区容量并不能解决物理内存不足的 问条）

题，提高用户进程的优先级会使系统的状态更加恶化。

7． 下列关于图的叙述中，正确的是（ ）。

I. 回路是简单路径

II. 存储稀疏图，用邻接矩阵比邻接表更省空间 III. 若有向图中存在拓扑序列，则该图不存在回路 A. 仅 II B. 仅 I 、II C. 仅III D. 仅 I 、III 【答案】C

【解析】第一个顶点和最后一个顶点相同的路径称为回路；序列中顶点不重复出现的路径称为简单路径；回路显然不是简单路径，所以选项I 错误。稀疏图用邻接表表示比邻接矩阵节省存储空间，稠密图适合用邻接矩阵的存储表示，所以选项II 错误。利用拓扑排序算法可以判断图中是否存在回路，即在拓扑排序输出结束后所余下的顶点都有前驱，则说明了只得到了部分顶点的拓扑有序序列，图中存在回路。所以选项III 正确。

8． 分别以下列序列构造二叉排序树，与用其他三个序列所构造的结果不同的是（ ）。

【答案】C

【解析】二叉排序树：左右子树都是二叉排序树，且保证右子树都比根结点大，左子树都比根结点小。据以上两点建立二叉排序树。

9． 图的BFS 生成树的树高比DFS 生成树的树高（ ）。

A. 小或相等 B. 小 C. 大或相等 D. 大 【答案】A

【解析】BFS 称作广度优先搜索，DFS 称作深度优先搜索。广度优先搜索类似与二叉树的层序遍历算法，深度优先搜索类似于树的先序遍历。因为深度优先搜索算法遵循的策略是尽可能的“深”地搜索一个图。所以图的BFS 生成树的树高比DFS 生成树的树高小或者相等。

10．下面关于串的叙述中，不正确的是（ ）。

A. 串是字符的有限序列 B. 空串是由空格构成的串 C. 模式匹配是串的一种重要运算

D. 串既可以采用顺序存储，也可以采用链式存储 【答案】B

【解析】

空格构成的串称空格串。空串用表示。零个字符的串称为空串，空格也是一个字符，因此B 项不正确。

二、填空题

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

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

12．以下是用类C 语言写山的算法，该算法将以二叉链表存储的二叉树中的叶结点按从左到右的顺序链成一个带头结点的双向循环链表，链接时，结点的Lchild 域作为前链域，指向结点的直接前驱，结点的Rchild 域作为后链域，指向结点的直接后继。算法中，使用一个顺序栈stack , 栈顶head 为双向循坏链表的头指针。 指针为top , P , t 为辅助指针，试填充算法中的空格，使算法完整。

void leafchain（BiTree Abt）

{p={BiTree）malloc （sizeof （BiTNode ））; If （!p ）{print£（“OVERFLOWn”; exit （1）; }

head=p; top=0; if （bt ）

{top++; stack[top]=bt; while （top ）

{t=stack[top]; top--;

if （it->Lchild && !t->Rchild）{ （1） ; （2） ; （3） ; } else {if（ （4） ）{top++; stack[top]= （5） ; } if （ （6） ）{top++; stack[top]= （5） ; } } }

（8） ; （9） ; } }

【答案】p->Rchild=t:t->Lchild=p:p=t: t->Rchild!=null:t->Rchild: t->Lchild!=null: t->Lchild: p->Rchild=head:head->Lchild=p

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

【答案】字符

14．对于一个具有n 个结点的单链表，在已知的结点半p 后插入一个新结点的时间. 复杂度为_____，在给定值为x 的结点后插入一个新结点的时间复杂度为_____。

【答案】

【解析】第一种情况只需直接修改指针的指向。第二种情况必须从头结点遍历找到x 的结点。

15．假定有k 个关键字互为同义词，若用线性探测再哈希法把这k 个关键字存入哈希表中，至少要进行_____次探测。

【答案】

【解析】当该关键字发生冲突时，用线性探测不会遇到别的关键字冲突，这个时候需要探测 的次数最小。总次数为

16．设为哈夫曼树的叶结点数日，则该哈夫曼树共有_____个结点。

【答案】

【解析】哈夫曼树只有度为0和2的节点。

17．下面描述的是一种构造最小生成树算法的基本思想。设要处理的无向图包括n

个顶点

用相邻矩阵A 表示，边的权全是正数。请在下列划线处填上正确叙述。

（1）若

是边，则

的值等于_____，若

不是边，则

的值是一个比任

何边的权，矩阵的对角线元素全为0。

（2）构造最小生成树过程中，若顶点Vi 已包括进生成树，就把相邻矩阵的对角线元素A （i , i ）置成若

【答案】（1）

已包括进生成树，就把矩阵元素A （i ，j ）置成。 边上的权值；都大的数；（2）1; 负值；（3）为负；边

（3）算法结束时，相邻矩阵中的元素指出最小生成树的

18．应用prim 算法求解连通网络的最小生成树问题。

（1）针对如图所示的连通网络，试按如下格式给出在构造最小生成树过程中顺序选出的各条边。

〔始顶点号，终顶点号，权值）

（2）下面是Prim 算法的实现，中间有5个地方缺失，请阅读程序后将它们补上。

的值在〈limits •h>中

//图的顶点数，应由用户定义

//用二维数组作为邻接矩阵表示

////

边生的成

树起

的点

边与

结终

点

点

//边上的权值

//最小生成树定义

//从顶点rt 出发构造图G 的最小生成树T ，rt 成为树的根结点

//初始化最小生成树

T

//依次求MST 的候选边

//遍历当前候选边集合

//选具有最小权值的候选边

//

图

//修改候选边集合

【答案】（1）（0，3，1）; （3，5, 4）; （5，2，2）; （3，1, 5）; （1，4，3） （2）①T[k]; tovex=i②min=Maxint③mispos=i④exit （O ）⑤T[i]; fromvex=v

【解析】Prim 算法的执行类似于寻找图的最短路径的Dijkstra 算法。假设N={V，E}是连通图

，是N

上最小生成树边的集合。算法从属于

为止。

E T 开始，重复执行下述操作：在所有u 属于

加入集合

同时将

并入

v

直到

的边（u ，v ）属于E

中找一条代价最小的边

不

连

通

，

出

错

处

理

三、应用题

19．模式匹配算法是在主串中快速寻找模式的一种有效的方法，如果设主串的长度为m , 模式的长度为n ，则在主串中寻找模式的KMP 算法的时间复杂性是多少? 如果某一模式给出它的next 函数值及next 函数的修正值nextval 之值。

【答案】KMP 算法的时间复杂性是01102201320。

请

p 的next 和nextval 值分别为01112212321和

20．（1）如果G1是一个具有n 个顶点的连通无向图，那么G1最多有多少条边?G1最少有多少条边？

（2）如果G2是一个具有n 个顶点的强连通有向图，那么G2最多有多少条边?G2最少有多少条边？

（3）如果G3是一个具有n 个顶点的弱连通有向图，那么G3最多有多少条边?G3最少有多少条边？

1）G1最多n （n-l ）/2条边，最少n-1条边。 【答案】（（2）G2最多n （n-l ）条边，最少n 条边。 （3）G3最多n （n-l ）条边，最少n-1条边。

21．用单链表保存m 个整数，节点的结构为（data , link ）, 且点而删除其余绝对值相等的节点。

例如若给定的单链表head 如下

删除节点后的head 为

要求

（1）给出算法的基本思想 （2）使用c 或

语言，给出单链表节点的数据类型定义。

语言描述算法，关键之处给出注释。

（3）根据设计思想，采用c 或【答案】（1）算法思想：

定义一个大小为n 的布尔数组flag ，初始时所有的元素都赋值为false , 用来标识遍历过程中是否出现元素绝对值为flag 的节点。然后遍历链表，遍历过程中，每一个当前结点data 域的绝对值，则将flag 位置为真（true ）所对应的flag 位：若为真，则删除该结点；若为假（false ）。

（2）节点的数据结构定义如下：

（3）

全局数组标志节点的绝对值是否出现过

（n 为正整数）。现要求

设计一个时间复杂度尽可能高效地算法，对于链表中绝对值相等的节点，仅保留第一次出现的节

（4）说明所涉及算法的时间复杂度和空间复杂度。

则删除该节点

如果此绝对值已经在节点值的绝对值中出现过

否则，将flag 中对应的位置置为true ，并将指针指向下一个元素

，申请大小（4）只遍历一次链表，所以时间复杂度为0 （m ） （m 为单链表中元素的个数）

为n 的数组，所以空间复杂度为0 （n ） （n 为节点绝对值的最大值）。

22．已知n 阶下三角矩阵A （即当，按照压缩存储的思想，可以将其主对角线以时，有）下所有元素（包括主对角线上元素）依次存放于一维数组B 中，请写出从第一列开始采用列序为主序分配方式时在B 中确定元素的存放位置的公式。

【答案】2

阶下三角矩阵元素第1列到第

列是梯形，元素数为

第1列有n 个元素，第j 列有而在第j 列上的位置是为

个元素，所以n

阶下三角矩阵A 按列存储，其元素在一维数组B 中的存储位置k 与i 和j 的关系为：

四、算法设计题

23．编写程序，统计在输入字符串中各个不同字符出现的频度并将结果存入文件（字符串中的合法字符为A ～Z 这26个字母和0～9这10个数字）。

【答案】算法如下：

24．假设以I 和O 分别表示入栈和出栈操作。栈的初态和终态均为空，入栈和出栈的操作序列可表示为仅由I 和O 组成的序列，称可以操作的序列为合法序列，否则称为非法序列。

（1）下面所示的序列中哪些是合法的？

（2）通过对（1）的分析，写出一个算法，判定所给的操作序列是否合法。若合法，返回true , 否则返回false （假定被判定的操作序列已存入一维数组中）。

【答案】（1）A 和D 是合法序列，B 和C 是非法序列。 （2）设被判定的操作序列已存入一维数组A 中，算法如下：

判断字符数组A 中的输入输出序列是否是合法序列。

为下标

一、选择题

1． 下列因素中，不会影响信道数据传输速率的是（ ）

A. 信噪比 B. 频率宽带 C. 调制速率 D. 信号传播速度 【答案】D

【解析】信道数据传输速率与信噪比、频率宽度、调制速率都有关。

2． 用邻接表存储图所用的空间大小（ ）。

A. 与图的顶点数和边数都有关 B. 只与图的边数有关 C. 只与图的顶点数有关 D. 与边数的平方有关 【答案】A

【解析】邻接表就是对图G 中的每个顶点Vi 建立一个单链表，第i 个单链表中的结点表示依附于顶点V i 的边，这个单链表就称为顶点Vi 的边表。因此邻接表既存储图的所有顶点，也存储顶点之间的边的信息。

3． 串的长度是指（ ）。

A. 串中所含不同字母的个数 B. 串中所含字符的个数 C. 串中所含不同字符的个数 D. 串中所含非空格字符的个数 【答案】B

【解析】串中字符的数目n 称为字符的长度，不必考虑其中单个字符是否相等。

4． 假定用若干个2Kx4位的芯片组成一个8Kx8位的存储器，则地址0B1FH 所在芯片的最小地址是（ ）。

A.0000H B.0600H C.0700H D.0800H 【答案】D

【解析】由若干芯片构成存储器，采用字和位同时扩展方法。8片2Kx4位的芯片分成4组，

每组2个芯片，各组芯片的地址分配分别为：第1组，0000H 〜07FFH ; 第2组，0800H 〜0FFFH ; 第3组，1000H 〜17FFH ; 第4组，1800H 〜1FFFH 。地址0BIFH 处于第2组内，其芯片的最小地址为0800H 。

5． 假定一台计算机的显示存储器用DRAM 芯片实现，若要求显示分辨率为1600x1200, 颜色深度为24位，帧频为85Hz , 显存总带宽的50%用来刷新屏幕，则需要的显存总带宽至少约为（ ）。

A.245Mbps B.979Mbps C. D. 【答案】D

【解析】显存的容量=分辨率×色深，带宽=分辨率×色深×帧频，考虑到

的时间用来刷新

1600×1200×24×85×2＝7834Mbps 屏幕，故显存总带宽应加倍。所以需要的显存总带宽至少约为：

6． 哈希函数有一个共同的性质，即函数值应当以（ ）取其值域中的每个值。

A. 最大概率 B. 最小概率 C. 平均概率 D. 同等概率 【答案】D

7． 有关二叉树下列说法正确的是（ ）。

A_二叉树的度为2

B. —棵二叉树的度可以小于2 C. 二叉树中至少有一个结点的度为2 D. 二叉树中任何一个结点的度都为2 【答案】B

【解析】树的度=MAX（结点1的度，结点2的度，结点3的度，... ，结点n 的度）。二叉树之所以称为二叉树，是因为二叉树中节点的度最大是2，也可以小于2。

8． 下列关于无向连通图特性的叙述中，正确的是（ ）。

I. 所有的顶点的度之和为偶数 II. 边数大于顶点个数减1 III. 至少有一个顶点的度为1 A. 只有I B. 只有II C.I 和II

D.I 和III 【答案】A

【解析】在图中，顶点的度TD 点数，

e 为总边数），因此，I 项正确。对于II 、III 项中的特性不是一般无向连通图的特性，可以轻松地举出反例。“至少有一个顶点的度为1”的反例如下图（1）所示，“边数大于顶点个数减1”的反例如下图（2）所示。

之和与边的数目满足关系式：

（n 为图的总结

图

9． 静态链表中指针表示的是（ ）。

A. 下一元素的地址 B. 内存储器的地址 C. 下一元素在数组中的位置 D. 左链或右链指向的元素的地址 【答案】C

【解析】静态链表的一般结构为：

这种结构是预先分配一个较大的空间，类似于一次申请一个较大的数组，但是元素的增删操作都不会移动元素，只需要移动next 成员就行。因此，静态链表中的指针实际上表示的就是下一个元素在数组中的位置。

10．某CPU 主频为1.03GHz , 采用4级指令流水线，每个段的执行需要1个时钟周期。假定CPU 执行了100条指令，在其执行过程中没有发生任何流水线阻塞，此时流水线的吞吐率为（ ）

A. B. C. D. 【答案】C

【解析】采用4级流水线执行100条指令，在执行过程中共用

条指令/秒，故答案为C 。

条指令/秒 条指令/秒 条指令/秒 条指令/秒

个时钟周期。

CPU 的主频是1.03GHz , 也就是说每秒钟有1.03G 个时钟周期。流水线的吞吐率

为

11．在进行入栈运算时应先判别栈是否_____:在进行出栈运算时应先判别栈是否_____:当栈中元素为n 个，进行入栈运算时发生上溢，则说明该栈的最大容量为_____。为了增加内存空间的利用率和减少溢出的可能性，由两个栈共享一片连续的空间时，应将两栈的_____分别设在内存空间的两端，这样只有当_____时才产生溢出。

【答案】满；空；n ; 栈底；两栈顶指针相邻（即值之差的绝对值为1）

12．设用希尔排序对数组{98，36，-9，0，47，23，1，8，10，7}进行排序，给出的步长（也称 增量序列）依次是4，2，1则排序需_____趟，写出第一趟结束后，数组中数据的排列次序_____。

【答案】3; （10，7，-9，0，47，23，1，8，98，36）

13．—个字符串中_____称为该串的子串。

【答案】任意个连续的字符组成的子序列 14．

【答案】5

15．对于一个具有n 个结点的二叉树，当它为一棵_____二叉树时具有最小高度，当它为一棵_____ 时. 具有最大高度

【答案】完全；只有一个叶结点的二叉树

16．起始地址为480，大小为8的块，其伙伴块的起始地址是_____；若块大小为32，则其伙伴块的起始地址为_____。

【答案】

【解析】起始地址为P ，大小为的内存块，其伙伴块的起始地址计算公式如下：

根据上述公式起始地址就为488。

17．已知链队列的头尾指针分别是f 和r , 则将值x 入队的操作序列是_____。

【答案】

【解析】队列采用链式存储结构，先分配一个节点的内存，然后在队尾添加该节点。

18．在循环队列中，队列长度为n ，存储位置从0到，编号，以rear 指示实际的队尾元素，现要在此队列中插入一个新元素，新元素的位置是（ ）。

【答案】

=_____

19．设有6个有序表A 、B 、C 、D 、E 、F , 分别含有10、35、40、50、60和200个数据元素，各表中元素按升序排列。要求通过5次两两合并，将6个表最终合并成1个升序表，并在最坏情况下比较的总次数达到最小。请回答下列问题。

（1）给出完整的合并过程，并求出最坏情况下比较的总次数。 （2）根据你的合并过程，描述

n 【答案】

（1）6个表的合并顺序如下图所示。

个不等长升序表的合并策略，并说明理由。

对应于合并过程的哈夫曼树

根据上图中的哈夫曼树，6个序列的合并过程为：

第1次合并：表A 与表B 合并，生成含45个元素的表AB ; 第2次合并：表AB 与表C 合并，生成含85个元素的表ABC ; 第3次合并：表D 与表E 合并，生成含110个元素的表DE ;

第4次合并：表ABC 与表DE 合并，生成含195个元素的表ABCDE ; 第5次合并：表ABCDE 与表F 合并，生成含395个元素的最终表。

由于合并两个长度分别为m 和n 的有序表，最坏情况下需要比较m+n-1次，故最坏情况下比较的总次数计算如下：

第1次合并：最多比较次数= 10+35-1=44; 第2次合并：最多比较次数=45+40-1 = 84; 第3次合并：最多比较次数=50+60-1 = 109; 第4次合并：最多比较次数=85+110-1 = 194;

第5次合并：最多比较次数= 195+200-1 = 394; 比较的总次数最多为：44+84+109+194+394 = 825。

（2）各表的合并策略是：在对多个有序表进行两两合并时，若表长不同，则最坏情况下总的比较次数依赖于表的合并次序。可以借用哈夫曼树的构造思想，依次选择最短的两个表进行合并，可以获得最坏情况下最佳的合并效率。

解析：本题具有较强的综合性，主要考查了构造哈夫曼树的算法思想和过程、归并排序的过程等。

20．二叉树的带权路径长度（WPL ）是二叉树中所有叶结点的带权路径长度之和，给定一棵二叉树T ，采用二叉链表存储，节点结构为：

其中叶节点的weight 域保存该结点的非负权值。设root 为指向T 的根节点的指针，设计求T 的WPL 的算法。要求：

（1）给出算法的基本设计思想；

（2）使用C 或C++语言，给出二叉树结点的数据类型定义；

（3）根据设计思想，采用C 或C++语言描述算法，关键之处给出注释。

【答案】（1）算法的基本思路是利用利用递归的思想来求解二叉树的带权路径长度，如果当前节点不是叶子节点，那么当前节点为根的树的带权路径长度便等于它的子树的带权路径长度之和，对于此函数要传入一个当前节点的树高的形参，那么递归调用孩子节点时只需要将这个形参加一即可。

（2）

typedef struct BiNode

（3）具体算法实现如下：

如果当前节点为空节点

//如果当前节点的左右孩子节点都为空，即当前节点为叶子节点，直接返回当前节点的

WPL

//如果当前节点不是叶子节点，则对当前节点的左右子树进行递归，返回左右子树WPL 之和

21．某计算机的CPU 主频为500MHz ，CPI 为5（即执行每条指令平均需要5个时钟周期）。假定某外设的数据传输率为0.5MB/S，采用中断方式与主机进行数据传送，以32位为传输单位，对应的中断服务程序包含18条指令，中断服务的其他开销相当于2条指令的执行时间。请回答下列问题，要求给出计算过程。

（1）在中断方式下，CPU 用于该外设I/O的时间占整个CPU 时间的百分比是多少？ （2）当该外设的数据传输率达到5MB/s时，改用DMA 方式传送数据。假定每次DMA 传送块大小为5000B , 且DMA 预处理和后处理的总开销为500个时钟周期，则CPU 用于该外设I/0时间占整个CTU 时间的百分比是多少？（假设DMA 与CPU 之间没有访存冲突）

【答案】（1）已知主频为500MHz ，则时钟周期=l÷500MHz=2ns，因为CPI=5, 所以每条指令，数据传输率为0.5MB/S, 所以传送时间平均5×2=10ns。又已知每中断一次传送32位（4个字节）=4÷0.5MB/s=

CPU 用于该外设I/0共需20条指令（中断服务程序包括18条指令+其他开销折

，花费时间=20×l0=200ns。CPU 用于该外设I/0的时间占整个CPU 时间的百分比合2条指令）

=200/8000×100%=0.025×100%=2.5%。

（2）改用DMA 方式传送数据，数据传输率为5MB/S，传送5000B 的时间=5000B÷5MB/s=lms。预处理和后处理的总开销时间=500×2ns=

CPU 用于该外设I/0时间占整个CPU 时间的百分比=

预处理和后处理的总开销时间÷传送数据的时间=l/1000×l00%=0.001×100%=0.1%。

22．在某程序中，有两个栈共享一个一维数组空间分别是两个栈的栈底。

（1）对栈1、栈2, 试分别写出（元素x ）入栈的主要语句和出栈的主要语句。 （2）对栈1、栈2, 试分别写出栈满、栈空的条件。 【答案】（1）入栈主要语句

出

栈

主

要

语

句

（2）

四、算法设计题

23．设有一头指针为L 的带有表头结点的非循环双向链表，其每个结点中除有pred （前驱指针），data （数据）和next （后继指针）域外，还有一个访问频度域freq 。在链表被启用前，其值均初始化为零。每当在链表中进行一次Locate （L ，x ）运算时，令元素值为x 的结点中freq 域的值増1, 并使此链表中结点保持按访问频度非增（递减）的顺序排列，同时最近访问的结点排在频度相同的结点的最后，以便使频繁访问的结点总是靠近表头。试编写符合上述要求的Locate （L , x ）运算的算法，该运算为函数过程，返回找到结点的地址，类型为指针型。

【答案】算法如下：

24．已知二叉树采用二叉链表存储，设计算法以输出二叉树T 中根结点到每个叶结点的路径。

【答案】算法如下：：

//打印从根结点bt 到结点p 之间路径上的所有结点

是元素为二叉树结点指针的栈，容量足够大

是数组，元素值为0或1, 访问左、右子树的标志，tag 和s 同

步

//根结点就是所找结点

//左子女入栈，并置标记

//找到结点P , 栈中元素均为结点P 的袓先

//沿左分支向下

//本题不要求输出遍历序列，

这里只出栈

沿右分支向下

}//结束算法

PrintPath

为叶结点

从根结点到P 结点的路径为

输出从根到叶子q 的路径上的所有祖先

从根结点到P 结点的路径为

一、选择题

1． 已知两个长度分别为m 和n 的升序链表，若将它们合并为一个长度为m+n的降序链表，则最坏情况下的时间复杂度是（ ）

A. B. C. D. 【答案】D

【解析】m 和n 是两个升序链表长度分别为m 和n ，在合并过程中最坏的情况是两个链表中的元素依次进行比较，比较的次数是m 和n 中的最大值。

2． 为实现快速排序算法，待排序序列宜采用的存储方式是（ ）。

A. 顺序存储 B. 散列存储 C. 链式存储 D. 索引存储 【答案】A

【解析】对绝大部分内部排序而言，只适用于顺序存储结构，快速排序在排序过程中，既要从后向前查找，也要从前向后查找，因此宜采用顺序存储。

3． 图G 是n 个顶点的无向完全图，则下列说法不正确的是（ ）

A.G 的邻接多重表需要n （n-l ）个边结点和n 个顶点结点 B.G 的连通分量个数最少 C.G 为连通图

D.G 所有顶点的度的总和为n （n-1） 【答案】A

【解析】A 项中G 的邻接多重表中需要n （n-l ）/2个边结点和n 个顶点结点。此时连通分量最少为1。无向完全图中任意两个顶点之间都存在路径，则G 必为连通图。每个顶点的度为n-1，则n 个结点的度的总和为n （n-l ）。

4． 下列存储器中，在工作期间需要周期性刷新的是（ ）。

A.SRAM B.SDRAM C.ROM

D.FLASH 【答案】B

【解析】动态随机存储器（DRAM ）是利用存储元电路中栅极电容上的电荷来存储信息的，电容上的电荷一般只能维持

因此即使电源不掉电，信息也会自动消失。为此，每隔一定时

间必须刷新。

5． 若数据元素序列11, 12, 13, 7, 8, 9, 23, 4, 5是采用下列排序方法之一得到的第二趟排序后的结果，则该排序算法只能是（ ）。

A. 起泡排序 B. 插入排序 C. 选择排序 D. 二路归并排序 【答案】B

【解析】经过两趟排序后，A 项起泡排序的结果是两个最小或最大的元素放到了序列的最终位置；B 项插入排序的结果是前三个数有序即可；C 项选择排序结果是两个最小的元素在最前面按顺序排好；D 项二路归并排序的结果是长度为4的子序列有序，即前4个数排好序，接下来的4个数排好序。显然题目中的元素序列只能是插入排序第二趟排序后的结果，因此，B 项正确。

6． 数据序列只能是下列排序算法中的（ ）的两趟排序后的结果。

A. 选择排序 B. 起泡排序 C. 插入排序 D. 堆排序 【答案】C

【解析】选择排序、起泡排序和堆排序两趟排序后，在序列的某一端应该有序列的两个最大值或者最小值。

7． 从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为（ ）排序法。

A. 插入 B. 选择 C. 希尔 D. 二路归并 【答案】A

【解析】解此题需要熟知各种排序方法的基本思想。插入排序的基本思想是：假设待排序的

记录存放在数组

中，排序过程的某一中间时刻，R

被划分成两个子区间

和

其中：前一个子区间是已排好序的有序区，后一个子区间则是当前未排序的部分，不妨

称其为无序区。将当前无序区的第1

个记录

插入到有序区

中适当的位置上。使

变为新的有序区。这种方法通常称为增量法，因为它每次使有序区增加1个记录。

8． 系统为某进程分配了4个页框，该进程已访问的页号序列为2, 0, 2, 9, 3, 4, 2, 8, 2, 3, 8, 4, 5, 若进程要访问的下一页的页号为7，依据LRU 算法，应淘汰页的页号是（ ）。

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

【答案】B

【解析】LRU 置换算法是选择最近最久未使用的页面予以淘汰。进程有4个页框，题中访问过程中页框的变化如下：

序列：页框：

淘汰：3。

9． 在OSI 参考模型中，直接为会话层提供服务的是（ ）

A. 应用层 B. 表示层 C. 传输层 D. 网络层 【答案】C

【解析】OSI 参考模型中，下层直接为上层提供服务，而会话层的下层为传输层。

10．将一个的三对角矩阵，按行优先存入一维数组中，A 中元素（即该元素下标

A.198 B.195 C.197

【答案】B

【解析】将对角矩阵

在B 数组中的位置K 为（ ）。

访问页号为7的页时，内存中存在的页的页号是：3、8、4和5，根据LRU 定义应淘汰的是

存入三对角矩阵压缩地址计算公式如下：

二、填空题

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

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

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

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

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

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

将P 结点链入链表中

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

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

13．对于给定的元素，可以构造出的逻辑结构有_____，_____，_____，_____四种。

【答案】集合；线性结构；树形结构；图状结构（网状结构）

14．从用户的观点看，文件的逻辑结构通常可以区分为两类：一类是如NdBASE 中数据库文件那样的文件组织结构，称为_____文件:另一种是诸如用各种文字处理软件编辑成的文本文件，称为_____文件。从文件在存储器上的存放方式来看，文件的物理结构往往可区分为三类，即_____，_____和_____。B+树适用于组织_____的索引结构，m

阶个关键码。

【答案】数据库；文本；顺序组织；随机组织；链组织；随机组织；

15．抽象数据类型的定义仅取决于它的一组_____，而与_____无关, 即不论其内部结构如何变化，只要它的_____不变，都不影响其外部使用。

【答案】逻辑特性；在计算机内部如何表示和实现；数学特性

16．在一个具有n 个单元的顺序栈中，假定以地址高端（即下标为n 的单元）作为栈底，以top 作为栈顶指针，则当向栈中压入一个元素时，top 的变化是top=_____。

【答案】

树每个结点至多有_____个儿子，除

根结点外每个结点至少有_____个儿子，根结点至少有_____个儿子，有k 个儿子的结点必有_____

【解析】由于栈底在地址高端，栈中压入一个元素时，栈顶向地址底端移动一个单位，

所以

17．建立索引文件的目的是_____。

【答案】提高查找速度

18．顺序查找n 个元素的顺序表，若查找成功，则比较关键字的次数最多为_____次；当使用监视哨时，若查找失败，则比较关键字的次数为_____。

【答案】视哨。

【解析】最多的情况就是把整个表遍历了一遍。使用监视哨时，需要多一个存储空间来存监

三、应用题

19．若森林共有n 个结点和b 条边（b

【答案】森林的n 个结点开始可看做是n 个连通分量，加入一条边将减少一个连通分量。因为树可以定义为无环的图，故加入b 条边将减少b 个连通分量，因而n 个结点b 条边的森林有n-b 棵树。

20．线性表有两种存储结构：一是顺序表，二是链表。试问：

（1）如果有，2个线性表同时并存，并且在处理过程中各表的长度会动态变化，线性表的总数也会自动地改变。在此情况下，应选用哪种存储结构? 为什么？

（2）若线性表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取线性表中的元素，那么应采用哪种存储结构? 为什么？

【答案】（1）应选择链式存储结构。因为它可动态申请内存空间，不受表长度（即表中元素个数）的影响，插入、删除时间复杂度为O （1）。

（2）应选择顺序存储结构。因为顺序表可以随机存取，时间复杂度为O （1）。

21．假设Internet 的两个自治系统构成网络如题图所示，自治系统ASI 由路由器R1连接两个子网构成；自治系统AS2由路由器R2、R3互联并连接3个子网构成。各子网地址、R2的接口名、R1与R3的部分接口 IP 地址如题图所示。请回答下列问题。

题图网络拓扑结构

（1）假设路由表结构如下所示。请利用路由聚合技术，给出R2的路由表，要求包括到达题图中所有子网的路由，且路由表中的路由项尽可能少。

（2）若R2收到一个目的IP 地址为194.17.20.200的IP 分组，R2会通过哪个接口转发该IP 分组？

R1与R2之间利用哪个路由协议交换信息？该路由协议的报文被封装到哪个议的分组中（3）进行传输？

【答案】

（1）在AS1中，子网中，子

网

和子网单独连接到

的接口

可以聚合为子网

但缺少

子网

于是可以得到R2的路由表如下：

（2）该IP 分组的目的IP 地址194.17.20.200与路由表中194.17.20.0/23和194.17.20.128/25两个路由表项均匹配，根据最长匹配原则，R2将通过E0接口转发该1P 分组。

（3）R1与R2之间利用BGP4 （或BGP ）交换路由信息；BGP4的报文被封装到TCP 协议段中进行传输。2012年全国硕士研究生入学统一考试计算机科学与技术学科联考计算机学科专此基础综合真题及详解

和子网

可以聚合为子网

在AS2

22．设某文件经内排序后得到100个初始归并段（初始顺串），若使用多路归并排序算法，并要求三趟归并完成排序，问归并路数最少为多少？

【答案】设归并路数为k ，归并趟数为s ，则最少5-路归并完成排序。

因

且k 为整数，故k=5，即

四、算法设计题

23．已知一个单链表中每个结点存放一个整数，并且结点数不少于2, 请设计算法以判断该链表中第二项起的每个元素值是否等于其序号的平方减去其前驱的值，若满足则返回ture , 否则返回false 。

【答案】算法如下：

24．已知L 为没有头结点的的单链表中第一个结点的指针，每个结点数据域存放一个字符，该字符可能是英文字母字符、数字字符或其他字符，编写算法构造三个以带头结点的单循环链表表示的线性表，使每个表中只含同一类字符（要求用最少的时间和最少的空间）。

【答案】算法如下：

一、选择题

1． 在下面的排序方法中，辅助空间为

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

2．

已知操作符包括

的后缀表达式

将中缀表达式

转换为等价

的是（ ）。

时，用栈来存放暂时还不能确定运算次序的操作符。若栈初始时为

空，则转换过程中同时保存在栈中的操作符的最大个数是（ ）。

A.5 B.7 C.8 D.11

【答案】A 。

【解析】基本思想是：采用运算符栈是为了比较运算符的优先级，所有运算符必须进栈。只将大于栈顶元素优先级的运算符直接进栈，否则需要退栈栈顶运算符（先出栈的运算符先计算，同优先级的运算符在栈中的先计算）

。表达式所列：

产生后缀表达式的过程如下表

通过上表可以看出，显然转换过程中同时保存在栈中的操作符的最大个数是5。

3． 采用递归方式对顺序表进行快速排序。下列关于递归次数的叙述中，正确的是（ ）。

A. 递归次数与初始数据的排列次序无关

B. 每次划分后，先处理较长的分区可以减少递归次数 C. 每次划分后，先处理较短的分区可以减少递归次数 D. 递归次数与每次划分后得到的分区的处理顺序无关 【答案】D

【解析】快速排序是递归的，递归过程可用一棵二叉树给出，递归调用层次数与二叉树的深，采用快速排序方法，其对应递归调用度一致。例如：待排序列{48, 62，35, 77, 55, 14, 35, 98）过程的二叉树如下图所示。

在最坏情况下，若初始序列按关键码有序或基本有序时，快速排序反而蜕化为冒泡排序。即其对应递归调用过程的二叉树是一棵单支树。因此快速排序的递归次数与初始数据的排列次序有关。但快速排序的递归次数与每次划分后得到的分区处理顺序无关，即先处理较长的分区或先处理较短的分区都不影响递归次数。

4． 归并排序中，归并的趟数是（ ）。

【答案】B

【解析】不妨设归并的趟数为m ，第一次归并每组有两个元素，最后一次归并只剩下一组，

这组的元素个数为n

。因此每次归并元素的个数增加一倍。所以

所以归并的趟数为

5． 下列线索二叉树中（用虚线表示线索），符合后序线索树定义的是（ ）。

【答案】D

【解析】线索二叉树利用二叉链表的空链域来存放结点的前驱和后继信息，解题思路较简单。题中所给二叉树的后序序列为dbca 。结点d 无前驱和左子树，左链域空，无右子树，右链域指向其后继结点b ; 结点b 无左子树，左链域指向其前驱结点山结点c 无左子树，左链域指向其前驱结点b ，无右子树，右链域指向其后继结点a 。所以正确选项为D 。

6． 某磁盘的转速为10, 000转/分，平均寻道时间是磁盘传输速率是为

读取一个4KB 的扇区所需平均时间约为（ ）

A.9ms B.9.4ms C.12ms D.12.4ms 【答案】B

【解析】磁盘转速是10 000转/分钟，平均转一转的时间是6ms ，因此平均查询扇区的时间是3ms ，平均寻道时间是6ms ，读取4KB 扇区信息的时间为0.2ms ，信息延迟的时间为0.2ms ，总时 间为

7． —

组记录的关键码为

准得到的一次划分结果为（ ）。

【答案】C

【解析】快速排序是将待排记录分割成独立的两部分，其中一部分的关键字均比另一部分记录的关键字小。

磁盘控制器延迟

则利用快速排序的方法，以第一个记录为基

第一次比较：46比84小，不交换； 第二次比较：40比46小，交换，此时为第三次比较：46比79小，交换，此时为第四次比较：38比46小，交换，此时为第五次比较：56比46大，交换，此时为

一次划分结束。

8． 对一组数据（2, 12, 16, 88, 5，10）进行排序，若前三趟排序结果如下：

第一趟：2，12，16, 5，10，88

第二趟：2，12，5，10，16, 88 第三趟：2，5，10，12，16, 88 则采用的排序方法可能是（ ）。 A. 起泡排序 B. 希尔排序 C. 归并排序 D. 基数排序 【答案】A

【解析】题目中所给的三趟排序过程，显然是使用起泡排序方法，每趟排序时从前往后依次，待序列中的记录“基比较，使大值“沉底”。希尔排序的基本思想是：先对序列进行“宏观调整”本有序”时再进行直接插入排序。宏观调整的方法是：通过某种规则将大的待排序序列分割为若干小的待排序序列，再依次对这些小的序列直接插入排序。宏观调整可以多次，每次分割的序列数逐渐増多，而每个序列中所包含的元素数逐渐减少。归并排序的基本操作是将多个小的有序序，直至整个序列为有序为止。 基数排序是分配排列合并为一个大的有序序列，然后“逐趟归并”

序的一种，这类排序不是通过关键字比较，而是通过“分配”和“收集”过程来实现排序的。 本，显然使用的是起泡排序法。 题中，很容易看出大值逐渐“沉底”

9． 设文件索引节点中有7个地址项，其中4个地址项为直接地址索引，2个地址项是一级间接地址索引，1个地址项是二级间接地址索引，每个地址项大小为4字节，若磁盘索引块和磁盘数据块的大小均为256字节，则可表示的单个文件最大长度是（ ）。

A.33KB B.519KB C.1057KB D.16513KB 【答案】C

【解析】4个地址项为直接地址索引，其指向的数据块大小4×256B=lKB，一级间接地址索引可以索引256/4=64个直接地址索引，故2个一级间接地址索引指向的数据块大小为2×64×256B=32KB，二级间接地址索引为256/4×256/4=4096个直接地址索引，故1个二级间接地址索引指向的数据块大小为4096×256B=1024KB, 共计1KB+32KB+1024KB=1057KB。

10．下述文件中适合于磁带存储的是（ ）。

A. 顺序文件 B. 索引文件 C. 哈希文件 D. 多关键字文件 【答案】A

【解析】磁带存储是一种顺序存储，

顺序文件序文件适合磁带存储。

是记录按其在文件中的逻辑顺序

依次进入存储介质而建立的，即顺序文件中物理记录的顺序和逻辑记录的顺序是一致的。因此顺

二、填空题

11．设广义表

则

是_____tail（L ）是_____；L 的长度是_____；深度是_____。

；；2；2 【答案】（ ）（（ ））

【解析】广义表的表头是表的第一个元素，表尾是除了第一个元素外其余的所有的元素构成的表；表的长度指表中元素的个数；表的深度指展开后括号的层数。

12．一个有2001个结点的完全二叉树的高度是_____。

【答案】11

【解析】

完全二叉树的高度

13．检索是为了在文件中寻找满足一定条件的记录而设置的操作。检索可以按_____检索。也可以按_____检索；按_____检索又可以有_____检索和_____检索。

【答案】关键字；记录号；记录号；顺序；直接

14．设有一个空找，栈顶指针为1000H （十六进制），现有输入序列为1，2，3, 4, 5，经过PUSH ，PUSH , POP , PUSH , POP ，PUSH ，PUSH 之后，输出序列是_____，而栈顶指针值是_____。设栈为顺序栈，每个元素占4个字节。

【答案】23; 100CH

15．假设一个15阶的上三角矩阵A 按行优先顺序压缩存储在一维数组B 中，则非零元素中的存储位置k=_____。（注：矩阵元素下标从1开始）

【答案】93

【解析】对于上三角矩阵

，将代入得93。

16．深度为H 的完全二叉树至少有_____个结点; 至多有_____个结点; H 和结点总数N 之间的关系是_____。

【答案】

在B

17．在单链表中设置头结点的作用是_____。

【答案】方便运算

18．在一棵m 阶的个数是_____。

【答案】

最少

【解析】m 阶树除根结点和叶子结点外，结点中关键字个数最多是

树中，若在某结点中插入一个新关键字而引起该结点分裂，则此结点中原有的

关键字的个数是_____；若在某结点中删除一个关键字而导致结点合并，则该结点中原有的关键字

三、应用题

19．设LS 是一个线性表，

若采用顺序存储结构，则在等概率的前提下，插

与

之间

的概率

为

入一个元素需要平均移动的元素个数是多少? 若元素插

在

【答案】需要分两种情况讨论：

，插入位置0..n ，则平均移动个数为（1）等概率（后插）

（2）若不等概率，则平均移动的元素个数为

20．已知两个各包含IV 和M 个记录的排好序的文件能在

则插入一个元素需要平均移动的元素个数又是多少？

时间内合并为一个包含个

记录的排好序的文件。当有多于两个排好序的文件要被合并在一起时，只需重复成对地合并便可完成。合并的步骤不同，所需花费的记录移动次数也不同。现有文件，FI ，F2，F3，F4，F5，各有记录数为20，30，10，5和30，试找出记录移动次数最少的合并步骤。

，【答案】类似最优二叉树（哈夫曼树）可先合并含较少记录的文件，后合并较多记录的文件，使移动次数减少，如图所示的哈夫曼树。

图

21．设二叉树BT 的存储结构如表：

表 二叉树BT 的存储结构

其中BT 为树根结点的指针，其值为6, Lchild 、Rchild 分別为结点的左、右孩子指针域data 为结点的数据域。试完成下列各题：

（1）画出二叉树BT 逻辑结构；

（2）写出按前序、中序、后序遍历该二叉树所得到的结点序列： （3）画出二叉树的后序线索树。

【答案】（1）二叉树的逻辑结构如图1所示：

图1

（2）前序序列：ABCEDFHGIJ 中序序列：ECBHFDJIGA 后序序列：ECHFJIGDBA

（3）:二叉树的后续线索树如图2所示：

图2

22．某32位计算机，CPU 主频为800MHz ，Cache 命中时的CPI 为4, Cache块大小为32字节；主存采用8体交叉存储方式，每个体的存储字长为32位、存储周期为40ns ; 存储器总线宽度为32位，总线时钟频率为200MHz , 支持突发传送总线事务。每次读突发传送总线事务的过程包括：送首地址和命令、存储器准备 数据、传送数据。每次突发传送32字节，传送地址或32位数据均需要一个总线时钟周期。请回答下列问题，要求给出理由或计算过程。

（1）CPU 和总线的时钟周期各为多少？总线的带宽（即最大数据传输率）为多少？ （2）Cache 缺失时，需要用几个读突发传送总线事务来完成一个主存块的读取？ （3）存储器总线完成一次读突发传送总线事务所需的时间是多少？

（4）若程序BP 执行过程中，共执行了100条指令，平均每条指令需进行1.2次访存，Cache 缺失率为5%, 不考虑替换等开销，则BP 的CPU 执行时间是多少？

【答案】

（1）因为CPU 主频为800MHz ，故CPU 的时钟周期为：总线时钟频率为200MHz ，故总线的时钟周期为：总线宽度为32bit=4B，故总线带宽为存块。

（3）—次读突发传送总线事务包括一次地址传送和32B 数据传送:用1个总线时钟周期传输地址;

每隔

，第一个体读数据花费40ns ，之后数据启动一个体工作（各进行1次存取）

存取与数据传输重叠；用8个总线时钟周期传输数据。读突发传送总线事务时间

：

s

BP 的CPU 执行时间包括Cache 命中时的指令执行时间和Cache 缺失时带来的额外开销。（4）即执行时间=指令条数间

：

时钟周期*命中率+访存次数*缺失率*缺失损失。命中时的指令执行时

指令执行过程中的CPU 执行时间

：

Cache

缺失时的额外开

销

（2）因为Cache 块大小为32B , 因此Cache 缺失时需要一个读突发传送总线事务读取一个贮

四、算法设计题

23．在一棵以二叉链表表示的二叉树上，试写出按层次顺序遍历二叉树的方法，统计树中具有度为1的结点数目的算法。

【答案】算法如下：

int Level（BiTree bt） //层次遍历二叉树，并统计度为1的结点的个数 {int num=C; //num统计度为1的结点的个数

if （bt ）{Queuelnit（Q ）; Queueln（Q , bt ）; //Q是以二叉树结点指针为元素德 队列 while （!QueueEmpty （Q ））

{p=Queueout（Q ）; printf （p->data）; //出队访问结点

//非空右子女入队

//返回度为1的结点的个数

24．用邻接多重表存储结构，编写FIRST-ADJ （G ，V ）函数，函数返回值为第一个邻接点，若V 没有邻接点，返回零。

【答案】算法如下：

//在邻接多重表g 中，求v 的第一邻接点, 若存在，返回第一邻接点，否则返回0

（

//确定顶点v 在邻接多重表向量中的下标, 不考虑不存在v 的情况

//取第一个边结点

//返回第一邻接点，ivex 和jvex 中必有一个等干

i

一、选择题

1． 对矩阵压缩存储是为了（ ）。

A. 方便运算 B. 方便存储 C. 提高运算速度 D. 减少存储空间 【答案】D

【解析】压缩存储也就是对那些没用的元素不进行存储或者对那些具有一定规律的相同元素放在一个存储空间，目的就是为了节省空间。

2． 下列选项中，不可能在用户态发生的事件是（ ）。

A. 系统调用 B. 外部中断 C. 进程切换 D. 缺页 【答案】C 。

【解析】我们在学习操作系统中知道，任何一个进程在现代操作系统中为了共享和保护，设，在用户态运行用户的程序，在内核定了用户态和内核态（可以通过设置软、硬件标志位来实现）

运行系统的程序。所以，从选 项来看，系统调用可以在任何态发生，用户可以发起系统调用，系统也可以；外部中断是不可控的，也会在任何时刻发生，缺页的发生也是不可控的，可以发生在用户代码之间；而进程切换却不会在用户态发生。我们可以考虑一下情形，进程切换是在什么时候发生的，进程切换前必定运行的是进程调度，只有进程调度选择了下一次被调度的进程，进程切换才可以进行。进程调度是scheduler , 进程切换是dispather , 这体现了现代操作系统策略与机制，必定分离的设计思想。所以，进程切换必定不会在用户态发生（所谓发生指其起始的源头时刻）是在内核态（进程调度）发生的。

3． 对任意一棵树，设它有n 个结点，这n 个结点的度数之和为（ ）。

A.n B. C. D. 【答案】C

【解析】每个结点（除根节点外）都是一个分支，即所有结点的度数之和等于分支个数等于

总的结点数减一，即n-1。

4． 动态存储管理系统中，通常可有（ ）种不同的分配策略。

【答案】C

【解析】动态存储管理系统中有以下三种：首次拟合法、最佳拟合法、最差拟合法。①首次拟合法，从表头指针开始查找可利用空间表，将找到的第一个大小不小于n 的空闲块的一部分分配给用户。②最佳拟合法，将可利用空间表中一个不小于n 且最接近n 的空闲块的一部分分配给用户。则系统在分配前首先要对可利用空间表从头到尾扫视一遍，然后从中找出一块不小于n 且最接近n 的空闲块进行分配。③最差拟合法，将可利用空间表中不小于n 且是链表中最大的空闲块的一部分分配给用户。

5． 对于100Mbps 的以太网交换机，当输出端口无排队直通（cut-throughswitching ）方式转发一个以太网帧（不包括前导码）时，引入的转发延迟至少是（ ）

A. B. C. D. 【答案】B

【解析】直通交换方式是指以太网交换机可以在各端口间交换数据。它在输入端口检测到一个数据包时，检查该包的包头，获取包的目的地址，启动内部的动态查找表转换成相应的输出端口，在输入与输出交叉处接通，把数据包直通到相应的端口，实现交换功能。通常情况下，直通交换方式只检查数据包的包头即前14个字节，由于不需要考虑前导码，只需要检测目的地址的6B ，

所以最短的传输延迟是

6． 若查找每个记录的概率均等，则在具有n 个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度

【答案】C

【解析】最快查找一次成功，最慢查找n

次成功。平均查找次数为

7． 将一棵树t 转换为孩子兄弟链表表示的二叉树h ，则t 的后序遍历是h 的（ ）。

A. 前序遍历 B. 中序遍历 C. 后序遍历 【答案】B

【解析】树的后序遍历恰好对应于二叉树的中序遍历。

为（ ）。

那么

8． 某计算机主频为1.2GHz ，其指令分为4类，它们在基准程序中所占比例及CPI 如下表所示。

该机的MIPS 数是（ ）

A.100 B.200 C.400 D.600

【答案】C

【解析】基准程序的

计算机的主频为

为1200MHz ，

该机器的

9． 在对n 个元素的序列进行排序时，堆排序所需要的附加存储空间是（ ）。

【答案】B

【解析】堆排序需要一个空间用于交换，因此堆排序所需要的附加存储空间为

10．对有2个顶点e 条边且使用邻接表存储的有向图进行广度优先遍历，其算法时间复杂度是（ ）。

A. B. C. D. 【答案】C 。

【解析】遍历图的过程实质上是对每个顶点查找其邻接点的过程。其耗费的时间则取决于所采用的存储结构。当用二维数组表示邻接矩阵图的存储结构时，查找每个顶点的邻接点所需时间

为

其中n 为图中顶点数。而当以邻接表作图的存储结构时，找邻接点所需时间为

即可得出正确答案。

其

中e 为无向图中边的数或有向图中弧的数。由此，当以邻接表作存储结构时，深度优先搜索遍历图的时间复杂度为

二、填空题

11．A 是一个任意给定的整数。free_tree设T 是一棵结点值为整数的二叉排序树，在下面的算法中，（T ）在对二叉排序树丁进行后序遍历时释放二又排序树T 的所有结点；

首

先在二叉排序树T 中查找值为A 的结点，根据查找情况分别进行如下处理：（1）若找不到值为A 的结点，则返回根结点的地址（2）若找到值为A 的结点，则删除以此结点为根的子树，并释放此子树中的所有结点，若值为A 的结点是查找树的根结点，删除后变成空的二叉树，则返否则返回根结点的地址。

【答案】

12．当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用_____存储结构。

【答案】顺序

【解析】顺序存储结构的存取操作比较方便，但插入和删除操作不如链式存储结构方便，而且需要连续的存储空间，由于该线性表的元素总数基本稳定，而且很少进行插入删除操作，为了更快的存取元素，顺序表更合适。

13．实现字符串拷贝的函数strcpy 为：

【答案】

14．数据结构是研讨数据的_____和_____以及它们之间的相互关系，并对与这种结构定义相应的_____，设计出相应的_____。

；算法 【答案】逻辑结构；物理结构；操作（运算）

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

【答案】

16．设正文串长度为n ，模式串长度为m ，则串匹配的KMP 算法的时间复杂度为_____。

【答案】

17．己知有序表为（12，18，24，35，47，50，62，83，90，115，134）当用二分法查找90时，需_____次查找成功，查找47时_____成功，查找100时，需_____次才能确定不成功。

【答案】2；4；3

【解析】二分法查找元素次数列表

查

找100是找到115就停止了。

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

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

三、应用题

19．为什么在倒排文件组织中，实际记录中的关键字域可删除以节约空间? 而在多重表结构中这样做为什么要牺牲性能？

【答案】因倒排文件组织中，倒排表有关键字值及同一关键字值的记录的所有物理记录号，可方便地查询具有同一关键字值的所有记录；而多重表文件中次关键字索引结构不同，删除关键字域后查询性能受到影响。

20．在树和树中查找关键字时，有什么不同？

【答案】在树中查找关键字从根结点开始，从根往下查找结点，然后在结点内查找关键字，得出查找成功与否的结论。

树的非终端结点是索引部分，其查找从根开始，从根往下查到关键

. 树还可以在最下层从最小关

字后，要继续查到最下层结点，得到查找成功与否的结论。另外，键字开始，从左往右进行顺序查找，B-树则不能作顺序查找。

21．如果两个串含有相等的字符，能否说它们相等？

【答案】仅从两串含有相等的字符，不能判定两串是否相等，两串相等的充分必要条件是两串长度相等且对应位置上的字符相同（即两串串值相等）。

22．KMP 算法（字符串匹配算法）较Brute （朴素的字符串匹配）算法有哪些改进？

【答案】朴素的模式匹配度达到

时，KMP 算法的优点更为突出。

时间复杂度是KMP 算法有一定改进，时间复杂

主要优点是主串指针不回溯。当主串很大不能一次读入内存且经常发生部分匹配

四、算法设计题

23．已知无向图采用邻接表存储方式，试写出删除边（i ，j ）的算法。

【答案】算法如下：

//在用邻接表方式存储的无向图g 中，刪除边（i , j ）

//删顶点i 的边结点（i , j ）pre 是前驱指针

释

放空间

//

//释

放空间

//沿链表继续査找

24．从键盘上输入一串正整数，最后输入-1作为结束标志。如：

请设计一个非递归程序，创建一棵二叉排序树，并且该二叉排序树也必须是中序线索二叉树。设该二叉排序树上的结点结构为那么

序遍历次序的前驱结点的地址。

那么

【答案】算法如下：

沿链表继续查找

//删顶点j 的边结点（j , i ）

其中：域为结点的数据场。

域中存在的是该结点的左儿子结点的地址。ltag=1，那么left 域中存放的是该结点的按中

那么right 域中存放的是该结点的右儿子结点的地址。

域中存放的是该结点的按中序遍历次序的后继结点地址。