2023年数据结构(本)期末综合练习(12月)

数据结构期末综合练习

2023年12月

期末练习一

一、单项选择题

1.一种逻辑结构在存储时（）。

A.只要存储数据元素间的关系B.只能采用一种存储结构

C.可采用不同的存储结构1）.只要存储数据元素的值

2.同一种逻辑结构（）。

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

C.只能表达某一种数据元素之间的关系D.以上三种说法均不对的

3.对链表，以下叙述中对的的是（）。

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

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

4.链表所具有的特点是（）。

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

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

5.线性表在存储后，假如相关操作是:规定已知第i个结点的位置访问该结点的前驱结点，则

采用（）存储方式是不可行的。

A.单链表B.双链表C.单循环链表D.顺序表

6.数据的物理结构（）。

A.与数据的逻辑结构无关B.仅仅涉及数据元素的表达

C.只涉及数据元素间关系的表达D.涉及数据元素的表达和关系的表达

7.栈和队列的共同特点是（）o

A.都是先进后出B.元素都可以随机进出

C.只允许在端点处插入和删除元素D.都是先进先出

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

A.一对一B.一对多

9.元素2,4,6,8按顺序依次进栈，按该栈的的也许输出序列依次入队列，该队列的也许输

出序列是（）（进栈出栈可以交替进行）。

A.8,6,2,4B.8,4,2,6

C.6,2,4,8D.8,6,4,2

10.以下表中可以随机访问的是（）。

A.单向链表B.双向链表

C.单向循环链表D.顺序表

11.在一个不带头结点的链队中，假设f和r分别为队头和队尾指针，则从该对列中删除一

个结点并把结点的值保存在变量x中的运算为（）。

A.x=r->data；r=r->next；B.r=r->next;x=r->data

C.x=f->data;f=f->next;D.f=f->next;x=f->data

12.算法的时间复杂度与（）有关。

A.所使用的计算机B.与计算机的操作系统

C.与算法自身D.与数据结构

13.设有一个20阶的对称矩阵A,采用压缩存储的方式,将其下三角部分以行序为主序存储

到一维数组B中（数组下标从1开始），则数组中第38号元素相应于矩阵中的元素是

（）。

A.3io,8B.a?,eC.ao,2D.a

8,5

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

A.n-i+1B.n_iC.n-i一1D.i

15.在C语言中，分别存储"S"和's',各需要占用（）字节。

A.一个和两个B.两个C.一个D.两个和一个

16.在一个单链表中，p、q分别指向表中两个相邻的结点,且q所指结点是p所指结点的直

接后继，现要删除q所指结点，可用的语句是（）。

A.p=q->nextB.p—>next=qC,p—>next=q->nextD.q->n

ext=NULL

17.一棵有n个结点,采用链式存储的二叉树中,共有（）个指针域被有效使用（即指针

域为非空）。

A.n+1B.nC.n_1D.n-2

18.从一个栈顶指针为top的链栈中删除一个结点时,用变量x保存被删结点的值，则执行

（）。

A.x=top->data;top=top->next；B.x=top—>data；

C.top=top->next；x=top->data;D.top=top->next;x=data;

19.在一棵二叉树中，若编号为i的结点存在双亲结点，则双亲结点的顺序编号为（）。

A.i/2.0B.i/2向下取整C.2i+1

D.i+2

20.在一个链队中，假设f和r分别为队头和队尾指针，则删除一个结点的运算为（）o

A.r=f—>next；B.r=r->next;C.f=f—>next；D.f=

r->next;

21.设一棵哈夫曼树共有2n+1个结点，则该树有（）个非叶结点。

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

22.一个栈的进栈序列是a,b,c,d,e,则栈的不也许输出序列是（）（进栈出栈可以交

替进行）。

A.dceabB.edcbaC.decbaD.abcde

23.一棵完全二叉树共有4层，且第4层上有2个结点，该树共有（）个非叶子结点

（根为第一层）。

A.5B.4C.3D.9

24.有一个长度为10的有序表，按折半查找对该表进行查找，在等概率情况下查找成功的

平均比较次数为（）。

