PDF文档公众号回复关键字:20240710
2020 CSP-J 选择题
单项选择题（共15题，每题2分，共计30分：每题有且仅有一个正确选项）
7.链表不具有的特点是（）
A.可随机访问任一元素
B.不必事先估计存储空间
C.插入删除不需要移动元素
D.所需空间与线性表长度成正比
8.有 10 个顶点的无向图至少应该有（ ）条边才能确保是一个连通图
A.9
B.10
C.11
D.12
9.二进制数 1011 转换成十进制数是（ ）
A.11
B.10
C.13
D.12
11.下图中所使用的数据结构是（ )
A.栈
B.队列
C.二叉树
D.哈希表
12.独根树的高度为 1。具有 61 个结点的完全二叉树的高度为（ ）
A.7
B.8
C.5
D.6
2 相关知识点
1) 链表
是一种常见的数据结构，它是由一系列节点（Node）组成，每个节点包含两部分：数据域和指针域。数据域用于存储数据，指针域用于存储下一个节点的地址。链表的第一个节点称为头节点（Head），最后一个节点称为尾节点（Tail），尾节点的指针域指向空（NULL）
链表占用空间大小，和链表的长度有关，没增加一个节点，增加一个数据节点和一个指针节点，存储空间和链表长度成正比
随机存取
随机存取（直接存取,Random Access）指的是当存储器中的数据被读取或写入时，所需要的时间与该数据所在的物理地址无关
顺序存取
顺序存取 (Sequential Access)是一种按记录的逻辑顺序进行读、写操作的存取方法，所需要的时间与该数据所在的物理地址有关。
顺序存取表现为:在存取第N个数据时，必须先访问前（N-1）个数据
#include<bits/stdc++.h>
using namespace std;
/*
随机存取、顺序存取
*/
int a[10]={0,1,2,3,4,5,6,7,8,9};
int main(){
cout<<a[9]<<endl;//随机读取下标为9的元素 输出 9
for(int i=0;i<10;i++){//顺序存储 逐一读取
cout<<a[i]<<" ";
}
return 0;
}
数组可以随机以及顺序存取，而链表只能顺序存取
内存分配
数组静态分配内存，定义时指定内存大小，链表动态分配内存，使用是指定内存大小
数组是一种线性表数据结构，有一组连续的内存空间，链表是通过指针将一组零散的内存块串联起来使用的数据结构，不需要一块连续的内存空间
链表的删除
链表通过指针建立起数据之间的联系，删除节点时，只需要改变对应的指针指向即可，不需要移动数组的元素
2) 连通图
连通性
如果任意两点间存在路径，此图具有连通性
无向图的连通性
任意两点是连通的，任意两点都可以形成通路
最小边数
n个节点的无向连通图最小边数为n-1条边
树为一种连通图，n个节点的树，边数为n-1
3) 2进制转10进制
按权展开，但要注意各个位的权，最低位（最右边）的权是0次方，权值为1
向左为2^1, 2^2, 2^3, 2^4, 2^5…
(11010110)2=1×2^7+1×2^6+0×2^5+1×2^4+0×2^3+1×2^2+1×2^1+0×2^0=(214)10
向右，小数部分，2^(-1), 2^(-2), 2^(-3), 2^(-4), 2^(-5)…
(1011.01)2=(1*2^3+1*2^1+1*2^0+1*2^(-2))=8+2+1+0.25=11.25
4) 数据结构
栈
栈又名堆栈，是一种限定仅在表尾进行插入和删除操作的线性表，这一端称为栈顶，另一端称为栈底
栈中的数据元素遵守后进先出的原则
队列
队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（head）进行删除操作，而在表的后端（tail）进行插入操作
队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头
队列可以理解成我们平时的排队，先进入的先出去
二叉树
每个结点至多拥有两棵子树(即二叉树中不存在度大于2的结点)，并且，二叉树的子树有左右之分，其次序不能任意颠倒
例如下面是一棵二叉树
完全二叉树
除了最下层，其他每层都饱满，去除最后一层是一棵满二叉树，最下层的结点都集中在该层最左边的若干位置上
哈希表
哈希表（Hash Table）是一种通过键（key）直接访问存储在内存中的特定位置的值（value）的数据结构。它支持快速的查找、添加和删除操作，其平均时间复杂度为O(1)
哈希表的工作原理基于哈希函数，该函数将键映射到数组的索引位置，可以随机读取
3 思路分析
7.链表不具有的特点是（ A ）
A.可随机访问任一元素
B.不必事先估计存储空间
C.插入删除不需要移动元素
D.所需空间与线性表长度成正比
分析
链表只能顺序访问，不能随机访问
8.有 10 个顶点的无向图至少应该有（ A ）条边才能确保是一个连通图
A.9
B.10
C.11
D.12
分析
无向连通图，需要每2个节点都可以连通，n个节点，需要n-1条边，所以选A
如下图4个结点，3条边是连通图，任意2个结点都是连通的
9.二进制数 1011 转换成十进制数是（ A ）
A.11
B.10
C.13
D.12
分析
/*
按权展开，最低位（最右边）的权是0次方，权值为1
向左为2^1, 2^2, 2^3, 2^4, 2^5......
*/
(1011)2=1*2^3+0*2^2+1*2^1+1*2^0=8+0+2+1=11
11.下图中所使用的数据结构是（ A )
A.栈
B.队列
C.二叉树
D.哈希表
分析
栈的操作是后进先出，队列操作是先进先出
如图 A进 B 进 B 出 C 进 符合栈的操作
二叉树需要构造树，没有体现
哈希表需要对键进行哈希函数运算，没有体现
12.独根树的高度为 1。具有 61 个结点的完全二叉树的高度为（ D ）
A.7
B.8
C.5
D.6
分析
独根树的高度为1，一个节点时树的高度为1
完全二叉树的特点为：除最后一层，都是满的
满二叉树结点个数
高度 1 - 结点 1 -2^1-1
高度 2 - 结点 3 -2^2-1
高度 3 - 结点 7 -2^3-1
高度 4 - 结点 15 -2^4-1
高度 5 - 结点 31 -2^5-1
高度 6 - 结点 63 -2^6-1
61个结点，最后一层不满，所以高度为6，第6层不满
所以选D