数据结构图,查找,内排序的练习及答案

习题一绪论.1.1 单项选择题1. 数据结构是一门研究非数值计算的程序设计问题中计算机的① A 以及它们之间的② B 和运算等的学科。

①A.操作对象Ｂ．计算方法Ｃ．逻辑存储Ｄ．数据映象②A．结构Ｂ．关系Ｃ．运算Ｄ．算法2. 数据结构被形式地定义为（K，R），其中K是① B 的有限集合，R是K上的②D 有限集合。

①A．算法Ｂ．数据元素Ｃ．数据操作Ｄ．逻辑结构②A．操作Ｂ．映象Ｃ．存储Ｄ．关系3. 在数据结构中，从逻辑上可以把数据结构分成 C 。

A．动态结构和静态结构Ｂ．紧凑结构和非紧凑结构Ｃ．线性结构和非线性结构Ｄ．内部结构和外部结构4. 线性表的顺序存储结构是一种① A 的存储结构，线性表的链式存储结构是一种② B 的存储结构。

A．随机存取B．顺序存取C．索引存取D．散列存取5. 算法分析的目的是① C ，算法分析的两个主要方面是② A B 。

① A. 找出数据结构的合理性 B. 研究算法中的输入和输出的关系C. 分析算法的效率以求改进D. 分析算法的易懂性和文档性② A. 空间复杂性和时间复杂性 B. 正确性和简明性C. 可读性和文档性D. 数据复杂性和程序复杂性6. 计算机算法指的是① C ，它必具备输入、输出和② B 等五个特性。

①A. 计算方法 B. 排序方法C. 解决问题的有限运算序列D. 调度方法②A. 可行性、可移植性和可扩充性 B. 可行性、确定性和有穷性C. 确定性、有穷性和稳定性D. 易读性、稳定性和安全性7. 线性表的逻辑顺序与存储顺序总是一致的，这种说法 B 。

A. 正确B. 不正确8. 线性表若采用链式存储结构时，要求内存中可用存储单元的地址 D 。

A. 必须是连续的B. 部分地址必须是连续的C. 一定是不连续的D. 连续或不连续都可以9. 在以下的叙述中，正确的是 B 。

A.线性表的线性存储结构优于链表存储结构B.二维数组是其数据元素为线性表的线性表C.栈的操作方式是先进先出D.队列的操作方式和先进后出10. 每种数据结构都具备三个基本运算：插入、删除和查找，这种说法 B 。

第三章排序一、选择题1．某内排序方法的稳定性是指( D )。

A．该排序算法不允许有相同的关键字记录、B．该排序算法允许有相同的关键字记录C．平均时间为0（n log n）的排序方法 D．以上都不对2．下面给出的四种排序法中( )排序法是不稳定性排序法。

A. 插入B. 冒泡C. 二路归并D. 快速排序3．下列排序算法中，其中（ CD ）是稳定的。

A. 堆排序，冒泡排序B. 快速排序，堆排序C. 直接选择排序，归并排序D. 归并排序，冒泡排序6．若要求尽可能快地对序列进行稳定的排序，则应选（ B ）。

A．快速排序 B．归并排序 C．冒泡排序12．排序趟数与序列的原始状态有关的排序方法是( D )排序法。

A．插入 B. 选择 C. 冒泡 D. 快速17．数据序列（8，9，10，4，5，6，20，1，2）只能是下列排序算法中的( C )的两趟排序后的结果。

A．选择排序 B.冒泡排序 C.插入排序18．数据序列（2，1，4，9，8，10，6，20）只能是下列排序算法中的( A )的两趟排序后的结果。

A. 快速排序B. 冒泡排序C. 选择排序D. 插入排序19．对一组数据（84，47，25，15，21）排序，数据的排列次序在排序的过程中的变化为（1） 84 47 25 15 21 （2） 15 47 25 84 21 （3） 15 21 25 8447 （4） 15 21 25 47 84，则采用的排序是 ( A )。

A. 选择B. 冒泡C. 快速D. 插入24．下列序列中，（ D ）是执行第一趟快速排序后所得的序列。

A. [68，11，18，69] [23，93，73]B. [68，11，69，23] [18，93，73]C. [93，73] [68，11，69，23，18]D. [68，11，69，23，18] [93，73]28．下列排序算法中，在待排序数据已有序时，花费时间反而最多的是( C )排序。

数据结构练习题（一）一、单选题1.栈和队列的共同特点是( )。

