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

沈阳工业大学2022年考研真题：855数据结构基础

适用专业：085410人工智能

一、单项选择题(每题2分，共20分)

1、与算法时间复杂度有关的是(   )。

A、编译程序质量

B、问题规模

C、计算机硬件性能

D、程序设计语言

2、线性表的顺序存储结构和链式存储结构相比，顺序存储优点是(   )

A、所有的操作算法实现简单

B、节省存储空间

C、便于插入和删除

D、便于随机存储

3、对于队列操作数据的原则是(   )

A、先进先出

B、后进先出

C、先进后出

D、不分顺序

4、经过InitStack(s)；Push(s，a)；Push(s，b)；Puh(s，c)；Pop(s，x)；GietTop(s，x)运算后，X的值是(   )。

A、0

B、a

C、b

D、c

5、假设有二维数组A[0...4，0..5]以行序为主序顺序存储，其A[0][0]基地址为1000，A[2][3]的地址为1060，则A[3][4]的存储地址为(   )

A、1088

B、1024

C、1096

D、1040

6、二叉树是非线性数据结构，所以(   )。

A、顺序结构和链式结构都不能使用

B、不能使用链式存储结构存储

C、顺序存储结构和链式存储结构都能存储

D、不能用顺序存储结构存储

7、设深度为k的二叉树中只有度为0和度为2的结点，则此类二叉树中所包含结点数最多为(   )

A、2^k+1-1

B、2^k-1

C、2^k+1

D、2^k-1-1

8、对给定下图G，从顶点A出发应用Prim算法求其最小生成树，最后选择的一条边是(   )。

A、AC

B、CE

C、AD

D、DB

9、设一组初始记录关键字序列为(5，13，19，21，37，56，64，75，80，88，92)，则利用折半查找关键字21需要进行关键字比较次数为(   )。

A、1

B、2

C、3

D、4

10、对于关键字序列(49，38，65，97，76，13，27)，完成创建小根堆序列是(   )。

A、(13，38，27，97，76，65，49)

B、(13，97，65，76，49，27，38)

C、(13，97，76，65，49，38，27)

D、(13，38，76，65，49，27，97)

二、填空题(每题2分，共10分)

11、只设尾指针tail的带头结点的非空循环单链表，指向首元素结点的指针p满足的条件是________。

12、设循环队列的容量为20(序号从0到19)，队列中始终少用一个单元，现经过一系列的入队和出队运算后，有(1)front=10，rear=18；(2)front=18，rear=10；在这两种情况下，循环队列中分别有元素个数是(1) ________(2) ________。

13、设一组权值集合W=(3，2，4，5，1)，要求根据这些权值集合构造一棵赫夫曼树，则这棵赫夫曼树的带权路径长度为________。

14、设无向图的顶点个数为n，则该图有最多边的个数是________。

15、设一组初始记录关键字序列为(16，48，32，26，08，21，39)，则按降序的第二趟直接插入排序结束后的结果序列是________。

三、名词解释(每题4分，共20分)

16、抽象数据类型、算法

17、满二叉树、完全二叉树

18、连通图、连通分量

19、拓扑排序、关键路径

20、稳定排序、内部排序

四、算法设计题.(每题10分，共s0分)

21、设计一个算法，实现创建单链表并将单链表中所有数据值在区间[emin，emax]中的元素删除。单链表的数据结构定义如下。

typedef struct LNode {

char data；

Struct LNode *next；

}LNode，*LinkList；

22、设计一个算法，采用简单选择排序实现将单链表中所有数据值从小到大进行排序。单链表的数据结构定义如下。

typedef struct LNode {

int data；

struct LNode *next；

}LNode，*LinkList；

23、设计一个算法，统计二叉树中度为0的结点且结点数据为e的结点个数。二叉树存储结构定义如下。

typedef struct BitNode {

TElemtype data；

struct BitNode*lchild，*rchild；

}BiTNode，*BiTree；

24、设计一个非递归算法，实现二叉树先序遍历。二叉树存储结构定义如下。

typedef struct BitNode {

TElemtype data；

struct BitNode*lchild，*rchild；

}BiTNode，*BiTree；

25、设计一趟快速排序算法。待排序记录的数据结构定义如下。

typedef struct{

KeyTypekey；

}RedType；

typedef struct{

RedTyper[MAXSIZE+1]；

int length；.

}SqList；

五、综合应用题(共3题，共50分)

26、(20分)已知一棵二叉树的先序遍历的结果序列为ABDEGCFHJI，中序遍历的结果序列为DBEGACHJFI，要求：

(1)画出这棵二叉树，并写出这棵二叉树的后序遍历序列的结果。(7分)

(2)分别列出度为0，1，2的结点。(3分)

(3)画出该二叉树对应的森林。(4分)

(4)写出该二叉树对应的森林的先序遍历序列。(3分)

(5)写出该二叉树对应的森林的中序遍历序列。(3分)

27、(10分)已知一个无向图的邻接表如下图所示。

解答下列问题：

(1)画出对应的无向图。(4分)

(2)写出从顶点V1出发的深度优先遍历序列。(3分)

(3)写出从顶点V1出发的广度优先遍历序列。(3分)

28、(20分)已知一个序列关键字为{19，14，23，01，68，20，84，27，55，11，10，79}，按要求完成以下操作：

(1)画出其对应的二叉排序树，并求在等概率情况下查找成功的平均查找长度(ASL)。(6分)

(2)如果长度为16哈希表[0..15]，哈希函数为H(key)=keyMOD13，采用线性探测再散列解决冲突方法创建哈希表，并求在等概率情况下查找成功的平均查找长度(ASL)。(7分)

(3)如果哈希函数为H(key)=keyMOD13，采用链地址解决冲突方法创建哈希表，并求在等概率情况下查找成功的平均查找长度(ASL)。(7分)

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