A.26/10B.29/10C.29/9D.31/10

25.如图1所示的一个图,若从顶点a出发,按广度优先搜索法进行遍历,则也许得到的一种顶

点序列为（）。

A.abedfcB.acfebdC.aebcdfD.aebcfd

图1

26.排序算法中，从未排序序列中依次取出元素与己排序序列（初始为空）中的元素进行比较

（规定比较次数尽量少），然后将其放入己排序序列的对的位置的方法是（）=

A.冒泡B.直接插入C.折半插入D.选择排序

27.一组记录的关键字序列为（56,30,89,66,48,50,94,87,100）,运用快速排序，以

第一个关键字为分割元素，通过一次划分后结果为（）。

A.30,50,48,56,66,89,94,100,87B.50,30,48,56,6

6,89,94,87,100

C.48,30,50,56,66,89,94,87,1001）.50,30,48,66,56,89,94,8

7,100

28.设有一个10阶的对称矩阵A,采用压缩存储的方式，将其下三角部分以行序为主存储到

一维数组B中（数组下标从1开始），则矩阵中元素A&5在一维数组B中的下标是（）。

A.33B.32C.85D.41

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

A.关键字有序的链接B.顺序C.关键字有序的顺序D.数组

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

30.在一个无向图中，所有顶点的度数之和等于边数的（）倍。

A.3B.2.5C,1.5D.2

二、填空题

1.数据的逻辑结构在计算机中的表达称为结构。

2.栈和队列的操作特点分别是和o

3.求两个n阶矩阵的乘积，算法的基本操作为，时间复杂度为o

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

5.设有一个长度为25的顺序表，第8号元素到第25号元素依次存放的值为8,9,10,11,-2

5,

某人想要在第8个元素前插入1个元素7（也就是插入元素作为新表的第8个元素），他

的做法是从第8号元素开始,直到第25号元素依次向后移动1个位置,然后把7存放在

8号位置，其结果是新表中第25号元素的值为o

6.根据数据元素间关系的不同特性，通常可分为集合、线性、、四类基本结

构。

7.在双向链表中，要在p所指的结后插入q所指的结点（设q所指的结点已赋值），

其中所用的一条语句（p->next）->prior=q；的功能是使P所指结点的

_指向qo

8.规定在n个数据元素中找其中值最大的元素，设基本操作为元素间的比较。则比较的次数

和算法的时间复杂度分别为和o

9.设有一个带头结点的，头指针为head的单向链表,P指向表中某一个结点，且有

p->next==NULL,现要删除头结点，并使该单向链表构导致单向循环链表，通过

操作head=head->next;。

10.在一个单向链表中p所指结点之后插入一个s所指向的结点时，应执行

和p->next=s；的操作。

11.从一个栈顶指针为top的链栈中删除一个结点时，用d保存被删结点的值，可执行

。（结点的指针域为next,数据域为data）

12.在二叉树的链式存储结构中，通常每个结点中设立三个域，它们是值域、

______________________________O

13循环链队列中，设fr。nt和rear分别为队头和队尾指针，（最多元素为MaxSize,采用少

用一

个元素的模式），判断循环链队列为满的条件为o

14.一棵二叉树中顺序编号为i的结点，若它存在左、右孩子，则左、右孩子编号分别为一

15.对稀疏矩阵进行压缩存储，可采用三元组表，一个6行7列的稀疏矩阵A相应的三元组

表共有8个元素，则矩阵A共有个零元素。

16.向一个栈顶指针为h的链栈中插入一个s所指结点时,可执行s->next=h;和。

17.一棵有20个结点的4度的树，其中3度结1个，2度结1个,1度结2个，则该树共有

_____个叶结点。

18.在一个链队中，设f和r分别为队头和队尾指针，则插入s所指结点的操作为和

r=s;（结点的指针域为next）

19.一棵有18个结点的二叉树，其2度结点数的个数为8,则该树共有

____________个［度结点

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

所在结点为第1层）

21.如图2所示的二叉树，其先序遍历序列为。

图2

22.对稀疏矩阵进行压缩存储，矩阵中每个非零元素相应的三元组涉及该元素的

