2017年苏州大学数据结构与操作系统考研试题真题

复习（一）一、选择题1．下面关于线性表的叙述错误的是（D）。

A、线性表采用顺序存储必须占用一片连续的存储空间B、线性表采用链式存储不必占用一片连续的存储空间C、线性表采用链式存储便于插入和删除操作的实现D、线性表采用顺序存储便于插入和删除操作的实现2．设哈夫曼树中的叶子结点总数为m，若用二叉链表作为存储结构，则该哈夫曼树中总共有（B ）个空指针域。

A、 2m-1B、 2mC、 2m+1D、 4m3．设顺序循环队列Q[0：M-1]的头指针和尾指针分别为F和R，头指针F总是指向队头元素的前一位置，尾指针R总是指向队尾元素的当前位置，则该循环队列中的元素个数为（C）。

A、 R-FB、 F-RC、(R-F+M)％MD、(F-R+M)％M4．设某棵二叉树的中序遍历序列为ABCD，前序遍历序列为CABD，则后序遍历该二叉树得到序列为（A）。

A、 BADCB、 BCDAC、 CDABD、CBDA5．设某完全无向图中有n个顶点，则该完全无向图中有（A ）条边。

A、 n(n-1)/2B、 n(n-1)C、 n2D、 n2-16．设某数据结构的二元组形式表示为A=(D，R)，D={01，02，03，04，05，06，07，08，09}，R={r}，r={<01，02>，<01，03>，<01，04>，<02，05>，<02，06>，<03，07>，<03，08>，<03，09>}，则数据结构A是（B ）。

A、线性结构B、树型结构C、物理结构D、图型结构7．下面程序的时间复杂为（B）for（i=1，s=0；i<=n；i++）{t=1；for(j=1；j<=i；j++) t=t*j；s=s+t；}A、 O(n)B、 O(n2)C、 O(n3)D、 O(n4)8．设指针变量p指向单链表中结点A，若删除单链表中结点A，则需要修改指针的操作序列为（A ）。

苏州大学2014年硕士研究生入学考试初试试题科目代码：872 科目名称：数据结构与操作系统满分：150分注意：①认真阅读答题纸上的注意事项；②所有答案必须写在答题纸上；③本试题纸须同答题纸一并交回。

一、数据结构部分注意：算法可以用类C、类C++、类JAVA或类PASCAL等语言编写，并请写出类型说明。

1.判断，若错，改正。

15分(1) 在一个图中，所有顶点度数之和等于所有边的总数。

(2) 快排在被排序的数据已经基本有序的情况下最易发挥长处。

(3) 求子串的定位操作成为串的模式匹配。

2.Dijkstra用途，思想，验证其正确性，及图的数据结构。

3.将数的质因数分解并按递减顺序写成一个有序单链表。

如：2100->7.5.5.3.2.24.二叉链的二叉树，递归，验证是否严格二叉。

（无度为1的结点）5.顺序表，整数，长为n，尽可能高效求得第n/4个元素。

二、操作系统部分6、判断，若错，改正。

15分(1)任何操作系统中，系统资源分配最小单位为线程。

(2)死锁的进程必然至少一个互斥资源。

(3)虚拟存储器大小为内外存之和。

(4)文件访问效率有两个，物理结构和逻辑结构。

(5)spooling可以减少进程上下文切换次数。

7、从文件逻辑结构，物理结构和文件目录三方面入手，举实例说明如何提高存取速度（还是效率？就那个意思！）。

8、资源共享，创建和结束三方面说明进程和它创建的子进程，进程和他创建的线程之间的关系。

9、分页存储（二级页表），页表存于内存：(1) 一次访问内存200NS，求访问一个内存单元多少时间。

(2) 若三级页表，多少时间？(3) 引入联想寄存器，90%的页表项可在快表中命中，则一次访存时间？（假设一次快表10NS）(4) 若虚拟存储，页面命中率80%，缺页处理5万NS/次，则一个内存单元多少时间？(5) 采用虚拟存储，命中率80%，缺页时有10%需要置换(不用置换的缺页处理4万NS/次，否则8万NS/次)，同问。

数据结构试卷试1一、解释下列术语（每小题4分，共20分）1. 头指针2. 二叉排序树的定义3. 头结点4. 数据的逻辑结构5. 排序方法的稳定性二、选择填空（每小题2分，共20分）（在每小题的4 个备选答案中，选出一个正确的答案，多选少选均不得分）1. 在一个长度为n的顺序表中，在第i个元素（1≤i≤n+1）之前插入一个新元素时顺向后移动( ) 个元素A.n-iB. n-i+1C. n-i-1D.i2. 某个栈的输入序列为1，2，3，4，下面的四个序列中( )不可能是它的输出序列A.1,2,3,4B.2,3,4,1C. 4,3,2,1D.3,4, 1,23. 对二叉排序进行( )遍历可以得到结点的排序序列A.前序B.中序C. 后序D.按层次4．有64个结点的完全二叉树的深度为（）。

