搜索
历年真题公共基础知识之算法与数据结构知识点一、算法1、算法的定义与基本特征2、算法的基本要素3、时间复杂度4、空间复杂度的定义二、数据结构1、数据结构研究的内容2、逻辑结构3、存储（物理）结构的含义4、线性结构与非线性结构5、线性表、栈、队列（循环队列）及运算原则6、线性链表、带链的栈、带链的队列7、树、二叉树、完全二叉树、满二叉树定义及性质8、二叉树的遍历三、查找与排序技术1、查找技术之顺序查找、二分法查找的原理及最坏情况复杂度2、排序技术的类型及各类型包括的典型方法的原理和最坏情况复杂度是指解题方案的准确而完整的描述可行性；确定性，有穷性，拥有足够的情报查找技术排序技术顺序查找二分法查找冒泡排序快速排序简单插入排序希尔排序简单选择排序堆排序法交换类排序插入类排序选择类排序nlog2nn(n-1)/2n(n-1)/2n(n-1)/2O(n1.5)n(n-1)/2O(nlog2n)最坏时间复杂度10-3（１）下列叙述中正确的是Ａ）对长度为ｎ的有序链表进行查找，最坏情况下需要的比较次数为ｎＢ）对长度为ｎ的有序链表进行对分查找，最坏情况下需要的比较次数为（n/2）Ｃ）对长度为ｎ的有序链表进行对分查找，最坏情况下需要的比较次数为（log2n）Ｄ）对长度为ｎ的有序链表进行对分查找，最坏情况下需要的比较次数为（log2n）（２）算法的时间复杂度是指Ａ）算法的执行时间Ｂ）算法所处理的数据量Ｃ）算法程序中的语句或指令条数Ｄ）算法在执行过程中所需要的基本运算次数AD10-3（１）一个队列的初始状态为空。现将元素Ａ，Ｂ，Ｃ，Ｄ，Ｅ，Ｆ，５，４，３，２，１依次入队，然后再依次退队，则元素退队的顺序为【１】。（２）设某循环队列的容量为50，如果头指针front＝45（指向队头元素的前一位置），尾指针rear＝10（指向队尾元素），则该循环队列中共有【２】个元素。ＡＢＣＤＥＦ５４３２１15ABCDFEGH（３）设二叉树如下：对该二叉树进行后序遍历的结果为【３】。10-3ＥＤＢＧＨＦＣＡ（1）下列数据结构中，属于非线性结构的是A）循环队列B)带链队列C)二叉树D）带链栈（2）下列数据结果中，能够按照“先进后出”原则存取数据的是A)循环队列B)栈C)队列D)二叉树（3）对于循环队列，下列叙述中正确的是A）队头指针是固定不变的B）队头指针一定大于队尾指针C）队头指针一定小于队尾指针D）队头指针可以大于队尾指针，也可以小于队尾指针09-9CBD09-9（4）算法的空间复杂度是指A）算法在执行过程中所需要的计算机存储空间B）算法所处理的数据量C）算法程序中的语句或指令条数D）算法在执行过程中所需要的临时工作单元数（1）某二叉树有5个度为2的结点以及3个度为1的结点，则该二叉树中共有【1】个结点。A1409-03（1）下列叙述中正确的是A）栈是“先进先出”的线性表B）队列是“先进先出”的线性表C）循环队列是非线性结构D）有序性表既可以采用顺序存储结构，也可以采用链式存储结构（2）支持子程序调用的数据结构是A）栈B）树C）队列D）二叉树（3）某二叉树有5个度为2的结点，则该二叉树中的叶子结点数是A）10B）8C）6D）4BAC09-3（4）下列排序方法中，最坏情况下比较次数最少的是A）冒泡排序B）简单选择排序C）直接插入排序D）堆排序假设一个长度为50的数组（数组元素的下标从0到49）作为栈的存储空间，栈底指针bottom指向栈底元素，栈顶指针top指向栈顶元素，如果bottom=49，top=30（数组下标），则栈中具有【1】个元素。D2008-9（1）一个栈的初始状态为空。现将元素1、2、3、4、5、A、B、C、D、E依次入栈，然后再依次出栈，则元素出栈的顺序是（）。A）12345ABCDEB）EDCBA54321C）ABCDE12345D）54321EDCBA（2）下列叙述中正确的是（）。A）循环队列有队头和队尾两个指针，因此，循环队列是非线性结构B）在循环队列中，只需要队头指针就能反映队列中元素的动态变化情况C）在循环队列中，只需要队尾指针就能反映队列中元素的动态变化情况D）循环队列中元素的个数是由队头指针和队尾指针共同决定BD08-9（3）在长度为n的有序线性表中进行二分查找，最坏情况下需要比较的次数是（）。A）O(n)B）O(n2)C）O(log2n)D）O(nlog2n)（4）下列叙述中正确的是（）。A）顺序存储结构的存储一定是连续的，链式存储结构的存储空间不一定是连续的B）顺序存储结构只针对线性结构，链式存储结构只针对非线性结构C）顺序存储结构能存储有序表，链式存储结构不能存储有序表D）链式存储结构比顺序存储结构节省存储空间CA08-9（1）对下列二叉树进行中序遍历的结果【1】。ABCDEFXYZ08年4月（5）算法的有穷性是指A）算法程序的运行时间是有限的B）算法程序所处理的数据量是有限的C）算法程序的长度是有限的D）算法只能被有限的用户使用（6）对长度为n的线性表排序，在最坏情况下，比较次数不是n(n-1)/2的排序方法是A）快速排序B）冒泡排序C）直接插入排序D）堆排序（7）下列关于栈的叙述正确的是A）栈按“先进先出”组织数据B）栈按“先进后出”组织数据C）只能在栈底插入数据D）不能删除数据（2）深度为5的满二叉树有【2】个叶子结点。（3）设某循环队列的容量为50，头指针front=5（指向队头元素的前一位置），尾指针rear=29（指向队尾元素），则该循环队列中共有【3】个元素。ADB162407年9月（6）下列叙述中正确的是。A）数据的逻辑结构与存储结构必定是一一对应的B）由于计算机存储空间是向量式的存储结构，因此，数据的存储结构一定是线性结构C）程序设计语言中的数组一般是顺序存储结构，因此，利用数组只能处理线性结构D）以上三种说法都不对（7）冒泡排序在最坏情况下的比较次数是。A）ｎ(n＋1)/2B）nlog2nC）n(n－1)/2D）ｎ/2（8）一棵二叉树中共有70个叶子结点与80个度为1的结点，则该二叉树中的总结点数为。A）219B）221C）229D）231（3）线性表的存储结构主要分为顺序存储结构和链式存储结构。队列是一种特殊的线性表，循环队列是队列的【3】存储结构。（4）对下列二义树进行中序遍历的结果为【4】。DCA顺序ACBDFEHGPFCEADGBHP07年4月(1)下列叙述中正确的是A)算法的效率只与问题的规模有关，而与数据的存储结构无关B)算法的时间复杂度是指执行算法所需要的计算工作量C)数据的逻辑结构与存储结构是一一对应的D)算法的时间复杂度与空间复杂度一定相关(5)下列对列的叙述正确的是A)队列属于非线性表B)队列按“先进后出”原则组织数据C)队列在队尾删除数据D)队列按“先进先出”原则组织数据(6)对下列二叉树进行前序遍历的结果为A)DYBEAFCZXB)YDEBFC)ABDYECFXZD)ABCDEFXYZ(7)某二叉树中有n个度为2的结点，则该二叉树中的叶子结点为A)n+1B)n-1C)2nD)n/2（1）在深度为7的满二叉树中，度为2的结点个数为_________。BDC63A06年9月（7）下列叙述中正确的是________。A）一个算法的空间复杂度大，则其时间复杂度也必定大B）一个算法的空间复杂度大，则其时间复杂度必定小C）一个算法的时间复杂度大，则其空间可复杂度必定小D）上述三种说法都不对（8）在长度为64的有序线性表中进行顺序查找，最坏情况下需要比较的次数为________。A）63B）64C）6D）7（10）对下列二叉树进行中序遍历的结果是________。A）ACBDFEGB）ACBDFGEC）ABDCGEFD）FCADBEG（4）按“先进后出”原则组织数据的数据结构是【4】。（5）数据结构分为线性结构和非线性结构，带链的队列属于【5】DBA栈线性结构06年4月(4)按照”后进先出”原则组织数据的数据结构是A)队列B)栈C)双向链表D)二叉树(5)下列叙述中正确的是A)线性链表是线性表的链式存储结构B)栈与队列是非线性结构C)双向链表是非线性结构D)只有根结点的二叉树是线性结构(6)对如下二叉树进行后序遍历的结果为A)ABCDEFB)DBEAFCC)ABDECFD)DEBFCA(7)在深度为7的满二叉树中,叶子结点的个数为A)32B)31C)64D)63(1)对长度为10的线性表进行冒泡排序,最坏情况下需要比较的次数为【1】。BAD45CABCDEF05年9月（2）下列数据结构中，能用二分法进行查找的是A）顺序存储的有序线性表BC）二叉链表D）有序线性链表（3）下列关于栈的描述正确的是A）在栈中只能插入元素而不能删除元素B）在栈中只能删除元素而不能插入元素C）栈是特殊的线性表，只能在一端插入或删除元素D）栈是特殊的线性表，只能在一端插入元素，而在另一端删除元素（4）下列叙述中正确的是A）一个逻辑数据结构只能有一种存储结构B）数据的逻辑结构属于线性结构，存储结构属于非线性结构C）一个逻辑数据结构可以有多种存储结构，且各种存储结构不影响数据处理的效率D）一个逻辑数据结构可以有多种存储结构，且各种存储结构影响数据处理的效率（2）算法复杂度主要包括时间复杂度和【2】复杂度。（4）一棵二叉树第六层（根结点为第一层）的结点数最多为【4】个。（5）数据结构分为逻辑结构和存储结构，循环队列属于【5】结构。ACD空间32逻辑05年4月（1）数据的存储结构是指______。A）存储在外存中的数据B）数据所占的存储空间量C）数据在计算机中的顺序存储方式D）数据的逻辑结构在计算机中的表示（2）下列关于栈的描述中错误的是______。A）栈是先进后出的线性表B）栈只能顺序存储C）栈具有记忆作用D）对栈的插入与删除操作中，不需要改变栈底指针（3）对于长度为n的线性表，在最坏情况下，下列各排序法所对应的比较次数中正确的是______。A）冒泡排序为n/2B）冒泡排序为nC）快速排序为nD）快速排序为n(n-1)/2（4）对长度为nA）log2nB）n/2C）nD）n+1（5）下列对于线性链表的描述中正确的是______。A）存储空间不一定是连续，且各元素的存储顺序是任意的B）存储空间不一定是连续，且前件元素一定存储在后件元素的前面C）存储空间必须连续，且前件元素一定存储在后件元素的前面D）存储空间必须连续，且各元素的存储顺序是任意的（1）某二叉树中度为2的结点有18个，则该二叉树中有【1】个叶子结点。（5）问题处理方案的正确而完整的描述称为【5】。DBD19算法CA程序设计基础知识点一、程序设计方法与风格1、当今主导程序设计风格2、良好程序设计风格应注重的因素二、结构化程序设计1、结构化程序设计的原则2、结构化程序的基本结构三、面向对象程序设计1、主要优点2、面向对象方法的基础概念：对象、类、对象与类的关系、对象的特点、消息、封装性、多态性、继承性清晰第一，效率第二源程序文档化，数据说明的方法，语句的结构，输入和输出自顶向下，逐步求精，模块化，限制GOTO顺序，选择，循环与人类思维一致，稳定性好，可生用性好，易于开发大型软件产品，可维护性好标识惟一性，分类性，多态性，封装性，模块独立性好05年4月－－08年4月（1）结构化程序设计的基本原则不包括A）多态性B）自顶向下C）模块化D）逐步求精（2）在面向对象方法中，实现信息隐蔽是依靠。A）对象的继承B）对象的多态C）对象的封装D）对象的分类（3）下列叙述中，不符合良好程序设计风格要求的是。A）程序的效率第一，清晰第二B）程序的可读性好C）程序中要有必要的注释D）输入数据前要有提示信息(4)下面选项中不属于面向对象程序设计特征的是A)继承性B)多态性C)类比性D)封装性（5）下列选项不符合良好程序设计风格的是________。A）源程序要文档化B）数据说明的次序要规范化C）避免滥用goto语句D）模块设主地要保证高耦合、高内聚ACACD05年4月－－08年4月(6)下列选项中不属于结构化程序设计方法的是A)自顶向下B)逐步求精C)模块化D)可复用(1)在面向对象方