2018年北方民族大学计算机技术833C语言程序设计与数据结构之数据结构考研仿真模拟五套题
● 摘要
一、填空题
1． 设有一个空枝，栈顶指针为1000H(十六进制) ，现有输入序列为1，2，3，4，5，经过PUSH ，PUSH ，POP ，PUSH ，POP ，PUSH ，PUSH 之后，输出序列是_____，而栈顶指针值是_____。设栈为顺序找，每个元素占4个字节。
【答案】23；100CH
2． 完善算法:求KMP 算法.next 数组。
k :＝_____；next[1]:＝0；
k :＝_____；
END ；
【答案】0；next[k]
3． 从用户的观点看，文件的逻辑结构通常可以区分为两类:一类是如NdBASE 中数据库文件那样的文件组织结构，称为_____文件; 另一种是诸如用各种文字处理软件编辑成的文本文件，称为_____文件。从文件在存储器上的存放方式来看，文件的物理结构往往可区分为三类，即_____， _____和_____。B+树适用于组织_____的索引结构，m 阶B+树毎个结点至多有_____个儿子，除根结点外每个结点至少有_____个儿子，根结点至少有_____个儿子，有k 个儿子的结点必有_____个关键码。
【答案】数据库；文本；顺序组织；随机组织；链组织；随机组织；m ;
4． 克鲁斯卡尔算法的时间复杂度为_____，它对_____图较为适合。 【答案】；边稀疏
5． 关键码序列(Q，H ，C ，Y ，Q ，A ，M ，S ，R ，D ，F ，X) ，要按照关键码值递增的次序进行排序，若采用初始步长为4的希尔排序法，则一趟扫描的结果是_____; 若采用以第一个元素为分界元素的快速排序法，则扫描一趟的结果是_____。
【答案】(Q，A ，C ，S ，Q ，D ，F ，X ，R ，H ，M ，Y) ; (F，H ，C ，D ，a ，A ，M ，Q ，R ，S ，Y ，X)
；2；k
【解析】希尔排序的基本思想是:先将整个待排记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。
快速排序(quick sort) 的基本思想是，通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
6． 已知t) ，LEN(t)＋1))
:
【答案】 ；；ASSIGN(S，U) ；ASSIGN(V，SUBSTR(S，INDEX(S，，求REPLACE(S，V ，m) ＝_____。
7． 索引顺序文件既可以顺序存取，也可以 _____存取。
【答案】随机
8． 当两个栈共享一存储区时，栈利用一维数组stack(1，，1) 表示，两栈顶指针为top[l]与top[2]，则当栈1空时，top[l]为_____，栈2空时，top[2]为_____，栈满时为_____。
【答案】0；n+1；top[l]+l＝top[2]
【解析】共享栈的栈底在共享存储区的两端，当栈满时栈顶相邻。
9． 一个算法具有5个特性: _____、_____、_____、有零个或多个输入、有一个或多个输出。
【答案】有穷性；确定性；可行性
10．每一棵树都能唯一地转换为它所对应的二叉树。若已知一棵二叉树的前序序列是BEFCGDH ，中序序列是FEBGCHD ，则它的后序序列是_____。设上述二叉树是由某棵树转换而成，则该树的前序序列是_____
【答案】FEGHDCB ；BEF
【解析】树的前序序列对应二叉树的前序序列，该二叉树转换成森林时含三棵树，其第一棵树的前序是BEF 。
二、判断题
11．设栈采用顺序存储结构。若已有i-1个元素入栈，则将第i 个元素入栈时，入栈算法的时间复杂性为O(i)。（ ）
【答案】 ×
【解析】由于该栈采用顺序存储结构，时间复杂度应该为O(1)。
12．对处理大量数据的外存介质而言，索引顺序存取方法是一种方便的文件组织方法。（ ）
【答案】×
【解析】索引顺序存取方法插入操作比较麻烦，对于处理大量数据，会有大量的记录进入溢
出区，而基本区中又浪费很多空间。
13．在二叉排序树中插入一个新结点，总是插入到叶结点下面。（ ）
【答案】×
【解析】不一定。插入二叉排序树的原则:将新节点元素值与根结点元素值相比较，如小于根结点元素值则插入到左子树口，否则插入到右子树中。所以就可能插在一个度为1的结点下面。
14．二维以上的数组其实是一种特殊的广义表。（ ）
【答案】 √
【解析】广义表是线性表的推广。广义表中的元素还有可能是广义表。对于维数大于二的数组，它在某一维上的元素还是数组。符合广义表的定义，因此二维以上的数组其实是一种特殊的广义表。
15．AOE 网一定是有向无环图。（ ）
【答案】×
【解析】在带权的有向图中，以顶点表示事件，有向边表示活动，边上的权值表示完成该活动的开销，则称这种有向图表示活动的网络，简称为AOE 网。因此对AOE 网是否是有向无环图没有要求。
16．堆是满二叉树。（ ）
【答案】×
【解析】堆的定义:
n 个关键字序列
①②且且 称为堆，当且仅当该序列满足如下性质(简称为堆性质) : 小根堆:满足第①种情况的堆；
大根堆:满足第②种情况的堆。
因此并不能保证堆是满二叉树。
17．倒排文件的目的是为了多关键字查找。（ ）
【答案】√
【解析】多关键字文件的特点是，在对文件进行检索操作时，不仅对主关键字进行简单询问，还经常需要对次关键字进行其它类型的询问检索。常见的多关键字文件为:多重表文件和倒排文件。
18．折半查找与二元查找树的时间性能在最坏的情况下是相同的。（ ）
【答案】×
相关内容
相关标签