23全程班2021领学班
查看: 9678|回复: 8

2020南昌大学838数据结构考研真题回忆

[复制链接]

0

主题

9

帖子

0

积分

王道论坛新道友

注册时间
2018-1-4
最后登录
2020-2-11
发表于 2019-12-23 13:47 | 显示全部楼层 |阅读模式
今年共三大题,15小题,没有编程题。


一、简答题

1.单链表,双链表,循环单链表,能否删除第k个结点并保持链表不断开,如果能,时间复杂度是多少。

2.快速排序的最优,最差,平均时间复杂度分别是多少。

3.要得到序列中前第k小的数,问用什么排序方法最佳。给了一个完整序列A,和一个前第k小序列B,问用该排序方法得出B一共做了几次比较。

4.有n个长度均为m的英文单词,m<5,n>>m,问用什么方法排序最佳,理由。

5.给了邻接矩阵,画出从结点1出发的深度优先生成树和广度优先生成树

6.已知一棵树和遍历序列,问是以下哪种遍历:LNR,NLR,RNL

7.简述快速排序原理,给了一组序列,写出快排一次的结果。




二、程序阅读题(写出程序的功能)

8.考查栈(逆置)
9.考查循环队列(逆置)
10.考查链表(判断相邻元素是否相等)


三、综合题(有一题实在想不起来了)

11.已知一个带权图,写出用Prim算法构造最小生成树的边,并画出最小生成树
12.有如下算法:若i<4j(j=1,2,3...),则继续查找直至i>4k,然后和4k-2比较,再和4k-1或4k-3比较。画出表长N=16的判定树,并写出该算法的平均查找长度。
13.已知一棵二叉树只有度为2和0的结点,证明:(求和符号,下标i=0,上标n)2的 -(Li-1) 次方   =   1
其中n为叶子结点的总数,Li为第i个叶子结点所在的层数(根节点为第一层)。
14.已知一棵m叉树,高为h
①最后一层至多有多少结点?
②整棵树至多有多少结点?
③给满m叉树按照从上往下、从左往右的顺序从1开始编号,求第i个结点的双亲结点编号。求第i个结点的第k个孩子结点的编号(假设存在孩子结点)。

0

主题

1

帖子

0

积分

王道论坛新道友

考研年份
2020
报考学校
南昌大学
本科学校
南昌航空大学
注册时间
2020-1-17
最后登录
2020-2-20
发表于 2020-1-17 14:47 | 显示全部楼层
你好,阅读程序题的第三题我印象中是判断是否为循环链表吧

0

主题

17

帖子

0

积分

王道论坛新道友

考研年份
2018
报考学校
北工大
本科学校
郑州大学西亚斯
注册时间
2018-4-25
最后登录
2021-3-12
发表于 2019-12-25 22:20 | 显示全部楼层
补充一下
1。while(i<n)
{
S+=1;
i+=s;
}
求时间复杂度
6.已知一棵树和遍历序列,问是以下哪种遍历:LNR,NLR,RNL。RLN,LRN。NRL.

1

主题

59

帖子

0

积分

王道论坛新道友

注册时间
2017-12-18
最后登录
2022-5-29
发表于 2019-12-29 13:43 来自手机 | 显示全部楼层
学长能否告诉我程序阅读题如何复习 我其他还好

0

主题

10

帖子

0

积分

王道论坛新道友

考研年份
2019
报考学校
郑州大学
本科学校
河南工程学院
注册时间
2018-1-21
最后登录
2021-11-2
发表于 2020-1-18 11:36 | 显示全部楼层
sw19950716 发表于 2020-1-17 14:47
你好,阅读程序题的第三题我印象中是判断是否为循环链表吧

同感,好像是判断链表中是否存在环。
您需要登录后才可以回帖 登录 | 注册

本版积分规则

小黑屋|Archiver|手机版|王道官网|王道论坛 | 粤ICP备19140740号 |

GMT+8, 2022-8-16 02:18 , Processed in 0.044867 second(s), 26 queries .

Powered by Discuz!

© 2008-2020 CSKAOYAN.COM

快速回复 返回顶部 返回列表