文档库 最新最全的文档下载
当前位置:文档库 › 北航软件学院 软件工程 (专业课991 专业硕士 全国1月统考) 2012-2013复试经验分享

北航软件学院 软件工程 (专业课991 专业硕士 全国1月统考) 2012-2013复试经验分享

北航软件学院 软件工程 (专业课991  专业硕士 全国1月统考) 2012-2013复试经验分享
北航软件学院 软件工程 (专业课991  专业硕士 全国1月统考) 2012-2013复试经验分享

北航软件学院软件工程991 双证2012-2013年考研复试经验来自北航大神与大伙分享本人从中获益匪浅

2012年考研复试经验招收50人保送应该是25人(去年招收60人保送大约是31人)

复试线335 50 85 比2011年暴涨35分实际上前两年都没有正常的按照比例划线故意划了一个很低的线去年笔试之后就刷掉了一半多

复试分为三个阶段资格审查笔试面试还没有机试个人感觉未来很有可能加上

第一天资格审查得知复试33人拟录取25人初试成绩分布大约如下第一名400 390-400的两人368排在第10 341第26 336有4人应该是没有335分的所以实际最低复试线336

第二天笔试8点30分开始实际上最后到了32人(还有一个没来复试不知道是什么情况)先进行专业笔试复试说明上的范围是数据结构C语言数据库软件工程操作系统;但是实际上数据结构只有一个选择还出了一个JAVA的判断而并不在范围中的计算机网络占了大半

题型如下:选择15个30分填空15分判断20 大题35 第一个就给个ER图写建表查询语句什么的第二个网络的好像是数据传递过程的协议描述(没看完全不会)第三个是银行系统的数据流图考出来觉得40分就万岁了预感要被刷

英语笔试在休息半个小时后进行就是选词完型(4级里的新题型的一种)阅读整段翻译问答问答有两个用英语回答操作系统的作用和瀑布模型的过程整体难度个人感觉不足6级(本人大学没有看过一个英语单词6级至今未过可见应该是不难的)

笔试完毕后就通知了面试地点大家都认为笔试不刷人了结果到最后录取完了大家都不知道笔试多少分。。。。

第三天9点开始面试没有按照顺序谁进去都可以分两个教室一个教室英语面试就一个男老师人也很和蔼就是男音听得不是很习惯我一直都不适应男音英语囧面试就自我介绍讲到一半会被打断然后问我觉得自己的英语READING能力怎样我说很差结果他说

我初试考了60多啥的听没大懂囧了然后问为什么选择北航选择软院大部分人都有被问到这两个问题跨考的和分比较低的会被问到为什么跨考觉得本科专业如何已经如果被刷掉了会怎么样

另一个教室专业面试在专业面试前和一起复试的聊了一下发现本校单转双以及软院本科考上来的可能加起来有快15个了还有本校其他专业的外校的也有人大吉大这样的名校的顿感压力山大面试大概有7个左右的老师先聊聊天谈谈本科生活做过什么项目然后抽2个题如果答不上来可以再抽也有可能老师会口头追加问题大部分老师都是很和蔼的就一个老师可能是专门负责深究的只要回答的比较模糊他都会继续追问下去直到你承认不会为止。。。。其中有一个哥们是本校数学专业考过来的结果面试的老师里就有一个是数学院过来的。。问了数学问题把他问囧了。。。。。。。题型很广涉及408 编译体系结构计算机安全等各方面网络的题好像较少软工和数据库数据结构的题较多记得的题有DBA 的作用满二叉树是不是完全二叉树三级模式的概念什么是数据模型木马和蠕虫的区别什么是数字证书工作集的定义和作用句子和句型的定义以及区别(编译的题基本上大家都囧到死)。。。抽了4个只有2个答了一半十分悲剧。。。

下午两点面试结束4点公布结果我去的时候已经很多人在那了刚好走过几个表情很难看的哥们说是出了最后是录取了25人从结果上看似乎初试所占比重更大350以上的好像没有被刷低分中跨专业的似乎不受青睐应该是都被刷了。以上情况供参考2013年考研复试经验

前面的话:写这篇帖子的目的只有一个,就是我深知考研之不易,关于北航软院复试的资料又比较少,所以想把自己知道的一些东西分享给有志于报考北航软件学院的同学。

每年的复试安排和流程可能会有差别,请根据当年的复试安排按时参加复试,本

帖是根据今年的实际复试情况所写。

复试流程:

1.资格审查:下午2:00-3:00,准备好审查材料(身份证原件及复印件,学生证,成绩单原

件,复试通知书),如果带了个人自述的也可以一块交上,审查老师会把它们订在一起收起来,没带的面试时交给面试老师。一个老师负责审查,另一个老师负责收钱。个人自述没有固定格式,可以到网上搜一搜。

2.专业笔试:下午4:00-5:30。内容包括:计算机网络,数据库,软件工程,操作系统,C

语言和数据结构。值得一提的是,虽然在复试安排上没写计算机网络,但考了相当多的

计算机网络的内容,而C语言和数据结构都只考了一个小题。所以准备复试时请尽量把时间用在计算机网络,数据库,软件工程和操作系统上。

题型:

第一题:选择题,共15个,每个2分;

第二题:判断题,共10个,每题2分;

第三题:简答题,10分,是关于计算机网络协议的。给了一小段材料,然后给了三个问题,第一个是写HTTP协议格式,第二个是写出发送分组时协议发送顺序,第三个是HTTP 协议处理错误请求的过程。

第四题:设计题,40分,设计一个图书馆管理系统。先给了系统很长的描述,包括系统的使用者和功能等描述,然后给了六个问题。第一个是让写出系统中的角色(应该就是用例图中的操作者);第二个是让画出系统的用例图;第三个是让画出系统的主要类及联系;第四个好像是画出借书操作的流程图;第五个是让画出E-R图实体-联系图(Entity Relationship Diagram);第六个是按要求写查询语句。

大家放心,笔试不会刷人,大家考得也应该都差不多。

3.面试:第二天上午8:30开始专业综合面试,9:00开始英语面试,两个面试在不同的教

室。面试顺序基本上是按照贴在门上的名单顺序进行,顺序是按照姓氏拼音排的。因为专业面试比较慢,英语面试比较快,排在后面的同学可以先进行英语面试再进行专业综合面试。

英语面试:进去之后,一个女老师坐在你对面,她会让你坐下,然后给你一篇文章,让你自己先默读,读完之后,会问你大概两个问题。问题可能和文章有关,也可能和文章无关,比如让你介绍家乡的美食,然后问你怎么做出来的。问你最喜欢的食物,最喜欢的运动及原因等等之类的问题。回答完之后会从文章中挑一段让你读,读完之后就完了。

