2018年三峡大学计算机与信息学院837计算机综合之数据结构考研基础五套测试题
● 摘要
目录
2018年三峡大学计算机与信息学院837计算机综合之数据结构考研基础五套测试题（一） ... 2 2018年三峡大学计算机与信息学院837计算机综合之数据结构考研基础五套测试题（二） . 13 2018年三峡大学计算机与信息学院837计算机综合之数据结构考研基础五套测试题（三） . 23 2018年三峡大学计算机与信息学院837计算机综合之数据结构考研基础五套测试题（四） . 33 2018年三峡大学计算机与信息学院837计算机综合之数据结构考研基础五套测试题（五） . 42
一、填空题
1． 在下面的程序段中，对X 的赋值语句的时间复杂度为_____ (表示为n 的函数) 。
【答案】1＋(1＋2) ＋(1＋2＋3) ＋…＋(l＋2＋…＋n) ＝n(n＋1)(n＋2)/6，即O(n)
【解析】当i ＝l 时，赋值语句就被执行了一次。当i ＝2时，赋值语句被执行了1＋2次。当i ＝3时，赋值语句被执行了1＋2＋3次。...... 可以推出赋值语句总共被执行了1＋(1＋2) ＋(1＋2＋3) ＋…＋(l＋2＋... ＋n) ＝n(n＋1)(n＋2)/6次。
2． 假设一个15阶的上三角矩阵A 按行优先顺序压缩存储在一维数组B 中，则非零元素中的存储位置k ＝_____。(注:矩阵元素下标从1开始)
【答案】93
【解析】对于上三角矩阵，k ＝(i﹣l)(2n﹣i ＋2)/2＋(j﹣i) ＋l 。将i ＝j ＝9，n ＝15代入得93。
3． 完善算法:求KMP 算法.next 数组。
k :＝_____；next[1]:＝0；
k :＝_____；
END ；
【答案】0；next[k]
4． 已知t) ，LEN(t)＋1))
:
【答案】
；
；ASSIGN(S，U) ；ASSIGN(V，SUBSTR(S，INDEX(S，，求REPLACE(S，V ，m) ＝_____。
在B
5． 以下是用类C 语言写出的算法，该算法将以二叉链表存储的二叉树中的叶结点按从左到右的顺序链成一个带头结点的双向循环链表，链接时，结点的Lchild 域作为前链域，指向结点的直接前驱，结点的Rchild 域作为后链域，指向结点的直接后继。算法中，使用一个顺序栈stack , 栈顶指针为top ，P ，t 为辅助指针，head 为双向循环链表的头指针。试填充算法中的空格，使算法完整。
【答案】
6． 假定有k 个关键字互为同义词，若用线性探测再哈希法把这k 个关键字存入哈希表中，至少要进行_____次探测。
【答案】
【解析】当该关键字发生冲突时，用线性探测不会遇到别的关键字冲突，这个时候需要探测的次数最小。总次数为。
7． 求图的最小生成树有两种算法，_____算法适合于求稀疏图的最小生成树e
【答案】克鲁斯卡尔
【解析】克鲁斯卡尔算法是一种按权值的递增次序选择合适的边来构造最小生成树的方法，这种算法中，采用堆来存放边的集合，适合于边稀疏而顶点较多的图。
8． 二叉树的前序序列和中序序列相同的条件是_____。
【答案】空树或任何结点至多只有右子树的二叉树
【解析】前序遍历的顺序为根左右，中序遍历的顺序为左根右，因此若中序遍历和前序遍历序列相同，则任何结点都没有左子树。
9． 下面程序的功能是用递归算法将一个整数按逆序存放到一个字符数组中。如123存放成321。请填空:
(_____i)；
＝
_____.
_____
【答案】a ＋l ；n%10
【解析】通过递归算法，首先找到最高位的值，将其放到str 对应的数组中，依次反向获取从高位到地位的值，将其放到数组中，完成了将整数逆序放到一个字符数组中。
10．对于一个具有n 个结点的二叉树，当它为一棵_____二叉树时具有最小高度, 当它为一棵_____时，具有最大高度。
【答案】完全；只有一个叶结点的二叉树
二、单项选择题
11．若一棵完全二叉树有768个结点, 则该二叉树中叶结点的个数是（ ）。
A.257 B.258 C.384 D.385
【答案】C
【解析】由
和
可知,
, 即
, 显然
则
384, 所以二叉树的叶结点个数是384。
还可以根据完全二叉树的另一个性质:
最后一个分支结点的序号为384, 而叶子结点的个数为。(
12．下列说法不正确的是（ ）。
表示不大于x 的最大整数, 比如
, 故非叶子结点数为
) 。
A. 图的遍历是从给定的源点出发每个顶点仅被访问一次 B. 遍历的基本方法有两种:深度遍历和广度遍历 C. 图的深度遍历不适用于有向图 D. 图的深度遍历是一个递归过程 【答案】C
【解析】图的遍历是指从图中的某一个顶点出发，按照某种搜索算法沿着图中的边对图中的所有顶点访问一次且仅访问一次。图的深度遍历类似于树的先序遍历，不仅适合无向图，也适合于有向图。
相关内容
相关标签