数据结构复习资料参考答案

《数据结构复习资料参考答案》由会员分享，可在线阅读，更多相关《数据结构复习资料参考答案（7页珍藏版）》请在装配图网上搜索。

1、选择题部分1、组成数据的基本单位是（ C） （A）数据项（B）数据类型（C）数据元素（D）数据变量2、数据结构是研究数据的（C）以及它们之间的相互关系。 （A）理想结构，物理结构 （B）理想结构，抽象结构（C）物理结构，逻辑结构 （D）抽象结构，逻辑结构3、在数据结构中，从逻辑上可以把数据结构分成C ） （A）动态结构和静态结构 （B）紧凑结构和非紧凑结构（C）线性结构和非线性结构（D）内部结构和外部结构4、数据结构是一门研究非数值计算的程序设计问题中计算机的 （A）以及它们之间的（B）和运算等的学科。 （A）数据元素（B）计算方法（C）逻辑存储（D）数据映像 （A）结构 （B）关系 （C）运

2、算 （D）算法5、算法分析的两个主要方面是（D ） （A）正确性和简单性 （B）可读性和文档性（C）数据复杂性和程序复杂性 （D）时间复杂度和空间复杂度6、算法分析的目的是（C）。 （A） 找出数据结构的合理性 （B）研究算法中的输入和输出的关系（C）分析算法的效率以求改进（D）分析算法的易懂性和文档性7、计算机算法指的是（C）,它必须具备输入、输出和（B）等5个特性。 （A）计算方法（B）排序方法（C）解决问题的有限运算序列（D）调度方法 （A）可执行性、可移植性和可扩充性（B）可行性、确定性和有穷性（C）确定性、有穷性和稳定性 （D）易读性、稳定性和安全性判断题 1、数据的机内表示称为数据

3、的存储结构。（对） 填空题 1.数据逻辑结构包括（线性结构 ）、（树型结构 ） 和（图形结构）三种类型,树形结构和图形结构合称为（非线性结构 ）。 2.在线性结构中,第一个结点（没有）前驱结点,其余每个结点有且只有（ 1）个前驱结点；最后一个结点（没有 ）后续结点,其余每个结点有且只有（1 ）个后续结点。 3.在树形结构中,树根结点没有（ 前驱）结点,其余每个结点有且只有（1 ）个前驱结点；叶子结点没有（后继 ）结点,其余每个结点的后续结点可以（任意个 ）。 4.在图形结构中,每个结点的前驱结点数和后续结点数可以（任意个 ）。 5.线性结构中元素之间存在（一对一 ）关系,树形结构中元素之间存在

4、（一对多 ）关系,图形结构中元素之间存在（多对多 ）关系。 6.算法的五个重要特性是（可行性 ）、（确定性 ）、（有穷性 ）、（输入 ）、（输出 ）。7.数据结构的三要素是指（数据元素 ）、（逻辑结构 ）和（存储结构 ）。8.链式存储结构与顺序存储结构相比较,主要优点是（插入、删除、合并等操作比较方便 ）。 9.设有一批数据元素,为了最快的存储某元素,数据结构宜用（ 顺序）结构,为了方便插入一个元素,数据结构宜用（ 链式）结构。 第二章 线性表 线性表的判断题 1.线性表的链接存储，表中元素的逻辑顺序与物理顺序一定相同。（错） 选择题部分 1.一个线性表第一个元素的存储地址是100,每个元素的

5、长度为2,则第5个元素的地址是( B) （A）110 （B）108（C）100 （D）120 3. 向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动（C ）个元素。 （A）64（B）63 （C）63.5（D）74.线性表采用链式存储结构时，其地址（D ）。 (A) 必须是连续的 (B) 部分地址必须是连续的(C) 一定是不连续的 (D) 连续与否均可以5. 在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行（B ） （A）s-next=p;p-next=s; （B） s-next=p-next;p-next=s;（C）s-next=p-next;

6、p=s; （D）p-next=s;s-next=p;6.在一个单链表中，若删除p所指结点的后续结点，则执行（ A） （A）p-next=p-next-next; （B）p=p-next; p-next=p-next-next;（C）p-next=p-next; （D）p =p-next-next;7.下列有关线性表的叙述中，正确的是（A） （A）线性表中的元素之间隔是线性关系（B）线性表中至少有一个元素（C）线性表中任何一个元素有且仅有一个直接前趋（D）线性表中任何一个元素有且仅有一个直接后继8.线性表是具有n个（ C）的有限序列（n0) （A）表元素 （B）字符 （C）数据元素 （D）数据项

