【数据结构入门精讲 | 第四篇】考研408、企业面试表专项习题

简介: 【数据结构入门精讲 | 第四篇】考研408、企业面试表专项习题


顺序表判断题

1.对于顺序存储的长度为N的线性表,删除第一个元素和插入最后一个元素的时间复杂度分别对应为O(1)和O(N)。(错)

解析:删除第一个元素需要将数组中的所有元素向前移动一位,以填补删除元素所占用的位置。因此,时间复杂度为O(N)。

void delete_first_element(int *arr, int n) {
    for (int i = 0; i < n - 1; i++) {
        arr[i] = arr[i+1];
    }
    arr[n-1] = 0;
}

插入最后一个元素只需要将新元素添加到数组的末尾即可,时间复杂度为O(1)

for (int i = 0; i < len; i++) {
       new_arr[i] = arr[i];
      }
       new_arr[len] = element;

2.在N个结点的顺序表中访问第i(1<=i<=N)个结点和求第i(2<=i<=N)个结点直接前驱的算法时间复杂度均为O(1)。(对)

解析如下:

printf("%d %d", arr[i - 1], arr[i - 2]);

3.顺序存储方式的优点是存储密度大,且插入、删除运算效率高。 (错)

解析:顺序存储方式存储密度大但插入删除效率低。

4.对于顺序存储的长度为N的线性表,访问结点和增加结点的时间复杂度分别对应为O(1)和O(N)。(对)

解析:在插入操作时,需要将插入位置后面的元素都向后移动,以便为新元素腾出空间

5.在用数组表示的循环队列中,front值一定小于等于rear值。(错)

顺序表选择题

1.

选B,解析:

三角矩阵如下图

三对角矩阵除了第一行和最后一行是每行2个元素外,中间的每行都是三个元素。m30,30对应的元素序号为:2(第一行2个元素)+28*3+2(最后一行2个元数)=88,在数组中下标为87。

2.稀疏矩阵采用三元组存储的时候,一般需要一个行逻辑链接的顺序表,用以指出每一行的第一个非零元素在三元组中的位置。用这个顺序表的主要目的是为了_ C_。

A.更清晰表示每列元素所在位置

B.更清晰表示每行元素所在位置

C.加快算法运行效率

D.节省存储空间

解析:使用行逻辑链接的顺序表可以加快对稀疏矩阵的操作和处理速度,从而提高算法的运行效率。这个顺序表可以帮助快速访问每一行的非零元素,减少不必要的遍历和搜索操作,从而节省时间。

3.在包含 n 个数据元素的顺序表中,▁▁B▁▁ 的时间复杂度为 O(1)。

A.将 n 个元素按升序排序

B.访问第 i(1≤i≤n) 个数据元素

C.在位序 i(1≤i≤n+1) 处插入一个新结点

D.删除位序 i(1≤i≤n) 处的结点

4.已知二维数组 A 按行优先方式存储,每个元素占用 1 个存储单元。若元素 A[0][0] 的存储地址是 100,A[3][3] 的存储地址是 220,则元素 A[5][5] 的存储地址是:选D

A.301

B.295

C.306

D.300

解析:由A[0][0]和A[3][3]的存储地址可知A[3][3]是二维数组A中的第121个元素,假设二维数组A的每行有n个元素,则n x 3 + 4 = 121,n=39

所以元素 A[5][5] 的存储地址是100 + 39 * 5 + 6 -1 = 300

5.对于顺序存储的长度为N的线性表,访问结点和增加结点的时间复杂度为:C

A.O(1), O(1)

B.O(N), O(N)

C.O(1), O(N)

D.O(N), O(1)

6.若在含n个元素的顺序表中执行删除操作,设删除每个元素的概率相同,则该删除操作需移动元素的平均次数为 (n-1)/2。

解析:

要删除的个数从1~n

如果删除最后一个,则不需要移动

删除倒二个,则移动一次

删除第一个,则移动n-1次

