武汉理工大学数据结构2018复习题

武汉理工大学教务处试题标准答案及评分标准用纸课程名称数据结构（A 卷）一、判断题（每小题2分，共20分）1、对2、对3、错4、对5、对6、对7、错8、对9、错10、对装二、选择题（每小题3分，共15分）1、B2、C3、B4、A5、D三、填空题（每小题3分，共21分）1、n-12、p->prior->next=p->next; p->next->prior=p->prior;3、334、中序5、n(n-1)6、(n+1)/2 或3(n+1)/47、CEF四、应用题（（每小题9分，共36分）1、(1)将数组中的负数调到非负数之前……………3分(2)只需对数组扫描一遍即可，故时间复杂度为O(n) ……………6分(3)最坏情况下：负数都位于非负数之后，需将负数与非负数对换，故记录的最大移动次数为n /2 ……………9分订2、中序遍历：LDR 后序遍历：LRD ……………2分由中序遍历和后序遍历一致，则应该是LD，任一个结点没有右孩子……………5分………………………9分线3、32%7=4，13%7=6，49%7=0，55%7=6，22%7=1，38%7=3，21%7=0 ……………2分哈希表为：495522383221130123456……………5分查找32，13，49，38需比较一次，查找22需比较两次，查找55需比较3次，查找21需比较6次……………8分故平均查找长度为：（1*4+2*1+3*1+6*1）/7=15/7 ……………9分4、排序算法主要有简单排序、快速排序、堆排序、归并排序、基数排序。

…………1分(1)从平均性能而言，快速排序最佳，其所需时间最省，但快速排序在最坏情况下的时间性能不如堆排序和归并排序，在n较大时，归并排序所需时间较堆排序省，但它所需的辅助存储量最多。

……………3分(2)“简单排序”包括除希尔排序之外的所有插入排序，起泡排序和简单排序，其中直接插入排序最简单，当序列中的记录“基本有序”或n较小时，它是最佳排序方法，因此常将它和其他的排序方法，诸如快速排序、归并排序等结合在一起使用。

