数据结构C考试题及答案

数据结构试题一

一、单项选择题（每小题3分，共30分）

1、在有n个叶子结点的哈夫曼树中，其结点总数为

（）。

A、不确定B、2nC、2n+1D、2n-1

2、下列序列中，（）是执行第一趟快速排序得到的

序列（排序的关键字类型是字符串）。

A、[da,ax,eb,de,bb]ff[ha,gc]

B、[cd,eb,ax,da]ff[ha,gc,bb]C、[gc,ax,

eb,cd,bb]ff[da,ha]D、[ax,

bb,cd,da]ff[eb,gc,ha]

3、若线性表最常用的操作是存取第i个元素及其前

驱的值，则采用（）存储方式节省时间。

A、单链表.B、双链表C、单循环链表

D、顺序表

4、下列排序算法中，时间复杂度不受数据初始状态

影响，恒为O（nlogn）的是（）o

A、堆排序B、冒泡排序C、直接选择排序

D、快序排序

5、某二叉树的先序序列和后序序列正好相反，则该

二叉树一定是（）的二叉树。

空或只有个结点

B、高度等于其结点数

C、任意结点无左孩子

D、任意结点无右孩子

6、下列排序算法中，某一趟结束后未必能选出一个

元素放在其最终位置上的是（）o

A、堆排序B、冒泡排序C、直接

选择排序D、快序排序

7、快速排序算法在最好情况下的时间复杂度为（）o

A、0（n）B、0（n2）C、

0（nIogn）D、0（Iogn）

8、已知数据表A中每个元素距其最终位置不远，则

采用（）排序算法最省时间。

A、堆排序B、插入排序C、直接

选择排序D、快序排序

9、带权有向图G用邻接矩阵A存储，则顶点i的人

度为A中（）。

A、第i行非8的元素之和B、第i

列非8的元素之和

C、第i行非8且非0的元素之和D、第i

列非8且非0的元素之和

10、在有n个结点且为完全二叉树的二叉排序树中查

找一个键值，其平均比较次数的数量级为（）o

A、O(n)B、O(n2)C、O(nlogn)D^O(logn)

二、判断题(认为对的在题后的括号内打“，”，错的打“x”，每小题1分，

共10分)

1.对任意一个图，从它的某个顶点出发进行一次深度优先或广度优先搜索遍历可

访问该图的每个顶点。()

2.在索引顺序表上实现分快查找，在等概率查找情况下，其平均查找长度不仅

与表的个数有关，而且与每一块中的元素个数有关。()

3、只有在初始数据为逆序时，冒泡排序所执行的比较次数最多。()

4、图G的最小生成树的代价一定小于其他生成树的代价。()

5、已知一棵树的先序序列和后序序列，一定能构造出该树。()

6、对一个堆按层次遍历，不一定能得到一个有序序列。()

7、设与一棵树T所对应的二叉树为BT,则与T中的叶子结点所对应的BT

中的结点也一定是叶子结点。()

8、不管ADT栈是用数组实现，还是用链表的指针实现，POP(S)与Push(x,S)的

耗时均为O(n)。()

9、如果删除二叉排序树中一个结点，再按照二叉排序椅的构造原则重新插入上

去，一定能得到原来的二叉排序树。()

10、快速排序是排序算法中最快的一种。()

三、填空题(每小题2分，共20分)

1、在双向循环表中，在p所指的结点之后插入指针f所指的结点，其操作为：

=p;f-*next=p-*next;=f;p—next=f。

2、在有序表A[1…20]中，采用二分查找算法查找元素值等于A[12]的元素，所

比较过的元素的下标依次为0

3、若某串的长度小于一个常数，则采用存储方式最节省空间。

4、在有n个顶点的有向图中，每个顶点的度最大可达_________

5、已知二叉树中叶子数为50,仅有一个孩子的结点数为30,则总结点数为

6、设键值序列为{KLK2,…，Kn},用筛选法建堆则必须从第个元素

开始筛选。

7、在二叉链表中判断某指针p所指结点为叶子结点的条件是________。

8、直接选择排序算法在最好情况下所作的交换元素的次数为o

9、有n个球队参加的足球联赛按主客场制进行比赛，共需进行比赛。