7、填空题部分 1.已知P为单链表中的非首尾结点，在P结点后插入S结点的语句为：(s-next=p-next;p-next=s; ) 。 2.顺序表中逻辑上相邻的元素物理位置(一定 )相邻， 单链表中逻辑上相邻的元素物理位置( 不一定)相邻。 3.线性表L（a1，a2，.，an）采用顺序存储，假定在不同的n1个位置上插入的概率相同，则插入一个新元素平均需要移动的元素个数是(n/2 ) 第三章 栈和队列 选择题部分 1. 一个栈的入栈序列是a,b,c,d,e,则栈的不可能的输出序列是（C）。 （A） edcba（B）decba（C）dceab （D）abcde 2.栈结构通常采用的两种存储结构是（A

8、）。 （A） 线性存储结构和链表存储结构（B）散列方式和索引方式（C）链表存储结构和数组 （D）线性存储结构和非线性存储结构3.判定一个栈ST(最多元素为m0)为空的条件是（B）。 （A） ST-top!=0 （B）ST-top=0 （C）ST-top!=m0 （D）ST-top=m04.判定一个栈ST(最多元素为m0)为栈满的条件是（D）。 （A）ST-top!=0 （B）ST-top=0 （C）ST-top!=m0-1（D）ST-top=m0-15.一个队列的入列序列是1,2,3,4,则队列的输出序列是（B）。 （A）4,3,2,1（B）1,2,3,4（C）1,4,3,2（D）3,2,4,

9、16.循环队列用数组A0,m-1存放其元素值,已知其头尾指针分别是front和rear则当前队列中的元素个数是（） （A）(rear-front+m)%m （B） rear-front+1 （C）rear-front-1（D）rear-front7.栈和队列的共同点是（C） （A） 都是先进后出（B）都是先进先出（C）只允许在端点处插入和删除元素（D）没有共同点8.表达式a*(b+c)-d的后缀表达式是（B）。 （A）abcd*+-（B）abc+*d- （C）abc*+d-（D）-+*abcd9.4个元素a1，a2，a3和a4依次通过一个栈，在a4进栈前，栈的状态，则不可能的出栈序是（C） (

10、A)a4，a3，a2，a1(B)a3，a2，a4，a1 (C)a3，a1，a4，a2(D)a3，a4，a2，a110.以数组Q0.m1存放循环队列中的元素，变量rear和qulen分别指示循环队列中队尾元素的实际位置和当前队列中元素的个数，队列第一个元素的实际位置是（D） (A)rearqulen(B)rearqulenm(C)mqulen (D)1（rearmqulen）% m填空题部分 1.栈的特点是（先进后出）,队列的特点是（先进先出）。 2.线性表、栈和队列都是（线性）结构,可以在线性表的（任意）位置插入和删除元素，对于栈只能在（端点）插入和删除元素，对于队列只能在（队尾）插入元素和（

11、对头）删除元素。 3.一个栈的输入序列是12345,则栈的输出序列12345是（可能的）。 4.设栈S和队列Q的初始状态皆为空，元素a1，a2，a3，a4，a5和a6依次通过一个栈，一个元素出栈后即进入队列Q，若6个元素出队列的顺序是a3，a5，a4，a6，a2，a1则栈S至少应该容纳(4 )个元素。 第四章 串 选择题部分 1.下列关于串的叙述中，正确的是（A） (A)一个串的字符个数即该串的长度(B)一个串的长度至少是1(C)空串是由一个空格字符组成的串(D)两个串S1和S2若长度相同，则这两个串相等第六章 树（基础知识） 选择题部分 1.在线索化二叉树中,t所指结点没有左子树的充要条件是

12、（B） （A）t-left=NULL （B）t-ltag=1（C）t-ltag=1且t-left=NULL （D）.以上都不对2.二叉树按某种顺序线索化后,任一结点均有指向其前趋和后继的线索,这种说法 （A）（A）正确（B）错误3.二叉树的前序遍历序列中,任意一个结点均处在其子女结点的前面,这种说法（A） (A)正确(B)错误4.由于二叉树中每个结点的度最大为2,所以二叉树是一种特殊的树,这种说法 （A）（A）正确（B）错误5.设高度为h的二叉树上只有度为0和度为2的结点,则此类二叉树中所包含的结点数至少为（B）。 （A）2h （B）2h-1（C）2h+1（D）h+16.已知某二叉树的后序遍历

13、序列是dabec。中序遍历序列是debac,它的前序遍历序列是（D）。 （A）acbed （B）decab（C）deabc （D）cedba7.如果T2是由有序树T转换而来的二叉树,那么T中结点的前序就是T2中结点的（A） （A）前序（B）中序（C）后序D.层次序8.某二叉树的前序遍历结点访问顺序是abdgcefh,中序遍历的结点访问顺序是dgbaechf,则其后序遍历的结点访问顺序是（D）。 （A）bdgcefha （B）gdbecfha （C）bdgaechf （D）gdbehfca9.二叉树为二叉排序树的充分必要条件是其任一结点的值均大于其左孩子的值、小于其右孩子的值。这种说法（B） （

