西安邮电大学826数据结构2013年-2015年考研真题

西安邮电大学硕士研究生招生考试大纲科目代码：826科目名称：《数据结构》一、课程性质和任务数据结构是计算机各专业的专业基础课。

它是操作系统、数据库、编译原理等所有软件专业基础课和专业课的重要基础；它还是进行程序设计，尤其是进行高水平的应用程序和系统程序必不可少的基础。

通过本课程的学习，使学生掌握数据组织、存储和运算的基本原理和方法，培养学生对各类数据结构和相关算法的分析和设计的能力，使学生能够编写出正确、清晰和较高质量的算法和程序。

二、课程教学内容和要求第一章数据结构和算法1.了解数据结构、逻辑结构、存储结构和抽象数据类型的基本概念。

2.了解数据结构的发展和地位。

3.了解各种算法描述方法和算法设计的基本要求。

4.掌握对算法的评价标准和算法效率的度量方法。

第二章线性表1.理解线性表的概念、定义、逻辑结构和存储结构。

2.熟练掌握线性表的顺序结构及其各种基本运算。

3.熟练掌握单链表、循环链表、双向链表的存储结构及其各种基本运算。

4.理解链表的应用——稀疏多项式存储和运算。

第三章栈和队列1.掌握栈的定义、表示、实现和应用。

2.掌握递归的概念和递归的实现过程。

3.掌握队列的定义以及顺序(循环队列)和链式存储结构的实现。

第四章串1.了解串的基本概念及顺序和链式存储结构。

2.掌握串的各种基本运算。

3.了解串的模式匹配算法。

第五章数组和广义表1.掌握数组的顺序存储结构。

2.理解稀疏数组的概念和压缩存储的方法。

3.理解稀疏矩阵的三元组存储结构和基本运算。

4.了解稀疏矩阵的十字链表存储结构。

5.理解广义表的基本概念，掌握广义表的存储结构。

第六章树1.理解树的基本概念及其存储结构。

2.熟练掌握二叉树的定义、性质以及各种存储结构和遍历算法。

3.掌握线索二叉树的概念、存储结构及线索化算法。

4.掌握树和森林与二叉树间的转换，掌握树和森林的遍历算法。

5.掌握哈夫曼树的概念、存储结构和应用。

第七章图1.理解图的基本概念，掌握图的邻接矩阵和邻接表的存储结构。

目　录2013年西安邮电大学826数据结构考研真题2014年西安邮电大学826数据结构考研真题2015年西安邮电大学826数据结构考研真题2016年西安邮电大学826数据结构考研真题2017年西安邮电大学826数据结构考研真题2013年西安邮电大学826数据结构考研真题西安邮电大学2013年招收攻读硕士学位研究生入学考试试题科目代码及名称826数据结构A考试时间2013年1月6日下午(3小时)答题要求：所有答案必须写在答题纸上的指定区域，在草稿纸和试卷上答题一律无效，考生编号务必写在指定位置！！I一、判断题(打，寸或"七每焦1分，共】。

分)()】,通常以算法的时间筮杂度和空间复杂度来判断一个算法的忧劣。

()L KHP算法的最大特点是指主申的指针不需要回潮.()3,如果一棵二叉树中没有度为1的结点，则必为潸二叉树。

()4,判断有向图是否存在回路，除了可以利用拓扑排序方法外,还可以利用深度优先遍仍算法,()5,有向图的鸵接矩阵一定是对称的.(}6、平衡二又排序树上，任何一个黠点的左、右子椅的高度之差的绝对值不大于I.(}L用折半查授法对一个顺序表进行查找,这个顺序表必须是按关键字值有序的"()8、对于同一蛆记录，生成二叉措序树的形态与插入诺录的沃序无美。

()%在堆排序中待排数据不能采用顺件存储方式。

