《北京科技大学-2013--2014学年-数据结构与算法分析期末考试试卷》由会员分享，可在线阅读，更多相关《北京科技大学-2013--2014学年-数据结构与算法分析期末考试试卷（8页珍藏版）》请在金锄头文库上搜索。
1、北京科技大学 2013-2014学年 第 1 学期 数据结构与算法分析 试卷院(系) 班级 学号 姓名 试卷卷面成绩占课程考核成绩70%平时成绩占30%课程考核成绩题号一二三四五六七小计得分装 订 线 内 不 得 答 题自 觉 遵 守 考 试 规 则，诚 信 考 试，绝 不 作 弊得 分一、（26分）选择题1设一维数组中有n个数组元素，则读取第i个数组元素的平均时间复杂度为（ ）。(A) O(n)(B) O(nlog2n)(C) O(1) (D) O(n2)2设一棵二叉树的深度为k，则该二叉树中最多有（ ）个结点。 (A) 2k-1 (B) 2k(C) 2k-1(D) 2k-13.设指针变量p
2、指向单链表中结点A，若删除单链表中结点A，则需要修改指针的操作序列为（ ）。(A) q=p-next；p-data=q-data；p-next=q-next；free(q)；(B) q=p-next；q-data=p-data；p-next=q-next；free(q)；(C) q=p-next；p-next=q-next；free(q)；(D) q=p-next；p-data=q-data；free(q)；4设有5000个待排序的记录关键字，如果需要用最快的方法选出其中最小的10个记录关键字，则用下列（ ）方法可以达到此目的。(A) 快速排序(B) 堆排序(C) 冒泡排序(D) 插入排序5设
3、一组初始关键字记录关键字为(20，15，14，18，21，36，40，10)，则以20为基准记录的一趟快速排序结束后的结果为( )。(A) 10，15，14，18，20，36，40，21(B) 10，15，14，18，20，40，36，21(C) 10，15，14，20，18，40，36，2l(D) 15，10，14，18，20，36，40，216. 设指针变量top指向当前链式栈的栈顶，则删除栈顶元素的操作序列为（ ）。(A) top=top+1;(B) top=top-1;(C) top-next=top;(D) top=top-next;7. 设一组权值集合W=(15，3，14，2，6，
4、9，16，17)，要求根据这些权值集合构造一棵哈夫曼树，则这棵哈夫曼树的带权路径长度为（ ）。(A) 129(B) 219(C) 189(D) 2298.设某棵二叉树中只有度数为0和度数为2的结点且度数为0的结点数为n，则这棵二叉中共有（ ）个结点。(A) 2n(B) n+l(C) 2n-1(D) 2n+l 9. 下列程序段的时间复杂度为（ ）。i=0，s=0； while (snext=p-next；p-next=-s；(B) q-next=s； s-next=p；(C) p-next=s-next；s-next=p；(D) p-next=s；s-next=q；11设有一个10阶的下三角矩阵
5、A（包括对角线），按照从上到下、从左到右的顺序存储到连续的55个存储单元中，每个数组元素占1个字节的存储空间，则A54地址与A00的地址之差为（ ）。(A) 10(B) 19(C) 28(D) 5512. 设有6个结点的无向图，该图至少应有( )条边才能确保是一个连通图。(A).5 (B).6 (C).7 (D).813. 设无向图G中的边的集合E=(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)，则从顶点a出发进行深度优先遍历可以得到的一种顶点序列为（ ）。(A) aedfcb(B) acfebd(C) aebcfd(D) aedfbc得 分二、（20分）填
6、空题1. 设有向图G的存储结构用邻接矩阵A来表示，则A中第i行中所有非零元素个数之和等于顶点i的_，第i列中所有非零元素个数之和等于顶点i的_。2. 下面程序段的功能是实现冒泡排序算法，请在下划线处填上正确的语句。void bubble(int rn)for(i=1;i=n-1; i+)for(exchange=0,j=0; jrj+1)temp=rj+1;_;rj=temp;exchange=1;if (exchange=0) return；4. 设一棵二叉树的中序遍历序列为BDCA，后序遍历序列为DBAC，则这棵二叉树的前序序列为_。5设用于通信的电文仅由8个字母组成，字母在电文中出现的频
7、率分别为7、19、2、6、32、3、21、10，根据这些频率作为权值构造哈夫曼树，则这棵哈夫曼树的高度为_。6. 设有n个结点的完全二叉树，如果按照从上到下、从左到右从1开始顺序编号，则第i个结点的双亲结点编号为_，右孩子结点的编号为_。7. 设一组初始关键字序列为(38，65，97，76，13，27，10)，则第3趟简单选择排序后的结果为_； 第2趟希尔排序后的结果为_。得 分三、（10分）判断题1. 不论是入队列操作还是入栈操作，在顺序存储结构上都需要考虑“溢出”情况。（ ）2当向二叉排序树中插入一个结点，则该结点一定成为叶子结点。（ ）3设某堆中有n个结点，则在该堆中插入一个新结点的时间
8、复杂度为O(log2n)。（ ）4完全二叉树中的叶子结点只可能在最后两层中出现。（ ）5哈夫曼树中没有度数为1的结点。（ ）6对连通图进行深度优先遍历可以访问到该图中的所有顶点。（ ）7先序遍历一棵二叉排序树得到的结点序列不一定是有序的序列。（ ）8由树转化成二叉树，该二叉树的右子树不一定为空。（ ）9线性表中的所有元素都有一个前驱元素和后继元素。（ ）10.背包问题是典型的贪心算法的例子。（ ）得 分四、（44分）算法设计及问答题1、（12分）给出统计二叉树中节点个数的算法得 分2.、（10分）定义一个学生类，输入学生的姓名、语文成绩、数学成绩，计算并输出每个学生的各门功课的成绩、总成绩和平均成绩。得 分3、（10分）说明线性表，栈与队列的异同点得 分4、（12分）对链表的主要操作有几种？请以一种链表为例分别写出关于这三种操作的算法。
