2014年华中科技大学软件学院数据结构与算法分析考研真题(回忆版)及部分参考答案【圣才出品】

《数据结构》试卷 (A 卷)2010 —2011 年度第二学期计算机学院 班级______ 学号___________ 姓名_________考试时间：2011年 月 日 考试形式：闭卷一、单项选择题(从下列各题四个备选答案中选出一个正确答案,将其代号(A,B,C,D)写在下表中,每小题1分,共10分) 1．对于栈的进栈和出栈运算，采用______存储结构时运算效率最高。

A ．单链表B ．容量足够大的顺序表C ．单向循环链表D ．双向循环链表2．链式队列和顺序队列比较，具有_____这个优势。

A ．进队操作方便B ．出队操作方便C ．通常不会出现满队列情况D ．求队列元素个数方便 3．下列关于串的叙述中，正确的是_____。

A ．2个串的长度相等，则2个串相等B ．空串至少包一个空格C ．替换操作可以实现字符的删除D ．一个串的长度至少是1 4．二叉树在线索化后，下列问题中相对难解决的是____。

A ．先根线索二叉树中求先根后继B ．中根线索二叉树中求中根前趋C ．中根线索二叉树中求中根后继D ．后根线索二叉树中求后根后继5．对序列（30，26，18，16，5，66）进行2遍 ________排序后得到序列（5，16，18，26，30，66）。

A ．选择B ．冒泡C ．插入D ．归并6．在下列排序算法中，_______算法可能出现如下情况：在最后一趟排序之前，所有元素均不在其最终的位置上。

A ．堆排序B ．快速排序C ．冒泡排序D ．插入排序 7．由4个结点可以组成______棵不同形态的二叉树。

A ．10B ．12C ．14D ．168．对包含n 个元素的散列表进行检索，平均查找长度为____。

A ．O(logn) B ．O(n) C ．O(nlogn) D ．不直接依赖于n 9．广义表 ((a,(b),c),((),(d)),(((((e)),f))),())的长度是____。

A ．2B ．3C ．4D ．510．对某无向图进行一次深度优先搜索遍历，如果能访问到所有的顶点，则该无向图一定是________。

今年是华科853经济学综合第一年改革，加了计量经济学。

作为刚刚考过的，我觉得或许我对于试题的回忆版能够给15年考研的学弟学妹们一些帮助吧。

毕竟与往年真题都不一样。

从整体上看今年计算题的分值加大，有55分，三大题都是计量经济学的计算题，是对于计量模型的一些计算，还有对于用于计量模型数值的含义要清楚，不然没办法下手。

这就要求对于模型能够看懂，并会解释其中的数值含义。

关于常用的对于多重共线性，异方差，自相关还有设定误差的检验的一些模型要清楚掌握。

今年就考到了white检验及它的分布。

下面是我对试题的大致回忆，有些题目不是记得很清楚了：一、选择题，共10题，每题2分。

考察了凸性偏好的性质，索洛增长模型，温和通货膨胀的好处，生产可能性曲线、流动性陷阱（在存在流动性陷阱的时候，ZF的哪些措施能够引起产出的增加）二、判断题，共5题，每题5分1、厂商获得最大利润的条件是mr=mc2、不记得了后面3题是计量判断题，主要是问当模型存在设定偏误或是存在自相关时是否所估计量不再是无偏的或是无效的了。

三、计算题1、考的是罗宾逊那个模型，前两年有考过类似的题目，休息L个小时，消费C单位椰子，可获得的效用是U=L^2*C，劳动T个小时，获得T^(2/3)单位椰子，问一天24个小时，工作多长时间可以获得最大效用（10分）2、给出了一个菲利普斯曲线的式子，根据这个式子，给出通货膨胀率的变化，求周期性失业率和牺牲率。

（10分）后面三大题都是计量经济学的模型计算题，对于课本后面的这样类型的题目要注意理解，每一题都有几个小问，有考到求β的显著性检验估计量的值，有根据可决系数求可修正的可决系数。

