《计算机导论-第四章-算法与数据结构期末测试习题与答案.docx》由会员分享，可在线阅读，更多相关《计算机导论-第四章-算法与数据结构期末测试习题与答案.docx（5页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
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.在栈中只能删除数据D.在栈中只能插入数据正确答案：B9、对
3、长度为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、已知二叉树后序编历序列是dabec，中续遍历序列是debac，不是其前序编历序列是（ ）。A.acb
4、edB.cedbaC.deabcD.ceabd正确答案：A、C、D3、关于查找，说法正确的是（ ）。A.衡量查找算法性能时，平均比较次数是一个非常关键的指标。B.在链式存储中，也可以使用二分查找。C.采用索引表查找时，需要为查找表建立索引表，且索引表中关键字有序。D.顺序查找又称顺序搜索。一般是在线性表中查找指定的元素。正确答案：A、C、D4、关于二叉树，说法正确的是（ ）。A.二叉树是树型结构的特例B.二叉树及可以采用顺序存储，也可以采用链式存储C. 对任意一棵二叉树T，若叶子结点数为n0，度数为2的结点数为n2，则n0=n2+1D.二叉树是一种非线性结构正确答案：B、C、D三、判断题1、数
5、据结构包括三个方面的内容：数据的逻辑结构、数据的存储结构和数据的运算。（对）2、同一种逻辑结构可以采用不同的存储结构。（对）3、常见的存储结构有4种，分别是顺序存储结构、链式存储结构、索引存储结构和散列存储结构。（对）4、线性表、栈和队列中，元素的关系都是线性关系。（对）5、可以将栈理解为是操作位置受限的线性表，仅能在一端插入，在另一端删除。（错）6、冒泡排序法和快速排序法都属于交换类的排序方法。（对）7、树的后序遍历序列等同于该树对应的二叉树的中序遍历序列。（对）8、在深度为5的满二叉树中，叶子结点的个数为15。（错）9、树是节点的集合，根节点数目是有且只有1 个。（错）10、通过哈夫曼树可以求取哈夫曼编码。（对）四、填空题1、（ ）是指解决问题的方法，而程序是该方法具体的实现。 正确答案：算法2、顺序存储方法是把逻辑上相邻的节点存储在物理位置（ ）的存储单元中。正确答案：连续 3、数据的逻辑结构有线性和（ ）两大类。正确答案：非线性 4、在算法正确的前提下，评价一个算法的两个标准是时间复杂度和（ ）。正确答案：空间复杂度5、数据结构分为逻辑结构与存储结构，线性链表属于（ ）。正确答案：存储结构 6、设一棵完全二叉树共有40个结点，则在该二叉树中有（ ）个叶子结点。正确答案：20专心-专注-专业