武汉理工大学研招办经济学院西方经济学（含微观、宏观经济学）2007——2009经济学（含微观、宏观经济学）1997——2000，2002——2006（2002——2004，2006有答案）宏观经济学2004——2006（2004有答案）货币银行学2004——2007（2004有答案）国际贸易概论1998——2000，2002——2009（2002——2004有答案）国际金融学2002，2004——2009（2002，2004有答案）国际市场营销2002财政学2007产业经济学2002，2006——2009（2002有答案）电子商务概论2008——2009运输经济学2002——2009区域经济学2007人力资源管理2007管理学概论2004——2007（2004有答案）管理学原理1997——2000，2002——2009（2002——2004有答案）微机原理及应用1997——2000，2002——2007概率论与数理统计2001——2009复试科目：国际贸易学2003加试科目：国际金融学2003；国际市场营销学2003复试科目：产业经济学2003复试科目：数量经济学专业复试2003文法学院伦理学基础综合2007——2009伦理学原理2007——2009伦理学2002——2005民法学2007民商法学2008——2009民商法学综合2007——2009经济法学2002，2004——2009经济法综合2007——2009法学综合2002——2006知识产权2007知识产权法2002——2005法理学与知识产权法2004——2005社会心理学2002心理学2002思想政治教育学原理与方法2002——2009中国化的马克思主义2007——2009马克思主义基本原理及其发展2007——2009马克思主义基本原理2007马克思主义哲学原理2002——2009新闻传播专业综合考试（含广告学、编辑出版学）2004——2005出版发行综合2006——2009广告学综合2006——2009传播学原理2004——2009专业综合（教育学、运动训练学）2007体育教育综合（运动生理学、运动训练学）2008——2009运动生理学2007复试科目：综合复试2003；复试（科技法方向）2003加试科目：专业加试2003；加试（科技法方向）2003高等教育研究所教育学2002——2006，2008——2009教育管理学2002——2006，2008——2009复试科目：综合复试2003加试科目：教育学2003；教育心理学2003外国语学院二外日语2002——2009二外法语2002——2009二外德语2002——2009二外俄语2003——2009基础英语2001——2009（注：其中2002，2003，2005年的试卷名称为“综合英语”）英语语言学2001——2003，2006——2009（2001有答案）语言学及英美文学2004——2005英美文学2007——2009英语写作2002复试科目：外国语言学及应用语言学专业复试2003艺术与设计学院设计艺术学专业综合（含设计艺术史论、工业设计及其理论、环境艺术设计及其理论、视觉传播艺术设计、动画艺术设计及其理论、数字艺术设计及其理论）2008——2009美术学专业综合2008——2009艺术学专业综合2008——2009设计艺术学专业史论2003——2006，2008——2009 美术学专业史论2008——2009艺术学专业史论2008——2009音乐艺术研究专业综合（报考艺术管理方向）2009 视觉传播艺术设计基础2007速写与焦墨山水画2005速写与花卉白描2005——2006速写与人物写生画2005——2006速写与色彩人物写生2005，2007速写与泥塑人物写生2007速写与素描人物写生2005速写与水彩或水粉画创作2005速写与装饰画创作2005——2006中外美术史2002，2005，2007中国美术史专题2006中国画创作基础2007艺术美术专业基础2007美术史论2005——2007美术理论2004艺术学概论2007艺术设计史基础2004——2005，2007艺术史论基础2007艺术设计史论基础2003，2006艺术设计理论2002艺术设计史2002专业史论2007艺术设计学“专业设计基础”2002专业设计2002信息设计基础2004——2005动画创作基础2004——2006艺术管理专业基础2004——2005，2007艺术教育专业基础2007民艺专业基础2004 ——2005民间美术2007民间艺术设计及其原理2006设计基础理论与设计基础表达2002环境艺术设计基础2006——2007环境艺术设计与公共艺术创作专业基础2002动画与数字化设计艺术基础2007动画设计与数码设计基础2002系统设计及传播艺术基础2002系统设计及传播艺术理论2002工业设计理论2002工业设计基础2004——2007数码设计理论2002数码艺术设计基础2003中外建筑史2002动画创作理论2002动画创作基础2003环境艺术设计2002环境艺术设计基础2004——2005公共艺术创作与设计2002公共艺术设计基础2006卡通画创作2002专业设计（计算机艺术设计）2002专业设计（系统设计及传播艺术设计）2002环境艺术设计专业方向（环境艺术设计基础）2003设计艺术学专业工业设计方向设计基础2003平面设计基础2003——2005平面艺术设计基础2006现代美术与公共艺术设计基础2003设计管理2006设计基础（展示设计及理论方向）2006信息设计基础2006影视艺术设计基础2006音乐艺术研究2007复试科目：艺术与设计学院复试2003加试科目：艺术与设计学院加试2003理工学院材料力学1997——2000，2002——2009弹性力学2002——2004，2007理论力学2002——2009工程力学2004微机原理及应用1997——2000，2002——2007微机原理（即：微型计算机原理）1997——2000，2002——2004 岩石力学1997——2000，2002岩体力学2003——2007（注：2003年有两种）结构力学2002——2009量子力学2004——2009物理光学2002，2004——2009电磁场与电磁波2004电磁场理论2005——2009概率论与数理统计2001——2009数值分析2002，2004——2007高等代数2001——2009数学分析2002——2009常微分方程2002——2007线性代数2002普通物理2002——2009运筹学2002——2008（注：2002年试卷有两种）物理化学2002——2009有机化学2002——2007无机化学2002——2009化学原理2008——2009基础无机化学2007物理化学原理2007高等数学2007，2009高等数学（工）2002——2006，2008高等数学（二）2004高等数学（文）2003——2005复试科目：应用化学专业复试2003复试科目：应用数学专业复试2003复试科目：固体力学专业复试2003资源与环境工程学院物理化学2002——2009材料力学1997——2000，2002——2009岩石力学1997——2000，2002岩体力学2003——2007（注：2003年有两种）岩石力学与工程2004——2009矿山岩石力学2002无机化学2002——2009浮选2002固体废物处理工程2002水污染控制工程2002大气污染控制工程2002化工基础2002——2007化工原理2002——2009（注：2002年称“环境化工原理”）采矿学2002安全工程学2007——2009爆破工程2002——2009（注：2003年称“凿岩爆破”）流体力学2002——2004胶体化学2003——2009结晶矿物学2003——2006环境学概论2004——2009环境化学2004——2007环境流体力学2002，2005——2007环境工程微生物学2005——2006环境生物学2005——2007矿物加工工程专业复试科目：综合复试2003采矿工程专业复试科目：专业复试2003环境工程专业复试科目：环境工程专业复试2003；加试科目：环境工程专业加试2003材料科学与工程学院材料科学基础2002——2009普通物理2002——2009材料力学1997——2000，2002——2009医学综合一（含生物化学、无机化学）2008——2009医学综合二（含生物化学、高分子化学）2008医学综合三（含生物化学、组织学）2008——2009医学综合2002，2004细胞生物学2002——2007组织学2002——2007物理光学2002，2004——2009计算机在材料科学中的应用2007计算机在材料中的应用2004——2005工程材料2002——2007生物化学2002——2007物理化学2002——2009有机化学2002——2007无机化学2002——2009陶瓷工艺原理2002玻璃工艺原理2002复合材料工艺2002铸造合金及其熔炼2002塑性成型原理2002材料成型原理2003——2009焊接冶金2002金属热处理2002金属材料学2007固体物理2002——2009聚合物加工原理与工艺2002胶凝材料学2002无机非金属材料工学2002，2004——2009金属学及热处理2002硅酸盐物理化学2002高分子化学及物理2002高分子化学2003——2009金属学原理2002——2007材料物理与化学专业复试科目：综合复试2003；加试科目：物理化学2003；材料学院同等学历加试2003材料学专业复试科目：综合复试2003；加试科目：物理化学2003；材料学院同等学历加试2003材料加工工程专业复试科目：综合复试2003；加试科目：物理化学2003；材料学院同等学历加试2003生物医学工程专业复试科目：生物医学工程专业复试2003；加试科目：生物化学2003；组织学2003机电工程学院材料力学1997——2000，2002——2009机械原理1997——2000，2002——2009机械设计1997——2000，2002——2009控制工程基础2002——2009统计质量管理2005——2009传感器原理2003——2009传感检测技术2002——2003传感技术1997——2000传感与检测技术2002电子技术基础2002——2009微机原理及应用1997——2000，2002——2007人机工程学2002——2006机电工程学院2003年同等学历考研加试题（测试技术）机电工程学院2003年同等学历考研加试题（机械原理）机电工程学院2003年同等学力考研加试题（机械设计）机电工程学院2003级硕士研究生复试试题汽车工程学院材料力学1997——2000，2002——2009理论力学2002——2009汽车理论基础2002——2009发动机原理2002——2009摩托车理论与结构设计2002汽车运用工程2002——2009汽车运输工程2002——2003工程热力学2002——2008汽车运输学2003——2005，2007交通运输学2006汽车营销与策划2009汽车市场学2004——2008动力机械及工程专业复试科目：动力机械及工程复试2003；加试科目：发动机构造2003；发动机原理2003车辆工程专业复试科目：综合复试2003；加试科目：汽车构造2003；汽车理论2003载运工具运用工程专业复试科目：综合复试2003自动化学院电路1997——2000，2002——2009电工技术基础2002电工原理2003——2006控制理论基础2002自动控制原理1997——2000，2002——2009信号处理技术2002——2005（注：2002——2003年称“信号分析与处理”）传感技术1997——2000传感与检测技术2002传感检测技术2002——2003传感器原理2003——2009电机及拖动基础2001电力电子技术（一）2007电力电子技术2002——2006，2008——2009微机原理及接口技术2002——2009数字电路2003——2009逻辑设计2004——2006电力电子与电力传动专业复试科目：电力电子与电力传动专业复试2003检测技术与自动化装置专业复试科目：检测技术与自动化装置专业复试2003 控制理论与控制工程专业复试科目：控制理论与控制工程专业复试2003；加试科目：自动控制原理2003；微机原理及接口技术2003计算机科学与技术学院数据结构1997——2000，2002——2008操作系统1998——2000，2002——2008计算机组成原理2002——2007微机原理及应用1997——2000，2002——2007C语言2007微机原理（即：微型计算机原理）1997——2000，2002——2004离散数学2002——2006计算机网络1999——2000，2002软件工程2002——2006数据库原理2002编译原理2002计算机原理2002计算方法2003——2005复试科目：计算机应用技术、计算机软件与理论专业2003加试科目：微机原理及应用2003；数据库应用2003信息工程学院数据结构1997——2000，2002——2008信号与系统1999——2000，2002——2009信号与线性系统2002——2006物理光学2002，2004——2008光纤光学2007现代光学2006高频电路2002微机原理及应用1997——2000，2002——2007微机原理（即：微型计算机原理）1997——2000，2002——2004 脉冲与数字电路1999——2000，2002电子技术基础2002——2009高频电子线路1999——2000，2002微机原理及其通信接口2003——2009信号分析与处理2002——2008传感技术1997——2000电路1997——2000，2002——2009数字信号处理1999——2000，2002，2009土木工程与建筑学院材料力学1997——2000，2002——2009传热学2002——2007中外建筑史2002——2009建筑历史2004——2007建筑设计2002——2004，2008——2009建筑设计（1）2005——2007建筑设计（2）2005——2007规划设计2007——2008城市规划原理2003——2009建筑结构抗震设计2007抗震结构设计2004结构力学2002——2009工程项目管理2008——2009建筑施工与工程项目管理2003——2007建筑施工技术2002建筑工程经济与企业管理2002工程热力学2002——2009土质学与土力学2002——2007水分析化学2002——2005水分析与物理化学2006——2007水力学与水泵2002——2007水力学与水分析化学2008——2009土力学2002——2009建筑构造2002岩石力学1997——2000，2002岩体力学2003——2007（注：其中2003年有两种）钢筋混凝土结构2002，2006——2009混凝土结构原理2003钢筋砼结构2005土力学与基础工程2002结构动力学2002结构设计原理2002（第1种），2002（第2种），2005——2007桥梁工程2002给水工程2002排水工程2002路基路面工程2002，2005——2007工程地质学2004——2006美学2004建筑设计及其理论专业复试科目：建筑设计2003；建筑设计知识2003；加试科目：中外建筑史2003结构工程专业复试科目：结构工程2003；综合复试（建筑工程施工技术、建设工程项目管理方向）2003；加试科目：施工组织学2003；建筑经济与企业管理2003；结构力学2003；混凝土结构2003桥梁与隧道工程专业复试科目：桥梁与隧道工程专业复试2003；加试科目：桥梁与隧道工程专业加试Ⅰ2003；桥梁与隧道工程专业加试Ⅱ2003岩土工程专业复试科目：综合复试2003市政工程专业复试科目：专业复试2003交通学院高等数学2007，2009高等数学（工）2002——2006，2008高等数学（二）2004交通运输装备2005——2007桥梁设计与施工2005，2007第三方物流理论与实践2007现代物流与运输2005——2006物流学2006现代物流学2002，2007——2009运输经济学2002——2009路基路面工程2002，2005——2007工程热力学2002——2009结构分析2008——2009理论力学2002——2009土质学与土力学2002——2006材料力学1997——2000，2002——2009施工组织及概预算2004土工原理与计算2008——2009公路工程施工组织及概预算2003信号与系统1999——2000，2002——2009微机原理及应用1997——2000，2002——2007运筹学2002——2009（注：2002年试卷有两种）船舶结构力学2002，2004——2009船舶原理2002——2009船舶设计原理2002——2009流体力学2002——2004，2006——2008环境学导论2002国际航运经济与政策2002——2004计算机辅助船体建造2002船舶技术经济学2002传热学2002——2007国际集装箱运输与多式联运2002——2004港口管理（运输企业管理学）2002——2005港口企业管理学2007运输企业管理学2006道路勘测设计2002船舶强度与结构设计2002——2007环境质量评价2002交通环境工程地质与应用2002声学基础2002，2006航运管理2002——2006（注：2002年有两种）结构设计原理2002（第1种），2002（第2种），2005——2007计算机辅助船舶设计2002船舶营运管理2007船舶建造工艺学2003——2007船机制造工艺学2002结构力学计算2008——2009结构力学与结构电算2003——2007运动生物力学2004划船运动概论2004船体振动学2006液压原理与控制2002机械制造工艺学2002流体力学专业复试科目：流体力学2003；加试科目：流体力学2003，工程热力学和传热学、水力学2003工程力学专业复试科目：理论力学2003道路与铁道工程专业复试科目：道路与铁道工程2003，桥梁工程2003；加试科目：土力学2003交通运输规划与管理专业复试科目：综合复试2003；加试科目：交通运输设备概论2003船舶与海洋结构物设计制造专业复试科目：综合复试2003；加试科目：船舶与海洋工程学2003结构工程专业复试科目：结构综合2003；加试科目：钢结构2003航运学院船舶管理2002——2009航运管理2002——2006（注：2002年有两种）航海学2002船舶操纵与避碰2002——2006航海气象学与海洋学2004，2006——2007（注：2007年试卷共3页，缺第2页）物理海洋数字计算2008信号与系统1999——2000，2002——2009能源与动力学院电力电子技术2008——2009电力电子技术（二）2006——2007测试技术2007A卷，2007B卷工程热力学与传热学2006——2009机械振动学2006热能与动力机械制造工艺学2006——2007轮机自动化2007——2009智能运输系统概论2006——2009专业综合（含工程热力学、传热学、内燃机原理）2005专业综合（含工程热力学、传热学、机械设计）2005专业综合（含自动控制理论、测试技术、计算机技术）2005专业综合（含自动控制理论、电工电子技术、计算机控制技术）2005专业综合（含机械设计、测试技术、自动控制理论）2005工程热力学2002——2009机械设计1997——2000，2002——2009船舶柴油机2009内燃机原理2007A卷，2007B卷内燃机原理2002——2004，2006传热学2002——2007自动控制理论2003——2004，2006——2007自动控制原理1997——2000，2002——2009动力机械制造与维修2009船舶动力装置原理与设计2002船舶建造工艺学2003——2007船机制造工艺学2002船舶机械制造与修理2003——2004船舶管理2002——2009机械制造工艺学2002轮机工程专业复试科目：轮机工程2003；加试科目：内燃机学2003；轮机概论2003；工程热力学和传热学2003载运工具运用工程专业复试科目：载运工具运用工程2003管理学院管理学原理1997——2000，2002——2009（2002——2004有答案）管理经济学基础2005——2007管理信息系统2002——2007（2002——2004部分有答案）概率论与数理统计2001——2009线性代数2002线性代数与概率统计2003——2009会计学原理1997——2000，2002——2009（2002——2004有答案）（注：1998年共3页，缺P3）技术经济学2002——2009（2002——2004部分有答案）运筹学2002——2009（注：2002年试卷有两种）现代工业管理2003——2004（2003——2004部分有答案）公司理财原理2002——2009（2002——2004有答案）（注：2002年称“财务管理学”，2003——2004称“公司财务管理”）项目管理2005——2007企业管理学2002（2002有答案）生产管理学2002（2002部分有答案）市场营销学2001(2001有答案)技术创新管理2003（2003部分有答案）工商管理硕士（MBA）专业复试科目：MBA专业综合课2003；加试科目：市场学2003；投资学2003会计学专业复试科目：财务会计与管理会计2003；加试科目：财务管理2003；会计学2003管理科学与工程专业复试科目：企业管理概论2003；加试科目：管理经济学2003；企业管理学2003技术经济及管理专业复试科目：投资分析2003；加试科目：产业经济学2003；投资学2003企业管理专业复试科目：市场营销与生产管理2003；加试科目：市场学2003；管理学原理2003系统工程专业复试科目：系统工程概论与线性规划2003；加试科目：概率统计2003；线性代数2003政治与行政学院邓小平理论和“三个代表”重要思想2007——2009邓小平理论2002——2006马克思主义哲学原理2002——2009政治学原理2007——2009西方哲学史2007——2009西方政治思想史2008——2009中外政治思想2007高等数学（文）2003——2004思想政治教育理论与方法2002——2005，2007科学技术史2002——2007中共党史2002——2009自然辩证法2002——2009中国近代史2002科学技术哲学专业复试科目：综合复试2003；加试科目：马克思主义哲学原理2003；现代科技导论2003中共党史专业复试科目：综合复试2003；加试科目：政治学原理2003；中国近代史2003物流工程学院机械设计基础2005——2009机械工程基础2004机械CAD基础2006起重运输机械2005——2009起重机械2002物流信息技术2005——2009物流学2006现代物流学2002，2007管理学基础2005——2009画法几何2002——2003，2005——2007材料力学1997——2000，2002——2009理论力学2002——2009机械原理1997——2000，2002——2009机械设计1997——2000，2002——2009电子技术基础2002——2009微机原理及应用1997——2000，2002——2007工程材料2002——2007工程力学2004运筹学2002——2009（注：2002年试卷有两种）运筹学与系统工程2004计算机应用基础与计算机技术基础2004仓储技术与设备2006——2007自动识别技术2007CAD/CAM技术2002液压原理与控制2002机械制造工艺学2002机电一体化技术2002液压技术2002机械制造及自动化专业复试科目：机械制造及自动化专业复试2003；面试科目：机械制造专业2003机械电子工程专业复试科目：机械电子工程专业复试2003；面试科目：机械一体化技术（机电专业）2003机械设计及理论专业复试科目：机械设计及理论专业复试2003化学工程学院制药化学2005——2009化工原理2005——2009药物分析2005——2007物理化学2006——2007。

