习题

一、选择题

1.在计算机中，算法是指________。

A.加工方法　　B.查询方法

C.排序方法　　D.解题方案的准确而完整的描述

2.在下列选项中，________不是一个算法一般应该具有的基本特征。

A.确定性　　B.可行性

C.无穷性　　D.输入/输出性

3.算法分析的目的是________。

A.找出数据结构的合理性　　B.找出算法中输入和输出之间的关系

C.分析算法的易懂性和可靠性　　D.分析算法的效率以求改进

4.下面叙述正确的是________。

A.算法的执行效率与数据的存储结构无关

B.算法的空间复杂度是指算法程序中指令（或语句）的条数

C.算法的有穷性是指算法必须能在执行有限个步骤之后终止

D.以上三种描述都不对

5.算法的有穷性是指________。

A.算法程序的运行时间是有限的　　B.算法程序所处理的数据量是有限的

C.算法程序的长度是有限的　　D.算法只能被有限的用户使用

6.算法的时间复杂度是指________。

A.算法的执行时间　　B.算法所处理的数据量

C.算法执行过程中所需要的基本运算次数　　D.算法程序中的语句或指令条数

7.算法的空间复杂度是指________。

A.算法程序中的语句或指令条数　　B.算法在执行过程中所需要的计算机存储空间

C.算法所处理的数据量　　D.算法在执行过程中所需要的临时工作单元数

8.算法的时间复杂度取决于________。

A.问题的规模　　B.待处理的数据的初态

C.问题的难度　　D.A和B

9.数据结构作为计算机的一门学科，主要研究数据的存储结构、对各种数据结构进行的运算，以及________。

A.数据的逻辑结构　　B.计算方法　　C.数据映像　　D.逻辑存储

10.数据在计算机存储中的表示是指________。

A.数据的存储结构　　B.数据结构

C.数据的逻辑结构　　D.数据元素之间的关系

11.数据的存储结构是指________。

A.存储在外存中的数据　　B.数据所占的存储空间量

C.数据在计算机中的顺序存储方式　　D.数据的逻辑结构在计算机中的表示

12.下列叙述中，错误的是________。

A.数据的存储结构与数据处理的效率密切相关

B.数据的存储结构与数据处理的效率无关

C.数据的存储结构在计算机中所占的空间不一定是连续的

D.一种数据的逻辑结构可以有多种存储结构

13.在数据结构中，与所使用的计算机无关的是数据的________。

A.存储结构　　B.物理结构　　C.逻辑结构　　D.物理和存储结构

14.根据数据结构中各数据元素之间前后件关系的复杂程度，一般将数据结构分成________。

A.动态结构和静态结构　　B.线性结构和非线性结构

C.紧凑结构和非紧凑结构　　D.内部结构和外部结构

15.下列叙述中正确的是________。

A.线性表是线性结构　　B.栈与队列是非线性结构

C.线性链表是非线性结构　　D.二叉树是线性结构

16.以下数据结构中不属于线性数据结构的是________。

A.队列　　B.线性表　　C.二叉树　　D.带链的栈

17.下列关于栈的叙述中正确的是________。

A.在栈中只能插入数据　　B.栈是先进后出的线性表

C.栈是先进先出的线性表　　D.在栈中只能删除数据

18.下列数据结构中，按后进先出原则组织数据的是________。

A.线性链表　　B.栈　　C.循环链表　　D.队列

19.下列叙述中正确的是________。

A.线性表的链式存储结构与顺序存储结构所需要的存储空间是相同的

B.线性表的链式存储结构所需要的存储空间一般要多于顺序存储结构

C.线性表的链式存储结构所需要的存储空间一般要少于顺序存储结构

D.上述三种说法都不对

20.以下不是栈的基本运算的是________。

A.读栈顶元素　　B.读栈底元素　　C.判断栈是否为空　　D.将栈置为空栈

21.栈通常采用的两种存储结构是________。

A.线性存储结构和链表存储结构　　B.散列方式和索引方式

C.链表存储结构和数组　　D.线性存储结构和非线性存储结构

22.如果进栈序列为A、B、C、D，则可能的出栈序列是________。

A.CADB　　B.CDAB　　C.BDCA　　D.CABD

23.栈底至栈顶依次存放元素A、B、C、D、E，在第六个元素F入栈前，栈中元素可以出栈，则出栈序列可能是________。

A.ABCEDF　　B.FDCBEA　　C.EDFCBA　　D.FCDABE

24.若进栈序列为a1，a2，a3，a4，进栈过程中可以出栈，则下列不可能的一个出栈序列是________。

A.a1，a4，a3，a2　　B.a2，a3，a4，a1

C.a3，a1，a4，a2　　D.a3，a4，a2，a1

