《北京大学数据结构与算法2015》由会员分享，可在线阅读，更多相关《北京大学数据结构与算法2015（4页珍藏版）》请在金锄头文库上搜索。
1、2015年数据结构与算法 A期末考试试题姓名 学寻任课裁师考场题号一三四总分得分注意事项：1. 全部题目都在空白答题纸上解答。2. 本试卷对算法设计都有质量要求，请尽量按照试题中的要求来写算法。否则将酌情扣分。3. 请申明所写算法的基本思想，并在算法段加以恰当的注释。一、选择(9分)1. (2分)假设一个15阶的上三角矩阵A按行优先顺序压缩存储在一维数组B中，则非零 元素A9, 9在E中的存储位置k=_坐(注：矩阵元素下标从0开始)2. (4 分)设广义表 L=()，0),则 head(L)是_Q_, tail(L)是_()., L 的长度是深度 是_。3. (3分)已知基于某关键码集合A,
2、EC, D所构造的最佳二叉搜索树，用户访问该树中 内部关键码节点的频率分别为1，5, 4, 3,外部节点访问的频率为5, 4, 3, 2, 1,则 该最佳二叉搜索树对应的ASL值为_57_。二、辨析与简答(共2题，每题6分，共12分)1. (6分)广义表A= (a), (b), c, (a), (d, e)(1) (2分)画出其一种存贮结构图；(2) (2分)写出表的长度与深度；(3) (2分)用求头部，尾部的方式求出e答案：(1)不带头结点的情况head丨丨I b I I I彳 I c | | 门丨丨|4 1丨“1A0d0eA带头结点的话，则在子表与子表中元素之间加入头结点。(2)长度为5,
3、深度为42. （6分）对于给定的高度为h的AVL树而言，请分析其最少节点数和最多节点数。高度为h的AVL树，节点数N最多2 1（其严呼最少节点数11如以费伯纳西数列可以用数学归纳法证明:* h-=珂+2 - 1 (几+2 是 Fibonacci polynomial) o即：N（ = 0 （表示AVL Tree高度为0的节点总数）N【=1 （表示AVLTwe高度为1的节点总数）N2 = 2 （表示AVL Tree高度为2的节点总数）Nh-= N -1 + A_2 + 1 （表示AVLTree高度为h的节点总数）换句话说，当节点数为n时，高度h最多为（W+1） 一 2。三、算法填空（每空3分，共
4、12分）仁卜列代码利用Trie树，实现了字典树中单词的插入，试补全下列代码段。 tvpedef stmct TrieNode/Trie 结点声明bool isStr;stmct TrieNode *nextMAX; Tne;void insert(Trie *root,const char *s) if(root=NULL|*sr0f) return;inti;Trie *p=root;wliile(*s!=0*)if(p-iiext*s-,a,=NULL)标记该结点处是否构成单词儿子分支将单词s插入到字典树中如果不存在，则建立结点Trie *temp=(Trie *)nialloc(size
5、of(Tne); for(i=0; in 亡 xti=NULL;temp-isSti-false;p-next*s-,al=temp;p=p 二nexU*sJal;elsep=p 二mexFsJa;s卄；p isSU=tiue;四、算法设计与实现（6分）1、数列维护现在有一个数组，你需要实现以下操作：1. 插入：在数组的第k个位置的数字后插入指定的数字x2. 删除：删除数组第k个位置的数字3. 修改：将数组第k个位置的数字x修改为y4. 求和：计算数组位置kl到k2的子序列的和5. 求最大连续子序列：求出整个数组中最大连续子序列的和请设计出一个算法可以实现上述操作，并尽量优化你的算法。你只需要
6、描述算法的思想，以及 各个操作的实现思路，也可以用伪代码来表示。答案：利用伸展树实现。对于伸展树中每个节点需要维护一卞几个信息：这个点的左右孩子left,right，父亲paient,数值value这个点为根的子树的X小size,总和sum,最人子序列maxsum。子树左端所延伸的最人子序列 leftniax,和子树右端所延伸的最大子序列rightniax。1. 插入操作：把第k个位置上的数splay到根节点，将待插入数字插入到根的右子树的中（即 最左节点）。之后将插入节点splay到根节点。2. 删除操作：把数组的第k-1位置的数splay到根，此时第k个位置的数为根节点右子树的最 左节点。之后直接删除第k个位置的数即可。3. 修改操作：把数组第k个位置上的数splay到根节点，修改value值，维护相应的信息。4. 求和操作：首先把第kl-1个位置上的数splay到根节点，然后将R2+1的数splay到根节点的 右子树的根，和即为splay树的右子树的左子树的根的sum值。（其它调整方法也可以）5. 求最大连续子序列：最人子序列的和有以卞几种情况：1）左子树最大子序列和2）右子树最人子序列和3）左子树rightmax加上自己value4）右子树leftmax加上自己value5）左子树leftmax加右子树leftmax再加上自己value6）value 本身
