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

《2018年浙江温州大学数据结构考研真题.doc》由会员分享，可在线阅读，更多相关《2018年浙江温州大学数据结构考研真题.doc（3页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、2018年浙江温州大学数据结构考研真题一、单项选择题（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.采用顺序存储的两个栈它

2、的共享空间为S1m，topi代表第i个栈（i=1，2）的栈顶，栈1的底在S1，栈2的底在Sm，则栈满的条件是（）。A. top2-top1=0B. top1+1=top2C. top1+top2=mD. top1=top25.已知二叉树有50个叶子结点，则该二叉树的总结点数至少应有（）个。A. 99B. 100C. 101D. 1026.无向图G有16条边，度为4的顶点有3个，度为3的顶点有4个，其余顶点的度均小于3，则图G至少有（）个顶点。A. 10B. 11C. 12D. 137.对于一个具有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是（）。A. nB. (n-1)/2C. n-

3、1D. n28.适合于折半查找的表的存储方式及元素排列要求为（）。A. 链接存储，元素无序B. 链接存储，元素有序C. 顺序存储，元素无序D. 顺序存储，元素有序9.排序算法的稳定性是指（）。A. 经过排序之后，能使值相同的数据保持原顺序中的相对位置不变B. 经过排序之后，能使值相同的数据保持原顺序中的绝对位置不变C. 排序算法的性能与待排序元素的数量关系不大D. 排序算法的性能与待排序元素的数量关系密切10.5个不同的数据元素进行直接插入排序，最多需要进行（）次比较。A. 8B. 14C. 15D. 25二、简答题（4小题，每小题10分，共40分）1找出满足以下条件的所有二叉树：（1）二叉树

4、的前序序列与中序序列相同；（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 low,

5、int high)int pivot;pivot=rlow;while(lowhigh)while(low=pivot)high-;rlow=rhigh;while(lowhigh & rlow=pivot)low+;rhigh=rlow; rlow=pivot; return low;void qSort(ElementType r, int low, int high)int pos;if(lowhigh)pos=partition(r, low, high);/*将rlow.high一分为二*/qSort(r, low, pos-1);/*对左边子表快速排序*/qSort(r, pos+

6、1, high);/*对右边子表快速排序*/void quickSort(ElementType r, int n)qSort(r, 1, n);三、算法设计题（共70分）1.（15分）编写一个算法，实现单链表原地逆转，逆转操作不使用额外的链表结点。单链表的存储结构描述如下：typedef int ElementType;typedef struct Node/*结点类型定义*/ElementType data;struct Node *next;Node, *LinkList;/*LinkList为结构指针类型*/给定的函数原型如下：void reverseList(LinkList L);

7、2.（15分）设计判断二叉树是否为二叉排序树的算法。二叉排序树的结构如下：typedef int KeyType;typedef struct NodeKeyType key;/*关键字的值*/struct Node *left;/*左指针*/struct Node *right;/*右指针*/BSTNode, *BSTree;3.（15分）编写一个算法，对顺序表进行二分查找。顺序表的存储结构描述如下：typedef int ElementType;typedef structElementType *array; /*存放元素的数组*/int length; /*已经有多少元素*/int c

8、apacity; /*容量*/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

9、 weight; /*边的权*/ struct ENode *nextEdge; /*指向下一条边的指针*/ENode;typedef struct VNode VertexType data; /*顶点信息*/ ENode *firstEdge; /*指向第一条依附该顶点的边的弧指针*/VNode;struct GraphStruct VNode vexsMAXVEX; 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。