数据结构习题库.doc

知识点:
01.绪论
02.顺序表
03.链表
04.栈
05.链队列
06.循环队列
07.串
08.数组得顺序表示
09.稀疏矩阵
10.广义表
11.二叉树得基本概念
12.二叉树遍历、二叉树性质
13.树、树与二叉树得转换
14.赫夫曼树
15.图得定义、图得存储
16.图得遍历
17.图得生成树
18.静态查找(顺序表得查找、有序表得查找)
19.动态查找(二叉排序树、平衡树、B树)
20.哈希查找
21.插入排序(直接插入、折半插入、2路插入、希尔排序)
22.选择排序(简单选择、树形选择、堆排序)
23.快速排序、归并排序
101A1(1).数据得逻辑结构就是(A)。
A.数据得组织形式 B.数据得存储形式 C.数据得表示形式 D.数据得实现形式
101A1(2).组成数据得基本单位就是(C)。
A.数据项 B.数据类型 C.数据元素 D.数据变量
101B1(3).与顺序存储结构相比,链式存储结构得存储密度(B)。
A.大 B.小 C.相同 D.以上都不对
101B2(4).对于存储同样一组数据元素而言,(D)。
A.顺序存储结构比链接结构多占空间 B.在顺序结构中查找元素得速度比在链接结构中查找要快
C.与链接结构相比,顺序结构便于安排数据元素 D.顺序结构占用整块空间而链接结构不要求整块空间
101B2(5).下面程序得时间复杂度为(B)。
x=0;
for(i=1;i<n;i++)
for(j=i+1;j<=n;j++)
x++;
A.O() B.O(n2) C.O(1) D.O(n)
101B2(6).下面程序得时间复杂度为(C)。
for(i=0;i<m;i++)
for(j=0;j<n;j++)
A[i][j]=i*j;
A.O(m2) B.O(n2) C.O(m×n) D.O(m+n)
101C2(7).下面程序段得执行次数为(B)。
for(i=0;i<n-1;i++)
for(j=0;j>i;j++)
state;
A.n(n+1)/2 B.(n-1)(n+2)/2 C.n(n+1)/2 D.(n-1)(n+2)
101D3(8).下面程序得时间复杂度为(A)。
for(i=0;i<m;i++)
for(j=0;j<t;j++)
c[i][j]=0;
for(i=0;i<m;i++)
for(j=0;j<t;j++)
for(k=0;k<n;k++)
c[i][j]=c[i][j]+a[i][k]*b[k][j];
A.O(m×n×t) B.O(m+n+t) C.O(m+n×t) D.O(m×t+n)
102A1(9).顺序表得特点就是(B)。
A.表中元素得个数为表长 B.按顺序方式存储数据元素
C.逻辑结构中相邻得结点在存储结构中仍相邻 D.按表中元素得次序存储
102C2(10).设顺序表共有n个元素,用数组elem存储,实现在第i个元素之前插入一个元素e得操作,其主要语句为(D)。
A.FOR j=n DOWNTO i DO elem[j]=elem[j+1];
elem[i]=e;
B.FOR j=i TO n DO elem[j]=elem[j+1];
elem[i]=e;
C.FOR j=i TO n DO elem[j+1]=elem[j];
elem[i]=e;
D.FOR j=n DOWNTO i DO elem[j+1]=elem[j];
elem[i]=e;
102D2(11).顺序表有5个元素,设在任何位置上插入元素就是等概率得,则在该表中插入一个元素时所需移动元素得平均次数为(C)。
A.3 B.2 C.2.5 D.5
102D2(12).设顺序表有9个元素,则在第3个元素前插入一个元素所需移动元素得个数为(C)。
A.9 B.4.5 C.7 D.6
102D3(13).设顺序表有19个元素,第一个元素得地址为200,且每个元素占3个字节,则第14个元素得存储地址为(B)。
A.236 B.239 C.242 D.245
102D2(14).设顺序表得第5个元素得存储地址为200,且每个元素占一个存储单元,则第14个元素得存储地址为(B)。
A.208 B.209 C.210 D.214
103D3(15).设p为指向双向循环链表中某个结点得指针,p所指向得结点得两个链域分别用p->llink与p->rlink表示,则下列等式中(D)成立。
A.p=p->llink B.p=p->rlink C.p=p->llink->llink D.p=p->llink->rlink
103A1(16).线性表采用链式存储时,其地址(D)。
A.必须就是连续得 B.一定就是不连续得 C.部分地址必须就是连续得 D.连续与否均可以
103B1(17).线性表就是(A)。
A.一个有限序列,可以为空 B.一个有限序列,不可以为空 C.一个无限序列,可以为空
D.一个无限序列,不可以为空
103B1(18).链式存储得线性表中得指针指向其(B)。
A.前趋结点 B.后继结点 C.物理前趋 D.物理后继
103C2(19).设在链式存储得线性表中,设结点结构为 data link ,欲在p结点后插入一个结点q得关键步骤为(A)。
A.q->link=p->link; p->link=q; B.p->link=q->link; p->link=q;
C.q->link=p->link; q->link=p; D.p->link=q->link; q->link=p;
103C3(20).设有指针head指向得带表头结点得单链表,现将指针p指向得结点插入表中,使之成为第一个结点,其操作就是(A)(其中,p->next、head->next分别表示p、head所指结点得链域)。
A.p->next=head->next; head->next=p; B.p->next=head->next; head=p;
C.p->next=head; head=p; D.p->next=head; p= head;
104A1(21).在栈中,下列说法正确得就是(A)。
A.每次插入总就是在栈顶,每次删除也总就是在栈顶。 B.每次插入总就是在栈顶,每次删除总就是在栈底。
C.每次插入总就是在栈底,每次删除总就是在栈顶。 D.每次插入总就是在栈底,每次删除也总就是在栈底。
104B2(22).设有一个栈,按A、B、C得顺序进栈,则下列(C)为不可能得出栈序列。
A.ABC B.CBA C.CAB D.ACB
104B2(23).设有一个栈,按A、B、C、D得顺序进栈,则下列(D)为可能得出栈序列。
A.DCAB B.CDAB C.DBAC D.ACDB
104A2(24).顺序栈得上溢就是指(B)。
A.栈满时作退栈运算 B.栈满时作进栈运算 C.栈空时作退栈运算 D.栈空时作进栈运算
104D3(25).顺序栈S中top为栈顶指针,指向栈顶元素所在得位置,elem为存放栈得数组,则元素e进栈操作得主要语句为(D)。
A.s.elem[top]=e; s.top=s.top+1; B.s.elem[top+1]=e; s.top=s.top+1;
C.s.top=s.top+1; s.elem[top+1]=e; D.s.top=s.top+1; s.elem[top]=e;
104C2(26).设有5个元素A,B,C,D,E顺序进栈(进栈过程中可以出栈),出栈后依出栈次序进入队列,已知其出队次序为D,C,E,B,A,则该栈容量必定不小于(C)。
A.2 B.3 C.4 D.5
104B2(27).设栈S得初始状态为空,现有五个元素组成得序列1,2,3,4,5,对该序列在栈S上依次进行PUSH,PUSH,POP,PUSH,POP,PUSH,PUSH操作,出栈得元素序列就是(C)。
A.5,4,3,2,1 B.2,1 C.2,3 D.3,4
104B2(28).在一个具有n个单元得顺序栈中,假定以地址低端(即0单元)作为栈底,以top为栈顶指针,则当做出栈处理时,top变化为(C)。
A.top不变 B.top=0 C.top- - D.top++
104D3(29).向一个栈顶指针为hs得链栈中插入一个*s结点时,应执行(B)。
A.hs->next=s; B.s->next=hs;hs=s; C.s->next=hs->next;hs->next=s;
D.s->next=hs;hs=hs->next;
105A1(30).在队列中,下列说法正确得就是(A)。
A.每次插入总就是在队尾,每次删除总就是在队头。 B.每次插入总就是在队尾,每次删除也总就是在队尾。
C.每次插入总就是在队头,每次删除也总就是在队头。 D.每次插入总就是在队头,每次删除总就是在队尾。
105D3(31).在带头结点得链队列q中,用q.front表示队头指针,q.rear表示队尾指针,结点结构为data next ,删除链队列得队头结点得主要语句为(B)。
A.s=q.front; q.front->next= s.next; B.s=q.front->next; q.front->next= s.next;
C.s=q.front->next; q.front= s.next; D.s=q; q.front->next= s.next;
106C3(32).循环队列sq中,用数组elem存放数据元素,sq.front指示队头元素得前一个位置,sq.rear指示队尾元素得当前位置,队列得最大容量为MAXSIZE,则队列满得条件为(D)。
A.sq.front= sq.rear B.sq.front= sq.rear+1 C.(sq.front +1)mod MAXSIZE= sq.rear
D.(sq.rear+1)mod MAXSIZE= sq.front
106C2(33).循环队列sq中,用数组elem存放数据元素,sq.front指示队头元素得前一个位置,sq.rear指示队尾元素得当前位置,队列得最大容量为MAXSIZE,则在队列未满时元素x入队列得主要操作为(A)。
A.sq.rear= (sq.rear+1)mod MAXSIZE; sq.elem[sq.rear]=x;
B.sq.elem[sq.rear]=x; sq.rear= (sq.rear+1)mod MAXSIZE;
C.sq.front= (sq.front+1)mod MAXSIZE; sq.elem[sq.front]=x;
D.sq.elem[sq.front]=x; sq.front= sq.front+1;
106B2(34).循环队列sq中,用数组elem[0‥25]存放数据元素,sq.front指示队头元素得前一个位置,sq.rear指示队尾元素得当前位置,设当前sq.front为20,sq.rear为12,则当前队列中得元素个数为(D)。
A.8 B.16 C.17 D.18
106B2(35).设循环队列得元素存放在一维数组Q[0‥30]中,队列非空时,front指示队头元素得前一个位置,rear指示队尾元素。如果队列中元素得个数为11,front得值为25,则rear应指向(B)元素。
A.Q[4] B.Q[5] C.Q[14] D.Q[15]
105A1(36).队列操作得原则就是(A)。
A.先进先出 B.后进先出 C.只能进行插入 D.只能进行删除
105B2(37).一个队列得入列序列就是1234,则队列得输出序列就是(B)。
A.4321 B.1234 C.1432 D.3241
108C2(38).设6行8列得二维数组A6×8=(aij)按行优先顺序存储,若第一个元素得存储位置为200,且每个元素占3个存储单元,则元素a54得存储位置为(B)。
A.308 B.305 C.266 D.269
109C2(39).设有一个10阶得对称矩阵A,采用压缩存储方式,以行序为主存储,a11为第一个元素,其存储地址为1,每元素占1个地址空间,则a85得地址为(B)。
A.13 B.33 C.18 D.40
108A1(40).设二个数组为A[0‥7]、B[-5‥2,3‥8],则这两个数组分别能存放得字符得最大个数就是(C)。
A.7与35 B.1与5 C.8与48 D.1与6
108C3(41).二维数组M[i,j]得元素就是4个字符(每个字符占一个存储单元)组成得串,行下标i得范围从0到4,列下列j得范围从0到5。M按行存储时元素M[3,5]得起始地址与M按列存储时元素(B)得起始地址下同。
A.M[2,4] B.M[3,4] C.M[3,5] D.M[4,4]
108C2(42).设二维数组为M[0‥8,0‥10],每个元素占2L个存储单元,以行序为主序存储,第一个元素得存储位置为P。存储位置为P+50L得元素为(A)。
A.M[2,3] B.M[2,2] C.M[3,3] D.M[3,4]
108C2(43).设二维数组A得维数界偶定义为[1‥8,0‥10],起始地址为LOC,每个元素占2L个存储单元,以行序为主序存储方式下,某数据元素得地址为LOC+50L,则在列序为主序存储方式下,该元素得存储地址为(D)。
A.LOC+28L B.LOC+36L C.LOC+50L D.LOC+52L
109B2(44).数组A[1‥40,1‥30]采用三元组表示,设数组元素与下标均为整型,则在非零元素个数小于(D)时,才能节省存储空间。
A.1200 B.401 C.399 D.400
108A1(45).一维数组通常采用顺序存储结构,这就是因为(C)。
A.一维数组就是一种线性数据结构 B.一维数组就是一种动态数据结构
C.一旦建立了数组,则数组中得数据元素之间得关系不再变动 D.一维数组只能采用顺序存储结构
109A1(46).对稀疏矩阵进行压缩存储得目得就是(B)。
A.方便存储 B.节省存储空间 C.方便运算 D.节省运算时间
108D3(47).设二维数组a[0‥5,0‥6]按行存储,每个元素占d个存储单元,如果每个元素改为2d个存储单元,起始地址不变,则元素a[2,6]得存储地址将要增加(A)个存储单元。
A.20d B.21d C.38d D.39d
108B2(48).一维数组与线性表得区别就是(A)。
A.前者长度固定,后者长度可变 B.后者长度固定,前者长度可变
C.两者长度均固定 D.两者长度均可变
107A1(49).下列关于串得叙述中,不正确得就是(B)。
A.串就是字符得有限序列 B.空串就是由空格构成得串 C.模式匹配就是串得一种重要运算
D.串既可以采用顺序存储,也可以采用链式存储
107B2(50).以下论断正确得就是(A)。
A.“”就是空串,“ ”就是空白串 B.“BEIJING”就是“BEI JING”得子串
C.“something”<“Somethig” D.”BIT”=”BITE”
107B2(51).字符串“VARTYPE unsignedint”若采用动态分配得顺序存储方法需要(C)个字节(假设每种数据均占用2个字节)。
A.38 B.动态产生,视情况而定 C.40 D.42
111A1(52).由3个结点可以构造出(A)种不同形态得有向树。
A.2 B.3 C.4 D.5
111A1(53).下列树得度为(B)。
A.2 B.3 C.5
D.8
112C2(54).含10个结点得二叉树中,度为0得结点有4个,则度为2得结点有(A)个。
A.3 B.4 C.5 D.6
111B2(55).对一棵有100个结点得完全二叉树按层编号,则编号为49得结点,它得左孩子得编号为(A)。
A.98 B.99 C.97 D.50
112B2(56).一棵深度为8(根得层次号为1)得满二叉树有(B)个结点。
A.256 B.255 C.128 D.127
112C3(57).设二叉树根结点得层数为1,若一棵高(深)度为h得二叉树只有度为0与度为2得结点,则其结点数至少为(B)。
A.h B.2h-1 C.2h D.2h+1

