西北大学2016年数据结构考研真题851与参考答案

数据结构考研真题和答案数据结构是计算机科学中的重要基础课程，对于计算机专业的学生而言，掌握好数据结构非常关键。

考研阶段，数据结构也是一个必考科目。

本文将介绍一些常见的数据结构考研真题以及详细的答案解析，希望能帮助同学们更好地备考。

1. 简述线性表的定义，举例说明线性表的应用场景。

线性表是数据结构中最基本的一种结构，它是由相同数据类型的有限个数据元素组成的序列。

线性表的特点是存储结构唯一，数据元素之间是一对一的关系。

在实际应用中，线性表常用来表示一组某种类型的数据集合，例如存储学生的学号信息、存储职工的工号信息等。

2. 解释栈的特点及其应用场景。

栈是一种特殊的线性表，它的特点是只能在表的一端进行插入和删除操作，表的另一端称为栈顶。

栈的插入操作称为入栈，删除操作称为出栈。

栈的特点是后进先出（LIFO），即最后插入的元素最先被删除。

栈在实际应用中有很多场景，例如函数调用栈、表达式求值、撤销操作等。

3. 什么是队列？请给出队列的一个实际应用案例。

队列也是一种特殊的线性表，它的特点是只允许在表的一端进行插入操作，而在另一端进行删除操作。

队列的插入操作称为入队，删除操作称为出队。

队列的特点是先进先出（FIFO），即最先插入的元素最先被删除。

队列在实际应用中有很多场景，例如排队、任务调度、消息队列等。

4. 什么是树结构？请简要介绍树结构的一些应用。

树是一种非线性的数据结构，它由n（n>=1）个有限节点组成一个具有层次关系的集合。

树的特点是一个节点可以有多个子节点，但是只能有一个父节点，除根节点外，每个节点可以有多个子节点。

树结构在实际应用中广泛存在，例如文件系统、组织结构、网络拓扑等。

5. 解释二叉树的定义，并给出一种常见的二叉树结构。

二叉树是一种特殊的树结构，它的每个节点最多有两个子节点，分别称为左子节点和右子节点。

二叉树的定义为一个有限的节点集合，该集合可以为空，如果非空则必须满足：（1）有且仅有一个称为根的节点；（2）该节点的左子树和右子树也是二叉树。

2016年全国硕士研究生入学统一考试《计算机学科专业基础综合》真题(总分：150.00，做题时间：180分钟)一、单项选择题(总题数：40，分数：80.00)1.已知表头元素为c的单链表在内存中的存储状态如下表所示现将f存放于1014H处并插入到单链表中，若f在逻辑上位于a和e之间，则a,e,f的“链接地址”依次是（）。

（分数：2.00）A.1010H，1014H，1004HB.1010H，1004H，1014HC.1014H，1010H，1004HD.1014H，1004H，1010H√prev data next结点，正确的语句序列是（）。

（分数：2.00）A.p->next->prev=p->prev;p->prev->next=p->prev;free(p);B.p->next->prev=p->next;p->prey->next=p->next;free(p);C.p->next->prev=p->next;p->prev->next=p->prev;free(p);D.p->next->prey=p->prey;p->prev->next=p->next;fr ee(p);√3.设有如下图所示的火车车轨，入口到出口之间有n条轨道，列车的行进方向均为从左至右，列车可驶入任意一条轨道。

现有编号为1～9的9列列车，驶入的次序依次是8，4，2，5，3，9，1，6，7。

若期望驶出的次序依次为1～9，则n至少是（）。

2.00）A.2B.3C.4√D.54.有一个100阶的三对角矩阵M，其元素mi,j(1≤i≤100，1≤j≤100)按行优先次序压缩存入下标从0开始的一维数组Ⅳ中。

元素m30,30在N中的下标是（）。

（分数：2.00）A.86B.87√C.88D.895.若森林F有15条边、25个结点，则F包含树的个数是（）。

2016考研真题及答案解析全程报道2016考研试卷及答案公布（点击进入考研真题解析专题），新东方网考研频道时刻关注2016考研初试情况，第一时间为考生提供考研真题答案及答案解析内容，同时新东方考研名师将在考后为考生提供在线答案解析直播。

请关注新东方网考研频道为您带来的精彩内容。

