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

　选择题： 1. 在建立某高校网站时，为方便浏览，建立了校 -系-教研室的链接，则这数据结构属于（ ） A ．线性结构 ????? B ．树结构 ??????? C ．图结构 ????? D ．集合结构 2. 设单链表的每个结点有两个域 :element 和link，在指针p所指示的结点之后插入新结点*s的操作是（ ） A．s-link=p;p-link=s; ??????????? B．s-link=p-link;p-link=s; C．s-link=p-link;p=s; ??????????? D．p-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）%MAXQSIZE＝＝Q.front B)?????Q.rear＝＝Q.front C)????（Q. front +1）%MAXQSIZE＝＝Q. rear D) Q.rear＋Q.front＝＝MAXQSIZE 　判断题： 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数组_____________________ 综合练习二 北师大06年研究生试题 一、翻译题　　二、简答题（考背诵）略 三、判断题，若正确，请画对号，否则画叉，并说明理由（２０分） 、图Ｇ的一棵最小生成树的代价未必小于Ｇ的其他任何一棵生成树的代价。（　） 、二唯数组Ａ的每个元素是由６个字符组成的串，其行下标i=0、１、２……８，列下标j=１、２……10，若Ａ按行先存储，元素A[8,5]的起始地址与Ａ按列先存储时的元素A[5,10]的起始地址相同（设每个字符占一个字节）。（　）　 、用邻接矩阵Ａ表示图，判定任意两个节点Vi和Vj之间是否有长度为m的路径相连，则只要检查Am的第i行第j列的元素是否为０即可（　） 、已知待排序的n个元素可分为n/k组，每个组内包含k个元素，且任一组内的各元素均分别大于前一组内的所有元素和小于后一组内的所有元素，若采用基于比较的排序，其时间下界应为O(nlog2K)（　） 四、填空（每题６分，共30分） 、下列程序的功能是按照右侧的格式输出的６行杨晖三角形，请填空将程序补充完整。 main() { int y[7][7],n,m; for(n=1;n7;n++) { _______=1; y[n][1]=1; } for(n=3;n7;n++) for(m=2;mn;m++) y[n][m]=_____________________ for(n=1;n7;n++){ for(m=1;m=n;m++) printf(%4d,________); printf(\n); } } 、具有1/2(n-1)条边的无向图称为_________，简称