25.由两个栈共享一个存储空间的好处是________。

A.减少存取时间，降低下溢发生的几率

B.节省存储空间，降低上溢发生的几率

C.减少存取时间，降低上溢发生的几率

D.节省存储空间，降低下溢发生的几率

26.下列叙述中正确的是________。

A.在栈中，栈中元素随栈底指针与栈顶指针的变化而动态变化

B.在栈中，栈顶指针不变，栈中元素随栈底指针的变化而动态变化

C.在栈中，栈底指针不变，栈中元素随栈顶指针的变化而动态变化

D.上述三种说法都不对

27.一些重要的程序语言（如C语言和Pascal语言）允许过程的递归调用。而实现递归调用中的存储分配通常用________。

A.链表　　B.堆　　C.数组　　D.栈

28.下列关于队列的叙述中正确的是________。

A.在队列中在队头插入数据　　B.在队列中在队尾删除数据

C.队列是先进后出的线性表　　D.队列是先进先出的线性表

29.一个队列的入队序列是A，1，B，2，C，3，D，4，E，5则队列的输出字母序列是________。

A.E，D，C，B，A　　B.A，B，C，D，E　　C.A，D，E，C，B　　D.C，B，D，A，E

30.下列叙述中正确的是________。

A.循环队列有队头和队尾两个指针，因此，循环队列是非线性结构

B.在循环队列中，只需要队头指针就能反映队列中元素的动态变化情况

C.在循环队列中，只需要队尾指针就能反映队列中元素的动态变化情况

D.循环队列中元素的个数是由队头指针和队尾指针共同决定

31.线性表L=（a1，a2，a3，…，ai，…，an），下列说法正确的是________。

A.每个元素都有一个直接前件和直接后件

B.线性表中至少要有—个元素

C.除第—个元素和最后一个元素外，其余每个元素都有一个且只有一个直接前件和后件

D.表中诸元素的排列顺序必须是由小到大或由大到小

32.栈和队列的共同特点是________。

A.都是后进后出　　B.都是后进先出

C.没有共同点　　D.只允许在端点处插入和删除元素

33.对线性表，在下列情况下应当采用链表表示的是________。

A.经常需要随机地存取元素　　B.经常需要进行插入和删除操作

C.表中元素需要占据一片连续的存储空间　　D.表中元素的个数不变

34.用链表表示线性表的优点是________。

A.便于随机存取　　B.花费的存储空间较顺序存储少

C.便于插入和删除操作　　D.数据元素的物理顺序与逻辑顺序相同

35.链表不具有的特点是________。

A.不必事先估计存储空间　　B.可随机访问任一元素

C.插入删除不需要移动元素　　D.所需空间与线性表长度成正比

36.线性表若采用链式存储结构时，要求内存中可用存储单元的地址________。

A.必须是连续的　　B.连续不连续都可以

C.一定是不连续的　　D.部分地址必须是连续的

37.线性表的顺序存储结构和线性表的链式存储结构分别是________。

A.顺序存取的存储结构、顺序存取的存储结构

B.随机存取的存储结构、顺序存取的存储结构

C.随机存取的存储结构、随机存取的存储结构

D.任意存取的存储结构、任意存取的存储结构

38.循环链表的主要优点是________。

A.从表中任一结点出发都能访问到整个链表

B.不再需要头指针

C.在进行插入、删除运算时，能更好地保证链表不断开

D.已知某个结点的位置后，能够容易地找到它的直接前件

39.在单链表中，增加头结点的目的是________。

A.方便运算的实现　　B.使单链表至少有一个结点

C.标识表结点中首结点的位置　　D.说明单链表是线性表的链式存储实现

40.NULL是指________。

A.0　　B.空格

C.未知的值或无任何值　　D.空字符串

41.与单链表相比，双向链表的优点之一是________。

A.插入、删除操作更加简单　　B.顺序访问相邻结点更加灵活

C.可以省略表头指针或表尾指针　　D.可以随机访问

42.树是结点的集合，它的根结点数目是________。

A.1或多于1　　B.有且只有1　　C.0或1　　D.至少2

43.下列有关树的概念错误的是________。

A.一棵树中只有一个无前驱的结点

B.一棵树的度为树中各个结点的度数之和

C.一棵树中，每个结点的度数之和等于结点总数减1

D.一棵树中每个结点的度数之和与边的条数相等

44.树最适合用来表示________。

A.有序数据元素　　B.无序数据元素

C.元素之间具有分支层次关系的数据　　D.元素之间无联系的数据

45.下面关于二叉树的描述正确的是________。

A.一棵二叉树中叶子结点的个数等于度为2的结点的个数加1

B.一棵二叉树中的结点个数大于0

C.二叉树中任何一个结点要么是叶，要么恰有两个子女

