查看: 23745|回复: 15

西南交通大学计算机硕士简介(性价比超高的211、985计算机考研院校)

[复制链接]

1

主题

9

帖子

17

积分

王道论坛实习道友

Rank: 1

考研年份
2007
报考学校
南京理工
本科学校
福建工程学院
注册时间
2014-3-18
最后登录
2014-7-10
发表于 2014-5-28 14:52 | 显示全部楼层 |阅读模式
西南交通大学
信息科学与技术学院
2014年
计算机/软件工程/信息安全 硕士研究生入学考试
840 数据结构与程序设计 / 959 数据结构

初试点评 (免费资料,请勿掏钱购买!谁掏钱,我跟谁急)
Powered by 未休矣前言
“我想说,真正牛逼的,不是那些可以随口拿来夸耀的事
迹,而是那些在困境中依然保持微笑的凡人。 ”
—摘自知乎“陈浩”
“这是一件很有意义的事,用一份开源的资料,献给
我们的青春。 ”
—鹏鹏未休矣
于眷诚斋
目录常识扫盲、经验汇总................................................................................................................1
西南交通大学2012年硕士研究生入学考试试卷................................................................ 6
西南交通大学2011年硕士研究生入学考试试卷..............................................................12
西南交通大学2010年硕士研究生入学考试试卷..............................................................19
西南交通大学2008年硕士研究生入学考试试卷..............................................................27
西南交通大学2007年硕士研究生入学考试试卷..............................................................37
西南交通大学2006年硕士研究生入学考试试卷..............................................................46
可以参考的“答案”.................................................................................................................57
补充资料—常考的一些算法................................................................................................... 741
常识扫盲、经验汇总
1.西南交通大学简介
2.西南交大信息科学与技术学院 简介
3.西南交大 研修生简介
4.西南交大信息学院 学硕/专硕情况简介
5.西南交大信息学院 录取规则与奖学金评选规则
6.西南交大计算机/软件工程/信息安全 简介
7.西南交大计算机/软件工程/信息安全 历年录取情况
8.西南交大计算机/软件工程/信息安全 初试专业课复习方法
9.如何找导师?
10.如何联系上师兄师姐?
11.是否有必要联系导师或师兄?
12.关于本书
1、西南交通大学简介
西南交通大学位于四川省成都市,肇建于 1896 年,百年老校。是国家首批“211 工程” 、
“特色 985 工程” (可以简单的理解为 985备胎的意思,注意,不是 985,而是备胎) 、 “2011
计划”建设高校以及正式设有研究生院的全国重点大学。 “大交通”类学科比较突出。学校强
势院系为“土” “机” “电” ,现在的主要院系为“土” “机” “电” “信” “运” 。拥有 4 名中国科学院院
士,8 名中国工程院院士(含两院院士) 。学校整体排名在全国大概 40~50 名。主校区为犀2
浦校区,招收一本学生;峨眉校区,招收二本学生。每年招收的本科生在大部分省份需要高
出一本线 40 分 左右;峨眉校区则为一本线左右。四川省本省生源约占 1/3。每年招收的
硕士研究生 3000 多名(报名人数稳定在 1W+) 。博士较少,相当一部分是本校直博或硕博
连读。
2、西南交大信息科学与技术学院 简介
1)科研环境:一般系主任级以上导师的实验室,空调、 电脑都是标配。配置上随便
一个硬盘分区都是 1T+,运气好的话,给配个四五万块的服务器玩玩也是正常的。2014 年
起,信息学院整体搬迁至犀浦校区,住宿、办公环境立马提升两个档次。
2)排名情况:信息学院由于每年招收硕士研究生数量为 300~400 名,人数上排名第
二,因而成为西南交大几个大院之一。主干学科为三类专业:通信类(通信、信号) 、自动
化类(交控、双控)和计算机类(计算机、软件工程和信息安全) 。其中通信和交控比较生
猛,计算机相对偏弱(本科通信 7 个班,计算机才 4 个班) 。根据教育部 2012 年学科排名,
通信排 20 名,计算机科学与技术排 38 名,软件工程排 42 名。
3)信息学院与 CAD 的关系:CAD(Computer Aided Design,计算机辅助设计)
中心处在校外,距九里校区较近。CAD的学生都属于信息学院,并且编入同一班级,同一宿
舍,上同样的课,同等资格评奖学金,拿同样的文凭。研一都一样,区别在研二必须跟着
CAD 的导师去 CAD 中心实习,做项目。除一部分是冲着孙林夫大 BOSS 的名号而保研过去
的,每年有近 30 个缺额用于接收复试被信息学院刷掉的学生。 (网上黑信息学院的要么是
复试前联系大 BOSS 遇阻,被吓的不行,不敢去复试就发帖找安慰;要么是初试高分,复试
不认真被信息学院刷掉就一把鼻涕一把泪网上哭诉,都没注意到还有 CAD 二次复试。 )3
4)考研难度:虽然计算机的整体水平跟南航、南理差不多一个档次。但鉴于年年招不
满(408统考时代) ,而且初试专业课简单到默默的流下感动的泪水,可以说西南交大计算
机是最好考的 211,没有之一(13 年是统考后自主命题第一年,参考性适当打折,谨慎参
考)。
3、西南交大研修生 简介
西南交大研修生招收对象为:具备本年度参加研究生统考,且准备报考西南交大任一专
业的人员,每年7、8月份报名(在暑假期间,信息学院官网会贴出招生通知) ,9月随当届
研究生一起上课。一边学习研一课程,一边复习准备考研。研修生虽是统考生身份,但是享
受本校学生待遇(只要过初试线,优先录取) ,研修生身份3 年(不含当年,含当年就是 4
年)内有效。学费 6000 元/年,学制 1年。安排住宿,校内,办理一卡通。研修时所修学
分在录取以后,可以转换,更可以申请提前毕业。
一般“土” “机” “电”这类比较难考的学院研修生比较多,信息学院往年研修生大概 20 人
左右,主要是报考通信的,报考计算机的一般 4~5 人。
4、西南交大信息学院 学硕/专硕情况简介
1)学制:西南交大信息学院的专硕在招生头年是 2 年制的,后来可能是年限过短,导
致质量稍差,现在一律改成 2.5~3 年的学制,与学硕相同。
2)学硕与专硕的相同点:选课相同,主要的课程都基本相同,想怎么选就怎么选,反
正都是选着玩,研究生阶段主要的还是靠自学。奖学金评比相同,而且学硕与专硕是分开评
比。住宿相同,大部分导师学硕专硕都收,在实验室基本也是同等对待。所修学分基本相同,4
学硕 26 个,专硕 30 个(含 5个专业实践分)
注意:很少有导师会指明只要学硕,连彭强这样的大牛也带了计算机专硕(别窃喜了,
人家是保研的)。导师都希望招到有用的人才,因此,你只要给导师一个充足的理由,让他
情愿选择你,而不是选择本校保研的学硕。
3)学硕与专硕的不同点:学硕必须要发表一篇核心期刊的论文,才有答辩资格。而专
硕无此要求。因此,一小部分导师点名要学硕的原因就是,学硕得老老实实的在实验室敲代
码,干不完论文写不出。
5、西南交大信息学院 录取规则与奖学金评选规则
1)录取规则:(初始总分/5)*60% + 复试成绩*40%=总成绩 (均是百分制)
2)奖学金评选规则:
第一学年按照统考分数、复试笔试分数、机试分数各占 60%、30%、10%评选。
第二学年按照课程成绩 70%、中期考核 30%评选。
注意:1)信息学院的录取规则和奖学金评选是两个不同的公式。
2)信息学院实行考生、导师双向选择制。先由考生自行联系导师,再按总成绩
划定录取线,之后由导师从过录取线的名单中选择考生。一定程度上保护了考生权益。
3)复试成绩包括笔试、机试、英语口试、专业面试四个部分,其中口试和面试
不计入奖学金评选公式。
4)奖学金等级依次为:
一等(10%):全免学费 10000 元/年 + 生活补助 500 元/月
二等(40%):免 2/3 学费 6667 元/年 + 生活补助 300 元/月
三等(15%):免 1/2 学费 5000 元/年 + 生活补助 200 元/月5
四等(15%):免 1/3 学费 3333 元/年 + 生活补助 200 元/月
不同专业分开评选、学硕专硕同等对待且分开评选。保研的只有一等和二等两个等级。统考
生会政策性的给 1~2 个一等奖学金名额。(通信初试 400 分左右,计算机 360 分左右)
3)公平性问题:信息学院至少在我们这届是还算公平的,本校的只保证录取,复试不
好,照样被调剂到 CAD 中心,奖学金评选上也是严格按照上述公式。计算机学硕专硕一共
两个统考生一等奖学金名额,均被外校的拿走。只是网上信息量少,容易让人想入非非。
6、西南交大计算机/软件工程/信息安全 简介
1)本校、保研情况:信息学院本科整体保研率在 17%左右,前面一小撮可以保校外,
其余校内。 西南交大计算机每年保研的学生占研究生招生总人数的 30%左右。虽然官方排名
比软件工程高,实际上,软件比计科更强。每年都有从计科保到软工。信息安全每年招收研
究生比较少,而且本科阶段的信息安全/网络工程已经停止招生,招生名额并入通信、计算
机。算上自觉考本校和考外校被刷,调剂回本校的。本校生总占比 40%~60%
2)研究方向:由于背靠通信和交控,师资力量充足(百度“李天瑞、孙林夫”等的时候,
请保持平和的心情,有一部分是老板自己编辑的) ,老板项目比较多,而且学科交叉明显。
比如,数字图像处理,信号的在做,计算机的也在做,大家还是同一个实验室,每周还开会
交流交流,探讨一下人生。再如,老蒋的单片机实验室,双控、通信和计算机都有。
7、西南交大计算机/软件工程/信息安全 历年录取情况
在 09~12 年 408 全国统考时代, 西南交大国家线都年年招不满, 学硕上线基本个位数,
12 年计算机专硕共录取 31 人,推免 7人,统考过线 8人。
13 年复试线为国家线,除了软件工程专硕多出 2人,其余都招不满(复试计算机学术6
26+14(调剂) ,计算机专硕 24,软件学术 14,专硕 22。计划招生是 30,30,15,20.最后
录取是计算机学硕 38 个,计算机专硕 32 个,CAD 包括在里面) ,分数梯度明显,高分、 中
等分、低分都有。计算机比软工分数相对高一些,计科最高分 380+,尤其注意复试很晚,
并且收 211 调剂生与一志愿直接参加复试。
虽说招不满,但是可能会象征性的刷掉最掉一个(需要同时满足俩条件,初试分巨低并
且复试巨酱油) ,又由于拥有西南交大 CAD 中心这个巨型备胎,每年缺额近 30 人。复试被
刷的被通知去 CAD 面试,所以,至少目前是只要过线,没有考不上的。
8、西南交大计算机/软件工程/信息安全 初试专业课复习方法
1)官方指定教材:
1、《数据结构》(C 语言版)严蔚敏,吴伟民编,清华大学出版社
2、《C程序设计》谭浩强编,清华大学出版社,第三版
2)复习方法:作为一名数学专业跨考的学生,鄙人斗胆推荐一种方法。如果之前摸过
上述课本,懂那么一点点,问你图的定义是什么?不知道。但是起码不会把一棵二叉树认成
图的水平下。6 月份以前无须看专业课,7、8 月猛看数学,猛做数学题,9 月份开始,每
天一晚上看专业课,即可。挑一本合适的辅导书。教材+真题+辅导书习题,来回过三遍,
120+分数问题不大。
3)老罗推荐的方法:对计算机而言,目前市场并无权威参考书籍,水平都是参差不齐,
甚至错误百出(尤其是教育部考试中心那本,错误居多) 。稍好一点的有清华李葆春的《数
据结构习题与解析(B 级) 》 ,另外推荐两个系列的书。此两系列书均出自论坛,
王道论坛:http://www.cskaoyan.com/7
天勤论坛:http://www.csbiji.com/
前者出自各大名校优秀考研学生(985 为主) ,单科和全书均有(主要面向统考,所以
可以自己酌情选择) ,王道论坛是计算机考研方面最好的论坛。后者是新秀,最近两年才出
来,主力是浙大学生,也有自己的辅导书。王道的书稍难点,天勤的书更注重基础,尤其适
合基础很差和跨考的同学使用。选择书籍可以去论坛试读,交流(书只是论坛的一部分, 论
坛主要是计算机考研交流平台) 。
.最后再强烈推荐一下数据结构 1800 题, 集合了近几十年各大名校的数据结构考研题,
非常好。再者就是真题了,不用多说。
4)辅导书选择:以下就市面上常见的和绝版的书,结合本人使用经验,进行点评。
复旦版《习题精编》 :这是一本无数跨考学子买的第一本计算机习题集处女书,习
题之基础的程度让人产生一种计算机专业就是“人傻” “钱多” “速来”的快感,然而到了考场就
会不自觉的发出呜呼哀哉的感叹。在 408 时代,它的作用就是在 6 月份以前的第一轮复习
给人一种自我陶醉感,好让你安心的扎在计算机专业。后 408 时代,可以摒弃。
高教版《计算机基础综合大纲解析》 :这本书给人的整体评价是“字小” ,如果非要加
一个修饰词,那就是“还是字小” 。总有些投机党,抱着一副“我钱都花了,总得透几个题吧”
的想法,妄图从中找到 408 原题,最后在考场上无一不受到正义的制裁。客观的说,这本
书上一些题让无数跨考学子闻所未闻,见所未见,很符合 408 真题的德行。用来准备西南
交大的计算机考试?同学,你想多了。
天勤版《习题集》 :由于本人用的是第一版,恰好又遇上抄袭事件。我对这本书好感
不足。整体评价:题量少,难度适中,解析过于详细,感觉就像一个傻小子对自己的女神,8
展开无限闯关模式似得。最关键的,里面的题目绝对不会出现在西南交大的试卷上。
王道版《习题集》 :这本书题量很大,有时光做一面的大题就得用两三个晚上。选择
题比较简单,正常人都有 80~90%的正确率。算法题题目巨多,有挑战。唯一不足的是解析
过于简单(相对写书的大牛来说,这已经写的够详细了) 。有空可以做做,尤其是其中的算
法题。
《1800 题》 :这本书老罗推荐做下选择和填空。我觉得可不做。原因,这本书没有
答案详解,当年本人也是在某 TOP 10 的 985 同学的远程答疑下才勉强吃透,吃不透的书
不做也罢。指望猛背答案瞎撞上几个?您以为这是期末考试呢?况且这本书错误比较多, 学
渣都发现不了。很多题型还不符合西南交大计算机的胃口,号称万年都不会考的题,做了有
啥用?虽然一部分选择题跟真题长得一模一样, 但是在下面这本神书面前, 都是浮云! 浮云!
李春葆版《数据结构习题与解析》:这就是一本神书,超五星好评!真棒!如果非要
给它一个定义,那就是“西南交大计算机历年真题题库” 。这本书已绝版,市面上不流通, 只
能在淘宝找到影印版。解答详细,知识讲解细致。该书有 A 级和 B 级两个版本,由于我本
人是在考前一个月才买到的 A级,时间仓促。至于 B 级如何,我这辈子也不知道了。
9.如何找导师?
百 度 一 下 西 南 交 大 研 究 生 院 的 导 师 个 人 主 页 ,
http://homepage.swjtu.edu.cn/Hom ... e=user&yuanxiID
=4
其次是西南交大信息学院,http://sist.swjtu.edu.cn/
均有导师详细情况,譬如研究方向、收学生的要求、办公室电话等等。
个人主页上有详细的研究方向,而信息学院的网站还配置了导师的行政职务,一般认
为,系主任级以上的导师项目巨多,而且给配台电脑是必须的。实验室主任以上的导师, 不9
一定会配电脑,但是科研水平有保证,可以认为是大牛级,实验室主任级导师一般来说, 学
硕专硕都收, 对初试分数要求也不高, 过线就要 (像李天瑞这种保研的都争破头的导师除外) 。
10.如何联系上师兄师姐?
老罗认为,联系师兄姐,还是论坛为主:
1.考研论坛计算机版或交大版 bbs.kaoyan.com
2.王道论坛 http://www.cskaoyan.com/
3.天勤论坛:http://www.csbiji.com/
4.交大研究生师兄姐经常出没的论坛:天佑斋社区 或者 bbs.swjtu.com
但是本人提供一种方法:网上都有上一年度的信息学院研究生拟录取名单,根据名单上
的名字,请平静的打开人人网和 QQ 的朋友网,键入“西南交大” 、 “姓名” 、 “入学年份” 。见证
奇迹的时刻到了,按下回车,上一届保研的学长个人主页将一览无遗。那么多人,总有一部
分是玩人人的,玩人人的总有一部分会通过你的好友请求。只要联系到了一个学长,呈现在
你眼前的,将是一个整建制的硕士班。此方法适用于复试时找自己同届的保研同学。
11.是否有必要联系导师或师兄?
老罗认为:
1.关于联系导师:个人观点,没必要,过线再联系
2.关于联系师兄姐:
一般愿意在论坛留下联系方式的师兄姐都是很乐意帮助学弟学妹的, 但是最基本的请注
意礼貌,这不是义务。也没有什么内幕资料,不要一上来就问泄题否之类的问题,这既是对10
交大也是对各位师兄姐的侮辱。还有爱耍宝的,先把这个简单问题思考清楚了再来耍----
一双端队列,按 1,2,3,4 的顺序入队,请写出其出队情况(邱,这句可以考虑删掉) (不
好意思,我想保留这句,by 邱) 。对于每一个虚心爱学的学弟学妹,师兄姐们是没有理由不
帮助你们的。
一句话---都是过来人,你的伤痛,我们懂。
12.关于本书
这是一套开源式免费资料,原则上原作者不再更新,任何人都可以拿去修改,发布, 无
须授权。如果有必要,哪怕是我们的名字,也请尽管舍弃,前提是免费发布。
本套资料从 X 德书店《红宝书》和 X宝网卖的《资料汇编》(蓝宝书),取其真题,去
其广告,结合过来人的亲身经历整理而得。 原作者是拿到一等奖学金的外校学生,很清楚
初试专业课真正需要的是什么,因此,本套资料在布局上是比较合理的。
在考研的路上,并不是所有人都可以平安的到达终点,总有一些人,因为这样、那样的
原因,而与理想失之交臂,甚至是明明触手可及,却差那么一丁点儿。我这人就是见不得别
人掉眼泪, 如果我苦逼一周的时间而能帮助上那么一两个迷茫的同学, 那么我就心满意足了。
在此,感谢那些曾经帮助过我们的学长们(没遇到过学姐,本套资料也没有学姐参与) ,
以及 13 级 7班和 10 班的同学们。
时间仓促,难免有遗漏。如遇到未说明到的问题、困惑开导、打鸡血、情感咨询等,
请联系 金牌客服: 老罗 扣扣:1045348996
备胎(原作者) :未休矣 扣扣:260197725
山西的老乡,请联系 鹏鹏 扣扣:33469123611
2013.9.11
试题代码: 959 试题名称:数据结构
机密★启用前
西南交通大学 2012 年全日制硕士研究生
入学考试试卷
试题代码:959
试题名称:数据结构
考试时间:2012 年 1月
考生请注意:
1. 本试题共4题,共6页,满分150分,请认真检查;
2. 答题时,直接将答题内容写在考场提供的答题纸尚,答在试卷上的内容无效;
3. 请在答题纸上按要求填写试题代码和试题名称;
4. 试卷不得拆开,否则遗失后果自负。
一、单项选择题(本大题共 25 题,每题2 分,共50 分)
1. 以下属于数据的逻辑结构的是【 】
A.顺序表 B.哈希表 C.线性表 D.单链表
2.计算机所处理的数据一般具有某种内在联系,这是指【 】
A.数据与数据之间存在某种关系 B.数据元素与数据元素之间存在某种关系
C.元素内部存在某种结构 D.数据项与数据项之间存在某种关系12
3.线性表是具有 n个【 】的有限序列(n≥0) 。
A.表元素 B.字符 C.数据元素 D.数据项
4.若某线性表最常用的操作是存取任意指定序号的元素和在表尾进行插入和删除,则选用
【 】的存储方式最节省时间。
A.顺序表 B.双链表
C.带头结点的双循环链表 D.单循环链表
5.若长度为 n的线性表采用顺序存储结构,在第 i 个位置插入一个新元素的算法的时间复
杂度为【 】 。
A.O(0) B. O(1) C. O(n) D. O()
6.如果对线性表的运算只有两种,即删除第一个数据元素,在最后一个数据元素的后面插
入一个新数据元素,则最好使用【 】
A.只有表头指针没有表尾指针的单循环链表
B.只有表尾指针没有表头指针的单循环链表
C.非循环双链表
D.顺序表
7.对于一个线性表,既要求能够较快速地进行插入和删除,又要求存储结构能反映数据元
素之间的逻辑关系,则应该采用【 】
A.顺序存储方式 B.链式存储方式 C.随机存储方式
D.以上均可以
8.用单链表表示的链队列的链表指针在链表的【 】
A.链头 B.链尾 C.链中 D.都不是
9.对于循环队列【 】13
A.无法判断队列是否为空 B.无法判断队列是否为满
C.队列不可能为满 D.以上说法都不对
10.一个栈的进栈序列为 A、B、C、D、E,则栈的不可能的输出序列是【 】
A.EDCBA B.DECBA C.DCEAB D.ABCDE
11.循环队列的最大容量为 M,则队空的条件是【 】
A.rear==front B.(rear+1)%M==front
C.rear+1==front D.(rear-1)%M==front
12.【 】是 C 语言中串“abcd321ABCD”的子串。
A.abcd B.321AB
C.”abcABC” D.”21AB”
13.稀疏矩阵一般的压缩方法有两种,即【 】
A.二维数组和三维数组 B.三元组和散列
C.三元组表和十字链表 D.散列和十字链表
14.利用二叉链表作为树的存储结构,则根结点的右指针是【 】 。
A.指向最左孩子 B.指向最右孩子
C.空 D.非空
15.一棵具有 n 个结点的完全二叉树的高 h为【 】 。
A. B. C. D.
16.某二叉树的先序遍历序列和后序遍历序列正好相同,则该二叉树一定是【 】 。
A.空或只有一个结点 B.完全二叉树
C.二叉排序树 D.高度等于其结点树
17.已知一棵完全二叉树有 625 个结点,叶结点的个数为【 】 。14
A.311 B.312 C.313 D.其他
18.一个有 n个顶点的有向图最多有【 】条边。
A. B.n(n-1) C.n(n-1)/2 D.2n
19.下列哪种图的邻接矩阵一定是对称的?【 】
A.有向图 B.无向图 C.AOV 图 D.AOE 图
20.在有向图的邻接表存储结构中,与顶点 v对应的单链表中结点的个数是【 】
A.顶点 v的度 B.顶点 v的出度 C.顶点 v 的入度 D.依附于顶点 v的边数
21.查找 n 个元素的有序表时,最有效的查找方法是【 】
A.顺序查找 B.分块查找 C.折半查找 D.二叉排序树
22.对查找表进行折半查找时,要求查找表必须【 】
A.以顺序方式存储
B.以顺序方式存储,且结点按关键字有序排列
C.以链式方式存储
D.以链式方式存储,且结点按关键字有序排列
23.当采用分块查找时,数据的组织方式为【 】
A.数据分成若干块,每块内数据关键字为有序
B.数据分成若干块,每块内数据关键字不必有序,但块间数据关键字有序,每块内最大
或最小关键字的数据组成索引块
C.数据分成若干块,每块内数据关键字有序,每块内最大或最小关键字的数据组成索引

