2018年东华理工大学信息工程学院811数据结构(含C程序设计)考研核心题库
● 摘要
一、填空题
1． 在一个无向图的的邻接表中，若表结点的个数是m ，则图中边的条数是_____条。 【答案】
【解析】对于无向图，在邻接表中，如果存在n 条边，则会有2n 个表结点。
2． 假定查找有序表 中每个元素的概率相等，则进行折半查找时的平均查找长度为_____。
【答案】
表
平均查找次数为。
3． 以下程序的功能是实现带附加头结点的单链表数据结点逆序连接，请填空完善之。
h 为附加头结点指针
(_____)
_____；
【答案】(1)p!＝NULL //链表未到尾就一直进行
(2)q //将当前结点作为头结点后的第一元素结点插入
4． 数组的存储结构采用_____存储方式。
【答案】顺序存储结构
【解析】数组本身的存储结构是线性的，也就是说它是连续存储的。
5． 文件由_____组成；记录由_____组成。
【答案】记录；数据项
6． 当两个栈共享一存储区时，栈利用一维数组stack(1，，1) 表示，两栈顶指针为top[l]与top[2]，则当栈1空时，top[l]为_____，栈2空时，top[2]为_____，栈满时为_____。
【答案】0；n+1；top[l]+l＝top[2]
【解析】折半查找时每个的次数如表所示:
【解析】共享栈的栈底在共享存储区的两端，当栈满时栈顶相邻。
7． 外排序的基本操作过程是_____和_____。
【答案】生成有序归并段(顺串) ；归并
8． 对于一个具有n 个结点的单链表，在已知的结点半p 后插入一个新结点的时间. 复杂度为_____，在给定值为x 的结点后插入一个新结点的时间复杂度为_____。
【答案】O(1)；O(n)
【解析】第一种情况只需直接修改指针的指向。第二种情况必须从头结点遍历找到x 的结点。
9． 在循环队列中，队列长度为n ，存储位置从0到，n ﹣1编号，以rear 指示实际的队尾元素，现要在此队列中插入一个新元素，新元素的位置是_____。
【答案】
10．设广义表L ＝(（ ），（ ）) ，则head(L)是_____tail(L)是_____L的长度是_____；深度是_____。
【答案】（ ）；(（ ）) ；2；2
【解析】广义表的表头是表的第一个元素，表尾是除了第一个元素外其余的所有的元素构成的表；表的长度指表中元素的个数；表的深度指展开后括号的层数。
二、判断题
11．广义表的取表尾运算，其结果通常是个表，但有时也可是个单元素值。（ ）
【答案】 ×
【解析】广义表的取表尾运算，是非空广义表除去表头元素，剩余元素组成的表，不可能是原子。
12．哈希函数越复杂越好，因为这样随机性好，冲突概率小。（ ）
【答案】×
【解析】随机性好和冲突概率小跟哈希函数的复杂程度无关，是根据具体情况而定的，跟实际的数据有很大关系。
13． 若一个有向图的邻接矩阵对角线以下元素均为零，则该图的拓扑有序序列必定存在。（ ）
【答案】√
【解析】因为一个有向图的邻接矩阵对角线以下元素均为零，则该图是一个有向无环图，所以该图的拓扑有序序列必定存在。
14． 数组可看成线性结构的一种推广，因此与线性表一样，可以对它进行插入，删除等操作。（ ）
【答案】 ×
【解析】数组在维数和界偶确定后，其元素个数已经确定，不能进行插入和删除运算。
15．若从二叉树的任一结点出发，到根的路径上所经过的结点序列按其关键字有序，则该二叉树一定是哈夫曼树。（ ）
【答案】×
【解析】在含有N 个带权叶子结点的二叉树中，其中带权路径长度最小的二叉树称为哈夫曼树，也叫做最优二叉树。关键字有序，可能叶子结点部分的关键字最大，根结点的关键字部分最小，此时就不是哈夫曼树。
16．对于有n 个结点的二叉树，其高度为log 2n 。（ ）
【答案】 ×
【解析】例如n 结点的单枝树，高度就为n 。
17．任何二叉树的后序线索树进行后序遍历时都必须用栈。（ ）
【答案】 ×
【解析】任何结点至多只有左子树的二叉树的遍历就不需要栈。
18．串长度是指串中不同字符的个数。（ ）
【答案】 ×
【解析】不是，串长度是指串中字符的总个数。需要注意的是，在计算字符串的长度时，不要漏掉了空格。
19．基数分类只适用于以数字为关键字的情况，不适用于以字符串为关键字的情况。（ ）
【答案】×
【解析】如果用字符串为关键字，可以将其中的字符串的每一位用Ascn 码进行比较。
20．对处理大量数据的外存介质而言，索引顺序存取方法是一种方便的文件组织方法。（ ）
【答案】×
【解析】索引顺序存取方法插入操作比较麻烦，对于处理大量数据，会有大量的记录进入溢出区，而基本区中又浪费很多空间。
三、算法设计题
21．对给定关键字序号j(1 例如:给定无序关键字{7，5，1，6，2，8，9，3}，当j=4时，找到的关键字应是5。
相关内容
相关标签