整个过程大概也就三四分钟吧。

专业综合面试:进去之后,一张很长的桌子,对面坐了大概六七个老师。当中一个是主面试官,一个老教授,大多数时间都是他在和你说,其他老师应该都是打酱油的。老师会先让你坐下,然后让你作自我介绍,自我介绍大概一到两分钟,,之后可能会和你聊一些其他问题。当时老师问我我们学校是不是211,我说不是,我说我们学校原来叫华北工学院,他说知道,然后就让我抽题。桌子上摆了很多卡片,然后让你随便抽两张,念完题后回答。如果不会的话就说不会,老师会让你接着抽。但很明显,抽的次数越多,分就会越低。我抽了两张,一个是说出选择编程语言所依据的规则,一个是给了几种二叉树问哪一个和存储结构有关,基本上都答出来了。然后老师说可以了,我就出去了。

面试题涉及范围包括数据库,软件工程,操作系统,数据结构,计算机网络,编译原理等。数据库,软件工程和操作系统的题貌似最多。有什么是关系数据库,需求分析,UML 建模语言,顺序图,面向对象软件工程特点,进程调度,CPU最小时间周期等等。面试时间有长有短,有十几分钟的,有五六分钟的,我就比较短。由于这次面试人数比较多,所以一上午没有面试完,有十几个是下午面试的。再次强调,准备复试的大部分时间应该放在数据库,操作系统,软件工程和计算机网络上。

4.第三天上午大概十点左右成绩就会贴在软件学院的宣传栏上。今年的情况是招生计划60

人,有28个是保研的(本校23个,外校5个)。43个进入复试,结果刷了7个,所以今年是比招生计划多招了4个。算计分原则是初试成绩加复试成绩,复试成绩300分,然后按照总成绩排名,刷掉最后若干个。今年被刷的都是初试成绩340以下,复试成绩200以下的。参加复试的女生有七个。

5.下午两点签协议书,领取政审表,找导师。导师信息会贴在宣传栏上,自己选择并根据

导师联系方式去找导师,可以去办公室找。导师和你聊了之后如果同意要你就会和你签

意向书。专业是开学之后再选。导师和选择的专业没太大关系,不过最好是选择一个和你想学的专业相关一点的导师。复试之前不用提前联系导师。

其他:

今年虽说题比去年难点,但也有很多高分的。最高392分, 380多的两个,370多的4个,360以下的比较多。

复试的也有很多名校和本校的,比如大连理工,北邮,天津大学,中山大学,华北电力等,很多都是往届生。所以竞争压力也挺大的,不过还好北航好像不太歧视非211的学生。所以不要考虑别的,好好准备初试和复试才是王道。

--------------------------------------------------------------------------------------------------------------------------------- 下面是收集到的其他的面试题:

1、类似于逻辑分析题一样的题目,某些题目有点像智力测试题,一般都会与概率、数据结

构的一些基本知识有关系,主要考察的应该是逻辑思维能力和解决问题的能力。

2、操作系统基本知识(像本人抽到的就是线程、进程的区别之类,还有人抽到什么处理的

五个步骤,我没学过这个所以记不清楚题目)

3、软件测试基本知识

4、数据库基本知识(从被抽到的题目来看大部分是数据库的基本理论知识,像关系数据库

的定义、三种范式之类的,另外此类题目似乎比较多)

5、软件工程的基本知识,题目不明,在我之前的似乎没人抽到,但复试通知里有明确写。

6、据说有人抽到计算机组成原理的题目,题目不明。

7、(数据结构)什么是树?什么是图?树和图有什么区别?

8、(操作系统)什么是系统调用?它和库函数调用有什么区别?

9、(数据库)什么是事务处理?……

10、(软件工程)什么是白盒测试?什么是黑盒测试?区别是什么?

由以上可以看出,面试的题目没有考察未来专业的特别专业性的知识,主要考察的还是计算机学科的基础知识。

--------------------------------------------------------------------------------------------------------------------------------- 下面是在网上找的前几届的一位学长专业面试经历,仅供参考:

面试的地点在一个会议室,敲门进去,对面坐了七、八个老师。交上复试通知上要求的个人简介和职业生涯规划,老师就让我做个自我介绍。因为我准备的自我介绍是英文的,结果用中文说一下子想不出来应该说些什么,讲了一些基本情况后就草草了结了。接着就是老师看你的材料,问一些问题。差不多是那种普通面试的问答了,问一些专业背景之类的,谈谈自己本科时的情况、曾经编写过什么程序、做过什么项目等等。我没被问到什么专业的问题,大部分是一些个人情况,有点像长辈和晚辈的聊天。这里要说下那个要交的“个人简介和职业生涯规划)。就我所见面试的老师对那个只是草草浏览一下,不会看得很细,所以假如哪一天MSE变得很火了(我相信那一天就在不久的将来……),而到时还要交这份材料的话,就一定要像写简历一样简洁地把最重要的东西写在最显眼的地方。

一阵接近闲聊的谈话之后,一个老师就让我抽题。一大把的纸条,让抽两个。抽出来后先把题目念一遍再回答。题目类型如上所述,很不幸,本人本科学过的也就C语言和数据结构(还好初试也就考这两个),其他的课程基本都没有学过,复试前因为不知道具体要问什么都是蜻蜓点水的看了一些书,不过自信自己平时经常看一些计算机杂志一些基本的知识还是知道的。所以当我读完第一道题时,就感觉不妙;读完第二题,感觉额头好大一滴汗……;读完第三题,有几个老师都笑了,说“他本科学机械的这些应该都没

学过的吧……”。我也只好尴尬承认自己对这方面都不太懂……。还好好心的老师又把纸条递过来让我再抽几道题,结果手气差到离谱,又是之前没有准备到的有关软件测试的题目,凭着印象用软件测试的基本理论胡诌了一番,只想向老师们证明:我真的有准备复试的,只是这运气…………最后还是那个给题的老师好心,帮我选了一个上面说到的第1类型的题目,和专业关系不大,轻松回答出来总算过了这关。

重庆邮电大学-软件技术基础--实验报告(耿道渠)

《软件技术基础》实验报告 实验名称:顺序表的操作 班级学号姓名 第9 周星期 2 、5,6 节成绩 一、实验目的: 1、掌握顺序表结构的实现方式; 2、掌握顺序表常用算法的实现; 3、熟悉利用顺序表解决问题的一般思路; 4、参照给定的顺序表的程序样例,验证给出的顺序表的常见算法,领会顺序表结构的优点和不足。 二、实验内容: 1、设计一个静态数组存储结构的顺序表,要求编程实现如下任务:(1)建立一个顺序表,首先依次输人整数数据元素(个数根据需要键盘给定)。 (2)删除指定位置的数据元素(指定元素位置通过键盘输入),再依次显示删除后的顺序表中的数据元素。 (3)查找指定数据的数据元素(指定数据由键盘输入),若找到则显示位置,若没有找到则显示0。 2、使用顺序表实现一个电话本的管理程序,电话本中的每条记录包括学号、姓名、手机号码和固定电话四项。要求实现菜单、初始化、添加、删除和显示等功能。 三、实验结果:

