2017年北京交通大学计算机与信息技术学院926数据结构与软件工程之数据结构考研冲刺密押题
● 摘要
一、填空题
1．
设单链表的结点结构为
为指针域，已知指针px 指向单链表中data 为x 的结
_____；点，指针py 指向data 为y 的新结点，若将结点y 插入结点x 之后，贝懦要执行以下语句：
_____;
【答案】
2． 顺序存储结构是通过_____表示元素之间的关系的；链式存储结构是通过_____表示元素之间的关系的。
【答案】物理上相邻；指针
【解析】顺序存储结构是通过物理位置表示元素之间的关系的，链式存储结构通过指针表示元素之间的关系。
3． 实现字符串拷贝的函数strcpy 为：
【答案】
4． 已知二叉排序树的左右子树均不为空，则_____上所有结点的值均小于它的根结点值，_____上所有结点的值均大于它的根结点的值。
【答案】左子树；右子树 【解析】二叉排序树
或者是一棵空树，或者是具有下列性质的二叉树：①若它
的左子树不空，则左子树上所有结点的值均小于它的根结点的值；②若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；③它的左、右子树也分别为二叉排序树。
5． 组成串的数据元素只能是_____。
【答案】字符
6． 在哈希函数中，P 值最好取_____。
【答案】小于等于表长的最大素数或不包含小于20的质因子的合数
【解析】在使用除留余数法时，对除数P 的选择很重要。若P 选的不好，容易产生同义词。一般情况下，可以选P 为质数或不包含小于20的质因素的合数。
7． 当两个栈共享一存储区时，栈利用一维数组表示，两栈顶指针为当栈1空时，
【答案】
为_____，栈2空时
，
为_____，栈满时为_____。
则
【解析】共享栈的栈底在共享存储区的两端，当栈满时栈顶相邻。
8． 二叉树由_____，_____，_____三个基本单元组成。
【答案】根结点；左子树；右子树
9． 在二叉树中，指针p 所指结点为叶结点的条件是_____。
【答案】
【解析】叶子节点的左右孩子都不存在。
10．若不考虑基数排序，则在排序过程中，主要进行的两种基本操作是关键字的_____和记录的_____，
【答案】比较；移动
11．在进行入栈运算时应先判别栈是否_____:在进行出栈运算时应先判别栈是否_____:当栈中元素为n 个，进行入栈运算时发生上溢，则说明该栈的最大容量为_____。为了增加内存空间的利用率和减少溢出的可能性，由两个栈共享一片连续的空间时，应将两栈的_____分别设在内存空间的两端，这样只有当_____时才产生溢出。
【答案】满；空；n ; 栈底；两栈顶指针相邻（即值之差的绝对值为1）
12．有向图G=（V ，E ）, 其中V （G ）=[0, 1，2，3，4, 5}, 用
【答案】50; 4
13．VSAM 系统是由_____、_____、_____构成的。
【答案】索引集；顺序集；数据集
14．下面描述的是一种构造最小生成树算法的基本思想。设要处理的无向图包括n
个顶点
用相邻矩阵A 表示，边的权全是正数。请在下列划线处填上正确叙述。
（1）若
是边，则
的值等于_____，若
不是边，则
的值是一个比任
何边的权，矩阵的对角线元素全为0。
（2）构造最小生成树过程中，若顶点Vi 已包括进生成树，就把相邻矩阵的对角线元素A （i , i ）置成若
【答案】（1）
已包括进生成树，就把矩阵元素A （i ，j ）置成。 边上的权值；都大的数；（2）1; 负值；（3）为负；边
和
每个元素占2个单元，按行优先顺处的元素为_____。
当其值为
（3）算法结束时，相邻矩阵中的元素指出最小生成树的
15．设二维数组A 的行和列的下标范围分别为
【答案】时，则i=2，j=3。
序存储，第一个元素的存储起始位置为b ，则存储位置为
【解析】令这个元素的行标为i ，列标为j 。则它的存储位置是
二、选择题
16．4个圆盘的Hanoi 塔，总的移动次数为（ ）。 A.7 B.-8 C.15 D.16
【答案】C 【解析】Hanoi 问题总移动次数为：次。
17．下列四个序列中，哪一个是堆（ ）？
A.75，65，30，15，25，45，20，10 B.75，65，45，10，30，25，20，15 C.75，45，65，30，15，25，20，10 D.75，45，65，10，25，30，20，15
【答案】C
【解析】堆的定义： n 个关键字序列
且
且
称为堆，当且仅当该序列满足如下性质（简称为堆性质）：
小根堆：满足第①种情况的堆； 大根堆：满足第②种情况的堆。 根据堆定义即可得出答案。