D.数据分成若干块,每块中数据个数相同
24.在待排序的元素序列基本有序的前提下,效率最高的排序方法是【 】15
A.插入排序 B.选择排序 C.快速排序 D.归并排序
25.排序方法中,从未排序序列中挑选元素,并将其依次放入已排序序列(初始为空)的后
面的方法,称为【 】
A.希尔排序 B.归并排序 C.直接插入排序 D.直接选择排序
二、填空题(每空1分,共 30 分)
1.一个数据结构在计算机中的 (1) 称为存储结构。
2.算法的执行时间是 (2) 的函数。
3.求线性表的顺序存储和链式存储的长度的算法时间复杂度分别是 (3) 和
(4) 。
4.在单链表中要删除某一个指定结点,必须找到该结点的 (5) 结点。
5.在 (6) 链表中,可以用表尾指针代替表头指针。
6.在一个单链表中的 p指针所指结点之前插入一个 s所指结点时, 可以执行如下操作:
s->next= (7) ;
p->next=s;
t=p->data;
p->data= (8) ;
s->data= (9) ;
7. 循 环 队 列 的 引 入 , 目 的 是 为 了 克 服
(10) 。
8. 栈 和 队 列 的 区 别 是
(11) 。
9. 如 果 栈 的 最 大 长 度 难 以 估 计 , 最 好 使 用16
(12) 。
10.具有 n 个结点的二叉树中,如果有 m 个叶结点,则一定有 (13) 个
度 为 2 的结点,有 (14) 个度为 1 的结点。
11.在一棵二叉树中,度为 0 的结点个数为 n0,度为 2 的结点个数为 n2,则有 n0=
(15) 。
12.具有 n 个结点的二叉树采用二叉链表存储结构,共有 (16) 个空指针域。
13. 在 二 叉 树 的 链 式 存 储 结 构 中 , 指 针 p 所 指 结 点 为 叶 结 点 的 条 件 是
(17) 。
14.树中任一结点允许有 (18) 个孩子结点,除根结点之外,其余结点有
(19) 个双亲结点。
15.一个图的 (20) 表示法是唯一的。而 (21) 表示法是不唯
一的。
16.已知一个有向图的邻接矩阵表示,删除所有从第 i 个结点出发的弧的方法是
(22) 。
17.具有 n 个顶点的连通图,它的生成树一定有 (23) 边。
18.哈希 表是通过 将关键 字按选定 的 (24) 和
(25) ,把记录按关键字转换为地址进行存储的存储表。
19. 用 二 分 查 找 一 个 查 找 表 , 该 查 找 表 必 须 具 有 的 特 点 是
(26) 。
20.在分块查找方法中,首先查找 (27) ,然后再查找相应的
(28) 。
21.在堆和快速排序中,若原始记录接近正序或反序,则选用 (29) ,若原始17
记录无序,则选用 (30) 。
三、简答题(共7小题 40 分)
1.当为解决某一问题已经选定其数据的逻辑结构后,选择数据的存储结构时,应从哪
些方面考虑?(4 分)
2.队列可以用单循环链表来实现,故可以只设一个头指针或只设一个尾指针,请分析
用哪种方案最合适。 (4分)
3.设数组 A[10][20][30],其基地址为 1000,每个元素占 2 个存储单元,以行序为
主序顺序存储,回答下列问题: (7分)
(1)该数组有多少个元素?
(2)该数组占用多少存储单元?
(3)数组元素 a[5][5][5]的存储地址是多少?
4.已知一棵二叉树的中序序列为 CBEDAHGIJF,后序序列为 CEDBHJIGFA,画出该二
叉树,并求其先序序列。 (6分)
5.已知一个无向图如下图所示,回答下列问题: (8分)
(1)构造该图的邻接表表示:
(2)要求分别用 Prime 和 kruskal 算法生成最小生成树(Prime 算法: 假设从顶
点 v1 开始,要求画出其构造过程)18
v1 v2
v6
v5 v4
v3
9
20
10
10
11
14
18
9
5
9
6.画出对长度为 10 的有序表进行折半查找的判定树, 并求其等概率时查找成功的平均
查找长度。 (6分)
7.已知数据集合{17, 18, 60, 40, 7, 32, 73, 65, 85},请给出采用
冒泡排序法对该数据集合进行升序排序时的每一趟的结果。 (5分)
四、完善算法和算法设计题(共4 小题30 分)
1、下面是求两个集合 A 和 B的并集(A∪B)的算法,集合 A和 B 分别用单链表 La和
La 的带头结点的单链表表示(链表中的数据按升序排列) ,其并集用单链表 Lc 表示(带头
结点,其数据也按升序排列) 。请填空完善算法。 (每空 2分)19
typedef struct ListNode{
int data;
struct ListNode, *next;
}ListNode .*Linklist;
void Mergelist_L(Linklist La,Linklist Lb,Linklist *Lc)
{pa=La->next; pb=Lb->next;
*Lc=pc=(ListNode *)malloc(sizeof(ListNode));
while(pa&&pb)
{ p= ;
if(pa->data<=pb->next)
{p->data= ;
pc->next= ;
pc=p;
pa=pa->next;
}
else { p->data=pb->data;
pc->next=p;
pc=p;
pb=pb->next;
}
}
pa=pa?pa:pb;20
while ( )
{ p=(ListNode *)malloc(sizeof(ListNode));
p->data=pa->data;
pc->next=p;
pc=p;
pa=pa->next;
}
pc->next= ;
}
2.对给定的带头结点的单链表 L,结点值的类型为整型,编写一个删除 L中值为 x
的算法(L中可能有多个值为 x的结点,且值的分布具有随机性) 。 (6 分)
3.假设将循环队列定义为:
#define MAXQSIZE 100
typedef struct {
QElemType *base;
int rear; //指向循环队列中队尾元素的
位置
int length; //表示队列中所含数据元素的
个数
}SqQueue;
SqQueue Q:
试给出此循环队列的队满的条件, 并写出相应的入队列和出队列的算法21
(在出队列的算法中要返回队头元素) 。 (8分)
4.编写一个递归算法,计算以二叉链表表示的二叉树 T的高度 h。 (6 分)
试题代码:959
西南交通大学 2011 年硕士研究生入学考试
试题名称:数据结构
考生注意:
5. 本试题共4题,共6页,满分150分,请认真检查;
6. 答题时,直接将答题内容写在考场提供的答题纸尚,答在试卷上的内容无效;
7. 请在答题纸上按要求填写试题代码和试题名称;
8. 试卷不得拆开,否则遗失后果自负。
题号 一 二 三 四 五 六 七 八 九 十 总分
得分
签字
一、单项选择题(本大题共 25 题,每题2 分,共50 分)22
1.数据结构在计算机内存中的表示是指【 】 。
A.数据的存储结构 B.数据结构
C.数据结构的逻辑结构 C.数据元素之间的关系
2.【 】是数据的基本单位。
A.数据项 B.数据元素
C.信息项 D.表元素
3.算法的计算量的大小称为算法的【 】 。
A.效率 B.时间复杂度 C.显示性 D.难度
4.链表不具备的特点是【 】
A.可随机访问任一结点 B.插入删除不需要移动元素
C.不必事先估算存储空间 D.所需空间与其长度成正比
5.设线性表有 n 个元素,以下操作中, 【 】在顺序表上实现比在链表上实现效
率更高。
A.输出第 i(1≤i≤n)个元素的值
B.顺序输出这 n 个元素
C.交换第 1 个与第 2 个元素的值
D.输出与给定值 x 相等的元素在线性表中的序号
6.设一个链表最常用的操作是在末尾插入结点和删除尾结点,则选用【 】最
节省时间。
A.带头结点的双循环链表 B.单循环链表
C.带尾指针的单循环链表 D.单链表
7.若长度为 n 的线性表采用顺序存储结构,在第 i 个位置插入一个新元素的算23
法的时间复杂度为【 】
A.O(0) B. O(1) C. O(n) D. O()
8.栈和队列的共同点是【 】
A.都是先进先出 B.都是后进后出
C.只允许在端点处进行插入和删除 D.无共同点
9.设入栈序列为 1,2, 3, 4,5,则可能得到的出栈序列为【 】
A.1,2,5,3,4 B.3,1,2,5,4
C.3,2,5,4,1 D.1,4,2,3,5
10.队列存放在 A[0…M-1]中,则入队时的操作为【 】
A.rear=rear+1 B.rear=(rear+1)%M
C.rear=(rear+1)%(M+1) D.rear=(rear+1)%(M-1)
11.两个串相等必有串长度相等且【 】
A.串的各位置字符任意 B.串中各位置字符均对应相等
C.两个串含有相同的字符 D.两个串所含字符任意
12.设有数组A[8][10], 每个元素占3个存储单元, 首地址为SA, 则元素[7][5]
的起始地址是【 】
A.SA+141 B.SA+144 C.SA+222 D.SA+225
13.设有一个 n*n的对称矩阵,采用压缩存储,则存入内存的元素个数为【 】
A.n*n B.n*n/2 C.n*(n+1)/2 D./2
14.有关二叉树下列说法正确的是【 】
A.二叉树的度为 2 B.一棵二叉树的度可以小于2
C.一棵二叉树至少有一个结点的度为 2 D.二叉树中任何一个结点的度为224
15.一棵 124 个叶结点的完全数,最多具有【 】个结点。
A.247 B.248 C.249 D.251
16.树最适合用来表示【 】
A.有序数据元素 B.无序数据元素
C.元素间具有分支层次关系的数据 D.元素间无联系的数据
17.在一棵非空二叉树的中序遍历序列中,根结点的右边【 】
A.只有右子树上的所有结点 B.只有右子树上的部分结点
C.只有左子树上的部分结点 D.只有左子树上的所有结点
18.对某个无向图的邻接矩阵来说【 】
A.第 i 行上的非 0 元素个数等于第 i列上非 0 元素个数
B.矩阵中非 0 元素个数等于图中的边数
C.第 i 行、第 i 列上非 0 元素个数等于顶点vi的度数
D.矩阵中非全 0 行的行数等于图中的顶点数
19.具有 4 个顶点的无向完全图有【 】条边。
A.6 B.12 C.16 D.20
20.顺序查找法适合于存储结构为【 】的查找表。
A.散列结构 B.顺序存储或链式存储
C.压缩存储 D.索引存储
21.采用折半查找法查找长度为n 的查找表时, 每个元素查找的平均查找长度为
【 】
A.O() B.O() C.O(n) D. ()
22.在关键字随机分布的情况下,用二叉排序树的方法进行查找,其查找长度与25
【 】量级相当。
A.顺序查找 B.折半查找 C.分块查找 D.前三个都不正确
23.散列表的平均查找长度【 】
A.与冲突处理方法有关而与表的长度无关
B.与冲突处理方法无关而与表的长度有关
C.与冲突处理方法有关且与表的长度有关
D.与冲突处理方法无关且与表的长度无关
24.在待排序的元素序列基本有序的前提下,效率最差的排序方法是【 】
A.插入排序 B.冒泡排序 C.快速排序 D.归并排序
25.就排序算法所用的辅助空间而言,堆排序、快速排序和归并排序的关系是
【 】
A.堆排序<快速排序<归并排序
B.堆排序<归并排序<快速排序
C.堆排序<归并排序<快速排序
D.堆排序<快速排序<归并排序
二、填空题(每空1分,共 30 分)
1.对线性结构而言,顺序存储方法把逻辑上 (1) 存储在物理位置上
(2) 里;链式存储方法中结点间的逻辑关系是由 (3) 表示的。
2.向一个长度为 n 的顺序表中的第 i个元素之前插入一个元素时,需要向
后移动 (4) 个元素。
3.在 (5) 链表中,删除最后一个结点的算法时间复杂度为O(1) 。26
4.根据 n 个数据元素建立对应的顺序表和单链表存储结构,其算法的时间
复杂度最好的情况是 (6) ,最坏的情况是 (7) 。
5.如果栈的最大长度难以估计,最好使用 (8) 。
6.从循环队列中插入一个元素的操作是 (9) 。
7.一个串中 (10) 称为该串的子串。
8.一棵二叉树第 i 层最多有 (11) 个结点,一棵有 n 个结点的满二
叉树共有 (12) 个结点,共有 (13) 个叶结点。
9.在一棵完全二叉树中,编号 i 和 j 的两个结点处于同一层的条件是
(14) 。
10.具有 n 个结点的二叉树采用二叉链表存储结构,共有 (15) 个空
指针域。
11.具有 n 个结点的二叉树中, 如果有 m 个叶结点, 则一定有 (16) 个
度为 2 的结点,有 (17) 个度为 1 的结点。
12. 二 叉 树 的 先 序 序 列 和 中 序 序 列 相 等 的 条 件 是
(18) 。
13.对于 n 的顶点的无向图,采用邻接矩阵表示,求图中边的方法是
(19) ,判断任意两个顶点是否有边相连的方法是 (20) ,求任意顶
点的度的方法是 (21) 。
14.若无向图有 m 条边,则表示该无向图的邻接矩阵表示,求图中边的方法
是 (22) 个结点。
15.折半查找的存储结构仅限于 (23) ,且是 (24) 。
16.分块查找法将待查找的表均匀地分成若干块且块中诸记录的顺序可以27
是任意的,但块与块之间 (25) 。
17.用二叉排序树查找,在最坏的情况下,平均查找长度为 (26) ,
最好的情况下,平均查找长度为 (27) 。
18.在插入和选择排序中,若初始数据基本正序,则选用 (28) , 若
初始数据基本反序,则选用 (29) 。
19.对 n 个元素的表进行直接选择排序,所需要的关键字的比较次数为
(30) 。
三、简答题(共7小题 40 分)
1.数据结构和数据类型有什么区别?(4分)
2.若频繁地对一个线性表进行插入和删除操作,则该线性表宜采用何种存
储结构,为什么?(4 分)
3.何谓队列上溢?何为假溢出现象?有哪些解决假溢出问题的方法,并分
别阐述其工作原理。 (6 分)
4.设数组 A[50][80],其基地址为 2000,每个元素占4 个存储单元,以
行序为主序顺序存储,回答下列问题: (6 分)
(1)该数组有多少元素?
(2)该数组占用多少存储单元?
(3)数组元素 a[30][30]的存储地址是多少?
5.有一份电文共有 5 个字符:a,b,c,d,e,它们出现的频率依次为4, 7,
5, 2, 9,构造对应的哈夫曼树,求哈夫曼树的带权路径长度和每个字符的哈
夫曼编码。 (8 分)28
6.已知一棵二叉树的先序序列为 EBADCFHGIKJ,其中序序列为
ABCDEFGHIJK,求后序序列。 (6 分)
7.设有数据集合 d={1, 12,5, 8,3, 10,7, 13,9},回答下列问题:
(6 分)
①依次取 d中各数据,构造一棵二叉排序树 bt;
②如何依据此二叉排序树得到d 的一个有序序列。
四、完善算法和算法设计题(共4小题 30 分)
下面1、2题的每个空2 分。
1. 下面是二叉树中序遍历的非递归算法,读程序并在每个空格处填上一个
合适的语句或表达式。
void inorder(BiTree bt)
{ initstack(s);
p= ;
while(p!=NULL||!empty(s))
{
while(p)
{ ;
p=p->lchild;
}
if(!empty(s))
{ ;29
visit(p->data);
;
}
}
}
2、下面是快速排序的任意子系列 L.r[low..high]的一趟划分算法,读
程序并在每个空格处填上一个合适的语句或表达式。
int partition(Sqlist &L,int low ,int high)
{ L.r[0]=L.r[low];
;
while(low<high)
{ while (low<high && L.r[high].key>=pivotkey) -
- high;
;
while( ) ++low;
L.r[high]=L.r[low];
;
return low ;
}
3、写一个算法,将单链表中值重读的结点删除,使所得的结果表中各结点
值均不相同(假设单链表中包含一个头结点) 。 (6 分)
4、设有两个整数集合 A 和 B,分别用递增有序链表表示,设计一算法实现30
两个集合的交运算(C=A∩B) ,运算结果页用递增有序链表表示。运算后,A、
B 两个链表保持不变(8 分) 。31
试题代码:959
西南交通大学 2010 年硕士研究生入学考试
试题名称:数据结构
考生注意:
9. 本试题共4题,共6页,满分150分,请认真检查;
10.答题时,直接将答题内容写在考场提供的答题纸尚,答在试卷上的内容无效;
11.请在答题纸上按要求填写试题代码和试题名称;
12.试卷不得拆开,否则遗失后果自负。
题号 一 二 三 四 五 六 七 八 九 十 总分
得分
签字
一、单项选择题(本大题共 25 题,每题2 分,共50 分)
1.在数据结构中,从逻辑上可以把数据结构分成【 】 。
A.动态结构和静态结构 B.紧凑结构和非紧凑结构
C.线性结构和非线性结构 D.内部结构和外部结构
2.在存储数据时,不仅要考虑存储各数据元素的值,而且还要存储【 】 。
A.数据处理的方法 B.数据元素的类型
C.数据元素之间的关系 D.数据的存储方法32
3.算法分析的目的是【 】 。
A.找出数据结构的合理性 B.研究输入和输出的关系
C.分析算法的效率以求改进 D.分析算法的易懂性
4.如果最常用的操作是取第 i 个结点及其前驱,则采用【 】存储方法最节省
时间。
A.单链表 B.双链表 C.线性链表 D.顺序表
5.线性表的顺序存储结构是一种【 】 。
A.随机存取的存储结构 B.顺序存取的存储结构
C.索引存取的存储结构 D.Hash 存取的存储结构
6.单链表中增加一个头结点的目的是为了【 】 。
A.使单链表至少有一个结点 B.标识表首结点的位置
C.方便运算的实现 D.说明单链表是线性表的链式存储
7.设一个链表最常用的操作是在末尾插入结点和删除尾结点,则选用【 】最
节省时间。
A.带头结点的双循环链表 B.单循环链表
C.带尾指针 的单循环链表 D.单链表
8.链表不具备的特点是【 】 。
A.可随机访问任一结点 B.插入删除不需要移动元素
C.不必事先估算存储空间 D.所需空间与其长度成正比
9.栈和队列的共同点【 】 。
A.都是先进先出 B.都是后进后出
C.只允许在端点处进行插入和删除 D.无共同点33
10.与顺序栈相比较,链栈有一个比较明显的优势是【 】 。
A.通常不会出现栈满的情况 B.插入操作更容易实现
C.通常不会出现栈空的情况 D.删除操作更容易实现
11.设计一个判别表达式中左、右括号是否匹配的算法,采用【 】数据结构最
佳。
A.线性表的顺序存储结构 B.队列
C.线性表的链式存储结构 D.栈
12.输入序列是 ABC,若输出序列变为 CBA,经过的栈操作为【 】 。
A.push,pop, push,po, push,pop B. push, push,
push,pop,pop,pop
C. push, push,pop,pop, push,pop D. push,pop, push,
push,pop,pop
13.一维数组与线性表的区别是【 】 。
A.前者长度固定,后者长度可变 B.后者长度固定,前者长度可变
C.两者长度均固定 D.两者长度均可变
14.设有一个 10*10 的对称矩阵 A,以行主次序进行压缩存储,每个元素占一
个存储单元,的地址是1,则的起始地址是【 】 。
A.13 B.33 C.18 D.40
15. 设 A 是 一 个 n*n 的 对 称 矩 阵 , 压 缩 存 储 到 一 个 一 维 数 组
B[0..n(n+1)/2-1]中,则下三角部分元素在B 中的位置是【 】 。
A.i(i-1)/2+j-1 B.i(i-1)/2+j C.i(i+1)/2+j-1
D.i(i+1)/2+j34
16.串是一种特殊的线性表,其特殊性体现在【 】 。
A.可以顺序存储 B.数据元素是一个字符
C.可以链式存储 D.数据元素可以使多个字符
17.若一棵二叉树具有 10 个度为2 的结点,5个度为 1 的结点,则度为 0 的结
点个数为【 】 。
A.9 B.11 C.15 D.不确定
18.一棵具有 n 个结点的完全二叉树的高h为【 】 。
A. B. C. D.
19.由 8 个权值构造一棵哈夫曼树,该哈夫曼树有【 】个结点。
A.15 B.16 C.17 D.14
20.一个有 n 个顶点的无向图最多有【 】条边。
A.n B.n(n-1) C.n(n-1)/2 D.2n
21.一个有 n 个顶点的无向图,若采用邻接矩阵表示,则该矩阵的大小是【 】 。
A.n B. C.(n-1) D.
22.采用顺序查找法查找长度为n 的查找表时, 每个元素查找的平均查找长度为
【 】 。
A.n B.n/2 C.(n+1)/2 D.(n-1)/2
23.对查找表进行折半查找时,要求查找表必须【 】 。
A.以顺序方式存储 B.以顺序方式存储,且结点按关键字有序排列
C.以链式方式存储 D.以链式方式存储,且结点按关键字有序排列
24.直接插入排序在最好的情况下的时间复杂度为【 】 。
A.O(n) B.O( ) C.O() D.O()35
25.在下列排序方法中,要求内存量最大的方法【 】 。
A.直接插入排序 B.选择排序 C.快速排序 D.归并排序
二、填空题(每空1分,共 30 分)
1.数据的物理结构包括 (1) 的表示和 (2) 的
表示。
2.在一个长度为 n 的顺序表中删除第i 个元素时,需要向前移动 (3)
个元素。
3.在单链表中设置头结点的作用是 (4) 。
4.在双链表中每个结点有两个指针,一个指向 (5) ,一个指向
(6) 。
5.在 (7) 链表中,删除最后一个结点的算法时间复杂度为 O
(1) 。
6.由 n 个数据元素生成一个顺序表,若每次都调用插入算法把一个元素插
入到表头,则整个算法的时间复杂度为 (8) ,若每次都调用插入算法把
一个元素插入到表尾,则整个算法的时间复杂度为 (9) 。
7.区分循环队列的空与满有 3 种方法,它们是 (10) 、
(11) 、 (12) 。
8.深度为k的完全二叉树至少有 (13) 个结点, 至多有 (14)
个结点。
9.根据二叉树的定义,具有3 个结点的二叉树共有 (15) 种不同
形态,它们分别是 (16) 。36
10.一个图的 (17) 表示法是唯一的,而 (18) 表示法
是不唯一的。
11.顺序查找含 n 个元素的顺序表,若查找成功,则比较关键字的次数最多
为 (19) 次,若查找不成功,则比较关键字的次数为 (20)
次。
12.在含有 n 个元素的有序顺序表中进行二分查找,最大的比较次数是
(21) 。
13.每次从无序子表中取出一个元素,把它插入到有序子表中恰当位置,此
种排序方法叫做 (22) 排序;若每次从无序子表中挑选出最小或最大
元素,把它交换到有序表的 一端,此种排序方法叫做 (23) 排序。
14.每次通过基准元素间接比较两个元素,不满足约定要求时就交换位置,
该排序方法叫做 (24) 排序;每次使两个相邻有序表合并成一个有序表
的排序方法叫做 (25) 排序。
15.在堆排序、快速排序和归并排序中,若只从存储空间考虑,则应首先选
取 (26) 方法,其次选择 (27) 方法,最后选择 (28)
方法;若只从平均情况下排序最快考虑,则应选取 (29) 方法;若只
从最坏情况下排序最快并且要节省内存考虑,则应选取 (30) 方法。
三、简答题(共6小题 40 分)
1.对于一个栈,其输入序列是 A,B,C,试给出全部可能的输出序列。 (5
分)
2.设有数组定义: (8分)
int a[7][8][9];37
假定每个数组元素占 2 个字节存储空间,数组在内存的开始地址为 1000,求:
①整个数组所占存储空间的大小。
②按行优先的原则,求数组元素 a[j][k]在内存中的地址的表达式。
③计算数组元素 a[3][4][5]的地址。
3.按给定的输入序列:45,24, 53, 12, 25, 90构成一棵二叉排序树。 (5 分)
4.设有如下图所示的二叉树,给出其前序、中序和后序遍历结果。 (6分)
e
a
d
f
g
h i
j
c
b
5.假设通信电文使用的字符集为{a, b, c, d, e, f}, 各字符在电文中出现的
频度分别为:34, 5, 12, 23, 8, 18,视为这 6个字符设计哈夫曼编码。请先画出
你所构造的哈夫曼树(要求树中左孩子结点的权值小于右孩子结点的权值) ,然后分别写出
每个字符对应的编码。 (8分)
6.设有带权无向图(见下图) : (8 分)38
①请写出该图的邻接矩阵表示。
② 请 画 出 该 图 的 一 棵 最 小 生 成 树 。
1
4
3
2
6 5
6 5
1
2
6
3
5
4
5
6
四、完善算法和算法设计题(共4小题 30 分)
1、下面是循环队列删除元素的算法,请填空完善算法。 (每空 2 分)
#define M 100 //循环队列中的存储空间
int DeQueue(SqQueue &Q,QElemType &e)
if( )
return(0);
else
{ e=Q.base[Q.front];
;
return(1);
}
}39
2.请完成以下折半查找的算法: (每空 2分)
int binsrch (SSTable r, keytype key)
{ int low=1,high=r.length,mid=0,suc=FLASE;
while( &&!suc)
{ mid= ;
if(key>r.elem[mid].key) low =mid+1;
else if(key==r.elem[mid].key) suc=TRUE;
else high= ;
}
if(suc) ;
else ;
}
3.设计一算法,实现在数据元素有序的顺序存储结构的线性表中插入一个
值为 x 的操作。如果无存储空间则插入失败,函数的返回值为插入操作成功与否
的标志。 (8 分)
4.设有两个整数集合 A 和 B,分别用递增有序链表表示,设计一算法实现
两个集合的联合运算,运算结果也用递增有序链表表示。运算后,A、B 两个链
表保持不变(8 分)4041
西南交通大学 2008 年硕士研究生入学考试试卷
试题代码:921
试题名称:程序设计与数据结构
考生注意:
1.本试题共 6大题,共 8页,考生请认真检查;
2.请务必将答案写在答卷纸上,写在试卷上的答案无效。
题号 一 二 三 四 五 六 七 八 九 十 总分
得分
签字
一、填空题(本大题共20 个空,每空1 分,共20 分)
1 、 设 有 定 义 : int x=1, y=2; 则 表 达 式 : 2.0+x/y 的 值
为: 。
2、在 C 语言中字符串的存放,其最后一个字符称为“空字符” ,也叫字符串
的结束符,对应的转义字符是 ,其值为 。
3、设有宏定义:#define AA 2-3 ,则 3*AA 的宏替换结果
是 。
4、设有定义:int a=3, b=2, c=1 ,则表达式:a>b>c 的值
是 。
5、定义一个名为a 的二维数组,并对数组元素赋初值,其值为下列矩阵,42
则对应的定义语句为: 。
1.0 3.8 2.6
3.3 5.0 9.8
6、设有定义:char s[]=”SWJTU”; 则数组占用的内存为 字节,
s[5]的值为 。
7、若有定义: inta[5],*p=a ;则*(p+3)表示 ;*p+3 表
示 。
8、在具有 n 个元素单元的循环队列中,若采用少用一个元素来解决队空队
满时都有头尾指针相等的问题,队满时共有 个元素。
9、带一个头结点的单链表head为空的条件是 。
10、 二维数组 A[10][20]采用列序为主序存储, 每个元素占一个存储单元,
并 且 A[0][0] 的 存 储 地 址 是 200 , 则 A[6][12] 的 地 址
是 。
11、深度为 k 的完全二叉树至少有 个结点,至多有
个结点。
12、在一棵二叉树中,度数为零的结点个数为 n0,度数为 2 的结点个数
为 n2,则有 n0= 。
13、在无向图 G 的邻接矩阵 A 中,若 A[j]等于 1,则 A[j]
于 。
14 、 对 n 个 元 素 的 序 列 进 行 冒 泡 排 序 时 , 最 少 的 比 较 次 数
是 。
15、以折半查找方法查找一个线性表时,此线性表必须是 存储43
的 表。
二、单项选择题(本大题共30 小题,每小题1 分,共30 分。在每
小题列出的四个选项中只有一个选项是符合题目要求的答案)
1、若有以下定义语句: char ; int b ;float c ;double d:则表达式
a+b*c-d 的值的类型是【 】 。
A.char B.int C.float D.double
2、以下程序段中与语句k=a>b?(b>c?1:0):0;功能等价的是【 】 。
A.if((a>b)&&(b>c)) k=1; else k=0;
B.if((a>b)||(b>c)) k=1; else k=0;
C.if(a<=b) k=0 ;else if(b<=c) k=0 ;else k=1; D.if(a>b)
k=1 ;else if(b>c) k=1 ;else k=0;
3、若程序中定义了以下函数,并将其放在调用语句之后,则在调用前需对该函
数进行说明,以下选项中错误的说明是【 】 。
double myadd(double a,double b)
{ return (a+b) ;}
A.double myadd (double a,b); B.double myadd
(double ,double);
C.double myadd (double b,double a); D.double myadd
(double x, double y)
4、假定 a 和 b 均为 int 型变量,则执行以下程序段后, b 的值是【 】 。
a=1; b=10;44
do{b-=a ;a++ ;} while (b--<0);
A.9 B.-2 C.-1 D.8
5、 语句:printf( “%d” ,strlen( “abc\n012\1\\” ));的输出结果是 【 】 。
A.9 B.10 C.11 D.12
6、设有定义:int n=0,*P=&n , **q=&p ;则以下选项中,正确的赋值语
句是【 】 。
A.p=1; B.*q=2; C.q=p D.*p=5
7、设有变量定义: int a[10]={1,2,3,4,5,6,7,8,9,10}, *P=&a[3],
b;则执行赋值语句 b=p[5];后 b 的值是【 】
A.5 B.6 C.8 D.9
8、在函数定义中未指定返回值类型,则其隐含的返回值类型是【 】 。
A.void B.int C.float D.编译出错
9、若有函数原型: viod f( int a[ ]); 和数组定义 int a[10];则以
下函数调用错误的是【 】 。
A.f(a) B.f(a+2) C.f(a[0])
D.f(&a[0])
10、设 k 为整型变量,与表达式 (!k)值完全相同的表达式是【 】 。
A.k==0 B.k==1 C.k!=0 D.k!=1
11、以下程序运行后,输出结果是【 】 。
int b ;
void MyFunc( int a,int *c)
{b=(a++) + (*c)++; }45
void main(void)
{ int a, c ;
a=1 ;b=2 ;c=3 ;
MyFunc (c, &a);
printf(“%d%d%d”,a ,b ,c );
}
A.144 B.243 C.123 D.143
12、以下函数的功能是【 】 。
int fun(char *s1 ,char *s2)
{ int i=0 ;
while(s1=s2&&s2!=’\0’)i++;
return(s1==’\0’&&s2==’\0’);
}
A.将 s2 所指字符串赋给 s1
B.比较 s1 和 s2所指字符串的大小,若 s1 比 s2的大,函数值为 1,否则函
数值为0
C.比较 s1 和 s2所指字符串是否相等,若相等,函数值为 1,否则函数值为
0
D.比较 s1 和 s2所指字符串的长度,若 s1 比 s2的长,函数值为 1,否则函
数值为0
13、以下程序段是从键盘上依次输入数据给数组元素,程序的下划线处应填上
【 】 。46
void main (void)
{ int a[20] ,i=0;
while(i<20) scanf(“%d”, );
}
A.&a B.&a[i+1] C.&a[i++]
D.&a++
14、 若文件型指针fp 已指向某文件的末尾, 则函数 feof(fp)的返回值是 【 】 。
A.0 B.-1 C.NULL D.非零值
15、在数据结构中,从逻辑上可以把数据结构分成【 】 。
A.动态结构和静态结构 B.紧凑结构和非紧凑结构
C.线性结构和非线性结构 D.内部结构和外部结构
16、在以下叙述中,正确的是【 】 。
A.线性表的顺序存储结构优于链式存储结构
B.二维数组是其数据元素为线性表的线性表
C.栈的操作方式是先进先出
D.队列的操作方式是先进后出
17、一个栈的入栈序列式a ,b ,c ,d ,e ,则不可能的出栈序列是【 】 。
A.edcba B.decba C.dceab D.abcde
18、若已知一个栈的入栈序列是 1, 2, 3, ……, n ,其输出序列为 p1 ,p2 ,
p3, …… ,pn,若 p1=n,则 p1 为【 】 。
A.i B.n=I C.n-i+1 D.不确定
19、循环队列用数组 A[m]存放其元素值,已知其头尾指针分别是 front 和47
rear,则当前队列中的元素个数是【 】 。
A.(rear-front+m)%m B.rear-front+1 C.rear-front -1
D.rear-front
20、设串 s1=” ”ABCDEFG, s2=”PQRST”, 函数 con(x,y)返回 x 和 y 串的连
接串, subs(s ,I ,j)返回串s 的从序号 i 的字符开始的j 个字符组成的子
串 , len(s)返回串 s 的长度,则 con(subs(s1 ,2 , len(s2)),
subs(s1 ,len (s2),2 )))的结果串是【 】 。
A.BCDEF B.BCDEFG C.BCPQRST
D.BCDEFEF
21、设矩阵 A 是一个对称矩阵,为了节省存储空间,将其下三角部分按行序存
放在一维数组B[n(n-1)/2]中,对下三角部分中任一元素ai,j(i≥j) ,在一
维数组B 中下标 k的值是【 】 。
A.i(i-1)/2+j-1 B.i(i-1)/2+j C.i(i+1)/2+j-1
D.i(i+1)/2+j
22、设高度为 h的二叉树上只有度为 0 和度为 2 的结点,则此类二叉树中所包
含的结点数至少为【 】 。
A.2h B.2h-1 C.2h+1 D.h+1
23、在一个具有 n 个顶点的无向图中,要连通全部顶点至少需要【 】条边。
A.n B.n+1 C.n-1 D.n/2
24、设哈希表长 m=14,哈希函数 H(key)=key%11.表中已有 4 个结点:
addr(15)=4,addr(38)=5,addr(61)=6,addr(84)=7,其余地址为空,
如用线性探测在散列处理冲突,关键字为49 的节点的地址是【 】 。48
A.3 B.4 C.5 D.6
25、 哈希表长度为m, 哈希函数H(K)=K%P, 一般来说 P应取小于 m 的最大 【 】 。
A.奇数 B.偶数 C.素数 D.合数
26、若用邻接矩阵表示一个有向图,则其中每一列包含的1 的个数为【 】 。
A.图中顶点的入度 B.图中顶点的出度
C.图中弧的条数 D.图中连通分数的数目
27、在对 n 个关键字进行直接选择排序的过程中,每一趟都要从无序区选出最
小关键字元素,则在进行第 i 趟排序之前,无序区中关键字元素的个数为【 】 。
A.i B.i+1 C.n-i D.n-i+1
28、下列排序算法中,其时间复杂度和记录的初始排列无关的是【 】 。
A.插入排序 B.堆排序 C.快速排序 D.冒泡排序
29、对 20 个有序记录进行折半查找,查找成功的平均查找长度为【 】 。
A.5 B.37/10 C.39/10 D.41/10
30、当初始数据有序时,不应采用【 】 。
A.堆排序 B.快速排序 C.基数排序 D.希尔排序
三、 阅读程序, 按提示给出结果 (共5小题, 每小题 4分, 共20 分) 。
1、 下面的函数 Func 的功能是 。
float Func (float a[ ], int N)
{ int i, float s;
for(i=0,s=0; i<N ;s+=a,i++);
return s/N;
}49
2、 以下程序运行后的输出结果是 。
void main(void)
{ int x=1,y=0 ,a=0,b=0 ;
switch(x)
{ case 1:switch(y)
{ case 0:a++;break;
case 1:b++;break;
}
case 2:a++;b++;break;
}
printf(“%d %d\n”,a ,b);
}
3、以下程序运行后的输出结果是 。
void main (void)
{ int i=0,s=0;
for(::)
{ i++;
if(i==3||i==5) continue;
if(i==6) break;
s+=i;
}
printf(“%d\n”,s);50
}
4、 下面程序运行时, 若输入234, 则输出结果是 。
unsigned Func (unsigned Num)
{ unsigned k=1;
do{k*=Num%10;Num/=10;}while (Num);
return k;
}
void main(void)
{ unsigned n;
scanf(“%u”,&n);
printf(“%d”,Func(n));
}
5 、 下 面 程 序 运 行 时 , 若 输 入 : 口 口 -893abc193 , 则 输 出 结 果
是 。
int IsDigit (char c)
{ return (c<’0’||c>’9’)?0:1:}
long Func(char s[ ])
{ long n; int Sign ;
for(:*s==’口’ :s++); //口 表示空格
Sign=(*s==’-’)?-1:1;
if(*s==’+’||*s==’-’)s++;
for(n=0L:IsDigit(*s) :s++) n=10*n+(*s-‘0’);51
return n*Sign;
}
void main (void)
{ char s[81];
gets(s);
printf(“%ld”,Func(s));
}
四、程序填空(本大题共10 个空,每空2 分,共20 分)
1、以下程序从键盘输入数据到数组中,统计其中正数的个数,并计算它们之和。
请填空。
void main(void)
{ int i,a[20],sum,count;
sum=count=0;
for(i=0;i<20;i++) scanf(“%d”, 【1】 ) ;
for(i=0;i<20;i++)
{ if(a>0)
{ count++;
sum+= 【2】 ;
}
}
printf(“Count=%d ,Sum=%d”,count,sum);
}52
2、以下函数的功能是删除字符串s 中的所有数字字符,请填空。
void DelSpace (char *s)
{ int n=0,i;
for(i=0; s; i++)
if( 【3】 ) s[n++]=s;
s[n]= 【4】 ;
}
3、下面是折半查找算法,请填空。
int Search_Bin (SSTable ST , KeyType key)
{ low =1 ;high=ST.length; //置区间初值
while(low<=high)
{ mid= 【5】 ;
if(ST.elem[mid].key=key) return mid ; //找到
待查元素
else if(key<ST.elem[mid].key)
【6】 ; //继续在前半区间进行查

else low= 【7】 ; //继续在后半区间进行
查找
}
return 0; // 顺序表中不存在待查元素
} //Search_Bin53
4、下面为直接插入排序的算法,请填空。
viod InsertSort(SqList &L) { //对顺序表 L 作直接插入排
序。
{for(i=2; i<=L.length; ++i)
if(L.r.key< L.r[i-1].key){
【8】 ;// 复制为监视哨
for(j=i-1;L.r[0].key<L.r[j].key; --j)
【9】 ; // 记录后移
【10】 ; // 插入到正确位置
}
}// InsertSort
五、简要回答题(共5 小题,每小题4分,共 20 分)
1、某二叉树的前序遍历节点访问顺序是 abdgcefh, 中序遍历的节点访
问顺序是 dgbaechf ,则其后序遍历的节点访问顺序是什么?
2、在队列的顺序存储结构中,为什么要采用循环队列的形式?
3、在有向图的邻接矩阵中,如何判断入度或出度为零的顶点?在有向图邻
接表中,又如何判断出度为零的顶点。
4、为什么说线性表的顺序存储结构是一种随机存取结构?
5、请求解下图的最小生成树。54
v1
v4
v3
v2
v6 v5
6 5
1
2
6
3
5
4
5
6
六、程序设计(本大题共4 小题,每题10 分,共40 分)
1、请编写函数 void Func(int *a,int *n); 它的功能是: 求出 1
到 1000之内能被 7 或 11 整除、但不能同时被 7 和 11 整除的所有整数并将它
们放在 a 所指的数组中,通过 n 返回这些数的个数。注:假设 a 所指的数组有
足够的空间存储满足条件的数。
2、编一个函数,用递归方法求n 阶勒让德多项式的值。其中:多项式的值
通过函数返回,多项式的阶 n 以及多项式的变量 x 通过函数参数传递。递归公
式如下:
3、有一个单链表,其结点的元素值以非递减有序排列,编写一个函数删除
该单链表中多余的元素值相同的结点。
4、设一棵二叉树以二叉链表为存储结构,设计一个算法求二叉树的高度。55
西南交通大学 2007 年硕士研究生入学考试试卷
试题代码:921
试题名称:程序设计与数据结构
考生注意:
1.本试题共 6大题,共 8页,考生请认真检查;
2.请务必将答案写在答卷纸上,写在试卷上的答案无效。
题号 一 二 三 四 五 六 七 八 九 十 总分
得分
签字
一、填空题(本大题共20 个空,每空1 分,共20 分)
1、一个 C程序的基本组成单位是 。
2、若有定义:int i=010 ,j=110; 则执行语句 printf(“%d,%d”,i,j);后的输出
结果是 。
3、下列数学表达式的 C语言表达式是 。56
4、若有定义:double x=3.5,y=8.3 ;int a=5:则表达式:
x+a%3*(int)(x+y)%3/4 的值是 。
5、若有 int x=0,z=2: 执行语句 z=(x=0)?13:8 后 : z= 。
6、设 a , b 均为整型变量,则语句: a=10; b=-a ; a*=b++; 执行后,
a= ;b= 。
7、有如下定义: char *s=”\”Hello\\world\n”; 指针 s 所指字符串的长度
为 。
8 、 若 有 定 义 : int a[5],*p=a; 则 p+3 表 示 ; *p+3 表
示 。
9、在大部分的应用场合,各种数据结构的存储形式有 , 两种。
10、队列的特点是: 。栈的特点是 。
11、一个二维数组的元素在内存中的存放方式有 和 两种。
12、由二叉树的前序(根)遍历序列和 遍历序列可以唯一确定一棵二叉树。
13、在一棵有 14 个结点的完全二叉树中,所含叶子结点的数目为 个。
14、 一个深度为5, 18个结点的完全二叉树, 编号为8的结点的右儿子的编号 。
15、对 n 个记录的表 r[1…n]进行简单选择排序,所需进行的关键字的比较次数
为 。
二、单项选择题(本大题共20 小题,每小题1 分,共20 分。在每
小题列出的四个选项中只有一个选项是符合题目要求的, 请将正确选
项前的字母写在答卷纸上)
1、以下关于 switch 语句和 break 语句的描述中,正确的是【 】 。57
A.在 switch 语句中必须使用 break 语句
B.在 switch 语句中,可以根据需要使用或不使用 break 语句
C.break语句只能用于 switch 语句中
D.break语句是 switch语句的一部分
2、以下语句或语句组能正确进行字符串赋值的是【 】 。
A.char *s; *s=”Hello” ; B.char *s ; s=”Hello” ;
C.char s[6]; *s=”Hello”; D.char s[6] ; s=”Hello”;
3、在 C 语言中,以下关于函数叙述正确的是【 】 。
A.函数定义可以嵌套,但函数调用不能嵌套
B.函数定义不可以嵌套,但函数调用可以嵌套
C.函数定义和调用均不能嵌套
D.函数定义和调用均可以嵌套
4、设有定义: int (*ptr) [10] ; 则标示符 ptr 是【 】 。
A.10 个指向整型变量的指针;
B.指向 10 个整型变量的函数指针
C.具有 10 个指针元素的一维指针数组,每个元素都只能指向整型量
D.一个指向具有 10 个整型元素的一维数组的指针。
5、假定 int 类型变量占用两个字节,若有定义: int a[10]={1,2,3};则数组 a在内
存中所占字节数是【 】 。
A.3 B.6 C.10 D.20
6、在 while (a) 中的 a 与下面条件表达式等价的是【 】 。
A.a==0 B.a==1 C.a!=1 D.a!=058
7、在函数中未指定存储类别的变量,其隐含的存储类型是【 】 。
A.自动变量(auto) B.静态变量(static)
C.寄存器变量(register) D.外部变量(extern)
8、 若 fp 是指向某文件的指针, 且已读到此文件末尾, 则库函数 feof(fp)的返回值是 【 】 。
A.EOF B.0 C.非零值 D.NULL
9、若变量已正确定义,要求程序段完成求 5!的计算,不能完成此操作的程序段是【 】 。
A.for(i=1,p=1;i<=5;i++) p*=i;
B.for(i=1;i<=5;i++) {p=1 ;p*=i;}
C.i=1;p=1;while(i<=5){p*=i;i++;}
D.i=1;p=1;do{p*=i;i++;}while(i<=5);
10、下列关于 C 语言数据文件的叙述中正确的是【 】 。
A.文件由 ASCII 码字符序列组成,C语言只能读写文本文件
B.文件由二进制数据序列组成,C 语言只能读写二进制文件
C.文件由记录序列组成,可按数据的存放形式分为二进制文件和文本文件
D.文件由字节流形式组成,可按数据的存放形式分为二进制文件和文本文件
11、将一个长度为 n 的向量的第 i个元素删除时,需要前移【 】个元素。
A.i B.n-i C.n+1 D.n-i+1
12、带头结点的单链表,头指针为 head,判断其是否为空的条件是【 】 。
A.head=NULL B.head->next=NULL
C.head=head D.head->next=head
13、在一个单链表中,已知 q 结点是 p 结点的前驱结点,在 q 之后插入结点 s,正确的操
作步骤序列是【 】 。59
A.q->next=s; s->next=p; B.s->next=p->next; q->next=s;
C.p->next=s; s->next=p; D.p->next=s;s->next=q;
14、设 s为类型 SqStack 的栈变量,判定栈空的条件是【 】 。
A.s=null B.s->top=0 C.s.top=0
D.s.top=s.base
15、深度为 4的二叉树至多有【 】个结点。
A.12 B.13 C.14 D.15
16、关于二叉排序树,下列论断正确的是【 】 。
A.根结点的值大于左子树上的所有结点的值,而小于右子树上所有结点的值
B.根结点的值大于左孩子结点的值,而小于右孩子结点的值
C.任意一个结点的值均不小于其左子树上的所有结点的值,而大于其右子树上所有结点的

D.根结点的值大于左子树上的所有结点的值,而小于右子树上所有结点的值,左右子树都
是二叉排序树
17、对 20 个有序记录进行折半查找,查找成功的平均查找长度为【 】 。
A.5 B.37/10 C.39/10 D.41/10
18、哈希表长度为 m,哈希函数 H(K)=K%P,一般来说 P 应取小于 m的最大【 】 。
A.奇数 B.偶数 C.素数 D.合数
19、当初始数据有序时,不应采用【 】 。
A.堆排序 B.快速排序 C.基数排序 D.希尔排序
20、在 n个元素中找出两个最小的元素,当 n 很大时,采用【 】方法比较次数较少。
A.堆排序 B.简单选择排序 C.归并排序 D.快速排序60
三、阅读程序(本大题共4小题,每小题4 分,共16 分。阅读下面
程序,将程序的运行结果写在答题纸上—请务必注意输出函数中的换
行控制符,你的答案必须反映出换行信息) 。
1、下面程序运行时,若输入 4,则输出结果是 。
#include <stdio.h>
void main(void)
{ int n,i ,j;
scanf(“%d”,&n)
for(i=1;i<=n;i++)
{ for(j=1;j<=i-1;j++) putchar(32); /* putchar(32)的功
能是打印一个空格*/
for(j=1;j<=2*(n-i)+1;j++) putchar(‘*’);
printf(“\n”);
}
}
2、下面程序运行时,若输入 4 13 8 7 9,则输出结果是 。
#include <stdio.h>
void Func(int a[ ],int s,int t)
{ int Temp;
if(s>=t) return;
Temp=a; a=a[t]; a[t]=Temp;
Func(a,s+1,t-1);61
}
void main(void)
{ int a[5],i;
for(i=0;i<5;i++) scanf(“%d”,&a);
Func(a,0,4);
for(i=0;i<5;i++) printf(“%4d”,a);
}
3、下面程序运行后输出结果是 。
#include <stdio.h>
void main(void)
{ char a[2][81]={“abc”,”defgh”};
char *p1,*p2;
p1=a[0];p2=a[1];
while(*p1) p1++;
while(*p2) *p1++=*p2++;
*p1=*p2;
printf(“%s\n%s”,a[0],a[1]);
}
4、对于下述算法,若输入 1348,则该算法的输出为 。
void conversion()
{ InitStack(S);
scanf(“%d”,&n);62
while(n){
Push(S,n%8);
n=n/8;
}
while(!StackEmpty()){
Pop(S,e);
Printf(“%d”,e);
}
}
四、程序填空(本大题共10 个空,每空2 分,共 20 分。将“ 【】 ”中
需要填入的内容写在答卷纸上)
1、函数 void Func(float *n,int n )的功能是:根据以下公式计算 S,计算结果通
过形参指针 sn 传回;n通过形参传入,n 的值大于等于 0,请填空完成该函数。
void Func(float *sn, int n)
{ float s=0.0 ,w , f=-1.0;
int i;
for(i=0; i<=n ; i++)
{ f=【 1 】*f;
w=f/(2*i+1);
s+=w;
}63
【 2 】 ;
}
2、 以下程序中, 函数 sumColumM 的功能是: 求出 M行 N列二维数组每列元素中的最小值,
并计算它们的和值。和值通过形参 sum 传回给主调函数。请填空该函数。
#define M 5
#define N 8
void SumColuMin (int a[M][N],int *sum)
{ int i,j,k,s=0;
for(i=0;i<N;i++)
{ k=0;
for(j=1;j<M;j++)
if(a[k][j]>a[j]) k=j;
s+=【 3 】 ;
}
【4】 ;
}
3、函数 Func 的功能是实现 N*N 阶方阵的转置,在 Func 中所调用的 Swap 函数的功能是
实现 2个整数的交换,请填空。
#define N 8
void Swap (int *p, int *q)
{ *p=*p+*q; *q=*p-*q; *p=*p-*q;
}64
void Func (int a[N][N])
{ int i,j ;
for(i=0; i<N; i++)
for(j=0;j< 【5】 ;j++) Swap(&a[j],【 6 】);
}
4、下面算法的功能是实现将两个带头结点的有序链表合并为一个有序链表,合并后不保留
原来连个链表,请填空。
void Mergelist_L(Linklist &La,Linklist &Lb,Linklist &Lc){
pa=La->next; pb=Lb->next;
Lc=pc=La;
while(【 7 】){
if(pa->data<=pb->data){
【 8 】 ;
pc=pa;
【 9 】 ;
} else {
pc->next=pb;
【 10 】 ;
pb=pb->next;
}
}
pc->next =pa?pa:pb;65
free(Lb);
}
五、简要回答题(本大题共 6小题,每小题4 分,共24 分)
1、设有整型数组 a[10][15][20],第一个数组元素的地址为 1000,每个数组元素占 4
个字节。请回答下列问题:
(1)数组 a 所占存储空间是多大?
(2)按低下标优先进行存储,元素 a[5][6][7]的存储地址是什么?
(3)按高下标优先进行存储,元素 a[5][6][7]的存储地址是什么?
2、对于队列的顺序存储结构,什么叫队列的假溢出?引起队列假溢出的原因何在?请给出
一种解决假溢出的方法。
3、某通讯系统只可能有 A、B、C、D、E、F 共 6种字符,其出现的概率分别是 0.14、0.4、
0.04、0.12、0.17、0.13,试画出相应的郝夫曼树。
4、假设一棵二叉树的前序序列为 GDCFEAB,中序序列为 CDEAFBG,请画出该二叉树。66
5、判断序列{46, 35, 62, 94, 73, 10, 24}是否构成一个堆,若不是堆,则按
初始堆创建算法将该序列调整为小顶堆(首元素最小) 。
6、设哈希表的长度 m=12,使用的哈希函数为 h(k)=k%11,采用线性探测再散列法处理冲
突,将数据{1,12, 13, 34, 38, 33, 27, 22}插入到哈希表中。
六、程序设计(本大题共5 小题,每小题10 分,共 50 分)
1、从键盘输入一个大于 0的实数 a,用迭代法求 a 的平方根。求平方根的迭代公式是:
要求前后 2次求出的 x 的差的绝对值小于。
2、从键盘输入一个大于 1的正整数 n,计算以下级数的值,并输出结果(显示结果保
留小数点后 6 位) 。
3、从键盘输入任意一个大于等于 2 的自然数 m,将 m写成所有素因子乘积的形式,67
例如,若输入: 13 , 则你的输出应该是: 13=13
若输入:420 , 则你的输出应该是: 420=2*2*3*5*7。
4、编写一个算法将一个带头结点的单链表 A 分解成两个单链表 A和 B,使得 A 链表中
含有原链表 A 中序号为奇数的元素,而 B 链表中含有原链表 A 中序号为偶数的元素,且保
持原来的相对顺序。
5、试编写一个算法,判断给定的二叉树是否是二叉排序树。假定二叉树中结点的值为
大于 0的整数。
西南交通大学 2006 年硕士研究生入学考试试卷
试题代码:412
试题名称:程序设计及数据结构
考生注意:
1.本试题共 6大题,共 9页,考生请认真检查;68
2.请务必将答案写在答卷纸上,写在试卷上的答案无效。
题号 一 二 三 四 五 六 七 八 九 十 总分
得分
签字
一、填空题(本大题共 20 小题,每小题1 分,共 20 分)
1、若有定义 :int a=2,b=2; 则计算表达式 a+=a*=b-=a 之后,a 的值
是 。
2、若有定义:inta[3]={3,13,56},*p=a,*q=a;则表达式:(*++p)+(++*q)的值
是 。
3、若有如下定义:int y=319,z=3;则下列表达式的值是:
(’E’/y*1000) ; (z=2*3,z*5,z*8) ;
4 、 若 有 宏 定 义 : #define MYFUNC(x,y)(x>y?x:y) 则 MYFUNC(3,7) 的 值
是 。
5、在平面坐标系中,点 A 的坐标是(x1,y1),点 B 的坐标是(x2,y2),则表示 A 与 B 的
距 离 的 C 语 言 表 达 式
是 。
6、C语言中构造数据类型有: 。
7、C语言存储字符串时,用特殊的字符 表示字符串的结束。
8、定义 C函数时,若函数没有返回值,则返回值类型应设为 。
9、用数组名作为函数调用时的实参,实际上传送给形参的是 。
10、以下程序运行后,输出结果是 。69
void main(void)
{ int i ,Sum;
for(i=0;i<=100;i++)
{ Sum=0;
Sum=Sum+i;
}
printf(“%d”,Sum);
}
11、数据结构中,处理数据的最小单位为 。
a.数据 b.数据项 c.数据对象 d.数据元素 e.基本数据类型
12、n 个节点的二叉树最大深度为 ;最小深度为 。
13、二叉排序树的查找时间复杂度为 ;最坏情形的查找比较次数
为 。
14、平衡二叉树是二叉树吗?(Yes or No) 。
15、平衡二叉树左右子树深度之差的绝对值小于 。
16、平衡二叉树的查找算法思想与折半查找算法思想一样吗? 。
17、数据结构有哪四种基本结构?
; ; ; ;
18、列出五种以上常见的基本操作:
; ; ; ; ;
19、栈是受限的线性表吗?(Yes or No) ;
20、栈的数据操作特点是什么? 。70
二、单项选择题(本大题共10 小题,每小题1 分,共10 分。在每
小题列出的四个选项中只有一个选项是符合题目要求的, 请将正确选
项前的字母写在答卷纸上)
1、若 fp 是指向某文件的指针,且 feof(fp)的返回值是非零,则表示【 】
A.此文件已关闭 B.未读到此文件的末尾
C.已读到此文件末尾 D.此文件尚未被打开
2、若 w 为 char 类型变量,则能正确判断 w 为小写字母的表达式是【 】
A.’a’<=w<=’z’ B.(w>=’a’)or(w<=’z’)
C.(w>=’a’)and(w<=’z’) D.(w>=’a’)&&(w<=’z’)
3、已知有共用体变量 Data 定义如下:
union uData
{ int i;
char c;
float f;
} Data;
则变量 Data 所占的内存存储空间可表示为【 】
A.sizeof(int) B.sizeof(char)
C.sizeof(float)
D.sizeof(int)+sizeof(char)+sizeof(float)
4、设有如下定义:char *s[2]={“Hello”,”World”};则以下说法中正确的是【 】
A.s数组元素的值分别是”Hello”和”World”
B.s是指针变量,它指向含有两个数组元素的字符型一维数组71
C.s数组的两个元素分别存放的是含有 5个字符的字符串常量的首地址
D.s数组的两个元素中各自存放了字符”H”和”W”的地址
5、若有定义:int a[10] ,*p=a;则 p+3 表示【 】
A.a[3] B.*a+3 C.*(a+3) D.&a[3]
6、若有定义:int a[7][6],*p=(int *)a;则能表示数组元素 a[M][N](0≤M<7;0
≤N<6)的是【 】
A.*(p+M*7+N) B.*(P+M*6+N) C.*(p+N*7+M) D.*(p+N*6+M)
7、有如下定义: int k; float f,g; 在执行赋值语句 f=k=g=3.5;后 f,g的值分
别是【 】
A.3.5 ,3.5 B.3.0 , 3.0 C.3.5 , 3.0 D.3.0 , 3.5
8、以下程序段输出结果是【 】
int x=9;
do{printf(“%4d”,x+=4);} while(x++);
A.-5 0 B. -5 C.-5 -1 0 D.死循环
9、以下程序运行后输出结果是【 】
#include<stdio.h>
int MyFunc(void)
{ static int x=0 ;
return ++x;
}
void main(void)
{ int i;72
for(i=0;i<3;i++) printf(“%4d”,MyFunc());
}
A.1 1 1 B.0 0 0 C.0 1 2 D.1 2 3
10、int Func(int n)
{ if(n<1) return n;
return n*Func(n-3);
}
void main(void)
{ printf(“%4d”,Func(7));
}
以上程序运行后,得出结果是【 】
A.28 B.-2 C.-56 D.-28
三、简要回答题(本大题共 8小题,每小题4 分,共32 分)
1、设有模式字符串 P=“1 1 2 1 2 1 1 2 1 3”,求 Next[j]。
2、下面为顺序方式存储的二叉树,画出该二叉树
a b c d e
1 2 3 4 5 6 7
3、下图为孩子兄弟法存储的森林,画出该森林的逻辑图73
1
^ 2
3
^ 7
8 ^
^ 5 4 ^ ^ 9
^ 10 ^ ^ 6 ^ 兄弟孩子表示法
4、假设序列长度为 n,下面算法的时间复杂度为: 。
int partition (Sqlist &L,int low , int high)
{ temp=L.r[low];
while(low<high)
{ while(low<high&&L.r[high].key>=temp.key)
--high;
L.r[low]=L.r[high];
while(low<high&&L.r[low].key<=temp.key) ++low;
L.r[high]=L.r[low];
}
L.r[low]=temp; return low;
}74
5、假设一棵二叉树的后序序列为 ACDBGJKIHFE,中序序列为 ABCDEFGHIJK,请画出该
二叉树。
6、设有如下权值序列: {7,14,19,2,6,32,3,21,10} ,求该权值序列的最优二叉树。
7、设关键字序列为{9,8,3,6,5,1,4,7,2},按初始堆创建算法将该序列调整为堆(首元
素最小)。
8、设有如下特殊矩阵 A,将其压缩存储到一维数组 SA 中。
SA=
(k=0,1,2,……,3n-3)
写出由下标[i,j]求 k 的映射公式。
四、阅读程序(本大题共3小题,每小题4 分,共12 分。阅读下面
程序,将程序的运行结果写在答题纸上—请务必注意输出函数中的换
行控制符,你的答案必须反映出换行信息) 。
1、下面的运行时,若输入: 4 5 28 54 19 ,则输出结果是 。
#include<stdio.h>
void main(void)75
{ int Sum,m,n,i;
Sum=0;
scanf(“%d”,&m);
for(i=1;i<=m;i++)
{ scanf(“%d”,&n);
if(n%2==0) Sum*=2;
else Sum+=2;
}
printf(“%d”,Sum);
}
2、下面程序的运行结果是 。
#include <stdio.h>
void Func(char x,char &y)
{x++; y++; }
void main (void)
{ char x=’a’, y=’b’;
Func(y,x); printf(“%c%c\n”,x,y);
Func(x,y) printf(“%c%c\n”,x,y);
Func(‘D’,x) printf(“%c%c\n”,x,y);
}
3、下面程序运行时,若从键盘输入:How are you 则输出结果是 。
#include <stdio.h>76
void main(void)
{ char s[81],*p;
get(s);
for (p=s;*p;p++)
if(*p==32)
{
if(*(p+1)!=32) printf(“\n”);
}
else putchar (*p);
}
五、程序填空(本大题共 12 个空,每空 2 分,共 24 分。将” 【】 ”
中需要填入的内容写在答卷纸上)
1、下面程序的功能是:输出 1000 以内能被 7整除且个位数为 8的所有整数,请填空。
#include <stdio.h>
void main(void)
{
int i,j;
for(i=0; 【1】 ;i++)
{ j=i*10+8;
if( 【2】 )continue ;
printf(“%10d”,j);
}77
}
2、以下是统计文本文件 c:\F.txt 中有多少空格,请填空。
void main(void)
{ FILE *fp;
char c;
int n=0;
if(!(fp=fopen( 【3】 )))
{
printf(”打开文件失败! ”);
return;
}
while(1)
{
c=fget(fp);
if( 【4】 ) break;
if( 【5】 ) n++;
}
printf(“\n 空格个数: %d” ,n);
fclose(fp);
}
3、下面为折半查找算法,填写适当的语句或条件,完善该算法。
int Search_Bin(SSTable ST,KeyType key);78
{ low=1;high= 【6】 。
while( 【7】 )
{ mid= 【8】 /2;
if EQ(key,ST.elem[mid].key) rerurn mid ;
else if LT(key,ST.elem[mid].key) high= 【9】 。
else 【10】 。
}
return(0); }
4、设有线性表:
L[1…10]={65, 43, 50, 10, 90, 18, 70, 30, 80, 20}
调用 partition(L, 2, 8)之后:有
L[1…10]={ 【11】 };
函数值= 【12】 ?
int partition(Sqlist &L,int low ,int high)
{ temp=L.r[low];
while(low<high)
{ while(low<high&&L.r[high].key>=temp.key)
--high;
L.r[low]=L.r[high];
while(low<high&&L.r[low].key<=temp.key) ++low;
L.r[high]=L.r[low];
}79
L.r[low]=temp; return low; }
六、程序设计(本大题共6小题,其中第 1、2、3 小题各 8分,第
4 小题9分。第 5题 6 分,第6 题13 分,共 52 分)
1、有一函数:
写一程序,从键盘输入 x 的值,输出 y 的值。
2、编写函数 Digit(int n, int k) ,函数返回值是正整数 n的左起第 k 位数,若位数
不够则返回-1.
例如:Digit(31415926, 6)=9,Digit(3141, 5)=-1.
3、已知单向链表结点结构为:struct MyNode(int Data;MyNode *pNext);编写一
个函数:struct MyNode *ChangeHead (struct MyNode *pHead),其中形参 pHead
为链表的头指针,该函数将链表的链头当链尾,链尾当链头,其余结点的次序不变,并返回
新的头指针。
4、编写程序,从键盘输入一个文本文件名和一个单词,统计在文件中有多少个这样的单词。
注:此出的“单词”指有由空格或换行符隔开的连续的字符串,而不管它是否有实际意义:
此外,对于英文字母不区分大小写。
如:输入的单词是:aBc 而文件内容如下(2 行):
123Abc abc abcd
ABC 7Ashd
则:你的输出应该是 280
又如:输入的单词是:123aBc 而文件内容如下(2行):
123aBc abc 12
3aBc 7Ashd
则:你的输出应该是 1
5、编写两个递归算法,分别计算二叉树中叶子结点的数目、二叉树深度。 (6分)
6、设有如下哈希查找表:学生库采用顺序存储结构,长度为 Maxlength,p 为顺序存储
结构的一个下标变量,总是指向下一个可用空间,初始值为 1;哈希映射表长度为 26,分
量类型与 p类型相同。哈希函数假设为学生姓名的拼音首字母在字母表中的位序(a的位序
为 0,z 的位序为 25) ;在哈希查找表中插入一个学生数据元素时,总是插入到 p 所指可用
空间中,p加 1后再次指向下一可用空间。
请完成:
A> 用高级语言描述哈希映射表的存储结构定义: (1 分)
B> 用高级语言描述学生项(数据元素)的类型定义: (2 分)
C> 用高级语言描述完整哈希表的存储结构定义: (3 分)
D> 在下表的基础上,采用什么方法解决冲突?(1分)
E> 写出在哈希查找表中插入一个数据元素的算法(注意冲突的解决) : (3分)
F> 假设哈希查找表初始化为空表,依次插入如下姓名的数据元素:
Lipin, Wanglin, Zhaogang, Wuxing, Luohao, Zongyong,
wengkai,Louyong
画出插入八个数据元素后的哈希查找表及内容。 (3分)81
可 用
空 间
姓名拼音 成绩总分 冲突地址
学生库 哈希查找表
哈希映射
0
1
25
P→82
可以参考的“答案”
说明:1、本部分只有数据结构参考答案;C 程序设计,毫无。
2、详细答案解析在李春葆版《数据结构习题与解析》上有;鄙人偷懒,不敲了。
2012 年真题参考答案
一、单项选择题
1~25: CBCAC BBBDC ADCCB ACBBB CBBAD
二、填空题
1.表示 2.关于规模 n 3.O(1) O(n) 4.前驱 5.非循环双
6.p->next s->data t 7.假溢出时大量移动数据元素
8.栈为“先进后出,后进先出” ,而队列为“先进先出,后进后出” 。83
9.链栈 10.m-1 n-2m+1 11.n2+1 12.n+1
13.p->lchild==NULL&&p->rchild==NULL 14.任意 1
15.邻接矩阵 邻接表 16.将第 i列元素全置为 0 17.n-1
18.哈希函数 解决地址冲突的方法 19.顺序存储且结点按关键字有序
20.索引表 块表 21.堆排序 快速排序
三、简答题
1.时间复杂度、空间复杂度
2.只设一个尾指针。插入、删除元素时的时间复杂度为 O(1)。
3.(1)
(2)
(3)
4.
A
B F
C D G
H E I
J
先序序列:ABCDEFGHIJ
5.(1)84
v1 2 5 ^
v2 1 6
v3
v4
v5
v6
2 6 ^
3 4 ^
2 3 5 6 ^
1 4 6 ^
1 2 4 5 ^
(2)略
6.
a[8]
a[3] a[7]
a[1] a[4]
a[2]
a[6] a[9]
a[5]
a[10]
7. 初始:17,18,60,40,7,32,73,65,85
第 1趟:17,18,40,7,32,60,65,73,85
第 2趟:17,18,7,32,40,60,65,73,8585
第 3趟:17,7,18,32,40,60,65,73,85
第 4趟:7,17,18,32,40,60,65,73,85
第 5趟:7,17,18,32,40,60,65,73,85
第 5趟无元素交换,则排序结束。
四、完善算法和算法设计题
1、 (ListNode *)malloc(sizeof(ListNode))
pa->data
p
pa
NULL
2、 void del(List &L)
{ p=L->next; //指向第一个结点
if(p!=NULL)
while(P->next!=NULL)
{ if(p->data!=x) p=p->next;
else
{ g=p->next;
p->next=g->next;
free(g);
}
}
}86
3、1)队满的条件:Q.length==MAXQSIZE;
2)入队列算法: Q[Q.rear]=x; Q.rear=(Q.rear+1)%MAXQSIZE;
Q.length=Q.length+1;
3)出队列算法: x=Q.[Q.rear-Q.length];
Q.length=Q.length-1;
return x;
4、 int Depth( BiTree &T)
{ int m,n;
if(!T) return 0;
m=Depth(T->child);
n=Depth(T->rchild);
return (m>n?m:n)+1;
}
2011 年真题参考答案
一、单项选择题
1~25:ABBAA ACCCB BDCBB CAAAB DBACA
二、填空题
1、相邻 连续的空间 指针 2、n-i+1 3、带尾指针的双向循环
4、O(n) O(n) 5、链栈 6、先存放元素,后移动队尾指针
7、任意个连续字符组成的子序列 8、 n
9、 10、n+1 11、m-1 n-2m+1
12、空树或者任意结点都没有左子树 13、矩阵中非零元素的个数/287
两顶点对应的元素是否为零 该顶点所在行的非零元素的个数
14、2m 15、顺序存储 结点元素按关键字有序
16、有序 17、O() O()
18、插入排序 选择排序 19、O(n)
三、简答题
1.数据结构用于描述数据对象及数据元素之间的关系;
数据类型描述了数据对象、数据元素间的关系及数据的基本处理方法。
2.链式存储;不需要移动大量元素
3. 1)队列中还有未使用的存储空间,但不能插入元素
2)队列的假溢出现象是指队列中还有空余的空间,但元素不能进队列
3)解决队列假溢出的方法如下:
①建立一个足够大的存储空间,但这样做会造成空间浪费
②采用环形队列方式
③采用平移元素的方法,每当删除一个队头元素时,依次移动队中的元素,始终使
front指向队列中的第一个位置。
4.(1)
(2)
(3)
5.88
11 16
5 6
4
7 9
21
2
0 1
0
1
0
1
0
1
c
a d
b
e
WPL
a:010 b:10 c:00 d:011 e:11
6.89
G
B
F
A D
C
H
E
I
K
J
后序序列:ACDBGJKIHFE
7、①
1
12
5 13
3 8
7 10
9
②:中序序列90
四、完善算法和算法设计题
1. bt push(s,p) pop(s,p) p=p->rchild
2. pivotkey=L.r[low].key
L.r[low]=L.r[high]
low<high&&L.r[low].key<=pivotkey
L.r[low]=L.r[0]
3. void del(List &L)
{ p=L->next; //指向第一个结点
if(p!=NULL)
while(p->next!=NULL)
{ if(p->data!=p->next->data)
p=p->next;
else
{ g=p->next;
p->next=g->next;
free(g);
}
}
}
4. void inter(SNode *A,SNode *B,SNode *c)91
{ SNode *pa=A->next,*pb=B->next,*s,*r;
C=(SNode *)malloc(sizeof(SNode)); //建立 C的头结点
C->next=NULL;
r=C;
while(pa!=NULL&&pb!=NULL)
{ if(pa->data < pb->data)
pa=pa->next;
else if(pa->data > pb->data)
pb=pb->next;
else
{ s=(SNode *)malloc(sizeof(SNode));
s->data=pa->data;
s->next=NULL; //建立一个复制结点
r->next=s;r=s;
pa=pa->next;pb=pb->next;
}
}
r->next=NULL;
}92
2010 年真题参考答案
一、单项选择题
1~25:CCCDA CAACA DBABA BBBAC DCBAD
二、填空题
1.顺序存储结构 链式存储结构 2.n-i 3.方便运算的实现
4.前驱结点 后继结点 5.循环双 6.O() O(n)
7.①一个标志字段区分队空队满,少用一个元素空间,m 个元素单元最多只存放 m-1 个元

