1、绝密考试结束前2021年硕士研究生招生考试试题科目代码及名称：826 数据结构 适用专业（方向）：081200 计算机科学与技术请考生按规定用笔将所有试题的答案写在答题纸上，在此试题纸上答题无效一、单项选择题（共10小题，每小题4分，共40分）1. 数组的逻辑结构不同于下列（ ）的逻辑结构。A线性表 B栈 C队列 D树2. 采用开放定址法处理散列表的冲突时，其平均查找长度（ ）。A低于链接法处理冲突 B高于链接法处理冲突C与链接法处理冲突相同 D高于二分查找3. 一个线性表中最常用操作是根据第i个元素获取其前驱节点i-1，则（ ）方式存储最节省存储空间。A单链表 B循环双链表 C循环单链表 D
2、顺序表4. 哪种遍历方式在遍历它的左子树和右子树之前遍历它自身？（ ）A后序遍历 B先序遍历C中序遍历 D层次遍历5. 设有一个二维数组Datamn，假设Data00存放位置在921，Data22存放位置在965，每个元素占一个空间，问Data33存放在（ ）位置？ A987 B986 C985 D9966. 设栈Stack和队列Que的初始状态为空，元素a1、a2、a3、a4、a5和a6依次通过栈Stack，一个元素出栈后即进入队列Que。若6个元素出列的顺序为a2、a4、a3、a6、a5和a1，则栈Stack的容量至少应该是（ ）。A6 B4C3 D27. 下列四种排序中（ ）的空间复杂度
3、最大。A插入排序 B冒泡排序C归并排序 D堆排序8. 用指向左、右孩子结点的二个引用域的二叉链表存储有n个结点的二叉树，则一共有( ) 个空的引用域。An+ 1 Bn-1 Cn D不能确定9. 设一组初始记录关键字序列(25，12，26，23，38)，以第一个记录关键字25为基准进行一趟快速排序的结果为（ ）。A12，23，25，38，26 B23，12，25，38，26C23，12，25，26，38 D12，23，26，25，2810. 设数组dataMAX作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行出队操作后其头指针front值为（ ）Afront=fron
4、t+1 Bfront=(front+1)%( MAX -1)Cfront=(front-1)% MAX Dfront=(front+1)% MAX二、分析题（共5小题，每小题10分，共50分）1. 从给定二叉树的先序和中序遍历序列，可以构造一棵二叉树。已知先序遍历序列为 ABCDEFGH ，中序遍历序列为 DCBEAGFH ，完成以下要求。（1）实现由先序、中序构造二叉树程序（7分）。（2）画出构造的二叉树（3分）。注：将下述代码抄写到答题纸上，并在答题纸上编写完成createBTree函数的代码。typedef struct Node ElementType data; struct Nod
5、e *left; struct Node *right;BTNode, *BTree;int preMAX,inMAX; /存放先序、中序遍历序列/先序、中序遍历构造二叉树/b1，t1分别是先序序列的下界（下标）和上界（下标）/b2，t2分别是中序序列的下界（下标）和上界（下标）BTree createBTree(int b1, int t1, int b2, int t2) 2. 用普里姆算法构造图1所示的无向图从顶点v0开始的最小生成树。完成以下要求。（1）从图2开始，依次画出最小生成树生成过程（6分）。（注：从图2开始，根据算法过程，每幅图依次增加一个顶点及相应的边。图n中应保留图n-1
6、的所有顶点和边。）（2） 简述普里姆算法（4分）。3. 双链表的数据结构如下所示。请实现在双链表的表头节点之后插入新节点操作。注：将下述代码抄写到答题纸上，并在答题纸上编写完成doubleLinkedListHeadInsert函数的代码。typedef struct DNode /数据结构ELEMTYP data;struct DNode *prev;struct DNode *next;DNode;typedef struct DoubleLinkedList /数据结构DNode *head;int len;DoubleLinkedList;int doubleLinkedListHea
7、dInsert(DoubleLinkedList *dlList, ELEMTYP x) /函数原型4. 在如图的平衡二叉树节点A的左子树的左子树上插入节点5，导致平衡二叉树不平衡，完成以下要求。（1）绘出调整后的平衡二叉树（6分）。（2）指出这种失衡的类型并简要其调整过程（4分）。5. 某工程中AOE网如下图所示。为了更好的完成工作，需要帮助他们找出关键活动和关键路径。请回答下列问题：（1）各事件的最早发生时间和最晚发生时间（4分）。V0V1V2V3V4V5最早发生时间最晚发生时间（2）各活动的最早开始时间和最晚开始时间（4分）。a1a2a3a4a5a6a7a8最早开始时间最晚开始时间（3）
8、关键路径：_；关键路径的长度：_（2分）。三、综合应用题（共4小题，每小题15分，共60分）1. 调整整数数组array中的元素位置，并返回分界位置i，使所有值为奇数的元素均落在array1.i上，使所有值为偶数的元素均落在arrayi1.h上。要求：（1）时间复杂度为O(n)、空间复杂度为O(1)；（2）算法用下面的函数原型表示。注：将下述代码抄写到答题纸上，并在答题纸上编写完成arrange函数的代码。/*顺序表结构*/typedef int ElementType;typedef structElementType arrayMAX;/*存放元素的数组*/int length;/*已经有
9、多少元素*/int capacity; /*容量*/*SeqList;int arrange(SeqList list) 2. 邻接矩阵法存储有向图及度的计算：（1）写出图中有向图的邻接矩阵（6分）。（2）计算图中各顶点的出度、入度和度（6分）。（3）描述根据有向图的邻接矩阵计算有向图的度的算法（3分）。ABCDFEABCDFE3. 假设用于通信的电文由字符集a, b, c, d, e, f, g, h中的字符组成，这8个字符在电文中出现的频率为0.07, 0.19, 0.02, 0.06, 0.32, 0.03, 0.21,0.10。（1）画出哈夫曼树（8分）。（2）计算最小带权路径和（3分）。（3）给出各字符的编码，左孩子编号0，右孩子编号1（4分）。4. 编写一个算法，用下面指定的链表结构实现两个多项式相加。如LA:2x2+3, LB:3x3+x2+1, LA和LB相加后得到LA：3x3+3x2+4。注：将下述代码抄写到答题纸上，并在答题纸上编写完成polyAdd函数的代码。struct Node /链表的数据结构 int coef; /系数 int expon; /指数 struct Node* next;Node,*LinkList;void polyAdd(LinkList poly1,LinkList poly2)/计算多项式的和第 9 页 共 9 页
