计算机科学与技术专业数据结构试题(最终)1.pdf

《计算机科学与技术专业数据结构试题(最终)1.pdf》由会员分享，可在线阅读，更多相关《计算机科学与技术专业数据结构试题(最终)1.pdf（4页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、计算机科学与技术专业数据布局试题一、填空题每题2 分1、与数据元素本身的形式、内容、相对位置、个数无关的是数据的A 存储布局B 逻辑布局C 算法D 操作2、链式栈与挨次栈比拟，一个比拟明显的长处是A 插入操作更加便利B 通常不会呈现栈满的情况C 不会呈现栈空的情况D 删除操作更加便利3、对待排序的元素序列进行划分，将其分为左、右两个子序列，再对两个子序列施加同样的排序操作，直到子序列为空或只剩一个元素为止。这样的排序方法是A 直接选择排序B 直接插入排序C 快速排序D 起泡排序4、假设采用邻接矩阵法存储一个N 个顶点的无向图，那么该邻接矩阵是一个A 上三角矩阵B 稀疏矩阵C 对角矩阵D 对称矩

2、阵5、在一个挨次存储的循环队列中，队头指针指向队头元素的A 前一个位置B 后一个位置C 队头元素位置D 队尾元素的前一位置6、用链表暗示线性表的长处是A 便于随机存取B 花费的存储空间比挨次表少C 便于插入与删除D 数据元素的物理挨次与逻辑挨次不异7、对 5 个不同的数据元素进行直接插入排序，最多需要进行次比拟。A 8B 10C 15D 258、以下存储形式中，不是树的存储形式A 双亲暗示法B 左子女右兄弟暗示法C 广义表暗示法D 挨次暗示法9、在一棵具有 5 层的满二叉树中结点数为A 31B 32C 33D 1610、设有 100 个数据元素，采用折半搜索时，最大比拟次数为A 6B 7C 8

3、D 10二、判断题每题1 分1、算法的运行时间涉及加、减、乘、除、转移、存、取、等根本运算。要想准确地计算总运算时间是不成行的。2、二维数组是数组元素为一维数组的线性表，因此它是线性布局。3、挨次表用一维数组作为存储布局，因此挨次表是一维数组。4、通常使用两个类来协同暗示单链表，即链表的结点类和链表类。5、栈和队列都是挨次存取的的线性表，但它们对存取位置的限制不同。6、在使用后缀表暗示实现计算器时用到一个栈的实例，其作用是暂存运算对象。7、具有 n 个结点的完全二叉树的高度为log2n+1。8、为度量一个搜索算法的性能，需要在时间和空间方面进行权衡。9、闭散列法通常比开散列法时间效率更高。10

4、、一棵 m阶 B树中每个结点最多有m个关键码，最少有2 个关键码。三、阅读理解题 10分void unknown(BinTreeNodeif(T!=NULL)*T,int a,int i)ai=T-data;unknown(T-leftChild,a,2unknown(T-rightChild,a,2*I+1);*I+2);主程序调用方式 unknown(BT.root,a,0);/将完全二叉树所有结点从要开始，自顶向下，同一层自左向右持续编号，/根结点的编号为 0。四、简答题共 35 分1、对下面的带权无向图采用prim 算法从顶点开始构造最小生成树。写出参加生成树顶点调集S和选择 Edge

5、的挨次 10分9107567118S：顶点号Edge：顶点，顶点，权值，2、某二叉树的结点数据采用挨次存储暗示如下：0123456789101112 1314 15161718 19EAFDHCGIB1试画出此二叉树的图形暗示。3 分2写出结点 D 的双亲结点及左、右子女。3 分3将此二叉树看作丛林的二叉树暗示，试将它复原为丛林。3 分3、设待排序序列为 10，18，4，3，6，12，1，9，15，8，请给出用希尔排序每一趟的成果。增量序列取为5，3，2，1。每一趟 2 分，共 8 分4、设散列表的长度为13，散列函数为Hk=k%13，给定的关键码序列为 19，14，23，01，68，20，8

6、4，27。试画出用线性探查法解决冲突时所构成的散列表。8分012345678910五、综合算法题每题5 分，共 15 分对于二维整数数组 Amn，对以下三种情况，别离编写相应的函数。1求数组所有边缘的和。5 分int suml(int AMN,int m,int n)/M和 N 别离大于等于 m 和 n2求从 A00 开始的互不相邻的所有元素的和5 分注：一个元素的八个标的目的上的第一个元素均为相邻元素。int sum2(int AMN,int m,int n)3假定 m=n，请别离计算正、反两条对角线上的元素的和。int sum3(int AMN,int n)11125 分六、填空题每题2

7、分，共 10 分一棵完全二叉树存放于一个一维数组Tn中，Tn中存放的是各结点的值。下面的算法的功能是：从 T0 开始挨次读出各结点的值，成立该二叉树的二叉链表暗示。此算法有 5 处缺掉，请按照 算法的功能补充之。10 分#includetypedef struct node int data;stuct nodeleftChild,rightchild;BintreeNode;typedef BintreeNode*BinaryTree;void ConstrucTree(int T ,int n,int I,BintreeNode*&ptr);int main(void)Binarytree t;int n;Coutn;Int*A=new intn;For(int I=0;In;I+);从键盘输入结点值For(int I=0;In;I+)coutAi;Cout=n);/置根指针为空elseptr=new BintreeNode;ptr-data=Ti;ConstrucTree(T,n,2*I+1,);ConstrucTree(T,n,ptr-rightchild);缺掉语句为：