所以一共移动(n-1)*n/2次

再除以n


解析:可以找n+1个位置插入

如果插入到最后一个后面,则不需要移动

插入到倒二个后面,则移动一次

插入到倒三个后面,则移动二次

所以一共移动(n+1)*n/2次

再除以n+1

8.在带哨兵结点的双循环链表中,设链结点的后继指针域为next,前驱指针域为prior,指针header指向哨兵结点,则判断该链表是否为空的表达式为:header->next==header 或 header->prior==header

顺序表编程题

R6-1 线性表元素的区间删除

给定一个顺序存储的线性表,请设计一个函数删除所有值大于min而且小于max的元素。删除后表中剩余元素保持顺序存储,并且相对位置不能改变。

函数接口定义:

List Delete( List L, ElementType minD, ElementType maxD );

其中List结构定义如下:

typedef int Position;
typedef struct LNode *List;
struct LNode {
    ElementType Data[MAXSIZE];
    Position Last; /* 保存线性表中最后一个元素在数组中的位置 */
};

L是用户传入的一个线性表,其中ElementType元素可以通过>、==、<进行比较;minDmaxD分别为待删除元素的值域的下、上界。函数Delete应将Data[]中所有值大于minD而且小于maxD的元素删除,同时保证表中剩余元素保持顺序存储,并且相对位置不变,最后返回删除后的表。

裁判测试程序样例:

#include <stdio.h>
#define MAXSIZE 20
typedef int ElementType;
typedef int Position;
typedef struct LNode *List;
struct LNode {
    ElementType Data[MAXSIZE];
    Position Last; /* 保存线性表中最后一个元素的位置 */
};
List ReadInput(); /* 裁判实现,细节不表。元素从下标0开始存储 */
void PrintList( List L ); /* 裁判实现,细节不表 */
List Delete( List L, ElementType minD, ElementType maxD );
int main()
{
    List L;
    ElementType minD, maxD;
    int i;
    L = ReadInput();
    scanf("%d %d", &minD, &maxD);
    L = Delete( L, minD, maxD );
    PrintList( L );
    return 0;
}
/* 你的代码将被嵌在这里 */

输入样例:

10
4 -8 2 12 1 5 9 3 3 10
0 4

输出样例:

4 -8 12 5 9 10
List Delete(List L,ElementType minD,ElementType maxD)
{
  int j=0;
  int k=L->Last;//最后一个元素的位置
  for(int i=0;i<=k;i++)
  {
    if(L->Data[i]<=minD||L->Data[i]>=maxD)
    {
      //如果该数应该被保留,则复制到新的线性表
      L->Data[j]=L->Data[i];
      j++;
    }
    else
    {
      //如果该数应该被删除
      //将原线性表的最后一个元素复制到当前位置i,同时将原线性表的最后一个元素的索引k减1
            //相当于删除了当前元素
      L->Last--;
    }
  }
}

R7-1 数组循环左移

本题要求实现一个对数组进行循环左移的简单函数:一个数组a中存有n(>0)个整数,在不允许使用另外数组的前提下,将每个整数循环向左移m(≥0)个位置,即将a中的数据由(a0a1⋯an−1)变换为(am⋯an−1a0a1⋯am−1)(最前面的m个数循环移至最后面的m个位置)。如果还需要考虑程序移动数据的次数尽量少,要如何设计移动的方法?

输入格式:

输入第1行给出正整数n(≤100)和整数m(≥0);第2行给出n个整数,其间以空格分隔。

输出格式:

在一行中输出循环左移m位以后的整数序列,之间用空格分隔,序列结尾不能有多余空格。

输入样例:

8 3
1 2 3 4 5 6 7 8

输出样例:

