数据结构综合练习

1、软件技术基础（二）数据结构（二）一、选择题只允许在一端进行插入删除的线性表称为.栈顶 B.队列 C.堆栈 D.队尾向顺序栈中压入元素时，A.先移动栈顶指针，后存入元素B.先存入元素，后移动栈顶指针C.谁先谁后无关紧要D.同时进行对链式存储的线性表。A.可采用顺序查找，但不可采用二分查找B.可采用二分查找，但不可采用顺序查找C.顺序查找和二分查找均可采用D.顺序查找和二分查找均不可采用线性表L在下列 情况下，适合使用链接结构实现。A.L中含有大量结点B.需经常对L表进行删除与插入C.需经常修改L的结点值 D.L表结点结构复杂设f和r分别是一个链表的队头和队尾，那么从该队列中删除一个结点的运算是。

2、A.r=f-next B.r=r-next C.f=f-next D.f=r-next设f和r分别是一个链表的队头和队尾，那么从该队列中插入一个结点的运算是。 A.r=f-next B.r=r-next C.f=f-next D.f=r-next在有n单元的顺序存储的堆栈中，假定以地址低端（即下标为1的单元）作为栈底，以top作为栈顶指针， 则当做入栈处理时,top的变化为：.A.top 不变 B. top=top+1 C. top=n D.top=top-1若进栈序列为1，2, 3, 4,假定进栈和出栈可以穿插进行，则不可能出栈的序列是.A. 1,4,3,2 B. 2,3,4,1 C. 3,

3、1,4,2 D. 3,4,2,1设栈初始为空，输入序列为：a，b，c，d。经过入栈、入栈、出栈、入栈、出栈、入栈操作之后，栈 中的元素（从栈底到栈顶）依次为。A. a，dB.a,c C. b， c D. d,a对于任何一棵二叉树，若叶子结点个数为n0，度为2的结点个数为n2，则n0=.A.n2-1B.n2C.n2+1D.2*n2一棵二叉树中共有70个叶子结点与80个度为1的结点，则该二叉树中的总结点数为A.219B.221C.229D.231深度为6的二叉树上共有 个叶子结点。A. 31B.32C.63D.64将有三棵树的森林转换成一棵二叉树，则第二棵树的根结点是该二叉树根结点的 的根结点。A

4、.左子树 B.左子女的右子树C.右子树 D.右子女的右子树将有三棵树的森林转换成一棵二叉树，则第三树的根结点是该二叉树根结点的 的根结点。A.左子树 B.左子树的右子树C.右子树D.右子树的右子树 假定一棵二叉树的结点数为18,则它的最小深度为.A.18B.9C.5D.3在具有size单元的顺序存储的循环队列中，假定front和rear分别指示队列中第一个元素和最后一 个元素的下一个位置，则判断队空的条件是： .A.front+1= rear B.front=0 C. front= rear D.front=rear+1在由m个单元组成的循环队列中，队首指针F指示队列中首元素的前一个位置，队尾

5、指针R指示队列 中最后一个元素，则判断队满的条件是。A.F=(R+1)%mB.F=RC.(F+1)%m=RD.R%m+1=F链栈与顺序栈相比，有一个比较明显的优点是A-插入操作更加方便B.通常不会出现栈满的情况C.不会出现栈空的情况D.删除操作更加方便如果n1和n2是二叉树T中两个不同结点，n2是n1的后代，那么按 遍历二叉树T时，结点n2 一定比结点n1先被访问。A.先序 B.中序 C.后序 D.逆中序一棵二叉树具有9个叶子结点。且非叶子结点都是度为2的结点，则这棵二叉树共有 结点。A.17B.18C.19D.20具有三个结点的二叉树的基本形态有 种。A.5B.4C.3D.2以下 不是队列的

6、基本操作。A.从队尾插入一个新元素B.从队列中删除第i个元素C.判断一个队列是否为空D。读取队头元素的值。在树结构中，如果结点A有3个兄弟，而且B是A的双亲，则B的度是。A.3 B.1C.4 D5.线性表是A. 一个有限序列，可以为空B. 一个有限序列，不能为空C. 一个无限序列，可以为空D. 一个无限序列，不能为空线性表采用链式存储时，其地址A.必须是连续的B。部分地址必须是连续的C. 一定是不连续的D.连续与否均可以一维数组和线性表的区别是。A.前者长度固定，后者长度可变B。后者长度固定，前者长度可变C.两者长度均固定D.两者长度均可变数据结构中，与所使用的计算机无关的是数据的 结构.A.

7、存储 B.物理 C.物理和存储D.逻辑 链表不具有的特点是。A.随机访问B.不必事先估计存储空间（1插入删除时不需移动元素D.所需空间与线性表成正比二叉树有多种形式，若深度为K,且有2K-1个结点的二叉树称为。A.完全二叉树B.满二叉树C.顺序二叉树D.排序树已知某二叉树的前序序列是ABDC，中序序列是DBAC，问它的后序序列是。A. ADBC B. DBCA C. CABD D.DCBA上溢现象通常出现在.A.顺序栈的入栈操作过程中B.顺序栈的出栈操作过程中C.链栈的入栈操作过程中D.链栈的出栈操作过程中引起循环队列队头位置发生变化的操作是.A.出队 B.入队 C.取队头元素D.取队尾元素除

8、第一层外，满二叉树中每一层结点个数是上一层结点个数的.A.1/2 倍 B. 1 倍 C. 2 倍 D. 3 倍在任意一棵二叉树的前序序列和后序序列中，各叶子之间的相对次序关系.A.不一定相同 B.都相同 C.都不相同 D.互为逆序一棵二叉树中共有10个叶子结点与20个度为1的结点，则该二叉树中的总结点数为A.30B.31C.39D.40栈结构通常采用的两种存储结构是A.顺序存储结构和链表存储结构B.链表存储结构和数组C.线性存储结构和非线性存储结构D.散列方式和索引方式 链式存储的存储结构所占存储空间。分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针只有一部分，存放结点值只有一部分

