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

试题代码：959 西南交通大学2011年硕士研究生入学考试 试题名称：数据结构 考生注意： 本试题共4题，共6页，满分150分，请认真检查； 答题时，直接将答题内容写在考场提供的答题纸尚，答在试卷上的内容无效； 请在答题纸上按要求填写试题代码和试题名称； 试卷不得拆开，否则遗失后果自负。 题号 一 二 三 四 五 六 七 八 九 十 总分 得分 签字 一、单项选择题（本大题共25题，每题2分，共50分） 1.数据结构在计算机内存中的表示是指【 】。 A.数据的存储结构 B.数据结构 C.数据结构的逻辑结构 C.数据元素之间的关系 2.【 】是数据的基本单位。 A.数据项 B.数据元素 C.信息项 D.表元素 3.算法的计算量的大小称为算法的【 】。 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的线性表采用顺序存储结构，在第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,4 C.3,2,5,4,1 D.1,4,2,3,5 10.队列存放在A[0…M-1]中，则入队时的操作为【 】 A.rear=rear+1 B.rear=(rear+1)%M C.rear=(rear+1)%(M+1) D.rear=(rear+1)%(M-1) 11.两个串相等必有串长度相等且【 】 A.串的各位置字符任意 B.串中各位置字符均对应相等 C.两个串含有相同的字符 D.两个串所含字符任意 12.设有数组A[8][10]，每个元素占3个存储单元，首地址为SA，则元素[7][5]的起始地址是【 】 A.SA+141 B.SA+144 C.SA+222 D.SA+225 13.设有一个n*n的对称矩阵，采用压缩存储，则存入内存的元素个数为【 】 A.n*n B.n*n/2 C.n*(n+1)/2 D./2 14.有关二叉树下列说法正确的是【 】 A.二叉树的度为2 B.一棵二叉树的度可以小于2 C.一棵二叉树至少有一个结点的度为2 D.二叉树中任何一个结点的度为2 15.一棵124个叶结点的完全数，最多具有【 】个结点。 A.247 B.248 C.249 D.251 16.树最适合用来表示【 】 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个顶点的无向完全图有【 】条边。 A.6 B.12 C.16 D.20 20.顺序查找法适合于存储结构为【 】的查找表。 A.散列结构 B.顺序存储或链式存储 C.