有些题目是考察对给出模型式子的理解出的题目。

四、论述题4题共40分1、在完全竞争市场下，市场均衡价格与厂商的成本之间有什么关系2、斗鸡博弈的主要特点有哪些，并说说序贯博弈和斗鸡博弈最后的结果是什么3、考察小型开放经济条件下，减税政策对于一国汇率和产出的影响，分浮动汇率和固定汇率考虑。

2014考研统考考研统考计算机基础综合真题解析计算机基础综合真题解析【回忆版】一、单项选择题单项选择题：：第1～40小题小题，，每小题2分，共80分。

下列每题给出的四个选项中下列每题给出的四个选项中，，只有一个选项是最符合题目要求的只有一个选项是最符合题目要求的。

2、假设栈初始为空，将中缀表达式a/b-(c*d+e*f)/g 转化为等价后缀表达式过程中，当扫描到f 时，栈中的元素依次为：A 、+（*-B 、+（-*C 、/+(*-*D 、/+-*涉及考点涉及考点：：考察中缀和后缀表达式的转化，并考察栈这种数据结构4、如下图二叉树进行中序线索化，则元素X 的左、右线索指向的元素为A 、 ecB 、 eaC 、 dcD 、 ba涉及考点涉及考点：：中序线索化二叉树，找出左右线索5、森林F 转化为对应二叉树T ，则F 的叶结点个数是（）A 、T 的叶结点个数B 、T 中度为1的结点个数C 、T 的左孩子指向为空的个数D 、T 的右孩子指向为空的个数涉及考点涉及考点：：森林转化为二叉树做法：第一，断开除最左孩子的孩子节点，第二，连接孩子节点中各兄弟节点，第三，将树顺时针旋转45度第四，同理处理其他树。

第五，将所有树按照先后顺序依次作为右子树连接。

6、5个元素有4种编码方案，下列不是前缀编码的是A 、01,0000,0001,001,1B 、011,000,001,010,1C 、000,001,010,011,100D 、0,100,110,1110,1100涉及考点涉及考点：：字符的前缀编码8、用哈希（散列）方法处理冲突（碰撞）时可能发生堆积（聚集)现象，则下列会直接受到堆积现象影响的是A 、存储效率B 、散列函数C 、载运因子D 、平均查找长度涉及考点涉及考点：：哈希（三列）方法处理冲突堆积现象影响的因素9、存一棵具有15个关键词的4阶B 树，则含有关键词的结点可能有A 、5B 、6C 、10D 、15涉及考点涉及考点：：B 树10、用希尔排序法，对一列数据序列排序时，若第一次排序结果为：9,1,4,13,7,8,20,23,15，则该排序可能的间隔是：A 、2B 、3C 、4D 、5涉及考点涉及考点：：希尔排序法中的间隔11、下列最不可能是快速排序第二轮的结果是A 、2,3,5,4,6,7,9B 、2,7,5,6,4,3,9C 、3,2,5,4,7,6,9D 、4,2,3,5,7,6,9涉及考点涉及考点：：快速排序法12、程序P 在装置M 执行时间为20秒，编译优化后，P 执行的指令数是以前的70%，但CPI 为以前的1.2倍，则现在P 在M 上的执行时间为A 、8.4秒B 、11.7秒C 、14.0秒D 、16.8秒涉及考点涉及考点：：cpu 计算时间的计算方法。

数据结构考研真题与答案解析【数据结构考研真题与答案解析】数据结构是计算机科学与技术中的重要学科，也是考研中不可或缺的一部分。

在考研中，掌握数据结构的相关知识对于顺利通过考试至关重要。

本文将为大家介绍一些历年考研真题，并对答案进行解析，希望对大家备考有所帮助。

一、堆排序相关问题1. 2014年考研真题（题目描述）给定n个整数的序列S，其中$n \leq 10^6$且没有相同元素，并且给定另外的一个元素x，输出S中小于x的最大的数，如果不存在则输出“-1”。

（解析）这是一道关于堆排序的问题。

我们可以利用大顶堆来解决这个问题。

