搜索
CopyRight@2010SWPUNCREAllRightsReserved二级公共基础知识2010年9月等级考试辅导考试方式1.公共基础的考试方式为笔试，与VB、C的笔试部分合为一张试卷。公共基础部分占全卷的30分。2.公共基础知识有10道选择题和5道填空题。算法与数据结构程序设计基础软件工程基础数据库设计基础35%5%30%30%分值分布学习方法•记忆和理解基本概念与基本原理•多做练习•适当记忆一些名词•与所学的程序设计知识结合起来，以增加对知识的理解能力算法定义特征－可行性、确定性、拥有足够的情报复杂度－时间复杂度和空间复杂度数据结构数据的逻辑结构数据的存储结构数据的运算线性结构→线性表→栈和队列非线性结构→树形结构(二叉树、树的遍历)顺序结构链式结构索引结构散列结构插入删除查找－顺序查找、二分法查找修改第一章算法与数据结构（占公基35%）1.1算法•什么是算法？•算法是指解题方案的准确而完整的描述•算法的4个特性•可行性•确定性•有穷性•拥有足够的情报(拥有输入和输出)•算法的两个基本要素•对数据对象的运算和操作•算法的结构(顺序结构、选择结构、循环结构)真题•[2005.4]问题处理方案的正确而完整的描述称为______。•[2008.4]算法的有穷性是指（）。A）算法程序的运行时间是有限的B）算法程序所处理的数据量是有限的C）算法程序的长度是有限的D）算法只能被有限的用户试用算法A算法的复杂度★•什么是算法的复杂度？•算法的复杂度是衡量算法好坏的度量，分为时间复杂度和空间复杂度•什么是算法的时间复杂度？•指执行算法所需要的计算工作量，即算法执行过程中所需要的基本运算次数。•什么是算法的空间复杂度？•指执行算法所需要的内存空间。一般来说，求解同一个问题有若有多种算法，则执行时间短的算法效率高，占用存储空间少的算法较好。但是算法的时间开销和空间开销往往是相互制约的，对高时间效率和低存储占用的要求只能根据问题的性质折中处理[2007.9]•下列叙述中正确的是()A）程序执行的效率与数据的存储结构密切相关B）程序执行的效率只取决于程序的控制结构C）程序执行的效率只取决于所处理的数据量D）以上三种说法都不对A算法的设计要求•好的算法应达到4个目标•正确性：算法应该满足具体问题的需求，正确反映求解问题对输入、输出和加工处理等方面的需求•可读性•健壮性：当输入非法数据时，算法应该能够适当做出反应或进行处理，输出表示错误的信息并终止执行。•时间效率和存储占用量算法定义特征－可行性、确定性、拥有足够的情报复杂度－时间复杂度和空间复杂度数据结构数据的逻辑结构数据的存储结构数据的运算线性结构→线性表→栈和队列非线性结构→树形结构(二叉树、树的遍历)顺序结构链式结构索引结构散列结构插入删除查找－顺序查找、二分法查找修改第一章算法与数据结构1.2数据结构的基本概念•什么是数据结构？•数据：凡是能被计算机识别、存取和加工处理的符号、字符、图形、图像、声音、视频信号、程序等一切信息。•结构：数据之间的逻辑关系。•数据结构指相互有关联的数据元素的集合。•数据、数据元素之间的关系。•数据元素是数据的基本单位。数据结构数据的逻辑结构数据的存储结构数据的运算线性结构→线性表→栈和队列非线性结构→树形结构(二叉树、树的遍历)顺序结构链式结构索引结构散列结构插入删除查找－顺序查找、二分法查找排序数据的逻辑结构•什么是数据的逻辑结构？•数据的逻辑结构是指数据元素之间的逻辑关系，与数据的存储无关，是独立于计算机的。•数据的逻辑结构可分成2类•线性结构•非线性结构春夏秋冬父亲儿子女儿数据的存储结构•什么是数据的存储结构？•数据的存储结构又称为物理结构，是指数据元素及其关系在计算机内存中的表示，即数据的逻辑结构在计算机存储空间中的存放形式。•数据的存储结构可分为哪4类？•顺序结构、链式结构、索引结构、散列结构•数据的存储结构与逻辑结构的关系•同一逻辑结构可以采用不同的存储结构真题•[2005.4]数据的存储结构是指______。A)存储在外存中的数据B)数据所占的存储空间量C)数据在计算机中的顺序存储方式D)数据的逻辑结构在计算机中的表示D真题•[2005.9]下列叙述中正确的是______。A）一个逻辑数据结构只能有一种存储结构B）数据的逻辑结构属于线性结构，存储结构属于非线性结构C）一个逻辑数据结构可以有多种存储结构，且各种存储结构不影响数据处理的效率D）一个逻辑数据结构可以有多种存储结构，且各种存储结构影响数据处理的效率D数据结构数据的逻辑结构数据的存储结构数据的运算线性结构→线性表→栈和队列非线性结构→树形结构(二叉树、树的遍历)顺序结构链式结构索引结构散列结构插入删除查找－顺序查找、二分法查找排序1.3线性表及其顺序存储结构•线性表必须满足的3个条件。•有且只有一个根节点a1，它无前件；•有且只有一个终点an，它无后件；•除了起点和终点，其余结点只有一个前件，也只有一个后件。……ana2a11.3线性表的顺序存储结构•线性表顺序存储结构的2个特点元素n…元素i…元素2元素1起始位置LoLo+mLo+(i-1)*m每个元素所占用的存储单元大小Lo+(n-1)*m1、所有元素所占的存储空间是连续的2、各元素在存储空间中是按逻辑顺序存放的结点个数n称为线性表的长度，当n=0时，称为空表顺序表移动后…an…ai+1aiaiai-1…a1插入后…an…ai+1aieai-1…a11n插入前i-1i+1…an…ai+1aiai-1…a1插入e→线性表的顺序存储结构的插入运算线性表的顺序存储结构的插入运算•插入运算的3步骤•判断是否上溢；•空出第i位位置；•插入。•插入算法的效率(数据元素的移动次数)•最好情况：•最坏情况：•平均情况：0nn/2看数组下标是否越界1n删除前i-1i+1删除ai→…an…ai+1aiai-1…a1移动删除后…an…ai+1ai-1…a1线性表的顺序存储结构的删除运算线性表的顺序存储结构的删除运算•删除运算(要删除第i个元素)•判断是否下溢•从第i+1个元素开始向前移动直到最后一个元素•元素个数减一•删除算法的时间复杂度(数据元素的移动次数)•最好情况：•最坏情况：•平均情况：0n-1(n-1)/21.4栈和队列•栈是一种特殊的线性表，是限定在一端进行插入和删除的线性表，FILO。•栈顶和栈底•入栈和出栈aaa…a入栈出栈栈顶n-1n21栈底•入栈•出栈（退栈）•取栈顶元素考点14栈的基本运算真题•[2006.4]按照“后进先出”原则组织数据的数据结构是A）队列C）双向链表D）二叉树•[2005.9]下列关于栈的描述正确的是______。A）在栈中只能插入元素而不能删除元素B）在栈中只能删除元素而不能插入元素C）栈是特殊的线性表，只能在一端插入或删除元素D）栈是特殊的线性表，只能在一端插入元素，而在另一端删除元素[2005.4]下列关于栈的描述中错误的是______。A)栈是先进后出的线性表C)栈具有记忆作用D)对栈的插入与删除操作中，不需要改变栈底指针•下列关于栈的叙述正确的是（）。A）栈按“先进先出”组织数据C）只能在栈底插入数据D）不能删除数据√B）栈B)栈只能顺序存储B）栈按“先进后出”组织数据√√√•[2008.9]一个栈的初始状态为空，现将元素1、2、3、4、A、B、C、D、E依次入栈，然后再次出栈，则元素出栈的顺序是______。A）1234ABCDEC）ABCDE12345D）54321EDCBA•[2009.3]支持子程序调用的数据结构是（）（A）栈（B）树（C）队列（D）二叉树√B）EDCBA54321√队列•队列是一种特殊的线性表，允许在一端进行插入操作，在另一端进行删除操作，FIFO(LILO)。•队头和队尾•入队和出队出队←a1a2…an←入队↑队头↑队尾队列：可能出现假溢出现象解决：采用循环队列（依然为顺序存储）循环队列及其运算•什么是循环队列•循环队列是队列的一种顺序存储结构形式，在队列最后一个位置已被使用，而第一个位置空闲的情况下，仍然能进行入队操作。•循环队列3种基本运算•入队、出队、读取数据元素•判断循环队列是否为空(满)的条件•循环队列为空：s=0•循环队列为满：s=1且front=rear•(s=0队列为空，s=1队列非空)J65J543210rearfront真题•[2008.4]设某循环队列的容量为50，头指针front=5（指向队头元素的前一位置），尾指针rear=29（指向队尾元素），则该循环队列中共有个元素。•[2008.9]下列叙述中正确的是。A）循环队列有队头和队尾两个指针，因此循环队列是非线性结构B）在循环队列中，只需要队头指针就能反映队列中元素的动态变化情况C）在循环队列中，只需要队尾指针就能反映队列中元素的动态变化情况D）循环队列中元素的个数是由队头指针和队尾指针共同决定24√数据结构数据的逻辑结构数据的存储结构数据的运算线性结构→线性表→栈和队列非线性结构→树形结构(二叉树、树的遍历)顺序结构链式结构索引结构散列结构插入删除查找－顺序查找、二分法查找排序1536元素21400元素11346元素3∧元素413451.5线性表的链式存储结构数据域指针域•什么是结点？结点由哪两部分组成？•链式存储结构方式有那些特点？•结点的储存不一定连续•各结点之间的存储顺序与数据元素的逻辑关系可以不一致•链式存储适合于线性结构也适合于非线性结构hh空指针链表1346元素31536………1536元素21400………∧元素413461400元素11345指针存储内容存储地址1536元素21400元素11346元素3∧元素41345hh1.5链式存储结构线性链表•什么是线性链表？•线性表的链式存储结构•线性链表有哪些基本运算？•查找•插入•删除abd∧chppp查找结束线性链表的查找操作abd∧ch线性链表的插入操作Mab∧dchPQ×线性链表的删除操作abd∧chab∧dchPQ×循环链表a1ana2…h双向链表a1∧a2an∧…ha1a2∧ana3…h线性链表真题•[2005.4]下列对于线性链表的描述中正确的是______。A)存储空间不一定是连续，且各元素的存储顺序是任意的B)存储空间不一定是连续，且前件元素一定存储在后件元素的前面C)存储空间必须连续，且前件元素一定存储在后件元素的前面D)存储空间必须连续，且各元素的存储顺序是任意的A真题•[2006.9]数据结构分为线性结构和非线性结构，带链的队列属于________。•[2007.9]线性表的存储结构主要分为顺序存储结构和链式存储结构。队列是一种特殊的线性表，循环队列是队列的____________存储结构。•[2008.9]下列叙述中正确的是。A）顺序存储结构的存储一定是连续的，链式存储结构的存储空间不一定是连续的B）顺序存储结构只针对线性结构，链式存储结构只针对非线性结构C）顺序存储结构能存储有序表，链式存储结构不能存储有序表D）链式存储结构比顺序存储结构节省存储空间线性结构顺序A数据结构数据的逻辑结构数据的存储结构数据的运算线性结构→线性表→栈和队列非线性结构→树形结构(二叉树、树的遍历)顺序结构链式结构索引结构散列结构插入删除查找－顺序查找、二分法查找排序1.6树与二叉树树•1.树是一种简单的非线性结构，所有元素之间具有明显的层次特性。•2.在树结构中，每一个结点只有一个前件（驱），称为父结点，没有前件（驱）的结点只有一个，称为树的根结点，简称树的根。每一个结点可以有多个后件（继），称为该结点的子结点。没有后件（继）的结点称为叶子结点。•3.在树结构中，一个结点所拥有的后件（继）的个数称为该结点的度，所有结点中最大的度称为树的度。树的最大层次称为树的深度。树ABCDEFGHIJKLM根结点父结点结点D的子结点叶子结点该树的度为3第一层第二层第三层第四层结点B的两棵子树度为3度为2该树的深度为4二叉树•二叉树的特点：（1）非空二叉树只有一个根结点；（2）每一个结点最多有两棵子树，且分别称为该结点的左子树与右子树。a