数据结构试题库

1 绪论

沈阳理工大学应用技术学院

信息与控制学院 计算机科学与技术教研室

2011-5-8

- 1 -

数据结构复习题：绪论 单选题

1、在数据结构中，与所使用的计算机无关的数据叫____结构。 A存储|B物理|C逻辑|D物理和存储

2、在数据结构中，从逻辑上可以把数据结构分成______。

A动态结构和静态结构|B紧凑结构和非紧凑结构|C线性结构和非线性结构|D内部结构和外部结构图 3、数据结构在计算机内存中的表示是指_______。

数据的存储结构|数据结构|数据的逻辑结构|数据元素之间的关系 4、在数据结构中，与所使用的计算机无关的是数据的______结构。 逻辑|存储|逻辑和存储|物理

5、在以下的叙述中，正确的是_____。

线性表的线性存储结构优于链表存储结构|二维数组是其数据元素为线性表的线性表|栈的操作方式是先进先出|队列的操作方式是先进后出

6、在决定选取何种存储结构时，一般不考虑_______。

各结点的值如何|结束个数的多少|对数据有哪些运算|所用编程语言实现这种结构是否方便 7、在存储数据时，通常不仅要存储各数据元素的值，而且还要存储_______。 数据的处理方法|数据元素的类型|数据元素之间的关系|数据的存储方法 8、下面说法错误的是_______。

(1) 算法原地工作的含义是指不需要任何额外的辅助空间

(2) 在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法 (3) 所谓时间复杂度是指最坏情况下，估计算法执行时间的一个上界 (4) 同一个算法，实现语句的级别越高，执行效率越低 (1)|(1)、(2)|(1)、(4)|(3)

9、通常要求同一逻辑结构中的所有数据元素具有相同的特性。这意味着______。 数据元素具有同一特点|不仅数据元素所包含的数据项的个数要相同，而且对应的数据项的类型要一致|每个数据元素都一样|数据元素所包含的数据项的个数要相等 10、以下说法正确的是_______。

数据元素是数据的最小单位|数据项是数据的基本单位|数据结构是带结构的数据项的集合|一些表面上很不相同的数据可以有相同的逻辑结构

11、数据项是数据的最小单元, 数据元素是数据的基本单位. 数据项|数据元素|信息项|表元素

12、数据结构是指__数据元素__以及它们之间的__结构___.

(1)数据元素 (2)结构|(1)计算方法 (2)关系|(1)逻辑存储 (2)运算|(1)数据映像 (2)算法 13、计算机所处理的数据一般具备某种内在的关系,这是的指_____.

数据和数据之间存在的某种关系|元素和元素之间存在某种关系|元素内部具有某种结构|数据项和数据项之间存在某种关系

14、数据的逻辑结构可以分为_____两类.

动态结构和表态结构|紧凑结构和非紧凑结构|线性结构和非线性结构|内部结构和外部结构 15、数据的逻辑结构是指_____关系的整体.

数据元素之间逻辑|数据项之间逻辑|数据类型之间|存储结构之间

16、在存储数据时,通常不仅要存储各数据元素的值,而且还要存储_____.

- 2 -

数据的处理方法|数据元素的类型|数据元素之间的关系|数据的存储方法 17、在数据的存储结构中,一个存储结点存储一个_____. 数据项|数据元素|数据结构|数据类型

18、在计算机的存储器中表示时,物理地址和逻辑地址直接对应并且是连续的,称之为_____. 逻辑结构|顺序存储结构|链式存储结构|以上都对 19、数据采用链式存储结构时,要求_____.

每个结点用占一片连续的存储区域|所有结点占用一片连续的存储区域|结点的最后一个数据域是指针类型|每个结点有多少个后继,就设多少个指针域 20、数据的运算_____.

效率与采用何种存储结构有关|是根据存储结构来定义的|有算术运算和关系运算两大类|必须用程序设计语言来描述

21、下列说法中,不正确的是_____.

数据元素是数据的基本单位|数据项是数据中不可分割的最小可标识单位|数据可由若干个数据元素构成|数据项可由若干个数据元素构成 22、_____不是算法的基本特性.

可行性|长度有限|在规定的时间内完成|确定性

23、计算机中算法指的是解决某一问题的有限运算序列,它必须具备输入、输出、_____.

可行性、可移植性和可扩充性|可行性、有穷性和确定性|确定性、有穷性和稳定性|易读性、稳定性和确定性

24、以下不属于算法特性的是_____. 可行性|有输入|确定性|健壮性

25、下面关于算法的说法正确的是_____.

算法最终必须由程序实现|算法的有穷性是对于任意的一组输入值必须在有穷步骤后结束|算法的可行性是指指令不能有二义性|以上几个都是错误的 26、算法的时间复杂度与______有关

问题规模|计算机硬件性能|编译程序质量|程序设计语言 27、算法分析的主要任务是分析_____.

算法是否具有较好的可读性|算法中是否存在语法错误|算法的功能是否符合设计要求|算法的执行时间和问题规模之间的关系

28、某算法的时间复杂度为O(n2),表明该算法的_____.

问题规模是n2|执行时间等于n2|执行时间与n2成正比|问题规模与n2成正比 29、算法分析的目的是_____.

找出数据结构的合理性|研究算法中输入和输出关系|分析算法的效率以求改进|分析算法的易读性和文档性 30、线性表是具有n个______的有限序列。 表元素|字符|数据元素|数据项 31、线性表是______。

一个有限序列，可以为空|一个有限序列，不可以为空|一个无限序列，可以为空|一个无限序列，不可以为空

32、线性表采用链表存储时，其地址______。

必须是连续的|一定是不连续的|部分地址必须是连续的|连续与否均可以 33、链表不具备的特点是______。

可随机访问任一结点|插入删除不需要移动元素|不必事先估计存储空间|所需空间与其长度成正比 34、线性表的静态存储结构与顺序存储结构相比优点是_______。

所有的操作算法实现简单|便于随机存取|便于插入和删除|便于利用零散的存储器空间

- 3 -

35、设线性表有n个元素，以下操作中，_______在顺序表上实现比在链表上实现效率更高。