一、选择题（答案不唯一可多选，26分，每空2分）1．下列各项中属于逻辑结构的有。

A. 哈希表B. 有序表C. 单链表D. 顺序表2．由3个结点组成的二叉树的深度可能是。

A．1 B.2 C.3 D.43．将一个a[100][100]的三对角矩阵以行主序存入一维数组B[298]中，元素a[65][64]在B数组中的位置k等于。

A．198 B.197 C.196 D.1954．一棵满二叉树同时又是一棵。

A. 完全二叉树B. 二叉排序树C . 正则二叉树D. 平衡二叉树5．长度为n的顺序表，在任何位置上插入或删除一个元素的概率相等，插入一个元素时平均移动个元素，删除一个元素时平均移动个元素。

A．（n+1）/2 B.n/2 C.(n-1)/2 D.(n-2)/26. 用s表示入栈操作，*表示出栈操作，栈的初态、终态均为空，入栈和出栈的操作序列可表示成仅为由s 和*组成的序列。

下面的序列中合法的操作序列有。

A．s*ss*s** B.sss**s** C. s**s*ss* D.sss*s*s*7. 是特殊的线性表。

A．队列B.哈希表C.栈D.判定表8. 表长为25的哈希表，用除留余数法公式H(key)=key % p 或H(key)=key mod p，则p应取为宜。

A.23B.24C.25D.269．任一个有向图的拓扑序列。

A.可能不存在B.有一个C. 一定有多个D.有一个可多个10．在下列的排序方法中，方法可能出现这种情况：在最后一趟开始之前，所有的元素都不在其最终应在的正确位置上。

A.快速排序B. 冒泡排序C.堆排序D. 插入排序11．若以{4,5,6,7,8}作为权值构造Huffmen树，则该树的带权路径长度为。

A.67B.68C.69D.7012．设head(L)、tail()分别为取广义表表头和表尾的操作，则从广义表L=((x,y,z),a,(u,v,w))中取出原子u 的运算为。

A.head(tail(tail(head(L))))B.tail(head(head(tail(L))))C.head(tail(head(taill(L))))D.head(head(tail(tail(L))))二、填空题（共32分，每空2分）13．在单链表中设置头结点和作用是__________________ 。