A.只允许在端点处插入和删除元素B.都是先进后出C.都是先进先出D.没有共同点2.用链接方式存储的队列，在进行插入运算时( )。

A. 仅修改头指针B. 头、尾指针都要修改C. 仅修改尾指针D.头、尾指针可能都要修改3.以下数据结构中( )是非线性结构。

A. 队列B. 栈C. 线性表D. 二叉树4.设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每个元素占一个空间，问A[3][3](10)存放在（）位置。

脚注(10)表示用10进制表示。

A．688 B．678 C．692 D．6965.树最适合用来表示( )。

A.有序数据元素B.无序数据元素C.元素之间具有分支层次关系的数据D.元素之间无联系的数据6.二叉树的第k层的结点数最多为( )。

A．2k-1 B.2K+1 C.2K-1 D. 2k-17.若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二分查找，则查找A［3］的比较序列的下标依次为( )。

A. 1，2，3B. 9，5，2，3C. 9，5，3D. 9，4，2，38.对于线性表（7，34，55，25，64，46，20，10）进行散列存储时，若选用H（K）=K %9作为散列函数，则散列地址为1的元素有（）个。

A．1 B．2 C．3 D．49.设有6个结点的无向图，该图至少应有( )条边才能确保是一个连通图。

A.5B.6C.7D.8二、填空题1.通常从四个方面评价算法的质量：_________、_________、_________和_________。

2.一个算法的时间复杂度为(n3+n2log2n+14n)/n2，其数量级表示为________。

3.假定一棵树的广义表表示为A（C，D（E，F，G），H（I，J）），则树中所含的结点数为__________个，树的深度为___________，树的度为_________。

1．顺序存储结构中数据元素之间的逻辑关系是由（存储位置）表示的。

2．若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（顺序表）存储方式最节省时间。

3. 执行下面程序段时，语句S的执行次数为(n+1)(n+2)/24 对于线性表最常用的操作是查找指定序号的元素和在末尾插入元素，则选择（顺序表）存储方式最节省时间。

5．在长度为n的顺序表的第i个位置上插入一个元素（1≤ i ≤n+1），元素的移动次数为：n – i + 16．非空的单循环链表由头指针head指示，p 指针指向链尾结点的条件是（p->next==head）。

7．下列选项中，（可以随机访问表中的任意元素）是链表不具有的特点。

8.假设有如下遗产继承规则：丈夫和妻子可以相互继承遗产；子女可以继承父亲或母亲的遗产；子女间不能相互继承。

则表示该遗产继承关系的最合适的数据结构应该是（图）。

9．栈和队列的共同点是（只允许在端点处插入和删除元素）10．一个队列的入队序列是a,b,c,d，则该队列的出队序列是（a,b,c,d）。

11.带头结点的单链表h为空的判断条件是（h->next== NULL）。

12. 下面关于串的叙述中，哪一个是不正确的？（空串是由空格构成的串）13．判断一个最大容量为m的循环队列Q为空的条件是（Q->front==Q->rear）。

14．在一棵树中，每个节点最多有（1）前驱节点？15．已知完全二叉树的第7层有10个叶子结点，则整个二叉树中结点数为（73）。

16. 下面的说法中，不正确的是（稀疏矩阵中大量值为零的元素分布有规律，因此可以采用三元组表方法存储）17．在一棵深度为k的满二叉树中，结点总数为（2k-1）18．数组A中，每个元素的长度为3个字节，行下标从1到5，列下标从1到6，从首地址SA开始连续存放在存储器内，存放该数组至少需要的字节数是（90）。

19. 如果从无向图的任一顶点出发进行一次深度优先搜索即可访问所有的顶点，则该图一定是（连通图）。

数据结构试题及答案⼀、选择题（共10题，每题1分，共10分）1．下⾯关于线性表的叙述中，错误的是哪⼀个？（）A．线性表采⽤顺序存储，必须占⽤⼀⽚连续的存储单元B．线性表采⽤顺序存储，便于进⾏插⼊和删除操作C．线性表采⽤链接存储，不必占⽤⼀⽚连续的存储单元D．线性表采⽤链接存储，便于插⼊和删除操作2．在⼀个单链表中，已知q所指结点是p所指结点的前驱，若在p和q之间插⼊s所指结点，则执⾏的操作是（）。

A. s->next=p->next;p->next=s;B. q->next=s;s->next=p;C. p->next=s->next;s->next=p;D. p->next=s;s->next=q;3．设有三个元素X，Y，Z顺序进栈，下列得不到的出栈排列是( )。

