《2022年数据结构模拟题 .pdf》由会员分享，可在线阅读，更多相关《2022年数据结构模拟题 .pdf（3页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、数据结构模拟题一、填空题（每空2 分，共 28 分）1线性表的顺序储存是通过位置间的关系来反映元素之间的逻辑关系，而链式储存结构是通过指针的链接反映元素之间的逻辑关系。2在一个长度为n 的顺序表中，删除第i 个元素(c i n-1)，需移动 n-i 个元素。3假定一棵二叉树的结点数为33，则它的最小高度为 6 ，最大高度为 33 。4.在一个单链表中，若p所指节点不是最后节点，在p 之后插入s 所指的节点，则执行 B 。A.a-link=p;p-link=s;B.s-link=p-link;p-link=s;C.a-link=p-link;p=s;D.p-link=s;s-link=p;5已知
2、一序列的关键码为6，45，15，5，30，100，45，75，8。用快速排序方法对此序列进行从小到大的排序，选择序列中间位置值30 为分区标准，第一趟排序的结果是；用 shell排序方法进行排序，取增量d=3，2，1 时，第一趟排序的结果是。6.用一维数组存放的一棵完全二叉树：ABDCEFHGI，写出中序遍历该二叉树时访问节点的顺序：GCTBEAFDH 。7.对关键码依次为8，32，46，49，52，68，70，75，88，90，92，95，100的有序顺序表，采用二分法检索，查找关键码为88 的记录时，经过 4 次关键码比较后查找成功；当查找关键码为55的记录时，经过 4 次关键码比较，可以
3、确认该记录不存在。8.线性表的链式储存结构主要有点链表、双链表、循环链表三种形式。二、辨析题（每题6 分，共 42 分）1 数据结构与抽象数据类型的关系是什么?2 对于表达式(a+b)*(c+d)*(e+f)，画出相应的二叉树表示；给出它的前缀表达式；给出它的后缀表达式。3 设由关键码分别为10，20，30 的三个结点，按照不同的输入顺序，画出所有可能的二叉排序树。4 算法和数据结构与问题求解的关系是什么？5 试为下列各种情况选择合适的排序方法(1)n=1000，且要求最坏情况下速度最快，可采用归并排序(2)n=30，且要求既要快，又要排序稳定(3)n=1000，要求既要快，又要最节省储存空间
4、，可采用堆排序名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页，共 3 页 -6 简单比较线性表的顺序和链接两种储存方式各有什么主要优缺点？7 设有有向图为G=(V,E)，其中 V=v0,v1,v2,v3,E=,请画出该有向图，并图示其邻接矩阵表示和邻接表表示。三、算法填空题（每空2 分，共 14 分）1阅读下面的算法，填充空格，使其成为完整的算法。该算法的功能是从一个顺序存储在线性表的不减序列中，删除值相等的多余元素。（注：若序列k1.k2.,kn,满足该序列为不减序列。）define MAX 30;struct SlistTable int*elem;/储存元素的数组int siz
5、e;/数组的大小;void deleteDuplicate(SlistTable list)int i=1;int j=0;while(1)if(list.elemi!=list.elemj)(2)(3)i+;(4)2对以下函数填空，实现用直接选择排序方法对n 个整数进行从小到大排序。Void zjxzpx(int r,int n)int i,j,k,x;For(i=1;in;i+)K=i;For(j=(5);j=n;j+)名师资料总结-精品资料欢迎下载-名师精心整理-第 2 页，共 3 页 -If(rjrk)(6);If(7)X=ri;ri=rk;rk=x;四、算法设计题（共16 分）1.设二叉树结点表示的数据元素类型为T，二叉树以链接表示。一棵二叉树的最大枝长就是二叉树层数；最小枝长就是离根结点距离最近的叶结点距离根路径上的边数。请从以下方面设计一个算法，同时求出一棵二叉树的最大和最小枝长。（1）(4 分)请给出顺序表示法表示的二叉树结点BinaryTreeNode的定义。（2）(4 分)请概要说明此算法思想；（3）(6 分)编写算法；（4）(2 分)请在算法关键的地方给出必要的注释。名师资料总结-精品资料欢迎下载-名师精心整理-第 3 页，共 3 页 -