一、A型题：1～90小题，每小题i.s分;gl~120小题，每小题2分;共1 95分。

在每给出的A, B, C,D 四个选项中，请选出一项最符合题目要求的。

1.下列关于机体内环境稳态的描述，错误的是DA.稳态是一种动态平衡B.稳态的维持是机体自我调节的结果c.稳态调节中都有一个调节点D.稳态是指细胞内液理化性质基本恒定2.在引起和维持细胞内外Na+、K+不对等分布中起重要作用的膜蛋白是BA.载体B.离子泵c.膜受体D.通道3.神经细胞的静息电位为一70mV, Na+平衡电位为+60mV, Na+的电化学驱动力则为AA. -130mVB. -10mVC. +lOmVD. +130mV4.风湿热时，红细胞沉降率加快的原因是CA.红细胞表面积/体积比增大B.血浆白蛋白、卵磷脂含量增高C.血浆纤维蛋白原、球蛋白含量增高D.红细胞本身发生病变5.阿司匹林通过减少TXA2合成而抗血小板聚集的作用环节是AA. 抑制COXB.抑制TXA-,合成酶C.抑制PGI7合成酶D.抑制PLA26.心室肌细胞在相对不应期和超常期内产生动作电位的特点是BA.0期去极化速度快B.动作电位时程短C.兴奋传导速度快D.O期去极化幅度大7。

在微循环中，进行物质交换的血液不流经的血管是BA.后微动脉B.通血毛细血管C.微静脉D.微动脉8.下列呼吸系统疾病中，主要表现为呼气困难的是AA.肺气肿B.肺水肿C.肺纤维化D.肺炎9.下列关于CO影响血氧运输的叙述，错谈的是AA. CO中毒时血02分压下降B. CO妨碍02与Hb的结合C. CO妨碍02与Hb的解离D.cO中毒时血02含量下降10.下列关于颈动脉体化学感受器的描述，错误的是DA.其流入流出血液中的Pa02差接近零，通常处于动脉血环境中B. Pa02降低、PaC02和H+浓度升高对其刺激有协同作用c.感受器细胞上存在对02,、C02、H+敏感的不同受体D.血供非常丰富，单位时间内血流量为全身之冠11.胃和小肠蠕动频率的决定性因素是DA. 胃肠平滑肌动作电位频率B.胃肠平滑肌本身节律活动C. 胃肠肌问神经丛活动水平D.胃肠平滑肌慢波节律12.在胃黏膜壁细胞完全缺乏时，病人不会出现的表现是CA.维生素B12吸收障碍B.肠道内细菌加速生长C.胰腺分泌HC03-减少D.食物蛋白质消化不良13.促进胰腺分泌消化酶最主要的胃肠激素是CA.胰多肽B.促胰液素C.缩胆囊素D.胃泌素14.人体发热初期出现畏寒、寒战的原因是BA.散热过程受阻B.体温调定点上调C.体温调节中枢功能异常D.产热过程过强15.利用肾清除率概念测定GFR，被清除物除能被肾小球滤过外，尚需满足的条件是CA.不被肾小管重吸收，但可被分泌B.可被肾小管重吸收，但不可被分泌C.不被肾小管重吸收和分泌D.可被肾小管重吸收和分泌16.肾小管重吸收Na+与水的量与肾小球滤过率成定比关系的部位是DA.髓袢细段B.髓袢升支粗段C.远曲小管D.近端小管17.机体安静情况下，对醛固酮分泌调节不起作用的因素是CA.高血Na+B.血管紧张素IIC.促肾上腺皮质激素D.高血K+18.视网膜中央凹处视敏度极高的原因是DA.感光细胞直径小，感光系统聚合联系B. 感光细胞直径大，感光系统单线联系C.感光细胞直径大，感光系统聚合联系D.感光细胞直径小，感光系统单线联系19.在突触传递中，与神经末梢释放递质的数量呈正相关的因素是DA.末梢内囊泡的大小B.囊泡内递质的含量C.活化区面积的大小D.进入末梢的Ca2+量20.在周围神经系统中，属于胆碱能纤维的是CA.所有副交感节后纤维B.所有支配血管的交感节后纤维C.所有自主神经节前纤维D.所有支配汗腺的交感节后纤维21.下列激素中，能使机体的能量来源由糖代谢向脂肪代谢转移的是CA.胰岛素B.皮质醇C.生长激素D.甲状腺激素22.口服葡萄糖比静脉注射等量葡萄糖引起更多的胰岛素分泌，其原因是BA.小肠吸收葡萄糖非常完全。

