数据结构习题-第2章

数据结构计算机科学与技术学院单项选择题链式存储结构，存储单元的地址（）。A．一定连续 B．一定不连续C．不一定连续 D．部分连续，部分不连续在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行。As->next=p;p->next=s;Bs->next=p->next;p->next=s;Cs->next=p->next;p=s;Dp->next=s;s->next=p;2/3/20232单项选择题链表不具有的特点是（）。A．插入、删除不需要移动元素 B．可随机访问任一元素C．不必事先估计存储空间 D．所需空间与线性长度成正比算法的计算量的大小称为计算的（）。A．效率 B．复杂性 C．现实性 D．难度若长度为n的线性表采用顺序存储结构，在其第i(1<=i<=n+1)个位置插入一个新元素的算法的时间复杂度为（）。A．O（0）B．O（1）C．O（n）D．O（n2）2/3/20233算法分析的两个主要方面是（）。A．空间复杂性和时间复杂性 B．正确性和简明性C．可读性和文档性D．数据复杂性和程序复杂性下列哪一项是链表具有的特点

。A．必事先估计存储空间B．可随机访问任一元素C．插入、删除不需要移动元素 D．逻辑地址与物理存储地址一致在顺序表中删除一个元素，需要平均移动的元素个数为（）。A．(n-1)/2 B．n/2 C．(n+1)/2 D．n-12/3/20234对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为（）。A．O(n)O(n)B．O(n)O(1) C．O(1)O(n) D．O(1)O(1)对于头指针为head的带头结点的单链表，判定该表为空表的条件是（）A．head＝＝NULL B．head->next＝＝NULLC．head->next＝＝head D．head!=NULL2/3/20235判断题1、数据项是数据的最小单位。2、数据的逻辑结构说明数据元素之间的顺序关系，它依赖于计算机的储存结构。 3、对任何数据结构链式存储结构一定优于顺序存储结构。4、顺序存储方式的优点是存储密度大，且插入、删除运算效率高。5、线性表的特点是每个元素都有一个前驱和一个后继。2/3/20236判断题线性表就是顺序存储的表。数据项是数据的基本单位，数据元素是数据的最小单位。线性表采用链接存储，必须要申请占用一片连续的存储单元。 数据结构的抽象操作的定义与具体实现有关。 2/3/20237填空题1、下面程序段的时间复杂度为________。(n>1)sum=1；for(i=0;sum<n;i++)sum+=1;2、已知指针p指向单链表L中的某结点，则删除其后继结点的语句是：________。3、带头结点的双循环链表L为空表的条件是：________。4、链接存储的特点是利用________来表示数据元素之间的逻辑关系。2/3/20238填空题5、对于双向链表,在两个结点之间插入一个新结点需修改的指针共______个，单链表为_______个6、在单链表L中，指针p所指结点有后继结点的条件是：________7、循环单链表的最大优点是：________8、顺序存储结构是通过________表示元素之间的关系的;链式存储结构是通过________表示元素之间的关系的。2/3/20239算法设计设有一个由正整数组成的无序（向后）单链表，编写能够完成下列功能的算法：（1）找出最小值结点，且打印该数值；（2）若该数值是奇数，则将其与直接后继结点的数值交换；（3）若该数值是偶数，则将其直接后继结点删除。。2/3/202310算法设计Intfunc(Linklist*L){Inttemp;Linklist*p=L->next；q=p;If(p==NULL)Return0;While(p){if(p->data<q->data)q=p;p=p->next;}Printf(“%d\n”,q->data);If(q->next==null)return0;If(q->data%2==1){temp=q->data;q->data=q->next->data;q->next->data=temp;}Else{p=q->next;q->next=p->next;free(p);}Return1;}2/3/202311算法设计在一个单链表L中，设计算法用指针P返回单链表中数据域最大的结点，并删除该结点。2/3/202312算法设计LinkedListL_MAXDEL(LinkedListL)∥L是单链表的头结点的指针{ pre=q=L;p=L->next;∥P指向最大的结点 while(q->next)∥查最后一个元素结点{if(q->next->data>p->