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

2017年中国地质大学(武汉)信息工程学院952软件综合之数据结构考研导师圈点必考题汇编

  摘要

一、填空题

1. 用循环链表表示的队列长度为n ,若只设头指针,则出队和入队的时间复杂度分别是_____和_____;若只设尾指针,则出队和入队的时间复杂度分别是_____和_____。

【答案】

【解析】队列的出队操作即删除队头的元素,队列的入队操作即在队尾添加元素,循环链表只设头指针,出队时,只要把头结点的下一个结点删除就好了,入队时,要把新的结点插入队尾,必须把队列遍历,找到队尾指针,才能插入。循环队列只设尾指针,出队时只要把为指针的下一个结点或者下下个结点删除即可,入队时,只要在尾指针的后面插入新的结点,并更新尾结点即可。

2. 设为哈夫曼树的叶结点数日,则该哈夫曼树共有_____个结点。

【答案】

【解析】哈夫曼树只有度为0和2的节点。

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

【答案】

4. 己知有序表为(12,18,24,35,47,50,62,83,90,115,134)当用二分法查找90时,需_____次查找成功,查找47时_____成功,查找100时,需_____次才能确定不成功。

【答案】2;4;3

【解析】二分法查找元素次数列表

找100是找到115就停止了。

5. 设有一个10阶对称矩阵A 采用压缩存储方式(以行为主序存储:

【答案】33

【解析】设存储的元素的行标为i ,列标为j 。若则

的地址为

代入得33。

第 2 页,共 57 页

,)则 的地址为_____。

则的地址为

6. 假定查找有序表

【答案】37/12

中每个元素的概率相等,则进行折半查找时的平均查找长度为_____

【解析】折半查找时每个的次数如表所示:

平均查找次数为

7. 按LSD 进行关键字排序,除最次位关键字之外,对每个关键字进行排序时,只能用_____的排序方法。

【答案】稳定

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

【答案】

9. 二叉树的前序序列和中序序列相同的条件是_____。

【答案】空树或任何结点至多只有右子树的二叉树

【解析】前序遍历的顺序为根左右,中序遍历的顺序为左根右,因此若中序遍历和前序遍历序列相同,则任何结点都没有左子树。

10.对于给定的元素,可以构造出的逻辑结构有_____,_____,_____,_____四种。

【答案】集合;线性结构;树形结构;图状结构(网状结构)

11.试利用下列栈和串的基本操作完成下述填空题。

initstack (S ) 置S 为空找; push (S , X ) 元素X 入找; pop (S ) 出栈操作; gettop (S ) 返回栈顶元素; sempty (S ) 判找空函数;

置串 判串 返回联接

empty (st ) 判串空函数

{若给定的表达式的前缀式pre 正确,本过程求得和它相应的表达式exp 并返回true , 否则exp

第 3 页,共 57 页

为空串;

是否相等的函数;

之后的串;

length (st ) 返回串st 的长度;

sub (S , i , 1) 返回S 中第i 个字符;

为空串,并返回false 。已知原表达式中不包含括弧,opset 为运算符的集合。)

注意:毎个空格只填一个语句。 【答案】(1)(2)(3)(4)(5)(6)(7)exp (8)(9)exp (10)(11

)(12)

取栈顶操作符 操作符取出后,出栈

将pre 的最后一个字符(操作数)加入到中缀式exp 的最后

若ch 是操作数且栈非空,则形成部分中缀表达式

栈S 初始化为空栈 串exp 初始化为空串 判取出字符是否是操作符

如ch 是运算符,则入操作符栈s 判栈8是否为空

若读出ch 是操作数且栈为空,则按出错处理

12.在有n 个顶点的有向图中,每个顶点的度最大可达。

【答案】2(n-l )

【解析】当有向图为完全连通图时每个顶点的度达到最大,出度入度均为n-1。

二、选择题

13.下列关于无向连通图特性的叙述中,正确的是( )。

I. 所有的顶点的度之和为偶数

第 4 页,共 57 页