电大数据结构复核习题（填空题）
1、 在一个长度为n的顺序存储结构的线性表中，向第i(1?i?n+1)个元素之前插入新元素时，需向后移动n-i+1个
数据元素。
2、 从长度为n的采用顺序存储结构的线性表中删除第i(1?i?n+1)个元素，需向前移动n-i个元素。 3、 数据结构按结点间的关系，可分为4种逻辑结构：集合、线性结构、树形结构、图状结构。 4、 数据的逻辑结构在计算机中的表示称为物理结构或存储结构。
5、 除了第1个和最后一个结点外，其余结点有且只有一个前驱结点和后继结点的数据结构为线性结构，每个结点
可有任意多个前驱和后继结点数的结构为非线性结构。
6、 算法的5个重要特性是有穷性、确定性、可形性、有零个或多个输入、有零个或多个输出。 7、 数据结构中的数据元素存在多对多的关系称为图状结构结构。 8、 数据结构中的数据元素存在一对多的关系称树形结构结构。 9、 数据结构中的数据元素存在一对一的关系称为线性结构结构。 10、
要求在n个数据元素中找其中值最大的元素，设基本操作为元素间的比较。则比较的次数和算法的时间复
杂度分别为n-1和O(n)。 11、
在一个单链表中p所指结点之后插入一个s所指结点时，应执行__s->next=p->next。__和p->next=s。的
操作。 12、
设有一个头指针为head的单向循环链表，p指向链表中的结点，若p->next= =head，则p所指结点为尾
结点。 13、
在一个单向链表中，要删除p所指结点，已知q指向p所指结点的前驱结点。则可以用操作q->next=p-
>next。。 14、
设有一个头指针为head的单向链表，p指向表中某一个结点，且有p->next= =NULL,通过操作p-
>next=head。,就可使该单向链表构造成单向循环链表。 15、 16、 17、 18、
每个结点只包含一个指针域的线性表叫单链表。 线性表具有顺序存储和链式存储两种存储结构。
数据的逻辑结构是从逻辑关系上描述数据，它与数据的关系存储结构无关，是独立于计算机的。 在双向循环链表的每个结点中包含两个指针域，其中next指向它的直接后继，prior指向它的直接前驱，
而头结点的prior指向尾结点，尾结点的next指向头结点。 19、
单向循环链表是单向链表的一种扩充，当单向链表带有头结点时，把单向链表中尾结点的指针域由空指针
改为头结点的指针；当单向链表不带头结点时，则把单向链表中尾结点的指针域由空指针改为指向指向第一个结点的指针。 20、
线性链表的逻辑关系时通过每个结点指针域中的指针来表示的。其逻辑顺序和物理存储顺序不再一致，而
是一种链式存储结构，又称为链表。 21、 22、 23、 24、 25、
栈是限定在表的一端进行插入和删除操作的线性表，又称为 后进先出表 。 队列的特性是先进先出表。
往栈中插入元素的操作方式是：先移动栈顶指针，后存入元素。 删除栈中元素的操作方式是：先取出元素，后移动栈顶指针。 循环队列队头指针在队尾指针下一个 位置，队列是“满”状态
1 / 4
26、 在队列的顺序存储结构中，当插入一个新的队列元素时，尾指针增1，当删除一个元素队列时，头指针增
1。 27、 28、
循环队列的引入，目的是为了克服假上溢。
向顺序栈插入新元素分为三步：第一步进行栈是否满判断，判断条件是s->top=MAXSIZE-1；第二步是修
改栈顶指针；第三步是把新元素赋给栈顶对应的数组元素。同样从顺序栈删除元素分为三步：第一步进行栈是否空判断，判断条件是s->top=-1。第二步是把栈顶元素 ；第三步修改栈顶指针。 29、
假设以S和X分别表示入栈和出栈操作，则对输入序列a,b,c,d,e一系列栈操作SSXSXSSXXX之后，得到
的输出序列为bceda。 30、 31、 32、
一个递归算法必须包括终止条件和递归部分。
判断一个循环队列LU（最多元素为m0）为空的条件是LU->front==LU->rear。
在将中缀表达式转换成后缀表达式和计算后缀表达式的算法中，都需要使用栈，对于前者，进入栈中的元
素为表达式中的运算符，而对于后者，进入栈的元素为操作数，中缀表达式(a+b)/c-(f-d/c)所对应的后缀表达式是ab+c/fde/--。 33、
向一个栈顶指针为h的链栈中插入一个s所指结点时，可执行 s->next=h。 和h=s。操作。(结点的指针域
为next)。 34、
从一个栈顶指针为h的链栈中删除一个结点时，用x保存被删结点的值，可执行x=h->data。和h=h-
>next。 。(结点的指针域为next) 35、
在一个链队中，设f和r分别为队头和队尾指针，则插入s所指结点的操作为r->next=s。 和r=s。 (结
点的指针域为next) 36、
在一个链队中，设f和r分别为队头和队尾指针，则删除一个结点的操作为f=f->next。 。 (结点的指针
域为next) 37、 38、 39、 40、 41、 42、 43、 44、
串是一种特殊的线性表，其特殊性表现在组成串的数据元素都是字符 。 串的两种最基本的存储方式是顺序存储方式 和链式存储方式 。 空串的长度是0；空格串的长度是空格字符的个数 。 需要压缩存储的矩阵可分为特殊 矩阵和稀疏 矩阵两种。
设广义表L=（（），（）），则表头是（） ，表尾是（）） ，L的长度是2 。 广义表A（（a,b,c）,(d,e,f)）的表尾为（（d,e,f）） 。 两个串相等的充分必要条件是串长度相等且对应位置的字符相等 。
设有n阶对称矩阵A，用数组s进行压缩存储，当i?j时，A的数组元素aij相应于数组s的数组元素的
下标为i(i-1)/2+j 。（数组元素的下标从1开始）。 45、
对稀疏矩阵进行压缩存储，矩阵中每个非零元素对应的三元组包括该元素的行下标 、列下标 和非零元素
值 三项信息。 46、 47、 48、 49、 50、 51、
结点的度是指结点所拥有的子树树木或后继结点数 。 树的度是指树中所有结点的度的最大值 。 度大于0的结点称作分支结点 或非终端结点 。 度等于0的结点称作叶子结点 或终端结点 。
在一棵树中，每个结点的子树的根 或者说每个结点的后继结点 称为该结点的孩子结点 ，简称为孩子。 一个结点称为其后继结点的双亲结点（简称双亲） 。
2 / 4
52、 53、 54、 55、 56、 57、 58、 59、
具有同一双亲 的结点互称为兄弟结点，简称为兄弟。 每个结点的所有子树中的结点被称为该结点的子孙 。 从根结点到该结点所经分支上的所有结点称为该结点的祖先 。 树的深度或高度是指树中结点的最大层数 。 m(m?0)棵互不相交的树的集合称为森林 。 度为k的树中的第i层上最多有Ki-1 结点。 深度为k的二叉树最多有2k-1 结点。
在一棵二叉树中，如果树中的每一层都是满的，则称此树为满二叉树 ；但如果出最后一层外，其余层都
是满的，并且最后一层是满的，或者是在缺少若干连续个结点，则称此二叉树为完全二叉树 。 60、 61、
具有n个结点的完全二叉树的深度是?log2n??1。
先序遍历二叉树的的操作定义为；若二叉树为空，则为空操作，否则进行如下操作，访问二叉树的根结
点 ；先序遍历二叉树的左子树 ，先序遍历二叉树的右子树 。 62、
中序遍历二叉树的的操作定义为；若二叉树为空，则为空操作，否则进行如下操作，中序遍历二叉树的左
子树 ；访问而叉树的根结点 ，中序遍历二叉树的右子树 。 63、
后序遍历二叉树的的操作定义为；若二叉树为空，则为空操作，否则进行如下操作，后序遍历二叉树的左
子树 ；后序遍历二叉树的右子树 ，访问而叉树的根结点 。 64、 65、 66、
将树中结点赋上一个有着某种意义的实数，称此实数为该结点的权 。 树的带权路径长度为树中所有叶子结点的 带权路径长度之和 。
哈夫曼树又称为最优二叉树 ，它是n个带权叶子结点构成的所有二叉树中带权路径长度WPL最小的二叉
树 。 67、 68、 69、 70、 71、 72、 73、 74、 75、 76、 77、 78、
若以4，5，6，7，8作为叶子结点的权值构造哈夫曼树，则其带权路径长度是69 。 具有m个叶子结点的哈夫曼树共有2m-1 结点。
在图中，任何两个数据元素之间都可能存在关系，因此图的数据元素之间是一种多对多 的关系。 图的邻接矩阵表示法是用一个二维数组 来表示图中顶点之间的相邻关系。 邻接表是图中的每个顶点建立一个邻接关系的单链表 。
图的遍历是从图的某一顶点出发，按照一定的搜索方法对图中所有顶点 各做一次 访问的过程。 图的深度优先搜索遍历类似于树的先序 遍历。 图的广度优先搜索类似于树的按层次 遍历。
具有n个顶点的有向图的邻接矩阵，其元素个数为n2 。 具有n个顶点的无向图至少有条边，才能确保其为一个连通图。 图常用的两种存储结构是邻接矩阵 和邻接表 。
一个AOV网（顶点活动图）应该是一个有向无环图 。即不应该带有回路，否则回路上的所有活动都无法
进行 。 79、 80、 81、 82、
用邻接矩阵存储有向图G，其第i行的所有元素之和等于顶点i的出度 。 在有n个顶点的有向图中，每个顶点的度最大可达2(n-1) 。 在一个带权图中，两顶点之间的最段路径最多经过n-1 条边。
为了实现图的深度优先搜索遍历，其非递归的算法中需要使用的一个辅助数据结构为栈 。
3 / 4