当前位置:问答库>考研试题

2017年武汉大学测绘遥感信息工程国家重点实验室970计算机技术基础考研导师圈点必考题汇编

  摘要

一、填空题

1. 数据结构是研讨数据的_____和_____以及它们之间的相互关系,并对与这种结构定义相应的_____,设计出相应的_____。

;算法 【答案】逻辑结构;物理结构;操作(运算)

2. 当线性表的元素总数基本稳定,且很少进行插入和删除操作,但要求以最快的速度存取线性表中的元素时,应采用_____存储结构。

【答案】顺序

【解析】顺序存储结构的存取操作比较方便,但插入和删除操作不如链式存储结构方便,而且需要连续的存储空间,由于该线性表的元素总数基本稳定,而且很少进行插入删除操作,为了更快的存取元素,顺序表更合适。

3. 高度为4的3阶B-树中,最多有_____个关键字。

【答案】26

【解析】第4层是叶结点,1层至3层每个结点两个关键字,每个节点的关键字达到最大时,关键字最多。

4. 在下面的程序段中,对X 的赋值语句的时间复杂度为_____(表示为n 的函数)。

【答案】1+(1+2)+(1+2+3)+"•+(l +2+... +n )=n(n +1)(n +2)/6,即

【解析】当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次。

5. 如果按关键码值递増的顺序依次将关键码值插入到二叉排序树中,则对这样的二叉排序树检索时,平均比较次数为_____。

【答案】序查找效率一样为

【解析】如果关键码是排好序的,构建二叉排序树就会形成一个单支树,它的查找效率和顺

6. 阅读下列程序,指出其功能,并写出空格处应填上的语句。

【答案】

【解析】本题是在哈希表ht[]中插入值为的元素,如该元素已在哈希表中,报告出错。

7.

给定一组数据以它构造一棵哈夫曼树,则树高为_____,

带权路径长度

的值为_____。 【答案】5;96

【解析】每次找两个最小的权值构建哈夫曼树:

8. 模式串

的next 函数值序列为_____。

【答案】01122312

9. —棵有个结点的满二叉树有_____个度为1的结点、有_____个分支(非终端)结点和_____个叶子,该满二叉树的深度为_____。

【答案】

【解析】满二叉树没有度为1的结点,度为0的结点等于度为2的结点个数+1。

10.设单链表的结点结构为为指针域,已知指针px 指向单链表中data 为x 的结_____;点,指针py 指向data 为y 的新结点,若将结点y 插入结点x 之后,贝懦要执行以下语句:_____;

【答案】

二、选择题

11.

A. B. C. D.

个分支结点的满二叉树的深度是( )。

【答案】C

【解析】满二叉树的结点总数=分支的结点总数+非分支的结点总数。由于此树为满二叉树, 所以非分支的结点总数为1,所以满二叉树共有个结点,所以满二叉树的深度为

12.元素a , b , c , d , e 依次进入初始为空的栈中,若元素进栈后可停留、可出栈,直到所有元素都出栈,则在所有可能的出栈序列中,以元素d 开头的序列个数是( )。

A.3 B.4 C.5 D.6

【答案】B

【解析】d 首先出栈后的状态如下图所示。

此时可有以下4种操作:

(1)e 进找后出栈,出梭序列为decba 。 (2)c 出找,e 进找后出栈,出找序列为dceba 。 (3)cb 出找,e 进找后出栈,出找序列为dcbea 。

(4)cba 出找,e 进找后出找,出找序列为dcbae 。

13.若X 是二叉中序线索树中一个有左孩子的结点,且X 不为根,则X 的前驱为( )。

A.X 的双亲

B.X 的右子树中最左的结点 C.X 的左子树中最右的结点 D.X 的左子树中最右的叶结点 【答案】C

【解析】中序线索,只有把其左子树最右结点遍历完后,才会遍历自己,所以X 的前驱为X 的左子树中最右的结点。

14.算法的计算量的大小称为计算的( )。

A. 效率 B. 复杂性