北京化工大学软件技术基础考试复习重点.doc

《北京化工大学软件技术基础考试复习重点.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、第一章算法算法是解决某个特定问题的一种方法或一个过程。算法的特性可行性；确定性；有穷性；输入；输出数据结构：简单地说，数据结构(DataStructure)是相互Z间存在一种或多种特定关系的数据元索的集合数据结构与算法的关系：确定使用的数据结构，并在此基础上设计对此数据结构实施各种操作的算法；算法描述语言是一种页向人而非机器的算法描述T具，其他的描述工具还有：传统流稈图N・S结构化流稈图伪代码算法设计基本方法列举法归纳法递推法递归法减半递推技术冋溯法递推关系往往是归纳分析的结果；递归的基础是归纳法；递归分类頁接递归；间接递归lvoidhanoi(intn，char

2、A,charB,charC){2if(n==l)3thenmove(l,A,C);4else{5hanoi(n-l,A,C,B);6move(n,A,C);7hanoi(n-l,B,A,C);8}9}voidtrial(inti’intn){/*进入木函数时，在nxn棋盘前已放置了互不攻击的i-1个棋了。现从第i行起示示续棋了选择合适的位置，当i>n时，求得合法布局并输出。*/if(i>n)then输出棋盘的当前布局；elsefor(j=1;jv二n;++j){在第i行第j列放一个棋了；if(当前布局合法)trialfi+l,n);移走第i行第j列的棋子；}}算法

3、时间复杂度指执行算法所需要的计算工作量。算法空间复杂度指执行算法所需要的内存空间。算法评价标准正确性可读性健壮性时间与空间效率第二章数据结构线性表定义线性表是由n(n^O)个类型相同的数据元素组成的有限序列。通常表示成下列形式：L=(al,a2,…J其中L为线性表名称,ai为纟ft成该线性表的数据元素；顺序存储结构线性表的顺序存储结构是指用一组连续的存储单元依次存储线性表屮的毎个数据元素。线性表的逻辑结构与存储结构(物理结构)一致；线性表屮所有元素所占存储空间是连续的线性表屮各元素按逻辑顺序依次存放；丿帧序线"性表插入在顺序线性表SL第idx个数据元素之前插入数据

4、元素elemvoidinsert(SeqListSL,intidx,ElemTypeelem){//检杳是否有剩余空间if(SL.Iength==MAX_LIST_SIZE)returnERROR;//检查idx值是否合法if(idx<011idx>SL.Iength)returnERROR;//将线性表笫i个元素Z后的所有元素向后移动for(j=SL.Iength-l;j>=idx-l;j--)SL.elems[j+l]=SL.elemsU]；//将新元素的内容放入线性表的第i个位置，SL.elems[idx-l]=elem;SL.Iength++;}顺序线性表

5、删除删除顺序线性表第idx个数据元素ElemTypedelete(SeqListSL,intidx){//检测线性表是否为空if(isEmpty(SL))returnERROR;//检查idx值是否合法if(idx<011i>=SL.Iength)returnERROR;//将欲删除的数据元素内容保存在变量elem屮ElemTypeelem=SL.elems[i-l];//将线性表第i+1个元索ZfJ的所有元索向前移动for(j=i;j

6、存储结构链式存储结构指用一-组任意的存储单元(可以连续，也可以不连续)存储线性表屮的数据元素，而数据元素Z间的逻辑关系由存储结点的指针域来确定。线性表屮的数据元素在存储单元屮的存放顺序与逻辑顺序不一定一致；访问数据元素时,只能由头指针进入链表，并通过结点的指针域向后扫描其余结点链式线性表插入在链表LL屮第idx个数据元素之前插入数据元素elemintinsert(LinkedListLL,intidx,ElemTypeelem){linode*p,s;intj;//开辟新结点空间s=(llnode*)malloc(sizeof(llnode));讦(s==NULL

7、)returnERROR;s->data=elem;if(idx<011i>length(LL))returnERROR;//寻找第i-1个结点for(p=LL.headj=O;p&&jnext;j++);//W新结点插入到链表中sonext=p->next;p・>next=s;returnOK;}链式线性表删除删除链农LL屮的第idx个数据元素,并返冋其值ElemTypedelete(LinkedListLL,intidx){linode*p,s;intj；if(idx<011idx>length(LL))returnERROR;//寻找第i

8、-1个结点