A 8B 7C 6D 55．折半查找法的时间复杂度是( )A.(n2)B.O(n)C. O(n㏒n)D. O(㏒n)6．A(1:5,1:6)的每个元素占5个单元，将其按行优先次序储存在起始地址为1000的连续的内存单元中，则元素A[5，5]的地址为（）。

A 1140B 1145C 1120D 11257. 有n个叶子结点的哈夫曼树的结点总数为（）。

A 不确定B 2nC 2n+1D 2n-18. 已知某二叉树的后序遍历序列是dabec, 中序遍历序列是debac, 则它的前遍历序列是（）。

A acbedB decabC deabcD cedba9．若循环队列用数组A(0:m-1)存放其元素值，已知其头、尾指针分别是f和r,则当前队列中的元素个数是（）。

A (r-f+m)mod mB r-f+1C r-f-1D r-f10. 一个二叉树的先序序列和后序序列正好相反，则该二叉树一定是（）的二叉树（树中结点个数大于1）。

A 空或只有一个结点B 高度等于其结点数C 任一结点无左孩子 D任一结点无右孩子三，判断题（每小题2分，对的打√，错的打×，共10分）1．若图G的最小生成树不唯一，则G的边数一定多于n-1，并且权值最小的边有多条（其中n为G的顶点数）。

2017考研计算机真题及答案：篇一：2017考研计算机专业考研备考资料2017考研计算机专业考研备考资料计算机专业已成为当前考研最热门专业之一，纵观近几年报名录取情况会发现：报考人数在逐年增加，竞争压力在持续升温，而录取概率却非常小。

今天小编为同学们推荐一些优质权威的计算机专业课复习资料，以帮助同学们提升复习效果。

考试内容计算机科学与技术学科的初试科目调整后为4门：政治理论（100分）、外国语（100分）、数学一（150）和计算机学科专业基础综合（150分）。

计算机学科专业基础综合科目，主要考查考生掌握相关基础知识、基本理论和分析问题解决问题的能力。

考试实行联合命题，考试内容包括：数据结构、计算机组成原理、操作系统和计算机网络。

各阶段资料推荐第一阶段（3～7月）这一阶段为基础复习阶段，复习资料应该选择和大纲吻合的教材以及配套的习题。

数据结构可以选用严蔚敏主编、清华大学出版社出版的C语言版的《数据结构》，习题建议选用李春葆主编、清华大学出版社出版的《数据结构习题与解析》。

计算机组成原理有两个版本的教材可供选择：一个是白中英主编、科学出版社出版的《计算机组织与结构》（最新版是第4版）及配套习题；另一个是唐朔飞主编、高等教育出版社出版的《计算机组成原理》及配套习题。

操作系统建议选用：汤子瀛主编、西安电子科技大学出版社出版的《计算机操作系统》，配套习题可以选用李春葆主编、清华大学出版社出版的《操作系统习题与解析》。

计算机网络选用谢希仁主编、电子工业出版社出版的《计算机网络》（最新版是第5版）及配套习题。

在复习书本知识的基础上，同学们可以配合网络课程学习。

该阶段我们推荐考试点网络免费课程： 2017年考研计算机专业备考指南。

该节课对同学们帮助非常大，尤其是一战学子。

第二阶段（７～10月）第二阶段为强化复习、重点深入阶段，时间一般是7～10月份。

该阶段可以选用的教材有：高等教育出版社出版的的《计算机专业基础综合考试大纲解析》、复旦大学出版社出版的《计算机专业基础综合考试复习指南》。

