《数据结构形成性考核作业1》由会员分享，可在线阅读，更多相关《数据结构形成性考核作业1（7页珍藏版）》请在金锄头文库上搜索。
1、1 数据结构（本）课程作业作业 1（本部分作业覆盖教材第1-2 章的内容）一、单项选择题1在数据结构中，从逻辑上可以把数据结构分为（）。A动态结构和静态结构B紧凑结构和非紧凑结构C线性结构和非线性结构D内部结构和外部机构2下列说法中，不正确的是（）。A数据元素是数据的基本单位B数据项是数据中不可分割的最小可标识单位C数据可有若干个数据元素构成D数据项可由若干个数据元素构成3一个存储结点存储一个（）。A数据项B数据元素C数据结构D数据类型4每个存储结点只存储一个数据元素，各结点存储在连续的存储空间，该存储方式是（）存储方式。A顺序B链接C索引D散列5每个存储结点不仅含有一个数据元素，还包含一组指
2、针，该存储方式是（）存储方式。A顺序B链接C索引D散列6数据结构中，与所使用的计算机无关的是数据的（）。A存储结构B物理结构C逻辑结构D物理和存储结构7下列的叙述中，不属于算法特性的是（）。A有穷性B输入性C可行性D可读性8算法分析的目的是（）。A找出数据结构的合理性B研究算法中的输入和输出的关系C分析算法的效率以求改进D分析算法的易懂性和文档性9数据结构是一门研究计算机中（）对象及其关系的科学。A数值运算B非数值运算C集合D非集合10算法的时间复杂度与（）有关。A所使用的计算机B与计算机的操作系统C与算法本身D与数据结构11把数据存储到计算机中，并具体体现数据元素间的逻辑结构称为（）。A逻辑
3、结构B物理结构C算法的具体实现D给相关变量分配存储单元12设有一个长度为n 的顺序表，要在第i 个元素之前（也就是插入元素作为新表的第i 个元素），则移动元素个数为（）。名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页，共 7 页 -2 An-i+1 Bn-i Cn-i-1 Di 13设有一个长度为n 的顺序表，要删除第i 个元素移动元素的个数为（）。An-i+1 Bn-i Cn-i-1 Di 14在一个单链表中，p、q 分别指向表中两个相邻的结点，且q 所指结点是p 所指结点的直接后继，现要删除q 所指结点，可用语句（）。Ap=q-next Bp-next=q Cp-next=qne
4、xt Dq-next=NULL 15在一个单链表中p 所指结点之后插入一个s 所指的结点时，可执行（）。Ap-next=s;snext=pnext Bp-next=snext;Cp=s-next Ds-next=p-next;p-next=s;16非空的单向循环链表的尾结点满足（）（设头指针为head，指针 p 指向尾结点）。A.P-next=NULL BP=NULL CP-next=head DP=head 17链表不具有的特点是（）。A可随机访问任一元素B插入删除不需要移动元素C不必事先估计存储空间D所需空间与线性表长度成正比18带头结点的链表为空的判断条件是（）（设头指针为head）。A
5、head=NULL Bhead-next=NULL Chead-next=head Dhead!=NULL 19在一个单链表中，p、q 分别指向表中两个相邻的结点，且q 所指结点是p 所指结点的直接后继，现要删除q 所指结点，可用语句（）。Ap=q-next Bp-next=q Cp-next=q-next Dq-next=NULL 20下面关于线性表的叙述错误的是()。A.线性表采用顺序存储,必须占用一片地址连续的单元B线性表采用顺序存储,便于进行插入和删除操作C线性表采用链式存储,不必占用一片地址连续的单元D线性表采用链式存储,便于进行插入和删除操作21 在一个链队中，假设 f 和 r 分
6、别为队头和队尾指针，则删除一个结点的运算为（）。Ar=f-next;Br=r-next;Cf=f-next;Df=r-next;22 在一个链队中，假设 f 和 r 分别为队头和队尾指针，则插入 s 所指结点的运算为（）。A f-next=s;f=s;Br-next=s;r=s;Cs-next=r;r=s;Ds-next=f;f=s;23.一个顺序表第一个元素的存储地址是90，每个元素的长度为2，则第 6 个元素的地址是（）。A98 B100 C102 D106 24 用链表表示线性表的优点是（）。A便于随机存取B花费的存储空间较顺序存储少C便于插入和删除名师资料总结-精品资料欢迎下载-名师精
7、心整理-第 2 页，共 7 页 -3 D数据元素的物理顺序和逻辑顺序相同 25 有关线性表的正确说法是（）。A每个元素都有一个直接前驱和一个直接后继B线性表至少要求一个元素C表中的元素必须按由小到大或由大到下排序D除了一个和最后一个元素外，其余元素都有一个且仅有一个直接前驱和一个直接后继二、填空题1在一个长度为n 的顺序存储结构的线性表中，向第i(1in+1)个元素之前插入新元素时，需向后移动个数据元素。2从长度为n 的采用顺序存储结构的线性表中删除第i(1in+1)个元素，需向前移动个元素。3数据结构按结点间的关系，可分为4 种逻辑结构：、。4数据的逻辑结构在计算机中的表示称为或。5除了第1
8、 个和最后一个结点外，其余结点有且只有一个前驱结点和后继结点的数据结 构 为，每 个 结 点 可 有 任 意 多 个 前 驱 和 后 继 结 点 数 的 结 构为。6算法的 5 个重要特性是、。7数据结构中的数据元素存在多对多的关系称为_ _结构。8数据结构中的数据元素存在一对多的关系称为_ _结构。9数据结构中的数据元素存在一对一的关系称为_ _结构。10要求在 n 个数据元素中找其中值最大的元素，设基本操作为元素间的比较。则比较的次数和算法的时间复杂度分别为_ _和 _ _。11在一个单链表中p 所指结点之后插入一个s 所指结点时，应执行_ _和 p-next=s;的操作。12设有一个头指
9、针为head 的单向循环链表，p 指向链表中的结点，若p-next=_ _，则 p 所指结点为尾结点。13在一个单向链表中，要删除 p 所指结点，已知 q 指向 p 所指结点的前驱结点。则可以用操作 _ _。14 设有一个头指针为head的单向链表，p 指向表中某一个结点，且有 p-next=NULL,通过操作 _ _,就可使该单向链表构造成单向循环链表。15每个结点只包含一个指针域的线性表叫。16线性表具有和两种存储结构。17数据的逻辑结构是从逻辑关系上描述数据，它与数据的关系无关，是独立于计算机的。18 在双向循环链表的每个结点中包含指针域，其中 next 指向它的，prior指向它的，而
10、头结点的prior指向，尾结点的next指向。19单向循环链表是单向链表的一种扩充，当单向链表带有头结点时，把单向链表中尾结点的指针域由空指针改为；当单向链表不带头结点时，则把单向链表中尾结点的指针域由空指针改为指向。名师资料总结-精品资料欢迎下载-名师精心整理-第 3 页，共 7 页 -4 20线性链表的逻辑关系时通过每个结点指针域中的指针来表示的。其逻辑顺序和物理存储顺序不再一致，而是一种存储结构，又称为。三、问答题1简述数据的逻辑结构和存储结构的区别与联系，它们如何影响算法的设计与实现？2解释顺序存储结构和链式存储结构的特点，并比较顺序存储结构和链式存储结构的优缺点。3什么情况下用顺序表
11、比链表好？4头指针、头结点、第一个结点（或称首元结点）的区别是什么？名师资料总结-精品资料欢迎下载-名师精心整理-第 4 页，共 7 页 -5 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=
12、NULL;（2）;for(i=1;idata=i;if(i=1)（3）;else（4）;（5）;return(head);3 下列是在具有头结点的单向列表的第ij 个结点之间插入新结点x 的算法（1 i n+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);名师资料总结-精品资料欢迎下载-名师精心整理-第 6 页，共 7 页 -7 4下列是在具有头结点单向列表中删除第i 个结点，请在空格内填上适当的语句。int delete(NODE*head,int i)NODE*p,*q;int j;q=head;j=0;while(q!=NULL)&(jnext;j+;if(q=NULL)return(0);（1）;（2）;free(p);return(1);五、完成：实验1线性表根据实验要求（见教材P201-202）认真完成本实验，并提交实验报告。名师资料总结-精品资料欢迎下载-名师精心整理-第 7 页，共 7 页 -
