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

选择题：

在建立某高校网站时，为方便浏览，建立了校-系-教研室的链接则这数据结构属于（

）A

．线性结构 B

．树结构 C

．图结构 D

．集合结构

设单链表的每个结点有两个域:element和link，在指针p所指示结点之后插入新结点*s的操作是（

）A．s->link=p;p->link=s;C．s->link=p->link;p=s;B．s->link=p->link;p->link=sD．p->link=s;s->link=p;3.元素序列(A，B，C，D，E)顺序进栈，每个元素必须进栈

一次，进栈后可立即出栈，也可在栈中停留一段时间后再出栈，则下面哪个序列不能得到（

）A

．

A,B,C,D,EC.

B,E,D,C,AB

．

E,D,C,B,AD.

B,E,C,D,A4.对一个已经存在的二叉排序树遍历，能够得到非递减序列的遍历是（

）A）

先序遍历

B）中序遍历

C）

后序遍历

D）

层遍历5.在循环队列中，判断队列满的条件是（

）（Q.rear+1）%MAXQSIZE＝＝Q.frontQ.rear＝＝Q.front（Q.

front

+1）%MAXQSIZE＝＝Q.

rearQ.rear＋Q.front＝＝MAXQSIZE判断题：

哈夫曼树的根结点的权值等于所有叶结点（外结点）的权值之和。一个无向连通图的生成树是一个极大的连通子图。

用堆排序时，若想得到一个非递减顺序表，则构造堆的堆顶元素应该最小选择排序是稳定的排序算法一个顶点数为n的无向连通图至少由n-1条边D=(A,

C,

B);三：填空题，请在答题纸上写下结果（共6题，每题5分）１、数据结构由四类基本结构，分别是

集合

、线性结构

、树形结构、_图形结构

。２、已知树t的先根次序访问序列为GFKDAIEBCHJ树t的后根次序访问序列为：

DIAEKFCJHBG请判断树t的度为

3

、层为5

。３、已知广义表：A=(

)；B=(e);

C=(a,(b,c,d));则GetHead(GetTail(D)=

C

４、图的遍历方法有深度优先和_广度优先５、对于关键字序列{46

,

58

,15

，

45

，

90

，

18

，

10

，

62}

，其快速排序第一趟的结果是_1_0

1_8

1_5_5

4_5

4_4_6

9_0

5_8

6_2_６、给出字符串“ａｂａｃａｂａａａｄ”在KMP算法中的next数0组1＿12＿12＿34＿22＿＿＿＿＿和nextval数0组102010422综合练习二北师大06年研究生试题一、翻译题

二、简答题（考背诵）略三、判断题，若正确，请画对号，否则画叉，并说明理由（２０分）·

、图Ｇ的一棵最小生成树的代价未必小于Ｇ的其他任何一棵生成树的代价。（

）·

、二唯数组Ａ的每个元素是由６个字符组成的串，其行下标i=0、２……８，列下标j=１、２……10，若Ａ按行先存储，元素A[8,5起始地址与Ａ按列先存储时的元素A[5,10]的起始地址相同（设每个字符占一个字节）。（

）·、用邻接矩阵Ａ表示图，判定任意两个节点Vi和Vj之间是否有长度为m的路径相连，则只要检查Am的第i行第j列的元素是否为０即可（

）·、已知待排序的n个元素可分为n/k组，每个组内包含k个元素，且任一组内的各元素均分别大于前一组内的所有元素和小于后

一组内的所有元素，若采用基于比较的排序，其时间下界应为O(nlog2K)（

）最小生成树不一定唯一。8*10+(5-1)!=(10-1)*9+5举例：1

2

3，画出矩阵组内用快速排序，快速排序的复杂度为klogk四、填空（每题６分，共30分）·

、下列程序的功能是按照右侧的格式输出的６行杨晖三角形，请填空将程序补充完整。main(){

int

y[7][7],n,m;·

for(n=1;n<7;n++)

{=1;

y[n][1]=11111211

3

3

1;

}14641y[1][n]

·

for(n=3;n<7;n++)·

for(m=2;m<n;m++)15

10

10

5

1·

y[n][ym[]n=-1][m]+y[n-1][m-1]

·

for(n=1;n<7;n++){·

for(m=1;m<=n;m++)·

printf("Y%[4nd]"[,m] );·

printf("\n");·}·}

、具有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;s[i]!=‘\0’;i++)switch

(s[j]);t[j++]=‘n’;;t[j++]=‘t’;brea]=s[i];break;}‘]\=\’‘]\=\’{case’\n’J+:+t[

case’\n’J+:+t[

default:tJ[++t[j]=‘\_0_’

;}五：应用题（16分）已知深度为h的二叉树采用顺序存储结构已经存放于数组BT[1:2h-1]中，请写算法，产生该二叉树的二叉链表结构。详见excersize-changetree.c

(用递归)·

、依据所示无向图，分别用prim和kruskal算法，画最小生成树普里姆算法：从一个顶点开始生成树，每次选与这个树相关连的最小的边，等树长成能涵盖所有顶点，即可。详见下图克鲁斯卡尔：每次找一条权值最小的边，如果这个边连接两个不同的连通分量，则添加该边。反复执行到所有顶点都连通为止。详细过程不再给出，请自行作出·、设有n个活动需要演讲会场，而在同一时间内会场只能分配给其中一个活动。如果用Ｅ表示活动集合，E={1,2……n}，每个活动i使用会场有一个起止时间(si,fi)，其中si<fi。如果两个活和j的时间段不相交，则称活动i与活动j是相容的，前后活动的时间边界重合不算相交。给定规模为10的问题实例E如下·

{(1,3),

(0,5),

(7,10),

(6,7),

(3,6),

(8,9),

(1,2),

(11,12),(10,13)}求·解给过出程以：上选问一题实开例始的时解间及最求小解过的程活动作第一个活动，选它的后继活动，使后继活动的开始时间大于且最接近其终止时间，依次选后继直到没有活动满足