数据结(00002

1、 数据结构复习题 一、选择题 1以下数据结构中，（ D ）是线性结构。 A图 B. 二叉树 C. 树 D. 串 2线性表是具有n个（ C）的有限序列。 A表元素 B字符 C数据元素 D数据项 E信息项 3线性表采用链接存储时，其地址（ D ）。 A. 必须是连续的 B. 部分地址必须是连续的 C. 一定是不连续的 D. 连续与否均可以 4一个队列的入队顺序是1，2，3，4，则队列的输出顺序是（ B ）。 A. 4321 B. 1234 C. 1432 D. 3241 5假设以数组Am存放循环队列的元素,其头尾指针分别为front和rear，则当前队列中的 。）A 元素个数为（ A(rear-f

2、ront+m)%m Brear-front+1 C(front-rear+m)%m D(rear-front)%m 6在一个无向图中，所有顶点的度数之和等于 所有边数的（D）倍。 A1/2 B1 C4 D 2 7串的长度是指（ B ） A串中所含不同字母的个数 B串中所含字符的个数 C串中所含不同字符的个数 D串中所含非空格字符的个数 8 设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为（ C ）。 A求子串 B联接 C匹配 D求串长 9数据结构是一门研究非数值计算的程序设计问题中，计算机的操作对象以及它们之间的（ B ）和操作等的学科。 逻辑存储 C关系 B结构A D算

3、法 10 设有一顺序栈S，元素s,s,s,s,s,s依614253次进栈，如果6个元素出栈的顺序是s,s,s, s, 6243 s,s,则栈的容量至少应该是（ B ）。 15A2 B.3 C.5 D.6 11（ D ）是C语言中“abcd321ABCD”的子串。 Aabcd B321AB C. “abcABC” D“21AB” 子串的定义是什么？串中任意个连续的字符组成的子序列成为该串的子串。 12二分查找要求被查找的表是（ C ） A键值有序的链接表 B链接表但键值不一定有序 C键值有序的顺序表 D顺序表但键值不一定有序 13数据结构的形式定义为(D,S)，其中D是 ）的有限集。 B （ A

4、.算法 B.数据元素 C.数据操作D. 逻辑结构14一个算法指的是（ B ）。 A程序 B问题求解步骤的描述 C要满足五个基本特性 DA和C 15具有10个叶结点的二叉树中有（ B）个度为2的结点。 A8 B9 C10 Dll 16以下数据结构中，（ D ）是线性结构。 A图 B. 二叉树 C. 树 D. 串 17数据结构的形式定义为(D,S)，其中D是（ B ）的有限集。 A.算法 D.数据操作C. 数据元素B. 逻辑结构 18一个算法指的是（）。 B 要 C程序A B问题求解步骤的描述C 和A D满足五个基本特性 A线性表采用顺序存储，必须占用一片连续的存储单元。 B线性表采用顺序存储，便

5、于进行插入和删除操作。 C线性表采用链接存储，不必占用一片连续的存储单元。 D线性表采用链接存储，便于插入和删除操作。 19在一个无向图中，所有顶点的度数之和等于所有边数的（D ）倍。 A1/2 B1 C4 D 2 20串是任意有限个（C）。 A符号构成的序列 B符号构成的集合 C. 字符构成的序列 D字符构成的集合 21二分查找要求被查找的表是（ C ） A键值有序的链接表 B链接表 但键值不一定有序 C键值有序的顺序表 D顺序表但键值不一定有序 22. 在单链表指针为p的结点之后插入指针为s 的结点，正确的操作是：（B ）。 Ap.next=s;s.next=p.next; B s.nex

6、t=p.next;p.next=s; Cp.next=s;p.next=s.next; D p.next=s.next;p.next=s; 23. 一个栈的输入序列为1，2，3，4，下面哪一个序列不可能是这个栈的输出序列( C ). A、 1，3，2，4 B、2，3，4，1 C、 4，3，1，2 D、3，4，2，1 24. 折半查找要求查找表中各元素的关键字值必须是（ A ）排列。 、 递增或递减 、递增 、递减 、无序 25. 在已知待排序文件已基本有序的前提下，效率最高的排序方法是（ A ） 直接选择 、 B直接插入排序 、A 排序 C、 快速排序 D、 归并排序 26数据结构是一门研究非

7、数值计算的程序设计问题中计算机的操作对象以及它们之间的 （ B ）和操作等的学科。 A结构 B关系 C逻辑存储 D算法 27下面（C ）不是算法所必须具备的特性。 A有穷性 B确切性 C高效性 D可行性 28已知一维数组A采用顺序存储结构，每个元素占用4个存储单元，第9个元素的地址为144，则第一个元素的地址是（A ）。 A108 B180 C176 D112 29一个栈的入栈序列是1，2，3，4，5，则栈的不可能的输出序列是（ C）。 A54321 B45321 C43512 12345 D 30 假设以数组Am存放循环队列的元素,其头尾指针分别为front和rear，则当前队列中的元素个数

8、为（ A ）。 A(rear-front+m)%m Brear-front+1 C(front-rear+m)%m D(rear-front)%m 31设有两个串p和q，求q在p中首次出现的位置的运算称作（B ）。 A连接 B模式匹配 C求子串 D求串长 32串的长度是指（ B ） A串中所含不同字母的个数 B串中所含字符的个数 C串中所含不同字符的个数 D串中所含非空格字符的个数 33一棵二叉树前序遍历结果为ABCDEF,中序遍历结果为CBAEDF,则后序遍历结果为（ A ）。 ACBEFDA B FEDCBA C CBEDFA D不定 结点总数为的满二叉树中，k在一棵高度为34 ）（ 2k

9、 2k-1 BAk+1 log? C2k-1 D?2 2C2D C A2-1 B2-1 k kk-1 k-1层只有当第k解析：一棵高为k的完全二叉树，根据二叉树最左边一个结点时具有最少的结点。个，2-1层共有结点的性质，第1层到第k-1k-1因此它至少有2-1+1=2个结点。 k-1k-135当采用分快查找时，数据的组织方式为 ( B ) A数据分成若干块，每块内数据有序 B数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大（或最小）的数据组成索引块 C. 数据分成若干块，每块内数据有序，每块内最大（或最小）的数据组成索引块 D. 数据分成若干块，每块（除最后一块外）中 数据个数需

10、相同 36下面关于线性表的叙述中，错误的是（ B ）。 A线性表采用顺序存储，必须占用一片连续的存储单元。 B线性表采用顺序存储，便于进行插入和删除操作。 C线性表采用链接存储，不必占用一片连续的存储单元。 D线性表采用链接存储，便于插入和删除操作。 二、判断题（正确的打“”，错误的打“”） 1数据的逻辑结构有线性结构和非线性结构两大类。( ) 2数据元素是数据的最小单位。( )数据项 3队列逻辑上是一个下端口和上端口能增加又能减少的线性表。（ ）头只减少， 尾只增加 4每种数据结构都具备三个基本操作：插入、删除和查找。( ) 线性表的逻辑顺序和存储顺序总是一致的。5 ( ) 6数据元素可由若

11、干个数据项组成。( ) 7线性表的特点是每个元素都有一个前驱和一 个后继。( ) 8若输入序列为1,2,3,4,5,6,则通过一个栈可以输出序列3,2,5,6,4,1。 ( ) 9空串与空格串是相同的。( ) 10基于某种逻辑结构之上的运算，其实现是唯一的。( ) 11评价一个算法时间性能的主要标准是算法的时间复杂度。( ) 12链表中的头结点仅起到标识的作用。( ) 13顺序存储的线性表可以随机存取。( ) 14顺序存储的线性表可以随机存取。( ) 15单链表表示法的基本思想是用指针表示结点间的逻辑关系。( ) 。表性线的限受作操种一是列队与栈16 （ ） 17. 数据项是数据的不可分割的最

12、小单位。 ( ) 18单链表表示法的基本思想是用指针表示结点间的逻辑关系。( ) 19栈与队列是一种操作受限的线性表。（ ） 20. 通常从正确性、易读性、健壮性、高效性等四个方面评价算法(包括程序)的质量。( ) 21数据元素是数据的最小单位。( )数据项 22健壮的算法不会因非法的输入数据而出现莫名其妙的状态。( ) 23线性表的逻辑顺序和存储顺序总是一致的。( ) 24栈和队列都是限制存取点的线性结构。（ ） 25在二叉树的先序遍历序列中，任意一个结点 ) ( 均处在其子女的前面。 26串是一种数据对象和操作都特殊的线性表。（ ） 27空串与空格串是相同的。( ) 28一个有向图的邻接表

13、和逆邻接表中的结点个数一定相等。( ) 29. 线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。( ) 30. 顺序存储的线性表可以随机存取。( ) 31. 在单链表中，要删除某一指定的结点，必须找到该结点的直接前驱结点。( ) 32. 链栈与顺序栈相比，有一个比较明显的优点即通常不会出现栈满的情况。（ ） 33. 设有一个空栈，现有输入序列为A、B、C、D、E，经过PUSH，PUSH，POP，PUSH，POP，PUSH，PUSH操作后，输出序列是 B、C。（ ）ADE 栈：先进后出 34. 循环队列的队满条件为sq.(rear+1) % ） （。maxsize =sq.fron

14、t 35. 由于二叉树中每个结点的度最大为2，所以二叉树是一种特殊的树。（ ) 36数据的逻辑结构有线性结构和非线性结构两 大类。( ) 37顺序存储的线性表可以随机存取。( ) 38由于二叉树中每个结点的度最大为2，所以二叉树是一种特殊的树。（ ） 39对链表进行插入和删除操作时，不必移动结点。 ( ) 40栈和队列的共同特点是只允许在端点处插入和删除。（ ） 41在单链表中，要删除某一指定的结点，必须找到该结点的直接前驱结点。( ) 42设有一个空栈，现有输入序列为A、B、C、D、E，经过PUSH，PUSH，POP，PUSH，POP，PUSH，PUSH操作后，输出序列是 B、C。（ ） 4