武汉理工大学研招办经济学院西方经济学（含微观、宏观经济学）2007——2009经济学（含微观、宏观经济学）1997——2000，2002——2006（2002——2004，2006有答案）宏观经济学2004——2006（2004有答案）货币银行学2004——2007（2004有答案）国际贸易概论1998——2000，2002——2009（2002——2004有答案）国际金融学2002，2004——2009（2002，2004有答案）国际市场营销2002财政学2007产业经济学2002，2006——2009（2002有答案）电子商务概论2008——2009运输经济学2002——2009区域经济学2007人力资源管理2007管理学概论2004——2007（2004有答案）管理学原理1997——2000，2002——2009（2002——2004有答案）微机原理及应用1997——2000，2002——2007概率论与数理统计2001——2009复试科目：国际贸易学2003加试科目：国际金融学2003；国际市场营销学2003复试科目：产业经济学2003复试科目：数量经济学专业复试2003文法学院伦理学基础综合2007——2009伦理学原理2007——2009伦理学2002——2005民法学2007民商法学2008——2009民商法学综合2007——2009经济法学2002，2004——2009经济法综合2007——2009法学综合2002——2006知识产权2007知识产权法2002——2005法理学与知识产权法2004——2005社会心理学2002心理学2002思想政治教育学原理与方法2002——2009中国化的马克思主义2007——2009马克思主义基本原理及其发展2007——2009马克思主义基本原理2007马克思主义哲学原理2002——2009新闻传播专业综合考试（含广告学、编辑出版学）2004——2005出版发行综合2006——2009广告学综合2006——2009传播学原理2004——2009专业综合（教育学、运动训练学）2007体育教育综合（运动生理学、运动训练学）2008——2009运动生理学2007复试科目：综合复试2003；复试（科技法方向）2003加试科目：专业加试2003；加试（科技法方向）2003高等教育研究所教育学2002——2006，2008——2009教育管理学2002——2006，2008——2009复试科目：综合复试2003加试科目：教育学2003；教育心理学2003外国语学院二外日语2002——2009二外法语2002——2009二外德语2002——2009二外俄语2003——2009基础英语2001——2009（注：其中2002，2003，2005年的试卷名称为“综合英语”）英语语言学2001——2003，2006——2009（2001有答案）语言学及英美文学2004——2005英美文学2007——2009英语写作2002复试科目：外国语言学及应用语言学专业复试2003艺术与设计学院设计艺术学专业综合（含设计艺术史论、工业设计及其理论、环境艺术设计及其理论、视觉传播艺术设计、动画艺术设计及其理论、数字艺术设计及其理论）2008——2009美术学专业综合2008——2009艺术学专业综合2008——2009设计艺术学专业史论2003——2006，2008——2009 美术学专业史论2008——2009艺术学专业史论2008——2009音乐艺术研究专业综合（报考艺术管理方向）2009 视觉传播艺术设计基础2007速写与焦墨山水画2005速写与花卉白描2005——2006速写与人物写生画2005——2006速写与色彩人物写生2005，2007速写与泥塑人物写生2007速写与素描人物写生2005速写与水彩或水粉画创作2005速写与装饰画创作2005——2006中外美术史2002，2005，2007中国美术史专题2006中国画创作基础2007艺术美术专业基础2007美术史论2005——2007美术理论2004艺术学概论2007艺术设计史基础2004——2005，2007艺术史论基础2007艺术设计史论基础2003，2006艺术设计理论2002艺术设计史2002专业史论2007艺术设计学“专业设计基础”2002专业设计2002信息设计基础2004——2005动画创作基础2004——2006艺术管理专业基础2004——2005，2007艺术教育专业基础2007民艺专业基础2004 ——2005民间美术2007民间艺术设计及其原理2006设计基础理论与设计基础表达2002环境艺术设计基础2006——2007环境艺术设计与公共艺术创作专业基础2002动画与数字化设计艺术基础2007动画设计与数码设计基础2002系统设计及传播艺术基础2002系统设计及传播艺术理论2002工业设计理论2002工业设计基础2004——2007数码设计理论2002数码艺术设计基础2003中外建筑史2002动画创作理论2002动画创作基础2003环境艺术设计2002环境艺术设计基础2004——2005公共艺术创作与设计2002公共艺术设计基础2006卡通画创作2002专业设计（计算机艺术设计）2002专业设计（系统设计及传播艺术设计）2002环境艺术设计专业方向（环境艺术设计基础）2003设计艺术学专业工业设计方向设计基础2003平面设计基础2003——2005平面艺术设计基础2006现代美术与公共艺术设计基础2003设计管理2006设计基础（展示设计及理论方向）2006信息设计基础2006影视艺术设计基础2006音乐艺术研究2007复试科目：艺术与设计学院复试2003加试科目：艺术与设计学院加试2003理工学院材料力学1997——2000，2002——2009弹性力学2002——2004，2007理论力学2002——2009工程力学2004微机原理及应用1997——2000，2002——2007微机原理（即：微型计算机原理）1997——2000，2002——2004 岩石力学1997——2000，2002岩体力学2003——2007（注：2003年有两种）结构力学2002——2009量子力学2004——2009物理光学2002，2004——2009电磁场与电磁波2004电磁场理论2005——2009概率论与数理统计2001——2009数值分析2002，2004——2007高等代数2001——2009数学分析2002——2009常微分方程2002——2007线性代数2002普通物理2002——2009运筹学2002——2008（注：2002年试卷有两种）物理化学2002——2009有机化学2002——2007无机化学2002——2009化学原理2008——2009基础无机化学2007物理化学原理2007高等数学2007，2009高等数学（工）2002——2006，2008高等数学（二）2004高等数学（文）2003——2005复试科目：应用化学专业复试2003复试科目：应用数学专业复试2003复试科目：固体力学专业复试2003资源与环境工程学院物理化学2002——2009材料力学1997——2000，2002——2009岩石力学1997——2000，2002岩体力学2003——2007（注：2003年有两种）岩石力学与工程2004——2009矿山岩石力学2002无机化学2002——2009浮选2002固体废物处理工程2002水污染控制工程2002大气污染控制工程2002化工基础2002——2007化工原理2002——2009（注：2002年称“环境化工原理”）采矿学2002安全工程学2007——2009爆破工程2002——2009（注：2003年称“凿岩爆破”）流体力学2002——2004胶体化学2003——2009结晶矿物学2003——2006环境学概论2004——2009环境化学2004——2007环境流体力学2002，2005——2007环境工程微生物学2005——2006环境生物学2005——2007矿物加工工程专业复试科目：综合复试2003采矿工程专业复试科目：专业复试2003环境工程专业复试科目：环境工程专业复试2003；加试科目：环境工程专业加试2003材料科学与工程学院材料科学基础2002——2009普通物理2002——2009材料力学1997——2000，2002——2009医学综合一（含生物化学、无机化学）2008——2009医学综合二（含生物化学、高分子化学）2008医学综合三（含生物化学、组织学）2008——2009医学综合2002，2004细胞生物学2002——2007组织学2002——2007物理光学2002，2004——2009计算机在材料科学中的应用2007计算机在材料中的应用2004——2005工程材料2002——2007生物化学2002——2007物理化学2002——2009有机化学2002——2007无机化学2002——2009陶瓷工艺原理2002玻璃工艺原理2002复合材料工艺2002铸造合金及其熔炼2002塑性成型原理2002材料成型原理2003——2009焊接冶金2002金属热处理2002金属材料学2007固体物理2002——2009聚合物加工原理与工艺2002胶凝材料学2002无机非金属材料工学2002，2004——2009金属学及热处理2002硅酸盐物理化学2002高分子化学及物理2002高分子化学2003——2009金属学原理2002——2007材料物理与化学专业复试科目：综合复试2003；加试科目：物理化学2003；材料学院同等学历加试2003材料学专业复试科目：综合复试2003；加试科目：物理化学2003；材料学院同等学历加试2003材料加工工程专业复试科目：综合复试2003；加试科目：物理化学2003；材料学院同等学历加试2003生物医学工程专业复试科目：生物医学工程专业复试2003；加试科目：生物化学2003；组织学2003机电工程学院材料力学1997——2000，2002——2009机械原理1997——2000，2002——2009机械设计1997——2000，2002——2009控制工程基础2002——2009统计质量管理2005——2009传感器原理2003——2009传感检测技术2002——2003传感技术1997——2000传感与检测技术2002电子技术基础2002——2009微机原理及应用1997——2000，2002——2007人机工程学2002——2006机电工程学院2003年同等学历考研加试题（测试技术）机电工程学院2003年同等学历考研加试题（机械原理）机电工程学院2003年同等学力考研加试题（机械设计）机电工程学院2003级硕士研究生复试试题汽车工程学院材料力学1997——2000，2002——2009理论力学2002——2009汽车理论基础2002——2009发动机原理2002——2009摩托车理论与结构设计2002汽车运用工程2002——2009汽车运输工程2002——2003工程热力学2002——2008汽车运输学2003——2005，2007交通运输学2006汽车营销与策划2009汽车市场学2004——2008动力机械及工程专业复试科目：动力机械及工程复试2003；加试科目：发动机构造2003；发动机原理2003车辆工程专业复试科目：综合复试2003；加试科目：汽车构造2003；汽车理论2003载运工具运用工程专业复试科目：综合复试2003自动化学院电路1997——2000，2002——2009电工技术基础2002电工原理2003——2006控制理论基础2002自动控制原理1997——2000，2002——2009信号处理技术2002——2005（注：2002——2003年称“信号分析与处理”）传感技术1997——2000传感与检测技术2002传感检测技术2002——2003传感器原理2003——2009电机及拖动基础2001电力电子技术（一）2007电力电子技术2002——2006，2008——2009微机原理及接口技术2002——2009数字电路2003——2009逻辑设计2004——2006电力电子与电力传动专业复试科目：电力电子与电力传动专业复试2003检测技术与自动化装置专业复试科目：检测技术与自动化装置专业复试2003 控制理论与控制工程专业复试科目：控制理论与控制工程专业复试2003；加试科目：自动控制原理2003；微机原理及接口技术2003计算机科学与技术学院数据结构1997——2000，2002——2008操作系统1998——2000，2002——2008计算机组成原理2002——2007微机原理及应用1997——2000，2002——2007C语言2007微机原理（即：微型计算机原理）1997——2000，2002——2004离散数学2002——2006计算机网络1999——2000，2002软件工程2002——2006数据库原理2002编译原理2002计算机原理2002计算方法2003——2005复试科目：计算机应用技术、计算机软件与理论专业2003加试科目：微机原理及应用2003；数据库应用2003信息工程学院数据结构1997——2000，2002——2008信号与系统1999——2000，2002——2009信号与线性系统2002——2006物理光学2002，2004——2008光纤光学2007现代光学2006高频电路2002微机原理及应用1997——2000，2002——2007微机原理（即：微型计算机原理）1997——2000，2002——2004 脉冲与数字电路1999——2000，2002电子技术基础2002——2009高频电子线路1999——2000，2002微机原理及其通信接口2003——2009信号分析与处理2002——2008传感技术1997——2000电路1997——2000，2002——2009数字信号处理1999——2000，2002，2009土木工程与建筑学院材料力学1997——2000，2002——2009传热学2002——2007中外建筑史2002——2009建筑历史2004——2007建筑设计2002——2004，2008——2009建筑设计（1）2005——2007建筑设计（2）2005——2007规划设计2007——2008城市规划原理2003——2009建筑结构抗震设计2007抗震结构设计2004结构力学2002——2009工程项目管理2008——2009建筑施工与工程项目管理2003——2007建筑施工技术2002建筑工程经济与企业管理2002工程热力学2002——2009土质学与土力学2002——2007水分析化学2002——2005水分析与物理化学2006——2007水力学与水泵2002——2007水力学与水分析化学2008——2009土力学2002——2009建筑构造2002岩石力学1997——2000，2002岩体力学2003——2007（注：其中2003年有两种）钢筋混凝土结构2002，2006——2009混凝土结构原理2003钢筋砼结构2005土力学与基础工程2002结构动力学2002结构设计原理2002（第1种），2002（第2种），2005——2007桥梁工程2002给水工程2002排水工程2002路基路面工程2002，2005——2007工程地质学2004——2006美学2004建筑设计及其理论专业复试科目：建筑设计2003；建筑设计知识2003；加试科目：中外建筑史2003结构工程专业复试科目：结构工程2003；综合复试（建筑工程施工技术、建设工程项目管理方向）2003；加试科目：施工组织学2003；建筑经济与企业管理2003；结构力学2003；混凝土结构2003桥梁与隧道工程专业复试科目：桥梁与隧道工程专业复试2003；加试科目：桥梁与隧道工程专业加试Ⅰ2003；桥梁与隧道工程专业加试Ⅱ2003岩土工程专业复试科目：综合复试2003市政工程专业复试科目：专业复试2003交通学院高等数学2007，2009高等数学（工）2002——2006，2008高等数学（二）2004交通运输装备2005——2007桥梁设计与施工2005，2007第三方物流理论与实践2007现代物流与运输2005——2006物流学2006现代物流学2002，2007——2009运输经济学2002——2009路基路面工程2002，2005——2007工程热力学2002——2009结构分析2008——2009理论力学2002——2009土质学与土力学2002——2006材料力学1997——2000，2002——2009施工组织及概预算2004土工原理与计算2008——2009公路工程施工组织及概预算2003信号与系统1999——2000，2002——2009微机原理及应用1997——2000，2002——2007运筹学2002——2009（注：2002年试卷有两种）船舶结构力学2002，2004——2009船舶原理2002——2009船舶设计原理2002——2009流体力学2002——2004，2006——2008环境学导论2002国际航运经济与政策2002——2004计算机辅助船体建造2002船舶技术经济学2002传热学2002——2007国际集装箱运输与多式联运2002——2004港口管理（运输企业管理学）2002——2005港口企业管理学2007运输企业管理学2006道路勘测设计2002船舶强度与结构设计2002——2007环境质量评价2002交通环境工程地质与应用2002声学基础2002，2006航运管理2002——2006（注：2002年有两种）结构设计原理2002（第1种），2002（第2种），2005——2007计算机辅助船舶设计2002船舶营运管理2007船舶建造工艺学2003——2007船机制造工艺学2002结构力学计算2008——2009结构力学与结构电算2003——2007运动生物力学2004划船运动概论2004船体振动学2006液压原理与控制2002机械制造工艺学2002流体力学专业复试科目：流体力学2003；加试科目：流体力学2003，工程热力学和传热学、水力学2003工程力学专业复试科目：理论力学2003道路与铁道工程专业复试科目：道路与铁道工程2003，桥梁工程2003；加试科目：土力学2003交通运输规划与管理专业复试科目：综合复试2003；加试科目：交通运输设备概论2003船舶与海洋结构物设计制造专业复试科目：综合复试2003；加试科目：船舶与海洋工程学2003结构工程专业复试科目：结构综合2003；加试科目：钢结构2003航运学院船舶管理2002——2009航运管理2002——2006（注：2002年有两种）航海学2002船舶操纵与避碰2002——2006航海气象学与海洋学2004，2006——2007（注：2007年试卷共3页，缺第2页）物理海洋数字计算2008信号与系统1999——2000，2002——2009能源与动力学院电力电子技术2008——2009电力电子技术（二）2006——2007测试技术2007A卷，2007B卷工程热力学与传热学2006——2009机械振动学2006热能与动力机械制造工艺学2006——2007轮机自动化2007——2009智能运输系统概论2006——2009专业综合（含工程热力学、传热学、内燃机原理）2005专业综合（含工程热力学、传热学、机械设计）2005专业综合（含自动控制理论、测试技术、计算机技术）2005专业综合（含自动控制理论、电工电子技术、计算机控制技术）2005专业综合（含机械设计、测试技术、自动控制理论）2005工程热力学2002——2009机械设计1997——2000，2002——2009船舶柴油机2009内燃机原理2007A卷，2007B卷内燃机原理2002——2004，2006传热学2002——2007自动控制理论2003——2004，2006——2007自动控制原理1997——2000，2002——2009动力机械制造与维修2009船舶动力装置原理与设计2002船舶建造工艺学2003——2007船机制造工艺学2002船舶机械制造与修理2003——2004船舶管理2002——2009机械制造工艺学2002轮机工程专业复试科目：轮机工程2003；加试科目：内燃机学2003；轮机概论2003；工程热力学和传热学2003载运工具运用工程专业复试科目：载运工具运用工程2003管理学院管理学原理1997——2000，2002——2009（2002——2004有答案）管理经济学基础2005——2007管理信息系统2002——2007（2002——2004部分有答案）概率论与数理统计2001——2009线性代数2002线性代数与概率统计2003——2009会计学原理1997——2000，2002——2009（2002——2004有答案）（注：1998年共3页，缺P3）技术经济学2002——2009（2002——2004部分有答案）运筹学2002——2009（注：2002年试卷有两种）现代工业管理2003——2004（2003——2004部分有答案）公司理财原理2002——2009（2002——2004有答案）（注：2002年称“财务管理学”，2003——2004称“公司财务管理”）项目管理2005——2007企业管理学2002（2002有答案）生产管理学2002（2002部分有答案）市场营销学2001(2001有答案)技术创新管理2003（2003部分有答案）工商管理硕士（MBA）专业复试科目：MBA专业综合课2003；加试科目：市场学2003；投资学2003会计学专业复试科目：财务会计与管理会计2003；加试科目：财务管理2003；会计学2003管理科学与工程专业复试科目：企业管理概论2003；加试科目：管理经济学2003；企业管理学2003技术经济及管理专业复试科目：投资分析2003；加试科目：产业经济学2003；投资学2003企业管理专业复试科目：市场营销与生产管理2003；加试科目：市场学2003；管理学原理2003系统工程专业复试科目：系统工程概论与线性规划2003；加试科目：概率统计2003；线性代数2003政治与行政学院邓小平理论和“三个代表”重要思想2007——2009邓小平理论2002——2006马克思主义哲学原理2002——2009政治学原理2007——2009西方哲学史2007——2009西方政治思想史2008——2009中外政治思想2007高等数学（文）2003——2004思想政治教育理论与方法2002——2005，2007科学技术史2002——2007中共党史2002——2009自然辩证法2002——2009中国近代史2002科学技术哲学专业复试科目：综合复试2003；加试科目：马克思主义哲学原理2003；现代科技导论2003中共党史专业复试科目：综合复试2003；加试科目：政治学原理2003；中国近代史2003物流工程学院机械设计基础2005——2009机械工程基础2004机械CAD基础2006起重运输机械2005——2009起重机械2002物流信息技术2005——2009物流学2006现代物流学2002，2007管理学基础2005——2009画法几何2002——2003，2005——2007材料力学1997——2000，2002——2009理论力学2002——2009机械原理1997——2000，2002——2009机械设计1997——2000，2002——2009电子技术基础2002——2009微机原理及应用1997——2000，2002——2007工程材料2002——2007工程力学2004运筹学2002——2009（注：2002年试卷有两种）运筹学与系统工程2004计算机应用基础与计算机技术基础2004仓储技术与设备2006——2007自动识别技术2007CAD/CAM技术2002液压原理与控制2002机械制造工艺学2002机电一体化技术2002液压技术2002机械制造及自动化专业复试科目：机械制造及自动化专业复试2003；面试科目：机械制造专业2003机械电子工程专业复试科目：机械电子工程专业复试2003；面试科目：机械一体化技术（机电专业）2003机械设计及理论专业复试科目：机械设计及理论专业复试2003化学工程学院制药化学2005——2009化工原理2005——2009药物分析2005——2007物理化学2006——2007。

