还剩1页未读，继续阅读
文本内容:
第章习题参考解答2
一、名词解释1）线性表线性数据结构是由有限个元素组成的有序序列，记作（a，a...,a）o除b n了改和演之外，任意元素a都有一个直接前趋a-和一个直接后继ai+1a无前趋，an无后继2）栈是限制在表的一端进行插入和删除操作的线性表3）队列是只能在表的一端进行插入，而在另一端进行删除操作的线性表4）完全二叉树从满二叉树叶子所在的层次中，自右向左连续缺少若干叶子所得到的二叉树被称为完全二叉树5）带权路径长度二叉树有〃个带有权值的叶子结点，每个叶子到根的路径长度乘以其权值之和称为二叉树带权路径长度6）无向图若图是由一些顶点和边构成则称之为无向图7）图中的路径在图中，若从顶点Vi出发，沿一些边或弧，经过顶点加，v必…，Vpm,到达顶点Vj则称顶点序列（Vi,V i,V,Vpm,Vj）为从顶点Vi到顶点Vj的路p p2径8）生成树在无向图中，一个连通图的生成树是它的极小连通子图，它包含了所有顶点以及足以够成一棵树的边，并且这些边使得任意两顶点相互连通9）平均查找长度是为了确定数据元素在查找表中的位置，需要将给定值和表中的数据元素的关键字进行比较的次数的期望值10）图中的弧若顶点x到y是的一条单向通路，则称为弧，用＜x,y＞表示11）连通图在无向图中，若从顶点Vi到顶点Vj有路径，则称顶点Vi与门是连通的如果图中任意一对顶点都是连通的，则称此图是连通图
二、填空题
1.算法效率的衡量主要有两个指标时间复杂度和空间复杂度
2.采用顺序存储结构的线性表称为顺序表,它的数据元素按照逻辑顺序依次存放在一组连续的存储单元中逻辑上相邻的数据元素，其存储位置也相邻
3.单链表用一组地址上篆的存储单元存放线性表中的数据元素其逻辑上相邻的元素的物理位置不一定相邻
4.单链表每个结点都包含数据域和指针域两部分
5.为了能顺次访问单链表的每个结点，需要保存单链表第一个结点的存储地址这个地址称为单链表的头指针
6.为了操作上的方便，可以在单链表的头部增加一个特殊的结点，称为头结点该结点的数据域为空
7.树有且只有一个根结点,没有孩子结点的结点可称为叶子，二叉树的每个结点至多只有两棵子树
8.图结构又可分为无向图和有向图两大类在图结构中，数据元素通常称为顶点；两个数据元素间的联系在有向图中称为弧，在无向图中称为边
三、判断题
（1）线性表每个结点都有一个前趋和一个后继（错）
（2）二叉树不能用顺序方式存储（错）
（3）哈夫曼树又称最小生成树（错）
（4）图的深度优先遍历优于广度优先遍历（错）
（5）平均查找长度就是时间复杂度（错）
（6）冒泡排序的时间复杂度优于简单选择排序（错）
四、选择题
1.一个有头结点的单链表中，P为指向头结点的指针，则首元（位于头结点之后）指针可表示为（）oA.P.next,next B.P C.P.data D.P.next答D
2.数列4321依次执行入栈操作，在入栈过程中可以随时执行出栈操作，则其出栈顺序可能是（）oA.1423B.2413C.1234D.4132答C
3.具有35个结点的完全二叉树的深度为（）oA.4B.6C.8D.12答B
4.对长度为12的有序表进行二分查找，在等概率情况下，查找成功的ASL为（）oA.37/12B.39/11C.34/12D.33/11答A
5.一棵完全二叉树共有200个数据元素，自上而下自左向右编号，则第67号点的右孩子是（）号A.134B.135C.136D.137答B
6.二叉树的中序遍历顺序为abed,先序遍历顺序为cabd,则二叉树是下列（）答:。
个人认证
优秀文档
获得点赞 0
