1、福师数据结构概论复习题及参考答案docx福师1103批次数据结构概论复习题1一、选择：（每题2分，共30分）1、 一个栈的输入序列为1 2 3 4 5,则下列序列中不可能是栈的输出序列的 是（B ）。A） 2 3 4 1 5 B） 5 4 1 3 2 C） 2 3 1 4 5 D） 1 5 4 3 22、 向一个长度为n的向量的第i （l=i=n+l）个元素之前插入一个元素时，需要后移（D ）个元素。A.n B. n-i C. n+1 D. n-i+13、不带表头的单链表，头指针为head ,判断其是否为空的条件是（D ）。A. head=nil B. head-next=nil12、开放定址
2、法中，增量序列的取法不包括（D ）A.线性探测再散列B.委随机探测再散列C.二次探测再散列 D.随机探测再散列13、 在最好和最坏情况下的时间复杂度均为O(n*logn)且稳定的排序方法是: ( C )A.快速排序 B.堆排序 C.归并排序 D.基数排序14、 设高度为h的二叉树中只有度为0, 2的结点，则该二叉树至少有(B ) 个结点。A. 2h B. 2h-l C. 2h+l D. h+115、 若进栈序列为a,b,c,则通过入出栈操作可能得到的a,b,c的不同排列个 数为：(B )A. 4 B. 5 C. 6 D. 7二、 填空题：(每空2分，共20分)1、 树中结点的最大层次称为树的深
3、度。2、 将一棵树转换成一棵二叉树后，二叉树根结点没有右孩子子树。3、 设二维数组A0. .m-1 0. .n-1按行优先顺序存储在内存中，每个元素占d个字节，则aij的地址为 L0C(a00) + (i*n+j)*d 。4、 在栈中存取数据的原则是：先进先出5、 在栈结构中，允许插入，删除的一端称为栈顶，另一端称为栈底。6、 算法的特点是 输入，输出，有穷性，确定性,可行性7、 路径长度最长的路径叫做关键路径三、 解答题：(每题6分，共30分)1、在具有n个结点的K (k=2)叉树的K叉链表表示中，有多少个空指针。 解：n个结点的K叉树共有nk个指针域，已使用的指针域为1,所以空指针的个数为
4、：n+1;2、 已知一棵二叉树的前序序列和中序序列分别为abdghcefi和gdhbaecif,请 画出该二叉树。解析：知识点二叉树的遍历，根据先序序列，确定a为根 1根据中序序列，确定gdhb为二叉树的左结点，根据先序序列确定a为其根 2根据先序序列a的下一个节点为b,中序中b之前有gdh可以判断，gdh为B的左子结点 先序中下一个结点是d,中序中d之前是g,所以g是d的左子结点，h为d的右子结点。 3至此，a及其左子树判定完毕，运用1-3的步骤判定ecif即可4、3、 一组记录的关键码为（46, 79, 56, 3& 40, 84）,则利用快速排序的方法,分别写 出以第一个记录为基准得到的
5、前三次划分结果。解是需要第一次选择的关键字是需要参与划分的。下面是搜到的具体算法步骤。设要排序的数组是A0AN-1,首先任意选取一个数据（通常选用第一个数据）作 为关键数据，然后将所有比它小的数都放到它前面，所有比它大的数都放到它后面，这 个过程称为一趟快速排序。一趟快速排序的算法是：1） 设置两个变量I、J,排序开始的时候：1=0, J=N-1；2） 以第一个数组元素作为关键数据，赋值给X,即X=A0；3） 从J开始向前搜索，即由后开始向前搜索（J=JT）,找到第一个小于X的值，让 该值与X交换（找到就行.找到后i大小不变）；4） 从I开始向后搜索，即由前开始向后搜索（1=1+1）,找到第一
6、个大于X的值，让 该值与X交换（找到就行.找到后j大小不变）；5） 重复第3、4步，直到I=J； （3,4步是在程序中没找到时候j=j-l, i-i+E找 到并交换的时候i，j指针位置不变。另外当i=j这过程一定正好是i+或j+完成的最后 另循环结束）本题起始为：46,79,56,38,40,84求解步骤如下：确定关键字为461） 46为关键字，从最后84开始比较，找到第一比46小的数，和46交换。得到 第一次排序结果：40,79,56,38,46,842） 46为关键字，从40的下个数79开始比较，找第一比46大的，和46交换，得到 第二次排序结果：40,46,56,38,79,84O O
7、O O4、 下面程序段的时间复杂度为 。（用0估计）FOR i:=l TO n DOFOR j:=i TO n DOs=s+j;解O(n)5、下面是一个无向图的邻接矩阵，试将有关数据填入本题的空白处(顶点号 由1开始)0101110100010101010110010该图的顶点数为该图的边数为顶点3的度为解5； 6； 2四、算法题：(每题10分，共20分，共2小题)1、中序遍历二叉树算法解Void merge(rcdtype sr, rcdtype &tr,int I,int m, int n)For(j=m+l, k=I;i=m&j=n;+k)If(la(sqtil - key, sqj.
8、key)trk=sri+;Else trk=srj+;If(i=m) tr k. n=sr i. n;If(j=n) trk. n=srj. n;2、归并排序算法解Midorder traverse (b it ree t, sta/t us(*visi t) (t elemtype e)Status printelement(telemtype e)Printf(e);Return ok;If(t)If(Midordertraverse (t-lch订d, visit)If (visit(t-data)If(Midordertraverse (t-rch订d, visit)Return ok
9、;Return errorElse return ok;福师1103批次数据结构概论复习题2一、选择：(每题2分，共30分，共15小题)1、 直接插入排序算法的时间复杂度为(C )A. 0 (N) Bo 0 (1) C. 0(N2) D. O(LOGN)2、 下列排序方法中，从平均时间而言最佳的是(A )A.快速 B.希尔 C.基数 D.归并3、 下列是稳定的排序方法的(D )A.快速 B.希尔 C.堆 D.基数4、 所需辅助空间为0 (N)的排序方法为(D )A.快速 B.希尔 C.基数 D.归并5表达式通常用(B )表示A.二叉树的先序 B.二叉树的中序 C.二叉树的后序 D.二叉树的层次
10、6、 构造哈希函数的方法不包括(D )A.直接定址 B.数字分析 C.折叠法 D.二分查找7、 哈希表中常用的处理冲突的方法不包括(D )A.开放定址 B.再哈希 C.链地址 D.折叠8、 二叉排序树的特点不包括(D )A.右子树大于根的值 B.左子术小于根的值 C.左右子树为二叉排序树D.左子树大于右子树的值9、 三个结点可以构成多少种二叉树(A )A. 5 B. 6 C. 7 D. 410、 假设一个栈的进栈顺序为a,b,c,d,则不可能的出栈顺序为（B ）A. a, b, c, d B. a, d, b, c C. d, c, b, a D. c, b, a, d11、 用邻接表表示图进
11、行深度优先遍历时，通常采用（A ）来实现算法.A.栈 B.队列 C.树 D.图12、 已知L是带头结点的单链表，p指向表中某结点，则要删除p结点的后继 结点应执行操作（A ） oA. p-next:二p-nextTnext; p-nextnext:二 T. next;C. pTnext:二s; sTnext:二pTnext; D. sTnext:二pTnext; pTnext:二s;13、 求关键路径的时间复杂度为（A ）A. 0 （N+E） B. O（N+1） C. O（l+E） D. O（N2+1）14、 4个结点的完全连通无向图有几个边（D ）A. 4 B. 3 C. 5 D. 615、
12、 顺序结构中删除一个元素的平均时间为（A ）A. 1/N B. 1/（N+1） C. 1 D. 1/N2二、 填空题：（每空2分，共20分，共5小题）1、 顺序表相对于链表的优点有操作简单和便于实现2、 某二叉树的前序和后序正好相反，则该二叉树一定是高度等于其结点数 二叉树。3、 图的遍历方式有深度和 广度.4、 栈的存储方式有顺序和链式两种5、 开放定址法中，增量序列的取法有线性探测再散列、二次探测再散列 和伪随机数序列三种三、 解答题：（每题6分，共30分，共5小题）1、 算法的特点答：1）有穷性2）确定性3）可行性4）输入5）输出2、 简单描述栈的特点答：先进后出3、 49, 38, 6
13、5, 97, 76, 13, 27, 49, 55, 4 的希尔排序过程答：49386597761327495541327495544938659776134493827495565977641327384949556576974、描述49, 38, 27, 67, 39, 87快速排序的过程答：解析：知识点快速排序，下面是搜到的具体算法步骤。设要排序的数组是A0AN-1,首先任意选取一个数据（通常选用第一个数据）作 为关键数据，然后将所有比它小的数都放到它前面，所有比它大的数都放到它后面，这 个过程称为一趟快速排序。一趟快速排序的算法是：1） 设置两个变量I、J,排序开始的时候：1=0, J
14、=N-1；2） 以第一个数组元素作为关键数据，赋值给X,即X=A0；3） 从J开始向前搜索，即由后开始向前搜索（J=JT）,找到第一个小于X的值，让该值 与X交换（找到就行.找到后i大小不变）；4） 从I开始向后搜索，即由前开始向后搜索（1=1+1）,找到第一个大于X的值，让该值 与X交换（找到就行.找到后j大小不变）；5） 重复第3、4步，直到I=J； （3, 4步是在程序中没找到时候j=j-l, i=i+lo找到并 交换的时候i, j指针位置不变。另外当i=j这过程一定正好是i+或j+完成的最后另循 环结束）下面是排序结果：493865977613272738134976976549132
15、738496576975、从时间复杂度，空间复杂度方面简单分析快速排序，基数排序，堆排序, 归并排序，简单排答：平均时间O（N2）快速排序0 (NL0GN)0(L0GN)堆排序0 (NL0GN)0(1)归并排序0(NL0GN)0(N)基数排序0 (D (N+RD)0(RD)四、算法题：(每题10分，共20分，共2小题)1、 2-路归并排序算法答：Void merge(redtype sr, redtype &tr, int I, int m, int n)For(j二m+1, k=I;i二m&j二n;+k)If (la(sqi. key, sqj. key)trk=sri+;Else trk二
16、srj+;If (i=m) trk. n=sr i. n;If (jdata)If (preordertraverse(t-lchild, visit)If (preordertraverse(t-rch订d, visit)Return ok;Return errorElse return ok;福师1103批次数据结构概论复习题3A. 1 B. 0 C. 28、具有6个顶点的无向图至少要有(C )条边才能确保是一个连通图。A. 4 B. 5 C. 6 D. 79、 已知一个顺序存储的线性表，设每个结点需占m个存储单元,若第一个结点 的地址为dal,则第i个结点的地址为(A )A. dal+(
17、iT)*m B. dal+i*m C. dal-i*m D. dal+(i+1) *m10、 在n个结点的顺序表中,算法的时间复杂度是0(1)的操作是：(A )A.访问第i个结点(l=i=n)和求第i个结点的直接前趋(2=i=n)B.在第i个结点后插入一个新的结点(l=i=n)C.删除第i个结点(l=inext;if(q) return q;else Error (*p is not in L);void Demo2(ListNode *p, ListNode *q)/*P, *q是某个链表中的两个结点 DataType temp;temp=p-data; p-data=q-data; q-d
18、ata=temp; 答：1)此算法是找个q结点是否存在2)此算法交换数据2、冒泡排序算法答:冒泡排序算法：void BubbleSort2(int a, int n) /相邻两趟向相反方向起泡的冒泡排序算法 change=l; low=0; high=n-l; /冒泡的上下界while(lowhigh & change) change二0; /设不发生交换for (i=low; iai+l) aiai+l ; change二1; / 有交换,修改标志 changehigh; /修改上界for (i=high; ilow; i-) /从下向上起泡if (aiai-l) aiail ;change
19、=l; low+; /修改下界/while/BubbleSort2算法讨论题目中“向上移”理解为向序列的右端，而“向下移”按向序列的左 端来处理。第一章概述1.算法的计算量的大小称为计算的( )。A.效率 B.复杂性 C.现实性 D.难度2.算法的时间复杂度取决于()A.问题的规模 B.待处理数据的初态 C. A和B3.一个算法应该是( )。A.程序 B.问题求解步骤的描述 C.要满足五个基本特性 D. A和C.4.下面说法错误的是( )(1)算法原地工作的含义是指不需要任何额外的辅助空间(2)在相同的规模n下，复杂度0(n)的算法在时间上总是优于复杂度0(2)的算法(3)所谓时间复杂度是指最
20、坏情况下，估算算法执行时间的一个上界(4)同一个算法，实现语言的级别越高，执行效率就越低A. (1) B. (1), (2) C. (1), (4) D. (3)5.从逻辑上可以把数据结构分为( )两大类。A.动态结构、静态结构 B.顺序结构、链式结构C.线性结构、非线性结构 D.初等结构、构造型结构6.以下与数据的存储结构无关的术语是（ ）oA.循环队列 B.链表 C.哈希表 D.栈7.以下数据结构中，哪一个是线性结构（ ）？A.广义表 B.二叉树 C.稀疏矩阵 D.串&以下数据结构中，（ ）是非线性数据结构A.树 B.字符串 C.队 D.栈9.下列数据中，（ ）是非线性数据结构。A.栈 B
21、.队列 C.完全二叉树 D.堆10.连续存储设计时，存储单元的地址（ ）。A. 一定连续B. 一定不连续C.不一定连续D.部分连续，部分不连续第二章线性表1.下述哪一条是顺序存储结构的优点？（ ）A.存储密度大B.插入运算方便C.删除运算方便D.可方便地用于各种逻辑结 构的存储表示2.下面关于线性表的叙述中，错误的是哪一个？（ ）A.线性表采用顺序存储，必须占用一片连续的存储单元。B.线性表采用顺序存储，便于进行插入和删除操作。C.线性表采用链接存储，不必占用一片连续的存储单元。D.线性表采用链接存储，便于插入和删除操作。3.链表不具有的特点是（ ）A.插入、删除不需要移动元素B.可随机访问任
22、一元素C.不必事先估计存储空间D.所需空间与线性长度成正比1.链表中的头结点仅起到标识的作用。（F ）2.顺序存储结构的主要缺点是不利于插入或删除操作。（T ）3.线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。（T ）4.顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好。（F ）5.对任何数据结构链式存储结构一定优于顺序存储结构。（F ）6.顺序存储方式只能用于存储线性结构。（F ）9.线性表的特点是每个元素都有一个前驱和一个后继。（F ）12.线性表只能用顺序存储结构实现。（F ）13.线性表就是顺序存储的表。（F ）15.顺序存储方式的优点是存储密度大，且插入、删
23、除运算效率高。（F ）16.链表是采用链式存储结构的线性表，进行插入、删除操作时，在链表中比在顺序存储 结构中效率高。（F ）第三章栈和队列1.对于栈操作数据的原则是（）。A.先进先出 B.后进先出 C.后进后出 D.不分顺序2.有六个元素6, 5, 4, 3, 2, 1的顺序进栈，问下列哪一个不是合法的出栈序列？（ ）A. 5 4 3 6 1 2 B. 4 5 3 1 2 6 C. 3 4 6 5 2 1 D. 2 3 4 1 5 63.设计一个判别表达式中左，右括号是否配对出现的算法，采用（ ）数据结构最佳。A.线性表的顺序存储结构 B.队列 C.线性表的链式存储结构 D.栈4.循环队列存
24、储在数组AO.m中，则入队时的操作为（ ）=6.下面关于串的的叙述中，哪一个是不正确的？（ ）A.串是字符的有限序列 B.空串是由空格构成的串C.模式匹配是串的一种重要运算D.串既可以采用顺序存储，也可以采用链式存储第四章树4.设树T的度为4,其中度为1, 2, 3和4的结点个数分别为4, 2, 1, 1则T中的叶子数为（ ）A. 5 B. 6 C. 7 D. 85.在下述结论中，正确的是（ ）只有一个结点的二叉树的度为0;二叉树的度为2；二叉树的左右子树可任 意交换；深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。A. B. C. D.6.设森林F对应的二叉树为B,它有m个结点，
25、B的根为p, p的右子树结点个数为n,森林F中第一棵树的结点个数是（ ）A. m-n B. m-nl C. n+1 D.条件不足，无法确定&若一棵二叉树具有10个度为2的结点,5个度为1的结点，则度为0的结点个数是（） A. 9 B. 11 C. 15 D.不确定9.在一棵三元树中度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，则度为0的结点数为（ ）个A. 4 B. 5 C. 6 D. 710.设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为Ml, M2和M3。与森林F对应的二叉树根结点的右子树上的结点个数是（ ）。A. Ml B. M1+M2 C. M3 D. M2+M311.具有10个叶结点的二叉树中有（）个度为2的结点A. 8 B. 9 C. 10 D. 1112.一棵完全