苏州大学政治与公共管理学院哲学概论2007公共管理基础理论2007（A卷），2007（B卷）公共部门管理（行政管理）2007（A卷）公共部门管理（社会医学与卫生事业理论）2007管理学（行政管理专业）2000，2001，2002，2003（A卷），2003（B卷），管理学原理（行政管理专业）2004（A卷）行政法学与管理学原理2006管理学与行政法学2005行政管理学1998，2000，2001，2002，2003（A卷），2003（B卷），2004（B卷），2005，2006管理学原理（行政管理学专业）2000——2004行政管理学2003年复试试卷（含行政法学、政治学原理）教育学专业基础综合（全国统考试卷）2007教育学2000——2005马克思主义基本原理2007马克思主义哲学原著2005——2006马克思主义哲学经典著作2002马克思主义哲学原理2002马克思主义哲学1999——2000西方哲学史1999——2000，2002，2004——2006现代西方哲学2006西方现代美学与哲学2005中国哲学原著解读2006伦理学原理1999——2000辩证唯物主义原理1999——2000历史唯物主义原理1999——2000政治学原理1998，2000，2004——2007西方政治思想史1998，2000，2004，2006中西政治思想史2007思想政治教育学2004，2006——2007邓小平理论2000法学院专业基础课（法学各专业）2007（A卷），2007（B卷）基础课（法学）2000——2001基础课(国际法专业)2002基础课（国际法专业）（含法理学、民法学、经济法）2004——2005基础课（诉讼法学专业）（含法理学、民法学、刑法学）2003——2006基础课二（法理学、民法学、经济法）2006（A卷）专业课（国际法学专业）2007（A卷），2007（B卷）专业课B（法律史专业）2007（A卷），2007（B卷）专业课C（宪法学与行政法学专业）2007（A卷），2007（B卷）专业课D（刑法学专业）2007（A卷）专业课E（民商法学专业）2007（A卷）中国法律史2006（A卷）西方法律思想史2006（B卷）行政法学（含行政诉讼法学）2006（A卷）经济法学专业（经济法学）2007（A卷），2007（B卷）中国刑法学2002国际法学与国际私法学2005（B卷），2006（B卷）国际公法和国际私法2000——2002法理学1999——2002，2004——2006国际经济法学2000——2002民法学2000——2002，2004——2006民商法学2002民事诉讼法学2002刑事诉讼法学与民事诉讼法学2003——2006法理学与经济犯罪学2004——2006（A卷）刑法总论与刑法分则2004——2006（A卷）行政法学与行政诉讼法学2005行政法学（含行政诉讼法学）2006（A卷）法理学与宪法学2006（A卷）中国刑事诉讼法2002宪法学2000——2002行政法学2000，2002综合卷（法学、法学理论专业）1999——2001综合卷（理论法学）2002综合卷(行政法专业)2002综合课(民事诉讼法专业)2002法学综合（国经方向）2002综合法学2000，2002体育学院体育学专业基础综合2007（A卷），2007（B卷）运动生理学2002——2005人体生理学2005运动训练学2002，2004——2005运动解剖学2005体育概论2003——2005体育社会学2005教育学院教育学专业基础综合（全国统考试卷）2007——2008教育学2000——2005教学论2000——2001中外教育史2000——2005高等教育2000——2001教育心理学2000——2002，2004教育心理学（课程与教学论专业）2005教育心理学（含发展心理学）（发展与教育心理学专业）2005——2006心理学研究方法2007（A卷），2008（A卷）普通心理学（含实验心理学）2000——2007心理统计与测量2003——2004心理统计2002管理心理学2000——2002公共管理基础理论2007（A卷），2007（B卷）教育经济学2005教育管理学2000——2002，2005文学院文学基础综合2007（A卷），2007（B卷），2008（A卷）评论写作（1）（美学、文艺学、中国古代文学、中国现当代文学、比较文学与世界文学、戏剧戏曲学专业）2007（A卷），2008（A卷）评论写作（戏剧戏曲专业）2004评论写作（中国古代文学专业）2003评论写作（2）（中国现当代文学专业）2000，2002评论写作（2）（新闻学、传播学专业）2007（A卷），2007（B卷）评论写作（3）（文艺学专业）2002评论写作（5）（新闻学、传播学专业）1999——2002新闻传播基础2007（B卷）新闻传播理论2004——2006新闻学基础1999——2006大众传播理论1999——2006古代汉语2001——2008现代汉语2002——2008语言学概论2002，2005（复试）中外文学与比较文学综合考试2005中外文学综合知识2002中国现当代文学史2000，2003——2004，2006中国现代文学史2002文学理论2003——2006文学概论2002中国古代文学2001——2006中国文论2003——2006中国文学史2002外国文学史2002——2006文艺理论2000，2002，2003比较文学原理2002——2006美学原理2004——2005中西美学史2004——2005，2007戏剧理论基础2005，2007中国戏剧2005中国戏剧（古典戏曲或现代戏剧）2006中国现代戏剧史2004语文教学论2004——2005教学论2000——2001教育学专业基础综合（全国统考试卷）2007——2008教育学2000——2005社会学院社会学原理2002——2005，2006（A卷），2007（A卷），2007（B卷）社会研究方法2002——2005，2006（A卷），2007（A卷），2007（B卷）社会调查方法2002中国历史文选2004——2005中国通史2004历史学专业基础（全国统考试卷）2007公共管理基础理论2007（A卷），2007（B卷）公共部门管理（社会保障学）2007（A卷），2007（B卷）管理学原理（旅游管理）2007管理学原理A（社会保障专业）2004（A卷），2004（B卷），2005（A卷），2006（B卷）西方经济学（社会保障专业）2004（A卷），2004（B卷），2005（A卷），2006（A卷）信息检索2007（A卷），2007（B卷）信息资源管理2007（A卷），2007（B卷）档案管理学2004——2005档案学原理2004——2005外国语学院二外法语2001——2002，2004——2008二外日语2000，2002——2008二外俄语2005——2006基础英语1997，1999——2008（1997有答案）翻译与写作1997，2003——2008（1997有答案）英汉双语翻译1999——2002英文写作1999——2002英美文学1997（1997有答案）英语语言学1997（1997有答案）二外英语2005——2007基础俄语2004——2007现代俄语2004——2005综合俄语2006——2007日语写作与翻译2008日语翻译与写作2007综合日语2007——2008教育学专业基础综合（全国统考试卷）2007——2008教育学2000——2005数学科学学院高等代数2000——2002，2004——2007数学分析2000——2002，2004——2007（2004——2005有答案）数学分析与高等代数2003（A卷），2003（B卷）教育学专业基础综合（全国统考试卷）2007教育学2000——2005物理科学与技术学院信号系统与数字逻辑2003——2007数字电子技术基础1999——2002信号与线性系统1997——2002自动控制原理2004——2007（其中2005试卷共3页，缺P3）高等数学2003——2007普通物理2004——2007教育学专业基础综合（全国统考试卷）2007教育学2000——2005信息光学工程、现代光学技术研究所信号系统与数字逻辑2003——2007数字电子技术基础1999——2002信号与线性系统1997——2002自动控制原理2004——2007（其中2005试卷共3页，缺P3）普通物理2004——2007化学化工学院有机化学和仪器分析2007（A卷）有机化学1999，2001，2003，2004，2005（第1种，代码为456），2005（第2种，代码为360），2006有机化学(1)2001——2002化学原理2007（A卷）化学（2）2004——2005化学（3）2003——2006化学四（含无机、分析）2005分析化学2003分析化学（含定量分析、仪器分析）2005无机化学(1)2001——2002无机化学2003——2005物理化学2000——2002，2004——2005高分子化学1999，2003——2007教育学专业基础综合（全国统考试卷）2007教育学2000——2005计算机科学与技术学院数据结构与操作系统2003——2007数据结构与编译原理2005操作系统原理1998——2002数据结构及程序设计1998——2002数据库2003年复试电子信息学院半导体物理与集成电路设计原理2006——2007半导体物理2004信号系统与数字逻辑2003——2007数字电子技术基础1999——2002信号与线性系统1997——2002自动控制原理2004——2007（其中2005试卷共3页，缺P3）机电工程学院理论力学2000——2001，2004——2007自动控制原理2004——2007（其中2005试卷共3页，缺P3）电子技术基础2007材料工程学院材料结构与性能（含高分子物理、无机非金属材料概论，两者任选一门考）2007 专业课程考试（高分子物理或无机非金属材料概论）2005纺织材料学1999，2004——2007纺织工艺学1999服装材料学2004——2005高分子材料成形工艺学1999有机化学和仪器分析2007（A卷）化学原理2007（A卷）有机化学1999，2001，2003，2004，2005（第1种，代码为456），2005（第2种，代码为360），2006有机化学(1)2001——2002高分子化学1999，2003——2005化学（2）2004——2005化学（3）2003——2006化学四（含无机、分析）2005自动控制原理2004——2007（其中2005试卷共3页，缺P3）商学院管理学（企业管理专业）2004——2006管理学（会计学、企业管理、农业经济管理专业）2007（A卷），2007（B卷）管理学原理（企业管理专业）2002——2003微观与宏观经济学2007（A卷），2007（B卷）经济学原理2004——2005经济学（含西方经济学）2002经济学A2002世界经济1998（B卷），1999（A卷），1999（B卷），2000 世界经济理论2003——2005国际经济合作1999——2000财政学2002——2005金融学联考2002——2007（2002——2005有答案）会计学（含财务管理）2002——2005区域经济学2005企业管理专业复试试题2003艺术学院绘画基础（色彩画）2007绘画基础（美术学专业）2003——2006（设计系）色彩2003——2005艺术史2007设计艺术史2005美术史2003——2005医学院基础医学系病理学1994——2005流行病学2005儿科学2002妇产科学2001内科学2002生理B2002生理学2003——2008生物化学2008生物化学（生）2003——2007生物化学B 2001——2002，2004——2005药理学2002药学综合2002，2007肿瘤学2002生命科学学院生物化学2008生物化学（生）2003——2007生物化学B 2001——2002，2004——2005细胞生物学2004——2007遗传学2005动物生理学2007教育学专业基础综合（全国统考试卷）2007——2008 教育学2000——2005放射医学与公共卫生病理学1994——2005预防综合2007流行病学2005儿科学2002妇产科学2001内科学2002生理B2002生理学2003——2008生物化学2008生物化学（生）2003——2007生物化学B 2001——2002，2004——2005药理学2002药学综合2002，2007肿瘤学2002普通物理2004——2007医学院临床医学儿科系病理学1994——2005流行病学2005儿科学2002妇产科学2001内科学2002生理B2002生理学2003——2008生物化学2008生物化学（生）2003——2007生物化学B 2001——2002，2004——2005药理学2002药学综合2002，2007肿瘤学2002医学院临床医学系病理学1994——2005流行病学2005儿科学2002妇产科学2001内科学2002生理B2002生理学2003——2008生物化学（生）2003——2007生物化学B 2001——2002，2004——2005药理学2002药学综合2002，2007肿瘤学2002药学院药学综合2002，2007药理学2002生物化学2008生物化学（生）2003——2007生物化学B 2001——2002，2004——2005化学（2）2004——2005化学（3）2003——2006化学四（含无机、分析）2005有机化学和仪器分析2007（A卷）化学原理2007（A卷）有机化学1999，2001，2003，2004，2005（第1种，代码为456），2005（第2种，代码为360），2006有机化学(1)2001——2002城市科学学院生物化学2008生物化学（生）2003——2007生物化学B 2001——2002，2004——2005。

