admin 管理员组文章数量: 1086019
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，
本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
更多相关文章
专业学习经历范文主要学习经历写
年月日发(作者：语言怎么用)专业学习经历范文主要学习经历写我是一名计算机科学专业的研究生，自大学开始一直致力于计算机领域的学习和研究。在我的专业学习经历中，我主要学习了计算机科学领域中的算法设计与分析、程序设计与开发、计算机网络、数据库系统
简述程序设计的基本步骤python
年月日发(作者：织梦模板格式)简述程序设计的基本步骤程序设计是计算机科学中的重要内容之一，它是指根据一定的算法和逻辑规则，使用特定的编程语言编写计算机程序的过程。程序设计可以帮助我们解决各种问题，并实现特定的功能。本文将以语言为例，介绍程序
程序设计的基本概念和步骤
年月日发(作者：设置字体颜色)程序设计的基本概念和步骤宝子！今天咱们来唠唠程序设计那点事儿。一、基本概念。程序设计呢，就像是当一个超级建筑师，不过咱建的不是房子，是软件世界里的各种奇妙功能。简单说，就是告诉计算机要做什么、怎么做。这里面有好
程序设计的基本方法
年月日发(作者：语言编程和图形编程有什么区别)第章程序设计的基本方法对于初学者来说，写出一个满足题目要求的程序并不是一件简单的事情。明明已经了解和掌握了语言中各种语句的语法和语义以及程序的基本结构，对题目的要求似乎也都清楚，但就是不知道怎样
2024年高职单招信息技术问题解决实践练习题
年月日发(作者：富马酸吉瑞替尼片)信息技术《用计算机处理问题》练习题知识点：、计算机处理问题的基本过程()程序设计语言的发展经历了机器语言、汇编语言、高级语言。计算机可以直接识别的语言是机器语言，机器语言是一串由“”和“”构成的二进制代码。
操作系统实验四：多种资源的银行家算法
多种资源的银行家算法 一、实验目的二、实验原理与内容(1) 实验内容:(2) 实验原理:三、实验过程(1) 设计过程：(2)问题：(3)运行结果四、实验总结一、实验目的 (1)加深了解有关资源申请、避免死锁等概念。 (2)体会和了解银行家
操作系统课设-银行家算法
成 绩： ****大学计算机学院 课 程 设 计 课 程 操作系统Ⅰ 题 目 银行家算法 学 院 计算机学院 专 业 软件工程 班 级姓 名学 号指导教师 **** 2019 年 6 月 16 日
Python+Django+Mysql实现简单在线电影、音乐、图书等推荐系统SimpleOnlineMovieCFRSPythopython实现基于用户的协同过滤推荐算法实现 源代码下载 算法实现
PythonDjangoMysql实现简单在线电影、音乐、图书等推荐系统（基于用户的协同过滤推荐算法） 一、项目简介 1、开发工具和实现技术 pycharm2020professional版
图像边缘检测算法体验步骤（Photoshop，Matlab）
图像边缘检测算法体验步骤（Photoshop，Matlab） 今天给大侠带来一本学习完收益颇多的数字图像处理的资料《冈萨雷斯数字图像处理MATLAB版》.中文版(第二版)，请在“FPGA技术江湖”公众号内回复“ 冈萨雷斯数字图像处理”，可
探索智能解决方案：Artificial-Potential-Field 算法实现
探索智能解决方案：Artificial-Potential-Field 算法实现 去发现同类优质开源项目:https:gitcode 在现代科技中，自动化和机器人技术领域的发展离不开高效
A星遗传算法rrt算法fuzzy算法prm算法potential算法路径规划集合 matlab路径规划算法，每种算法附带不同的地图，可以生产路径图及相应部分数据
A星遗传算法rrt算法fuzzy算法prm算法potential算法路径规划集合 matlab路径规划算法，每种算法附带不同的地图，可以生产路径图及相应部分数据，可以对不同算
机器学习常用算法
2019独角兽企业重金招聘Python工程师标准>>> 介绍 历史背景 决策树算法是最早的机器学习算法之一。早在 1966 年 Hunt,Marin 和 Stone 提出的CLS 学习系统就有了决策树算法的概念。但到了
[算法前沿]--002-ChatGPT对安全的影响和开源的LLM大模型资源汇总
文章目录 0.ChatGPT大模型带来的影响0.1 ChatGPT带来信息化革命性创新，目前尚不能处理专业知识但成长很快0.2 Chat GPT为网安行业带来新的创新方向，也将引领新一轮投融资热潮0.2.1 攻击方发起网络攻击的门槛降低0.
真正统治世界的十大算法
本文英文出处：Marcos Otero。未经许可，禁止转载！ 不久前的某一天，我在浏览Reddit发现了一篇有趣的文章《统治世界的十大算法》&#
【算法】十大经典算法
感谢博主，转自：https:blog.csdnqq_42495360articledetails80746548 什么是算法？ 直白地说，
基于JAVA的银行家算法实现实验报告
一、实验概述 1. 实验名称 基于JAVA平台的银行家算法实现 2. 实验目的 （1）理解利用银行家算法避免死锁的问题； （2）在了解和掌握银行家算法的基础上，编制银行家算法通用程序，将调试结果显示在计算机屏幕上，并检测机算和笔算
在浏览器中禁止拖动元素打开新界面
在编写前端前端页面的过程中，使用a链接是避免不了的，但是有时候我们不希望通过拖拽a元素就打开新界面， 这是就可以在body标签内添加 οndragstart"re
【任务协同】合同网算法无人机任务重规划【含Matlab源码 MMB001期】
💥💥💥💥💥💥💥💥💞&am
计算机毕业设计SpringBoot+Vue.js协同过滤算法东北特产销售系统(源码+文档+PPT+讲解)
温馨提示：文末有 CSDN 平台官方提供的学长联系方式的名片！ 温馨提示：文末有 CSDN 平台官方提供的学长联系方式的名片！ 温馨提示
【操作系统--页面置换算法】C语言详解--大作业版（附代码）
一、实验目的 1设计和实现FIFO,LRU,OPT和CLOCK算法 2设计和实现一个完整的可供选择不同算法的程序 3通过页面访问序列随机发生器实现对上述算法的测试及性能比较 4领略页面置换背后的资源调配思想，并
发表评论