升研教育考研频道为23考研、24考研的同学们整理了“重庆理工大学2021年考研专业课真题：812数据结构”的相关信息，希望对正在备考的你有所帮助。考研复习效率不高怎么办？自己备考抓不住重点？想报考985/211等热门院校，但是没把握？升研教育推出考研集训营，全日制封闭式面授，10余年授课经验的老师，浓厚的学习氛围助你冲击目标、一战上研！

重庆理工大学2021年考研专业课真题：812数据结构

适用专业：0854电子信息

1、（15分）试给出顺序表的类型定义，并编写函数分别实现顺序表的插入和删除操作。

2、（15分）试给出链式堆栈的类型定义，并编程实现链式堆栈的入栈和出栈操作。

3、（15分）设给定权集w={5,7,2,3,6,8,9}，试写出构造关于w的一颗哈夫曼树（要求权小结点在左，权大结点在右）的过程，并求其加权路径长度WPL。

4、（15分）输入一个正整数序列{40,28,6,72,100,3,54,1,80,91,38}，建立一颗二叉排序树，然后删除结点72，试分别画出该二叉排序树及删除结点72后的二叉排序树。

5、(共30分)假设有图G=(V,E),V={1,2,3,4,5,6,7}，其邻接矩阵如下所示，

(1)（15分）画出所对应的图，并从顶点1出发使用普里姆（PRIM）算法构造出一颗最小生成树，要求写出构造过程及结果。

(2)(15分)使用迪杰斯特拉（Dijkstra）算法，求从顶点1到其他各顶点之间的最短路径，要求写出计算过程。

6、（15分）假设有图G=(V,E)，V={a,b,c,d,e},E={<a,b>,<a,c>,<d,c>,<d,e>,<b,e>,<c,e>}。试画出该图，并写出该图的所有拓扑排序。

7、（15分）已知序列{11,18,4,3,6,15,1,9,19,8}，试给出采用归并排序和插入排序对该序列作升序排序时每一趟的结果。

8、（15分）编程实现快速排序算法，并给出其时间复杂度。

9、（15分）设哈希表为T[0,…,12],哈希函数为H(key)=key%13，键值序列为{39,36,28,38,44,15,42,12,6,25}。试画出线性探测法处理冲突所构造的哈希表，并求出查找成功时的平均查找长度。

【24考研辅导课程推荐】24考研集训营、周末辅导班、一对一辅导，相关课程都配有内部讲义及书籍资料，同时还有辅导老师进行学习规划及全程督学，详情可直接在线咨询。