数据结构期末前小题复习（建议期末前多看看）

谁践踏了优雅 2023-02-23 08:50 9阅读 0赞

###### 作为一个学软工的孩子，我深知数据结构期末前的暴风雨，在这先祝大家满绩，冲冲冲~今天给大家整理了一波小题，后面也会告诉大家要着重复习哪些大题目的. ######

## 首先是小题： ##

1.函数名代表该函数的入口地址。因此，可用函数名给指向函数的指针变量赋值。

2.char \*s=“C Language”;表示s是一个指向字符串的指针变量，把字符串的首地址赋予s。

3.结构体类型本身不占用内存空间，结构体变量占用内存空间。

4.所谓随机存取，就是通过首地址和元素的位序号值可以在O(1)的时间内找到指定的元素。

5.在线性表的顺序存储结构中可实现快速的随机存取，而在链式存储结构中则只能进行顺序存取。

6.对于一非空的循环单链表，h和p分别指向链表的头、尾结点，则有p->next == h

7.顺序栈中元素值的大小是有序的。（错）

8.栈底元素是不能删除的元素。（错）

9.在n个元素连续进栈以后，它们的出栈顺序和进栈顺序一定正好相反。

10.对顺序栈进行进栈、出栈操作不涉及元素的前、后移动问题。

11.所谓“循环队列”是指用单向循环链表或者循环数组表示的队列。（错）

12.循环队列也存在着空间溢出问题。

13.循环队列执行出队操作时会引起大量元素的移动。（错）

14.不论是入队列操作还是入栈操作,在顺序存储结构上都需要考虑"溢出"情况。

15.队列中允许插入的一端叫队头，允许删除的一端叫队尾。 （错）

16.在有N个结点且为完全二叉树的二叉搜索树中查找一个键值，其平均比较次数的数量级为： O(logN)。

17.在构造二叉排序树时，若关键字序列有序，则二叉排序树的高度最大。

18.对N个记录进行简单选择排序，比较次数和移动次数分别为O(N2)和O(N)。

19.二叉树的树叶就是他的叶子结点。

20.树的结点无左右之分，而二叉树的结点有左右之分；

21.图的广度优先遍历类似于二叉树的层次遍历。

22.图的深度优先遍历类似于二叉树的先序遍历。

23.在有n（>1）个元素的最大堆（大根堆）中，最小元的数组下标可以是：⌊n/2⌋+2

24.堆一定是一棵完全二叉树，因此适合采用链式存储实现。（错）

25.哈夫曼树的任意非叶结点的左右子树交换后仍是哈夫曼树。

26.设一段文本中包含4个对象\{a,b,c,d\}，其出现次数相应为\{4,2,5,1\}，则该段文本的哈夫曼编码比采用等长方式的编码节省了多少位数？  
（5*1+4*2+1*3+2*3）-（5+4+1+2）\*2=-2

27.Kruskal 算法是维护一个森林，每一步把两棵树合并成一棵。

28.采用递归方式对顺序表进行快速排序，每次划分后，先处理较短的分区可以减少递归次数。（错）

29.对N个记录进行归并排序，归并趟数的数量级是O(logN)。

30.对N个记录进行归并排序，空间复杂度为： O(N)

31.用递归方式对顺序表进行快速排序，递归次数与各元素初始排列有关，如果每一次划分后分区比较平衡，则递归次数少；

如果划分后分区不平衡，则递归次数多。

递归次数与处理顺序无关。

在快速排序的一趟划分过程中，当遇到与基准数相等的元素时，如果左右指针都会停止移动，那么当所有元素都相等时，算法的时间复杂度是O(NlogN)

在快速排序的一趟划分过程中，当遇到与基准数相等的元素时，如果左右指针都不停止移动，那么当所有元素都相等时，算法的时间复杂度是O(N2)

在快速排序的一趟划分过程中，当遇到与基准数相等的元素时，如果左指针停止移动，而右指针在同样情况下却不停止移动，那么当所有元素都相等时，算法的时间复杂度是O(N2)

32.Kruskal 算法是维护一个森林，每一步把两棵树合并成一棵。

33.Prim 算法是通过每步添加一条边及其相连的顶点到一棵树，从而逐步生成最小生成树。

34.设N个顶点E条边的图用邻接表存储，则求每个顶点入度的时间复杂度为： O(N+E)

35.for ( i=0; i<n; i++ )  
for ( j=0; j<m; j++ )  
a\[i\]\[j\]= 0;

这个的时间复杂度是mn，不是n²

36.T(1)=1，T(N)=2T(N/2)+N。则程序时间复杂度是：O(NlogN)

37.斐波那契数列FN的时间复杂度是O(FN)。

38.(logN)²是O(N)的。

39.logN是O(N)的。

40.n!是O(n的n次方)的。