2016 年武汉科技大学 856 数据结构（C 语言版）考研真题（ A 卷）1.以下说法正确的是（ ）。

（分数： 2.00 ）A.数据元素是数据的最小单位B. 数据项是数据的基本单位C. 数据结构是带有结构的各数据项的集合D. 一些表面上很不相同的数据可以有相同的逻辑结构 解析： 2. 在顺序表（长度为 127 ）中插入一个元素平均要移动（A. 8B. 63.5 √C. 63D.7 解析：3. 若完全二叉树的结点总数为 1001 ，则度为 1 的结点有（A. 0 √B. 1C. 500D. 501 解析：A.左兄弟B. 右兄弟C. 祖先 √D.后裔解析： 5.二叉树在线索化后，仍不能有效求解的问题是（ ）。

（分数： 2.00 ）A.前序线索二叉树中求前序后继B. 中序线索二叉树中求中序后继C. 中序线索二叉树中求中序前驱D. 后序线索二叉树中求后序后继 √（ 总分： 150.00 ，做题时间： 180 分钟 )、选择题 （总题数： 10， 分数： 20.00） ）个元素。

（分数： 2.00 ））个。

（分数： 2.00 ）4.二叉树先序遍历 x 在 y 之前，后序遍历 x 在 y 之后，则 是 y 的（ ）。

（分数： 2.00 )解析：6. 下列关于AOE 网的叙述中，不正确的是（）。

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

（分数：2.00 )A.37/12B.63/13C.39/12D.49/13 √ 解析：8. 二叉查找树的查找效率与二叉树的（）有关。

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

第4章栈和队列1.设一数列为1,2,3,4,5,6,通过栈操作,要得到顺序为3,2,5,6,4,1和1,5,4,6,2,3的输出序列是否可能,请阐述理由。

答案：(1)3,2,5,6,4,1是可能的,但1,5,4,6,2,3不可能.(2)因为5在4,2,3之前出栈,那么5出栈时,栈内状态为:5,4,3,2。

根据先进后出原则,其次序只能是5,4,3,2,不可能出现5,4,2,3,想出2时,2却被3压在下面,2不能比3先出栈,所以不可能出现1,5,4,6,2,3这种序列.2. 把1、2、3、4依次进栈（栈初始为空），任何时刻（只要栈不空），都可以出（退）栈，试写出所有可能的出栈序列（如1234）。

答案略第6章树3.对数列{3，1，7，4，2，8，5}构造出二叉排序树。

答案：3.假设一棵二叉树的先序序列为ABDEGHJCFI和中序序列为DBGEHJAC FI。

请画出该树。

答案：4.一棵二叉树后序遍历为DECBHGFA ，中序遍历为BDCEAFHG ，能不能唯一的确定一棵二叉树？如果能够，请构造此二叉树，并写出其前序遍历序列。

解答:前序遍历序列:ABCDEFGH5. 设有一组权ＷＧ＝1,4,9,16,25,36,49,64,81,100，试画出其哈夫曼树，并计算加权的路径长度。

答案：树不唯一，但加权路径长度均为1078WPL=1*7+4*7+9*6+16*5+25*4+36*3+49*3+64*3+81*2+100*2=1078试问：⑴哪个结点是根结点？⑵哪个结点是D的双亲结点？ ⑶C 的左右孩子分别是什么？ ⑷画出这棵二叉树。

答案:根结点为: A D 的双亲结点: C C 的左右孩子: 空、D7.已知信息为“ABCDBCDＢCBDBACB”，（1）请按此信息构造哈夫曼树；（2）计算哈夫曼树的加权路径长度WPL；（3）求出每一字符的最优编码；提示：统计各个字符的出现频率，构造哈夫曼树，算WPL，编码。

数据结构分析考研真题答案数据结构分析考研真题答案考研是许多大学生为了进一步深造而选择的一条道路，而数据结构是计算机科学与技术专业的一门重要课程。

在考研过程中，数据结构分析是非常关键的一部分，因为它涉及到对数据的存储、组织和操作的理解与掌握。