A．XYZ B. YZX C. ZXY D. ZYX4．若⽤⼀个长度为6的数组来实现循环队列，且当前rear和front的值分别为0和3，则从队列中删除⼀个元素，再增加两个元素后，rear和front的值分别是( )。

A．1和5 B．2和4 C．4和2 D. 5和15．下列说法中正确的是（）。

A．⼆叉树就是度为2的树 B．⼆叉树中不存在度⼤于2的结点C．⼆叉树中⾄少有⼀个结点的度为2 D．⼆叉树中任何⼀个结点的度都为2 6．在具有n个结点的⼆叉链表中，共有（）个空指针。

A. nB. n-1C. n+1D. 不确定7．根据⼆叉树与树的转换关系可知，深度为h的满⼆叉树对应的森林由（）棵树构成。

A．1 B．log2n C. h/2 D. h8．在⼀个⽆向图中，所有顶点的度数之和等于所有边数的（）倍。

A．1/2 B．1 C. 2 D. 49．对17个元素的查找表做折半查找，则查找长度为5的元素下标依次是（）。

A．8,17 Ｂ．5,10,12 C．9,16 D．9,1710．关于排序，下列说法中正确的是（）。

一、单项选择题1.逻辑关系是指数据元素间的（）A．类型B．存储方式C．结构D．数据项2.对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构为( )A．顺序表 B.用头指针表示的单循环链表C. 用尾指针表示的单循环链表D. 单链表3.设数组data[m]作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行出队操作后其头指针front值为（）A．front=front+1B．front=(f ront+1)%(m-1)C．front=(front-1)%m D．front=(front +1)%m4.在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队头指针和队尾指针，则判断队满的条件为( )。

A．rear％n==front B．(front+l)％n==rearC．rear％n-1==front D．(rear+l)％n==front5.在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队头指针和队尾指针，则判断队空的条件为( )。

A．rear％n==front B．front+l=rearC．rear==front D．(rear+l)％n=front6.已知一颗二叉树上有92个叶子结点，则它有____个度为2的结点。

( )A. 90B. 91C. 92D. 937.在一棵非空二叉树的中序遍历序列中，根结点的右边_____。

A. 只有右子树上的所有结点B. 只有右子树上的部分结点C. 只有左子树上的所有结点D. 只有左子树上的部分结点8.有n条边的无向图的邻接表存储法中，链表中结点的个数是( )个。

A. nB. 2nC. n/2D. n*n9.判断有向图是否存在回路，除了可利用拓扑排序方法外，还可以利用（）。

A. 求关键路径的方法B.求最短路径的方法C. 深度优先遍历算法D.广度优先遍历算法10.对线性表进行二分查找时，要求线性表必须( )。

2．应用题（1）试找出满足下列条件的二叉树① 先序序列与后序序列相同 ②中序序列与后序序列相同 ③ 先序序列与中序序列相同 ④中序序列与层次遍历序列相同 先序遍历二叉树的顺序是“根—左子树—右子树”，中序遍历“左子树—根—右子树”，后序遍历顺序是：“左子树—右子树―根＂，根据以上原则，本题解答如下： （１） 若先序序列与后序序列相同，则或为空树，或为只有根结点的二叉树（２） 若中序序列与后序序列相同，则或为空树，或为任一结点至多只有左子树的二叉树． （３） 若先序序列与中序序列相同，则或为空树，或为任一结点至多只有右子树的二叉树．（４） 若中序序列与层次遍历序列相同，则或为空树，或为任一结点至多只有右子树的二叉树（2）设一棵二叉树的先序序列： A B D F C E G H ，中序序列： B F D A G E H C①画出这棵二叉树。

②画出这棵二叉树的后序线索树。

③将这棵二叉树转换成对应的树（或森林）。

(1) (2)（4）已知下列字符A 、B 、C 、D 、E 、F 、G 的权值分别为3、12、7、4、2、8，11，试填写出其对应哈夫曼树HT 的存储结构的初态和终态。

