电大数据结构-填空.doc

12_中序_遍历二叉排序树可得到一个有序序列。1 本书中介绍的树形结构和_图状结构_ 属非线性结构。 6串的两种最基本的存储方式是_顺序存储 链式存储_。19中序遍历_二叉排序_树可得到一个有序序列。 12在二叉树的链式存储结构中，通常每个结点中设置三个域，它们是值域 左指针 右指针 。1 数据的逻辑结构在计算机中的表示称为_物理_结构。 1数据元素可以有一个或_多个数据项_组成。2数据元素之间的抽象关系称为_逻辑_结构 。4结构中的数据元素存在多对多的关系称为_图状 _结构。2栈和队列的操作特点分别是_后进先出 和_先进先出 _。3 求两个n阶矩阵的乘积，算法的基本操作为_乘法_，时间复杂度为 _ O(n3)_。 4要求在n个数据元素中找值最大的元素，其基本操作为_元素间的比较_。算法的时间复杂度为_ O(n)_ 。 6根据数据元素间关系的不同特性，通常可分为集合、线性、树形 、 图状 四类基本结构。22对稀疏矩阵进行压缩存储，矩阵中每个非零元素对应的三元组包括该元素的_行下标、列下标、非零元素值_三项信息。22对记录序列排序是指按记录的某个关键字排序，记录序列按_主关键字_排序结果是唯一的。23在查找表中，通过记录的某关键字能唯一地确定一个记录，该关键字称为_主关键字_。24按某关键字对记录序列排序，若 关键字相等的记录 在排序前和排序后仍保持它们的前后关系，则排序算法是稳定的，否则是不稳定的。3 结构中的数据元素存在一对一的关系称为线性结构。而数据元素存在 _多对多_ 的关系称为图状结构。 18图的深度优先搜索和广度优先搜索序列不一定是唯一的。此断言是_正确_的。(回答正确或不正确) 23 给定一组权重值，构造哈夫曼树，哈夫曼树的高度一定是唯一的，这种说法是_不正确_的。(回答正确或不正确) 24二叉排序树或者是一棵空树，或者是一棵具有下列性质的二叉排：若它的左子树非空，则左子树的所有结点的值都小于它的根结点的值；若它的右子树非空，则右子的所有结点的值都大于（若允许结点有相同的值，则大于等于）它的根结点的值。这种说法是_不正确_的。(回答正确或不正确) 20二叉树为二叉排序的充分必要条件是其任一结点的值均大于其左孩子的值、小于其右孩子的值。这种说法是_不正确_的。(回答正确或不正确) 21对于一棵具有_n_个结点的二叉树，其相应的链式存储结构中共有n+1个指针域空 11 从一个栈顶指针为top的链栈中取栈顶元素，用d保存栈顶元素的值，可执行_ d=top-data;_。(结点的数据域为data) 11从一个栈顶指针为top的链栈中删除一个结点时，用d保存被删结点的值，可执行_ d=top-data;top=top-next;_。(结点的指针域为next,数据域为data) 18在一个链队中，设f和r分别为队头和队尾指针，则插入s所指结点的操作为_r-next=s;_和r=s; (结点的指针域为next)10在一个单向链表中，要删除p所指结点的直接后继结点。则可以用操作 _ p-next=p-next-next;_。（用一条语句）10在一个单向链表中p所指结点之后插入一个s所指向的结点时，应执行_ s-next=p-next; _和p-next=s;的操作。10对于一棵具有n个结点的二叉树，其相应的链式存储结构中共有_ n+1_个指针域为空。24在对一组记录(55,39,97,22,16,73,65,47,88)进行直接插入排序时，当把第7个记录65插入到有序表时，为寻找插入位置需比较_3_次。7在一个单向链表中p所指结点之后插入一个s所指向的结点时，应执行s-next=p-next;和 _ p-next=s;_的操作 17设有一棵深度为5的完全二叉树，该树共有20个结点,第五层上有 5 个叶结点。 （根所在结点为第1层） 16向一个栈顶指针为h的链栈中插入一个s所指结点时，可执行s-next=h;和_h=s_。11向一个栈顶指针为top的链栈中插入一个p所指结点时，某人用语句top=p；p-next=top;这样做的结果使p所指向的结点的指针域指向了 _ p本身_。 12向一个栈顶指针为top的链栈中插入一个p所指结点时，可执行_ p-next=top; top=p；_操作。 ( 填两条语句, 结点的指针域为next) 13在一个链队中，设front和rear分别为队头和队尾指针，则s所指结点(数据域已赋值)的入队操作为s-next=NULL;_ rear-next=s;_和rear=s; 14在一个带头结点的链队中，设front和rear分别为队头和队尾指针，则删除一个结点的操作为 p=front-next;_ front-next _=p-next;(结点的指针域为next, p为辅助用指针) 18 一棵3度的树，其中3度结1个，2度结2个，1度结2个，则该树共有_5_个叶结点。 17一棵有20个结点的4度的树，其中3度结1个，2度结1个，1度结2个，则该树共有_13_个叶结点。 19一棵有18个结点的二叉树，其2度结点数的个数为8，则该树共有 _1_个1度结点 4一棵二叉树中顺序编号为i的结点，若它存在左、右孩子，则左、右孩子编号分别为_2i和2i+1 _。8一棵有2n-1个结点的二叉树，其每一个非叶结点的度数都为2，则该树共有_n_个叶结点。20一棵有7个叶结点的二叉树，其1度结点数的个数为2，则该树共有_15_个结点 。 9一个栈和一个队列的输入序列都为abcdefg，它们可能有相同的输出序列吗？_ abcdefg _。 （若没有则回答没有，若有则写出序列,进栈出栈可以交替进行）。9设有一个带头结点的，头指针为head的单向链表，p指向表中某一个结点，且有p-next= =NULL,现要删除头结点，并使该单向链表构造成单向循环链表，通过操作head=head-next; _ p-next= head;_。 9设有一个头指针为head的单向链表，p指向链表中的某结点，若要使该链表成为单向循环链表，可用语句while(p-next!= NULL) p= p-next; 和_ p-next=head;_。 3设有一个长度为18的顺序表，要在第4个元素之前插入2个元素（也就是插入元素作为新表的第5个和第4个元素），则最少要移动元素的个数为（ 15 ）。 5 设有一个长度为25的顺序表,第8号元素到第25号元素依次存放的值为8,9,10,11,25,某人想要在第8个元素前插入1个元素7（也就是插入元素作为新表的第8个元素），他的做法是从第8号元素开始,直到第25号元素依次向后移动1个位置,然后把7存放在8号位置，其结果是新表中第25号元素的值为_8_ 。 5设有一个长度为25的顺序表，要删除前3个元素,则最少要移动元素的个数为（ 22 ）。6设有一个长度为25的顺序表,第8号元素到第25号元素依次存放的值为 8,9,10,11,25，某人想要删除第8个元素，他的做法是从第25号元素开始,直到第9号元素依次向前移动1个位置,其结果新表中第9号元素的值为（ 25 ）。 19设有一棵有78个结点的完全二叉树，该树共有_7_层。（根所在结点为第1层）20设有一棵深度为4的完全二叉树，第四层上有5个结点，该树共有_12_个结点。（根所在结点为第1层）5在双向链表中，要删除p所指的结点，可以先用语句（p-prior）-next=p-next；然再用语句（p-next）-prior=p-prior；。 7在双向链表中，要在p所指的结后插入q所指的结点(设q所指的结点已赋值)，其中所用的一条语句（p-next）-prior=q； 的功能是使P所指结点的_直接前驱的左指针_指向q 。 8要求在n个数据元素中找其中值最大的元素，设基本操作为元素间的比较。则比较的次数和算法的时间复杂度分别为_ n-1_和 _ O(n)_ 。13 循环链队列中，设front和rear分别为队头和队尾指针，(最多元素为MaxSize,采用少用一个元素的模式),判断循环链队列为满的条件为_ front= =(rear+1)% MaxSize _ 。13 循环链队列中，设front和rear分别为队头和队尾指针，(最多元素为MaxSize,),判断循环链队列为空的条件是_ front= =rear _为真 。15对稀疏矩阵进行压缩存储,可采用三元组表，一个6行7列的稀疏矩阵A相应的三元组表共有8个元素,则矩阵A共有_34_个零元素。 15 对稀疏矩阵进行压缩存储,可采用三元组表，设a是稀疏矩阵A相应的三元组表类型（结构体类型）变量，a中的一个成员项是三元组类型的结构体数组data，按书中定义，若adata0i=2;adata0j=3; adata0v=16; 它提供的 A数组的相关信息有_ A的第一个非零元素的下标为2，3 ，元素为16_17对稀疏矩阵进行压缩存储,可采用三元组表，设a是稀疏矩阵A相应的三元组表类型（结构体类型）变量，a中的一个成员项是三元组类型的结构体数组data，按书中定义，若data的下标从零开始，最后一个元素下标为10，又data10i=8;adata10j=5; adata10v=36; 它提供的 A数组的相关信息有_ A共有11个非零元素 ，a8,5为36_。 7在双向链表中，要删除p所指的结点，其中所用的一条语句（p-prior）-next=p-next；的功能是：使P所指结点的直接前驱的右指针指向_ P所指结点的直接后继_。8在双向链表中，要在p所指的结后插入q所指的结点(设q所指的结点已赋值)，可以先用语句q-next=p-next; （p-next）-prior=q；然后再用语句q-prior=p;和语句_ p-next=q；_。 15设有n阶对称矩阵A，用一维数组s压缩存储A的下三角元素，s的下标从零开始，元素s26相应于A中的元素为_ a7,6_。 16设有n阶对称矩阵A，用一维数组s压缩存储A的下三角元素，s的下标从零开始，最后一个元素的下标为27，则n=_7_。 21如图2所示的二叉树，其先序遍历序列为_215347896_。 efgibachd 3c7gd6f5e4dc2b1a8hd9 图214如图5所示的