1.7数算选择题专练

排序

就是说此时是有5个有序的两两对，然后进行下一轮归并?

时间复杂度和初始次序无关的应该是，堆排序，归并排序，选择排序

比较次数与初始序列无关是：选择排序 和 折半插入排序

?

堆排序不需要开新空间，是直接在原数组上做的操作，快速建堆

归并需要辅助空间，是用于数组合并，快速排序需要辅助空间，是树的大小，递归的过程，递归向下需要栈空间?

?

?

逆序的话，每次都是从最底部冒到最上部，每次都是从头交换到尾，所以交换次数最多?

选择排序的时间复杂度不随序列的变化而变化，任何一个序列都是ON^2

选择排序，快速排序，堆排序，希尔排序都是不稳定的?

稳定排序有 冒泡排序，插入排序，归并排序，计数排序，基数排序，桶排序

快递排序的递归次数与元素的初始排列有关。如果每一次划分后分区比较平衡，则递归次数少；如果划分后分区不平衡，则递归次数多。但快速排序的递归次数与分区处理顺序无关，即先处理较长的分区或先处理较短的分区都不影响递归次数。

此外，可以形象地把快速排序的递归调用过程用一个二叉树描述，先处理较长或较短分区，可以想象为交换某一递归结点处的左右子树，这并不会影响树中的分支数。

?

两趟排序导致QU是有序的,其他四个字母还无序,选择排序则QU应该在后面,冒泡和堆排序两趟也会使元素到达他最终位置,所以排除

A 希尔排序：因为33和6交换，那么按照分隔的距离12需要和8进行交换，和结果不符合，所以排除
B 归并排序：归并第一趟后得出【12，33，10，44】【6，8，17】，和结果不符合，所以排除
C 快速排序：按照快排性质，选出的元素需要满足左边比它小，右边比它大的性质，第一趟只有6满足，第二趟只有8满足，第三趟只有10满足，可以看出这种选元素的方式并不符合快排，也就是说，没有一种选取元素算法能够如此精确的选出6，8，10这三个数来，所以排除
D 选择排序：每一趟选出最小的数，满足选择排序性质
?

快速排序的过程是先选一个数，使左边的都是比它小的，右边都是比他大的

然后继续向左右递归，接着找

?

链表

静态链表采用数组实现链表的存储，用空间换取时间，删除与插入需要改的是游标 ?

图

在n个结点的无向图中，若该图是连通图,则其边数大于等于n-1，
在n个结点的无向图中，若边数大于(n-2)(n-1)/2，则该图必是连通图

8个边会产生8个入度与8个出度

找拓扑排序的数量，一个递归收缩的过程，每个结点可以到达的方式，包含前一个可以到达的结点的方式总数，但不局限于此，而是所有可以到达这个点的方式总和，然后递归收缩完后，以这个点为起点继续向后

到A的方式有1，到E的方式有1,到B的方式有1，到C的方式有2（A到它B到它共两条），D到的方式有3，从E到它，从C到它?

DFS的时候，如果要访问的元素已经访问过，它在当前的栈内还没出栈，那么就是有环。BFS不行是因为可能有多个节点指向该节点，不一定是因为有环。

拓扑排序会循环执行以下两步： (1) 选择一个入度为0的顶点，输出 (2) 从图中删除此顶点以及所有的出边 循环结束后，若输出的顶点数小于网中的顶点数，则说明有回路

队列

即p代表要操作的元素，然后Q是要接收的位置?

这里注意，这个头指针是虚指，尾指针是实指，头指针指向的是元素的前一个位置?

循环队列是队列的一种顺序存储结构，用队尾指针?rear?指向队列中的队尾元素，用排头指针?front?指向排头元素的前一个位置。入队运算时，队尾指针进?1?（即?rear+1?），然后在?rear?指针指向的位置插入新元素。退队运算时，排头指针进?1?（即?front+1?），然后删除?front?指针指向的位置上的元素。当?front=rear=15?时可知队列空或者队列满，此后又退出一个元素，如果之前队列为空，退出操作会产生错误，队列里有?0?个元素；如果退出之前队列已满?(40?个元素?)?，执行退出后，队列里还有?39?个元素。故本题答案为?A?选项。?

注意此时队列大小为M+1而不是M?

?

往循环队列里插入元素时，头指针移动；删除元素时，尾指针移动

?

?

奇怪的

?

当我们存入队列的数字在内存中已经有的时候就不缺页，没有就缺页；且是先进先出的原则。?