《备考电大数据结构（本）填空题专练.doc》由会员分享，可在线阅读，更多相关《备考电大数据结构（本）填空题专练.doc（2页珍藏版）》请在三一办公上搜索。
1、二、填空题【每小题2分，共24分)1.结构中的数据元素存在一对多的关系称为树形结构。2.求两个n阶矩阵的乘积，算法的基本操作和时间复杂度分别为乘法和O(n3)3.在一个单向链表中，要删除P所指结点，已知Q指向P所指结点的前驱结点。则可以用操作q-next=p-next;4.向一个栈顶指针为h的链栈中插人一个s所指结点时，可执行s-next=h;和h=s;操作。(结点的指针域为next)5.串的两种最基本的存储方式分别是顺序存储和链式存储。6.对稀疏矩阵进行压缩存储，矩阵中每个非零元素对应的三元组包括该元素的行下标、列下标和非零元素值三项信息。7.设有一棵深度为4的完全二叉树，第四层上有5个结点
2、，该树共有12个结点。(根所在结点为第1层)8.一棵二叉树中有2n-2条边(结点间的连线)，其中每一个非叶结点的度数都为2，则该树共有n-1个非叶结点。9.如图2所示的二叉树，其中序遍历序列为dgbaechif10.哈希函数是记录关键字值与该记录存储地址之间所构造的对应关系。11.在对一组记录(55,39,97,22,16,73,65,47,88)进行直接插人排序时，当把第7个记录65插人到有序表时，为寻找插人位置需比较3次。12.n个元素进行冒泡法排序，通常需要进行n-1趟冒泡，第J趟冒泡要进行n-j次元素间的比较。1.结构中的数据元素存在多对多的关系称为图状结构。2.要求在n个数据元素中找
3、其中值最大的元素，设基本操作为元素间的比较。则比较的次数和算法的时间复杂度分别为n-1和O(n)3.设有一个头指针为head的单向循环表,P指向链表中的结点，若p- next =head,则P所指结点为尾结点。4.向一个栈顶指针为h的链栈中插人一个s所指结点时，可执行s- next = h;和h=s;5.在一个链队中，设f和r分别为队头和队尾指针，则插人s所指结点的操作为r-next =s;和r= s;(结点的指针域为next)6.设有n阶对称矩阵A，用数组S进行压缩存储，当i next= =NULL通过操作p- next=head，就可使该单向链表构造成单向循环链表。5.从一个栈顶指针为h的
4、链栈中删除一个结点时，用x保存被删结点的值，可执行x= h- data;和h=h-next;。(结点的指针域为一next)6.两个串相等的充分必要条件是串长度相等且对应位置的字符相等。7.对二叉树的遍历可分为先序、中序、后序、层次四种不同的遍历次序。8一棵有n个叶结点的二叉树，其每一个非叶结点的度数都为2，则该树共有2n-1个结点。9一棵有14个结点的完全二叉树，则它的最高层上有7个结点10.如图2所示的二叉树，其先序遍历序列为abdgcefhi11.哈希函数是记录关键字值与该记录存储地址之间所构造的对应关系。12.二叉树排序中任一棵子树都是二叉排序树，这种说法是正确的。(回答正确或不正确)1
5、.结构中的元素之间存在多对多的关系称为图状结构。2.设有一个单向循环链表，结点的指针域为next，头指针为head，指针P指向表中某结点，若逻辑表达式p-next= =head的结果为真，则p所指结点为尾结点。3.设有一个链栈，栈顶指针为hs，现有一个s所指向的结点要入栈，则可执行操作s-next=hs;hs=s。4.在一个链队中，f和r分别为队头和队尾指针，队结点的指针域为next, s指向一个要入队的结点，则入队操作为r-next=s; r=s;。5.循环队列的最大存储空间为MaxSize= 6，采用少用一个元素空间以有效地判断栈空或栈满，若队头指针front= 4，当队尾指针rear=3
6、时队满，队列中共有5个元素。6.程序段char*s=aBcD; n=0; while(*s!=0) if(*s=a&*snext=p-next;3.设有一个链栈,栈顶指针为hs,现有一个s所指向的结点要入栈，则可执行操作s-next=hs;和hs=s;4.在一个不带头结点的非空链队中， f和r分别为队头和队尾指针，队结点的数据域为data，指针域为next，若要进行出队操作， 并用变量x存放出队元素的数据值，则相关操作为x=f-data;f=f-next.5.顺序存储字符串ABCD需要占用5个字节。6.一棵二叉树叶结点(终端结点)数为5，单分支结点数为2，该树共有11个结点。7.设一棵完全二叉
7、树，其最高层上最右边的叶结点的编号为奇数，该叶节点的双亲结点的编号为10，该完全二叉树一共有21个结点。8. 结构中的数据元素存在一对多的关系称为树形结构。9. 结构中的数据元素存在一对一的关系称为线性结构。10.如图2所示的二叉树，其后序遍历序列为gdbeihfca11.图的深度优先搜索和广度优先搜索序列不一定是唯一的。此断言是正确的。(回答正确或不正确)1.通常数据的逻辑结构包括集合、线性、树形、图状 四种类型。2.设有一个单向链表,结点的指针域为next,头指针为head,p指向尾结点,为了使该单向链表改为单向循环链表,可用语句p-next=head;3.设有一个单向循环链表,头指针为h
8、ead,链表中结点的指针域为next,p指向尾结点的直接前驱结点,若要删除尾结点,得到一个新的单向循环链表,可执行操作p-next=head;4.在一个链队中,f和r分别为队头和队尾指针,队结点的指针域为next,则插入一个s所指结点的操作为r-next=s;r=s。5.循环队列的队头指针为f,队尾指针为r,当r=f时表明队列为空。6.串函数StrCat(a,b)的功能是进行串连接.7.一棵二叉树没有单分支结点,有6个叶结点,则该树总共有11个结点.8.按照二叉树的递归定义,对二叉树遍历的常用算法有先序、中序、后序 三种。9.把数据存储到计算机中,并具体体现数据之间的逻辑结构称为物理(存储)结
9、构10. 如图2所示的二叉树,其后序遍历序列为gdbeihfca。1.通常可以把一本含有不同章节的书的目录结构抽象成树形 结构。2.要在一个单向链表中p所指向的结点之后插入一个s所指向的新结点,若链表中结点的指针域为next,可执行 和p-next=s;s-next=p-next;的操作。3.设有一个非空的链栈,栈顶指针为hs,要进行出栈操作,用x保存出栈结点的值,找结点的指针域为next,则可执行x=hs-data;hs=hs-next;4.在一个不带头结点的非空链队中,f和r分别为队头和队尾指针,队结点的数据域为data,指针域为next,若要进行出队操作,并用变量x存放出队元素的数据值,
10、则相关操作为x=f-data;f=f-next;5.循环队列的最大存储空间为MaxSize=8,采用少用一个元素空间以有效的判断找空或栈满,若队头指针ront=4,则当队尾指针rear=4 时,队列为空,当rear=2 时,队列有6个元素。6.稀疏矩阵存储时,采用一个由行号 、列号 非零元3部分信息组成的三元组唯一确定矩阵中的一个非零元素。7.一棵二叉树顺序编号为6的结点(树中各结点的编号与等深度的完全二叉中对应位置上结点的编号相同),若它存在右孩子,则右孩子的编号为13。11.在队列的顺序存储结构中,当插入一个新的队列元素时,尾 指针的值增1,当删除一个元素队列时, 头 指针的值增1。12.循环队列的引入,目的是为了克服假上溢 。“电大天堂”
