数据结构（本）期末综合练习

数据结构（本）期末综合练习

2017年5月

综合练习一

一、单项选择题

1.设有头指针为head的带有头结点的非空单向循环链表，指针p指向其尾结点，要删除

头结点，并使其仍为单向循环链表，则可利用下述语句head=head->next;（）,,

A.p=head;B.p=NULL;C.p->next=head;D.head=p;

2.在一个单链表中p指向结点a,q指向结点a的直接后继结点b,要删除结点b,可执

行（）。

A.p->next=q->next;B.p=q->next;

C.p->next=q;D.p->next=q;

3.以下说法不正确的是

A.线性表的链式存储结构不必占用连续的存储空间

B.一种逻辑结构只能有唯一的存储结构

C.一种逻辑结构可以有不同的存储结构

D.线性表的顺序存储结构必须占用连续的存储空间

4.在一个单向链表中，在p所指结点之后插入一个s所指的结点时，可执行（）；和

p->next=s;

A.p=s;B.p->next=s->next;

C.p=s->next;D.s->next=p->next;

5.把数据存储到计算机中，并具体体现（）称为物理结构。

A.数据元素间的逻辑关系

B.数据的处理方法

C.数据的性质

D.数据的运算

6.设有一个长度为23的顺序表，要删除第8个元素需移动元素的个数为（）。

A.16B.14C.15D.13

7.链表所具备的特点之一是（）。

A.可以随机访问任一结点B.需要占用连续的存储空间

C.插入元素的操作不需要移动元素D.删除元素的操作需要移动元素

8.设一棵有8个叶结点的二叉树，度数为1的结点有3个，则该树共有（）

个结点。

A.20B.18C.17D.16

9.图状结构中数据元素的位置之间存在（）的关系。

A.一对一B.多对多

C.一对多D.每一个元素都有一个直接前驱和一个直接后继

10.一棵具有5层的完全二叉树，最后一层有4个结点，则该树总共有（）个结点。

A.14B.15C.19D.18

11.元素15,9,11,13按顺序依次进栈，则该栈的不可能输出序列是（）

（进栈出栈可以交替进行）。

A.13,11,9,15B.15,9,11,13

C.13,11,15,9D.9,15,13,11

12.设主串为“FABcCDABcdEFaBc"，以下模式串能与主串成功匹配的是（)o

A.EFaBcB.ABCdE

C.DABCCD.FAbcC

13.设有一个14阶的对称矩阵A（第一个元素为采用压缩存储的方式，将其下三

角部分以行序为主序存储到一维数组B中（数组下标从1开始），则矩阵中元素a.g在

一维数组B中的下标是（)o

A.9B.10C.11D.8

14.元素111,113,115,117按顺序依次进栈,则该栈的不可能输出序列是（）（进

栈出栈可以交替进行）。

A.117,115,113,111B.111,113,115,117

C.113,111,117,115D.117,115,111,113

15.在一棵二叉树中,若编号为8的结点存在右孩子，则右孩子的顺序编号为（

A.18B.16C.15D.17

16.以下说法不正确的是（）o

A.栈和队列都是线性结构B.栈的特点是后进先出

C.栈和队列的特点都是先进后出D.队列的特点是先进先出

17.设一棵哈夫曼树共有14个非叶结点，则该树总共有（）个结点。

A.29B.27C.30D.28

18.设有一个15阶的对称矩阵A（第一个元素为采用压缩存储的方式，将其下三

角部分以行序为主序存储到一维数组B中（数组下标从1开始），则矩阵中元素a」,2

在一维数组B中的下标是（）。

A.9B.8C.7D.10

19.如图1所示的一个图，若从顶点a出发，按深度优先搜索法进行遍历，则可能得

到的一种顶点序列为（）o

A.abecdfB.acfebdC.aebcfdD.aedbfc

图1

20.如图2所示的一个图，若从顶点a出发，按深度优先搜索法进行遍历，则可能

得到的一种顶点序列为（）o

A.acedbfB.acebfdC.aebcfdD.aedfcb

二、填空题

1.队列的特点之一是：元素进、出队的次序是:先进。

2.序列13』1,14,12,17,15,采用冒泡排序算法，经一趟冒泡后,序列的结果是o

3.结构中，数据元素间存在一对多的关系。

4.对16个元素的序列用冒泡排法进行排序，通常需要进行_____趟冒泡。