首先建立一个大顶堆，然后依次将序列S中的元素插入到堆中。

在插入的过程中，我们可以通过比较当前元素和x的大小，找到小于x的最大的数。

最后输出即可。

若不存在小于x的元素，则输出“-1”。

二、图的遍历问题2. 2016年考研真题（题目描述）对于一个无向图G，设计一个算法，判断图G是否连通，并给出详细的算法描述和复杂度分析。

（解析）对于这个问题，我们可以使用深度优先搜索（DFS）或广度优先搜索（BFS）来解决。

我们可以从图中的任意一个节点开始进行深度或广度遍历，然后标记遍历过的节点。

最后判断所有的节点是否都被遍历到，若是，则图G是连通的，否则不连通。

若使用邻接表表示图，则DFS和BFS的时间复杂度均为O(|V|+|E|)，其中|V|和|E|分别代表图中的节点数和边数。

三、二叉搜索树相关问题3. 2018年考研真题（题目描述）给定一个二叉搜索树，请设计一个算法，找出其中第k大的节点。

（解析）对于这个问题，我们可以利用二叉搜索树的性质。

由于二叉搜索树的中序遍历结果是有序的，我们可以进行中序遍历，并将遍历结果保存到一个有序数组中。

然后根据数组中第k个位置的元素找到对应的节点即可。

算法的时间复杂度为O(n)，其中n为二叉搜索树中节点的个数。

四、哈夫曼编码问题4. 2017年考研真题（题目描述）给定一段文字，编写一个算法，根据字符出现的频率构建哈夫曼编码。

《数据结构》试卷 (A 卷)2010 —2011 年度第二学期计算机学院 班级______ 学号___________ 姓名_________考试时间：2011年 月 日 考试形式：闭卷一、单项选择题(从下列各题四个备选答案中选出一个正确答案,将其代号(A,B,C,D)写在下表中,每小题1分,共10分) 1．对于栈的进栈和出栈运算，采用______存储结构时运算效率最高。

A ．单链表B ．容量足够大的顺序表C ．单向循环链表D ．双向循环链表2．链式队列和顺序队列比较，具有_____这个优势。

A ．进队操作方便B ．出队操作方便C ．通常不会出现满队列情况D ．求队列元素个数方便 3．下列关于串的叙述中，正确的是_____。

A ．2个串的长度相等，则2个串相等B ．空串至少包一个空格C ．替换操作可以实现字符的删除D ．一个串的长度至少是1 4．二叉树在线索化后，下列问题中相对难解决的是____。

A ．先根线索二叉树中求先根后继B ．中根线索二叉树中求中根前趋C ．中根线索二叉树中求中根后继D ．后根线索二叉树中求后根后继5．对序列（30，26，18，16，5，66）进行2遍 ________排序后得到序列（5，16，18，26，30，66）。

A ．选择B ．冒泡C ．插入D ．归并6．在下列排序算法中，_______算法可能出现如下情况：在最后一趟排序之前，所有元素均不在其最终的位置上。

A ．堆排序B ．快速排序C ．冒泡排序D ．插入排序 7．由4个结点可以组成______棵不同形态的二叉树。

A ．10B ．12C ．14D ．168．对包含n 个元素的散列表进行检索，平均查找长度为____。

A ．O(logn) B ．O(n) C ．O(nlogn) D ．不直接依赖于n 9．广义表 ((a,(b),c),((),(d)),(((((e)),f))),())的长度是____。

A ．2B ．3C ．4D ．510．对某无向图进行一次深度优先搜索遍历，如果能访问到所有的顶点，则该无向图一定是________。

数据结构与算法题库（含参考答案）一、单选题（共100题，每题1分，共100分）1、在一次校园活动中拍摄了很多数码照片，现需将这些照片整理到一个PowerPoint 演示文稿中，快速制作的最优操作方法是：A、创建一个 PowerPoint 相册文件。

B、创建一个 PowerPoint 演示文稿，然后批量插入图片。