四、实验中遇到的问题及解决方法: 第一次编写C++,感觉力不从心,回去多看看PPT。

五、实验心得体会: 对顺序表的一些常用语句不熟悉,对顺序表的整体思路理解不深刻以后要加强练习 附:源程序(自行编写或修改的程序。若为修改程序请注明修改部分的功能,若为书上实例则可不附。) #include #include #include #include #define MAXSIZE 20 using namespace std; int num; typedef struct { string student_number; string name; string tel; string home_phone; int id; } TEL; void shuaxin(TEL *); void delet(TEL *);

1999-2016年北京航空航天大学911材料综合考研真题及答案解析 汇编

2017版北京航空航天大学《911材料综合》全套考研资料 我们是布丁考研网北航考研团队,是在读学长。我们亲身经历过北航考研,录取后把自己当年考研时用过的资料重新整理,从本校的研招办拿到了最新的真题,同时新添加很多高参考价值的内部复习资料,保证资料的真实性,希望能帮助大家成功考入北航。此外,我们还提供学长一对一个性化辅导服务,适合二战、在职、基础或本科不好的同学,可在短时间内快速把握重点和考点。有任何考北航相关的疑问,也可以咨询我们,学长会提供免费的解答。更多信息,请关注布丁考研网。 以下为本科目的资料清单(有实物图及预览,货真价实): 北京航空航天大学《材料综合》全套考研资料 一、北京航空航天大学《材料综合》历年考研真题及答案解析 2015年北京航空航天大学《材料综合》考研真题(含答案解析) 2015年北京航空航天大学《材料综合》考研真题(含答案解析) 2014年北京航空航天大学《材料综合》考研真题(含答案解析) 2013年北京航空航天大学《材料综合》考研真题(含答案解析) 2012年北京航空航天大学《材料综合》考研真题(含答案解析) 2011年北京航空航天大学《材料综合》考研真题(含答案解析) 2010年北京航空航天大学《材料综合》考研真题(含答案解析) 2009年北京航空航天大学《材料综合》考研真题(含答案解析) 2008年北京航空航天大学《材料综合》考研真题(含答案解析) 2007年北京航空航天大学《材料综合》考研真题(含答案解析) 2006年北京航空航天大学《材料综合》考研真题(含答案解析) 2005年北京航空航天大学《材料综合》考研真题(含答案解析) 2004年北京航空航天大学《材料综合》考研真题(含答案解析) 2003年北京航空航天大学《材料综合》考研真题(含答案解析) 2002年北京航空航天大学《材料综合》考研真题(含答案解析) 2000年北京航空航天大学《材料综合》考研真题(含答案解析) 1999年北京航空航天大学《材料综合》考研真题(含答案解析) 二、材料分析重点总结 三、金属学原理重点总结 四、金属学原理名称解析总结 五、物理化学复习总结 六、无机非金属材料复习总结 七、高分子物理复习总结 八、高分子化学复习总结 以下为截图及预览: 2015真题及答案

北航软件学院 软件工程 (专业课991 专业硕士 全国1月统考) 2012-2013复试经验分享

北航软件学院软件工程991 双证2012-2013年考研复试经验来自北航大神与大伙分享本人从中获益匪浅 2012年考研复试经验招收50人保送应该是25人(去年招收60人保送大约是31人) 复试线335 50 85 比2011年暴涨35分实际上前两年都没有正常的按照比例划线故意划了一个很低的线去年笔试之后就刷掉了一半多 复试分为三个阶段资格审查笔试面试还没有机试个人感觉未来很有可能加上 第一天资格审查得知复试33人拟录取25人初试成绩分布大约如下第一名400 390-400的两人368排在第10 341第26 336有4人应该是没有335分的所以实际最低复试线336 第二天笔试8点30分开始实际上最后到了32人(还有一个没来复试不知道是什么情况)先进行专业笔试复试说明上的范围是数据结构C语言数据库软件工程操作系统;但是实际上数据结构只有一个选择还出了一个JAVA的判断而并不在范围中的计算机网络占了大半 题型如下:选择15个30分填空15分判断20 大题35 第一个就给个ER图写建表查询语句什么的第二个网络的好像是数据传递过程的协议描述(没看完全不会)第三个是银行系统的数据流图考出来觉得40分就万岁了预感要被刷 英语笔试在休息半个小时后进行就是选词完型(4级里的新题型的一种)阅读整段翻译问答问答有两个用英语回答操作系统的作用和瀑布模型的过程整体难度个人感觉不足6级(本人大学没有看过一个英语单词6级至今未过可见应该是不难的) 笔试完毕后就通知了面试地点大家都认为笔试不刷人了结果到最后录取完了大家都不知道笔试多少分。。。。 第三天9点开始面试没有按照顺序谁进去都可以分两个教室一个教室英语面试就一个男老师人也很和蔼就是男音听得不是很习惯我一直都不适应男音英语囧面试就自我介绍讲到一半会被打断然后问我觉得自己的英语READING能力怎样我说很差结果他说

北航考研991考试大纲

