北京科技大学2014-2015年数据结构与算法试题

北京科技大学2014--2015学年第1学期数据结构与算法分析试题答案一、（28分）选择题1.A2.D3.D4.C5.C6.D7.C8.A9.B10.C11.A12.A13.C14.B二、（16分）填空题1.BDCA2.n+1-i；n-i3.04.冒泡5.2n;n-1;n+1三、（10分）判断题1．错；2．对；3．对；4．对；5．对；6．错；7．对；8．；对9.错；10.对四、（44分）算法设计及问答题1、（6分）设一组初始记录关键字序列为(45，80，48，40，22，78)，则分别给出第4趟简单选择排序和第4趟直接插入排序后的结果。直接写答案，不需要过程。(22,40,45,48,80,78)(3分)(22,40,45,48,80,78)(3分)2、（6分）设指针变量p指向双向链表中结点A，指针变量q指向被插入结点B，要求给出在结点A的后面插入结点B的操作序列（设双向链表中结点的两个指针域分别为llink和rlink）。1.答案:q-llink=p;q-rlink=p-rlink;p-rlink-llink=q;p-rlink=q;3、（10分）下图所示的森林：(1)求树（a）的先根序列和后根序列；(2)求森林先序序列和中序序列；（3）将此森林转换为相应的二叉树；ABCDEFGHIJK(a)(b)答案:(1)ABCDEF;BDEFCA；(2)ABCDEFGHIJK;BDEFCAIJKHG(3)森林转换为相应的二叉树；AGBCDEFHIJK4、（6分）阅读下面程序段,回答问题:LinkListmynote(LinkListL){//L是不带头结点的单链表的头指针if(L&&L-next){q=L；L=L－next；p=L；S1：while(p－next)p=p－next；S2：p－next=q；q－next=NULL；}returnL；}请回答下列问题：（1）说明语句S1的功能；（2）说明语句组S2的功能；（3）设链表表示的线性表为（a1,a2,…,an）,写出算法执行后的返回值所表示的线性表。答:（1）查询链表的尾结点（2）将第一个结点链接到链表的尾部，作为新的尾结点（3）返回的线性表为（a2,a3,…,an,a1）5、（14分）什么叫完全二叉树？给出一个完全二叉树的例子.用程序实现求求二叉树深度的算法。答案:定义见书上.程序如下:#includestdio.h#includestdlib.htypedefstructnode{chardata;structnode*left,*right;}Node,*PNode;PNodecreateBtree(PNoderoot)//创建二叉树，控制台下输入，基于先序遍历输入{chardata;scanf(%c,&data);if(data==''){root=NULL;returnroot;}root=(PNode)malloc(sizeof(Node));root-data=data;root-left=createBtree(root-left);root-right=createBtree(root-right);returnroot;}intdepth(PNoderoot)//这就是你要的函数。{intld,rd;if(root==NULL){return0;}ld=1+depth(root-left);rd=1+depth(root-right);returnldrd?ld:rd;}intmain(){PNoderoot=NULL;root=createBtree(root);printf(%d,depth(root));return0;}