计算机导论第四章算法与数据结构期末测试习题与答案

1、、选择题1、算法的时间复杂度是指（ ）。A. 算法执行过程中所需要的基本运算次数B. 执行算法程序所需要的时间C. 算法程序的长度D. 算法程序中的指令条数正确答案： A2、 算法的空间复杂度是指（）。A. 算法程序的长度B. 算法程序所占的存储空间C. 算法执行过程中所需要的存储空间D. 算法程序中的指令条数正确答案： C3、 线性表采用链式存储的优点是（）A. 花费的存储空间较顺序储存少B. 数据元素的物理顺序与逻辑顺序相同C. 便于随机存取D .便于插入和删除操作正确答案： D4、 下列叙述中正确的是（）。A. 二叉树是线性结构B. 线性链表是非线性结构C. 线性表是线性结构D .栈与队

2、列是非线性结构正确答案： C5、数据结构中，与所使用的计算机无关的是数据的（ ）A. 逻辑结构B. 物理结构C. 物理和存储结构D. 存储结构正确答案： A6、 存储结构是指（）。A. 逻辑结构在计算机中的表示B. 数据所占的存储空间量C. 存储在外存中的数据D. 数据在计算机中的顺序存储方式正确答案： A7、 下列关于队列的叙述中，正确的是（）。A. 队列是先进后出B. 队列是先进先出C. 在队列中只能插入数据D. 在队列中只能删除数据正确答案： B8、 下列关于栈的叙述中，正确的是（）。A. 栈只能采用顺序存储B. 栈可以采用链式存储，采用链式存储时不会产生栈溢出现象。C. 在栈中只能删除

3、数据D.在栈中只能插入数据正确答案： B 9 、对长度为 n 的线性表进行顺序查找，查找成功时，最坏情况下所需要的比较次数为 （ ）。A. n/2B. （n+1）/2C. n+lD. n正确答案： D10 、下列叙述中，正确的是（ ）。A. 以上三种说法都不对B. 算法就是程序C. 设计算法时只需要考虑结果的可靠性D. 设计算法时只需要考虑数据结构的设计正确答案： A二、多选题1、如果进栈的顺序为 e1,e2,e3,e4 ，则可能的出栈序列是（ ）。A. e3,e1,e4,e2B. e4,e3,e2,e1C. e1,e2,e3,e4D. e2,e4,e3,e1正确答案： B、C、D2、 已知二

4、叉树后序编历序列是dabec,中续遍历序列是 debac,不是其前序编历序列 是（ ）。A. acbedB. cedbaC. deabcD. ceabd正确答案： A、 C、D3、关于查找，说法正确的是（）。A. 衡量查找算法性能时，平均比较次数是一个非常关键的指标。B. 在链式存储中，也可以使用二分查找。C. 采用索引表查找时，需要为查找表建立索引表，且索引表中关键字有序。D. 顺序查找又称顺序搜索。一般是在线性表中查找指定的元素。正确答案： A、 C、D4、关于二叉树，说法正确的是（）。A. 二叉树是树型结构的特例B. 二叉树及可以采用顺序存储，也可以采用链式存储C. 对任意一棵二叉树 T

5、,若叶子结点数为n0 ,度数为2的结点数为n2 ,则nO=n2+1D. 二叉树是一种非线性结构正确答案： B、C、D三、判断题1 、数据结构包括三个方面的内容：数据的逻辑结构、数据的存储结构和数据的运算。 （对）2、同一种逻辑结构可以采用不同的存储结构。（对）3、常见的存储结构有 4 种，分别是顺序存储结构、链式存储结构、索引存储结构和散 列存储结构。（对）4、线性表、栈和队列中，元素的关系都是线性关系。（对）5、可以将栈理解为是操作位置受限的线性表，仅能在一端插入，在另一端删除。（错）6、冒泡排序法和快速排序法都属于交换类的排序方法。（对）7、树的后序遍历序列等同于该树对应的二叉树的中序遍历序列。（对）8、 在深度为 5 的满二叉树中，叶子结点的个数为15。（错） 9、树是节点的集合，根节点数目是有且只有 1 个。（错）10 、通过哈夫曼树可以求取哈夫曼编码。（对） 四、填空题1、（）是指解决问题的方法，而程序是该方法具体的实现。正确答案：算法2、顺序存储方法是把逻辑上相邻的节点存储在物理位置（ 正确答案：连续3、数据的逻辑结构有线性和（）两大类。正确答案：非线性4、在算法正确的前提下，评价一个算法的两个标准是时间复杂度和 正确答案：