数据结构作业2a

《数据结构作业2a》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、一、判断题。•1、通常数组采用静态内存分配进行存储，链表采用动态内存分配进行存储。（对）•2、链表在进行插入与删除操作时，根本就不需要移动数据元素。（对）•3、在查找结点时，双向链表比单链表较为迅速；在插入或删除一个具体结点时，双向链表比单链表较为费时。（对）•4、顺序存储的线性表可以按序号随机存取。（对）二、选择题。（选择题答案填入下列表格中）题号12345678答案CAAAACAC题号9101112131415答案BDBCADCò1、在有n个数据元素的链表中进行插入操作，在最坏情况下需要读取多少个元素？(A).1(B).n/2(C).n(D

2、).n/3ò2、如下链表中，f为头指针，请问结点d的数据域如何表示？fbedw^(A).((f→next)→next)→data(B).((f→next)→next)→next(C).(((f→next)→next)→next)→data(D).以上都不是ò3、在双向链表中，插入一个newnode在某node的右边，请在空格内选择正确的操作。•Voiddinsert(node_pointernode,node_pointernewnode)•{newnode→Llink=node;•newnode→Rlink=node→Rlink;•()=ne

3、wnode;•node→Rlink=newnode;}(A).node→Rlink→Llink(B).node→Llink→Rlink(C).node→Llink(D).node→Llink→Llinkò4、链表不具有的特点是什么？A.可随机访问任一元素B.插入和删除时不需要移动元素C.不必事先估计存储空间D.所需空间与线性表的长度成正比ò5、线性链表（动态）是通过什么方式表示元素之间的关系的？A.保存后继元素地址B.元素的存储顺序C.保存左、右孩子地址D.保存后继元素的数组下标ò6、设顺序表的每个元素占8个存储单元，第1个单元的存储地址是10

4、0，则第6个元素占用的最后一个存储单元的地址是什么？A.139B.140C.147D.148ò7、设顺序表的长度为n，并设从表中删除元素的概率相等，则在平均情况下，从表中删除一个元素需移动的元素个数是什么？A.(n-1)/2B.n/2C.n(n-1)/2D.n(n+1)/2ò8、在线性链表存储结构下，插入操作算法的操作如何？A.需要判断是否表满B.需要判断是否表空C.不需要判断表满D.需要判断是否表空和表满ò9、带头结点的单链表head为空的判断条件是（）。A.head==NULLB.head->next==NULLC.head->next=h

5、eadD.head!=NULLò10、若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（）存储方式最节省运算时间。A.单链表B.仅有头指针的单循环链表C.双链表D.仅有尾指针的单循环链表ò11、线性表的静态链表存储结构与顺序存储结构相比优点是（）。A.所有的操作算法简单B.便于插入和删除C.便于利用零散的存储器空间D.便于随机存取ò12、长为n的线性表采用顺序存储结构，在第i个位置插入一个新元素的算法时间复杂度为（）。A.O(logn)B.O(1)C.O(n)D.O(n2)注：长为n的线性表采用顺序存储结构，在第

6、i个位置插入一个新元素需要移动次数为O(n-i+1)＝O(n).ò13、将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数为（）。A.nB.2n-1C.2nD.n-1注：当一个表的最小元素大于另一个表的最大元素时比较次数最少，共需n次比较。ò14、在双循环链表p所指结点之后插入s所指结点的操作是（）。A.p->next=s;s->prior=p;p->next->prior=s;s->prior=p->next;B.p->next=s;p->next->prior=s;s->prior=p;s->next=p->next;C.s->p

7、rior=p;s->next=p->next;p->next=s;p->next->prior=s;D.s->prior=p;s->next=p->next;p->next->prior=s;p->next=s;ò15、在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q结点和p结点之间插入s结点，则执行（）。A.s->next=p->next;p->next=s;B.p->next=s->next;s->next=p;C.q->next=s;s->next=p;D.p->next=s;s->next=q;三、算法编程题。3.1将一顺序

8、表A中的元素逆置。如原来顺序表A中元素是100,90,80,70,60,50,40逆置以后为40,50,60,70,80,90,100要求算法所用的辅