请选择 进入手机版 | 继续访问电脑版

牛客刷题笔记--(数组专项练习1-50)

[复制链接]
云韵 发表于 2021-1-2 19:45:44 | 显示全部楼层 |阅读模式 打印 上一主题 下一主题
知识点

设一维数组中有n个数组元素,则读取第i个数组元素的匀称时间复杂度为(O(1))
稀疏矩阵一般接纳三元组顺序表方法压缩存储
数组作为函数参数通报的是数组的首地点
在二分查找中,如果剩下的子序列有奇数个数字,就取中间谁人为middle。如果有偶数个数字,取前一半的最后一个为middle
数组静态分配内存,链表动态分配内存;
数组在内存中一连,链表不一连;
数组元素在栈区,链表元素在堆区;
数组使用下标定位,时间复杂度为O(1),链表定位元素时间复杂度O(n);
数组插入或删除元素的时间复杂度O(n),链表的时间复杂度O(1)。
线性表接纳链式存储时,其地点一连与否均可。线性表的链式存储可用一连或不一连的存储单位来存储线性表中的元素,也即线性表中的元素存储地点一连与否均可。 王道考研2019版第四页第七题提到,链式存储设计时,结点内的存储单位地点一定一连。因此许多同学认为此题应选部分地点必须一连。这里的部分应指结点间,而非结点内。
线性表若接纳链式存储体现时所有结点之间的存储单位地点可一连可不一连。
顺序存储,占用内存的地点一连,体现为数组,插入删除,需要移动当前下标以后的数据的位置; 链式存储,占用非一连的内存地点,每个节点都有数据data部分以及next指针,故插入删除只需要改变指针的指向就行,不需要移动数据位置。
线性表可以为空 ,除第一个和最后一个元素外,别的每个元素都有且仅有一个直接前驱和直接后继
练题

1 下面哪项是数组优于链表的特点? D
  1. 方便删除方便插入长度可变存储空间小
复制代码
1: 数组内存空间少比链表少
2:数组支持随机访问,链表不具有随机访问的特性
3:插入和删除是链表优于数组,数组需要移动被删除大概插入位置之后的元素
https://blog.csdn.net/u014082714/article/details/44259029
D 链表要生存指向下个节点的指针,占用空间比数组更大
2 在C++中,以下界说和初始化的两数组a1和a2,那么下列说法正确的是( D)。
  1. a1和a2完全相同a1和a2差别,a1是指针a1和a2存储单位的数目相同a1和a2差别,a1的存储单位数目多
复制代码
a1中存储的是字符串,因此在末端存在字符’\0’;而a2中没有’\0’字符,所以sizeof(a1)=8,sizeof(a2)=7,a1存储单位数目多
3 以下二维数组声明中,正确的是( B)。
  1. char b[2][3]={"a","b","c"};char b[][3]={0};char b[2][]={0};char b[][]={0}
复制代码
A.char str[2][3]体现声明白一个字符串的数组,最多可以存放两个字符串,每一个字符串的长度为3。题中{“a”,“b”,“c”}为三个字符串。
C.在声明数组时,数组个数可以缺省,数组长度不能缺省。该项中数组长度缺省。
D.同上。
4 数组A=array[1…100,1…100]以行序为主序存储,设每个数据元素占2个存储单位,基地点为10,则LOC[5,5]应为C
  1. 10201010818808
复制代码
[(5-1)*100+(5-1)]*2+10=818,第一个5体现以行为序列,所以要使用列中的5,而不是使用行中的5,纵然用A[5][5]中的第二个5,即(5-1)100(这里的100体现列,相当于A[100][100]中的第二个100,),因为行和列都是从1开始,所以行和列都要-1,每个数据元素占2个存储,所以行和列都要2,基地点为10,意思为首地点为10,所以选818
5 以下使用中,数组比链表速度更快的是____ACE
  1. 原地逆序头部插入返回中间节点返转头部节点选择随机节点
