搜索
数据结构习题习题一一、选择题1、数据结构是一门研究非数值计算的程序设计问题中的操作对象以及它们之间的（B）和运算的学科。A．结构B．关系C．运算D．算法2、在数据结构中，从逻辑上可以把数据结构分成（C）。A．动态结构和静态结构B．紧凑结构和非紧凑结构C．线性结构和非线性结构D．逻辑结构和存储结构3、线性表的逻辑顺序和存储顺序总是一致的，这种说法（B）。A．正确B．不正确C．无法确定D．以上答案都不对4、算法分析的目的是（C）。A．找出算法的合理性B．研究算法的输人与输出关系C．分析算法的有效性以求改进D．分析算法的易懂性二、填空题1、数据是信息的载体，是对客观事物的符号表示，它能够被计算机识别、存储、加工和处理，数据是对能够有效的输人到计算机中并且能够被计算机处理的符号的总称。例如，数学中所用到的整数和实数，文本编辑所用到的字符串等。2、数据元素是数据的基本单位，有些情况下也称为元素、结点、顶点、记录等。3、数据项是数据不可分割的最小单元，是具有独立含义的最小标识单位。例如构成一个数据元素的字段、域、属性等都可称之为_数据项。4、简而言之，数据结构是数据之间的相互关系，即数据的组织形式。5、数据的逻辑结构是指数据之间的逻辑关系。逻辑结构是从逻辑关系上描述数据，它与具体存储无关，是独立于计算机的。因此逻辑结构可以看作是从具体问题抽象出来的数学模型。6、数据的存储结构指数据元素及其关系在计算机存储器内的表示。存储结构是逻辑结构在计算机里的实现，也称之为映像。7、数据的运算是指对数据施加的操作。它定义在数据的逻辑结构之上，每种逻辑结构都有一个数据的运算。常用的有：查找、排序、插人、删除、更新等操作。8、数据逻辑结构可以分为四种基本的类型，集合结构中的元素除了仅仅只是同属于一个集合_，不存在什么关系。9、数据逻辑结构的四种基本类型中，线性结构_中的元素是一种一对一的关系，这种结构的特征是：若结构是非空集，则有且只有一个开始结点和一个终端结点，并且所有结点最多只能有一个直接前驱和一个直接后继。10、数据逻辑结构的四种基本类型中，树形结构中的元素是一种一对多的关系。11、图型结构或图状结构是一种多对多的关系。在这种逻辑结构中，所有结点均可以有多个前驱和多个后继。12、有时也可将树型结构、集合和图型结构称为非线性结构，这样数据的逻辑结构就可以分为线性结构和非线性结构两大类。13、顺序存储方式是指逻辑上相邻的结点被存储到物理上也相邻的存储单元中。这种存储结构只存储结点的数值，不存储结点之间的关系，结点之间的关系是通过存储单元的相邻关系隐含的表示出来的。14、链接存储方式是种存储方法，不要求逻辑上相邻的结点在物理上也相邻，即数据元素可以存储在任意的位置上。15、索引存储方式又可以分为稠密索引和稀疏索引。若每个结点在索引表中都有一个索引项，则该种索引存储方式称为稠密索引_；若一组结点在索引表中只对应一个索引项，则索引存储方式称为稀疏索引。在稠密索引中，索引项的地址指示结点所在的位置，而稀疏索引中，索引项的地址指示一组结点的起始位置。16、散列存储方式是利用结点关键字的值直接计算出该结点存储单元地址，然后将结点按某种方式存人该地址的一种方法。17、所谓算法（Algorithm）是对特定问题求解方法和步骤的一种描述，它是指令的一组有限序列，其中每个指令表示一个或多个操作。18、算法的有穷_性是指算法必须能够在执行有限个步骤之后结束，并且每个步骤都必须在有穷的时间内完成。19、算法的确定性是指算法中的每一个步骤必须是有明确定义的，不允许有模棱两可的解释，也不允许有多义性。并且，在任何条件下，算法只能有惟一的一条执行路径，即只要输人是相同的就只能得到相同的输出结果。20、算法的可行性又称为算法的能行性，是指算法中描述的操作是可以通过已经实现的基本运算执行有限_次来实现，即算法的具体实现应该能够被计算机执行。21、判断一个算法的好坏主要以下几个标准：正确性，可读性_、健壮性、效率。22、算法分析是对一种算法所消耗的计算机资源的估算，其中包括计算机运行时间的长短和所占据空间的大小。23、空间复杂度（SPaceComPlexity）也是度量一个算法好坏的标准，它所描述的是算法在运行过程中所占用存储空间的大小。三、判断题1、顺序存储方式只能用于存储线性结构。（×）树型结构也可以用顺序方式进行存储。2、数据元素是数据的最小单位。（×）数据元素是数据的基本单位，数据项是数据的最小单位。3、算法可以用不同的语言描述，如果用C语言或PASCAL语言等高级语言描述，则算法实际上就是程序了。（×）算法用各种计算机语言描述表现为一个程序，但是不等于程序，程序逻辑不一定能满足有穷性。4、数据结构是带有结构的数据元素的集合。（对）5、数据的逻辑结构是指各元素之间的逻辑关系，是用户根据需要而建立的。（对）6、数据结构、数据元素、数据项在计算机中的映像分别称为存储结构、结点、数据域。（对）7、数据的物理结构是指数据在计算机中实际的存储形式。（对）8、具有存取任一元素的时间相等这一特点的存储结构称为随机存取结构。（对）四、综合题1、用大O形式表示下面算法的时间复杂度：for（i=0；i＜m；i十十）for（j=0；j＜n；j＋＋）A[i][j]=i*j；O(m×n)。2、写出下面算法的时间复杂度：i＝0；s=0；while(s＜n）｛i++;s+=i;｝O(n)3、写出以下算法的时间复杂度：for（i＝0;i＜m;i＋＋）for（j＝0;j＜t;j＋＋）c[i][j]=0；for（i=0；i＜m；i＋＋）for（j=o;jt;j++）for（k=0；k＜n；k＋＋）c［i］［j］＋＝a［i］［k］*b[k][j];O(m×n×t)。4、写出下面算法的时间复杂度：i=1;while（i＜＝n）i=i*3;log3(n)。5、求下面函数中各条语句的频度和算法的时间复杂度：prime（intn）｛inti＝2；while((n％i）！=0＆＆i＜sqrt(n))i++;if（i＞sqrt(n))printf（”％disaprimenumber.＼n”，n）；elseprintf（”％disnotaprimenumber.＼n”，n）；｝O(n)习题二一、选择题1．在一个长度为n的顺序表中删除第i个元素（0＜in）时，需要向前移动(A)个元素。A．n-iB．n-i+1C．n-i+1D．i+12．从一个具有n个元素的线性表中查找其值等于x的结点时，在查找成功的情况下，需平均比较(C)个元素结点。A．n/2B．nC．(n-1)/2D．(n+1)/23．对一个具有n个元素的线性表，建立其单链表的时间复杂度为(A)。A．O(n)B．O(1)C．O(n2）D．O（long2n）4．线性表采用链式存储时，其地址(D)。A．必须是连续的B．一定是不连续的C．部分地址必须连续D．连续与否均可以5．在一个具有n个结点的有序单链表中插人一个新的结点，使得链表仍然有序，该算法的时间复杂度是(D)。A．O（long2n）B．O（l）C．O（n2）D．O（n）6．线性表是(A)。A．一个有限序列，可以为空B．一个有限序列，不可以为空C．一个无限序列，可以为空D．一个无限序列，不可以为空7．在一个长度为n的顺序表中，向第i个元素（0一1＜n＋1）之前捕人一个新元素时，需要向后移动(B)个元素。A．n-iB．n-i＋1C．n－i－1D．i＋18．如果某链表中最常用的操作是取第i个结点及其前驱，则采用(D)存储方式最节省时间。A．单链表B．双向链表C．单循环链表D．顺序表9．一个顺序存储线性表的第一个元素的存储地址是90，每个元素的长度是2，则第6个元素的存储地址是（B）。A．98B．100C．102D．10610．下列排序方法中，某一趟结束后未必能选出一个元素放在其最终位置上的是(C)。A．堆排序B．冒泡排序C．直接插人排序D．快速排序11．对线性表进行二分查找时，要求线性表必须（C）。A．以顺序方法存储B．以链接方法存储C．以顺序方法存储，且结点接关键字有序排列D．以链接方法存储，且结点接关键字有序排列12．在顺序存储的线性表（a1……an）中，删除任意一个结点所需移动结点的平均移动次数为(C)A．nB．n／2C．(n-1)/2D．（n＋l）/213．在线性表的下列存储结构中，读取元素花费的时间最少的是（D）。A．单链表B．双链表C．循环链表D．顺序表14．若某链表中最常用的操作为在最后一个结点之后插入一个结点和删除最后一个结点，则采用（D）存储方式最节省时间。A．双链表B．单链表C．单循环链表D．带头结点的双循环链表二、填空题1．线性表（LinearList）是最简单、最常用的一种数据结构。线性表中的元素存在着___一对一的相互关系。2．线性表中有且仅有一个开始结点，表中有且仅有一个终端结点，除开始结点外，其他每个元素有巨仅有一个直接前驱，除终端结点外，其他每个元素有且仅有一个直接后继3．线性表是n（n=0）个数据元素的_有限序列。其中n为数据元素的个数，定义为线性表的长度。当n为零时的表称为空表。4．所谓顺序表（SequentialLISt）是线性表的顺序存储结构，它是将线性表中的结点按其逻辑顺序依次存放在内存中一组连续的存储单元中，使线性表中相邻的结点存放在地址相邻的存储单元中。5．单链表不要求逻辑上相邻的存储单元在物理上也一定要相邻。它是分配一些任意的存储单元来存储线性表中的数据元素，这些存储单元可以分散在内存中的任意的位置上，它们在物理上可以是一片连续的存储单元，也可以是不连续的。因此在表示线性表这种数据结构时，必须在存储线性表元素的同时，也存储线性表的逻辑关系。6．线性表的链式存储结构的每一个结点（Node）需要包括两个部分：一部分用来存放元素的数据信息，称为结点的数据域；另一部分用来存放元素的指向直接后继元素的指针(即直接后继元素的地址信息)，称为指针域或链域。7．线性链表的逻辑关系是通过每个结点指针域中的指针来表示的。其逻辑顺序和物理存储顺序不再一致，而是一种非顺序存储结构，又称为非顺序映像。8．如果将单链表最后一个结点的指针域改为存放链表中的头结点的地址值，这样就构成了循环链表。9．为了能够快速地查找到线性表元素的直接前驱，可在每一个元素的结点中再增加一个指向其前驱的指针域，这样就构成了双向链表。10．双向链表某结点的指针P，它所指向结点的后继的前驱与前驱的后继都是p所指向的结点本身。11．在单链表中，删除指针P所指结点的后继结点的语句是P-next=p-next-next_。12．在双循环链表中，删除指针P所指结点的语句序列是P-prior-next＝p-next及P-next-prior=P-prior_。13．单链表是线性表的链接存储表示。14．可以使用双链表表示树形结构。15．向一个长度为n的向量的第i个元素(l≤i≤n+1）之前插人一个元素时，需向后移动n-i+1个元素。16．删除一个长度为n的向量的第i个元素（l≤i≤n）时，需向前移动n-i个元素。17．在单链表中，在指针P所指结点的后面插人一个结点S的语句序列是S-next=P-next;P-next=S18．在双循环链表中，在指针P所指结点前插人指针S所指的结点，需执行语句p-prior-next=S;s-prior=p-prior;s-next=p;p-prior=s;19．取出广义表A＝（（x，（a，b，c，d））中原子c的函数是head(tail(tail((head(tail(head(A))))))。20．在一个具有n个结点的有序单链表中插人一个新结点并使之仍然有序的时间复杂度为O(n)。21．写出带头结点的双向循环链表L为空表的条件(L==L-Next)&&(L==L-Prior)。22．线性表、栈和队列都是线性_结构。23．向栈中插人元素的操作是先移动栈顶针，再存人元素。三、判断题1．线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。（错）2．在具