《二级公共基础知识2020》由会员分享，可在线阅读，更多相关《二级公共基础知识2020（14页珍藏版）》请在金锄头文库上搜索。
1、二级公共基础知识第一部分 数据结构（5-6个题目，占10分）*1所谓算法是指解题方案的准确而完整的描述。严格来说，一个算法必须具有以下五个主 要特征：有穷性确定性可行性输入输出（或说成：拥有足够的情报）2. 算法的组成要素算法中对数据的运算和操作及算法的控制结构3算法设计基本方法列举法归纳法递推递归减半递推回溯法*4算法的复杂度可分为时间复杂度和空间复杂度，是衡量算法优劣的量度。（1）算法的时间复杂度：算法的时间复杂度是指执行算法所需要的工作量。一般情况下， 算法的时间复杂度为算法中的基本操作重复执行的次数。是问题规模n的某个函数f（n）。（2）算法的空间复杂度：算法的空间负杂度是指执行这个算
2、法所需要的内存空间。5数据结构的定义是指相互有关联的数据元素的集合。（一定要注意是数据元素的集合，不是数据的集合） *6.数据结构主要研究三个方面的问题：1）逻辑结构是各数据元素之间的逻辑关系。它与在计算机中的存储位置无关，是独立于计 算机的。2）在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构。3）对各种数据结构进行的运算。7. 常见的存储结构：顺序存储结构链式存储结构索引存储结构散列存储结构一般分为：线性存储和非线性存储8. 线性表的顺序存储结构用一组地址连续的存储单元依次存放线性表中的数据元素，即以“存储位置相邻”表示“存储，表中第一个元素的存储位置作称作线性表的基地
3、址。所有数据元素的存储位置均可由第一个数据元素的存储位置得到ADR（ai） = ADR（a1） + （i-1）XCff基地址一个数据元素所占存储量9. 线性表的插入和删除运算最坏的时间复杂度为O（n-1）,最好为0（0）.10. 栈是限定仅在表的一端进行插入和删除操作的线性表。允许插入和删除的一端称为栈顶, 另一端称为栈底。栈顶元素总是最后被插入的元素，从而也是最先被删除的元素；栈底元素 总是最先被插入，也是最后被删除的元素。栈是一种后进先出的线性表（通常用指针top指 示栈顶位置，用指针bottom指示栈底位置。11. 栈的操作有：入栈：在栈顶位置插入一个新元素，栈顶指针top加1（退栈：取
4、出栈顶元素并赋值给一个指定的变量，栈顶指针top减1（取栈顶元素：将栈顶元素的值赋给一个指定的变量，不删除栈顶元素，栈顶指针不变。12. 如果某栈的入栈顺序是ABCDEF，贝9出栈顺序不可能是哪个（C）（此类型的题目一定 要会推导）A、DCEFBA B、ABCDEF C、EDFCAB D、CBAEDF13. 队列是一种先进先出的线性表，它只允许在表的一端插入元素（队尾），在另一端删除元 素（队头）。通常定义头指针front指向队头元素的前一个位置，定义尾指针rear指向队尾元 素的位置。队列是一种先进先出的数据结构。14. 循环队列是将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状
5、空间。 容量的计算：*当 rearfront 时，元素个数=rearfront ；*当rear1时，其余的结点可分为m个互不相交的子集T1,T2,Tm,其中每个有限子集本身 又是一棵树。*22. 树的的几个重要术语：（不明白的自己看书） 树的度 叶节点 双亲、孩子和兄弟 层次 深度*23. 二叉树是另一种树型结构，其特点是每个结点至多有两棵子树，并且二叉树的子树有 左右之分，其顺序不能任意颠倒。几个重要的性质：性质1 在二叉树的第i层上至多有2i-1个结点（i1）性质2 深度为k的二叉树至多有2k-1个结点（k1）性质3对任何一棵二叉树T，如果其终端结点数为n0,度为2的结点数为n2，贝V：
6、n0 =n2+1 性质4具有n个结点的二叉树，其深度至少为log2n +1 24.满二叉树除最后一层外，每一层上的所有结点都有两个子节点，也就是说每一层上的结 点数都达到最大值，即在满二叉树的第k层上有2k-1个结点，且深度为m的满二叉树有2m-1 个结点。*25.完全二叉树除最后一层外，每一层上的结点数均达到最大值，在最后一层上只缺少右 边的若干结点。具有n个结点的完全二叉树，其深度为Iog2n+1。（一定要会计算结点的个 数）26. 二叉树的链式存储结构中，每个结点设置三个域，即数据域，左指针域和右指针域，两 个指针域分别存储左右子树根节点的存储位置，即指针。*27. 二叉树的遍历指不重复
7、地访问二叉树的所有结点。分为：先序、后序和中序遍历。一 定要明白由先序和中序推出后序，和由后序和中序推出先序 ！28. 顺序查找是指在一个给定的数据结构中查找某个指定的元素。最好情况查找长度为1， 最坏为n,所以平均查找长度为（n+1）/2。时间复杂度为0（n）。29二分查找法只适用于顺序存储的有序表。查找过程为：给定值首先和处于待查区间“中 间位置”的关键字进行比较，若相等，贝查找成功，否贝将查找区间缩小到“前半个区间” 或“后半个区间”之后继续进行查找。平均查找长度小于等于厂Iog2 (n+1)n ，时间复 杂度为 O(log2n)。*30. 排序方法有：插入排序：包括简单插入排序法和希尔
8、排序法等 交换排序：包括冒泡排序和快速排序法等选择排序：包括简单选择排序和堆排序等31.冒泡排序最坏情况下运算的次数为：n*(n-1)/2 (即时间复杂度)。最好情况下为：n-1。 *32.排序部分应该掌握的几点：1当原表有序或基本有序时，直接插入排序和冒泡排序最好，时间复杂度可降至0(n)(也 就是最好情况下) 。如果选择快速排序则相反，达到最坏时间复杂度。2. 空间复杂度最坏的是归并排序 O(n) ，其次是基数排序 O(rd) (3. 平均时间最好的是快速、堆、归并排序 O(nlgn)(4. 稳定排序和不稳定排序(希尔、堆、直接选择，快速)(5. 最坏情况下，时间复杂度最小的是：堆和归并排
9、序(第一部分典型例题1：已知一组数据原先采用顺序存储，现改为散列存储，则(B)不变。A.存储结构B.逻辑结构C.数据间的顺序D.不确定2：常见的线性结构有_线性表_,_队列_,_栈3：在线性表中删除第5个节点，则原第6个节点的位置(B),如果单链表则(C)A.6B.5C.不变D.不确定4：已知栈的头指针front当前位置为5,从栈中读取一个数据，则front指向(A)A.5B.6C.不变D.不确定5：如果某栈的入栈顺序是123456，则出栈顺序不可能是哪个(C)A、435621 B.123456C、546312D、6543216:容量为25的循环队列中，若front=16, rear=9,有_
10、18_个元素7：一棵二叉树中共有 70个叶子结点与80个度为 1 的结点，则该二叉树中的总结点数为 ( B)A) 221B) 219C) 231D) 2298：一棵含 18 个结点的二叉树的高度至少为(5)A) 3B) 4C) 5D) 69： 在一棵二叉树上第 5 层的结点数最多是 (B)A) 8B) 16C) 32D) 1510：在深度为5的满二叉树中，叶子结点的个数为(C)A) 32B) 31C) 16D) 1511：深度为4的二叉树中，编号为7的节点，它的右孩子节点为(D)该树为满二叉树；如 果该树是完全二叉树，但不是满二叉树，则它的最大节点编号为(A)A) 14B) 8C) 9D) 1
11、512：设树 T 的度为 4，其中度为 1， 2， 3， 4 的结点个数分别人 4， 2， 1， 1.则 T 中的叶子结 点数为 (A)A)8B)7C)6D)513. (3)线性表L= (a1,a2,a3,ai,an),下列说法正确的是(D)A)每个元素都有一个直接前件和直接后件B)线性表中至少要有一个元素C）表中诸元素的排列顺序必须是由小到大或由大到小D）除第一个元素和最后一个元素外，其余每个元素都有一个且只有一个直接前件和直接后 件14、3）链表不具有的特点是（B）A）不必事先估计存储空间B）可随机访问任一元素C）插入删除不需要移动元素D）所需空间与线性表长度成正比15、1）由两个栈共享一
12、个存储空间的好处是（B）A）减少存取时间，降低下溢发生的机率B）节省存储空间，降低上溢发生的机率C）减少存取时间，降低上溢发生的机率D）节省存储空间，降低下溢发生的机率16、设有两个串p和q,求q在p中首次出现位置的运算称作（B）A）连接B）模式匹配C）求子串D）求串长17、n个顶点的连通图中边的条数至少为（C）A） 0B） 1 C） n-1D） n18、n个顶点的强连通图中边的条数至少为（D）A） 0B） 1 C） n-1D） n19、（2）非空的循环单链表head的尾结点（由p所指向），满足A） p-next=NULLB） p=NULLC） p-next=headD） p=head20、已
13、知数据表A中每个元素距其最终位置不远，为节省时间，应采用的算法是（B）A）堆排序B）直接插入排序C）快速排序D）直接选择排序21、最简单的交换排序方法是（D）A）快速排序B）选择排序C）堆排序D）冒泡排序22、栈和队列通常采用的存储结构是【链式存储和顺序存储】23、冒泡排序算法在最好的情况下的n个元素交换次数为【0】次，但比较次数为【n-1】24、当线性表采用顺序存储结构实现存储时，其主要特点是【存储位置相邻】25、用链表表示线性表的突出优点是【插入、删除操作方便】第二部分程序设计基础（1-2题）和软件工程（4-5题）1. 程序设计主要经历了结构化的程序设计和面向对象的程序设计阶段。在程序设计中， 通常采用“自顶向下，逐步求精”的方法。结构化程序设计由三种基本控制结构组成：顺序 结构、选择结构和循环结构。2程序风格也是非常重要的。良好的程序设计风格概括起来包括以下4个方面： 源程序文档化（1）标识符的命名:要有一定的实际含义。（2）程序的注释：分为序言性注释和功能性注释。（3）程序的视觉组织：一定要层次清晰数据说明的方法（1）数据说明的次序应该规范化（2）说明语句中变量的安排有序化：如多个变量出现在同一个说明语句中，要按顺序排列。（3）使用注释说明