C、创建一个 PowerPoint 演示文稿，然后在每页幻灯片中插入图片。

D、在文件夹中选中所有照片，然后单击鼠标右键直接发送到PowerPoint 演示文稿中。

正确答案：A2、下面对“对象”概念描述错误的是A、对象不具有封装性B、对象是属性和方法的封装体C、对象间的通信是靠消息传递D、一个对象是其对应类的实例正确答案：A3、设栈与队列初始状态为空。

首先A,B,C,D,E依次入栈，再F,G,H,I,J 依次入队；然后依次出队至队空，再依次出栈至栈空。

则输出序列为A、F,G,H,I,J,E,D,C,B,AB、E,D,C,B,A,J,I,H,G,FC、F,G,H,I,J,A,B,C,D,E,D、E,D,C,B,A,F,G,H,I,J正确答案：A4、设表的长度为 20。

则在最坏情况下，冒泡排序的比较次数为A、20B、19C、90D、190正确答案：D5、设二叉树的前序序列为 ABDEGHCFIJ，中序序列为 DBGEHACIFJ。

则后序序列为A、DGHEBIJFCAB、JIHGFEDCBAC、GHIJDEFBCAD、ABCDEFGHIJ正确答案：A6、Excel工作表B列保存了11位手机号码信息，为了保护个人隐私，需将手机号码的后 4 位均用“*”表示，以 B2 单元格为例，最优的操作方法是：A、=REPLACE(B2,7,4,"****")B、=REPLACE(B2,8,4,"****")C、=MID(B2,7,4,"****")D、=MID(B2,8,4,"****")第 10 组正确答案：B7、小金从网站上查到了最近一次全国人口普查的数据表格，他准备将这份表格中的数据引用到 Excel 中以便进一步分析，最优的操作方法是：A、通过 Excel 中的“自网站获取外部数据”功能，直接将网页上的表格导入到 Excel 工作表中。

2014年的上机题是两道原题，第一题是按要求输出：在三位整数（100至999）中寻找符合条件的整数并依次从小到大存入数组中；他既是完全平方数，又是两位数字相同，例如144，676等第二题是任意输入一串字符把下标为奇数的小写字母(从0开始编号)转换为大写字母.专业笔试部分很多题目都是2008年的那份专业笔试卷子里面的原题其中最后两个简答题：（1）说一说结构化的C语言跟面向对象的C++语言之间的相同点与差异点（15分）（2）已知先序和中序遍历，能否确定一个序列，简要说明原因并举例。

（3分）英语听力（10分）14年的听力我没有去翻看，反正是考的近两年的CET—4的section C 的一篇，原题，没有任何改动，所以建议如果通过初试，把最近5年的四六级听力的section C部分都把它看看，往年都是出的四六级里面的secton C部分的原题！这复试10分很重要，你如果准备好了拿满分容易！英语面试英语面试是两个老师。

每个人抽纸条抽选topic，其中有一两个会比较难，就像我抽到的是让你用英语描述你大学期间做过哪些项目，并介绍其中的一个。

其它的都比较简单，有最喜欢的节日、周末怎么度过、家乡的天气、自己的梦想之类的。

专业面试今年专业面试个人感觉很轻松，就是跟你聊聊，为什么选择华科软工，很少会有涉及到专业方面的提问，这个环节你要放轻松，老师们都是很好的！复试总成绩计算方法：初试成绩/5*0.6+复试成绩*0.4 （500/5*0.6+100*0.4=100）所以复试10分换算成初试成绩10*0.4=4 4/0.6*5=33.3这相当于复试一分等于初试的3.3分，所以复试里面每一分都很重要！说说上机环境，机房每台电脑里面都有VS，所以会用VS的就不需担心，但是对于有些中用过VC的，那就要注意了，不是每台电脑上都有，所以这个要提前做好准备！。

2014年下半年系统架构师下午真题案例分析试题一:请详细阅读有关Web应用架构设计方面的说明，在答题纸上回答问题1至问题3。