初态:ABFD (CE HG终态（1）已知如图6.27所示的有向图，请给出： ① 每个顶点的入度和出度； ② 邻接矩阵； ③ 邻接表；④ 逆邻接表。

（2）已知如图6.28所示的无向网，请给出： ① 邻接矩阵； ② 邻接表； ③ 最小生成树图 6.28 无图 6.27 有⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎣⎡∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞6456252363794567555553955434→→→ → →→ → → →→ → → →→ → → →^ → →→^→ → →^ → → →^（3）已知图的邻接矩阵如6.29所示。

试分别画出自顶点1出发进行遍历所得的深度优先生成树和广度优先生成树。

数据结构习题答案一评论:0 条查看:40 次zjw313014322发表于2009-04-21 16:25一、选择题1. 下面说法错误的是 C 。

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

（2）在相同的规模n下，复杂度O（n）的撒在时间上总是优于复杂度O(2n)的算法。

（3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界。

（4）同一个算法，实现语言的级别越高，执行效率越低。

A、（1）B、（1）（2）C、（1）（4）D、（3）2. 一个递归算法必须包括 B 。

A、递归部分B、终止条件和递归部分C、迭代部分D、终止条件和迭代部分3. 数据的 C 包括查找、插入、删除、更新、排序等操作类型。

A、存储结构B、逻辑结构C、基本运算D、算法描述4. 在数据结构中，从逻辑上可以把数据结构分成 C 。

A、动态结构和静态结构B、紧凑结构和非紧凑结构C、线性结构和非线性结构D、内部结构和外部结构5. 与数据元素本身的形式、内容、相对位置、个数无关的是数据的 C 。

A、存储结构B、存储实现C、逻辑结构D、运算实现6. 通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着 B 。

A、数据具有同一特点B、不仅数据元素所包含的数据项的个数要相同，而且对应数据项的类型要一致C、每个数据元素都一样D、数据元素所包含的数据项的个数要相等7. 以下说法正确的是 D 。

A、数据元素是数据的最小单位B、数据项是数据的基本单位C、数据结构是带有结构的各数据项的集合D、一些表面上很不相同的数据可以有相同的逻辑结构8. 以下说法错误的是 A 。

A、程序设计的实质是数据处理B、数据的逻辑结构是数据的组织形式，基本运算规定了数据的基本操作方式C、运算实现是完成运算功能的算法或这些算法的设计D、数据处理方式总是与数据的某种相应表示形式相联系，反之亦然9. 下列程序段的时间复杂度为 B 。

x=n;y=0;while (x>=(y+1)*(y+1))y=y+1;A、O(n)B、O(n1/2)C、O(1)D、O(n2)10. 下列叙述中有关好的编程风格的正确描述是 C 。

单项选择题：单项选择题共20道题，每题2分第1题：在一个具有n个结点的有序顺序表中插入一个新结点并仍然有序，时间复杂度是（）。

A、O（1）B、O（n）C、O（logn）D、O（nlogn）第2题：n个顶点e条边的图，若采用邻接矩阵存储，则矩阵空间大小为（）。

A、O（1）B、O（n）C、O（n+e）D、O（n^2）第3题：树的后根遍历序列等同于该树对应的二叉树的( )。

A. 先序序列B. 中序序列C. 后序序列D.层次序列第4题：若链队列Q用一带头结点的单链表表示，则元素e(其结点由指针p指向)的入队操作为（）。

A.Q.rear->next=p;Q.rear=p;B.Q.rear=p;Q.rear->next=p;C.Q.front->next=p;Q.front=p;D.Q.front=p;Q.front->next=p;第5题：计算机算法指的是（）。

A、计算方法B、排序方法C、解决问题的有限运算序列D、调度方法第6题：n个顶点e条边的图采用邻接矩阵存储，深度优先遍历算法的时间复杂度为（）。

A、O（1）B、O（n）C、O（n+e）D、O（n^2）第7题：最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是（）。

A. (Q.rear+1)%n=Q.frontB. Q.rear=Q.front C．Q.rear+1=Q.front D. (Q.rear-l)%n=Q.front第8题：算法分析的两个主要方面是（）。

A、空间复杂性和时间复杂性B、正确性和简明性C、可读性和文档性D、数据复杂性和程序复杂性第9题：一棵左子树为空的二叉树在先序线索化后，其中空的链域的个数是：( )A．不确定 B. 0 C. 1 D. 2第10题：线性表Ｌ在（）情况下适用于使用顺序结构实现。

A、经常对Ｌ进行删除B、经常对Ｌ进行插入C、经常访问Ｌ中的结点值D、 ABC第14题：一个无回路的AOV网有n个顶点e条边，拓扑排序的时间复杂度为（）。

一、判断题：1、线性表的逻辑顺序与物理顺序总是一致的。

( )2、线性表的顺序存储表示优于链式存储表示。

( )3、线性表若采用链式存储表示时所有结点之间的存储单元地址可连续可不连续。

( )4、二维数组是其数组元素为线性表的线性表。

( )5、每种数据结构都应具备三种基本运算：插入、删除和搜索。

( )6、数据结构概念包括数据之间的逻辑结构，数据在计算机中的存储方式和数据的运算三个方面。

( )7、线性表中的每个结点最多只有一个前驱和一个后继。

（）8、线性的数据结构可以顺序存储，也可以链接存储。

非线性的数据结构只能链接存储。

（）9、栈和队列逻辑上都是线性表。

（）10、单链表从任何一个结点出发，都能访问到所有结点（）11、删除二叉排序树中一个结点，再重新插入上去，一定能得到原来的二叉排序树。

（）12、快速排序是排序算法中最快的一种。

（）13、多维数组是向量的推广。

（）14、一般树和二叉树的结点数目都可以为0。

（）15、直接选择排序是一种不稳定的排序方法。

（）16、98、对一个堆按层次遍历，不一定能得到一个有序序列。

（）17、在只有度为0和度为k的结点的k叉树中，设度为0的结点有n0个，度为k的结点有nk个，则有n0=nk+1。

（）18、折半搜索只适用与有序表，包括有序的顺序表和有序的链表。

（）19、堆栈在数据中的存储原则是先进先出。

（）20、队列在数据中的存储原则是后进先出。

（）21、用相邻矩阵表示图所用的存储空间大小与图的边数成正比。

（）22、哈夫曼树一定是满二叉树。

（）23、程序是用计算机语言表述的算法。

（）24、线性表的顺序存储结构是通过数据元素的存储地址直接反映数据元素的逻辑关系。

（）25、用一组地址连续的存储单元存放的元素一定构成线性表。

（）26、堆栈、队列和数组的逻辑结构都是线性表结构。

（）27、给定一组权值，可以唯一构造出一棵哈夫曼树。

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

《数据结构（C语言版第2版）》（严蔚敏著）第七章练习题答案第7章查找1．选择题（1）对n个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为（）。

A．(n-1)/2B．n/2C．(n+1)/2D．n答案：C解释：总查找次数N=1+2+3+…+n=n(n+1)/2，则平均查找长度为N/n=(n+1)/2。

（2）适用于折半查找的表的存储方式及元素排列要求为（）。

A．链接方式存储，元素无序B．链接方式存储，元素有序C．顺序方式存储，元素无序D．顺序方式存储，元素有序答案：D解释：折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。

（3）如果要求一个线性表既能较快的查找，又能适应动态变化的要求，最好采用()查找法。

A．顺序查找B．折半查找C．分块查找D．哈希查找答案：C解释：分块查找的优点是：在表中插入和删除数据元素时，只要找到该元素对应的块，就可以在该块内进行插入和删除运算。

由于块内是无序的，故插入和删除比较容易，无需进行大量移动。

如果线性表既要快速查找又经常动态变化，则可采用分块查找。

（4）折半查找有序表（4，6，10，12，20，30，50，70，88，100）。

若查找表中元素58，则它将依次与表中（）比较大小，查找结果是失败。

A．20，70，30，50B．30，88，70，50C．20，50D．30，88，50答案：A解释：表中共10个元素，第一次取⎣(1+10)/2⎦=5，与第五个元素20比较，58大于20，再取⎣(6+10)/2⎦=8，与第八个元素70比较，依次类推再与30、50比较，最终查找失败。

（5）对22个记录的有序表作折半查找，当查找失败时，至少需要比较（）次关键字。

A．3B．4C．5D．6答案：B解释：22个记录的有序表，其折半查找的判定树深度为⎣log222⎦+1=5，且该判定树不是满二叉树，即查找失败时至多比较5次，至少比较4次。

（6）折半搜索与二叉排序树的时间性能（）。

数据结构练习试题和答案解析第1章绪论判断题数据的逻辑结构与数据元素本⾝的内容和形式⽆关。

（V ）⼀个数据结构是由⼀个逻辑结构和这个逻辑结构上的⼀个基本运算集构成的整体。

（V ）数据元素是数据的最⼩单位。

（X ）数据的逻辑结构和数据的存储结构是相同的。

（X ）程序和算法原则上没有区别，所以在讨论数据结构时可以通⽤。

（X ）从逻辑关系上讲，数据结构主要分为线性结构和⾮线性结构两类。

（V ）数据的存储结构是数据的逻辑结构的存储映象。

（V ）数据的物理结构是指数据在计算机内实际的存储形式。

（V ）数据的逻辑结构是依赖于计算机的。

（X ）算法是对解题⽅法和步骤的描述。

（V ）填空题数据有逻辑结构和存储结构两种结构。

数据逻辑结构除了集合以外，还包括线性结构、树形结构和图形结⽊。

数据结构按逻辑结构可分为两⼤类，它们是线性结构和⾮线性 ____ 。

树形结构和图形结构合称为⾮线性结构。

在树形结构中，除了树根结点以外，其余每个结点只有 1个前驱结点。

在图形结构中，每个结点的前驱结点数和后继结点数可以任意多 _ 。

数据的存储结构⼜叫物理结构。

数据的存储结构形式包括顺序存储、链式存储、索引存储和散列存 ___ 。

线性结构中的元素之间存在⼀只的关系。

树形结构中的元素之间存在⼀只的关系。

图形结构的元素之间存在多对多的关系。

数据结构主要研究数据的逻辑结构、存储结构和算法（或运算） 3个⽅⾯的内容。

数据结构被定义为（D, R ）,其中D 是数据的有限集合， R 是D 上的关系有限集合。

算法是⼀个有穷指令的集合。

算法效率的度量可以分为事先估算法和事后 ______ 。

⼀个算法的时间复杂度是算法输⼊规模的函数。

算法的空间复杂度是指该算法所耗费的存储空间，它是该算法求解问题规模的 n 的函数。

若⼀个算法中的语句频度之和为 T （n ）=6n+3nlog 2n,则算法的时间复杂度为 0 （ nlog 2n ）若⼀个算法的语句频度之和为T （n ）=3n+nlog 2+n 2,则算法的时间复杂度为 0（n 2）。

计算机学科专业基础综合数据结构-查找(一)(总分：100.00，做题时间：90分钟)一、{{B}}单项选择题{{/B}}(总题数：38，分数：38.00)1.对长度为n的有序单链表，若查找每个元素的概率相等，则顺序查找表中任一元素查找成功的平均查找长度为______。

∙ A.n/2∙ B.(n+1)/2∙ C.(n-1)/2∙ D.n/4（分数：1.00）A.B. √C.D.解析：[解析] 对单链表和顺序表进行顺序查找，都需要逐个扫描表中元素，因此其平均查找长度相同，都是(n+1)/2。

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

∙ A.以顺序方式存储∙ B.以链接方式存储∙ C.以顺序方式存储，且结点按关键字有序排序∙ D.以链接方式存储，且结点按关键字有序排序（分数：1.00）A.B.C. √D.解析：[解析] 折半查找要求表的存储结构有随机存储特性，且表中元素要有序，因此本题选C。

3.采用折半查找方式查找一个长度为n的有序顺序表时，其平均查找长度为______。

∙ A.O(n)∙ B.O(log2n)∙ C.O(n2)∙ D.O(nlog2n)（分数：1.00）A.B. √C.D.解析：[解析] 对长度为n的有序顺序表进行折半查找，其平均查找长度与有n个结点的完全二叉树同数量级，即O(log2n)，因此本题选B。

4.在对长度为n的顺序存储的有序表进行折半查找时，对应的二叉判定树的高度为______。

A．n B．C． D（分数：1.00）A.B.C.D. √解析：[解析] 折半查找的平均查找长度可用二叉判定树分析，其高度与完全二叉树相同，根据完全二叉树的性质，有[*]。

5.采用折半查找法查找长度为n的有序顺序表，查找每个元素的数据比较次数______对应二叉判定树的高度(设高度≥2)。

∙ A.小于∙ B.大于∙ C.等于∙ D.小于等于（分数：1.00）A.B.C.D. √解析：[解析] 对有序顺序表中的元素进行查找所需要的总比较次数与对应元素在表中的位置有关，最多不会超出该表对应二叉判定树的高度，因此本题选D。

第一章绪论一、选择题1.数据结构是一门研究非数值计算的程序设计问题中计算机的1以及它们之间的2和运算等的学科。

1 A.数据元素 B.计算方法 C.逻辑存储 D.数据映像2 A.结构 B.关系 C.运算 D.算法2.数据结构被形式地定义为(K, R)，其中K是1的有限集，R是K上的2有限集。

1 A.算法 B.数据元素 C.数据操作 D.逻辑结构2 A.操作 B.映像 C.存储 D.关系3.在数据结构中，从逻辑上可以把数据结构分成。

A.动态结构和静态结构B.紧凑结构和非紧凑结构C.线性结构和非线性结构D.内部结构和外部结构4.线性结构的顺序存储结构是一种1的存储结构，线性表的链式存储结构是一种2的存储结构。

A.随机存取 B.顺序存取 C.索引存取 D.散列存取5.算法分析的目的是1，算法分析的两个主要方面其一是指2，其二是指正确性和简单性。

1 A.找出数据结构的合理性 B.研究算法中的输入和输出的关系C.分析算法的效率以求改进D.分析算法的易懂性和文档性2 A.空间复杂度和时间复杂度 B.研究算法中的输入和输出的关系C.可读性和文档性D.数据复杂性和程序复杂性k6.计算机算法指的是1，它必须具备输入、输出和2等5个特性。

1 A.计算方法 B.排序方法 C.解决问题的有限运算序列 D.调度方法2 A.可执行性、可移植性和可扩充性 B.可行性、确定性和有穷性C.确定性、有穷性和稳定性D.易读性、稳定性和安全性7.线性表的逻辑顺序与存储顺序总是一致的，这种说法。

A.正确 B.不正确8线性表若采用链式存储结构时，要求内存中可用存储单元的地址。

A.必须连续的B.部分地址必须连续的C.一定是不续的D连续不连续都可以9.以下的叙述中，正确的是。

A.线性表的存储结构优于链式存储结构 B.二维数组是其数据元素为线性表的线性表C.栈的操作方式是先进先出D.队列的操作方式是先进后出10.每种数据结构都具备三个基本运算：插入、删除和查找，这种说法。

第1章绪论习题1．简述下列概念：数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型。

2．试举一个数据结构的例子，叙述其逻辑结构和存储结构两方面的含义和相互关系。

3．简述逻辑结构的四种基本关系并画出它们的关系图。

4．存储结构由哪两种基本的存储方法实现？5．选择题（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．栈6．试分析下面各程序段的时间复杂度。

（1）x=90; y=100;while(y>0)if(x>100){x=x-10;y--;}else x++;（2）for (i=0; i<n; i++)for (j=0; j<m; j++)a[i][j]=0;（3）s=0;for i=0; i<n; i++)for(j=0; j<n; j++)s+=B[i][j];sum=s;（4）i=1;while(i<=n)i=i*3;（5）x=0;for(i=1; i<n; i++)for (j=1; j<=n-i; j++)x++;（6）x=n; //n>1y=0;while(x≥(y+1)* (y+1))y++;（1）O（1）（2）O（m*n）（3）O（n2）（4）O（log3n）（5）因为x++共执行了n-1+n-2+……＋1= n(n-1)/2，所以执行时间为O（n2）（6）O(n)第2章线性表1．选择题（1）一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（）。