和三项信息。

23.在查找表中，通过记录的某关键字能唯一地拟定一个记录，该关键字称为

____O

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

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

三、综合题

1.(1)对给定权值3,1,4,4,5,6,构造深度为5的哈夫曼树。(设根为第1层)

(2)求树的带权途径长度。

(3)链接存储上述哈夫曼树，结点中共有多少个个指针域为空，说明理由.

2.

(1)以2,3,4,7,8,9作为叶结点的权，构造一棵哈夫曼树(规定每个结点的左子树根结

点的权小于等于右子树根结点的权)，给出相应权重值叶结点的哈夫曼编码。

(2)一棵哈夫曼树有n个叶结点，它一共有多少个结点?简述理由？

3.(1)如下的一棵树，给出先序遍历序列

(2)把1,2,3,4,5,6,7,8,9填人，使它成为一棵二叉排序树

提醒：设图中的树是二叉排序树,找出中序遍历序列与1,2,…9的相应关系

(3)请在该树中再插入一个结点3.5作为叶结点，并使它仍然是一棵二叉排序树。

Al

图3

4.一组记录的关键字序列为(46,79,56,38,40,84)

(1)运用快速排序的方法，给出以第一个记录为基准得到的一次划分结果(给出逐次互换元

素的过程，规定以升序排列)

(2)对上述序列用堆排序的方法建立大根堆，规定以二叉树逐次描述建堆过程。

5.设查找表为(5,6,7,8,9,10,11,12,13,14)

(1)画出对上述有序表进行折半查找所相应的鉴定树(规定以数据元素作为树结点)

(2)给出二叉排序树的定义，针对上述折半查找所相应的鉴定树的构造过程，说明鉴定树

是否是二叉排序树(设树中没有相同结点)？

(3)为了查找元素5.5,通过多少次元素间的比较才干拟定不能查到？

6.设查找表为(50,60,75,85,96,98,105,110,120,130)

(1)说出进行折半查找成功查找到元素120需要进行多少次元素间的比较？

(2)为了折半查找元素95,通过多少次元素间的比较才干拟定不能查到？

(3)画出对上述有序表进行折半查找所相应的鉴定树(规定以数据元素作为树结点)

四、程序填空题

