数据结构原理与分析

发布时间:2018-12-17 作者:吉林大学自考招生信息网
数据结构原理内部资料 严禁外泄
1.什么是增长树?答:当二叉树中结点没有左子树形或没有右子树形时,增加特殊的结点,由此生成的二叉树称为增长的二叉树,简称增长树。
2.什么是线性表?答:一个线性表是由零个或多个具有相同类型的结点组成的有序集合。
3.什么是一维数组?答:一维数组是若干个元素的一个有限序列,每个元素都通过一个下标来指定,所有的数组元素都具有相同的数据类型,占据相同大小的存储空间.
4.什么是森林?答:一个森林就是一组(0个或多个)不相交的树形(通常诸树形间还有次序)。
5.什么是强连通图?答:若G为有向图,且对于V(G)中任意两个不同的顶点连通,也连通,则称G为强连通图。
6.什么是图中两点的简单路径?答:如果一条路径上除了起点和终点可以相同外,再无相同的顶点,则称此路径为简单路径。
7.设单链表中存放着n个字符,设计算法判断字符串是否中心对称,如xyzzyx即为中心对称的字符串。
答:将全部字符进栈,然后将栈中的字符逐个与链表中的字符比较
队列的定义是什么?答:队列是一种操作受限的线性表,它只允许在表的一端进行插入,在表的另一端进行删除。
8. 字符串的定义是什么?答:字符串是由零个或多个字符(字母、数字及其它一些符号)组成的有限连续序列,简称为串。
9. 二叉树的定义是什么?答:二叉树是结点的有限集合,它必须满足下面的一个条件:它是空集。
它由一个根结点和根结点的左右子树构成,且其左右子树满足二叉树定义。
10. 有向图的定义是什么?答:图G由两个集合V和E组成,记为G = (V , E) . 其中V是顶点的有限集合,E是连接V中两个不同顶点(顶点对)的边的有限集合。如果E中的顶点对是有序的,即E中的每条边都是有方向的,则称G为有向图。
11. AOV网的定义是什么?答:用顶点表示活动,有向边表示活动之间先后关系的有向图简称为AOV网。
12.设计一个算法,求出无向无权连通图中距离顶点v的最短路径长度为k的所有顶点,路径长度以变数为单位计算。
答:算法中须用从顶点v出发广度优先遍历的层次特性来求解,因此,访问顶点时要知道一个顶点相对于v的层数,而每个顶点的层数是由其前驱顶点决定的。
可以从顶点v开始,每访问到一个顶点就根据其前驱的层数计算该顶点的层数,并将层数值与顶点编号一起入队和出队。算法中可以使用两个队列,一个记录入队的顶点编号,另一个记录该顶点的层数,并保持二者的同步。
13. 两个整数序列A=a1,a2,a3,…,am和B=b1,b2,b3,…,bn已经存入两个单链表中,设计一个算法,判断序列B是否是序列A的子序列。
1) 给出算法的基本设计思想 (4分);
2) 用算法描述语言描述算法,并要求对算法中的关键步骤给出注释。
答:1)本题实质上是一个模式匹配问题,这里匹配的元素是整数而不是字符。因两整数序列已存入两个链表中,操作从两链表的第一个结点开始,若对应数据相等,则后移指针;若对应数据不等,则A链表从上次开始比较结点的后继开始,B链表仍从第一结点开始比较,直到B链表到尾表示匹配成功。A链表到尾B链表未到尾表示失败。操作中应记住A链表每次的开始结点,以便下趟匹配时好从其后继开始。
在线客服

关闭