资源预览内容
第1页 / 共12页
第2页 / 共12页
第3页 / 共12页
第4页 / 共12页
第5页 / 共12页
第6页 / 共12页
第7页 / 共12页
第8页 / 共12页
第9页 / 共12页
第10页 / 共12页
亲,该文档总共12页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
第 1 页 共 12 页 考试科目名称 数据结构数据结构 (A1 卷) 1、填空题。、填空题。 (每小题 2 分,本题满分 20 分) (1) C+语言中,数组是按行优先顺序存储的,假设定义了一个二维数组 A2030,每个元 素占两个字节,其起始地址为 2140,则二维数组 A 的最后一个数据元素的地址为 2140+2*(30*20-1) = 3338(3338,3339) 。 (2) 若 A,B 是两个单链表,链表长度分别为 n 和 m,其元素值递增有序,将 A 和 B 归并成一个按元素值递增有序的单链表,并要求辅助空间为 O(1),则实现该功能的算法的时间复杂度为 O(m+n) 。 (3) 快速排序的平均时间复杂度是_n*lg n_。 (4) 假设有一个包含 9 个元素的最小堆,存放在数组 A 中,则一定比 A3大的元素有_ _2 (A7,A8) _个; 一定比 A3小的元素有_2 (A0,A1)_个。 (元素从第 0 个位置开始存放) (5) 广义表(A),(B,C), D, (A), (E,F) 的长度是 4 ,深度是 4 。 (6) 有 10 个元素的有序表, 采用折半查找, 需要比较 4 次才可找到的元素个数为_3_。 (7)当两个栈共享一存储区时,栈利用一维数组 An表示,两栈顶指针为 top0与 top1,则栈满时的判断条件为_top0+1=top1_ 或者 top0 = top1+1 _。 (8) 假设计算斐波那契数的函数 Fib(long n)定义如下: long Fib(long n) if(nrightchild-rightchild_。假设二叉树的结点结构为: 2、选择题。、选择题。 (每小题 2 分,本题满分 20 分) (1) 如果能够在只知道指针 p 指向链表中任一结点, 不知道头指针的情况下,将结点*p 从链表中删除,则这个链表结构应该是: ( B,C )(多选题) A. 单链表 B. 循环链表 C. 双向链表 D. 带头结点的单链表 (2) 以下哪种矩阵压缩存储后会失去随机存取的功能?( A ) A. 稀疏矩阵 B. 对称矩阵 C. 对角矩阵 D. 上三角矩阵 (3) 下面哪一方法可以判断出一个有向图是否有环(回路) :( B ) (选 A,B 也对) A. 广度优先遍历 B. 拓扑排序 C. 求最短路径 D.求关键路径 (4) n 个结点的线索二叉树(没有头结点)上含有的线索数为( B ) 得分 得分 leftchild data rightchild 第 2 页 共 12 页 A. 2n B. nl C. nl D. n (5) 循环队列存储在数组 A0.m中,则入队时队尾指针 rear 的操作为( D ) A. rear=rear+1 B. rear=(rear+1) mod (m-1) C. rear=(rear+1) mod m D. rear=(rear+1)mod(m+1) (6) 使用加权规则得到改进的 Union 操作 WeightedUnion,其目的是: ( B ) A. 提高 Union 操作的时间性能 B. 提高 Find 操作的时间性能 C. 减少 Union 操作的空间存储 D. 减少 Find 操作的空间存储 (7) 使用 Kruscal 算法求解最小生成树时,为了设计效率较高的算法, 数据结构方面可以选择: ( A ) A. 利用最小堆存储边 B. 利用栈存储结点 C. 利用二维数组存储结点 D. 利用并查集存储边 (8) 已知一算术表达式的后缀形式为 ABC*+DE/-,其前缀形式为:( D ) A. -A+B*C/DE B. -A+B*CD/E C. -+*ABC/DE D. -+A*BC/DE (9) n 个关键码排序,如果选用直接插入排序方法,则元素的移动次数在最坏情况下可以达到( B )。 A. n*n/2 B. n*(n-1)/2 C. n/2 D. (n-1)/2 (10) 关键路径是 AOE 网络中 A C 。 (多选) A. 从源点到汇点的最长路径 B. 从源点到汇点的最短路径 C. 所有活动都是关键活动的路径 D. 最短回路 、简答题简答题。 (每小题 5 分,本题满分 20 分) (1) 对如下无向图,按照 Dijkstra 算法,写出从顶点 1 到其它各个顶点的最短路径和最短 路径长度。 1 3 5 2 4 6 结点编号 1 2 3 4 5 6 路径长度 0 11 7 12 14 15 最短路径 1 1-2 1-3 1-3-4 1-3-5 1-3-6 (2)请画出在如下图所示的 5 阶 B 树中插入一个关键码 360 后得到的 B 树。 100 200 300 400 20 40 150 180 240 260 310 320 350 370 420 430 得分 7 10 5 8 6 9 11 7 第 3 页 共 12 页 300 100 200 350 400 20 40 150 180 240 260 310 320 360 370 420 430 (3) 假设有权值集合16,40,15,4,25,给出相应的 huffman 树。假设某类信息由符号 a,b,c,d,e,组成, 而上面的权值分别是符号 a,b,c,d,e 的出现频率。 请给出各个符号的 Huffman 编码。 Huffman 编码: a: 001 b: 1 c: 0001 d: 0000 e: 01 注意:因为左右子树不同, 所以编码可以有多种,但是只要 其长度分别是 3,1,4,4,2;且 相互之间不形成前缀关系就 是正确的。 (4)在 AVL 树的插入操作中,假设插入一个结点后,当前节点 p 的平衡因子是-2,其左子结点的平衡因子是+1,左子结点的右子结点的平衡因子是-1。如图所示,请给出旋转调整之后的结构。 4 15 19 16 35 25 60 40 100 A B C t1 t2 t3 t4 -2 +1 -1 p A C B t1 t2 t3 t4 0 +1 -1 第 4 页 共 12 页 4、已知输入关键码序列为(10,90,20,60,78,35,42,31,15) ,地址区间为 011。 (1) 请设计一个散列函数,把上述关键码散到 011 中。画出散列表,冲突用线性探测法解 决。 (5 分) 散列函数为: f(x) = x % 12 允许其它的散列函数 0 1 2 3 4 5 6 7 8 9 10 11 60/1 31/7 15/1 90/1 78/2 20/1 42/4 10/1 35/1 (2) 搜索元素 31 需要比较的次数是多少?(2 分) 7 (78-9-10-11-0-1 (成功) ) (3) 计算在等概率情况下查找成功的平均查找长度 ASLsucc。 (3 分) (1+7+1+1+2+1+4+1+1) / 9 = 19/9 5、 程序设计题。程序设计题。 (每小题 15 分,本题满分 30 分) 1. 设计一个算法,根据一棵二叉树的前序序列和中序序列,构造出这棵二叉树。 二叉树的结点都用字符表示。前序序列和中序序列都是字符串。二叉树的结点定义如下: struct binTreeNode char data; binTreeNode *leftChild, *rightChild; 解:解: TreeNode * tree(char *preorder, *midorder) return TreeRecursive(preorder, 0, strlen(preorder)-1, midorder, 0, strlen(midorder)-1); TreeNode * TreeREcursive(char *pre, int preSt, int preEnd, char* mid, int midSt, int midEnd) if (preEnd midEnd)coutdata = rt; int lLen = j - midSt; root-leftChild = treeRecursive(pre, preSt+1, preSt+lLen - 1, 得分 得分 第 5 页 共 12 页 mid, midSt,midSt+lLen-1); root-rightChild=treeRecursive(pre, preSt+lLen+1, preEnd, mid, midSt+lLen+1, midEnd); return root; 要点在于根据 preOrder 的第一个字符,在 midOrder 中找到左右子树的分界;然后递归调用生成左右子树;做到这一点,就可以给出大部分分数。 可能有很多细节上不一样的地方,比如这里的 preEnd 指向的字符在相应的树中;但是有些人可能是 preEnd 指向下一个位置。或者传递参数时直接使用字符串传递。都是可以的。 如果使用别的办法,参考其效率,酌情给分。只要效率过得去,也可以得满分。但是纯粹枚举则得分不高。 2. 设计非递归算法实现图的深度优先遍历。 (图用邻接表表示,已经定义了一个顺序栈stacktop,top 为栈顶指针,使用 visit(node)来表示对顶点 node 的访问。 ) 图的邻接表结构定义如下: struct Edge int dest; Edge *link; /下一条边链指针 struct Vertex int data; Edge *adj; /边链表的头指针 class Graph private: Vertex *Nodetable; /顶点表 int cnt 解:解: Graph : : DFS(int v)/从 v 开始搜索; bool visitedMAXVert; Edge nextEdgeMAXVert; stack0 = v; nextEdge0 = graph.Nodetablev.adj; top = 0; visited(stacktop); 第 6 页 共 12 页 visitedstacktop = true; while(top = 0) while(nextEdgetop if(nextEdgetop != NULL) int nextVert = nextEdgetop-dest; visite(nextVert); /访问下一个邻接结点;保证了被压入栈中的顶点都被访问; visitednextVert = true; stacktop+1 = nextVert; /压栈,进入下一个结点; nextEdgetop+1 = Nodetabl
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号