一、名词解释(每题2分，共10分)
1. 数据结构
2. 算法
3. 栈
4. 二叉树
5. 查找
二、判断正误(正确打√，错误划×，每题1分，共10分)
1. 算法可以是无限循环。( )
2. 顺序表能够动态分配结点空间。( )
3. 队列是一种先进先出的线性表。( )
4. 广义表的求表尾操作得到的也是广义表。( )
5. 二叉树的叶子结点数等于度为2的结点数。( )
6. 图的任一结点的相邻结点数不能大于2。( )
7. 二分查找适于任意的线性表。（ ）
8. 假设结点总数为n，冒泡排序至多进行n-1轮排序。( )
9. 单链表的结点的指针域只能有一个。( )
10. 顺序查找方法既适用于线性表的顺序存储结构，也适用于线性表的链式存储结构。( )
三、填空(每空2分，共10分)
1. 数据的逻辑结构是数据元素之间的逻辑关系，通常有下列4 类：集合、线性结构、树型结构、( )。
2. 一个算法必须在执行有穷步之后结束，这是算法的( )。
3. ( )是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。
4. 设一棵二叉树中，度为2的结点数为9，则该二叉树的叶结点的数目为( )。
5. 若图G中每条边都( )方向，则G为有向图。
四、选择题(单选或多选)(每题2分，共30分)
1. 算法的每一步，必须有确切的定义，也就是说，对于每一步需要执行的动作必须严格、清楚地给出规定。这
是算法的( )
A. 正确性 B. 有穷性 C. 确定性 D. 可行性
2. 设一棵二叉树中，度为1的结点数为9，则该二叉树的叶结点的数目为( )。
A. 10 B. 11 C. 12 D. 不确定
3. 任何一棵二叉树的叶子结点在先根、中根和后遍历序列中的相对次序( )
A. 不发生改变 B. 发生改变 C. 不能确定 D. 以上都不对
4. 关于栈的说法正确的是（ ）
A. 后进先出 B. 属于非线性结构 C. 只能采用顺序存储 D.属于散列结构
5. 用单链表表示的链式队列的队头是在链表的( )位置
A. 表尾 B. 表头 C. 表中 D. 任意
6. 树的叶子结点是（ ）。
A. 度为1的结点 B. 根结点 C. 度为0的结点 D. 孩子结点
7. 图的邻接矩阵是表示( )之间相邻关系的矩阵。
A. 边 B. 顶点 C. 路径 D.有向边
8. 一个图的生成树的顶点是图的( )顶点。
A. 1个 B. 1/3 C. 所有 D.1/2
9. 广度优先遍历算法类似于二叉树的( )遍历
A. 按层次 B. 先根 C. 中根 D. 后根
10. 如果要求一个线性表既能较快地查找，又能适应动态变化的要求，可以采用( )查找方法
A. 分块 B. 顺序 C. 折半 D. 散列
11. 在对n个元素进行冒泡排序的过程中，至少需要（ ）趟完成。
A. n-1 B. n C. 1 D. n/2
12. 若一个元素序列基本有序，则选用( )方法较快
A 直接插入排序 B 直接选择排序 C 堆排序 D 快速排序
13. 关于链式存储的说法正确的有( )
A. 能动态分配结点空间 B. 只能应用于线性表结构
C. 能随机存取 D. 需要定义指针域
14. 数据的存储结构所包括的存储方法有( )
A. 顺序存储方法 B. 链接存储方法
C. 索引存储方法 D. 散列存储方法
15. 以下哪些属于算法的特性( )
A. 有穷性 B. 确定性
C. 可行性 D. 运行性
五、简述题 (每题10分，共30分)
1. 算法与程序有何异同?
2. 试描述头指针、头结点、开始结点的区别
3. 简述二叉树先根遍历思想。
六. 程序分析与设计(每题5分，共10分)。
． 1. 假设以下代码段中，b为指向二叉树根结点的指针
． Btree swaptree(btree b)
{
btree t,t1,t2;
if (b==NULL) t=NULL;
else {
t=(btree)malloc(sizeof(btree));
t->data=b->data;
t1=swaptree(b->Lchild);
t2=swaptree(b->Rchild);
t->Lchild=t2;
t->Rchild=t1;
}
return t;
}
试说明该代码段主要实现了什么功能？
2. 试写一算法，将x插入顺序表L中。
一、名词解释(每题2分，共10分)
1. 数据结构
答：是指数据对象（集合）以及该数据对象集合中的数据元素之间的相互关系的集合（即数据元素的组织形式）。
2. 算法
答：是对特定问题求解步骤的一种描述 ，它是指令的有限序列，其中每一条指令表示一个或多个操作。
3. 栈
答：栈是一种仅允许在一端进行插入和删除运算的线性表,通常将表中允许进行插入、删除操作的一端称为栈顶(Top)，同时表的另一端被称为栈底(Bottom)。
4. 二叉树
答：二叉树是由n(n≥0) 个结点的有限集T 构成，此集合或者为空集，或者由一个根结点及两棵互不相交的左右子树组成，并且左右子树都是二叉树。
5. 查找
答：在含有n条记录的表（文件）中找出关键字等于给定值K的记录。若找到，则查找成功，返回该记录的信息或该记录在表（文件）中的位置；否则查找失败，返回相关的指示信息。
二、判断正误(每题1分，共10分)
1~5 ××√√×
6~10 ××√√√
三、填空(每空2分，共10分)
1.图状结构2. 有穷性 3. 队列 4. 10 5. 有
四、选择题(单选或多选) (每题2分，共30分)
1 C 2 D 3 C 4 A 5 B
6 C 7 B 8 C 9 A 10 A
11 C 12 A 13 AD 14 ABCD 15 ABC
五、简述题 (每题10分，共30分)
1. 算法与程序有何异同?
答：尽管算法的含义与程序非常相似，但两者还是有区别的。首先，一个程序不一定满足有穷性，因此它不一定是算法。例如，系统程序中的操作系统，只要整个系统不遭受破坏，它就永远不会停止，即使没有作业要处理，它仍处于等待循环中，以待一个新作业的进入。因此操作系统就不是一个算法。其次，程序中的指令必须是计算机可以执行的，而算法中的指令却无此限制。如果一个算法采用机器可执行的语言来书写，那么它就是一个程序。
2. 试描述头指针、头结点、开始结点的区别。
答：头结点
为了更方便的判断空表、插入和删除结点，通常在单链表的第一个结点前面加上一个附设的节点，称为头结点。头结点的数据域可以不存储任何信息，也可以存储一些附加信息；而头结点的指针域存储链表第一个结点的地址。
如果头结点的指针域为“空”，即L->next==NULL，则表示该链表为空表
头指针
是指向链表中的第一个结点( 可以是头结点，也可以是开始结点) 的指针。若链表中附设了头结点，则不管线性表是否为空，头指针均不为空；若链表中不设头结点，则线性表为空时，链表的头指针为空
开始结点(即首元结点)
是指链表中存储线性表中第一个数据元素a1的结点
3. 简述二叉树先根遍历思想。
答：先根遍历是先访问根结点，再先根遍历左右子树。
六. 程序分析与设计(每题5分，共10分)。
1. 答：该代码段主要实现的功能为：以二叉链表为存储结构，交换各结点的左右子树。
2. 答：
int Ins(sequenlist *L， int i, datatype item)
{int j;
if(i<0 || i>L->length) return FALSE；
for(j=L->length;j>i-1;j--) /*因为数组的下标从0开始*/
L->elem[j]=L->elem[j-1]; /*后移*/
L->elem[i-1]=item; /*插入*/
L->length++; /*元素个数增1*/
return TRUE;
}
来源：网络整理 免责声明：本文仅限学习分享，如产生版权问题，请联系我们及时删除。
相关文章：
电大《学前教育学》试题 2013年1月04-27
电大《学前教育学》试题2012年7月04-27
电大《学前教育学》试题2011年1月04-27
电大《中国古代文学( B )( l )》试题 2011 年1 月04-27
电大《中国古代文学(B)（1）》试题 2009年7月04-27