D.二叉树中，任何一个结点的左子树和右子树上的结点个数一定相等

46.具有3个结点的树有________种形态。

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

47.具有3个结点的二叉树有________种形态。

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

48.设树T的深度为4，其中度为1，2，3，4的结点个数分别为4，3，2，1，则T中的叶子结点为________。

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

49.一棵二叉树中共有70个叶子结点与80个度为1的结点，则该二叉树中的结点总数应该为________。

A.219　　B.221　　C.229　　D.231

50.在一棵二叉树上第7层的结点数最多是________。

A.16　　B.32　　C.64　　D.128

51.在深度为6的满二叉树中，叶子结点的个数为________。

A.32　　B.31　　C.16　　D.15

52.在深度为7的满二叉树中，度为2结点的个数为________。

A.64　　B.63　　C.32　　D.31

53.下面关于完全二叉树的叙述中，错误的是________。

A.除了最后一层外，每一层上的结点数均达到最大值

B.可能缺少若干个左右叶子结点

C.完全二叉树一般不是满二叉树

D.具有n个结点的完全二叉树的深度至少为log2n+1

54.在一棵非空二叉树的中序遍历中，根结点的右边________。

A.只有右子树上的所有结点　　B.只有右子树上的部分结点

C.只有左子树上的部分结点　　D.只有左子树上的所有结点

55.设t，k为一棵二叉树上的两个结点，在中序遍历中，t在k后的条件是________。

A.t在k右树上　　B.t是k的祖先

C.t在k左树上　　D.t是k的子孙

56.设有如右图所示二叉树：

对此二叉树的中序遍历结果为________。

A.ABCDEF　　B.DBEACF

C.ABDECF　　D.DEBFCA

57.设有如右图所示二叉树：

对此二叉树前序遍历的结果为________。

A.ZBTYCPKXAH　　B.ABTKYPCXZH

C.ZBTACYXPKH　　D.ATBZXCPKYH

58.已知二叉树后序遍历序列是DABEC，中序遍历序列是DEBAC，它的前序遍历序列是________。

A.ACBED　　B.DCABE

C.CEDBA　　D.DEABC

59.已知一棵二叉树前序遍历和中序遍历分别为ABDEGCFH和DBGEACHF，则该二叉树的后序遍历为________。

A.DGEBHFCA　　B.GEDHFBCA　　C.ACBFEDHG　　D.ABCDEFGH

60.若某二叉树的后序遍历访问顺序是GDBEHFCA，中序遍历访问顺序是DGBAECHF，则其前序遍历的结点访问顺序是________。

A.BDGCEFHA　　B.GDBECFHA　　C.ABDGECHF　　D.ABDGCEFH

61.任何一棵二叉树的叶子结点在先序、中序和后序遍历序列中的相对次序________。

A.发生改变　　B.不发生改变　　C.不能确定　　D.以上都不对

62.设有两个串p和q，求q在p中首次出现位置的运算称为________。

A.连接　　B.模式匹配　　C.求子串　　D.求串长

63.串的长度是________。

A.串中不同字符的个数　　B.串中所含字符的个数且字符个数大于零

C.串中不同字母的个数　　D.串中所含字符的个数

64.对长度为n的线性表进行顺序查找，在最坏情况下所需要的比较次数为________。

A.n+1　　B.n　　C.（n+1）/2　　D.n/2

65.对长度为n的线性表进行二分查找，在最坏情况下所需要的比较次数为________。

A.n+1　　B.log2n　　C.log2（n+1）/2　　D.n/2

66.下列叙述中正确的是________。

A.对长度为n的有序链表进行查找，最坏情况下需要的比较次数为n

B.对长度为n的有序链表进行二分查找，最坏情况下需要的比较次数为n/2

C.对长度为n的有序链表进行二分查找，最坏情况下需要的比较次数为log2n

D.对长度为n的有序链表进行二分查找，最坏情况下需要的比较次数为nlog2n

67.对长度为n的线性表排序，在最坏情况下，比较次数不是n（n-1）/2的排序方法是________。

A.快速排序　　B.冒泡排序　　C.直接插入排序　　D.堆排序

68.顺序查找适合于存储结构为________的线性表。

A.散列存储　　B.顺序存储或链式存储

C.压缩存储　　D.索引存储

69.下列数据结构中，能用二分法进行查找的是________。

A.顺序存储的有序线性表　　B.线性链表

C.二叉链表　　D.有序线性链表

70.对线性表进行折半查找时，要求线性表必须________。

A.以顺序方式存储

B.以链接方式存储

C.以顺序方式存储，且结点按关键字有序排列

D.以链接方式存储，且结点按关键字有序排列

71.堆排序属于________。

A.交换排序　　B.归并排序　　C.选择排序　　D.插入排序