10、下列排序算法中，占用辅助空间最多的是________(堆排序，希尔排序,

快速排序，归并排序)。

四、简答题(每题10分，共60分)

1、在单链表、双链表和单循环链表中，若仅知道指针p指向某结点，不知道头

指针，能否将结点p从相应的链表中删去？若可以，其时间复杂度各为多少？

2、设有一组关键字(17,13,14,153,29,35)需插入到表长为12的散列表

中.请回答以下问题：

(1)设计一个适合该散列表的散列函数。

(2)用设计的散列函数将上述关键字插入到散列表中，并用线性探测法解决

冲突，画出其结构；并指出用线性探测法解决冲突时构造散列表的装填因子为

多少？

3、对n个顶点的无向图和有向图，采用邻接矩阵和邻接表表示时，如何判别下

列有关问

(1)图中有多少条边？

(2)任意两个顶点i和j是否有边相连？

(3)任意一个顶点的度是多少？

4、已知下面二叉排序树的各结点的值依次为1…9,请标出各结点的值。

5、具有3个结点的树和具有3个结点的二叉树，它们的所有不同形态有哪些？

6、分析以下程序段中语句x=x+y的执行次数。

x=0;y=0;

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

for(intj=l;j<=i;j++)

for(intk=l;k<=j;k++)

x=x+y；

五、算法设计题(每题15分，共30分)

说明：可以使用任何高级程序设计语言或伪(类)程序设计语言。

1、假设以二叉链表作为二叉树存储结构，其类型定义如下：

typedefstructnode

{chardata;

structnode*lchil"rchild;〃左右孩子指针

}BinTNode,*BinTree;

写一函数，完成以下功能：

对二叉树中每个结点，如果其左孩子为空(右孩子不为空)，则将其右孩子

设置为左孩子。

2、试设计将数组A[0…ml]中所有奇数移到所有偶数之前的算法。要求不另增

加存储空间且时间复杂度为O(n)。

数据结构试题1参考答案

一、1——5：DADAB6——10：CCBDD

二、1------5：xVxxV6------10：Vxxxx

三、1、①f—prior,②p—next—prior2、1015123、顺序压缩4、2(n-l)

5、1296、n/2的最小整数7、(p—lchild==NULL)&&(pfrchild==NULL)

8、09、n(n-l)10、归并排序

四、1、答案：在单错表中不能删除，而在双倍表和单循环错表中可以删除p结点。

双链表的删除时间复杂度为0(1),单循环链表删除p结点的时间复杂度为O(n)°

2、答案：(1)由于散列表的长度为12,则可选不超过表长的最大素数11作为除留余数

法的模，则可得其散列函数为h(k)=k%lL

(2)若用线性探测法解决冲突，则可构造出散列表如下：

1314351729153

012345678910

11

此时，其装填因子为6/12=1/2,若用链式法解决冲突，则其散列表为：

1-1

14

一1V

-----------------上1

J153

----------------

3、答案：（1）无向图的邻接矩阵所有数值之和除以2,为边数。有向图邻接矩阵各行数

值之和为总边数。邻接表表示无向图内部顶点个数除以2,有向图内部顶点个数。

（2）无向图中I行和J列的交叉点的值是否为1。有向图I行J列交叉点或I列

和J行交叉点的值为1。

（3）无向图顶点的度为每一行的数值之和；有向图顶点度为该行和该列数值之和。

4答案：

5、答案：具有3个结点的树的形态为：三个结点的两种树形态，无左右之分。

具有3个结点的二叉树的形态为：5种形态，有左右之分。

6：答案:

X££1=S£.7=S；D=JSz

z=1/=1Ar=I/=1/=1i=122，=i27=1

n(n+1)(2〃+1)+_L/(〃+D+1)(〃+2)

222

五、Is答案：voidexchange(BinTreeT)

