2018年北方民族大学计算机系统结构832C语言程序设计与数据结构之数据结构考研仿真模拟五套题
● 摘要
一、填空题
1． 文件可按其记录的类型不同而分成两类，即 _____和_____文件。
【答案】操作系统文件；数据库
2． 检索是为了在文件中寻找满足一定条件的记录而设置的操作。检索可以按_____检索。也可以按_____检索；按_____检索又可以有
检索和_____检索。
【答案】关键字；记录号；记录号；顺序；直接
3． 若不考虑基数排序，则在排序过程中，主要进行的两种基本操作是关键字的 _____和记录的_____。
【答案】比较；移动
4． 分别采用堆排序，快速排序，起泡排序和归并排序，对初态为有序的表，则最省时间的是_____算法，最费时间的是_____算法。
【答案】起泡；快速
【解析】当初态为有序表时，冒泡排序只需要进行一趟比较即可，此时时间复杂度为O(n)，
2
而快速排序算 法需要比较的次数达到最大，时间复杂度为O (n) 。
5． 表达式23＋((12*3﹣2)/4＋34，5/7) ＋108/9的后缀表达式是_____。
【答案】(表达式中的点(.)是数分隔符，如是三个数)
6． 在一棵m 阶B-树中，若在某结点中插入一个新关键字而引起该结点分裂，则此结点中原有的关键字的个数是_____; 若在某结点中删除一个关键字而导致结点合并，则该结点中原有的关键字的个数是_____。
【答案】
【解析】m 阶B-树除根结点和叶子结点外，结点中关键字个数最多是m －1，最少
7． 阅读下列程序说明和程序，填充程序中的_____。
【程序说明】本程序完成将二叉树中左、右孩子交换的操作。交换的结果如下所示。 本程序采用非递归的方法，设立一个堆栈stack 存放还没有转换过的结点，它的栈顶指针为tp 。交换左、右子树的算法为:
(1)把根结点放入堆栈。
(2)当堆栈不空时，取出栈顶元素，交换它的左、右子树，并把它的左、右子树分别入栈。 (3)重复(2)直到堆栈为空时为止。
【答案】
【解析】本题主要使用堆栈完成了二叉树左右子树交换的操作。首先根结点进栈，然后判断栈是否为空，如果不为空，则取栈顶元素，交换取出结点的左右指针。并将左右指针分别进栈，重复这一操作。完成二叉树左右孩子的交换。
8． 试利用下列栈和串的基本操作完成下述填空题。
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 的最后
9． 设有一个10阶对称矩阵A 采用压缩存储方式(以行为主序存储:a 11＝l) ， 则a 85的地址为_____。
【答案】33
【解析】设存储的元素的行标为i ，列标为j 。若i ＞＝j ，则
的地址为l ＋2＋... ＋i ﹣l ＋j
＝i(i﹣l)/2＋j 。若i ＜j 。则的地址为j(j﹣l)/2＋i 。将i ＝8，j ＝5代入得33。
10．完善算法:求KMP 算法.next 数组。
k :＝_____；next[1]:＝0；
k :＝_____；
相关内容
相关标签