数据结构-A卷.doc

　　　　　　　　　　　　　　　　　　　　试卷编号：　　　　（A)卷 数据结构 课程 课程类别：必 闭卷 考试日期：　　　　　 题号 一 二 三 四 五 六 七 八 九 十 总分 累分人签名 题分 20 30 30 10 10 100 得分 考生注意事项：1、本试卷共 8 页，总分　100　分，考试时间　120　分钟。 2、考试结束后，考生不得将试卷、答题纸和草稿纸带出考场。 3、所有答案必须写在答题纸上，写在试卷上无效。 一、选择题(每题2分，共20分) 1．线性表采用链式存储时，结点的存储地址（ ） A．必须是不连续的 B．连续与否均可 C．必须是连续的 D．和头结点的存储地址相连续 2.如果在数据结构中每个数据元素只可能有一个直接前驱，但可以有多个直接后继，则该结构是（ ） A. 栈 B. 队列 C. 树 D. 图 3．求单链表中当前结点的后继和前驱的时间复杂度分别是（　　） A．O(n)和O(1) B．O(1)和O(1) C．O(1)和O(n) D．O(n)和O(n) 4．非空的单循环链表的头指针为head,尾指针为rear，则下列条件成立的是（　　） A．rear-next==head B．rear-next-next==head C．head-next==rear D．head-next-next==rear 5.队和栈的主要区别是( ) A.逻辑结构不同 B.存储结构不同 C.所包含的运算个数不同 D.限定插入和删除的位置不同 6．10.如图所示的有向无环图可以得到的不同拓扑序列的个数为（　　） A.1 B.2 C.3 D.4 二、填空题(每空2分，共30分) 根据数据元素之间的关系不同，四种基本的数据结构是_________、_________、_____________和_____________。 链式存储结构的特点是借助 来表示数据元素之间的逻辑关系。 在如图所示的链表中，若在指针p所指的结点之后插入数据域值相继为a的一个结点，则可用下列两个语句实现该操作，它们依次是 和 。 空串的长度是 ；空格串的长度是 。 设串sl=Data Structures”,s2=″S″，则子串定位函数index(s1,s2)的值为 。 由4个权值为2,4,5,7构造的赫夫曼树的WPL（带权路径长度）为 。 在一棵度为 3 的树中 , 度为3 的结点个数为 2, 度为 2 的结点个数为 1, 则度为 0 的结点个数为 。 在有n个结点的二叉链表中必定存在 个空链域。 n个顶点的有向完全图中含弧的数目为 。 二分查找的存储结构仅限于顺序存储结构，而且是用 表表示。 三、问答题(共30分) 1. （5分）假设以有序对p,c表示从双亲结点到孩子结点的一条边，若已知树中边的集合为{a,b,a,d,a,c,c,e,c,f,c,g,c,h,e,i,e,j, g,k},请回答下列问题： （1）哪个结点是根结点？（2）哪些结点是叶子结点？（3）哪些结点是k的祖先？（4）哪些结点是j的兄弟？（5）树的深度是多少？ 4.（5分）已知一棵含有n个结点的树中，只有度为k的分支结点和度为0的叶子结点。试求该树中叶子结点的数目。 5.（8分）已知一个无向图的顶点集为 {a,b,c,d,e} , 其邻接矩阵如下所示 （1）画出该图的图形；（2分） （2）求出每个顶点的度；（2分） （3）根据邻接矩阵从顶点 a 出发进行深度优先遍历和广度优先遍历，写出相应的遍历序列。（4分） 6. （4分）连通网络如图所示。试按 (顶点1，顶点2，权值)的格式，若从顶点1出发应用普里姆算法给出在构造最小生成树过程中顺序选出的各条边。 四、算法填空题(每空2分，共10分) 1. 带头结点的单链表L（长度大于1），s为指向链表中某个结点的指针。算法的功能是，删除并返回链表中指针s所指结点的前驱的值。请在空缺处填入合适的内容，使其成为完整的算法。 typedef struct node { DataType data； struct node *next； }*LinkList； DataType f (LinkList L, LinkList s) { LinkList pre，p； DataType e； pre=L； p=L-next； while( (1) ) { pre=p;