【明德尚行教育】2022年广外846数据结构专业课考研初试回忆真题

sunshine

【明德尚行教育】2022年广外846数据结构专业课考研初试回忆真题

活动福利：凡是参与了本次回忆试题活动的考生，并联系我们的工作人员登记好了相关信息（姓名、专业、微信号和QQ号）

①加入我们提供的内部复试群，享受群内一次集中复试答疑指导；（群人数超过30人）群内提供免费的复试相关资料和复试信息！

②免费享有复试研究生学姐录制的复试辅导学课视频课件（大部分热门专业）

③免费享有复试导学直播课（大部分热门专业，价值59）

④针对所有2022年考生特别优秀也可参与100元奖学金活动！

活动对象：所有12月份参加研究生考试，报考广外所有专业的同学！

活动内容：诚邀参加了12月份初试的同学，在考试后能尽快联系我们提供专业课回忆版试题！即有神秘福利等着大家哦~~~

提供方式：

1.将整理好内容可以以邮件的方式发送到3058372634@qq.cpm（备注专业！）

2.添加微信：kaoyanvip00【刘老师】 发送整理好的内容、文档给到工作人员！

3.用个人论坛账号将回忆试题的内容发布到论坛 ，或者是评论帖子，以跟帖的形式在此贴回复！！

广外研招信息

一、选择题（10小题，每题2分，共20分）
1. 用P代表入栈，O代表出栈。栈的初始状态和最终状态都为空，则下列栈操作正确的是( )。
APOOPOOPP
BPOPOPOOP
CPPPOOOPP
D．PPPOOPOO
2.  从长度为n的链表中取任意一个节点的时间复杂度是(    )。
A、O(1)
B、O(n)
C、O(n^2)
D、O((n+1)/2)
3.  在内部排序中,排序时不稳定的有(      ) 。
    A. 插入排序     B. 冒泡排序       C. 快速排序        D.归并排序
4. 设有一个二维数组A[m][n]，假设A[0][0]存放位置在644 (10进制)，A[2][2]存放位置在676，每个元素占一个空间，问A[3][3]存放在什么位置？（ ）（和此题类似具体数字记不清）。
       A．688          B．678        C．692        D．696
5．对线性表进行折半查找时,要求线性表必须  (      ) 。
    A.以顺序方式存储          B. 以顺序方式存储,且结点按关键字有序排序
C. 以链接方式存储         D.以链接方式存储,且结点按关键字有序排序
6.  当有1024个关键字要选出最大的前五个以下哪些算法最优（   ）
A. 希尔排序      B. 堆排序       C. 冒泡    D. 直接插入
7.  设某棵二叉树中有2000个结点，则该二叉树的最小高度为（  ）。
         A. 9            B. 10            C. 11           D. 12
8. 在内部排序中,排序时不稳定的有(      ) 。
    A. 插入排序     B. 冒泡排序       C. 快速排序        D.归并排序

9．设有一个无向图G=（V，E）和G’=（V’，E’），如果G’为G的生成树，则下面不正确的说法是（      ）。
A．G’为G 的子图                     B．G’为G 的连通分量
C．G’为G的极小连通子图且V’=V     D．G’为G的一个无环子图
10. 栈顶元素出栈时top指针如何变化（     ）。
A. 不变                         B. top-1   
C. top++                       D. top=0       

二、填空题（15空，每空2分，共30分）
1. 若使用二叉链表作为树的存储结构，在有n个结点的二叉链表中非空的链域的个数为_________。
2. 算法中的五个基本特性是：输入，输出，_________和                ，________
3. 设某棵二叉树中有2000个结点，则该二叉树的最小高度为_______。
4.  在单链表中，若要删除指针p所指结点的后一结点，则需要执行下列语句：（设q为指针变量）q=p->next;                ；                   。

5. 循环队列SQ的存储空间为M，front为队头指针，rear为队尾指针
则队列长度为                。
6.  设GetHead(p)为求广义表p的表头函数，GetTail(p)为求广义表 p的表尾函数。其中()
是函数符号，运算GetTail(GetHead((ab)(cde)))的结果是__________
7. 在一棵二叉树上，度为零的结点的个数为n0，度为2的结点的个数为n2，则n0的值为___________。
8. 在有n个叶子结点的哈夫曼树中，其结点总数为_________其空的链域的个数为_________。
9. 下面程序段的功能实现数据Key查找，要求在下划线处填上正确的语句。
bool contain(Node* node, Key key){

        if( node == NULL )
            return false;

        if( key == node->key )
           _________
        else if( key < node->key )
            return contain( _________ );
        else // key > node->key
            return contain( _________ );
    }
