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

2018年武汉大学卫星导航定位技术研究中心942数据结构考研核心题库

  摘要

一、填空题

1. 执行顺序查找时,存储方式可以是_____,折半查找时,要求线性表_____,分块查找时要求线性表_____,而哈希表的查找,要求线性表的存储方式是_____。

【答案】顺序存储或链式存储;顺序存储且有序;块内顺序存储,块间有序;散列存储

2. G 是一个非连通无向图,共有28条边,则该图至少有_____个顶点。

【答案】9

【解析】求该非连通无向图的最少顶点数,则该图为一个孤立的顶点和一个完全连通图。

3. 实现字符串拷贝的函数strcpv 为:

(_____)

【答案】s++=*t++或(*s++=*t++)!='\0’

4. 分别采用堆排序,快速排序,起泡排序和归并排序,对初态为有序的表,则最省时间的是_____算法,最费时间的是_____算法。

【答案】起泡;快速

【解析】当初态为有序表时,冒泡排序只需要进行一趟比较即可,此时时间复杂度为O(n),

2而快速排序算 法需要比较的次数达到最大,时间复杂度为O (n) 。

5. 设有两个算法在同一机器上运行,其执行时闻分别为100n 2和2n ,要使前者快于后者,n 至少为_____。

【答案】15

2n 【解析】当时,100n2>2n,而,时,100n <2

6. 在双向循环链表中,向P 所指的结点之后插入指针f 所指的结点,其操作是_____、_____、_____、_____。

【答案】f ﹣>next =p ﹣>next ;f ﹣>prior =p ;p ﹣>next ﹣>prior =f ;p ﹣>next =f ;

7. 一棵有11个结点的满二叉树有_____个度为1的结点、有_____个分支(非终端) 结点和_____个叶子,该满二叉树的深度为_____。 【答案】或

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

8. 组成串的数据元素只能是_____。

【答案】字符

9. 检索是为了在文件中寻找满足一定条件的记录而设置的操作。检索可以按_____检索。也可以按_____检索;按_____检索又可以有 检索和_____检索。

【答案】关键字;记录号;记录号;顺序;直接

10.在一棵m 阶B-树中,若在某结点中插入一个新关键字而引起该结点分裂,则此结点中原有的关键字的个数是_____; 若在某结点中删除一个关键字而导致结点合并,则该结点中原有的关键字的个数是_____。 【答案】

【解析】m 阶B-树除根结点和叶子结点外,结点中关键字个数最多是m -1,最少

11.设正文串长度为n ,模式串长度为m ,则串匹配的KMP 算法的时间复杂度为_____。

【答案】O(m+n)

12.在顺序存储的二叉树中,编号为i 和j 的两个结点处在同一层的条件是_____。 【答案】

要加“虚结点”。

设编号为i 和j 的结点在顺序存储中的下标为s 和t , 则结点i 和j 在同一层上的条件是

【解析】用顺序存储结构存储二叉树时,要按完全二叉树的形式存储,非完全二叉树存储时,

二、单项选择题

13.稀疏矩阵一般的压缩存储方法有两种,即( )。

A. 二维数组和三维数组

B. 三元组和散列

C. 三元组和十字链表

D. 散列和十字链表

【答案】C

【解析】稀疏矩阵一般的压缩方法为三元组表和十字链表。三元组表就是将非零元素及其对应的行和列构成一个三元组(行标,列标,值) 。十字链表相比三元组表而言,主要是对每个结点增加了两个链域。如果数组经常运算时,会产生大量数据元素的移动,此时,采用链表存储结构更为恰当。

14.用海明码对长度为8位的数据进行检/纠错时, 若能纠正一位错, 则校验位数至少为( )

A.2

B.3

C.4

D.5

【答案】C

【解析】设校验位的位数为k , 数据位的位数为n , 根据海明码编码k 和n 应满足下述关系。

n=8, 当k=4时, , 符合要求, 校验位至少是4位, 故答案为C 。

15.计算机算法指的是解决问题的步骤序列,它必须具备( )三个特性。

A. 可执行性、可移植性、可扩充性

B. 可执行性、确定性、有穷性

C. 确定性、有穷性、稳定性

D. 易读性、稳定性、安全性

【答案】B

【解析】计算机算法是以一步接一步的方式来详细描述计算机如何将输入转化为所要求的输出的过程,或者说,算法是对计算机上执行的计算过程的具体描述,也就是解决问题的步骤序列。一个算法通常需要具备五大特性:有穷性;确定性;可执行性;输入一个算法有零个或多个输入;输出一个算法有零个或者多个输出。

16.由3个“1”和5个“0”组成的8位二进制补码, 能表示的最小整数是( )。

A.-126

B.-125

C.-32

D.-3

【答案】B

【解析】能表示的最小整数一定是负数, 符号位占用1个“1”; 负数的补码和原码的转化是:原码符号位不变, 数值部分按位取反, 末位加“1”。

因此最小的整数的补码是“10000011”, 原码为“111111101”, 即。

17.在体系结构中, 直接为ICMP 提供服务的协议是( )。

A.PPP

B.IP

C.UDP

D.TCP

【答案】B 。

【解析】首先明确ICMP 是网络层的协议, 由于服务必须是下一层向上一层提供服务的, 因此选项C 项中的UDP 和选项D 项中的TCP 属于传输层, 在网络层上面, 所以显然错误, 而PPP 协议是广域网数据链路层协议, 直接为网络层, 也就是IP 层提供服务, ICMP 协议是封装在网络层, 因此