中央广播电视大学2001—2002学年度第一学期“开放本科”期末考试计算机专业数据结构试题

《中央广播电视大学2001—2002学年度第一学期“开放本科”期末考试计算机专业数据结构试题》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、___________________________________________________________________________________________中央广播电视大学2001—2002学年度第一学期“开放本科”期末考试计算机专业数据结构试题中央广播电视大学2001—2002学年度第一学期“开放本科”期末考试计算机科学与技术专业数据结构试题2002年1月一、单选题(每小题2分，共20分)1．与数据元素本身的形式、内容、相对位置、个数无关的是数据的()。A.存储结构B．逻辑结构C.算法

2、D．操作2．链式栈与顺序栈相比，一个比较明显的优点是()。A.插入操作更加方便B．通常不会出现栈满的情况C．不会出现栈空的情况D．删除操作更加方便3．对待排序的元素序列进行划分，将其分为左、右两个子序列，再对两个子序列施加同样的排序操作，直到子序列为空或只剩一个元素为止。这样的排序方法是(22________________________________________________________________________________________________________________

3、_____________________________________________________________________)。A.直接选择排序B．直接插入排序C．快速排序D．起泡排序4．若采用邻接矩阵法存储一个n个顶点的无向图，则该邻接矩阵是一个()。A.上三解矩阵B．稀疏矩阵C．对角矩阵D．对称矩阵5．在一个顺序存储的循环队列中，队头指针指向队头元素的()。A.前一个位置B．后一个位置C．队头元素位置D．队尾元素的前一位置6．用链表表示线性表的优点是()。A.便于随机存取B．花费的存储空间比顺序

4、表少C．便于插入与删除D.数据元素的物理顺序与逻辑顺序相同7．对5个不同的数据元素进行直接插人排序，最多需要进行()次比较。A．8B．10C.15D．258．下列存储形式中，()不是树的存储形式。A.双亲表示法B．左子女右兄弟表示法C．广义表表示法22_____________________________________________________________________________________________________________________________________

5、________________________________________________D．顺序表示法9．在一棵具有5层的满二叉树中结点总数为()。A．31B．32C.33D．1610．设有100个数据元素，采用折半搜索时，最大比较次数为()。A．6B．7C.8D．10二、判断题(判断下列各个叙述的正误。对，在题号前的括号内填入“√”；错，在题号前的括号内填入“×”。每小题1分，共10分)()1．算法的运行时间涉及加、减、乘、除、转移、存、取等基本运算。要想准确地计算总运算时间是不

6、可行的。()2.二维数组是数组元素为一维数组的线性表，因此它是线性结构。()3.顺序表用一维数组作为存储结构，因此顺序表是一维数组。()4．通常使用两个类来协同表示单链表，即链表的结点类和链表类。(22______________________________________________________________________________________________________________________________________________________________

7、_______________________)5．栈和队列都是顺序存取的线性表，但它们对存取位置的限制不同。()6．在使用后缀表示实现计算器类时用到一个栈的实例，其作用是暂存运算对象。()7．具有n个结点的完全二叉树的高度为+1。(n≥0，根在第0层)()8．为度量一个搜索算法的性能，需要在时间和空间方面进行权衡。()9．闭散列法通常比开散列法时间效率更高。()10．一棵m阶B树中每个结点最多有m个关键码，最少有2个关键码。三、阅读理解题(说明下列递归过程的功能。10分)四、简答题(共35分)1．对下面的

8、带权无向图采用prim算法从顶点①开始构造最小生成树。(写出加入生成树顶点集合S和选择边Edge的顺序)(10分)22________________________________________________________________________________________________________________________________