2018年浙江温州大学数据结构考研真题.doc

发布时间：2022-09-19 发布人：admin 分类：说明书资料大小：0.04M 资料格式：doc 举报版权申诉

第1页 / 共3页

第2页 / 共3页

第3页 / 共3页

文本预览

2018 年浙江温州大学数据结构考研真题）。）。）个。）。）。 B. 错误的）。 B. O(n) ）个顶点。 B. 11 B. 100 C. 101 C. O(nlogn) D. O(nlogn+n) B. top[1]+1=top[2] D. top[1]=top[2] 一、单项选择题（10 小题，每小题 4 分，共 40 分） 1.计算机所处理的数据一般具有某种内在联系，这是指（ A. 数据和数据之间存在某种关系 B. 数据元素和数据元素之间存在某种关系 C. 数据元素内部具有某种结构 D. 数据项和数据项之间存在某种关系 2.顺序存储方式只能用于线性结构，不能用于非线性结构。这个断言是（ A. 正确的 3.设某算法完成对 n 个元素进行处理，所需的时间是 T(n)=100nlog2n+200n+500，则该算法的时间复杂度是（ A. O(1) 4.采用顺序存储的两个栈它的共享空间为 S[1…m]，top[i]代表第 i 个栈（i=1，2）的栈顶，栈 1 的底在 S[1]，栈 2 的底在 S[m]，则栈满的条件是（ A. top[2]-top[1]=0 C. top[1]+top[2]=m 5.已知二叉树有 50 个叶子结点，则该二叉树的总结点数至少应有（ A. 99 D. 102 6.无向图 G 有 16 条边，度为 4 的顶点有 3 个，度为 3 的顶点有 4 个，其余顶点的度均小于 3，则图 G 至少有（ A. 10 7.对于一个具有 n 个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是（ A. n 8.适合于折半查找的表的存储方式及元素排列要求为（ A. 链接存储，元素无序 C. 顺序存储，元素无序 9.排序算法的稳定性是指（ A. 经过排序之后，能使值相同的数据保持原顺序中的相对位置不变 B. 经过排序之后，能使值相同的数据保持原顺序中的绝对位置不变 C. 排序算法的性能与待排序元素的数量关系不大 D. 排序算法的性能与待排序元素的数量关系密切 10.5 个不同的数据元素进行直接插入排序，最多需要进行（ A. 8 二、简答题（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}，请按照下面的快速排序算法，给出该序列作升序排列时前三趟的结果。 int partition(ElementType r[], int { B. 链接存储，元素有序 D. 顺序存储，元素有序）次比较。 D. 25 C. n-1 D. n2 C. 12 D. 13 B. 14 C. 15 B. (n-1)/2 ）。）。 low, int high)

int pivot; pivot=r[low]; while(low=pivot){ high--; } r[low]=r[high]; while(low

struct Node *right;/*右指针*/ }BSTNode, *BSTree; 3.（15 分）编写一个算法，对顺序表进行二分查找。顺序表的存储结构描述如下： typedef int ElementType; typedef struct{ ElementType int length; int capacity; *array; /*存放元素的数组*/ /*已经有多少元素*/ /*容量*/ }SeqList; 给定的函数原型如下： int binarySearch(SeqList list, ElementType k); 4.（25 分）给定无向带权图，编写最小生成树算法（Prim）。预置代码如下： #include #include #include #define MAXVEX 200 /*最大顶点数*/ typedef char VertexType; struct GraphStruct; typedef struct GraphStruct *Graph; typedef struct ENode{ int adjVertex; int weight; struct ENode *nextEdge; /*该边所指的顶点的位置*/ /*边的权*/ /*指向下一条边的指针*/ }ENode; typedef struct VNode{ VertexType data; ENode *firstEdge; /*指向第一条依附该顶点的边的弧指针*/ /*顶点信息*/ }VNode; struct GraphStruct{ VNode vexs[MAXVEX]; int vertexNum,edgeNum; /*图的当前顶点数和弧数*/ }; 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。

分享到：

赞收藏

资料库

2018年浙江温州大学数据结构考研真题.doc

相关推荐

考研

热门标签

最新资料