9、，存储表示结点间关系的指针分两部分，一部分存放结点值，另一部分存放结点所占单元数只允许在二端进行插入删除的线性表称为.A.栈顶 B.队列 C.堆栈 D.队尾堆栈结构的特点是。A.同时进出 B.先进先出C.后进后出D.后进先出网状数据模型.A.允许有一个以上的结点无双亲B有且只有一个结点无双亲C .除了一个根结点，其他结点只有一个双亲 D.每一个结点的子女不能多于一个学校中学生作为一个实体与他的学习课程（另一个实体）之间的联系是.A.一对一B.多对多 C一对多0.多对一 链表中进行 操作的效率比顺序表中高。A.二分查找和删除B.插入和删除C.二分查找和插入 D.快速查找当栈中的元素为n个，作进栈

10、运算时发生上溢，则说明该栈的最大容量为.A.n-1B.n C.n+1D.n/2栈和队列.A.的共同点都是先进后出B.的共同点都是先进先出C.的共同点是只允许在端点处插入和删除元素D.没有共同点二.填空题有一棵顺序二叉树，有编号为22结点的双亲，其左孩子在 编号位置上。在深度为7的满二叉树中，度为2的结点个数为。按“先进后出”原则组织数据的数据结构是。需要对线性表进行插入和删除运算，则最好采用 存储结构。若一个栈的输入序列是1，2, 3.，n，输出序列的第一个元素是n，则第I个输出元素是。允许在一端进行插入，而在一端进行删除的线性表称为.对于任一棵二叉树，若叶子结点个数为n0,度为2的结点数为n

11、2，则n2=.一个具有22个叶子结点的二叉树，其度数为2的结点数是。在二叉树上的第3层上至多有 个结点.采用二叉链表存储二叉树时，具有10个结点的二叉树，则有 个指针域为空。一棵二叉树其终端结点为10，则度为2的结点数有 个。深度为K的满二叉树有 个结点.（K=1）顺序表是一种随机存取的存储结构，而单链表是一种 的存储结构.需要对线性表经常进行插入和删除运算，则最好采用 存储结构。为了最快的存取某元素，宜用顺序结构；为了方便地插入一个元素，宜用.设有n个节点的完全二叉树，顺序存放在数组A1.n中，对任一个节点Ai，若Ai有左子女， 则左子女是数组A的 .设有n个节点的完全二叉树，顺序存放在数组

12、A1.n中，对任一个节点Ai，若Ai有父母，则 父母是数组A的 . 链式存储结构的特点是借助 来表示数据元素之间的逻辑关系。树形结构中节点a有4个兄弟，b是a的双亲，则b的度为二元组（D，R）来表示数据结构，那么D指数据元素，R指。二叉排序树进行中序遍历时，得到的结点序列是一个.在树中，一个结点的直接子结点的个数称为该结点的.数据库的层次模型有且仅有一个结点无双亲，而网状模型一定会有 结点无双亲，这是与层次模型的重要区别。三改错题如果一棵二叉树中的结点的度只有0或2,则称此树为满二叉树。（）栈是操作受限的线性表，它的运算仅能在线性表的二端进行。（） TOC o 1-5 h z 在顺序表中插入和

13、删除元素时，移动元素的个数仅与该元素的位置有关。（）顺序存储方式的优点是存储密度大，且插入和删除运算效率高.（）用树的前序遍历和后序遍历可以导出树的中序遍历。（）如果一棵二叉树中的结点的度只有0或2,则称此树为顺序二叉树。（）栈是操作受限的线性表，它的运算仅能在线性表的二端进行。（）用树的前序遍历和中序遍历可以导出树的后序遍历。二叉树是树的特殊情况。在哈夫曼树中，权重的结点离树根愈远。将一棵树转换成二叉树后，根结点没有左子树。二叉树中每个结点有二个子结点，而一般的树则无此限制，因此二叉树是树的特殊情况。链接存储方式的优点是存储密度大，但是插入和删除运算效率差。每个结点的度都小于等于2的树是二叉

14、树。不使用递归，也可以实现二叉树的前序、中序、后序遍历。完全二叉树中，若一个结点没有左孩子，则它必然是叶子。图结构是一种线性数据结构.二叉树中结点只有一个孩子时无左右之分.堆栈结构是一种特殊的线性数据结构二叉树中必有度为 2 的结点简答题（每题5分，共15分）什么是数据的逻辑结构?什么是数据的物理结构？数据结构有几种类型？各有什么特点？请分别写出栈和队的定义，并写出它们的简单应用例。试画出具有三个结点的二叉树的所有不同形态。栈与队列是两种特殊的线性表，栈的特点是什么？队的特点是什么？二叉树和树有什么不同？综合应用题（共3*7=21分）若a，b，c，d，e，f的权重分别为11,2,16,3,22,18，试构造关于w的一棵哈夫曼树，并求出其 wpl和各字符的编码（结点的排列为左小右大）。95.设二叉树的存储结构如下:12345678910Lchild00237580101JHFDBACEGI0009400000DataRchild其中根结点的指针值为6 , Lchild、Rchild分别为结点的左、右孩子指针域，Data为数据域。画出该二叉树的逻辑结构。写出该二叉树的前序、中序和后序遍历的序列。有一棵二叉树如5图所示，试写出该二叉树的中序遍历和后序遍历序列。假设一棵二叉树的先序遍历序列为FAMBXCR，中序遍历序列为AFXBMCR，请画出该二叉树和求出二叉 树的后序遍历序列。98