资源描述
2018 年硕士研究生招生考试试题（A 卷）科目代码及名称：831 数据结构 适用专业：081201 计算机系统结构081202 计算机软件与理论第 1 页，共 4 页（请考生在答题纸上答题，在此试题纸上答题无效）一、 单项选择题（10 小题，每小题 4 分，共 40 分）1. 计算机所处理的数据一般具有某种内在联系，这是指（ ） 。A. 数据和数据之间存在某种关系B. 数据元素和数据元素之间存在某种关系C. 数据元素内部具有某种结构D. 数据项和数据项之间存在某种关系2. 顺序存储方式只能用于线性结构，不能用于非线性结构。这个断言是（ ） 。A. 正确的 B. 错误的3. 设某算法完成对 n 个元素进行处理，所需的时间是 T(n)=100nlog2n+200n+500，则该算法的时间复杂度是（ ） 。A. O(1) B. O(n) C. O(nlogn) D. O(nlogn+n)4. 采用顺序存储的两个栈它的共享空间为 S1m，topi代表第 i 个栈（i=1 ，2）的栈顶，栈 1 的底在 S1，栈 2 的底在 Sm，则栈满的条件是（ ） 。A. top2-top1=0 B. top1+1=top2C. top1+top2=m D. top1=top25. 已知二叉树有 50 个叶子结点，则该二叉树的总结点数至少应有（ ）个。A. 99 B. 100 C. 101 D. 1026. 无向图 G 有 16 条边，度为 4 的顶点有 3 个，度为 3 的顶点有 4 个，其余顶点的度均小于 3，则图 G 至少有（ ）个顶点。A. 10 B. 11 C. 12 D. 137. 对于一个具有 n 个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是（ ） 。A. n B. (n-1)/2 C. n-1 D. n28. 适合于折半查找的表的存储方式及元素排列要求为（ ） 。A. 链接存储，元素无序 B. 链接存储，元素有序C. 顺序存储，元素无序 D. 顺序存储，元素有序9. 排序算法的稳定性是指（ ） 。A. 经过排序之后，能使值相同的数据保持原顺序中的相对位置不变B. 经过排序之后，能使值相同的数据保持原顺序中的绝对位置不变C. 排序算法的性能与待排序元素的数量关系不大D. 排序算法的性能与待排序元素的数量关系密切10. 5 个不同的数据元素进行直接插入排序，最多需要进行（ ）次比较。A. 8 B. 14 C. 15 D. 25二、 简答题（4 小题，每小题 10 分，共 40 分）1 找出满足以下条件的所有二叉树：（1）二叉树的前序序列与中序序列相同；（2）二叉树的中序序列与后序序列相同；（3）二叉树的前序序列与后序序列相同。2 假设通讯电文中只用到 A，B，C，D，E，F 六个字母，它们在电文中出现的相对频率分别为：8，3，16，10，5，20。 （1）构造哈夫曼树。 （2）计算该哈夫曼树的带权路径长度 WPL。3 己知序列355，672，91 ，83，781，34，410，76，125 ，320 ，建大根堆。4 已知序列12, 2, 16, 30, 8, 28, 4, 10, 20, 6, 18，请按照下面的快速排序算法，给出该序列作升序排列时前三趟的结果。2018 年硕士研究生招生考试试题（A 卷）科目代码及名称：831 数据结构 适用专业：081201 计算机系统结构081202 计算机软件与理论第 2 页，共 4 页int partition(ElementType r, int low, int high)int pivot;pivot=rlow;while(low=pivot)high-;rlow=rhigh;while(low#include#include#define MAXVEX 200 /*最大顶点数*/typedef char VertexType;struct GraphStruct;typedef struct GraphStruct *Graph;typedef struct ENodeint adjVertex; /*该边所指的顶点的位置*/int weight; /*边的权*/struct ENode *nextEdge; /*指向下一条边的指针*/ENode;typedef struct VNodeVertexType data; /*顶点信息 */ENode *firstEdge; /*指向第一条依附该顶点的边的弧指针*/VNode;struct GraphStructVNode vexsMAXVEX;int vertexNum,edgeNum; /*图的当前顶点数和弧数*/2018 年硕士研究生招生考试试题（A 卷）科目代码及名称：831 数据结构 适用专业：081201 计算机系统结构081202 计算机软件与理论第 4 页，共 4 页;int Prim(Graph g, VertexType u);int main()Graph g=createGraph();/* 此处由测试代码自动添加，用于测试 int Prim(Graph g, VertexType u);函数，你无需关心具体测试代码*/return 0;/*你的代码将被放在此处之后，请完成 */请注意：你只需完成 int Prim(Graph g, VertexType u);函数。该函数用 Prim 算法求 g 的最小生成树的权，如果最小生成树不存在，则返回-1。
展开阅读全文