复制代码
A选项,如果是数组只要遍历一半元素就可以了,翻转的思想类似于字符串逆序,但链表如果要完成逆序,就算只是修改指针也要把所有的元素遍历完,所以相比而言数组照旧比链表快的。
B链表只需插入一个节点,数组需移动n个元素
C选项的访问中间节点,数组可以通过array[length/2]访问,链表需要依次查找到中间节点。
D头结点都一样
E 数组是顺序存储的线性表,相对于链表而言主要的优点就是可以通过下标随机访问数组中的任意元素。
6 在表长为n的顺序表上做插入运算,匀称要移动的结点数为(C ) 。
  1. n/4n/3n/2n
复制代码
假设长度为n数组a, 从数组最前(插到a[0]前)到最后(插到a[n-1]后)共n+1种情况,分别需要移动n,n-1,…,0次,每种情况等概率P=1/(n+1), 盼望为(n+n-1+…+0)/(n+1) = (1+n)*n/2/(n+1)=n/2
7 需要频仍的插入删除使用使用什么布局比力符合?C
  1. 数组队列链表栈
复制代码
A,数组是一连地点的,插入和删除都需要移动大量元素,不适合插入删除使用
B,队列适合一端插入另一端删除的情况
C,链表适合插入和删除,不需要移动元素
D, 栈适合在同一端插入和删除的使用
在四种布局中,数组是一连占据一块空间,如果举行插入等使用,在中间数据的话就比力困难。而队列和栈,一个是先进先出,一个后进先出,对于插入等更是困难。链表的话,通过修改前一个结点的指向地点,然后将先前指向地点放进去新添加的即可。
数组和链表方式实现顺序表,各有其优缺点。数组的优点是较高的存储效率和快速的随机存取,缺点是数组不能动态的增长,而且在插入和删除时,匀称会移动n/2的数据,不适用于随机位置插入和删除很频仍的使用。而链表则恰好具备此优点,一般来说链表的插入和删除根本是固定时间的,链表的缺点是不太适合于随机访问,而在一连访问时,链表也具有很好的体现。
队列(queue)和栈是一种使用受限的线性表。栈的使用受限体现在插入和删除只能对栈顶元素举行,删除的元素永远是最新插入的,即使用遵循后入先出(LIFO)原则。队列中的使用原则与栈的相反。删除的元素是最早插入到队列中的,就像列队一样,排在最前面的人将最先从队伍中出列。这样的使用原则常常称作先入先出。所以对于栈和队列的频仍随机插入删除不符合
8 以下能对一维数组 a 举行正确初始化的语句是( BC )
  1. int a[10]=(0, 0, 0, 0, 0);int a[10]={  };int a[]={0};int a[10]={10*a};
复制代码
9 顺序存储布局的主要缺点是倒霉于插入或删除使用(√)
在盘算机中用一组地点一连的存储单位依次存储线性表的各个数据元素,称作线性表的顺序存储布局.
顺序存储布局是存储布局范例中的一种,该布局是把逻辑上相邻的节点存储在物理位置上相邻的存储单位中,结点之间的逻辑关系由存储单位的毗连关系来体现。由此得到的存储布局为顺序存储布局,通常顺序存储布局是借助于盘算机步调设计语言(比方c/c++)的数组来形貌的。
顺序存储布局的主要优点是节流存储空间,因为分配给数据的存储单位全用存放结点的数据(不思量c/c++语言中数组需指定巨细的情况),结点之间的逻辑关系没有占用额外的存储空间。接纳这种方法时,可实现对结点的随机存取,即每一个结点对应一个序号,由该序号可以直接盘算出来结点的存储地点。但顺序存储方法的主要缺点是未便于修改,对结点的插入、删除运算时,大概要移动一系列的结点。
**10 稀疏矩阵一般的压缩存储方式有两种,即 **
  1. 三元组和十字链表
复制代码
所谓三元组就是一个元素存放三个信息,矩阵中的行号,列号以及值,这样就可以不存放值为0的元素,实现压缩。 十字链表相当于是毗连表和逆毗连表的合集,在一个元素内里存放了值以及出度表和入度表,这样也不需要像毗连矩阵那样存放大量0元素,而且找一个节点的入节点和找出节点一样快。
11 数组Q[0…m-1]用来体现一个循环队列, 用front指向队头元素,rear指向队尾元素的后一个位置 ,则当前队列中的元素数是。(队列总的元素数不会凌驾队列巨细) A
  1. (rear-front+m)% mrear-front+1rear-front-1rear-front