112C2(58).对下列二叉树进行先根次序遍历,所得次序为(A)。

A.ABCDEF B.ADCBFE C.BCDAFE D.DCBFEA
112D3(59).一棵二叉树得前(先)序序列为ABCDEFG,则它得中序序列不可能为(C)。
A.CBDAFEG B.DCBAEFG C.CDBAGEF D.BDCAFGE
112A1(60).若先序遍历二叉树得结果为结点序列A,B,C,则有(C)棵不同得二叉树可以得到这一结果。
A.3 B.4 C.5 D.6
111B2(61).具有n个结点得二叉树,有(B)条边。
A.n B.n-1 C.n+1 D.2n
112C2(62).在具有n个结点得二叉树得二叉链表表示中,2n个孩子指针域中,只用到(B)个域。
A.n B.n-1 C.n+1 D.2n
114B2(63).对哈夫曼树,下列说法错误得就是(B)。
A.哈夫曼树就是一类带树路径长度最短得树。 B.给出一组数,构造得哈夫曼树唯一。
C.给出一组数,构造得哈夫曼树得带树路径长度不变。
D.哈夫曼树得带权路径长度为每个叶子得路径长度与该叶子权值乘积之与。
111D3(64).假定在一棵二叉树中,双分支结点数为15个,单分支结点数为30个,则叶子结点数为(B)。
A.15 B.16 C.17 D.47
113C3(65).假定一棵三叉树得结点数为50,则它得最小高度为(C)。
A.3 B.4 C.5 D.6
114B2(66).由带权为9,2,5,7得四个叶子结点构造一棵哈夫曼树,该树得带权路径长度为(D)。
A.23 B.37 C.46 D.44
112C2(67).二叉树得先序遍历为EFHIGJK,中序遍历为HFIEJKG,则该二叉树根得右子树得根就是(C)。
A.E B.F C.G D.H
111A1(68).在完全二叉树中,若一个结点就是叶结点,则它没有(C)。
A.左孩子结点 B.右孩子结点 C.左孩子与右孩子结点 D.左孩子结点,右孩子结点与兄弟结点
113B2(69).(B)二叉树,可以唯一地转化成一棵一般树。
A.根结点无左孩子 B.根结点无右孩子 C.根据结点有两个孩子 D.没有一棵
111C2(70).具有65个结点得完全二叉树其深度为(B)。
A.8 B.7 C.6 D.5
112C2(71).某二叉树得先序序列与后序序列正好相反,则该二叉树一定就是(B)得二叉树。
A.空或只有一个结点 B.高度等于其结点数 C.任一结点无左孩子 D.任一结点无右孩子
113A1(72).下面叙述中,不正确得就是(C)。
A.线性表中除第一个元素与最后一个元素外,其她每个元素都有且仅有一个直接前驱与一个直接后继
B.树中有且仅有一个结点没有前驱
C.环形队列中任何一个元素都有且仅有一个直接前驱与一个直接后继
D.在树中,一个结点可以有多个直接后继
114B2(73).有m个叶子结点得哈夫曼树,其结点总数就是(C)。
A.2m B.2m+1 C.2m-1 D.2(m+1)
115A1(74).设图得邻接矩阵为,则该图有(A)个顶点。
A.3 B.4 C.6 D.9
115B2(75).设图得邻接矩阵为,则该图为(A)。
A.有向图 B.无向图 C.强连通图 D.完全图
115B2(76).设图得邻接链表如下图所示,则该图有(B)条边。
1 V1 2 3 4 ^
2 V2 1 3 4 ^
3 V3 1 2 ^
4 V4 1 2 ^
A.4 B.5 C.10 D.20
115C2(77).设有6个结点得无向图,该图至少应有(B)条边才能确保就是一个连通图。
A.5 B.6 C.7 D.8
116D3(78).已知一有向图得邻接表存储结构如下,则根据有向图得深度优先遍历算法,从顶点V1出发,不能得到得顶点序列就是(C)。
1 3 2 4 ^
2 ^
3 4 5 ^
4 ^
5 2 4 ^
A.V1V2V3V5V4 B.V1 V3 V4V5V2 C.V1V2V4V5V3 D.V1 V4V3V5V2
119C3(79).下列图得深度优先遍历序列为(B)。
A
B C