武汉理工大学2019-2020学年第一学期2018级软件工程专业《Java语言程序设计》期末考试试题姓名：_________ 年级：_______级专业：_________ 学号：___________一、单项选择题(本大题共10小题，每小题1分，共10分) 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。

错选、多选或未选均无分。

1. 在Java中，负责对字节代码解释执行的是() (1分)A：垃圾回收器B：虚拟机C：编译器D：多线程机制2. 在Java中，获取选择框是否被选中的方法是() (1分)A：getSelect()B：getSelected()C：isSelect()D：isSelected()3. 下列叙述中,正确的是() (1分)A：Java语言的标识符是区分大小写的B：源文件名与public类名可以不相同C：源文件名其扩展名为.jarD：源文件中public类的数目不限4. 要为程序中的按钮button设置一个热键alt+A，可以采用的代码是() (1分)A：button.setMnemonic(?A?)B：button.setMnemonic("alt+A")C：button.setToolTipText(?A?)D：button.setToolTipText("alt+A")5. 在Java中，设置字型应使用Graphics的()方法。

(1分)A：setfont(Font font)B：setFont(Font font)C：Font(String fontname,int style,int size)D：font(String fontname,int style,int size)6. 列表事件的事件源有两种，其中之一是单击列表中的选项，则与单击选项事件相关的接口是() (1分)A：ActionListenerB：ListSelectionEventC：ListSelectionListenerD：addListSelectionListener7. 在Java语言的java.util包中，用于语言符号(单词)分析的类是() (1分)A：stringTokenizerB：StringTokenizerC：ToKenizerD：tokenizer8. 下列语句中，错误的Java语句是() (1分)A：连续出现多个分号B：try......catch语句C：include语句D：switch语句9. 在Java程序中，已将FileWriter对象接到BufferedWriter对象上，要实现缓冲式输出，可对BufferedWriter对象使用的方法是() (1分)A：read()B：write()C：readLine()D：writeLong()10. 接口的所有变量和方法分别默认为是() (1分)A：final static和public abstractB：final static和public finalC：public static和public abstractD：public static和public final二、填空题(本大题共10小题，每小题2分，共20分)请在每小题的空格中填上正确答案。

8．（）堆排序中，在输出一个根之后的调整操作中，“临时根”结点的值将被调到“叶子结点”上。

3、填空（每小题2分，共14分）1．在单链表中，删除指针P所指结点的后继结点的语句是（）。

2．已知完全二叉树的第八层有8个结点，则其叶子结点数是（）。

3．有n个顶点的强连通有向图G至少有（）条弧。

4．求最短路径的DIJKSTRA算法的时间复杂度为（）。

5．在有序表A[1，20]中，采用二分查找算法查找元素值等于A[12]的元素，所比较过的元素的下标依次为（）。

6．直接选择排序算法所执行的元素交换次数最多为（）。

7．下列排序算法中，稳定的排序算法是（）（选择排序，堆排序，快速排序，直接插入排序）。

4、解答下列各题(38分)1．一棵二叉树的先序序列和中序序列分别如下，画出该二叉树。

(6分)先序序列ABCDEFGHIJ中序序列CBEDAGHFJI2．对下面给出的数据序列，构造一棵哈夫曼树，并求出其带权路径长度。

(8分)4， 5， 6， 7， 10， 12， 15， 18， 233．图G的邻接表如下，完成下列各题：(8分)(1)画出从顶点5出发进行广度遍历所生成的生成树。

(2)判断其中是否存在有向回路，若不存在，求出其拓扑序列。

13225436749859108611712899101011111212^4．对下列数据表，写出采用快速排序算法排序的每一趟的结果。

(8分)(60，20，31，1，5，44，55，61，200，30，80，150，4，29)5．已知哈希表地址空间为0．．8，哈希函数为H(k)=k % 7，采用线性探查法处理冲突。

将下面数据序列依次存入该散列表中，并求出在等概率下的平均查找长度。

(8分)100，20，21，35，3，78，99，450 1 2 3 4 5 6 7 85、算法设计(共30分)1．已知单循环链表L中至少有两个结点，每个结点的两个字段为data和next，其中字段data的类型为整型。

数据结构试卷（一）一、单选题（每题 2 分，共20分）1.栈和队列的共同特点是( A )。

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层的结点数最多为( ).k-1A．2k-1 B.2K+1 C.2K-1 D. 27.若有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个结点的无向图，该图至少应有( )条边才能确保是一个连通图。

A.5B.6C.7D.8二、填空题（每空1分，共26分）1.通常从四个方面评价算法的质量：__ _、__ _____、______和_________。

2.一个算法的时间复杂度为(n3+n2log2n+14n)/n2，其数量级表示为_____。

一、计算( 每题参考分值5分)1、用一台60MHZ处理机执行标准测试程序，程序所含的混合指令数和每类指令的CPI如表所示，求有效CPI、MIPS 速率和程序的执行时间。

正确答案：解：总的指令数为：45000+35000+15000+15000=100000条，因此各类指令所占的比例分别是：整数运算为45%，数据传送为25%，浮点操作为15%，控制传送为15%。

有效CPI、MIPS速率和程序的执行时间分别计算如下：(1)有效CPI为：1×0.45+2×0.25+4×0.15+2×0.15=1.85CPI (2)MIPS速率为:1/1.85×60=32.43MIPS (3)程序的执行时间为：100000×1.85/(60×106)=0.003083s=3083us2、用一台50MHZ处理机执行标准测试程序，程序所含的混合指令数和每类指令的CPI如表所示，求有效CPI、MIPS 速率和程序的执行时间。

正确答案：解：总的指令数为：5000+3000+1000+1000=10000条，因此各类指令所占的比例分别是：整数运算为50%，数据传送为30%，浮点操作为10%，控制传送为10%。

有效CPI、MIPS速率和程序的执行时间分别计算如下：(1)有效CPI为：1×0.5+2×0.3+3×0.1+2×0.1=1.6CPI (2)MIPS速率为:1/1.6×50=31.325MIPS (3)程序的执行时间为：10000×1.6/(50×106)=0.00032s=320us3、用一台40MHZ处理机执行标准测试程序，程序所含的混合指令数和每类指令的CPI如表所示，求有效CPI、MIPS 速率和程序的执行时间。

正确答案：解：总的指令数为：45000+32000+15000+8000=100000条，因此各类指令所的比例分别是：整数运算为45%，数据传送为32%，浮点操作为15%，送为8%。

《852数据结构真题》2002年数据结构研究生入学考试试题一．选择题（30分，每空2分。

答案可能不唯一）1．算法在发生非法操作时可以作出处理的特性称为。

①正确性②可读性③键状性④可靠性2．指针p所指的元素是双向链表L的尾元素的条件是 A 。

若队列采用链式存储，则该链式队列 B 。

A：① p==L ② p==NULL ③ p->Llink==L ④p->Rlink==LB：①存在队满的情况②不存在队空的情况③入队之前必须判断队满否④出队之前必须判断队空否3．二叉排序树是：。

①中序遍历得到一升序序列的二叉树②每一分支结点的度均为2的二叉树③按层次从左到右顺序编号的二叉树④每一分支结点的值均小于其右子树上所有结点的值（若右子树存在），又大于其左子树上所有结点的值（若左子树存在）4．三对角矩阵a[1…n][1…n]以行为主序顺序存储，其存储始址是b，每个元素占一个存储单元，则元素a[i][j]的存储始址为。

①b+2*j+i-2 ② b+2*i+j-2 ③ b+2*j+i-3 ④ b+2*i+j-35．已知一棵二叉树的前序序列和中序序列分别是GFDBHCEA和DFHBGCAE，则该二叉树的后序序列为 A ，层次序列为 B ，若由森林转化得到的二叉树是非空的二叉树，则该二叉树是 C ，如果满足条件 D ，线索二叉树中结点p无右孩子。

A、B：① DBHFEACG ② GFCDBEHA ③ DHBFAECG ④ DFGBCEHAC：①根结点无右子树②根结点可能有左子树和右子树③根结点无左子树④各结点只有一个孩子D：①p->rchild==NULL ②p->rtag==1 p->rtag==0 ④p->rtag==NULL6.一个加权连通无向图的最小生成树可以使用 A 生成。

一项工程完工所需的最少时间等于某个 BA：① Hash算法② Dijstra算法③ prim算法④ Huffman算法B：① AOE网中源点到汇点事件最多的路径的长度②AOE网中源点到汇点的最长路径的长度③AOE网中源点到汇点的最短路径的长度④AOE网中源点到汇点活动最多的路径的长度7.用冒泡排序的方法对n个记录进行排序，第一趟共要比较 A对元素。