复制代码
因为是循环链表 rear不一定就比front地点高 所以有大概rear-fornt得到效果是负数 所以为了正确性起见需要+m再%m
12 长度为n 的非空顺序表,若在第i个位置插入新的元素X,则i的取值范围是 1≤i≤n+1,需要移动的元素个数为( D )。
  1. in-i-1n-in-i+1
复制代码
新的元素替换掉了原来在i的元素,原先在i位置上的元素以及背面元素都往后移,所以需要 + 1
13 在一个有8个int数据的数组中,随机给出数组的数据,找出最大和第二大元素一定需要举行(B)次比力:
  1. 891011
复制代码
14 若数组A[0…m-1][0…n-1]按列优先顺序存储,则aij地点为( A)。
  1. LOC(a00)+[j*m+i]LOC(a00)+[j*n+i]LOC(a00)+[(j-1)*n+i-1]LOC(a00)+[(j-1)*m+i-1]
复制代码
以0开始,下标是几就是多少个,从1开始,下标减1
15 下列叙述中正确的是( A)。
  1. 顺序存储布局的存储一定是一连的,链式存储布局的存储空间不一定是一连的顺序存储布局只针对线性布局,链式存储布局只针对非线性布局顺序存储布局能存储有序表,链式存储布局不能存储有序表链式存储布局比顺序存储布局节流存储空间
复制代码
1.顺序表的特点是逻辑上相邻的数据元素,其物理存储位置也相邻,而且顺序表的存储空间需要预先分配;
2.链式存储中逻辑上相邻的数据元素其物理存储位置不一定相邻,是因为链表通过指针实现元素间的逻辑关系;
3.顺序存储布局适合频仍的查询时使用,链式存储布局适合频仍的插入,删除和更新元素时使用
链式存储布局既可以针对线性布局也可以针对非线性布局,所以B与C错误。链式存储布局中每个结点都由数据域与指针域两部分组成,增加了存储空间,所以D错误
常见线性布局包罗:线性表,栈,队列,数组 常见非线性布局:二维数组,***数组,广义表,树,图 Java中队列都可以通过LinkedList实现,说明链式布局可以实现线性布局
16 希望用最快的速度从一个无序数组中挑选出此中前十个最大的元素,在以下的排序方法中(B)
  1. 快速排序堆排序归并排序基数排序
复制代码
用堆排序最好,因为堆排序不需要等整个排序竣事就可挑出前50个最大元素,而快速排序和基数排序都需期待整个排序竣事才华知道前50个最大元素。
17 请问对一个排好序的数组举行查找,用匀称时间复杂度最小的算法,时间复杂度为(B)
  1. O(n)O(lgn)O(nlgn)O(1)
复制代码
二分查找的根本思想是将n个元素分成大抵相等的两部分,去a[n/2]与x做比力,如果x=a[n/2],则找到x,算法中止;如果xa[n/2],则只要在数组a的右半部搜索x.
时间复杂度无非就是while循环的次数!
总共有n个元素,
徐徐跟下去就是n,n/2,n/4,…n/2^k,此中k就是循环的次数
由于你n/2^k取整后>=1
即令n/2^k=1
可得k=log2n,(是以2为底,n的对数)
所以时间复杂度可以体现O()=O(logn)
18 便于插入和删除的容器是(ACD)
  1. listvectormapset
复制代码
1.list 底层数据布局为双向链表,支持快速增删
2.vector 底层数据布局为数组,支持快速随机访问
3.map 底层数据布局为红黑树,除了hashmap无序,其他实现布局有序,不重复
4.set 底层数据布局为红黑树,除了hashset无序,其他实现布局有序,不重复
19 线性表就是顺序存储的表(B)(×)
线性布局与非线性布局,主要看元素之间的关系,如果是一对一的关系则是线性表,如果不是一对一的关系则是非线性表。
线性表可以分顺序存储和链式存储。
线性布局包罗顺序存储布局和链接存储布局。所以线性表有两种情况。除了线性布局尚有非线性布局,如:树,图。栈和队列就是用线性布局实现的,它自己就是一种布局。可以把栈和队列归在线性布局中
线性表包罗顺序存储布局(即顺序表)和链式存储布局(即链表)。但是线性表、树、图 是三种差别的数据布局,树和图不属于线性表的链式布局。
因为数据布局,从逻辑上来分的话,可分为:聚集布局、 线性布局、 树形布局、 图形布局。
但是,如果从存储布局来分类,就只有:顺序存储布局和链接存储。 所以,线性布局固然也可分为这两类。
20 假设要存储一个数据集,数据维持有序,对其的使用只有插入、删除温顺序遍历,综合存储效率和运行速度,下列哪种数据布局是最适合的是?B
  1. 数组链表哈希表队列
