《考点1：数据结构与算法资料》由会员分享，可在线阅读，更多相关《考点1：数据结构与算法资料（23页珍藏版）》请在金锄头文库上搜索。
1、1.下列叙述中正确的是（ ）。答案：BA）所谓算法就是计算方法B）程序可以作为算法的一种描述方法C）算法设计只需考虑得到计算结果D）算法设计可以忽略算法的运算时间题目解析:算法是一组有穷指令集，是解题方案的准确而完整的描述。通俗地说，算法就是计算机解题的过程,重在解题方案的设计，并且不等于计算方法，故A和C选项不正确，程序的编制不可能优于算法的设计，但算法的描述可以用程序、伪代码、流程图来描述，故B选项正确。算法要求执行过程中所需要的基本运算次数和时间最少，即时间复杂度最低，所以C选项不正确。正确答案为B。2.下列各序列中不是堆的是（ ）。答案：CA）(91,85,53,36,47,30,24
2、,12)B）(91,85,53,47,36,30,24,12)C）(47,91,53,85,30,12,24,36)D）(91,85,53,47,30,12,24,36)题目解析:堆可以看成一棵完全二叉树：任一根节点=左右孩子（或者=）（大的叫大根堆，小的叫小根堆。）注意一个堆中的这种性质有一致性，不能既有大于又有小于情况存在,这题可以这么做，把结点按照完全二叉树画出来就一目了然了。这个题目很明显91是最大的根，而C选项是左根右的排序，那么91的左边只有47，其他都在右边，而右边无法按照此顺序排列，故选C。3.深度为5的完全二叉树的结点数不可能是（ ）。答案：AA）15B）16C）17D）18
3、题目解析:对于满二叉树，叶子结点的数目等于2（n-1）,n为深度，这里就是2的5-1=4次方，就是16。4. 设二叉树如下：则前序序列为（ ）。答案：AA）ABDEGCFHB）DBGEAFHCC）DGEBHFCAD）ABCDEFGH题目解析:前序遍历首先访问根结点然后遍历左子树，最后遍历右子树；在遍历左、右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树。故正确选项选A；B选项为中序遍历。C选项为后序遍历；D选项不正确。5.下列叙述中正确的是（ ）。答案：AA）循环队列是顺序存储结构B）循环队列是链式存储结构C）循环队列是非线性结构D）循环队列的插入运算不会发生溢出现象题目解析:循环队
4、列属于队列的特例和栈同属于线性结构，C选项不正确。在顺序队列中,由于数组空间不够而产生的溢出叫真溢出；顺序队列因多次入队列和出队列操作后出现的有存储空间但不能进行入队列操作的溢出称为假溢出；假溢出是由于队尾rear的值和队头front的值不能由所定义数组下界值自动转为数组上界值而产生的，解决的办法是把顺序队列所使用的存储空间构造成一个逻辑上首尾相连的循环队列，因此，顺序队列通常都采用顺序循环队列结构；栈的存储方式有顺序存储和链式存储，故正确选项为A；B选项不正确。循环队列虽然能解决由于假溢出，却不能解决在顺序队列中,由于数组空间不够而产生的溢出的真溢出，故选项C不正确。6.下列叙述中正确的是（
5、 ）。答案：DA）所有数据结构必须有根结点B）所有数据结构必须有终端结点（即叶子结点）C）只有一个根结点，且只有一个叶子结点的数据结构一定是线性结构D）没有根结点或没有叶子结点的数据结构一定是非线性结构题目解析:只有一个空节点的结构也属数据结构，所以A和B选项不正确；有且只有一个根结点，每一个结点最多有一个前件，也最多有一个后件的数据结构才属于线性结构，其它的都属于非线性结构，故C选项不正确，正确选项为D。7.下列关于算法的描述中错误的是（ ）。答案：DA）算法强调动态的执行过程，不同于静态的计算公式B）算法必须能在有限个步骤之后终止C）算法设计必须考虑算法的复杂度D）算法的优劣取决于运行算法
6、程序的环境题目解析:算法的优劣取决自身的运行效率，时间和空间复杂度高低，并不取决于运行算法程序的环境，故D选项错误。8. 设二叉树如下：则中序序列为（ ）。答案：BA）ABDEGCFHB）DBGEAFHCC）DGEBHFCAD）ABCDEFGH题目解析:中序遍历（LDR）是指首先遍历左子树，然后访问根结点，最后遍历右子树；故正确答案为B。9.线性表的链式存储结构与顺序存储结构相比，链式存储结构的优点有（ ）。答案：BA）节省存储空间B）插入与删除运算效率高C）便于查找D）排序时减少元素的比较次数题目解析:顺序存储时，相邻数据元素的存放地址也相邻（逻辑与物理统一）；要求内存中可用存储单元的地址必
7、须是连续的。优点：存储密度大（1），存储空间利用率高。缺点：插入或删除元素时不方便。链式存储时，相邻数据元素可随意存放，但所占存储空间分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针 优点：插入或删除元素时很方便效率高，使用灵活。缺点：存储密度小（1），存储空间利用率低。故正确选项为B。10.深度为的完全二叉树中共有125个结点，则该完全二叉树中的叶子结点数为（ ）。答案：BA）62B）63C）64D）65题目解析: 对于满二叉树，结点的数目等于2n-1，叶子结点数目为2n-1，n为深度，这里就是2的7次方-1，就是127个结点，叶子结点是64个，然而题目中只有125个结点，说明少
8、了两个结点，那么就少了一个叶子结点，即63个。11.下列叙述中正确的是（ ）。答案：CA）所谓有序表是指在顺序存储空间内连续存放的元素序列B）有序表只能顺序存储在连续的存储空间内C）有序表可以用链接存储方式存储在不连续的存储空间内D）任何存储方式的有序表均能采用二分法进行查找题目解析:有序表可以用顺序存储空间内连续存放的元素序列来实现，也可以用链接存储方式存储在不连续的存储空间内，已达到逻辑上连续，存储空间上不一定连续的效果。二分法进行查找只适用于顺序存储的有序表。故选项C正确。12. 设二叉树如下：则后序序列为（ ）。答案：CA）ABDEGCFHB）DBGEAFHCC）DGEBHFCAD）A
9、BCDEFGH题目解析:后序遍历（LRD）首先遍历左子树，然后访问遍历右子树，最后访问根结点。故正确选项为C。13.下列叙述中正确的是（ ）。答案：BA）结点中具有两个指针域的链表一定是二叉链表B）结点中具有两个指针域的链表可以是线性结构，也可以是非线性结构C）二叉树只能采用链式存储结构D）循环链表是非线性结构题目解析:结点中尽管有两个指针域但没有分别指向两个不同的结点就不是二叉链表，故A选项不正确；二叉树是非线性结构，即每个数据结点至多只有一个前驱，但可以有多个后继。它可采用顺序存储结构和链式存储结构，故C选项不正确；循环链表是在单链表中，将终端结点的指针域NULL改为指向表头结点或开始结点
10、的线性结构，故D选项不正确；当结点中两个指针分别指向前驱结点和后继结点是为线性结构，当指向两个不同的前驱或后继结点时为非线性结构，故B选项正确。14.设某二叉树中共有140个结点，其中有40个度为1的结点。则（ ）。答案：DA）该二叉树中有51个叶子结点B）该二叉树中有50个叶子结点C）该二叉树中有51个度为2的结点D）不可能有这样的二叉树题目解析:140个结点除去40个度为1的结点，说明有100个度为2的结点，而根据二叉树性质，这个数值无法得出故本题答案选D。15.带链的栈与顺序存储的栈相比，其优点是（ ）。答案：CA）入栈与退栈操作方便B）可以省略栈底指针C）入栈操作时不会受栈存储空间的限
11、制而发生溢出D）以上都不对题目解析:带链的栈与顺序存储的栈相比优点是不受连续存储空间大小的限制，即不需考虑栈满的问题，故C选项正确。16.某二叉树的前序序列为ABCD，中序序列为DCBA，则后序序列为（ ）。答案：BA）BADCB）DCBAC）CDABD）ABCD题目解析:在二叉树前序遍历中ABCD中A是根节点，二在后序遍历中根结点位于最后，所以正确答案为B。17. 某系统结构图如下所示该系统结构图的最大扇入数是（ ）。答案：AA）nB）1C）2D）3题目解析:系统结构图中的最大扇入数为系统图中进入某一节点的最大节点数，本系统图中功能n.1节点输出节点为功能1到功能n,所以系统结构图的最大扇入
12、数为n,故正确选项为A。18.下列关于算法复杂度叙述正确的是（ ）。答案：BA）最坏情况下的时间复杂度一定高于平均情况的时间复杂度B）时间复杂度与所用的计算工具无关C）对同一个问题，采用不同的算法，则它们的时间复杂度是相同的D）时间复杂度与采用的算法描述语言有关题目解析:准确把握算法复杂度的概念。19.设有栈S和队列Q，初始状态均为空。首先依次将A,B,C,D,E,F入栈，然后从栈中退出三个元素依次入队，再将X,Y,Z入栈后，将栈中所有元素退出并依次入队，最后将队列中所有元素退出，则退队元素的顺序为（ ）。答案：BA）DEFXYZABCB）FEDZYXCBAC）FEDXYZCBAD）DEFZY
13、XABC题目解析:栈是一种特殊的线性表栈中的数据时按照先进后出或者是后进先出的规则进行的，队列是同栈不太相同的线性结构，进出顺序为先进先出的规则，根据题意要求本题正确答案为B选项。20.下列叙述中正确的是（ ）。答案：DA）有两个指针域的链表称为二叉链表B）循环链表是循环队列的链式存储结构C）带链的栈有栈顶指针和栈底指针，因此又称为双重链表D）结点中具有多个指针域的链表称为多重链表题目解析:结点中尽管有两个指针域但没有分别指向两个不同的结点就不是二叉链表，故A选项不正确；循环链表是在单链表中，将终端结点的指针域NULL改为指向表头结点或开始结点的线性结构，故B选项不正确；当结点中两个指针分别指
14、向前驱结点和后继结点是为线性结构，当指向两个不同的前驱或后继结点时为非线性结构，故B选项正确。双重链表的结点有两个指针，一个指向前驱，一个指向后继，从一个结点既可以向前也可以向后才是双重链表，故C选项不正确。D选项正确。21.某二叉树共有845个结点，其中叶子结点有45个，则度为1的结点数为（ ）。答案：CA）400B）754C）756D）不确定题目解析:二叉树中，度为0的结点（即叶子节点）比度为2的结点多1个，而度为0、1、2的结点相加等于总结点数845，所以度为1的结点数为845-45-（45-1）=756。22.深度为7的二叉树共有127个结点，则下列说法中错误的是（ ）。答案：AA）该
15、二叉树有一个度为1的结点B）该二叉树是满二叉树C）该二叉树是完全二叉树D）该二叉树有64个叶子结点题目解析:大家一定要记清楚这几个二叉树的性质。23.下列叙述中正确的是（ ）。答案：DA）非线性结构只能采用链式存储结构B）非线性结构只能用多重链表表示C）所有数据结构既可以采用顺序存储结构，也可以采用链式存储结构D）有的非线性结构也能采用顺序存储结构题目解析:链式存储方式即可用于表示线性结构，也可用于表示非线性结构，非线性结构也可以用连续存储空间顺序存储。所以AB选项不正确在所有的数据结构中并非所有的结构都能用顺序存储结构和采用链式存储结构表示，故选项C不正确，D选项正确。24.某二叉树的中序序列为BDCA，后序序列为DCBA，则前序序列为（ ）。答案：CA）DCBAB）BDCAC）ABCDD）BADC题目解析:在二叉树后序遍历中DCBA中A是根节点，二在前序遍历中根结点位于首位，所以正确答案为B。25. 某系统结构图如下图所示该系统结构图的最大扇出数是（
