计算机科学与技术专业数据结构试题

《计算机科学与技术专业数据结构试题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、８开放教育(本科)计算机科学与技术专业《数据结构》2002年1月试题及答案试卷代号：1010中央广播电视大学2001～2002学年度第一学期“开放教育(本科)”期末考试计算机科学与技术专业数据结构试题2002年1月一、单选题（每小题2分，共20分）1．与数据元素本身的形式、内容、相对位置、个数无关的是数据的（）。A、存储结构B、逻辑结构C、算法D、操作2．链式栈与顺序栈相比，一个比较明显的优点是（）。A、插入操作更加方便B、通常不会出现栈满的情况C、不会出现栈空的情况D、删除操作更加方便3．对待

2、排序的元素序列进行划分，将其分为左、右两个子序列，再对两个子序列施加同样的排序操作，直到子序列为空或只剩下一元素为止。这样的排序方法是（）。A、直接选择排序B、直接插入排序C、快速排序D、起泡排序4．若采用邻接矩阵法存储一个n个顶点的无向图，则该邻接矩阵是一个（）。A、上三角矩阵B、稀疏矩阵C、对角矩阵D、对称矩阵5．在一个顺序存储的循环队列中，队头指针指向队头元素的（）。A、前一个位置B、后一个位置C、队头元素位置D、队尾元素的前一个位置6．用链表表示线性表的优点是（）。A、便于随机存取B、花

3、费的存储空间比顺序表少C、便于插入与删除D、数据元素的物理顺序与逻辑顺序相同7．对5个不同的数据元素进行直接插入排序，最多需要进行（）次比较。A、8B、10C、15D、258．下列存储形式中，（）不是树的存储形式。A、双亲表示法B、左子女右兄弟表示法C、广义表表示法D、顺序表表示法9．在一棵具有5层的满二叉树中结点的总数为（）。A、31B、32C、33D、1610．设有100个数据元素，采用折半搜索时，最大比较次数为（）。A、6B、7C、8D、10二、判断题（判断下列各个叙述的正误。对，在题号前

4、的括号内填入“√”；错，在题号前的括号内填入“×”。每小题1分，共10分）（）1、算法的运行时间涉及加、减、乘、除、转移、存、取等基本运算。要想准确地计算总运算时间是不可行的。（）2、二维数组是数组元素为一维数组的线性表，因此它是线性结构。（）3、顺序表用一维数组作为存储结构，因此顺序表是一维数组。（）4、通常使用两个类来协同表示单链表，即链表的结点类和链表类。（）5、栈和队列都是顺序存取的线性表，但它们对存取位置的限制不同。８开放教育(本科)计算机科学与技术专业《数据结构》2002年1月试题及

5、答案（）6、在使用后缀表示实现计算器类时用到一个栈的实例，其作用是暂存运算对象。（）7、具有n个结点的完全二叉树的高度为。（n≥0，根在第0层）（）8、为度量一个搜索算法的性能，需要在时间和空间方面进行权衡。（）9、闭散列法通常比开散列法时间效率更高。（）10、一棵m阶B树中每个结点最多有m个关键码，最少有2个关键码。三、阅读理解题（说明下面递归过程的功能。10分）intunknown(BinTreeNode*T,inta[],inti){//指针T是完全二叉树的根指针。if(T!=NULL){

6、a[i]=Tàdata;unknown(TàleftChild,a,2*i+1);unknown(TàrightChild,a,2*i+2);}}四、简答题（共35分）1、对下面的带权无向图采用prim算法从顶点①开始构造最小生成树。（写出加入生成树顶点集合S和选择边Edge的顺序）(10分)2、设某二叉树的结点数据采用顺序存储表示如下：８开放教育(本科)计算机科学与技术专业《数据结构》2002年1月试题及答案(1)请画出此二叉树的图形表示。(3分)(2)写出结点D的双亲结点及左、右子女。(3分

7、)(3)将此二叉树看作森林的二叉树表示，试将它还原为森林。(3分)3、设待排序序列为{10，18，4，3，6，12，1，9，15，8}，请给出用希尔排序每一趟的结果。增量序列取为5，3，2，1。（每一趟2分，共8分）4、设散列表的长度为13，散列函数为H(k)=k%13，给定的关键码序列为19，14，23，01，68，20，84，27。试画出用线性探查法解决冲突时所构成的散列表。（8分）五、综合算法题（每小题5分，共15分）对于二维整数数组A[m][n]，对下列三种情况，分别编写相应的函数。(1

8、)求数组所有边缘元素的和。(5分)intsum1(intA[M][N],intm,intn)//M和N分别大于等于m和n{}(2)求从A[0][0]开始的互不相邻的所有元素的和。(5分)注：一个元素的八个方向上的元素的第一个元素均为相邻元素。intsum2(intA[M][N],intm,intn){}(3)假定m=n，请分别计算正、反两条对角线上的元素的和。(5分)intsum3(intA[M][N],intn){}六、填空题（每空2分，共10分）已知一棵完全二叉树存放于一个一维数组T[n]中