1. 下面程序段的执行次数为Afori=0;i＜n-1;i++forj=n;j＞i;j--state;A. nn+22 B .n-1n+22 C. nn+12 D. n-1n+22. 一个向量第一个元素的存储地址是100;每个元素的长度为2;则第5个元素的地址是 B A. 110 B .108 C. 100 D. 1203. 一个栈的入栈序列是a;b;c;d;e;则栈的不可能的输出序列是 C A. edcba B .decba C. dceab D. abcde4. 循环队列用数组A0;m－1存放其元素值;已知其头尾指针分别是front和rear;则当前队列中的元素个数是 DA. rear-front+m%m B .read-front+1C. read-front-1 D. read-front5．不带头结点的单链表head为空的判定条件是 A A. head=NULL B .head-next=NULLC. head-next=head D. head=NULL6．在一个单链表中;若p所指的结点不是最后结点;在p之后插入s所指结点;则执行BA.s-next=p;p-next=s; B .s-next=p-next;p-next=s; C. s-next=p-next;p=s; D. p-next=s;s-next=p;7. 从一个具有n个结点的单链表中查找其值等于x结点时;在查找成功的情况下;需平均比较多少个结点 D A. n B .n2 C. n-12 D. n+128．从一个栈顶指针为HS的链栈中删除一个结点时;用x保存被删结点的值;则执行 D A. x=HS;HS=HS-next;B .x=HS-data;C.HS=HS-next;x=HS-data;D. x=HS-data;HS=HS-next; 9．串是一种特殊的线性表;其特殊性体现在BA. 可以顺序存储 B .数据元素是一个字符C. 可以链接存储 D. 数据元素可以是多个字符11．二维数组M的元素是4个字符每个字符占一个存储单元组成的串;行下标i的范围从0到4;列下标j的范围从0到5;M按行存储时元素M35的起始地址与M按列存储时下列哪一元素的起始地址相同 B A. M24 B .M34 C. M35 D. M4412. 数组A中;每个元素A的长度为3个字节;行下标i从1到8;列下标j从1到10;从首地址SA 开始连续存放在存储器内;该数组按行存放时;元素A85的起始地址为 C A. SA+144B .SA+180 C. SA+222 D. SA+22513. 设高度为h的二叉树上只有度为0和度为2的结点;则此类二叉树中所包含的结点数至少为：B A. 2h B .2h-1 C. 2h+1 D. h+114. 已知某二叉树的后序遍历序列是dabec;中序遍历序列是debac;它的前序遍历序列是 D A. acbed B .decab C. deabc D. cedba15. 树的基本遍历策略可分为先根遍历和后根遍历；二叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历..这里;我们把由树转化得到的二叉树叫做这棵树对应的二叉树..下列结论哪个正确 A A. 树的先根遍历序列与其对应的二叉树的先序遍历序列相同B .树的后根遍历序列与其对应的二叉树的后序遍历序列相同C. 树的先根遍历序列与其对应的二叉树的中序遍历序列相同D. 以上都不对16. 具有6个顶点的无向图至少应有多少条边才能确保是一个连通图 AA. 5 B .6 C. 7 D. 817. 顺序查找法适合于存储结构为 B 的线性表 A. 散列存储B .顺序存储或链接存储C. 压缩存储 D. 索引存储18.采用顺序查找方法查找长度为n的线性表每个元素的平均查找长度为C A. n B .n2 C. n+12 D. n-1219. 有一个长度为12的有序表;按二分查找法对该表进行查找;在表内各元素等概率情况下查找成功所需的平均比较次数为 BA. 3512 B .3712 C. 3912 D. 431220.有一个有序表为{1;3;9;12;32;41;45;62;75;77;82;95;100};当二分查找值82为的结点时;几次比较后查找成功 C二、填空题每空1分;共20分1.在线性表的顺序存储中;元素之间的逻辑关系是通过物理存储位置;决定的；在线性表的链接存储中;元素之间的逻辑关系是通过链域的指针值决定的..2．对于一个具有N个结点的单链表;在已知的结点P后插入一个新结点的时间复杂度为O1;在给定值为X的结点后插入一个新结点的时间复杂度为ON.. 3.有一空桟;现有输入序列1;2;3;4;5;经push;push;pop;push;pop;push;push后;输出序列为2;3 ..4．在一个无向图中;所有顶点的度数之和等于所有边数的2 倍 5.对于一棵具有n个结点的树;该树中所有结点的度数之和为n-1..6. 在一棵三叉树中;度为3的结点数有2个;度为2的结点数有1个;度为1的结点数为2个;那么度为0的结点数有6个7.在霍夫曼编码中;若编码长度只允许小于等于4;则除了已对两个字符编码为0和10外;还可以最多对 4 个字符编码..8. 对于一个具有n个顶点和e条边的连通图;其生成树中的顶点数和边数分别为n 和n-1 ..9. 对20个记录进行归并排序时;共需要进行5 趟归并;在第三趟归并时是把长度为4 的有序表两两归并为长度为8 的有序表..三、问答题 1. 简述下面算法的功能栈和队列的元素类型均为intvoid algo3Queue &Q{Stack S; int d;InitStackS;whileQueueEmptyQ{DeQueueQ;d;PushS;d;}whileStackEmptyS{PopS;d; EnQueueQ;d;}}算法的功能：利用栈作辅助;将队列中的数据元素进行逆置2. 已知一棵二叉树的中序遍历序列和先序遍历序列为;试问能不能唯一确定一棵二叉树..若给定先序遍历序列和后序遍历序列;能不能唯一确定呢由中序遍历序列和先序遍历序列能唯一确定一棵二叉树..由先序遍历和后序遍历序列不能唯一确定一棵二叉树...一、选择题1. 下面程序段的执行次数为fori=0;i＜n-1;i++forj=n;j＞i;j--state;A. nn+22 B .n-1n+22 C. nn+12 D. n-1n+22. 判定一个栈ST最多元素为m0为空的条件是： A. ST-top0 B .ST-top＝0C. ST-topm0D. ST-top＝m03. 一个栈的入栈序列是a;b;c;d;e;则栈的不可能的输出序列是 A. edcba B .decba C. dceab D. abcde4. 在一个单链表中;若p所指的结点不是最后结点;在p之后插入s所指结点;则执行 A.s-next=p;p-next=s;B .s-next=p-next;p-next=s;C. s-next=p-next;p=s;D. p-next=s;s-next=p;5．在一个链队中;假设f和r分别为队首和队尾指针;则删除一个结点的运算时 A. r=f-next;B .r=r-next; C. f=f-next;D. f=r-next;6．串是一种特殊的线性表;其特殊性体现在 A. 可以顺序存储 B .数据元素是一个字符 C. 可以链接存储 D. 数据元素可以是多个字符7. 稀疏矩阵一般的压缩方法有两种;即 A. 二维数组和三维数组 B .三元组和散列C. 三元组和十字链表D. 散列和十字链表8．将递归算法转换成对应的非递归算法时;通常需要使用 A. 栈 B .队列 C. 链表 D. 树9．二维数组M的元素是4个字符每个字符占一个存储单元组成的串;行下标i的范围从0到4;列下标j的范围从0到5;M按行存储时元素M35的起始地址与M按列存储时下列哪一元素的起始地址相同 A. M24 B .M34 C. M35 D. M4410. 数组A中;每个元素A的长度为3个字节;行下标i从1到8;列下标j从1到10;从首地址SA开始连续存放在存储器内;该数组按行存放时;元素A85的起始地址为 A. SA+144 B .SA+180 C. SA+222 D. SA+22511. 如果T2是由有序树T转换而来的二叉树;那么T中结点的后序就是T2中结点的 A. 前序 B .中序 C. 后序 D. 层次序12.一个有n个顶点的无向图最多有多少边 A. n B .nn-1 C. nn-12 D. 2n13.按照二叉树的定义;具有3个结点的二叉树有种A. 3 B .4 C. 5 D. 6 14.在一非空二叉树的中序遍历序列中;根结点的右边 A. 只有右子树上的所有结点 B .只有右子树上的部分结点 C. 只有左子树上的部分结点 D. 只有左子树上的所有结点15. 在一个图中;所有顶点的度数之和等于所有边数的多少倍 A. 12 B .1 C. 2 D. 416.采用邻接表存储的图的深度优先遍历算法类似于二叉树的 A. 先序遍历 B .中序遍历C. 后序遍历D. 按层遍历17.采用顺序查找方法查找长度为n的线性表每个元素的平均查找长度为 A. n B .n2C. n+12D. n-12二、填空题1. 算法的计算量的大小称为计算的___ _..2．数据结构是研究数据的和以及他们之间的相互关系;并对这种结构定义相应的运算;设计出相应的;而确保经过这些运算后所得的新结构是结构类型..3．在一个单链表中删除p结点;应执行下列操作：q=p-next;p-data=p-next-data;p-next= ;freeq;4.有一空桟;现有输入序列5;4;3;2;1;经push;push;pop;push;pop;push;push后;输出序列为..5．在双向链表中每个结点包含两个指针域;一个指向结点;另一个指向结点..6．一维数组的逻辑结构是;存储结构是.. 7.对于一棵含有40个结点的理想平衡树;它的高度为____ ..8.假定对长度n＝50的有序表进行折半搜索;则对应的判定树高度为;判定树中前5层的结点数为;最后一层的结点数为.. 9. 假定一组记录的排序码为46;79;56;38;40;80;对其进行归并排序的过程中;第二趟归并后的结果为____ ..10. 假定一组记录的排序码为46;79;56;38;40;80;对其进行快速排序的一次划分的结果为____..三、简答题 1.假定有四个元素A;B;C;D依次进栈;进栈过程中允许出栈;试写出所有可能的出栈序列 2.一棵含有n个结点的k叉树;可能达到的最大深度和最小深度各为多少 3. 设有5000个无序的元素;希望用最快速度挑选出其中前10个最大的元素;在以下的排序方法中;采用哪种方法最好为什么快速排序;堆排序;基数排序一、选择题1. B 2. B 3. C 4. B 5．C 6．B 9．C 10．A 11．B 12. C 13. B 14.C 15. C 16. A 17. C 18. A 19. C二、填空题1.复杂度2．物理结构; 逻辑结构;算法; 原来的3．q-next; 4. 4;3 5. 前驱; 后续6．线性结构; 顺序结构7. 5 8. 5 ; 31 ;19 .. 9. 38 46 56 7940 84 ..10. 84;79;56;38;40;46 ..三、问答题 1.答：共有14种可能的出栈序列为：ABCD; ABDC; ACBD; ACDB; BACD; ADCB; BADC; BCAD;BCDA;BDCA;CBAD;CBDA;CDBA;DCBA 2. 答：显然能达到最大深度的是单支树其深度为n；深度最小的是完全k叉树..3. 答：用堆排序最好;因为堆排序不需要等整个排序结束就可挑出前10个最大元素;而快速排序和基数排序都需等待整个排序结束才能知道前10个最大元素..1. 下面程序段的执行次数为Afori=0;i＜n-1;i++forj=n;j＞i;j--state;A. nn+22 B .n-1n+22 C. nn+12 D. n-1n+22. 一个向量第一个元素的存储地址是100;每个元素的长度为2;则第5个元素的地址是 B A. 110 B .108 C. 100 D. 1203. 一个栈的入栈序列是a;b;c;d;e;则栈的不可能的输出序列是 C A. edcba B .decba C. dceab D. abcde4. 循环队列用数组A0;m－1存放其元素值;已知其头尾指针分别是front和rear;则当前队列中的元素个数是 DA. rear-front+m%m B .read-front+1C. read-front-1 D. read-front5．不带头结点的单链表head为空的判定条件是 A A. head=NULL B .head-next=NULLC. head-next=head D. head=NULL6．在一个单链表中;若p所指的结点不是最后结点;在p之后插入s所指结点;则执行BA.s-next=p;p-next=s; B .s-next=p-next;p-next=s; C. s-next=p-next;p=s; D. p-next=s;s-next=p;7. 从一个具有n个结点的单链表中查找其值等于x结点时;在查找成功的情况下;需平均比较多少个结点 D A. n B .n2 C. n-12 D. n+128．从一个栈顶指针为HS的链栈中删除一个结点时;用x保存被删结点的值;则执行 D A. x=HS;HS=HS-next;B .x=HS-data;C.HS=HS-next;x=HS-data;D. x=HS-data;HS=HS-next; 9．串是一种特殊的线性表;其特殊性体现在BA. 可以顺序存储 B .数据元素是一个字符C. 可以链接存储 D. 数据元素可以是多个字符11．二维数组M的元素是4个字符每个字符占一个存储单元组成的串;行下标i的范围从0到4;列下标j的范围从0到5;M按行存储时元素M35的起始地址与M按列存储时下列哪一元素的起始地址相同 B A. M24 B .M34 C. M35 D. M4412. 数组A中;每个元素A的长度为3个字节;行下标i从1到8;列下标j从1到10;从首地址SA 开始连续存放在存储器内;该数组按行存放时;元素A85的起始地址为 C A. SA+144B .SA+180 C. SA+222 D. SA+22513. 设高度为h的二叉树上只有度为0和度为2的结点;则此类二叉树中所包含的结点数至少为：B A. 2h B .2h-1 C. 2h+1 D. h+114. 已知某二叉树的后序遍历序列是dabec;中序遍历序列是debac;它的前序遍历序列是 D A. acbed B .decab C. deabc D. cedba15. 树的基本遍历策略可分为先根遍历和后根遍历；二叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历..这里;我们把由树转化得到的二叉树叫做这棵树对应的二叉树..下列结论哪个正确 A A. 树的先根遍历序列与其对应的二叉树的先序遍历序列相同B .树的后根遍历序列与其对应的二叉树的后序遍历序列相同C. 树的先根遍历序列与其对应的二叉树的中序遍历序列相同D. 以上都不对16. 具有6个顶点的无向图至少应有多少条边才能确保是一个连通图 AA. 5 B .6 C. 7 D. 817. 顺序查找法适合于存储结构为 B 的线性表 A. 散列存储B .顺序存储或链接存储C. 压缩存储 D. 索引存储18.采用顺序查找方法查找长度为n的线性表每个元素的平均查找长度为C A. n B .n2 C. n+12 D. n-1219. 有一个长度为12的有序表;按二分查找法对该表进行查找;在表内各元素等概率情况下查找成功所需的平均比较次数为 BA. 3512 B .3712 C. 3912 D. 431220.有一个有序表为{1;3;9;12;32;41;45;62;75;77;82;95;100};当二分查找值82为的结点时;几次比较后查找成功 C二、填空题每空1分;共20分1.在线性表的顺序存储中;元素之间的逻辑关系是通过物理存储位置;决定的；在线性表的链接存储中;元素之间的逻辑关系是通过链域的指针值决定的..2．对于一个具有N个结点的单链表;在已知的结点P后插入一个新结点的时间复杂度为O1;在给定值为X的结点后插入一个新结点的时间复杂度为ON.. 3.有一空桟;现有输入序列1;2;3;4;5;经push;push;pop;push;pop;push;push后;输出序列为2;3 ..4．在一个无向图中;所有顶点的度数之和等于所有边数的2 倍 5.对于一棵具有n个结点的树;该树中所有结点的度数之和为n-1..6. 在一棵三叉树中;度为3的结点数有2个;度为2的结点数有1个;度为1的结点数为2个;那么度为0的结点数有6个7.在霍夫曼编码中;若编码长度只允许小于等于4;则除了已对两个字符编码为0和10外;还可以最多对 4 个字符编码..8. 对于一个具有n个顶点和e条边的连通图;其生成树中的顶点数和边数分别为n 和n-1 ..9. 对20个记录进行归并排序时;共需要进行5 趟归并;在第三趟归并时是把长度为4 的有序表两两归并为长度为8 的有序表..三、问答题 1. 简述下面算法的功能栈和队列的元素类型均为intvoid algo3Queue &Q{Stack S; int d;InitStackS;whileQueueEmptyQ{DeQueueQ;d;PushS;d;}whileStackEmptyS{PopS;d; EnQueueQ;d;}}算法的功能：利用栈作辅助;将队列中的数据元素进行逆置2. 已知一棵二叉树的中序遍历序列和先序遍历序列为;试问能不能唯一确定一棵二叉树..若给定先序遍历序列和后序遍历序列;能不能唯一确定呢由中序遍历序列和先序遍历序列能唯一确定一棵二叉树..由先序遍历和后序遍历序列不能唯一确定一棵二叉树...一、选择题1. 下面程序段的执行次数为fori=0;i＜n-1;i++forj=n;j＞i;j--state;A. nn+22 B .n-1n+22 C. nn+12 D. n-1n+22. 判定一个栈ST最多元素为m0为空的条件是： A. ST-top0 B .ST-top＝0C. ST-topm0D. ST-top＝m03. 一个栈的入栈序列是a;b;c;d;e;则栈的不可能的输出序列是 A. edcba B .decba C. dceab D. abcde4. 在一个单链表中;若p所指的结点不是最后结点;在p之后插入s所指结点;则执行 A.s-next=p;p-next=s;B .s-next=p-next;p-next=s;C. s-next=p-next;p=s;D. p-next=s;s-next=p;5．在一个链队中;假设f和r分别为队首和队尾指针;则删除一个结点的运算时 A. r=f-next;B .r=r-next; C. f=f-next;D. f=r-next;6．串是一种特殊的线性表;其特殊性体现在 A. 可以顺序存储 B .数据元素是一个字符 C. 可以链接存储 D. 数据元素可以是多个字符7. 稀疏矩阵一般的压缩方法有两种;即 A. 二维数组和三维数组 B .三元组和散列C. 三元组和十字链表D. 散列和十字链表8．将递归算法转换成对应的非递归算法时;通常需要使用 A. 栈 B .队列 C. 链表 D. 树9．二维数组M的元素是4个字符每个字符占一个存储单元组成的串;行下标i的范围从0到4;列下标j的范围从0到5;M按行存储时元素M35的起始地址与M按列存储时下列哪一元素的起始地址相同 A. M24 B .M34 C. M35 D. M4410. 数组A中;每个元素A的长度为3个字节;行下标i从1到8;列下标j从1到10;从首地址SA开始连续存放在存储器内;该数组按行存放时;元素A85的起始地址为 A. SA+144 B .SA+180 C. SA+222 D. SA+22511. 如果T2是由有序树T转换而来的二叉树;那么T中结点的后序就是T2中结点的 A. 前序 B .中序 C. 后序 D. 层次序12.一个有n个顶点的无向图最多有多少边 A. n B .nn-1 C. nn-12 D. 2n13.按照二叉树的定义;具有3个结点的二叉树有种A. 3 B .4 C. 5 D. 6 14.在一非空二叉树的中序遍历序列中;根结点的右边 A. 只有右子树上的所有结点 B .只有右子树上的部分结点 C. 只有左子树上的部分结点 D. 只有左子树上的所有结点15. 在一个图中;所有顶点的度数之和等于所有边数的多少倍 A. 12 B .1 C. 2 D. 416.采用邻接表存储的图的深度优先遍历算法类似于二叉树的 A. 先序遍历 B .中序遍历C. 后序遍历D. 按层遍历17.采用顺序查找方法查找长度为n的线性表每个元素的平均查找长度为 A. n B .n2C. n+12D. n-12二、填空题1. 算法的计算量的大小称为计算的___ _..2．数据结构是研究数据的和以及他们之间的相互关系;并对这种结构定义相应的运算;设计出相应的;而确保经过这些运算后所得的新结构是结构类型..3．在一个单链表中删除p结点;应执行下列操作：q=p-next;p-data=p-next-data;p-next= ;freeq;4.有一空桟;现有输入序列5;4;3;2;1;经push;push;pop;push;pop;push;push后;输出序列为..5．在双向链表中每个结点包含两个指针域;一个指向结点;另一个指向结点..6．一维数组的逻辑结构是;存储结构是.. 7.对于一棵含有40个结点的理想平衡树;它的高度为____ ..8.假定对长度n＝50的有序表进行折半搜索;则对应的判定树高度为;判定树中前5层的结点数为;最后一层的结点数为.. 9. 假定一组记录的排序码为46;79;56;38;40;80;对其进行归并排序的过程中;第二趟归并后的结果为____ ..10. 假定一组记录的排序码为46;79;56;38;40;80;对其进行快速排序的一次划分的结果为____..三、简答题 1.假定有四个元素A;B;C;D依次进栈;进栈过程中允许出栈;试写出所有可能的出栈序列 2.一棵含有n个结点的k叉树;可能达到的最大深度和最小深度各为多少 3. 设有5000个无序的元素;希望用最快速度挑选出其中前10个最大的元素;在以下的排序方法中;采用哪种方法最好为什么快速排序;堆排序;基数排序一、选择题1. B 2. B 3. C 4. B 5．C 6．B 9．C 10．A 11．B 12. C 13. B 14.C 15. C 16. A 17. C 18. A 19. C二、填空题1.复杂度2．物理结构; 逻辑结构;算法; 原来的3．q-next; 4. 4;3 5. 前驱; 后续6．线性结构; 顺序结构7. 5 8. 5 ; 31 ;19 .. 9. 38 46 56 7940 84 ..10. 84;79;56;38;40;46 ..三、问答题 1.答：共有14种可能的出栈序列为：ABCD; ABDC; ACBD; ACDB; BACD; ADCB; BADC; BCAD;BCDA;BDCA;CBAD;CBDA;CDBA;DCBA 2. 答：显然能达到最大深度的是单支树其深度为n；深度最小的是完全k叉树..3. 答：用堆排序最好;因为堆排序不需要等整个排序结束就可挑出前10个最大元素;而快速排序和基数排序都需等待整个排序结束才能知道前10个最大元素..。

