大学计算机第四章-练习题答案————————————————————————————————作者：————————————————————————————————日期：第四章练习题答案(1) 下面叙述正确的是______。

(C)A）算法的执行效率与数据的存储结构无关B）算法的空间复杂度是指算法程序中指令（或语句）的条数C）算法的有穷性是指算法必须能在执行有限个步骤之后终止D）以上三种描述都不对(2) 算法的时间复杂度是指______。

(C)A. 执行算法程序所需要的时间B. 算法程序的长度C. 算法执行过程中所需要的基本运算次数D. 算法程序中的指令条数(3) 算法的空间复杂度是指______。

(D)A. 算法程序的长度B. 算法程序中的指令条数C. 算法程序所占的存储空间D. 算法执行过程中所需要的存储空间(4) 下列叙述中正确的是______。

(B)A) 算法的效率只与问题的规模有关，而与数据的存储结构无关B) 算法的时间复杂度是指执行算法所需要的计算工作量C) 数据的逻辑结构与存储结构是一一对应的D) 算法的时间复杂度与空间复杂度一定相关(5）算法的有穷性是指______。

( A )A）算法程序的运行时间是有限的B）算法程序所处理的数据量是有限的C）算法程序的长度是有限的D）算法只能被有限的用户使用(6) 数据的存储结构是指______。

( B )A. 数据所占的存储空间量B. 数据的逻辑结构在计算机中的表示C. 数据在计算机中的顺序存储方式D. 存储在外存中的数据(7) 下面描述线性表的链式存储结构错误的是______。

(A)A）线性表顺序存储B）线性表随机存储C）线性表的链式存储结构也称为线性链表D）线性表的链式存储结构只能顺序存取(8）数据的存储结构是指______。

（ B）A.数据所占的存储空间量B.数据的逻辑结构在计算机中的表示C.数据在计算机中的顺序存储方式D.存储在外存中的数据(9) 下列叙述中正确的是______。

（D ）A）一个逻辑数据结构只能有一种存储结构B）数据的逻辑结构属于线性结构，存储结构属于非线性结构C）一个逻辑数据结构可以有多种存储结构，且各种存储结构不影响数据处理的效率D）一个逻辑数据结构可以有多种存储结构，且各种存储结构影响数据处理的效率(10）下列叙述中正确的是______。

（A）A) 线性链表是线性表的链式存储结构B) 栈与队列是非线性结构C) 双向链表是非线性结构D) 只有根结点的二叉树是线性结构(11) 数据结构中，与所使用的计算机无关的是数据的______。

（ c ）。

A．存储结构 B．物理结构C．逻辑结构 D．物理和存储结构(12) 下列叙述中正确的是______。

(A)A. 线性表是线性结构B. 栈与队列是非线性结构C. 线性链表是非线性结构D. 二叉树是线性结构(13) 链表不具有的特点是（ A ）。

A．可随机访问任一元素 B．插入和删除不需要移动元素C．不必事先估计存储空间 D．所需空间与线性表长度成正比(14)下列关于队列的叙述中正确的是______。

(C)A. 在队列中只能插入数据B. 在队列中只能删除数据C. 队列是先进先出的线性表D. 队列是先进后出的线性表(15) 用链表表示线性表的优点是______。

(A)A. 便于插入和删除操作B. 数据元素的物理顺序与逻辑顺序相同C. 花费的存储空间较顺序存储少D. 便于随机存取(16) 按照”后进先出”原则组织数据的数据结构是______。

（ B ）A)队列B)栈C)双向链表D)二叉树(17) 以下数据结构中不属于线性数据结构的是______。

(C)A. 队列B. 线性表C. 二叉树D. 栈(18)下列关于栈的描述中错误的是______。

（B）A) 栈是先进后出的线性表B) 栈必须链式存储C) 栈具有记忆作用D) 对栈的插入与删除操作中，不需要改变栈底指针(19）下列关于栈的描述正确的是______。

（C）A）在栈中只能插入元素而不能删除元素B）在栈中只能删除元素而不能插入元素C）栈是特殊的线性表，只能在一端插入或删除元素D）栈是特殊的线性表，只能在一端插入元素，而在另一端删除元素（20）下列关于栈的叙述正确的是 ______。

（ B）A）栈按“先进先出”组织数据B) 栈按“先进后出”组织数据C）只能在栈底插入数据D）不能删除数据(21) 下列叙述中正确的是______。

（ D）A）栈是“先进先出”的线性表B）队列是“先进后出”的线性表C）循环队列是非线性结构D）有序线性表既可以采用顺序存储结构，也可以采用链式存储结构(22) 下列对列的叙述正确的是______。

( D )A) 队列属于非线性表B) 队列按“先进后出”原则组织数据C) 队列在队尾删除数据D) 队列按“先进先出”原则组织数据(23) 一个栈的初始状态为空。

现将元素1、2、3、4、5、A、B、C、D、E 依次入栈，然后再依次出栈，则元素出栈的顺序是______。

BA）123456ABCDE B）EDCBA54321C）ABCDE12345 D）54321EDCBA(24) 按“先进后出”原则组织数据的结构是______。

（ B ）。

A．有序表 B．栈 C．队列 D．二叉树(25) 栈底至栈顶依次存放元素A、B、C、D，在第五个元素E入栈前，栈中元素可以出栈，则出栈序列可能是______。

