北京科技大学2015年数据结构与算法分析试卷+答案

数据结构与算法分析试卷第1页共5页北京科技大学2015--2016学年第1学期数据结构与算法分析试卷院(系)班级学号姓名试卷卷面成绩占课程考核成绩70%平时成绩占30%课程考核成绩题号一二三四五六七小计得分一、（30分）选择题1.设一组权值集合W={2，3，4，5，6}，则由该权值集合构造的哈夫曼树中带权路径长度之和为()。(A)20(B)30(C)48(D)452.执行一趟快速排序能够得到的序列是()。(A)[41，12，34，45，27]55[72，63](B)[45，34，12，41]55[72，63，27](C)[63，12，34，45，27]55[41，72](D)[12，27，45，41]55[34，63，72]3.设指针变量p指向单链表中结点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.时间复杂度不受数据初始状态影响而恒为O(nlog2n)的是()。(A)堆排序(B)冒泡排序(C)希尔排序(D)快速排序5.设二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树满足的条件是()。得分装订线内不得答题自觉遵守考试规则，诚信考试，绝不作弊数据结构与算法分析试卷第2页共5页(A)空或只有一个结点(B)高度等于其结点数(C)任一结点无左孩子(D)任一结点无右孩子6.一趟排序结束后不一定能够选出一个元素放在其最终位置上的是()。(A)堆排序(B)冒泡排序(C)快速排序(D)希尔排序7.设某棵二叉树中只有度数为0和度数为2的结点且度数为0的结点数为n，则这棵二叉中共有（）个结点。(A)2n(B)n+l(C)2n-1(D)2n+l8.顺序查找不论在顺序线性表中还是在链式线性表中的时间复杂度为()。(A)O(n)(B)O(n2)(C)O(n1/2)(D)O(1og2n)9.下列程序段的时间复杂度为（）。i=0，s=0；while(sn){s=s+i；i++；}(A)O(n1/2)(B)O(n1/3)(C)O(n)(D)O(n2)10.深度为k的完全二叉树中最少有()个结点。(A)2k-1-1(B)2k-1(C)2k-1+1(D)2k-111.设指针变量front表示链式队列的队头指针，指针变量rear表示链式队列的队尾指针，指针变量s指向将要入队列的结点X，则入队列的操作序列为()。(A)front-next=s;front=s;(B)s-next=rear;rear=s;(C)rear-next=s;rear=s;(D)s-next=front;front=s;12.设某无向图中有n个顶点e条边，则建立该图邻接表的时间复杂度为()。(A)O(n+e)(B)O(n2)(C)O(ne)(D)O(n3)13.设某哈夫曼树中有199个结点，则该哈夫曼树中有()个叶子结点。(A)99(B)100(C)101(D)10214.设无向图G中的边的集合E={(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)}，则从顶点a出发进行深度优先遍历可以得到的一种顶点序列为（）。(A)aedfcb(B)acfebd(C)aebcfd(D)aedfbc15.设用邻接矩阵A表示有向图G的存储结构，则有向图G中顶点i的入度为()。(A)第i行非0元素的个数之和(B)第i列非0元素的个数之和(C)第i行0元素的个数之和(D)第i列0元素的个数之和数据结构与算法分析试卷第3页共5页二、判断题(20分)1.调用一次深度优先遍历可以访问到图中的所有顶点。()2.完全二叉树中的叶子结点只可能在最后两层中出现。（）3.冒泡排序在初始关键字序列为逆序的情况下执行的交换次数最多。()4.满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树。()5.设一棵二叉树的先序序列和后序序列，则能够唯一确定出该二叉树的形状。()6.层次遍历初始堆可以得到一个有序的序列。()7.设一棵树T可以转化成二叉树BT，则二叉树BT中一定没有右子树。()8.线性表的顺序存储结构比链式存储结构更好。()9.中序遍历二叉排序树可以得到一个有序的序列。()10.快速排序是排序算法中平均性能最好的一种排序。()三、（30分）填空题1.for(i=1，t=1，s=0;i=n;i++){t=t*i;s=s+t;}的时间复杂度为_________。2.设指针变量p指向单链表中结点A，指针变量s指向被插入的新结点X，则进行插入操作的语句序列为__________________________(设结点的指针域为next)。3.设有向图G的二元组形式表示为G=(D，R)，D={1，2，3，4，5}，R={r}，r={1,2，2,4，4,5，1,3，3,2，3,5}，则给出该图的一种拓扑排序序列__________。4.设无向图G中有n个顶点，则该无向图中每个顶点的度数最多是_________。5.设二叉树中度数为0的结点数为50，度数为1的结点数为30，则该二叉树中总共有_______个结点数。6.设F和R分别表示顺序循环队列的头指针和尾指针，则判断该循环队列为空的条件为_____________________。7.设二叉树中结点的两个指针域分别为lchild和rchild，则判断指针变量p所指向的结点为叶子结点的条件是_____________________________________________。8.简单选择排序和直接插入排序算法的平均时间复杂度为___________。得分数据结构与算法分析试卷第4页共5页9.快速排序算法的空间复杂度平均情况下为__________，最坏的情况下为_________。10.设一棵二叉树的中序遍历序列为BDCA，后序遍历序列为DBAC，则这棵二叉树的前序序列为____________________。四、（20分）算法设计及问答题在链式存储结构上建立一棵二叉排序树。(6分)设计判断二叉树是否为二叉排序树的算法。(6分)在链式存储结构上设计直接插入排序算法。(8分)答案一、选择题（30分）1.D2.A3.A4.A5.DB6.D7.C8.A9.A10.D11.C12.A13.B14.A15.B二、判断题1.错2.对3.对4.对5.错6.错7.对8.错9.对10.对三、填空题1.O(n)2.s-next=p-next;p-next=s3.(1，3，2，4，5)4.n-15.1296.F==R7.p-lchild==0&&p-rchild==08.O(n2)9.O(nlog2n)，O(n)10.CBDA四、算法设计题(答案为多种,依据个人编程序的技能)1.在链式存储结构上建立一棵二叉排序树。#definen10得分数据结构与算法分析试卷第5页共5页typedefstructnode{intkey;structnode*lchild,*rchild;}bitree;voidbstinsert(bitree*&bt,intkey){if(bt==0){bt=(bitree*)malloc(sizeof(bitree));bt-key=key;bt-lchild=bt-rchild=0;}elseif(bt-keykey)bstinsert(bt-lchild,key);elsebstinsert(bt-rchild,key);}voidcreatebsttree(bitree*&bt){inti;for(i=1;i=n;i++)bstinsert(bt,random(100));}2.设计判断二叉树是否为二叉排序树的算法(6分)。intminnum=-32768,flag=1;typedefstructnode{intkey;structnode*lchild,*rchild;}bitree;voidinorder(bitree*bt){if(bt!=0){inorder(bt-lchild);if(minnumbt-key)flag=0;minnum=bt-key;inorder(bt-rchild);}}3.在链式存储结构上设计直接插入排序算法(8分)voidstraightinsertsort(lklist*&head){lklist*s,*p,*q;intt;if(head==0||head-next==0)return;elsefor(q=head,p=head-next;p!=0;p=q-next){for(s=head;s!=q-next;s=s-next)if(s-datap-data)break;if(s==q-next)q=p;else{q-next=p-next;p-next=s-next;s-next=p;t=p-data;p-data=s-data;s-data=t;}}}