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

一、填空题

1． 在单链表L 中，指针P 所指结点有后继结点的条件是_____

【答案】P ﹣＞next! ＝NULL

【解析】指针所指节点的指针域所指向的元素非空，说明该指针所指节点有后继结点。

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

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

3． 在基于关键字比较且时间为

【答案】归并；堆

4． 设单链表的结点结构为(data，next) ，next 为指针域，已知指针px 指向单链表中data 为x 的结点，指针py 指向data 为y 的新结点，若将结点y 插入结点x 之后，则需要执行以下语句: _____；_____；

【答案】py ﹣＞next ＝px ﹣＞next ；px ﹣＞next ＝py

5． 二进制地址为011011110000, 大小为

【答案】011011110100；011011100000

【解析】011011110000是块的起始地址，大小分别为算公式如下:

当大小为4时，起始地址为011011110000+0100。当大小为16时，起始地址为:011011110000-010000。

6． 对n 个记录的表进行简单选择排序，所需进行的关键字间的比较次数为_____。

【答案】n (n－1) /2

【解析】第一次需要n －1次比较，第i 此需要n －i 此比较，所以共需要

。

和

其伙伴块的起始地址计

和

块的伙伴地址分别为:_____

_ 的排序中，若要求排序是稳定的，则可选用_____

排序；若要求就地排序(及辅助空间为O(1))，则可选用_____排序。

7． 已知一循环队列的存储空间为则此循环队列判满的条件是_____

【答案】

，其中n ＞m ，队头和队尾指针分别为front 和rear ，

8． 索引顺序文件既可以顺序存取，也可以 _____存取。

【答案】随机

9． 设二维数组A 的行和列的下标范围分别为[0:8]和[0:10]，每个元素占2个单元，按行优先顺序存储，第一个元素的存储起始位置为b ，则存储位置为b+50处的元素为_____。

【答案】A[2][3]

【解析】令这个元素的行标为i ，列标为j 。则它的存储位置是(ll*i＋j ＋l ﹣l)*2＋b 。当其值为b ＋50时，则i ＝2，j ＝3。

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

(_____)

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

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

【答案】23；100CH

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

；

，首先在二叉排序树T 中查找值为A 的结点，根据查找情况分别进行如下

处理:(1)若找不到值为A 的结点，则返回根结点的地址(2)若找到值为A 的结点，则删除以此结点为根的子树，并释放此子树中的所有结点，若值为A 的结点是查找树的根结点，删除后变成空的二叉树，则返NULL ; 否则返回根结点的地址。

【答案】

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

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

)

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

的值在

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

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

生成树的边结点

边的起点与终点

边上的权值

最小生成树定义

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

初始化最小生成树

T

依次求MST 的候选边

遍历当前候选边集合

选具有最小权值的候选边

图不连通，出错处理

中