算法与数据结构专项练习1
1. 32系统，函数
void Func(char str[100]){}
中sizeof(str)=
正确答案: A
4
5
6
7
**解析：**数组作为参数时，[]里的数不起作用，传递的是首元素的地址，32位OS下是4个字节，数组具体有多少个元素，要自己指出，比如void Func(char str[], int n);
2.对于长度为n的线性表，建立其对应的单链表的时间复杂度为（）。
正确答案: C
O(1)
O(log2n)
O(n)
O(n^2)
解析：我们使用头插式或尾插式创建链表都只需要一次循环遍历就可实现，所以时间复杂度为O(n)。
线性表是最基本、最简单、也是最常用的一种数据结构。线性表中数据元素之间的关系是一对一的关系，即除了第一个和最后一个数据元素之外，其它数据元素都是首尾相接的（注意，这句话只适用大部分线性表，而不是全部。比如，循环链表逻辑层次上也是一种线性表（存储层次上属于链式存储），但是把最后一个数据元素的尾指针指向了首位结点）。
链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。 相比于线性表顺序结构，链表比较方便插入和删除操
3.定一个二维数组的定义语句为“int a[3][4]={{3,4},{2,8,6}};”，则元素a[1][2]的值为（ ）。
正确答案: C
2
4
6
8
解析：
定义中每个{ }，表示一行的数据，每行数据不够的补0，每一行的编号从0开始
4.假设要存储一个数据集，数据维持有序，对其的操作只有插入、删除和顺序遍历，综合存储效率和运行速度，下列哪种数据结构是最适合的是？
正确答案: B
数组
链表
哈希表
队列
解释：
数组可以实现顺序遍历但是插入删除操作复杂，平均移动n/2个元素
链表因为存储的地址不连续（逻辑上连续实际上不连续），可以实现顺序遍历
哈希表是随机存储，所以是离散分布，顺序遍历实现不了
队列只可以在队尾插入队头删除，不可以实现中间插入和删除，不满足条件
综上，链表最合适
5.若用数组S[0. .n-1]做为两个栈S1和S2的共同存储结构，对任何一个栈，只有当S全满时才不能作入栈操作。为这两个栈分配空间的最佳方案是（ ）。
正确答案: A
S1的栈底位置为0，S2的栈底位置为n-1
S1的栈底位置为0，S2的栈底位置为n/2
S1的栈底位置为1，S2的栈底位置为n/2
解释：两个栈的栈底一个在数组第一个元素，朝着数组正方向增长
另一个在数组最后一个元素，朝着数组索引减小的方向增长。
当两个栈的栈顶相等是，表明数组满了，不能继续入栈
6.在面向对象的程序设计中，关于数组，下列说法正确的有
正确答案: B
数组属于一种原生类
数组是一种对象
int number=[]={31,23,33,43,35,63}
数组的大小可以任意改变
解释：
A.原生类指未被实例化的类,数组一般指实例化,被分配空间的类,不属于原生类.
B.对象的特点是封装了一些数据，同时提供了一些属性和方法，从这个角度来讲，数组是对象
C.格式有误
D.数组的大小确定之后不可改变
7.设 int x[]={1,2,3,4,5,6},p=x; 则值为 3 的表达式是
正确答案: B
p+=2,++p;
p+=2,p++
p+=3,p
p+=2,++p
解释
答案为b p=x这里指针p指向数组的首元素地址，p+=2则指针指向第三个元素，而++p是前置加加，p先自增，再解引用，就指向第四个元素了 b中为后置加加，是先解引用再加所以不影响，正确， c中p+=3就错了，因为指向第四个元素了 d中++p，因为p为3，所以就是++3了，结果为4
**8.一个54的矩阵，有多少个长方形？（正方形也算是长方形）
正确答案: B
120
150
100
80
解释
9.若6行5列的数组以列序为主序顺序存储,基地址为1000,每个元素占2个存储单元,则第3行第4列的元素(假定无第0行第0列)的地址是()
正确答案: A
1042
1026
备选答案A,B,C都不对
解释思路：按列存储，第一列的基址是：1000，第二列的基址是：1012，第３列是：1024，第４列是：1036，所以第三行第４列为：1036+2+2=1040 注：以“列序”为主，默以为以“行序”为主了
10.在一个元素个数为N的数组里，找到升序排在N/5位置的元素的最优算法时间复杂度是
正确答案: A
O(n)
O(n log n)
O(n (log n)2)
O(n 3/2)
解释
BFPRT算法解决的问题十分经典，即从某n个元素的序列中选出第k大（第k小）的元素，通过巧妙的分 析，BFPRT可以保证在最坏情况下仍为线性时间复杂度。该算法的思想与快速排序思想相似，当然，为使得算法在最坏情况下，依然能达到o(n)的时间复杂 度，五位算法作者做了精妙的处理。
算法步骤：
- 将n个元素每5个一组，分成n/5(上界)组。
- 取出每一组的中位数，任意排序方法，比如插入排序。
- 递归的调用selection算法查找上一步中所有中位数的中位数，设为x，偶数个中位数的情况下设定为选取中间小的一个。
- 用x来分割数组，设小于等于x的个数为k，大于x的个数即为n-k。
- 若i==k，返回x；若i<k，在小于x的元素中递归查找第i小的元素；若i>k，在大于x的元素中递归查找第i-k小的元素。
终止条件：n=1时，返回的即是i小元素。