数据结构 李学刚 单元2 同步训练及答案

1、单元2 同步训练及参考答案同步训练一、单项选择题1线性表是（ ）的有限序列。 A数据B数据项C数据元素D表元素2以下关于线性表的说法不正确的是（ ）。A线性表中的数据元素可以是数字、字符、记录等不同类型。B线性表中包含的数据元素个数不是任意的。C线性表中的每个结点都有且只有一个直接前驱和直接后继。D存在这样的线性表：表中各结点都没有直接前驱和直接后继。3顺序表是线性表的（ ）。A链式存储结构B顺序存储结构C索引存储结构D散列存储结构4对于顺序表的优缺点，以下说法错误的是（ ）。A无需为表示结点间的逻辑关系而增加额外的存储空间B可以方便地随机存取表中的任一结点C插入和删除运算较方便D容易造成一部分空间长期闲置而得不到充分利用5在顺序表中，只要知道（ ），就可在相同时间内求出任一结点的存储地址。A基地址B结点存储长度C向量大小D基地址和存储长度 6一个顺序表第一个元素的存储地址是100，每个元素的存储长度为4，则第5个元素的地址是（ ）。A110B116C100D120 7一个长度为n的顺序表中，在第i（1in+1）个元素的位置上插入一个新元素时，需要向后移动个元素。An-iBn-i+1C

2、n-i-1Di 8一个长度为n的顺序表中，删除第i（1in）个元素时，需要向前移动（ ）个元素。An-i Bn-i+1Cn-i-1Di 9在一个长度为n的顺序表中插入一个结点需平均移动（ ）个结点。A（n+1）/2Bn/2C（n-1）/2Dn 10在一个长度为n的顺序表中删除一个结点需平均移动（ ）个结点。A（n+1）/2Bn/2 C（n-1）/2 Dn 11在（ ）情况下应当选择顺序表作为数据的存储结构。A对线性表的主要操作为插入操作 B对线性表的主要操作为插入操作和删除操作 C线性表的表长变化较大 D对线性表的主要操作为存取线性表的元素 12下列算法实现在顺序表L的第i（1iL-length+1）个结点的位置上插入值为t的元素，其中ListSize为顺序表L的容量，表中第1个结点的数据存放在数组元素L-data0中。下列选项中能完成此功能的语句序列为（ ）。int InsertList(SeqList *L,DataType t,int i)/将t插入顺序表L的第i个结点的位置上int j;if (iL-length+1)puts(插入位置错);return 0; if (L-le

3、ngth=ListSize)puts(表满不能插入); return 0;for(j=L-length-1;j=i-1;j-)/结点依次后移/插入t/表长加1return 1;AL-dataj-1=L-dataj; L-datai=t; L-length+1; BL-dataj-1=L-dataj; L-datai-1=t; L-length+; CL-dataj+1=L-dataj; L-datai-1=t; L-length+;DL-dataj+1=L-dataj; L-datai=t; L-length+1; 13下列算法实现删除顺序表L的第i（1iL-length）个结点，表中第1个结点的数据存放在数组元素L-data0中。下列选项中能完成此功能的语句序列为（ ）。int DeleteList(SeqList *L,int i)/从顺序表L中删除第i个结点int j;if (iL-length) puts(删除位置错); return 0; if (L-length=0)puts(空表不能删除); return 0; for(j=i;jlength-1;j+)/结点依次前移/表

