数据结构复习三

www.tiyu532.com|www.ganxi021.com|www.0532ty.com|www.meishu999.com|www.wudao321.com

一、单项选择题

1、计算机算法必须具备输入、输出和（C ）。 A、计算方法 B、排序方法

C、解决问题的有限运算步骤 D、程序设计法

2、若对数据结构采用了顺序存储，第一个结点地址为1001，每个节点的值需占用2个存储单元，则第三个节点的起始地址为（B）。 A、1003 B、1005 C、1006 D、1007 3、（b ）是数据的基本单位。 A、数据结构 B、数据元素 C、数据项 D、数据类型

4、一般而言，最适合描述算法的语言为（c ）。 A、自然语言 B、计算机程序语言 C、伪语言 D、数学公式

5、一种抽象数据类型包括数据和( b )两个部分。 A、数据类型 B、操作 C、数据抽象 D、类型说明

6、当一个作为实际传递的对象占用的存储空间较大并可能被修改时，应最好说明为(b )，以节省参数值的传输时间和存储参数的空间。 A、基本类型 B、引用型 C、指针型 D、常值引用型

7、线性表的顺序存储结构是一种（a ）的存储结构。 A、随机存储 B、顺序存储 C、索引存取 D、散列存取

8、在顺序表上做增、删结点运算的平均时间复杂度是（b ）。 A、O(1) B、O(n ) C、O(n2 ) D、O(log2n )

9、在顺序表中，只要知道（d ），就可以在相同的时间内求出任一结点的存储地址。 A、开始结点 B、终端结点

C、向量大小 D、基地址和结点大小

10、在非空线性表中，有且只有一个直接前驱和一个直接后继的结点是（c ）。 A、开始结点 B、终端结点 C、内部结点 D、所有结点

11、顺序表中逻辑上相邻的结点的物理位置为（a ）。 A、一定相邻 B、不必相邻 C、按某种规律排列 D、不要求

12、在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是（b ）。 A、O(1) B、O(n ) C、O(n2 ) D、O(log2n )

13、在（b ）运算中，使用顺序表比链表好。 A、插入 B、根据序号查找 C、删除 D、根据元素值查找

14、利用双向链表作线性表的存储结构的优点是（B ）。

www.tiyu532.com|www.ganxi021.com|www.0532ty.com|www.meishu999.com|www.wudao321.com

A、便于单向进行插入和删除的操作 B、便于双向进行插入和删除的操作 C、节省空间 D、便于销毁结构释放空间

15、在一个顺序存储的循环队列中，队头指针指向队头元素的(a )位置。 A、前一个 B、后一个 C、当前 D、后面

16、线性表中第一个结点没有直接前趋，称为（ a ）结点。 A、开始 B、末端 C、当前 D、尾端

17、假定一个链式队列的队头和队尾指针分别为front和rear，则判断队空的条件为(A )。 A、front == rear B、front != NULL C、rear != NULL D、front == NULL 18、链表不具有的特点是（ A ）。

A、可以随机访问任何一个元素 B、插入和删除元素不需要移动元素 C、不必事先估计存储空间 D、所需的存储空间和链表长度无关 19、堆栈和队列的相同之处是（d ）。

A、元素的进出满足先进后出 B、元素的进出满足先进先出 C、只允许在端点进行插入和删除操作 D、无共同点 20、栈与一般线性表的区别在于（b ）。

A、数据元素的类型不同 B、运算是否受限制 C、数据元素的个数 D、逻辑结构不同

21、一个栈的入栈序列是abcde，则栈不可能的输出序列是（c ）。 A、edcba B、decba C、dceab D、abcde

22、4个元素的进入队列Q的顺序是A,B,C,D,进行DeQueue(Q)操作后，队头元素是（b ）。 A、A B、B C、C D、D

23、一个队列的入队序列是1，2，3，4，则队列的输出序列是（ a）。 A、1，2，3，4 B、4，3，2，1 C、1，4，3，2 D、3，2，4，1 24、栈的插入和删除操作在( a )进行。 A、栈顶 B、栈底

C、任意位置 D、指定位置

25、若让元素1,2,3依次进栈，则出栈次序不可能出现(c )种情况. A、3,2,1 B、2,1,3 C、3,1,2 D、1,3,2

