东南大学数据结构考研真题(东南大学 数据结构)

问题编号：451

题名：数据结构

1.回答下列问题（共32分）

1、最近最少使用的页面替换是虚拟存储系统中常用的策略。如何使用页面链接表来始终跟踪最近最少使用的页面？ （8分）

2、已知无向图G，V(G)={1,2,3,4}，E(G)={(1,2),(1,3),(2,3), (2 , 4), (3, 4)}，尝试画出G的邻接多重表（AdjacencyMultilists），并说明，如果已知点i，如何根据邻接多重表找到与i相邻的点j？ （8分）

3. 最好使用什么分类（排序）方法来查找前k 个最大元素？为什么？什么是稳定分类？指出下列算法是否是稳定的分类算法或者可以很容易地变为稳定的分类算法？

(a) 插入分类(b) 快速分类(c) 合并分类(d) 堆分类(e) 基数排序（8分）

4.构建最佳二叉搜索树的先决条件是什么？在动态情况下，AVL树的一般查询性能不如完全二叉搜索树。人们为什么使用AVL 树？ （8分）

2. 以下算法将n 位二进制数加1。假设没有溢出，该算法最坏情况的时间复杂度是多少？并分析其平均时间复杂度。 （15 分）

typeNum=数组[1……n]of[0……1];

procedureInc(varA:Num);

varj：整数；

开始：=n;

而A[i]=1do

A[i]:=0;i:=i-1;

结尾；

A[i]：=1；

结束公司；

3. 给定一个n*m 矩阵A[a.b, c.d]，令A[i, j]=A[i, j+1] (a=i=b, c=j=d -1) 和A[i,j]=A[i+1,j] (a=i=b-1, c=j=d)，设计时间复杂度小于O(n*m) 的算法) 判断值x是否在A中。（17分）

4. 假设图G有n个点。利用从某个源点到其余点的最短路径算法的思想，设计生成G的最小生成树的算法。（18分）

5. 删除序列任意位置任意数量的元素，得到字符序列的子序列。序列x和y的最长公共子序列记为Lcs(x,y)，它是x和y的公共子序列，长度最大。例如，adcbcb 是x=abdcbcbb 和y=adacbcb 的最长公共子序列。设x的长度为n，y的长度为m。设计一个算法来计算x 和y 的最长公共子序列的长度。尽可能改进你的算法，使其时间复杂度为O(n*m)。 （18分）

  相关文章:

  第1篇    减法的四种算法(减法的四个运算定律)    作者：admin

   8月底，考研大纲即将公布。预注册将于9月进行，正式注册将于10月进行。考研初试离我们越来越近了。朋友们早出晚归，努力复习、收集各种材料。很多人的状态可以用“忙、累、慌、乱”来形容。是不是意味着复习越努力、收集的信息越多，考研成功的概率就越大呢？并非如此。考研，你要学

  第2篇    mpa管理类联考考什么(管理类mpa联考过国家线难吗)    作者：admin

   1.学校声誉虽然MPA的学习内容与各学校的基础课程非常相似，但附加课程却明显不同，具有很强的特色。课程的设置和重点与各学校的专业特长和教学领域有很大关系。例如，对外经济贸易学校有以海关为主的课程，农业院校有以农业或扶贫为主的课程等。考生在选择时应根据自己的喜好考虑学校的声

  第3篇    考研政治真题试卷pdf(考研政治真题试卷2022)    作者：admin

   摘要本文主要从五个角度论证研究生政考试卷的重要性和必要性。首先，研究生政治考试试卷是研究生政治考试的重要组成部分。掌握真题真题可以帮助你更好的应对考试。其次，通过分析真题，可以了解考研政治的考点和命题思路，有助于提高备考效果。第三，通过分析真题，可

  第4篇    云南大学2021年硕士研究生拟录取(2020年云南大学研究生)    作者：admin

   云南大学研究生2023录取摘要云南大学是云南省重点大学之一，以优良的学风和丰富的研究资源而闻名。随着时间的流逝，云南大学2023年研究生招生即将拉开帷幕。本文将从五个角度论证并详细介绍云南大学2023年研究生招生的重要性以及招生政策的变化。1.录取政策的变化云南大学的研究生招生政策将随着时间的推移进行调整，以更好地适应当今社会的需求。2023年招生

  第5篇    南京大学的新闻传播研究生好考吗(南京大学新闻传播专业考研)    作者：admin

   南京大学新闻传播硕士考研经验摘要本文旨在分享我作为南京大学新闻与传播专业研究生的经历。我将从多个角度来论证这一点，包括准备计划、复习方法和技巧、面试准备、学术研究和准备阶段的实践经验。本文总结了我在考研期间所学到的知识，希望对即将考