《电大数据结构本形成性考核册作业1-4原题带答案.doc》由会员分享，可在线阅读，更多相关《电大数据结构本形成性考核册作业1-4原题带答案.doc（14页珍藏版）》请在金锄头文库上搜索。
1、数据结构（本）课程作业作业1（本部分作业覆盖教材第1-2章的内容）29一、单项选择题1在数据结构中，从逻辑上可以把数据结构分为（C ）。A动态结构和静态结构 B紧凑结构和非紧凑结构 C线性结构和非线性结构 D内部结构和外部机构2下列说法中，不正确的是（ D ）。A数据元素是数据的基本单位 B数据项是数据中不可分割的最小可标识单位 C数据可有若干个数据元素构成 D数据项可由若干个数据元素构成3一个存储结点存储一个（ B ）。A数据项 B数据元素 C数据结构 D数据类型4数据结构中，与所使用的计算机无关的是数据的（ C ）。A存储结构 B物理结构C逻辑结构 D物理和存储结构5下列的叙述中，不属于算
2、法特性的是（ D ）。A有穷性 B输入性 C可行性 D可读性6算法分析的目的是（ C ）。 A找出数据结构的合理性 B研究算法中的输入和输出的关系 C分析算法的效率以求改进 D分析算法的易懂性和文档性7数据结构是一门研究计算机中（B ）对象及其关系的科学。A数值运算 B非数值运算C集合 D非集合 8算法的时间复杂度与（ C ）有关。 A所使用的计算机 B与计算机的操作系统 C与算法本身 D与数据结构9设有一个长度为n的顺序表，要在第i个元素之前（也就是插入元素作为新表的第i个元素），则移动元素个数为（ A ）。 An-i+1 Bn-i Cn-i-1 Di10设有一个长度为n的顺序表，要删除第i
3、个元素移动元素的个数为（ 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-next Ds-next=p-next; p-next=s;13非空的单向循环链表的尾结点满足（C ）（设头指针为head，指针p指
4、向尾结点）。 A.P-next= =NULL BP= =NULL CP-next= =head DP= = head 14链表不具有的特点是（ A ）。 A可随机访问任一元素 B插入删除不需要移动元素 C不必事先估计存储空间 D所需空间与线性表长度成正比15带头结点的链表为空的判断条件是（B ）（设头指针为head）。Ahead = =NULLBhead-next= =NULL Chead-next= =headDhead!=NULL16在一个单链表中，p、q分别指向表中两个相邻的结点，且q所指结点是p所指结点的直接后继，现要删除q所指结点，可用语句（C ）。Ap=q-nextBp-next=
5、qCp-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-next=f;f=s;19.一个顺序表第一个元素的存储地址是90，每个元素的长度为2，则第6个元素的地址是（B ）。A98 B100 C102 D10620有关线性表的正确说法是（ D ）。
6、A每个元素都有一个直接前驱和一个直接后继 B线性表至少要求一个元素C表中的元素必须按由小到大或由大到下排序 D除了一个和最后一个元素外，其余元素都有一个且仅有一个直接前驱和一个直接后继二、填空题1在一个长度为n的顺序存储结构的线性表中，向第i(1in+1)个元素之前插入新元素时，需向后移动 n-i+1 个数据元素。2从长度为n的采用顺序存储结构的线性表中删除第i(1in+1)个元素 ，需向前移动 n-i 个元素。3数据结构按结点间的关系，可分为4种逻辑结构： 集合 、 线性结构 、 树形结构 、 图状结构 。4数据的逻辑结构在计算机中的表示称为 物理结构 或 存储结构 。5除了第1个和最后一个
7、结点外，其余结点有且只有一个前驱结点和后继结点的数据结构为 线性结构 ，每个结点可有任意多个前驱和后继结点数的结构为 非线性结构 。6算法的5个重要特性是 有穷性 、 确定性 、 可形性 、 有零个或多个输入 、 有零个或多个输出 。7数据结构中的数据元素存在多对多的关系称为_图状结构_结构。8数据结构中的数据元素存在一对多的关系称为_树形结构_结构。9数据结构中的数据元素存在一对一的关系称为_线性结构_结构。10要求在n个数据元素中找其中值最大的元素，设基本操作为元素间的比较。则比较的次数和算法的时间复杂度分别为_ n-1_和 _ O(n)_ 。11在一个单链表中p所指结点之后插入一个s所指
8、结点时，应执行_ 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指向表中某一个结点，且有p-next= =NULL,通过操作_ p-next=head _,就可使该单向链表构造成单向循环链表。15每个结点只包含一个指针域的线性表叫 单链表 。16线性表具有 顺序存储 和 链式存储 两种存储结构。17数
9、据的逻辑结构是从逻辑关系上描述数据，它与数据的关系 存储结构 无关，是独立于计算机的。18在双向循环链表的每个结点中包含 两个 指针域，其中next指向它的 直接后继 ，prior指向它的 直接前驱 ，而头结点的prior指向 尾结点 ，尾结点的next指向 头结点 。19单向循环链表是单向链表的一种扩充，当单向链表带有头结点时，把单向链表中尾结点的指针域由空指针改为 头结点的指针 ；当单向链表不带头结点时，则把单向链表中尾结点的指针域由空指针改为指向 指向第一个结点的指针 。20线性链表的逻辑关系时通过每个结点指针域中的指针来表示的。其逻辑顺序和物理存储顺序不再一致，而是一种 链式 存储结构
10、，又称为 链表 。 三、问答题1简述数据的逻辑结构和存储结构的区别与联系，它们如何影响算法的设计与实现？答：若用结点表示某个数据元素，则结点与结点之间的逻辑关系就称为数据的逻辑结构。数据在计算机中的存储表示称为数据的存储结构。可见，数据的逻辑结构是反映数据之间的固有关系，而数据的存储结构是数据在计算机中的存储表示。尽管因采用的存储结构不同，逻辑上相邻的结点，其物理地址未必相同，但可通过结点的内部信息，找到其相邻的结点，从而保留了逻辑结构的特点。采用的存储结构不同，对数据的操作在灵活性，算法复杂度等方面差别较大。2解释顺序存储结构和链式存储结构的特点，并比较顺序存储结构和链式存储结构的优缺点。答
11、：顺序结构存储时，相邻数据元素的存放地址也相邻，即逻辑结构和存储结构是统一的，要求内存中存储单元的地址必须是连续的。优点：一般情况下，存储密度大，存储空间利用率高。缺点：（1）在做插入和删除操作时，需移动大量元素；（2）由于难以估计，必须预先分配较大的空间，往往使存储空间不能得到充分利用；（3）表的容量难以扩充。链式结构存储时，相邻数据元素可随意存放，所占空间分为两部分，一部分存放结点值，另一部分存放表示结点间关系的指针。优点：插入和删除元素时很方便，使用灵活。缺点：存储密度小，存储空间利用率低。3什么情况下用顺序表比链表好？答：顺序表适于做查找这样的静态操作，链表适于做插入和删除这样的动态操
12、作。如果线性表的变化长度变化不大，且其主要操作是查找，则采用顺序表；如果线性表的长度变化较大，且其主要操作是插入、删除操作，则采用链表。4头指针、头结点、第一个结点（或称首元结点）的区别是什么？头结点是在链表的开始结点之前附加的一个结点；第一个结点（或称首元结点）是链表中存储第一个数据元素的结点；头指针是指向链表中第一个结点（或为头结点或为首元结点）的指针。5解释带头结点的单链表和不带头结点的单链表的区别。答：带头结点的单链表和不带头结点的单链表的区别主要体现在其结构上和算法操作上。在结构上，带头结点的单链表，不管链表是否为空，均含有一个头结点，不带头结点的单链表不含头结点。在操作上，带头结点
13、的单链表的初始化为申请一个头结点。无论插入或删除的位置是地第一个结点还是其他结点，算法步骤都相同。不带头结点的单链表，其算法步骤要分别考虑插入或删除的位置是第一个结点还是其他结点。因为两种情况的算法步骤不同。四、程序填空题1下列是用尾插法建立带头结点的且有n个结点的单向链表的算法，请在空格内填上适当的语句。NODE *create1(n)/* 对线性表(1,2,.,n),建立带头结点的单向链表 */ NODE *head,*p,*q; int i; p=(NODE *)malloc(sizeof(NODE); head=p; q=p; p-next=NULL; for(i=1;i=n;i+) p=(NODE *)malloc(sizeof(NODE); （1）p-
