这是一个程序员的自我修养，一个学术者的自我探索，一个大神的养成之道。
下列关于栈的描述中错误的是
- A 栈是先进后出的线性表
- B 栈只能顺序存储
- C 栈具有记忆作用
- D 对栈的插入弓删除操作中，不需要改变栈底指针
分析：栈既有顺序存储结构也有链式存储结构
答：B
对于长度为n的线性表，在最坏情况下，下列各排序法所对应的比较次数中正确的是
- A 冒泡排序为n/2
- B 冒泡排序为n
- C 快速排序为n
- D 快速排序为n(n-1)/2
分析：冒泡排序的平均时间复杂度位O（n^2）。
每次都会选取线性表的轴值，随后以此轴值划分为两个子线性表再分别进行快排，在最坏情况下，也就是说每次选出的线性表轴值完全不能将这个线性表划分为两个子线性表。那么此时快速排序退化为冒泡排序了。
那么第一趟排序时，轴值（线性表的中间位置）被选出，这个值绝对是这个线性表中最大的（不然也不能是最坏情况），其他值都比他小，那么线性表现在分为完全不对等的两段（一段是0,另一段是n - 1），一段是这个值，一段是其他值。同样第二趟排序在刚才剩下的值中选中间值（剩余值中最大的那个），又分为不对等两段，依次递推。也就是说每次都比较了N - 1个元素（轴值选出后都与它比较大小），那么肯定是比较了n - 1次（如第一次先挑了个轴值，然后剩下n - 1比较）,n代表当前子线性表中元素个数由此最白痴的数列问题出现了，如下1 + 2 + 3 + .......... + n - 2 + n - 1 = n(n - 1) / 2。
答：D
下列对于线性链表的描述中正确的是
- A 存储空间间不一定是连续，且各元素的存储顺序是任意的
- B 存储空间不一定是连续，且前件元素一定存储在后件元素的前面
- C 存储定间必须连续，且前件元素一定存储在后件元素的前
- D 存储空间必须连续，且各元素的存储顺序是任意的
分析：链式存储不是连续的，且顺序任意
答：A
专注，坚持
网友评论