三、简答题（4小题，每题10分，共40分）
1.  算法的 时间复杂度是否只和问题大小的规模相关？
2.  都有哪些常见的存储方式，简单说明其特点。
3.  树，森林为什么转成二叉树数据结构，其主要目的是什么？
4.  简单说明队列的性质，和其基本呢的用途（至少两种）。

四、应用题（4小题，每题10分，共40分）
1. 设用于通信的电文由字符集{a, b,c,d,e,f,g}中的字母构成，它们在电文中出现的频度分别为{0.34,0.12,0.10,0.08,0.13,0.20,0.03},如何为这7个字母设计二进制前缀编码使得电文总长最短，写出编码过程（和此题类似 数字记不清了）
2. 已知待散列的线性表为（ 36 ， 15 ， 40 ， 63 ， 22 ），散列用的一维地址空间为 [0..6] ，假定选用的散列函数是 H （ K ） = K mod 7 ，若发生冲突采用线性探查法处理.（于此题类似具体数字记不清）
试： （ 1 ）计算出每一个元素的散列地址并写出散列表，并求出冲突次数： `


3.  已知一有向图的邻接表存储结构如下图所示。











（1）画出此图
（2）根据有向图的深度优先遍历算法和广度优先遍历算法，从顶点 v1 出发，所得到的顶点序




4.  写出用希尔排序将关键字序列{54,23,89,48,64,50,25,90,34,72}排序过程的每一趟结果（于此题类似具体数据记不清了）

五、算法设计题 （2题，每题10分，共20分）
1.  设有两个集合A和集合B，要求设计生成集合C=A∩B的算法，其中集合A、B和C用链式存储结构表示。
2.  编写一算法判断无向图中任意给定的两个顶点之间是否存在一条长度为k的简单路径（即不含回路）。

广外考研报录比

选择题
设有图G1有点集V1、边集E1，图G2有点集V2、边集E2。V1是V2的子集，E1是E2的子集，正确的是
A.G1是G2子图  B.G2是G1子图  C.G1是G2连通分量  D.G2是G1连通分量

填空题
1.一哈夫曼树有50个叶节点，问二叉链表下，有多少空指针域。
2.算法的五大特性是

简答题
1.算法的时间复杂度只与问题的规模有关吗
2.有哪几种常用的存储方式，试列出并简要说明
3.树，二叉树，森林三种数据结构有什么不同，将树和森林转化成二叉树的基本目的是什么
4.队列的性质有哪些，举出用途（至少两个）

代码题
1.有A，B，C三个单链表，C=A交B （交集），写代码求C

广外考研报录比

选择题
1.把中缀表达式3*2-8/4转换为后缀表达式用栈进行操作，p为输入o为输出
A．pppooo B . popopo C . ppopoo D . popopo
2.存储中第一个元素存储位置为90，每个元素占2个空间，第六个的位置是
A 100 b 120 c 102 d 98
3.二叉树第i个节点的右孩子是
2i+1  2i  2i-1  i
4.链表没有的性质是
随机存取
不用事先分配空间
插入删除方便
。。
5.迅速找前五个最大元素
冒泡 选择 堆 快速
6.二叉树概念
7.线性表队列概念
填空题
链表中一个节点为p，插入一个q节点在他后面（两个空）
循环队列表头front 表尾rear 最大m求表长
哈夫曼树叶子节点为n，问这树空链域是多少
二叉树度为2节点为n2个，叶子节点多少
二叉树2000个节点，求最小高度
广义表(（a,b,c）（x,y,z）)
二叉排序树查找代码填空（三个空）
简答题
算法时间复杂度仅和问题相关吗
简述几个存储结构
树森林二叉树概念讨论
队列的概念
应用题
哈夫曼编码
散列表查找
画图找深度广度遍历
希尔排序5 3 1 间隔

算法
A表B表的∩合成一个c表
找图任意两点的最短路径代码