《算法与数据结构》练习及答案

习题二一、选择题在一个长度为n的顺序表中删除第i个元素（0＜i<n）(A)素。A．n-i B．n-i+1 C．n-i+1 D．i+1从一个具有n个元素的线性表中查找其值等于x的结点时，在查找成功的情况下，需平均比较(C)个元素结点。A．n/2B．nC．(n-1)/2D．(n+1)/2对一个具有n个元素的线性表，建立其单链表的时间复杂度( A)。A．O(n) B．O(1) C．O(n2） D．O（long2(D。必须是连续的 B．一定是不连续的C．部分地址必须连续 D．连续与否均可以在一个具有n个结点的有序单链表中插人一个新的结点，使得链表仍然有序，该法的时间复杂度(D )。A．O（longn）B．O（l） C．O（n2） D．O（n）2(A。一个有限序列，可以为空 B．一个有限序列，不可以为C．一个无限序列，可以为空 D．一个无限序列，不可以为ni（0(B个元素。A．n-i B．n-i＋1 C．n－i－1 D．i＋18．如果某链表中最常用的操作是取第i个结点及其前驱，则采( D)存储方式最节时间。单链表 B．双向链表 C．单循环链表 D．顺序表9．一个顺序存储线性表的第一个元素的存储地址是90，每个元素的长度是2，则第个元素的存储地址是B。A．98 B．100 C．102 D．106下列排序方法中某一趟结束后未必能选出一个元素放在其最终位置上的( C)A．堆排序 B．冒泡排序 C．直接插人排序D．快速排序对线性表进行二分查找时，要求线性表必须A．以顺序方法存储以链接方法存储C．以顺序方法存储，且结点接关键字有序排列D在顺序存储的线性表中，删除任意一个结点所需移动结点的平均移次数为( C )An Bn／2 ．(n-1)/2 D13．在线性表的下列存储结构中，读取元素花费的时间最少的是。A．单链表 B．双链表 C．循环链表 D．顺序表14．若某链表中最常用的操作为在最后一个结点之后插入一个结点和删除最后一个点，则采用（D）存储方式最节省时间。A．双链表 B．单链表 C．单循环链表 D．带头结点的双循环链二、填空题线性（Linear是最简单最常用的一种数据结构线性表中的元素存在 一对一的相互关系。直接后继线性表是_。其中n。当n。所谓顺序表其依次存放在内存中一组连续的存储单元中地址相邻的存储单元中。的。线性表的链式存储结构的每一个结点(即链域。。成了循环链表。。p的结点本身。在单链表中，删除指针P所指结点的后继结点的语句是P->next=p->next->next_。PP->prior->next＝p->next及P->next->prior=P->prior_。的链接存储表示。表示树形结构。ni(l≤i≤n+1）n-i+1个元素。删除一个长度为n的向量的第i个元素时，需向前移动n-i个元素。17．在单链表中，在指针P 所指结点的后面插人一个结点S的语句序列是S->next=P->next;P->next=S18．在双循环链表中，在指针P所指结点前插人指针S所指的结点，需执行语句p->prior->next=S;s->prior=p->prior;s->next=p;p->prior=s;19．取出广义表A＝xa，b，c，d中原子c 的函数是head(tail(tail((head(tail(head(A))))))。nO(n)。写出带头结点的双向循环链表L(L==L->Next)&&(L==L->Prior)。_结构。三、判断题线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的（错）错)顺序存储的线性表不可以随机存取（错）单链表不是一种随机存储结构（对）顺序存储结构线性表的插入和删除运算所移动元素的个数与该元素的位置无关错)顺序存储结构是动态