数据结构模拟测试（选择）
一下关于数据元素之间关系的说法中错误的是（1）
- 集合是一种数据结构
- 树形结构具有分之和层次的特点，其形态有些像自然界中的数，即一对多
- 图形结果中的每个元素都可能与其他结点有邻接（有关系），即多对多
- 线性结构中数据元素形成一对一的关系
/******************************************************************/
1 | count=1; |
/******************************************************************/
设线性表有n个元素且采用顺序存储结构，算法的时间复杂度为O(1)的操作是（2）
- 删除第i个元素
- 访问第i个元素，求第i个元素的直接前驱和直接后继
- 在第i个位置插入一个新元素
- 查找元素x
/******************************************************************/
一颗有n个结点的二叉树的最大高度为（n）
/******************************************************************/
假设具有n个结点的完全二叉树采用顺序存储结构。储存空间用一维数组R表示，根结点存于R0，若Ri存储结点有左孩子，则左孩子的存储位置是（2*i+1）
/******************************************************************/
一课树采用孩子-兄弟链表存储结构,若要找到结点K的第5个孩子（假设点K的孩子个数大于等于5个）,则需要先根据结点k的左孩子指针找到它的第1个孩子,再沿着第1个孩子结点的（2）即可。
- 左孩子指针链连续扫描5个结点
- 右兄弟指针链连续扫描4个结点
- 左孩子指针链连续扫描4个结点
- 右兄弟指针链连续扫描5个结点
/******************************************************************/
具有n个顶点的完全无向图的边数为（n(n-1/2)）
/******************************************************************/
关于最小生成树的说法正确的是（2）
- 用prim算法从不同的顶点开始得到的最小生成树一定相同
- 最小生成树的代价（边的权值之和）唯一
- prim算法和kruskal算法得到的生成树总是不同
- 权值最小的边一定会出现在所有的生成树中
/******************************************************************/
设待排序元素序列为{38,7,72,12,43,65,62,88,31,27,15,54}，若以当前待排序序列的第一个元素作为基准（轴元素）进行快速排序，那么经过2趟快速排序后的结果序列为（{12,7,15,27,31,38,54,43,62,65,72,88}）
/******************************************************************/
栈结构采用顺序存储存放在数组A中,如果进线元素依次为13,20,15,43,38,65,47,51,10,21，前7个元素进栈之后，出核4个元素，再依次入核3个元素，则元素43的状态是（在栈外）
/******************************************************************/
将一个m*n的二维数组A按列优先顺序存储，A[1][1]的存储地址是a，每一个数组元素A[i][j]占用k个存储单元，则元素A[i][j]的地址为（a+((j-1)*m+i-1)*k）
/******************************************************************/
线性表结构的查找方法有顺序查找法，二分查找法等，顺序查找适用于查找顺序存储或者连接存储的线性表，二分查找法只适用于查找（已排序）的顺序表
/******************************************************************/
设有向无环图G中的有向边集合E={<1,2>,<2,3>,<3,4>,<1,4>}，则下列属于该有向图G的一种拓扑排序序列是（1,2,3,4）
/******************************************************************/
设计一个判别表达式中左右括号是否配对的算法，采用（栈）数据结构最佳（详见本博客：括号匹配（栈））
/******************************************************************/
如果图采用邻接表存储结构，在邻接表中有奇数个边结点，则该图（是有向图）
/******************************************************************/
假设线性表a的长度n ,线性表b的长度为n,均采用带头结点的单链式存储结构，头结点指针分别是la、lb,则线性表b连接到线性表a后面操作的算法的时间复杂度为（O(m)）
/******************************************************************/
一棵度为m的树有n个结点，则（3）
- 树的最大高度是n-m
- 第i层最多有m（i-1）个结点
- 树的高度最大是n-m+1
- 至少在某一层上正好有m个结点
/******************************************************************/
已知一棵树有2011个结点，其叶节点个数为116。该树转换为二叉树后，在二叉树中，无右孩子的结点个数是（2011-116+1=1896）
/******************************************************************/
下面不可能是Huffman编码的是（4）
- 111,110,10,01,00
- 001,000,01,110,10
- 000,001,010,011,1
- 100,11,10,1,0
/******************************************************************/
一个连通图，他的生成树指的是包含图中所有顶点的一个（极小连通）子图
/******************************************************************/
单链表长度为n，若查找每个元素的概率相等，则顺序查找表中任意元素的查找成功的平均查找长度为（(n+1)/2）
/******************************************************************/
下列程序段的时间复杂度为（O(sqrt(n))）
1 | x = n, y = n; |