15、3有向图用邻接矩阵表示后，顶点i的入度等于邻接矩阵中第i列的元素个数。( ) 有一个比较明显的优点链栈与顺序栈相比，44 即通常不会出现栈满的情况。（ ） 45通常从正确性、易读性、健壮性、高效性等四个方面评价算法(包括程序)的质量。( ) 46数据元素是数据的最小单位。( )数据项 47单链表表示法的基本思想是用指针表示结点间的逻辑关系。( ) 48栈与队列是一种操作受限的线性表。（ ） 49队列逻辑上是一个下端口和上端口能增加又能减少的线性表。（ ） 50有向图用邻接矩阵表示后，顶点i的入度等于邻接矩阵中第i列的元素个数。( ) 51链栈与顺序栈相比，有一个比较明显的优点即通常不会出现栈满

16、的情况。（ ） 52. 逻辑结构与数据元素本身的内容和形式无关。( ) 53健壮的算法不会因非法的输入数据而出现莫 ) ( 名其妙的状态。 54对任何数据结构链式存储结构一定优于顺序存储结构。（ ） 55顺序存储方式只能用于存储线性结构。 （ ） 56循环链表不是线性表。（ ） 57线性表中每个元素都有一个直接前驱和一个直接后继。（） 58二叉树的前序遍历序列中，任意一个结点均处在其孩子结点的前面。（ ） 59线性表中存在没有前驱或后继的元素。( ) 60. 基于某种逻辑结构之上的运算，其实现是唯一的。( ) 61线性表的逻辑顺序和存储顺序总是一致的。( ) 62. 栈与队列是一种特殊操作的线

17、性表。( ) 63串是一种数据对象和操作都特殊的线性表。 ） （ 64. 由树转换成二叉树，其根结点的右子树总是空的。( ) 65一个有向图的邻接表和逆邻接表中的结点个 数一定相等。( ) 66冒泡排序算法关键字比较的次数与记录的初始排列次序无关。( )选择排序 67对线性表进行折半查找时，要求线性表必须以链式方式存储，且结点按关键字有序排列。( ) 68通常从正确性、易读性、健壮性、高效性等四个方面评价算法(包括程序)的质量。( ) 69对任何数据结构链式存储结构一定优于顺序存储结构。（ ） 70长度为1的串等价于一个字符型常量。( ) 71二叉树的前序遍历序列中，任意一个结点均处在其孩子结

18、点的前面。（ ） 三、填空题 链栈中，在作进栈运算时不必判别栈是否1 ；在作退栈运算时应先判别栈是否（满）（空）。)根结点)、( 左子树 )和(右子树2二叉树由 ( 三个基本单元组成。 是重要指标两结3. 数据构中评价算法的个 。 时间复杂度 空间复杂度 、所指结点有后继结点中，指针p4. 在单链表L 。的条件是：_p-next!=NULL 1in+1）在一个长度为n（的顺序表的第i5. n-i+1 个元素之前插入一个元素，需向后移动（1in）个元素时，需向个元素，删除第i 前移动 n-i 个元素。栈顶（每个元素占2个字节），设有一个空栈6. 5，、1、2、3、4，现有输入序列为指针为1000

19、Hpush，push，pop，push，经过push，pushpop， _ 145 ，栈顶指针为_ 5 。后，输出序列是根据数据元素之间关系的不同特性，通常有7（网、 （ 树状结构）线性结构）（集合结构）、 它们反映了四类基络结构）四类基本逻辑结构， 本的数据组织形式。_串是一种特殊的线性表，其特殊性体现在8. 。数据元素是一个字符 两个串的9. 两个串相等的充分必要条件是_ 对应位置的字符相同_ 。长度相等 、 _2i-1 （i1）层最多有i10. 一棵二叉树的第）个结点的满二叉树共个结点；一棵有n（n0个非终端结_ 2/n 有_2/n 个叶子结点和 点。）个 0 11一棵有n个结点的满二叉

20、树有（非终的结点、有（ (n-1)/2）个分支 度为1）个叶子，该满二叉端）结点和（ (n+1)/2 ）。树的深度为（ n+1log2邻接图的存储结构主要有两种，分别是 12. 邻接矩 和13. 算法具有的5个特性是: ( 确定性 )、(可行性 )、( 有穷性 )、输入和输出。 14. 顺序查找n个元素的顺序表，若查找成功，则比较关键字的次数最多为( n )次；当使用监视哨时，若查找失败，则比较关键字的次数为( n+1 )。 表示栈空，此时作退栈运算，则产生15. top=0 “( 下溢 )”；top=sqstack_maxsize-1表示栈满，此时作进栈运算，则产生“( 上溢 )”。 16.

21、 线性结构的基本特征是：若至少含有一个结 点，则除起始结点没有直接( 前驱 )外，其他结点有且仅有一个直接( 前驱 )；除终端结点没有直接( 后继 )外，其它结点有且仅有一个直接( 后继 )。 17在树形结构中，树根结点没有（前驱）结点，其余每个结点有且只有（ 1）个前驱结点；叶子结点没有（ 后继 ）结点，其余每个结点的后继结点可以有（ 任意多 ）个。 18. 根据数据元素之间关系的不同特性，通常有集合、( 线性 )、( 树状 )、( 网络 )四类基本逻辑结构，它们反映了四类基本的数据组织形式。 19. 组成串的数据元素只能是(单个字符 )，空串是（ 空格 ），其长度等于（空格个数）。 20.

22、 具有n个结点的二叉树的中,一共有2n个指针域,其中只有(n-1)个用来指向结点的左右孩 。NULL）个指针域为n+1子，其余的（ 21根据数据元素之间关系的不同特性，通常有（集合结构）、（ 线性结构）（ 树状结构 ）、（网络结构）四类基本逻辑结构，它们反映了四类基 本的数据组织形式。 22在树形结构中，树根结点没有（前驱）结点，其余每个结点有且只有（ 1）个前驱结点；叶子结点没有（ 后继 ）结点，其余每个结点的后继结点可以有（ 任意多 ）个。 23二叉排序树是一种特殊的、增加了限制条件的二叉树，其限制条件是任一结点的键值（ 大 ）于其左孩子（及其子孙）的键值且（ 小 ）于其右孩子（及其子孙）

23、的键值。 24链栈中，在作进栈运算时不必判别栈是否（空）；在作退栈运算时应先判别栈是否（满）。 25一棵有n个结点的满二叉树有（ 0 ）个度为1的结点、有（ (n-1)/2）个分支 （非终端）结点和（ (n+1)/2 ）个叶子，该满二叉树的深度为（ ）。 n+1 log226二叉树由 ( 根结点)、( 左子树 )和(右子 三个基本单元组成。)树 ，队列27栈中存取数据的原则是（先进后出 ） 先进先出 ）。中存取数据的原则是（ ，( 单个字符 )28组成串的数据元素只能是 空格个数）。空串是（空格），其长度等于（ 描述数据结构是讨论数据元素关系的集合，29：关系的是数据间1：1 线性结构 、描述

24、1 关系的是 树状结构 、描述m：关系的是nm 图结构 。我们将数据结构在计算机中的表示形式称30 则数据结构在计为数据的物理结构或存储结构， 算机中主要有两种不同的存储结构， 顺序表单链逻辑上相邻的元素的物理位置必定相邻， 中逻辑上相邻的元素的物理位置则不一定 表 相邻。队 31 具有先进先出操作特征的数据结构是 、具有先进后出的操作特征的数据结构是列 。 栈32栈中存取数据的原则是（ 先进后出 ），队列中存取数据的原则是（ 先进先出 ）。 ， )单个字符( 组成串的数据元素只能是33 空格个数）。空串是（空格），其长度等于（ 增加了限制条件二叉排序树是一种特殊的、34值点的键一，的二叉树其限制条件是任结 ）于其左孩子（及其子孙）的键值且 大 （ ）于其右孩子（及其子孙）的键值。（ 小根据二叉树的特征，我们可以知道，一颗35 k 深度为 的满二叉树的节点个数有 。k-1 2 我们在讨论图的存储结构时主要使用了36 邻接矩阵 和 邻接表 两种。我们主要讨论了两种查找在讨论查找表时，37后者在和 静态查找表 ，动态查找表表 不会更改表中的数查找特定