4 5 6 7 8 1 2 3
#include <stdio.h>
int main()
{
  int a,b;scanf("%d%d",&a,&b);int c[a];
  for(int i=0;i<a;i++)scanf("%d",&c[i]);
  int t=b%a;//对b>a的情况进行处理
    //如果左移八位,但是只有七个元素,相当于只左移了一个(取余)
  //如果t=1,则第一个元素要移动
  //如果t=2,则第二个元素要移动
  //将要移动的元素存储在另一个数组
  int d[a],j=0;
  for(int i=0;i<t;i++)
  {
    d[j]=c[i];
    j++;
  }
  //先输出不动的元素,再输出新数组中的元素
  for(int i=t;i<a;i++)
    printf("%d ",c[i]);
  for(int i=0;i<j;i++)
    printf("%d ",d[i]);
}

R7-1 最长连续递增子序列

给定一个顺序存储的线性表,请设计一个算法查找该线性表中最长的连续递增子序列。例如,(1,9,2,5,7,3,4,6,8,0)中最长的递增子序列为(3,4,6,8)。

输入格式:

输入第1行给出正整数n(≤105);第2行给出n个整数,其间以空格分隔。

输出格式:

在一行中输出第一次出现的最长连续递增子序列,数字之间用空格分隔,序列结尾不能有多余空格。

输入样例:

15
1 9 2 5 7 3 4 6 8 0 11 15 17 17 10

输出样例:

3 4 6 8
#include <stdio.h>
int main()
{
  int n;scanf("%d",&n);int a[n];for(int i=0;i<n;i++)scanf("%d",&a[i]);
  int count=1,max=1,b[n];
  b[0]=a[0];//如果没有递增子序列,则输出第一个元素
  for(int i=0;i<n-1;i++)
  {
    if(a[i]<a[i+1])//如果后一个大于前一个
    {
      count++;//个数递增
    if(count>max)//如果当前递增序列个数大于最大序列个数,就进行max和数组的赋值
    {
      max=count;
      for(int j=0;j<max;j++)
      {
        b[j]=a[i-j+1];
      }
    }
    }
    else
    {
      //如果后一个不会大于前一个,则连续递增子序列需要重新开始计算
      count=1;
    }
  }
  for(int i=max-1;i>0;i--)
  {
    printf("%d ",b[i]);
  }
  printf("%d",b[0]);
}

R7-2 求链式线性表的倒数第K项

给定一系列正整数,请设计一个尽可能高效的算法,查找倒数第K个位置上的数字。

输入格式:

输入首先给出一个正整数K,随后是若干非负整数,最后以一个负整数表示结尾(该负数不算在序列内,不要处理)。

输出格式:

输出倒数第K个位置上的数据。如果这个位置不存在,输出错误信息NULL

输入样例:

4 1 2 3 4 5 6 7 8 9 0 -1

输出样例:

7
#include <stdio.h>
int main()
{
  int a;scanf("%d",&a);
  int b[1000],count=0;
  for(int i=1;;i++)
  {
    scanf("%d",&b[i]);
    if(b[i]<0)
    break;
    count++;
  }
  printf("%d",b[count-a+1]);
}
//a[1] a[2] a[3] a[4] a[5] a[6] a[7]
//  1    2    3    4    5    6   -1
//此时count为6
//如果输出倒数第三个
//那就是a[count-3+1]
方法二:
    #include <stdio.h>
int main()
{
  int k,n=0;
  scanf("%d",&k);
  int i,a[1000];
  for(i=1;i++;)
  {
    scanf("%d",&a[i]);
    n++;
    if(a[i]<0)
    break;
  }
  a[0]=k;
printf("%d",a[n-k+1]);
}

链表判断题

1.链表是一种随机存取的存储结构。(错)

解析:链表的顺序访问是通过从头节点开始,依次遍历链表的节点来实现的,即链式存储结构。

数组是一种随机存取的存储结构,可以通过索引直接访问数组中的任意元素。

2.线性表L如果需要频繁地进行不同下标元素的插入、删除操作,此时选择顺序存储结构更好。(错)

解析:由于链式存储结构在插入和删除操作时不需要移动大量元素,只需修改指针连接,因此更适合频繁变动的情况。

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

