计算机公共基础习题

第一章数据结构和算法（习题)1.1算法一、选择1、下列叙述中正确的是（C)A、算法的执行效率与数据的存储结构无关B、算法的空间复杂度是指执行算法程序中指令（或语句)的条数C、算法的有穷性是指算法必须能执行有限个步骤之后终止D、以上3种描述都不对2、下列叙述中正确的是（A）A)、程序执行的效率与数据的存储结构密切相关B、程序执行的效率只取决于程序的控制结构C、程序执行的效率只取决于所处理的数据量D、以上3种说法都不对3、下列关于算法的时间复杂度陈述正确的是（C）A、算法时间复杂度是指执行算法程序所需要的时间B、算法的时间复杂度是指算法程序的长度C、算法的时间复杂度是指算法程序执行过程中所需要的基本运算次数D、算法的时间复杂度是指算法程序中的指令条数4、算法的时间复杂度是指(C）A、执行算法程序所需要的时间B、算法程序的长度C、算法执行过程中所需要的基本运算次数D、算法程序中的指令条数.5、算法的空间复杂度是指（D）A、算法程序的长度B、算法程序中的指令条数C、算法程序所占的存储空间D、算法执行过程中所需要的存储空间6、以下叙述正确的是（D）A、算法空间复杂度是指算法程序的长度B、算法的效率只与所处理数据的规模有关，而于数据的存储结构无关C、数据的逻辑结构与存储结构是一一对应的D、上述三种说法都不对.7、算法分析的目的是（D）A)找出数据结构的合理性B)找出算法中输入和输出之间的关系C)分析算法的易懂性和可靠性D)分析算法的效率以求改进8、下列叙述中正确的是（D）________.A)一个算法的空间复杂度大，则其时间复杂度也必定大B)一个算法的空间复杂度大，则其时间复杂度必定小C)一个算法的时间复杂度大，则其空间可复杂度必定小9、在计算机中，算法是指（D）A)加工方法B)用解题方案准确而完整的描述.C)排序方法D)查询方法10、在下列选项中，哪个不是一个算法一般应该具有的基本特征_C_____.A.确定性B.可行性C.无穷性D.拥有足够的情报11、下列叙述正确的是（B）A)算法的效率只与问题的规模有关，而与数据的存储结构无关B)算法的时间复杂度是指执行算法所需要的工作量C)数据的逻辑结构与存储结构是一一对应的D)算法的时间复杂度和空间复杂度一定相关12、算法一般都可以用哪几种控制结构组合而成_D_____.A.循环、分支、递归B.顺序、循环、嵌套C.循环、递归、选择D.顺序、选择、循环二、填空1、算法的复杂度主要包括_时间_复杂度和空间复杂度.2、算法执行过程中所需要的存储空间称为算法_空间复杂度_3、问题处理方案的正确而完整的描述称为为_算法_.4、算法基本特征是可行性，确定性，__有穷性___和拥有足够的情报.5、在算法正确的前提下，评价一个算法的两个标准是__时间复杂度和空间复杂度.1.2数据结构一、选择1、以下数据结构中不属于线性数据结构的是（C）A、队列B、线性表C、二叉树D、栈2、数据的存储结构是指（D）A、存储在外存中的数据B、数据所占的存储空间C、数据在计算机中的顺序存储方式D、数据结构在计算机中的表示3、下列叙述中正确的是（D）A、一个逻辑数据结构只能有一种存储结构B、数据的逻辑结构属于线性结构，存储结构属于非线性结构C、一个逻辑结构可以有多种存储结构，且各种存储结构不影响数据处理的效率D、一个逻辑数据结构可有多种存储结构，且各种存储结构影响数据处理的效率.4、下列叙述中正确的是（A）A、线性链表是线性表的链式存储结构B、栈和队列是非线性结构C、双向链表是非线性结构D、只有一个根结点的二叉树是线性结构5、以下数据结构中不属于线性数据结构的是（C）A、队列B、线性表C、二叉树D、栈6、数据结构分为（D）A、表、队列、栈和树B、逻辑结构C、存储结构D、逻辑结构和存储结构7、数据结构是指反映数据元素之间关系的数据元素集合的表示，在下面的选项中，包含了数据结构信息的选项是（B）A、表示各数据元素之间的大小关系B、表示各数据元素之间的前后件关系C、表示各数据元素之间的相容关系D、表示各数据元素之间的排斥关系8、下面是对空的数据结构的描述，期中描述正确的是（C）A、一个空的数据结构只能是线性结构B、一个空的数据结构只能是非线性结构C、线性结构和非线性结构都可以是空的数据结构D、以上3个叙述都不对.9、数据结构中，与所使用的计算机无关的是数据的（C）A)存储结构B)物理结构C)逻辑结构D)物理和存储结构10、数据结构作为计算机的一门学科，主要研究数据的逻辑结构，对各种数据结构进行的运算以及（A）A)数据的存储结构B)计算方法C)数据映象D)逻辑存储11、下列叙述中正确的是____A__.A.线性表是线性结构B.栈与队列是非线性结构C.线性链表是非线性结构D.二叉树是线性结构12、数据的存储结构是指___B___.A.数据所占的存储空间量B.数据的逻辑结构在计算机中的表示C.数据在计算机中的顺序存储方式D.存储在外存中的数据13、下列叙述中正确的是(D)A)数据的逻辑结构与存储结构必定是一一对应的B)由于计算机存储空间是向量式存储结构.因此，数据的存储结构必定是线性结构C)程序设计语言中的数组一般是顺序存储结构，因此,利用数组只能处理线性结构D)以上3种说法都不对二、填空1、数据的逻辑结构在计算机存储空间中的存放方式称为数据的_存储结构_.2、按照逻辑结构分类，数据结构分为线性结构和非线性结构.二叉树属于非线性__.3、数据逻辑结构有线性结构和__非线性___两大类.4、数据结构分为线性结构和非线性结构，带链的队列属于__线性结构1.3顺序表和线性链表一、选择1、下列关于线性链表的描述正确的是（A)A、存储空间不一定连续，且各元素的存储顺序是任意的B、存储空间不一定是连续的，且前件元素一定存储在后件元素前面C、存储空间必须连续，且前件元素一定存储在后件元素的前面D、存储空间必须是连续的，且各元素的存储顺序是任意的2、链表不具有得特点是（B)A)不必事先估计存储空间B)可随机访问任意元素所需空间与线性表长度成正比C)插入删除元素不需要移动元素D)3、用链表表示线性表的优点是（C)A)便于随机存储B)花费的存储空间较顺序存储少C)便于插入和删除操作D)数据元素的物理顺序和逻辑顺序相同4、线性表L=(A1,A2,A3,……AI,…AN),下列说法正确的是（D)A)每个元素都有一个直接前件和直接后件B)线性表至少要有一个元素C)表中诸元素的排列顺序必须是由小到大或由大到小D)除了第一元素和最后一个元素，其余每个元素都有一个且只有一个直接前件和直接后件.5、在单链表中，增加头节点的目的是（A)A)方便运算的实现B)使单练表至少有一个节点C)标识表节点中首节点的位置D)说明单练表是线性表达额链式存储实现.6、采用链接方式存储线性表的优点是C)A)便于随机读取B)花费的存储空间较顺序存储少C)便于插入和删除操作D)数据元素的物理顺序和逻辑顺序相同7、与单链表相比，双向链表的优点之一是（D)A)插入，删除更加方便B)可以随机访问C)可以省略表头指针或表尾指针D)顺序访问相邻结点更加灵活.8、对线性表，应该采用链表表示的下列情况的是(B)A)经常需要随机地读取数据B)经常需要进行插入和删除操作C)表中元素的个数不变D)表中元素需要占据一片连续的存储空间9、线性表的顺序存储和线性表的链式存储分别是(B)A)顺序存取的存储结构、顺序存取的存储结构B)随机存取的存储结构、顺序存取的存储结构C)随机存取的存储结构、随机存取的存储结构D)任意存取的存储结构、任意存取的存储结构10、循环链表的主要优点是(B)A)不再需要头指针了.B)从表中任一结点出发都能访问整个链表C)在进行插入、删除运算时，能更好的保证链表不断开.D)已知某个结点位置之后，能够容易的找到它的直接前件.二、填空1、顺序存储方法是把逻辑上相邻的节点存储在物理位置___相邻_____的存储单元中.2、长度为n的顺序存储线性表中，当在任何位置上插入一个元素的概率相等时，插入一个元素所需要移动元素的平均个数为____n/2_______.3、数据结构分为逻辑结构和存储结构，循环队列属于__存储______结构.1.4栈和队列一、选择1、下列关于栈叙述正确的是(D)A、在栈中只能插入数据B、在栈中只能删除数据C、栈是先进先出的线性表D、对栈的插入和删除操作中，不需要改变栈底的指针2、下列关于栈的描述错误的是(B)A、栈是先进后出的线性表B、栈只能顺序存储C、栈具有记忆作用D、对栈的插入和删除操作中，不需要改变栈底指针.3、下列关于栈的描述正确的是(C)A在栈中只能插入元素而不能删除元素B、在栈中只能删除元素而不能插入元素C、栈是特殊的线性表，只能在一端插入或删除元素D、栈是特殊的线性表，只能在一段插入元素，而在另一端删除元素4、按照先进后出原则组织数据的是（B)A、队列B、栈C、双向链表D、二叉树5、下列数据结构中，插入时不需要移动其他元素的是(C)A、有序线性表B、无序线性表C、栈和队列D、以上都不是6、设栈S的初始状态为空，元素a,b,c,d,e,f依次通过栈S，若出栈的顺序是b,d,c,f,e,a则栈的容量至少应该为(A)A、3B、4C、5D、67、栈和队列的共同特点是(C)A)都是先进先出B)都是先进后出C)只允许在端点处插入和删除元素D)没有共同点8、一些重要的程序语言（如c语言和pascal语言)允许过程的递归调用.而实现递归中的存储分配方式通常用(A)A)栈B)堆C)数组D)链表9、栈通常采用的两种存储结构是(A)A)顺序存储结构和链式存储结构B)散列方式和索引方式C)链表存储和数组D)线性存储和非线性存储10、栈底至栈顶依次存放元素A、B、C、D,在第五个元素E入栈之前，栈中元素可以出栈则出栈的序列可能是(B)A)ABCEDB)DCBEAC)DBCEAD)CDABE11、下列关于队列的叙述中正确的是___C___.A.在队列中只能插入数据B.在队列中只能删除数据C.队列是先进先出的线性表D.队列是先进后出的线性表12、如果进栈序列为e1,e2,e3,e4则可能的出栈序列是(B)A)e3,e1,e4,e2B)e2,e4,e3,e1C)e3,e4,e1,e2D)任意顺序二、填空1、在一个容量为15的循环队列中，若头指针为front=6,尾指针rear=9,则该循环队列中共有___3____个元素.2、当循环队列非空且队尾指针等于队头指针时，说明循环队列已满，不能进入入队运算，这种情况称为___上溢________.1.5树和二叉树一、选择1、设树T的度为4，其中度为1，2，3，4的结点个数分别为4，2，1，1.则叶子结点数为()A、8B、7C、6D、52、树是结点的集合，它的根结点数目是（）A)有且只有1个B)1或多于1个C)0或1D)至少23、在一棵二叉树上第5层的结点数最多的是（）A、8B、16C、32D、154、一棵二叉树共有70个叶子结点与80个度为1的结点，则该二叉树中总的结点个数为A、221B、219C、231D、2295、具有3个结点的二叉树有（）A)2种形态B)4种形态C)7种形态D)5种形态6、下列关于二叉树的说法正确的是（）A)一棵二叉树中任何一个结点要么是叶子结点，要么恰有两个子树B)二叉树中的结点个数大于0C)一棵二叉树中叶子结点的个数等于度为2的结点个数加1D)二叉树中任何一个结点的左子树和右子树上的结点个数一定相等7、深度为5的二叉树至多有（）个结点.A)16B)32C)31D)108、在深度为7的满二叉树中，叶子结点的个数为（）A、32B、31C、64D、639、在一棵深度为K的完全二叉树中，所含结点个数不少于()A)2KB)2K+1C)2K-1D)2K-110、在一棵具有35个结点的完全二叉树中，该树的深度是（）A)5B)6C)7D)811、设一棵完全二叉树共有699个结点，则在该二叉树中的叶子结点数为______.A.349B.350C.255D.351二、填空1、某二叉树中度为2的结点有18个，则该二叉树中有_____19_个叶子结点