{if(T|

{if(!T-lchild&&T-*rchild)

{T-lchild=T-rchild;

T^rchild=NULL;}

exchange(T->lchild);

exchange(T-*rchild);}}

2、答案：intoddbeforc(A,n)〃将数组A[0…n-11中所有奇数移到所有偶数之前

intA[];

{intc,ij；i=O;j=n-l;〃初始化i、j

while(i<j)

{while((A[i]%2==l)&&(i<j))〃A[i]为奇数时，i向右扫描

i++；

while((A[i]%2==0)&&(i<j))〃A[”为偶数时，j向右扫描

//A[i]与进行交换，i向右、j向左扫

描；{c=A[i];

A[i]=A[j];A[j]=c;i++;

i-;M

return(l)

//oddbefore

数据结构试题2

一、单项选择题（每小题3分，共30分）

1、下列排序算法中，（）排序在每趟结束后，不一定能选出一个元素放到其排好序的最终

位置上。

A、选择B、冒泡C、归并D、堆

2、若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则

采用（）存储方式最节省运算时间。

A、单链表B、仅有头指针的单循环链表C、双链表D、仅有尾指针的单循环链表

3、串的长度是（）。

A、串中不同字符的个数B、串中不同字母的个数

C、串中所含字符的个数且字符个数大于0D、串中所含字符的个数

4、有一个散列表，表长度m为100,采用除余法构造散列函数，即H（k）=k%P,（P小于等

于m）,为使散列函数有较好的性能，P的选择应是（

A、99B、97C^91D、93

5、在包括n个键值的二叉排序树中查找一个键值，其平均比较的量级为（）。

A、O（n）B、O（logn）C、O（nlogn）D>O（n）

6、对有14个元素的有序表A[I…14]作二分查找，查找A[4]时的被比较元素依次为（）o

A、A[l],A[2],A[3],A[4|B、A[l],A[14],A[7],A[4]

C、A[7],A[3],A[5],A[4]D、A[7],A[5],A[3],A[4]

7、具有65个结点的完全二叉树其深度为（）o

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

8、带权有向图G用邻接矩阵A存储，则顶点i的入度等于A中（）。

A、第i行非无穷元素之和B、第i列非无穷元素之和

C、第i行非零且非无穷元素个数D、第i列非零且非无穷元素个数

9、队列操作的原则是（）»

A、先进先出B、后进先出C、只能进行插入D、只能进行删除

10、若表R在排列前已按元素键值递增顺序排序，采用（）的比较次数少。

A、直接插入排序B、快速排序C、归并排序D、选择排序

二、判断题（认为对的，在题后的括号内打“J”，错的打“X”，每小题1分，共10

分）1、在栈空的情况下，不能做退栈运算，否则产生下溢。（）

2、在快速排序算法中，取待排序的n个记录中的第一个的键值为基准，将所有记录分为

两组，读记录就排在这两组的中间，这也是该记录的最终位置。（）

3、在索引顺序表查找方法中，对索引顺序表可以使用顺序表查找方法，也可以使用二分

查找方法。（）

4、设有键值序列（kl,k2,,•,»kn）,当i＞n/2时，任何一个序列（kLk2,…，kn）一

定是堆。（）

5、在向二叉排序树中插入一个新结点时，需要比较结点的次数可能大于此二叉树的高度ho

（）

6、在一个有向图的邻接表或逆邻接表中，如果某个顶点的链表为空，则该顶点的度一定为

零。（）

7、双循环链表中，任一结点的前驱指针均为不空。（）

8、线性表采用链式存储方式和顺序存储方式，执行插入、删除运算的算法时间复杂度都

是O（n）,因而两种存储方式的插入、删除运算所花费的时间相同。（）

9、如果有向图G=（V,E）的拓扑序列不唯一，则图中必有两条弧＜vi,vj＞和＜vj,vi＞存在。（）

10、矩阵压缩存储的方法是用三元组表存储矩阵元素。（）

三、填空题（每小题2分，共20分）

1、设sq[l…maxsize]为一个顺序存储的栈，变量top指示栈顶元素的位置。作进栈操作时，

必须判别—。如要把栈顶元素取到x中，需执行语句。

2、设一个二叉树共有50个叶结点（终端结点），则共有个度为2的结点。

3、在单链表中，若要在指针p所指结点（data,next）后插入指针s所指结点，则需要执行下

列两条语句：s-*next=p-*next;。

4、3个结点可构成棵不同形状的树。

5、利用直接选择排序算法对n个记录进行排序，最坏情况下，记录交换的次数为

6、如果含n个顶点的图是一个环，则它有棵生成树。

7、如果要将序列｛50,16,23,68,94,70,73｝建成堆，则只需把16与相互交换

即可。

8、在一棵高度为h的平衡二叉树中，最少含有个结点，最多含有2h个结

点O

9、假设一个9阶的上三角矩阵A按列优先顺序压缩存储在一维数组B中，其中B|0]

存储矩阵中第1个元素all,则B[31]中存放的元素是。

10、在单链表上难以实现的排序方法有和堆排序。

四、简答题（每题10分，共60分）

1、在单链表、双链表和单循环链表中，若仅知道指针p指向某结点，不知道头指针，能

否将结点P从相应的链表中删去？若可以，其时间复杂度各为多少？

2、一项工程由Pl、P2、…、P6六项子工程组成，这些工程之间有下列关系：PKP2,

P3Vp6,P4Vp3,P2Vp6,P4Vp5,P1＜P3,P5Vp6,符号表示“优于”关系，例如

P2Vp6,表示P2完成后P6才能开始。请给出工程P的三种可能的施工顺序。

3、设散列表长度为14,散列函数H（x）=L2/iJ,其中i为键值中第一个字母在字母表中

的序号，若键值的输入顺序为Jan,Feb,Mar,Apr,May,Jun,Jul,Aug,Sep,

Oct,Nov,Dec,用拉链法处理冲突，要求：

（1）构造散列表。

（2）求出在等概率情况下，查找成功的平均查找长度。

4、设下图所示的二叉树是由森林转化而成的，试将它还原为森林。

5、何为队列的“假溢出”现象？如何解决？

6、分析以下程序段中语句x=x+y的执行次数。

x=0;y=0;

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

for(intj=l;j<=i;j++)

for(intk=l;k<=j;k++)

x=x+y;

五、算法设计题(每题15分，共30分)

说明：可以使用任何高级程序设计语言或伪(类)程序设计语言。

1、设计一个算法，求出指定结点在给定的二叉排序树中所在的层次。

2、已知线性表的元素按递增顺序排列，并以带头结点的单链表作存储结构。试编写一个删

除表中所有值大于min且小于max的元素(若表中存在这样的元素)的算法。

数据结构试题2答案

一、1——5：CDDBB6——10:CBDAA

二、1----5：VVVxx6-----10：xVxxx

三、1、①栈是否满(或top=maxsize)②x=sq[top|2、493、p->next=s;

4、25、n-16、n7、508、h9、A8210、快速排序

四、1、答案：在单链表中不能删除，而在双链表和单循环链表中可以删除p结点。双链

表的删除时间复杂度为0(1),单循环链表删除p结点的时间复杂度为O(n)。

2、答案：可给出有向图表示各子工程间的关系按照入度为零的结点先访问的原则，访问各

个结点即可。

找出3个可能的施工顺序如下：

Pl,P2,P3,P4,P5,P6

Pl,P4,P2,P3,P5,P6

P4,P5,Pl,P2,P3,P6

3、答案：(1)：

(2)ASL=(l*7+2*4+3*l)/12=5。

4、答案:

5、答案：队列的“假溢出”现象是指用数组实现的顺序队列中，对尾指针已达到数组的下

标上界产生上溢而对头指针之前还有若干空间闲置的现象。解决的办法之一是利用循环

队列技术使数组空间首尾相连。

6、答案：

72iJn+1)1〃21〃

2ZX1=XX./=X《J=弓Z/+三Zi

j==l左=]/=£/=1j=]2=[2f=]

1J2(T2+1)(272+1)172(72+1)72(72+1)(72+2)

=­•-------------------1---.----------=------------------

26226

五、1、答案：intlevel(t,p)；

bitree*t,*p;

{intcount;

count=0;

jf(t==NULL)

return(O);

else{count=count+l;while(t->data!=p->data){

if(t—data<p-data)

t=t-*rchild;

else

t=t-*lchild;

count=count+l;}}

return(count);

2、答案：delete(head,max,min)〃删除有序单链表中所有值大于min且小于

max的元素linklist*head;

intmax,min;

{linklist*p,*q;

if(hcad!=NULL)

{q=head;

p=head->next;}

while((p!=NULL)&&(p-*data<max))

p=p-*next:

q->next=p;}

数据结构试题3

一、单项选择题（每小题3分，共30分）

1、假设有n个关键字，它们具有相同的Hash函数值，用线性探测法把这n

个关键字存入到Hash地址空间中要做（）次探测。

A>ii2B、n（n+l）C>n（n+l）/2D、n（n-l）/2

2、若有一个栈的输入序列是1,2,3,…，n输出序列的第一个元素是n,则

第i个输出元素是（）o

A>n-iB、n-i-1C>n-i+1D、不确定

3、在一棵度为3的树中，度为3的结点数为2个，度为2的结点数为1个，

度为1的结点树为2个，那么度为0的结点数为（）。

A、4B、5C、6D、7

4、在一个具有n个结点的无向完全图中，包含有（）条边。

A、n（n-l）/2B、n（n-l）C、n（n+l）/2D、n2

5、已知一个有序表为（13,18,24,35,47,50,62,83,90,115,134）,当

二分检索值为90的元素时，需（）次比较可检索成功。

A、1B、2C、3D、4

6、在所有排序方法中，关键字的比较次数与记录的初始排序无关的是（）o

A、Shell排序B、冒泡排序C、直接插入排序D、直接选择排序

7、已知8个元素（34,76,45,18,36,54,92,65）,按照依次插入结点的

方法生成一棵二叉排序树，该树的深度为（

A、4B、5C、6D、7

8、设有一个10阶的对称矩阵A,采用压缩存储方式以行序为主存储，a00为第

一个元素，其存储地址为0,每个元素占有1个存储地址空间，则a85的

地址为（）o

A、13B、33C、17D、32

9、设关键字序列为：3,7,6,9,8,1,4,5,2。进行排序的最小交换次数

为（

A、6B、7C、8D、20

10、给定权的集合｛15,3,14,2,6,9,16,17）,所构造出的哈夫曼树的带

权路径长度为（

A、129B、219C、189D、229

二、判断题（认为对的，在题后的括号内打“J”，错的打“x”，每小题1分,

共10分）

1、在单链表中任何两个元素的存储位置之间都有固定的联系，因为可以从头结

点进行查找任何一个元素。（）

2、若一个叶子结点是某子树的中序遍历序列的最后一个结点，则它必是该子树

的先序遍历中的最后一个结点。（）

3、用相邻矩阵法存储一个图时，不在考虑压缩存储的情况下，所占用的存储空

间大小与图中结点的个数有关，而与图的边数无关。（）

4、哈希表的查找效率主要取决于哈希建表时所选取的哈希函数和处理冲突

的方法两个方面。（）

5、因为算法和程序没有区别，所以在数据结构中二者是通用的。（）

6、进栈操作push（xQ）作用于链接栈时，无须判满。（）

7、稳定排序算法是最好的。（）

8、二叉搜索树的左、右子树都是二叉搜索树。（）

9、先序遍历一棵二叉搜索树所得的结点访问序列不可能是键值递增序列。（）

10、表中的每一个元素都有一个前驱和后继元素。（）

三、填空题（每小题2分，共20分）

1、在散列表（Hash）查找中，评判一个散列函数优劣的两个主要条件是_______

和。

2、设根结点处在第一层，那么具有n个结点的完全二叉树，其高度为o

3、快速排序方法的最坏时间复杂度为,平均时间复杂度为

4、给定表（55,63,44,38,75,80,31,56）,用筛无法建立初始堆，则初始

堆表为o

5、设图G的顶点数为n,边数为e,各顶点的度数为D（Vi）,则e=。

6、将5个不同的数据进行排序，至少需要比较次，至多需要比较

次。

7、二分折半查找的查找速度一般比顺序查找的速度快，设有100个元素，用二

分折半查找时，最大比较次数是一，最小比较次数是_o

8、由a,b,c3个结点构成的二叉树，共有种不同的结构。

9、在一棵高度为h的平衡二叉树中，至少含有个结点，最多含有2h

-1个结点。

10、在一个单链表中删除*p结点，应执行如下操作：

q=p->next;

pfdata=p—next—data;

pfnext=;

free（q）;

四、简答题（每题10分，共60分）

1、在单链表、双链表和单循环链表中，若仅知道指针p指向某结点，不知道头

指针，能否将结点P从相应的链表中删去？若可以，其时间复杂度各为多少？

2、假设用干通讯的电文仅有8个字母组成.字母在电文中出现的频率分别为:

7,19,2,6,32,3,21,10。试用这8个频率值构造哈夫曼树，并画出该

哈夫曼所对应的森林。

3、己知一个长度为12的表（Jan,Feb,Mar,Apr,May,June,July,Aug,

Sep,Oct,Nov,Dec）：

（1）构造最价二叉排序树；

(2)试求在等概率情况下对此二又排序树进行折半检索时检索成功的平均长

度。

4、对于下图，试给出：

(1)每个顶点的入度和出度；(2)邻接矩阵；

(3)逆邻接表；(4)强连通分量；

5、快速排序、插入排序、自然两路归并排序、堆排序,哪一种排序方法所需的

辅助空间最大？请简单说明。

6、分析以下程序段中语句x=x+y的执行次数。

x=0;y=0;

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

for(intj=l;,j<=i;j++)

for(intk=l;k<=j;k++)

x=x+y;

五、算法设计题(每题15分，共30分)

说明：可以使用任何高级程序设计语言或伪(类)程序设计语言。

1、假设以二叉链表作为二叉树存储结构，其类型定义如下：

typedefstructnode

{chardata;

structnode*lchild,*rchild;〃左右孩子指针

}BinTNode,*BinTree;

写一函数，完成以下功能：

对二叉树中每个结点，如果其左孩子为空(右孩子不为空)，则将其右孩

子设置为左孩子。

2、已知线性表的元素按递增顺序排列，并以带头结点的单链表作存储结

构。试编写一个删除表中所有值大于min且小于max的元素(若表中

存在这样的元素)的算法。

数据结构试题3答案

一、1——5：CCCAB6—10：DCBAD

二、1------5：xVVVx6------10：VxVxx

三、1、①值均匀分布于表空间以减少冲突②函数尽可能简单以方便计算

2、logn的最小整数+1①O(n2)②O(nlogn)

4、(3138445675805563)或(8075555663443138)

5、().5*D(Vi)之和(i…n)6、①4②10

7、①7②18、59、h10、p-*next-*next

四、1、答案：在单链表中不能删除，而在双链表和单循环链表中可以删除p

结点。双链表的删除时间复杂度为0(1),单循环链表删除p结点的时

间复杂度为O(n)o

2、答案：（哈夫曼树有多种形态，不是唯一的。）

（1）哈夫曼树为：

（2）哈夫曼树所对应的森林为:

3、答案：（1）

（2）在等概率情况下检索成功的平均检索长度：

ASL=（1*1+2*2+3*4+4*4+5*1）/12=38/12=19/6

3、答案：（1）各个顶点的入度和出度如下：

顶点：123456

入度：221321

出度：123032

（2）邻接矩阵为：（3）逆邻接表为:

00

I0

00

00

II

01

(4)、强连通分量有如下3个:

o0

5、答案:快速排序需要的辅助空间与辅助栈的深度有关,平均情况下为O(logn),

最坏情况下需要O(n)；插入排序和堆排序只需要一个元素大小的辅助空间

在元素交换时用，为0(1)；而自然两路归并排序需和待排序数组同样大小的

辅助空间，为O(n),所以自然两路归并排序所需的辅助空间最大，快速排

序次之，插入排序和堆排序最小。

6、答案：

niJnin“/\\I〃)1〃

ESS1=SXJ=S+=*Zi2Tgi

/=1J=lk=lz=lj=1/=122z=12z=1

+1)(2〃+1).〃(〃+I)_+1)(〃+2)

-2•62*2―6~

五、1、答案：voidexchange(BinTreeT)

{if(T)

{if(!T-*lchild&&T-*rchild)

{T->lchild=T-*rchild;

T-*rchild=NULL;)

exchange(T-*lchild);

exchange(T->rchild);)}

2、答案：delete(head,max,min)〃删除有序单链表中所有值大于min且小

于max的元素linklist*head;

intmax,min;

{linklist*p,*q;

if(head!=NULL)

{q二head;

p=headfnext;}

while((p!=NULL)&&(p->data<max))

p二p-next;

q->next=p;}

数据结构试题4

一、单项选择题(每小题3分，共30分)

1.一般情况下将递归算法转换为等价的非递归算法应设置.()

[A]堆栈[B]队列[C]数组[D]堆栈或队列

2.设队列的输入序列是1、2、3、4,则只有是其出队序列。()

[A]1234[B]2134[C]1432[D]4312

3.C语言中要保存10个字符的字符串，至少需要声明大小为一的一维数组。

()

[A]10[B]o[A]F(0)=0[B]F(l)=l[C]F(0)=l[D]

F(n)=n

4.若一棵哈夫曼树有20个度为2的结点，则它共有个叶结点。()

[A]19[B]21[C]23[D]25

5.如果T2是由有序树T转换而来的二叉树，那么T中结点的后根序列就是

T2中结点的o()

[A]先根序列[B]中根序列[C]后根序列[D]层次序列

6.有向图中所有顶点的入度之和等于所有顶点的出度之和的一倍。()

[A]lIB]2[C]1/2[D]不一定

7.递归函数F(n)=F(n・l)+n+l(n>l)的递归出口是___.()

|A]F(0)=0|B]F(1)=1[C]F(0)=l|DlF(n)=n

