admin 管理员组文章数量: 1184232
2024年4月21日发(作者：霹雳布袋戏好听的名字和称号)
(完整版)清华大学数据结构试题及答案
一、
单选题（每题 2 分，共20分)
1.
1.
对一个算法的评价，不包括如下（B )方面的内容。
A．健壮性和可读性 B．并行性 C．正确性 D．时空复杂度
2.
2.
在带有头结点的单链表HL中,要向表头插入一个由指针p指向的结点，则执行
（ ）。
A。 p—>next=HL->next； HL—>next=p; B。 p—〉next=HL； HL=p；
C. p—>next=HL; p=HL； D. HL=p； p—〉next=HL；
3.
3。
对线性表，在下列哪种情况下应当采用链表表示？( )
A.经常需要随机地存取元素 B。经常需要进行插入和删除操作
C。表中元素需要占据一片连续的存储空间 D.表中元素的个数不变
4.
4.
一个栈的输入序列为1 2 3，则下列序列中不可能是栈的输出序列的是( C )
A。 2 3 1 B. 3 2 1
C。 3 1 2 D。 1 2 3
5.
5。
AOV网是一种( ）.
A．有向图 B．无向图 C．无向无环图 D．有向无环图
6.
6.
采用开放定址法处理散列表的冲突时,其平均查找长度( ）。
A．低于链接法处理冲突 B。 高于链接法处理冲突
C．与链接法处理冲突相同 D．高于二分查找
7.
7.
若需要利用形参直接访问实参时，应将形参变量说明为（ ）参数。
A．值 B．函数 C．指针 D．引用
8.
8。
在稀疏矩阵的带行指针向量的链接存储中,每个单链表中的结点都具有相同的
( ）。
A．行号 B．列号 C．元素值 D．非零元素个数
9.
9。
快速排序在最坏情况下的时间复杂度为( ).
A．O（log
2
n) B．O（nlog
2
n) C．0(n） D．0（n
2
)
10.
10.
从二叉搜索树中查找一个元素时,其时间复杂度大致为（ ）。
A。 O(n） B。 O(1) C. O(log
2
n） D。 O（n
2
)
二、
二、
运算题（每题 6 分，共24分）
1.
1。
数据结构是指数据及其相互之间的______________.当结点之间存在M对N（M：
N)的联系时，称这种结构为_____________________。
2.
2。
队列的插入操作是在队列的___尾______进行，删除操作是在队列的____首
______进行。
3.
3.
当用长度为N的数组顺序存储一个栈时,假定用top==N表示栈空，则表示栈满
的条件是___top==0___（要超出才为满)_______________。
4.
4.
对于一个长度为n的单链存储的线性表，在表头插入元素的时间复杂度为
_________，在表尾插入元素的时间复杂度为____________。
5.
5.
设W为一个二维数组，其每个数据元素占用4个字节，行下标i从0到7 ,列
下标j从0到3 ,则二维数组W的数据元素共占用＿_____＿个字节。W中第6 行的元素和第
4 列的元素共占用＿_______＿个字节。若按行顺序存放二维数组W，其起始地址为100，则
二维数组元素W［6，3］的起始地址为＿________＿.
6.
6。
广义表A= (a,（a，b),(（a,b)，c）)，则它的深度为____________，它的长
(完整版)清华大学数据结构试题及答案
度为____________。
7.
7.
二叉树是指度为2的____________________树。一棵结点数为N的二叉树，其
所有结点的度的总和是_____________。
8.
8.
对一棵二叉搜索树进行中序遍历时，得到的结点序列是一个______________.
对一棵由算术表达式组成的二叉语法树进行后序遍历得到的结点序列是该算术表达式的
__________________.
9.
9.
对于一棵具有n个结点的二叉树，用二叉链表存储时,其指针总数为
_____________个,其中_______________个用于指向孩子，_________________个指针是空闲
的。
10.
10。
若对一棵完全二叉树从0开始进行结点的编号，并按此编号把它顺序存储到一维数
组A中，即编号为0的结点存储到A[0]中.其余类推，则A[ i ］元素的左孩子元素为________，
右孩子元素为_______________，双亲元素为____________。
11.
11。
在线性表的散列存储中，处理冲突的常用方法有________________________和
_____________________________两种。
12.
12.
当待排序的记录数较大，排序码较随机且对稳定性不作要求时,宜采用
_______________排序；当待排序的记录数较大，存储空间允许且要求排序是稳定时，宜采
用________________________排序.
三、
三、
运算题（每题6分，共24分）
1.
1.
已知一个6´5稀疏矩阵如下所示，
0
0
0
0
5
0
0
0
0
0
0
0
0
0
0
0
1
0
0
2
0
0
10
00
00
07
试：
（1）
(1）
写出它
的三元组线性表；
（2）
（2)
给出三元组线性表的顺序存储表示。
2.
2.
设有一个输入数据的序列是 { 46， 25, 78， 62, 12, 80 }， 试画出从空树
起,逐个输入各个数据而生成的二叉搜索树.
3.
3。
对于图6所示的有向图若存储它采用邻接表，并且每个顶点邻接表中的边结点
都是按照终点序号从小到大的次序链接的，试写出：
(1） 从顶点①出发进行深度优先搜索所得到的深度优先生成树；
(2） 从顶点②出发进行广度优先搜索所得到的广度优先生成树；
4.
4。
已知一个图的顶点集V和边集E分别为：
V={1,2,3，4,5，6，7};
E=｛〈2，1>,〈3，2>，〈3，6〉,〈4，3〉,<4,5>,<4,6>,
〈5,1>,<5,7〉,〈6,1>,〈6,2〉，〈6,5〉};
若存储它采用邻接表，并且每个顶点邻接表中的边结
点都是按照终点序号从小到大的次序链接的，按主教材中
图6
(完整版)清华大学数据结构试题及答案
介绍的拓朴排序算法进行排序，试给出得到的拓朴排序的序列。
四、
四、
阅读算法（每题7分，共14分）
1.
1。
int Prime(int n)
{
int i=1;
int x=（int） sqrt（n);
while (++i<=x）
if (n％i==0) break；
if （i〉x) return 1；
else return 0;
}
(1)
(1)
指出该算法的功能；
(2)
（2)
该算法的时间复杂度是多少？
2.
2.
写出下述算法的功能:
void AJ(adjlist GL, int i， int n）
{
Queue Q；
InitQueue（Q)；
cout< visited［i]=true； QInsert(Q,i)； while(!QueueEmpty(Q）) ｛ int k=QDelete(Q); edgenode* p=GL［k]; while（p！=NULL） ｛ int j=p—>adjvex; if（!visited[j]） { cout<〈j〈<’ ’； visited[j]=true； QInsert（Q，j)； } p=p—>next; ｝ ｝ } 五、 五、 算法填空（共8分） 如下为二分查找的非递归算法，试将其填写完整。 Int Binsch(ElemType A［ ］,int n，KeyType K） (完整版)清华大学数据结构试题及答案 { int low=0; int high=n—1; while (low〈=high） { int mid=_______________________________; if (K==A［mid］.key） return mid； //查找成功，返回元素的下标 else if (K<［mid］.key) ______________________________________; //在左子表上继续查找 else __________________________________； //在右子表上继续查找 } return —1; //查找失败，返回—1 } 六、 六、 编写算法（共8分) HL是单链表的头指针，试写出删除头结点的算法. ElemType DeleFront(LNode ＊ ＆ HL) 参考答案 一、 单选题（每题2分,共20分) 1.B 2.A 3。B 4。C 5.D 6。B 7.D 8.A 9.D 10。C 二、 二、 填空题（每空1分,共26分） 1. 1。 联系 图（或图结构） 2. 2。 尾 首 3. 3。 top==0 4. 4。 O（1） O（n） 5. 5. 128 44 108 6. 6. 3 3 7. 7。 有序 n-1 6 5 5 8. 8. 有序序列 后缀表达式（或逆波兰式） 1 5 1 9. 9. 2n n-1 n+1 10. 10. 2i+1 2i+2 （i-1）/2 3 2 — 11. 11. 开放定址法 链接法 1 12. 12. 快速 归并 4 5 -2 三、 三、 运算题（每题6分，共24分） 5 1 5 1. 1。 （1） ((1，5，1)，(3，2,-1)，（4，5，-2)，(5,1,5）,(6,3,7）） 6 3 7 (3分） 图7 （2） 三元组线性表的顺序存储表示如图7示。 一、 (完整版)清华大学数据结构试题及答案 2. 2。 3. 3。 图8 如图8所示。 ƒ„… DFS：
版权声明：本文标题：(完整版)清华大学数据结构试题及答案 内容由网友自发贡献，该文观点仅代表作者本人，
转载请联系作者并注明出处：http://www.roclinux.cn/b/1713679689a646640.html，
本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
更多相关文章
7-1 银行家算法--安全性检查 (20 分)(思路+详解+知识分析)宝 你今天 AC了吗
一：前言停更一周了，在这一周里，我每时每刻都在 想这我这 29个粉丝，庆幸教师资格证终于结束了，贴心杰又可以天天更新博客了哈哈
操作系统实验二-银行家算法（以随机数作为输入）
广州大学学生实验报告开课学院：计算机科学与网络工程学院实验室：计算机软件实验室计科183实验二银行家算法一、实验目的1、了解什么是操作系统安全状态和不安全状态ÿ
java实现银行家算法
实验一、银行家算法实现一、实验目的：了解进程管理的实现方法，理解和掌握处理进程同步问题的方法。二、实验内容：实现银行家算法、进程调度过程的模拟、读者-写者问题的写者优先算法。
【机器学习】必会降维算法之：特征选择（Feature Selection）
特征选择（Feature Selection） 1、引言 2、特征选择（Feature Selection） 2.1 定义 2.2 应用场景 2.3 实现方式 2.3.1 过滤法（Filter Methods） 2.3.2 包装法（Wrap
CAD2020输入序列码后出现脚本错误怎么解决（已解决）
点击是，然后关闭当前页面，重新以管理员身份运行！如果运行之后提示重复出现序列号错误，无效和跳转不到机器码页面，这个原因是高版本m
QGIS identify Features 无法选中元素
问题QGIS identify Features 无法选中元素原因：要先选中图层才能，对元素框选
无聊科技正经事周刊（第3期）：美团的推荐算法，是在玩火吗？
这里记录每周值得分享的科技内容，周三发布。 本刊开源（GitHub: senlypanweekly），欢迎投稿，推荐或自荐文章
CV 加持的工业检测，从算法选型到模型部署
随着AI技术的逐渐成熟，越来越多的传统企业希望借助AI技术，实现智能质检。传统质检更多依靠有经验的人工劳动力来实现质量检查甚至分拣，但这样的方式，许多场
转载--算法分析实战篇和应用篇之提高（一）我的常用断点系统
【文章标题】: 算法分析实战篇和应用篇之提高（一）我的常用断点系统 【文章作者】: NBA2005【作者邮箱】: stockfox1699126【作者QQ号】: 382309369【软件名称】:
安卓手机图片相似度对比--OpenCV感知哈希算法
最近公司要求做一个类似腾讯手机管家的应用，其中有一个功能需要把用户手机中的相似图片查找出来，供用户选择是否删除。 完全毫无头绪，就上网查找有哪些技术可以做的，找来找去，都在说OpenCV，于是乎就看看OpenCV要如何实现 几种方式中，
如何使用Createjs来编写HTML5游戏（八） 通过继承扩展EaselJS中的基础元素
从我第一天了解到javascript开始，就听说在这里是没有类的。其实一开始我是沮丧的，尽管我并不知道有没有“类”对编程究竟有多大影响，不过有缺憾总是让人感觉遗憾，哪怕这是一个你可能永远不会用到的东西。确实，在没有任何自定义“类”的情况下，
中国的AI APP算法有多少是基于CHATGPT开发的，CHATGPT关闭服务以后还能用么？
目前，并没有官方或权威机构发布具体的统计数据来表明中国有多少AI APP算法是基于ChatGPT开发的。这是因为AI应用的开发具有高度的多样性和创新性，很多应用可能只是部分借鉴了ChatGPT的技
PCQQ official算法逆向
在分析pcqq协议时，0836包里有一个official算法，经多次测试发现，如果这个算法没有或者错误，会导致账号被冻结或屏蔽。为了解决这个问题&
【操作系统 - 4】动态分区分配算法
操作系统系列 学习至此，发现很多学了但很久没用的知识，久而久之，慢慢遗忘。等哪天还需要的话，却发现已经忘得差不多了，即使整理了文档（word等），还是得从头再学一遍。读研第一学期，发现很多东西都可以从博客上学习到，也有不少博主呕心沥血整
cache中write back和write through算法描述
这张图展示了基本的缓存（Cache）处理算法，并讨论了缓存命中（Hit）和未命中（Missÿ
2021新型面试题-血虐面试官斩获字节跳动Offer！Android 精选版面试题级答案（Android+Java+算法+性能优化+四大组件...）
前言 双非本科，自认为技术水平不差，8月从美图实习离职回学校，各种倒霉的事不断，到现在11月，为了找个好的环境复习，9月又在学校附近租了房，基本是没有面试通知就学不进去，前面由于过于自信，也没拿个保底的offer，也只去湖大跑过一次58到
「冰狐智能辅助」实战秘籍：即时调试你的代码，提升效率！
「冰狐智能辅助平台」可以在不连接手机和电脑请况下实现在线实时抓取Log和在线实时获取当前页面的UI树，具体步骤如下： 1.登录平台 2.打开手机的在线调试开关。进入「移动端」「我的设备」，选择对应的手机，然后选择「编
Flash玩家必备：a标签与download元素，完美匹配制胜关键
download 属性是HTML5中新增的 <a> 标签属性。 注意:href属性的href 需要是 限于同源文件，如果引用的是第三方或是调用后台的
Firenvim高手之路：理解并运用全局配置(globalSettings)与局部调整(localSettings)
Firenvim配置对象深度解析：globalSettings和localSettings的完整用法 Firenvim是一个强大的浏览器插件，它允许你在浏览器中直接使用Neovim编辑器。通过精心配置globalSetting
告别冗余元素：教你去除页眉横线与分页
删除页眉上的横线：双击页眉（或者点击插入–>页眉–>编辑页眉），进入页眉和页脚页面，选中页眉上的文字内容（一个单一的换行符也可以） 选中菜单栏中的设计菜单栏 单击页面边框，进入边框和底纹对话框
发表评论