《计算机数据结构期末复习题》由会员分享，可在线阅读，更多相关《计算机数据结构期末复习题（8页珍藏版）》请在金锄头文库上搜索。
1、本文格式为Word版，下载可任意编辑计算机数据结构期末复习题 计算机数据布局期末复习题 1. 数据布局是一门研究非数值计算的程序设计问题中计算机的 操作对象 以及它们之间的 关系 和运算等的学科。 2. 数据布局被形式地定义为（D, R），其中D是 数据元素 的有限集合，R是D上的 关系 有限集合。 3. 数据布局包括数据的 规律布局 、数据的 存储布局 和数据的 运算 这三个方面的内容。 4. 数据布局按规律布局可分为两大类，它们分别是 线性布局 和 非线性布局 。 5.有n个球队加入的足球联赛按主客场制举行比赛，共需举行n(n-1)场比赛。 参考答案： n(n-1) 6.一棵树的前根遍历序
2、列为EFHIGJK，后根遍历序列为HFIEJKG，将树转换成二叉树形式后，该二叉树的后序遍历序列为HIFKJGE。 5. 线性布局中元素之间存在一对一关系，树形布局中元素之间存在一对多关系，图形布局中元素之间存在多对多关系。 6 在线性布局中，第一个结点 没有 前驱结点，其余每个结点有且只有 1个前驱结点；结果一个结点 没有 后续结点，其余每个结点有且只有1个后续结点。 7. 在树形布局中，树根结点没有 前驱 结点，其余每个结点有且只有 1 个前驱结点；叶子结点没有 后续 结点，其余每个结点的后续结点数可以任意多个 。 8. 在图形布局中，每个结点的前驱结点数和后续结点数可以 任意多个 。 9
3、数据的存储布局可用四种根本的存储方法表示，它们分别是依次 、 链式 、 索引 和 散列 。 10. 数据的运算最常用的有5种，它们分别是插入 、 删除、修改、 查找 、排序。 11.在一棵m阶B树上，每个内部结点的关键字数目最少为?m/2?-1个，最多为m-1个，其子树数目最少为?m/2?，最多为m。 12. 后缀算式9 2 3 +- 10 2 / -的值为 -1； 中缀算式8-(3+5)*(5-6/2)对应的后缀算式为8 3 5 + 5 6 2 / - * -。 13. 在一段文字中，5个常用汉字及展现频度如下：于 个 和 是 有 18 17 14 10 1 要求： (1)求出每个汉字的Hu
4、ffman编码：于:11 个:10 和01 是:001 有:000（5分） (2)其带权路径长度为131。（1分） 14. 栈是一种特殊的线性表，允许插入和删除运算的一端称为 栈顶 。不允许插入和删除运算的一端称为 栈底 。 15. 队列 是被限定为只能在表的一端举行插入运算，在表的另一端举行删除运算的线性表。 16. 对于一棵具有n个结点的二叉树，用二叉链表存储时，其指针总数为2n个，其中n-1个用于指向孩子，n+1个指针是空闲的。 17. 设有向图G中有向边的集合E=,，那么该图的一种拓扑序列为(1,4,2,3)。 18 由个结点所构成的二叉树有 5 种形态。 19一棵具有个结点的完全二叉
5、树，它的深度为 9 20设一棵完全二叉树有700个结点，那么共有 350 个叶子结点。 21在数据的存放无规律而言的线性表中举行检索的最正确方法是 依次查找（线 性查找） 。 22. 线性有序表（a1，a2，a3，a256)是从小到大排列的，对一个给定的值k，用二分法检索表中与k相等的元素，在查找不告成的处境下，最多需要检索 8 次。设有100个结点，用二分法查找时，最大对比次数是 7 。 23. 假设在有序线性表a20上举行折半查找，那么对比一次查找告成的结点数为1；对比两次查找告成的结点数为 2 ；对比四次查找告成的结点数为 8 ；平均查找长度为 3.7 。 24折半查找有序表（4，6，1
6、2，20，28，38，50，70，88，100），若查找表中元素20，它将依次与表中元素 28，6，12，20 对比大小。 25. 在各种查找方法中，平均查找长度与结点个数n无关的查找方法是 散列查 找 。 26. 散列法存储的根本思想是由 关键字的值 抉择数据的存储地址。 27.设一组初始记录关键字序列为(15,9,7,8,20,-1,6,4)，那么根据这些初始关键字序列建成的初始小顶堆为(-1,4,6,8,20,7,15,9)。 参考答案： 28. 下图是某一工程作业的网络图G的邻接表表示法，那么： （1）以结点V1启程深度遍历图G所得的结点序列为：(20)； （2）以结点V1启程广度遍历
7、图G所得的结点序列为：(21)； （3）从结点V1到结点V8的最短路径为：(22)，最短路径的长度为：(23)； （4）从结点V1到结点V8的关键路径为：(24)，关键路径的长度为：(25)天。 参考答案： （1）V1,V2,V3,V8,V5,V7,V4,V6； （2）V1,V2,V4,V6,V3,V5,V7,V8； （3）V1到V8最短路径为V1-V2-V5-V7-V8，长度为56； （4）V1到V8的关键路径是V1-V6-V5-V3-V8，长度为97。 （ B ）1. 非线性布局是数据元素之间存在一种： A）一对多关系 B）多对多关系 C）多对一关系 D） 一对一关系 （ C ）2. 数据
8、布局中，与所使用的计算机无关的是数据的 布局； A) 存储 B) 物理 C) 规律 D) 物理 和存储 （ C ）3. 算法分析的目的是： A) 找出数据布局的合理性 B) 研究算法中的输入和输出的 关系 C) 分析算法的效率以求提升 D) 分析算法的易懂性和文档性 （ A ）4. 算法分析的两个主要方面是： A) 空间繁杂性和时间繁杂性 B) 正确性和简明性 C) 可读性和文档性 D) 数据繁杂性和程序繁杂性 （ C ）5. 计算机算法指的是： A) 计算方法 B) 排序方法 C) 解决问题的有限运算序列 D) 调度方法 （ B ）6. 计算机算法务必具备输入、输出和 等5个特性。 A) 可
9、行性、可移植性和可扩展性 B) 可行性、确定性和有 穷性 C) 确定性、有穷性和稳定性 D) 易读性、稳定性和安 全性 （ B ）7.对一个算法的评价，不包括如下（ ）方面的内容。 A刚强性和可读性 B并行性 C正确性 D时空繁杂度 （ A ）8。数据布局是指（ ）。 A数据元素的组织形式 B数据类型 C数据存储布局 D数据定义 （ C ）9.在长度为n的依次表的第i个位置插入一个新元素的算法的时间繁杂度为（ ）(1next=p; Q.front=p; BQ.rear-next=p; Q.rear=p; Cp-next=Q.rear; Q.rear=p; D.p-next=Q.front;Q.
10、front=p; （ A ）20.数组A67的每个元素占五个字节，将其按列优先次序存储，若首元素A00的存储地址为1000，那么元素A55的存储地址为（ ）。 A1175 B1180 C1205 D1210 （ A ）21. 链接存储的存储布局所占存储空间： （A） 分两片面，一片面存放结点值，另一片面存放表示结点间关系的指针 （B） 只有一片面，存放结点值 (C） 只有一片面，存储表示结点间关系的指针 （D） 分两片面，一片面存放结点值，另一片面存放结点所占单元数 （ B ）22. 链表是一种采用 存储布局存储的线性表； （A）依次 （B）链式 （C）星式 （D）网状 （ D ）23. 线性表若采用链式存储布局时，要求内存中可用存储单元的地址: （A）务必是连续的 （B）片面地址务必是连续的 （C）确定是不连续的 （D）连续或不连续都可以 （ B ）24 线性表在 处境下适用于使用链式布局实现。 （）需经常修改中的结点值 （）需不断对举行删除插入 （）中含有大量的结点 （）中结点布局繁杂 （ B ）25.栈中元素的进出原那么是 先进先出 后进先出 栈空那么进 栈满那么出 （ C ）26. 8设一组初始记录关键字序列(5，2，6，3，8)，以第一个记录关键字5 为基准举行一趟快速排序的结果为（ ）。 (A) 2，3，5，8，6 (B) 3，2，5，8，6 8
