内蒙古工业大学谢秀兰计算机软件基础小抄.docVIP

数据是现实世界客观存在的实体或事情的属性值。是信息的载体。 硬件系统的组成：运算器、控制器、存储器、输入设备输出设备。 数据对象：具有相同性质的数据元素的集合。 数据结构： 数据结构是指同一数据对象中各数据元素间存在的关系。 S=(D,R) D是一个数据元素的非空有限集合，R是定义在D上的关系的非空有限集合。 算法表示：算法名（参量表） 6、线性表的基本运算有： (1)插入：在两个确定元素之间插入一个新元素。 (2)删除：删除线性表中某个元素。 (3)查找：按某种要求查找线性表中的一个元素，需要时可以进行更新。 (4)排序：按给定要求对表中元素重新排序。 7、插入 设在长度为n的线性表中第i个元素前插入一个元素x，其中存放线性表的向量为V[1:m](mn)，算 法如下： INSERTLIST(V,n,i,x) if (i1) OR (in+1) then {参数错 return} for j=n to i step(-1) V[j+1]←V[j] end (j) V[i] ←x n← n+1 return 8、回收一个由p指针指向的结点，放回空白链表的算法为： RET(p) next(p) ←av av ←p return 9、设有顺序s[1:m],top为栈顶指示器，其插入（进栈）和删除（退栈）运算如下： PUSH(s,m,top,x)//将元素x入栈// 1. if(top=m)then{“上溢”，return} 2. top←top+1 3. s[top] ←x 4. return POP(s,top,y)//退栈，将栈顶元素送入y中// 1. if(top=0)then{“下溢”，return} 2. y← s[top] 3. top←top-1 4. return 10、 设CQ[0:m-1]表示最大容量为m的循环队列， 其中头、尾指示(front,rear)均按顺时针方向前进，rear=front=n-1为初态。 循环队列的插入和删除算法如下： ADDCQ(CQ,m,front,rear,x)//将x插入队列CQ中// 1. if(front=(rear+1)mod m) then {“队满” return} 2. rear ←(rear+1) mod m 3. CQ[rear]←x 4. return DELCQ(CQ,m,front,rear,y)//删除队首元素送入y中// 1. if(front=rear) then {“队空”return} 2. front ←(front+1) mod m 3. y← CQ[front] 4. return 11、设A，B分别为某稀疏矩阵转置前后的三元组表，i为行下标，j为列下标，v为元素值。变量m为稀疏矩阵行数，n为稀疏矩阵列数，tu为非零元素个数。本算法要求把A中的行下标、列下标交换后送到B中，并且使B中行下标仍按递增顺序存放。 TRANSMAT(A，B) 1．if(tu≠0) then 2．{q←1 //q为转置以后B的行号// 3．for col＝1 to n 4． for p＝1 to tu //p为转置前A的行号// 5． if A[p]．j＝col then 6． {B[q]．i←A[p]．j; B[q]．j←A[p]．i; 7． B[q] ．v ← A[p]．v；q←q+1} 8． end(p) 9． end(col)} 10． return 12、树的定义： 树是由n个(n≥0)结点组成的有限集合T，其中有且仅有一个结点称为根结点(root)，其余结点可以分为m(m≥0)个互不相交的有限集合T1,T2,…,Tm，其中每一个集合Ti本身又是一棵树，称为根结点root的子树。 用二元组关系来定义树为 Tree＝(T，R) 其中数据元素集合T及关系R组成。 13、树结构中的术语: 结点(node)：表示树中的元素。 结点的度(degree)：结点拥有的子树数。 叶子(leaf)：度为零的结点，又称端结点。 孩子(child)：除根结点外，每个结点都是其前趋结点的孩子。 双亲(parents)：对应上述孩子结点的上层结点称为这些结点的双亲。 兄弟(sibling)：同一双亲的孩子。 结点的层次(level)：从根结点开始算起，根为第一层，根的直接后继结点为第二层，其余各层依此类推。 深度(depth)：树中结点的最大层次数。 森林(forest)：是m(m≥0)棵互不相交的树的集合。 有序树：树中结点在同层中按从左至右有序排列、不能互换的称为有序树，反之称为无序树。 14、二叉