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