2011西南交通大学考研959真题专硕

《2011西南交通大学考研959真题专硕》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、试题代码：959西南交通大学2011年硕士研究生入学考试试题名称：数据结构考生注意：1.本试题共4题，共6页，满分150分，请认真检查；2.答题时，直接将答题内容写在考场提供的答题纸尚，答在试卷上的内容无效；3.请在答题纸上按要求填写试题代码和试题名称；4.试卷不得拆开，否则遗失后果自负。题号一二三四五六七八九十总分得分签字一、单项选择题（本大题共25题，每题2分，共50分）1.数据结构在计算机内存中的表示是指【】。A.数据的存储结构B.数据结构C.数据结构的逻辑结构C.数据元素之间的关系2.【】是数据的基本单位。A.数据项B.数据元素C.信息项D.表元素3.算法的计算量

2、的大小称为算法的【】。A.效率B.时间复杂度C.显示性D.难度4.链表不具备的特点是【】A.可随机访问任一结点B.插入删除不需要移动元素C.不必事先估算存储空间D.所需空间与其长度成正比5.设线性表有n个元素，以下操作中，【】在顺序表上实现比在链表上实现效率更高。A.输出第i（1≤i≤n）个元素的值B.顺序输出这n个元素C.交换第1个与第2个元素的值D.输出与给定值x相等的元素在线性表中的序号6.设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用【】最节省时间。A.带头结点的双循环链表B.单循环链表C.带尾指针的单循环链表D.单链表7.若长度为n的线性表采用顺序存

3、储结构，在第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,4B.3,1,2,5,4C.3,2,5,4,1D.1,4,2,3,510.队列存放在A[0…M-1]中，则入队时的操作为【】A.rear=rear+1B.rear=(rear+1)%MC.rear=(rear+1)%(M+1)D.rear=(rear+1)%(M-1)11.两个串相等必有串

4、长度相等且【】A.串的各位置字符任意B.串中各位置字符均对应相等C.两个串含有相同的字符D.两个串所含字符任意12.设有数组A[8][10]，每个元素占3个存储单元，首地址为SA，则元素[7][5]的起始地址是【】A.SA+141B.SA+144C.SA+222D.SA+22513.设有一个n*n的对称矩阵，采用压缩存储，则存入内存的元素个数为【】A.n*nB.n*n/2C.n*(n+1)/2D./214.有关二叉树下列说法正确的是【】A.二叉树的度为2B.一棵二叉树的度可以小于2C.一棵二叉树至少有一个结点的度为2D.二叉树中任何一个结点的度为215.一棵124个叶结点

5、的完全数，最多具有【】个结点。A.247B.248C.249D.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行的行数等于图中的顶点数19.具有4个顶点的无向

6、完全图有【】条边。A.6B.12C.16D.2020.顺序查找法适合于存储结构为【】的查找表。A.散列结构B.顺序存储或链式存储C.压缩存储D.索引存储21.采用折半查找法查找长度为n的查找表时，每个元素查找的平均查找长度为【】A.O（）B.O()C.O(n)D.()22.在关键字随机分布的情况下，用二叉排序树的方法进行查找，其查找长度与【】量级相当。A.顺序查找B.折半查找C.分块查找D.前三个都不正确23.散列表的平均查找长度【】A.与冲突处理方法有关而与表的长度无关B.与冲突处理方法无关而与表的长度有关C.与冲突处理方法有关且与表的长度有关D.与冲突处理方法无关且与

7、表的长度无关24.在待排序的元素序列基本有序的前提下，效率最差的排序方法是【】A.插入排序B.冒泡排序C.快速排序D.归并排序25.就排序算法所用的辅助空间而言，堆排序、快速排序和归并排序的关系是【】A.堆排序＜快速排序＜归并排序B.堆排序＜归并排序＜快速排序C.堆排序＜归并排序＜快速排序D.堆排序＜快速排序＜归并排序二、填空题（每空1分，共30分）1.对线性结构而言，顺序存储方法把逻辑上（1）存储在物理位置上（2）里；链式存储方法中结点间的逻辑关系是由（3）表示的。2.向一个长度为n的顺序表中的第i个元素之前插入一个元素时，