8.在下列算法中，算法可能出现以下情况：在最后一趟开始之前，所有

的元素都不在其最终的位置上。()

[A]堆排序[B]冒泡排序[C]插入排序[D]快速排序

9.在对n个元素进行冒泡排序的过程中,最好情况下的时间复杂度为一o()

[A]O(1)[B]O(log2n)[C]O(n2)[D]O(n)

10.具有四层结点AVL树至少有个结点。()

[A]10[Bl9[C]8[D]7

二、填空题(每小题2分，共20分)

1.在线性结构、树结构和图结构中，前驱和后继结点之间分别存在着的

、和的联系。

2.在线性表而单链接存储中，指向下一结点的指4%next。若一个元素所在结

点的地址为P，则其后继结点的地址为,若假定p为一个数组

a中的下标，则其后继结点的下标为。

3.栈又称为表，队列又称为表。

4.后缀表达式“45+3*24+*"的值为o

5.一棵深度为5的满二叉树中的结点数为个，一棵深度为3的满四叉树中

的结点数为个。

6,对于一棵含有40个结点的理想平衡树，它的高度为o

7.每次直接或通过基准元素间接比较两个元素，若出现逆序排列时就交换它们

的位置，此种排序方法叫做____排序；每次使两个相邻的有序表合并成

一个有序表的排序方法叫做_______排序.

8.当从一个小根堆中删除一个元素时，需要把_______元素填补到________位

置,然后再按条件把它逐层_______调整。

9.对于一个具有n个顶点的图，若采用邻接矩阵表示，则矩阵大小为。

10.向一棵B一树插入元素的过程中，若最终引起树根结点的分裂，则新树的高

度比原树增;从一棵B一树删除元素的过程中，若最终引起树根

结点的合并，则新树的高度比原树减O

三、判断题（认为对的，在题后的括号内打“，”，错的打“X”，每小题1

分，共10分）

1.给出不同输入序列建造二叉排序树，一定得到不同二叉排序树。（）

2.有向图的邻接表和逆邻接表中的结点数一定相同。（）

3.图G的拓扑序列唯一，则其弧数必为n・l（其中n为G的顶点数）。（）

4.在索引顺序文件中插入新的记录时，必须复制整个文件。（）

5.如果某种排序算法是不稳定的，则该方法没有实际的应用价值。（）

6.对n个记录进行冒泡排序，在最坏情况下所需要的时间是0（1?）。（）

7.在线性结构中，每个结点都有一个直接前驱和一个直接后继。（）

8.AVL树的任何子树都是AVL树。（）

9.B+树既适于随机检索，也适于顺序检索。（）

10.两个字符串相等的充要条件是两个串包含的字符相同。（）

四、简答题（每题10分，共60分）

1.说明数组和链表的区别，各有何优缺点？

2.已知序列（17,18,60,40,7,32,73,65,85）,请给出采用起泡排序法

对该序列作升序排序时的每一趟的结果。

3.邻接矩阵表示图时，若图中有1000个顶点，500条边，则形成的邻接矩阵有

多少个元素？有多少个非零元素？是否为稀疏矩阵？

4.简述二叉排序树的概念，并按给定的输入序列：

25、13、15、31、7、20、37

构造一棵二叉排序树。

5.一棵二叉树的前序、对称序和和后序序列分别如下，其中有一部分未显示出

来，试求空格处内容，并画出该二叉树对应的森林。

前序：_B_F_JCEH_G

对称序：D_KFIA_E.JC_

后序：_K_FBHJ_G_A

6.有一份电文中共使用五个字符：a、b、c、d、e,它们的出现频率依次为8、

14、10、4、18,请构造相应的哈夫曼树（左子树根结点的权小于等于右子树

根结点的权），求出每个字符的huffman编码。

五、算法设计题（每题15分，共30分）

说明：可以使用任何高级程序设计语言或伪（类）程序设计语言。

1.己知长度为n的线性表A采用顺序存储结构，写一算法，删除该线性表中所

有值为item的数据元素，并给出算法的时间复杂度。

2.设计一个算法，统计一个采用邻接矩阵存储、具有n个顶点的无向无权图所

有顶点的度。

数据结构试题4答案

一、1.A2.A3.B4.B5.B6.A7.B8.C9.I）10.1）

二、1.1:11:NM:N（或者一对一1对多多对多）

2.p->nexta[p].next3.后进先出先进先出4.162

5.31216.67.交换二路归并（或归并）

8.堆尾堆顶向下9.n210.11

三、1.X2.V3.V4.X5.X6.V7.X8.V9.X10.X

四、答案：区别：数组占用连续的内存空间，链表不要求结点的空间连续。

各有何优缺点：（1）插入和删除操作。数组插入和删除需移动数据元素,

链表插入和删除不移动数据元素，链表比数组易于实现插入和删除操作；

（2）在空间占用方面，数组优于链表；

（3）在数据存取方面，数组是随机存取方式，而链表是顺序存取方式。

2.答案：采用起泡排序法排序的各趟结果如下:

初始：17,18,60,40,07,32,73,65,85

第一趟：17,18,40,07,32,60,65,73,85

第二趟：17,18,07,32,40,60,65,73,85

第三趟：17,07,18,32,40,60,65,73,85

第四趟：07,17,18,32,40,60,65,73,85

第五趟：07,17,18,32,40,60,65,73,85

第五趟无元素交换，排序结束。

3.答案：邻接矩阵有1000000个元素。

对于有向图，有500个非零元素；对于无向图，有1000个非零元素。

此邻接矩阵是稀疏矩阵。

4.答案：如果一棵二叉椅的每个结点对应于一个关键码，且每个结点的左子树

中所有结点的关键码值都小于该结点的关键码值，而右子树中所有结点的关

键码值都大于该结点的关键码值，称此二叉树为二叉排序树。

5.答案：前序区BHF丛ICEHJ_G

对称序:D皂KFIA_HEJCG

后序:口KJ.FBHJE_GX_A

对应的森林为：

6.答案:

相应的哈夫曼编码为：:001b:10c:01d:000e:ll.

五、1答案：算法的ADL描述如下：

算法DEL(A,n,item)

i-1VVHILE(i<=n)DO

IF(A[i]=item)THEN

{FORj=i+lTOnDO

A[j-l]+A[j]

n^n-1}

ELSE

i-i+1

算法的时间复杂度为O(n2)

2.答案：假设邻接矩阵为adjacency(二维数组)，顶点的度保存在一维数组A

中0

算法的ADL描述如下：

[初始化]

FORi=lTOnDO

A[i]T

FORi=lTOnDO

FORj=lTOnDO

IFadjacency[ij]=lTHEN

A[i]*-A[i]+1

数据结构试题5

一、单项选择题(每小题3分，共30分)

1.线性表是具有n个的有限序列。()

[A]表元素[B]字符[C]数据元素[D]信息项

2.若长度为n的线性表采用顺序存储结构，在第i个位