② front=rear ---队空 (rear+1)%m=front ---队满
③长度计数器
8. 9.5 (画图太麻烦,第二个空自行意会) 10.邻接矩阵 邻接表
11.n n+1 12. 13.直接插入 简单选择
14.快速排序 归并 15.堆排序 快速排序 归并排序 快速排序 堆排序
三、简答题
1.ABC CBA ACB BAC BCA
2.①


3.93
45
53
25 90 12
24
4.前: eadcbjfghi
中:abcdjefhgi
后:bcjdahigfe94
5.
41 59
18 23
13
25 34
21
12
0 1
0
1 0
1
f
e
c
d a
5 8
0
1
0 1
b
a:11 b:1010 c:100 d:01 e:1011 f:00
6.95


2
1
3
4
5
6
四、完善算法和算法设计题
1. Q.rear==Q.front
Q.front=(Q.front+1)%M
2. low<=high
(low+high)/2
mid-1
mid96
return 0
3. int AddList(Sqlist &L,int &x)
{ int i,p;
if(L.length==MAX)
return 0;
for(i=1;i<=L.length;i++)
if(x<L.data)
{
p=i;
}
if(x>L.data[L.length])
p=L.length;
for(i=L.length;i>=p;i--)
L.data[i-1]=L.data;
L.data[p]=x;
L.length++;
return +;
}
4. void intsert(SNode *A,SNode *B,SNode *c)
{ SNode *pa=A->next;*pb=B->next,*r,*s;
C=(SNode *)malloc(sizeof(SNode));
C->next=NULL;97
r=C;
while(pa!=NULL&&pb!=NULL)
{ if(pa->data > pb->data)
{ s=(SNode *)malloc(sizeof(SNode));
s->data=pb->data;
s->next=NULL;
r=s;r=r->next;
pb=pb->next;
}
if(pa->data < pb->data)
{ s=(SNode *)malloc(sizeof(SNode));
s->data=pb->data;
s->next=NULL;
r=s;r=r->next;
pa=pa->next;
}
if(pa->data == pb->data)
{ s=(SNode *)malloc(sizeof(SNode));
s->data=pb->data;
s->next=NULL;
r=s;r=r->next;
pa=pa->next;pb=pb->next;98
}
while(pa)
{ r=pa;pa=pa->next;}
while(pb)
{ r=pb;pb=pb->next;}
}
}
2008 年真题参考答案(注意,此部分不包括程序设计答案,数据结
构的详解请参考李春葆版《数据结构习题与解析》 )
一、填空题
1~7:略
8.n-1 9.head->next==NULL 10.200+10*12+6=326 11. 12.n2+1
13.1 14.n-1 15.顺序 有序
二、单项选择题
1~14:略 15~30:C BCCAD ABCAC ADBBB
三、阅读程序,按提示给出结果
1~5:略
四、程序填空
1~2:略
3. (low+high)/2 high=mid-1 mid+1
4. L.r[0]=L.r L.r[j+1]=L.r[j] L.r[j+1]=L.r[0]
五、简要回答题99
1.gdbehfca
2.防止出现队列假溢出
3. 1)入度:该顶点所在行对应的元素全为 0
2)出度:该顶点所在列对应的元素全为 0
3)度为零:顶点的邻接点域为零。
4.顺序存储是以元素在计算机内“物理位置相邻”来表示线性表中数据元素之间的逻辑关系,
因此,只要确定了存储线性表的起始位置,线性表中任一数据元素都可随机存取。
5.
v2
v1
v3
v4
v5
v6
六、程序设计
1~2:略
3. void del(List &L)
{ p=L->next;
if(p!=NULL)
while(p->next!=NULL)
{ if(p->data!=p->next->data)100
p=p->next;
else
{
g=p->next;
p->next=g->next;
free(g);
}
}
}
4. int Depth(BiTree &T)
{
int m,n;
if(!T) return 0;
m=Depth(T->lchild);
n=Depth(T->rchild);
return (m>n?m:n)+1 ;
}
2007 年真题答案(注意,此部分不包括程序设计答案,数据结构的
详解请参考李春葆版《数据结构习题与解析》 )
一、填空题
1~8:略
9.顺序存储 链式存储 10.在表的一端进行插入,在另一端进行删除101
在表的一端进行插入删除
11.顺序存储 链式存储 12.中序 13.7 14.17 15. n(n-1)/2
二、单项选择题
1~10:略
11~20: BBADD DBCBA
三、阅读程序