【说明】某软件公司开发运维了一个社交网站系统，该系统基于开源软件平台LAMP(Linux+Apache+MySQL+PHP)构建，运行一段时间以来，随着用户数量及访问量的增加，系统在Web服务器负载、磁盘I/O等方面出现了明显瓶颈，已不能满足大量客户端并发访问的要求，因此公司成立了专门的项目组，拟对系统架构进行调整以提高系统并发处理能力。

目前系统采用了传统的三层结构，系统架构如下图所示。

【问题1】（10分）针对目前出现的Web服务器负载过大问题，项目组决定在客户端与中间层Web服务器之间引入负载均衡器，通过中间层Web服务器集群来提高Web请求的并发处理能力。

在讨论拟采用的负载均衡机制时，王工提出采用基于DNS的负载均衡机制，而李工则认为应采用基于反向代理的负载均衡机制，项目组经过讨论，最终确定采用李工提出的方案。

请用200字以内的文字，分别简要说明两个机制的基本原理；并从系统执行效率、安全性及简易性等方面将两种机制进行对比，将对比结果填入下表中。

【问题2】（7分）针对并发数据库访问所带来的磁盘I/O瓶颈问题，项目组决定在数据层引入数据库扩展机制。

经过调研得知系统数据库中存储的主要数据为以用户标识为索引的社交网络数据，且系统运行时发生的大部分数据库操作为查询操作。

经过讨论，项目组决定引入数据库分区和MySQL主从复制两种扩展机制。

数据库分区可采用水平分区和垂直分区两种方式，请用350字以内的文字说明在本系统中应采用哪种方式及其原因，并分析引入主从复制机制给系统带来的好处。

【问题3】（8分）为进一步提高数据库访问效率，项目组决定在中间层与数据层之间引入缓存机制。

赵工开始提出可直接使用MySQL的查询缓存(query cache)机制，但项目组经过分析好友动态显示等典型业务的操作需求，同时考虑已引入的数据库扩展机制，认为查询缓存尚不能很好地提升系统的查询操作效率，项目组最终决定在中间层与数据层之间引入Memcached分布式缓存机制。

华科历年上机题汇总（欢迎补全）2014华科机试回忆1.超素数就是这样的数,比如2333，2是素数，23是素数，233是素数，2333是素数，找出所有的四位超素数。

每行输出六个，数之间空格隔开。

（我的做法是先开个10000的数组，找出每个是素数的数组值为1,否则为0，对于每个四位数，分别看这几位是否都是素数即可,注意1不是素数）2.两个二进制数加减乘除，short型的，十六位，比如101 100 +，输出1001，也可把前几位0输出。

（我刚开始想用大数运算来计算，发现比较麻烦，就把这两个数转化为十进制，然后运算，再转化为short型的二进制（转化为二进制时我的负数形式估计考虑错了））。

3.判断一个整型变量是否正确，比如02是八进制，0x2是十六进制，12是十进制，只有这三种进制判断。

前面的0是零。

（我判断时将八进制和十六进制的负数形式搞错了，以为这两种也是前面加个负号（比如-01，-0x1）的，其他的都能判断出来，三个大if 语句就行了）。

大致就只能想出这些了，建议你们找找图片版的，其他同学应该已经上传了。

可以看出今年的试题还是很基础的，没有很复杂的算法。

算法一定要注释，首先说出自己的大致想法。

当时时间比较急，我也没细想，做的题想法也不一定好，反正能先运行再说。

2013华科机试试题回忆版1.素数就是不能被等分的数，如3，5,7等。

一个数n是素数，若n+2也是素数，则，这两个数是孪生素数。

找不超过整数m（m在5到10000之间）的最大孪生素数。

2.回旋矩阵：如5的回旋矩阵是1 2 3 4 516 17 18 19 615 24 25 20 714 23 22 21 813 12 11 10 9输入一个n，求他的回旋矩阵。

3.求一个字符串的最右最长回文子串。

字符串包括字符和标点，空格可忽略。

如abba是回文a bb a也是回文。

