《温州大学2022年[数据结构]考研真题》由会员分享,可在线阅读,更多相关《温州大学2022年[数据结构]考研真题(7页珍藏版)》请在金锄头文库上搜索。
1、温州大学 2022 年数据结构考研真题温州大学 2022 年数据结构考研真题一、单项选择题一、单项选择题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
3、.nB.(n-1)/2C.n-1D.n28.适合于折半查找的表的存储方式及元素排列要求为()。A.链接存储,元素无序B.链接存储,元素有序C.顺序存储,元素无序D.顺序存储,元素有序9.排序算法的稳定性是指()。A.经过排序之后,能使值相同的数据保持原顺序中的相对位置不变B.经过排序之后,能使值相同的数据保持原顺序中的绝对位置不变C.排序算法的性能与待排序元素的数量关系不大D.排序算法的性能与待排序元素的数量关系密切10.5 个不同的数据元素进行直接插入排序,最多需要进行()次比较。A.8B.14C.15D.25二、简答题二、简答题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,int high)int pivot
5、;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+1,high);/*对右边子表快速排序*/void qu
6、ickSort(ElementType r,int n)qSort(r,1,n);三、算法设计题三、算法设计题1.编写一个算法,实现单链表原地逆转,逆转操作不使用额外的链表结点。单链表的存储结构描述如下:typedef int ElementType;typedef struct Node/*结点类型定义*/ElementType data;struct Node*next;Node,*LinkList;/*LinkList 为结构指针类型*/给定的函数原型如下:void reverseList(LinkList L);2.设计判断二叉树是否为二叉排序树的算法。二叉排序树的结构如下:typed
7、ef int KeyType;typedef struct NodeKeyType key;/*关键字的值*/struct Node *left;/*左指针*/struct Node *right;/*右指针*/BSTNode,*BSTree;3.编写一个算法,对顺序表进行二分查找。顺序表的存储结构描述如下:typedef int ElementType;typedef structElementType *array;/*存放元素的数组*/int length;/*已经有多少元素*/int capacity;/*容量*/SeqList;给定的函数原型如下:int binarySearch(S
8、eqList list,ElementType k);4.给定无向带权图,编写最小生成树算法(Prim)。预置代码如下:#include#include#include#define MAXVEX 200/*最大顶点数*/typedef char VertexType;struct GraphStruct;typedef struct GraphStruct*Graph;typedef struct ENodeint adjVertex;/*该边所指的顶点的位置*/int weight;/*边的权*/struct ENode*nextEdge;/*指向下一条边的指针*/ENode;typede
9、f struct VNodeVertexType data;/*顶点信息*/ENode*firstEdge;/*指向第一条依附该顶点的边的弧指针*/VNode;struct GraphStructVNode 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。