四、程序填空

五、简要回答问题
1.
(1)
(2)
(3)
2.
(1)队空间还有存储单元未使用,但不能再插入元素
(2)头、尾指针值总是不断增加,已使用过的单元无法再使用
(3)1、将队中元素依次向队头方向移动
2、将队空间设想成一个循环的表
3.102
1
0.4 0.6
0.27
0.33
0.14 0.13 0.17
0.16
0.04 0.12
B
A F E
D
4.
5.
G
D
C F
E
B
A
C103
46
62 35
24 94 73 10
不构成一个堆。调整为小顶堆如下:
10
24 35
46 94 73 62
6.h(1)=1%11=1
h(12)=12%11=1 冲突 h(12)=(12+1)%11=2 (以下处理冲突方法雷同)
h(13)=(13+1)%11=3
h(34)=(34+3)%11=4
h(38)=38%11=5
h(33)=33%11=0
h(27)=27%11=6 h(22)=(22+7)%11=7
0 1 2 3 4 5 6 7 8 9 10
33 1 12 13 34 38 27 22104
六、程序设计
1~3:略
4. void Separate(LNode a,LNode b)
{ LNode r,p,g;
b=(LNode *)malloc(sizeof(LNode));
b->next=NULL;
r=b;
p=a->next;
while(p!=NULL&&p->next!=NULL)
{ g=p->next;
if(g!=NULL)
{ p->next=g->next;
r->next=g;
r=g;
p=p->next;
}
}
r->next=NULL;
}
5.略
2006 年真题答案(注意,此部分不包括程序设计答案,数据结构的
详解请参考李春葆版《数据结构习题与解析》 )105
一、填空题
1~10:略
11.b 12.n 13.O() O() 14.YES
15.2 16.一样 17.线性结构、树形结构、图形或网状结构、集合
18.插入、删除、查找、修改、排序 19.YES 20.只在一端插入删除
二、单项选择题
1~10:略
三、简要回答题
1.略(李版习题集有相似题)
2.
a
c b
e d
3.106
1 7
3
6
2 4
5
8
9 10
4. O()
5.
E
F B
H D
A
C
G
I
K
J
6.107
9
8 3
6 5 1
2 7
4
=>
1
2 3
6 5 9
8 7
4
7.
四、阅读程序

