哈夫曼树的度一定为2_构造哈夫曼树左子树权值小于右子树

温州大学2021年考研真题：826数据结构 　　2021年硕士研究生招生考试试题 　　科目代码及名称：826 数据结构 　　适用专业（方向）：081200 计算机科学与技术 　　请考生按规定用笔将所有试题的答案写在答题纸上，在此试题纸上答题无效 　　一、单项选择题（共10小题，每小题4分，共40分） 　　1. 数组的逻辑结构不同于下列（    ）的逻辑结构。 　　A．线性表                        B．栈   　　C．队列                          D．树 　　2.采用开放定址法处理散列表的冲突时，其平均查找长度（   ）。 　　A．低于链接法处理冲突         B．高于链接法处理冲突 　　C．与链接法处理冲突相同       D．高于二分查找 　　3. 一个线性表中最常用操作是根据第i个素其前驱节点i-1，则（    ）方式存储最节省存储空间。 　　A．单链表       B．循环双链表      C．循环单链表      D．顺序表 　　4. 哪种遍历方式在遍历它的左子树和右子树之前遍历它自身？（    ） 　　A．后序遍历                              B．先序遍历 　　C．中序遍历                              D．层次遍历 　　5.设有一个二维数组Data[m][n]，假设Data[0][0]存放位置在921，Data[2][2]存放位置在965，每个素占一个空间，问Data[3][3]存放在（    ）位置？ 　　A．987          B．986        C．985        D．996 　　6.设栈Stack和队列Que的初始状态为空，素a1、a2、a3、a4、a5和a6依次通过栈Stack，一个素出栈后即进入队列Que。若6个素出列的顺序为a2、a4、a3、a6、a5和a1，则栈Stack的容量至少应该是（      ）。 　　A．6                            B．4 　　C．3                            D．2 　　7. 下列四种排序中（    ）的空间复杂度最大。 　　A．插入排序                              B．冒泡排序 　　C．归并排序                              D．堆排序 　　8. 用指向左、右孩子结点的二个引用域的二叉链表存储有n个结点的二叉树，则一共有(     )  个空的引用域。 　　A．n+ 1       B．n-1       C．n      D．不能确定 　　9. 设一组初始记录关键字序列(25，12，26，23，38)，以第一个记录关键字25为基准进行一趟快速排序的结果为（    ）。 　　A．12，23，25，38，26                   B．23，12，25，38，26 　　C．23，12，25，26，38                   D．12，23，26，25，28 　　10.设数组data[MAX]作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行出队操作后其头指针front值为（    ） 　　A．front=front+1                     B．front=(front+1)%( MAX -1) 　　C．front=(front-1)% MAX              D．front=(front+1)% MAX 　　二、分析题（共5小题，每小题10分，共50分） 　　1. 从给定二叉树的先序和中序遍历序列，可以构造一棵二叉树。已知先序遍历序列为{ ABCDEFGH }，中序遍历序列为{ DCBEAGFH }，完成以下要求。 　　（1）实现由先序、中序构造二叉树程序（7分）。 　　（2）画出构造的二叉树（3分）。 　　注：将下述代码抄写到答题纸上，并在答题纸上编写完成createBTree函数的代码。 　　typedef struct Node{ 　　      ElementType data; 　　      struct Node *left; 　　      struct Node *right; 　　}BTNode, *BTree; 　　int pre[MAX],in[MAX]; //存放先序、中序遍历序列 　　//先序、中序遍历构造二叉树 　　//b1，t1分别是先序序列的下界（下标）和上界（下标） 　　//b2，t2分别是中序序列的下界（下标）和上界（下标） 　　BTree createBTree(int b1, int t1, int b2, int t2) 　　{   　　} 　　2. 用普里姆算法构造图1所示的无向图从顶点v0开始的最小生成树。完成以下要求。 　　（1）从图2开始，依次画出最小生成树生成过程（6分）。 　　（注：从图2开始，根据算法过程，每幅图依次增加一个顶点及相应的边。图n中应保留图n-1的所有顶点和边。） 　　（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 doubleLinkedListHeadInsert(DoubleLinkedList *dlList, ELEMTYP x)   //函数原型 　　{ 　　} 　　4. 在如图的平衡二叉树节点A的左子树的左子树上插入节点5，导致平衡二叉树不平衡，完成以下要求。 　　（1）绘出调整后的平衡二叉树（6分）。 　　（2）指出这种失衡的类型并简要其调整过程（4分）。 　　
　　5.某工程中AOE网如下图所示。为了更好的完成工作，需要帮助他们找出关键活动和关键路径。请回答下列问题： 　　
　　（1）各事件的最早发生时间和最晚发生时间（4分）。 　　V0 　　V1 　　V2 　　V3 　　V4 　　V5 　　最早发生时间 　　最晚发生时间 　　（2）各活动的最早开始时间和最晚开始时间（4分）。 　　a1 　　a2 　　a3 　　a4 　　a5 　　a6 　　a7 　　a8 　　最早开始时间 　　最晚开始时间 　　（3）关键路径：____________；关键路径的长度：____________（2分）。 　　三、综合应用题（共4小题，每小题15分，共60分） 　　1. 调整整数数组array[]中的素位置，并返回分界位置i，使所有值为奇数的素均落在array[1..i]上，使所有值为偶数的素均落在array[i＋1..h]上。 　　要求：（1）时间复杂度为O(n)、空间复杂度为O(1)；（2）算法用下面的函数原型表示。 　　注：将下述代码抄写到答题纸上，并在答题纸上编写完成arrange函数的代码。 　　/*顺序表结构*/ 　　typedef int ElementType; 　　typedef struct{ 　　ElementType array[MAX]; /*存放素的数组*/ 　　int length;   /*已经有多少素*/ 　　int capacity;    /*容量*/ 　　}*SeqList; 　　int arrange(SeqList list) 　　{ 　　} 　　2. 邻接矩阵法存储有向图及度的计算： 　　（1）写出图中有向图的邻接矩阵（6分）。 　　（2）计算图中各顶点的出度、入度和度（6分）。 　　（3）描述根据有向图的邻接矩阵计算有向图的度的算法（3分）。 　　 
　　3. 假设用于通信的电文由字符集{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:2×2+3, LB:3×3+x2+1, LA和LB相加后得到LA：3×3+3×2+4。 　　注：将下述代码抄写到答题纸上，并在答题纸上编写完成polyAdd函数的代码。 　　struct Node{  //链表的数据结构 　　    int coef;  //系数 　　    int expon;  //指数 　　    struct Node* next; 　　}Node,*LinkList; 　　void polyAdd(LinkList poly1,LinkList poly2)//计算多项式的和 　　{ 　　} 　　相关推荐： 　　考研政治/英语/数学/专业课历年真题汇总 　　历年考研复试分数线汇总 　　扫一扫二维码，加入考研群  　　
  　　超多干货福利随机掉落，志同道合小伙伴随时交流~ 　　扫一扫二维码，233考研   　　
　　最新资讯第一时间知晓，备考经验技巧专栏传授