2005 级计算机专业数据结构试卷第 1 页 共 13 页1 算法与程序有何区别和联系？（6 分） 1.算法是对特定问题求解步骤的一种描述，可以用自然语言、流程图、伪代码、程序 代码来表示。程序是算法的具体实现，可以用不同的语言实现。 2 树的存储方法主要有哪些？任你画一个树举例说明具体存储结构。 （6 分） 2.(1)双亲表示法以一组连续空间存储树的结点，在每个结点中设一个指示器指示双 亲结点的位置。 (2)孩子表示法每个结点的孩子以单链表的形式存储，n 个结点有 n 个孩子链表，n 个 头指针又组成一个线性表，并以顺序存储结构存储。 (3)孩子兄弟表示法以二叉链表作为树的存储结构，链表中的结点的两个指针分别指 向该结点的第一个孩子结点和下一个兄弟结点。 3 设有序表的长度为 10，用二分查找方法进行查找，试计算查找成功情况下 的平均查找长度（6 分） ASL = 1/10 *(1+2*2+4*3+3*4) = 2.9 4 图的遍历方法主要有哪些？任你画一个图举例具体说明。 （6 分） 深度优先搜索，宽度优先搜索。例如： 深度优先搜索遍历：ABXFYDEC 宽度优先搜索遍历：ABCDXEYF5 画出广义表 D=( )，x，(a，(b，c)的存储结构，并写出广义表类型定义。#define ATOM 0#define LIST 1typedef enumATOM, LISTElemTag;/表头表尾结构struct GLNodeElemTag tag; /区分原子结点表结点unionint atom;structstruct GLNode *hp;struct GLNode *tp;ptr;/后继结点结构struct GLNodeElemTag tag;unionint atom; /原子结点的值域struct GLNode *hp; /表结点的头指针;struct GLNode *tp; /下一个元素结点;采用后继结点的存储结构6. 分别画出一个 B 树和 B+树的例子，并指出它们之间的区别。 （6 分）2005 级计算机专业数据结构试卷第 2 页 共 13 页B 树与 B+树的区别：1) B 树：每个结点的关键字个数等于指针个数减 1。B+树：每个结点的关键字个数等于指针个数。2) B+树中所有叶子结点包含了全部关键字信息，以及指向关键字记录的指针，叶子节点依关键字大小自小到大链接。非终端结点作索引，结点中含有其子树根结点的最大（最小）关键字。7. 你知道有哪些排序算法？试比较各种排序算法的性能。 （8 分）排序算法 时间复杂度空间复杂度稳定性直接插入 排序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设一组关键字为（7，15，20，31，48，53，64，76，82，99） ，Hash 函数H（key）= key % 11，Hash 表表长 m=11，用线性探测法解决冲突，试构造Hash 表，并分别计算查找成功和查找失败情况下的平均查找长度。 （8 分）7%11=7 查找 1 次成功 15%11=4 查找 1 次成功20%11=9 查找 1 次成功31%11=9 9+1=10 查找 2 次成功48%11=4 4+1 =5 查找 2 次成功53%11=9 9+1+1-11=0 查找 3 次成功64%11=9 9+1+1+1-11=1 查找 4 次成功76%11=10 10+1+1+1-11=2 查找 4 次成功82%11=5 5+1=6 查找 2 次成功99%11=0 0+1+1+1=3 查找 4 次成功查找成功时的平均查找长度：(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)到某个定点的最短路径找到后，考察它对其余顶点当前最短路径的影响。算法步骤：1）设 arcs 存储带权有向图的边的权值，v 为出发顶点，S 为已找到的从 v 出发的最短路径的终点集合，开始为空。从 v 出发到图中其余顶点 vi 最短路径长度初始值为 Di2005 级计算机专业数据结构试卷第 3 页 共 13 页=arcsoi o, i 为 v, vi 的位置2）选择 vj，使得 Dj=MinDi| viV-S vj 是从 v 出发的最短路径的终点。S=Sj3）修改从 v 出发到集合 V-S 任一顶点 vk 可达的最短路径长度。如果 Dj+arcsjk/将有序的 SRi.m和 SRm+1.n归并为有序的 TRi.nvoid Merge(int SR, int TR, int i, int m, int n)int j,k;j = m+1;k = i;while(idata = l.elem0;root-lchild=root-rchild=NULL; /二叉排序树的根节点for(i=1; idata) q = p;p = p-lchild;else if(l.elemip-data)q = p;p = p-rchild;else/该值已在排序树中出现，不再插入break;if(p = NULL)r = (BiTNode*) malloc(sizeof(BiTNode);r-data = l.elemi;r-lchild = NULL;r-rchild = NULL;/生成新结点if(l.elemidata)q-lchild = r;elseq-rchild = r; /新结点作 q 的叶子结点五、设单链表 L 中的结点按 data 域数值递减排列，试设计一个算法将 L 中的 结点按 data 域数值递增加排列，要求算法的时间复杂性为 O（n）。（12 分）typedef struct LNodeint data;struct LNode *next; LNode;void TraverseList(LNode *LNode *p = l, *q;while(p)q = p;p =p-next;q-next = head;head = q;l = head;2005 级计算机专业数据结构试卷第 5 页 共 13 页一、填空一、填空题题（每空（每空 2 分，共分，共 20 分）分）1当 时，快速排序算法的时间复杂性最差。2对于具有 300 个记录的文件，采用分块索引查找法查找，其中用二分查找法查找索引表，用顺序查找法查找块内元素，假定每块长度均为 30 个元素，则平均查找长度为 。3设某二叉树的前序和中序序列均为 ABCDE，则它的后序序列是 。4假设以一维数组作为 n 阶对称矩阵 A 的存储空间，以行序2/1nnS为主序存储 A 的下三角，则元素 A56的值存储在 S_中。5. 若一棵树中度为 1 的结点有 N1 个，度为 2 结点有 N2 个，度为 m的结点有 Nm 个，则该树的叶结点有 个。6.设循环队列的元素存放在一维数组 Q0.30中,front 指向队头元素的前一个位置,rear 指向队尾元素。若 front=25, rear=5,则该队列中的元素个数为 。7图的遍历方法主要是 。8设源串 S=“bcdcdcb” ，模式串 P=“cdcb” ，按 KMP 算法进行模式匹配，当“S2S3S4”=“P1P2P3” ，而 S5P4时，S5应与 比较。9. 设序列12，34，19，23，8，56，试建立表长为 7 的 Hash 表。Hash函数为 H（key）=key % 7，用线性探测法解决冲突，则 56 冲突 次。10.求解图的最小生成树的算法有两个，分别是 。一、填空题填空题 1.待排数据本身已排好序 2.18.4 3.EDCBA 4.26 5.N2+2N3+(m-1)Nm 6.11 7.宽度优先搜索 深度优先搜索 8.P2 9.3 2005 级计算机专业数据结构试卷第 6 页 共 13 页10. Prim 算法和 Kruskal 算法二、根据要求解答下列二、根据要求解答下列问题问题。 。 （共（共 34 分）分）1画出广义表 D=( )，x，(a，(b，c)的存储结构。 （5 分） 2根据图的邻接表画邻接矩阵。 （5 分）3请给出堆排序不稳定的例子。 （6 分）堆排序不稳定1 2 2 4 排序后结果为 1 2 2 44设输入下列关键字序列：12，34，56，8，5，18，15，试建立一棵平衡的二叉排序树，写出步骤。 （6 分）5 分别画出一个 B 树和 B+树的例子，并指出它们之间的区别。 （6 分）B 树与 B+树的区别：1.B 树：每个结点的关键字个数等于指针个数减 1。B+树：每个结点的关键字个数等于指针个数。 2.B+树中所有叶子结点包含了全部关键字信息，以及指向关键字记录的指针，叶子节点依关键字大小自小到大链接。非终端结点作索引，结点中含有其子树根结点的最大（最小）关键字。6. 举例说明栈和队列的应用。 （6 分）栈是一种后进先出的数据结构，可应用于递归操作、表达式求值、括号匹配等。队列是一种先进先出的数据结构，可应用于树的层次遍历，操作系统中的作业排队，先来先服务三在数据结构课程中，你学习了哪些算法？请至少列举 20 个算法名称。有序线性表的合并、KMP 算法、顺序查找、二分查找、Hash 查找、建立二叉排序树的算法、冒泡排序、选择排序、插入排序、堆排序、快速排序、归并排序、基数排序、Prim 算法、2005 级计算机专业数据结构试卷第 7 页 共 13 页Kruskal 算法、图的深度优先搜索算法、图的广度优先搜索算法、Dijkstra 算法、拓扑排序算法、Huffman 算法、二叉树的先序遍历算法、中序线索二叉树算法。四、试编写对顺序表 L 进行归并排序的算法。 （12 分）#include #include /线性表结点typedef struct SqListint* elem;int length;int listsize; SqList;/将有序的 SRi.m和 SRm+1.n归并为有序的 TRi.nvoid Merge(int SR, int TR, int i, int m, int n)int j,k;j = m+1;k = i;while(ileft);hr = GetHeight(t-right);t-bal = hl-hr;if(hl0，且有如下程序段：int i; i = n;while (i0) i=i/10;则该程序的时间复杂性为_。3 稀疏矩阵的压缩存储方法是