武汉科技大学数据结构(C语言版)(B卷)2013考研专业课真题

10级软件工程专业《数据结构》试题B卷答案及评分细则一、选择题（每小题3分，共30分，选错不给分，选对给3分）1,C 2,A 3,D 4,C 5,B 6,C 7,B 8,B 9,A 10,A二、填空题（每空2分，共20分，填对给2分，填错不给分）1,2 4；2，SXSSXXSX3,-+A*BC/DE4,128 75,存储位置指针6，任意若干连续字符序列7，相同类型数据元素三、应用题1 解：其步骤为i1=index(S,S1,1)………………………………………………(2分)i2=index(S,S2,1)+3………………………………………………(2分)sub1=substr(S,i1,length(S)-i1+1) …………………………………(2分)sub2=substr(S,i2,length(S)-i2+1…………………………………………(2分) S3=concat(sub1, sub2) ………………………………………………(2分)2 解本题即为构造最小生成树，按照最小生成树的构造方法，构造如下：303解：其拓扑排序序列为152634；156234；152364；512634；516234；512364；5612344 解：按照题目要求构造的二叉树如下四、算法设计题由于队列是先进先出，而栈是先进后出，所以只有经过两个栈，即先在第一个栈里先进后出，再经过第二个栈后进先出来实现队列的先进先出。

因此用两个栈模拟一个队列运算就是用一个栈作为输入，而另一个栈作为输出。

当进队列时，总是将数据进入到作为输入的栈中。

在输出时，如果作为输出的栈已空，则从输入栈将已输入到输入栈的所有数据压入输出栈中，然后由输出栈输出数据；如果作为输出的栈不空，则就从输出栈输出数据。

显然，只有在输入、输出栈均为空时队列才为空。

…………………………（写出思想给5分）一个栈s1用来插入元素，另一个栈S2用来删除元素，删除元素时应将前一栈s1中的所有元素读出，然后进入到第二个栈s2中，算法描述如下：Void Enqueue(s1,x)……………………………………………(2分)stack s1;int x;{if(s1->top==0)Printf(“队列上溢“)；ElsePush(s1,x);}Void Dequeue(s1,s2,x) ……………………………………………(2分)Stack s1,s2;Int x;{ S->top=0; /将s2清空While (!empty(s1) /将s1的所有元素退栈后压入s2,此时栈s1为空 Push(s2,pop(s1));Pop(s2,x); /弹出栈s2的栈顶元素（对首元素）并赋给xWhile (!empty(s2) /将剩于元素重新压入栈s1恢复为原s1中的顺序 Push(s1,pop(s2));}Int Queue_empty(s1)……………………………………………(1分) Stack s1;{if empty(s1)Return(1);ElseReturn(0);}。

浙江理工大学2013年硕士学位研究生招生入学考试试题考试科目：数据结构代码：991（请考生在答题纸上答题，在此试题纸上答题无效）一、单选题（在每小题的四个备选答案中选出一个正确答案。

每小题2分，共20分。

）1.链表不具备的特点是______。

A. 可随机访问任一结点B. 插入删除不需要移动元素C. 不必事先估计存储空间D. 所需空间与其长度成正比2.设线性表有n个元素，以下算法中，在顺序表上实现比在链表上实现效率更高。

A. 交换第0个元素与第1个元素的值B. 顺序输出这n个元素的值C. 输出第i(0≤i≤n-1)个元素值D. 输出与给定值x相等的元素在线性表中的序号3.设输入序列为a、b、c、d，则借助栈所得到的输出序列不可能是_________。

A. a、b、c、dB. d、c、b、aC. a、c、d、bD. d、a、b、c4.为解决计算机主机与打印机之间的速度不匹配问题，通常设计一个打印数据缓冲区，主机将要输出的数据依次写入到该缓冲区，而打印机则依次从该缓冲区中取出数据。

该缓冲区的逻辑结构应该是。

A. 栈B. 队列C. 树D. 图5.设哈夫曼树中的叶子结点总数为m，若用二叉链表作为存储结构，则该哈夫曼树中总共有个空指针域。

A. 2mB. 4mC. 2m+1D. 2m -16.二叉树若用顺序存储结构表示，则下列四种运算中最容易实现。

A. 先序遍历二叉树B. 层次遍历二叉树C. 中序遍历二叉树D. 后序遍历二叉树7.以下关于有向图的说法正确的是。

A. 强连通图是任何顶点到其他所有顶点都有边B. 完全有向图一定是强连通图C. 有向图中某顶点的入度等于出度D. 有向图边集的子集和顶点集的子集可构成原有向图的子图8.若一个有向图中的顶点不能排成一个拓扑结构序列，则可断定该有向图____________。

A. 含有多个出度为0的顶点B. 是个强连通图C. 含有多个入度为0的顶点D. 含有顶点数目大于1的强连通分量9.顺序查找法适合于存储结构为的线性表。

姓名： 报考专业： 准考证号码： 密封线内不要写题2016年攻读硕士学位研究生入学考试试题科目名称：数据结构（C 语言版）（■A 卷□B 卷）科目代码：856考试时间：3小时 满分 150 分可使用的常用工具：√无 □计算器 □直尺 □圆规（请在使用工具前打√）注意：所有答题内容必须写在答题纸上，写在试题或草稿纸上的一律无效；考完后试题随答题纸交回。

一、选择题(共10小题，每小题2分，共20分)1. 以下说法正确的是（ ）。

A ）数据元素是数据的最小单位 B ）数据项是数据的基本单位C ）数据结构是带有结构的各数据项的集合D ）一些表面上很不相同的数据可以有相同的逻辑结构2. 在顺序表（长度为127）中插入一个元素平均要移动（ ）个元素。

A ）8 B ）63.5 C ）63 D ）73. 若完全二叉树的结点总数为1001，则度为1的结点有（ ）个。

A ）0 B ）1 C ）500 D ）5014. 二叉树先序遍历x 在y 之前，后序遍历x 在y 之后，则x 是y 的（ ）。

A ）左兄弟 B ）右兄弟 C ）祖先 D ）后裔5. 二叉树在线索化后，仍不能有效求解的问题是（ ）。

A ）前序线索二叉树中求前序后继B ）中序线索二叉树中求中序后继C ）中序线索二叉树中求中序前驱D ）后序线索二叉树中求后序后继 6. 下列关于AOE 网的叙述中，不正确的是（ ）。

A ）某些关键活动提前，则整个工程将会提前完成 B ）任一关键活动提前，则整个工程将会提前完成 C ）所有关键活动提前，则整个工程将会提前完成 D ）关键活动不按期完成会影响整个工程的完成时间7. 12个数据有序顺序存储，采用二分查找，查找失败时的ASL 值是（ ）。

A ）37/12 B ）63/13 C ）39/12 D ）49/13 8. 二叉查找树的查找效率与二叉树的（ ）有关。

A ）高度B ）结点的多少C ）树型D ）结点的位置9. 用函数H(k)=key%17构造散列表，则链地址法解决冲突需（ ）个链表。

二O 一三年招收硕士研究生入学考试试题考试科目代码及科目名称： 806 安全系统工程可使用的常用工具： （计算器）答题内容写在答题纸上，写在试卷或草稿纸上一律无效考完后试题随答题纸交回。

考试时间3小时，总分值 150 分。

姓名： 报考专业： 准考证号码：密封线内不要写题二O 一三年招收硕士研究生入学考试试题考试科目代码及科目名称：806 安全系统工程B卷参考答案一、填空题（40分，每空2分）1、安全检查表主要分设计用、厂级用、车间用、岗位用、专业用安全检查表五种。

2、“道化”火灾爆炸指数评价法由物质系数、一般工艺危险系数、特殊工艺危险系数确定火灾爆炸指数。

3、实现安全目标分为目标制定、目标执行、成果评价三个步骤。

4、防止能量破坏作用的措施有限制能量积累、控制能量释放、隔离能量。

5、编制安全检查表的注意事项有技术、管理、操作人员三结合、符合标准，突出重点、危险事件不遗漏。

6、故障率浴盆曲线分早期失效期、偶然失效期、损耗失效期三期。

二、简答题（20分，每题4分）1、安全系统工程的定义答：应用系统工程的原理，使系统达到最佳的安全状态的一门学科2、原因后果分析法的特征及初始事件选取方法答：FTA与ETA相结合，选择指明事件作为初始事件3、可靠性的定义答：产品在规定的条件下和规定的时间内完成规定功能的能力4、安全评价的定义答：通过对系统的定性和定量分析，确定系统发生危险的可能性大小，与评价指标相比较，以判定系统的安全性并提出相应的防范措施，称安全评价。

5、最小径集在事故分析中的作用。

答：最小径集表示系统的安全性，最小径集数越多，系统越安全；最小径集可以用于选择控制事故发生的最佳方案，消除少事件通常比消除多事件容易；作定量计算。

三、计算题（共50分，第1题20分，第2题30分）1、 系统如图1所示，其各单元故障发生概率分别为：p 1，p 2，p 3，p 4。

（1）试绘出事件树（2）写出系统故障概率表达式。

武汉科技大学2022年《数据结构（C语言）》考研真题与答案解析一、选择题1. 计算算法的时间复杂度是属于一种（）的方法。

A）事前统计B）事前分析估算C）事后统计D）事后分析估算2. 数据的逻辑结构可以分为（）。

A）静态结构和动态结构B）物理结构和存储结构C）线性结构和非线性结构D）虚拟结构和抽象结构3. 线性表若采用链式存储结构时，要求内存中可用存储单元的地址（）。

A）必须是连续的B）部分地址必须是连续的C）一定是不连续的D）连续不连续都可以4. 线性表既可以用带头结点的链表表示，也可以用不带头结点的链表表示，前者最主要好处是（）。

A）使空表和非空表的处理统一B）可以加快对表的遍历C）节省存储空间D）可以提高存取表元素的速度5. 若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3。

当从队列中删除一个元素，再加入两个元素后，rear 和front的值分别为（）。

A）1和5 B）2和4 C）4和2 D）5和16. 对二叉树T中的某个结点x，它在先根序列、中根序列、后根序列中的序号分别为pre（x），in（x）、post（x），a和b是T中的任意两个结点，下列选项一定错误的是（）。

A）a是b的后代且pre（a）<pre（b）B）a是b的祖先且post（a）>post（b）C）a是b的后代且in（a）<in（b）D）a在b的左边且in（a）<in（b）7. 若二叉树的前序序列和后序序列正好相反，则该二叉树一定是（）的二叉树。

A）空或只有一个结点B）任一结点无左子树C）任一结点无右子树D）高度等于其结点数8. 下面几个符号串编码集合中，不是前缀编码的是（）。

A）{0,10,110,1111} B）{11,10,001,101,0001}C）{00,010,0110,1000} D）{b,c,aa,ac,aba,abb,abc}9. 一个n个顶点的连通无向图,其边数至少为（）。

二O 一三年招收硕士研究生入学考试试题 考试科目代码及科目名称：统计学（602） （B 卷）和参考答案 可使用的常用工具： 计算器 答题内容写在答题纸上，写在试卷或草稿纸上一律无效，考完后试题随答题纸交回。

考试时间3小时，总分值 150 分。

姓名： 报考专业： 准考证号码： 密封线内不要写题B 卷答案一、选择题（本大题共10小题，每小题4分，共40分）1-10 CACCB DACBB二、名词解释（本大题共5小题，每小题6分，共30分）11、组成总体的每一个元素成为个体。

12、在某一个区间或多个区间上取任何值的变量，它的取值是连续不断的。

13、顺序数据是指朱能归于某一有序类别的非数字型数据。

14、四分位数是指一组数据排序后处于25%和75%位置上的值。

15、无偏性是指参数估计量的期望等于真值。

三、问答题（本大题共1小题，共20分）16、（1）总体是所有IT 从业者。

（2）数值型变量(3)分类变量。

（4）截面数据。

四、计算题（本大题共4小题，每小题10分，共40分）17、B={任取一件产品为一等品}，i A ={该产品来自第i 箱}，i=1,2, 则52213018215010)()|()()|()(2211=⨯+⨯=+=A P A B P A P A B P B P 18、041142041)1(=⨯+⨯+⨯-=EX 2141142041)1(2222=⨯+⨯+⨯-=EX 则 21)(22=-=EX EX DX19、（1）1,0},,,,,,{654321==Ωi x x x x x x x（2）样本均值为2/3(3)样本方差为4/1520、区间估计为))15(),15((025.0025.0t n X t n X σσ+-，代值可得（13.7211，16.2789）五、简答题（本大题共1小题，共20分）21、可以以实际案例说明统计常用的数据处理方法。

2013年武汉科技大学专升本（计算机基础）真题试卷(总分：100.00，做题时间：90分钟)一、填空题(总题数：11，分数：22.00)1.填空题每空。

请将每一个空的正确答案写在答题卡上。

（分数：2.00）__________________________________________________________________________________________ 解析：2.典型的微型计算机系统总线是由数据总线、控制总线和 1三部分组成。

（分数：2.00）填空项1:__________________ （正确答案：正确答案：逻辑总线）解析：3.计算机工作时，内存储器中存储的是 1。

（分数：2.00）填空项1:__________________ （正确答案：正确答案：数据和指令）解析：4.在windows XP的回收站窗口中，要想恢复选定的文件或文件夹，可以使用文件菜单中的 1命令。

（分数：2.00）填空项1:__________________ （正确答案：正确答案：还原）解析：5.在windows XP若要删除选定文件，可直接按 1键。

（分数：2.00）填空项1:__________________ （正确答案：正确答案：Shift+Delete）解析：6.数据结构是研究 1和 2之间关系的一门学科。

（分数：2.00）填空项1:__________________ （正确答案：正确答案：所有数据元素的信息、各数据元素）解析：7.二叉树通常有 1存储结构和 2存储结构。

（分数：2.00）填空项1:__________________ （正确答案：正确答案：顺序、链式）解析：8.计算机病毒是1，它能够侵入2，并且能够过修改其他程序，把自己或自己的变种复制插入其他程序中，这些程序又可以传染别的程序，实现繁殖传播。

（分数：2.00）填空项1:__________________ （正确答案：正确答案：一种人工编制的程序、计算机系统）解析：9.微型计算机的内存容量主要是指 1。

二O 一三年招收硕士研究生入学考试试题考试科目代码及科目名称：437社会工作实务和参考答案一、名词解释（每小题4分，共20分）1、（狭义的）青少年福利是指由特定形态的机构向特殊的青少年群体提供的一种特定的服务2、医务社会工作指医药卫生和健康照顾服务领域中的社会工作专业服务3、社会康复是指从社会的角度，采取各种有效措施为残疾人创造一种适合其生存、创造、发展、实现自身价值的环境的活动，其目的是使残疾人享受与健全人同等的权利，达到全面参与社会生活的目的。

4、应用性研究指那些侧重于现实社会问题、有针对性地提供特定的社会政策的经验研究。

5、观察是带着明确的目的，用自己的感官和辅助工具去直接地、有针对性地了解正在发生、发展和变化着的现象。

二、辨析题（每小题2分，判断1分，分析1分，判断错误全小题没分，把判断的“×”或“√”写在答题纸对应的题号后面）1、（√）矫正是针对罪犯或有犯罪倾向的人所确立的司法制度和司法手段。

2、（×）怀旧和生命回顾是老年人个案工作中运用的比较多的技巧3、（×）从世界各国的经验来看，福利制度和直接面对穷人的缓贫计划是反贫困的主要武器。

4、（√）从组成某个总体的所有元素的集合中，按一定的方式选择或抽出一部分元素的过程叫抽样。

5、（×）定性研究侧重于和依赖于对事物的含义、特征、隐喻、象征的描述和理解。

三、简答题（每小题10分，共60分）1、个案辅导：1）商谈与观察；2）访问；3）共同活动团体活动：1）榜样示范；2）行为锻炼；3）情景感染；4）竞赛激励；（5）角色模拟；2、优点：（1）节省时间、经费和人力；（2）具有很好的匿名性；（3）可避免人为因素的影响；缺点：（1）问卷的有效回收率有时难以保证；（2）自填问卷法对被调查者的文化水平有一定要求；（3）调查资料的质量常常得不到保证。

3、社会目标模式的理论主要来源于系统论和社会学的观点，强调社会系统与人和群体间是相互作用和相互影响的。

2013年全国硕士研究生入学统一考试计算机科学与技术学科联考计算机学科专业基础综合试题一、单项选择题：第1～40小题，每小题2分，共80分。

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

1．已知两个长度分别为m 和n 的升序链表，若将它们合并为一个长度为m +n 的降序链表，则最坏情况下的时间复杂度是（ ）。

A ．()O n B ．()O m n ⨯ C ．(min(,))O m n D ．(max(,))O m n 2．一个栈的入栈序列为1,2,3,,n ，其出栈序列是123,,,,n p p p p 。

若23p =，则3p 可能取值的个数是（ ）。

A ．3n -B ．2n -C ．1n -D ．无法确定3．若将关键字1，2，3，4，5，6，7依次插入到初始为空的平衡二叉树T 中，则T 中平衡因子为0的分支结点的个数是（ ）。

A ．0B ．1C ．2D ．34．已知三叉树T 中6个叶结点的权分别是2，3，4，5，6，7，T 的带权（外部）路径长度最小是（ ）。

A ．27B ．46C ．54D ．565．若X 是后序线索二叉树中的叶结点，且X 存在左兄弟结点Y ，则X 的右线索指向的是（ ）。

A ．X 的父结点B ．以Y 为根的子树的最左下结点C ．X 的左兄弟结点YD ．以Y 为根的子树的最右下结点6．在任意一棵非空二叉排序树T 1中，删除某结点v 之后形成二叉排序树T 2，再将v 插入T 2形成二叉排序树T 3。

下列关于T 1与T 3的叙述中，正确的是（ ）。

I ．若v 是T 1的叶结点，则T 1与T 3不同II ． 若v 是T 1的叶结点，则T 1与T 3相同III ．若v 不是T 1的叶结点，则T 1与T 3不同IV ．若v 不是T 1的叶结点，则T 1与T 3相同A ．仅I 、IIIB ．仅I 、IVC ．仅II 、IIID ．仅II 、IV7．设图的邻接矩阵A 如下所示。

各顶点的度依次是（ ）。

二O 一三年招收硕士研究生入学考试试题考试科目代码及科目名称： 856 数据结构(C 语言版)答题内容写在答题纸上，写在试卷或草稿纸上一律无效考完后试题随答题纸交回。

考试时间3小时，总分值 150 分。

姓名： 报考专业： 准考证号码：密封线内不要写题二O 一四年招收硕士研究生入学考试试题考试科目代码及科目名称： 856 数据结构(C 语言版)答题内容写在答题纸上，写在试卷或草稿纸上一律无效考完后试题随答题纸交回。

考试时间3小时，总分值 150 分。

姓名： 报考专业： 准考证号码：密封线内不要写题参考答案(A)一、选择题（10小题，每题2分，共20分）1. B2. C3. B4. D5. B6. B7. C8. A9. A 10. D二、填空题（10小题，每题2分，共20分）1. O(n)2. 运算或操作3. 33/11=34. 985. 66. 517. 空8. Head->next==NULL9. O(nlogn)10. 空或一个结点或单分支三、判断题（10小题，每题2分，共20分）1. ×2. √3. ×4. ×5. √6. √7. √8. ×9. √ 10. ×四、综合应用题（6小题，每题10分，共60分）1.关键路径：a1->a4->a8->a11->a12完成该工程所需最短时间：212.设具有n个结点的完全二叉树的深度为H由完全二叉树的定义可知：第i(1≤i≤H－1)层上的结点数将达到最大(2i-1),第H层上的结点数将≥2且≤2k-1∴1＋2＋……＋2H-2＋2≤n≤ 1＋2＋……＋2H-2＋ 2H-12H-1+1≤n≤ 2H-1 2H-1<n< 2HH-1<log2n<H∴ H=[ log2n ]3.4.（1） p=8（2） k=i*(i-1)/2+i+j-n-15.查找成功时的平均查找长度: (1*1+2*2+3*4+4*4)/11=3查找不成功时的平均查找长度: (4*3+8*4)/12=44/12=3.336.堆排序的初始堆（大根堆）关键字序列:96 63 78 25 57 11 44堆排序1趟以后的关键字序列:78 63 44 25 57 11 96快速排序1趟以后的关键字序列:11 25 96 63 57 78 44快速排序2趟以后的关键字序列:11 25 44 63 57 78 96冒泡排序1趟以后的关键字序列:25 11 63 57 78 44 96五、算法设计与编程（3小题，每题10分，共30分）1.int digit(int n,int k){ if(n==0) return -1;else if(k==1) return n%10;else return digit(n/10,k-1); }int digit(int n,int k){ while(n){ if(k==1) return n%10;k--; n=n/10; }return -1;}2.void compare(int x, Node *L){int count=0, comp=0,status=0;Node *p, *t, *pre, *end,*work=NULL;p=L->next; pre=L; end=L;while(p){if(p->data<x) status=1;if(comp!=p->data&&status==0) { count++; comp=p->data; }if(status==0){if(p==L&&p->data%2==0) { t=p; L->next=p->next; free(t); p=L->next; }else if(p!=L&&p->data%2==0){ t=p; pre->next=p->next; free(t); p=pre->next; }else { pre=p; p=p->next; }end=pre;}if(status==1){ t=pre->next; pre->next=work; work=p; p=t; }}end->next=work;}3．typedef struct{BiTree t;int tag; //tag=0表示左子女被访问，tag=1表示右子女被访问}stack;void Search(BiTree bt,ElemType x){stack s[];top=0;while(bt!=null||top>0){while(bt!=null && bt->data!=x){ s[++top].t=bt; s[top].tag=0; bt=bt->lchild; } if(bt->data==x){printf(“所查结点的所有祖先结点的值为:\n”);for(i=1;i<=top;i++) printf(s[i].t->data);return;}while(top!=0 && s[top].tag==1) top--;if(top!=0) { s[top].tag=1; bt=s[top].t->rchild; }}}int Qiuzu(Node *Head){if (Head==null) return 0;if (Head ->data==x) return 1；if(Qiuzu(Head->Lchild)||Qiuzu(Head->Rchild)){cout<<Head->date<<endl;return 1;}else return 0;}参考答案(A)一、选择题（10小题，每题2分，共20分）1. D2. D3. C4. C5. B6. B7. A8. A9. A 10. C二、填空题（10小题，每题2分，共20分）1. s->next=p->next; p->next=s;2. (n-1)/23. 3124. 2h-15. [log2i]=[log2j]6. 深度7. O(n2)8. k(k+1)/29. [log2i]+1 10.2三、综合应用题（7小题，每题10分，共70分）1.根据完全二叉树的性质，A[i]的双亲是A[i/2]，双亲的双亲是A[i/2/2]，...同理，A[j]的双亲是A[j/2]，双亲的双亲是A[j/2/2]，...if(i==j) A[i]和A[j]的最近的共同祖先就是A[i/2];elsewhile(i!=j) { if(i>j) i=i/2; else j=j/2; }A[i]和A[j]的最近的共同祖先就是A[i];2.设总结点数为n，度为1和2的结点数分别为n1和n2n=B+1=n0+n1+n2 n1=0 n2=n0-1B=2n0-23.（1）i<n-1-i （2）j<=n-1-i （3）r[j].key<r[min].key（4）i!=min （5）max==i4.（1） 15627384 15627834 15672384 15672834 15678234（2）（3）（4）给出其关键路径: <1-2> <2-3> <3-4>5.（1）线性探测法等概率下查找成功时的平均查找长度ASL succ =(1+1+2+1+2+1+2+3)/8=13/8等概率下查找失败时的平均查找长度ASL unsucc=(1+2+1+1+8+7+6+5+4+3+2)/11=40/11（2）链地址法等概率下查找成功时的平均查找长度ASL succ =(1*4+2*3+3*1)/8=13/8等概率下查找失败时的平均查找长度ASL unsucc=(1*7+2*1+3*2+4*1)/11=19/116.只有堆排序，在未结束全部排序前，可以有部分排序结果。

2013 年全国硕士研究生入学统一考试—计算机专业基础综合试题2013 年全国硕士研究生入学统一考试计算机科学与技术学科联考计算机学科专业基础综合试题（科目代码 408）12013 年全国硕士研究生入学统一考试—计算机专业基础综合试题一、单项选择题：第1～40小题，每小题2分，共80分。

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

1．求整数n(n≥0)阶乘的算法如下，其时间复杂度是int fact(int n){if (n<=1)return 1;return n*fact(n-1);}A. O(log2n)B. O(n)C. (nlog2n)D. O(n2)2．已知操作符包括‘+’、‘-’、‘*’、‘/’、‘(’和‘)’。

将中缀表达式a+b-a*((c d)/e-f)+g转换为等价的后缀表达式ab+acd+e/f-*-g+ 时，用栈来存放暂时还不能确定运算次序的操作符，若栈初始时为空，则转换过程中同时保存在栈中的操作符的最大个数是A. 5B. 7C. 8D. 113.若一棵二叉树的前序遍历序列为a, e, b, d, c，后序遍历序列为b, c, d, e, a，则根结点的孩子结点A.只有eB.有e、bC.有e、cD.无法确定4．若平衡二叉树的高度为6，且所有非叶结点的平衡因子均为1，则该平衡二叉树的结点总数为A. 10B. 20C. 32D. 335．对有n个结点、e条边且使用邻接表存储的有向图进行广度优先遍历，其算法时间复杂度是A. O(n)B. O(e)C. O(n+e)D. O(n*e)6．若用邻接矩阵存储有向图，矩阵中主对角线以下的元素均为零，则关于该图拓扑序列的结论是A.存在，且唯一C.存在，可能不唯一B.存在，且不唯一D.无法确定是否存在7．对如下有向带权图，若采用迪杰斯特拉（Dijkstra）算法求源点a到其他各顶点的最短路径，则得到的第一条最短路径的目标顶点是b，第二条最短路径的目标顶点是c，后续得到的其余各最短路径的目标顶点依次是22013 年全国硕士研究生入学统一考试—计算机专业基础综合试题A.d,e,fB.e,d,fC. f,d,eD.f,e,d8．下列关于最小生成树的说法中，正确的是I.最小生成树树的代价唯一II.权值最小的边一定会出现在所有的最小生成树中III.用普里姆（Prim）算法从不同顶点开始得到的最小生成树一定相同IV.普里姆算法和克鲁斯卡尔（Kruskal）算法得到的最小生成树总不相同A.仅IB.仅IIC.仅I、IIID.仅II、IV9．设有一棵3阶B树，如下图所示。

第 1 页 共 7 页 2019年全国硕士研究生招生考试初试自命题试题科目名称：数据结构（C 语言版）（□√A 卷□B 卷）科目代码：856 考试时间：3小时 满分150分可使用的常用工具：□√无 □计算器 □直尺 □圆规（请在使用工具前打√） 注意：所有答题内容必须写在答题纸上，写在试题或草稿纸上的一律无效；考完后试题随答题纸交回。

一、选择题(共15小题，每小题2分，共30分)1. 计算算法的时间复杂度是属于一种（ ）的方法。

A ）事前统计B ）事前分析估算C ）事后统计D ）事后分析估算2. 数据的逻辑结构可以分为（ ）。

A ）静态结构和动态结构B ）物理结构和存储结构C ）线性结构和非线性结构D ）虚拟结构和抽象结构3. 线性表若采用链式存储结构时，要求内存中可用存储单元的地址（ ）。

A ）必须是连续的B ）部分地址必须是连续的C ）一定是不连续的D ）连续不连续都可以4. 线性表既可以用带头结点的链表表示，也可以用不带头结点的链表表示，前者最主要的好处是（ ）。

A ）使空表和非空表的处理统一B ）可以加快对表的遍历C ）节省存储空间D ）可以提高存取表元素的速度5. 若用一个大小为6的数组来实现循环队列，且当前rear 和front 的值分别为0和3。

当从队列中删除一个元素，再加入两个元素后， rear 和front 的值分别为（ ）。

A ）1和5B ）2和4C ）4和2D ）5和16. 对二叉树T 中的某个结点x ，它在先根序列、中根序列、后根序列中的序号分别为pre（x ），in （x ）、post （x ），a 和b 是T 中的任意两个结点，下列选项一定错误的是（ ）。

A ）a 是b 的后代且pre （a ）<pre （b ）B ）a 是b 的祖先且post （a ）>post （b ）C ）a 是b 的后代且in （a ）<in （b ）D ）a 在b 的左边且in （a ）<in （b ）7. 若二叉树的前序序列和后序序列正好相反，则该二叉树一定是（ ）的二叉树。