复制代码
数组插入、删除需要移动数组元素,匀称移动n/2
哈希表难以实现顺序遍历
队列插入删除效率低下
数组可以实现顺序遍历但是插入删除使用复杂,匀称移动n/2个元素
链表因为存储的地点不一连(逻辑上一连实际上不一连),可以实现顺序遍历
哈希表是随机存储,所以是离散分布,顺序遍历实现不了
队列只可以在队尾插入队头删除,不可以实现中间插入和删除,不满足条件
综上,链表最符合
21 线性表的顺序存储布局是一种(A) 的存储布局,线性表的链式存储布局是一种顺序存取 的存储布局。
  1. 随机存取顺序存取索引存取散列存取
复制代码
顺序存储布局中,数据元素存放在一组地点一连的存储单位中,每个数据元素地点可通过公式LOC(ai)=LOC(a1)+(i-1)L盘算得到,从而实现了随机存取。对于链式存储布局,要对某结点举行存取,都得从链的头指针指向的结点开始,这是一种顺序存取的存储布局。
一:顺序表的特点是逻辑上相邻的数据元素,物理存储位置也相邻,而且,顺序表的存储空间需要预先分配。
它的优点是:
(1)方法简朴,各种高级语言中都有数组,容易实现。
(2)不消为体现节点间的逻辑关系而增加额外的存储开销。
(3)顺序表具有按元素序号随机访问的特点。
缺点:
(1)在顺序表中做插入、删除使用时,匀称移动表中的一半元素,因此对n较大的顺序表效率低。
(2)需要预先分配足够大的存储空间,估计过大,大概会导致顺序表后部大量闲置;预先分配过小,又会造成溢出。
二、在链表中逻辑上相邻的数据元素,物理存储位置不一定相邻,它使用指针实现元素之间的逻辑关系。而且,链表的存储空间是动态分配的。
链表的最大特点是:
插入、删除运算方便。
缺点:
(1)要占用额外的存储空间存储元素之间的关系,存储密度低落。存储密度是指一个节点中数据元素所占的存储单位和整个节点所占的存储单位之比。
(2)链表不是一种随机存储布局,不能随机存取元素。
*22 若有说明语句“int a[10],p=a;”,对数组元素的正确引用是 D
  1. a[p]p[a]p+2*(p+2)
复制代码
注意 是对数组中元素的引用 a为数组名 也代表数组首元素的地点值 p=a则p也指向数组a的第一个元素地点,则(p+2)指向数组a中第三个元素
23 数组界说为”int a[4][5];”, 引用”*(a+1)+2″体现()(从第0行开始)B
  1. a[1][0]+2a数组第1行第2列元素的地点a[0][1]+2a数组第1行第2列元素的值
复制代码
a是个行指针,a+1后指向下一行,*(a+1)后变成一个列指针,再+2仍为列指针,指向a数组第一行第二列的元素,选B。题目形貌的禁绝确,第一行也可认为是a[0]。按照给的选项只能选B
23 如果剩下的子序列有奇数个数字,就取中间谁人为middle。如果有偶数个数字,取前一半的最后一个为middle。 A
  1. 12,18,14,1612,14, 18,166,9,7,86,7,9,8
复制代码
如果剩下的子序列有奇数个数字,就取中间谁人为middle。如果有偶数个数字,取前一半的最后一个为middle。
第一次查找到12之后,做指针要移动到12的下一个数再继续查找
24 设循环队列中数组的下标范围是1~n,其头尾指针分别为f和r,则其元素个数为(D)
  1. r-fr-f+1(r-f) mod n +1(r-f+n) mod n