1.以下函数为直接选择排序算法，对a[l…a[n]中的记录进行直接选择排序，完毕程

序中的空格

typedefstruct

{intkey;

}NODE;

voidseIsort(N0DEa[],intn)

(

»inti,j,k;

NODEtemp;

for(i=1;i<=_⑴；i++)

(

8k=i;

。for(j=i+1；j<=(2)；j++)

»if(a[j],key<aEk].key)_(3)；

»if(i!=k)

{

emp=a[i];

6o___(4);

8(5)；

00

。}

)

2.以下是用尾插法建立带头结点且有n个结点的单向链表的程序，结点中的数据域从

前向后依次为1,2,3,……,n,完毕程序中空格部分。

NODE*create(n)

{NODE*head,*p,*q;

inti;

p=(NODE*)ma11oc(sizeof(NODE))；

head=(1);(2);p->next=NULL;/*建立头结点*/

for(i=l;i<=n;i++)

{P=_Q)___________________；

p-^data=i；

pTnext=NULL；

q->next=(4);

(5);

return(head);

3.设有一个头指针为head的不带头结点单向链表，且p、q是指向链表中结点类型的

指针变量，p指向链表中某结点a(设链表中没有结点的数据域与结点a的数据域相同),

写出相关语句

(1).使该单向链表成为单向循环链表

(2)删去a结点

q=p;x=p->data;

whi1e(q—>next!=NULL)q=q—>next；

_(1)—

q=p;p=p->next；

whi1e(p->data!=x)

{q=p；

-(2)—

)

一(3)

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

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

voidInorder(structBTreeNode*BT)

{if(BT!=NULL){

_£U______________________；

(2);

J_3J_______________________；

)

)

期末复习一答案

一、单项选择题

1.C2.B3.A4.C5.A6.D7.C8.A9.D10.D11.C

12.C13.C14.B15.D16.C17.C18.A19.B20.C2

1.A22.A23.B24.B25.C26.C27.B28.A29.C3

0.D

二、填空题

1.物理(存储)

2.后进先出、先进先出

3.乘法0(/)

4.图状(网状)

5.8

6.树形图状

7.直接前驱的左指针

8.n-1,0(n)、

9.p->next=head;

10.s->next=p->next；

11.d=top->data；top=top—>next;

12.左指针右指针

13.front==(rear+1)%MaxSize

14.2i2i+l

15.34

16.h=s;

17.13

18.r->next=s；

19.1

20.12

21.

22.行下标、列下标、非零元素值

23.主关键字

24.3

三、综合应用题

图4

(2)WPL=3*4+l*4+4*3+6*2+4*2+5*2=58

(3)共11个结点,22个指针域，除根结点外，每个结点相应一个指针域.，共10个指针域非空,

有22-10=12个空指针域,

2.

(1)

图5

2:1110

3:1111

4：110

7：00

8:01

9:10

(2)2n-l个，由于非叶结点数比叶结点数少一个。

3.

(1)A1A2A4A7A8A5A9A3A6

(2)

(3)

图6

4.

(1)初始序列

同79,56,38,40,84

40,79,56,38回，84

40,国，56,38,79,84

40,38,56,画,79,84

40,38,园56,79,84

40,38国56,79,84

图7

(2)二叉排序树或者是一棵空树，或者是一棵具有下列性质的二叉排：若它的左子树

非空，则左子树的所有结点的值都小于它的根结点的值;若它的右子树非空，则右子

树的所有结点的值都大于(若允许结点有相同的值，则大于等于)它的根结点的值；

左，右子树也是一棵二叉排序树，按定义鉴定树是二叉排序树。

(3)3次

6.

(1)3次

(2)4次

(3)

图8

四、程序填空题

1.(l)n-l

(2)n

(3)k=j

(4)a[i]=a[k]

(5)a[k]=temp

(1)P

(2)q=p

(3)(NODE*)ma11oc(sizeof(NODE))

(4)p

(5)q=p

3.

(1)q->next=head;

(2)p=p—>next；

(3)q->next=p->next;

4.

(1)Inorder(BT->left)

(2)printf(,BT->data)

(3)Inorder(BT->right)

期末练习二

一、单项选择题

1.结构中的元素之间存在一对多的关系是（）o

A.集合B.线性结构

C.树形结构D.图状结构

2.在C语言中，顺序存储长度为3的字符串，需要占用（）个字节。

A.4B.3C.6D.12

3.对不带头结点的单向链表，判断是否为空的条件是（）（设头指针为head）。

A.head==NULLB.head->next==NULL

C.head->next==headD.head=NULL

4.串函数StrCat（a,b）的功能是进行串（）。

A.比较B.复制C.赋值D.连接

5.在一个不带头结点的单循环链表中,p、q分别指向表中第一个结点和尾结点，现要删除第

一个结点，可用的语句是（）。

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

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

6.一棵有n个结点采用链式存储的二叉树中，共有（）个指针域为空。

A.n+1B.nC.n-lD.n-2

7.一个栈的进栈序列是1,2,3,4,5,则栈的不也许输出序列是（）（进栈出栈可以交

替进行）。

A.12345B.43512C.45321D.54321

8.设一棵哈夫曼树共有n个非叶结点,则该树有（）个叶结点。

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

9.一个队列的入队序列是2,4,6,8,按该队列的输出序列使各元素依次入栈，该栈的也许

输出序列是（）。

A.8,6,4,2B.6,2,4,8

C.8,4,2,6D.8,2,4,6

10.从一个栈顶指针为top的链栈中删除一个结点时，用变量x保存被删结点的值，则执行

（）。

A.x=top->data;top=topfnext；B.x=top—>data;

C.top=top—>next;x=top->data;D.top=top->next;x=data；

11.在一个链队中，假设f和r分别为队头和队尾指针，已生成一个结点P,要为结点P赋

值X,并入队的运算为（）。

A.p->data=x;p—>next=NULL;f—>next=p;f=p;

B.p->data=x;p—>next=NULL；r—>next=p;r=p;

C.p->data=x；p->next=r;r=s;

D.p->data=x;p->next=f；f=s;

12.一棵完全二叉树共有5层，且第5层上有六个结点，该树共有（）个结点。

A.30B.20C.21I）.23

13.设有一个25阶的对称矩阵A,采用压缩存储的方式，将其下三角部分以行序为主序存储到

一维数组B中（数组下标从1开始），则矩阵中元素.a7,6在一维数组B中的下标是（）。

A.34B.14C.26D.27

14.在一个无向图中，所有顶点的度数之和等于边数的（）倍。

A.3B.2.5C.1.5D.2

15.以下程序段的结果是c的值为（）。

chara[5]="1236789"，int*p=a,intc=0;

while（*p++）c++;

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

16.已知如图1所示的一个图,若从顶点修出发，按深度优先搜索法进行遍历，则也许得到的

一种顶点序列为（）o

A.VMV4V8V5V3V6V7B.VMVMVMV6V7

C.V1V2V4V8V3V5V6V7D.%V3V6V7V2V4V5V8

图1

17.一棵有23个结点，采用链式存储的二叉树中，共有（）个指针域为空。

A.24B.25C.23D.45

18.已知如图2所示的一个图，若从顶点a出发,按广度优先搜索法进行遍历，则也许得到的一

种顶点序列为（）。

A.abcedfB.abcefdC.aebcfdD.acfdeb

19.在一棵二叉树中，若编号为i的结点是其双亲结点的左孩子，则双亲结点的顺序编号为

（）。

A.i/2B.2i-lC.2i+lD.i/

2-1

20.对二叉排序树进行（）遍历，可以使遍历所得到的序列是有序序列.

A.按层次B.后序C.中序D.前序

21.设一棵哈夫曼树共有2n+1个叶结点,则该树有（）个叶结点。

A.n-1B.nC.n+1D.2n

22.在有序表｛2,4,7,14,34,43,47,64,75,80,90,97,120｝中，用折半查找法查找

值80时，经（）次比较后查找成功。

A.4B.2C.3D.5

23.已知如图3所示的一个图,若从顶点a出发，按深度优先搜索法进行遍历，则也许得到的

一种顶点序列为（）。

A.abecdfB.acfebdC.aebcfdD.aedbfc

24.有一个长度为9的有序表,按折半查找对该表进行查找，在等概率情况下查找成功的平

均比较次数为（）。

A.25/10B.25/9C.20/9D.17/9

25.已知如图4所示的一个图,若从顶点B出发，按广度优先法进行遍历,则也许得到的一种

顶点序列为（）。

A.BADEHCFGB.ADEHCGFC.BADECHFGD.BADEHCFG

图4

26.排序算法中，从未排序序列中依次取出元素与已排序序列（初始为空）中的元素进行比

较（规定比较次数尽量少），然后将其放入已排序序列的对的位置的方法是（）。

A.冒泡B.直接插入C.折半插入D.选择排序

27.一组记录的关键字序列为（46,38,56,40,79,84）,运用快速排序，以第一个关键

字为分割元素，通过一次划分后结果为（）。

A.40,38,46,79,56,84B.40,38,46,56,79,84

C.40,38,46,84,56,79D.38,40,46,56,79,84

28.一组记录的关键字序列为（46,79,56,38,40,84）,运用快速排序，以第一个关

键字为分割元素,通过一次划分后结果为（）。

A.40,38,46,79,56,84B.40,38,46,56,79,84

C.40,38,46,84,56,79D.38,40,46,56,79,84

29.在有序表｛21,23,28,33,43,45,46,73,77,78,89,99,106｝中，用折半查找值

43时，经（）次比较后查找成功。

A.6B.3C.8D.4

30.排序方法中,从尚未排序序列中挑选元素,并将其依次放入已排序序列（初始为空）的一端

的方法，称为（）排序。

A.归并B.插入C.快速D.选择

二、填空题

1.本书中介绍的树形结构和属非线性结构。

2.在二叉树的链式存储结构中，通常每个结点中设立三个域，它们是、、

右指针。

3.设有一个长度为18的顺序表，要在第4个元素之前插入2个元素（也就是插入元素作为

新表的第5个和第4个元素），则最少要移动元素的个数为（）。

4.一棵二叉树中顺序编号为i的结点，若它存在左、右孩子，则左、右孩子编号分别为

5.在双向链表中，要删除p所指的结点,可以先用语句（p->prior）—>next=p—>next;然

再用语句。

6.串的两种最基本的存储方式是和。

7.在一个单向链表中p所指结点之后插入一个s所指向的结点时,应执行s->next=p->next;

和的操作.

8.一棵有2n-1个结点的二叉树，其每一个非叶结点的度数都为2，则该树共有个叶

结点。

9.一个栈和一个队列的输入序列都为abcdefg，它们也许有相同的输出序列吗？。

（若没有则回答没有，若有则写出序列,进栈出栈可以交替进行）。

10.对于一棵具有n个结点的二叉树，其相应的链式存储结构中共有个指针域为空。

11.从一个栈顶指针为top的链栈中取栈顶元素，用d保存栈顶元素的值，可执行

o（结点的数据域为data）

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

13.循环链队列中，设front和rear分别为队头和队尾指针，（最多元素为MaxSize,）,判

断循环链队列为空的条件是为真。

14.如图5所示的二叉树，其后序遍历序列为。

图5

15.对稀疏矩阵进行压缩存储，可采用三元组表，设a是稀疏矩阵A相应的三元组表类型（结

构体类型）变量，a中的一个成员项是三元组类型的结构体数组data,按书中定义,

若a.data[0].i=2;a.data[O].j=3;a.data[0].v=16;它提供的A数组的相关信息有

16.如图6所示的二叉树，其先序遍历序列为

图6

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

（根所在结点为第1层）

18.图的深度优先搜索和广度优先搜索序列不一定是唯一的。此断言是的。（回答对的

或不对的）

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

20.二叉树为二叉排序的充足必要条件是其任一结点的值均大于其左孩子的值、小于其右孩

子的值。这种说法是的。（回答对的或不对的）

21.如图7所示的二叉树，其后序遍历序列为o

A

图7

22.对记录序列排序是指按记录的某个关键字排序，记录序列按排序结果是唯

一的。

23.给定一组权重值，构造哈夫曼树，哈夫曼树的高度一定是唯一的，这种说法是

的。(回答对的或不对的)

24.按某关键字对记录序列排序，若__________________在排序前和排序后仍保持它们的前

后关系，则排序算法是稳定的，否则是不稳定的。

三、综合题

1.(1)说明什么是顶点活动网(AOV网)和拓扑序列

(2)设有向图G如下，写出3种拓扑序列，

(3)在图G中增长一条边，使图G仅有一条拓扑序列

图8

2.设查找表为(16,15,20,53,64,7),

(1)用冒泡法对该表进行排序(规定升序排列)，写出每一趟的排序过程，通常对n个元

素进行冒泡排序要进行多少趟冒泡?第j趟要进行多少次元素间的比较？

(2)在排序后的有序表的基础上，画出对其进行折半查找所相应的鉴定树.(规定以数据元

素作为树结点)

3.如下是一棵二叉排序树,A1,A2,…A9代表1,2,3,...9中各个不同数字，

(1)给出对该树中序遍历的结果

(2)A3.A5,A7的值各为多少？

(3)请在该树中再插入一个结点9.5作为叶结点，并使它仍然是一棵二叉排序树

4.

(1)设有查找表{5,14,2,6,18,7,4,16,3},依次取表中数据，构造一棵二叉排序树。

(2)说明如何由序列的二叉排序树得到相应序列的排序结果，对上述二叉排序给出中序遍

历的结果。

5.

(1)设有查找表{17,26,14,16,15,30,18,19,28},依次取表中数据构造一棵二叉

排序树.

(2)对上述二叉树给出后序遍历的结果

(3).对上述二叉树给出中后序遍历的结果

(4))在上述二叉树中查找元素15共要进行多少次元素的比较?

6.(1)对给定权值2,1,3,3,4,5,构造哈夫曼树。

(2)同样用上述权值构造另一棵哈夫曼树，使两棵哈夫曼树有不同的高度，并分别求两

棵树的带权途径长度。

四、程序填空题

1.以下函数是二叉排序树的查找算法，若二叉树为空，则返回根结点的指针，否则，返回

值是指向树结点的结构指针P(查找成功P指向查到的树结点，不成功P指向为NULL)完

毕程序中的空格

typedefstructBnode

{intkey;

structBnode*left；

structBnode*right；

}Bnode；

Bnode*BSearch(Bnode*bt,intk)

/*bt用于接受二叉排序树的根结点的指针,k用以接受要查找的关键字*/

{Bnode*p;

if(bt==____(1))

return(bt);

P=bt;

whi1e(p->key!=_(2))。

{if(k<p—>key)®。

—(3);

else(4)了

if(p==NULL)break;

)

return(____(5))；

}

)

