数据结构模拟试卷(5)

《数据结构模拟试卷(5)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、数据结构模拟试卷（5）一、简要回答下列问题1．算法与程序有何区别和联系？算法是对特定问题求解步骤的一种描述，可以用自然语言、流程图、伪代码、程序代码来表示。程序是算法的具体实现，可以用不同的语言实现。2．树的存储方法主要有哪些？任你画一个树举例说明具体存储结构。(1)双亲表示法——以一组连续空间存储树的结点，在每个结点中设一个指示器指示双亲结点的位置。(2)孩子表示法——每个结点的孩子以单链表的形式存储，n个结点有n个孩子链表，n个头指针又组成一个线性表，并以顺序存储结构存储。(3)孩子兄弟表示法——以二叉链表作为树的存储结构，链表中的结点的两个指针分别指向该结点的第

2、一个孩子结点和下一个兄弟结点。双亲表示法：       孩子表示法：     孩子兄弟表示法：3．设有序表的长度为10，用二分查找方法进行查找，试计算查找成功情况下的平均查找长度1．图的遍历方法主要有哪些？任你画一个图举例具体说明。深度优先搜索，宽度优先搜索。例如：深度优先搜索遍历：ABXFYDEC宽度优先搜索遍历：ABCDXEYF2．画出广义表D=(()，x，(a，(b，c)))的存储结构，并写出广义表类型定义#defineATOM0#defineLIST1typedefenum{ATOM,  LIST}ElemTag;//表头表尾结构structGLNode{El

3、emTagtag;   //区分原子结点表结点union{intatom;struct{structGLNode*hp;structGLNode*tp;}ptr;};};//后继结点结构structGLNode{ElemTagtag;union{intatom;          //原子结点的值域structGLNode*hp; //表结点的头指针};structGLNode*tp;  //下一个元素结点}采用后继结点的存储结构6.分别画出一个B树和B+树的例子，并指出它们之间的区别。B树：B+树：B树与B+树的区别：1) B树：每个结点的关键字个数等于指针个数减1

4、。B+树：每个结点的关键字个数等于指针个数。2) B+树中所有叶子结点包含了全部关键字信息，以及指向关键字记录的指针，叶子节点依关键字大小自小到大链接。非终端结点作索引，结点中含有其子树根结点的最大（最小）关键字。7.你知道有哪些排序算法？试比较各种排序算法的性能。排序算法时间复杂度空间复杂度稳定性直接插入排序O(n2)O(1)稳定冒泡排序O(n2)O(1)稳定快速排序O(nlogn)O(logn)不稳定选择排序O(n2)O(1)不稳定堆排序O(nlogn)O(1)不稳定归并排序O(nlogn)O(n)稳定基数排序O(d(n+rd))O(rd)不稳定8．设一组关键字为

5、（7，15，20，31，48，53，64，76，82，99），Hash函数H（key）=key%11，Hash表表长m=11，用线性探测法解决冲突，试构造Hash表，并分别计算查找成功和查找失败情况下的平均查找长度。查找成功时的平均查找长度：(1+1+1+2+2+3+4+4+2+4)/10=2.4查找失败的平均查找长度：（1+2+3+4+5+6+7+8+9+10+11）/11=6二、简述利用Dijkstra算法求解从某顶点到其余各顶点最短路径的步骤。Dijkstra算法思想：(1)求解顺序：按最短路径递增的顺序求解。(2)到某个定点的最短路径找到后，考察它对其余顶点当

6、前最短路径的影响。算法步骤：1）设arcs存储带权有向图的边的权值，v为出发顶点，S为已找到的从v出发的最短路径的终点集合，开始为空。从v出发到图中其余顶点vi最短路径长度初始值为D[i]=arcs[o][i]o,i为v,vi的位置2）选择vj，使得D[j]=Min{D[i]

7、vi∈V-S}vj是从v出发的最短路径的终点。S=S∪{j}3）修改从v出发到集合V-S任一顶点vk可达的最短路径长度。如果D[j]+arcs[j][k]

8、nclude//将有序的SR[i...m]和SR[m+1...n]归并为有序的TR[i...n]voidMerge(intSR[],intTR[],inti,intm,intn){intj,k;j=m+1;k=i;while(i<=m&&j<=n)if(SR[i]<=SR[j])TR[k++]=SR[i++];elseTR[k++]=SR[j++];while(i<=m)TR[k++]=SR[i++];while(j<=n)TR[k++]=SR[j++];}//将SR[s...t]归并排序为TR1[s...t]voidMSort(i