解析:访问结点的时间复杂度为O(N),增加结点的时间复杂度为O(1)。

4.若用链表来表示一个线性表,则表中元素的地址一定是连续的。(错)

解析:链表中的节点可以在内存中的任意位置,它们通过指针连接起来形成链表结构。

使用数组来表示线性表时,数组中的元素是连续存储的。

5.将N个数据按照从小到大顺序组织存放在一个单向链表中。如果采用二分查找,那么查找的平均时间复杂度是O(logN)。(错)

如果是存放在数组中,则是对的。但由于在链表中,所以不会是logn

6.对于单循环链表,表空的表达式为header->next==header。(对)

链表选择题

1.假设某个带头结点的单链表的头指针为head,则判定该表为空表的条件是( D )

A.head= =NULL

B.head!=NULL

C.head->next= =head

D.head->next= =NULL

解析:在带头结点的单链表中,如果链表为空表,头结点的下一个指针head->next指向的也应为空。


选A,解析:“链接地址”是指结点next所指的内存地址。

3.在具有N个结点的单链表中,实现下列哪个操作,其算法的时间复杂度是O(N)? 选B

A.在地址为p的结点之后插入一个结点

B.遍历链表和求链表的第i个结点

C.删除地址为p的结点的后继结点

D.删除开始结点

解析:遍历链表需要按顺序访问每个结点,因此时间复杂度为O(N)。而求链表的第i个结点也需要遍历i个结点,所以同样具有O(N)的时间复杂度。

选项 A. 在地址为p的结点之后插入一个结点 的操作只需要修改指针连接,时间复杂度为O(1)。 选项 C. 删除地址为p的结点的后继结点 的操作也只需要修改指针连接,时间复杂度为O(1)。 选项 D. 删除开始结点的操作只需要修改头指针的指向,时间复杂度为O(1)。


选C,解析:要实现两个多项式的乘法,需要让一个多项式的每一项乘以另外一个多项式的每一项,因此这个题目的时间复杂度只跟非零项的个数有关,与最高项的指数无关。

5.已知指针ha和hb分别是两个单链表的头指针,下列算法将这两个链表首尾相连在一起,并形成一个循环链表(即ha的最后一个结点链接hb的第一个结点,hb的最后一个结点指向ha),返回ha作为该循环链表的头指针。请将该算法补充完整。

typedef struct node{
ElemType data;
    struct node *next;
}LNode;
LNode *merge(LNode *ha, LNode *hb) {
LNode *p=ha;
     if (ha==NULL || hb==NULL) {
cout<<”one or two link lists are empty!”<<endl;
          return NULL;
     }
     while ( p->next!=NULL )
           p=p->next;
     p->next=hb;
     while ( p->next!=NULL )
           p=p->next;
           _____A_____
}

A.p->next=ha; return ha;

B.ha=p->next; return p;

C.p->next=ha; return p;

D.ha=p->next; return ha;

选A,解析:在补充完整算法的过程中,首先让p指针遍历到链表ha的末尾,然后将ha的末尾指针指向hb的头部,形成循环链表。最后返回ha作为该循环链表的头指针。

6.对于一非空的循环单链表,hp分别指向链表的头、尾结点,则有:选C

A.p->next == NULL

B. p == h

C.p->next == h

D.p == NULL

解析:对于非空的循环单链表,尾结点的指针域应该指向头结点,即p->next == h

7.双链表的结点类型定义如下:

typedef struct node *link; //双链表结点指针类型

typedef struct node {// 双链表结点类型

ListItem element;//表元素

link left,//链表左结点指针

right;//链表右结点指针

}Node;

在双向链表存储结构中,删除 p 所指的结点,相应语句为:( )

A.p->right->left=p; p->right=p->right->right;

B.p->right=p->left->left; p->left=p->right->right;

C.p->left->right=p->right; p->right->left=p->left;

D.p->left=p->left->left; p->left->right=p;

解析:选C,画图即可