14、A）正确（B）错误10.按照二叉树的定义,具有3个结点的二叉树有（C）种。 （A）3（B）4（C）5（D）611.在一非空二叉树的中序遍历序列中,根结点的右边（A） （A）只有右子树上的所有结点（B）只有右子树上的部分结点（C）只有左子树上的部分结点（D）只有左子树上的所有结点12.树最适合用来表示（C）。 （A）有序数据元素（B）无序数据元素（C）元素之间具有分支层次关系的数据（D）元素之间无联系的数据13.任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序（A） （A）不发生改变（B）发生改变（C）不能确定D.以上都不对14.实现任意二叉树的后序遍历的非递归算法而不使用栈结构,最

15、佳方案是二叉树采用（C）存储结构。 （A）二叉链表（B）广义表存储结构（C）三叉链表（D）顺序存储结构15.对一个满二叉树,m个树叶,n个结点,深度为h,则（D） （A）n=h+m （B）h+m=2n（C）m=h-1（D）n=2h-116.如果某二叉树的前序为stuwv,中序为uwtvs,那么该二叉树的后序为（C） （A）uwvts （B）vwuts（C）wuvts （D）wutsv17.具有五层结点的二叉平衡树至少有（B）个结点。 （A）10（B）12（C）15（D）17树的判断题 1.二叉树中任何一个结点的度都是2。（错）2.由二叉树结点的先根序列和后根序列可以唯一地确定一棵二叉树。（对）

16、3.一棵哈夫曼树中不存在度为1的结点。（对）4.平衡二叉排序树上任何一个结点的左、右子树的高度之差的绝对值不大于1（对） 填空题部分 1.指出树和二叉树的三个主要差别（树的结点个数至少为1，而二叉树的结点个数可以为0）,（树的结点的最大度数任意，而二叉树的结点度数最大为2）,（树的结点无左右之分，而二叉树的结点有左右之分）。 2.从概念上讲,树与二叉树是两种不同的数据结构,将树转化为二叉树的基本目的是（可采用树的存储结构并利用二叉树的已有算法解决树的有关问题） 3.若结点A有三个兄弟(包括A本身),并且B是A的双亲结点,B的度是(3 ) 4.若一棵具有n个结点的二叉树采用标准链接存储结构,那么

17、该二叉树所有结点共有（n+1 ）个空指针域。 5.已知二叉树的前序序列为ABDEGCFHIJ,中序序列为DBGEAHFIJC,写出后序序列（DGEBHJIFCA ）。 6.已知二叉树的后序序列为FGDBHECA,中序序列为BFDGAEHC ,并写出前序序列（ ）。 7.找出满足下列条件的二叉树 1）先序和中序遍历，得到的结点访问顺序一样。(无左子树 ) 2）后序和中序遍历，得到的结点访问顺序一样。( 无右子树)3）先序和后序遍历，得到的结点访问顺序一样。( 仅有一个结点的二叉树) 8.一棵含有n个结点的k叉树，可能达到的最大深度和最小深度各是多少？n ，LOG2N+1 9.一棵二叉树有67个结

