数据结构与算法期末考试.pdf

北北 京京 交交 通通 大大 学学 考考 试试 试试 题题 （A 卷）卷） 课程名称:数据结构与算法 2011-2012 学年第一学期 出题教师:张勇 (请考生注意:（1）本试卷共有六道大题，（2）答案一律写在答题纸上，（3）试卷不 得带出考场) 题号题号 一一 二二 三三 四四 五五 六六 总分总分 得分得分 阅卷人阅卷人 一、一、 填空题（每空填空题（每空 2 分，共分，共 20 分）分） 1. 在顺序表中访问任意一个元素的时间复杂度均为 ，因此顺序表也称为 的数据结构。 2三维数组 a432(下标从 0 开始)，假设 a000的地址为 50，数据以行序优先方 式存储，每个元素的长度为 2 字节，则 a211的地址是 。 3. 直接插入排序用监视哨的作用是 。 4. 已知广义表 Ls=(a, (b, c), (d, e), 运用 head 和 tail 函数取出 Ls 中的原子 d 的运算 是 。 5对有 14 个元素的有序表 A1.14进行折半查找，当比较到 A4时算法结束。被比较 元素除 A4外，还有 。 6. 在 AOV 网中，顶点表示 ，边表示 。 7. 有向图 G 可进行拓扑排序的判别条件是 。 8. 若串 S1=ABCDEFGHIJK,S2=451223,S3=#,则执行 Substring(S1,Strlength(S3),Index(S2,12,1)的结果是 。 二、二、 选择题选择题（每空（每空 2 分，共分，共 20 分）分） 1. 在下列存储形式中，哪一个不是树的存储形式？（ ） A双亲表示法 B孩子链表表示法 C孩子兄弟表示法 D顺序存储表示法 2. 查找 n 个元素的有序表时，最有效的查找方法是（ ）。 A顺序查找 B分块查找 C折半查找 D二叉查找 3. 将所示的 s 所指结点加到 p 所指结点之后，其语句应为（ ）。 p s (A) s-next=p+1 ; p-next=s; (B) (*p).next=s; (*s).next=(*p).next; (C) s-next=p-next ; p-next=s-next; (D) s-next=p-next ; p-next=s; 4. 在有向图的邻接表存储结构中，顶点 v 在链表中出现的次数是（ ）。 A. 顶点 v 的度 B. 顶点 v 的出度 C. 顶点 v 的入度 D. 依附于顶点 v 的边数 5. 算法的时间复杂度为 O（nlog2n）、空间复杂度为 O(1)的排序算法是（ ）。 A. 堆排序 B. 快速排序 C. 归并排序 D.直接选择 6. 设矩阵 A 是一个对称矩阵，为了节省存储，将其 下三角部分（如右图所示）按行序存放在一维数 组 B 1, n(n-1)/2 中，对下三角部分中任一元素 ai,j(ij), 在一维数组 B 中下标 k 的值是（ ）： i(i-1)/2+j-1 i(i-1)/2+j i(i+1)/2+j-1 i(i+1)/2+j 7. 由一个长度为 11 的有序表，按二分查找法对该表进行查找，在表内各元素等概率情 况下，查找成功的平均查找长度是（ ）。 A29/11 B. 31/11 C. 33/11 D.35/11 8. AVL 树是一种平衡的二叉排序树，树中任一结点的（ ）。 A. 左、右子树的高度均相同 B. 左、右子树高度差的绝对值不超过 1 C. 左子树的高度均大于右子树的高度 D. 左子树的高度均小于右子树的高度 9. 下列四种排序方法中，不稳定的方法是（ ）。 A. 直接插入排序 B. 冒泡排序 C. 归并排序 D. 堆排序 10. 设树的度为 4，其中度为 1,2,3,4 的结点个数分别为 4, 2, ,1, 1, 则 T 中的叶子数为 （ ）。 A5 B6 C7 D8 三、三、 判断题判断题（10 分，每小题分，每小题 1 分）分） 1. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。（ ） nnnn aaa aa a A ,2,1 , 2,21 , 2 1 , 1 2. 数组不适合作任何二叉树的存储结构。（ ） 3. 广义表的取表尾运算，其结果通常是个表，但有时也可是个原子。（ ） 4. 在含有 n 个结点的树中，边数只能是 n-1 条。（ ） 5. 所谓一个排序算法是否稳定，是指该算法在各种情况下的效率是否相差不大。 （ ） 6. 简单选择排序在最好情况下的时间复杂度为 O(n)。（ ） 7. 在二叉排序树中插入一个新结点，总是插入到叶结点下面。（ ） 8. 采用线性探测处理冲突，当从哈希表中删除一个记录时，不应将该记录所在位置置 空，因为这会影响以后的查找。（ ） 9. 有 n 个数存放在一维数组 A1.n中，在进行顺序查找时，这 n 个数的排列有序或无 序，其平均查找长度不同。（ ） 10. 广义表中原子个数即为广义表的长度。( ) 四、四、 应用题（应用题（24 分）分） 1. （6 分）将下列由三棵树组成的森林转换为二叉树。 B A D E F C H G J K I L 2(6 分)给定下列图，完成以下问题 （1）画出该图的邻接矩阵和邻接表 （2）根据所画的邻接表，从顶点 B 出发，画出图的深度优先搜索树 （3）根据普里姆（Prim）算法，求它的最小生成树（不必写出全部过程，在生成树中 标出边生成的次序即可） 1 3 3 1 2 6 5 4 C B A D E F 5 G 3（6 分）输入一个正整数序列（53,17,12,66,58,70,87,25,56,60），试完成下列各题： （1）构造一棵二叉排序树，计算查找成功的平均查找长度； （2）依此二叉排序树，如何得到一个从大到小的有序序列； （3）画出在此二叉排序树中，删除“66”后的树结构. 4. （6 分）将序列25, 34, 12, 7, 15, 47, 65, 79，47+，16 中的关键字按升序重新 排列，请写出 （1）冒泡排序一趟扫描的结果 （2）以第一个元素为分界点的快速排序一趟扫描的结果 （3）堆排序所建的初始堆和第一趟排序结果。 五、五、 程序填空题（程序填空题（10 分，每空分，每空 1 分）分） 1. 下列算法是建立单链表的算法，请填写适当的语句，完成该功能。 typedef struct Lnode ElemType data; struct Lnode *next; LNode, *LinkList; Status CreatList_L(LinkList if(!L) return ERROR; L-next=NULL; p= ( 1 ) ; for(i=0;idata); (2) ; (3) ; p-next=NULL; return OK; /CreatList_L 2. 下列算法是经典模式匹配算法程序，请填写适当的语句，完成该功能。 #define MAXSTRLEN 255 typedef unsigned char SStringMAXSTRLEN+1; /0 号单元存放串长 int Index(SString S, SString T, int pos) if(pos=1 j= (4) ; while(inext; while( r ) if( (8) ) q=r; r= (9) ; tmp=q-data; q-data=p-data; p-data=tmp; p= (10) ; 六、六、 算法设计题（算法设计题（16 分）分） 算法书写要求：应简单阐述算法的主要思想，对关键变量和关键语句进行注释；如果为递算法书写要求：应简单阐述算法的主要思想，对关键变量和关键语句进行注释；如果为递 归算法，则应说明递归调用的初始条件，否则扣分。写出正确的设计思想和伪代码可以酌归算法，则应说明递归调用的初始条件，否则扣分。写出正确的设计思想和伪代码可以酌 情给分。情给分。 如果算法中用到堆如果算法中用到堆栈，可直接调用下列操作：栈，可直接调用下列操作： InitStack(S): 栈初始化 push(S,x): 将元素 x 推入栈 S；（插入） pop(S,x): 将栈顶元素存入变量 x 中；（删除） StackEmpty(S): 判别栈 S 是否为空，如果是，返回 1，否则返回 0 如果算法中用到队列，可直接调用下列操作：如果算法中用到队列，可直接调用下列操作： InitQueue(Q): 队列初始化 EnQueue(Q,x): 将元素 x 加入队列 Q；（插入） DeQueue(Q,x): 取出队头元素，放入变量 x 中；（删除） QueueEmpty(Q): 判别队列 Q 是否为空，如果是，返回 1，否则返回 0 1.（8 8 分）分）已知一个带有头结点的单链表，假设该链表只给出了头指针 L。在不改变链 表结构的前提下，请设计一个尽可能高效的算法，查找链表中倒数第 k 个位置上的结点 （k 为正整数），若查找成功，则打印该结点的值，并返回 1；否则，只返回 0。（注：注： 如果时间性能达不到要求，但算法思路正确，可酌情给分）如果时间性能达不到要求，但算法思路正确，可酌情给分） 链表结构定义为： typedef struct Lnode ElemType data; struct Lnode *next; LNode, *LinkList; 2、(8 分分) 下题中任选一题下题中任选一题 （1）给定一棵赫夫曼树 T，编写算法，求该赫夫曼树 T 的带权路径长度。 赫夫曼树 T 采用如下定义的存储结构： typedef struct BiTNode TElemType data; /此处 data 代表结点的权值 struct BiTNode *lchild, *rchild; BiTNode, *BiTree; （2）假设一棵二叉树以二叉链表表示，元素值为整数，且元素值无重复，编写算法， 打印以元素值等于某个给定的整数的结点为根的子树中的各个叶结点。 二叉树 T 采用如下定义的存储结构： typedef struct BiTNode TElemType data; struct BiTNode *lchild, *rchild; BiTNode, *BiTree; （3）设计一算法，要求将二叉树的叶结点按从左到右的顺序连成一个单链表，表头指 针为 head, 二叉树按二叉链表方式存储，链接时用叶结点的右指针域来存放单链表指 针，分析算法的时间、空间复杂度。 假设二叉树 T 采用如下定义的存储结构： typedef struct BiTNode TElemType data; struct BiTNode *lchild, *rchild; BiTNode, *BiTree; 2011 年数据结构与算法参考答案 一、一、 填空题填空题 1. O(1) 随机存取 2. 80 3. 防止数组下标越界 4. Head【Head【Tail【Tail（LS）】 5. A3 A5 A7 6. 活动 活动之间的先后关系 7. 该有向图无环 8. DEF 二、二、 选择题选择题 1.D 2.C 3.D 4.C 5.A 6.B 7.C 8.B 9.D 10.D 三、三、 判断题判断题 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 四、四、 应用题应用题 1. A B D G C E H F K JL I 2. (1) 邻接矩阵： 13 142 416 23 15 35 6355 G F E D C B A 邻接表： A B C D E F G 1234 06 04 05 025 34 15 0 1 2 3 4 5 6 6 (2) 深度优先搜索树为： B A C F E GD (3)最小生成树： A G E C V5F D 1 2 3 4 6 5 3. (1)二叉排序树如下： 33 1766 1225 58 70 56 8760 平均查找长度 ASL=(1+2X2+4X3+3X4)/10=2.9 (2)按照右子树根节点左子树的顺序遍历该二叉树， 即可得到从大到小的 顺序 (3) 33 1760 1225 58 70 56 87 (4) 125、12、7、15、34、47、65、47+、16、79 216、15、12、7、25、47、65、79、47+、34 3初始堆：79、47+、65、34、16、47、12、7、25、15 第一趟排序后：65、47+、47、34、16、15、12、7、25、79 （二叉树表示方法也可） 五、五、 程序填空题程序填空题 1. L 2. p-next = s 3. p = s 4. 1 5. i = i - j + 2 6. j = 1 7. i j + 1 8. q-data r-data 9. r-next 10. p-next 六、六、 算法设计题算法设计题 1. 三种基本思路，（1）设一指针 p 指向链表的第 1 个结点，之后找到离 p 距 离为 k 的结点 q（如果有的话），然后 p 与 q 同时移动，直到 q 指向链表尾 部。（2）计算出单链表的长度，从而计算出要查找的节点在正向的位置， 再从头遍历，将其找出。 （3）将单链表所有节点入栈，出栈过程中找到第 K 个节点。第一种思路可得满分，后两种扣 2 分。 第二种方法参考代码： int Search(LinkList L, int k) Lnode *p; int length = 0, i; if(!L | !L-next) return -1; p = L-next; while(p) length+; p = p-next; if(length next; for(i=0; inext; printf(“该元素为：%dn”, p-data); return p-data; 2. (1) int Hvalue(BiTree T, int h) int lvalue, rvalue; if(!T) return