2017《数据结构》期末考试试题及答案2017《数据结构》期末考试试题及答案《数据结构》期末考试试题及答案1 (2)试题1答案 (7)《数据结构》期末考试试题及答案2 (9)试题2答案 (14)《数据结构》期末考试试题及答案3 (16)试题3答案 (21)《数据结构》期末考试试题及答案1⼀、单选题（每题 2 分，共20分）1.栈和队列的共同特点是( )。

A.只允许在端点处插⼊和删除元素B.都是先进后出C.都是先进先出D.没有共同点2.⽤链接⽅式存储的队列，在进⾏插⼊运算时( ).A. 仅修改头指针B. 头、尾指针都要修改C. 仅修改尾指针D.头、尾指针可能都要修改3.以下数据结构中哪⼀个是⾮线性结构？( )A. 队列B. 栈C. 线性表D. ⼆叉树4.设有⼀个⼆维数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每个元素占⼀个空间，问A[3][3](10)存放在什么位置？脚注(10)表⽰⽤10进制表⽰。

A．688 B．678 C．692 D．6965.树最适合⽤来表⽰( )。

A.有序数据元素B.⽆序数据元素C.元素之间具有分⽀层次关系的数据D.元素之间⽆联系的数据6.⼆叉树的第k层的结点数最多为( ).A．2k-1 B.2K+1 C.2K-1 D. 2k-17.若有18个元素的有序表存放在⼀维数组A[19]中，第⼀个元素放A[1]中，现进⾏⼆分查找，则查找A［3］的⽐较序列的下标依次为( )A. 1，2，3B. 9，5，2，3C. 9，5，3D. 9，4，2，38.对n个记录的⽂件进⾏快速排序，所需要的辅助存储空间⼤致为A. O（1）B. O（n）C. O（1og2n）D. O（n2）9.对于线性表（7，34，55，25，64，46，20，10）进⾏散列存储时，若选⽤H（K）=K %9作为散列函数，则散列地址为1的元素有（）个，A．1 B．2 C．3 D．410.设有6个结点的⽆向图，该图⾄少应有( )条边才能确保是⼀个连通图。