26、一个顺序栈一旦被声明，其占用空间大小（a ）。 A、已固定 B、可以变化 C、不能固定 D、动态变化 27队列的插入操作是在（b）进行的。 A、队首 B、队尾 C、队前 D、队后

28、队列的删除操作是在（a ）进行的。 A、队首 B、队尾 C、队前 D、队后

www.tiyu532.com|www.ganxi021.com|www.0532ty.com|www.meishu999.com|www.wudao321.com

29、空串与空格字符组成的串的区别在于（ b ）。 A、没有区别 B、两串的长度不相等

C、两串的长度相等 D、两串包含的字符不相同 30、一个字串在包含它的主串中的位置是指（d ）。

A、子串的最后那个字符在主串中的位置 B、子串的最后那个字符在主串中首次出现的位置

C、子串的第一个字符在主串中的位置 D、子串的第一个字符在主串中首次出现的位置 31、字符串采用结点大小为1的链表作为其存储结构，是指（d ）。 A、链表的长度为1 B、链表中只存放一个字符

C、链表的每个结点的数据域中不仅只存放一个字符 D、链表的每个链结点的数据域中只存放了一个字符

32、在长度为n的字符串中S的第i个位置插入另外一个字符串，i的合法值应该是（c ）。 A、i>0 B、i<=n

C、1≤i<≤n D、1≤i<≤n＋1

33、设s1=”I am a teacher”,其长度等于（b ）。 A、0 B、14 C、13 D、15

34、有两个串P和Q，求P和Q中首次出现的位置的运算称（c ）。 A、连接 B、模式匹配 C、求子串 D、求串长

35、串是一种特殊的线性表，其特殊性体现在（b ）。 A、可以顺序存储 B、数据元素是一个字符 C、可以链接存储 D、数据元素可以是多个字符 36、广义表是线性表的推广，它们之间的区别在于（a ）。 A、能否使用子表 B、能否使用原子项 C、表的长度 D、是否能为空

37、广义表c=(A,B,()),则表c的长度为（c ）。 A、1 B、2 C、3 D、4

38、数组与一般线性表的区别主要在（c ）。 A、存储方面 B、不能进行插入运算 C、逻辑结构方面 D、不能进行删除运算 39、广义表A=(a),则表尾为（c ）。 A、a B、(( )) C、空表 D、（a）

40、设广义表的L=(a,b,L),其深度是（ b ） A、3 B、无穷 C、2 D、都不对

41、树型结构最合适用来描述（ c）。 A、有序的数据元素 B、无序的数据元素

C、数据元素之间具有层次关系的数据 D、数据元素之间没有关系的数据

42、若在一棵非空树中，某结点A有3个兄弟结点（包括A自身），B是A的双亲结点，则B的度为（b ）。 A、2 B、3

www.tiyu532.com|www.ganxi021.com|www.0532ty.com|www.meishu999.com|www.wudao321.com

C、4 D、5

43、按照树的定义，具有3个结点的树有（a ）种形态。 A、2 B、3 C、4 D、5

44、按照二叉树的定义，具有3个结点的二叉树有（d）种形态。 A、2 B、3 C、4 D、5

45、下面说法中，（d ）是正确的。

A、度为2的树是二叉树 B、度为2的有序树是二叉树

C、子树有严格左、右之分的树是二叉树 D、子树有左、右之分、且度不超过2的树是二叉树

46、下面的说法中，（ c ）是正确的。

A、二叉树的度为2 B、二叉树中任意一个结点的度都为2

C、任何二叉树中结点度可以小于2 D、任何二叉树中至少有一个结点的度为2 47、若一棵二叉树有10个度为2的结点，则该二叉树的叶结点的个数（b ）。 A、9 B、11 C、12 D、不确定

48、利用3,6,8,12这四个值作为叶子结点的权，生成一棵霍夫曼树，该树的带权路径长度为( a )。 A、55 B、29 C、58 D、38

49、若一棵满二叉树有2047个结点，则该二叉树中叶结点的个数为（b ）。 A、512 B、1024 C、2048 D、4096

50、具有n个结点的二叉树采用二叉链表作为存储结构，链表中有（c ）个存放nil的指针域。 A、n-1 B、n C、n+1 D、2n

