国家开放大学电大考试《数据结构(本)》形成性考核册作业1-4原题及答案.docx

《国家开放大学电大考试《数据结构(本)》形成性考核册作业1-4原题及答案.docx》由会员分享，可在线阅读，更多相关《国家开放大学电大考试《数据结构(本)》形成性考核册作业1-4原题及答案.docx（5页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、B. P二二NULLD. P二二 headB .插入删除不需D .所需空间与线)(设头作业1一、单项选择题L在数据结构中，从逻辑上可以把数据结构分为(C ) oA.动态结构和静态结构B.紧凑结构和非紧凑结C.线性结构和非线性结构D.内部结构和外部机构2 .下列说法中，不正确的是(数据元素是数据的基本A.单位B.数据项是数据中不可分割的最小可标识单位C.数据可有若干个数据元素构成数据项可由若干个D.数据元素构成3 . 一个存储结点存储一个(B )A.数据项B.数据元素C.数据结构D.数据类型)A.存储结构B.物理结构C.逻辑结构D.物理和存储结构5 .下列的叙述中，不属于算法特性的是(D ) o

2、A.有穷性B.输入性C.可行性D.可读性6 .算法分析的目的是(C)Z OA.找出数据结构的合理性B.研究算法中的输入和输出的关系C.分析算法的效率以求改进D.分析算法的易懂性和文档性7 .数据结构是一门研究计算机中(B )对象及其关系的8 .数据结构中，与所使用的计算机无关的是数据的(C 科学。A.数值运算B.非数值运算C.集合D.非集合8.算法的时间复杂度与(C )有关。A.所使用的计算机B.与计算机的操作系统A. head = =NULLhead-next= =NULLB. head-next= =headhead!=NULL16 .在一个单链表中，p、q分别指向表中两个相邻的结点，且

3、q所指结点是P所指结点的直接后继，现要删除q所指结点，可用语 句(C )。A. p=q-nextp-next=qB. p) next=q-) nextq-next=NULL17 .在一个链队中，假设f和r分别为队头和队尾指针，则 删除一个结点的运算为(C ) OA. r=f-next;B.r=r-next;C. f=f-next;D. f=r-next;(本部分作业覆盖教材第1-2章的内容)C.与算法本身D.与数据结构9 .设有一个长度为n的顺序表，要在第i个元素之前(也就是 插入元素作为新表的第i个元素)，则移动元素个数为(A )A. n-i+1B. n-iC. n-i-1 D. i10 .

4、设有一个长度为n的顺序表，要删除第i个元素移动元素的个数为(B ) oA. n-i+1B. n-iC. n-i-l D. i11 .在一个单链表中，P、q分别指向表中两个相邻的结点，且 q所指结点是P所指结点的直接后继，现要删除q所指结点，可 用语句(C ) O18.在一个链队中，假设f和r分别为队头和队尾指针，则插 入s所指结点的运算为(B ) oA. p=q-next B . p-next=q C. p-next=qAnext D. q-next=NULLA .p-next= s;sAnext= pAnextB. p-next=sAnext;C.p=s-nextD.s-next=p-nex

5、t; p-next=s;13,非空的单向循环链表的尾结点满足(C)(设头指针为head,指针p指向尾结点)。A. P-next二二NULLP-next=head14 .链表不具有的特点是(A ) oA.可随机访问任一元素要移动元素C.不必事先估计存储空间性表长度成正比15 .带头结点的链表为空的判断条件是(B 指针为head)。12.在一个单链表中p所指结点之后插入一个s所指的结点 时, 可执行(D ) oA. f-next=s; f=s; B. r-next=s;r=s;1 . s-next=r;r=s; D. s-next=f;f=s;19 . 一个顺序表第一个元素的存储地址是90,每个元

