数据结构形成性考核作业册

1、数据结构（本）形成性考核作业册使用说明本作业册是中央广播电视大学计算机科与技术专业（本科）数据结构（本）课程形成性考核的依据，与数据结构（本科）教材（伟生主编，中央电大出版）配套使用。数据结构 （本）课程是中央广播电视大学计算机科学技术专业的一门统设必修、学位课程， 4 学分，共72 学时。其中实验24 学时，开设一学期。本课程的特点是综合性、实践性强，容抽象， 在专业中具有承上启下的作用。因此，在学习本课程时，要注意理论联系实际，结合教学容进行上机实践，认真完成作业和实验容。本课程的总成绩按百分制记分，其中形成性考核所占的比例为30%，终结性考试占70（闭卷，答题时限为 90 分钟）。课程总

2、成绩达到 60 分及以上者为合格，可以获得该课程的学分。本课程的学位课程学分为 70 分，即课程总成绩达到 70 分及以上者有资格申请专业学位。本课程共设计了4 次形考作业， 每次形考作业均包括实验容，由各地电大根据学生对作业中各种题型练习和实验的完成情况进行考核。对于实验容要求按实验要求认真完成，并提交实验报告。数据结构（本）课程作业作业 1（本部分作业覆盖教材第1-2 章的容）一、单项选择题1在数据结构中，从逻辑上可以把数据结构分为（）。A动态结构和静态结构B紧凑结构和非紧凑结构C线性结构和非线性结构D部结构和外部机构2下列说法中，不正确的是（A数据元素是数据的基本单位）。B数据项是数据中

3、不可分割的最小可标识单位C数据可有若干个数据元素构成D数据项可由若干个数据元素构成3一个存储结点存储一个（）。A数据项B 数据元素C数据结构D数据类型4每个存储结点只存储一个数据元素，各结点存储在连续的存储空间，该存储方式是（）存储方式。A顺序BC索引D散列5每个存储结点不仅含有一个数据元素，还包含一组指针，该存储方式是（）存储方式。A顺序BC索引D散列6数据结构中，与所使用的计算机无关的是数据的（A存储结构B物理结构C逻辑结构D物理和存储结构7下列的叙述中，不属于算法特性的是（）。A有穷性B输入性C可行性D可读性）。8算法分析的目的是（）。A 找出数据结构的合理性B研究算法中的输入和输出的关

4、系C分析算法的效率以求改进D分析算法的易懂性和文档性9数据结构是一门研究计算机中（）对象及其关系的科学。A数值运算B 非数值运算C集合D 非集合10算法的时间复杂度与（）有关。A 所使用的计算机B与计算机的操作系统C与算法本身D与数据结构11把数据存储到计算机中，并具体体现数据元素间的逻辑结构称为（）。iA逻辑结构B物理结构C算法的具体实现D给相关变量分配存储单元12设有一个长度为n 的顺序表， 要在第 i 个元素之前 （也就是插入元素作为新表的第个元素），则移动元素个数为（）。An-i+1Bn-iC n-i-1D i13设有一个长度为n 的顺序表，要删除第i 个元素移动元素的个数为（）。An

5、-i+1Bn-iC n-i-1D i14在一个单链表中，p、 q 分别指向表中两个相邻的结点，且q 所指结点是p 所指结点的直接后继，现要删除q 所指结点，可用语句（）。Ap=q-nextBp-next=qCp-next=qnext D q-next=NULL15在一个单链表中p 所指结点之后插入一个s 所指的结点时，可执行（）。Ap-next= s; snext= pnextB p-next=snext;Cp=s-nextDs-next=p-next; p-next=s;16非空的单向循环链表的尾结点满足（）（设头指针为head，指针p 指向尾结点）。A. P-next= =NULLC P-

6、next= =headBDP= =NULLP= = head17链表不具有的特点是（）。A可随机访问任一元素BC不必事先估计存储空间D插入删除不需要移动元素所需空间与线性表长度成正比18带头结点的链表为空的判断条件是（A head = =NULL）（设头指针为head）。B head-next= =NULLC head-next= =headD head!=NULL19在一个单链表中，p、 q 分别指向表中两个相邻的结点，且q 所指结点是p 所指结点的直接后继，现要删除q 所指结点，可用语句（）。A p=q-nextB p-next=qC p-next=q-nextD q-next=NULL2

