请简述路径的概念以及结构路径的基本元素有哪些？

来源：蜘蛛抓取(WebSpider) 时间：2022-05-24 08:30 标签： 路径分为哪两大类

数据结构重点研究“数据”还是“结构”
重点研究结构。数据结构是一门研究非数值计算的程序设计问题中计算机操作对象（即数据元素）以及他们之间的关系和运算的学科。如何合理组织高效处理数据是数据结构主要研究问题。

线性表的存储结构胶顺序表，线性表的链式存储结构叫链表，请简述你对“顺序表顺序存储、随机读取；链表随机存储、顺序读取”这句话的理解

顺序表的存储位置是一片连续的区域，可以根据下标进行随机读取，而链表散布在存储区域的各个地方，通过指针连接，想要读取一个数据，就要从到不断通过指针向后寻找

数据结构中你熟悉的那些数据类型是递归定义的？请给出一种递归数据类型的定义，并做简单的解释
单链表就是一种递归的数据结构

栈和队列与普通线性表有何异同？
相同点：数据元素之间存在一对一的关系，存储方式和线性表相同
不同：栈是限定尽在表尾进行插入或删除，是后进先出；队列是限定在一端进行插入，在另一端进行删除，是先进先出

基于关键字比较的排序算法所能达到的最优时间复杂度是？能否设计一种不需要关键字间比较的算法？请给出基本思路
O(n);基数排序；基于关键字大小进行排序，借助分配和收集两种操作对单逻辑关键字进行排序

简述KMP算法如何提高字符串的模式匹配效率
每当一趟匹配出现字符比较不对等时，不需要回溯指针二利用已经得到的“部分匹配”的结果，将模式想做滑动尽可能远的一段距离后继续进行比较

请给出四种数据结构基本类型
集合、线性结构、树形结构、图状结构和网状结构

栈只允许表的一端进行插入或删除操作
队列只允许在表的一端进行插入，在另一端进行删除

在AOE网中，有些活动可以并行地运行，最短完成时间应是从源点到汇点的最长路径（指路径上所有权值之和），称这样的路径为关键路径

插入类排序有哪几种？其中哪些是不稳定的排序
插入排序分为直接插入排序、折半插入排序、希尔排序
其中希尔排序是不稳定的排序算法

数据结构式相互之间存在一种或多种特定关系的数据元素的集合

稳定的排序方法：假设关键字Ki=Kj，且在排序前的序列中，Ki领先于Kj，若排序后Ki仍然领先于Kj，则称该排序方法稳定
稳定的排序：冒泡、直接插入、归并、基数
不稳定的排序：快速、希尔、堆
不确定的排序：简单选择排序（插入版稳定，交换版不稳定）

二叉排序树也称二叉查找树，二叉排序树是一颗空树或者是一颗具有以下特性的非空二叉树：
1、若左子树非空，则左子树上所有结点关键字值均小于根结点关键字值
2、若右子树非空，则右子树上所有结点关键字值均大于根结点关键字值
3、左右子树本身也是二叉排序树

简述以下三个概念的区别：头指针、头结点、表头结点
头指针：是指向链表第一个结点的指针
头结点：是在首元结点之前附设的一个结点，其指针域指向首元结点
表头结点：也称首元结点，是链表中存储第一个数据元素的结点

什么是递归程序？递归程序的优缺点？递归程序在执行时，应借助何种数据结构来完成？
递归程序：如果一个函数过程或数据结构定义中应用了他自身，那么这个函数过程或数据结构称为是递归定义，简称递归
优点：把一个大型复杂问题转化为一个规模较小的问题来求解，大大减小了程序的代码量，使问题的描述和求解变得简单清晰，算法更易设计

简述循环队列的数据结构，并写出初始状态，队列空、队列满时队首指针域队尾指针的值

有关排序算法复杂度和稳定性
串、数组、广义表从元素间关系上看可以看成线性结构，他们与一般意义上的线性表相比有何特殊性
串是零个至多个字符组成的有限序列。从数据结构角度讲，串属于线性结构，与线性表的特殊性在于串的元素是字符
数组类似于线性表，是由同种类型的数据元素构造而成，数组的每个元素由一个值和一组下标决定，数组中个元素之间的关系由下标体现出来
广义表是一种 非线性的数据结构，是线性表的一种推广，即广义表中放松对元素的原子限制，允许它们具有自身结构

借助栈可以实现更复杂的操作，请简述如何利用栈实现对表达式中括号是否匹配的检验
从左到右扫描表达式，发现“（”就入栈发现“）”就出栈，若无“(”则不匹配，扫描到最后若栈为空则匹配

图的广度优先遍历与树的何种遍历相似？请给出简单的解释
图的广度优先遍历和树的层次遍历相似，两者都是从一点出发访问其他相邻所有结点，树是看连接它的左右子树，图是看连通点

数据结构中经常使用“树形化组织”的方式来整理数据，比如折半查找表、二叉排序树、大顶堆/小顶堆等，请简述这样做的优点
用树形结构可以使数据的存储和查找更加方便，在进行查找时能极大提高效率，同时可以表示数据之间的关系

什么是队列的上溢？有哪些解决方法
在队列的顺序存储结构中，设队头指针为front，队尾指针为rear，队列的容量为maxnum，当有元素要加入队列时，若rear=maxnum，则会发生队列的上溢，此时就不能讲该元素入队。对于队列，还有一种假溢出现象，队列中尚有足够的空间，但元素不能入队，一般是由队列的存储结构或操作方式的选择不当导致，可以用循环队列解决。
解决上溢的办法：建立足够大的存储空间

对于线性别的两种存储结构，若线性表的总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素，应选用何种存储结构？
应选择顺序存储结构，因为每个数据元素的存储位置和线性表的起始位置相差一个和数据元素在线性表中的序号成正比的常数。因此只要确定了起始位置，线性表中的任意一个数据元素都可以随机存取，因此线性表的顺序存储结构是一种随机存取的数据结构，而链表则是一种顺序存取的存储结构

在单循环链表中设置尾指针比设置头指针好吗？为什么
设置尾指针比设置头指针好，尾指针是指向终端节点的指针，用它来表示单循环链表可以使得查找链表的开始结点和终端节点都和方便

  • 先序=中序：空树或者任一结点均无左孩子的非空二叉树
  • 后序=中序：空树或者任一结点均无右孩子的非空二叉树
  • 先序=后序：空树或者仅有一个结点的二叉树

我要回帖

更多关于 路径分为哪两大类 的文章

 

随机推荐