6、素的长度为 2,则第6个元素的地址是(B )。A. 98B. 100 C. 102D. 10620 .有关线性表的正确说法是(D )A.每个元素都有一个直接前驱和一个直接后继B.线性表至少要求一个兀素C.表中的元素必须按由小到大或由大到下排序D.除了一个和最后一个元素外，其余元素都有一个且仅有 一个直接前驱和一个直接后继 二、填空题1 .在一个长度为n的顺序存储结构的线性表中，向第i(lin+l) 个元素之前插入新元素时，需向后移动顼-1+1_个数据 元素。2 .从长度为n的采用顺序存储结构的线性表中删除第i(linext=p-next 和 p-next=s;的操作。12 .设有一个头指针为h

7、ead的单向循环链表，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 .数据的逻辑结构是从逻辑关系上描述数据，它与数据的关系 一存储结构一无关，是独立于计算

8、机的。18 .在双向循环链表的每个结点中包含一两个指针域，其中 next指向它的一直接后继一，prior指向它的一直接前驱一，而头结 点的prior指向一尾结点一，尾结点的next指向一头结点一。19 .单向循环链表是单向链表的一种扩充，当单向链表带有头结 点时，把单向链表中尾结点的指针域由空指针改为一头结点的指针 一；当单向链表不带头结点时，则把单向链表中尾结点的指针域由空 指针改为指向一指向第一个结点的指针一。20 .线性链表的逻辑关系时通过每个结点指针域中的指针来表 示的。其逻辑顺序和物理存储顺序不再一致，而是一种一链式存储结 构，又称为一链表一。三、问答题1.简述数据的逻辑结构和存储结

9、构的区别与联系，它们如何影 响算法的设计与实现？答：若用结点表示某个数据元素，则结点与结点之间的逻辑关系 就称为数据的逻辑结构。数据在计算机中的存储表示称为数据的存储 结构。可见，数据的逻辑结构是反映数据之间的固有关系，而数据的 存储结构是数据在计算机中的存储表示。尽管因采 用的存储结构不 同，逻辑上相邻的结点，其物理地址未必相同，但可通过结点的内部 信息，找到其相邻的结点，从而保留了逻辑5 .除了第1个和最后一个结点外，其余结点有且只有一个前 驱 结点和后继结点的数据结构为一线性结构一，每个结点可有任意多个 前驱和后继结点数的结构为一非线性结构 O6 .算法的5个重要特性是一有穷性 确定性

10、可 形性一、一有零个或多个输入一、结构的特点。采用的存储结构不同， 对数据的操作在灵活性，算法复杂度等方面差别较大。2 .解释顺序存储结构和链式存储结构的特点，并比较顺序存储结构 和链式存储结构的优缺点。答：顺序结构存储时，相邻数据元素的存放地址也相邻，即逻辑 结构和存储结构是统一的，要求内存中存储单元的地址必须是连续 的。优点：一般情况下，存储密度大，存储空间利用率高。缺点：（1）在做插入和删除操作时，需移动大量元素；（2）由 于难以估计，必须预先分配较大的空间，往往使存储空间不能得到充 分利用；（3）表的容量难以扩充。链式结构存储时，相邻数据元素可随意存放，所占空间分为两部 分，一部分存放

11、结点值，另一部分存放表示结点间关系的指针。优点：插入和删除元素时很方便，使用灵活。缺点：存储密度小， 存储空间利用率低。3 .什么情况下用顺序表比链表好？答：顺序表适于做查找这样的静态操作，链表适于做插入和删除 这样的动态操作。如果线性表的变化长度变化不大，且其主要操作是 查找，则采用顺序表；如果线性表的长度变化较大，且其主要操作是 插入、删除操作，则采用链表。4 .头指针、头结点、第一个结点（或称首元结点）的区别是什么？头结点是在链表的开始结点之前附加的一个结点；第一个结点 （或称首元结点）是链表中存储第一个数据元素的结点；头指针是指 向链表中第一个结点（或为头结点或为首元结点）的指针。5

12、.解释带头结点的单链表和不带头结点的单链表的区别。带头结点的单链表和不带头结点的单链表的区别主要体现在其 结构上和算法操作上。答：在结构上，带头结点的单链表，不管链表是否为空，均含有一 个头结点，不带头结点的单链表不含头结点。在操作上，带头结点的单链表的初始化为申请一个头结点。无 论插入或删除的位置是地第一个结点还是其他结点，算法步骤都相 同。不带头结点的单链表，其算法步骤要分别考虑插入或删除的位置 是第一个结点还是其他结点。因为两种情况的算法步骤不同。四、程序填空题1. 下列是用尾插法建立带头结点的且有n个结点的单向链表 的算法，请在空格内填上适当的语句。NODE createl （n）/*

13、对线性表（1,2,n），建立带头结点的单向链表*/NODE *head, *p, *q;int i;p=(NODE *)malloc(sizeof(NODE);head=p; q=p; p-next=NULL; for(i=l;idata=i;(2)p-next=NULL;- q-next=p;j=0；while(q!=NULL)&(jnext;j+；if(q=NULL)return(0);q=P；)return(head);2. 下列是用头插法建立带头结点的且有n个结点的单向链表 的算法，请在空格内填上适当的语句。NODE *create2(n)/*对线性表(n,n-l, ,1),建立带头结

14、点的线性链表*/(NODE *head, *p, *q;int i;p=(NODE *)malloc(sizeof(NODE);CUhead=p;p-next=NULL;(2) _q = p；for(i=l;idata=i;if(i=l)(3) p-next=NULL;elsep-next=q-next;(4) - q-next=p; return(head);)3.下列是在具有头结点单向列表中删除第i个结点，请在空格内填 上适当的语句。int delete(NODE *head, int i)B.先存入元素,D.同时进行B.先存入元素,D.同时进行(1) p=q-next.(2) q-nex

15、t=p-next free (p); return (1);)五、完成：实验1一一线性表根据实验要求(见教材P)认真完成本实验，并提交实验201-202 报告。数据结构(本)课程作业2(本部分作业覆盖教材第3-5章的内容)一、单项选择题)B. 2, 1, 31 .若让兀C 3, L 2素1, 2, 3依次进栈，则出栈顺序不可能为(CA. 3, 2, 1A. 4, 3, 2, 1B. 1,2,3,1,4, 3,2D. 3, 2, 4,C. 1, 3, 2. 一个队列的入队序列是1,2, 3, 4。则队列 的输出序列是(B2 .向顺序栈中压入新元素时，应当(AA.先移动栈顶指针，再存入元素 再移动

16、栈顶指针top-next=p;A. C.先后次序无关紧要p-next=top; top=p;B. 4.在一个栈顶指针为top的链栈中，将一个p指针所指的 结点入栈，应执行(C ) O p-) next=top- next; top-next=p;x=top;top=top-next;A. x=top-data;C.p-next=top-next; top=top-next;D. 5.在一个栈顶指针为top的链栈中删除一个结点时，用x 保存被删结点的值，则执行(B )。 top=top-next; x=top-data; x=top-data; top=top-next;一般情况下，将递归算法转换成等价的非递归算法应该设置A )oA.栈NODE *p, *q;NODE *p, *q;C.堆栈或队列int j;q=head;D. -+*abcd判断一个顺序队列sq （最多元素为m ）为空的条 件是（C 0sq-rear-sq-front= sq-rear-sq-front-l= mB.队列D.数组7 .表达式a* （b+c） -d的后缀表达式是（B ）。C . abc*+d-A . abcd*+-B . abc+*d-.B.