你这回忆不完整啊，第三题是考虑回文子串的时候要忽略掉标点符号，打印输出的时候要再加上->12上机按照要求是可以使用VC,TC和CodeBlocks环境。

2014年上半年上午软件设计师考试试题-答案与解析一、单项选择题（共75分，每题1分。

每题备选项中，只有1个最符合题意）●第1题.在CPU中，常用来为ALU执行算术逻辑运算提供数据并暂存运算结果的寄存器是（1）。

A.程序计数器B.状态寄存器C.通用寄存器D.累加寄存器【参考答案】D【答案解析】CPU中有一些重要的寄存器，程序计数器（PC）用于存放指令的地址。

当程序顺序执行时，每取出一条指令，PC内容自动增加一个值，指向下一条要取的指令，当程序出现转移时，则将转移地址送入PC，然后由PC给出新的指令地址。

状态寄行器用于记录运算中产生的标志信息。

状态寄存器中的每一位单独使用，成为标志位。

标志位的取值反映了ALU当前的工作状态，可以作为条件转移指令的转移条件。

典型的标志位有以下几种：进位标志位（C）、零标志位（Z）、符号标志位（S）、溢出标志位（V）、奇偶标志位（P）。

通用寄存器组是CPU中的一组工作寄存器，运算时用于暂存操作数或地址。

在程序中使用通用寄存器可以减少访问内存的次数，提高运算速度。

累加器（accumulator）是一个数据寄存器，在运算过程中暂时存放操作数和中间运算结果，不能用于长时间地保存一个数据。

●第2题.某机器字长为n，最高位是符号位，其定点整数的最大值为（2）。

A.2n-1B.2n-1-1C.2nD.2n-1【参考答案】B【答案解析】机器字长为n，最高位为符号位，则剩余的n-1位用来表示数值，其最大值是这n-1位都为1，也就是2n-1-1。

●第3题.海明码利用奇偶性检错和纠错，通过在n个数据位之间插入k个校验位，扩大数据编码的码距。

若n=48，则k应为（3）。

A.4B.5C.6D.7【参考答案】C【答案解析】设数据位是n位，校验位是k位，则n和k必须满足以下关系：2k-1≥n+k。

若n=48，则k为6时可满足26-1≥48+6。

海明码的编码规则如下。

设k个校验位为Pk，Pk-1，…，P1，n个数据位为Dn-1，Dn-2，…，D1，D0。

3371 博士研究生《数据结构及算法分析》科目入学考试大纲第一部分考试说明一、考试性质《数据结构》和《算法分析》是计算机专业的专业基础课。

《数据结构及算法分析》是华中科技大学计算机软件与理论专业博士研究生入学考试的一个综合考试科目。

它的评价标准是，高等学校本学科优秀毕业生能达到的及格或及格以上水平，以保证被录取者具有基本的计算机专业理论基础，以利于计算机软件与理论专业各导师择优选拔。

考试对象为参加博士研究生入学考试的应届或非应届硕士毕业生和具有同等学力的在职人员。

二、考试的学科范围1.数据结构各种基本类型的数据结构的概念、特征、操作、存储表示和基本应用；各类查找表的查找方法，基本的内排序和外排序方法；文件在外存储器中的表示方法；相关算法的C/C++描述与分析。

2.算法分析算法的基本概念,分治策略，贪心策略，动态规划，基本检索与周游方法。

三、评价目标1.数据结构在考察数据结构的基本概念、基本方法和相关算法的基础上，注重考察综合应用的能力，即分析和解决实际问题的能力。

2.算法分析掌握一定的算法分析能力, 掌握算法设计的基本观点和基本方法, 能正确地选用常用的非数值计算算法, 能站在算法设计策略的高度上设计算法。

具体要求见第二部分“考查要点”。

四、考试形式与试卷结构1.答卷方式：闭卷，笔试。

2.答题时间：180分钟。

3.考查内容及其考查比例基本概念、基本方法约占40%～50%；综合应用、算法设计(程序设计)与分析约占60%～50%。

