09本科-数据结构期末考试B答案-陈正铭
装
订
线—————————————————————————————————————————————————————————— 2010－2011学年第一学期 计算机科学学院《数据结构》期末考试试卷（B卷） 答案与评分标准
注：1、总分共100分，考试时间120分钟。 2、此试卷适用于09级计算机科学与技术本科专业学生。 2分，共20分） 1．数据的逻辑结构在计算机存储器内的表示，称为数据的（ 存储结构 ）。 2．当线性表的元素总数不稳定，且经常进行插入和删除运算，应采用（ 链式 ）存储结构。 3. 求最小生成树的普里姆算法耗用的时间与图中（ 顶点 ）的数目相关。 4．若序列中关键字相同的记录在排序前后的相对次序发生变化，则称该排序算法是（ 不稳定 ）的。 5. 若s=″ABCDEFGHIJK″,t=″ABC″,执行运算substr(s,strlen(t), strlen(t))后的返回值为（ CDE ）。 6．已知一棵完全二叉树共有848个结点，则该树中有（ 424
）个叶子结点。 7．树T有n个结点且结点的度均为p或者0，则树中的叶子结点总数为：（ n－(n-1)/p ） 。 8．在无向图的邻接矩阵中，第i列非零元个数就是第i个顶点的（ 度数 ）。 9．具有m个结点的二叉树，采用二叉链表存储，共有（ m+1 ）个空链域。 10．某二叉树的后序遍历序列是CDBGFEA，中序遍历序列是CBDAFGE，则其先序遍历序列是（ ABCDEFG ）。 2分，共20分） 1．二维数组A[8][9]采用列优先存储方法，若每个元素各占2个存储单元，而且A[0][0]的地址为1000，则A[5][7]的地址为 （ A ） A．1122 B．1234 C．1212 D．1120
