admin 管理员组文章数量: 1087139
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://roclinux.cn/b/1713679689a646640.html，
本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
更多相关文章
简述程序设计的基本步骤python
年月日发(作者：织梦模板格式)简述程序设计的基本步骤程序设计是计算机科学中的重要内容之一，它是指根据一定的算法和逻辑规则，使用特定的编程语言编写计算机程序的过程。程序设计可以帮助我们解决各种问题，并实现特定的功能。本文将以语言为例，介绍程序
2024年高职单招信息技术问题解决实践练习题
年月日发(作者：富马酸吉瑞替尼片)信息技术《用计算机处理问题》练习题知识点：、计算机处理问题的基本过程()程序设计语言的发展经历了机器语言、汇编语言、高级语言。计算机可以直接识别的语言是机器语言，机器语言是一串由“”和“”构成的二进制代码。
操作系统实验四：多种资源的银行家算法
多种资源的银行家算法 一、实验目的二、实验原理与内容(1) 实验内容:(2) 实验原理:三、实验过程(1) 设计过程：(2)问题：(3)运行结果四、实验总结一、实验目的 (1)加深了解有关资源申请、避免死锁等概念。 (2)体会和了解银行家
操作系统实习-银行家算法（C语言）
文章目录 设计目的设计内容设计思路算法流程图测试数据程序结构数据结构实现代码测试结果 设计目的 了解死锁产生的条件和原因，并采用银行家算法有效地避免死锁的发生，进一步理解银行家算法。 设计内容 完
时间序列分类20：数据可视化与问题分析建模流程详解（UCI-HAR）
【时间序列预测分类】 全系列60篇由浅入深的博文汇总：传送门 上篇文章介绍了人类活动识别常用的方法、最新进展和面临的挑战。UCI人类活动识别数据集是人类活动识别领域的benchmark数据集（还
【视频讲解】Xgboost、ARIMA 和 Prophet对国际牛肉市场份额、比特币价格时间序列预测|数据分享...
原文链接：https:tecdat?p37228 分析师：Kechen Zhao 本文将通过视频讲解，展示如何用Xgboost、ARIMA 和 Prophet对国际牛肉
探索智能解决方案：Artificial-Potential-Field 算法实现
探索智能解决方案：Artificial-Potential-Field 算法实现 去发现同类优质开源项目:https:gitcode 在现代科技中，自动化和机器人技术领域的发展离不开高效
多算法路径规划集合：A星、遗传、RRT、模糊、PRM和Potential算法
A星遗传算法rrt算法fuzzy算法prm算法potential算法路径规划集合 matlab路径规划算法，每种算法附带不同的地图，可以生产路径图及相应部分数据，可以对不同算法进行学习，更好掌握路径规划方法。 ID:674867042
《异常检测——从经典算法到深度学习》20 HotSpot：多维特征 Additive KPI 的异常定位
《异常检测——从经典算法到深度学习》 0 概论1 基于隔离森林的异常检测算法 2 基于LOF的异常检测算法3 基于One-Class SVM的异常检测算法4 基于高斯概率密度异常检测算法5 Opprentice——异常检测经典算法最终篇6
机器学习十大经典算法——环境搭建与算例分析
机器学习十大经典算法——环境搭建与算例分析 根据对机器学习相关算法资料的收集情况，我们总结出了十四个经典常用的机器学习算法，分别在Windows环境下和Linux环境下搭建了开发环境，对每一个算法进行了原理分析与代码实现。同时，对于每一个
程序员必须知道的10大基础实用算法及其讲解
算法一：快速排序算法 快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下，排序 n 个项目要Ο(n log n)次比较。在最坏状况下则需要Ο(n2)次比较，但这种状况
【算法】十大经典算法
感谢博主，转自：https:blog.csdnqq_42495360articledetails80746548 什么是算法？ 直白地说，
《推荐系统开发实战》之基于标签的推荐算法介绍和案例实战开发
转载请注明出处：http:blog.csdngamer_gyt 博主微博：http:weibo234654758 Github：https:githubth
银行家算法 c语言
操作系统学习之银行家算法，c语言代码实现： 本人原创代码，如果有什么错误的地方，欢迎大佬指正！ #include<stdio.h>#include <malloc.h>#include<stdlib.h
银行家算法的思路银行家算法
算法思路 先对用户提出的请求进行合法性检查，即检查请求是否大于需要的，是否大 于可利用的。若请求合法，则进行预分配，对分配后的状态调用安全性算法进行 检
银行家算法（安全序列）
前言 要解释银行家算法，必须先解释操作系统安全状态和不安全状态。 1）安全状态：如果存在一个由系统中所有进程构成的安全序列P1，…ÿ
【任务协同】合同网算法无人机任务重规划【含Matlab源码 MMB001期】
💥💥💥💥💥💥💥💥💞&am
计算机毕业设计SpringBoot+Vue.js协同过滤算法东北特产销售系统(源码+文档+PPT+讲解)
温馨提示：文末有 CSDN 平台官方提供的学长联系方式的名片！ 温馨提示：文末有 CSDN 平台官方提供的学长联系方式的名片！ 温馨提示
操作系统：银行家算法避免死锁
银行家算法是用来避免死锁的，该方法将系统的状态分为安全和不安全，只要系统处于安全状态，便可避免死锁的发生。之所以成为银行家算法，是由于该算法能用于银行系
【操作系统--页面置换算法】C语言详解--大作业版（附代码）
一、实验目的 1设计和实现FIFO,LRU,OPT和CLOCK算法 2设计和实现一个完整的可供选择不同算法的程序 3通过页面访问序列随机发生器实现对上述算法的测试及性能比较 4领略页面置换背后的资源调配思想，并
发表评论