3.设有一个头指针为head的不带头结点单向链表,P、q是指向链表中结点类型的指

针变量，p指向链表中结点a,(设链表中没有结点的数据域与结点a的数据域相同)，

写出相关语句

(1).使该单向链表成为单向循环链表

(2)插入结点s,使它成为a结点的直接前驱

q=p;x=p->data;

while(_(1))q=q->next;

q->next=head;

q=p;p=p->next；

while(p->data!=x)

{q=p；

_⑵_____

}

s->next=p;

_(3)—

答案

一、单项选择题

1.C2.A3.A4.D5.D6.A7.B8.B9.A10.A11.B12.C

13.D14.D15.B16.A17.A18.B19.A20.C21.C22.A

23.D24.B25.C26.C27.B28.B29.B30.D

二、填空题

1.图状结构

2.值域左指针

3.15

4.2i和2i+l

5.(p->next)->prior=p->prior；

6.顺序存储链式存储

7.p—>next=s;

8.n9.abcdefg

10.n+1

11.d=top->data;

12.中序

13.front==rear

14.gdbeihfca

15.A的第一个非零元素的下标为2,3,元素为16

16.abdefcg

17.5

18.对的

19.二叉排序

20.不对的

21.

22.主关键字

23.不对的

24.关键字相等的记录

