文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > 资格考试/认证 > 其它考试 > 北航软院2012年数据结构与C语言程序设计参考答案(原版)
侵权投诉

北航软院2012年数据结构与C语言程序设计参考答案(原版)

北航软院2012年数据结构与C语言程序设计参考答案(原版)

北京航空航天大学2012年硕士研究生入学考试试题

“数据结构与C语言程序设计”(科目代码:991)参考答案

一、填空(本题共20分,每小题各2分)

1.从总体上说,“数据结构”课程主要研究数据的内容。

2.若对某线性表最常用的操作是在表中插入元素或者删除表中元素,则对于顺序存储结构和链式存储结构这两种存储结构而言,线性表应该采用 链式存储结构 。

3.在长度为n的非空队列中进行插入或者删除操作的时间复杂度用大O符号表示为

4.若一棵度为4的树中度为1、2、3和4的结点个数分别为4、2、1和1,则该树中叶结点的个数为 8 。

5.若某二叉树的中序遍历序列为B,A,F,D,G,C,E,按层次遍历序列为A,B,C,D,E,F,G,则该二叉树的后序遍历序列为 B,F,G,D,E,C,A 。

6.将一棵结点总数为n、且具有m个叶结点的树转换为一棵二叉树以后,该二叉树中右子树为空的结点有 n-m+1 个。

7.对于图G=(V,E) 与 G^=(V^,E^),若V^包含于V,E^包含于E,则称G^是G的子图 。

8.在顺序表(6,15,30,37,65,68,70,72,89,99)中采用折半查找法查找元素37,与表中进行过比较的元素依次是 65,15,30,37 。

9.若已知n个关键字值具有相同的散列函数值,并且采用线性探测再散列法处理冲突,那么,将这n个关键字值全部散列到初始为空的地址空间中,发生散列冲突的次数是 。

10.若长度为n的序列K=(k1,k2,…,kn)当且仅当满足ki≤k2i并且ki≤k2i+1(1≤i≤n/2)时,则称该序列为一个小顶堆积(Heap)。根据该定义,序列(26,5,77,1,61,11,59,48,15,19)对应的小顶堆积是 1,5,11,15,19,77,59,48,26,61 。

二、简答题(本题共20分,每小题各5分)

1.答:该邻接矩阵是稀疏矩阵。因为邻接矩阵中一共有10000个元素,只有200个非零元素,非零元素的数目只占整个稀疏矩阵元素总个数的2%,按照题目假设,可以认为该邻接矩阵是稀疏矩阵。

2.答:该方法的基本思想是当发生散列冲突时按照下列方法求得后继散列地址: Di=H(k)+di) MOD m i=1,2,…,n (n≤m-1)

其中,H(k)为散列函数,k为关键字,m为散列表长,di为地址增量序列,可以有以下三种取法:(1)di=1,2,3,…,m-1 称为线性探测再散列;

(2)di=1^2,-1^2,2^2,-2^2,…,±n^2(n≤m/2)称为二次探测再散列;

(3)di=伪随机数序列,称为伪随机探测再散列。

3.答:该结果是采用了起泡排序法排序得到的。若选择排序法每一趟排序选择一个最大值元素,该最大值元素只需要与当前参加排序的最后那个元素交换位置,而不需要改变其他元素的位置,显然,从上述结果可以看出不是如此。上述结果符合起泡排序的规律。

第1页

你可能喜欢

  • 设计的程序
  • 数据处理
  • 程序设计报告
  • 数据处理与分析
  • 数据结构和程序设计
  • 数据结构作业答案

热门文档

相关文档

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email