left-A-right left-p-right left-b-right

8.链表具有的特点是(D)。

A.可随机访问任意一个元素

B.要事先估计存储空间

C.插入删除需要移动元素

D.所需空间与线性表长度成正比

解析:A,不可。B,不需要。C,只要移动指针。D,对。

9.在单链表指针为p的结点之后插入指针为s的结点,正确的操作是__B__。

A.p->next=s;s->next=p->next

B.s->next=p->next;p->next=s

C.P->next=s;p->next=s->next

D.P->next=s->next;p->next=s

10.在需要经常查找结点的前驱与后继的场合中,使用( B )比较合适。

A.单链表 B.双链表 C.顺序表 D.循环链表

11.用链接方式存储的队列,在进行插入运算时( D ).

A. 仅修改头指针 B. 头、尾指针都要修改

C. 仅修改尾指针 D.头、尾指针可能都要修改

12.下列关于静态链表的说法错误的是( C )。

A、多条静态链表可共用一个数组空间

B、在数组空间中,静态链表中的元素可以随机存放

C、静态链表可以无限扩充

D、静态链表的指针域也称为游标,存放下一元素在数组中的下标

链表填空题

(pre)p(next)   与   (pre)q(next)是双向指向的
要在两者之间插入新的节点x,怎么操作?
解析:
x->pre=p
x->next=p->next
p->next->pre=x
p->next=x

下列代码的功能是返回带头结点的单链表L的逆转链表。

List Reverse( List L )
{
    Position Old_head, New_head, Temp;
    New_head = NULL;
    Old_head = L->Next;
    while ( Old_head )  {
        Temp = Old_head->Next;
                ;//Old_head->Next = New_head
        New_head = Old_head;  
        Old_head = Temp; 
    }
                ;//L->Next = New_head
    return L;
}

解析:代码注释如下

List Reverse( List L )
{
    Position Old_head, New_head, Temp;
    New_head = NULL;  // 初始化新链表头节点指针为NULL
    Old_head = L->Next;  // 保存原链表头节点的下一个节点
    while ( Old_head )  {
        Temp = Old_head->Next;  // 保存当前节点的下一个节点
        Old_head->Next = New_head;  // 将当前节点的Next指针指向新链表的头节点
        New_head = Old_head;  // 更新新链表的头节点为当前节点(将当前节点插入到新链表的头部)
        Old_head = Temp;  // 将当前节点移动到下一个节点
    }
    L->Next = New_head;  // 将原链表的头节点指向新链表的头节点
    return L;  // 返回反转后的链表头节点指针
}

链表函数题

R6-1 单链表分段逆转

给定一个带头结点的单链表和一个整数K,要求你将链表中的每K个结点做一次逆转。例如给定单链表 1→2→3→4→5→6 和 K=3,你需要将链表改造成 3→2→1→6→5→4;如果 K=4,则应该得到 4→3→2→1→5→6。

函数接口定义:

void K_Reverse( List L, int K );

其中List结构定义如下:

typedef struct Node *PtrToNode;
struct Node {
    ElementType Data; /* 存储结点数据 */
    PtrToNode   Next; /* 指向下一个结点的指针 */
};
typedef PtrToNode List; /* 定义单链表类型 */

L是给定的带头结点的单链表,K是每段的长度。函数K_Reverse应将L中的结点按要求分段逆转。

裁判测试程序样例:

#include <stdio.h>
#include <stdlib.h>
typedef int ElementType;
typedef struct Node *PtrToNode;
struct Node {
    ElementType Data; /* 存储结点数据 */
    PtrToNode   Next; /* 指向下一个结点的指针 */
};
typedef PtrToNode List; /* 定义单链表类型 */
List ReadInput(); /* 裁判实现,细节不表 */
void PrintList( List L ); /* 裁判实现,细节不表 */
void K_Reverse( List L, int K );
int main()
{
    List L;
    int K;
    L = ReadInput();
    scanf("%d", &K);
    K_Reverse( L, K );
    PrintList( L );
    return 0;
}
/* 你的代码将被嵌在这里 */