5.对稀疏矩阵进行压缩存储，矩阵中每个非零元素对应的三元组包括该元素的

三项信息是o

6.对9个元素的一组记录(58,35,93,20,12,78,56,41,79)进行直接插入排

序(由小到大排序)，当把第7个记录56插入有序表，为寻找插入位置需比较

______次。

7.在对11个记录的序列(12,35,9,7,2,11,56,95,37,58,60)进行直接插入排序时，当把

第6个记录11插入到有序表时，为寻找插入位置，元素间需比较次。(由

小到大排列)

8.结构中的数据元素存在一对多的关系称为结构。

9.哈希函数是记录关键字的值与该记录之间所构造的对应关系。

10.设有一棵深度为5的完全二叉树，第5层上有3个结点，该树共有个结点。

(根所在结点为第1层)

11.20个元素进行冒泡法排序，通常需要进行19趟冒泡，其中第10趟冒泡共需要进行

次元素间的比较.

12.一棵二叉树中每一个非叶结点的度数都为2,共有10个非叶结点，则该树共有

____个结点。

13.一棵有19个结点的二叉树，采用链式结构存储，该树结构中有个指针

域为空。

14.序列3,1,7,18,6,9,13,12经一趟归并排序的结果为。

15.中序遍历一棵树可得到一个有序序列。

16.一棵有16个叶结点的哈夫曼树，则该树共有个非叶结点。

17.二叉排序树插入操作中，新插入的结点总是以树的结点被插入的

18.遍历二叉排序树可得到一个有序序列。

19.广义表的(a,(d,a,b),h,(e,((i,j),k)))深度是。

20.广义表(f,h,(a,b,d,c),d,e,((i,j),k))的长度是。

21.序列4,2,5,3,8,6,7,9,采用归并排序算法(升序),经一趟归并后，序列的结果

22.广义表的(h,c,g,a,(a,b),d,e,((i,j),k))深度是。

23.字符串al="teijing",a2="tef",a3="teifang",a4="tefi"最小的

是o

24.设有串pl="ABADF"，P2="ABAFD"，P3="ABADFA”P4="ABAF”，四个串中最

小的是•

三、综合题

1.设查找表为

序号1234567891011

序列4121819375565778586117

(1)画出对上述查找表进行折半查找所对应的判定树(树中结点用下标表示)

(2)说明成功查找到元素86需要经过多少次比较？

(3)求在等概率条件下，成功查找的平均比较次数？

2.(1)设有数据集合{50,39,17,83,111,14,65,13,91,102,49},依次取

集合中各数据构造一棵二叉排序树。

(2)一组记录的关键字序列为(6,9,7,4,5,8),利用堆排序(堆顶元素

是最小元素)的方法建立初始堆。(要求用完全二叉树表示)

3.

(1)一组记录的关键字序列为(26,59,36,18,20,25),给出利用堆排序(堆顶

元素是最小元素)的方法建立的初始堆(要求以完全二叉树描述)。

(2)对关键字序列(26,59,36,18,20,64)采用快速排序，给出以第一个关键字为分割

元素，经过一次划分后的结果。

4.(1)如下表为一个长度为10的有序表，给出按折半查找对该表进行查找的判定树

(2)按折半查找对该表进行查找，求在等概率情况下查找成功的平均比较次数。

为了成功查找72，给出元素的比较次数。

序号12345678910

序列23493918256072845559

5.(1)以1,2,3,6,7,8作为叶结点的权，构造一棵哈夫曼树

(2)给出具有相应权重值的叶结点的哈夫曼编码。

四、程序填空题

1.以下函数在a[0]到a[n-l]中，用折半查找算法查找关键字等于k的记录，查找成功返回

该记录的下标，失败时返回-1,完成程序中的空格

typcdcfstruct

{intkey;

}NODE;

intBinaty_Search(NODEa[],intn,intk)

intlow,mid,high;

low=O;

high=n-1;

while((1))

mid二(⑵)

if(a[mid].key==k)

return⑶

elseif((4))

low=mid+1;

else(5)；

return-1

2.设线性表以不带头结点的单向链表存储，链表头指针为head,以下程序的功能是

输出链表中各结点中的数据域data。完成程序中空格部分。

#defineNULL0

voidmain()

{NODE*head,*p;

p=head;/*p为工作指针*/

do

{printfC%d\n,\⑴):

⑵二

}whilef(3));