51、在非空二叉树的中序遍历序列中，二叉树的根结点的左边（a ）。 A、只有左子树上的所有结点 B、只有左子树上的部分结点 C、只有右子树上的所有结点 D、只有右子树上的部分结点

52、若非空二叉树的前序序列与后序序列的次序正好相反，则该二叉树一定是（d ）的二叉树。 A、空或仅有一个结点 B、其分支结点无左子树 C、其分支结点无右子树 D、其分支结点的度都为1 53、下面关于哈夫曼树的说法，不正确的是（d ）。

A、对应一组权值构造出的哈夫曼树一般不是唯一的 B、哈夫曼树具有最小带权路径长度 C、哈夫曼树没有度为1的结点 D、哈夫曼树中除了具有度为1的结点外，还有度为2的结点和叶结点

54、一组权值为（7，5，2，4）对应的哈夫曼树的带权路径长度为（b ）。 A、25 B、35 C、45 D、55

55、深度为5的二叉树至多有（ b ）个结点。 A、16 B、31 C、15 D、30

56、若由森林转化得到的二叉树是非空的二叉树，则二叉树的形状是（c ）。

www.tiyu532.com|www.ganxi021.com|www.0532ty.com|www.meishu999.com|www.wudao321.com

A、根结点无右子树的二叉树 B、根结点无左子树的二叉树

C、根结点可能有左二叉树和右二叉树 D、各结点只有一个孩子的二叉树 57、在一棵树中，( c )没有前驱结点。 A、树枝结点 B、叶子结点 C、树根结点 D、空结点

58、在一棵树中，( d )没有后继结点。 A、树枝结点 B、叶子结点 C、树根结点 D、空结点

59、在一棵具有n个结点的二叉树中，所有结点的空子树个数等于(c )。 A、n B、n-1 C、n+1 D、2*n

60、在一棵树的左孩子-右兄弟表示法中，一个结点的右孩子是该结点的( a )结点。A、兄弟 B、父子 C、祖先 D、子孙

61、在一棵树的静态双亲表示中，每个存储结点包含( b )个域。 A、1 B、2 C、3 D、4

62、在一个图中，所有顶点的度数之和等于所有边的数目的（c ）倍。 A、1/2 B、1 C、2 D、4

63、在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（ b）倍。 A、1/2 B、1 C、2 D、4

64、一个具有n个顶点的无向图最多有（a ）条边。 A、n×（n－1）/2 B、n×（n－1） C、n×（n+1）/2 D、n×n

65、一个具有n个顶点的有向图最多有（b ）条边。 A、n×（n－1）/2 B、n×（n－1） C、n×（n+1）/2 D、n×n

66、具有6个顶点的无向图至少应该有（b ）条边才能是一个连通图。 A、4 B、5 C、6 D、7

67、一个无向图采用邻接矩阵存储方法，其邻接矩阵一定是一个（a ）。 A、对称矩阵 B、对角矩阵 C、三角矩阵 D、稀疏矩阵

68、图的深度优先搜索算法类似于二叉树的（a ）。 A、前序遍历 B、中序遍历 C、后序遍历 D、按层次遍历

69、具有n个顶点、e条边的无向图采用邻接矩阵存储方法。则邻接矩阵的大小为（d A、n B、(n-1) ×（n+1） C、(n+1) ×（n+1） D、n×n

70、图的广度优先搜索算法类似于二叉树的（d ）。 A、前序遍历 B、中序遍历 C、后序遍历 D、按层次遍历

。 ）

www.tiyu532.com|www.ganxi021.com|www.0532ty.com|www.meishu999.com|www.wudao321.com

71、有向图的一个顶点的度数等于该顶点的 (c )。 A、入度 B、出度

C、入度与出度之和 D、（入度+出度）／２

72、一个连通图的生成树是包含图中所有顶点的一个 ( c )。 A、极小子图 B、连通子图 C、极小连通子图 D、无环子图 73、n个顶点的连通图中至少含有 ( a )。 A、n-1条边 B、n条边

C、n(n-1)/2条边 D、n(n-1)条边 74、n个顶点的强连通图中至少含有 (b )。 A、n-1条有向边 B、n条有向边

