温州大学 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.采用顺序存储的两个栈它的共享空间为 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-1D.n28.适合于折半查找的表的存储方式及元素排列要求为（）。A.链接存储，元素无序B.链接存储，元素有序C.顺序存储，元素无序D.顺序存储，元素有序9.排序算法的稳定性是指（）。A.经过排序之后，能使值相同的数据保持原顺序中的相对位置不变B.经过排序之后，能使值相同的数据保持原顺序中的绝对位置不变C.排序算法的性能与待排序元素的数量关系不大D.排序算法的性能与待排序元素的数量关系密切10.5 个不同的数据元素进行直接插入排序，最多需要进行（）次比较。A.8B.14C.15D.25二、简答题二、简答题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 low,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+1,high);/*对右边子表快速排序*/void quickSort(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.设计判断二叉树是否为二叉排序树的算法。二叉排序树的结构如下：typedef 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(SeqList 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;typedef 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。