数据结构模拟试卷

1、数据结构模拟试卷（6）一、填空题1当 待排数据本身已排好序 时，快速排序算法的时间复杂性最差。2对于具有300个记录的文件，采用分块索引查找法查找，其中用二分查找法查找索引表，用顺序查找法查找块内元素，假定每块长度均为30个元素，则平均查找长度为 18.4 。 3设某二叉树的前序和中序序列均为ABCDE，则它的后序序列是 EDCBA 。4假设以一维数组作为n阶对称矩阵A的存储空间，以行序为主序存储A的下三角，则元素A56的值存储在S_26_中。5. 若一棵树中度为1的结点有N1个，度为2结点有N2个，度为m的结点有Nm个，则该树的叶结点有 N2+2N3+(m-1)Nm 个。6.设循环队列的元素

2、存放在一维数组Q0.30中,front指向队头元素的前一个位置,rear指向队尾元素。若front=25, rear=5,则该队列中的元素个数为 11 。 7图的遍历方法主要是 宽度优先搜索 深度优先搜索 。8设源串S=“bcdcdcb”，模式串P=“cdcb”，按KMP算法进行模式匹配，当“S2S3S4”=“P1P2P3”，而S5P4时，S5应与 P2 比较。9. 设序列12，34，19，23，8，56，试建立表长为7的Hash表。Hash函数为H（key）=key % 7，用线性探测法解决冲突，则56冲突 3 次。1. 10.求解图的最小生成树的算法有两个，分别是 Prim算法和Krusk

3、al算法 。二、根据要求解答下列问题。 1画出广义表D=( )，x，(a，(b，c)的存储结构。2根据图的邻接表画邻接矩阵。3请给出堆排序不稳定的例子。4设输入下列关键字序列：12，34，56，8，5，18，15，试建立一棵平衡的二叉排序树，写出步骤。5 分别画出一个B树和B+树的例子，并指出它们之间的区别。6. 举例说明栈和队列的应用。栈是一种后进先出的数据结构，可应用于递归操作、表达式求值、括号匹配等。队列是一种先进先出的数据结构，可应用于树的层次遍历，操作系统中的作业排队，先来先服务三在数据结构课程中，你学习了哪些算法？请至少列举20个算法名称。有序线性表的合并、KMP算法、顺序查找、二

4、分查找、Hash查找、建立二叉排序树的算法、冒泡排序、选择排序、插入排序、堆排序、快速排序、归并排序、基数排序、Prim算法、Kruskal算法、图的深度优先搜索算法、图的广度优先搜索算法、Dijkstra算法、拓扑排序算法、Huffman算法、二叉树的先序遍历算法、中序线索二叉树算法四、试编写对顺序表L进行归并排序的算法。#include #include /线性表结点typedef struct SqListint* elem;int length;int listsize; SqList;/将有序的SRi.m和SRm+1.n归并为有序的TRi.nvoid Merge(int SR, in

5、t TR, int i, int m, int n)int j,k;j = m+1;k = i;while(i=m & j=n)if(SRi=SRj)TRk+ = SRi+;elseTRk+ = SRj+;while(i=m)TRk+ = SRi+;while(j=n)TRk+ = SRj+;/将SRs.t归并排序为TR1s.tvoid MSort(int SR, int TR1, int s, int t)int m;int TR210;if(s = t)TR1s = SRs;elsem = (s+t)/2; /SRs.t平分为SRs.m和SRm+1.tMSort(SR,TR2,s,m);

6、/递归地将SRs.m归并为有序的TR2s.mMSort(SR,TR2,m+1,t); /递归地将SRm+1.t归并为有序的TR2m+1.tMerge(TR2,TR1,s,m,t); /将TR2s.m和TR2m+1.t归并到TR1s.t/主程序，供测试用void main()SqList l;int i;l.listsize = l.length = 10;l.elem = (int*)malloc(sizeof(int)*l.listsize);for(i=0; il.length; i+)scanf(%d,&l.elemi);MSort(l.elem,l.elem,0, l.length-1

7、);/for(i=0; ileft);hr = GetHeight(t-right);t-bal = hl-hr;if(hlhr)return hr+1;elsereturn hl+1;六、设采用邻接表作为有向图的存储结构，试编写算法：计算有向图中每个顶点的出度和入度。typedef struct ArcNodeint adjvex;struct ArcNode *nextarc;ArcNode;typedef struct VNode int data;int in;int out;ArcNode *firstarc; VNode;typedef struct VNode verticesNUM;int vexnum;int arcnum;AlG