C、n(n-1)/2条有向边 D、n(n-1)条有向边 75、一个有n个顶点和n条边的无向图一定是 (d )。 A、连通的 B、不连通的 C、无环的 D、有环的

76、任何一个连通图的生成树（c ）。 A、可能不存在 B、只有一棵 C、一棵或多棵 D、一定有多棵

77、具有8个顶点的无向图最多有（b ）条边。 A、8 B、28 C、56 D、72

78、具有8个顶点的有向图最多有（c ）条边。 A、8 B、28 C、56 D、72

79、散列查找是由键值（b ）确定散列表中的位置，并进行存储或查找。 A、本身 B、散列函数值 C、相反数 D、平方

80、采用二分查找长度为n的线性表时，每个元素的平均查找长度为（ d）。 A、O(n2 B、O(nlog2n ) C、O(n ) D、O(log2n )

81、采用顺序查找长度为n的线性表时，每个元素的平均查找长度为（c ）。 A、n B、n /2 C、（n+1）/2 D、（n-1）/2

82、通常把查找过程中对关键字需要执行的（C ）作为衡量一个查找算法效率优劣的标准。 A、BST B、WPL C、ASL D、BFS

83、在表长是N的顺序表中，实施顺序查找，在查找不成功时，与关键字比较的次数（c ）。 A、N B、1 C、N+1 D、N-1

84、如果要求一个线性表既能较快的查找，又能适应动态变化的要求，则采用（ c）查找方法。 A、顺序 B、折半 C、分块 D、基本属性 85、线性表必须是（ b ），才能进行二分查找。 A、用向量存储的线性表 B、用向量存储的有序表 C、用链表存储的线性表 D、用链表存储的有序表

86、设有100个元素，用折半查找法进行查找时，最小比较次数是（a ）。 A、1 B、2 C、3 D、6

87、在查找过程中，如同时还要做增、删工作，这种查找称为（c ）。 A、静态查找 B、内查找 C、动态查找 D、外查找 88、下列（c ）不是利用查找表中数据元素的关系进行查找的方法。

A、平衡二叉树 B、有序表的查找 C、散列查找 D、二叉排序树的查找

www.tiyu532.com|www.ganxi021.com|www.0532ty.com|www.meishu999.com|www.wudao321.com

89、在所有的排序方法中，关键字的比较次数与记录的初始排列次序无关的是（d ）。 A、希尔排序 B、冒泡排序 C、插入排序 D、选择排序

90、目前已比较为基础的内部排序中，其比较次数与待排序的纪录的初始排列状态无关的是（ d ）。

A、快速排序 B、冒泡排序 C、插入排序 D、二分插入排序 91、内部排序与外部排序的区别不在于（c ）。

A、待排序文件的大小 B、有无内外存的交换C、是否在内存中排序 D、可采用的排序策略 92、设有1000个无序的元素，希望以最快的速度挑选出其中前10个最大的元素，最好选用的排序法是（ a ）。

A、堆排序 B、起泡排序 C、快速排序 D、基数排序 93、在排序方法中，（ c）是不稳定的排序方法。

A、直接插入排序 B、冒泡排序 C、直接选择排序 D、归并排序 94、评价排序算法好坏的标准主要是（d ）。

A、执行时间 B、辅助时间 C、算法本身复杂度 D、执行时间和所辅助时间 95、堆排序是一种（ b）的排序。

A、插入 B、选择 C、交换 D、归并 96、快速排序在（c ）的情况下最易发挥其长处。

A、被排序的数据中含有多个相同的排序码 B、被排序的数据已基本有序 C、被排序的数据完全无序 D、被排序的数据中的最大值和最小值相差悬殊 97、下述几种排序方法中，要求内存量最大是（b ）。

A、插入排序 B、归并排序 C、快速排序 D、选择排序 98、下述几种排序方法中，平均查找长度最小的是（c ）。 A、希尔排序 B、冒泡排序 C、插入排序 D、选择排序

99、每次从无序表中取出一个元素，把它插入到有序表中的适当位置，此种排序方法叫做（a 排序。

A、插入 B、交换 C、选择 D、归并

100、直接插入排序的方法要求被排序的数据（ a ）存储。

A、必须是顺序 B、必须是链表 C、顺序或链表 D、二叉树

）

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