《数据结构(本)课程作业》由会员分享，可在线阅读，更多相关《数据结构(本)课程作业（9页珍藏版）》请在金锄头文库上搜索。
1、数据结构数据结构( (本本) )课程作业课程作业个人总结，仅供交流 个人总结 数据结构（本）课程作业作业 1（本部分作业覆盖教材第 1-2 章的内容）一、单项选择题1在数据结构中，从逻辑上可以把数据结构分为（ C ） 。A动态结构和静态结构 B紧凑结构和非紧凑结构 C线性结构和非线性结构 D内部结构和外部机构2下列说法中，不正确的是（ D ） 。A数据元素是数据的基本单位 B数据项是数据中不可分割的最小可标识单位 C数据可有若干个数据元素构成 D数据项可由若干个数据元素构成3一个存储结点存储一个（ B ） 。A数据项 B数据元素 C数据结构 D数据类型4数据结构中，与所使用的计算机无关的是数据
2、的（ C ） 。A存储结构 B物理结构C逻辑结构 D物理和存储结构5下列的叙述中，不属于算法特性的是（ D ） 。A有穷性 B输入性 C可行性 D可读性6算法分析的目的是（ C ） 。A找出数据结构的合理性 B研究算法中的输入和输出的关系 C分析算法的效率以求改进 D分析算法的易懂性和文档性7数据结构是一门研究计算机中（ B ）对象及其关系的科学。A数值运算 B非数值运算C集合 D非集合 8算法的时间复杂度与（ D ）有关。A所使用的计算机 B与计算机的操作系统 C与算法本身 D与数据结构9设有一个长度为 n 的顺序表，要在第 i 个元素之前（也就是插入元素作为新表的第 i 个元素） ，则移动
3、元素个数为（ A ） 。An-i+1 Bn-i Cn-i-1 Di10设有一个长度为 n 的顺序表，要删除第 i 个元素移动元素的个数为（ B ） 。An-i+1 Bn-i Cn-i-1 Di11在一个单链表中，p、q 分别指向表中两个相邻的结点，且 q所指结点是 p 所指结点的直接后继，现要删除 q 所指结点，可用语句（ C ） 。Ap=q-next Bp-next=q Cp-next=qnext Dq-next=NULL12在一个单链表中 p 所指结点之后插入一个 s 所指的结点时，可执行（ D ） 。Ap-next= s; snext= pnext Bp-next=snext; Cp=s
4、-next Ds-next=p-next; p-next=s;13非空的单向循环链表的尾结点满足（ C ） （设头指针为head，指针 p 指向尾结点） 。A.P-next= =NULL BP= =NULLCP-next= =head DP= = head 14链表不具有的特点是（ A ） 。A可随机访问任一元素 B插入删除不需要移动元素C不必事先估计存储空间 D所需空间与线性表长度成正比15带头结点的链表为空的判断条件是（ B ） （设头指针为head） 。Ahead = =NULLBhead-next= =NULL Chead-next= =head Dhead!=NULL16在一个单链表
5、中，p、q 分别指向表中两个相邻的结点，且q 所指结点是 p 所指结点的直接后继，现要删除 q 所指结点，可用语句（ C ） 。Ap=q-nextBp-next=q Cp-next=q-nextDq-next=NULL17在一个链队中，假设 f 和 r 分别为队头和队尾指针，则删除一个结点的运算为（ C ） 。Ar=f-next; Br=r-next; Cf=f-next; Df=r-next;18在一个链队中，假设 f 和 r 分别为队头和队尾指针，则插入s 所指结点的运算为（ B ） 。Af-next=s; f=s; Br-next=s;r=s; Cs-next=r;r=s; Ds-nex
6、t=f;f=s;19.一个顺序表第一个元素的存储地址是 90，每个元素的长度为2，则第 6 个元素的地址是（ C ） 。A98 B100 C102 D10620有关线性表的正确说法是（ D ） 。A每个元素都有一个直接前驱和一个直接后继 B线性表至少要求一个元素C表中的元素必须按由小到大或由大到下排序 D除了一个和最后一个元素外，其余元素都有一个且仅有一个直接前驱和一个直接后继二、填空题1在一个长度为 n 的顺序存储结构的线性表中，向第i(1?i?n+1)个元素之前插入新元素时，需向后移动 n-i+1 个数据元素。2从长度为 n 的采用顺序存储结构的线性表中删除第i(1?i?n+1)个元素 ，
7、需向前移动 n-i 个元素。3数据结构按结点间的关系，可分为 4 种逻辑结构： 线性表 、树 、 图 、 集合 。4数据的逻辑结构在计算机中的表示称为 物理结构 或 存储 。5除了第 1 个和最后一个结点外，其余结点有且只有一个前驱结点和后继结点的数据结构为 线性表 ，每个结点可有任意多个前驱和后继结点数的结构为 图 。6算法的 5 个重要特性是 有穷性 、 确定性 、 可行性 、 有零个或多个输入 、 有一个或多个输出 。7数据结构中的数据元素存在多对多的关系称为_图型_ _结构。8数据结构中的数据元素存在一对多的关系称为_树型_结构。9数据结构中的数据元素存在一对一的关系称为_线性_结构。
8、10要求在 n 个数据元素中找其中值最大的元素，设基本操作为元素间的比较。则比较的次数和算法的时间复杂度分别为_(n+1)/2_ _和 _O(n) _ 。11在一个单链表中 p 所指结点之后插入一个 s 所指结点时，应执行_s-next=p-next_ _和 p-next=s;的操作。12设有一个头指针为 head 的单向循环链表，p 指向链表中的结点，若p-next= =_head _，则 p 所指结点为尾结点。13在一个单向链表中，要删除 p 所指结点，已知 q 指向 p 所指结点的前驱结点。则可以用操作_ q-next=p-next _。14设有一个头指针为 head 的单向链表，p 指
9、向表中某一个结点，且有 p-next= =NULL,通过操作_p-next=head_ _,就可使该单向链表构造成单向循环链表。15每个结点只包含一个指针域的线性表叫 单链表 。16线性表具有 顺序 和 链接 两种存储结构。17数据的逻辑结构是从逻辑关系上描述数据，它与数据的 物理 关系无关，是独立于计算机的。18在双向循环链表的每个结点中包含 两个 指针域，其中next 指向它的 直接后继 ，prior 指向它的 直接前驱 ，而头结点的 prior 指向 尾结点 ，尾结点的 next 指向 头结点 。19单向循环链表是单向链表的一种扩充，当单向链表带有头结点时，把单向链表中尾结点的指针域由空
10、指针改为 指向头结点 ；当单向链表不带头结点时，则把单向链表中尾结点的指针域由空指针改为指向 第一个结点 。20线性链表的逻辑关系是通过每个结点指针域中的指针来表示的。其逻辑顺序和物理存储顺序不再一致，而是一种 离散 存储结构，又称为 链式存储结构 。 三、问答题1简述数据的逻辑结构和存储结构的区别与联系，它们如何影响算法的设计与实现？答案要点：个人总结，仅供交流 (1) 数据的逻辑结构表示数据之间的逻辑关系，有线性表、树、图和集合四种；个人总结 (2) 数据的存储结构为数据的逻辑结构在计算机中的存储表示，有顺序和链接两种；(3) 数据的存储结构应包含数据元素的表示和关系的表示。同一种逻辑结构
11、可以根据实际的需要表示成不同存储结构；(4) 数据结构，尤其是数据的存储结构对基于该结构的搜索算法、插入和删除算法在时间复杂度和空间复杂度均有很大的影响。2解释顺序存储结构和链式存储结构的特点，并比较顺序存储结构和链式存储结构的优缺点。答案要点(1) 顺序存储结构的特点为：数据的逻辑结构和存储表示一致，占用连续的存储空间；(2) 链接存储结构的特点为：数据的逻辑结构用指针来链接，不要求占用连续的存储空间；(3) 顺序存储结构的优点是占用存储空间小，操作简便，可根据下标直接访问表中数据元素，缺点是需要占用连续的存储空间，插入和删除需要移动大量的数据元素；(4) 链接存储结构的优点是不要求占用连续
12、的存储空间，插入和删除的效率高，缺点是占用较大的存储空间，不能对数据元素直接访问。3什么情况下用顺序表比链表好？答案要点：线性表的长度较小，不需要进行大量的插入和删除运算或插入和删除仅在表的一端进行，如队列和栈就经常组织成顺序表的形式。4头指针、头结点、第一个结点（或称首元结点）的区别是什么？答案要点：头指针是指向表头的指针，头结点是为操作上的便利而给线性表增加的附加结点；第一个结点是线性表的开始结点。5解释带头结点的单链表和不带头结点的单链表的区别。答案要点：单链表的头结点不属于单链表本身，其主要的作用有两个：一是用于存放表头结点及一些线性表的辅助信息，二是用于统一空表和非空表的操作。四、程序填空题1下列是用尾插法建立带头结点的且有 n 个结点的单向链表的算法，请在空格内填上适当的语句。NODE *create1(n)/* 对线性表(1,