下面将对一道数据结构分析考研真题进行解析，帮助考生更好地理解和掌握数据结构的知识。

题目如下：设有一个含有n个结点的二叉树，采用二叉链表存储结构，结点结构定义如下：struct Node {int data;struct Node *left;struct Node *right;};其中，data表示结点的数据，left和right分别指向左子树和右子树。

现给定一个指向二叉树根结点的指针root，请写出一个递归算法，计算二叉树中结点的个数。

解析：首先，我们需要明确递归算法的基本思想。

递归算法是一种将问题分解为相同或类似子问题的方法，通过解决子问题来解决原始问题。

在二叉树中计算结点个数的问题中，可以将问题分解为计算左子树结点个数、计算右子树结点个数和计算根结点个数三个子问题。

接下来，我们可以根据这个思路编写递归算法。

算法如下：int countNodes(struct Node *root) {if (root == NULL) {return 0;} else {return 1 + countNodes(root->left) + countNodes(root->right);}}首先，我们判断根结点是否为空，如果为空，则返回0，表示当前子树结点个数为0。

如果根结点不为空，则递归调用countNodes函数计算左子树和右子树的结点个数，并将结果相加，再加上根结点本身，即可得到整个二叉树的结点个数。

通过这个递归算法，我们可以方便地计算出二叉树中结点的个数。

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

因为每个结点都需要访问一次，所以时间复杂度与结点个数成正比。

第1章绪论一、选择题1. 算法的计算量的大小称为计算的（）;A．效率 B. 复杂性 C. 现实性 D. 难度2. 算法的时间复杂度取决于（）;A．问题的规模 B. 待处理数据的初态 C. A和B3.计算机算法指的是（），它必须具备（）这三个特性;(1)A．计算方法 B. 排序方法 C. 解决问题的步骤序列 D. 调度方法(2)A．可执行性、可移植性、可扩充性 B. 可执行性、确定性、有穷性C. 确定性、有穷性、稳定性D. 易读性、稳定性、安全性4．一个算法应该是（）;A．程序 B．问题求解步骤的描述 C．要满足五个基本特性 D．A和C 5. 下面关于算法说法错误的是（）;A．算法最终必须由计算机程序实现B.为解决某问题的算法同为该问题编写的程序含义是相同的C. 算法的可行性是指指令不能有二义性D. 以上几个都是错误的6. 下面说法错误的是（）;(1）算法原地工作的含义是指不需要任何额外的辅助空间;（2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法;（3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界;（4）同一个算法，实现语言的级别越高，执行效率就越低A．(1) B.(1),(2) C.(1),(4) D.(3)7．从逻辑上可以把数据结构分为（）两大类;A．动态结构、静态结构 B．顺序结构、链式结构C．线性结构、非线性结构 D．初等结构、构造型结构8．以下与数据的存储结构无关的术语是（）;A．循环队列 B. 链表 C. 哈希表 D. 栈9．以下数据结构中，哪一个是线性结构（）;A．广义表 B. 二叉树 C. 稀疏矩阵 D. 串10．以下那一个术语与数据的存储结构无关？（）;A．栈 B. 哈希表 C. 线索树 D. 双向链表11．在下面的程序段中，对x的赋值语句的频度为（）;FOR i:=1 TO n DOFOR j:=1 TO n DOx:=x+1;A． O(2n) B．O(n) C．O(n2) D．O(log2n)12．程序段 FOR i:=n-1 DOWNTO 1 DOFOR j:=1 TO i DOIF A[j]>A[j+1]THEN A[j]与A[j+1]对换；其中 n为正整数，则最后一行的语句频度在最坏情况下是（）;A. O（n）B. O(nlogn)C. O(n3)D. O(n2)13．以下哪个数据结构不是多型数据类型（）;A．栈 B．广义表 C．有向图 D．字符串14．以下数据结构中，（）是非线性数据结构;A．树 B．字符串 C．队 D．栈15. 下列数据中，（）是非线性数据结构;A．栈 B. 队列 C. 完全二叉树 D. 堆16．连续存储设计时，存储单元的地址（）;A．一定连续 B．一定不连续 C．不一定连续 D．部分连续，部分不连续17．以下属于逻辑结构的是（）;A．顺序表 B. 哈希表 C.有序表 D. 单链表二、判断题1. 数据元素是数据的最小单位。