复制代码
循环队列会空出一个位置,为了判断队列为满的状态,即当(rear+1)mod n==front为满,所以牺牲一个空格,所以rear-front的绝对值为队列中元素的个数(因为rear指向一个尚未填入元素的内存,所以不消加1),(rear-front+n)就是为了包管绝对值,所以为(r-f+n)mod n
举个例子,一个循环队列,队列长度N=10,下标从1-9,可以或许储存9个元素,index=0处为空。初始时,头指针下标为1,尾指针下标为1。当从队尾入队一个元素,尾指针下标移动,当从队首出队一个元素,头指针下标移动。头指针指向队首,尾指针指向队尾的下一位。 第一步,执行入队使用。入队9个元素,队列满,此时头指针下标为1,尾指针下标为0; 第二步,执行出队使用。头指针向后移动,好比此时出队3个元素,头指针移动到下标指向4,尾指针依然下标为0,此时队列中有6个元素。 第三步,执行入队使用。头指针稳定,指向下标为4,参加两个元素,此时尾指针的下标从0指向2,此时队列中有8个元素。 效果:头指针指向4,尾指针指向2,队列中有8个元素。(2+10-4)%10=8 循环队列靠指针来执行入队出队。若用数组实现的平常队列,index=0的元素出队后,要把背面的元素全部遍历一遍做向前移动的使用;若用平常链表实现的队列,出队时要遍历到链表最后一位的前一位,再断开。
25 下列叙述中正确的是( B)
  1. 有一个以上根结点的数据布局不一定是非线性布局只有一个根结点的数据布局不一定是线性布局循环链表是非线性布局双向链表是非线性布局
复制代码
线性布局应满足:有且只有一个根结点与每个结点最多有一个前件,也最多有一个后件,所以 B 正确。所以有一个以上根结点的数据布局一定是非线性布局,所以 A 错误。循环链表和双向链表都是线性布局的数据布局
线性布局:直接前驱和直接后驱的数目至多为1,有且只有一个根节点 树:非线性布局,多个子节点
26 已知int a[3][4];则下列能体现a[1][2]元素值的是A
  1. *(*(a+1)+2)*(a+1+2)(&a[0]+1)[2]*(a[0]+1)
复制代码
数组名是第一个数组的地点.
注意这里a不是第一个元素的地点,而是第一个维数组的地点,a[0][0]才是体现的一维数组第一个元素的地点.
地点 + 1体现向下移一层.
  1. 这是一个三行四列的数组*(a+1)体现第二行的首地点,和a[1]一样。*(a+1)+2第二行第三个数字的地点*(*(a+1)+2)就是第二行第三个数字的值
复制代码
  1. A,   a 是一个二级指针,不是一级指针,*(a+1)体现的第二个数组的地点B,  *(a+1+2)即是*(a+3),是一个int *, 体现的是 第4个数组a[3]的地点,而 **(a+3)体现a[3][0]的值,     *((int *)(a+3)) 也可以体现 a[3][0]的值C. (&a[0]+1)体现的是第2个数组 a[1]的地点, (&a[0]+1)[2]实在是数组a[3]的地点,改成    ((int *)(&a[0]+1))[2] 才是对的D. *(a[0]+1) 是 a[0][1]的值
复制代码
27 一个5*4的矩阵,有多少个长方形?(正方形也算是长方形) 150
  1. 长任取两个点C(6,2)*宽任取两个点C(5,2) = 15* 10 = 150
复制代码

28 下面有关数据布局的说法是正确的?B
  1. 数组和链表都可以随机访问数组的插入和删除可以 O(1)哈希表没有办法做范围查抄以上说法都不正确
复制代码
数组可以直接通过下标得到存储的值 因此支持随机,访问链表是链式存储布局时无法支持随机访问,要访问一个指定位置的元素必须重新开始做指针移动。哈希表支持直接通过关键码得到值 实在数组就是一种哈希表 下标就是关键码 通过下标直接得到值 因此哈希表肯定需要做范围查抄也有办法做范围查抄的
在数组的开头或末端插入和删除 是O(1),但正常情况下为O(n)
所以说数组的插入和删除复杂度大概是O(1)
数组静态分配内存,链表动态分配内存;
数组在内存中一连,链表不一连;
数组元素在栈区,链表元素在堆区;
数组使用下标定位,时间复杂度为O(1),链表定位元素时间复杂度O(n);
数组插入或删除元素的时间复杂度O(n),链表的时间复杂度O(1)。

