当前位置:首页 > 数据结构c语言版试题大全(含答案)
}slnodetype;
slnodetype *p,*q,*s;
void merge(slnodetype *la,slnodetype *lb) { slnodetype *p;
p=lb->next; Lb->next= la->next;
la->next=p->next; free(p); }
14、statas InsertDubList (DuLinkList &L, int e) {
malloc(f); f->data=Y;
if(p->next==null) {
p->next=f; f->prior=p; } else {
f->prior=p; p->next ->prior=f; f->next=p->next; p->next=f; } }
15、Statas delete(cirLinkList&L) {
If(L=null)
Error(‘nodata’); If(p→next=L) {
L→next=L; L→prior=L. Free(p); } Else {
p→prior→next=→next; p→next→prior=→prior; free(p);
- 25 -
} }
16、statas change (CirLinkList &L) {
If(L=null)
error(‘nodata’); else
If(p->next==null) error(‘can’t change’) else {
q=p->next; p->prior->next=q; q->prior=p->prior; p->next=q->next; q->next=p; p->prior=q; }
19、void MergeList_L(LinkList &La, LinkList &Lb, LinkList &Lc)
{ //已知带头结点的单链线性表La和Lb的元素按值非递减排列。归并La和Lb得到新的单链线性表Lc,Lc的元素也按值非递减排列。 LinkList pa, pb, pc; pa = La->next; pb = Lb->next;
Lc = pc = La; // 用La的头结点作为Lc的头结点 while (pa && pb) {
if (pa->data <= pb->data)
{ pc->next = pa; pc = pa; pa = pa->next; } Else
{ pc->next = pb; pc = pb; pb = pb->next; } }
pc->next = pa ? pa : pb; // 插入剩余段
free(Lb); // 释放Lb的头结点 } // MergeList_L
- 26 -
数据结构复习题:线性表 填空题
1、在线性结构中第一结点_____前驱结点,其余每个结点有且只有______个前驱结点;最后一个结点______后继结点。
2、对于顺序存储的线性表,当随机插入或删除一个元素时,约需平均移动表长______的元素。
3、对于长度为n的顺序表,插入或删除元素的时间复杂性为________;对于顺序栈或队列,插入或删除元素的时间复杂性为_________。
4、在线性表的顺序存储中,元素之间的逻辑关系是通过__________决定的;在线性表的链接存储中,元素之间的逻辑关系是通过____________决定的。
5、一个单链表中删除*p结点时,应执行如下操作: (1)q=p->next;
(2)p->data=p->next->data; (3)p->next=__________; (4)free(q);
6、对于线性表的顺序存储,需要预先分配好存储空间,若分配太多则容易造成存储空间的__________,若分配太少又容易在算法中造成__________,因此适应于数据量变化不大的情况;对于线性表的链接存储(假定采用动态结点),不需要__________存储空间,存储器中的整个__________都可供使用,分配和回收结点都非常方便,能够有效地利用存储空间,在算法中不必考虑__________的发生,因此适应数据量变化较大的情况。
7、从顺序表中删除第i个元素时,首先把第i个元素赋给__________带回,接着从_____________开始向后的所有元素均___________一个位置,最后使线性表的长度_____________。
8、向一个长度为n的顺序表中的第i个元素(0<=i<=n-1)之前插入一个元素时,需向后移动______个元素。 9、在一个长度为n的顺序表删除第i个元素(0<=i<=n-1)时,需向前移动______个元素。 10、在单链表中设置头结点的作用是___________。
11、在单链表中,要删除某一指定的结点,必须找到该结点的_______结点。 12、访问单链表中的结点,必须沿着________依次进行。
13、在双链表中,每个结点有两个指针域,一个指向________,另一个指向_________。 14、在______链表上,删除最后一个结点,其算法的时间复杂度为O(1)。
15、在一个单链表中的p所指结点之前插入一个s所指结点时,可执行如下操作。 (1)s->next=_________。 (2)p->next=s; (3)t=p->data;
(4)p->data=_________。 (5)s-.data=_________。
16、在一个单链表中删除p所指结点时,应执行以下操作: q=p->next;
p_data=p->next->data; p->next=______; free(q);
17、在一个单链表中p所指结点之后插入一个s所指结点时,应执行s->next=_______和p->next=________的操作。
18、对于一个具有n个结点的单链表,在*p结点后插入一个新结点的时间复杂度是________;在给定值为x的结点后插入一后新结点的时间复杂度是________。
- 27 -
19、在线性表的顺序存储中,元素之间的逻辑关系是通过______决定的;在线性表的链式存储中,元素之间的逻辑关系是通过______决定的。
20、在一个长度为n的顺序表中删除第i个元素(1<=i<=n)时,需向前移动_______个元素。 21、为了设置一个空的顺序表L,采用的操作是______。 22、删除顺序表的______元素,不需要移动任何元素。 23、删除顺序表的______元素,不需要移动的元素最多。
24、在顺序表_____元素后面插入一个元素,不需要移动任何元素。 25、插入顺序表的______元素,需要移动的元素最多。
26、在长度为n的顺序表L中查找指定元素值的元素,其时间复杂度为______。 27、求单链表长度的时间复杂度为_______。
28、删除单链表L中某结点*p之后的一个结点,其时间复杂度为______。 29、删除单链表L中某结点*p之前的一个结点,其时间复杂度为______。
30、在一个单链表(己知每个结点含有数据域data和指针域next)中删除p所指结点时,应执行以下操作: (1)q=p->next;
(2)p->data=q->data; (3)p->next = _____; (4)free(q);
31、在一个单链表中的p所指结点之后插入*s结点时,应执行s->next=_____和p->next______的操作。 32、对于一个具有n个结点的单链表,在*p结点后插入一个新结点的时间复杂度是_______;在给定值为x的结点后插入一个新结点的时间复杂度是_______。
33、删除双链表L中某结点*p之后的一个结点,其时间复杂度为_______。 34、删除双链表L中某结点*p之前的一个结点,其时间复杂度为_______。 35、在非循环的______链表中,可以用表尾指针代替表头指针。
36、对于双链表,在两个结点之间插入一个新结点需要修改的指针共______。 37、在一个双链表中,若要在*p结点之前插入结点*q,则执行的操作是______。 38、循环单链表L为空的条件是______。
39、在单链表中,结点与结点之间的逻辑关系不是通过存储单元的顺序来表示的,而是通过______来实现的. 40、对于一个长度为n的顺序存储的线性表,在表头插入元素的时间复杂度为____________,在表尾插入元素的时间复杂度为____________。
41、对于一个单链接存储的线性表,在表头插入结点的时间复杂度为____________,在表尾插入元素的时间复杂度为____________。
42、在线性表的顺序存储中,若一个元素的下标为i,则它的前驱元素的下标为____________,后继元素的下标为____________。
43、在线性表的单链接存储中,若一个元素所在结点的地址为p,则其后继结点的地址为____________,若p为一个数组a中的下标,则其后继结点的下标的____________。
44、在循环单链表中,最后一个结点的指针域指向____________结点。
45、在双向链表中每个结点包含有两个指针域,一个指向其____________结点,另一个指向其____________结点。
46、在循环双向链表中表头结点的左指针域指向____________结点,最后一个结点的右指针域指向____________结点。
47、在以HL为表头指针的带表头附加结点的单链表和循环单链表中,链表为空的条件分别为____________和____________。
50、在由数组a中元素结点构成的单链表中,在下标为i的结点的后面插入一个下标为j的结点时,需要进行的操作为____________和____________语句。
- 28 -
共分享92篇相关文档