汗水和丰收是忠实的朋友，勤学和知识是一对最美丽的恋人。
数据结构模拟试题（1）
一、填空题:06分，每题02分
1、 从一个具有n个结点的单链表中搜索其值等于x的结点时, 在搜索成功的情况下, 需平均比较_______次。
2、 根据一组记录(56,42,50,64,48)依次插入结点生成一棵AVL树时，当插入到值为_______的结点时需要进行旋转调整。
3、 根据一组记录(56,74,63,64,48)依次插入结点生成一棵AVL树时，当插入到值为63的结点时需要进行________________调整。
单选题:10分，每题02分
4、 某算法的时间代价为T(n)=100n+10nlog2n+n2+10，其时间复杂度为（ ）。
A:O(n) B:O(nlog2n)
C:O(n2) D:O(1)
5、从一个长度为n的顺序表中顺序搜索一个值为x的元素时，在等概率的情况下，搜索成功时的平均比较次数为（ ）。
A:n B:n/2
C:(n+1)/2 D:(n-1)/2
6、在一个长度为n的顺序表中删除第i个元素（0≤i≤n-1）时，需要从前向后依次前移（ ）个元素。
A:n-I B:n-I+1
C:n-i-1 D:I
7、 不带头结点的单链表first为空的判定条件是( )。
A:first == NULL; B:first->link == NULL;
C:first->link == first; D:D. first != NULL;
8、 树中所有结点的度之和等于所有结点数加( )。
A:0 B:1
C:－1 D:2
9、 一棵具有35个结点的完全二叉树的高度为( )。假定空树的高度为 -1。
A:5 B:6
C:7 D:8
10、 对于具有e条边的无向图，它的邻接表中有 ( ) 个边结点。
A:e-1 B:e
C:2(e-1) D:2e
11、 图的深度优先搜索类似于树的（ ）次序遍历。
A:先根 B:中根
C:后根 D:层次
12、 设有向图有n个顶点和e条边，采用邻接表作为其存储表示，在进行拓扑排序时，总的计算时间为（ ）。
A:O(nlog2e) B:O(n+e)
C:O(ne) D:O(n2)
13、 在下列排序算法中，( )算法使用的附加空间与输入序列的长度及初始排列无关。
A:锦标赛排序 B:快速排序
C:基数排序 D:归并排序
二、判断题:10分，每题01分
14、 数组是一种静态的存储空间分配，就是说，在程序设计时必须预先定义数组的数据类型和存储空间大小，由编译程序在编译时进行分配。
15、 在顺序表中，逻辑上相邻的元素在物理位置上不一定相邻。
16、 每次从队列中取出的是具有最高优先权的元素, 这种队列就是优先级队列。
17、 若让元素1,2,3依次进栈，则出栈次序1,3,2是不可能出现的情况。
18
、 递归的算法简单、易懂、容易编写，而且执行效率也高。
19、 用非递归方法实现递归算法时一定要使用递归工作栈。
20、 一个广义表的表头总是一个广义表。
21、 对用顶点表示活动的网络（AOV网）进行拓扑排序必然得到唯一的结果。
22、 堆排序是一种稳定的排序算法。
23、 在散列法中采取开散列（链地址）法来解决冲突时, 其装载因子的取值一定在(0,1)之间。
三、中型计算题:10分，每题10分
24、 设有一个n×n的对称矩阵A，将其上三角部分按列压缩存放于一个一维数组B中：
B=[A00, A01, A11, A02, A12, A22, ......, A0 n-1, A1 n-1, A2 n-1, ......, An-1 n-1]
同时有两个函数：max(i,j)和min(i,j)，分别计算下标i和j中的大者与小者。试利用它们给出求任意一个A[i][j]在B中存放位置的公式。（若式中没有max(i,j)和min(i, j) 则不给分）
参考答案：
max(i,j)*(max(i,j)+1)/2+min(i,j)
25、 设有一个三维数组A[10][20][15]，按页/行/列存放于一个连续的存储空间中，每个数组元素占4个存储字，首元素A[0][0][0]的存储地址是1000，求A[8][4][10]的地址。
参考答案：
10880
答案解释：
对于三维数组，若第一、第二、第三维的元素个数为m1、m2、m3，每个元素所占存储字数为d，首地址为LOC(0,0,0)，则对于任一数组元素A[i][j][k]，它的存储地址为
LOC(i,j,k)=LOC(0,0,0)+(i*m2*m3+j*m3+k)*d
根据题意，m1=10, m2=20, m3=15, d=4, LOC(0,0,0)=1000，则有
LOC(8,4,10)=LOC(0,0,0)+(8*20*15+4*15+10)*4
=1000+2470*4=10880
26、 下图是一个3阶B树，试给出依次插入65和15之后B树的单关键码结点数和双关键码结点数。
单关键码结点数：
双关键码结点数：
参考答案：
单关键码结点数：9
双关键码结点数：2
四、小型计算题:40分，每题08分
27、 设有一个二维数组A[10][20]，按列存放于一个连续的存储空间中，A[0][0]的存储地址是200，每个数组元素占1个存储字，则A[6][2]的地址是多少。
参考答案：
226
答案说明：
按列存储时，计算A[i][j]地址的公式为
LOC(i,j)=LOC(0,0)+(j*m+i)*d
其中首地址LOC(0,0)=200, 每个数组元素的存储占用数d=1, 二维数组的行数m=10，则数组元素A[6][2]的存储地址为
LOC(6,2)=200+(2*10+6)*1=226
28、 设有一个10′10的对称矩阵A，将其上三角部分按行存放在一个一维数组B中，A[0][0]存放于B[0]中，那么A[8][5]存放于B中什么位置。
参考答案：
43
答案说明：
汗水和丰收是忠实的朋友，勤学和知识是一对最美丽的恋人。
根据题意，矩阵A中当元素下标I与J满足I≤J时，任意元素A[I][J]在一维数组B中的存放位置为
(2*n－I－1)*I/2+J
但当I＞J时，需要计算其对称元素
A[J][I]在B中的存放位置
(2*n－J－1)*J/2+I
因此，A[8][5]在数组B中对称元素A[J][I]的位置为
(2*10－5－1)*5/2+8=43
29、 已知一个有序表(15,26,34,39,45,56,58,63,74,76,83,94)顺序存储于一维数组a[12]中，根据折半搜索过程填写成功搜索下表中所给元素34, 56, 58, 63, 94时的比较次数。
参考答案：
元素 34 56 58 63 94
比较次数 2 1 3 4 4
30、 已知一棵二叉搜索树的广义表表示为：28(12(,16),49(34(30),72(63)))，求出从中依次删除72,12,49,28结点，最后得到的二叉搜索树的广义表表示。
广义表表示：
参考答案：
广义表表示：30(16,63(34))
31、 已知一个数据表为{48,25,56,32,40}，请写出在进行快速排序的过程中每次划分后数据表的变化。
(0) [48 25 56 32 40]
(1)
(2)
(3)
参考答案：
(0) [48 25 56 32 40]
(1) [40 25 32] 48 56
(2) [32 25] 40 48 56
(3) 25 32 40 48 56
32、 已知有一个数据表为{30,18,20,15,38,12,44,53,46,18*,26,86}，给出进行归并排序的过程中每一趟排序后的数据表变化。
(0) [30 18 20 15 38 12 44 53 46 18* 26 86]
(1)
(2)
(3)
(4)
参考答案：
(0) [30 18 20 15 38 12 44 53 46 18* 26 86]
(1) [18 30][15 20][12 38][44 53][18* 46][26 86]
(2) [15 18 20 30][12 38 44 53][18* 26 46 86]
(3) [12 15 18 20 30 38 44 53][18* 26 46 86]
(4) [12 15 18 18* 20 26 30 38 44 46 53 86]
33、 设散列表为HT[17], 待插入关键码序列为{"Jan", "Feb", "Mar", "Apr", "May", "June", "July", "Aug","Sep","Oct","Nov","Dec"}，散列函数为H(key)=?i/2?，其中i是关键码第一个字母在字母表中的序号（字母'A'在字母表中的序号为1，以下类推），采用线性探查法解决冲突。根据建立的闭散列表，搜索长度大于等于3的关键码有那些？
搜索长度大于等于3的关键码有：
参考答案：
搜索长度大于等于3的关键码有："June","July","Oct","Nov"
五、综合题:20分，每题10分
34、 已知二叉树中的结点类型BinTreeNode定义为:
struct BinTreeNode {ElemType data; BinTreeNode *left, *right;};
其中data为结点值域，left和right分别为指向左、右子女结点的指针域。参数bt指向一棵二叉树，引用参数x一开始具有的值小于树中所有结点的值。试根据下面的函数定义指出此算法的功能。
int JB(BinTreeNode* bt, ElemType& x)
{
if(bt==NULL) return 1;
else {
if(JB(bt->left,x)==0) return 0;
if(bt->data
if(JB(bt->right,x)==0) return 0;
else return 1;
}
}
算法功能：
参考答案：
算法功能：判断二叉树bt是否为一棵二叉搜索树，若是则返回1否则返回0。
六、填空题(主观):04分，每
题02分
35、 快速排序在平均情况下的空间复杂度为____________。
参考答案：
O(log2n)
36、 假定对长度为n的线性表进行索引顺序搜索，并假定每个子表的长度均为 ，则进行索引顺序搜索的时间复杂度为________。
参考答案：
O()
汗水和丰收是忠实的朋友，勤学和知识是一对最美丽的恋人。