数据结构（本科）武汉理工大学在线作业一、判断(共计40分,每题2.5分)1、快速排序是排序算法中平均性能最好的一种排序。

（）A. 正确B. 错误答案:【A】2、调用一次深度优先遍历可以访问到图中的所有顶点。

（）A. 正确B. 错误答案:【B】3、对连通图进行深度优先遍历可以访问到该图中的所有顶点。

（）A. 正确B. 错误答案:【A】4、线性表中的所有元素都有一个前驱元素和后继元素。

（）A. 正确B. 错误答案:【B】5、设一棵二叉树的先序序列和后序序列，则能够唯一确定出该二叉树的形状。

（）A. 正确B. 错误答案:【B】6、先序遍历一棵二叉排序树得到的结点序列不一定是有序的序列。

（）A. 正确B. 错误答案:【A】7、不论线性表采用顺序存储结构还是链式存储结构，删除值为X的结点的时间复杂度均为O(n)。

（）A. 正确B. 错误答案:【A】8、满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树。

（）B. 错误答案:【A】9、子串“ABC”在主串“AABCABCD”中的位置为2。

( )A. 正确B. 错误答案:【A】10、非空的双向循环链表中任何结点的前驱指针均不为空。

（）A. 正确B. 错误答案:【A】11、分块查找的平均查找长度不仅与索引表的长度有关，而且与块的长度有关。

（）A. 正确B. 错误答案:【A】12、线性表的顺序存储结构比链式存储结构更好。

（）A. 正确B. 错误答案:【B】13、向二叉排序树中插入一个结点需要比较的次数可能大于该二叉树的高度。

（）A. 正确B. 错误答案:【B】14、层次遍历初始堆可以得到一个有序的序列。

