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