输入样例:

6
1 2 3 4 5 6
4

输出样例:

4 3 2 1 5 6

代码如下:

void K_Reverse(List L,int K)
{
  List H=L;
  PtrToNode p,q,w,t;//定义指针
  int num;//用于计数
  while(H)//遍历整个链表
  {
    num=0;
    p=H;//p指向当前待翻转的第一个节点
    //找到需要翻转的K个节点
    while(num<K&&p->Next)
    {
      num++;
      p=p->Next;
    }
    if(num<K)
    return;//如果不足K个节点,则退出循环
    else
    {
      //对这K个节点进行翻转操作
            t=H->Next;//t指向待翻转区间的前驱节点
      w=p->Next;//w指向待翻转区间的后继节点
      p->Next=null;//将待翻转区间的后继节点置为Null,便于后面插入节点
      //将待翻转的每个节点插入到头部节点之后
      p=H->Next;
      while(p)
      {
        q=p;//q指向当前待插入的节点
        p=p->Next;
        q->Next=H->Next;//将该节点插入到头部节点之后
        H->Next=q;
      }
      //连接待翻转区间的前驱节点和后继节点
      t->Next=w;
      //将指针H指向下一个待翻转区间的头部节点
      H=t;
    }
  }
}

链表编程题

R7-1 喊山

喊山,是人双手围在嘴边成喇叭状,对着远方高山发出“喂—喂喂—喂喂喂……”的呼唤。呼唤声通过空气的传递,回荡于深谷之间,传送到人们耳中,发出约定俗成的“讯号”,达到声讯传递交流的目的。原来它是彝族先民用来求援呼救的“讯号”,慢慢地人们在生活实践中发现了它的实用价值,便把它作为一种交流工具世代传袭使用。

一个山头呼喊的声音可以被临近的山头同时听到。题目假设每个山头最多有两个能听到它的临近山头。给定任意一个发出原始信号的山头,本题请你找出这个信号最远能传达到的地方。

输入格式:

输入第一行给出3个正整数nmk,其中n(≤10000)是总的山头数(于是假设每个山头从1到n编号)。接下来的m行,每行给出2个不超过n的正整数,数字间用空格分开,分别代表可以听到彼此的两个山头的编号。这里保证每一对山头只被输入一次,不会有重复的关系输入。最后一行给出k(≤10)个不超过n的正整数,数字间用空格分开,代表需要查询的山头的编号。

输出格式:

依次对于输入中的每个被查询的山头,在一行中输出其发出的呼喊能够连锁传达到的最远的那个山头。注意:被输出的首先必须是被查询的个山头能连锁传到的。若这样的山头不只一个,则输出编号最小的那个。若此山头的呼喊无法传到任何其他山头,则输出0。

输入样例:

7 5 4
1 2
2 3
3 1
4 5
5 6
1 4 5 7

输出样例:

