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

沈阳工业大学2022年考研真题：807信号与系统

适用专业：085404计算机技术、081200计算机科学与技术

一、解释下列名词(共20分，每小题4分)

1、队列

2、二叉树

3、平均查找长度

4、时间复杂度

5、有向完全图

二、填空(共30分，每空3分)

1、数据的存储结构包括:顺序存储、__________、索引存储和散列存储。树形结构中的数据元素之间存在__________的关系。

2、在栈中存取数据应遵循的原则是__________。解决顺序队列“假溢出”的方法是采用__________。

3、二维数组A[0..3][0..4]的首地址是1000，每个数据元素长度是6，则A[2][3]的地址是__________。广义表(c，d)，c，d)的表尾是__________。

4、具有n个结点的完全二叉树的深度是__________。如果一棵二叉树度为2的结点个数为5，度为1的结点个数为3，那么叶子结点的个数为__________。

5、有向图G是由(V，VR)组成，其中顶点的集合V={A,B,C,D,E}，弧的集合VR={<A,B>,<A,C>,<C,B>,<C,D>,<B,D>,<E,A>,<E,B>,<E,C>}，则该图的拓扑排序序列为__________，顶点D的入度为__________。

三、解答下列问题(共50分，每题10分)

1、设一棵二叉树结点的先序遍历序列是：ABFCGDEH，中序遍历序列是：FBGCADHE，要求：

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

(2)画出该二叉树对应的森林。

(3)画出该二叉树的后序线索二叉树。

2、设一个关键字序列为{25，32，48，16，21，37，9，12}，按要求完成以下操作:

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

(2)如果哈希表的长度为12，哈希函数为H(key)=key MOD 9，用线性探测再散列方法创建哈希表，并求在等概率情况下查找成功的平均查找长度(ASL)。

3、设一组权值序列为(8，11，5，17，7，29)，按要求完成以下操作:

(1)根据权值构建哈夫曼树。

(2)写出每个权值对应的哈夫曼编码。

(3)求带权路径的长度(WPL)。

4、已知一个无向图的存储结构如下图所示:

按要求完成以下操作：

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

(2)写出无向图对应的邻接矩阵。

(3)写出从顶点V0出发深度优先和广度优先遍历的序列。

5、已知一组关键字的序列为{23,48,17,9,27,3,20,69,55}，请写出采用归并排序法对该序列作升序排序时每一趟的结果。

四、编程题，程序设计语言不限(除C、C++外请标明是哪种语言)(共50分，每题10分)

1、从键盘输入10个整数存储在一个顺序表中，再输入一个整数赋值给变量x，然后将这个顺序表划分成两部分，其中左半部分的每个整数均小于x，右半部分的每个整数均大于等于x。

2、设有两个集合A和B分别存储在两个单链表中，设计求A和B的交集C的程序，集合C也存储在一个单链表中。(集合元素类型自行定义)

3、从键盘输入二叉树数据，采用二叉链表建立二叉树，并写出对该二叉树前序遍历的递归程序。

(注意：程序前面要用文字说明键盘输入二叉树数据的格式)

4、从键盘输入一个有向图，建立一个邻接矩阵。再输入一个顶点编号num，输出编号为num的顶点的度(入度和出度之和)。

5、从键盘输入10个整数到一个一维整型数组，然后采用简单选择排序法进行排序并输出。

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