数据结构习题解答-副本

《数据结构习题解答-副本》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、习题一1填空题(1)(数据元素、或元素、或结点、或顶点、或记录）是数据的基本单位，在计算机程序中作为一个整体进行考虑和处理。(2)（数据项、或字段）是数据的最小单位，（数据元素）是讨论数据结构时涉及的最小数据单位。(3)从逻辑关系上讲，数据结构主要分为(集合)、(线性结构)、(树结构)和(图)。(4)数据的存储结构主要有（顺序存储结构）和（链式存储结构）两种基本方法，不论哪种存储结构，都要存储两方面的内容：（数据元素）和（它们之间的关系）。(5)算法具有5个特性，分别是（输入）、（输出）、（有穷性）、（确定性）、（可行性）。(6)算法的描述方法通常有(自

2、然语言)、(流程图)、(程序设计语言)、(伪代码)4种，其中，(伪代码)被称为算法语言。(7)一般情况下，一个算法的时间复杂度是算法（输入规模）的函数。(8)设待处理问题的规模为n,若一个算法的时间复杂度为一个常数，则表示成数量级的形式为(O(1))，若为n*log25n,则表示成数量级的形式为(O(n*log2n))。2.选择题:(1)C,D(2)B(3)B(4)A(5)D(6)A(7)C(8)C,E习题二1.填空题(1)在顺序表中，等概率情况下，插入和删除一个元素平均需移动(表长的一半)个元素，具体移动元素的个数与(表的长度)和(数据元素所在的位置)

3、有关。(2)一个顺序表的第一个元素的存储地址是100，每个数据元素的长度是2，则第5个数据元素的存储地址是（108）。(3)设单链表中指针p指向单链表的一个非空结点A，若要删除结点A的直接后继，则需要修改指针的操作为（p->next=(p->next)->next,或者q=p->next;p->next=q->next）。(4)单链表中设置头结点的作用是(方便运算,减少程序的复杂性，使得空表和非空表处理统一)。(5)非空的循环单链表由头指针head指示，则其尾结点(由指针p所指)满足(p->next=head)。(6)在有尾指针rear指示的循环单链表中

4、，在表尾插入一个结点s的操作序列是（s->next=rear->next;rear->next=s;rear=s），删除开始结点的操作序列是（q=rear->next->next;rear->next->next=q->next;deleteq;）。注：假设此循环单链表有表头结点(7)一个具有n个结点的单链表，在p所指结点后插入一个新结点s的时间复杂性为（O(1)）；在给定值x的结点后插入一个新结点的时间复杂性为(O(n)）。(8)可由一个尾指针惟一确定的链表有(循环链表)、(双链表)、(双循环链表)。2.选择题:(1)A,B(2)D(3)B(4)A(5

5、)A(6)D(7)B(8)B(9)C(10)B(11)B(12)D(13)A(14)A5.算法设计(1)设计一个时间复杂度为O(n)的算法。实现将数组A[n]中所有元素循环左移k个位置。算法思想：要使a1…akak+1…an->ak+1…ana1…ak,可以先让a1…akak+1…an->ak…a1an…ak+1,再让ak…a1an…ak+1->ak+1…ana1…ak，参见第1章16页的思想火花算法：voidconverse(Ta[],inti,intj){for(s=i;s<=(i+j)/2;s++)//将数组a中从i到j中的元素倒置{temp=a[

6、s];a[s]=a[j-s+i];a[j-s+i]=temp;}}voidmove(Ta[],k){converse(a,0,k-1);//3次调用函数converseconverse(a,k,n-1);converse(a,0,n-1);}(2)已知数组A[n]中的元素为整型，设计算法将其调整为左右两部分，左边所有元素为奇数，右边所有元素为偶数，并要求算法的时间复杂度为O(n).解法1：voidtiaozhen(TA[],intn){s=0;t=n-1;while(s

7、==0)t--;if(s

8、hrow"输入的插入位置值小于1";if(i==1){s=newNode;