输出第i(1<=i<=n)个元素值|交换第1个元素与第2个元素的值|顺序输出这n个元素的值|输出与给定值x相等的元素在线性表中的序号

36、对于一个线性表，既要求能够较快地进行插入和删除，又要求存储结构能够反映数据元素之间的逻辑关系，则应采用_______存储结构。 顺序|链式|散列|索引

37、设线性表中有2n个元素，以下操作中，______在单链表上实现要比在顺序表上实现效率更高。

删除指定的元素|在最后一个元素的后面插入一个新元素|顺序输出前k个元素|交换第i个元素和第2n-i-1个元素的值(i=0，1，?，n-1)

38、需要分配较大空间，插入和删除不需要移动元素的线性表，其存储结构是______。 单链表|静态链表|线性链表|顺序存储结构

39、如果最常用其所长的操作是取第i个结点及其前驱，则采用______结构方式最节省时间。 单链表|双链表|单循环链表|顺序表

40、与单链表相比，双链表的优点之一是______。

插入、删除操作更简单|可以进行随机访问|可以省略表头指针或表尾指针|访问前后相邻结点更灵活 41、数据结构在计算机内存中的表示是指______.

数据的存储结构|数据结构|数据的逻辑结构|数据元素之间的关系 42、下面程序段的时间复杂度为_________． O(m)| O(n)|O(m*n)|O(m+n)

