第2章 线性表Word文件下载.docx
《第2章 线性表Word文件下载.docx》由会员分享,可在线阅读,更多相关《第2章 线性表Word文件下载.docx(11页珍藏版)》请在冰点文库上搜索。
()6.顺序存储方式的优点是存储密度大,且插入、删除运算效率高。
()7.线性表在物理存储空间中也一定是连续的。
()8.线性表在顺序存储时,逻辑上相邻的元素未必在存储的物理位置次序上相邻。
()9.顺序存储方式只能用于存储线性结构。
()10.线性表的逻辑顺序与存储顺序总是一致的。
三、单项选择题
()1.数据在计算机存储器内表示时,物理地址与逻辑地址相同并且是连续的,称之为:
(A)存储结构(B)逻辑结构(C)顺序存储结构(D)链式存储结构
()2.一个向量第一个元素的存储地址是100,每个元素的长度为2,则第5个元素的地址是
(A)110(B)108(C)100(D)120
()3.在n个结点的顺序表中,算法的时间复杂度是O
(1)的操作是:
(A)访问第i个结点(1≤i≤n)和求第i个结点的直接前驱(2≤i≤n)
(B)在第i个结点后插入一个新结点(1≤i≤n)
(C)删除第i个结点(1≤i≤n)
(D)将n个结点从小到大排序
()4.向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变,平均要移动个元素
(A)8(B)63.5(C)63(D)7
()5.链接存储的存储结构所占存储空间:
(A)分两部分,一部分存放结点值,另一部分存放表示结点间关系的指针
(B)只有一部分,存放结点值
(C)只有一部分,存储表示结点间关系的指针
(D)分两部分,一部分存放结点值,另一部分存放结点所占单元数
()6.链表是一种采用存储结构存储的线性表;
(A)顺序(B)链式(C)星式(D)网状
()7.线性表若采用链式存储结构时,要求内存中可用存储单元的地址:
(A)必须是连续的(B)部分地址必须是连续的
(C)一定是不连续的(D)连续或不连续都可以
()8.线性表L在情况下适用于使用链式结构实现。
(A)需经常修改L中的结点值(B)需不断对L进行删除插入
(C)L中含有大量的结点(D)L中结点结构复杂
()9.单链表的存储密度
(A)大于1;
(B)等于1;
(C)小于1;
(D)不能确定
()10.设a1、a2、a3为3个结点,整数P0,3,4代表地址,则如下的链式存储结构称为
P0
3
4
a1
a2
A3
(A)循环链表(B)单链表(C)双向循环链表(D)双向链表
四、简答题
1.试比较顺序存储结构和链式存储结构的优缺点。
在什么情况下用顺序表比链表好?
2.描述以下三个概念的区别:
头指针、头结点、首元结点(第一个元素结点)。
在单链表中设置头结点的作用是什么?
第6章树和二叉树自测卷解答
一、下面是有关二叉树的叙述,请判断正误(每小题1分,共10分)
()1.若二叉树用二叉链表作存贮结构,则在n个结点的二叉树链表中只有n—1个非空指针域。
()2.二叉树中每个结点的两棵子树的高度差等于1。
()3.二叉树中每个结点的两棵子树是有序的。
()4.二叉树中每个结点有两棵非空子树或有两棵空子树。
()5.二叉树中每个结点的关键字值大于其左非空子树(若存在的话)所有结点的关键字值,且小于其右非空子树(若存在的话)所有结点的关键字值。
(应当是二叉排序树的特点)
()6.二叉树中所有结点个数是2k-1-1,其中k是树的深度。
(应2i-1)
()7.二叉树中所有结点,如果不存在非空左子树,则不存在非空右子树。
()8.对于一棵非空二叉树,它的根结点作为第一层,则它的第i层上最多能有2i—1个结点。
(应2i-1)
()9.用二叉链表法(link-rlink)存储包含n个结点的二叉树,结点的2n个指针区域中有n+1个为空指针。
()10.具有12个结点的完全二叉树有5个度为2的结点。
二、填空(每空1分,共15分)
1.由3个结点所构成的二叉树有种形态。
2.一棵深度为6的满二叉树有个分支结点和个叶子。
3.一棵具有257个结点的完全二叉树,它的深度为。
4.设一棵完全二叉树有700个结点,则共有个叶子结点。
5.设一棵完全二叉树具有1000个结点,则此完全二叉树有个叶子结点,有个度为2的结点,有个结点只有非空左子树,有个结点只有非空右子树。
6.一棵含有n个结点的k叉树,可能达到的最大深度为,最小深度为。
7.二叉树的基本组成部分是:
根(N)、左子树(L)和右子树(R)。
因而二叉树的遍历次序有六种。
最常用的是三种:
前序法(即按NLR次序),后序法(即按次序)和中序法(也称对称序法,即按LNR次序)。
这三种方法相互之间有关联。
若已知一棵二叉树的前序序列是BEFCGDH,中序序列是FEBGCHD,则它的后序序列必是。
8.中序遍历的递归算法平均空间复杂度为O(n)。
答:
即递归最大嵌套层数,即栈的占用单元数。
精确值应为树的深度k+1,包括叶子的空域也递归了一次。
9.用5个权值{3,2,4,5,1}构造的哈夫曼(Huffman)树的带权路径长度是。
三、单项选择题(每小题1分,共11分)
()1.不含任何结点的空树。
(A)是一棵树;
(B)是一棵二叉树;
(C)是一棵树也是一棵二叉树;
(D)既不是树也不是二叉树
()2.二叉树是非线性数据结构,所以。
(A)它不能用顺序存储结构存储;
(B)它不能用链式存储结构存储;
(C)顺序存储结构和链式存储结构都能存储;
(D)顺序存储结构和链式存储结构都不能使用
()3.具有n(n>
0)个结点的完全二叉树的深度为。
(A)log2(n)(B)log2(n)(C)log2(n)+1(D)log2(n)+1
()4.把一棵树转换为二叉树后,这棵二叉树的形态是。
(A)唯一的(B)有多种
(C)有多种,但根结点都没有左孩子(D)有多种,但根结点都没有右孩子
5.从供选择的答案中,选出应填入下面叙述?
内的最确切的解答,把相应编号写在答卷的对应栏内。
树是结点的有限集合,它A根结点,记为T。
其余的结点分成为m(m≥0)个
的集合T1,T2,…,Tm,每个集合又都是树,此时结点T称为Ti的父结点,Ti称为T的子结点(1≤i≤m)。
一个结点的子结点个数为该结点的。
供选择的答案
A:
①有0个或1个②有0个或多个③有且只有1个④有1个或1个以上
B:
①互不相交②允许相交③允许叶结点相交④允许树枝结点相交
C:
①权②维数③次数(或度)④序
6.从供选择的答案中,选出应填入下面叙述?
二叉树。
在完全的二叉树中,若一个结点没有,则它必定是叶结点。
每棵树都能惟一地转换成与它对应的二叉树。
由树转换成的二叉树里,一个结点N的左子女是N在原树里对应结点的,而N的右子女是它在原树里对应结点的。
①是特殊的树②不是树的特殊形式③是两棵树的总称④有是只有二个根结点的树形结构
①左子结点②右子结点③左子结点或者没有右子结点④兄弟
C~D:
①最左子结点②最右子结点③最邻近的右兄弟④最邻近的左兄弟
⑤最左的兄弟⑥最右的兄弟
四、简答题(每小题4分,共20分)
1.一棵度为2的树与一棵二叉树有何区别?
C的结点类型定义如下:
structnode
{chardata;
structnode*lchild,rchild;
};
C算法如下:
voidtraversal(structnode*root)
{if(root)
{printf(“%c”,root->
data);
traversal(root->
lchild);
printf(“%c”,root->
traversal(root->
rchild);
}
2.设如下图所示的二叉树B的存储结构为二叉链表,root为根指针,结点结构为:
(lchild,data,rchild)。
其中lchild,rchild分别为指向左右孩子的指针,data为字符型,root为根指针,试回答下列问题:
1.对下列二叉树B,执行下列算法traversal(root),试指出其输出结果;
2.假定二叉树B共有n个结点,试分析算法traversal(root)的时间复杂度。
(共8分)
3.给定二叉树的两种遍历序列,分别是:
前序遍历序列:
D,A,C,E,B,H,F,G,I;
中序遍历序列:
D,C,B,E,H,A,G,I,F,
试画出二叉树B,并简述由任意二叉树B的前序遍历序列和中序遍历序列求二叉树B的思想方法。
4.给定如图所示二叉树T,请画出与其对应的中序线索二叉树。
五、阅读分析题(每题5分,共20分)
1.(P604-26)试写出如图所示的二叉树分别按先序、中序、后序遍历时得到的结点序列。
2.(P604-27)把如图所示的树转化成二叉树。
BiTreeInSucc(BiTreeq){
//已知q是指向中序线索二叉树上某个结点的指针,
//本函数返回指向*q的后继的指针。
r=q->
rchild;
if(!
r->
rtag)
while(!
rtag)r=r->
returnr;
}//ISucc
3.阅读下列算法,若有错,改正之。
4.画出和下列二叉树相应的森林。
六、算法设计题(前5题中任选2题,第6题必做,每题8分,共24分)
1.编写递归算法,计算二叉树中叶子结点的数目。
2.写出求二叉树深度的算法,先定义二叉树的抽象数据类型。
(10分)
编写递归算法,求二叉树中以元素值为x的结点为根的子树的深度。
3.编写按层次顺序(同一层自左至右)遍历二叉树的算法。
或:
按层次输出二叉树中所有结点;
4.已知一棵具有n个结点的完全二叉树被顺序存储于一维数组A中,试编写一个算法打印出编号为i的结点的双亲和所有的孩子。
5.编写算法判别给定二叉树是否为完全二叉树。
6.假设用于通信的电文仅由8个字母组成,字母在电文中出现的频率分别为0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10。
试为这8个字母设计哈夫曼编码。
使用0~7的二进制表示形式是另一种编码方案。
对于上述实例,比较两种方案的优缺点。