4、长减1return 1;AL-dataj-1=L-dataj; L-length-1; BL-dataj-1=L-dataj; L-length-; CL-dataj+1=L-dataj; L-length-; DL-dataj+1=L-dataj; L-length-1; 14下列算法实现在顺序表L中查找值为t的结点，找到返回位置值i，否则返回-1，表中第1个结点的数据存放在数组元素L-data0中。下列选项中能完成此功能的选项为（ ）。int SearchList(SeqList *L,DataType t)/从顺序表L中查找值为t的结点，找到返回位置值i，否则返回-1int i=1;while (ilength& )i+;if( ) return i;elsereturn -1;AL-datai-1 =t L-datai-1!=t BL-datai-1!=t L-datai-1!=t CL-datai-1=t L-datai-1=t DL-datai-1!=t L-datai-1=t 15下列算法实现对顺序表L的划分。下列选项中能完成此功能的语句序列为（ ）。void Part(

5、SeqList *L)int i,j;DataType x,y;/用于存放基准和当前小于基准的结点x=L-data0;/将基准置入x中for(i=1;ilength;i+)if(L-datai=0;j-)Ay=x; L-dataj-1= L-dataj; L-data0=x; By=L-datai; L-dataj+1= L-dataj; L-data0=y; Cy=L-datai; L-dataj-1= L-dataj; L-data0=x; Dy=L-datai; L-dataj-1= L-dataj; L-data0=y; 16在单链表的一个结点中有（ ）个指针。A1B2C3D4 17设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用（ ）最节省时间。A单链表B单循环链表 C带尾指针的单循环链表D带头结点的双循环链表18若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ ）存储方式最节省时间。A顺序表B双链表 C带头结点的双循环链表D单循环链表19在单链表指针为p的结点之后插入指针为s的结点，正确的操作是（ ）。 Ap-next=s;s-n

6、ext=p-next; Bs-next=p-next;p-next=s; Cp-next=s;p-next=s-next; Dp-next=s-next;p-next=s;20对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是（ ）。Ahead=NULL Bhead-next=NULLChead-next=headDhead!=NULL21在双向链表指针p的结点前插入一个指针q的结点操作是（ ）。Ap-prior=q;q-next=p;p-prior-next=q;q-prior=q; Bp-prior=q;p-prior-next=q;q-next=p;q-prior=p-prior; Cq-next=p;q-prior=p-prior;p-prior-next=q;p-prior=q; Dq-prior=p-prior;q-next=q;p-prior=q;p-prior=q; 22在一个具有 n 个结点的有序单链表中插入一个新结点，并使插入结点后的单链表仍然有序，则该操作的时间复杂性量级为（ ）。AO（1）BO（n）CO（nlog2n）DO（n2） 23在一个单链

7、表中，若删除P所指结点的后续结点，则执行（ ）。Ap-next=p-next-next; Bp=p-next;p-next=p-next-next;Cp-next=p-next; Dp=p-next-next; 24不带头结点的单链表head为空的判定条件是。Ahead=NULL Bhead-next=NULL Chead-next=headDhead!=NULL25链表不具有的特点是（ ）。A插入、删除不需要移动元素 B可随机访问任一元素C不必事先估计存储空间 D所需空间与线性长度成正比二、问题解答题1已知线性表的存储结构为顺序表，阅读下列算法，并回答问题：(1)设线性表L=（21，-7，-8，19，0，-11，34，30，-10），写出执行fun(&L)后的L状态；(2)简述算法fun的功能。void fun(SeqList *L)int i,j;for(i=j=0;ilength; i+)if(L-datai=0)if(i!=j)L-dataj=L-datai;j+;L-length=j;2阅读下列算法，并回答问题：(1)设顺序表L=(3,7,11,14,20,51)，写出执行fun(&L,15)之后的L；(2)设顺序表L=(4,7,10,14,20,51)，写出执行fun(&L,10)之后的L；(3)简述算法的功能。void fun(SeqList *L, DataType x)int i =0, j;while (ilength & xL-datai) i+;if(ilength & x=L-datai)for(j=i+1;jlength;j+)L-dataj-1=L-dataj;L-length-;elsefor(j=L-length;ji;j-)L-dataj=L-dataj-1;L-datai=x;L-length+;

《数据结构 李学刚 单元2 同步训练及答案》由会员清晨86****784分享，可在线阅读，更多相关《数据结构 李学刚 单元2 同步训练及答案》请在金锄头文库上搜索。