数据结构试题及答案(10套最新)数据结构试题及答案(10套最新)第一套试题：问题一：什么是数据结构？数据结构的作用是什么？回答：数据结构是一种组织和存储数据的方式，它关注数据元素之间的关系以及对数据元素的操作。

数据结构的作用包括提供高效的数据存储和访问方式，减少资源消耗，简化问题的解决方法，提高算法的性能和程序的可读性。

问题二：请列举几种常见的线性数据结构，并简要介绍它们的特点。

回答：常见的线性数据结构包括数组、链表和栈。

数组是一种连续存储数据元素的结构，具有随机访问的特点；链表是一种通过指针相连的数据元素，可以灵活地插入和删除元素；栈是一种遵循先进后出原则的数据结构，常用于解决递归问题。

问题三：请说明二叉树的定义及其性质。

回答：二叉树是一种特殊的树形数据结构，每个节点最多有两个子节点。

二叉树具有以下性质：每个节点最多有两个子节点，分别称为左子节点和右子节点；左子树和右子树都是二叉树；二叉树的节点个数为n，边的个数为n-1。

问题四：在数组中查找一个元素的时间复杂度是多少？为什么？回答：在数组中查找一个元素的时间复杂度是O(n)，其中n是数组的长度。

因为在数组中查找元素需要按照索引一个一个比较，最坏情况下需要比较n次才能找到目标元素。

问题五：请解释堆排序算法的原理及时间复杂度。

回答：堆排序算法利用堆这种数据结构进行排序。

首先将待排序的元素构建成一个大顶堆，然后将堆顶元素与最后一个元素交换，继续调整堆，再取出堆顶元素与倒数第二个元素交换，依次执行，最后得到从小到大排序的序列。

