2008-2009算法与数据结构试卷B.doc

北京物资学院 2008 — 2009 学年第 1 学期期末考试 算法与数据结构（Ｃ） 课程试卷（ B 卷） 题 号 一 二 三 四 五 六 七 八 九 总 分 评 分 评卷人 审核人： 名词解释（8分，每小题2分） 1、数据结构的逻辑结构 2、栈 3、小根堆 4、图的邻接矩阵 二、（16分）填空 1、抽象数据类型由一种数据结构和在其上的 所组成。 2、算法时间复杂度可以用与样本量有关的 表示，简称大O表示法。 3、顺序存储的线性表是由 作为存储空间的，其最大存 储空间定义变量为 。 4、队列插入元素的操作是在 进行，删除操作是在 进行。 5、如果某种数据结构的存储类型定义如下： typedef int DataType; struct Node; typedef struct Node * PNode; struct Node { DataType info; PNode link; }; typedef struct Node * LinkList; 则此数据类型定义为： ，其中link的含义是 。 6、在递归函数调用时，计算机自动建立栈，栈 中 至 少 包含二个域： 和参数域 。 7、一棵度为3的树，它的结点个数是12，则它的最小高度是 ；最大高度是 。 8、对一棵二叉排序树进行中序遍历，得到的结点序列一定是 。 9、一个图的边集为{0,2,0,4,2,53,2,4,14,3}，从0顶点出发进行深度遍历的结果是： ；从0顶点出发进行广度遍历的结果是： 。 10、若根据数据集合{24，44，36，48，52，72，62，58}建立散列表，采用h(K)=K%13计算散列地址，并采用链接法处理冲突，则元素72的初始散列地址为： ，数据集合中的 有地址冲突。 三、选择题（10分） 1、在栈的有关定义中以下哪种说法是正确的：（ ） A． 栈顶元素只有出栈后才能读。 B． 栈是一种链接的线性表。 C. 栈是一种后进先出的线性表。 D. 栈是一种先进先出的线性表。 2、若顺序循环队列有 MAXNUM个存储单元，front、rear分别为队首和队尾指针，队首和队尾的数据类型为 （ ） A． int B. char C. flout D. struct 3、对于链接存储的队列，front、rear分别为队首和队尾指针，队首和队尾的数据类型为 （ ） A． int B. char C. flout D. 指针类型 4、在广义表结点定义中，每个结点由三个域组成： 其中atom是一个标志位，atom＝0时表示本结点为广义表，此时info存放子广义表中（ ）。 A．第一个元素结点的元素值 B. 第一个元素结点的地址 C. 下一个元素结点的元素值 D. 下一个元素结点的地址 5、一棵二叉树如下，此二叉树中根周游结果为（ ）。 ABCDEF DBAFEC DBACEF ADBFEC 6、对一个有n个结点的二叉树来说，如果将其扩充，其扩充二叉树中有（ ）个外部结点。 A．n－1 B．n C．n＋1 D．2n 7、由权值分别为2、3、4、6、7、9的叶子结点生成一棵哈夫曼树，它的带权路径长度为（ ）。 A. 39 B. 49 C. 59 D. 69 8、已知一个有向图的边集为{0,16, 0,25, 0,32, 1,410, 3,22, 2,49, 3,48 }，则该图从0顶点到其余各顶点的最短路径是（ ）。 A. V0－V1 V0－V1－V2 V0－V1－V2－V3 V0－V1－V2－V3－V4 B. V0－V3 V0－V3－V1 V0－V3－V1－V2 V0－V3－V1－V2－V4 C. V0－V3 V0－V3－V2 V0－V3－V2－V1 V0－V3－V2－V1－V4 D. V0－V3 V0－V3－V2 V0－V1 V0－V3－V2－V4 9、利用二叉排序树进行检索，算法的时间复杂度是（ ）。 A．O(1) B．O(log2n) C．O(n)