for(int i=0;i

for(int j=0;j

数据结构复习题：绪论 判断题

1、数据元素是数据的最小单位。 2、数据项是数据的基本单位。 3、数据元素是数据的最小单位

4、数据对象就是一组任意数据元素的集合

5、任何数据结构都具备3个基本运算: 插入、删除和查找. 6、数据是由一些类型相同的数据元素构成的

7、数据是逻辑结构与各数据元素在计算机中如何存储有关 8、如果数据元素值发生改变,则数据的逻辑结构也随之改变. 9、逻辑结构相同的数据,可以采用多种不同的存储方法. 10、逻辑结构相同的数据,结点类型也一定相同

11、逻辑结构不相同的数据,必须采用不同的存储方式来存储 12、数据的逻辑结构是指数据的各数据项之间的逻辑关系.

13、算法的优劣与算法描述语言有无关，但与所有计算机有关。

14、算法可以用不同的语言描述，如果用C或Pascal等高级语言来描述，则算法实际上就是程序了。 15、程序一定是算法。

16、算法最终必须由计算机程序实现。F

19、健壮的算法不会因非法入输数据而出现莫名其妙的执行结果。

- 4 -

数据结构复习题：绪论 算法分析题

1、求两个n阶矩形的乘法C=A*B,其算法如下: #define MAX 100

void maxtrixmult(int ,float a[MAX][MAX],b[MAX][MAX],float c[MAX][MAX]) {

int i,j,k; float x;

for(i=1;i<=n;i++) //① {

for (j=1;j<=n;j++) //② {

x=0; //③ for(k=1;k<=n;k++) //④ x+=a[i][k]*b[k][j]; //⑤ c[i][j]=x; //⑥ } } }

计算①～⑥各语句的频度,并分析该算法的时间复杂度。

2、设n是偶数,试计算运行下列程序段后m的值并给出该程序段的时间复杂度。 m=0;

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

for(j=2*1;j<=n;j++) m++; 3、阅读下列算法: void suan_fa(int n) {

int i,j,k,s,x;

for (s=0,i=0;i

i++; j--; x+=2; }

pirntf(\}

(1) 分析算法中语句\的执行次数; (2) 分析算法中语句\的执行次数;

- 5 -

(3) 分析该算法的时间复杂度;

(4) 假定n=5, 试指出执行该算法的输出结果。

6、设n是偶数,试计算运行下列程序段后m的值并给出该程序段的时间复杂度。 int m=0,i,j;

for (i=1;i<=n;i++) for (j=2*i;j<=n;j++)

m++; m=n*n/4 O() 数据结构复习题：绪论 填空题

1、一个数据结构在计算机中___映像___称为存储结构。

2、数据逻辑结构包括 、 和 三种类型，树形结构和图形结构合称为________。 3、在线性结构中，第一个结点________前驱结点，其余每个结点有且只有_______个前驱结点：最后一个结点______后续结点，其余每个结点有且只有______个后续结点。 4、在树形结构中，树根结点没有______结点，其余每个结点有且只有______个前驱结点:叶子结点没有______结点,其余每个结点后的后续结点可以_______

5、在图形结构中，每个结点的前驱结点数和后续结点数可以___任意多个_____。

6、线性结构中元素之间存在___一对一______关系，树形结构中元素之间存在___一对多____关系，图形结构中元素之间存在____多对多____关系。

7、算法的5个重要特性是_________、__________、__________、输入和输出。 8、算法可以用不同的语言描述，如果用C语言或PASCAL语言等高级语言来描述，则算法实现上就是程序了。这个断言是________。

9、数据结构、数据元素和数据项在计算机中的映射(或表示)分别称为存储结构、结点和数据域。这个断言是_______。

10、下面程序段的时间复杂度是_______。

for (i=0;i

11、下面程序段的时间复杂度是__O(sqrt(n))_____。

i=s=0; while(s

i++; s+=i; }

12、下面程序段的时间复杂度是_______。 s=0;

for (i=0;i

for (j=0;j

13、下面程序段的时间复杂度是___O(log3n)_____。 i=1;

- 6 -

while(i<=n) i=i*3;

14、有如下递归函数fact(n),分析其时间复杂度。 int fact(int n) {

if (n<=1)

return 1; else

return (n*fact(n-1)); }

15、指出下列各算法的时间复杂度 (1) prime(int n) {

int i=2;

while(n%i!=0 && i

if (i*1.0>sqrt(n))

printf \是一素数\ else

printf \不是一素数\} O(sqrt(n)) (2) sum1(int n) {

int p=1,sum=0,i; for (i=1;i<=n;i++) {

p*=i; sum+=p; }

returm (sum); } (3) sum2(int n) {

int sum=0,i,j; for (i=1;i<=n;i++) {

p=1;

for (j=1;j<=i;j++) p*=j; sum+=p; }

return (sum); }

16、数据的逻辑结构是指_____.

- 7 -

17、一个数据结构在计算机中的_表示_____称为存储结构.

18、顺序存储方法是把逻辑上__相邻的结点___存储在物理位置上___相邻的存储单元___里;链式存储方法中结点间的逻辑关系是由 附加的指针字段表示____的.

19、数据结构是指研究数据的__存储结构___和__逻辑结构___以及它们之间的相互关系,并对这种结构定义相应的__运算___,设计出相应的__算法___,从而确保经过这些运算后所得到的新结构是原来的结构类型. 20、一个算法具有5个特性:_____、_____、_____、输入和输出。 21、算法的执行时间是_____的函数。

22、数据的逻辑结构是从逻辑上描述数据,它与数据的___存储结构、物理结构___无关,是独立于计算机的. 23、数据的逻辑结构被分为____________、____________、___________和____________４种。 24、数据的存储结构被分为____________、____________、____________和____________４种。

25、在线性结构、树形结构和图形结构中，前驱和后继结点之间分别存在着____1:1________、____1：N________、_____M:N_______的联系。

26、一种抽象数据类型包括______数据______和____操作_______两个部分。 27、从一维数组a[n]中顺序查找出一个最大值元素的时间复杂度为____________，输出一个二维数组b[m][n]中所有元素值的时间复杂度为____________

28、在下面程序段中，s=s+p语句的执行次数为______n______，p*=j语句的执行次数为______n*(n+1)/2______，该程序段的时间复杂度为______O(n*n)______。 int i=0,s=0; while(++i<=n) { int p=1;

for(int j=1;j<=i;j++) p*=j; s=s+p;}

29、一个算法的时间复杂度为（3*n*n+2nlog2n+4n-7)/(5n)，其数量级表示为_____O(n)_______。

30、从一个数组a[10]中顺序查找元素时，假定查找每个元素的概率都相同，则进行一次查找运算时的平均查找长度（即同元素的平均比较次数）为____________。

31、从一个数组a[7]中顺序查找元素时，假定查找第1个元素a[0]的概率为1/3，查找第2个元素a[1]的概率为1/4，其找其余元素的概率均相同，则在查找成功时同元素的平均比较次数为____35/12________。 32、对于一个n*n的矩阵Ａ的任意矩阵元素a[i][j]，按行存储时和按列存储时的地址之差是

____(i-j)*(n-1)*d______。设两种存储时的开始存储地址均为ＬＯＣ(0,0)，每个元素所占存储单元数均为d。 33、设有一个二维数组A[10][20]，按行存放于一个连续的存储空间中，A[0][0]的存储地址是200，每个数组元素占1个存储字，则A[6][2]的存储字地址是____________

34、设有一个二维数组A[10][20]，按列为主序存放于一个连续的存储空间中，A[0][0]的存储地址是200，每个数组元素占1个存储字，则A[6][2]的存储字地址是____________。

37、在线性表的单链接存储结构中，每个结点包含有两个域，一个叫____________，另一个叫____________域。

数据结构复习题：绪论 问答题

1、当你为解决某一问题而选择数据结构时,应从哪些方面考虑? 2、简述逻辑结构与存储结构的关系. 3、数据运算是数据结构的一个重要方面,试举例说明两个数据结构的逻辑结构和存储方式完全相同,只是对于运算的定义不同,因而两个结构具有显著不同的特性,则这两个数据结构是不同的.

- 8 -

数据结构复习题答案：绪论 问答题

1、解答：通常从两方面考虑：第一是算法所需的存储空间量；第二是算法所需的时间。对算法所需的时间又涉及以下三点：

（1）程序运行时所需输入的数据总量。 （2）计算机执行每条指令所需的时间。 （3）程序中指令重复执行的次数。

2、答：数据的逻辑结构反映数据元素之间的逻辑关系（即数据元素之间的关联方式或“邻接关系”），数据的存储结构是数据结构在计算机中的表示，包括数据元素的表示及其关系的表示。 3、答：栈和队列的逻辑结构相同，其存储表示也可相同（顺序存储和链式存储），但由于其运算集合不同而成为不同的数据结构。

2 线性表

沈阳理工大学应用技术学院

信息与控制学院 计算机科学与技术教研室

2011-5-8

- 9 -

- 10 -

50、在由数组a中元素结点构成的单链表中，在下标为i的结点的后面插入一个下标为j的结点时，需要进行的操作为____________和____________语句。 数据结构复习题：线性表 问答题

1、线性表有两种存储结构：一是顺序表，二是链表。试问： (1)两种存储表示各有哪些主要优缺点?

(2)如果有n个线性表同时并存，并且在处理过程中各表的长度会动态发生变化，线性表的总数也会自动地改变。在此情况下，应选用哪种存储结构?为什么?

(3)若线性表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取线性表中的元素，那么，应采用哪种存储结构?为什么?

解答：(1)顺序存储是按索引（隐含的）直接存取数据元素，方便灵活，效率高，但插入、删除操作时将引起元素移动，因而降低效率；链接存储内存采用动态分配，利用率高，但需增设指示结点之间有序关系的指针域，存取数据元素不如顺序存储方便，但结点的插入、删除操作十分简单。 (2)应选用链接表存储结构。其理由是，链式存储结构用一组任意的存储单元依次存储线性表里各元素，这里存储单元可以是连续的，也可以是不连续的。这种存储结构，在对元素作插入或删除运算时，不需要移动元素，仅修改指针即可。所以很容易实现表的容量扩充。

(3)应选用顺序存储结构。其理由是，每个数据元素的存储位置和线性表的起始位置相差一个和数据元素在线性表中的序号成正比的常数。由此，只要确定了起始位置，线性表中任一数据元素都可随机存取，所以线性表的顺序存储结构是一种随机存取的存储结构。而链表则是一种顺序存取的存储结构。 2、用线性表的顺序结构来描述一个城市的设计和规划合适吗?为什么?

不合适。因为一个城市的设计和规划涉及非常多的项目，很复杂，经常需要修改、 扩充和删除各种信息，才能适应不断发展的需要。有鉴于此，顺序线性表不能很好适应其需要，故是不合适的。 3、在单链表和双向表中，能否从当前结点出发访问到任一结点?

在单链表中只能由当前结点访问其后的任一结点，因为没有指向其前驱结点的指针。而在双向链表中，既有指向后继结点的指针又有指向前驱结点的指针，故可由当前结点出发访问链表中任一结点。 4、编写下列算法

(1)向类型有list的线性表L的第i个元素（0≤i≤L.len）之后插入一个新元素x。 (2)从类型为list的线性表L中删除其值等于x的所有元素。

(3)将两个有序表A和B合并成一个有序表C，其中A，B，C均为list类型的变参。 (1) 解答: status insert(SqList L,int i,ElemType x){

// 向线性表L中第i个元素之后插入值为x的新元素 (1) if (L.len = =m0) error('overflow');

(2) if (i<0) || (i>L.len) error ('out of range'); (3) for (j=L.len ;j>= i＋1;--j ) L.vec[j＋1]＝L.vec[j]; }

(4) L.vec[i＋1]＝x; (5) L.len＝len＋1; }

(2) 解答: status delete(L,x) {

// 从线性表L中删除其值等于x的所有元素 i＝1;

while (i<＝L.len ) if (L.vec[i]= =x ){

- 16 -

(Ⅰ) for( j＝i＋1 ;j<= L.len ;++j) L.vec[

5、编写下列算法，假定单链表的表头指针用HL表示，类型为linklist。 (1)将一个单链表中的所有结点按相反次序链接。 (2)删除单链表中第i个（i≥1）结点。 (3)删除单链表中由指针p所指向的结点。

(4)从带有附加表头结点的循环单链表中删除其值等于x的第一个结点。 (5)在单链表中指针p所指结点之前插入一个值为x的新结点。 (6)从循环单链表中查找出最小值。

(7)根据一维数组A(1:n)中顺序存储的具有n个元素的线性表建立一个带有附加表头结 点的单链表。 解答：(1)将一个单链表中的所有结点按相反次序链接。 (1) 解答: status contrary(HL){

// 使HL单链表中的所有结点按相反次序链接

p＝HL ; //p指向未被逆序的第一个结点，初始指向原表头结点 HL＝nil; //HL指向逆序后的表头结点，初始值为空 while (p!=nil ){

(1) q＝p; //q指向将被逆序链接的结点 (2) p＝p＾.next; (3) q＾.next＝HL; (4) HL＝q; } }

(2)删除单链表中第i个（i≥1）结点。 (2) 解答:status delete(HL,i){

(1) if (i<＝0) or (HL＝nil) error('not h&&le'); (2) if (i＝1 )

{ HL＝HL->next; return ; }

(3) j＝1; p＝HL; //p指针所指向的结点，是单链表中第j 6、对链表设置头结点的作用是什么?(至少说出两条好处)

解答：(1) 对带头结点的链表，在表的任何结点之前插入结点或删除表中任何结点，所要做的都是修改前一结点的指针域，因为任何元素结点都有前驱结点。若链表没有头结点，则首元素结点没有前驱结点，在其前插入结点或删除该结点时操作会复杂些。

(2) 对带头结点的链表，表头指针是指向头结点的非空指针，因此空表与非空表的处理是一样的。

7、在单链表、双链表和单循环表中，若仅知道指针p指向某结点，不知道头指针，能否将结点*p从相应的链表中删去？若可以，其时间复杂度各为多少？

解答：1. 单链表。当我们知道指针p指向某结点时，能够根据该指针找到其直接后继，但是由于不知道其头指针，所以无法访问到p指针指向的结点的直接前趋。因此无法删去该结点。

2. 双链表。由于这样的链表提供双向链接，因此根据已知结点可以查找到其直接前趋和直接后继，从而可以删除该结点。其时间复杂度为O(1)。 3. 单循环链表。根据已知结点位置，我们可以直接得到其后相邻的结点位置(直接后继)，又因为是循环链表，

- 17 -

所以我们可以通过查找，得到p结点的直接前趋。因此可以删去p所指结点。其时间复杂度应为O(n)。 8、简述顺序表和链表存储方式的特点。

答：顺序表可以直接存取数据元素，方便灵活、效率高，但插入、删除操作时将会引起元素的大量移动，因而降低效率；而链表内存采用动态分配，利用率高，但需增设指示结点之间关系的指针域，存取数据元素不如顺序表方便，但结点的插入、删除操作较简单。

9、有两个递增有序表，设计一个算法将它们归并成一个有序表(假设每个表中没有重复关键字的元素，归并时重复关键字的元素只归并一次)。 答：void Merge (LinkList &La, LinkList Lb) { pa=La->next; pb=Lb->next; p=La; while(pa && pb)

{ if (pa->data<=pb->data)

{p->next=pa; p=pa; pa=pa->next;} else

{p->next=pb; p=pb; pb=pb->next;} }

if(pa) p->next=pa; else p->next=pb; free(Lb); }

3 栈和队列

沈阳理工大学应用技术学院

信息与控制学院 计算机科学与技术教研室

2011-5-8

数据结构复习题：栈和队列

- 18 -

单选题

1、在一个具有n个单元的顺序栈中，假定以地址低端作为栈底，以top作为栈顶指针， 则当做退栈处理时，top变化为_____。

2、向顺序栈中压入元素时，是__先移动栈顶指针，后存入元素___。

3、在一个顺序存储的循环队列中，队首指针指向队首元素的__前一个位置___。 4、若进栈序列为1,2,3,4,进栈过程中可以出栈，则_____不可能是一个出栈序列。

5、在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队首指针和队尾指针，则判断队空的条件是_____。

6、在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队首指针和队尾指针，则判断队满的条件是_____。

7、向一个栈项指针为hs的链栈中插入一个*s结点时，则执行_____。

8、在一个链队列中，假定front和rear分别为队首指针和队尾指针，则进行插入*s结点的操作时应执行_____。

9、栈的特点是_______队的特点是______ 10、栈和队列的共同点是_______。

11、一个栈的进栈序列是a,b,c,d,e,则栈的不可能的输出序列是________。

12、若己知一个栈的进栈序列是1,2,3,?,n,其输出序列为p1,p2,p3,?,pn,若p1=n,则pi(1

16、若己知一个栈的进栈序列p1,p2,p3,?,pn，输出序列是1,2,3,?,n。若pn=1,则pi(1<=i

19、最不适合用作链栈的链表是___只有表头指针没有表尾指针的循环单链表_____。 20、向一个栈项指针为hs的链栈中插入一个s所指结点时，则执行_______。

21、从一个栈项指针为hs的链栈中删除一个结点时，用x保存被删结点的值，则执行__x=hs->data;hs=hs->next____。

22、一个队列的入队序列是1,2,3,4,则队列的输出序列是_______。

23、判定一个环形队列qu(最多元素为MaxSize)为空的条件是________。 24、判定一个环形队列qi(最多元素为MaxSize)为满队列的条件是________。 25、环形顺序队列中是否可以插入下一个元素,________。

26、环形队列用数组A[0...MaxSize-1]存放其元素值,己知其头尾指针分别是front和rear,则当前队列的元素个数是_______。

27、若用一个大小为6的一维数组来实现环形队列，且当前rear和front的值分别为0和3。当从队列中删除一个元素，再加入两个元素后，rear和front的值分别是______。 28、最不适合用作链队的链表是__只带队头指针的非循环双链表____。

29、在一个链队中，假设f和r分别为队头和队尾指针，则插入s所指结点的运算是_______。 30、在一个链队中，假设f和r分别为队头和队尾指针，则删除一个结点的运算是_______。 31、用单链表表示的链队的队头在链用不着的____链头____位置。 32、中缀表达式A*(B+C)/(D-E+F)的后缀表达式是________。

33、己知一个栈的进栈序列是ABC,出栈序列为CBA,经过的栈操作是________。 34、判定一个顺序栈st为(元素个数最多为MaxSize)空的条件为______。 35、判定一个顺序栈st(元素个数最多为MaxSize)为栈满的条件是______。 36、表达式a*(b+c)-d的后缀表达式是______。

- 19 -

37、表达式(2+2*3)*2+6*3/2的后缀表达式是______。

38、链栈与顺序栈相比有一个明显的优点,即___通常不会出现栈满的情况___。 39、最不适合用作链栈的链表是__只有表头指针没有表尾指针的循环单链表____。 40、如果以链表作为栈的存储结构,则退链栈操作时___必须差别链栈是否空___。

41、向一个不带头结点的栈指针为1st的链栈中插入一个s所指结点时,则执行______。

42、从一个不带头结点的栈顶指针为1st的链栈中删除一个结点时,用x保存被删结点的值,则执行______。 43、一个栈的进栈序列是a,b,c,d,e,则栈的不可能的输出序列是______.

44、在一个长度为n的顺序存储的集合中查找值为x的元素时，在等概率情况下，查找成功时的平均查找长度为_________。

45、在一个长度为n的链接存储的集合中查找值为x的元素时，算法的时间复杂度为___O(n)______。 46、已知一个元素x不属于一个长度为n的顺序或链接存储的集合Ｓ中的元素，把它插入集合Ｓ时不进行比较过程，则插入过程的时间复杂度为_________。 47、设一个具有t个非零元素的m*n大小的稀疏矩阵采用顺序存储，求其转置矩阵的普通转置算法的时间复杂度为____O(n*t)_____。

数据结构复习题：栈和队列 判断题

1、栈底元素是不能删除的元素。 2、顺序栈中元素值的大小是有序的。

3、在n个元素进栈后,它们的出栈顺序和进栈顺序一定正好相反。 4、栈顶元素和栈底元素有可能是同一个元素。

5、若用S[1]-S[m]表示顺序栈的存储空间,则对栈的进栈、出栈操作最多只能进行m次。F 6、空栈没有栈顶指针。

数据结构复习题答案：栈和队列 判断题 1、False 2、False 3、True 4、True 5、False 6、False

数据结构复习题：栈和队列 算法分析题

1、设计一个算法,利用栈的基本运算将指定栈中的内容进行逆转。 status Nizhuan(sqstacks, int a, int b, int t) {

If(s.top==s.base) error(‘no data’);

for(i=0;i

a=*--top; b=*s.base;

- 20 -

解答：d,e,b,g,h入队 d e b g h F r d,e出队

b g h F r i,j,k,l,m入队 b g h i j k l m F r

n,o,p入队 b g h i j k l m n o p

F r

所有元素均正好能入队，共有11个存储空间，恰好11个元素。

9、假设CQ[0..10]是一个环形队列,初始状态为front=rear=0,画出做完下列操作后队列的头尾指针的状态变化情况,若不能入队,请指出其元素,并说明理由。 d,e,b,g,h入队 d,e出队 i,j,k,l,m入队 b出队 n,o,p入队

解答： 图略 。

p不能入队，共有11个地址，p为第12个元素，故不能入队。

10、有5个元素,其进栈次序为A、B、C、D、E,在各种可能的出栈次序中,以元素C、D最先出栈(即C第一个且D第一个出栈)的次序有哪几个? 答：三个：CDEBA，CDBEA，CDBAE

11、设输入元素为1、2、3、P和A,入栈次序为123PA,元素经过栈后到达输出序列,当所有元素均到达输出序列后,有哪些序列可以作为高级语言的变量名?

答：一般说，高级语言的变量名是以字母开头的字母数字序列。故本题答案是: AP321,PA321,P3A21,P32A1,P321A。 12、简要叙述栈和队列的特点.

答：栈和队列都是插入和删除操作的位置受限制的线性表。栈是限定仅在表尾进行插入和删除的线性表，是后进先出的线性表，而队列是限定在表的一端进行插入，在另一端进行删除的线性表，是先进先出的线性表。

- 26 -

4 串

数据结构复习题：串单选题

沈阳理工大学应用技术学院信息与控制学院 计算机科学与技术教研室

2011-5-8

- 27 -

1、设字符串s1='abcdefg',s2='pqrst'，则运算s=concat(sub(s1,2,len(s2)),sub(s1,len(s2),2))后串值为_____。 2、空串与空白串是相同的,这种说法________。

3、串是一种特殊的线性表,其特殊性体现在________。 4、_______是C语言中\的子串。

5、有串s1='ABCDEFG',s2='PQRST',假设函数con(x,y)返回x和y串的连接串,subs(s,i,j)返回串s的从序号i的字符开始的j个字符组成的子串,len(s)返回串s的长度,则con(subs(s1,2,len(s2)),subs(s1,len(s2),2))的结果串是___CDEFGFG ____。

6、经过以下队列运算后,队头的元素是______。

InitQueue(qu);enQueue(qu,'a');enQueue(qu,'b');enQueue(qu,'c');deQueue(qu);

7、经过以下队列运算后,QueueEmpty(q)的值是______。

InitQueue(qu);enQueue(qu,a);enQueue(qu,b),deQueue(qu,x);deQueue(qu,y);

8、元素A、B、C、D顺序连续进入队列qu后,队头元素是______,队尾元素是______。 9、一个队列的入列序列为1234,则队列可能的输出序列是______。 10、环形队列qu的队满条件是______。 11、环形队列qu的队空条件是______。

12、设环形队列中数组的下标是0～N-1,其头、尾指针分别为f和r,则其元素个数为___(r-f+N)%N___。 13、判定一个环形队列qu(存放元素位置0～QueueSize-1)队满的条件是______。

14、假设用qu[0..M]实现环形队列,qu[f]、qu[r]分别为队首元素的前一个位置和队尾位置。若用\作为队满的标志,则______。

15、最适合用作链队的链表是__带队首指针和队尾指针的非循环单链表____。 16、用单链表表示的链队的队头在链表的______位置。 17、用单链表表示的链队的队尾在链表的______位置。 18、对于链队,在进行删除操作时,______。 19、栈和队列的共同点是______.

20、判定一个环形队列Q(存放元素位置为0～QueueSize-1)队满的条件是______. 21、栈的插入和删除操作在_________进行。

22、当利用大小为N的数组顺序存储一个栈时，假定用top==N表示栈空，则向这个栈插入一个元素时，首先应执行_________语句修改top指针。

23、假定利用数组a[N]顺序存储一个栈，用top表示栈顶指针,top==-1表示栈空,并已知栈未满,当元素x进栈时所执行的操作为_________.

24、利用数组a[N]顺序存储一个栈，用top表示栈顶指针，top==-1表示栈空，并已知栈未空，当退栈并返回栈顶元素时所执行的操作为____return a[top--]_____。

25、一个链栈的栈顶指针用top表示，当p所指向的结点进栈时，执行的操作为_________。 26、一个链栈的栈顶指针用top表示，当进行退栈时所进行的指针操作为_________。 27、若让元1，2，3依次进栈，则出栈次序不可能出现_________种情况。 28、在一个顺序队列中，队首指针指向队首元素的____前一个_____位置。

29、当利用大小为N的数组顺序存储一个队列时，若没有队列长度的变量，则该队列的最大长度为_________。

30、当利用大小为N的数组顺序存储一个队列时，若不设有队列长度的变量，则该队列的最大长度为____N-1_____。

31、从一个顺序队列删除元素时，首先需要____队首指针循环加１_____。

32、一个不设队列长度变量的顺序队列的队首和队尾指针分别为f和r,则判断队空的条件为_________。 33、假定一个链队的队首和队尾指针分别为front和rear，则判断队空的条件为___front==NULL______。 34、假定利用数组a[N]循环顺序存储一个队列，用f和r分别表示队首和队尾指针，并已知队未满，当元

- 28 -

素x进队时所执行的操作为_________。

37、在一个长度为N的数组空间中，顺序存储着一个队列，该队列的队首和队尾指针分别用front和rear表示，则该队列中的元素个数为_________。

数据结构复习题：串 判断题

1、栈和队列都是限制存取端的线性表。

2、队列是一种对进队列、出队列操作的次序作了限制的线性表。F 3、n个元素进队列的顺序和出队列的顺序总是一至的。T

4、顺序队中有多少元素,可以根据队首指针的值和队尾指针的值来计算。 5、队列的输入序列为124?n,输出序列为a1a2?an,则ai

数据结构复习题答案：串 判断题 1、True 2、False 3、True 4、True 5、True

数据结构复习题：串 填空题

1、串的两种最基本的方式是____顺序存储方式和链式存储方式_____。

2、两个串相等的充分必要条件是____两个串的长度相等且对应位置的字符相同____。 3、空串是____零个字符的串____,其长度等于_________。

4、空白串是____由一个或多个空格字符组成的串____,其长度等于____其包含的空格个数_____。 5、设s='I_AM_A_TEACHER',(其中,_表示一个空格字符),其长度是_______。 6、设s1='GOOD',s2=' ',s3='BYE!',则s1,s2和s3连接后的结果是________。 7、队列是一种具有______特性的线性表。 8、顺序队和链队的区别仅在于______的不同。

9、如果队列的最大长度以难以估计,则最好使用______。 10、在队列中,新插入的元素只能插入到______。 11、环形队列的优点是__解决了假溢出问题____。 12、设有数组A[0..m]作为环形队列的存储空间,front为队头指针,rear为队尾指针,则元素x执行入队的操作是______。

13、设有数组A[0..m]作为环形队列的存储空间,front为队头指针,rear为队尾指针,假设队列车不空,则元素出队并保存到x中的操作是______。

14、若用带头结点的单链表来表示链队,则队列空的标志是______。

15、若用不带头结点的单链表来表示链队,则创建一个空队列所要执行的操作是___将单链表的首结点指针赋空值___。

16、若用带头结点的单链表来表示链队,则创建一个空队列所要执行的操作是______。 17、己知链队的头、尾指针分别是f和r,则将值x入队的操作序列是

__p=(QNode*)malloc(sizeof(QNode));p->data=x;p->next=r->next;r->next=p;r=p___。

- 29 -

18、在顺序队列实现的时候,通常将数组看成是一个首尾相连的环,这样做的目的是为避免产生___假溢出___现象.

19、环形队列用数组A[0..m-1]存放其元素值,己知其头尾指针分别是front和rear,则当前队列中的元素个数是______.

20、队列的插入操作在____________进行，删除操作在____________进行。 21、栈又称为____________表，队列又称为____________表。

22、向一个顺序栈插入一个元素时，首先使____________后移一个位置，然后把待插入元素____________到这个位置上。

23、从一个顺序栈删除元素时，首先取出____________的值，然后再使栈顶指针____________。 24、在一个不设队列长度变量的顺序队列Ｑ中，判断队空的条件为____________，判断队满的条件为____________。

25、在一个链队中，若队首指针与队尾指针的值相同，则表示该队为____________或该队______只含有一个结点______。

26、向一个链栈插入一个新结点时，首先把栈顶指针的值赋给____________，然后把新结点的存储位置赋给____________。 27、从一个链栈中删除一个结点时，需要把栈顶结点_____指针域_______的值赋给______栈顶指针______。 28、当用长度为Ｎ的数组顺序存储一个栈时，假定用top==N表示栈空，则表示栈满的条件为____________。 29、向一个栈顶指针为ＨＳ的链栈中插入一个新结点*p时，应执行____________和____________操作。 30、中缀表达式3*(x+2)-5所对应的后缀表达式为____________。

33、设元素a,b,c,d依次进Ｓ栈，若要在输出端得到序列cbda，则应进行的操作序列为push(S,a),push(S,b),push(S,c),____________,____________,____________,pop(S),pop(S)。

数据结构复习题：串 问答题

1、设栈s和队列q的初始状态都为空,元素a,b,c,d,e和f依次通过栈s,一个元素出栈后即进入队列q,若6个元素出队的序列是bdcfea,则栈s的容量至少应该存多少个元素?

数据结构复习题答案：串 问答题

1、答：栈s的容量至少应该存3个元素。

6 树和二叉树

- 30 -

沈阳理工大学应用技术学院

信息与控制学院 计算机科学与技术教研室

2011-5-8

数据结构复习题：树和二叉树 单选题

1、假定在一棵二叉树中，双分支结点数为15个，单分支结点数为32个，则叶子结点 数为___16__。 2、假定一棵二叉树的结点数为18个，则它的最小高度__5___。 3、在一棵二叉树中第五层上的结点数最多为__16___。 4、在一棵具有五层的满二叉树中，结点总数为__31___。

5、已知8个数据元素为(34、76、45、18、26、54、92、65)，按照依次插入结点的方法生成一棵二叉排序树后，最后两层上的结点总数为___2__。

6、由分别带权为9、2、5、7的四个叶子结点构造一棵哈夫曼树，该树的带权路径长度为__44___。

7、在树中除根结点外，其余结点分成m(m≥0)个___互不相交__的集合T1,T2,T3...Tm,每个 集合又都是树，此时结点T称为Ti的父结点，Ti称为T的子结点(1≤i≤m)。

8、下面答案__二叉树中的每个结点的关键字大于其左子树（如果存在）所有结点的关键字值，且小于其右子树（如果存在）所有结点的关键字值__是查找二叉树（又称二叉排序树）。 9、如果结点A有三个兄弟，而且B是A的双亲，则B的出度是__4___。

- 31 -

10、一个深度为L的满K叉树有如下性质：第L层上的结点都是叶子结点，其余各层上每 个结点都有K棵非空子树。如果按层次顺序从１开始对全部结点编号，编号为n的有右兄弟的条件是__(n-1)%k!=0___。 11、在完全二叉树中，当i为奇数且不等于１时，结点i的左兄弟是结点__i+1___，否则没有左兄弟。 12、某二叉树T有n个结点，设按某种遍历顺序对T中的每个结点进行编号，编号值为1,2,?,n且有如下性质：T中任一结点V，其编号等于左子树上的最小编号减1，而V的右子树 的结点中，其最小编号等于V左子树上结点的最大编号加1。这时按__前序遍历序列___编号。 13、最小代价生成树_____。

14、将递归算法转换成对应的非递归算法时,通常需要使用_____栈_____。 15、设二维数组A[m][n],每个数组元素占用K个存储单元,第一个数组元素的存储地址是Loc(a[0][0]),求按行优先顺序存放的数组元素a[i][j](0<=i<=m-1,0<=j<=n-1)的存储地址为___ Loc(a[0][0])+[i*n+j]*k ___。 16、设二维数组A[m][n],每个数组元素占用k个存储单元,第一个数组元素的存储地址是Loc(a[0][0]),求按列优先顺序存放的数组元素a[i][j](0<=i<=m-1,0<=j<=n-1)的存储地址为______。 17、设二维数组A[6][10],每个数组元素占用4个存储单元,若按行优先顺序存放的数组元素,a[0][0]的存储地址为860,则a[3][5]的存储地址是___1000___。 18、设二维数组A[6][10],每个数组元素占用4个存储单元,若按行优先顺序存放的数组元素a[3][5]的存储地址为1000,则a[0][0]的存储地址是______。

19、若将n阶上三角矩阵A按列优先顺序压缩存放在一维数组B[1..n(n+1)/2]中,第一个非零元素a1,1存于B[0]中,则应存放到B[k]中的非零元素ai,j(1<=i<=n,1<=j<=i)的下标i、j与k的对应关系是_j(j-1)/2+i-1_。 20、若将n阶下三角矩阵A按列优先顺序压缩存放在一维数组B[1..n(n+1)/2]中,第一个非零元素a1,1存于B[0]中,则应存放到B[k]中的非零元素ai,j(1<=i<=n,1<=j<=i)的下标i、j与k的对应关系是___(j-1)(2n-j+1)/2+i-j___。

21、对稀疏矩阵进行压缩存储的目的是___节省存储空间___。 22、稀疏矩阵压缩后,必会失去___随机存取___功能。

23、一个n*n的对称矩阵A,采用压缩方式存放到一维数组B中,则B的容量为___(n^2)/2___. 24、由权值分别为3,8,6,2,5的叶子结点生成一棵哈夫曼树，它的带权路径长度为____53_____。

25、在一棵深度为h的具有n个元素的二叉搜索树中，一个元素的最大搜索长度（即 经比较的结点数） 为_____h____。

26、根据集合{25,30,16,48}，按照依次插入结点的方法生成一棵二叉搜索树，在等概率情况下成功查找一个元素的平均查找长度为____2.5_____。

27、利用n个值作为叶结点的权生成的霍夫曼树中共包含有____2*n-1_____个结点。 28、利用n个值作为叶结点的权生成的霍夫曼树中共包含有_____n-1____个双支结点。

29、利用3,6,8,12这4个值作为叶子结点的权，生成一棵霍夫曼树，该树中所有叶子的最长带权路径长度为____18_____。

30、在平衡二叉树中，每个结点的平衡因子的绝对值被限制为_____1____。

数据结构复习题：树和二叉树 判断题

1、由树转换成二叉树，其根结点的右子树总是空的。

2、后序遍历树和中序遍历与该树对应的二叉树，其结果不同。F

3、有一个结点是某二叉树子树的中序遍历序列中的最后一个结点，则它必是该子 树的前序遍历序列中的

- 32 -

最后一个结点。

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

5、已知二叉树的前序遍历和后序遍历序列并不能唯一地确定这棵树，因为不知道树 的根结点是哪一个。 6、在哈夫曼编码中，当两个字符出现的频率相同时，其编码也相同，对于这种情况应作特殊处理。F 7、中序遍历二叉排序树的结点就可以得到排好序的结点序列。

8、在二叉排序树上插入新的结点时，不必移动其它结点，仅需改动某个结点的指针， 由空变为非空即可。 9、堆中所有非终端结点的值均小于或等于（大于或等于）左右子树的值。 10、用一维数组元素矩阵,可以简化对矩阵的存取操作。F

11、对角矩阵的特点是非零元素只出现在矩阵的两条对角线上。 12、在n(n>3)阶三对角线矩阵中,每一行都有3个非零元素。 13、在n(n>3)阶三对角矩阵中,每一行都有3个非零元素。

数据结构复习题答案：树和二叉树 判断题 1、True 2、False 3、False 4、True 5、False 6、False 7、True 8、True 9、True 10、False 11、False 12、False 13、False

数据结构复习题：树和二叉树

1、己知二叉树采用二叉链存储结构存储,设计一个算法使用栈对二叉树进行先序遍历. void PreOrder1(BTNode *b) { BTNode *p; struct { BTNode *pt; int tag; //1:未访问，0:可访问 } St[MaxSize]; int top=-1; top++; St[top].pt=b; St[top].tag=1; while (top>-1) //栈不空时循环 { if (St[top].tag==1) //不能直接访问的情况

- 33 -

{ p=St[top].pt; top--; if (p!=NULL) {

//(2)式

top++; //右孩子结点进栈 St[top].pt=p->rchild; St[top].tag=1;

top++; //左孩子结点进栈 St[top].pt=p->lchild; St[top].tag=1; top++; //根结点进栈 St[top].pt=p; St[top].tag=0; } } //end of if (St[top].tag==1)

if (St[top].tag==0) //直接访问的情况 { printf(\ top--; } } //while }

数据结构复习题答案：树和二叉树 第二种方法

数据结构复习题：树和二叉树 填空题

1、对于一棵具有n个结点的树，则该树中所有结点的度之和为___n-1___。

2、在一棵二叉树中，度为0的结点的个数为n0 ，度为2的结点的个数为n2 ，则：n0=___n2+1___。 3、在二叉树的顺序存储中，对于下标为5的结点，它的双亲结点的下标为____2____， 若它存在左孩子，则左孩子结点的下标为____10____，若它存在右孩子，则右孩子结点的下标为____11_____。 4、在一棵二叉排序树中，按____中序___遍历得到的结点序列是一个有序序列。

5、由分别带权为3,9,6,2,5的共五个叶子结点构成一棵哈夫曼树，则带权路径长度为____55____。 6、有如下递归函数: int dunno (int m) {

int value; if (m==0) value=3; else

value=dunno(m-1)+5; return (value); }

- 34 -

执行语句printf(\；的结果是____18____。

7、所谓稀疏矩阵指的是___非零元素很少且分布没有规律___的矩阵。 8、一个稀疏矩阵Am*n采用三元组表示后,若把三元组中有关行下标与列下标的值互换,并把m和n的值互换,则就完成了Am*n的转置运算。这句话___不是___正确的。 9、若稀疏矩阵采用三元组压缩方法存储,只要把每个元素的行下标和列下标互换,就成了对该矩阵的转置运算,这种观点___错误___(正确或错误).

10、在一棵非空的二叉搜索树中，以每个分支结点为根的子树都是一棵______二叉搜索树______。 11、对一棵二叉搜索树进行中序遍历时，得到的结点序列是一个______有序序列______。

12、从一棵二叉搜索树中查找一个元素时，若元素的值等于根结点的值，则表明_____查找成功_______，若元素的值小于根结点的值，则继续向______左子树______查找，若元素的值大于根结点的值，则继续向______右子树______查找。

13、在一个堆的顺序存储中，若一个元素的下标为i，则它的左孩子元素的下标为______2i+1______，右孩子元素的下标为______2i+2______。

14、在一个小根堆中，堆顶结点的值是所有结点中的______最小值______，在一个大根堆中，堆顶结点的值是所有结点中的______最大值______。

15、当向一个小根堆插入一个具有最小值的元素时，该元素需要逐层______向上______调整，直到被调整到______栈顶______位置为止。

16、不管一棵哈夫曼树中有偶数或奇数个叶子结点，则树中总结点的个数必为______奇数____个。 17、在中序线索二叉搜索树中，具有最小值结点的左指针域的值为______空_____。

数据结构复习题：树和二叉树 问答题

1、对于二叉排序树，当所有结点的权都相等的情况下，最佳二叉排序树有何特点。 其特点是只有最下面的二层结点可以小于２，其它结点的度数必须为２。

2、分别写出对二叉树进行中根遍历和先根遍历的非递归算法(不允许使用转向语句)。 解答：中根遍历的非递归算法： status inorder(bt){ top＝0; p＝bt; do{

(1) while (p!=nil ){

top＝top＋1; s[top]＝p;

p:＝p->left; //p指向左子树 }

(2) if (top>0 ){

p＝s[top]; top＝top－1; printf(p->data);

p＝p->right; // p指向右子树 }

}while !((top＝0) && (p＝nil)); }

解答: 先根遍历的非递归算法：

- 35 -

本文来源：https://www.bwwdw.com/article/qoog.html