《二级公共基础知识（学生版）》由会员分享，可在线阅读，更多相关《二级公共基础知识（学生版）（25页珍藏版）》请在金锄头文库上搜索。
1、二级公共基础知识第一部分 数据结构(5-6个题目，占10分)*1.所谓算法是指解题方案的准确而完整的描述。严格来说，一个算法必须具有以下五个主要特征：n 有穷性 确定性 可行性 输入 输出（或说成：拥有足够的情报 ）2.算法的组成要素n 算法中对数据的运算和操作及算法的控制结构3.算法设计基本方法n 列举法 归纳法 递推 递归 减半递推 回溯法*4.算法的复杂度可分为时间复杂度和空间复杂度，是衡量算法优劣的量度。（1）算法的时间复杂度：算法的时间复杂度是指执行算法所需要的工作量。一般情况下，算法的时间复杂度为算法中的基本操作重复执行的次数。是问题规模n的某个函数f(n)。（2）算法的空间复杂度
2、：算法的空间复杂度是指执行这个算法所需要的内存空间。5.数据结构的定义 是指相互有关联的数据元素的集合。（一定要注意是数据元素的集合，不是数据的集合）*6. 数据结构主要研究三个方面的问题： 1) 逻辑结构是各数据元素之间的逻辑关系。它与在计算机中的存储位置无关，是独立于计算机的。2)在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构。3)对各种数据结构进行的运算。7. 常见的存储结构：n 顺序存储结构 链式存储结构 索引存储结构 散列存储结构n 一般分为：线性存储和非线性存储8. 线性表的顺序存储结构用一组地址连续的存储单元依次存放线性表中的数据元素，即以“存储位置相邻”表
3、示“存储，表中第一个元素的存储位置作称作线性表的基地址。 所有数据元素的存储位置均可由第一个数据元素的存储位置得到 ADR(ai) = ADR(a1) + (i-1)C 基地址 一个数据元素所占存储量 9. 线性表的插入和删除运算最坏的时间复杂度为O(n-1),最好为O(o).10. 栈是限定仅在表的一端进行插入和删除操作的线性表。允许插入和删除的一端称为栈顶，另一端称为栈底。栈顶元素总是最后被插入的元素，从而也是最先被删除的元素；栈底元素总是最先被插入，也是最后被删除的元素。栈是一种后进先出的线性表。通常用指针top指示栈顶位置，用指针bottom指示栈底位置。11. 栈的操作有：n 入栈：
4、在栈顶位置插入一个新元素，栈顶指针top加1。n 退栈：取出栈顶元素并赋值给一个指定的变量，栈顶指针top减1。n 取栈顶元素：将栈顶元素的值赋给一个指定的变量，不删除栈顶元素，栈顶指针不变。12. 如果某栈的入栈顺序是ABCDEF，则出栈顺序不可能是哪个（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
6、，度为2的结点数为n2 ，则：n0 =n2+1性质4 具有n个结点的二叉树，其深度至少为log2n +124.满二叉树除最后一层外，每一层上的所有结点都有两个子节点，也就是说每一层上的结点数都达到最大值，即在满二叉树的第k层上有2k-1个结点，且深度为m的满二叉树有2m-1个结点。*25.完全二叉树除最后一层外，每一层上的结点数均达到最大值，在最后一层上只缺少右边的若干结点。具有n个结点的完全二叉树，其深度为log2n +1。（一定要会计算结点的个数）26. 二叉树的链式存储结构中，每个结点设置三个域，即数据域，左指针域和右指针域，两个指针域分别存储左右子树根节点的存储位置，即指针。*27.
7、二叉树的遍历指不重复地访问二叉树的所有结点。分为：先序、后序和中序遍历。一定要明白由先序和中序推出后序，和由后序和中序推出先序！28. 顺序查找是指在一个给定的数据结构中查找某个指定的元素。最好情况查找长度为1，最坏为n，所以平均查找长度为（n+1)/2。时间复杂度为O(n)。29二分查找法只适用于顺序存储的有序表。查找过程为：给定值首先和处于待查区间“中间位置”的关键字进行比较，若相等，则查找成功，否则将查找区间缩小到“前半个区间” 或 “后半个区间” 之后继续进行查找。平均查找长度小于等于 log2 (n+1) ，时间复杂度为O(log2n)。*30. 排序方法有：插入排序：包括简单插入排
8、序法和希尔排序法等交换排序：包括冒泡排序和快速排序法等选择排序：包括简单选择排序和堆排序等31. 冒泡排序最坏情况下运算的次数为：n*(n-1)/2（即时间复杂度）。最好情况下为：n-1。*32.排序部分应该掌握的几点： 1.当原表有序或基本有序时,直接插入排序和冒泡排序最好，时间复杂度可降至O(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.6 B.5 C.不变 D.不确定4：已知栈的头指针front当前位置为5，从栈中读取一个数据，则front指向（A） A.5 B.6 C.不变 D.不确定5：如果某栈的入栈顺序是123456，则出栈顺序不可能是哪个（C） A、435621 B.123456 C、546312 D、6543216:容量为25的循环队列中，若fron
10、t=16，rear=9，有 _18_ 个元素7： 一棵二叉树中共有70个叶子结点与80个度为1的结点，则该二叉树中的总结点数为 ( B) A）221 B）219 C）231 D）229 8：一棵含18个结点的二叉树的高度至少为(5) A）3 B）4 C）5 D）69： 在一棵二叉树上第5层的结点数最多是 (B) A）8 B）16 C）32 D）1510：在深度为5的满二叉树中，叶子结点的个数为(C) A）32 B）31 C）16 D）1511：深度为4的二叉树中，编号为7的节点，它的右孩子节点为（D）该树为满二叉树；如果该树是完全二叉树，但不是满二叉树，则它的最大节点编号为（A） A）14 B
11、）8 C）9 D）1512：设树T的度为4，其中度为1，2，3，4的结点个数分别人4，2，1，1.则T中的叶子结点数为(A) A)8 B)7 C)6）13（3）线性表L=（a1,a2,a3,ai，an），下列说法正确的是（D）A）每个元素都有一个直接前件和直接后件 B）线性表中至少要有一个元素C）表中诸元素的排列顺序必须是由小到大或由大到小D）除第一个元素和最后一个元素外，其余每个元素都有一个且只有一个直接前件和直接后件143）链表不具有的特点是（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）0 B）1 C）n-1 D）n18、 n个顶点的强连通图中边的条数至少为（D）A）0 B）1 C）n-1 D）n19. （2）非空的循环单链表head的尾结点（由p所指向），满足A）p-next=NULL B）p=NULL C）p-next=head D）p=head20、已知数据表A中每个元素距其最终位置不远，为节省时间，应采用的算法是（B）A）堆排序 B）直接插入排序 C）快速排序 D）直接选择排序21、最简单的交换排序方法是（D）A）快速排序 B）选择排序 C）堆排序 D）冒泡排序22、栈和队列通常采用的存储结构是 【链式存储和顺序存储】。23、冒泡排序算法在最好的情况下的n个元素交
