数据结构与算法的基本概念

1、单选题：
‌数据在计算机存储内表示时，数据的物理地址和逻辑相对位置是不是连续的，称之为（）。​‌​‌​
选项：
A: 存储结构
B: 逻辑结构
C: 顺序存储结构
D: 链式存储结构
答案: 【 链式存储结构】

2、单选题：
‍与数据元素本身的形式、内容、相对位置、个数无关的是数据的（    ）。‍‍‍
选项：
A: 存储结构
B: 线性结构
C: 逻辑结构
D: 运算实现
答案: 【 逻辑结构】

3、单选题：
‎与算法的事前分析法无关的因素是（   ）‏‎‏
选项：
A: 依据算法选用何种策略
B: 问题的规模
C: 数据的存储结构
D: 程序设计的语言
答案: 【 数据的存储结构】

4、单选题：
‌一个算法必须具有的特性有（  ）‍
选项：
A: 确定性
B: 输出
C: 确定性
D: 输入
答案: 【 输入】

5、单选题：
‌要设计一个好的算法，下面哪个不是算法要考虑的基本要求（   ）​‌​
选项：
A: 正确性
B: 可读性
C: 健壮性
D: 无穷性
答案: 【 无穷性】

6、单选题：
‏下面代码的时间复杂度为​‏for(i=1; i<=1000; ++i)​‏      {sum+= x; s+=x ; } ​‏​
选项：
A: O（1）
B: O（n）
C: O（1000）
D: O（log2n）
答案: 【 O（1）】

7、单选题：
‍下面是关于两个矩阵加法的算法实现，其时间复杂度是(    )。‏for(i=0;i<n;i++)‏for(j=0;i<n;j++)‏c[i][j]= a[i][j]+ b[i][j];‏A．O(1)B．O(n)C．O(log2n)              D．O(n2)‏‍‏
选项：
A: O(1)
B: O(n)
C: O(log2n) 
D: O(n*n) 
答案: 【 O(n*n) 】

8、单选题：
下面是关于两个矩阵加法的算法实现，其时间复杂度是(    )。​for(i=0;i<n;i++)​for(j=0;i<10;j++)​c[i][j]= a[i][j]+ b[i][j];​‎​
选项：
A: O(n)
B: O(1)
C: O(n*n)
D: O(10*n)
答案: 【 O(n)】

9、单选题：
‍算法分析的两个主要方面是(    )。‌‍‌
选项：
A: 空间复杂性和时间复杂性
B: 正确性和简明性 
C: 可读性和文档性
D: 数据复杂性和程序复杂性
答案: 【 空间复杂性和时间复杂性】

10、单选题：
‏ 下列时间复杂度中最坏的是(    )。‏‏‏
选项：
A: O(2^n)
B: O(1)
C: O(nlog2n)
D: O(n*n)
答案: 【 O(2^n)】

11、判断题：
‏程序和算法原则上没有区别，在讨论数据结构时可以通用。  ‌
选项：
A: 正确
B: 错误
答案: 【 错误】

12、判断题：
‌数据的物理结构就是把数据简单地存储在计算机中就可以了。‏
选项：
A: 正确
B: 错误
答案: 【 错误】

13、判断题：
‏链表的存储密度肯定小于1。‎
选项：
A: 正确
B: 错误
答案: 【 正确】

14、判断题：
​一个算法的实现，可以有多个程序来实现。‌
选项：
A: 正确
B: 错误
答案: 【 正确】

15、判断题：
‍算法可以直接在程序中调用。‏
选项：
A: 正确
B: 错误
答案: 【 错误】

16、填空题：
‌(   )是数据结构中讨论的基本单位​
答案: 【 数据元素】

17、填空题：
‎(   )是相互之间存在着某种逻辑关系的数据元素的集合，主要包含两方面的涵义，一是指数据的集合，二是限定这些数据是有结构的‌
答案: 【 数据结构】

18、填空题：
‍(    )是数据的逻辑结构在计算机存储器内的表示‌
答案: 【 ​物理结构##%_YZPRLFH_%##存储结构】

19、填空题：
‎顺序存储结构就是在计算机中开辟一组连续的存储空间来依次存储数据元素，数据元素的（   ）与其物理存放位置的次序是相同的。‌
答案: 【 逻辑次序##%_YZPRLFH_%##逻辑##%_YZPRLFH_%##逻辑关系】

20、填空题：
‎（  ）是对特定问题求解步骤的一种描述，是指令的有限序列，其中每一条指令表示一个或多个操作。‎
答案: 【 算法##%_YZPRLFH_%##Algorithm】

21、填空题：
算法的（   ），是指算法必须在有穷步之后结束，即必须在有限时间内完成。‏‎
答案: 【 有穷性】