991数据结构与C语言程序设计考试大纲(2013版)2013年《数据结构与C语言程序设计》考试内容包括“数据结构”与“C语言程序设计”两 门课程的内容,各占比例50%,试卷满分为150分。 《数据结构》部分 指定参考书:《数据结构教程(第二版)》唐发根编著北京航空航天大学出版社 一、概述 1.数据的逻辑结构与存储结构的基本概念; 2.算法的定义、基本性质以及算法分析的基本概念,包括采用大 形式表示时间复杂度和空间复杂度。 二、线性表 1.线性关系、线性表的定义,线性表的基本操作; 2.线性表的顺序存储结构与链式存储结构(包括单(向)链表、循环链表和双向链表)的构造原理; 3.在以上两种存储结构的基础上对线性表实施的基本操作,包括顺序表的插入与删除、链表的建立、插入与删除、查找等操作对应的算法设计(含递归算法的设计)。 三、堆栈与队列 1.堆栈与队列的基本概念与基本操作; 2.堆栈与队列的顺序存储结构与链式存储结构的构造原理; 3.在不同存储结构的基础上对堆栈与队列实施插入与删除等基本操作的算法设计; 4.堆栈和队列在解决实际问题中应用。 四、树与二叉树 1.树与二叉树的基本概念,基本特征、名词术语; 2.完全二叉树与满二叉树的基本概念,二叉树的基本性质; 3.二叉树与树、树林之间的转换; 4.二叉树的顺序存储结构与二叉链表存储结构; 5.二叉树的前序遍历、中序遍历、后序遍历和按层次遍历,以及在二叉链表基础上各种遍历算法(重点为非递归算法)的设计与应用; 6.二叉排序树的基本概念、建立(插入)、查找与平均查找长度ASL的计算; 7.哈夫曼(Huffman)树的基本概念,哈夫曼树的构造与带权路径长度(WPL)的计算。 五、图 1.图的基本概念、名词术语; 2.图的邻接矩阵存储方法和邻接表(含逆邻接表)存储方法的构造原理及特点; 3.图的深度优先搜索与广度优先搜索; 4.最小(代价)生成树、最短路径、AOV网与拓扑排序以及AOE网与关键路径的基本概念与求解过程。 六、文件及查找 1.顺序查找法以及平均查找长度(ASL)的计算; 2.折半查找法以及平均查找长度(ASL)的计算,包括查找过程对应的“判定树”的构造; 3.B-树和B+树的基本概念,B-树的插入与查找; 4.散列(Hash)表的构造、散列函数的构造,散列冲突的基本概念、处理散列冲突的基本方法以

北航计算机复试面试题

操作系统: 1.文件系统与数据库系统的区别,哪个效率更高,为什么。 2.进程上下文切换具体过程,就是什么实现的 3.BIOS的意思,程序的可移植性 4.、操作系统的基本概念 5.操作系统开机过程; 6.操作系统分哪些部分,进程管理包含什么内容; 7.操作系统我们所学的其她课程有什么关系,还就是操作系统就是个独立的课程 8.什么就是系统调用?它与库函数调用有什么区别? 计算机网络: 1.数据链路层就是干什么的 2.输入数据在网络层叫什么 3.分组的生命期,为什么要设置这个生命期 4.dns的工作过程 5.点击一个链接的网络过程; 6.网络模型,网络层协议有哪些,应用层协议有哪些 7.两台计算机中的进程进行通信,需要解决什么问题? 基础数学: 1.什么就是极限,什么就是趋近 2.极值的求法 3. 泰勒级数的展开式;为什么把一个简单的函数表示成那么麻烦的泰勒级数? 4.信息与数据的区别? 5.图形与图像有什么区别? 6.概率的全概率公式,高数的傅立叶级数,现代秩的概念 7.一枚硬币抛三次,至少一次正面的概率 8.什么就是图的同构 9.说一下数理逻辑的定义 10.矩阵的用途 11.线性相关与无关 12.离散数学包含那些部分; 13.集合的势,无限集合的大小比较,偏序,良序,全序,划分,欧拉图,Hamilton图 14.什么就是群 15.谓词逻辑与命题逻辑的区别 16.什么就是等价关系,什么就是子句,什么就是合取范式 17.什么就是二元关系 数据结构与算法: 1.什么就是二叉树 2.已知病毒特征码一百万个与文件一个,问用什么查找算法能尽快的检测出该文件就是否有病毒? 3.快排与插入排序那个更高效? 4.简单描述九宫格算法 5.学数据结构的意义; 6.离散数学的图论与数据结构图论的相同点与不同点 7.堆栈与堆的区别

2019北航软件学院软件工程考研专业课991考试大纲

2019北航软件学院软件工程考研专业课991考试大纲 2019年“数据结构与C语言程序设计”考试内容包括“数据结构”与“C 语言程序设计”两门课程的内容,各占比例50%。试卷满分为150分。 “数据结构”部分 一、概述 1.数据的逻辑结构与存储结构的基本概念; 2.算法的定义、基本性质以及算法分析的基本概念,包括采用大 形式表示时间复杂度和空间复杂度。 二、线性表 1.线性关系、线性表的定义,线性表的基本操作; 2.线性表的顺序存储结构与链式存储结构(包括单(向)链表、循环链表和双向链表)的构造原理; 3.在以上两种存储结构的基础上对线性表实施的基本操作,包括顺序表的插入与删除、链表的建立、插入与删除、查找等操作对应的算法设计(含递归算法的设计)。 三、数组 1.一维数组和二维数组的存储; 2.矩阵的压缩存储的基本概念; 3.对称矩阵、对角矩阵以及三角矩阵的压缩存储。 四、堆栈与队列

1.堆栈与队列的基本概念与基本操作; 2.堆栈与队列的顺序存储结构与链式存储结构的构造原理; 3.在不同存储结构的基础上对堆栈与队列实施插入与删除等基本操作的算法设计; 4.堆栈和队列在解决实际问题中应用。 五、树与二叉树 1.树与二叉树的基本概念,基本特征、名词术语; 2.完全二叉树与满二叉树的基本概念,二叉树的基本性质及其应用; 3.二叉树的顺序存储结构与二叉链表存储结的基本原理; 4.二叉树的前序遍历、中序遍历、后序遍历和按层次遍历,重点是二叉树在以二叉链表作为存储结构基础上各种遍历算法(包括非递归算法)的设计与应 用; 5.二叉排序树的基本概念、建立(插入)、查找以及平均查找长度ASL的计算。 六、图 1.图的基本概念、名词术语; 2.图的邻接矩阵存储方法和邻接表(含逆邻接表)存储方法的构造原理及特点; 3.图的深度优先搜索与广度优先搜索; 4.最小(代价)生成树、最短路径、AOV网与拓扑排序的基本概念。 七、文件及查找 1.顺序查找法以及平均查找长度(ASL)的计算; 2.折半查找法以及平均查找长度(ASL)的计算,包括查找过程对应的“判定树” 的构造;

北航计软实验报告一

北航计软实验报告一

————————————————————————————————作者: ————————————————————————————————日期:

计算机软件基础上机实验报告(一) XXXXXX班XXX 1.实验目的 掌握线性表在顺序分配下的插入与删除运算;掌握线性表的链式存储结构;掌握插入排序的方法;并掌握一种产生随机数的方法。 2.实验内容 1.产生1000个0至999间的随机整数,并以产生的次序存入一个数据文件中。 2.编制一个程序,依次实现以下功能: (1)?定义一个有序(非递减)线性表,其最大容量为1000,初始时为空。 (2)?从由1产生的数据文件中依次取前N个随机整数,陆续插入到此线性表中,并要求在每次插入后保持线性表的有序性。最后将此有序线性表打印输出。 (3)?在由(2)产生的线性表中,依在1中产生的次序逐个将元素删除,直至表空为止。 3. 以N=100及N=400分别运行2的程序,并比较它们的运行时间。 4. 编写一个程序,用插入排序依次将1中产生的1000个随机整数链接成有序链表(不改变原随机数在存储空间中的顺序)。 3.源代码与运行结果 #include<stdio.h> #include<stdlib.h> #include /** 1_1 产生1000个0至999间的随机整数,并以产生的次序存入一个数据文件(1_1.txt)中。 **/ main() { FILE *fo=fopen("1_1.txt","w"); int i,j; srand((unsigned)time(0)); for(i=0;i<=999;i++)fprintf(fo,"%d\n",rand()%1000); fclose(fo); printf("1000个随机数已输出至目录下1_1.txt文件\n");

