数据结构模拟试题（4）
一、填空题:06分，每题02分
1、模板类是一种数据抽象，它把________当作参数，可以实现类的复用。

2、假定对长度n=50的有序表进行折半搜索，则对应的判定树中最底下一层的结点数为______个。

3、第i(i=1,2,...,n-1) 趟从参加排序的序列中取出第i个元素，把它插入到由第0个至第i-1个元素组成的有序表中适当的位置，此种排序方法叫做__________排序。

二、单选题:10分，每题02分
4、
设循环队列的结构是
const int MaxSize=100;
typedef int DataT ype;
struct Queue {
DataT ype data[MaxSize];
int front, rear;
};
若有一个Queue类型的队列Q，试问判断队列满的条件应为( )。

A: Q.front==Q.rear;
B: Q.front-Q.rear==MaxSize;
C: Q.front+Q.rear==MaxSize;
D: Q.front==(Q.rear+1) % MaxSize;
5、已知一棵二叉树的广义表表示为a(b(c),d(e(,g(h)),f))，则该二叉树的高度为( )。

假定树根结点的高度为0。

A: 3
B: 4
C: 5
D: 6
6、对于长度为n的顺序存储的有序表，若采用折半搜索，则对所有元素的搜索长度中最大的为( )的值向上取整。

A: log2(n+1)
B: log2n
C: n/2
D: (n+1)/2
7、设无向图的顶点个数为n，则该图最多有（）条边。

A: n-1
B: n(n-1)/2
C: n(n+1)/2
D: n(n-1)
8、在采用开散列法解决冲突时，每一个散列地址所链接的同义词子表中各个表项的（）值相同
A: 关键码
B: 非关键码
C: 散列函数
D: 某个域
三、判断题:10分，每题01分
9、数据的逻辑结构是指各数据元素之间的逻辑关系，是用户根据应用需要建立的。

10、
如果采用如下方式定义一维字符数组：
const int maxSize = 30;
char a[maxSize];
则这种数组在程序执行过程中不能扩充。

11、若让元素1,2,3依次进栈，则出栈次序1,3,2是不可能出现的情况。

12、二叉树是一棵无序树。

13、能够在链接存储的有序表上进行折半搜索，其时间复杂度与在顺序存储的有序表上相同。

14、在由n个元素组成的有序表上进行折半搜索时，对任意一个元素进行搜索的长度都不会大于log2n+1。

15、对用顶点表示活动的网络（AOV网）进行拓扑排序必然得到唯一的结果。

16、装载因子是散列表的一个重要参数，它反映了散列表的装满程度。

17、闭散列法通常比开散列法时间效率更高。

18、A VL树（平衡二叉搜索树）的所有叶结点不一定在同一层次上，同样，平衡m路搜索树的叶结点也不一定在同一层次上。

四、中型计算题:10分，每题10分
19、设有一个三维数组A[10][20][15]，按页/行/列存放于一个连续的存储空间中，每个数组元素占4个存储字，首元素A[0][0][0]的存储地址是1000，求A[8][4][10]的地址。

五、小型计算题:40分，每题08分
20、已知一个有序表(15,26,34,39,45,56,58,63,74,76,83,94)顺序存储于一维数组a[12]中，根据折半搜索过程填写成功搜索下表中所给元素34, 56, 58, 63, 94时的比较次数。

21、假定一个线性序列为(38,52,25,74,68,16,30,54,90,72)，根据此线性序列中元素的排列次序生成的一棵二叉搜索树，求出对该二叉搜索树搜索38,74,68,30,72等元素时的比较次数。

22、已知图G=(V,E)，其中V={a,b,c,d,e}，E={<a,b>，<b,a>，<c,b>，<c,d>，<d,e>，<e,a>，<e,c>}，请写出各结点的出度和入度。

结点 a b c d e
出度
入度
23、
已知一个AOV网络的顶点集V和边集G分别为：
V={0,1,2,3,4,5,6,7};
E={<0,2>,<1,3>,<1,4>,<2,4>,<2,5>,<3,6>,<3,7>,<4,7>,<5,7>,<6,7>};
若存储它采用邻接表，并且每个顶点邻接表中的边结点都是按照终点序号(即dest域的值)从小到大的次序链接的，则按主教材中介绍的进行拓扑排序的算法，写出得到的拓扑序列（提示：先画出对应的图形，然后再运算）。

拓扑序列：
24、
设散列表为HT[13]，即表大小m=13，采用双散列法解决冲突。

散列函数和再散列函数分别为：
H0 = Hash(key) = key % 13; 注：%是求余数运算（= mod ）；
Hi = ( Hi-1 + REV ( key + 1) % 11 + 1) % 13，i = 1, 2, ..., m-1。

其中，函数REV(x)表示颠倒10进制数x的各位，如REV(37)=73，REV(7)=7等。

待依次插入的关键码序列为{2,8,31,20,19,18,53,27}，请根据上述条件填列下表。

六、综合题:20分，每题10分
25、
阅读下列算法，按标号补充所缺内容。

void purge_linkst( ListNode *& la){
// 从头指针为la 的有序链表中删除所有值相同的多余元素，并释放被删结点空间ListNode *p,*q;
if(la==NULL) return;
q=la; p=la->link;
while(p) {
if (p && ___(1)___) {q=p; p=p->link;}
else {
q->link= ___(2)___;
delete(p);
p=___(3)___;
}
}//while
}// purge_linkst
(1) (2) (3)
26、
指出下面算法的功能。

Stack unknown(Stack S) {
Stack T; int d;
T.IniStack( ); //初始化栈
While(!S.IsEmpty( )){
d=S.GetT op();
S.Pop();
T.Push(d);
}
return T;
}
算法功能：
七、填空题(主观):04分，每题02分
27、在具有n个结点的堆排序中，对任意一个分支结点进行调整运算的时间复杂度为____________。

28、在一棵m阶B树上，每个非根结点的关键码数最少为__________个。