五、程序填空
1~2:略
3. ST.length
low<=high
(low+high)
mid-1
low=mid+1
4. 65,30,18,10,43,90,50,80,20
5
六、程序设计
1~4:略
5.计算叶子结点的数目:
void Num(BTNode *BT)108
{ if(BT==NULL) return 0;
if(BT->left==NULL&&BT->right==NULL)
return 1;
else return Num(BT->left)+Num(BT->right);
}
计算二叉树深度:
int Depth(BiTree &T)
{ int m,n;
if(!T) return 0;
m=Depth(T->lchild);
n=Depth(T->rchild);
return (m>n?m:n)+1;
}
6.略109
补充资料—常考的一些算法
说明:1)由于作者是数学专业跨考计算机,不保证这些算法全都正确。若是因为尽信此资
料而出了事,请您听天由命。
2)数据结构的算法大题基本是以下题的原题或变种题,其他的图、队列之类可能出
算法填空题,但不会出算法大题。
1、折半查找
2、直接插入排序
3、冒泡排序
4、简单选择排序
5、一趟快速排序
6、求二叉树的高度
7、计算一棵给定二叉树的单孩子的结点树
8、求二叉树的叶结点数
9、中序遍历110
10、在单链表中删除指定结点 P的算法
11、单链表分解
12、从单链表有序表 A中删除所有和有序表 B 中元素值相同的结点的算法
13、删除 P 的直接前驱的算法
14、删除元素值以非递减有序排列的单链表中多余的元素值相同的结点的算法
1、折半查找
int search(int R[],int low,int high,int k)
{ int mid;
while(low<=high)
{ mid=(low+high)/2;
if(R[mid]==k)
return mid;
else if(R[mid]>k)
high=mid-1;
else
low=mid+1;
}
rerurn 0;
}
2、直接插入排序
void InsertSort(seqlist &L)111
{ int i,j;
for(i=2;i<=L.length;++i)
if(LT(L.r.key,L.r[i-1].key))
{ L.r[0]=L.r;
for(j=i-1;LT(L.r[0].key,L.r[j].key);--j)
L.r[j+1]=L.r[j];
L.r[j+1]=L.r[0];
}
}
3、冒泡排序
void Bubblesort(int R[],int n)
{ int i,j,flag; int temp;
for(i=n;i>=2;i--) //数组从下标 1 开始存储数据
{ flag=0; //用来标记本趟排序是否发生了变换
for(j=2;j<=i;j++)
if(R[j-1]>R[j])
{ temp=R;
R[j]=R[j-1];
R[j-1]=temp;
flag=1;
}
if(flag==0)112
return ;
}
}
4、简单选择排序
void SelectSort(int R[],int n)
{ int i,j,k;
int temp;
for(i=1;i<=n;i++) //从无序序列中挑出一个最小的元素
{ k=i;
for(j=i+1;j<=n;i++)
{
k=i;
for(j=i+1;j<=n;j++)
if(R[k]>R[j])
k=j;
temp=R; //完成最小元素与无序序列第一个元素的
交换
R=R[k];
R[k]=temp;
}
}113
5、一趟快速排序
int partition(Sqlist &L,int low,int high)
{ L.r[0]=L.r[low];
pivotkey=L.r[low].key;
while(low<high)
{ while(low<high&&L.r[high].key>=pivotkey) --high;
L.r[low]=L.r[high];
while(low<high&&L.r[low].key<=pivotkey) ++low;
L.r[high]=L.r[low];
}
L.r[low]=L.r[0];
rerurn low;
}
6、求二叉树的高度
int Depth(BiTree &T)
{ int m,n;
if(!T) return 0;
m=Depth(T->lchild);
n=Depth(T->rchild);
rerurn (m>n?m:n)+1;
}
7、计算一棵给定二叉树的单孩子的结点树114
int onechild (btree *b)
{ int num1,num2;
if(b==NULL) return 0;
else if( (b->left==NULL&&b->rhght!=NULL) ||
b-left!=NULL&&b->right==NULL))
return 1;
else
{ num1=onechild (b->left);
num2=onechild (b->right);
return (num1+mun2);
}
}
8、求二叉树的叶结点数
Leaf_Num(BTnode *BT)
{ if(BT==NULL) return 0;
if(BT->left==NULL&&BT->right==NULL)
return 1;
else return Leaf_Num(BT->left)+ Leaf_Num(BT->right);
}
9、中序遍历
void order(T)
{ if(T)115
{ order(T->lchild);
printf(T->data);
order(T->rchild);
}
}
10、在单链表中删除指定结点P的算法
int Del(LinkList head,LNode *p)
{ LNode *g;
g=head;
while(g->next && g->next!=p) g=g->next;
if(!g->next) return 0;
g->next=p->next;free(p);
return 1;
}
11、 将一头结点指针为 a的单链表 A分解成两单链表 A和 B。 其头结点指针分别为 a和 b,
使得 A 链表中含有原链表 A 中序号为奇数的元素,而 B链表中含有原链表 A 中序号为偶数
的元素,且保持原来的相对顺序。
void Separate(LinkList a,LinkList b)
{ LinkList r,p,g;
b=(LinkList)malloc(sizeof(LNode)); //申请头结点
b->next=NULL;
r=b;116
p=a->next;
while(p!=NULL&&p->next!=NULL)
{g=p->next;
if(g!=NULL)
{ p->next=g->next;
r->next=g;
r=g;
p=p->next;
}
}
r->next=NULL;
}
12、从单链表有序表A 中删除所有和表B 中元素值相同结点的算法
Status Delete(LinkList A,LinkList B)
{ pre=A; pa=A->next;
pb=B-.next;
while(pa)
{ if(pa->data<pb->data)
{pre=pa;pa=pa->next; }
else if(pa->data==pb->data)
{ pre->next=pa->next;
free(pa);117
pa=pre->next;
pb=pb->next;
}
else if(pa->data > pb->data)
{ pb=pb->next ; }
return OK;
}
13、假设循环单链表的长度大于 1,既无头结点也无头指针,P
为指向该链表中某个结点的指针,删除P 的直接前驱的算法
Lnode delprior(Lnode *p)
{ Lnode *g,*r;
g=p;
while(g->next!=p) {g=g->next;} //找 P的直接前驱
r=g;
while(r->next!=g){r=r->next;} //找 P的直接前驱的前驱
r->next=p;
free(g);
return p;
}
14、删除元素值以非递减有序排列的单链表中多余的元素值相同
的结点的算法
void del(ListLink &L)118
{ p=L->next; //指向第一个结点
if(p!=NULL)
while(p->next!=NULL)
{ if(p->data!=p->next->data) p=p->next;
else{ g=p->next;
p=next=g->next;
free(g);
}
}
}
牛客网——免费领取计算机考研真题&答案!

2

主题

64

帖子

10

积分

王道论坛实习道友

Rank: 1

考研年份
2015
报考学校
安徽大学
本科学校
皖西学院
注册时间
2010-11-9
最后登录
2017-7-16
QQ
发表于 2014-5-29 20:23 | 显示全部楼层
牛客网——免费领取计算机考研真题&答案!

2

主题

64

帖子

10

积分

王道论坛实习道友

Rank: 1

考研年份
2015
报考学校
安徽大学
本科学校
皖西学院
注册时间
2010-11-9
最后登录
2017-7-16
QQ
发表于 2014-5-29 20:23 | 显示全部楼层
希望楼主继续更新复试相关细节和相关资料,赞!!!

1

主题

9

帖子

17

积分

王道论坛实习道友

Rank: 1

考研年份
2007
报考学校
南京理工
本科学校
福建工程学院
注册时间
2014-3-18
最后登录
2014-7-10
 楼主| 发表于 2014-6-9 13:10 | 显示全部楼层
加群327831433,一大波学长在等着你们!

12

主题

272

帖子

18

积分

王道论坛特别道友

Rank: 4

考研年份
2014
报考学校
北京航空航天大学
本科学校
西北农林科大
注册时间
2012-10-27
最后登录
2015-5-10
发表于 2014-6-13 13:24 | 显示全部楼层
这个好强大……

0

主题

2

帖子

3

积分

王道论坛实习道友

Rank: 1

考研年份
2015
报考学校
西南交大
注册时间
2014-8-25
最后登录
2014-9-23
发表于 2014-9-2 16:58 | 显示全部楼层
求 2014 的题啊

12

主题

114

帖子

10

积分

王道论坛实习道友

Rank: 1

考研年份
2014
报考学校
西南交大
本科学校
河海大学文天学院
注册时间
2012-9-14
最后登录
2014-9-19
QQ
发表于 2014-9-19 23:10 | 显示全部楼层
我这有更多,更详细,更新的内部资料,需要的加群:369738161

0

主题

24

帖子

39

积分

王道论坛初级道友

Rank: 2

考研年份
2015
报考学校
同济大学
本科学校
郑州大学
注册时间
2015-3-5
最后登录
2015-3-31
发表于 2015-3-17 09:54 | 显示全部楼层
想问下西南交通收调剂生吗,15年考了304.

0

主题

9

帖子

8

积分

王道论坛实习道友

Rank: 1

考研年份
2015
报考学校
西南交大
本科学校
西南交大
注册时间
2014-4-17
最后登录
2017-10-28
发表于 2015-4-19 22:17 | 显示全部楼层
今日不同往时,今年是报考大热门

0

主题

18

帖子

18

积分

王道论坛实习道友

Rank: 1

考研年份
2017
报考学校
西安交大
注册时间
2014-5-7
最后登录
2016-9-26
QQ
发表于 2015-5-12 15:08 | 显示全部楼层
有人说西南交大是热门,报川大的今年也说是热门,啊。。。好纠结,压力好大

0

主题

5

帖子

6

积分

王道论坛实习道友

Rank: 1

考研年份
2016
报考学校
华东理工
本科学校
合肥学院
注册时间
2015-7-4
最后登录
2015-9-6
发表于 2015-7-8 11:18 | 显示全部楼层
学长是今年考上的吗?

0

主题

22

帖子

10

积分

王道论坛实习道友

Rank: 1

考研年份
2016
报考学校
四川大学
本科学校
西南科大
注册时间
2015-6-3
最后登录
2016-10-12
QQ
发表于 2015-7-12 20:20 | 显示全部楼层
回复 10# kzp931104


    同纠结!

3

主题

23

帖子

186

积分

王道论坛初级道友

Rank: 2

考研年份
2016
报考学校
安徽大学
本科学校
安徽理工
注册时间
2014-10-21
最后登录
2015-9-17
发表于 2015-7-30 21:41 | 显示全部楼层
回复 1# tomkeruse

lz棒

1

主题

31

帖子

10

积分

王道论坛实习道友

Rank: 1

考研年份
2016
报考学校
电子科大
本科学校
湖北工大
注册时间
2015-5-1
最后登录
2016-12-25
发表于 2016-2-26 11:42 | 显示全部楼层
2016可以调剂到西南交通大学吗?另外求告知西南交通大学的qq群

1

主题

12

帖子

8

积分

王道论坛实习道友

Rank: 1

考研年份
2017
报考学校
西安电子
本科学校
中原工学院
注册时间
2015-11-2
最后登录
2016-10-14
发表于 2016-8-27 20:38 | 显示全部楼层
学长,17考研求联系。
2863855230

0

主题

1

帖子

0

积分

王道论坛新道友

考研年份
2017
报考学校
中南
本科学校
湖南科技大学
注册时间
2016-4-26
最后登录
2017-4-17
发表于 2017-4-17 15:36 | 显示全部楼层
这帖子删了吧 西南交大现在已经越来越难考了 2017年就是例子
您需要登录后才可以回帖 登录 | 注册

本版积分规则

王道图书2018预定

Archiver|手机版|小黑屋|王道论坛 ( 浙ICP备08017232号 ) | | 湘公网安备 43011102000392号

GMT+8, 2017-12-16 20:44 , Processed in 0.082310 second(s), 31 queries.

Powered by Discuz!

© 2008-2016 CSKAOYAN.COM

快速回复 返回顶部 返回列表