数据结构2007试卷及答案(共8页).doc

《数据结构2007试卷及答案(共8页).doc》由会员分享，可在线阅读，更多相关《数据结构2007试卷及答案(共8页).doc（8页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选优质文档-倾情为你奉上 上 装 订 线 院（系）名： 班级： 姓名： 学号： 考生类别： 考试日期： 下 装 订 线 陕西师范大学20062007学年第二学期期末考试计算机科学学院2005级计算机科学专业数据结构题号一二三四总分分数答卷注意事项： 1、学生必须用蓝色（或黑色）钢笔、圆珠笔或签字笔直接在试题卷上答题。2、答卷前请将密封线内的项目填写清楚。 3、字迹要清楚、工整，不宜过大，以防试卷不够使用。 4、本卷共 4 大题，总分为100分。得分评卷人一、选择题（每题2分 ，共10分）1. 下面程序段的时间复杂度为(C)。 for(int i=0;im;i+) for(int j=0;jl

2、child ); depthRight= Depth( T-rchild ); depthval = 1 + (depthLeft depthRight?depthLeft:depthRight); return depthval;2. 设C=a1,b1,a2,b2,an,bn为一线性表,采用带头结点的hc单链表存放，编写一个算法，将其拆分为两个线性表，使得：A=a1,a2,an，B=b1,b2,bn。（8分）答案：解:设拆分后的两个线性表都用带头结点的单链表存放。先建立两个头结点*ha和*hb，它们用于存放拆分后的线性表A和B,ra和rb分别指向这两个单链表的表尾，用p指针扫描单链表hc，将

3、当前结点*p链到ha未尾，p沿next域下移一个结点，若不为空，则当前结点*p链到hb未尾，p沿next域下移一个结点，如此这样，直到p为空。最后将两个尾结点的next域置空。对应算法如下：void fun(LinkList *hc, LinkList *&ha, LinkList *&hb) LinkList *p=hc-next,*ra,*rb; ha=hc; /*ha的头结点利用hc的头结点*/ ra=ha; /*ra始终指向ha的末尾结点*/ hb=(LinkList *)malloc(sizeof(LinkList); /*创建hb头结点*/ rb=hb; /*rb始终指向hb的末尾结点*/while (p!=NULL) ra-next=p;ra=p; /*将*p链到ha单链表未尾*/ p=p-next; if (p!=NULL) rb-next=p; rb=p; /*将*p链到hb单链表未尾*/ p=p-next; ra-next=rb-next=NULL; /*两个尾结点的next域置空*/专心-专注-专业