18、点，这些结点的度要么是0，要么是2。这棵二叉树中度为2的结点有( 33)个。10.含有100个结点的树有(99 )条边。 11.一棵哈夫曼树有19个结点，则其叶子结点的个数是(10 )。 12.设一棵二叉树结点的先根序列为ABDECFGH，中根序列为DEBAFCHG，则二叉树中叶子结点是( )。13.将一棵有50个结点的完全二叉树从根结点开始，由根向下，每一层从左至右，顺序地存储在一个一维数组bt1.50中，这棵二叉树最下面一层上最左边一个结点存储在数组元素(bt32)中。 第七章 图（基础知识） 图的判断题 1.一个无向图的邻接矩阵中各元素之和与图中边的条数相等(错） 选择题部分 1.在一个

19、图中,所有顶点的度数之和等于所有边数的（C）倍。 （A）1/2（B）1（C）2（D）42.在一个有向图中,所有顶点的入度之和等于所有顶点的出度之和的（B）倍。 （A）1/2（B）1（C）2（D）43.一个有n个顶点的无向图最多有（C）条边。 （A）n （B）n(n-1)（C）n(n-1）/2（D）2n4.具有4个顶点的无向完全图有（A）条边。 （A）6（B）12（C）16（D）205.具有6个顶点的无向图至少应有（A）条边才能确保是一个连通图。 （A）5（B）6（C）7（D）86.在一个具有n个顶点的无向图中,要连通全部顶点至少需要（C）条边。 （A）n （B）n+1（C）n-1（D）n/27

20、.对于一个具有n个顶点的无向图,若采用邻接矩阵表示,则该矩阵的大小（D） （A）n （B）(n-1)2（C）n-1 （D）n28.对于一个具有n个顶点和e条边的无向图,若采用邻接表表示,则表头向量的大小为（A），所有邻接表中的结点总数是（C）。 （A）n （B）n+1（C）n-1（D）n+e（A）e/2（B）e（C）2e （D）n+e9.采用邻接表存储的图的深度优先遍历算法类似于二叉树的（A）。 （A）先序遍历（B）中序遍历（C）后序遍历（D）按层遍历10.采用邻接表存储的图的宽度优先遍历算法类似于二叉树的（B）。 （A）先序遍历（B）中序遍历（C）后序遍历（D）按层遍历11.判定一个有向图是

21、否存在回路除了可以利用拓扑排序方法外,还可以利用（D）. （A）求关键路径的方法（B）求最短路径的Dijkstm方法（C）宽度优先遍历算法（D）深度优先遍历算法12.用Prim算法求下列连通的带权图的最小代价生成树，在算法执行的某刻，已选取的顶点集合U1，2，3，边的集合TE（1，2），（2，3），要选取下一条权值最小的边，应当从（A）组中选取。(A)（1，4），（3，4），（3，5），（2，5）(B)（4，5），（1，3），（3，5）(C)（1，2），（2，3），（3，5）(D)（3，4），（3，5），（4，5），（1，4） 填空题部分 1.n个顶点的连通图至少（n-1）条边。 2.在一个无

22、环有向图G中，若存在一条从顶点i到顶点j的弧，则在顶点的拓扑序列中，顶点i与顶点j的先后次序是(i在前，j在后 )。 3.在一个无向图的邻接表中，若表结点的个数是m，则图中边的条数是(m/2 )条。 第八章 排序（基础知识） 选择题部分 1.在所有排序方法中，关键字比较的次数与记录得初始排列次序无关的是（D） （A）希尔排序 （B）起泡排序 （C）插入排序 （D）选择排序 2.设有1000个无序的元素,希望用最快的速度挑选出其中前10个最大的元素,最好（C）排序法。 （A）起泡排序（B）快速排序（C）堆排序（D）基数排序3.在待排序的元素序列基本有序的前提下,效率最高的排序方法是（A） （A）

23、插入排序（B）选择排序（C）快速排序（D）归并排序4.一组记录的排序码为(46,79,56,38,40,84),则利用堆排序的方法建立的初始推为（B）。 （A）79,46,56,38,40,80 （B）84,79,56,38,40,46（C）84,79,56,46,40,38（D）84,56,79,40,46,385.一组记录的关键码为(46,79,56,38,40,84),则利用快速排序的方法,以第一个记录为基准得到的一次划分结果为（C）。 （A）38,40,46,56,79,84（B）40,38,46,79,56,84（C）40,38,46,56,79,84（D）40,38,46,84,5

24、6,796.一组记录的排序码为(25,48,16,35,79,82,23,40,36,72),其中含有5个长度为2的有序表,按归并排序的方法对该序列进行一趟归并后的结果为（A）。 （A）16,25,35,48,23,40,79,82,36,72（B）16,25,35,48,79,82,23,36,40,72（C）16,25,48,35,79,82,23,36,40,72（D）16,25,35,48,79,23,36,40,72,827.排序方法中,从未排序序列中依次取出元素与己排序序列(初始时为空)中的元素进行比较,将其放入己排序序列的正确位置上的方法,称为（C） （A）希尔排序（B）起泡排序

25、（C）插入排序（D）选择排序8.排序方法中,从未排序序列中挑选元素并将其依次放入己排序序列(初始为空)的一端的方法,称为（D） （A）希尔排序（B）归并排序（C）插入排序（D）选择排序9.用某种排序方法对线性表(25,84,21,47,15,27,68,35,20)进行排序时,元素序列的变化情况如下: (1)25,84,21,47,15,27,68,35,20 (2)20,15,21,25,47,27,68,35,84 (3)15,20,21,25,35,27,47,68,84 (4)15,20,21,25,27,35,47,68,845则所采用的排序方法是（D）。 （A）选择排序（B）希尔排

26、序（C）归并排序（D）快速排序10.下述几种排序方法中,平均查找长度最小的是（C） （A）插入排序（B）选择排序（C）快速排序（D）归并排序11.下述几种排序方法中,要求内存量最大的是（D）。 （A）插入排序（B）选择排序（C）快速排序（D）归并排序12.快速排序方法在情况下最不利于发挥其长处。C （A）要排序的数据量太大（B）要排序的数据中含有多个相同值（C）要排序的数据已基本有序（D）要排序的数据个数为奇数13.设有10000个元素组成的无序序列,希望尽快挑选出其中前10个最大值元素,在不改变已有算法结构的前提下,以下几种内排序算法中( )最合适。 C(A)选择排序法(B)快速排序法(C)堆排序法(D)冒泡排序法。