2015数据结构考试试题答案.doc

北京科技大学 2014--2015学年 第 1 学期 数据结构与算法分析 试题答案 一、（28分）选择题 1.A 2.D 3.D 4.C 5.C 6.D 7.C 8.A 9.B 10.C 11.A 12.A 13.C 14.B 二、（16分）填空题 1. BDCA 2. n+1-i；n-i 3. 0 4.冒泡 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）。 答案: q-llink=p; q-rlink=p-rlink; p-rlink-llink=q; p-rlink=q; （10分）下图所示的森林：　　 (1) 求树（a）的先根序列和后根序列； (2) 求森林先序序列和中序序列； （3）将此森林转换为相应的二叉树； 答案: (1) ABCDEF; BDEFCA； (2) ABCDEFGHIJK; BDEFCAIJKHG (3)森林转换为相应的二叉树； 4、（6分） 阅读下面程序段, 回答问题: LinkList mynote(LinkList L) {//L是不带头结点的单链表的头指针 if(LL-next){ q=L；L=L－next；p=L； S1： while(p－next) p=p－next； S2： p－next=q；q－next=NULL； } return L； } 请回答下列问题： （1）说明语句S1的功能； （2）说明语句组S2的功能； （3）设链表表示的线性表为（a1,a2, …,an）,写出算法执行后的返回值所表示的线性表。 答: （1）查询链表的尾结点 （2）将第一个结点链接到链表的尾部，作为新的尾结点 （3）返回的线性表为（a2,a3,…,an,a1） 5、（14分）什么叫完全二叉树？给出一个完全二叉树的例子. 用程序实现求 求二叉树深度的算法。 答案: 定义见书上.程序如下: #include stdio.h#include stdlib.htypedef struct node{ char data; struct node *left,*right;}Node,*PNode;PNode createBtree(PNode root)//创建二叉树，控制台下输入，基于先序遍历输入{ char data; scanf(%c,data); if (data== ) { root=NULL; return root; } root = (PNode)malloc(sizeof(Node)); root-data = data; root-left = createBtree(root-left); root-right = createBtree(root-right); return root;}int depth(PNode root)//这就是你要的函数。{ int ld,rd; if (root==NULL) { return 0; } ld = 1+depth(root-left); rd = 1+depth(root-right); return ldrd?ld:rd;}int main(){ PNode root=NULL; root = createBtree(root); printf(%d,depth(root)); return 0;}