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

一、填空题

1． 一个算法具有5个特性：_____、_____、_____、有零个或多个输入、有一个或多个输出。

【答案】有穷性；确定性；可行性

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

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

3． 有向图G=（V ，E ）, 其中V （G ）=[0, 1，2，3，4, 5}, 用三元组表示弧及弧上的权d 。 E （G ）为 E （G= {<0，5, 100>, <0，2，10>, <1，2，5>，<0，4, 30>，<4, 5, 60>，<3，5, 10>，<2. 3，50>， <4, 3, 20>}，则从源点0到顶点3的最短路径长度是_____，经过的中间顶点是_____。

【答案】50; 4

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

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

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

【答案】

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

【答案】23; 100CH

7． 以下是用类C 语言写山的算法，该算法将以二叉链表存储的二叉树中的叶结点按从左到右的顺序链成一个带头结点的双向循环链表，链接时，结点的Lchild 域作为前链域，指向结点的直接前驱，结点的Rchild 域作为后链域，指向结点的直接后继。算法中，使用一个顺序栈stack , 栈顶

head 为双向循坏链表的头指针。 指针为top , P , t 为辅助指针，试填充算法中的空格，使算法完整。

void leafchain（BiTree Abt）

{p={BiTree）malloc （sizeof （BiTNode ））;

If （!p ）{print£（“OVERFLOW\n”; 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:

p->Rchild=head:head->Lchild=p

8． 求图的最小生成树有两种算法，_____算法适合于求稀疏图的最小生成树e

【答案】克鲁斯卡尔

【解析】克鲁斯卡尔算法是一种按权值的递增次序选择合适的边来构造最小生成树的方法，这种算法中，采用堆来存放边的集合，适合于边稀疏而顶点较多的图。

9． 已知如下程序段：

语句1执行的时间复杂度为_____；语句2执行的时间复杂度为_____；语句3执行的时间复杂度为_____；语句4执行的时间复杂度为_____。

【答案】（1）n ＋1

（2）n

（3）n （n ＋3）/2

（4）n （n ＋l ）/2

【解析】语s 句1执行到不符合条件情况下，执行了n ＋1次。当语句1不符合条件了是不会执行语句2的，所以语句2被执行了n 次。语句3每次都要执行到不符合条件，故为2＋3＋4...... ＋（n ＋l ）加起来就是n （n ＋3）/2。语句3不符合条件了是不会执行语句4的。所以语句4被执行了1＋2＋3...... ＋n 即n （n ＋l ）/2。

t->Lchild:

10．G 是一个非连通无向图，共有28条边，则该图至少有_____个顶点。

【答案】9

【解析】求该非连通无向图的最少顶点数，则该图为一个孤立的顶点和一个完全连通图。

11．设T 和P 是两个给定的串，在T 中寻找等于P 的子串的过程称为_____，又称P 为_____。

【答案】模式匹配；模式串

12．串是一种特殊的线性表，其特殊性表现在_____; 串的两种最基本的存储方式是_____、_____; 两个串相等的充分必要条件是_____。

【答案】其数据元素都是字符；顺序存储；链式存储；串的长度相等且两串中对应位置的字符也相等

二、选择题

13．float 类型（即IEEE754单精度浮点数格式）能表示的最大正整数是（ ）。 A.

B.

C.

D.

【答案】D 。

【解析】IEEE754单精度浮点数尾数采用隐藏位策略的原码表示，且阶码用移码表示的浮点数。规格化的短 浮点数的真值为：

故float 类型能表示的最大整数是

14．算法的计算量的大小称为计算的（ ）。

A. 效率

B. 复杂性

C. 现实性

D. 难度

【答案】B

【解析】算法复杂度通常分为时间复杂度和空间复杂度，算法的计算量的大小可以用时间复杂度衡量，即可以称为计算的复杂度。

15．在系统内存中设置磁盘缓冲区的主要目的是（ ）。

A. 减少磁盘I/O次数

B. 减少平均寻道时间

C. 提高磁盘数据可靠性

D. 实现设备无关性

S 为符号位，E 的取值为 f 为23位；