2
6
4
0
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <cmath>
#include <algorithm>
#include <vector>
using namespace std;
#define PI 3.1415926535897932
#define E 2.718281828459045
#define INF 0x3f3f3f3f  // 无穷大的定义,用于表示不可达的距离
#define mod 123456789   // 取模的常数
#define N 70            // 节点的最大数量
typedef long long ll;   // 定义长整型数据类型
const int M=1005;       // 定义图的最大边数
int n,m;                // 节点数和边数
int cnt;                // 素数个数
int sx,sy,sz;           // 起点坐标
int mp[M][12];          // 存储图的邻接矩阵
int pa[M],rankk[M];     // 并查集使用的数组
int head[M*6],vis[M*10]; // 链表头和访问标记数组
double dis[M][10];      // 距离数组
ll prime[M*1000];       // 存储素数的数组
bool isprime[M*1000];   // 是否为素数的标记数组
int lowcost[M],closet[M];// 最小生成树算法中的数组
char st1[5050],st2[5050];// 字符串数组
int len[M*6];           // 每个节点对应的字符串长度数组
typedef pair<int ,int> ac; // 存储节点和距离的pair类型
vector<int> g[M*10];    // 图的邻接表表示
int dp[2005][2005];     // 动态规划数组
bool has[10000];        // 哈希表判重数组
int month[13]= {0,31,59,90,120,151,181,212,243,273,304,334,0}; // 每月的天数
int dir[8][2]= {{0,1},{0,-1},{-1,0},{1,0},{1,1},{1,-1},{-1,1},{-1,-1}}; // 八个方向的偏移量
bool isrun(int year)    // 判断是否为闰年的函数
{
    if((year%4==0&&year%100!=0)||(year%400==0))
        return true;    // 是闰年返回true
    return false;       // 不是闰年返回false
}
void getpri()           // 筛选素数的函数
{
    ll i;
    int j;
    cnt=0;
    memset(isprime,false,sizeof(isprime)); // 初始化isprime数组为false
    for(i=2; i<1000000LL; i++)  // 从2开始遍历到1000000
    {
        if(!isprime[i])prime[cnt++]=i;  // 若当前数是素数,则将其加入prime数组,并计数加一
        for(j=0; j<cnt&&prime[j]*i<1000000LL; j++)  // 将当前的素数与后面的数相乘,标记它们为非素数
        {
            isprime[i*prime[j]]=1;   // 将合数标记为true
            if(i%prime[j]==0)break;  // 若当前数能整除已有的素数,则跳出循环
        }
    }
}
ll qk_mul(ll a,ll b,ll mo)   // 快速乘运算,避免大数相乘溢出
{
    ll t=0;
    while(b)
    {
        if(b&1)
            t=(t+a)%mo;
        a=(a<<1)%mo;
        b>>=1;
    }
    t%=mo;
    return t;
}
ll qk_mod(ll a,ll b,ll mo)   // 快速模运算,避免大数取模溢出
{
    ll ans=1;
    while(b)
    {
        if(b&1) ans=qk_mul(ans,a,mo);
        a=qk_mul(a,a,mo);
        b>>=1;
    }
    ans%=mo;
    return ans;
}
int gcd(int a,int b)    // 求两个数的最大公约数
{
    return b == 0 ? a : gcd(b, a%b);
}
int bfs(int x)          // 广度优先搜索,用于找出某个节点到其他节点的最短路径
{
    int minx=x,mindis=0;// 最小节点和最短距离
    queue<ac> qu;
    qu.push(ac(x,0));    // 将起点加入队列
    vis[x]=1;            // 标记起点已访问
    while(!qu.empty())   // 队列非空时循环
    {
        ac u=qu.front();  // 取出队头节点
        int z=u.first;
        int y=u.second;
        qu.pop();         // 弹出队头节点
        if(mindis==y)     // 若当前距离和最短距离相等
        {
            minx=min(z,minx);  // 更新最小节点为较小的值
        }
        if(mindis<y)      // 若当前距离大于最短距离
        {
            mindis=y;     // 更新最短距离
            minx=z;       // 更新最小节点
        }
        for(int i=0;i<g[z].size();i++)  // 遍历当前节点的邻接节点
        {
            int v=g[z][i];
            if(!vis[v])   // 若邻接节点未被访问过
            {
                vis[v]=1;   // 标记为已访问
                qu.push(ac(v,y+1));  // 将邻接节点加入队列,并距离加一
            }
        }
    }
    if(mindis==0)
        return 0;   // 若最短距离为0,说明没有其他可达节点,返回0
    return minx;    // 返回最小节点
}
int main()
{
    int i,j,t,k;
    int u,v;
    scanf("%d%d%d",&n,&m,&k);  // 读入节点数、边数和查询次数
    for(i=1;i<=m;i++)
    {
        scanf("%d%d",&u,&v);   // 读入每条边的起点和终点
        g[u].push_back(v);     // 将边加入图的邻接表中
        g[v].push_back(u);     // 无向图,所以需要加入反向边
    }
    int ans;
    for(i=0;i<k;i++)          // 进行k次查询
    {
        memset(vis,0,sizeof(vis));  // 初始化访问标记数组为0
        scanf("%d",&u);             // 读入查询的起点
        ans= bfs(u);                // 调用bfs函数找出最短路径
        printf("%d\n",ans);         // 输出结果
    }
    return 0;
}