数据结构部分课后习题答案第一章1.1数据的逻辑结构是从具体问题中抽象出来的数学模型，体现了事物的组成和事物之间的逻辑关系。

数据的存储结构主要用来解决各种逻辑结构在计算机中物理存储表示的问题。

1.2事前分析和事后统计事前分析：优点，程序不必运行，所得结果只依赖于算法本身缺点，不够精确事后统计：优点，精确缺点，必须运行程序，所得结果依赖于硬件、环境等因素考虑赋值、运算操作执行的次数第3行赋值2次第6行赋值执行n次，加法执行n次所以，总共2n+2次操作，算法复杂度为O(n)1.4y= y + i * j 执行次数：1.5第二章2.9内存中一片连续空间（不妨假设地址从1到m）提供给两个栈S1和S2使用，怎样分配这部分存储空间，使得对任一个栈，仅当这部分空间全满时才发生上溢。

答：S1和S2共享内存中一片连续空间（地址1到m），可以将S1和S2的栈底设在两端，两栈顶向共享空间的中心延伸，仅当两栈顶指针相邻（两栈顶指针值之差的绝对值等于1）时，判断为栈满，当一个栈顶指针为0，另一个栈顶指针m+1时为两栈均空。

2.10线性表是数据项组成的一种有限且有序的序列，各元素之间呈线性关系。

