2014暨南大学数据结构考研真题

《2014暨南大学数据结构考研真题》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、.WORD文档下载可编辑.2013年全国硕士研究生统一入学考试自命题试题（副卷）********************************************************************************************学科与专业名称：计算机技术，软件工程考试科目代码与名称：830数据结构考生注意：所有答案必须写在答题纸（卷）上，写在本试题上一律不给分。一.选择题(每题2分，共30分)1．在数据结构中，从逻辑上可以把数据分为（）。A.动态结构和静态结构B.紧凑结构和非紧凑结构C.线性结构和非线性结构D.内部结构和外部

2、结构2.设某无向图中有n个顶点e条边，则该无向图中所有顶点的度之和为（）。A．nB.eC.2nD.2e3.在内部排序中,排序时不稳定的有()。A.插入排序B.冒泡排序C.快速排序D.归并排序4.在循环队列中，若front与rear分别表示队头元素和队尾元素的位置，则判断循环队列空的条件是()。A．front==rear+1B．rear==front+1C．front==rearD．front==05.设单链表中指针p指着结点A,若要删除A之后的结点(若存在),则需要修改指针的操作为()。A.p->next=p->next->nextB.p=p->nextC.p

3、=p->next->nextD.p->next=p6.最坏情况下堆排序的时间复杂度是()。A.O(log2n)B.O(log2n2)C.O(nlog2n)D.O(n2)7.设使用的邻接表表示某有向图，则顶点vj在表结点中出现的次数等于（）。A.顶点vj的度B.顶点vj的出度C.顶点vj的入度D.无法确定8．树最适合用来表示（）。A．有序数据元素B．无序数据元素C．元素之间具有分支层次关系的数据D．元素之间无联系的数据9．具有n个顶点的连通图至少应有（）条边。A．n-1B．nC．n(n-1)/2D．2n10.时间复杂度不受数据初始状态影响而恒定为O(nlog2n

4、）的是（）。A．堆排序B．冒泡排序C．希尔排序D．快速排序考试科目：数据结构共6页，第1页专业资料整理分享.WORD文档下载可编辑.11．任何一颗二叉树的叶子结点在前序、中序、后序遍历序列中的相对次序（）。A．不变B．发生改变C．不能确定D．以上全不对12.一组记录（50，40，95，20，15，70，60，45，80）进行冒泡排序时，第一趟需进行相邻记录的交换的次数为（）。A.5B.6C.7D.813.循环队列中是否可以插入下一个元素（）。A.与曾经进行过多少次插入操作有关.B.只与队尾指针的值有关,与队头指针的值无关.C.只与数组大小有关,与队首指针和队尾

5、指针的值无关D.与队头指针和队尾指针的值有关.14.某二叉树的先序遍历序列为abdgcefh,中序遍历序列为dgbaechf，则它的左子树的结点数目为（）。A．3B．4C．5D．615.对于元素是整数(占2个字节)的对称矩阵A,采用以行序为主的压缩存储方式(下三角),若A[0][0]的地址是400,则元素A[8][5]的存储地址是（C）。A.440B.480C.482D.582二．填空题(每题2分，共20分)1．稀疏矩阵一般的压缩存储方法主要有两种，即和。2．线性结构中元素之间存在的关系，树形结构中元素之间存在的关系。3．由n个权值构成的哈夫曼树共有个结点。4

6、．在散列表(hash)查找中，评判一个散列函数优劣的两个主要条件是：和。5．线索二叉树的左线索指向，右线索指向。6．在一棵二叉树中，度为零的结点的个数为n0，度为2的结点的个数为n2，则该二叉树有个叶子结点。7．有一个100×90的稀疏矩阵，非0元素有10，设每个整型数占2个字节，则用三元组表示该矩阵时，所需的字节数是。8．带头结点的循环单链表L为空的条件是。9．设给定权值集合w={9,2,5,7}，对应huffman树的加权路径长度WPL为。10．若某记录序列的关键字序列是（50，40，95，20，15，70），用简单选择法进行排序，第一次收集的结果是。考试

7、科目：数据结构共6页，第2页专业资料整理分享.WORD文档下载可编辑.三．判断题（每题1分，共10分，正确的选t，错误的选f）1．采用邻接表存储的图的深度优先遍历相当于树的中序遍历。（）2．无向图的邻接矩阵一定是对称的。（）3．线性表中的每一个元素都有一个前驱和后继元素。（）4．B和B+树都能有效地支持随机查找。（）5．拓扑排序是按AOE网中每个结点事件的最早发生事件对结点进行排序。（）6．一颗满二叉树同时又是一颗平衡树。（）7．对初始堆进行层次遍历可以得到一个有序序列。（）8.冒泡排序是稳定的。()9.哈夫曼树中权值最小的结点离跟最近。（）10．带权无向图的

8、最小生成树是唯一的。()四.简答题（5