数据结构试题及答案6

6-1《数据结构》自考复习思考试题○6一、填空题（每小题2分）1、与数据元素本身的形式、内容、相对位置、个数无关的是数据的（）A存储结构B逻辑结构C算法D操作2、链式栈与顺序栈相比，一个比较明显的优点是（）A插入操作更加方便B通常不会出现栈满的情况C不会出现栈空的情况D删除操作更加方便3、对待排序的元素序列进行划分，将其分为左、右两个子序列，再对两个子序列施加同样的排序操作，直到子序列为空或只剩一个元素为止。这样的排序方法是（）A直接选择排序B直接插入排序C快速排序D起泡排序4、若采用邻接矩阵法存储一个N个顶点的无向图，则该邻接矩阵是一个（）A上三角矩阵B稀疏矩阵C对角矩阵D对称矩阵5、在一个顺序存储的循环队列中，队头指针指向队头元素的（）A前一个位置B后一个位置C队头元素位置D队尾元素的前一位置6、用链表表示线性表的优点是（）A便于随机存取B花费的存储空间比顺序表少C便于插入与删除D数据元素的物理顺序与逻辑顺序相同7、对5个不同的数据元素进行直接插入排序，最多需要进行（）次比较。A8B10C15D258、下列存储形式中，（）不是树的存储形式A双亲表示法B左子女右兄弟表示法C广义表表示法D顺序表示法9、在一棵具有5层的满二叉树中结点数为（）A31B32C33D1610、设有100个数据元素，采用折半搜索时，最大比较次数为（）A6B7C8D10二、判断题（每小题1分）（）1、算法的运行时间涉及加、减、乘、除、转移、存、取、等基本运算。要想准确地计算总运算时间是不可行的。（）2、二维数组是数组元素为一维数组的线性表，因此它是线性结构。（）3、顺序表用一维数组作为存储结构，因此顺序表是一维数组。（）4、通常使用两个类来协同表示单链表，即链表的结点类和链表类。（）5、栈和队列都是顺序存取的的线性表，但它们对存取位置的限制不同。（）6、在使用后缀表表示实现计算器时用到一个栈的实例，其作用是暂存运算对象。（）7、具有n个结点的完全二叉树的高度为┖log2n┘+1。（）8、为度量一个搜索算法的性能，需要在时间和空间方面进行权衡。（）9、闭散列法通常比开散列法时间效率更高。（）10、一棵m阶B树中每个结点最多有m个关键码，最少有2个关键码。三、阅读理解题（10分）voidunknown(BinTreeNode*T,inta[],inti){if(T!=NULL){a[i]=T-data;unknown(T-leftChild,a,2*I+1);unknown(T-rightChild,a,2*I+2);}}主程序调用方式unknown(BT.root,a,0);6-2//将完全二叉树所有结点从要开始，自顶向下，同一层自左向右连续编号，//根结点的编号为0。四、简答题（共35分）1、对下面的带权无向图采用prim算法从顶点①开始构造最小生成树。（写出加入生成树顶点集合S和选择Edge的顺序）（10分）①910②7③567④⑤⑥118S：顶点号Edge：（顶点，顶点，权值）①（，，）①（，，）①（，，）①（，，）①（，，）①2、某二叉树的结点数据采用顺序存储表示如下：012345678910111213141516171819EAFDHCGIB（1）试画出此二叉树的图形表示。（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，散列函数为H（k）=k%13，给定的关键码序列为19，14，23，01，68，20，84，27。试画出用线性探查法解决冲突时所构成的散列表。（8分）0123456789101112五、综合算法题（每题5分，共15分）对于二维整数数组A[m][n]，对下列三种情况，分别编写相应的函数。6-3（1）求数组所有边缘的和。（5分）intsuml(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]中，T[n]中存放的是各结点的值。下面的算法的功能是：从T[0]开始顺序读出各结点的值，建立该二叉树的二叉链表表示。此算法有5处缺失，请根据算法的功能补充之。（10分）#includeistream.htypedefstructnode{intdata;stuctnodeleftChild,rightchild;}BintreeNode;typedefBintreeNode*BinaryTree;voidConstrucTree(intT[],intn,intI,BintreeNode*&ptr);intmain(void){Binarytreet;intn;6-4Cout”pleaseenterthenumberofnode:\n”;cinn;Int*A=newint[n];For(intI=0;In;I++)①;从键盘输入结点值For(intI=0;In;I++)coutA[i];Coutendl;ConstructTree(A,n,0,t);②;//删除数组Areturn1;}voidConstrucTree(intT[],intn,intI,BintreeNode*&ptr){if(I=n)③;//置根指针为空elseptr=newBintreeNode;ptr-data=T[i];ConstrucTree(T,n,2*I+1,④);ConstrucTree(T,n,⑤,ptr-rightchild);}}缺失语句为：①②③④⑤6-5数据结构试题答案及评分标准一、单选题（每题2分，共20分）1.B2.B3.C4.D5.A6.C7.B8.D9.A10.B二、判断题（每题1分，共10分）1.√2.╳3.╳4.√5.√6.√7.╳8.√9.╳10.╳三、阅读理解题（说明下列递归过程的功能。10分）将用二叉链表表示的完全二叉树转换为二叉树的顺序（数组）表示。四、简答题1、（10分）每加对一个顶点和一条边得2分，全对得10分。①910②7③567④⑤⑥118S：顶点号Edge：（顶点，顶点，权值）①（1，2，9）①②（2，4，5）①②④（2，3，7）①②④③（3，5，6）①②④③⑤（3，6，7）①②④③⑤⑥①9②7③567④⑤⑥2、（1）二叉树的图形表示：（3分）AAAABAAACDEFGHI6-6（2）结点D的双亲结点为A，左子女结点为C，右子女为空。（3分）（3）对应森林为：（3分）3、各趟排序结果如下：（每一趟2分，共8分）10184361219158d1=510----------------1218----------------14----------------93----------------156----------------810143612189158d2=310----------------3----------------18----------------81----------------6----------------94----------------12----------------1531486121091518d3=23----------------4----------------6----------------10----------------151----------------8----------------12----------------9----------------1531486910121518d4=13------1------4-------8-----6------9-----10-----12-----15-----18134689101215184、计算各关键码得到的散列地址（8分）关键码1914230168208427散列地址611013761在散列表中散列结果01234567891011121401682719208423评分标准：每对一个元素得1分，全对8分。EAAAADCBAAAFHGI6-7五、综合算法题（每小题5分，共15分）（1）本小题是计算数组A的最外围的4条边的所有元素之和。可以先累加各个靠边的元素的值，再减去位于4个角上重复相加的元素的值。intsum1(intA[M][N],intm,intn){ints=0,i,j;for(i=0;im;i++){s+=A[i][0];s+=A[i][n-1];}for(j=0;jn;j++){s+=A[0][j];s+=A[m-1][j];}s=s-A[0][0]-A[0][n-1]-A[m-1][0]-A[m-1][n-1];returns;}评分标准5分，根据情况酌情给分。（2）本小题的互不相邻是指上、下、左、右、对角线均互不相邻，即求第0，2，4，…..，列的所有元素的值之和。intsum2(intA[M][N],intm,intn){ints=0,i,j;for(i=0,im,i+=2)for(j=0,jn,j+=2)s+=A[i][j];returns;}评分标准5分，根据情况酌情给分。（3）本小题中一条对角线是A[i][j]，i=0,1,…..n-1;另一条对角线是A[i][n-i-1]，i=0,1,…..n-1。可以用循环实现。intsum3(intA[M][N],intn){ints=0,i;for(i=0,in,i++){s+=A[i][j];s+=A[i][n-i-1];}returns;}评分标准5分，根据情况酌情给分。六、填空题（每空2分，10分）缺失语句：①cinA[i]②delete[A]③ptr=NULL④ptr-leftchild⑤2*i+2