29 链表与数组的优缺点以下说明正确的是 D
  1. 数组动态分配内存,并在内存中一连,链表静态分配内存,但不一连查询时,数组的时间复杂度为O(n),链表为O(1)插入或删除时,数组的时间复杂度为O(1),链表为O(n)数组元素在栈区,链表元素在堆区
复制代码
解答:数组静态分配内存,链表动态分配内存; 数组在内存中一连,链表不一连; 数组元素在栈区,链表元素在堆区; 数组使用下标定位,时间复杂度为O(1),链表定位元素时间复杂度O(n); 数组插入或删除元素的时间复杂度O(n),链表的时间复杂度O(1)
数组插入大概删除时,一般情况下时间复杂度为O(n),但是在数组尾部举行插入大概删除时间复杂度为O(1).
30 以下错误的是(B)
  1. (1)静态链表既有顺序存储的优点,又有动态链表的优点。所以,它存取表中第i个元素的时间与i无关。(2)静态链表中能容纳的元素个数的最大数在表界说时就确定了,以后不能增加.(3)静态链表与动态链表在元素的插入、删除上类似,不需做元素的移动。
复制代码
  1. (1),(2)(1)(1),(2),(3)(2)
复制代码
(1)错,(2)(3)对。
静态链表是用数组存储节点数据,模拟链表的实现,但是没有用到指针。每个数组节点包罗两部分:data域和cursor(游标)域。data存储数据,cursor指明下个元素在数组中的下标。
(1)存取第i个元素时,需要重新遍历到i-1和元素,由第i-1个节点的cursor,才华知道第i个元素存储的位置,因此和i是相关的。
(2)使用数组对元素举行存储,在界说时巨细已经确定。
(3)插入和删除使用无需移动元素,只需要修改cursor游标的值即可,就像修改动态链表中的指针一样。
31 对n个记载的线性表举行快速排序为淘汰算法的递归(栈)深度,以下叙述正确的是(A)
  1. 每次分区后,先处理处罚较短的部分每次分区后,先处理处罚较长的部分与算法每次分区后的处理处罚顺序无关以上三者都不对
复制代码
表明:
  1. 现在有这么个序列:123456789假设每次分别出短序列的长度为1即第一次分别短序列:1长序列:23456789如果优先处理处罚短序列1则栈中仅用生存23456789,深度为1然后23456789出栈,分别短序列:2长序列:3456789同样的先处理处罚短序列栈中生存3456789,深度为1类推下去,处理处罚完整个序列,栈的最大深度都为1如果每次分别出的短序列长度为2呢短序列:12长序列:3456789优先处理处罚短序列12栈中生存3456789 深度为112只能分别为同样长度的序列1和2先处理处罚左边的栈生存2 此时栈中有3456789 和 2 深度为2然后2 出栈 处理处罚接着3456789出栈分别为短序列34长序列 56789处理处罚短序列34栈中生存56789类推下去,处理处罚完整个序列,栈的最大深度都为2也就是说栈的最大深度取决于分别出来的短序列的长度 (前提是先处理处罚短序列)那么先处理处罚长序列呢短序列:1长序列:23456789如果优先处理处罚长序列序列23456789 短序列入栈,长序列分别为2和34567892入栈,3456789分别。。。8入栈,9处理处罚此时栈中有12345678 深度为8短序列:12长序列:345678912入栈 3456789分别为34和5678934入栈 56789分别为56和78956入栈 789分别为78和99入栈  78分别为7和87入栈 8处理处罚此时栈中有12 34 56 9 7 深度为5很显着先处理处罚长序列 栈的深度要大于 先处理处罚短序列栈的深度。
复制代码
32 选项代码中能正确使用数组元素的是(AB)
[code]int main(){  int a[N][N]={{0,0},{0,0}};  for(int i=0;i
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则


专注素材教程免费分享
全国免费热线电话

18768367769

周一至周日9:00-23:00

反馈建议

27428564@qq.com 在线QQ咨询

扫描二维码关注我们

Powered by Discuz! X3.4© 2001-2013 Comsenz Inc.( 蜀ICP备2021001884号-1 )