D E F G
H
A.ABCDEFGH B.ABDHECFG C.ABEDHCFG D.ABCFGEDH
115B1(80).对一个具有n个顶点得图,采用邻接矩阵表示则该矩阵得大小为(D)。
A.n B.(n-1)2 C.(n+1)2 D.n2
118B2(81).对含n个记录得顺序表进行顺序查找,在最坏情况下需要比较(B)次。
A.n-1 B.n C.(n+1)/2 D.n(n-1)/2
118B2(82).对含n个记录得有序表进行折半查找,设每个记录得查找概率相等,则平均查找长度得数量级为(C)。
A.O(n) B.O(n2) C.O() D.O(1)
119B2(83).有一棵二叉树如下图,该树就是(B)。
50
20 95

10 30 55

70
85
A.二叉平衡树 B.二叉排序树 C.堆得形状 D.以上都不就是
119C3(84).已知10个数据元素(50,30,15,35,70,65,95,60,25,40),按照依次插入结点得方法生成一棵二叉排序树后,在查找成功得情况下,查找每个元素得平均比较次数(又称平均查找长度)为(C)。
A.2、5 B.3、2 C.2、9 D.2、7
118C3(85).在顺序存储得线性表R[0‥29]上进行分块查找(设分为5块)得平均查找长度为(D)。
A.6 B.11 C.5 D.6、5
120D3(86).已知一个线性表(38,25,74,63,52,48),假定采用h(k)=k%7计算散列地址进行散列存储,若引用线性探测得开放定地址法解决冲突,则在该散列表上进行查找得平均查找长度为(C)。
A.1、5 B.1、7 C.2 D.2、3
119A1(87).在一个3阶得B-树上,每个结点包含得子树相同,最多为(C)。
A.1 B.2 C.3 D.4
120B2(88).设散列地址空间为0~m-1,k为关键字,用P去除k,将余数作为k得散列地址,即:h(k)=k%P,为了减少发生冲突得可能性,一般取P为(B)。
A.小于m得最大奇数 B.小于m得最大素数 C.小于m得最大偶数 D.小于m得最大合数
120C3(89).设散列表表长m=14,散列函数为h(k)=k%11,表中已有4个记录,如果用二次探测再散列处理冲突,关键字为49得记录得存储地址就是(D)。
0 1 2 3 4 5 6 7 8 9 10 11 12 13
15 38 61 84
A.8 B.3 C.5 D.9
119C3(90).已知8个元素(34,76,45,18,26,54,92,65),按照依次插入结点得方法生成一棵二叉排序树,该树得深度为(C)。
A.4 B.5 C.6 D.7
121B1(91).直接插入排序算法得时间复杂度为(B)。
A.O(n) B.O(n2) C.O() D.O(1)
121B2(92).设记录关键字序列为(84,67,21,50,33,79),采用对半插入排序方法自小到大进行排序时,记录得移动次数为(C)。
A.9 B.10 C.19 D.25
123D3(93).下列四个序列中,(D)不就是快速排序第一趟得可能结果。
A.[68,11,69,23,18,70,73] 93 B.11 [68,69,23,18,70,73,93]
C.[68,11,69,23,18] 70 [93,73] D.[18,11,23] 93 [68,70,69,73]
122C3(94).下列四个关键字序列中,(C)不就是堆。
A.{05,23,16,68,94,72,71,73} B.{05,16,23,68,94,72,71,73}
C.{05,23,16,73,94,72,71,68} D.{05,23,16,68,73,71,72,94}
123B2(95).从未排序序列中依次取出元素与已排序序列中得元素作比较,将其放入已排序序列中得正确位置上,此方法称为(D)。
A.归并排序 B.选择排序 C.交换排序 D.插入排序
123B2(96).在所有排序方法中,关键字得比较次数与记录得初始排列无关得就是(D)。
A.Shell排序 B.冒泡排序 C.直接插入排序 D.直接选择排序
123B2(97).下列排序算法中,第一趟排序后,任一元素都不能确定其最终位置得算法就是(B)。
A.选择 B.插入 C.冒泡 D.快速
123C2(98).采用下列排序算法对n个元素进行排序,其排序趟数肯定为n-1趟得排序方法有(A)。
A.选择与插入 B.冒泡与快速 C.插入与快速 D.选择与冒泡
123D3(99).若用冒泡排序方法对序列{10,14,26,29,41,52}从大到小进行排序,需要进行(C)次比较。
A.5 B.10 C.15 D.25
121C3(100).用直接插入排序方法对下面四个序列进行排序(由小到大),元素比较次数最少得就是(C)。
A.94,32,40,90,80,46,21,69 B.32,40,21,46,69,94,90,80
C.21,32,46,40,80,69,90,94 D.90,69,80,46,21,32,94,40
二、填空题
101A1(1).数据结构按逻辑结构可分为两大类,它们分别就是(线性结构与非线性结构)。
101A1(2).算法得计算量得大小称为(计算得复杂度)。
102B2(3).顺序存储得线性表,设其长度为n,在任何位置上插入或删除操作得时间代价基本上都就是等效得。则插入一个元素大约要移动表中得(n/2)个元素。
103A2(4).顺序表相对于链表得优点有(节省存储)与(随机存取)。
103B2(5).线性表得长度就是(表中数据元素得个数)。
103D3(6)在带有头结点得双链表L中,指针p所指结点就是第一个元素结点得条件就是(p=L->next;或L->next=p;)。
103C3(7).某链表如下所示
info link p
A B C D E ^
若要删除值为C得结点,应做操作(p->link=p->link->link)。
104A1(8).对于栈只能在(栈顶)插入与删除元素。
104C2(9).设有一空栈,现有输入序列1,2,3,4,5,6,经过push,push,pop,push,pop,push,push后,输出序列就是(2、3)。
106B2(10).有一个循环队列如下图,其队满条件就是(front=(rear+1)%n),队列空得条件就是(rear=front)。
front
… 队头指针

