数据结构复习提纲带所有答案.docx

《数据结构复习提纲带所有答案.docx》由会员分享，可在线阅读，更多相关《数据结构复习提纲带所有答案.docx（24页珍藏版）》请在三一办公上搜索。

1、数据结构复习提纲一，选择题1. 数据结构是指（A）。A.数据元素的组织形式B.数据类型C.数据存储结构D.数据定义2. 数据在计算机存储器内表示时物理地址与逻辑地址不相同的，称之为（C）。A. 存储结构B. 逻辑结构C. 链式存储结构D. 顺序存储结构3. 设语句x+的时间是单位时间，则以下语句的时间复杂度为（B）。for(i=1; i=n; i+)for(j=i; j=n; j+)x+;A. 0(1)B.o( n 2)C. O(n)D.O( n 3)4.计算机内部数据处理的基本单位是（B）。A.数据B.数据元素 C.数据项 D.数据库5.在一个长度为n的顺序表中删除第i个元素（1=inext

2、=s; s-prior=p;p-next-prior=s; s-next=p-next;B. s-prior=p; s-next=p-next;p-next=s; p-next-prior=s;C. p-next=s; p-next-prior=s;s-prior=p; s-next=p-next;D. s-prior=p; s-next=p-next;p-next-prior=s; p-next=s;9. 设单链表中指针p指向结点m,若要删除m之后的结点(若存在), 则需修改指针的操作为A。A. p-next=p-next-next; B. p=p-next;C. p=p-next-next

