资源描述：
《2016年全国硕士研究生统一入学考试自命题试题（a卷）》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、2016年全国硕士研究生统一入学考试自命题试题（A卷）********************************************************************************************学科、专业名称：计算机科学与技术、软件工程研究方向：计算机系统结构081201，计算机软件与理论081202，计算机应用技术081203，软件工程083500，计算机技术(专业学位)085211，软件工程(专业学位)085212考试科目名称及代码：数据结构830考生注意：所有
2、答案必须写在答题纸（卷）上，写在本试题上一律不给分。一、单项选择题(每题2分，共30分)1.在线索化二叉树中，T所指结点没有左子树的充要条件是（）。A.T->lchild=NULLB.T->ltag=1C.t->ltag=1且t->lchild=NullD.以上都不对2.一个带有头结点的单链表为空的判定条件是()。A.head==NULLB.head->next==NULLC.head->next==headD.head!=NULL3.线性链表不具有的特点是（）。A.随机访问B.不必预估所需存储空间大小C.插
3、入与删除时不必移动元素D.所需空间与线性表长度成正比4.在下面的排序方法中，稳定的是（）。A.希尔排序B.堆排序C.插入排序D.快速排序5.设有n个待排序的记录关键字，则在堆排序中需要（）辅助记录空间。A．O(1)B.O(n)C.O(nlog2n)D.O(n2)6.数组A［５］［６］的每个元素占5个字节，将其按行优先次序存储。假设A[1][1]元素的存储地址为1000，则元素A［５，５］的存储地址为()。A.1140B.1145C.1120D.11257.高度为n的完全二叉树的结点数至少为（ ）。A.2n-
4、1B.2n-1+1C.2nD.2n+18.设有一个无向图G=（V，E）和G’=（V’，E’），如果G’为G的生成树，则下面不正确的说法是（）。A．G’为G的子图B．G’为G的连通分量C．G’为G的极小连通子图且V’=VD．G’为G的一个无环子图9.在有向图的邻接表存储结构中，顶点V在表结点中出现的次数是（）。A.顶点V的度B.顶点V的出度C.顶点V的入度D.依附于顶点V的边数10.关键路径是事件结点网络中()。A．最短的回路B．从源点到汇点的最短路径C．最长的回路D．从源点到汇点的最长路径考试科目：数据结构共
5、5页，第1页11.一个有n个结点的无向图最多有（）条边。A.nB.n-1C.n(n-1)D.n(n-1)/212.对某个无向图的邻接矩阵来说，()。A．第i行上的非零元素个数和第i列的非零元素个数一定相等B．矩阵中的非零元素个数等于图中的边数C．第i行上，第i列上非零元素总数等于顶点vi的度数D．矩阵中非全零行的行数等于图中的顶点数13.平衡二叉树的平均查找长度是()。A.O(n2）B.O(nlog2n）C.O(n）D.O(log2n）14.下列哪种排序需要的附加存储开销最大()。A.快速排序B.堆排序C.归
6、并排序D.插入排序15.设一数列的顺序为1,2,3,4,5,6,通过栈操作可以得到（）的输出序列。A.3,2,5,6,4,1B.1,5,4,6,2,3C.6,4,3,2,5,1D.3,5,6,2,4,1二．填空题(每空2分，共20分)1.在一个长度为n的顺序表中删除第i个元素时，需向前移动个元素。2.设数组Data[0..m]作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针则执行出队操作时front指针的值应更新为front=。3.在单链表中，若要删除指针p所指结点的后一结点，则需要执行下
7、列语句：（设q为指针变量）q=p->next;；。4.在有n个结点的二叉链表中，值为NULL的链域的个数为。5.二叉树中度为0的结点数为30，度为1的结点数为30，总结点数为。6.在堆排序的过程中，对任一分支结点进行筛选运算的时间复杂度为，整个堆排序过程的时间复杂度为。7.对于n个记录（假设每个记录含d个关键字）进行链式基数排序，总共需要进行趟分配和收集。8.设有向图G中有向边的集合E={<1，2>，<2，3>，<1，4>，<4，2>，<4，3>}，则该图的一种拓扑序列为。三．判断题（每题1分，共10分，正确
8、的选t，错误的选f）1.在n个顶点的无向图中，若边数>n-1，则该图必是连通图。（）2.具有n个结点的二叉排序树有多种，其中树高最小的二叉排序树是最佳的（）3.使用散列法存储时，哈希表的大小可随意选取，通常取10的倍数。（）4.向一个二叉排序树插入新的结点时，新插入的结点总是叶子结点（）5.数据元素是数据的最小单位。（）6.普里姆(Prim)算法相对于克鲁斯卡尔(Kruskal)算法更适合求一个稀疏