41.下列函数中，哪个函数具有最慢的增长速度：B  
A.N1.5（次方）  
B.NlogN

42.如果无向图G必须进行两次广度优先搜索才能访问其所有顶点，则G中一定有回路。 (3分)  
答案：F

43.用邻接表法存储图，占用的存储空间数只与图中结点个数有关，而与边数无关。 (3分)  
答案：F

44.所谓“循环队列”是指用单向循环链表或者循环数组表示的队列。 (2分)  
答案：F

45.一棵有124个结点的完全二叉树，其叶结点个数是确定的。 (3分)  
答案：T  
*斜体样式*

## 其次是编程大题： ##

###### 1.哈夫曼树的构建和哈夫曼编码是如何写出来的。（这个我之前有写文章，思路清晰，建议看看） ######

###### 2.邻接表和邻接矩阵建立、输出有向图和无向图。 ######

###### 3.基于邻接表和邻接矩阵的图的递归的深度遍历和非递归的广度遍历。 ######

###### 4.循环队列的实现和内涵。 ######

###### 5.最小图的prim和克鲁斯尔算法。 ######

###### 6.单源最短路径算法。 ######

###### 7.八种排序算法以及时间复杂度和空间复杂度（这个也总结过，建议多看看，尤其是快速排序和堆排序）。 ######

###### 8.哈希表的实现和存在的意义。 ######

###### 9.各种二叉树的构建和输出。 ######

###### 10.基于堆栈的后缀表达式的计算和转换。 ######

## 等等… … ##

发表评论取消回复

表情：

评论列表（有 0 条评论，9人围观）

还没有评论，来说两句吧...

相关阅读

相关数据结构(C语言版)-期末复习汇总

数据结构（C语言版）期末复习汇总第一章绪论数据结构：是一门研究非数值计算程序设计中的操作对象，以及这些对象之间的关系和操作的学科。数据结构是一门综合性的专业课程

柔情只为你懂/ 2024年02月21日 10:12/ 0 赞/ 80 阅读

相关大数据基础期末复习

1. 大数据概念、大数据的性质、大数据技术概述、大数据应用趋势与应用实例大数据5V，结构化非结构化半结构化数据，大数据处理过程图1-5，大数据的技术特征。答：Volum

亦凉/ 2023年10月29日 07:49/ 0 赞/ 129 阅读

相关数据结构期末前小题复习（建议期末前多看看）

作为一个学软工的孩子，我深知数据结构期末前的暴风雨，在这先祝大家满绩，冲冲冲~今天给大家整理了一波小题，后面也会告诉大家要着重复习哪些大题目的. 首先是小题： 1.

谁践踏了优雅/ 2023年02月23日 08:50/ 0 赞/ 10 阅读

相关数据结构之查找（期末复习）

【知识框架】 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9n

淩亂°似流年/ 2023年02月21日 01:51/ 0 赞/ 149 阅读

相关数据结构-期中前复习

1-2 数据的逻辑结构是指数据的各数据项之间的逻辑关系。【false】数据的逻辑结构是指数据元素之间的逻辑关系，而非数据元素内部的数据项之间的关系 2-3 下列关于数据

青旅半醒/ 2022年12月14日 15:54/ 0 赞/ 13 阅读

相关期末复习——数据结构部分

一、顺序查找从表中的第一个（或最后一个记录）开始，逐个进行记录的关键字和给定值比较，若某个记录字与给定值相等则查找成功，找到所查找的记录。如果直到最后一个记录（或第一个记

悠悠/ 2022年06月02日 02:25/ 0 赞/ 197 阅读

相关数据结构期末题

免费版：[华文慕课-数据结构期末题][-] 1、由小到大写出以下时间复杂度的序列： ![20181205094937447.png][] > 答案： (3)(6)(4

深碍√TFBOYSˉ_/ 2022年04月11日 03:40/ 0 赞/ 222 阅读

相关数据结构简答题期末复习

1、数据结构定义数据结构是指相互之间存在着一种或多种关系的[数据][Link 1]元素的集合和该集合中数据[元素][Link 2]之间的关系组成。 2、其逻辑结构的

灰太狼/ 2022年04月02日 13:22/ 0 赞/ 363 阅读

相关 java 期末复习

知识点总结： [Java基础知识总结][Java] [Java知识点汇总][Java 1] [Java基础知识总结（博客园）][Java 2] 百度文库： [http

桃扇骨/ 2022年03月30日 08:25/ 0 赞/ 315 阅读

相关【操作系统】期末复习

第一章引论 1.了解系统硬件组织，理解软件的层次结构与虚拟机的概念；P4 2.掌握操作系统的定义，了解系统的形成和发展；定义：用以控制和管理系统资源，方便用户使用计算

我不是女神ヾ/ 2021年12月21日 04:53/ 0 赞/ 560 阅读