72.最简单的交换排序方法是________。

A.快速排序　　B.选择排序　　C.堆排序　　D.冒泡排序

73.在待排序的元素序列基本有序的前提下，效率最高的排序方法是________。

A.冒泡排序　　B.选择排序　　C.快速排序　　D.归并排序

74.在下列几种排序方法中，要求内存量最大的是________。

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

75.已知数据表A中每个元素距其最终位置不远，为节省时间，应采用的算法是________。

A.堆排序　　B.直接插入排序　　C.快速排序　　D.直接选择排序

二、填空题

1.算法的基本特征是可行性、确定性、________和________。

2.算法的工作量大小和实现算法所需的存储单元多少分别称为算法的________和________。

3.数据结构包括数据的逻辑结构、数据的________以及对数据的操作运算。

4.数据的逻辑结构有线性结构和________两大类。

5.在复杂的线性表中，一个数据元素可以由若干个数据项组成，由若干个数据项组成的数据元素称为________，而由多个记录构成的线性表称为________。

6.数据结构分为逻辑结构与存储结构，线性链表属于________。

7.顺序存储方法是把逻辑上相邻的结点存储在物理位置________的存储单元中。

8.栈的基本运算有三种：入栈、退栈和________。

9.栈和队列通常采用的存储结构是________。

10.当循环队列非空且队尾指针等于队头指针时，说明循环队列已满，不能进行入队运算，这种情况称为________。

11.用链表表示线性表的突出优点是________。

12.当线性表采用顺序存储结构实现存储时，其主要特点是在存储结构中________。

13.访问单链表中的结点，必须沿着________依次进行。

14.长度为n的顺序存储线性表中，当在任何位置上插入一个元素概率都相等时，插入一个元素所需移动元素的平均个数为________。

15.假设用一个长度为50的数组（数组元素的下标从0～49）作为栈的存储空间，栈底指针bottom指向栈底元素，栈顶指针top指向栈顶元素，如果bottom=49，top=30（数组下标），则栈中具有________个元素。

16.一个栈的初始状态为空。首先将元素5，4，3，2，1依次入栈，然后退栈一次，再将元素A，B，C，D依次入栈，之后将所有元素全部退栈，则所有元素退栈（包括中间退栈的元素）的顺序为________。

17.一个队列的初始状态为空。现将元素A，B，C，D，E，F，5，4，3，2，1依次入队，然后再依次退队，则元素退队的顺序为________。

18.在一个容量为15的循环队列中，若头指针front=6，尾指针rear=9，则该循环队列中共有________个元素。

19.设某循环队列的容量为50，如果头指针front=45（指向队头元素的前一位置），尾指针rear=10（指向队尾元素），则该循环队列中共有________个元素。

20.在树形结构中，树根结点没有________。

21.在树形结构中，树叶结点没有________。

22.设一棵完全二叉树共有700个结点，则在该二叉树中有________个叶子结点，有________个度为2的结点，有________个度为1的结点。

23.设一棵完全二叉树共有599个结点，则在该二叉树中有________个叶子结点，有________个度为2的结点，有________个度为1的结点。

24.设有如右图所示的二叉树：

对此二叉树中序遍历的结果为________。

25.设一棵二叉树的中序遍历结果为CBDEAGFIHJ，后序遍历结果为CEDBGIJHFA，则前序遍历为________。

26.设一棵二叉树的前序遍历结果为YMFALI，中序遍历结果为FMAYIL，则后序遍历结果为________。

27.在长度为n的线性表中，寻找最大项至少需要比较________次。

28.在长度为n的线性表中进行顺序查找，最坏情况下需要的比较次数为________。

29.在长度为n的有序线性表中进行二分法查找，最坏情况下需要的比较次数为________。

30.设有一个顺序存储的有序线性表L={18，20，25，31，38，45，67，75，89，95}，若在线性表中采用二分法查找数67，则比较________次。

31.排序是计算机程序设计中的一种重要操作，常见的排序方法有插入排序、________和选择排序等。

32.在长度为n的线性表中，在最坏情况下，冒泡排序的时间复杂度为________。

33.在长度为n的线性表中，在最坏情况下，快速排序的时间复杂度为________。

34.在长度为n的线性表中，在最坏情况下，简单插入排序的时间复杂度为________。

35.在长度为n的线性表中，在最坏情况下，希尔排序的时间复杂度为________。

36.在长度为n的线性表中，在最坏情况下，简单选择排序需要比较的次数为________。

37.在长度为n的线性表中，在最坏情况下，堆排序需要比较的次数为________。

38.在长度为n的线性表中，在最好情况下，插入类排序的时间复杂度为________。

39.若串s="VisualBasic"，则其子串的数目是________。