三、综合应用题

1.

⑴原序列16152053647

71516205364

I、)

图10

2.

(1)原序列16152053647

71516205364

(2)

图11

(3)平均查找长度二(1*1+2*2+3*3)/6=14/6

3.

(1)

图12

(2)中序遍历

中序2,3,4,5,6,7,14,16,18

4.

图13

(2)中序遍历

中序2,3,4,5,6,7,14,16,18

图15

wp12=45

wpll=45

四、程序填空题

1.(1)NULL

(2)k

(3)p=p->left

(4)p=p—>right

(5)p

2.

(1)&a

⑵d-next=NULL

(3)p->data

(4)p=p->next

(5)p!=NULL

3.

(1)q—>next!=NULL

(2)p=p->next;

(3)q->next=s；

4.

(1)Postorder(BT->1eft)

(2)Postorder(BT->right)

(3)printf("%c”,BT-〉data)

期末练习三

一、单项选择题

1.数据结构在计算机内存中的表达是指（）。

A.数据元素之间的关系B.数据的存储结构

C.数据元素的类型D.数据的逻辑结构

2.在数据结构和算法中，与所使用的计算机有关的是（）o

A.数据元数间的抽象关系B.数据的存储结构

C.算法的时间复杂度I）.数据的逻辑结构

3.结构中的元素之间存在多对多的关系是（）。

A.集合B.线性结构

C.树形结构1）.图状结构

4.对顺序表，以下叙述中对的的是（）。

A.用一组地址连续的存储单元依次存放线性表的数据元素

B.各个数据元素的首地址是连续的

C.数据元素不能随机访问

D.插入操作不需要移动元素

5.设有一个长度为20的顺序表，要在第5个元素之前插入1个元素（也就是插入元素作为

新表的第5个元素），则移动元素个数为（）。

A.15B.16C.5D.4

6.设有一个长度为25