数据结构-Pascal

1、数据结构-Pascal第一章什么是数据结构通常由下列四类基本结构:（1） 集合：数据元素间的关系是同属一个集合。（图1）（2） 线性结构：数据元素间存在一对一的关系。（图2）（3） 树形结构：结构中的元素间的关系是一对多的关系。（图3）（4） 图（网）状结构：结构中的元素间的关系是多对多的关系。（图4）1.单链表第二章线性表插入新元素:删除元素循环链表第三章栈出桂校顶栈底入枝特殊的表先进后出1. 某个车站呈狭长形，宽度只能容下一台车，并 且只有一个出入口。已知某时刻该车站状态为 空，从这一时刻开始的出入记录为：“进，出, 进，进，出，进，进，进，出，出，进，出。 假设车辆入站的顺序为1, 2,

2、 3,，则车 辆出站的顺序为（E ）。A. 1, 2, 3, 4, 5B. 1,2, 4, 5, 7C. 1, 3, 5,4, 6 D. 1, 3, 5, 6, 7 E. 1, 3, 6, 5, 7第四章队列特殊的表循环队列：我们将队列中从队头到队尾的元素按顺时针方向存放在循环数组中一段连续的单元中。当需要将新元素入队时，可将队尾游标Q.rear按顺时针方向移一位，并在新的队尾游标指示的单元中存入新元素。岀队操作也很简单，只要将队头游标 Q.front依顺时针方向移一位即可。容易看岀, 用循环数组来实现队列可以在0（1）时间内完成 Enqueue和Dequeue运算。执行一系列的入队与岀队运算

3、，将使整个队列在循环数组中按顺时针方向移动。通常，用队尾游标 元素所在的单元，用队头游标 Q.front指向队头元素所在单元的前一个单元，maxsize-1 个元素如图 3所示。Q.rear指向队尾并且约定只能存放第五章树和二叉树树的概念树的递归定义如下：（1 ）至少有一个结点（称为根）（2）其它是互不相交的子树1. 度树上任一结点所拥有的子树的数目称为该结点的度。入B的度为2, M的度为0。以组成该树各结点中最大的度作为该树的度，如上图的树，其度为3;树中度为零的结点称为叶结点或终端结点。树中度不为零的结点称为分枝结点或非终端结点。除根结点外的分枝结点统称为内部结点。2. 树的深度一一组成该

4、树各结点的最大层次，如上图，其深度为4 ；3. 森林指若干棵互不相交的树的集合，如上图，去掉根结点A，其原来的二棵子树 T1、T2、T3的集合T1,T2,T3就为森林；4. 有序树指树中同层结点从左到右有次序排列，它们之间的次序不能互换，这样的树称为有序树，否则称为无序树。二叉树二叉树是结点的有穷集合，它或者是空集，或者同时满足下述两个条件：(1)有且仅有一个称为根的结点；(2)其余结点分为两个互不相交的集合T1、T2、，T1和T2都是二叉树，并且分别称为根的 左子树和右子树。(1) 空二叉树一一(a)；(2) 只有一个根结点的二叉树一一(b);(3) 右子树为空的二叉树一一(c);(4) 左

5、子树为空的二叉树(d);(5) 完全二叉树一一(e)(1) 完全二叉树一一只有最下面的两层结点度小于2，并且最下面一层的结点都集中在该层最左边的若干位置的二叉树；(2) 满二叉树一一除了叶结点外每一个结点都有左右子女且叶结点都处在最底层的二叉树完全二叉树满二叉树二叉树性质：1、 在二叉树中，第i层的结点总数不超过 2A(i-1);满二叉树为2A(i-1)2、深度为h的二叉树最多有 2h-1个结点(h=1)，最少有h个结点；满二叉树为 2h-13、具有n个结点的完全二叉树的深度为int (log2n) +1练习：1、满二叉树的叶结点个数为N，则它的结点总数为(C )。A. N B. 2 * N

6、C. 2 * N T D. 2 * N + 1 E.2n -12、二叉树T,已知其前序遍历序列为1 2 4 3 5 76,中序遍历序列为4 2 1 5 7 3 6,则其后序遍历 序列为(B )A. 4 2 5 7 6 3 1B. 4 2 7 5 6 3 1C. 4 2 7 53 6 1 D. 4 7 2 3 5 6 1E. 4 5 2 6 3 7 15,乙13,则13(顶点的前后3、已知队列(13, 2, 11, 34, 41, 77,18, 26, 15),第一个进入队列的元素是 第五个出队列的元素是(B )。A) 5 B) 41 C) 77 D)E) 186.二叉树的遍历运算(递归定义)(

7、1)先序遍历访问根；按先序遍历左子树；按先序遍历右子树(2 )中序遍历按中序遍历左子树；访问根；按中序遍历右子树(3)后序遍历按后序遍历左子树；按后序遍历右子树；访问根第六章图概念图是由顶点 V的集合和边E的集合组成的二元组记 G=( V, E)如下图是一无向图 顺序不限)V=V1,V2,V3,V4,V5E=(V1,V2),(V2,V3),(V3,V4),(V4,V5),(V5,V1),(V2,V5),(V4,V1)下图是一有向图(顶点分先后顺序)V=V1,V2,V3,V4E=,vV2,V4,vV1,V3,vV3,V4,vV4,V1完全图(每一对不同的顶点都有一条边相连,n个顶点的完全图共有 n (n-1 ) /2条边)顶点的度：与顶点关联的边的数目，有向图中等于该顶点的入度与岀度之和。入度一一以该顶点为终点的边的数目和出度以该顶点为起点的边的数目和度数为奇数的顶点叫做奇点，度数为偶数的点叫做偶点。定理1图G中所有顶点的度数之和等于边数的2倍。因为计算顶点的度数时。每条边均用到2次。定理2任意一个图一定有偶数个奇点。练习：1、假设我们用d=(a1,a2,a5表示无向图G的 5个顶点的度数，下面给出的哪(些)组 d值合 理(BE )。A) 5 ,4,