2017年北京联合大学数字艺术803软件基础之数据结构考研冲刺密押题
● 摘要
一、填空题
1． 如下的算法分别是后序线索二叉树求给定结点node 的前驱结点与后继结点的算法，请在算法
，其空格处填上正确的语句。设线索二叉树的结点数据结构为（lflag ，lcft ，data ，right ，rflag ）
中：lflag=0，lcft 指向其左孩子，lflag=1，left 指向其前驱：rflag=0，right 指向其右孩子，rflag=1，right 指向其后继。
Prior （node , x ）
{ if（node !=null）
If （ （1） ） *x=node->right；else * x-node->left;
}
next （bt , node, x ）/*bt是二叉树的树根*/
{ （2） ;
if （node->rflag）（3）;
else {do t=*x；;
while （*x==node ）;
*x=t;
}
}
【答案】nodc->rflag==O; *x=ht; *x=nodc->right; prior （t , X ）
2． 数组的存储结构采用_____存储方式。
【答案】顺序存储结构
【解析】数组本身的存储结构是线性的，也就是说它是连续存储的。
3． 假设一个15阶的上三角矩阵A 按行优先顺序压缩存储在一维数组B 中，则非零元素中的存储位置k=_____。（注：矩阵元素下标从1开始）
【答案】93
【解析】对于上三角矩阵
， 将代入得93。 在B
4． 设数组
储，则元素
为_____。
【答案】9174；8788 的基地址为2000，每个元素占2个存储单元，若以行序为主序顺序存的存储地址为_____；若以列序为主序顺序存储，则元素的存储地址
【解析】设一个元素的行标为i ，列标为j 。若以行序为主存储顺序，
则它的存储地址为
若以列序为主存储顺序，则它的存储地址为
5． 有五个数据依次入栈：1，2, 3, 4, 5。在各种出栈的序列中，以3, 4先出栈的序列有_____。（3在4之前出栈）
【答案】3个
【解析】以3, 4先出栈的序列有34521、34215、34251共3个。
6． 空格串是指_____，其长度等于_____。
【答案】由空格字符（值32）所组成的字符串；空格个数
7． 深度为H 的完全二叉树至少有_____个结点; 至多有_____个结点; H 和结点总数N 之间的关系是_____。 【答案】
8． 数据结构是研讨数据的_____和_____以及它们之间的相互关系，并对与这种结构定义相应的_____，设计出相应的_____。
；算法 【答案】逻辑结构；物理结构；操作（运算）
9． —棵有个结点的满二叉树有_____个度为1的结点、有_____个分支（非终端）结点和_____个叶子，该满二叉树的深度为_____。 【答案】
或
【解析】满二叉树没有度为1的结点，度为0的结点等于度为2的结点个数+1。
10．下面描述的是一种构造最小生成树算法的基本思想。设要处理的无向图包括n
个顶点
用相邻矩阵A 表示，边的权全是正数。请在下列划线处填上正确叙述。
（1）若是边，则的值等于_____，若不是边，则的值是一个比任何边的权，矩阵的对角线元素全为0。
（2）构造最小生成树过程中，若顶点Vi 已包括进生成树，就把相邻矩阵的对角线元素A （i , i ）置成若
【答案】（1）
已包括进生成树，就把矩阵元素A （i ，j ）置成。 边上的权值；都大的数；（2）1; 负值；（3）为负；边 （3）算法结束时，相邻矩阵中的元素指出最小生成树的
二、选择题
11．在一棵度为4的树T 中，若有20个度为4的结点，10个度为3的结点，1个度为2的结点，10个度为1的结点，则树T 的叶结点个数是（ ）。
A.41
B.82
C.113
D.122
【答案】B
【解析】根据二叉树的性质3的推广公式：
入公式，
即可直接在将数据带树T 的叶子结点的个数是82。如果考生不能熟练掌握二叉树的性质3的推广公式，得到本题的正确答案将费时费力。因此，需要熟练掌握二叉树的性质及推广。
12．某同步总线采用数据线和地址线复用方式。其中地址数据线有8根，总线时钟频率为66MHZ , 每个时钟同期传送两次数据。（上升沿和下降沿各传送一次数据）该总线的最大数据传输率是（总线带宽）（ ） ：
A. B. C. D.
【答案】C
【解析】总线带宽=总线工作频率X （总线宽度/8）, 由于地址线与数据线复用，所以在两次数据传输过程中总线上数据一共传输了8次，那么总线带宽为
13．以下说法错误的是（ ）。
（1）算法原地工作的含义是指不需要任何额外的辅助空间
（2）在相同的规模n 下，复杂度的算法在时间上总是优于复杂度的算法
（3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界
（4）同一个算法，实现语言的级别越高，执行效率就越低
A. （1）
B. （1）, （2）
C. （1）, （4）
D. （3）
【答案】A
【解析】算法原地工作的含义不是指不需要任何额外的辅助，而是算法所需要的辅助空间不随着问题的规模而变化，是一个确定的值。
14．在下列表述中，正确的是（ ）
A. 含有一个或多个空格字符的串称为空格串
所以选C