1、西南交通大学全国考研959真题专硕doc试题代码：959西南交通大学2011年硕士研究生入学考试试题名称：数据结构考生注意：1. 本试题共4题，共6页，满分150分，请认真检查；2. 答题时，直接将答题内容写在考场提供的答题纸尚，答在试卷上的内容无效；3. 请在答题纸上按要求填写试题代码和试题名称；4. 试卷不得拆开，否则遗失后果自负。题号一二三四五六七八九十总分得分签字一、单项选择题（本大题共25题，每题2分，共50分）1.数据结构在计算机内存中的表示是指【 】。A.数据的存储结构 B.数据结构C.数据结构的逻辑结构 C.数据元素之间的关系2.【 】是数据的基本单位。A.数据项 B.数据元素
2、C.信息项 D.表元素3.算法的计算量的大小称为算法的【 】。A.效率 B.时间复杂度 C.显示性 D.难度4.链表不具备的特点是【 】A.可随机访问任一结点 B.插入删除不需要移动元素C.不必事先估算存储空间 D.所需空间与其长度成正比5.设线性表有n个元素，以下操作中，【 】在顺序表上实现比在链表上实现效率更高。A.输出第i（1in）个元素的值B.顺序输出这n个元素C.交换第1个与第2个元素的值D.输出与给定值x相等的元素在线性表中的序号6.设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用【 】最节省时间。A.带头结点的双循环链表 B.单循环链表C.带尾指针的单循环链表 D.单链
3、表7.若长度为n的线性表采用顺序存储结构，在第i个位置插入一个新元素的算法的时间复杂度为【 】A.O(0) B. O(1) C. O(n) D. O()8.栈和队列的共同点是【 】A.都是先进先出 B.都是后进后出C.只允许在端点处进行插入和删除 D.无共同点9.设入栈序列为1，2, 3, 4，5，则可能得到的出栈序列为【 】A.1,2,5,3,4 B.3,1,2,5,4C.3,2,5,4,1 D.1,4,2,3,510.队列存放在A0M-1中，则入队时的操作为【 】A.rear=rear+1 B.rear=(rear+1)%MC.rear=(rear+1)%(M+1) D.rear=(rea
4、r+1)%(M-1)11.两个串相等必有串长度相等且【 】A.串的各位置字符任意 B.串中各位置字符均对应相等C.两个串含有相同的字符 D.两个串所含字符任意12.设有数组A810，每个元素占3个存储单元，首地址为SA，则元素75的起始地址是【 】A.SA+141 B.SA+144 C.SA+222 D.SA+22513.设有一个n*n的对称矩阵，采用压缩存储，则存入内存的元素个数为【 】A.n*n B.n*n/2 C.n*(n+1)/2 D./214.有关二叉树下列说法正确的是【 】A.二叉树的度为2 B.一棵二叉树的度可以小于2C.一棵二叉树至少有一个结点的度为2 D.二叉树中任何一个结点
5、的度为215.一棵124个叶结点的完全数，最多具有【 】个结点。A.247 B.248 C.249 D.25116.树最适合用来表示【 】A.有序数据元素 B.无序数据元素C.元素间具有分支层次关系的数据 D.元素间无联系的数据17.在一棵非空二叉树的中序遍历序列中，根结点的右边【 】A.只有右子树上的所有结点 B.只有右子树上的部分结点C.只有左子树上的部分结点 D.只有左子树上的所有结点18.对某个无向图的邻接矩阵来说【 】A.第i行上的非0元素个数等于第i列上非0元素个数B.矩阵中非0元素个数等于图中的边数C.第i行、第i列上非0元素个数等于顶点vi的度数D.矩阵中非全0行的行数等于图中
6、的顶点数19.具有4个顶点的无向完全图有【 】条边。A.6 B.12 C.16 D.2020.顺序查找法适合于存储结构为【 】的查找表。A.散列结构 B.顺序存储或链式存储C.压缩存储 D.索引存储21.采用折半查找法查找长度为n的查找表时，每个元素查找的平均查找长度为【 】A.O（） B.O() C.O(n) D. () 22.在关键字随机分布的情况下，用二叉排序树的方法进行查找，其查找长度与【 】量级相当。A.顺序查找 B.折半查找 C.分块查找 D.前三个都不正确23.散列表的平均查找长度【 】A.与冲突处理方法有关而与表的长度无关B.与冲突处理方法无关而与表的长度有关C.与冲突处理方法
7、有关且与表的长度有关D.与冲突处理方法无关且与表的长度无关24.在待排序的元素序列基本有序的前提下，效率最差的排序方法是【 】A.插入排序 B.冒泡排序 C.快速排序 D.归并排序25.就排序算法所用的辅助空间而言，堆排序、快速排序和归并排序的关系是【 】A.堆排序快速排序归并排序B.堆排序归并排序快速排序C.堆排序归并排序快速排序D.堆排序快速排序归并排序二、填空题（每空1分，共30分）1.对线性结构而言，顺序存储方法把逻辑上 （1） 存储在物理位置上 （2） 里；链式存储方法中结点间的逻辑关系是由 （3） 表示的。2.向一个长度为n的顺序表中的第i个元素之前插入一个元素时，需要向后移动 （
8、4） 个元素。3.在 （5） 链表中，删除最后一个结点的算法时间复杂度为O（1）。4.根据n个数据元素建立对应的顺序表和单链表存储结构，其算法的时间复杂度最好的情况是 （6） ，最坏的情况是 （7） 。5.如果栈的最大长度难以估计，最好使用 （8） 。6.从循环队列中插入一个元素的操作是 （9） 。7.一个串中 （10） 称为该串的子串。8.一棵二叉树第i层最多有 （11） 个结点，一棵有n个结点的满二叉树共有 （12） 个结点，共有 （13） 个叶结点。9.在一棵完全二叉树中，编号i和j的两个结点处于同一层的条件是 （14） 。10.具有n个结点的二叉树采用二叉链表存储结构，共有 （15）
9、个空指针域。11.具有n个结点的二叉树中，如果有m个叶结点，则一定有 （16） 个度为2的结点，有 （17） 个度为1的结点。12.二叉树的先序序列和中序序列相等的条件是 （18） 。13.对于n的顶点的无向图，采用邻接矩阵表示，求图中边的方法是 （19） ，判断任意两个顶点是否有边相连的方法是 （20） ，求任意顶点的度的方法是 （21） 。14.若无向图有m条边，则表示该无向图的邻接矩阵表示，求图中边的方法是 （22） 个结点。15.折半查找的存储结构仅限于 （23） ，且是 （24） 。16.分块查找法将待查找的表均匀地分成若干块且块中诸记录的顺序可以是任意的，但块与块之间 （25） 。
10、17.用二叉排序树查找，在最坏的情况下，平均查找长度为 （26） ，最好的情况下，平均查找长度为 （27） 。18.在插入和选择排序中，若初始数据基本正序，则选用 （28） ，若初始数据基本反序，则选用 （29） 。19.对n个元素的表进行直接选择排序，所需要的关键字的比较次数为 （30） 。三、简答题（共7小题40分）1.数据结构和数据类型有什么区别？（4分）2.若频繁地对一个线性表进行插入和删除操作，则该线性表宜采用何种存储结构，为什么？（4分）3.何谓队列上溢？何为假溢出现象？有哪些解决假溢出问题的方法，并分别阐述其工作原理。（6分）4.设数组A5080，其基地址为2000，每个元素占4
11、个存储单元，以行序为主序顺序存储，回答下列问题：（6分） (1)该数组有多少元素？ (2)该数组占用多少存储单元？ (3)数组元素a3030的存储地址是多少？5.有一份电文共有5个字符：a,b,c,d,e，它们出现的频率依次为4, 7, 5, 2, 9，构造对应的哈夫曼树，求哈夫曼树的带权路径长度和每个字符的哈夫曼编码。（8分）6.已知一棵二叉树的先序序列为EBADCFHGIKJ，其中序序列为ABCDEFGHIJK，求后序序列。（6分）7.设有数据集合d=1, 12，5, 8，3, 10，7, 13，9，回答下列问题：（6分）依次取d中各数据，构造一棵二叉排序树bt；如何依据此二叉排序树得到d
12、的一个有序序列。四、完善算法和算法设计题（共4小题30分）下面1、2题的每个空2分。1. 下面是二叉树中序遍历的非递归算法，读程序并在每个空格处填上一个合适的语句或表达式。 void inorder(BiTree bt) initstack(s)； p= ; while(p!=NULL|!empty(s) while(p) ; p=p-lchild; if(!empty(s) ; visit(p-data); ; 2、下面是快速排序的任意子系列L.rlow.high的一趟划分算法，读程序并在每个空格处填上一个合适的语句或表达式。 int partition(Sqlist &L,int low
13、,int high) L.r0=L.rlow; ; while(lowhigh) while (low=pivotkey) - - high; ; while( ) +low; L.rhigh=L.rlow; ; return low ; 3、写一个算法，将单链表中值重读的结点删除，使所得的结果表中各结点值均不相同（假设单链表中包含一个头结点）。（6分）4、设有两个整数集合A和B，分别用递增有序链表表示，设计一算法实现两个集合的交运算（C=AB），运算结果页用递增有序链表表示。运算后，A、B两个链表保持不变（8分）。赠送以下资料考研英语作文模板（英语一）大作文考研英语大作文一般是看图写作，从一
14、幅图分析含义及意义，所以只需要几个好的模板，根据题目套上去就行了。题目反映的意义无非三种：积极，消极和中性。所以我准备了三个不同类型的模板，到时候大家根据题目自己分析一个写作方向，再结合模板，把内容填进模板就好了。模板只是保证文章结构不过于混乱，具体的写作还希望大家多背历年写作真题和资料书上的作文，总结出自己喜欢的句子背下来，背熟之后根据原文的中文意义用自己的语言再把文章写出来，这样才能得到更好的效果。切记：模板只能起到应急和保证结构的作用，真正写好作文拿高分还需要自己不断地背诵和练习，祝大家考试顺利！模板一：积极（图画反映了什么积极现象，我们应提倡）（开头：为了避免跟大部分模板有重复之嫌，我
15、们可以在第一句写一句跟作文话题有关的句子，俗语和谚语皆可，也可以是一句关于话题的感悟。如果实在写不出可以不写）.，The picture above symbolically/subtly illustrate/demonstrate that (描述图画)。Below the drawing，there is a caption which indicates(图片下的标题).。或者：【on the drawing，there are huge Chinese characters reads ：(图片上的中文字).】Undoubtedly，we can deduce from the ca
16、rtoon that the painter is trying to show us that （主旨）.。To begin with，。In addition，.。（小结）.。As far as I am concerned ，it is high time that we highlighted the significance of and cultivated the citizensawareness that .is essential to us 。only by enforcing these measures into practice ，can our society b
17、e more harmonious，our economy be more prosperous and we，as individuals ，embrace more promising prospect。模板二：消极（图画反映了什么消极现象，我们应采取行动改变）（开头：为了避免跟大部分模板有重复之嫌，我们可以在第一句写一句跟作文话题有关的句子，俗语和谚语皆可，也可以是一句关于话题的感悟。如果实在写不出可以不写）.，The picture above symbolically/subtly illustrate/demonstrate that (描述图画)。Below the drawin
18、g，there is a caption which indicates(图片下的标题).。或者：【on the drawing，there are huge Chinese characters reads ：(图片上的中文字).】Undoubtedly，we can deduce from the cartoon that due attention has to be paid to the issue of .。The causes of this phenomenon are as follows ：To begin with，。In addition，.。Last but not
19、least ，。If we let this situation continue as it is，ourwill suffer a great destruction/damage/injury。The problem will be worse and worse 。As far as I am concerned ，It is imperative for us to take drastic and effective measures to reverse the disturbing trend revealed in the above picture。On the one h
20、and，.。on the other hand，.。Only by enforcing these measures into practice can we curb the current phenomenon/surmount this difficulty ，and we will have a brilliant future。 模板三：中性（图画反映的现象是一把双刃剑，只要好好利用）（开头：为了避免跟大部分模板有重复之嫌，我们可以在第一句写一句跟作文话题有关的句子，俗语和谚语皆可，也可以是一句关于话题的感悟。如果实在写不出可以不写）.，The picture above symbo
21、lically/subtly illustrate/demonstrate that (描述图画)。Below the drawing，there is a caption which indicates(图片下的标题).。或者：【on the drawing，there are huge Chinese characters reads ：(图片上的中文字).】Apparently，we can deduce from the cartoon that the painter is trying to attract our attention to the issue of .。A coi
22、n has two sides ，the likes a double-edged sword 。On the one hand，.。on the other hand，.。（小结）.。 As far as I am concerned，itself is not good or bad and we can benefit a lot from .as long as we take a good control over them 。Only by doing so canour society be more harmonious，our economy be more prosperous and we ，as individuals，embrace more promising prospect。
