数据结构-B卷.docVIP

　　　　　　　　　　　　　　　　　　　　试卷编号：　　　　（B)卷 数据结构 课程 课程类别：必 闭卷 考试日期：　 　　　 题号 一 二 三 四 五 六 七 八 九 十 总分 累分人签名 题分 20 30 30 10 10 100 得分 考生注意事项：1、本试卷共 8 页，总分　100　分，考试时间　120　分钟。 2、考试结束后，考生不得将试卷、答题纸和草稿纸带出考场。 3、所有答案必须写在答题纸上，写在试卷上无效。 一、选择题(每题2分，共20分) 1．单链表的一个存储结点包含（　D　）。 A．数据域或指针域 B．指针域或链域 C．指针域和链域 D．数据域和指针域 2. 线性表是具有n个（ C ）的有限序列（n0）。 A．表元素 B．字符 C．数据元素 D．数据项 3．对顺序表上的插入、删除算法的时间复杂性分析来说，通常以（ B ）为标准操作来考虑。 A．条件判断 B．结点移动 C．算术表达式 D．赋值语句 4．循环链表主要优点是 （ D ） A．不再需要头指针了 B．已知某个结点的位置后，能够容易找到它的直接前趋 C．在进行插入、删除运算时，能更好地保证链表不断开 D．从表中任一结点出发都能扫描到整个链表 5．栈和队都是（ C ） A．顺序存储的线性结构 B. 链式存储的非线性结构 C．限制存取点的线性结构 D．限制存取点的非线性结构 6． A．有向图 B．无向图 C．AOV网 D．AOE网 7. 二维数组A[6][8]采用行优先的存储方法，若每个元素各占10个存储单元，且第1个元素的A[0][0]地址为1000，则元素A[4][7]的地址为( B ) A. 1282 B. 1390 C. 1270 D. 1276 8. 在深度为6的完全二叉树中 （ D ） A.最少有31个结点，最多有64个结点 B.最少有32个结点，最多有64个结点 C.最少有31个结点，最多有63个结点 D.最少有32个结点，最多有63个结点 9．具有n个顶点的连通图至少有（ A ）条边。 A. n-1 B. n C. n+1 D. 2n 10．具有3个结点的二叉树的有（ B ）种不同形态。 A. 6 B. 5 C. 3 D. 4 二、填空题(每空2分，共30分) 1.通常从__正确性 _、_可读性 _、__健壮性 _、__高效性_ _等几方面评价算法的(包括程序)的质量。 2.程序段“for(i=l;i=n;i++){k++;for(j=1;j=n;j++)L+=k;}”的时间复杂度T(n)= __ O（n2）__。 3.在循环队列中用数组A[0..m-1] 存放队列元素，其队头和队尾指针分别为front和rear，则当前队列中的元素个数是( rear - front + m) % m 。 4.在有n个结点的二叉链表中，值为非空的链域的个数为 n-1 。 5.组成串的数据元素只能是 字符 ，则INDEX（‘DATASTRUCTURE’，‘STR’）的值为 5 。 6.一个n*n的对称矩阵，如果以行或列为主主序存入内存，则其存储容 为 n*(n+1) /2 。 7.由权值分别为，，，，的叶子结点生成一棵哈夫曼树，它的带权路径长度为）(共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）树的深度是多少？ 2.（5分）已知二叉树的先序序列和中序序列分别为ABECDFGHIJ和EBCDAFHIGJ， (1)画出该二叉树;（2分） (2)写出该二叉树的后序序列。（3分） 3.（4分）写出有向图的所有拓扑排序序列。 解：（1）ABCDEG （2）ABCEDG 4.（4分）请画出与下列森林对应的二叉树。 5.（8分）已知一个无向图的邻接表如下图所示。 （1）画出该图的图形；（2分） （2）求