从逻辑结构来说，栈和队列与线性表相同，都是典型的线性结构。

与线性表不同的是，栈和队列的操作特殊，受到一定的限制，仅允许在线性表的一端或两端进行。

栈是限定仅在一端进行插入删除的线性表，无论插入、删除还是读取都在一端进行，按后进先出的原则。

队列的元素只能从一端插入，从另一端删除，按先进先出的原则进行数据的存取。

2.11共有132种合法序列。

235641序列可以。

154623序列不可以。

对于每一个数来说，必须进栈一次、出栈一次。

我们把进栈设为状态‘1’，出栈设为状态‘0’。

n个数的所有状态对应n个1和n个0组成的2n位二进制数。

由于等待入栈的操作数按照1‥n的顺序排列、入栈的操作数b大于等于出栈的操作数a(a≤b)，因此输出序列的总数目=由左而右扫描由n个1和n个0组成的2n位二进制数，1的累计数不小于0的累计数的方案种数。

数据结构试题及答案第一章一、选择题1、研究数据结构就是研究（ D ）。

A. 数据的逻辑结构B. 数据的存储结构C. 数据的逻辑结构和存储结构D. 数据的逻辑结构、存储结构及其基本操作2、算法分析的两个主要方面是（ A ）。

A. 空间复杂度和时间复杂度B. 正确性和简单性C. 可读性和文档性D. 数据复杂性和程序复杂性3、具有线性结构的数据结构是（ D ）。

