北航软院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.答:该结果是采用了起泡排序法排序得到的。若选择排序法每一趟排序选择一个最大值元素,该最大值元素只需要与当前参加排序的最后那个元素交换位置,而不需要改变其他元素的位置,显然,从上述结果可以看出不是如此。上述结果符合起泡排序的规律。
北航软院2012年数据结构与C语言程序设计试题(原版)北航软院2012年数据结构与C语言程序设计试题(原版)隐藏>> 北京航空航天大学 2012 年硕士研究生入学考试试题“...
北航考研真题数据结构与C语言程序设计2008_其它考试_资格考试/认证_教育专区。... 北京航空航天大学数据结... 8页 免费 北航软院2012年数据结构... 6页 7...
新祥旭北航数据结构与C语言程序设计考研参考书目-...2012年《数据结构与C语言程序设计》考试内容包括“... 2013年注会设计统考真题及答案160份文档 ...
北京航空航天大学数据结构与C语言程序设计2005-2008、2010-2012年(12年带答案)... 北航考研真题数据结构与... 6页 免费 北航软院2012年数据结构... 4页 7...
北航软院2012年数据结构... 6页 7下载券 C语言... 十套数据结构试题及答案 40页 1下载券20...3)设计内容 4)程序流程图 5)源程序 6)软件测试...
数据结构与c语言设计复习试题数据结构与 C 语言程序设计答案是非题( 10) 一. 是非题(2'×10) (×)...
8页 免费 北航软院2012年数据结构... 4页 7下载券喜欢此文档的还喜欢...北航《C 语言程序设计》在线作业一一、单选题(共 15 道试题,共 60 分。) 1...
北航软院2012年数据结构... 6页 7下载券 2012...c 语言程序设计复习题 一、选择题 (1) 算法具有...(D) 以上三个答案全是错误的 B、数组中第一个...
数据结构与C语言程序设计试题及答案。求职资料数据结构与 C 语言程序设计答案是非题( 10) 一. 是非题(2’×10) (×)1、 队列逻辑上是一个表头和表尾既能...
北航考研真题数据结构与C语... 7页 免费 北航软院2012年数据结构与... 6... 北航《C 语言程序设计》在线作业一 单选题 判断题 一、单选题(共 15 道...
热门文档