7、0下面关于线性表的叙述错误的是()。A. 线性表采用顺序存储 , 必须占用一片地址连续的单元B线性表采用顺序存储, 便于进行插入和删除操作C线性表采用链式存储, 不必占用一片地址连续的单元D线性表采用链式存储, 便于进行插入和删除操作21在一个链队中， 假设 f 和 r 分别为队头和队尾指针，则删除一个结点的运算为（）。A r=f-next;B r=r-next;C f=f-next;D f=r-next;22在一个链队中， 假设 f 和 r 分别为队头和队尾指针，则插入 s 所指结点的运算为 （）。A f-next=s; f=s;Br-next=s;r=s;C s-next=r;r=s;D

8、s-next=f;f=s;23. 一个顺序表第一个元素的存储地址是90，每个元素的长度为2，则第 6 个元素的地址是（）。A98B 100C102D 10624 用链表表示线性表的优点是（A便于随机存取）。B花费的存储空间较顺序存储少C便于插入和删除D数据元素的物理顺序和逻辑顺序相同25 有关线性表的正确说法是（）。A每个元素都有一个直接前驱和一个直接后继B线性表至少要求一个元素C表中的元素必须按由小到大或由大到下排序D除了一个和最后一个元素外，其余元素都有一个且仅有一个直接前驱和一个直接后继二、填空题1在一个长度为n 的顺序存储结构的线性表中，向第i(1in+1) 个元素之前插入新元素时，需

9、向后移动个数据元素。2从长度为n 的采用顺序存储结构的线性表中删除第i(1in+1) 个元素，需向前移动个元素。3数据结构按结点间的关系，可分为4 种逻辑结构：、。4数据的逻辑结构在计算机中的表示称为或。5除了第1 个和最后一个结点外，其余结点有且只有一个前驱结点和后继结点的数据结构为，每个结点可有任意多个前驱和后继结点数的结构为。6算法的5 个重要特性是、。7数据结构中的数据元素存在多对多的关系称为_ _ 结构。8数据结构中的数据元素存在一对多的关系称为_ _ 结构。9数据结构中的数据元素存在一对一的关系称为_ _ 结构。10要求在 n 个数据元素中找其中值最大的元素，设基本操作为元素间的比

10、较。的次数和算法的时间复杂度分别为_和 _。11在一个单链表中p 所指结点之后插入一个s 所指结点时，应执行_和 p-next=s;的操作。、则比较_12设有一个头指针为head 的单向循环链表，p 指向链表中的结点，若p-next= =_，则 p 所指结点为尾结点。13在一个单向链表中，要删除 p 所指结点， 已知 q 指向 p 所指结点的前驱结点。则可以用操作 _。14设有一个头指针为head 的单向链表， p 指向表中某一个结点，且有 p-next=NULL,通过操作 _,就可使该单向链表构造成单向循环链表。15每个结点只包含一个指针域的线性表叫。16线性表具有和两种存储结构。17数据的

11、逻辑结构是从逻辑关系上描述数据，它与数据的关系无关，是独立于计算机的。18在双向循环链表的每个结点中包含指针域，其中next指向它的，prior指向它的，而头结点的prior指向，尾结点的next指向。19单向循环链表是单向链表的一种扩充，当单向链表带有头结点时，把单向链表中尾结点的指针域由空指针改为；当单向链表不带头结点时，则把单向链表中尾结点的指针域由空指针改为指向。20线性链表的逻辑关系时通过每个结点指针域中的指针来表示的。其逻辑顺序和物理存储顺序不再一致，而是一种存储结构，又称为。三、问答题1简述数据的逻辑结构和存储结构的区别与联系，它们如何影响算法的设计与实现？2解释顺序存储结构和链

12、式存储结构的特点，并比较顺序存储结构和链式存储结构的优缺点。3什么情况下用顺序表比链表好？4头指针、头结点、第一个结点（或称首元结点）的区别是什么？5解释带头结点的单链表和不带头结点的单链表的区别。6与单链表相比，双向循环链表有哪些优点？四、程序填空题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;inext=NULL;（2）;for(i=1;idata=i;if(i=1)（3）;else（4）;（5）;return(head);3下列是在具有头结点的单向列表的第ij个结点之间插入新结点x 的算法（ 1in+1），请在空格填上适当的语句。int insert(NODE *head,int x,int i)NODE *q,*p;int j;（1）;j=0;while(q!=NULL)&(jnext;j+;if(q=NULL) return(0);p=(NODE *)malloc(sizeof(NODE);p-data=x;（2）;（3）;return(1);4下列是在