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

2017年中国矿业大学(徐州)计算机科学与技术学院874数据结构[专业硕士]考研导师圈点必考题汇编

  摘要

一、填空题

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

【答案】2(n-l )

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

2. 在单链表L 中,指针P 所指结点有后继结点的条件是_____

【答案】

【解析】指针所指节点的指针域所指向的元素非空,说明该指针所指节点有后继结点。

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

【答案】

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

4. 有向图G=(V ,E ), 其中V (G )=[0, 1,2,3,4, 5}, 用三元组表示弧及弧上的权d 。 E (G )为 E (G= {<0,5, 100>, <0,2,10>, <1,2,5>,<0,4, 30>,<4, 5, 60>,<3,5, 10>,<2. 3,50>, <4, 3, 20>},则从源点0到顶点3的最短路径长度是_____,经过的中间顶点是_____。

【答案】50; 4

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

【答案】

6. 起始地址为480,大小为8的块,其伙伴块的起始地址是_____;若块大小为32,则其伙伴块的起始地址为_____。

【答案】

【解析】起始地址为P ,大小为的内存块,其伙伴块的起始地址计算公式如下:

根据上述公式起始地址就为488。

7. 下列程序是快速排序的非递归算法,请填写适当的语句,完成该功能。

【答案】

【解析】快速排序(quicksort )的基本思想是,通过一趟排序将待排记录分割成独立的两部分,其中一部分记录的关键字均比另一部分记录的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有序。

8. 遍历图的过程实质上是_____,广度优先遍历图的时间复杂度_____; 深度优先遍历图的时间复杂度_____, 两者不同之处在于_____, 反映在数据结构上的差别是_____。

【答案】查找顶点的邻接点的过程;0(n+e); 0(n+e); 访问顶点的顺序不同;队列和栈 【解析】广度优先遍历图使用队列这种数据结构,深度优先遍历图使用栈这种数据结构。

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

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

置串 判串

为空串;

是否相等的函数;

之后的串;

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

返回联接

empty (st ) 判串空函数

{若给定的表达式的前缀式pre 正确,本过程求得和它相应的表达式exp 并返回true , 否则exp sub (S , i , 1) 返回S 中第i 个字符;

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

注意:毎个空格只填一个语句。 【答案】(1)栈S 初始化为空栈 (2)串exp 初始化为空串 (3)判取出字符是否是操作符

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

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

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

(9)exp (10)取栈顶操作符 (11

)操作符取出后,出栈

(12)

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