以上就是本篇文章的全部内容,下一篇文章中我们将介绍栈的相关知识点。

目录
相关文章
|
1月前
|
存储 算法 数据处理
数据结构从入门到精通——栈
栈,作为一种后进先出(LIFO)的数据结构,在计算机科学中扮演着重要的角色。它的特性使得它在处理函数调用、括号匹配、表达式求值等问题时具有得天独厚的优势。然而,如果我们跳出传统思维的束缚,会发现栈的用途远不止于此。
49 0
|
1月前
|
存储 缓存 算法
数据结构从入门到精通——链表
链表是一种常见的数据结构,由一系列节点组成,每个节点包含数据和指向下一个节点的指针。链表的一个显著特点是,它不需要在内存中连续存储,因此可以高效地插入和删除节点。这种灵活性使得链表在许多应用中成为理想的选择,尤其是在需要动态调整数据结构大小的场景中。
72 0
|
1月前
|
存储 消息中间件 算法
数据结构从入门到精通——顺序表
顺序表是一种常见的线性数据结构,它使用一段连续的存储单元依次存储数据元素。这种数据结构的特点是逻辑上相邻的元素在物理存储位置上也相邻,因此可以快速地访问表中的任意元素。 顺序表的实现通常依赖于数组,数组是一种静态的数据结构,一旦创建,其大小就是固定的。这意味着在顺序表中插入或删除元素可能会导致空间的浪费或不足。例如,如果在一个已经满了的顺序表中插入一个新元素,就需要重新分配更大的数组空间,并将原有元素复制到新数组中,这是一个相对耗时的操作。
51 0
|
21天前
|
存储 缓存 算法
Java入门高频考查基础知识4(字节跳动面试题18题2.5万字参考答案)
最重要的是保持自信和冷静。提前准备,并对自己的知识和经验有自信,这样您就能在面试中展现出最佳的表现。祝您面试顺利!Java 是一种广泛使用的面向对象编程语言,在软件开发领域有着重要的地位。Java 提供了丰富的库和强大的特性,适用于多种应用场景,包括企业应用、移动应用、嵌入式系统等。下是几个面试技巧:复习核心概念、熟悉常见问题、编码实践、项目经验准备、注意优缺点、积极参与互动、准备好问题问对方和知其所以然等,多准备最好轻松能举一反三。
46 0
Java入门高频考查基础知识4(字节跳动面试题18题2.5万字参考答案)
|
24天前
|
存储 NoSQL Java
Redis 数据结构操作入门
Redis 数据结构操作入门
15 0
|
1月前
|
机器学习/深度学习 存储 缓存
数据结构从入门到精通——队列
队列是一种特殊的线性数据结构,遵循先入先出(FIFO)的原则。它只允许在队列的末尾添加元素(称为入队操作),并从队列的开头移除元素(称为出队操作)。队列在多种应用中发挥着重要作用,如计算机系统的任务调度、打印机作业管理以及多线程编程中的线程同步等。
48 0
|
12天前
|
消息中间件 存储 搜索推荐
深入理解栈和队列(二):队列
深入理解栈和队列(二):队列
29 0
|
1月前
【栈】数据结构栈的实现
【栈】数据结构栈的实现
|
1月前
|
存储
数据结构--栈和队列
数据结构--栈和队列
|
1月前
|
C语言
数据结构之栈详解(C语言手撕)
数据结构之栈详解(C语言手撕)
35 1

热门文章

最新文章