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

一、填空题

1． 实现字符串拷贝的函数strcpv 为:

(_____)

【答案】s++＝*t++或(*s++＝*t++)!＝'\0’

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

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

3． 顺序存储结构是通过_____表示元素之间的关系的；链式存储结构是通过_____表示元素之间的关系的。

【答案】物理上相邻；指针

【解析】顺序存储结构是通过物理位置表示元素之间的关系的，链式存储结构通过指针表示元素之间的关系。

4． 从平均时间性能而言，_____排序最佳。

【答案】快速

【解析】快速算法的平均时间复杂度为nlogn 。

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

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

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

【答案】

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

【答案】2; 4; 3

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

查找100是找到115就停止了。

8． 顺序栈用存储数据，栈顶指针是top ，则值为x 的元素入栈的操作是_____。

【答案】if(top!＝n)data[++top]＝x ；

【解析】先判断栈是否满，如果不满，元素入栈。否则返回溢出信息。

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

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

10．阅读下列程序，指出其功能，并写出空格处应填上的语句。

【答案】

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

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

12．已知二维数组

【答案】1196

【解析】设元素的行标为i ，列标为j 。则它的存储位置为:l000＋[(i﹣l)*l0＋(j﹣0)]*4

中每个元素占4个单元，在按行优先方式将其存储到起始地址

为1000的连续存储区域时，A[5，9]的地址是: _____。

13．分别采用堆排序，快速排序，起泡排序和归并排序，对初态为有序的表，则最省时间的是_____算法，最费时间的是_____算法。

【答案】起泡；快速

【解析】当初态为有序表时，冒泡排序只需要进行一趟比较即可，此时时间复杂度为O(n)，

2

而快速排序算 法需要比较的次数达到最大，时间复杂度为O (n) 。

14．栈是_____的线性表，其运算遵循_____的原则。

【答案】操作受限(或限定仅在表尾进行插入和删除操作) ；后进先出

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

(1)针对如图所示的连通网络，试按如下格式给出在构造最小生成树过程中顺序选出的各条边。(始顶点号，终顶点号，权值

)

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

的值在

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

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

生成树的边结点

边的起点与终点

边上的权值

最小生成树定义

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

初始化最小生成树

T

依次求MST 的候选边

遍历当前候选边集合

中