()】队在AOE网中一定只有一条关链路径，二、单项选择题(每痛2分，共20分)1、数据元素的逻辑结构分为()神基本类型，，20,3C,4 D.52、链占不具沛特点是().L可随机访向任一个元素B、插入删除不需要移动元素C、不必嘴先估计存赭空间队所需空间与线性表的长度成正比3、若线性表最常用的操作是存取第i个元素及其前驱的值，则采取()存储方式最节省时间.A.单一链表B、双槌表"顺序表D、单向糖环链表试题共5页第1页4、若某堆栈的输入序列为I.2,3,…，n-l.n,输出序列的第1个元素为n,姻第i个输出元素为（）.A、n-i+1B、n-l C.i D、哪个元素都有可能5、若循环队列的最大检度是HAXSIZE,则循环队列中.当使用“少用一个元素空间”来解决队列的“满”与“空”状态时.判满的条件是（）.=A、rear==frontB、rear->next=NULLC、rear—NULL D*（rear+Daod MAXSIZE—front6、稀疏矩阵一般的压璃存储方法有两神.即（）.A、二维数组和三维数组B、.三元组和酸列C、三元组和十字链表D、散列和十字链表L采用邻接表存储的图的广度优先遍疝算法类似于二叉树的｛）3A、按厚ifi巧B、先序醐历C、中序遢坊D、后序遍历8、含有10个结点的树有（）条分支.A、0B、10C、9D、不确定9、n个顶点的强述通图至少有（）条边,A、nB、n+lC、n-lD、n（n-l）10、对n个记灵的集合进行廿泡排序使之形成非璀减有序序列，在从小到达排列好的情我下比鞭的次数最少，其比较次数为《）.A、n+l E、n C、n-l D、n（n-l）/2三、填空题（每空2分，共20分）1、数据结构是研究数据的f）和（）及他们之间的相互黄系，芥利这神结梅定义相成的运算.2、若一个算法中的请句颗度之和T（n）=3720n+4nlQgn,则算法的时间复杂度为]）*3、进楼嘶序为A B C,则出枝的顺序不可临I）.4、设有_绯.数蛆A[5]0],其每个元素占2个字节，首元素A[0][0]的存储地址为100,则接漩茏存婀存储地址为1W6的数蛆元素为（），5、a="I0AW3A0STUDENT0\StrLtingth（a）的结果是（）.6、已知广义表LS=（&b,c）,（d,e,f））.运用head和tail成数取LS中原子电的运算是（）.7、已知一个算数表这式的中堰式为A+B7-IVE,后缱式为AB8+DE/-,其前缀式为（）.试题共5页第2页8、设高度为卜的二叉树上只有度为。

2015年考研必备资料2015年考研计算机数据结构试题及答案目录2015年考研计算机数据结构试题及答案（1） (2)2015年考研计算机数据结构试题（1） (2)2015年考研计算机数据结构试题答案（1） (5)2015年考研计算机数据结构试题及答案（2） (6)2015年考研计算机数据结构试题（2） (6)2015年考研计算机数据结构试题答案（2） (9)2015年考研计算机数据结构试题及答案（3） (11)2015年考研计算机数据结构试题（3） (11)2015年考研计算机数据结构试题答案（3） (13)2015年考研计算机数据结构试题及答案（4） (15)2015年考研计算机数据结构试题（4） (15)2015年考研计算机数据结构试题答案（4） (17)2015年考研计算机数据结构试题及答案（5） (19)2015年考研计算机数据结构试题（5） (19)2015年考研计算机数据结构试题答案（5） (21)2015年考研计算机数据结构试题及答案（1）2015年考研计算机数据结构试题（1）一、选择题(24分)1.下列程序段的时间复杂度为( )。

