Question

一道数据结构与算法的题目，怎么做？

使用散列函数hashf(x)=xmod11,把一个整数值转换成散列下标，现要把数据：1，13，12，34，38，33，2，22插入到散列中。使用线性探查再散列法来构造散列表，确定其装填因子，查找成功所需的平均探查次数，以及查找不成功所需的平均探查次数。

Answer 1

(1) 用单链表表示的链式队列的对头在链表的( )位置。
　　(2)如果只想得到1000个元素组成的序列中第5个最小元素之前的部分排序的序列，用( )方法最快。
　　(3)如果待排序序列中两个数据元素具有相同的值，在排序前后它们的相互位置发生颠倒，则称该排序算法是不稳定的。( )就是不稳定的排序方法。

　　(4)线性表是具有n个( )的有限序列( n>0).

　　(5)设无向图的顶点个数为n，则该图最多有( )条边。

　　[供选择的答案]

　　A:(1)链头 (2)链尾 (3)链中

　　B:(1)起泡排序(2)快速排列(3)Shell排序(4)堆排序(5)简单选择排序

　　C:(1)起泡排列(2)归并排列(3)Shell排列(4)直接插入排列(5)简单选择排序

　　D:(1)表元素(2)字符(3)数据元素(4)数据项(5)信息项

　　E: (1) n-1 (2) n(n-1) (3) n(n+1)/2 (4) 0 (5) n.*n

　　二、双端队列(deque)是一个可以在任一端进行插入和删除的线性表。现采用一个一维数组作为双端队列的数据存储结构，使用类Pascal语言描述如下

　　const maxsize=32; {数组中可容纳的元素个数}

　　type deque=record

　　elem: array[0..maxsize-1]of datatype; {环形队列的存放数组}

　　end1,end2:0..maxsize; {环形数组的两端}、
　　end;
　　试编写两个算法add(Qu:duque;x:datatype;tag:0..i)和delete(Qu:duque; var x:datatype; tag:0..1)用以在此两端队列的任一端进行插入和删除。当tag=0时在左端 endl端操作，当tag=1时在右端end2端操作。