文档介绍：北京物资学院2008—2009学年第1学期期末考试学号:班级:姓名:装订线内不要答题算法与数据结构(C)课程试卷(B卷)题号一二三四五六七八九总分评分评卷人审核人:名词解释(8分,每小题2分)1、数据结构的逻辑结构2、栈3、小根堆4、图的邻接矩阵二、(16分)填空1、抽象数据类型由一种数据结构和在其上的所组成。2、算法时间复杂度可以用与样本量有关的表示,简称大O表示法。3、顺序存储的线性表是由作为存储空间的,其最大存储空间定义变量为。4、队列插入元素的操作是在进行,删除操作是在进行。5、如果某种数据结构的存储类型定义如下:typedefintDataType;structNode; typedefstructNode*PNode; structNode{ DataTypeinfo;PNodelink;};typedefstructNode*LinkList;则此数据类型定义为:,其中link的含义是。6、在递归函数调用时,计算机自动建立栈,栈中至少包含二个域:和参数域。7、一棵度为3的树,它的结点个数是12,则它的最小高度是;最大高度是。8、对一棵二叉排序树进行中序遍历,得到的结点序列一定是。9、一个图的边集为{<0,2>,<0,4>,<2,5><3,2>,<4,1><4,3>},从0顶点出发进行深度遍历的结果是:;从0顶点出发进行广度遍历的结果是:。10、若根据数据集合{24,44,36,48,52,72,62,58}建立散列表,采用h(K)=K%13计算散列地址,并采用链接法处理冲突,则元素72的初始散列地址为:,数据集合中的有地址冲突。三、选择题(10分)1、在栈的有关定义中以下哪种说法是正确的:()。。。。2、若顺序循环队列有MAXNUM个存储单元,front、rear分别为队首和队尾指针,队首和队尾的数据类型为()、对于链接存储的队列,front、rear分别为队首和队尾指针,队首和队尾的数据类型为()、在广义表结点定义中,每个结点由三个域组成:atominfolink其中atom是一个标志位,atom=0时表示本结点为广义表,此时info存放子广义表中()。、一棵二叉树如下,此二叉树中根周游结果为()。BCFEDABCDEFDBAFECDBACEFADBFEC6、对一个有n个结点的二叉树来说,如果将其扩充,其扩充二叉树中有()个外部结点。-+、由权值分别为2、3、4、6、7、9的叶子结点生成一棵哈夫曼树,它的带权路径长度为()。 、已知一个有向图的边集为{<0,1>6,<0,2>5,<0,3>2,<1,4>10,<3,2>2,<2,4>9,<3,4>8},则该图从0顶点到其余各顶点的最短路径是()。->V1V0->V1->V2V0->V1->V2->V3V0->V1->V2->V3->->V3V0->V3->V1V0->V3->V1->V2V