4.试卷结构与考试题型(1)单项选择题,多项选择题: 约20%(2)填空题，简答题，应用题: 约35%(3)算法设计题, 算法分析题: 约35%(4)其它题型: 约10%五、参考书目1.严蔚敏等，数据结构(C语言版)，清华大学出版社2.余祥宣崔国华邹海明，计算机算法基础(前五章)，华中理工大学出版社,20003.Horowitz,S Sahni,Fundamentals of Computer Algorithms.New York: Computer Science Press,1978第二部分考查要点一、数据结构(约60%)1.数据结构和算法C/C++描述。

2013-2014《数据结构》期末考试笔试样题一、单项选择题（每小题2分，共16分）1．若将数据结构形式定义为二元组(K，R)，其中K是数据元素的有限集合，则R是K上（）A．操作的有限集合B．映象的有限集合C．类型的有限集合D．关系的有限集合2．在头指针为head且表长大于1的单循环链表中，指针p指向表中某个结点，若p->next->next=head，则（）A．p指向头结点B．p指向尾结点C．*P的直接后继是尾结点D．*p的直接后继是头结点3．在具有n个结点的有序单链表中插入一个新结点并使链表仍然有序的时间复杂度是（）A．O(1) B．O(n) C．O(nlogn) D．O(n2)4．队列和栈的主要区别是（）A．逻辑结构不同B．存储结构不同C．所包含的运算个数不同D．限定插入和删除的位置不同5．若进栈序列为a,b,c，则通过入出栈操作可能得到的a,b,c的不同排列个数为（）A．4 B．5 C．6 D．76．一棵含18个结点的二叉树的高度至少为( )A．3 B．4 C．5 D．67．在一个带权连通图G中，权值最小的边一定包含在G的（）A．最小生成树中B．深度优先生成树中C．广度优先生成树中D．深度优先生成森林中8．已知一组关键字为{25,48,36,72,79,82,23,40,16,35}，其中每相邻两个数为有序子序列。

对这些子序列进行一趟长度为2的两两归并的结果是( )A．{25,36,48,72,23,40,79,82,16,35}B．{25,36,48,72,16,23,40,79,82,35}C．{25,36,48,72,16,23,35,40,79,82}D．{16,23,25,35,36,40,48,72,79,82}二、算法阅读题（每小题8分，共16分）1．带头结点的单链表存储结构定义如下：typedef struct node{ int data;struct node *next;}linknode;typedef linknode *linklist;阅读算法fun(linklist head)，回答：（1）该算法的主要功能是什么？（2）对如下所示的单链表head，画出执行fun(head)单链表的状态。

软件体系结构试卷一、填空题（每空1分，共30分）1.系统的质量属性有多种，请列举其中六种：可用性、可修改性、性能、安全、可测试性、易用性、可移植性、可重用、可集成（任选六个）2.构架战术是：那些影响质量属性的设计决策。

3.构架编档的基本原则是：从读者的角度出发来编写。

4.构架驱动的因素包括：功能、质量、商业属性。

5.构架评审的六个优点是：财务上的收益、强制为评审做的准备、捕获构架设计的基本思想、在早期检测中发现问题、验证需求、改进构架。

6.构架本身的质量属性包括：概念完整性、正确性与完整性、可构建性。

7.构架的商业属性包括：上市时间、成本和收益、所希望统生命周期的长短、目标市场、推行计划、与老系统的集成。

8.构架样式有多种，其中四种是：以数据为中心、数据流、虚拟机、调用返回、独立组件、异构（任选其中四个）二、名词解释（每小题5分，共10分）1.软件架构答：是系统的一个或多个结构，它们由软件组件（元素）、这些组件的外部可见属性以及组件之间的关系组成。

组件的外部可见属性是指其它组件对该组件所做的假设。

2.软件架构商业周期（用画图形式表示）三、对错题（每小题2分，共10分）1.软件构架可以由几名设计师共同完成。

（错）2.设计师对系统的质量属性应平等看待，在系统设计中全部予以解决。

（错）3.构架的文档应该完备，并使所有风险承担者都能看懂。

