电大2016年度考试数据结构复习题填空题小抄.doc

电大数据结构复核习题（填空题） 在一个长度为n的顺序存储结构的线性表中，向第i(1(i(n+1)个元素之前插入新元素时，需向后移动 n-i+1 个数据元素。 从长度为n的采用顺序存储结构的线性表中删除第i(1(i(n+1)个元素 ，需向前移动 n-i 个元素。 数据结构按结点间的关系，可分为4种逻辑结构： 集合 、 线性结构 、 树形结构 、 图状结构 。 数据的逻辑结构在计算机中的表示称为 物理结构 或 存储结构 。 除了第1个和最后一个结点外，其余结点有且只有一个前驱结点和后继结点的数据结构为 线性结构 ，每个结点可有任意多个前驱和后继结点数的结构为 非线性结构 。 算法的5个重要特性是 有穷性 、 确定性 、 可形性 、 有零个或多个输入 、 有零个或多个输出 。 数据结构中的数据元素存在多对多的关系称为 图状结构 结构。 数据结构中的数据元素存在一对多的关系称 树形结构 结构。 数据结构中的数据元素存在一对一的关系称为 线性结构 结构。 要求在n个数据元素中找其中值最大的元素，设基本操作为元素间的比较。则比较的次数和算法的时间复杂度分别为 n-1 和 O(n) 。 在一个单链表中p所指结点之后插入一个s所指结点时，应执行__s-next=p-next;__和p-next=s;的操作。 设有一个头指针为head的单向循环链表，p指向链表中的结点，若p-next= = head ，则p所指结点为尾结点。 在一个单向链表中，要删除p所指结点，已知q指向p所指结点的前驱结点。则可以用操作 q-next=p-next; 。 设有一个头指针为head的单向链表，p指向表中某一个结点，且有p-next= =NULL,通过操作 p-next=head; ,就可使该单向链表构造成单向循环链表。 每个结点只包含一个指针域的线性表叫 单链表 。 线性表具有 顺序存储 和 链式存储 两种存储结构。 数据的逻辑结构是从逻辑关系上描述数据，它与数据的关系 存储结构 无关，是独立于计算机的。 在双向循环链表的每个结点中包含 两个 指针域，其中next指向它的 直接后继 ，prior指向它的 直接前驱 ，而头结点的prior指向 尾结点 ，尾结点的next指向 头结点 。 单向循环链表是单向链表的一种扩充，当单向链表带有头结点时，把单向链表中尾结点的指针域由空指针改为 头结点的指针 ；当单向链表不带头结点时，则把单向链表中尾结点的指针域由空指针改为指向 指向第一个结点的指针 。 线性链表的逻辑关系时通过每个结点指针域中的指针来表示的。其逻辑顺序和物理存储顺序不再一致，而是一种 链式 存储结构，又称为 链表 。 栈是限定在表的一端进行插入和删除操作的线性表，又称为 后进先出表 。 队列的特性是 先进先出表 。 往栈中插入元素的操作方式是：先 移动栈顶指针 ，后 存入元素 。 删除栈中元素的操作方式是：先 取出元素 ，后 移动栈顶指针 。 循环队列队头指针在队尾指针 下一个 位置，队列是“满”状态 在队列的顺序存储结构中，当插入一个新的队列元素时，尾指针 增1 ，当删除一个元素队列时，头指针 增1 。 循环队列的引入，目的是为了克服 假上溢 。 向顺序栈插入新元素分为三步：第一步进行 栈是否满 判断，判断条件是 s-top=MAXSIZE-1 ；第二步是修改 栈顶指针 ；第三步是把新元素赋给 栈顶对应的数组元素 。同样从顺序栈删除元素分为三步：第一步进行 栈是否空 判断，判断条件是 s-top=-1 。第二步是把 栈顶元素 ；第三步 修改栈顶指针 。 假设以S和X分别表示入栈和出栈操作，则对输入序列a,b,c,d,e一系列栈操作SSXSXSSXXX之后，得到的输出序列为 bceda 。 一个递归算法必须包括 终止条件 和 递归部分 。 判断一个循环队列LU（最多元素为m0）为空的条件是 LU-front==LU-rear 。 在将中缀表达式转换成后缀表达式和计算后缀表达式的算法中，都需要使用栈，对于前者，进入栈中的元素为表达式中的 运算符 ，而对于后者，进入栈的元素为 操作数 ，中缀表达式(a+b)/c-(f-d/c)所对应的后缀表达式是 ab+c/fde/-- 。 向一个栈顶指针为h的链栈中插入一个s所指结点时，可执行 s-next=h; 和h=s;操作。(结点的指针域为next)。 从一个栈顶指针为h的链栈中删除一个结点时，用x保存被删结点的值，可执行x=h-da