4、出它们分别以属于何种结构。（1）A=(K,R),其中K={a,b,c,d,e,f,g,h}R={r}r={,,,,,,}(2)B=(K,R),其中K＝{a,b,c,d,e,f,g,h}R={r}r={,,,,,,}(3)B=(K,R),其中K={1,2,3,4,5,6}R={r}r={(1,2),(2,3),(2,4),(3,4),(3,5),(3,6),(4,5),(4,6)}三、计算题
5、设n为整数，求下列各程序段的时间复杂度（1）i=1;k=2;While(ij)j=j+1;Elsei=i+1;(3)x=91;y=100While(y>0)If(x>100){x=x-10;y=y-1;}elsex=x+1;44习题2一、选择题1线性表是（A）A一个有限序列，可以为空B一个有限序列，不能为空C一个无限序列，可以为空D一个无限序列，不能为空2在一个长度为n的顺序表中，向第iI个元素（1≤i≤n+1）位置插入一个新元素
6、时，需要从后向前依次后移（B）个元素。An-iBn-i+1Cn-i-1Di3在一个顺序表的表尾插入一个元素的时间复度的量级为（B）。AO(n)BO(1)CO(n2)DO(logn)4表长为n的顺序存储的线性表，当在任意位置上插入或删除一个元素的概率相等时，插入一个元素所需移动元素的平均个数为（D），删除一个元素需要移动元素的平均个数为（A）A(n-1)/2BnC(n+1)/2Dn/25设单链表中指针p指向结点a，若要删除p之后的结点（若存在），则需修改指针的操作为（A）。Ap->next=p->next->nextBp=p->
7、nextCp=p->next->nextDnext=p6单链表的存储密度为（C）。A大于1B等于5C小于1D不能确定7在一个单链表中，若要在p所指向的结点之后插入一个新结点，则需要相继修改（B）个指针域的值。A1B2C3D48在一个单链表中，若要在p所指向的结点之前插入一个新结点，则此算法的时间复杂度的量级为（A）。AO(n)BO(n/2)CO(1)DO(n1/2)9在一个带头结点的双向循环链表中，若要在p所指向的结点之前插入一个新结点，则需要相继修改（C）个指针域的值。A2B3C4D6二、简答题1什么叫线性表？它有哪些特点？
8、2在链表的设计中，为什么通常采用带头结点的链表结构？3对比顺序表与单链表，说明顺序表与单链表的主要优点和主要缺点。444试编写算法实现顺序表的逆置，即把顺序表A中的数据元素（a1,a2,…,an）逆置为（an,an-1,…,a1）。5已知A和B为两个非递减的线性表，现要求实现
