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

北京物资学院 2008 — 2009 学年第 1 学期期末考试 算法与数据结构（Ｃ） 课程试卷（ A 卷） 题 号 一 二 三 四 五 六 七 八 九 总 分 评 分 评卷人 审核人： 一、名词解释（8分，每小题2分） 1、抽象数据类型 2、队列 3、哈夫曼树 4、图的最小生成树 二、（16分）填空 1、在线性结构、树形结构、图形结构中，前驱和后继结点之间分别存在着　　　　　　　　、1：N、　　　　　　　　　的联系。 2、算法应具备以下五个特性： 有穷性 、确定性、 　　　　　　　 、输入、　　　　　　　　　。 3、如果一个算法的时间复杂度为6n2+7n+7，则该算法时间复杂度的数量级为： 　　　　　　　　　　。 4、栈是一种运算受限的线性表，运算规则为：　　　　　　　　　。 5、动态链接存储的线性表是由　　　　　　　　　构成的，如果带表头附加结点，则空表时，表头指针的link域值为　　　　　　　　　　。 6、如果顺序表数据结构的存储类型定义如下，填写缺失的定义语句，或填写对应语句的说明语句。 Typedef int DataType； struct SeqList { int MAXNUM; /*　　　　　　　　　　　　　*/ int n; /* 存放线性表中元素的个数n≤MAXNUM */ 　　　　　　　　　　　; /* element[0],element[1]，…，element[n - 1]存放线性表中的元素 */}; 7、当求解一个问题时，是通过求解与它具有同样解法的子问题而得到的，这就是 　　　　　 。 8、在广义表结点定义中，每个结点由三个域组成： 其中atom是一个标志位，atom＝0时表示本结点为 　　　　 ，此时info存放子广义表中第一个元素结点的地址。 9、在一个小根堆中，堆顶结点的值是所有结点中的　　　　　　　　；在一个大根堆中，堆顶结点的值是所有结点中的　　　　　　　　　。 10、在一个具有n个顶点的无向图中，要连通所有顶点则至少需要 　　　　　　　　　　　　条边。 11、若根据数据集合{23，44，36，48，52，73，64，58}建立散列表，采用h(K)=K%13计算散列地址，并采用链接法处理冲突，则元素64的初始散列地址为： 　　　　　　　 。 三、选择题（10分） 1、以下哪种属于数据结构的逻辑结构描述（ 　 ）。 A. 顺序存储 B. 链接存储 C. 顺序存储的堆栈 D. 一个结点有多个直接后继结点 2、以下哪种属于数据结构的物理结构描述（ 　 ）。 A. 一棵二叉树可以为空 B. 栈的运算规则为后进先出 C. 顺序存储的堆栈 D. 一个结点有一个直接后继结点 3、在对算法的时间复杂度评价中，以下说法中，正确的是（ 　 ）。 A. 计算机主频速度决定了算法的时间复杂度 B. 算法的正确性决定了算法的时间复杂度 C. 要以最坏的情况作为时间复杂度的计算依据 D. 只需考虑时间复杂度的数量级 4、若循环队列有MAXNUM个顺序存储单元，front、rear分别为队首和队尾指针，则判断队空的条件是( 　 )。 A. front = = rear B. (front-1)% MAXNUM= = rear C. (rear+1) %MAXNUM= = front D. (front+1)% MAXNUM= = rear 5、对由n个内部结点构成的二叉树进行扩充后形成的扩充二叉树，它有（ 　 ）个外部结点 A． 1 B. n-1 C. n+1 D. n 6、如果一棵完全二叉树的高度为3，，那么以下正确的说法是（ 　 ）。 这棵树上的结点数不能少于9个 这棵树上的结点数不能多于3个 这棵树上的结点数8至15个之间 以上说法都不对 7、由权值分别为2、3、6、7、9的叶子结点生成一棵哈夫曼树，它的带权路径长度为（ 　 ）。 A. 32 B. 59 C. 69 D. 86 8、已知一个无向图的边集为{(0,1)3,　(0,2)5,　(0,3)6,　(1,4)10,　(2,3)2,　(2,4)9,　(3,4)8　}，则该图的最小生成树的边集是（ 　 ）。 {(0,1)3,(0,2)5,(0,3)6,(3,4)8} {(0,1)3,(0,2)5,(0,3)6,(2,3)2 } { (0,2)5,(0,3)6,(2,3)2,(3,4)8} {(0,1)3,(0,2)5,(2,3)2,(