作业5-单链表

痛定思痛。 2022-12-25 00:51 58阅读 0赞

1-1  
在具有N个结点的单链表中，  
访问结点和增加结点的时间复杂度分别对应为O(1)和O(N)。(F)

1-2  
若用链表来表示一个线性表，则表中元素的地址一定是连续的。(F)

1-3  
将长度分别为m,n的两个单链表合并为一个单链表的时间复杂度为O(m+n)。(F)  
\[解析\]只考虑合并操作的话 是O(1),就是把一个链表的尾指针指向  
下一个链表的首元素.

1-4  
(neuDS)单链表不是一种随机存取的存储结构。(T)

2-1  
设h为不带头结点的单向链表。在h的头上插入一个新结点t的语句是：(D)  
A.h=t; t->next=h->next;  
B.t->next=h->next; h=t;  
C.h=t; t->next=h;  
D.t->next=h; h=t;  
\[解析\]没有头结点

2-2  
在单链表中，若p所指的结点不是最后结点，在p之后插入s所指结点，则执行©  
A.s->next=p; p->next=s;  
B.s->next=p->next; p=s;  
C.s->next=p->next; p->next=s;  
D.p->next=s; s->next=p;

2-3  
带头结点的单链表h为空的判定条件是：(B)  
A.h == NULL;  
B.h->next == NULL;  
C.h->next == h;  
D.h != NULL;

2-4  
将两个结点数都为N且都从小到大有序的单向链表  
合并成一个从小到大有序的单向链表，  
那么可能的最少比较次数是：(B)  
A.1  
B.N  
C.2N  
D.NlogN  
\[解析\]L1max <= L2min

2-5  
线性表若采用链式存储结构时，要求内存中可用存储单元的地址(B)  
A.必须是连续的  
B.连续或不连续都可以  
C.部分地址必须是连续的  
D.一定是不连续的

2-6  
在具有N个结点的单链表中，实现下列哪个操作，  
其算法的时间复杂度是O(N)？©  
A.在地址为p的结点之后插入一个结点  
B.删除开始结点  
C.遍历链表和求链表的第i个结点  
D.删除地址为p的结点的后继结点

2-7  
对于一个具有N个结点的单链表，  
在给定值为x的结点后插入一个新结点的时间复杂度为©  
A.O(1)  
B.O(N/2)  
C.O(N)  
D.O(N2)

2-8  
链表不具有的特点是：(B)  
A.插入、删除不需要移动元素  
B.方便随机访问任一元素  
C.不必事先估计存储空间  
D.所需空间与线性长度成正比

2-9  
(neuDS)在一个含有n个结点的有序单链表中插入一个新结点，  
使单链表仍然保持有序的算法的时间复杂度是()。©  
A.O(1)  
B.O(log2n)  
C.O(n)  
D.O(n2)  
\[解析\]查找的时间复杂度是O(N)

2-10  
将长度为n的单链表连接在长度为m的单链表之后的算法的时间复杂度为()。(B)  
A.O(1)  
B.O(m)  
C.O(n)  
D.O(n+m)

2-11  
(neuDS)在单链表中，增加一个头结点的最终目的是为了()。(B)  
A.使单链表至少有一个结点  
B.方便运算的实现  
C.标识表结点中首结点的位置  
D.说明单链表是线性表的链式存储  
\[解析\]不清楚原因

2-12  
在单链表中，要删除某一指定结点，必须先找到该结点的()。()  
A.直接前驱  
B.自身位置  
C.直接后继  
D.直接后继的后继  
\[解析\]找到的直接前驱用来连接直接后继

2-13  
以下关于链式存储结构的叙述中，()是不正确的。©  
A.结点除自身信息外还包括指针域，因此存储密度小于顺序存储结构  
B.逻辑上相邻的结点物理上不必邻接  
C.可以通过计算直接确定第i个结点的存储地址  
D.插入、删除运算操作方便，不必移动结点

2-14  
线性链表不具有的特点是()。(A)  
A.随机访问  
B.不必事先估计所需存储空间大小  
C.插入与删除时不必移动元素  
D.所需空间与线性长度成正比

2-15  
线性表若采用链式存储结构时，要求内存中可用存储单元的地址()。(D)  
A.必须是连续的  
B.部分地址必须是连续的  
C.一定是不连续的  
D.连续或不连续都可以

2-16  
对线性表，在下列情况下应当采用链表表示的是()。(B)  
A.经常需要随机地存取元素  
B.经常需要进行插入和删除操作  
C.表中元素需要占据一片连续的存储空间  
D.表中的元素个数不变

2-17  
不带表头附加结点的单链表为空的判断条件是头指针head满足条件()。(A)  
A.headNULL  
B.head->nextNULL  
C.head->next== head  
D.head!=NULL

2-18  
可以用带表头附加结点的链表表示线性表，  
也可以用不带头结点的链表表示线性表，前者最主要的好处是()。(B)  
A.可以加快对表的遍历  
B.使空表和非空表的处理统一  
C.节省存储空间  
D.可以提高存取表元素的速度

2-24  
线性表L在什么情况下适用于使用链式结构实现？(A)  
A.需不断对L进行删除插入  
B.需经常修改L中的结点值  
C.L中含有大量的结点  
D.L中结点结构复杂

2-25  
线性表采用链式存储时，其地址()。(D)  
A.必须是连续的  
B.一定是不连续的  
C.部分地址必须是连续的  
D.连续与否均可以

6-2 单链表元素定位 (12分)
    int ListLocate_L(LinkList L, ElemType x)
    {
        
    	LNode *p = L->next;
    	int i = 1;
    	while (p != NULL)
    	{
        
    		if (p->data == x)
    			break;
    		i++;
    		p = p->next;
    	}
    	if (p == NULL) return 0;
    	else return i;
    }
    
    6-3 删除单链表中最后一个与给定值相等的结点 (10分)
    void ListLocateAndDel_L(LinkList L, ElemType x)
    {
        
    	LNode *tgt_p = NULL;
    	LNode *prep = L;
    	LNode *p = L->next;
    	while (p != NULL)
    	{
        
    		if (p->data == x)
    		{
        
    			tgt_p = prep;
    		}
    		prep = p;
    		p = p->next;
    	}
    	//没有和x相等的元素
    	if (tgt_p == NULL) return ;
    	else 
    	{
        
    		p = tgt_p->next;
    		tgt_p->next = p->next;
    		free(p);
    	}
    }