（）A. 正确B. 错误答案:【B】15、冒泡排序在初始关键字序列为逆序的情况下执行的交换次数最多。

（）A. 正确B. 错误答案:【A】16、设初始记录关键字基本有序，则快速排序算法的时间复杂度为O(nlog2n)。

（）B. 错误答案:【B】二、单选(共计60分,每题2.5分)17、在二叉排序树中插入一个关键字值的平均时间复杂度为（）。

复习题集一判断题（×）1．线性表在物理存储空间中也一定是连续的。

（×）2．顺序存储方式只能用于存储线性结构。

（√）3．栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。

（√）4．两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。

（×）5．二叉树的度为2。

（√）6．若二叉树用二叉链表作存贮结构，则在n个结点的二叉树链表中只有n—1个非空指针域。

（×）7．二叉树中每个结点的两棵子树的高度差等于1。

（√）8．用二叉链表法存储包含n个结点的二叉树，结点的2n个指针区域中有n+1个为空指针。

（）9．在冒泡法排序中，关键值较小的元素总是向前移动，关键值较大的元素总是向后移动。

（）10．计算机处理的对象可以分为数据和非数据两大类。

（）11．数据的逻辑结构与各数据元素在计算机中如何存储有关。

（）12．算法必须用程序语言来书写。

（）13．判断某个算法是否容易阅读是算法分析的任务之一。

（）14．顺序表是一种有序的线性表。

（）15．分配给顺序表的内存单元地址必须是连续的。

（）16．栈和队列具有相同的逻辑特性。

（）18．树形结构中每个结点至多有一个前驱。

（）19．在树形结构中，处于同一层上的各结点之间都存在兄弟关系。

（）20．如果表示图的邻接矩阵是对称矩阵，则该图一定是无向图。

（）21．如果表示图的邻接矩阵是对称矩阵，则该图一定是有向图。

（）22．顺序查找方法只能在顺序存储结构上进行。

（）23．折半查找可以在有序的双向链表上进行。

（）24．满二叉树中不存在度为1的结点。

（）25．完全二叉树中的每个结点或者没有孩子或者有两个孩子。

（）26．对n个元素知心快速排序，在进行第一次分组时，排序码的比较次数总是n-1次。

（）27．在有向图中，各顶点的入度之和等于各顶点的出度之和。

一、选择题（）1. 在n个结点的顺序表中，算法的时间复杂度是O(1)的操作是：A) 访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n）C) 删除第i个结点（1≤i≤n）B) 在第i个结点后插入一个新结点（1≤i≤n）D) 将n个结点从小到大排序（C）2. 算法分析的目的是：A) 找出数据结构的合理性B) 研究算法中的输入和输出的关系C) 分析算法的效率以求改进D) 分析算法的易懂性和文档性（A）3. 算法分析的两个主要方面是：A) 空间复杂性和时间复杂性B) 正确性和简明性C) 可读性和文档性D) 数据复杂性和程序复杂性（B）4. 计算机算法必须具备输入、输出和等5个特性。

一、单选( 每题参考分值2.5分)1、系统的吞吐量指的是（）。

A.每天的数据输出量B.每秒执行的作业数C.每秒的数据处理量D.每日的数据输入量正确答案是【B】2、()指的是企业管理中必要的逻辑上相关的，为了完成某种管理功能的一组活动A.管理流程B.业务过程C.系统规划D.开发方法正确答案是【B】3、对某些特定对象而形成的同类记录的集合构成（）。

A.数据库B.文件C.文件系统D.数据结构正确答案是【B】4、电子商务中企业对企业的形式可称作（）。

A.B to BB.C to BC.G to BD.B to G正确答案是【A】5、U/C矩阵式用来进行（）的方法。

A系统分析B.系统规划C.子系统划分D.系统开发正确答案是【C】6、为便于系统重构，模块划分应（）A.大些B.适当C.尽量大D.尽量小正确答案是【B】7、数据（）。

A.就是信息B.经过解释成为信息C.必须经过加工才成为信息D.不经过加工也可以称作信息正确答案是【B】8、代码设计在（）阶段开始。

A.系统设计B.系统分析C.系统实施D.系统规划正确答案是【A】9、具有固定个体变动属性的数据应当存放在（）A.处理文件B.随机文件C.主文件D.周转文件正确答案是【D】10、淘宝网的电子商务模式是（）。

A.C2CB.B2BC.B2CD.B2G正确答案是【A】11、校验输入月份最大不超过12是属于（）。

A.视觉校验B.数据类型校验C.逻辑校验D.平衡校验正确答案是【C】12、管理信息系统的应用离不开一定的环境和条件，环境具体指的是（）。

A.组织所处的自然环境B.组织所处的社会环境C.组织内外各种因素的综合D.组织所处的自然环境和社会环境的综合正确答案是【C】13、防火墙可以是一种装在主机或路由器上的（）。

A.公钥B.软件C.杀毒软件D.秘钥正确答案是【B】14、关于商务智能技术，我们一般认为主要是（）。

A.数据加工技术和信息处理技术B.人工智能技术和机器学习技术C.数据挖掘技术和在线分析技术D.知识转化技术和知识传播技术正确答案是【C】15、（）是管理信息系统环境中最重要的因素之一，决定着管理信息系统应用的目标和规模。

数据结构复习题一、单项选择题1.不带头结点的单链表head为空的判断条件是( )。

A.head==NULLB.head->next==NULLC.head->next==headD.head!=NULL2.链表不具有的特点是( )。

A.可随机访问任一元素B.插入删除不需要移动元素C.不必事先估计存储空间D.所需空间与线性表长度成正比3. 设输入序列为A,B,C,D,借助一个栈不可以得到的输出序列是( )。

A. A,B,C,DB. A,C,D,BC. D,C,B,AD. D,A,B,C4.栈和队列都是（）。

A.顺序存储的线性表B.链式存储的线性表C.限制存取点的线性结构D.限制存取点的非线性结构5. 串的长度是（）。

A.串中不同字符的个数B. 串中不同字母的个数C.串中所含字符的个数且字符个数大于0D.串中所含字符的个数6. 栈和队列的主要区别在于（）。

A.它们的逻辑结构不一样B.它们的存储结构不一样C.所包含的运算个数不一样D.插入删除运算的限定不一样7.从具有n个结点的单链表中查找值等于x的结点时，在查找成功的情况下，平均需比较（）个结点。

A.nB.n/2C.(n-1)/2D.(n+1)/28.线性表是具有n个（）的有限序列。

A. 表元素B. 字符C. 数据元素D. 信息项9.某二叉树的前序和后序序列正好相同，则该二叉树一定是（）的二叉树。

A. 空或只有一个结点B. 高度等于其结点数C. 任一结点无左孩子D. 任一结点无右孩子10.下列排序算法中,第一趟排序完毕后,其最大或最小元素一定在其最终位置上的算法是（）。

A. 归并排序B. 直接插入排序C. 快速排序D. 冒泡排序11.深度为n的二叉树中所含叶子结点的个数最多为（）个。

A.2nB.nC.2n-1D.2n-112.某数组第一个元素的存储地址为100，每个元素的长度为2，则第五个元素的地址是（）。

A.110B.108C.100D.12013.串是（）。

试题标准答案及评分标准用纸| 课程名称数据结构（B卷）一、填空题（每空2分，共20分）1．逻辑结构存储结构运算2. 单链表3. 队尾队首4. 顺序表5．直接插入排序、简单选择排序、起泡排序、快速排序、基数排序、归并排序、堆排序中任选2种6. 2h-1二、单选题（每小题1分，共10分）1.B2.C3. B4.C5. A6.C7.A8. C9. D 10.B三、问答题（每小题5分，共10分）1. 算法是解决给定问题的一种方法（策略），即为解决某一特定问题而由若干条指令组成的有穷序列。

（2分）算法分析的目的是研究算法执行时间随问题规模变化的情况（问题规模是一个和输入有关的量，如n），提高算法的效率。

（1分）算法分析主要涉及：时间复杂度和空间复杂度。

（2分）2.线性表（a1,a2,……,an）中每个元素都具有相同的类型，它有两种存储结构：顺序表和链表。

广义表（d1,d2,……,dn）中每个元素可以是原子，也可以是子表。

可以将广义表看作是线性表的推广。

由于原子和子表的类型不同，所以只能用链式存储结构。

四、图表计算题（每小题8分，共40分）3．构造的哈夫曼树如图所示：4．第一趟： 060,820,200,150,331,001,761,044,004,125,545,806,308,029 第二趟： 200,001,004,806,308,820,125,029,331,044,545,150,060,761 第三趟： 001,004,029,044,060,125,150,200,308,331,545,761,806,820 5．其拓扑序列如下：l 2 4 5 8 9 10 3 7 6 ll 12五、算法设计题（20分）略。

数据结构（本科）武汉理工大学在线作业一、判断(共计40分,每题2.5分)1、快速排序是排序算法中平均性能最好的一种排序。

（）A. 正确B. 错误答案:【A】2、调用一次深度优先遍历可以访问到图中的所有顶点。

（）A. 正确B. 错误答案:【B】3、对连通图进行深度优先遍历可以访问到该图中的所有顶点。

（）A. 正确B. 错误答案:【A】4、线性表中的所有元素都有一个前驱元素和后继元素。

（）A. 正确B. 错误答案:【B】5、设一棵二叉树的先序序列和后序序列，则能够唯一确定出该二叉树的形状。

（）A. 正确B. 错误答案:【B】6、先序遍历一棵二叉排序树得到的结点序列不一定是有序的序列。

（）A. 正确B. 错误答案:【A】7、不论线性表采用顺序存储结构还是链式存储结构，删除值为X的结点的时间复杂度均为O(n)。

（）A. 正确B. 错误答案:【A】8、满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树。

（）B. 错误答案:【A】9、子串“ABC”在主串“AABCABCD”中的位置为2。

( )A. 正确B. 错误答案:【A】10、非空的双向循环链表中任何结点的前驱指针均不为空。

（）A. 正确B. 错误答案:【A】11、分块查找的平均查找长度不仅与索引表的长度有关，而且与块的长度有关。

（）A. 正确B. 错误答案:【A】12、线性表的顺序存储结构比链式存储结构更好。

（）A. 正确B. 错误答案:【B】13、向二叉排序树中插入一个结点需要比较的次数可能大于该二叉树的高度。

（）A. 正确B. 错误答案:【B】14、层次遍历初始堆可以得到一个有序的序列。

（）A. 正确B. 错误答案:【B】15、冒泡排序在初始关键字序列为逆序的情况下执行的交换次数最多。

（）A. 正确B. 错误答案:【A】16、设初始记录关键字基本有序，则快速排序算法的时间复杂度为O(nlog2n)。

（）B. 错误答案:【B】二、单选(共计60分,每题2.5分)17、在二叉排序树中插入一个关键字值的平均时间复杂度为（）。