（对）4.构架的设计应该有助于增量式实现。

（对）5.应将产生数据的模块和使用数据的模块分离开。

（对）四、简答题（每小题5分，共10分）1.为什么要分析软件构架？答：（1）因为构架非常重要，它是风险承担者交流的平台、是早期设计决策的体现，是可传递的系统抽象（构架级重用）。

（2）系统的质量属性不可能在系统实现的最后阶段追加上去，必须在设计之初就考虑到。

2.请说明架构模式、参考模型和参考构架之间的联系与区别。

答：构架模式是对组件和关系类型以及一组对其使用方式的限制的描述。

参考模型是一种考虑数据流的功能划分。

2014年计算机学科专业基础综合试题参考答案一、单项选择题（一）单选题答案1．C2．B3． A 4．D5．C6．D7．D8．D9．D10．B11．C12．D13．C14．A 15．A 16．D17．A 18．C19．C20．C21．D22．B23．A 24．B25．D26．A 27．A 28．C29．B30．A 31．C32．D33．C 34．B 35．D 36．C 37．B 38．A 39．B 40．D （二）单选题答案解析1．内层循环条件j<=n与外层循环的变量无关，每次循环j自增1，每次内层循环都执行n次。

外层循环条件为k<=n，增量定义为k*=2，可知循环次数为2k<=n，即k<=log2n。

所以内层循环的时间复杂度是O(n)，外层循环的时间复杂度是O(log2n)。

对于嵌套循环，根据乘法规则可知，该段程序的时间复杂度T(n)=T1(n)*T2(n)=O(n)*O(log2n)=O(nlog2n)。

2．将中缀表达式转换为后缀表达式的算法思想如下：从左向右开始扫描中缀表达式；遇到数字时，加入后缀表达式；遇到运算符时：a.若为'('，入栈；b.若为')'，则依次把栈中的的运算符加入后缀表达式中，直到出现'('，从栈中删除'(' ；c.若为除括号外的其他运算符，当其优先级高于除'('以外的栈顶运算符时，直接入栈。

否则从栈顶开始，依次弹出比当前处理的运算符优先级高和优先级相等的运算符，直到一个比它优先级低的或者遇到了一个左括号为止。

在此，再给出中缀表达式转换为前缀或后缀表达式的一种手工做法，以上面给出的中缀表达式为例：第一步：按照运算符的优先级对所有的运算单位加括号。

式子变成了：((a/b)+(((c*d)-(e*f))/g))第二步：转换为前缀或后缀表达式。

前缀：把运算符号移动到对应的括号前面，则变成了：+(/(ab)/(-(*(cd)*(ef))g))把括号去掉：+/ab/-*cd*efg前缀式子出现。

2014年华中科技大学数据结构与算法分析考研试题（部分）
一、填空题：
1、写出数据结构的四种基本逻辑结构
2、写出算法的四种特性
3、一个栈中有六个数字，要求对其进行重新排序，求堆栈的最小容量
4、求出一串数字的非平凡子串个数
5、求一平衡二叉树的成功查找长度和不成功查找长度
….
二、选择题：（略）
三、分析题：
1、给出一个算法过程，要求列出它的开销公式并解出开销函数
2、根据题意画出Huffman前缀码树并求出编码长度
3、该题关于KRUSKAL(V，E，w)的最小生成树算法，由给出的具体算法写出其中元素A
的变化过程，并求出最小生成树的权
4、由题中给出的网络流图求剩余流图，在图中标出最小切割，解出S→t的最大网络流
5、给出一个图，从a开始深度优先搜索，算出每个节点发现和结束的时刻d/f，根据
搜索结果标出图上边的类型
四、算法题：
1、①3②
B
A 4
④7③
根据最短路径延伸算法给出递归表达式，将全成对最短路径填写到题目中的4X4
表格中，并写出表格中某一阴影指定位置的路径
2、证明：A∪(u，v)是图G最小生成树的子集
3、权重函数f，动态划归，写递推式，用伪码描述算法。