软件技术基础教学大纲资料

软件技术基础》教学大纲 课程编号: 23000840 适用专业:电子信息类(非计算机专业) 学时数: 40学分数: 2.5 开课学期:第4 学期 先修课程: 《C 语言》 考核方式:笔试(闭卷) 执笔者:沈晓峰编写日期:2015 年3月审核人(教学副院长): 一、课程性质和目标授课对象:电子信息工程专业大学二年级本科生课程类别:学科拓展课程教学目标: 本课程是针对工科电子信息类本科生开设的一门学科拓展课程。着重培养学生在软件设计领域的基本素质,基本方法和设计理念。授课对象为大学二年级学生,课程任务是通过本课程的学习和相关实验的练习,使学生掌握数据结构、操作系统等软件技术的基本理论知识,具有一定的软件开发能力。 二、教学内容和要求 1、课堂理论教学要求和学时安排(32 学时) 1) C 程序设计(4 学时) (1)C 语言回顾,指针的基本概念、运算方法和使用( 2 学时)。 (2)结构体的基本概念和使用方法(2 学时)。 2)数据结构(20 学时) (1)数据结构的基本概念(2 学时):理解数据结构的基本概念;理解线性和非线性结构的概念。 (2)线性数据结构(9 学时):理解表、栈、队列等线性数据结构的概念,存储方式及基于不同存储方式的相关操作的实现方法。 a. 理解表的概念及顺序表的存储特点,掌握其创建、插入、删除等实现方法(2 学时); b. 掌握单链表、双链表、循环链表的创建、插入、删除方法( 2 学时); c. 理解栈的概念及结构特点,掌握顺序栈及链栈的出栈、入栈操作的实现方法 (2 学时); d. 理解队列的概念及特点,掌握顺序、循环队列的创建、出队、入队、判空、判满等操作。掌握链 队列的创建及出队、入队(2 学时); e. 理解数组的概念及二维数组的存放方式,掌握对称矩阵及稀疏矩阵的压缩存储方法 (1 学时)。

计算机软件技术基础实验报告Word版

计算机软件基础实验报告 姓名学号实验目的 1. 掌握C语言程序设计方法,并学会上机调试。 2. 熟悉Huffman编码源程序,并构造Huffman树。 实验内容 1.试设计一算法,从包括n个元素的数组中,求最大和最小元素,并使得当n 个元素为有序排列时,元素之间的比较次数仅为n-1次。 2.在给出的Huffman编码源程序基础上,要求画出Huffman树,求出与等长编 码相比时的压缩比。 实验要求 1.根据实验内容编写算法,并用 C 语言进行程序设计。 2. 将所编程序在计算机上调试通过,并全面测试。 实验结果 1.以一个含有8个元素的一维数组{1,2,3,5,7,8,9,12}为例,设计程序如下: #include int maxArray(int x ,int y); int minArray(int x ,int y); int main(void) { int i = 0 ; int array[8]={ 1,2,3,5,7,8,9,12} ; printf; do { scanf("%d",&array[i]); i++; } while(i < 8); int maxTemp = array[0]; int minTemp = array[0]; int maxIndex = 0; int minIndex = 0; for(i=1;i<8;i++)

maxTemp = maxArray(array[i] , maxTemp); minTemp = minArray(array[i] , minTemp); } for(i=0;i<8;i++) { if (maxTemp == array[i]) { maxIndex = i; } if (minTemp == array[i]) { minIndex = i; } } printf; return 0; } 运行结果如下: 2.Huffman编码源程序 #include #include #include #include #include typedef struct {unsigned int weight; //结点权值 unsigned int parent,lchild,rchild; //结点的父指针,左右孩子指针 }HTNode,*HuffmanTree; //动态分配数组存储哈夫曼树 typedef char **HuffmanCode; //动态分配数组存储哈夫曼编码表 void CreateHuffmanTree(HuffmanTree &,unsigned int*,int ); //生成哈夫曼树 void HuffmanCoding(HuffmanTree,HuffmanCode &,int ); //对哈夫曼树

北航数据结构与程序设计真题 2013年北航991真题及答案