堆排序的时间复杂度为O(nlogn)。

第二套试题：问题一：请解释图的邻接矩阵和邻接表表示法。

回答：图的邻接矩阵表示法是使用二维数组来表示图的连接关系，数组中的元素表示相应节点之间的边的关系。

邻接表表示法使用链表来表示图的连接关系，链表中的元素表示相邻节点之间的边的关系。

问题二：请说明深度优先搜索算法的原理及其应用。

回答：深度优先搜索（DFS）算法是一种遍历或搜索图的算法，其原理是从起始节点开始，依次深入到尽可能远的节点，直到无法继续深入为止，然后回溯到上一个节点，再继续深入其他未访问过的节点。

第一章概论一、选择题1、研究数据结构就是研究（D ）。

A. 数据的逻辑结构B. 数据的存储结构C. 数据的逻辑结构和存储结构D. 数据的逻辑结构、存储结构及其基本操作2、算法分析的两个主要方面是（ A ）。

A. 空间复杂度和时间复杂度B. 正确性和简单性C. 可读性和文档性D. 数据复杂性和程序复杂性3、具有线性结构的数据结构是（ D ）。

A. 图B. 树C. 广义表D. 栈4、计算机中的算法指的是解决某一个问题的有限运算序列，它必须具备输入、输出、（B ）等5个特性。

A. 可执行性、可移植性和可扩充性B. 可执行性、有穷性和确定性C. 确定性、有穷性和稳定性D. 易读性、稳定性和确定性5、下面程序段的时间复杂度是（ C ）。

for(i=0;i<m;i++)for(j=0;j<n;j++)a[i][j]=i*j;A. O(m2)B. O(n2)C. O(m*n)D. O(m+n)6、算法是（D ）。

A. 计算机程序B. 解决问题的计算方法C. 排序算法D. 解决问题的有限运算序列7、某算法的语句执行频度为（3n+nlog 2n+n 2+8）,其时间复杂度表示（ C ）。

A. O(n)B. O(nlog 2n)C. O(n 2)D. O(log 2n)8、下面程序段的时间复杂度为（ C ）。

i=1; while(i<=n)i=i*3;A. O(n)B. O(3n)C. O(log 3n)D. O(n 3)9、数据结构是一门研究非数值计算的程序设计问题中计算机的数据元素以及它们之间的（ B ）和运算等的学科。

A. 结构B. 关系C. 运算D. 算法10、下面程序段的时间复杂度是（A ）。

i=s=0;while(s<n){ i++;s+=i; 根号（n ）}A. O(n)B. O(n 2)C. O(log 2n)D. O(n 3)11、抽象数据类型的三个组成部分分别为（ A ）。

苏州大学操作系统原理课程试卷（一）答案共4页一、填空题（20分，每空1分）1、进程通信的常用方式有直接通信和间接通信等。

2、如果P(S1)和P(S2)两个操作在一起，那么P操作的顺序至关重要，一个同步P操作与一个互斥P操作在一起时同步P操作在互斥P操作前。

而两个V操作的次序无关紧要。

3、P(S)：表示申请一个资源；V(S)表示释放一个资源。

信号量的初值应该大于等于0 。

4、在请求式分页系统中，页框的分配中有一种方式称为固定分配。

固定分配有两种不同的方式，分别是平均分配和按比率分配。

5、在请求式分页存储管理系统中，不能在计算机中实现的页面淘汰算法是最佳算法，选择淘汰不再使用或最远的将来才使用的页的算法是先进先出算法，选择淘汰在主存驻留时间最长的页的算法是最近最少使用。

6、将作业地址空间中的逻辑地址转换为主存中的物理地址的过程称为地址转换。

7、访问磁盘时间由三部分组成寻道时间、旋转延迟时间和传输时间。

8、I/O设备的控制方式有轮询、中断和DMA等。

二、判断题（20分，每题4分，请说明正确与否的理由）1、分布式系统就是紧偶合系统。

错。

分布式系统是松散偶合系统。

2、在一个只有单个CPU的计算机中，进程不能并行操作。

错。

一个进程在利用CPU运行，另一个进程可以同时进行I/O操作，它们是并行的。

3、线程可以分为内核级（Kernel Thread）和用户级（User Thread）两种，操作系统不可以直接调度用户级的线程。

对。

4、有m个进程的操作系统出现死锁时, 死锁进程的个数为1<k≤m。

对。

5、在虚存系统中, 只要磁盘空间无限大, 作业就能拥有任意大的编址空间。

错。

作业的编制空间是由计算机的字长决定的。

三、简答题（20分，每题5分）1、为什么要在设备管理种引入缓冲技术？答：1）解决设备间速度的不匹配；2）减少中断频率；3）提高并行性。