(D)A. ABCEDB. DBCEAC. CDABED. DCBEA(26) 若进栈序列为1，2，3，4，则（ C ）不可能是出栈序列。

A．1，2，3，4 B．4，3，2，1C．3，4，1，2 D．2，4，3，1(27）某二叉树有5个度为2的结点，则该二叉树中的叶子结点数是______。

（C ）A）10 B）8C）6 D）4(28）一棵二叉树中共有70个叶子结点与80个度为1的结点，则该二叉树中的总结点数为______。

（A ）A）219 B）221 C）229 D）231(29) 在深度为7的满二叉树中,叶子结点的个数为______。

（ C ）A)32 B)31 C)64 D)63(30) 在深度为5的满二叉树中，叶子结点的个数为______。

(C)A. 32B. 31C. 16D. 15(31) 某二叉树中有n个度为2的结点，则该二叉树中的叶子结点为______。

（A ）A) n+1 B) n-1 C) 2n D) n/2(32) 设一棵完全二叉树共有699个结点，则在该二叉树中的叶子结点数为______。

(B)A. 349B. 350C. 255D. 351(33）对如下二叉树进行后序遍历的结果为______。

（ D）A) ABCDEF B) DBEFCA C) DEBCFA D) DEBFCA(34) 对下列二叉树进行前序遍历的结果______B_____。

A. DBEGACFB. ABDEGCFC. DGEBFCAD. DEGBFCA（35）对下列二叉树：进行中序遍历的结果是___A___。

A ）、ACBDFEGB ）、ACBDFGEC ）、ABDCGEFD ）、FCADBEG(36) 对下列二叉树进行后序遍历的结果____C_______。

A. ABCDEFGB. DBEGACFC. DGEBFCAD. DEGBFCA*(37) 已知二叉树后序遍历序列是dabec ，中序遍历序列是debac ，它的前序遍历序列是______。

（ A ）。

A ．cedbaB ． acbedC ． decabD ．cdeab(38) 对于长度为n 的线性表进行顺序查找，在最坏情况下所需要的比较次数为______。

（C ）A) log2n B) n/2 C) n D) n+1(39）下列数据结构中，能用二分法进行查找的是______。

（A ）A ）顺序存储的有序线性表B ）线性链表C ）二叉链表D ）有序线性链表FCE AG B D ABC DF G E ABC DF G E(40) 在长为64的有序线性表中进行顺序查找，最坏情况下需要比较的次数为______。

__B____。

A）、63 B）、64 C）、6 D）、7二、填空题(1) 算法的复杂度主要包括______复杂度和空间复杂度。

答：时间(2) 数据结构包括数据的逻辑结构、数据的 ______以及对数据的操作运算。

答：存储结构(3) 顺序存储方法是把逻辑上相邻的结点存储在物理位置______的存储单元中。

答：相邻(4) 栈的基本运算有三种：_______、退栈和读栈顶元素。

答：入栈(5) 在深度为5的完全二叉树中，度为2的结点数最多为______个。

【15】(6) 某二叉树中度为2的结点有18个，则该二叉树中有______个叶子结点。

（19）(7）一棵二叉树第六层（根结点为第一层）的结点数最多为 ______个。

（ 32 ）(8）在深度为7的满二叉树中，度为2的结点个数为______63___。

(9) 在深度为7的满二叉树中,叶子结点的个数为（64）。

(10）深度为5的满二叉树有【】个叶子结点。

答：16(11) 设一棵二叉树中有3个叶子结点，有6个度为1的结点，则该二叉树中总的结点数为_________个。

【11】(12) 设一棵完全二叉树共有500个结点，则在该二叉树中有______个叶子结点。

答：250(13) 在最坏情况下，冒泡排序所需要的比较次数为（）。

n(n-1)/2(14) 对于线性表( 5 , 8 , 3 , 2 , 7 , 1 )，冒泡排序第一趟扫描的结果为_________；答：( 5 , 3 , 2 , 7 , 1 , 8 )(15) 对于线性表( 12 , 8 , 9 , 17 , 5 , 3 )，冒泡排序第一趟扫描的结果为_________；答：( 8 , 9 , 12 , 5 , 3 ,17 )(16）当线性表为无序表，则无论其采用顺序存储结构或链式存储结构，均可采用顺序查找；顺序查找的比较次数最少_________次。

( 1 )(17) 当线性表为无序表，则无论其采用顺序存储结构或链式存储结构，均可采用顺序查找；顺序查找的比较次数最多_________次。

( n )(18) 在长度为N的线性表中进行二分查找，在最快的情况下，需要比较的次数为______。

【1】。

(19) 在长度为n的有序线性表中进行二分查找，最多比较次数为________。

LOG2(N +1) (20）对于长度为n的线性表，冒泡排序最多需要对表扫描_____遍；(n-1)(21) 选择排序的算法第一步，扫描整个线性表，从中找出最小的元素，与__________元素交换； (第一个)(22) 对于线性表( 5, 8 , 3 , 2 , 7 , 1 )，选择排序最多需要对表扫描_________遍答：( 5 )(23) 对于线性表( 5 , 8 , 3 , 2 , 7 , 1 )，选择排序第一趟扫描的结果为_________；答：( 1 , 8 , 3 , 2 , 7 , 5 )(24) 设一棵二叉树的中序遍历结果为DBEAFC ，前序遍历结果为ABDECF ，则后序遍历结果为___DEBFCA_____。