2018年3月计算机二级C语言练习题三.docxVIP

2018年3月计算机二级C语言练习题三　　第1章 程序设计基本概念　　1.2 算法　　1[单选题] 线性表常采用的两种存储结构是(　　)。　　A.散列方法和索引方式　　B.链表存储结构和数组　　C.顺序存储结构和链式存储结构　　D.线性存储结构和非线性存储结构　　参考答案：C　　参考解析：线性表的存储通常要用两种存储结构：顺序存储结构和链式存储结构。　　2[单选题] 程序设计的任务包括(　　)。　　A.编写程序代码并上机调试　　B.确定所用数据结构　　C.确定所用算法　　D.以上选项均正确　　参考答案：D　　参考解析：程序设计是一门技术，需要相应的理论、技术、方法和工具来支持。程序设计的任务包括选项A)、B)、c) 等方面。　　3[填空题]　　在最坏情况下，堆排序需要比较的次数为_________。　　参考解析：O(nlog2n)　　【解析】在最坏情况下，冒泡排序所需要的比较次数为n(n-1)/2;简单插入排序所需要的比较次数为n(n-1)/2;希尔排序所需要的比较次数为O(n1.5);堆排序所需要的比较次数为O(nlog2n)。　　4[单选题] 下列关于栈的描述中，正确的是(　　)。　　A.在栈中只能插入元素　　B.在栈中只能删除元素　　C.只能在一端插入或删除元素　　D.只能在一端插入元素，而在另一端删除元素　　参考答案：C　　参考解析：栈实际也是线性表，只不过是一种特殊的线性表。栈是只能在表的一端进行插入和删除运算的线性表，通常称插入、删除的这一端为栈顶，另一端为栈底。当表中没有元素时称为空栈。栈顶元素总是最后被插入的元素，从而也是最先被删除的元素：栈底元素总是最先被插入的元素，从而也是最后才能被删除的元素。　　5[单选题] 在一棵二叉树中，叶子结点共有30个，度为1的结点共有40个，则该二叉树中的总结点数共有(　　)个。　　A.89　　B.93　　C.99　　D.100　　参考答案：C　　参考解析：根据二叉树性质3：对任何一棵二叉树，度为0的结点(即叶子结点)总是比度为2的结点多一个。所以该二叉树度为2的结点有29个，故总结点数=30个叶子结点+29个度为2的结点+40个度为1的结点=99个结点。　　6[填空题]　　队列是限定在表的一端进行插入和在另一端进行删除操作的线性表。允许删除的一端称作__________。　　参考解析：队头　　【解析】队列是只允许在一端删除，在另一端插入的顺序表，在队列中。允许插入的一端叫做“队尾”，允许删除的一端叫做“队头”。　　7[单选题] 下列关于栈叙正确的是(　　)。　　A.栈顶元素最先能被删除　　B.栈顶元素最后才能被删除　　C.栈底元素永远不能被删除　　D.以上三种说法都不对　　参考答案：A　　参考解析：栈是先进后出的线性表，栈顶的元素最先被删除，栈底的元素最后被删除。　　8[单选题] 下列叙述中正确的是(　　)。　　A.有一个以上根结点的数据结构不一定是非线性结构　　B.只有一个根结点的数据结构不一定是线性结构　　C.循环链表是非线性结构　　D.双向链表是非线性结构　　参考答案：B　　参考解析：在数据结构中，树这类的的数据结构只有一个根结点，但它不是线性结构。　　9[单选题] 某二叉树共有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。　　10[填空题]　　一颗二叉树的中序遍历结果为DBEAFC，前序遍历结果为ABDECF，则后序遍历结果为 【2】 。　　参考解析：【2】DEBFCA　　【解析】根据二叉树的中序遍历原则可知D为二叉树的最左边的叶子结点，根据二叉树的前序遍历原则可知A是二叉树的根结点，就可以确定二叉树的结构，所以二叉树的后序遍历结果为：DEBFCA。　　11[单选题] 下列叙述中正确的是(　　)。　　A.算法就是程序　　B.设计算法时只需要考虑数据结构的设计　　C.设计算法时只需要考虑结果的可靠性　　D.以上三种说法都不对　　参考答案：D　　参考解析：所谓算法是指解题方案的准确而完整的描述。是一一组严谨地定义运算顺序的规则，并且每一个规则都是有效的，且是明确的，此顺序将在有限的次数下终止。算法不等于程序，也不等于计算方法。设计算法时不仅要考虑对数据对象的运算和操作，还要考虑算法的控制结构。　　12[单选题] 下列关于线性链表的叙述中，正确的是(　　)。　　A