2、CPU调度可能发生的时机有哪些？答：CPU调度可能发生在当一个进程:●从运行转到等待●运行转到就绪●从等待转到就绪●终止运行3、同步机构应遵循哪些原则？答：使用互斥区的原则：有空让进：当无进程在互斥区时，任何有权使用互斥区的进程可进入。

苏州大学计算机学院数据结构与操作系统考研复试指南本文包含：具有苏大特色的《数据结构与操作系统》（872）备考指南、苏大特色的复试，分量绝对足。

本文不包含：不包含政治英语数学等内容。

一、简单介绍本人2013届考研，我是到大三下了才开始有考研的想法的，被两个关系很好的老师给“忽悠”的。

本科是一所内地普通的二本院校，一般来讲考苏大的本科背景都差不多。

我本科阶段的成绩并不好，挂科也有，60徘徊的科目也不少。

英语六级过了但是考了三次，软考过了软设也考了三次，然后就没有了，说这些主要是为了让学弟学妹们有所比较，说实在的讲到底考研最重要的还是坚持，很多的同学就是不能坚持，甚至考到最后了弃考的。

二、《数据结构与操作系统》（872）备考指南（一）时间安排我当时是最后两个月了才开始看的，并且只在下午看。

我的基础很一般，专业课的复习既要重视因为分数多好拿分，复试的同学除了跨专业的几乎没有低于120的，我考了136，所以说要重视。

同时又要轻视因为实在是很简单的，比起408难度降低了很多。

要记得东西稍微有点多，所以可以靠后点开始复习。

（二）全部书籍资料准备0．请忽略苏大所谓的参考教程，特别是那本板砖操作系统，如果是对付考研绝对没必要看。

1．我没有买任何专业课方面的书只在学校图书馆借了两本书《计算机专业考研辅导丛书：数据结构联考辅导教程(2010版)》、《计算机专业考研辅导丛书:计算机操作系统联考辅导教程(2011版)》，这两本书用来对付苏大的872非常好，并不要求最新的，要知道苏大的考纲都很多年没改了，试卷结构题型也比较稳定。

相信你们学校图书馆也肯定有借。

2．打印一份苏大872考纲，只要打印《数据结构与操作系统》的就可以了。

3．打印苏大99-2010年的872真题（某些年份可能缺失），论坛就有得下。

（三）复习过程1．首先要看一遍苏大的考纲和真题，了解苏大考什么、怎么考。

考纲更重要的作用是看不考什么，例如树的遍历，大纲上是没有层次遍历的，这个一直也没考过。

数据结构考研真题及其答案数据结构是计算机科学与技术专业考研中的重要科目之一，它对于培养学生的程序设计和算法分析能力具有关键作用。

以下将为大家呈现一些典型的数据结构考研真题，并提供详细的答案解析。

一、选择题1、若一个栈的输入序列为 1, 2, 3, 4, 5，不可能得到的输出序列是（）A 2, 3, 4, 1, 5B 5, 4, 3, 2, 1C 1, 5, 4, 3, 2D 3, 4, 2, 5, 1答案：C解析：栈的特点是“后进先出”。

对于选项 C，先输出 1，意味着 2、3、4、5 都已入栈，此时栈顶元素为 5，不可能接着输出 5 之后就输出4。

2、已知一棵二叉树的先序遍历序列为 ABCDEFG，中序遍历序列为 CBDAEGF，则其后序遍历序列为（）A CDBAFGEB CDBGFEAC CDBAGFED BCDAFGE答案：B解析：先根据先序和中序遍历序列构建二叉树。

先序遍历中第一个节点 A 为根节点，在中序遍历中找到 A，其左边的 CBD 为左子树，右边的 EGF 为右子树。

同样的方法确定左子树和右子树的结构。

然后按照“左子树右子树根节点”的顺序得到后序遍历序列 CDBGFEA。

3、对于一个具有 n 个顶点的无向图，若采用邻接矩阵表示，则该矩阵的非零元素个数为（）A n(n 1) ／ 2B n(n ＋ 1) ／ 2C n(n 1)D n(n ＋ 1)答案：A解析：无向图的邻接矩阵是对称的。

对于顶点 i 和 j（i ≠ j），若它们之间有边，则矩阵中对应位置为 1，共有 n(n 1) ／ 2 对不同的顶点对，所以非零元素个数为 n(n 1) ／ 2 。

二、简答题1、简述冒泡排序的基本思想，并分析其时间复杂度和空间复杂度。

答案：冒泡排序的基本思想是通过相邻元素的两两比较和交换，将最大（或最小）的元素逐步“浮”到数组的一端。

时间复杂度：在最坏情况下，即数组完全逆序，需要进行 n 1 轮比较，每轮比较 n i 次（i 为轮数，从 1 到 n 1），所以总的比较次数为n(n 1) ／ 2，时间复杂度为 O(n^2)。

