发布时间 : 星期一 文章数据结构c语言版试题大全（含答案）更新完毕开始阅读13adb34dc850ad02de804116
}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、在以ＨＬ为表头指针的带表头附加结点的单链表和循环单链表中，链表为空的条件分别为____________和____________。
50、在由数组a中元素结点构成的单链表中，在下标为i的结点的后面插入一个下标为j的结点时，需要进行的操作为____________和____________语句。
- 28 -