3.以下程序是前序遍历二叉树的递归算法的程序，完成程序中空格部分(树结构中左、

右指针域分别为left和right,数据域data为字符型，BT指向根结点)。

voidInorder(structBTreeNode*BT)

(

if(BT!=NULL){

⑴；

⑵；

Inorder(BT->right);}

)

利用上述程序对右图进行前序遍历，结果是⑶；

4.以下程序是后序遍历二叉树的递归算法的程序，完成程序中空格部分(树结构中左、

右指针域分别为left和right,数据域data为字符型，BT指向根结点)。完成程序中

空格部分。

voidInorder(structBTreeNode*BT)

(

if(BT!=NULL){

Inorder(BT->left);

⑴

⑵

5.顺序查找算法如下，完成程序中空格部分。

intsearch(NODEa[],intn,intk)

/*在a[0],a[l]…中查找关键字等于k的记录,查找成功返回记录的下标，失

败时返回-1*/

{inti=0;

while(i<n&&a[i].key(1))

⑵

if(⑶)

returni;

elsereturn-1;

综合练习一答案

一、单项选择题

1.C2,A3.B4.D5.A6.C7.C8.B9.B10.C11.C

12.A13.A14.D15.D16.C17.A18.B19.D20.B

二、填空题

1.先出

2.11,13,12,14,15,17

3.树型

4.15

5.行下标列下标数组元素

6.4次

7.3

8.树形

9.存储位置

10.18

11.10

12.21

13.20

14.1,3,7,18,6,9,12,13

15.二叉排序树

16.15

17.叶

18.中序

19.4

20.6

21.2,4,3,5,6,8,7,9

22.3

23.a2

24.Pl

三、综合题

1.

(1)55

1885

4196586

123777117

(2)3次

(3)平均查找长度=(1+2*2+3*4+4*4)/11=3

图5

⑵4,5,7,9,6,8

图6

(1)18,20,25,59,26,36

图7

(2)20,18,26,36,59,64

图8

⑵(1+2*2+3*4+4*3)/10=29/104次

5.(1)

图9

(2)

10000

20001

3001

601

710

811

四、程序填空题

1.(1)low<=high

(2)(low+high)/2

(3)mid;

(4)a[mid].key<k

(5)high=mid-l;

2.

(1)p->data

(2)p=p->next

(3)p!=NULL

3.

(1)printf(,BT->data)

(2)Inorder(BT->left)

(3)abdfec

4.

(1)Inorder(BT->right)

(2)printf(“枇”，BT->data)

(1)!=k

⑵i++；

(3)a[i].key==k

综合练习二

一、单项选择题

1.设头指针为head的非空的单向循环链表，指针p指向尾结点，则满足表达式（）

为真。

A.p->next==NULLB.p==NULLC.p->next==headD.p==head

2.数据的存储结构包括数据元素的表示和（）。

A.数据处理的方法C.相关算法

D.数据元素的类型D.数据元素间的关系的表示

3.一种逻辑结构（）。

A.可以有不同的存储结构B.只能有唯一的存储结构

C.是指某一种数据元素之间的存储关系D.是指某一种数据元素的性质

4.在一个头指针为head的单向链表中，p指向尾结点，要使该链表成为单向循环链表

可执行（

A.p=head->next;B.head->next=p;

C.head->next=p->next;D.p->next=head;

5.链表所具备的特点之一是（

A.可以随机访问任一结点B.占用连续的存储空间

C.插入删除元素的操作不需要移动元素结点D.可以通过下标对链表进行直接访问

6.元素111,113,115,117按顺序依次进栈,则该栈的不可能输出序列是（）（进

栈出栈可以交替进行）。

A.117,115,113,111B.111,113,115,117

C.117,115,111,113D.113,111,117,115

7.线性结构中数据元素的位置之间存在（）的关系。

A.一对一B.一对多

C.多对多D.每一个元素都有一个直接前驱和一个直接后继

8.以下说法正确的是（）。

A.栈的特点是先进后出

B.栈的特点是先进先出

C.队列的特点是先进后出

D.栈和队列的特点都是先进后出

9.在一个单向链表中p所指结点之后插入一个s所指的结点时，可执行（）。

A.p->next=s;s->next=p->nextB.p->next=s->next;

C.p=s->nextD.s->next=p->next;p->next=s;

10.设有一个20阶的对称矩阵A（第一个元素为ai,i）,采用压缩存储的方式，将其下三

角部分以行序为主序存储到一维数组B中（数组下标从1开始），则矩阵中元素S6.2

在一维数组B中的下标是（）。

A.24B.17C.16D.23

11.元素11,13,15,17按顺序依次进栈，则该栈的不可能输出序列是（）

（进栈出栈可以交替进行）。

A.17,15,13,11B.11,13,15,17

C.17,15,11,13D.13,11,17,15

12.设一棵有2n+l个结点的二叉树，除叶结点外每个结点度数都为2,则该树共有（）

个叶结点。

A.nB.n+1C.n+2D.n-1

13.设有一个20阶的对称矩阵A（第一个元素为ai,D,采用压缩存储的方式，将其下三角

部分以行序为主序存储到一维数组B中（数组下标从1开始），则矩阵中元素a.%2在一

维数组B中的下标是（）。

A.11B.12C.13D.10

14.已知如图1所示的一个图，若从顶点a出发，按广度优先搜索法进行遍历，则可能

得到的一种顶点序列为（）。

A.abecdfB.aecbdfC.aebcfdD.aedfcb

15.设一棵哈夫曼树共有11个非叶结点，则该树有（）个叶结点。

A.22B.10C.11D.12

16.线性表以（）方式存储，能进行折半查找。

A.关键字有序的顺序B.顺序C.链接D.二叉树

17.一棵具有38个结点的完全二叉树，最后一层有（）个结点。

A.7B.5C.6D.8

18.一棵具有38个结点的完全二叉树，最后一层有（）个结点。

A.7B.5C.6D.8

19.已知如图2所示的一个图，若从顶点a出发，按深度优先搜索法进行遍历，则可能得

到的一种顶点序列为（）.

A.abecdfB.acfebdC.aebcfdD.aedfcb

20.对一个栈顶指针为top的链栈进行出栈操作，用变量e保存栈顶元素的值，则执行

()。

A.e=top->next;top->data=e;B.top=top->next;e=top->data;

C.e=top->data;top=top->next;D.top=top->next;e=data;

二、填空题

1.字符串al="BEIJING",a2="BEF",a3="BEFANG",a4="BEI”最小的

是。

2.数组a经初始化chara[]="English”;a[7]中存放的是。

3.把数据存储到计算机中，并具体体现数据元素间的逻辑结构称为。

4.设有串pl="ABADF"，P2="ABAFD"，P3="ABADFA"P4="ABAF”，四个串中最大的是

5.设有一个长度为22的顺序表，要删除第8个元素需移动元素的个数为。

6.在一棵二叉树中，若编号为i的结点存在右孩子，则右孩子的顺序编号为。

7.在一棵二叉树中，若编号为i的结点存在左孩子，则左孩子的顺序编号为。

8.设有一个长度为20的顺序表，要插入一个元素，并作为第8个元素，需移动元素的个

数为。

9.设一棵有n个叶结点的二叉树，除叶结点外每个结点度数都为2,则该树共有

________个结点。

10.结构中的数据元素存在多对多的关系称为结构。

11.在对一组序列(45,29,87/2,6,63,55,37,78)进行直接插入排序时，当把第8个记录37插

入到有序表时，为寻找插入位置需比较次。(由小到大排序)

12.设有一棵深度为4的完全二叉树，第四层上有5个结点，该树共有个结点。

(根所在结点为第1层)

13.n个元素进行冒泡法排序，通常需要进行_______趟冒泡。

14.一棵二叉树中有n个非叶结点，每一个非叶结点的度数都为2,则该树共有

个叶结点。

15.一棵有21个结点的哈夫曼树，该树中有个叶结点。

16.在对一组记录(55,39,97,22,16,73,65,47,88)进行直接插入排序时，当把第7个记录65插

入到有序表时，为寻找插入位置需比较次。(由小到大排序

17.遍历二叉排序树可得到一个有序序列。

18.n个元素进行冒泡法排序，第j趟冒泡要进行次元素间的比较。

19.广义表(a,(a,b),d,e,((i,j),k))的长度是。

20.一棵有n个叶结点的哈夫曼树，则该树共有个结点。

21.广义表的(a,(a,b),d,e,((i,j),k))深度是。

22.中序遍历可得到一个有序序列。

23.序列14,12,15,13,18,16,采用冒泡排序算法(升序),经一趟冒泡后，序列的结果

是。

24.广义表((a,b),d,e,((i,j),k))的长度是。

三、综合题

1.设查找表为(7,15,21,22,40,58,68,80,88,89,120),元素的下标依次为1,2,3,……-11.

(1)画出对上述查找表进行折半查找所对应的判定树(树中结点用下标表示)

(2)说明成功查找到元素40需要经过多少次比较？

(3)求在等概率条件下，成功查找的平均比较次数？

2.(1)设有数据集合{40,29,7,73,101,4,55,2,81,92,39},依次取集合

中各数据构造一棵二叉排序树。

(2)一组记录的关键字序列为(5,8,6,3,4,7),利用堆排序(堆顶元素是最

小元素)的方法建立初始堆。(要求用完全二叉树表示)

3.(1)一组记录的关键字序列为(47,80,57,39,41,46),给出利用堆排序(堆顶

元素是最小元素)的方法建立的初始堆(要求以完全二叉树描述

(2)对关键字序列(47,80,57,39,41,85)采用快速排序，给出以第一个关键字为分割

元素，经过一次划分后的结果。

(3)如图3所示的二叉树，给出其前序遍历序列。

图3

4.(1)以2,3,4,7,8,9作为叶结点的权，构造一棵哈夫曼树

(2)给出上述哈夫曼树叶结点的哈夫曼编码。

(3)一组记录的关键字序列为(37,70,47,29,31,85),利用快速排序，以第一

个关键字为分割元素，给出经过一次划分后结果。(由小到大排序)

四、程序填空题

1.以下程序是中序遍历二叉树的递归算法的程序，完成程序中空格部分(树结构中左、

右指针域分别为left和right,数据域data为字符型，BT指向根结点)。

voidInorder(structBTreeNode*BT)乙

if(BT!=NULL){<7)^(

Inorder(BT->left);}1

——；0O亡

利用上述程序对右图进行中序遍历，结果是(3)__________________:图4

2.设线性表为(6,10,16,4),以下程序用说明结构变量的方法建立单向链表，并输出

链表中各结点中的数据。

#defineNULL0

voidmain()

{NODEa,b,c,d,*head,*p;

a.data=6;

b.data=10;

c.data=16;

d.data=4;/*d是尾结点*/

head=(1);

a.next=&b;

b.next=&c;

c.next=&d;

(2);/*以上结束建表过程*/

p=head;/*p为工作指针，准备输出链表*/

do

Srintfr%d\n”,(3))：

}while((5));

)

3.以下冒泡法程序对存放在a[l],a[2],……，a[n]中的序列进行排序，完成程序中

的空格部分，其中n是元素个数，要求按升序排列。

voidbsort(NODEa[],intn)

{NODEtemp;

inti,j,flag;

for(j=l;(1)；j++)；

{flag=O;

for(i=l;(2);i++)

if(a[i].key>a[i+l].key)

{flag=l;

temp=a[i];

(3);

(4);

)

if(flag==0)break;

)

)

程序中flag的功能是(5)_______________________

4.以下程序是中序遍历二叉树的递归算法的程序，完成程序中空格部分（树结构中左、

右指针域分别为left和right,数据域data为字符型，BT指向根结点）.

voidInorder(structBTreeNode*BT)

(

if(BT!=NULL){

___LU_______;

(2)_____________;

Inorder(BT->right);}

)

利用上述程序对右图进行遍历，结果是(3):

综合练习二答案

一、单项选择题

1.C2.D3.A4.D5.C6.C7.A8.A9.D10.B

11.C12.B13.B14.B15.D16.A17.A18.A19.D20.C

二、填空题

1.a2

2.字符串的结束符

3.物理结构（存储结构）

4.p2

5.14

6.2i+l

7.2i

8.13

9.2n-l

10.图状

11.5

12.12

13.n-1

14.n+1

15.11

16.3

17.中序

18.n-j

19.5

20.2n-l

21.3

22.二叉排序树

23.12,14,13,15,16,18

24.4

三、综合题

图6

Q)4次

(3)ASL=(1+2*2+3*4+4*4)711=3

图7

(2)3,4,6,8,5,7

3(1)39,41,46,80,47,57

(2)41,39,47,57,80,85

(3)abdefcg

图10

(2)

2：0000

40001

5001

810

911

1001

(3)31,29,37,47,70,85

四、程序填空题

1.

(1)printf(“枇”，BT->data)

(2)Inorder(BT->right)

(3)dbeafc

2.

(1)&a

(2)d->next=NULL

(3)p->data

(4)p=p->next

(5)p!=NULL

(1)j<=n-l

(2)i<=n-j

(3)a[i]=a[i+l]

(4)a[i+l]=temp

(5)当某趟冒泡中没有出现交换则已排好序，结束循环

(1)Inorder(BT->left)

(2)printf("%c”，BT->data)

(3)bedafc

综合练习三

一、单项选择题

1.数据的存储结构包括数据元素的表示和()»

A.数据处理的方法B.数据元素的类型

C.相关算法D.数据元素间的关系的表示

2.设有头指针为head的不带头结点的非空的单向循环链表，指针p指向其尾结点，要

删除第一个结点，则可利用下述语句head=head->next;和()。

A.p=head;B.p=NULL;C.p->next=head;D.head=p;

3.树状结构中数据元素的位置之间存在（）的关系。

A.每一个元素都有一个直接前驱和一个直接后继B.一对一

C.多对多D.一对多

4.以下说法正确的是（）»

A.线性表的链式存储结构必须占用连续的存储空间

B.一种逻辑结构可以有不同的存储结构

C.一种逻辑结构只能有唯一的存储结构

D.线性表的顺序存储结构不必占用连续的存储空间

5.设有一个长度为26的顺序表，要插入一个元素,并使它成为新表的第6个元素，需

移动元素的个数为（）。

A.21B.22C.20D.19

6.把数据存储到计算机中，并具体体现（）称为物理结构。

A.数据的处理方法B.数据的性质

C.数据的运算D.数据元素间的逻辑关系

7.头指针为head的带头结点的单向循环链表，p所指向尾结点，要使该链表成为

不带头结点的单向循环链表，可执行head=head->nex;和（）。

A.p=head->nextB.head->next=p

C.head->next=p->nextD.p->next=head;

8.顺序表所具备的特点之一是（）o

A.可以随机访问任一结点B.不需要占用连续的存储空间

C.插入元素的操作不需要移动元素D.删除元素的操作不需要移动元素

9.元素111,113,115,117按顺序依次进栈，则该栈的不可能输出序列是（）（进

栈出栈可以交替进行）。

A.117,115,113,111B.111,113,115,117

C.117,115,111,113D.113,111,117,115

10.图状结构中数据元素的位置之间存在（）的关系。

A.一对一B.一对多

C.多对多D.每一个元素都有一个直接前驱和一个直接后继

11.以下说法正确的是（）。

A.栈的特点是先进先出

B.栈的特点是先进后出

C.队列的特点是先进后出

12.元素20,14,16,18按顺序依次进栈，则该栈的不可能输出序列是（）

（进栈出栈可以交替进行）。

A.18,16,14,20

B.20,14,16,18

C.18,16,20,14

D.14,20,18,16

D.栈和队列的特点都是后进后出

13.设有一个20阶的对称矩阵A（第一个元素为aiQ,采用压缩存储的方式，将其下三

角部分以行序为主序存储到一维数组B中（数组下标从1开始），则矩阵元素a612

在一维数组B中的下标是（

A.21B.17C.28D.23

14.设有一个12阶的对称矩阵A（左上角第一个元素为ai,】），采用压缩存储的方式，将

其下三角部分以行序为主序存储到一维数组B中（数组下标从1开始），则矩阵中元素

a5.4在一维数组B中的下标是（）。

A.14B.12C.13D.11

15.设有串pl="ABADF"，P2="ABAFD"，P3="ABADFA"，P4="ABAF"，以下四个串中最

大的是（）.

A.p3B.p2C.plD.p4

16.设有一个长度为22的顺序表，要删除第8个元素需移动元素的个数为（）。

A.25B.14C.15D.23

17.数组a经初始化chara[]="English”;a[7]中存放的是（）。

A.字符串的结束符B.字符h

C.、'h"D.变量h

18.在一棵二叉树中，若编号为5的结点存在右孩子，则右孩子的顺序编号为（）。

A.12B.9C.11D.10

19.设主串为“ABcCDABcdEFaBc"，以下模式串能与主串成功匹配的是（）。

A.BedB.BCdC.ABCD.Abe

20.一棵具有5层的完全二叉树，最后一层有4个结点，则该树总共有（）个结点。

A.14B.15C.19D.18

21.在一棵二叉树中，若编号为i的结点存在左孩子，则左孩子的顺序编号为（）.

A.2i+lB.21-1C.2iD.2i+2

22.如图1所示，若从顶点a出发，按图的广度优先搜索法进行遍历，则可能得到的一种

顶点序列为（）。

A.abcdfgeB.abcedfgC.aebfedgD.abcfgde

图1

23.如图2所示，若从顶点a出发，按图的广度优先搜索法进行遍历，则可能得

到的一种顶点序列为（）。

A.abecdfB.aecbdfC.aebefdD.aedfeb

图2

24.字符串''abcd321ABCDz/的子串是（）。

A."21ABC"B."abcABCD"

C.abcDD.、'321a"

25.线性表以（）方式存储，能进行折半查找。

A.链接B.顺序C.关键字有序的顺序D.二叉树

26.数组a经初始化chara[]="English"；a[l]中存放的是（）。

A.字符nB.字符E

C.、'n"D."E"

27.一棵具有38个结点的完全二叉树，最后一层有（）个结点。

A.7B.5C.6D.8

28.如图3所示，若从顶点a出发，按图的深度优先搜索法进行遍历，则可能得

到的一种顶点序列为（）。

A.abecdfB.acfebdC.aebcfdD.aedfcb

29.下图的拓扑序列是（）。

A.52346

C.56234

30.下图的拓扑序列是（）»

A.52346B.52364

C.56423D.23456

二、填空题

1.结构中的数据元素存在多对多的关系称为结构。

2.栈的特点之一是：元素进、出栈的次序是:先进。

3.n个元素进行冒泡法排序，第j趟冒泡要进行次元素间的比较。

4.对稀疏矩阵进行压缩存储，矩阵中每个非零元素对应的三元组包括该元素的三项信息

是o

5.中序遍历树可得到一个有序序列。

6.在对10个记录的序列(9,35,19,77,2,10,53,45,27,68)进行直接插入排序时，当把第

6个记录10插入到有序表时，为寻找插入位置，元素间需比较次。

(按升序排序)

7.待排序的序列为8,341,2,5,9,采用直接选择排序算法,当进行了两趟选择后，结果序列

为()。

8.字符串al="beijing",a2="bef",a3="beifang",a4="befi"最小的

是o

9.广义表(包5),(1,6,(。/),1;))的长度是。

10.10个元素进行冒泡法排序，，其中第5趟冒泡共需要进行次元素间的比较。

11.广义表的(c,a,(a,b),d,e,((i,j),k))深度是。

12.遍历一棵二叉排序树可得到一个有序序列。

13.对稀疏矩阵进行压缩存储，可采用三元组表，一个有10行10列的稀疏矩阵A共有

95个零元素，其相应的三元组表共有个元素。

14.广义表(c,(a,b,c),(d,e,f),((i,j),k))的长度是.

15.在对一组记录(50,49,97,22,16,73,65,47,88)进行直接插入排序时，当把第7个记

录65插入到有序表时，为寻找插入位置需比较次。

16.广义表的(c,(b,a,b),f,e,((i,j),k))深度是.

17.一棵有5个叶结点的哈夫曼树，该树中总共有个结点。

18.序列4,2,5,3,8,6,采用冒泡排序算法(升序)，经一趟冒泡后，结果序列是。

19.设有一棵深度为4的完全二叉树，第四层上有5个结点，该树共有个结点。

(根所在结点为第1层)。

20.待排序的序列为8,3,4,125,9,采用直接选择排序算法,当进行了两趟选择后，结果序列

为

21.设有一个长度为40的顺序表，要删除第8个元素需移动元素的个数为。

22.线性表用方式存储可以随机访问。

23.有以下程序段

chara[]="English";

char*p=a;intn=0;

while(*p!=’\0'){n++;p++;}结果中，n的值是。

24.顺序表,,6,5,1,2,4,3,8,7经过一趟(1,1)归并后的结果序列为________。

三、综合题

1.有一个长度为11的有序表(1,2,11,15,24,28,30,56,69,70,80),元素的下标依次为

1,2,3,……,11,按折半查找对该表进行查找。

(1)画出对上述查找表进行折半查找所对应的判定树。

(2)说出成功查找到元素56”需要依次经过与哪些元素的比较？

(3)说出不成功查找元素72,需要进行元素比较的次数？

2.设查