1、下列叙述中正确的是
A:一个算法的空间复杂度大,则其时间复杂度也必定大
B:一个算法的空间复杂度大,则其时间复杂度必定小
C:一个算法的时间复杂度大,则其空间复杂度必定小
D:算法的时间复杂度与空间复杂度没有直接关系
答案:D
解析:算法的空间复杂度是指算法在执行过程中所需要的内存空间,算法的时间复杂度,是指执行算法所需要的计算工作量,两者之间并没有直接关系,答案为A
2、下列叙述中正确的是
A:算法的效率只与问题的规模有关,而与数据的存储结构无关
B:算法的时间复杂度是指执行算法所需要的计算工作量
C:数据的逻辑结构与存储结构是一一对应的
D:算法的时间复杂度与空间复杂度一定相关
答案:B
解析:算法的效率与问题的规模和数据的存储结构都有关,A错误
算法的时间复杂度,是指执行算法所需要的计算工作量,B正确
由于数据元素在计算机存储空间中的位置关系可能与逻辑关系不同,因此数据的逻辑结构和存储结构不是一一对应的,C错误。
算法的时间复杂度和空间复杂度没有直接的联系,D错误
3、下列叙述中正确的是
A:程序执行的效率与数据的存储结构密切相关
B:程序执行的效率只取决于程序的控制结构
C:程序执行的效率只取决于所处理的数据量
D:以上说法均错误
答案:A
解析:程序执行的效率与数据的存储结构、数据的逻辑结构、程序的控制结构、所处理的数据量等有关
4、下列关于栈的叙述中,正确的是
A:栈底元素一定是最后入栈的元素
B:栈顶元素一定是最先入栈的元素
C:栈操作遵循先进后出的原则
D:以上说法均错误
答案:C
解析:栈顶元素总是后被插入的元素,从而也是最先被删除的元素'栈底元素总是最先被插入的元素,从而也是最后才能被删除的元素栈的修改是按后进先出的原则进行的因此,栈称为先进后出表,或( 后进先出) 表,所以选择C
5、一个栈的初始状态为空。现将元素1,2,3,A,B,C依次入栈,然后再依次出栈,则元素出栈的顺序是
A:1,2,3,A,B,C
B:C,B,A,1,2,3
C:C,B,A,3,2,1
D:1,2,3,C,B,A
答案:C
解析:栈的修改是按后进先出的原则进行的,所以顺序应与入栈顺序相反,故选C
6、下列与队列结构有关联的是
A:函数的递归调用
B:数组元素的引用
C:多重循环的执行
D:先到先服务的作业调度
答案:D
解析:队列的修改是依先进先出的原则进行的,D正确
7、下列叙述中正确的是
A:循环队列中的元素个数随队头指针与队尾指针的变化而动态变化
B:循环队列中的元素个数随队头指针的变化而动态变化
C:循环队列中的元素个数随队尾指针的变化而动态变化
D:以上说法都不对
答案:A
解析:在循环队列中,用队尾指针rear指向队列中的队尾元素,用排头指针front指向排头元素的前一个位置。因此,从排头指针front指向的后一个位置直到队尾指针rear指向的位置之间所有的元素均为队列中的元素所以循环队列中的元素个数与队头指针和队尾指针的变化而变化,A正确
8、设循环队列的存储空间为Q(1:35),初始状态为front=rear=35。现经过一系列入队与退队运算后,front=15,rear=15,则循环队列中的元素个数为
A:15
B:16
C:20
D:0 或35
答案:D
解析:在循环队列中,用队尾指针rear指向队列中的队尾元素,用排头指针front指向排头元素的前一个位置。在循环队列中进行出队、入队操作时,头尾指针仍要加1,朝前移动。只不过当头尾指针指向向量上界时,其加1操作的结果是指向向量的下界0。由于入队时尾指针向前追赶头指针,出队时头指针向前追赶尾指针,故队空和队满时,头尾指针均相等。答案为D选项
9、下列叙述中正确的是
A:线性表链式存储结构的存储空间一般要少于顺序存储结构
B:线性表链式存储结构与顺序存储结构的存储空间都是连续的
C:线性表链式存储结构的存储空间可以是连续的,也可以是不连续的
D:以上说法均错误
答案:C
解析:线性表的顺序存储结构具备如下两个基本特征:1.线性表中的所有元素所占的存储空间是连续的2.线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。用一组任意的存储单元来依次存放线性表的结点,这组存储单元既可以是连续的,也可以是不连续的,甚至是零散分布在内存中的任意位置上的。因此C正确
10、下列链表中,其逻辑结构属于非线性结构的是
A:二叉链表
B:循环链表
C:双向链表
D:带链的栈
答案:A
解析:在定义的链表中,若只含有一个指针域来存放下一个元素地址,称这样的链表为单链表或线性链表带链的栈可以用来收集计算机存储空间中所有空闲的存储结点,是线性表在单链表中的结点中增加一个指针域指向它的直接前件,这样的链表,就称为双向链表(一个结点中含有两个指针",也是线性链表循环链表具有单链表的特征,但又不需要增加额外的存贮空间,仅对表的链接方式稍做改变,使得对表的处理更加方便灵活,属于线性链表二叉链表是二叉树的物理实现,是一种存储结构,不属于线性结构答案为A选项
11、一棵二叉树中共有80个叶子结点与70个度为1的结点,则该二叉树中的总结点数为
A:219
B:229
C:230
D:231
答案:B
解析:二叉树中,度为0的节点数等于度为2的节点数加1,即n2=n0-1,叶子节点即度为0,则n2=79,总结点数为n0+n1+n2=80+70+79=229,答案为B
12、某二叉树共有12个结点,其中叶子结点只有1个则该二叉树的深度为(根结点在第1层)
A:3
B:6
C:8
D:12
答案:D
解析:二叉树中,度为0的节点数等于度为2的节点数加1,即n2=n0-1,叶子节点即度为0,n0=1,则n2=0,总节点数为12=n0+n1+n2=1+n1+0.,则度为1的节点数n1=11,故深度为12,选D
13、对下列二叉树进行前序遍历的结果为
A:DYBEAFCZX
B:YDEBFZXCA
C:ABDYECFXZ
D:ABCDEFXYZ
答案:C
解析:前序遍历是指在访问根结点、遍历左子树与遍历右子树这三者中,首先访问根结点,然后遍历左子树,最后遍历右子树'并且,在遍历左右子树时,仍然先访问根结点,然后遍历左子树,最后遍历右子树前序遍历描述为:若二叉树为空,则执行空操作否则:1.访问根结点2.前序遍历左子树3.前序遍历右子树,C正确
14、对长度为10的线性表进行冒泡排序,最坏情况下需要比较的次数为
A:9
B:10.
C:45
D:90
答案:C
解析:冒泡法是在扫描过程中逐次比较相邻两个元素的大小,最坏的情况是每次比较都要将相邻的两个元素互换,需要互换的次数为9+8+7+6+5+4+3+2+1=45,选C
15、对长度为n的线性表作快速排序,在最坏情况下,比较次数为
A:n
B:n-1
C:n(n-1)
D:n(n-1)/2
答案:D
解析:快速排序最坏情况就是每次选的基准数都和其他数做过比较,共需比较(n-1)+(n-2)+…+1=n(n-1)/2,选D
免责声明:以上内容源自网络,版权归原作者所有,如有侵犯您的原创版权请告知,我们将尽快删除相关内容。