资源描述：
《2011年暨南大学830数据结构考研试题》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。
1、2011年全国硕士研究生统一入学考试自命题试题********************************************************************************************学科与专业名称：计算机技术,软件工程考试科目代码与名称：数据结构考生注意：所有答案必须写在答题纸（卷）上，写在本试题上一律不给分。一.选择题(每题2分，共30分)1.算法分析的目的是（）。A.找出数据结构的合理性C.分析算法的效率以求改进2.下列函数中渐近时间复杂度最小的是（B.研究算法中的输入和输出关系D.分析算法的易读性和文档性）。233.线性表的动态链表
2、存储结构与顺序存储结构相比，优点是（）。A.所有的操作算法实现简单C.便于插入与删除B.便于随机存取D.便于节省存储器空间4．若进栈序列为1,2,3,4,5,6,且进栈和出栈可以穿插进行，则可能出现的出栈序列为()。A．3,2,6,1,4,5C．5,1,2,3,4,6B．5,6,4,2,3,1D．3,4,2,1,6,55.顺序存储的线性表的第一个元素的存储地址是100，每个元素的长度为4，则第4个元素的存储地址是（）。A.108B.112C.116D.1206.在任意一棵二叉树的先序序列和后序序列中，各叶子之间的相对次序关系()。A．不一定相同B．互为逆序C．都不相同D
3、．都相同7.高度为5的二叉树至多有结点数为（）。A.63B.32C.31D.648.图的邻接矩阵表示法适用于表示（）。A．无向图B．有向图C．稠密图D．稀疏图9.在一个单链表中,若p所指的结点不是最后一个结点,在p之后插入s所指的结点,则执行()。A.s->next=p;p->next=sC.p=s;s->next=p->nextB.p->next=s;s->next=pD.s->next=p->next;p->next=s10.若在线性表中采用折半查找法查找元素，该线性表应该是（）。A.元素按值有序C.元素按值有序且采用顺序存储结构B.采用顺序存储结构D.元素按值有
4、序且采用链式存储结构考试科目：数据结构共5页，第1页A.T1(n)=log2n+5000nB.T2(n)=n-8000nC.T3(n)=n+5000nD.T4(n)=2nlog2n-1000n11.已知一棵二叉树结点的先序序列为ABDGCFK,中序序列为DGBAFCK,则结点的后序序列为()。A.GDBFKCAB.DGBFKCAC.KFCABDGD.CAFKGDB12.对于元素是整数(占2个字节)的n行n列对称矩阵A,采用以行序为主的压缩存储方式存储到一维数组s[n*(n+1)/2]中(下三角),若A[1][1]的起始地址是400，问元素A[8][5]的存储地址是().A.432B.
5、563C.484D.46413.在所有排序方法中，关键字的比较次数与记录的初始排列无关的是（）。A.Shell排序B.冒泡排序C.直接插入排序D.直接选择排序14.具有6个顶点的无向图至少应有（）条边才能确保是一个连通图。A．5B．6C．7D．815.如果T2是由树T1转换而来的二叉树,那T1中结点的先序就是T2中结点的()。A.先序B.中序C.后序D.层次序二．填空题(每题2分，共20分)1.在数据结构中，数据的逻辑结构分和。2.若对关键字序列(12,18,4,3,6,13,2,9,19,8)进行快速排序（以第一个元素为支点），则第一趟排序得到的结果为3.堆排序采
6、用了记录，就建立。作为其数据结构，如果希望第一次就能找出最小关键字堆。4.二叉树中度为0的结点数为30，度为1的结点数为30，总结点数为。5.向栈中压入元素的操作是先，后。6.在的情况下，链队列的出队操作需要修改尾指针。7.所谓连通图G的生成树,是G的包含其全部n个顶点的一个极小连通子图。它必定包含且包含G的条边。8.对于一个有向图，若一个顶点的度为k1，出度为k2，则对应邻接表中该顶点单链表中的边节点数为。9.设GetHead(p)为求广义表p的表头函数，GetTail(p)为求广义表p的表尾函数。其中()是函数符号，运算GetTail(GetHead((a,b),(c,d
7、,e)))的结果是。10.对n个结点进行快速排序，最大比较次数是。三．判断题（每题1分，共10分,正确的选t，错误的选f）1．一个广义表的表尾总是一个广义表。（）2．顺序表用一维数组作为存储结构，因此顺序表是一维数组。()3．双循环链表中，任一结点的前驱指针均为不空。（）4.存储图的邻接矩阵中，邻接矩阵的大小不但与图的顶点个数有关，而且与图的边数也有关。（）5.当从一个最小堆中删除一个元素时，需要把堆尾元素填补
