1）阅读下列函数说明和C代码将應填进（n）处的字句写在答题纸的对应栏内。
【说明】设有一个带表头结点的双向循环链表L,每个结点有4个数据成员：指向先驱结点的指针prior、指向后继结点的指针next、存放数据的成员data和访问频度freq所有结点的freq初始时都为0.每当在链表上进行一次L.Locate（x）操纵时，令元素值x的结点的访问頻度freq加1并将该结点前移，链接到现它的访问频度相等的结点后面使得链表中所有结点保持按访问频度递减的顺序排列，以使频繁访问嘚结点总是靠近表头

2）有一个用数组 C[1..m]表示的环形队列，m 为数组的长度假设 f 为队头元素在数组中的位置，r 为队尾元素的后一位置(按顺时針方向)若队列非空，则计算队列中元素个数的公式应为

3）假设要存储一个数据集，数据维持有序对其的操作只有插入、删除和顺序遍历，综合存储效率和运行速度下列哪种数据结构是最适合的是？
解答：选择“链表”即选择B）

4）就分类算法所用的辅助空间而言,堆汾类、快速分类和归并分类的关系是？
解答：在分类算法里堆分类的辅助空间为O(1)，快速分类的辅助空间为O(nlogn)归并分类的辅助空间为O(n)，由於O(n)>O(nlogn)>O(1)所以按所需的辅助空间从大到小排序时得到：
　　堆分类<快速分类<归并分类
5) 在堆排序算法中我们用一个数组A来模拟二叉树T，如果该A[0]存放的是T的根节点那么A的父亲节点是?
　　a）如果二叉树从1,2,3,…,n进行编号，则节点i 的父节点编号为[i/2]（向下取整）；
　　b）如果二叉树从0,1,2,…,m进行編号则节点i的父节点编号为[(i-1)/2] (向下取整)；
　　注意节点的起点编号，前者为1后者为0，所以公式要进行相应的调整由于题目编号的起点為A[0]即以0开始，所以父节点编号为(k-1)/2即选A)

6）关键码序列(Q,H,C,Y,Q,A,M,S,R,D,F,X)，要按照关键码值递增的次序进行排序若采用初始步长为4的Shell的排序法，则一趟扫描嘚结果是 ；若采用以第一个元素为分界元素的快速排序法，则扫描一趟的结果是 。
　　题目所给为4因此，上来1,5,9号元素（即QQR）进行比較在这三个位置上进行排序，即还是QQR
然后2,6,10号元素（即HAD）进行比较在这三个位置上进行排序，即变成了ADH
　　依次排序后面的，即可获嘚QACSQDFXRHMY
　　6.2）快排，主要看排序时从后往前和从前往后的比较过程中，加不加等号
　　以第一个元素为pivot，从后往前遇到第一个比pivot小的，则换到前面然后从前面开始往后遍历，遇到第一个比pivot大的则换到后面此题答案对应的是没有等号的情况，即严格大才会换位置