《数据结构试卷与答案》由会员分享,可在线阅读,更多相关《数据结构试卷与答案(13页珍藏版)》请在金锄头文库上搜索。
1、2005 级计算机专业数据结构试卷第 1 页 共 13 页1 算法与程序有何区别和联系?(6 分) 1.算法是对特定问题求解步骤的一种描述,可以用自然语言、流程图、伪代码、程序 代码来表示。程序是算法的具体实现,可以用不同的语言实现。 2 树的存储方法主要有哪些?任你画一个树举例说明具体存储结构。 (6 分) 2.(1)双亲表示法以一组连续空间存储树的结点,在每个结点中设一个指示器指示双 亲结点的位置。 (2)孩子表示法每个结点的孩子以单链表的形式存储,n 个结点有 n 个孩子链表,n 个 头指针又组成一个线性表,并以顺序存储结构存储。 (3)孩子兄弟表示法以二叉链表作为树的存储结构,链表中的
2、结点的两个指针分别指 向该结点的第一个孩子结点和下一个兄弟结点。 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, LISTElemT
3、ag;/表头表尾结构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 树与
4、 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)稳定基
5、数排序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 次成功
6、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 为
7、出发顶点,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,
8、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)
9、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
10、 页 共 13 页一、填空一、填空题题(每空(每空 2 分,共分,共 20 分)分)1当 时,快速排序算法的时间复杂性最差。2对于具有 300 个记录的文件,采用分块索引查找法查找,其中用二分查找法查找索引表,用顺序查找法查找块内元素,假定每块长度均为 30 个元素,则平均查找长度为 。3设某二叉树的前序和中序序列均为 ABCDE,则它的后序序列是 。4假设以一维数组作为 n 阶对称矩阵 A 的存储空间,以行序2/1nnS为主序存储 A 的下三角,则元素 A56的值存储在 S_中。5. 若一棵树中度为 1 的结点有 N1 个,度为 2 结点有 N2 个,度为 m的结点有 Nm 个,则该树的叶结
11、点有 个。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.求解图的最小生成树的算法有两个,分别是 。一、填
12、空题填空题 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,
13、56,8,5,18,15,试建立一棵平衡的二叉排序树,写出步骤。 (6 分)5 分别画出一个 B 树和 B+树的例子,并指出它们之间的区别。 (6 分)B 树与 B+树的区别:1.B 树:每个结点的关键字个数等于指针个数减 1。B+树:每个结点的关键字个数等于指针个数。 2.B+树中所有叶子结点包含了全部关键字信息,以及指向关键字记录的指针,叶子节点依关键字大小自小到大链接。非终端结点作索引,结点中含有其子树根结点的最大(最小)关键字。6. 举例说明栈和队列的应用。 (6 分)栈是一种后进先出的数据结构,可应用于递归操作、表达式求值、括号匹配等。队列是一种先进先出的数据结构,可应用于树的层次遍
14、历,操作系统中的作业排队,先来先服务三在数据结构课程中,你学习了哪些算法?请至少列举 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 稀疏矩阵的压缩存储方法是