2018年甘肃省培养单位寒区旱区环境与工程研究所864程序设计之数据结构考研强化五套模拟题
● 摘要
一、填空题
1. 数据结构是研讨数据的_____和_____以及它们之间的相互关系,并对与这种结构定义相应的_____, 设计出相应的_____。
【答案】逻辑结构;物理结构;操作(运算) ;算法
2. 阅读下列程序说明和程序,填充程序中的_____。
【程序说明】本程序完成将二叉树中左、右孩子交换的操作。交换的结果如下所示。 本程序采用非递归的方法,设立一个堆栈stack 存放还没有转换过的结点,它的栈顶指针为tp 。交换左、右子树的算法为:
(1)把根结点放入堆栈。
(2)当堆栈不空时,取出栈顶元素,交换它的左、右子树,并把它的左、右子树分别入栈。 (3)重复(2)直到堆栈为空时为止。
【答案】
【解析】本题主要使用堆栈完成了二叉树左右子树交换的操作。首先根结点进栈,然后判断栈是否为空,如果不为空,则取栈顶元素,交换取出结点的左右指针。并将左右指针分别进栈,重复这一操作。完成二叉树左右孩子的交换。
3. —个有2001个结点的完全二叉树的高度是_____。
【答案】11
【解析】完全二叉树的高度
4. 对于给定的元素,可以构造出的逻辑结构有_____,_____,_____,_____四种。
【答案】集合;线性结构;树形结构;图状结构(网状结构)
5. 根据线性表的链式存储结构中每一个结点包含的指针个数,将线性链表分成_____和_____;而又根据指针的连接方式,链表又可分成_____和_____。
【答案】单链表;双链表;(动态) 链表;静态链表
【解析】线性表的链式存储结构根据每个结点包含的指针个数分为单链表和双链表,单链表只包含一个指针,指向后续元素,双链表包括两个指针,指向前一个元素和后续元素。根据指针的连接方式,链表可分为动态链表和静态链表。静态链表的指针指向下一个元素的编号,动态链表的指针指向下一个元素的物理位置。
6. 试利用下列栈和串的基本操作完成下述填空题。
initstack(S)置S 为空栈; push(S,X) 元素X 入栈; pop(S)出栈操作; gettop(S)返回栈顶元素; sempty(S)判栈空函数; setnull(St)置串St 为空串; length(st)返回串st 的长度;
equal(S1,S 2) 判串S 1并S 2是否相等的函数; concat(S1,S 2) 返回联接S 1和S 2之后的串; sub(S,i ,1) 返回S 中第i 个字符; empty(st)判串空函数
FUNCinvert(pre:string ;V ARexp :string) :boolean ;
{若给定的表达式的前缀式pre 正确,本过程求得和它相应的表达式exp 并返回true ,否则exp 为空串,并返回false 。已知原表达式中不包含括弧,opset 为运算符的集合。
)
_____;_____;
_____THEN_____
IF_____THEN_____
(_____,_____);
(_____,_____);
_____
_____THEN
注意:每个空格只填一个语句。
【答案】(1)initstack(S)//栈s 初始化为空栈 (2)setnull(exp)//串exp 初始化为空串 (3)chinopset//判取出字符是否是操作符
(4)push(s,ch)//如ch 是运算符,则入操作符栈s (5)sempty(s)//判栈s 是否为空
(6)succ:=false//若读出ch 是操作数且栈为空,则按出错处理 (7)exp
(8)ch//若ch 是操作数且栈非空,则形成部分中缀表达式 (9)exp
(10)gettop(s)//取栈顶操作符 (11)pop(s)//操作符取出后,出栈
(12)sempty(s)//将pre 的最后一个字符(操作数) 加入到中缀式exp 的最后
7. VSAM 系统是由_____、_____、_____构成的。
【答案】索引集;顺序集;数据集
8. 顺序存储结构是通过_____表示元素之间的关系的;链式存储结构是通过_____表示元素之间的关系的。
【答案】物理上相邻;指针
【解析】顺序存储结构是通过物理位置表示元素之间的关系的,链式存储结构通过指针表示元素之间的关系。
9. 如某二叉树有20个叶结点,有30个结点仅有一个孩子,则该二叉树的总结点数为_____。
【答案】69
【解析】二叉树叶结点数为20, 则度为2的结点数为19, 所以总的结点数为20+19+30=69。
10.在单链表L 中,指针P 所指结点有后继结点的条件是_____
【答案】P ﹣>next! =NULL
【解析】指针所指节点的指针域所指向的元素非空,说明该指针所指节点有后继结点。
二、单项选择题