数据结构（c语言版）程海英-课后习题

《数据结构（c语言版）程海英-课后习题》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、1.解释下列术语：数据、数据元素、数据对象、数据结构、存储结构、线性结构、算法、抽象数据类型。2.试举一个数据结构的例子，叙述其逻辑结构、存储结构及运算3方面的内容。3.选择题1）在数据结构中，从逻辑上可以把数据结构分成（）。A.动态结构和静态结构C.线性结构和非线性结构B.紧凑结构和非紧凑结构D.内部结构和外部结构2）与数据元素本身的形式、内容、相对位置、个数无关的是数据的（）。A.存储结构B.存储实现C.逻辑结构D.运算实现3）通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着（）。A.数据具有同一特点B.不仅数据元

2、素所包含的数据项的个数要相同，而且对应数据项的类型要一致C.每个数据元素都一样D.数据元素所包含的数据项的个数要相等4）以下说法正确的是（）。A.数据元素是数据的最小单位B.数据项是数据的基木单位C.数据结构是带有结构的各数据项的集合D.一些表面上很不相同的数据可以有相同的逻辑结构5）以下数据结构屮，（）是非线性数据结构A.树B.字符串C.队D.栈4.填空题1）数据结构是一门研究非数值计算的程序设计问题中计算机的以及它们之I'可的和运算等的学科。2）数据结构被形式定义为（D,R）,其屮D是的有限集合，R是D上的有限集合。3）数据结

3、构包括数据的、数据的和数据的这三个方面的内容。4）线性结构中元素之间存在关系，树形结构中元素之间存在关系，图形结构中元素之间存在关系。5）一个算法的效率可分为效率和效率。1.试分析下面各算法的时间复杂度。1)x=90;y=100;while(y>0)if(x>100){x=x-10;y-;}elsex++;1)for(i=0;ivn;i++)for(j=0;j

4、4)i=0,sl=0,s2=0;while(i++ly=o；while(x>=(y+1)*(y+1))y++;1.线性表有两种存储结构，分别是顺序表和链表。试问：两种存储结构各有哪些主要优缺卢。八八•2.试分析线性表的特征并举例说明。3.选择题1）在一个长度为n的顺序存储的线性表中，向第i个元素（lWiWn+1）位置插入一个新元素吋，需要从后向前依次后移（）个元素。A.n-iB.n-i+lC・n-i-1D.i2）在一个t度为n的顺序存储的线性表屮，删除第i

5、个元素（IWiWn）时，需要从前向后依次前移（）个元素。A.n-iB.n-i+1C.n-i-1D.i3）在一个顺序表中任何位置插入一个元素的时间复杂性的量级为（）。A.O（n）B.O（n/2）C.0（1）D.0（n2）4）在一个顺序表的表尾插入一个元素的时间复杂性的量级为（）。A.O（n）B.O（1）C.O（n*n）D.O（log2n）5）线性表的链式存储比顺序存储最有利于进行（）操作。A.查找B.表尾插入或删除C.按值插入或删除D.表头插入或删除6）在一个单链表中，若要在p所指向的结点之后插入一个新结点，则需要相继修改（）个指针

6、域的值。A.1B.2C.3D.47）在一头指针为H的单链表中，若要向表头插入一个由指针p指向的结点，则应执行（）操作。A.H=p;p->next=H;B.p->next=H;H=p;C.p->next=H;p=H;D.p->next=H->next;H->next=p;8）在一个表头指针为H的单链表中，若要在指针q所指结点的后面插入一个由指针p所指向的结点，则执行（）操作。A.q->next=p->next;p-next=q;B.p・>next二q・>next;q=p;C.q・>next=p・>next;p・>next二p・>ne

7、xt;D•p->next=q->next;q->next=p;1.填空题1）顺序表屮访问任意结点的时I'可复杂度均为，顺序表也称为随机存取的数据结构。2）顺序表中逻辑上相邻的元素的物理位置相邻。单链表中逻辑上相邻的元素的物理位置相邻。3）在单链表中，除了第一个结点外，任一结点的存储位置由指示。4）在n个结点的单链表中要删除已知结点*p,需找到它的,其吋间复杂度为05）对于长度为n的顺序存储的线性表，在表头插入元素的时间复杂度为,在表尾插入结点的时间复杂度为o6）对于单链表，在表头插入结点的时间复杂性度为,在表尾插入结点的时间复杂度

8、为。2.已知长度为n的线性表A采用顺序存储，编写时间复杂度为0（n）、空间复杂度为0（1）的算法，该算法删除线性表中所有值为item的数据元素。3.设计一个算法，通过一遍扫描在单链表屮确定值最大的结点。4.编写在顺序表和带头结点的单链表上，统计出值