2013年“数据结构与C程序设计”(代码991)试题 一、单项选择题(本题共20分,每小题各2分) 1.对于长度为n的线性表,建立其对应的单链表的时间复杂度为( )。 A.O(1);B.O(log2n);.O(n);D.O(n2)。 2.一般情况下,在一个双向链表中插入一个新的链结点,( )。 A.需要修改4个指针域内的指针;B.需要修改3个指针域内的指针; C.需要修改2个指针域内的指针;D.只需要修改1个指针域内的指针。 3.假设用单个字母表示中缀表达式中的一个运算数(或称运算对象),并利用堆栈产生中缀表达式对应的后缀表达式。对于中缀表达式A+B*(C/D-E),当从左至右扫描到运算数E时,堆栈中的运算符依次是( )。(注:不包含表达式的分界符) A.+*/-;B.+*(/-;C.+*-;.+*(-。 4.若某二叉排序树的前序遍历序列为50,20,40,30,80,60,70,则后序遍历序列为( )。 A.30,40,20,50,70,60,80;B.30,40,20,70,60,80,50; C.70,60,80,50,30,40,20;D.70,60,80,30,40,20,50。 5.分别以6, 3, 8, 12, 5, 7对应叶结点的权值构造的哈夫曼(Huffman) 树的深度为( )。 A.6;B.5;C.4;D.3。 6.下列关于图的叙述中,错误的是( )。 A.根据图的定义,图中至少有一个顶点; B.根据图的定义,图中至少有一个顶点和一条边(弧); C.具有n个顶点的无向图最多有n(n-1)/2条边; D.具有n个顶点的有向图最多有n(n-1)条边(弧)。 7.若在有向图G的拓扑序列中,顶点vi在顶点vj之前,则下列4种情形中不可能出现的是( )。 A.G中有弧; B.G中没有弧; C.G中有一条从顶点vi到顶点vj的路径; D.G中有一条从顶点vj到顶点vi的路径。 8.下列关于查找操作的叙述中,错误的是( )。 A.在顺序表中查找元素可以采用顺序查找法,也可以采用折半查找法; B.在链表中查找结点只能采用顺序查找法,不能采用折半查找法; C.一般情况下,顺序查找法不如折半查找法的时间效率高; D.折半查找的过程可以用一棵称之为“判定树”的二叉树来描述。 9.在一棵m阶B-树中,除根结点之外的任何分支结点包含关键字的个数至少是( )。 A.m/2-1;B.m/2;C.m/2-1;D.m/2。 10.若对序列(49, 38, 65, 97, 76, 13, 27, 49’)进行快速排序,则第一趟排序结束(即确定了第1个分界元素的最终位置)时,序列的状态是( )。 A.(13, 27, 49’, 38, 49, 76, 97, 65);B.(13, 38, 27, 49’, 49, 76, 97, 65); C.(13, 38, 49’, 27, 49, 97, 76, 65);D.(13, 38, 49’, 27, 49, 76, 97, 65)。 二、填空题(本题共20分,每小题各2分) 1.非空线性表在采( )存储结构的情况下,删除表的一个数据元素平均需要移动表中近一半元素的位置。2.将一个长度为n的单链表链接到一个长度为m的单链表后面,该算法的时间复杂度用大O符号表示为( )。 3.若完全二叉树的叶结点的数目为k,且最下面一层的结点数大于1,则该完全二叉树的深度为( )。

北航考研复试班-北京航空航天大学软件学院软件工程考研复试经验分享

北航考研复试班-北京航空航天大学软件学院软件工程考研复试经验 分享 北京航空航天大学(Beihang University)简称北航,是中华人民共和国工业和信息化部直属、中央直管副部级建制的全国重点大学,世界一流大学建设高校,211工程、985工程重点建设高校,入选珠峰计划、2011计划、111计划、卓越工程师教育培养计划、中国政府奖学金来华留学生接收院校、国家建设高水平大学公派研究生项目、国家级新工科研究与实践项目、国家级大学生创新创业训练计划、国家大学生创新性实验计划、全国深化创新创业教育改革示范高校,为国际宇航联合会、中欧精英大学联盟、中国西班牙大学联盟、中俄工科大学联盟成员,是全国第一批16所重点高校之一、80年代恢复学位制度后全国第一批设立研究生院的22所高校之一,也是新中国第一所航空航天高等学府。 北京航空航天大学创建于1952年,时名北京航空学院,由当时的清华大学、北洋大学、厦门大学、四川大学等八所院校的航空系合并组建,1988年4月改名为北京航空航天大学,1989年成为国家八五期间全国14所重点建设的高校之一,首批进入“211工程”,2001年进入“985工程”,2017年入选国家“双一流”建设名单。 启道考研复试班根据历年辅导经验,编辑整理以下关于考研复试相关内容,希望能对广大复试学子有所帮助,提前预祝大家复试金榜题名! 专业介绍 软件工程硕士(MSE)Master of Software Engineering.2002年,全国35所高校的软件学院成为国家教育部批准成立的首批全国示范性软件学院,授权培养软件工程硕士,其主要目的就是培养从事软件工程各领域工作,如软件开发、项目管理、网络安全等具有较高学历层次的人才,以满足我国软件行业迅猛发展对高层次人才的需求,据启文中国在职研究生网了解到,教育部发出专业硕士学位改革通知,自2014年,已经不再进行34所院校的自主招生,转而进行GCT统一考试。 招生人数与考试科目 ①101 思想政治理论②201 英语一③301 数学一④991 数据结构与 C 语言程序设计 复试时间地点

北航2003年计算机专业硕士研究生入学考试基础真题

北航2003年计算机专业硕士研究生入学考试基础真题 一、1、数据的存储结构通常可以有()。 A、两种,它们分别是:顺序存储结构和链式存储结构 B、三种,它们分别是:顺序存储结构、链式存储结构与索引结构 C、三种,它们分别是:顺序存储结构、链式存储结构与散列结构 D、四种,它们分别是:顺序存储结构、链式存储结构、索引结构与散列结构 2、删除非空线性链表中由指针p 所指链结点的直接后继结点的过程是依次执行动作()。(设链结点的构造为[data|link])。 A、r<-link(p); link(p)<-r; call RET(r) B、r<-link(p); link(p)<-link(r); call RET(r)C、r<-link(p); link(p)<-r; call RET(p) D、link(p)<-link(link(p)); call RET(p) 3、已知二维数组A[1:4,1:6]采用列序为主序方式存储,每个元素占用4 个存储单元,并且A[3,4]的存储地址为1234,元素A[1,1]的存储地址是()。 A、1178 B、1190 C、1278 D、1290 4、某堆栈的输入序列为1,2,3,4,下面四个序列中的()不可能是它的输出序列。 A、1,3,2,4 B、2,3,4,1 C、4,3,1,2, D、3,4,2,1 5、若某完全二叉树的深度为h,则该完全二叉树中至少有()个结点。 A、2 的h 次幂 B、2 的h+1 次幂 C、2 的h-1 次幂-1 D、2 的h-1 次幂+1 6、若一棵深度为6 的完全二叉树的第6 层有3 个也结点,则该二叉树共有()个也结点。 A、17 B、18 C、19 D、20 7、已知带权连通无向图G=(V,E),其中 V={v1,v2,v3,v4,v5,v6,v7},E={(v1,v2)10,(v1,v3)2,(v3,v6)11,(v2,v5)1,(v4,v5)4,

软件技术基础实验报告

《计算机软件技术基础》实验报告 专业_____________ 年级_____________ 学号_____________ 学生姓名_____________ 指导老师_____________ 南华大学计算机学院编

【实验报告】

I 实验要求 1.每次实验中有若干习题,每个学生至少应该完成其中的两道习题。 2.上机之前应作好充分的准备工作,预先编好程序,经过人工检查无误后,才能上机,以提高上机效率。 3.独立上机输入和调试自己所编的程序,切忌抄袭、拷贝他人程序。 4.上机结束后,应整理出实验报告。书写实验报告时,重点放在调试过程和小节部分,总结出本次实验中的得与失,以达到巩固课堂学习、提高动手能力的目的。 实验一线性表 【实验目的】 1.熟悉VC环境,学习如何使用C语言实现线性表的两种存储结构。 2.通过编程、上机调试,进一步理解线性表的基本概念,熟练运用C语言实现线性表基本操作。 3.熟练掌握线性表的综合应用问题。 【实验内容】 必做: 1.一个线性表有n个元素(n

北航991真题2012年答案

一、填空题 1 逻辑结构、存储结构、算法 2 链式存储结构 3 O(1) 4 8 4+4+3+4条边,一共16个结点,叶节点为8,也可以画图试试 5 BFGDECA 先找根节点到A,A的左子树B,右子树FDGCE,右子树的根节点C,C的左子树FDG,右子树E,左子树的根节点D,D的左子树F,右子树G 6 n-m+1,对于任何一个有子节点的结点而言,其子节点有且只有一个子节点右子树为空,再加上根结点也是没有右子树的 7 子图 8 4次依次比较65,15,30,37 9 n(n-1)/2 0+1+……+n-1 10 1,5,11,15,19,77,59,48,26,61 二、简答题 1. 矩阵总元素数量是100x100=10000,非零元素数量为200,200/10000=0.02<5%,所以是稀疏矩阵 2. 书上的概念,没啥好说的 3. 起泡排序法,因为选择排序每趟排序只会交换两个元素,第二趟交换了三个元素的位置,而泡排序每趟排序将最大值像泡一样交换到数组最右边,同时每趟排序过程中,如果相邻元素不符合要求的顺序,会交换两个相邻元素,符合所给结果 4最大递归深度是n,最小递归深度是log2(n+1)取上界

三、综合题 1. 第四句,p->rlink->llink = p做过类似的题目,修改四个指针,前两句做的是修改p 的左右指针,没什么问题,后两句做的是修改q的右指针和原q的右结点的左指针,但第四句错了,因为q的右结点已经修改了 2. 又是一道似曾相识的题目,有两种大的情况,第7层只有叶节点,还有一种情况是第7层还有分支结点。10+2^6-1=73,(2^6=64,64-10=54,2^7-1=127 127+108(107)=235(234) 3. 从度的角度更好一点,将顶点编号为1,2……n,第1个顶点可以跟其他顶点有n 条边,除去顶点1,第2个顶点可以跟其他顶点有n-1条边,而第n-1个顶点可以跟第n个顶点有一条边,归纳总结为n+(n-1)+……+1=(n-1)xn/2 4. 90,30,50,10,80,20 || 90,80,50,10,30,20 || 90,80,50,10,30, 20 || 90,80,50,30,10,20 || 90,80,50,30,20,10 四、算法设计题 判断一个序列是否是有向图的拓扑序列,简单 typedef int vertype;//防止无法编译用,实际做题删除 typedef struct edge { int adjvex; struct edge*next; }ELink;

最新北航计算机复试面试题

操作系统: 1.文件系统和数据库系统的区别,哪个效率更高,为什么。 2.进程上下文切换具体过程,是什么实现的 3.BIOS的意思,程序的可移植性 4..操作系统的基本概念 5.操作系统开机过程; 6.操作系统分哪些部分,进程管理包含什么内容; 7.操作系统我们所学的其他课程有什么关系,还是操作系统是个独立的课程 8.什么是系统调用?它和库函数调用有什么区别? 计算机网络: 1.数据链路层是干什么的 2.输入数据在网络层叫什么 3.分组的生命期,为什么要设置这个生命期 4.dns的工作过程 5.点击一个链接的网络过程; 6.网络模型,网络层协议有哪些,应用层协议有哪些 7.两台计算机中的进程进行通信,需要解决什么问题? 基础数学: 1.什么是极限,什么是趋近 2.极值的求法 3. 泰勒级数的展开式;为什么把一个简单的函数表示成那么麻烦的泰勒级数? 4.信息和数据的区别? 5.图形和图像有什么区别? 6.概率的全概率公式,高数的傅立叶级数,现代秩的概念 7.一枚硬币抛三次,至少一次正面的概率 8.什么是图的同构 9.说一下数理逻辑的定义 10.矩阵的用途 11.线性相关与无关 12.离散数学包含那些部分; 13.集合的势,无限集合的大小比较,偏序,良序,全序,划分,欧拉图,Hamilton图 14.什么是群 15.谓词逻辑和命题逻辑的区别 16.什么是等价关系,什么是子句,什么是合取范式 17.什么是二元关系 数据结构与算法: 1.什么是二叉树

2.已知病毒特征码一百万个和文件一个,问用什么查找算法能尽快的检测出该文件是否有病毒? 3.快排和插入排序那个更高效? 4.简单描述九宫格算法 5.学数据结构的意义; 6.离散数学的图论和数据结构图论的相同点和不同点 7.堆栈和堆的区别 8.递归变成非递归需要什么(堆栈) 9.堆栈溢出是怎么回事儿 10.算法的几种策略,迪杰斯特拉算法 11.要得到文件的后N行,需要什么数据结构实现 12.数据库中B+树和B-树的区别 13.什么是树?什么是图?树和图有什么区别? 14.矩阵相乘的时间复杂度是多少? 15.现在有一未知大小的文件,里面是单词的集合,现要将文件读入内存,问采用什么存储结构较好? 数据库: 1.数据库查询语句怎样写效率更高 2.使用sql语句实现图的某一顶点可达的该图的其他顶点的查找 3.数据库完整性措施; 4.如何保证数据的一致性 5.数据库的基本理论知识,像关系数据库的定义、三种范式 6.什么是事务处理? 软件测试: 1.工程使用什么测试手段,什么模型 2.软件测试时软件开发过程的哪个阶段的 3.什么是白盒测试?什么是黑盒测试?区别是什么? 计组: 1.冯诺依曼系统结构 2.冯诺依曼机的存储思想 3.做过哪些实验 4.程序和数据分别怎么存储(其实也就是问冯诺依曼机和哈佛机的区别 编程语言 1.什么是C++动态联编技术,为什么C++要引入动态联编 2.虚函数作用,主要在应用中 3.纯虚函数的作用,这也主要在实际应用中

19考研必看北京大学软件工程专业经验分享

19考研北京大学软件工程专业考研经验指导 在没考完之前,我就总想着考完了我一定要写篇长经验帖,考完了,又是忙着论文,忙着兼职,now!以下是这一年给我印象最深的两句话:考研说难很难,说容易也容易、热闹是别人的,我们什么也没有。当你经历了整个过程,便也明白了其中的酸甜苦辣。所以希望19的你们,在这一路上能更加轻快,顺畅一点。关于选学校 在现在这个时间段,19的小可爱们也应该大致有自己的目标学校和专业了吧,如果还没确定就先复习英语、政治和数学呀!不能让自己松懈了。在暑假前要定下学校哦,暑假就要开始专业课的复习了。我最想说的是选学校一定要选择自己喜欢的,能够使你坚持到最后的。如果你实在不知道选那里,就从区域开始吧。 关于软件工程 说一下软件工程的基本情况,这几年这个专业慢慢的热起来,比较好的软件工程北京这边的学校像北大、清华、北航、北交、北邮。我当时关注了软件工程考研联盟,好多软工考研知识就是从那里得到的。北京地区阅卷较严,所以考北大的同学统考科目分数比起一些水区院校研究生的分数较低,且软件与微电子学院最近三年的报考人数增加明显,考研北大软件工程和计算机技术的难度越来越大。北京大学软件工程全日制专业硕士公共课考试科目为英语一和数学一,难度高于其他院校专硕的英语二和数学二,专业课有很独特的学院风格,需要有针对性的准备。我当初是报了班的,毕竟要考北大,而且还想一次性考上。 关于参考书 我推荐《数据结构》(C语言版)严蔚敏、《计算机操作系统》汤子瀛、《计算机网络》谢希仁,这三本书,当然我在新祥旭上专业课期间还用到了新祥旭的内部应试宝典,还给我提供了北大的本科课件和其他名校cs,ee的各种真题,经典模拟题。 关于专业课复习 当时老师了解了我的情况之后备好课来给我上课的,他把参考教材给我仔细的讲了一遍,后来又根据科目的考试要求,对各个重点章节,考试重点,考试难点进行系统的讲解,让我快速建立起了复习框架。 后来还对我进行了习题专项训练,根据考试内容不同的侧重点,配合习题进行深入的、针对性训练。包括真题讲解,超级细心。课下我自己有不懂的就经常问老师嘛,老师也没嫌我烦,看到就立刻回复我了。所以我觉得学弟学妹们如果不知道自己怎么复习的话,也可以跟着这个学习节奏来。 关于公共课 英语和政治就不多说什么了,英语多做真题,每篇阅读都要做到超精读,推荐大家使用张剑的黄皮书真题。词汇从真题里背就可以了。 政治就用肖老爷子的肖四、肖八和肖1000就可以了,堪称大神了。后期要好好背。 数学很重要,全靠数学和专业课拉分,我的大部分时间都给了数学和专业课。数学看张宇的书和视频。多练题,要先自己琢磨题,自己找思路,不能老靠着答案找思路,最好自己整理错题本,数学也是有知识点的,多锻炼自己的做题思维。

北航计算机软件技术基础实验报告计软实验报告3——冒泡排序和快速排序

实验报告 实验名称冒泡排序和快速排序 班级 学号 姓名 成绩

#include #include #define N 20 //定义用于比较和交换计数的全局变量 static int compare, move; int main() { int data1[N], data2[N]; int i; void bubbleSort(int[20]); void quickSort(int[20], int, int); //创建两个相同的数组用于两种排序方法 for (i = 0; i

软件技术基础实验一

软件技术基础实验一单链表的各种基本运算的实现

单链表的各种基本运算的实现 一. 实验目的: 1. 熟悉c语言上机环境; 2. 实现单链表的创建; 3. 掌握单链表的基本操作:插入、删除、输出等运算; 二. 实验内容: 编写一个程序,实现单链表的各种基本操作,并在此基础上设计一个主程序完成如下功能: 1.初始化单链表: 2 .依次采用头插法插入从文件中读取的多个元素; 3. 输出单链表; 4. 在第四个元素位置上插入从文件中读取的单个元素; 5. 删除该单链表的从文件中指定序数的元素; 三. 完整的源程序 #include #include #include #include #define max 10 #define num 6 int a[20]; int i; typedef struct link { int data; struct link *next; }link;

/*初始化单链表*/ initlink(link *L) ( L= NULL; L= ( link *)malloc(sizeof(link)); /* 建立表头结点*/ L->next = NULL; L->data = 0; } void hcreat(link *L) /*头插法插入从文件中读取的多个元素*/ ( link *s; L->next=NULL; s=(struct link*)malloc(sizeof(struct link)); int i=0; FILE *fp; if((fp=fopen("h:\\a.txt”,"r"))==NULL) printf("error!\n"); printf("文件中的数为:\n"); while(!feof(fp)&& idata=a[i]; s->next=L->next; L->next=s; i++; } fclose(fp); } void print(link *L) /* 输出单链表*/ ( link *p=L->next; while(p!=NULL) ( printf ("%d ",p->data); p=p->next; } printf("\n"); int insert(link *L, int i) ( int j,m;

北航2015年考研991科目的答案

北航2015年考研991科目的答案 一、单项选择题 1.C 2.A 3.D 4.B 5.C 6.B 7.D 8.A 9.C 10.D 二、填空题 1.顺序2.O(m) 3.log2k+1 4.235 5.2(n-1) 6.该有向图中不存在回路7.2.9 8.m-1 9.插入排序法10.9 三、综合题 1.答:(1)多个堆栈共享一个连续的存储空间,可以充分利用存储空间,只有在整个存储空间都用完时才能产生溢出,其缺点是当一个堆栈溢出时需要向左、右栈查询有无空闲单元。若有,则需要移动相应元素和修改相关的栈底和栈顶指针的位置。当各个堆栈接近溢出时,查询空闲单元、移动元素和修改栈底栈顶指针位置的操作频繁,计算复杂,并且耗费时间。(2)每个堆栈仅用一个顺序存储空间时,操作简便。但难以确定初始分配存储空间的大小,空间分配少了,容易产生溢出,空间分配多了,容易造成空间浪费;并且各个堆栈不能共享空间。 (3)一般情况下,分别建立多个链接堆栈不考虑堆栈的溢出(仅受用户内存空间限制),缺点是堆栈中各元素要通过指针链接,比顺序存储结构多占用存储空间。2.(T->lchild==NULL && T->rchild==NULL) T->lchild T->rchild 3.(由于图表显示限制,此题答案见指定教材(《数据结构教程第二版》(2012年4月第7次印刷)) 第418页8-16题)4. (1).根据α=散列表中存入的元素数/散列表的长度,得到表的长度为18,因此,合适的散列函数应该为H(k)=k MOD 17。 (2).(由于图表显示限制,此题答案见指定教材(《数据结构教程第二版》(2012年4月第7次印刷)) 第428页9-15题) 四、算法设计题SORT(int A[ ], int n) { int ,i, j, min, max, temp; i=1; while(i<=n/2){ min=i; max=i; for(j=i+1;jA[max]) max=j; } /* 确定某趟排序的最小值元素和最大值元素*/ if(min!=i){ temp=A[min]; A[min]=A[i]; A[i]=temp; } /* 交换A[min]与A[i]的位置*/ if(max!=n-i+1) if(max==i){ temp=A[min]; A[min]=A[n-i+1]; A[n-i+1]=temp; } /* 交换A[min]与A[n-i+1]的位置*/ else{ temp=A[max]; A[max]=A[n-i+1]; A[n-i+1]=temp; /* 交换

相关文档
相关文档 最新文档