2017年9月计算机二级C语言章节练习题及答案(2).doc

1.2 算法 　　1[填空题] 　　一颗二叉树的中序遍历结果为DBEAFC，前序遍历结果为ABDECF，则后序遍历结果为 【2】 。 　　参考解析：【2】DEBFCA 　　【解析】根据二叉树的中序遍历原则可知D为二叉树的最左边的叶子结点，根据二叉树的前序遍历原则可知A是二叉树的根结点，就可以确定二叉树的结构，所以二叉树的后序遍历结果为：DEBFCA。 　　2[填空题] 　　队列是限定在表的一端进行插入和在另一端进行删除操作的线性表。允许删除的一端称作__________。 　　参考解析：队头 　　【解析】队列是只允许在一端删除，在另一端插入的顺序表，在队列中。允许插入的一端叫做“队尾”，允许删除的一端叫做“队头”。 　　3[填空题] 　　在最坏情况下，堆排序需要比较的次数为_________。 　　参考解析：O(nlog2n) 　　【解析】在最坏情况下，冒泡排序所需要的比较次数为n(n-1)/2;简单插入排序所需要的比较次数为n(n-1)/2;希尔排序所需要的比较次数为O(n1.5);堆排序所需要的比较次数为O(nlog2n)。 　　4[单选题] 算法的有穷性是指(　　)。 　　A.算法程序的运行时间是有限的 　　B.算法程序所处理的数据量是有限的 　　C.算法程序的长度是有限的 　　D.算法只能被有限的用户使用 　　参考答案：A 　　参考解析：算法具有5个特性：①有穷性：一个算法必须(对任何合法的输入值)在执行有穷步之后结束，且每一步都可在有限时间内完成，即运行时间是有限的;②确定性：算法中每一条指令必须有确切的含义，读者理解时不会产生歧义。③可行性：一个算法是可行的，即算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现。，④输入：一个算法有零个或多个输入，这些输入取自于某个特定的对象的集合。⑤输出：一个算法有一个或多个输出。 　　5[单选题] 下列叙述中正确的是(　　)。 　　A.数据的逻辑结构与存储结构是一一对应的 　　B.算法的时间复杂度与空间复杂度一定相关 　　C.算法的效率只与问题的规模有关，而与数据的存储结构无关 　　D.算法的时间复杂度是指执行算法所需要的计算工作量 　　参考答案：D 　　参考解析：根据时间复杂度和空间复杂度的定义可知，算法的时间复杂度与空间复杂度并不相关。数据的逻辑结构就是数据元素之间的逻辑关系，它是从逻辑上描述数据元素之间关系的，是独立于计算机的;数据的存储结构是研究数据元素和数据元素之间的关系如何在计算机中表示的，它们并非一一对应。算法的执行效率不仅与问题的规模有关，还与数据的存储结构有关。 　　6[单选题] 有三个关系R、S和T如下： 　　则由关系R和S得到关系T的操作是(　　)。 　　A.自然连接 　　B.并 　　C.差 　　D.交 　　参考答案：C 　　参考解析：R和S的差是由属于R但不属于S的元组组成的集合，运算符为“-”。记为T=R-S。根据本题关系R和关系S运算前后的变化，可以看出此处进行的是关系运算的差运算。 　　7[单选题] 一棵二叉树共有25个节点，其中5个叶子节点，那么度为1的节点数为(　　)。 　　A.4 　　B.6 　　C.10 　　D.16 　　参考答案：D 　　参考解析：由二叉树的性质n0=n2+1可知，度为0的结点数(即叶子结点数)=度为2的结点数+1，根据题意得知，度为2的结点数为4个，那么25-5-4=16即为度为1的结点数。 25个节点，5个子节点，其中子节点(度为0的节点)个数-度为2的节点个数=1，所以度为2的节点个数为4。节点度数有0，1，2，所以度为1的节点数为25-4-5=16，选项D正确。 　　8[单选题] 下列叙述中正确的是(　　)。 　　A.循环队列是队列的一种顺序存储结构 　　B.循环队列是队列的一种链式存储结构 　　C.循环队列是非线性结构 　　D.循环队列是一直逻辑结构 　　参考答案：A 　　参考解析：为了充分利用存储空间，可以把顺序队列看成一个环状空间，即把顺序队列的头尾指针相连，这样的队列称之为循环队列。它是对顺序队列的改进，故循环队列是队列的一种顺序存储结构。 　　9[单选题] 下列关于二叉树的叙述中，正确的是(　　)。 　　A.叶子结点总是比度为2的结点少一个 　　B.叶子结点总是比度为2的结点多一个 　　C.叶子结点数是度为2的结点数的两倍 　　D.度为2的结点数是度为1的结点数的两倍 　　参考答案：B 　　参考解析：由二叉树的性质可以知道在二叉树中叶子结点总是比度为2的结点多一个。 　　10[单选题] 下列关于线性链表的叙述中，正确的是(　　)。 　　A.各数据结点的存储空间可以不连续，但它们的存储顺序与逻辑顺序必须一致 　　B.各数据结点的存储顺序与逻辑顺序可以不一致，但它们的存储空间必须连续 　　C.进行插入与删除时，不需要移动表中的元素 　　D.以上三种说法都不对 　　参考答案：C 　　参考解析：线性表的链式存储结构称为线性链表。在链式存储结构中，存储数据结构的存储空间可以不连续，各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致，而数据元素之间的逻辑关系是由指针域来确定的。 11[单选题] 下列叙述中正确的是(　　)。 　　A.算法就是程序 　　B.设计算法时只需要考虑数据结构的设计 　　C.设计算法时只需要考虑结果的可靠性 　　D.以上三种说法都不对 　　参考答案：D 　　参考解析：所谓算法是指解题方案的准确而完整的描述。是一一组严谨地定义运算顺序的规则，并且每一个规则都是有效的，且是明确的，此顺序将在有限的次数下终止。算法不等于程序，也不等于计算方法。设计算法时不仅要考虑对数据对象的运算和操作，还要考虑算法的控制结构。 　　12[单选题] 某二叉树共有7个结点，其中叶子结点只有l个，则该二叉树的深度为(假设根结点在第1层)(　　)。 　　A.3 　　B.4 　　C.6 　　D.7 　　参考答案：D 　　参考解析：叶子节点就是度为0的结点，比度为2的结点多一个，即度2的没有，这样度为1的结点就是6个，故深度为7(1度就是结点连着1个子树，二叉树最多俩子树，即左右子树)。根据二叉树的性质，度为0的结点(即叶子结点)总是比度为2的结点多一个。题目中的二叉树的叶子结点为1，因此度为2的结点的数目为0，因而这个二叉树的深度为7。 　　13[单选题] 下列叙述中正确的是(　　)。 　　A.有一个以上根结点的数据结构不一定是非线性结构 　　B.只有一个根结点的数据结构不一定是线性结构 　　C.循环链表是非线性结构 　　D.双向链表是非线性结构 　　参考答案：B 　　参考解析：在数据结构中，树这类的的数据结构只有一个根结点，但它不是线性结构。 　　14[单选题] 下列关于栈叙正确的是(　　)。 　　A.栈顶元素最先能被删除 　　B.栈顶元素最后才能被删除 　　C.栈底元素永远不能被删除 　　D.以上三种说法都不对 　　参考答案：A 　　参考解析：栈是先进后出的线性表，栈顶的元素最先被删除，栈底的元素最后被删除。 　　15[单选题] 下列数据结构中，能用二分法进行查找的是(　　)。 　　A.无序线性表 　　B.线性链表 　　C.二叉链表 　　D.顺序存储的有序表 　　参考答案：D 　　参考解析：二分法查找只适用于顺序存储的有序表，表中的元素按值从小到大排列。 　　16[单选题] 对下列二叉树进行中序遍历的结果是(　　)。 　　 　　A.ABCDEFGH 　　B.ABDGEHCF 　　C.GDBEHACF 　　D.GDHEBFCA 　　参考答案：C 　　参考解析：遍历就是不重复地访问二叉树的所有结点。二叉树遍历的方法有3种：前序遍历、中序遍历和后序遍历。记住3种遍历的顺序： 　　①前序，访问根一按前序遍历左子树一按前序遍历右子树。 　　②中序，按中序遍历左子树一访问根一按中序遍历右子树。 　　③后序，按后序遍历左子树一按后序遍历右子树->访问根。 　　所以对该二叉树的中序遍历结果为GDBEHACF。 　　17[单选题] 在一棵二叉树中，叶子结点共有30个，度为1的结点共有40个，则该二叉树中的总结点数共有(　　)个。 　　A.89 　　B.93 　　C.99 　　D.100 　　参考答案：C 　　参考解析：根据二叉树性质3：对任何一棵二叉树，度为0的结点(即叶子结点)总是比度为2的结点多一个。所以该二叉树度为2的结点有29个，故总结点数=30个叶子结点+29个度为2的结点+40个度为1的结点=99个结点。 　　18[单选题] 下列关于栈的描述中，正确的是(　　)。 　　A.在栈中只能插入元素 　　B.在栈中只能删除元素 　　C.只能在一端插入或删除元素 　　D.只能在一端插入元素，而在另一端删除元素 　　参考答案：C 　　参考解析：栈实际也是线性表，只不过是一种特殊的线性表。栈是只能在表的一端进行插入和删除运算的线性表，通常称插入、删除的这一端为栈顶，另一端为栈底。当表中没有元素时称为空栈。栈顶元素总是最后被插入的元素，从而也是最先被删除的元素：栈底元素总是最先被插入的元素，从而也是最后才能被删除的元素。 　　19[单选题] 算法的有穷性是指(　　) 　　A.算法程序的运行时间是有限的 　　B.算法程序所处理的数据量是有限的 　　C.算法程序的长度是有限的 　　D.算法只能被有限的用户使用 　　参考答案：A 　　参考解析：算法的基本特征主要包括以下四个方面： 　　•可行性：针对实际问题而设计的算法，执行后能够得到满意的结果。 　　•确定性：算法中的每一个步骤都必须有明确的定义，不允许有模棱两可的解释和多义性。 　　•有穷性：算法必需在有限时间内做完，即算法必需能在执行有限个步骤之后终止。 　　•拥有足够的情报：要使算法有效必需为算法提供足够的情报当算法拥有足够的情报时，此算法才最有效的;而当提供的情报不够时，算法可能无效。 　　20[单选题] 以下关于算法叙述错误的是(　　)。 　　A.算法可以用伪代码、流程图等多种形式来描述 　　B.一个正确的算法必须有输入 　　C.一个正确的算法必须有输出 　　D.用流程图可以描述的算法可以用任何一种计算机高级语言编写成程序代码 　　参考答案：B