一、单项选择题(共40分，每题2分)
1. 树形结构是数据元素之间存在一种（ D ）。
A.一对一关系 B.多对多关系
C.多对一关系 D.一对多关系
2. 设语句x++的时间是单位时间，则以下语句的时间复杂度为（ B ）。
for(i=1; i<=n; i++)
for(j=i; j<=n; j++)
x++;
A.O(1) B.O() C.O(n) D.O()
3. 线性表是（A）。
A．一个有限序列，可以为空 B．一个有限序列，不可以为空
C．一个无限序列，可以为空 D．一个无限序列，不可以为空
4. 在顺序表中，只要知道（D），就可在相同时间内求出任一结点的存储地址。
A．基地址 B．结点大小
C．向量大小 D．基地址和结点大小
5. 设有一个栈，元素的进栈次序为A, B, C, D, E,下列是不可能的出栈序列（C）。
A．A, B, C, D, E B．B, C, D, E, A
C．E, A, B, C, D D．E, D, C, B, A
6. 一个子串在包含它的主串中的位置是指（ D ）。
A.子串的最后那个字符在主串中的位置
B.子串的最后那个字符在主串中首次出现的位置
C.子串的第一个字符在主串中的位置
D.子串的第一个字符在主串中首次出现的位置
7. 已知二维数组A10×10中，元素a20的地址为560，每个元素占4个字节，则元素a10的地址为（ A ）。
A.520 B.522 C.524 D.518
8. 假设在一棵二叉树中，双分支结点数为15，单分支结点数为30个，则叶子结点数为（ B ）个。
A. 15 B. 16 C. 17 D. 47
9. 在一棵二叉树上第4层的结点数最多为（ D ）。
A. 2 B. 4 C. 6 D. 8
10. 已知一棵完全二叉树的结点总数为9个，则最后一层的结点数为（ B ）。
A. 1 B. 2 C. 3 D. 4
11. 下面叙述正确的是（ D ）。
A. 二叉树是特殊的树
B. 二叉树等价于度为2的树
C. 完全二叉树必为满二叉树
D. 二叉树的左右子树有次序之分
12. 在一个具有n个顶点的有向图中，若所有顶点的出度数之和为s，则所有顶点的入度数之和为( A )。
A. s B. s-1 C. s+1 D. n
13. 在一个具有n个顶点的无向完全图中，所含的边数为( C )。
A. n B. n(n-1) C. n(n-1)/2 D. n(n+1)/2
14. 在一个无向图中，若两顶点之间的路径长度为k，则该路径上的顶点数为( B )。
A. k B. k+1 C. k+2 D. 2k
15. 对于长度为18的顺序存储的有序表，若采用折半查，则查第15个元素的比较次数为( B )。
A. 3 B. 4 C. 5 D. 6
16. 若根据查表(23,44,36,48,52,73,64,58)建立哈希表，采用h(K)=K%13计算哈希地址，则元素64的哈希地址为( C )。
A. 4 B. 8 C. 12 D. 13
17. 假定对元素序列（7, 3, 5, 9, 1, 12, 8, 15）进行快速排序，则进行第一次划分后，得到的左区间中元素的个数为（ B ）。
A. 2 B. 3 C. 4 D. 5
18. 假定对元素序列（7, 3, 5, 9, 1, 12）进行堆排序，并且采用小根堆，则由初始数据构成的初始堆为（ B ）。
A. 1, 3, 5, 7, 9, 12 B. 1, 3, 5, 9, 7, 12
C. 1, 5, 3, 7, 9, 12 D. 1, 5, 3, 9, 12, 7
19. 设有广义表D=(a,b,D)，其长度为（ B ），深度为（ A ）。
A.无穷大 B.3 C.2 D.5
20. 假定在数组A中，每个元素的长度为3个字节，行下标i从1到8，列下
标j从1到10，从首地址SA开始连续存放在存储器内，存放该数组至少需要的单元数为（ C ）。
A.80 B.100 C.240 D.270
二、填空题(共10分, 每题1分)
1. 线性结构中元素之间存在_____一对一_____关系；树型结构中元素之间存在_____一对多____关系；图型结构中元素之间存在_______多对多______关系。
2. 一个算法的效率可分为_______时间______效率和_____空间_ ____效率。
3. 顺序表中逻辑上相邻的元素的物理位置__也相邻_____。
4. 由三个结点构成的二叉树，共有__5__种不同的形态
5. 设有一空栈，现有输入序列1，2，3，4，5，经过push, push, pop, push, pop, push, push后，输出序列是___23541______。
6. 一个广义表为(a,(a,b),d,e,((i,j),k))，则该广义表的长度为__5___，深度为___3__。
7. 对于一棵具有n个结点的二叉树，若一个结点的编号为i(1≤i≤n)，则它的左孩子结点的编号为____2i____，右孩子结点的编号为____2i+1____，双亲结点的编号为 i/2（或字符串长度为0和50之间 i/2 ） 。
8. 表示图的两种存储结构为_____邻接矩阵_____和___邻接表_______。
9. 图中的一条路径长度为k，该路径所含的顶点数为__k+1______。
10. 对线性表(18,25,63,50,42,32,90)进行哈希存储时，若选用H(K)=K % 9作为哈希函数，则哈希地址为0的元素有____3____个，哈希地址为5的元素有_____2___个。
三、简答题(共30分)
1.线性表的定义及其两种存储方式
参考答案：
线性表是n个数据元素的有限序列，其中n（n≥0）为线性表的长度。
顺序表是指线性表的顺序存储结构，即用一组连续的存储单元依次存放线性表的数据元素。
链表是线性表的链式存储结构。链表是用一组任意的存储单元（可以是连续的，也可以是不连续的）存放线性表的数据元素。
2.一棵度为2的树与一棵二叉树有什么区别？
参考答案：
度为2的树有两个分支，但分支没有左右之分；一棵二叉树也有两个分支，但有左右之分，左右子树的次序不能交换。
3. 假定用于通信的电文由8个字符A、B、C、D、E、F、G、H组成，各字母在电文中出现的概率为5％、25％、4％、7％、9％、12％、30％、8％，试为这8个字母设计哈夫曼编码。
参考答案：
设计哈夫曼编码
利用得到的哈夫曼树，规定左分支用0表示，右分支用1表示，字母A、B、C、D、E、F、G、H的哈夫曼编码如下表示：
A:0011 B:01 C:0010 D:1010
E:000 F:100 G:11 H:1011
4. 对于如下图所示的带权无向图，用图示说明：
（1）利用prim算法从顶点a开始构造最小生成树的过程；
（2）利用kruskal算法构造最小生成树的过程。
参考答案：
1、利用Prim算法从顶点a开始构造最小生成树的过程如图所示。
2、利用Kruskal算法构造最小生成树的过程如图所示。
四、算法实现题(共20分)(请考生根据自己所学的语言编写，可以用C、C++、JAVA、C#、PHP中任一种语言实现，如果采用伪代码实现功能成绩减半)
1、在整型顺序表的某个位置删除一个值为a的整型元素。
参考答案：
public boolean delete(int i){
int j;
if(i<0||i>=length){ //检查删除位置是否存在
System.out.println("The position is mistake.");
return false;
}
for(j=i;j<length;j++){
data[j] = data[j+1];
length --;
return true;
}
}
2、折半查程序实现
参考答案：
public class HalfSearch{
public int Binary_Search(int a[],int k){
int low ,high,mid ,flag=0;
low=1;high=a.length;
while(low<=high)
{
mid=(low+high)/2;
if(k<a[mid])
high=mid-1;
else if(k>a[mid])
low=mid+1;
else{
flag=mid;
System.out.println(flag);
break;
}
}
return flag;
}
一、单项选择题(共40分，每题2分)
1. 计算机内部数据处理的基本单位是（ B ）。
A.数据 B.数据元素 C.数据项 D.数据库
2. 设语句x++的时间是单位时间，则以下语句的时间复杂度为（ B ）。
for(i=1; i<=n; i++)
for(j=i; j<=n; j++)
x++;
A.O(1) B.O() C.O(n) D.O()
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。
发表评论