22、填空题：
‌算法的（  ），是指当输入的数据非法时，算法应当恰当地作出反映或进行相应处理，而不是产生不正确的输出结果；应能作适当处理，不至引起严重后果。‎
答案: 【 健壮##%_YZPRLFH_%##健壮性##%_YZPRLFH_%##鲁棒性】

23、填空题：
​一般用（   ）的描述方法来进行算法描述，是介于高级程序设计语言和自然语言之间的一种语言。‏
答案: 【 伪码语言##%_YZPRLFH_%##伪码】

24、填空题：
‍一个程序的（  ）（Time Complexity）是指程序运行从开始到结束所需要的时间。‏‏‍‏
答案: 【 一个程序的时间复杂度（Time Complexity）是指程序运行从开始到结束所需要的时间。

​】

25、填空题：
‏算法中基本操作重复执行的次数是问题规模n的某个函数，是对算法时间效率的一种近似评价，称作算法的（  ）估计，‍
答案: 【 渐近时间复杂度】

线性表的链式存储结构及实现

1、单选题：
​不带头结点的单链表head为空的判断条件是(    )。‌
选项：
A: head!=NULL
B: head==NULL
C: head >next==NULL 
D: head->data==NULL 
答案: 【 head==NULL】

2、单选题：
​带头结点的单链表head为空的判断条件是(     )。‍
选项：
A: head==NULL
B: head->data==NULL
C: head >next==NULL
D: head!=NULL
答案: 【 head >next==NULL】

3、单选题：
‍在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在p和q之间插入s结点，则执行(    )。‏‏
选项：
A: A.s->next=p;  q->next=s;     
B: p->next=s->next; s->next=p;
C: q->next=s->next; s->next=p;  
D: p->next=s ; p->next=s;
答案: 【 A.s->next=p;  q->next=s;     】

4、单选题：
‍两个指针p和q，分别指向单向链表的两个元素，p是q的前驱条件是(    )。‌
选项：
A: p->next= =q->next 
B: p->next= =q    
C: q->next= =p
D: p==q
答案: 【 p->next= =q    】

5、单选题：
‏一个单链表中，若刪除p所指结点的后续结点，则执行(    )。‎
选项：
A: p=p->next;  p->next=p->next->next;
B: p->next=p->next->next
C: p->next=p
D: p=p->next->next;
答案: 【 p->next=p->next->next】

6、单选题：
‏在n个结点的顺序表中，算法的时间复杂度是O (n)的是(    )。‌
选项：
A: 访问第i个结点
B: 在第n+1个结点后插入一个新结点
C: 删除第i个结点
D: 将n个结点从小到大排序
答案: 【 删除第i个结点】

7、单选题：
‎在长度为n的单链表中，查找给定结点p的前驱结点的时间复杂度为（  ）。‎
选项：
A: O(n)
B: O(1)
C: 不确定
D: O(n-1)
答案: 【 O(1)】

8、单选题：
‍在长度为n的单链表中，查找第i个结点的时间复杂度为（  ）。‌
选项：
A: O(1)
B: O(n)
C: O(n*n)
D: 不确定
答案: 【 O(n)】

9、单选题：
‏不带头结点的单链表head中，判断结点p是尾结点的条件(    )。‌
选项：
A: p==NULL 
B: p->next==NULL 
C: p->next==head  
D: head==p
答案: 【 p->next==head  】

10、单选题：
‎在单链表中，存储每个结点有两个域，一个是数据域，另一个是指针域，指针域指向该结点的(      )。‎‎
选项：
A: 直接前趋 
B: 直接后继
C: 开始结点
D: 终端结点
答案: 【 直接后继】

链表基础知识

1、填空题：
‌若head表示循环链表的头指针，t表示尾结点，则头指针head与尾结点t之间的关系可表示为__________。‍
答案: 【 t->next=head】

2、填空题：
​在已知头指针的单链表中，要在其尾部插入一新结点，其算法所需的时间复杂度为                。‏
答案: 【 O(n）】

3、填空题：
​在单链表中，插入一个新结点需修改_______个指针。‌
答案: 【 2】

4、填空题：
当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取​线性表中的元素时，应采用         存储结构。​​​
答案: 【 顺序】

5、填空题：
‍设单链表中指针p指向结点A，若要删除A之后的结点（假设存在），则需要修改指针的操作为____________________。‍
答案: 【 p->next=p->next->next】

6、填空题：
‏求链表长度的时间复杂度为             。​
答案: 【 O（n）】

7、填空题：
‏求顺序表长度的时间复杂度为             。‎
答案: 【 O（1）】

8、填空题：
‏在有n个数据元素的链表中，要在第i个位置上插入一个元素，则需要移动  &