可编辑修改精选全文完整版第一章概论一、选择题1、研究数据结构就是研究（ D ）。

A. 数据的逻辑结构B. 数据的存储结构C. 数据的逻辑结构和存储结构D. 数据的逻辑结构、存储结构及其基本操作2、算法分析的两个主要方面是（ A ）。

A. 空间复杂度和时间复杂度B. 正确性和简单性C. 可读性和文档性D. 数据复杂性和程序复杂性3、具有线性结构的数据结构是（ D ）。

A. 图B. 树C. 广义表D. 栈4、计算机中的算法指的是解决某一个问题的有限运算序列.它必须具备输入、输出、（ B ）等5个特性。

A. 可执行性、可移植性和可扩充性B. 可执行性、有穷性和确定性C. 确定性、有穷性和稳定性D. 易读性、稳定性和确定性5、下面程序段的时间复杂度是（ C ）。

for(i=0;i<m;i++)for(j=0;j<n;j++)a[i][j]=i*j;A. O(m2)B. O(n2)C. O(m*n)D.O(m+n)6、算法是（ D ）。

A. 计算机程序B. 解决问题的计算方法C. 排序算法D. 解决问题的有限运算序列7、某算法的语句执行频度为（3n+nlog2n+n2+8）,其时间复杂度表示（ C ）。

A. O(n)B. O(nlog2n)C. O(n2)D.O(log2n)8、下面程序段的时间复杂度为（ C ）。

i=1;while(i<=n)i=i*3;A. O(n)B. O(3n)C. O(log3n)D. O(n3)9、数据结构是一门研究非数值计算的程序设计问题中计算机的数据元素以及它们之间的（）和运算等的学科。

A. 结构B. 关系C. 运算D. 算法10、下面程序段的时间复杂度是（A ）。

i=s=0;while(s<n){i++;s+=i;}A. O(n)B. O(n2)C. O(log2n)D. O(n3)11、抽象数据类型的三个组成部分分别为（ A）。

A. 数据对象、数据关系和基本操作B. 数据元素、逻辑结构和存储结构C. 数据项、数据元素和数据类型D. 数据元素、数据结构和数据类型12、通常从正确性、易读性、健壮性、高效性等4个方面评价算法的质量.以下解释错误的是（）。

一、数据结构部分1、选择题（1）一个运算次数为n*n+nlog2n+n+1的程序时间复杂度为多少A.O(n*n)B.O(nlog2n)C.O(n)D.O(1)（2）下列哪个算法适合求稀疏图的最小生成树A.PrimB.KruskalC.DijkstraD.Floyd（3）.......2、判断题(5个）（1）栈和队列是双端队列的特殊情况（2）树的子结点可以有任意多个，二叉树的孩子节点至多有两个，所有二叉树是树的特殊情况（3）一个带有头结点的单链表，结点数据类型为整形（1）编写算法将结点元素为负整数的放到链表前面，将结点元素为正整数的放到链表后面（2）对于上述问题用何种物理结构实现较好（4）对于一颗二叉树，打印从根节点到先序遍历下最后一个节点的路径（5）图用邻接表实现，打印从顶点i 到顶点j 的所有简单路径二、操作系统部分一、判断题(5个）（1）最早的gui 界面是在window 系统上二、操作计算题1. 一个可抢占的动态优先级调度算法，优先数大的优先级高（1）等待状态下，进程优先级以a 速度变化（2）运行状态下，进程优先级以b 速度变化2. 进程优先级变化不同，会成为不同的调度算法问：（1）a>b>0 时是什么调度算法（2）a< b< 0 时是什么调度算法3. 一个含有一百万条记录的文件，每个文件16kb 到到32kb 不等，每个物理块4kb（1）如何设计文件目录，目录文件如何实现（2）（3）设计文件的物理结构（4）基于上述设计，访问某个文件的某个字节信息，最多访问几次磁盘，最少访问几次4. 磁盘16 年第七题原题有一个计算机的虚存系统采用请求式分页机制。

其中，从内存读/写-个单元需要花费100ms。

该虚存系统由内存和硬盘组成，硬盘具有以下参数:转速7200RPM,磁盘块大小4KB,平均寻道时间5ms,传输率16b/s,控制开销为0.1ms。

请回答以下问题:(1) 假如缺页率为0,则该虚存系统的有效访问时间是多少?(2) 从硬盘读入或写出一个磁盘块的平均时间是多少?(3)如果缺页率为1%，缺页时页面被修改的比例是20%，不考虑缺页时的系统开销，则该虚存系统的有效访问时间是多少?5. 2016pv 操作题稍作修改:有四个进程S1、S2、R1 和R2，其中S1、S2 向缓冲区BUFF 发送消息，R1 和R2 从缓冲区BUFF 接收消息。