3、;D. p-next=p;10. 在一个长度为n的顺序表中向第i个元素(0 inext=p-next; p-next=sB. q-next=s; s-next=pC. p-next=s-next; s-next=pD. p-next=s; s-next=q12. 在顺序表中，只要知道_D_,就可在相同时间内求出任一结点的 存储地址。A.基地址B.结点大小C.向量大小D.基地址和结点大小13. 设有一个栈，元素的进栈次序为A, B, C, D, E,下列是不可能的出 栈序列_ C_。A. A, B, C, D, EB. B, C, D, E, AC. E, A, B, C, DD. E, D,

4、C, B, A14. 向一个栈顶指针为hs的链栈中插入一个s结点时，应执行_B_。A. hs-next=s;B. s-next=hs; hs=s;C. s-next=hs-next;hs-next=s;D. s-next=hs; hs=hs-next;15. 在具有n个单元的顺序存储的循环队列中，假定front和rear分 别为队头指针和队尾指针，则判断队满的条件为_D。A. rear%n= = frontB. (front+l)%n= = rearC. rear % n -1= = front D. (rear+l) %n= = front16. 在具有n个单元的顺序存储的循环队列中，假定f

5、ront和rear分 别为队头指针和队尾指针，则判断队空的条件为_C_。A.rear%n= = frontB.front+l= rearC. rear= = frontD. (rear+l) %n= front17. 在一个链队列中，假定front和rear分别为队首和队尾指针，则 删除一个结点的操作为_A。A. front二front-nextB. rear二rear-nextC. rear二front-nextD. front二rear-next418. 设二维数组A0m-10n-1按行优先顺序存储在内存中，第一个元素的地址为p,每个元素占k个字节，则元素a的地址为(A)。A.p +i*n

6、+j-1*kB.p+(iT)*n+jT*kC.p+(jT)*n+iT*kD.p+j*n+iT*k19. 若数组A0m0n按列优先顺序存储，则a.地址为(A)。A.LOC(a00) + j*m+iB. LOC(a0) + j*n+iC.LOC(a00) + (j-1)*n+i-1D. LOC(a0) + (jT)*m+iT20. 若下三角矩阵A*,按列顺序压缩存储在数组Sa0(n+1)n/2中，则非零元素a.的地址为(B)。(设每个元素占d个字节)A. (j-1)*n-.软，。+i-1*d2B. (j-1)*n- (一 W D +i*d2C. (j-1)*n-(j-2)(j-1) +i+1*d2

7、D. (j-1)*n-.2)(. 1) +i-2*d221. 设有广义表D=(a,b,D)，其长度为(B)，深度为(A)。A.无穷大 B. 3C. 2D.522. 广义表 A=(x,(a,B),(x,(a,B),y)，则运算 head(head(tail(A)的结果 为(A)。A.xB.(a,B)C.(x,(a,B) D.A23. 稀疏矩阵一般的压缩存储方法有两种，即(C)。A.二维数组和三维数组C.三元组和十字链表B.三元组和散列D.散列和十字链表24. 一个广义表的表头总是一个（D）。A.广义表 B.元素C.空表D.元素或广义表25. 一个广义表的表尾总是一个（A ）。A.广义表 B.元素

8、C.空表D.元素或广义表526. 在一棵度为3的树中，度为3的结点数为2个，度为2的结点数 为1个，度为1的结点数为2个，则度为0的结点数为（C）个。树中结点数等于所有结点度数的和加1.所以：2+1+2+X=2*3+1*2+2*1+X*0+1所 以X=6A. 4 B. 5 C. 6 D. 727. 假设在一棵二叉树中，双分支结点数为15,单分支结点数为30 个，则叶子结点数为（B）个。N=n0+n1+n2;no=n2+116A. 15 B. 16 C. 17 D. 4728. 假定一棵三叉树的结点数为50，则它的最小高度为（C）。最小高度就是除叶子外,每个结点都有3个孩子的三叉树的高度：x 层

9、公有 1+3+9+-+3A（x-1）=（3Ax-1）/2 要让结果50x=5A. 3 B. 4 C. 5 D. 629. 用顺序存储的方法将完全二叉树中的所有结点逐层存放在数组中R1.n，结点Ri若有左孩子，其左孩子的编号为结点（B）。右孩子节点为AA. R2i+1 B. R2i C. Ri/2 D. R2i-130. 由权值分别为3, 8, 6, 2, 5的叶子结点生成一棵哈夫曼树，它的带 权路径长度为（D）。画出哈夫曼树 （6+5+8）*2+（2=3）*3=53A. 24B. 48C. 72D. 5331. 设n , m为一棵二叉树上的两个结点，在中序遍历序列中n在m 前的条件是(B)。中

10、序遍历就是一竖一竖列的读，只要在左方就okA. n在m右方B. n在m左方C. n是m的祖先D. n是m的子孙32. 如果F是由有序树T转换而来的二叉树，那么T中结点的前序就 是F中结点的(B)。A.中序 B.前序 C.后序 D.层次序633. 在一个具有n个顶点的有向图中，若所有顶点的出度数之和为s， 则所有顶点的入度数之和为(A)。A. sB. s-1C. s+1D. n34. 在一个具有n个顶点的有向图中，若所有顶点的出度数之和为s， 则所有顶点的度数之和为(D)。A. sB. s-1C. s+1D. 2s35. 在一个具有n个顶点的无向完全图中，所含的边数为(C)。A. n B. n(

11、n-1) C. n(n-1)/2 D. n(n+1)/236. 在一个具有n个顶点的有向完全图中，所含的边数为(B )。A. nB. n(n-1) C. n(n-1)/2 D. n(n+1)/237. 若一个图中包含有k个连通分量，若要按照深度优先搜索的方法 访问所有顶点，则必须调用(A)次深度优先搜索遍历的算法。A. kB. 1C. k-1D. k+138. 若要把n个顶点连接为一个连通图，则至少需要(C )条边。A. nB. n+1C. n-1D. 2n39. 在一个具有n个顶点和e条边的无向图的邻接矩阵中，表示边存 在的元素(又称为有效元素)的个数为(D )。A. nB. nxeC. e

12、D. 2xe40. 在一个具有n个顶点和e条边的有向图的邻接矩阵中，表示边存 在的元素个数为(C)。A. nB. nxeC. eD. 2xe41. 在一个具有n个顶点和e条边的有向图的邻接表中，保存顶点单 链表的表头指针向量的大小至少为(A )。A. nB. 2nC. eD. 2e42. 对于一个有向图，若一个顶点的度为k1，出度为k2，则对应逆 邻接表中该顶点单链表中的边结点数为(C)。对应邻接表中该顶点单链表中的边结点数为(B )。A. k1B. k2C. k1-k2 D. k1+k243. 若一个图的边集为(A,B),(A,C),(B,D),(C,F),(D,E),(D,F)，则从顶点A

13、开始对该图进行深度优先搜索，得到的顶点序列可能为(B)。A. A,B,C,F,D,EB. A,C,F,D,E,BC. A,B,D,C,F,ED. A,B,D,F,E,C44. 若一个图的边集为(A,B),(A,C),(B,D),(C,F),(D,E),(D,F)，则从顶点A开始对该图进行广度优先搜索，得到的顶点序列可能为(D)。A. A,B,C,D,E,FB. A,B,C,F,D,EC. A,B,D,C,E,FD. A,C,B,F,D,E45. 若一个图的边集为,，则从顶点1开始对该图进行深度优先搜索，得到的顶点序列可能为(A )。B. 1,2, 3,4, 5A. 1,2, 5,4, 3C.

14、1,2, 5, 3,4D. 1,4, 3,2, 546. 若一个图的边集为,，则从顶点1开始对该图进行广度优先搜索，得到的顶点序列可能为(C)。A.1,2,3,4, 5B.1,2,4,3, 5C.1,2,4,5,3D.1,4,2,5,347. 由一个具有n个顶点的连通图生成的最小生成树中，具有(B)条 边。A. nB. n-1C. n+1D. 2 n48. 已知一个有向图的边集为,， 则由该图产生的一种可能的拓扑序列为(A)。A. a,b,c,d,e B. a,b,d,e,b C. a,c,b,e,d D. a,c,d,b,e 749. 对具有n个元素的有序表采用折半查找，则算法的时间复杂度为

15、 (D )。A. O(n)B. O(n2)C. O(1)D. O(log n)250. 若查找每个元素的概率相等，则在长度为n的顺序表上查找任一 元素的平均查找长度为(D)。A. n B. n+1C. (n-1)/2 D. (n+1)/251. 对于长度为9的顺序存储的有序表，若采用折半查找，在等概率 情况下的平均查找长度为(A)的9分之一。A. 20B. 18C. 25D. 2252. 对具有n个元素的有序表采用折半查找，则算法的时间复杂度为 (D)。A. O(n)B. O(n2) C. O(1)D. O(log n)2A. n+kB. k+n/k C. (k+n/k)/2 D. (k+n/

16、k)/2+153. 在索引查找中，若用于保存数据元素的主表的长度为144，它被 均分为12子表，每个子表的长度均为12,则索引查找的平均查找长 度为(A)。A. 13B. 24C. 12D. 7954. 从具有n个结点的二叉排序树中查找一个元素时，在平均情况下 的时间复杂度大致为(C)。A. O(n)B. O(1)C. O(log n) D. O(m)255. 在一棵平衡二叉排序树中，每个结点的平衡因子的取值范围是(A) 。A. -1 1B. -22C. 1 2D. 0156. 若根据查找表(23,44,36,48,52,73,64,58)建立哈希表，采用 h(K)=K%7计算哈希地址，则哈希

17、地址等于3的元素个数(B)。A. 1B. 2C. 3D. 457. 若根据查找表建立长度为m的哈希表，采用线性探测法处理冲突， 假定对一个元素第一次计算的哈希地址为d，则下一次的哈希地址为 (D)。A. dB. d+1C. (d+1)/m D. (d+1)%m858. 在对n个元素进行冒泡排序的过程中，第一趟排序至多需要进行(B) 对相邻元素之间的交换。A. nB. n-1C. n+1D. n/259. 在对n个元素进行直接插入排序的过程中，算法的空间复杂度为(C) 。A.0（1）B. O（log2n）C.O（n2）D.O（nlog2n）60. 在对n个元素进行堆排序的过程中，时间复杂度为（D

18、 ）。A.0（1）B. O（log2n）C.O（n2）D.O（nlog2n）61. 假定一个初始堆为（1, 5, 3, 9, 12, 7, 15, 10），要求从大到小排序， 则进行第一趟堆排序后得到的结果为（A）。A. 3, 5, 7, 9, 12, 10, 15, 1B. 3, 5, 9, 7, 12, 10, 15, 1C. 3, 7, 5, 9, 12, 10, 15, 1D. 3, 5, 7, 12, 9, 10, 15, 162. 若对n个元素进行归并排序，则进行归并的趟数为（D）。A. nB. n-1C. n/2D.log n263. 若要对1000个元素排序，要求既快又稳定，则

19、最好采用（B） 方法。A.直接插入排序B.归并排序C.堆排序D.快速排序64. 若要对1000个元素排序，要求既快又节省存储空间，则最好采 用（C）方法。A.直接插入排序B.归并排序 C.堆排序 D.快速排序65. 在平均情况下速度最快的排序方法为（D）。A.简单选择排序 B.归并排序 C.堆排序 D.快速排序 二，填空题1. 数据结构按逻辑结构可分为两大类，分别是线性结构_和_非线性 结构_。2. 数据的逻辑结构有四种基本形态，分别是_集合_、_线性_、_树_ 和_图_。3. 线性结构反映结点间的逻辑关系是一对一的，非线性结构反映 结点间的逻辑关系是一对多或多对多_的。4. 一个算法的效率可

20、分为时间效率和_空间_效率。5. 线性结构中元素之间存在一对一关系；树型结构中元素之间存 在一对多关系；图型结构中元素之间存在多对多关系。6. 下面程序段的时间复杂度是O(n)。i=s=0;while(sn)( i+； s+=i;7. 下面程序段的时间复杂度是O(Log3N)。i=1;while(i=n)i=i*3;8. 算法时间复杂度的分析通常有两种方法，即事后统计，事前估 计的方法，通常我们对算法求时间复杂度时，米用后一种方法。-29. 在一个长度为n的顺序表的第i个元素之前插入一个元素，需 要后移n-i+1个元素。10. 在线性表的顺序存储中，元素之间的逻辑关系是通迁物理存储位置_ 决定

21、的；在线性表的链接存储中，元素之间的逻辑关系是通过链域的指针值决 定的。11. 在双向链表中，每个结点含有两个指针域，一个指向前趋结点，另一个指向后继结点。12. 当对一个线性表经常进行存取操作，而很少进行插入和删除操作时，则采用_顺序存储结构为宜。相反，当经常进行的是插入 和删除操作时，则采用链接存储结构为宜。13. 线性表、栈和队列都是线性结构，可以在线性表的任何 位置插入和删除元素；对于栈只能在顶位置插入和删除元素；对 于队列只能在 队尾位置插入元素和在 队头 位置删除元素。14.设有一空栈，现有输入序列1，2，3，4，5，经过push, push, pop, push, pop, pu

22、sh, push 后，输出序列是2, 3 。15.无论对于顺序存储还是链式存储的栈和队列来说，进行插入 或删除运算的时间复杂度均相同为_o_。416.对于一个二维数组Amn，若按行序为主序存储，则任一元素Aij相对于A00的地址为 iXn+j个元素位置。17. 一个广义表为(a,(a,b),d,e,(i,j),k)，则该广义表的长度为5，深度为3 。18. 一个稀疏矩阵为为(0， 2， 2)， (1， 0，005-。3)，(2，2，-1)，(2，3，5)0300000020-10，则对应的三元组线性表19. 已知广义表A=(a,b,c),(d,e,f)，贝 运算head(tail(tail(A

23、)= e20.设有一个10阶的对称矩阵A，采用压缩存储方式以行序为主序存储，a00为第一个元素，其存储地址为0，每个元素占有1个存储 地址空间，则a85的地址为41。21.已知广义表Ls=(a,(b,c,d),e)，运用head和tail函数取出Ls中的原子b的运算是 head(head(tail(Ls)22. 数组A110, -26, 28以行优先的顺序存储，设第一 个元素的首地址是100,每个元素占3个存储长度的存储空间，则元 素A5, 0, 7的存储地址为 913 。(5-1)*9*7+(0-2)*7+(7-2)*3+100;523. 假定一棵树的广义表表示为A (B (E), C (F

24、 (H, I, J),G), D),则该树的度为_，树的深度为_，终端结点的个数 为冬_，单分支结点的个数为_1 ,双分支结点的个数为_二_, 三分支结点的个数为_二_, C结点的双亲结点为_ A,其孩子结 点为_和_ G_结点。24. 对于一个有n个结点的二叉树，当它为一棵完全_二叉 树时具有最小高度，即为log2(n+1),当它为一棵单支树具有_最大_高 度，即为n。25. 由带权为3, 9, 6, 2, 5的5个叶子结点构成一棵哈夫曼树， 则带权路径长度为_至_。26. 在一棵二叉排序(搜索)树上按遍历得到的结点序 列是一个有序序列。27. 对于一棵具有n个结点的二叉树，当进行链接存储时

25、，其二 叉链表中的指针域的总数为主_个，其中_n-1_个用于链接孩子结 点，_ n+1个空闲着。28. 在一棵二叉树中，度为0的结点个数为n0,度为2的结点个数为 ,则 n0= n2+1。29. 一棵含有n个结点的k叉树，单支树 形态达到最大深度，完全二叉树态达到最小深度。30. 线索链表中的rtag域值为 时，表示该结点无右孩子， 此时 RChild域为指向该结点后继线索的指针。631. 在一个图中，所有顶点的度数之和等于所有边数的_2倍。32. 在一个具有n个顶点的无向完全图中，包含有 n(n-1)/2条边，在一个具有n个顶点的有向完全图中，包含有-n(n-1)_ 条边。33. 假定一个有

26、向图的顶点集为a, b, c, d, e, f，边集为, , , , , ，则出度为 0 的顶点个数为_2_， 入度为1的顶点个数为_4。34. 在一个具有n个顶点的无向图中，要连通所有顶点则至少需 要n-1条边。35. 表示图的两种存储结构为邻接矩阵 和邻接表。36. 若一个图的顶点集为a,b,c,d,e,f，边集为(a,b),(a,c),(b,c),(d,e)，则该图含有 1个连通分量。37. 对于具有n个顶点和e条边的有向图和无向图，在它们对应 的邻接表中，所含边结点的个数分别为2e 和 e 。38. 在有向图的邻接表和逆邻接表表示中，每个顶点邻接表分别 链接着该顶点的所有 出边 和 入

27、边 结点。39. 对于一个具有n个顶点和e条边的无向图，当分别采用邻接 矩阵和邻接表表示时，求任一顶点度数的时间复杂度分别为O(n)，O(e/n)40. 假定一个图具有n个顶点和e条边，则采用邻接矩阵和邻接 表表示时，其相应的空间复杂度分别为O (n2)，O (n+e) _。41. 图的深度，优先搜索遍历算法是一种递归算法，图的上度优先搜索遍历算法需要使用队列。742. 对长度为n的查找表进行查找时，假定查找第i个元素的概 率为p,查找长度(即在查找过程中依次同有关元素比较的总次数) 为c，则在查找成功情况下的平均查找长度的计算公式为_。ipici43. 以折半查找方法在一个查找表上进行查找时

28、，该查找表必须 组织成顺序存储的有序表。44. 从有序表(12, 18, 30, 43, 56, 78, 82, 95)中分别折半查找43和 56元素时，其比较次数分别为 和。45. 假定对长度n=50的有序表进行折半查找，则对应的判定树高 度为 6 ，最后一层的结点数为19。46. 假定在索引查找中，查找表长度为n，每个子表的长度相等，设为s，则进行成功查找的平均查找长度为8。47. 在索引查找中，假定查找表(即主表)的长度为96，被等分 为8个子表，则进行索引查找的平均查找长度为(n/s+s)/2+1。48. 根据n个元素建立一棵二叉排序树的时间复杂度大致为O(nlog2n)49. 在一棵

29、平衡二叉排序树中，每个结点的左子树高度与右子树高度之差的绝对值不超过1_。50. 假定对线性表(38,25,74,52,48)进行哈希存储，采用 H(K)=K % 7作为哈希函数，采用线性探测法处理冲突，则在建立哈希表的过程中，将会碰到5 次存储冲突。51. 对线性表(18,25,63,50,42,32,90)进行哈希存储时，若选用H(K)=K % 9作为哈希函数，则哈希地址为0的元素有3个，哈希地 址为5的元素有 2 个。852. 每次从无序子表中取出一个元素，把它插入到有序子表中的 适当位置，此种排序方法叫做插入 排序;每次从无序子表中挑选 出一个最小或最大元素，把它交换到有序表的一端，此

30、种排序方法叫 做选择排序。53. 每次直接或通过支点元素间接比较两个元素，若出现逆序排 列时就交换它们的位置，此种排序方法叫做快速排序;每次使两个 相邻的有序表合并成一个有序表的排序方法叫做归并_排序。54. 对n个记录进行冒泡排序时，最少的比较次数为口-L，最少的趟数为1。55. 假定一组记录为(46,79,56,38,40,84)，则利用堆排序方法建立 的初始小根堆为(38,40,56,79,46,84) _。56. 假定一组记录为(46,79,56,38,40,84)，(往后冒泡)在冒泡排序 的过程中进行第一趟排序后的结果为(46,56,38,40,79,84)。57. 假定一组记录为(

31、46,79,56,38,40,80)，对其进行快速排序的第一次划分后的结果为40 38。58. 假定一组记录为(46,79,56,38,40,80,46,75,28,46)，对其进行归并排序的过程中，第三趟归并后的第2个子表为28 46。59. 在所有排序方法中，堆排序 方法使数据的组织采用 的是完全二叉树的结构。60. 直接选择_排序方法能够每次从无序表中顺序查找出一个最 小值。三，算法设计与应用题1，设计将带表头的链表逆置算法。设单循环链表的头指针为head，类型为LinkList。逆置时需将每 一个结点的指针域作以修改，使其原前趋结点成为后继。如要更改q 结点的指针域时，设s指向其原前趋

32、结点，p指向其原后继结点，则 只需进行q-next=s;操作即可，算法描述如下：void invert(LinkList *head)( 逆置head指针所指向的单循环链表linklist *p, *q, *s;q=head;p=head-next;while (p!=head) 当表不为空时，逐个结点逆置( s=q;q=p;p=p-next;q-next=s;p-next=q;2，已知用一维数组存放的一棵完全二叉树：ABCDEFGHIJKL，写出 该二叉树的先序、中序和后序遍历序列。先序序列：ABDHIEJKCFLG中序序列：HDIBJEKALFCG后序序列：HIDJKEBLFGCA3,给出

33、如图A所示的森林的先根、后根遍历结点序列，然后画出该 森林对应的二叉树。先根遍历 ABCDEFGHIJKLMNO后根遍历：BDEFCAHJIGKNOML森林转换成二叉树如图B所示。4. 给定一棵用二叉链表表示的二叉树，其中的指针t指向根结点，试 写出从根开始，按层次遍历二叉树的算法，同层的结点按从左至右的 次序访问。考虑用一个顺序队que来保存遍历过程中的各个结点，由于二叉 树以二叉链表存储，所以可设que为一个指向数据类型为bitree的指 针数组，最大容量为maxnum，下标从1开始，同层结点从左到右存放。算法中的front为队头指针，rear为队尾指针。levelorder (BiTre

34、e *t) 按层次遍历二叉树 t( BiTree *quemaxnum;int rear,front;if (t!=NULL)( front=0; 置空队列rear=1;que1=t;do( front=front%maxsize+1; 出队t=quefront;printf(t-data);if (t-lchild!=NULL) 左子树的根结点入队( rear=rear%maxsize+1;querear=t-lchild;if (t-rchild!=NULL) 右子树的根结点入队( rear=rear%maxsize+1;querear=t-rchild;while (rear= =fro

35、nt); 队列为空时结束5. 已知一个无向图的邻接表如图C所示，试写出从顶点0出发分别 进行深度优先和广度优先搜索遍历得到的顶点序列。要求画出无向图。深度优先搜索序列：0,3,6,4,1,5,2广度优先搜索序列：0,3,2,6,5,4,16. 假定一个待哈希存储的线性表为 (32,75,29,63,48,94,25,36,18,70,49,80)，哈希地址空间为 HT12，若采 用除留余数法构造哈希函数和拉链法处理冲突，试画出最后得到的哈 希表，并求出平均查找长度。H(K)=K % 11,哈希表如图7-5所示，平均查找长度17/12299418324670487563257.已知一组记录为(46,74,53,14,26,38,86,65,27,34)，给出采用快速排序法进行排序时每一趟的排序结果。3.(0)467453142638866527 34(1)342738142646866553 74262714343846746553 86142627343846536574 86(4)142627343846536574 864.