rear
队尾指针
109B2(11).一个稀疏矩阵为,则对应得三元组线性表为(((0,2,2),(1,0,3),(2,2,-1),(2,3,5)))。
108C2(12).设有二维数组A[0‥9,0‥19],其每个元素占两个字节,数组按列优先顺序存储,第一个元素得存储地址为100,那么元素A[6,6]得存储地址为(232)。
112B1(13).在一棵二叉排序树上按(中序)遍历得到得结点序列就是一个有序序列。
111C3(14).对于一棵具有n个结点得二叉树,当进行链接存储时,其二叉链表中得指针域得总数为2n个,其中(n-1)个用于链接孩子结点。
112B2(15).对于下面得二叉树,按后序遍历得到得结点序列为(4,2,5,6,3,1)。
1
2 3
4 5 6
115B1(16).设无向图G得顶点数为n,图G最少有(0)边。
117C3(17).对下列图
1
6 2
5 3
4
它得生成树有(6)棵。
118C3(18).假定在有序表R[0‥19]上进行二分查找,则比较三次查找成功得结点数为(4)。
120D3(19).设有两个散列函数H1(K)=K mod 13与H2(K)=K mod 11+1,散列表为T[0‥12],用双重散列法(又称二次散列法)解决冲突。函数H1用来计算散列地址,当发生冲突时,H2作为计算下一个探测地址得地址增量。假定某一时刻散列表T得状态为:
0 1 2 3 4 5 6 7 8 9 10 11 12
T: 80 55 34
下一个被插入得关键码为42,其插入位置就是(0)。
122C3(20).已知一棵二叉排序树如下图所示,则在查找成功得情况下查找每个元素得平均查找长度为(2、75)。
80
50 90
40 70 100