A. 图B. 树C. 二叉树D. 栈4、计算机中的算法指的是解决某一个问题的有限运算序列，它必须具备输入、输出、（ B ）等5个特性。

A. 可执行性、可移植性和可扩充性B. 可执行性、有穷性和确定性C. 确定性、有穷性和稳定性D. 易读性、稳定性和确定性5、下面程序段的时间复杂度是（ C ）。

for(i=0;i<m;i++)for(j=0;j<n;j++)a[i][j]=i*j; A. O(m 2) B. O(n 2) C. O(m*n) D. O(m+n)6、算法是（ D ）。

A. 计算机程序B. 解决问题的计算方法C. 排序算法D. 解决问题的有限运算序列7、某算法的语句执行频度为（3n+nlog 2n+n 2+8）,其时间复杂度表示（ C ）。

A. O(n) B. O(nlog 2n) C. O(n 2) D. O(log 2n)8、下面程序段的时间复杂度为（ C ）。

i=1;while(i<=n)i=i*3;A. O(n)B. O(3n)C. O(log 3n)D. O(n 3)9、数据结构是一门研究非数值计算的程序设计问题中计算机的数据元素以及它们之间的（ B ）和运算等的学科。

A. 结构B. 关系C. 运算D. 算法10、抽象数据类型的三个组成部分分别为（ A ）。

