搜索
第一章绪论一、基本内容数据、数据元素、数据对象、数据结构、存储结构和数据类型等概念术语的确定含义、抽象数据类型的定义、表示和实现方法、描述算法的类C语言、算法设计的基本要求。二、学习要点1、熟悉各名词、术语的含义，掌握基本概念，特别是数据的逻辑结构和存储结构之间的关系。分清哪些是逻辑结构的性质，哪些是存储结构的性质。2、了解抽象数据类型的定义、表示和实现方法。3、熟悉类C语言的书写规范，特别要注意值调用和引用调用的区别，输入、输出的方式以及错误处理方式。4、理解算法五个要素的确切含义。1.1基础知识一、填空题1、数据的逻辑结构包括①，②，③和④四种类型，树型结构和图型结构合称为⑤，数据的存储结构即物理结构包括：⑥，⑦等两种基本类型。2、在线性结构中元素之间存在①关系，树形结构中元素间存在②关系，图形结构中元素间存在③关系。3、一个数据结构用二元组表示时，它包括①集合D和D上②的集合S。4、一个算法应具有①，②，③，④和⑤这五个特性。5、在图形结构中，每个节点的前驱节点和后继节点可以有①个。6、一个抽象数据类型用三元组（D，S，P）表示时，D是①，S是②，P是③。7、数据元素在计算机中的映象是①。8、算法的设计取决于①，算法的实现取决于②。二、选择题1、数据元素是数据的单位。(A)基本(B)最小2、使用指针表示数据元素之间逻辑关系的存储结构是。(A)顺序结构(B)链式结构(C)树状结构(D)图状结构3、以下____术语与数据的存储结构无关。(A)线索二叉树(B)双向链表(C)栈(D)哈希表4、以下____术语与数据的逻辑结构无关。(A)线性结构(B)链式结构(C)树型结构(D)网状结构5、指出下列叙述____不属于算法的特性。(A)有穷性(B)复杂性(C)可行性(D)确定性6、以下数据结构中____是线性结构。(A)队列(B)有向图(C)树(D)哈夫曼树解答：一、填空题1、①线性②集合③树④图或网⑤非线性结构⑥顺序存储⑦链式存储2、①1：1②1：n③m：n3、①数据元素②关系4、①有穷性②确定性③可行性④输入⑤输出5、①多个6、①数据对象②D上的关系集合③对D的基本操作集合7、①元素或结点8、①数据（逻辑）结构②采用的存储结构二、选择题1、A2、B3、C4、B5、B6、Al.2应用知识1、什么是算法？算法的特性是什么？算法设计的要求是什么?解答:（略）2、设有数据结构USER_STRU表示如下：USER_STRU=（D，S）D={a1，a2，…，a9}S={a1，a3，a1，a8，a2，a3，a2，a4，a2，a5，a3，a9，a5，a6，a8，a9，a9，a7，a4，a7，a4，a6}画出这个数据结构的图示，并确定其类型。解答：该结构的图示如下，该结构为图形结构。3、设有数据结构USER_STRU表示如下：USER_STRU=（D，S）D={a1，a2，…，a9}S={a1，a2，a1，a3，a3，a4，a3，a6，a6，a8，a4，a5，a6，a7，a8，a9}画出这个数据结构的图示，并确定其类型。解答：该结构的图示如下，该结构为树形结构。a2a4a5a6a7a3a1a9a8a1a2a3a6a4a8a7a54、影响高级语言程序运行消耗时间的因素有哪些？解答：主要有以下因素：(1)算法选用的策略；(2)问题的规模；(3)书写程序的语言；(4)编译程序产生的机器代码质量；(5)机器执行指令的速度。5、选择解决某种问题的最佳数据结构的标准是什么?解答：一般有两条标准：(1)所需的存储空间量；(2)算法所需要的时间；而算法所需要的时间又包括以下几点：(1)程序运行时所需要的数据总量；(2)源程序进行编译所需要的时间；(3)计算机执行每条指令所需要的时间；(4)程序中的指令重复执行的次数，而本条正是讨论算法中的重点内容。6、设三个函数f,g,h分别为f(n)=100n3+n2+1000,g(n)=25n3+5000n2,h(n)=n1.5+5000nlgn请判断下列关系是否成立：(1)f(n)=O(g(n))(2)g(n)=O(f(n))(3)h(n)=O(n1.5)(4)h(n)=O(nlgn)解答：（1）成立；（2）成立；（3）成立；（4）不成立。7、设n为正整数，利用大O记号，将下列程序段的执行时间表示为n的函数。(1)i=1;k=0;while(in){k=k+10*i;i++;}(2)i=0;k=0;do{k=k+10*i;i++;}while(in);(3)i=1;j=0;while(i+j=n){if(ij)j++;elsei++;}(4)x=n;//n1while(x=(y+1)*(y+1))y++;(5)x=91;y=100;while(y0)if(x100){x=x-10;y--;}elsex++;解答：（1）为T(n)=O(n)；（2）为T(n)=O(n)；（3）为T(n)=O(n)（4）由x=n且x的值在程序中不变，又while的循环条件(x=(y+1)*(y+1))可知：当(y+1)*(y+1)刚超过n的值时退出循环。由(y+1)*(y+1)n得：yn^0.5-1所以，该程序段的执行时间为：向下取整(n^0.5-1)（5）为T(n)=O(1)8、算法的时间复杂度仅与问题的规模相关吗?解答：算法的时间复杂度不仅与问题的规模相关，还与输入实例中的初始状态有关。但在最坏的情况下，其时间复杂度就是只与求解问题的规模相关的。我们在讨论时间复杂度时，一般就是以最坏情况下的时间复杂度为准的。9、按增长率由小至大的顺序排列下列各函数：2100,(3/2)n，(2/3)n，nn,n0.5,n!，2n，lgn,nlgn,n(3/2)解答：常见的时间复杂度按数量级递增排列,依次为:常数阶0(1)、对数阶0(log2n)、线性阶0(n)、线性对数阶0(nlog2n)、平方阶0(n2)、立方阶0(n3)、k次方阶0(nk)、指数阶0(2n)。先将题中的函数分成如下几类：常数阶：2100对数阶：lgnK次方阶：n0.5、n(3/2)指数阶(按指数由小到大排)：nlgn、(3/2)n、2n、n!、nn注意：(2/3)^n由于底数小于1，所以是一个递减函数，其数量级应小于常数阶。根据以上分析按增长率由小至大的顺序可排列如下：(2/3)n2100lgnn0.5n(3/2)nlgn(3/2)n2nn!nn10、设有两个算法在同一机器上运行，其执行时间分别为100n2和2n,要使前者快于后者，n至少要多大?解答：要使前者快于后者，即前者的时间消耗低于后者，即：100n22n求解上式，可得n=15第二章线性表一、基本内容线性表的逻辑结构定义、抽象数据类型定义和各种存储结构的描述方法；在线性表的两类存储结构（顺序的和链式的）上实现基本操作、稀疏多项式的抽象数据类型定义、表示和加法的实现。二、学习要点1、了解线性表的逻辑结构特性是数据元素之间存在着线性关系，在计算机中表示这种关系的两类不同的存储结构是顺序存储结构和链式存储结构。用前者表示的线性表简称为顺序表，用后者表示的线性表简称为链表。2、熟练掌握这两类存储结构的描述方法，如一维数组中一个区域[i…j]的上、下界和长度之间的变换公式(L=j-i+1，i=j-L+1，j=i+L-1)，链表中指针p和结点*p的对应关系(结点*（p-next)是结点*p的后继等)，链表中的头结点、头指针和首元结点的区别及循环链表、双向链表的特点等。链表是本章的重点和难点。扎实的指针操作和内存动态分配的编程技术是学好本章的基本要求。3、熟练掌握线性表在顺序存储结构上实现基本操作：查找、插入和删除的算法。4、熟练掌握在各种链表结构中实现线性表操作的基本方法，能在实际应用中选用适当的链表结构。了解静态链表，能够加深对链表本质的理解。2.1基础知识一、填空题1、对于双向循环链表，在两个结点间插入一个新结点时需修改的指针共有①个，单链表为②个。2、当向一个顺序表插入一个元素时，被插入元素之后的所有元素均需向①移动一个位置，元素的移动顺序是从②向③依次移动。3.要从一个顺序表删除一个元素时，被删除元素之后的所有元素均需向①移动一个位置，元素的移动顺序是从②向③依次移动。4、在一个循环单链表中，表尾结点指针域与表头指针值①。5、在线性表的顺序存储中，元素之间的逻辑关系是通过①表示的；在线性表的链接存储中，元素之间的逻辑关系是通过②表示的。6、在双向链表中，每个结点含有两个指针域，一个指向①结点，另一个指向②结点。7、在一个单链表中删除p所指结点时，应执行下列操作:q=p-next;p-data=p-next-data;p-next=①;free(q);8、若要在一个不带表头结点的单链表的首结点*p之前插入一个*s结点时，可执行下列操作：s-next=①；p-next=S；t=p-data；p-data=②；s-data=③；9、根据线性表的链式存储结构中每个结点所含指针的个数，链表可分为①和②；而根据指针的联接方式，链表又可分为③和④。10、单链表表示法的基本思想是利用①表示结点间的逻辑关系。11、当对一个线性表经常进行的是存取操作，而很少进行插入和删除操作时，则采用①存储结构为宜，相反，当经常进行的是插入和删除操作时，则采用②存储结构为宜。12、在单链表中设置头结点的作用是①。13、顺序表中逻辑上相邻的元素，物理位置①紧邻，单链表中逻辑上相邻的元素，物理位置②紧邻。14、一个采用了顺序存储结构的线性表，其长度为30，若在第7个元素前插入一个元素，需要移动①个元素，若接着又将第12个元素删除，那么需要移动②个元素。二、选择题1、在一个长度为n的顺序表中删除第i个元素(1≤i≤n)时，需向前移动个元素。(A)n-i(B)n-i+1(C)n-i-1(D)i2、用链表表示线性结构的优点在于。(A)便于随机存取(B)便于插入和删除(C)节省空间(D)元素的物理顺序和逻辑顺序一致3.在双向循环链表中，在p所指的结点之后插入s指针所指的结点，其操作是。(A)p-next=s；s-prior=p；(p-next)-prior=s；s-next=p-next；(B)s-prior=p；s-next=p-next；p-next=s；p-next-prior=s；(C)p-next=s；p-next-prior=s；s-prior=p；s-next=p-next；(D)s-prior=p；s-next=p-next；p-next-prior=s；p-next=s；4、设单链表中指针p指向结点m，若要删除m之后的结点(假定存在)，则需修改指针的操作为。(A)p-next=p-next-next；(B)p=p-next；(C)p=p-next-next；(D)p-next=p；5、线性表采用链式存储时，其存储单元的地址。(A)必须是连续的；(B)一定是不连续的；(C)部分地址必须是连续的；(D)连续与否均可以；6、在一个单链表中，已知*q结点是*p结点的前趋结点，若在*q和*p之间插入*s结点，则须执行。(A)s-next=p-next；p-next=s；(B)q-next=s；s-next=p；(C)p-next=s-next；s-next=p；(D)p-next=s；s-next=q；7、线性表是。(A)一个有限序列，可以为空；(B)一个有限序列，不可以为空；(C)一个无限序列，可以为空；(D)一个无限序列，不可以为空；8、在一个长度为n的顺序表中向第i个元素(0i≤n+1)之前插入一个新元素时，需向后移动个元素。(A)n-i(B)n-i+1(C)n-i-1(D)i9、下面关于线性表的叙述中，错误的是。(A)若采用顺序结构，需占用连续存储空间(B)若采用顺序结构，便于进行插入和删除(C)若采用链式结构，不必占用连续存