2018年中国石油大学(北京)地球物理与信息工程学院858计算机科学基础之数据结构考研核心题库

更新时间:2023-04-28 05:25:01 阅读量: 实用文档 文档下载

说明:文章内容仅供预览,部分内容可能不全。下载后的文档,内容与下面显示的完全一致。下载之前请确认下面内容是否您想要的,是否完整无缺。

专注考研专业课13年,提供海量考研优质文档!

第 1 页,共 45 页

目录

2018年中国石油大学(北京)地球物理与信息工程学院858计算机科学基础之数据结构考研核

心题库(一) ........................................................................................................................... 2 2018年中国石油大学(北京)地球物理与信息工程学院858计算机科学基础之数据结构考研核

心题库(二) ......................................................................................................................... 11 2018年中国石油大学(北京)地球物理与信息工程学院858计算机科学基础之数据结构考研核

心题库(三) ......................................................................................................................... 20 2018年中国石油大学(北京)地球物理与信息工程学院858计算机科学基础之数据结构考研核

心题库(四) ......................................................................................................................... 28 2018年中国石油大学(北京)地球物理与信息工程学院858计算机科学基础之数据结构考研核

心题库(五) (38)

专注考研专业课13年,提供海量考研优质文档!

第 2 页,共 45 页 2018年中国石油大学(北京)地球物理与信息工程学院858计算机科学基础之数据结

构考研核心题库(一)

说明:本套核心题库按照考试大纲、历年真题、指定参考书等结合考试侧重点和难度,精心整理编写。核心题库更突出针对性和实战性,考研冲刺必备资料。

——————————————————————————————————————————

一、填空题

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

initstack(S)置S 为空栈;

push(S ,X)元素X 入栈;

pop(S)出栈操作;

gettop(S)返回栈顶元素;

sempty(S)判栈空函数;

setnull(St)置串St 为空串;

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

equal(S 1,S 2)判串S 1并S 2是否相等的函数;

concat(S 1,S 2)返回联接S 1和S 2之后的串;

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

empty(st)判串空函数

FUNCinvert(pre :string ;V ARexp :string):boolean ;

{若给定的表达式的前缀式pre 正确,本过程求得和它相应的表达式exp 并返回true ,否则exp 为空串,并返回false 。已知原表达式中不包含括弧,opset 为运算符的集合。

)

_____;_____;

_____THEN_____

IF_____THEN_____

(_____,_____);

(_____,_____);

_____

_____THEN

专注考研专业课13年,提供海量考研优质文档!

第 3 页,共 45 页

注意:每个空格只填一个语句。

【答案】(1)initstack(S)//栈s 初始化为空栈

(2)setnull(exp)//串exp 初始化为空串

(3)chinopset//判取出字符是否是操作符

(4)push(s ,ch)//如ch 是运算符,则入操作符栈s

(5)sempty(s)//判栈s 是否为空

(6)succ :=false//若读出ch 是操作数且栈为空,则按出错处理

(7)exp

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

(9)exp

(10)gettop(s)//取栈顶操作符

(11)pop(s)//操作符取出后,出栈

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

2. 完善算法:求KMP 算法.next 数组。

k :=_____;next[1]:=0;

k :=_____;

END ;

【答案】0;next[k]

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

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

4. 设为哈夫曼树的叶结点数目,则该哈夫曼树共有_____个结点。 【答案】

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

5. 下面描述的是一种构造最小生成树算法的基本思想。设要处理的无向图包括n 个顶点

用相邻矩阵A 表示,边的权全是正数。请在下列划线处填上正确叙述。

(1)若是边,则的值等于_____,若不是边,则A(i ,j)的值是一个比任何边的权_____,矩阵的对角线元素全为0。

专注考研专业课13年,提供海量考研优质文档!

第 4 页,共 45 页 (2)构造最小生成树过程中,若顶点已包括进生成树,就把相邻矩阵的对角线元素

成_____,若

已包括进生成树,就把矩阵元素置成_____。 (3)算法结束时,相邻矩阵中_____的元素指出最小生成树的_____。 【答案】(1)边上的权值;都大的数;(2)1;负值;(3)为负;边

6. 设T 和P 是两个给定的串,在T 中寻找等于P 的子串的过程称为_____,又称P 为_____。

【答案】模式匹配;模式串

7. 设有一个10阶对称矩阵A 采用压缩存储方式(以行为主序存储:a 11=l),则a 85的地址为_____。

【答案】33

【解析】设存储的元素的行标为i ,列标为j 。若i >=j ,则的地址为l +2+... +i ﹣l +j =i(i ﹣l)/2+j 。若i <j 。则的地址为j(j ﹣l)/2+i 。将i =8,j =5代入得33。

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

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

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

9. 模式串的next 函数值序列为_____。

【答案】01122312

10.在循环队列中,队列长度为n ,存储位置从0到,n ﹣1编号,以rear 指示实际的队尾元素,现要在此队列中插入一个新元素,新元素的位置是_____。

【答案】

二、判断题

11.AOE 网一定是有向无环图。( )

【答案】×

【解析】在带权的有向图中,以顶点表示事件,有向边表示活动,边上的权值表示完成该活动的开销,则称这种有向图表示活动的网络,简称为AOE 网。因此对AOE 网是否是有向无环图没有要求。

12.若把堆看成是一棵完全二叉树,则该树一定是一棵二叉排序树。( )

【答案】×

【解析】堆中某个节点的值总是不大于或不小于其父节点的值,这个并不是二叉排序树的性质。

本文来源:https://www.bwwdw.com/article/4ugq.html

Top