A. 数据对象、数据关系和基本操作B. 数据元素、逻辑结构和存储结构C. 数据项、数据元素和数据类型D. 数据元素、数据结构和数据类型11、下列程序段的时间复杂度为（B ）。

第1章概论习题参考解答一、填空题1、数据的逻辑结构是数据元素之间的逻辑关系，通常有下列4类：（）、（）、（）、（）。

【答】集合、线性结构、树型结构和图状结构。

2、数据的存储结构是数据在计算机存储器里的表示，主要有4种基本存储方法：（）、（）、（）、（）。

【答】顺序存储方法、链接存储方法、索引存储方法和散列存储方法。

二、选择题1、一个算法必须在执行有穷步之后结束，这是算法的（）。

（A）正确性（B）有穷性（C）确定性（D）可行性【答】B。

2、算法的每一步，必须有确切的定义。

也就是说，对于每步需要执行的动作必须严格、清楚地给出规定。

这是算法的（）。

（A）正确性（B）有穷性（C）确定性（D）可行性【答】C。

3、算法原则上都是能够由机器或人完成的。

整个算法好像是一个解决问题的“工作序列”，其中的每一步都是我们力所能及的一个动作。

这是算法的（）。

（A）正确性（B）有穷性（C）确定性（D）可行性【答】D。

三、简答题1、算法与程序有何异同？【答】尽管算法的含义与程序非常相似，但两者还是有区别的。

首先，一个程序不一定满足有穷性，因此它不一定是算法。

例如，系统程序中的操作系统，只要整个系统不遭受破坏，它就永远不会停止，即使没有作业要处理，它仍处于等待循环中，以待一个新作业的进入。

因此操作系统就不是一个算法。

其次，程序中的指令必须是计算机可以执行的，而算法中的指令却无此限止。

如果一个算法采用机器可执行的语言来书写，那么它就是一个程序。

2、什么是数据结构？试举一个简单的例子说明。

【答】数据结构是指数据对象以及该数据对象集合中的数据元素之间的相互关系（即数据元素的组织形式）。

例如，队列的逻辑结构是线性表（先进先出）；队列在计算机中既可以采用顺序存储也可以采用链式存储；对队列可进行删除、插入数据元素以及判断是否为空队列、将队列置空等操作。

3、什么是数据的逻辑结构？什么是数据的存储结构？【答】数据元素之间的逻辑关系，也称为数据的逻辑结构。