公共基础答案解析新

《公共基础答案解析新》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第一章数据结构与算法一，选择题1答案：B概念题。算法有四个特性，本题除A.C.D外，还包括“拥有足够情报”的特性；见教材《公共基础知识》第一章第一页第二行。2答案：C概念题。算法的时间复杂度是指算法执行过程中所需要的基本运算次数。见教材第一章第2页第四行。3答案：C概念题。见教材第一章第2页第一行。同第二题。4答案：D两者无此必然联系，可用平均性态和最坏情况复杂度两种方法分析算法时间复杂度注：1.2.3.4题考查算法复杂度5答案：D见第一章第三页倒数第十五行：数据存储结构。6答案：B通常，一种数据的逻辑结构根据需要可以表示成多种存储结构，常见的存储结构有顺序、链接、索引等存储结构。

2、采用不同的存储结构，其数据处理的效率是不同的。7答案：D见第一章第三页倒数第11行注：5，6，7题考查知识点，数据逻辑与存储结构。见P38答案：C栈是一种特殊的线性表。在这种特殊的线性表中，插入与删除操作都只在其一端进行。因此，栈是一种被限定仅在一端进行插入与删除操作的线性表。见教材第一章第七页第六行。9答案：B在栈中，允许插入与删除的一端称为栈底。栈是按照“先进后出”或“后进先出”的原则组织数据的，因此，栈也被称为“先进后出”或“后进先出”的线性表。因此栈具有记忆功能。栈是线性表，也可采用链式存储结构，故选B。10答案：D参考第八、九题的分析。11答案：B栈是按照“先进后出”或“

3、后进先出”的原则组织数据的，因此，栈也被称为“先进后出”或“后进先出”的线性表。因此选B。12答案：B同上分析。栈是按照“先进后出”或“后进先出”的原则组织数据的，因此，栈也被称为“先进后出”或“后进先出”的线性表。因此选B。13答案：C在栈中，允许插入与删除的一端称为栈底。栈是按照“先进后出”或“后进先出”的原则组织数据的，因此，栈也被称为“先进后出”或“后进先出”的线性表。因此栈具有记忆功能。14答案：C栈是一种特殊的线性表。在这种特殊的线性表中，插入与删除操作都只在其一端进行。因此，栈是一种被限定仅在一端进行插入与删除操作的线性表。见教材第一章第七页第六行。注：8至14题重点

4、，栈的基本概念，须熟记15答案：C队列也是一种特殊的线性表，是一种只允许在一端进行插入、而在另一端进行删除的线性表。队列是按照“先进先出”的原则组织数据的，因此队列又称为“后进后出”的线性表。见第一章第八页倒数第五行队列的概念16.答案：A17.答案：A18.答案：D线性链表中的各元素在存储空间中的位置不一定是连续的，而且各元素的存储顺序也是任意的。19.答案：AP5倒数第11行17至19总结：考查线性链表概念，链式存储方式可表示线性与非线结构20.答案：A队列是线性结构，树为非线性结构21.无此题22.答案：C深度是m的二叉树叶子结点（度为0的结点）数最多有2^(m-1)个，即满

5、二叉树叶子结点数23.答案：A注；T的深度为4。采用“摸石头过河”方法，自画一个满足此条件的树，一个个数叶子结点24.答案：B清楚此题限制为二叉树，采用同上方法25.答案：A双向链表，栈，队列是线性结构。树不符合线性结构条件26.答案：D树是非线性链表27.答案：C27-1注意；22，23，24，27分清楚树的度和深度的概念，知道二叉树的基本性质28.答案：B首先看到A是根结点，遍历左子树T.T又可看成“根结点”，T没有左子树，则遍历右子树B.再把B作为根结点，遍历左子树在，此时A的右边已遍历完。回到A的左子树X.同理……，所以最终遍历结果是ATBZXCYP29.答案：A中序遍历，

6、最右边的结点最后遍历30.答案：D后续遍历，根结点总是最后一个遍历注意；28至30搞清楚前序，中序，后序遍历的概念31.答案：C对长度为n的线性表进行顺序查找，在最坏情况下所需要的比较的次数为n.故选C。32.答案：A二分法查找只能应用于顺序存储的有序表。见第一章第14页第11行。33.答案：A对于长度为N的有序线性表，在最坏的情况下，折半查找只需要比较log2n次，而顺序查找则需要比较N次。34.答案：B对于长度为N的有序线性表，在最坏的情况下，而顺序查找则需要比较N次。35.答案：D在简单插入排序法中，每一次比较后最多移掉一个逆序，最坏的情况下，对长度为n的线性表，简单插入需要

7、n(n-1)/2次比较。36.答案：D二1.算法是正确而完整问题处理方案的描述。2.算法复杂度主要包括时间复杂度和空间复杂度。3.数据结构分为线性结构和非线性结构，带链队列属于线性结构。4.数据结构分为逻辑结构和存储结构，循环队列属于存储结构。5.数据结构分为逻辑结构和存储结构，线性链表属于存储结构。6.按“先进后出”原则组织数据的数据结构是栈。7.按“先进先出”原则组织数据的数据结构是队列。8.3front