文档介绍：第一章疑难解答:算法的工作杲用什么來计算?分法的工作最用算法所执行的基本运算次数來计算,而算法所执行的基本运算次数是问题规模的函数,即算法的工作量=f(n),其中n是问题的规模。空的数据结构是线性结构还是非线性结构?一个空的数据结构究竞是属于线性结构还是属于非线性结构,这要根据具体情况來确定。如果对该数据结构的算法是按线性结构的规则來处理的,则属于线性结构;否则属于非线性结构。栈是按照"先进后f『或"后进先出"的原则组织数据,但是出栈方式有多种选择,在考题屮经常考查各种不同的出栈方式。在链式结构屮,存储空间位置关系与逻紺关系是什么?在链式存储结构屮,存储数据结构的存储空间可以不连续,各数据结点的存储顺序与数据元索之间的逻辑关系可以不一致,而数据元索之间的逻辑关系是山指针域來确定的。小技巧:在二叉树的遍历中,无论是前序遍历,中序遍历还是后序遍历,二叉树的叶子结点的先后顺序都是不变的。树与二叉树的不同之处是什么?在二叉树屮,毎一个结点的度域大为2,即所有子树(左子树或右子树)也均为二叉树,而树结构中的毎一个结点的度可以是任意的。二分査找法适用于哪种情况?二分査找法只适用于顺序存储的有序表。在此所说的有序表是指线性表屮的元素按值非递减排列(即从小到大,但允许相邻元素值相等)。这个过程一直进行到查找成功或子表长度为0为止。対于长度为n的有序线性表,在最坏情况下,二分查找只需要比较log2n次。冒泡排序和快速排序的平均执行时间分别是多少?冒泡排序法的平均执行时间是O(I?),而快速排序法的平均执行时间是O(nlog2n)例题详解一、选择题【例1】算法的吋间复杂度取决于 o(考点2)A)问题的规模 B)待处理的数据的初态C)问题的难度 D)A)和B)解析:算法的吋间复杂度不仅与问题的规模有关,在同一个问题规模下,而且与输入数据有关。即与输入数据所有的可能収值范围、输入各种数据或数据集的概率有关。答案:D)7例2】在数据结构中,从逻辑上可以把数据结构分成 o(考点3)A)内部结构和外部结构 B)线性结构和非线性结构C)紧凑结构和非紧凑结构 D)动态结构和静态结构解析:逻辑结构反映数据元素之间的逻辑关系,线性结构表示数据元素之间为一对一•的关系,非线性结构表示数据元素ZI'可为一-对多或者多对一的关系,所以答案为B)。答案:B)[例3】以下不是栈的基本运算。(考点5)A)判断栈是否为素空 B)将栈置为空栈C)删除栈顶元素 D)删除栈底元素解析:栈的基本运算有:入栈,出栈(删除栈顶元素),初始化、置空、判断栈是否为空或满、提取栈顶元素等,对栈的操作都是在栈顶进行的。答案:D)【例4】链表不具备的特点是 o(考点6)A)可随机访问任意一个结点 B)插入和删除不需要移动任何元素C)不必事先估计存储空间 D)所需空间与英长度成止比解析:顺序表可以随机访问任意一个结点,而链衣必须从第一个数据结点出发,逐一•查找每个结点。所以答案为A)°答案:A)【例5】己知某二叉树的后序遍历序列是DACBE,中序遍历序列是DEBAC,则它的前序遍历序列是。(考点8)A) ACBED B))DECAB D)EDBAC解析:后序遍历的顺序是〃左子树一右子树一根结点〃;中序遍历顺序是〃左子树一根结点一右子树〃;前序遍历顺序是〃根结点一左子树一右子树〃。根据各种遍历算法,不难得出前序遍历序列是E