C习题-链表01

标签：优先 遍历 复杂度 next 链表 01 顶点 习题

1、用邻接表表示图进行深度优先遍历时,通常是采用（）来实现算法的。 A.栈 B.队列 C.树 D.图 答案：A；

深度优先遍历(DFS)：
从某个顶点出发，一直往下一个顶点遍历，直到没有下一个顶点为止，再返回上一个顶点的其他路径继续进行深度优先，直到该出发顶点的所有深度优先遍历结束，同样的操作对每个顶点都进行一次。

广度优先遍历(BFS)：
从某个顶点出发，把所有的下一层顶点都依次遍历，结束后再对该层每个顶点广度优先遍历，直到该出发顶点的广度优先遍历结束，同样的操作对每个顶点都进行一次。

深度DFS：需要递归，使用顺序栈；广度BFS：类似层次遍历；需要循环队列。   2.下列算法的功能是什么？

/*L是无头节点单链表*/
LinkList Demo(LinkList L){
    ListNode *Q,*P;
    if(L&&L->next){
        Q=L;
        L=L->next;
        P=L;
        while(P->next)
            P=P->next;
        p->next=Q;
    }
    return L;
}

A、遍历链表 B、链表深拷贝 C、链表反转 D、单链表转变为循环链表

答案：D

Q指向链表的头节点，遍历P，使P指向链表的最后一个节点，使最后一个节点指向链表的头节点。

 

3、若广义表A满足Head(A) = Tail (A), 则A为？

A、( ) B、( ( ) ) C、( ( ), ( ) ) D、（ ），（ ），（ ）） 答案：B； 只有非空广义表才有表头和表尾这两个概念，A是一个空表。   4、线性表(a_1,a_2,a_3,...,a_n)(a1​,a2​,a3​,...,an​)以链表方式存储时,访问第i位置元素的时间复杂性为（）？ A、O(i) B、O(1) C、O(n) D、O(i-1) 答案：C；i是1到n的所有可能，所以复杂度是O（n）。   5、将N条长度均为M的有序链表进行合并，合并以后的链表也保持有序，时间复杂度为（） A、O(N * M * logN) B、O(N*M) C、O(N) D、O(M) 答案：A； （1）首先取出每个链表的第一个元素放在大小为N的数组中，此处的时间复杂度为O(N)；并调整成为小根堆，调整堆的时间复杂度为O（lgN） （2）取出数组的第一个元素。将该元素所在链表的下一个元素放在数组的第一个位置，继续调整，使之成为小根堆； （3）重复（2），如果有一个链表已经为空，则改变数组的大小。 共调整MN-1次，调整堆的时间复杂度为O(M*N*lgN）；建堆的时间复杂度为O(N)；故总的时间复杂度为 O(M*N*lgN）
 

标签：优先,遍历,复杂度,next,链表,01,顶点,习题
From： https://www.cnblogs.com/ljf-0804/p/17599033.html