数据结构综合二(北师大06真题).ppt

选择题： 1. 在建立某高校网站时，为方便浏览，建立了校 -系-教研室的链接，则这数据结构属于（ ） A 线性结构 B 树结构 C 图结构 D 集合结构 2. 设单链表的每个结点有两个域 :element 和link，在指针p所指示的结点之后插入新结点*s的操作是（ ） As-link=p;p-link=s; Bs-link=p-link;p-link=s; Cs-link=p-link;p=s; Dp-link=s;s-link=p; 3. 元素序列 (A ， B ， C ， D ， E) 顺序进栈，每个元素必须进栈一次，进栈后可立即出栈，也可在栈中停留一段时间后再出栈，则下面哪个序列不能得到（ ） A A,B,C,D,E B E,D,C,B,A C. B,E,D,C,A D. B,E,C,D,A,4.对一个已经存在的二叉排序树遍历，能够得到非递减 序列的遍历是（ ） A） 先序遍历 B）中序遍历 C） 后序遍历 D） 层遍历 5.在循环队列中，判断队列满的条件是（ ） A) （Q.rear+1）%MAXQSIZEQ.front B) Q.rearQ.front C) （Q. front +1）%MAXQSIZEQ. rear D) Q.rearQ.frontMAXQSIZE,判断题： 1. 哈夫曼树的根结点的权值等于所有叶结点（外结点）的权值之和。 2. 一个无向连通图的生成树是一个极大的连通子图。 3. 用堆排序时，若想得到一个非递减顺序表，则构造堆的堆顶元素应该最小 4. 选择排序是稳定的排序算法 5. 一个顶点数为n的无向连通图至少由n-1条边,三：填空题，请在答题纸上写下结果（共6题，每题5分） 、数据结构由四类基本结构，分别是 _、 _ 、_ 、_。 、已知树t的先根次序访问序列为GFKDAIEBCHJ 树t的后根次序访问序列为： DIAEKFCJHBG 请判断树t的度为_、层为_。 、已知广义表：A=( )；B=(e); C=(a,(b,c,d); D=(A, C, B); 则GetHead(GetTail(D)=_ 、图的遍历方法有_和_ 、对于关键字序列 46 , 58 ,15 ， 45 ， 90 ， 18 ， 10 ， 62 ，其快速排序第一趟的结果是_ 、给出字符串“”在KMP算法中的next数组和nextval数组_,集合 线性结构 树形结构 图形结构,3 5,C,深度优先 广度优先,10 18 15 45 46 90 58 62,0112123422,0102010422,综合练习二,北师大06年研究生试题,一、翻译题 二、简答题（考背诵）略 三、判断题，若正确，请画对号，否则画叉，并说明理由（分） 、图的一棵最小生成树的代价未必小于的其他任何一棵生成树的代价。（ ） 、二唯数组的每个元素是由个字符组成的串，其行下标i=0、，列下标j=、10，若按行先存储，元素A8,5的起始地址与按列先存储时的元素A5,10的起始地址相同（设每个字符占一个字节）。（ ） 、用邻接矩阵表示图，判定任意两个节点Vi和Vj之间是否有长度为m的路径相连，则只要检查Am的第i行第j列的元素是否为即可（ ） 、已知待排序的n个元素可分为n/k组，每个组内包含k个元素，且任一组内的各元素均分别大于前一组内的所有元素和小于后一组内的所有元素，若采用基于比较的排序，其时间下界应为O(nlog2K)（ ）,四、填空（每题分，共30分） 、下列程序的功能是按照右侧的格式输出的行杨晖三角形，请填空将程序补充完整。 main() int y77,n,m; for(n=1;n7;n+) _=1; yn1=1; for(n=3;n7;n+) for(m=2;mn;m+) ynm=_ for(n=1;n7;n+) for(m=1;m=n;m+) printf(“%4d“,_); printf(“n“); ,1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1,y1n,yn-1m+yn-1m-1,Ynm,、具有1/2(n-1)条边的无向图称为_，简称为_,其中n表示无向图顶点的个数， 1/2(n-1)是具有n个顶点无向图所拥有边的_ 、在AOV 网中不可能出现有向环或回路，如果出现环或回路，这意味着某项活动是_，这样的工程无法进行，对于计算机中的程序流程图来说就是_ 、比较以下4种排序方法，填写下表：,无向完全图 完全图,最大数,以自己为先决条件,死循环,五：函数expand（char s ,char t )在将字符串s复制到字符串t时，将其中的换行符和制表符转换为可见的转义字符，即用“n”表示换行符，用“t”表示制表符。填空将程序补充完整。 Expand (char s ,char t ) int i,j; for(i=j=0;si!=0;i+) switch (sj) casen:t _ =_;tj+=n; casen:t _ =_;tj+=t;break; default:t _ =si;break; tj=_; ,J+ ,J+ ,J+,0,五：应用题（16分） 已知深度为h的二叉树采用顺序存储结构已经存放于数组BT1:2h-1中，请写算法，产生该二叉树的二叉链表结构。详见excersize-changetree.c (用递归),、依据所示无向图，分别用prim和kruskal算法，画最小生成树,普里姆算法：从一个顶点开始 生成树，每次选与这个树相关 连的最小的边，等树长成能涵盖 所有顶点，即可。详见下图,克鲁斯卡尔：每次找一条权值最 小的边，如果这个边连接两个不 同的连通分量，则添加该边。反 复执行到所有顶点都连通为止。 详细过程不再给出，请自行作出,、设有n个活动需要演讲会场，而在同一时间内会场只能分配给其中一个活动。如果用表示活动集合，E=1,2n，每个活动i使用会场有一个起止时间( si , fi )，其中sifi。如果两个活动i和j的时间段不相交，则称活动i 与活动j是相容的，前后活动的时间边界重合不算相交。给定规模为10的问题实例E如下 (1,3), (0,5), (7,10), (6,7), (3,6), (8,9), (1,2), (11,12), (8,11), (10,13) 给出以上问题实例的解及求解过程 设计一个求解“活动方案”的算法，使得在方案中安排的所有活动都是相容的且活动数目最多。（18分）,求解过程：选一开始时间最小的