i=0，s=0; while (s(A) O(n1/2) (B) O(n1/3) (C) O(n) (D) O(n2)2.设某链表中最常用的操作是在链表的尾部插入或删除元素，则选用下列( )存储方式最节省运算时间。

(A) 单向链表 (B) 单向循环链表(C) 双向链表 (D) 双向循环链表3.设指针q指向单链表中结点A，指针p指向单链表中结点A的后继结点B，指针s指向被插入的结点X，则在结点A和结点B插入结点X的操作序列为( )。

(A) s->next=p->next;p->next=-s; (B) q->next=s; s->next=p;(C) p->next=s->next;s->next=p; (D) p->next=s;s->next=q;4.设输入序列为1、2、3、4、5、6，则通过栈的作用后可以得到的输出序列为( )。

西 安 邮 电 学 院2013年招收攻读硕士学位研究生入学考试试题 考试科目代码及名称 824信号与系统A注：符号()t ε为单位阶跃函数，()k ε为单位阶跃序列，LTI 为线性时不变。

一、填空题（每空3分，共30分）1．积分 ()()=--⎰+∞∞-dt t t 2422εε。

2．周期序列⎪⎭⎫ ⎝⎛++⎪⎭⎫ ⎝⎛+=63cos 443cos )(ππππk k k f 的周期为 。

3．一连续LTI 系统的单位阶跃响应())(13)(2t e t g t ε-=-，则该系统的单位冲激响应为 =)(t h 。

4．离散序列()k f 1和的波形如图1所示，已知()k f 2)()()(21k f k f k f *=，则()=2f 。

5．信号()()[]t e dtd t f t ε12)(--=的傅里叶变换()=ωj F 。

6．因果信号的单边拉普拉斯变换为))(t f ()(213)(2+++=s s s s F ，则对应原函数的初值 =+)0(f ；终值=∞)(f 。

7．序列()=k f ()1---k a k ε的象函数()=z F ； 其 收敛域为。

8．已知()t S t 22)(=，对)(t f 进行理想冲激取样，则使频谱不发生混叠的奈奎f a =s T 斯特间隔 。

二、选择题（共8题，每题4分，共32分）1．已知，则应按下列哪种运算求得（式中、都为正值） )(t f )(0at t f -0t a （A ）左移（B ）右移（C ）左移)(at f -0t )(at f 0t )(at f a t 0（D ）右移)(at f -at 0。

2．如图2所示周期信号，其直流分量等于)(t f（A ） （B ） （C ） （D ）02463．下列叙述正确的是（A ） 序列()k f 与()k y 是周期信号，其和()()k y k f +是周期的； 号：；； 。

)（B ） 由已知信号()t f 构造信)∑nT t f ，则()t y 为周期信号()(∞-∞=+=n t y （C ） 非线性系统的全响应必等于零状态响应与零输入响应之和（D ） 冲激信号是一个高且窄的尖峰信号，它有有限的面积和能量4．系统的幅频特性(ωj H 和相频特性()ωϕ如图3所示，则下列信号通过该系统时，不产生失真的是（A ） （B ）()()()t t t f 8cos cos +=()()()t t t f 4sin 2sin += （C ） （D ）()()()t t t f 4sin 2sin =()()t t f 4cos 2=5．单边拉普拉斯变换()42+=-s se s F s的原函数为（A ）()()12sin -t t ε （B ）()()112sin --t t ε （C ）()()112cos --t t ε （D ）()()12cos -t t ε6．序列的单边()()[∑-=-1012k i iki ε]z 变换为（A ）422-z z （B ）()()12+-z z z （C ）422-z z （D ）()()122--z z z 7．连续系统的系统函数为23)(2++=s s ss H ，则其幅频特性响应所属类型为（A ）低通 （B ）高通 （C ）带通 （D ）带阻8．对于离散因果系统5.02)(--=z z z H ，下列说法错误的是（A ）这是一个一阶系统 （B ）这是一个稳定系统 （C ）这是一个全通系统 （D ）这是一个最小相位系统 三、（8分，每题4分）1．已知和()t f 1()t f 2的波形如图4所示，试求卷积()()()(t f t f t f t f 221*)*=，并画出波形图。

目　录2013年西安邮电大学825微机原理与接口技术考研真题2014年西安邮电大学825微机原理与接口技术考研真题2015年西安邮电大学825微机原理与接口技术考研真题2016年西安邮电大学825微机原理与接口技术考研真题2017年西安邮电大学825微机原理与接口技术考研真题2013年西安邮电大学825微机原理与接口技术考研真题2013年招收攻读硕士学位研究生入学考试试题科目代码及名称825微机原理与接口技术A考试时间2013年」月6日下午（3小时）答题要求：所有答案必须写在答题纸上的指定区域.在草稿纸和试卷上答题一律无效，考生编号务必写在指定位盟！！！*名词解释（每题3分，共15分）1.HIV.&.，、于宅口字元-■端L」盘U5研母W仁中论技”一8力在;.岂在珂"中存人不旧3.浅出炬#胃氏彩上字宥号勤电袒届寻华弱一锻葬字方M •I,存繇井冲点、士亡g矿只此1由勺引襦笔挎作户斤需的匚乱即地址某'店叫式为押山,止：找以宙EgF'[扃括t V址,・二填空袈（每空2分，共40分）1.计TZ机中各功能部件倒传送信息的公共通路称为W*£.二阳WiCPL可在堂___阳站大炳神方式下3.加8&为内存进行分段为地都个逻机校的M火&也为_±里J字节.■L80%tTL读取内存中一个牌地址字时.漏妥师"MifUS[次*t>-H08武PL外部地址和故USI脚采川f技术.6,…片昭的A M曾现号可中曲.7.在地55A的三个端I】中，只村A口可以1.（1J■式乏.H."而君扩展的方心：.要:山含，广屈.竺也登』I里度史竺%：*'J-J-l n诉今中.n的含义『中曜打楚W至10.若某8255A芯片的控制口地址为43H，则其A口地址为,II.MOV指令中,若某操作数的有效地址存放于BX寄存器中，则其寻址方式为.12.数据操作数可以存放于指令本身、、和中’13・汇编程序M ASM可将文件配编成文件.14.已知某RAM芯片有12根地址线，X根数据线，则其存储容形为字节。

1H
_ +
2Ω
u s (t ) + _
u c (t )
i (t )
C
图1
2015年招收攻读硕士学位研究生入学考试试题
科目代码及名称 824 信号与系统 A
考试时间 2014年12月28日下午（３小时）
答题要求：所有答案必须写在答题纸上的指定区域，在草稿纸和试卷上答题一律无效，考生编号务必写在指定位置！！！
注：符号()t ε为单位阶跃函数，()k ε为单位阶跃序列，LTI 为线性时不变。

一、填空题（每空3分，共30分） 1．积分()[]()=+⎰
∞
-ττδπτd t 'sin 1 。

2．已知离散序列()()()1--=k k k h δδ，()()()2--=k k k f εε，则卷积
()()=*k f k h 。

3．某LTI 系统，其输入)(t f 与输出)(t y 的关系为()()dx x f e t y t x t 2)(1
2-=⎰
∞---，
则该系统的冲激响应=)(t h 。

4．如图1所示电路系统，其系统函数
()()()1
21
2++==
s s s u s u s H s c ，则电容=C 。

5．信号()∞<<∞-=-t e t f t j ,)(3的傅里
叶变换()=ωj F 。

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

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

请在答题卡上将所选项的字母涂黑。

1．已知程序如下：程序运行时使用栈来保存调用过程的信息，自栈底到栈顶保存的信息依次对应的是（）。

A．main（）->S（1）->S（0）B．S（0）->S（1）->main（）C．main（）->S（0）->S（1）D．S（1）->S（0）->main（）【答案】A【解析】函数S（int n）是一个递归函数：①当实际参数小于等于零时则返回0，并终止递归；②当实际参数大于零时则递归调用S（n－1），并将S（n－1）的结果加上n作为返回值。

程序从main（）函数开始，首先调用main（）函数；在main（）函数中调用S （1）函数时，将main（）函数的上下文保存到栈中，并进入函数S（1）；由于函数S（1）的实际参数大于零，需要调用S（0），故将S（1）函数的上下文保存到栈中，进入S（0）；在S（0）中，实际参数小于等于零，递归终止。

2．先序序列为a，b，c，d的不同二叉树的个数是（）。

A．13B．14C．15D．16【答案】B【解析】二叉树的先序遍历定义为：若二叉树为空，则空操作；否则，访问根节点，然后先序遍历左子树，最后先序遍历右子树。

本题中，结点a为二叉树的根节点，左右子树的先序遍历可能存在下面四种情况：①左子树为空，bcd为右子树；②b为左子树，cd为右子树；③bc为左子树，d为右子树；④bcd为左子树，右子树为空。

然后将左右子树继续分解，如第①种情况的右子树先序遍历（bcd）可能有：a．左子树为空，右子树为cd；b．左子树为c，右子树为d；c．左子树为cd，右子树为空。

按照这种方法继续分解左右子树，直到不能再分解为止，可得第①和④种情况各包含5种不同情况，第②和③种情况各包含2种情况，因此总共有14种不同的二叉树。

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树，如下图所示。