2017年武汉大学卫星导航定位技术研究中心942数据结构考研导师圈点必考题汇编
● 摘要
目录
2017年武汉大学卫星导航定位技术研究中心942数据结构考研导师圈点必考题汇编（一）.... 2 2017年武汉大学卫星导航定位技术研究中心942数据结构考研导师圈点必考题汇编（二）.. 12 2017年武汉大学卫星导航定位技术研究中心942数据结构考研导师圈点必考题汇编（三）.. 21 2017年武汉大学卫星导航定位技术研究中心942数据结构考研导师圈点必考题汇编（四）.. 32 2017年武汉大学卫星导航定位技术研究中心942数据结构考研导师圈点必考题汇编（五）.. 41
第 1 页，共 51 页
一、填空题
1． 对于给定的元素，可以构造出的逻辑结构有_____，_____，_____，_____四种。
【答案】集合；线性结构；树形结构；图状结构（网状结构）
2． 在单链表L 中，指针P 所指结点有后继结点的条件是_____
【答案】
【解析】指针所指节点的指针域所指向的元素非空，说明该指针所指节点有后继结点。
3． 抽象数据类型的定义仅取决于它的一组_____，而与_____无关, 即不论其内部结构如何变化，只要它的_____不变，都不影响其外部使用。
【答案】逻辑特性；在计算机内部如何表示和实现；数学特性
4． 克鲁斯卡尔算法的时间复杂度为_____，它对_____图较为适合。
【答案】O （eloge ）; 边稀疏
5． 二叉树由_____，_____，_____三个基本单元组成。
【答案】根结点；左子树；右子树
6． 一个算法具有5个特性：_____、_____、_____、有零个或多个输入、有一个或多个输出。
【答案】有穷性；确定性；可行性
7． —棵深度为k 的平衡二叉树， 其每个非终端结点的平衡因子均为0，则该树共有_____个结点。
【答案】树。故结点个数为
8． 已知二维数组
【答案】1196
【解析】设元素的行标为i ，列标为j 。则它的存储位置为：
9． 在哈希函数中，P 值最好取_____。
【答案】小于等于表长的最大素数或不包含小于20的质因子的合数
第 2 页，共 51 页
中每个元素占4个单元，在按行优先方式将其存储到起始地址的地址是：_____。
【解析】每个非终端结点都是0表示该平衡二叉树没有高度落差。也就是说它是一棵满二叉
为1000的连续存储区域时
，
【解析】在使用除留余数法时，对除数P 的选择很重要。若P 选的不好，容易产生同义词。一般情况下，可以选P 为质数或不包含小于20的质因素的合数。
10．VSAM 系统是由_____、_____、_____构成的。
【答案】索引集；顺序集；数据集
11．试利用下列栈和串的基本操作完成下述填空题。
initstack （S ） 置S 为空找； push （S , X ） 元素X 入找； pop （S ） 出栈操作； gettop （S ） 返回栈顶元素； sempty （S ） 判找空函数；
置串 判串 返回联接
empty （st ） 判串空函数
{若给定的表达式的前缀式pre 正确，本过程求得和它相应的表达式exp 并返回true , 否则exp 为空串，并返回false 。已知原表达式中不包含括弧，opset 为运算符的集合。）
注意：毎个空格只填一个语句。 【答案】（1）
栈S 初始化为空栈
第 3 页，共 51 页
为空串；
是否相等的函数；
之后的串；
length （st ） 返回串st 的长度；
sub （S , i , 1） 返回S 中第i 个字符；
（2）（3）（4）（5）（6）（7）exp （8）（9）exp （10）（11
）（12）
串exp 初始化为空串 判取出字符是否是操作符
如ch 是运算符，则入操作符栈s 判栈8是否为空
若读出ch 是操作数且栈为空，则按出错处理
若ch 是操作数且栈非空，则形成部分中缀表达式
取栈顶操作符 操作符取出后，出栈
将pre 的最后一个字符（操作数）加入到中缀式exp 的最后
和
每个元素占2个单元，按行优先顺处的元素为_____。
当其值为
12．设二维数组A 的行和列的下标范围分别为
【答案】时，则i=2，j=3。
序存储，第一个元素的存储起始位置为b ，则存储位置为
【解析】令这个元素的行标为i ，列标为j 。则它的存储位置是
二、选择题
13．设无向图的顶点个数为m 则该图最多有（ ）条边。 A.n-1
B.n （n-l ）/2
C.n （n+l）/2 D.0 E.n2
【答案】B
【解析】在数据结构中仅讨论简单图，在计算无向图的最多边时，不考虑顶点与顶点的边。因此边数最多时，构成的是无向完全图。此时的边数为n （n-l ）/2。
14．—个具有1025个结点的二叉树的高h 为（ ）。
A.11 B.10
C.11至1025之间
D.10至1024之间 【答案】C
【解析】当一棵树是完全二叉树时，其高度最低，此时高度为11，当一棵树的结点在一条线上时，此时最高，这时二叉树的高度是1025。
第 4 页，共 51 页
相关内容
相关标签