一、名词解释(每题2分，共10分)
1. 数据类型
2. 线性表
3. 队列
4. 串
5. 图
二、判断正误(正确打√，错误划×，每题1分，共10分)
1. 算法必须有输入参数。( )
2. 链表能够动态分配结点空间。( )
3. 栈是一种先进先出的线性表。( )
4. 二维数组能够实现随机存取。( )
5. 在二叉树的第i层上至多有2i-1个结点(i≥1)。( )
6. 在有向图中，<v1,v2>与<v2,v1>是两条不同的边。( )
7. 邻接表只能用于有向图的存储。（ ）
8. 有向图不能进行广度优先遍历( )
9. 平均查找长度 ASL可作为衡量一个查找算法效率高低的标准。( )
10. 所有的内部排序算法都是稳定的。( )
三、填空(每空2分，共10分)
1. 线性表、栈和队列都是( )结构。
2. 栈是一种特殊的线性表，允许插入和删除运算的一端称为（ ）。
3. 队列的出队操作总是在( )进行。
4. 按存储结构不同，串可分为( )。
5. 深度为k 的完全二叉树至少有( )个结点。
四、选择题(单选或多选)(每题2分，共30分)
1. 算法原则上都是能够由机器或人完成的。整个算法好像是一个解决问题的“工作序列”，其中的每一步都是我
们力所能及的一个动作。这是算法的( )。
A. 正确性 B. 有穷性 C. 确定性 D. 可行性
2. 设一棵二叉树中，度为2的结点数为9，则该二叉树的叶结点的数目为( )。
A．10 B. 11 C. 12 D. 不确定
3. 某二叉树结点的先根序列为E、A、C、B、D、G、F，对中根遍历的序列为A、B、C、D、E、F、G。该二
叉树结点的后根遍历的序列为( )
A. [B 、D 、C 、A 、F 、G 、E] B. [B 、D 、C 、F 、A 、G 、E]
C. [E 、G 、F 、A 、C 、D 、B] D. [E 、G 、A 、C 、D 、F 、B]
4. 关于队列的说法正确的是（ ）
A. 先进先出 B. 属于非线性结构 C. 只能采用顺序存储 D.属于散列结构
5. 用单链表表示的链式队列的队尾是在链表的( )位置
A. 表尾 B. 表头 C. 表中 D. 任意
6. 树的非叶子结点是（ ）。
A. 度为1的结点 B. 根结点 C. 度不为0的结点 D. 孩子结点
7. 设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为( )。
A. 2h B. 2h+1 C. 2h-1 D. h+1
8. 深度为5的二叉树至多有多少个结点？( )
A 16 B 32 C 31 D 10
9. 在一个图中，所有顶点的度数之和等于图的边数的( )倍。
A. ½ B. 1 C. 2 D. 4
10. 有8个顶点的无向图最多有( )条边。
A. 14 B. 28 C. 56 D. 112
11. 具有8个顶点的有向完全图有( )条边。
A. 14 B. 112 C. 28 D. 56
12. 生成树的构造方法有( )。
A．深度优先 B. 深度优先和广度优先 C. 无前驱的顶点优先 D. 无后继的顶点优先
13. 采用顺序查找法查找长度为n的线性表时，每个元素的平均查找长度为( )
A. n B. n/2 C. (n+1)/2 D. (n-1)/2
14. 关于二分查找的说法正确的有( )
A. 可用二叉树来描述 B. 要求线性表是有序表
C. 适用于链式存储结构 D. 适用于任意的线性表
15. 关于冒泡排序的说法正确的有( )
A. 属于交换排序 B. 在整个排序过程中，最多执行n-1遍
C. 属于选择排序 D. 在某一趟排序过程没有气泡交换，则可终止该算法
五、简述题 (每题10分，共30分)
1. 什么是数据结构？试举一个简单的例子说明。
2. 何时选用顺序表、何时选用链表作为线性表的存储结构为宜？
3. 数组、广义表与线性表之间有什么样的关系？
六. 程序分析与设计(每题5分，共10分)。
1. 假设以下代码段中，R为线性表
void Separate(SeqList R)
{
int i,j;
i=1; j=n;
while(i<j){
while(s[i]<0)i++;
while(s[j]>0)j--;
if(i>=j)break;
R[0]=s[i];s[i]=s[j];s[j]=R[0];
i++; j--;
}
}
试说明该代码段主要实现了什么功能？
2. 设计一个算法，利用折半查找算法在一个有序表中插入一个元素x，并保持表的有序性。
一、名词解释(每题2分，共10分)
1. 数据类型
答：数据类型 （data type ）是计算机程序中的数据对象以及定义在这个数据对象集合上的一组操作的总称。可以看作是数据结构的实现。
2. 线性表
答：线性表（Linear List）是具有相同数据类型的n(n≥0)个数据元素的有限序列，通常记为：(a1，a2，… ai-1，ai，ai+1，…an)，其中，数据元素的个数n称为线性表的长度。当n＝0 时称为空表。
3. 队列
答：队列 (Queue)是另一种限定性的线性表，它只允许在表的一端插入元素，而在另一端删除元素，所以队列具有先进先出(Fist In Fist Out， 缩写为FIFO)的特性。
4. 串
答：是字符串的简称，是由零个或多个字符组成的有限序列。
5. 图
答：图是由顶点集合及顶点间的关系集合组成的一种数据结构。
二、判断正误(每题1分，共10分)
1~5 ×√×√√
6~10 √××√×
三、填空(每空2分，共10分)
1.线性2. 栈顶 3. 队头 4. 顺序串和链串 5. 2k-1
四、选择题(单选或多选) (每题2分，共30分)
1 D 2 A 3 A 4 A 5 A
6 C 7 C 8 C 9 C 10 B
11 D 12 B 13 C 14 AB 15 ABD
五、简述题 (每题10分，共30分)
1. 什么是数据结构？试举一个简单的例子说明。
答：数据结构是指数据对象（集合）以及该数据对象集合中的数据元素之间的相互关系的集合（即数据元素的组织形式）。
例如，栈的逻辑结构是线性表(后进先出)，栈在计算机中既可以采用顺序存储业可以采用链式存储；对栈可进行入栈、出栈，判断是否为空栈以及将栈置空等操作。
2. 何时选用顺序表、何时选用链表作为线性表的存储结构为宜？
答：头顺序表中查找元素、获取表长非常容易，但是，要插入或者删除一个元素却需要移动大量的元素；相反，链表中却可以方便地插入或者删除元素，但在查找元素时需要进行遍历。因此，当所涉及的问题常常需要进行查找等操作，而插入、删除操作相对较少的时候，适合采用顺序表；当常常需要进行插入、删除操作的时候，适合采用链表。
3. 数组、广义表与线性表之间有什么样的关系？
答：广义表是线性表的推广，线性表是广义表的特例，当广义表中的元素都是原子时，即为线性表。数组可以看做是线性表的一种。
六. 程序分析(每题5分，共10分)。
1. 答：该代码段主要实现的功能为：遍历整个线性表，并且将负整数放在线性表的前半部分，正整数放在线性表的后半部分。
2. 答：
void insert(sqlist r,int x,int n)
{
int low=0,high=n-1,mid,pos,i,find=0;
while(low<high&&!find)
{
mid=(low+high)/2;
if(x<r[mid].key)
high=mid-1;
else if(x>r[mid].key)
low=mid+1;
else
{
i=mid;
find=1;
}
}
if(find)
pos=mid;
else
pos=low;
for(i=n;i>=pos+1;i--)
r[i].key=r[i-1].key;
r[pos].key=x;
}
来源：网络整理 免责声明：本文仅限学习分享，如产生版权问题，请联系我们及时删除。
相关文章：
电大《中国古代文学( B )( l )》试题 2011 年1 月04-27
电大《中国古代文学(B)（1）》试题 2009年7月04-27
电大《中国古代文学(B) （1)》试题 2010年1月04-27
电大《学前儿童发展心理学》试题 2013 年1 月04-27