数据结构期末练习题(共17页)

1、精选优质文档-倾情为你奉上专心-专注-专业1. 数据的不可分割的基本单位是 (A)。A元素B结点C数据类型D数据项2. 计算机处理数据的最小单位是（D） 。A元素B结点C数据类型D数据项3. 算法是指 (C)。A计算方法B排序方法C解决问题的有限运算步骤D查找方法4. 顺序存储结构中数据元素之间的逻辑关系是由（ C ）表示的A 线性结构B 非线性结构C 存储位置D 指针5. 单循环链表的主要优点是（ B ） 。A 不再需要头指针了B 从表中任一结点出发都能扫描到整个链表；C 已知某个结点的位置后，能够容易找到它的直接前趋；D 在进行插入、删除操作时，能更好地保证链表不断开。6. 一个栈的入栈序

2、列是 1，2，3，4，5，则栈的不可能的输出序列是( C )。A 54321B 45321C 43512D 123457. 常对数组进行的两种基本操作是(B)A建立和删除B 索引和修改C插入和修改D插入和索引8. 算法分析的两个主要方面是（ A ） 。A 空间性能和时间性能 B 正确性和简明性 C 可读性和文档性 D 数据复杂性和程序复杂性9. 在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印缓冲区， 该缓冲区应该是一个（ B ）结构。/需满足先进先出原则A 栈B 队列C 数组D 线性表10. 二维数组 A 的每个元素是由 6 个字符组成的串，行下标的范围从 08，列下标的范围是从

3、 09，则存放 A 至少需要（ D ）个字节。A 90B 180C 240D 54011. 讨论树、森林和二叉树的关系，目的是为了（B） 。此题的解决步骤是如果出现一个三元素顺序是a、b、c，且acb,则为不可能序列精选优质文档-倾情为你奉上专心-专注-专业A 借助二叉树上的运算方法去实现对树的一些运算B 将树、 森林按二叉树的存储方式进行存储并利用二叉树的算法解决树的有关问题C 将树、森林转换成二叉树D 体现一种技巧，没有什么实际意义12. 算法在发生非法操作时可以作出处理的特性称为（ A ） 。A 健壮性B 确定性C 可行性D 正确性13. 二叉排序树中，最小值结点的（ A ） 。A 左指

4、针一定为空B 右指针一定为空C 左、右指针均为空D 左、右指针均不为空14. 算法指的是（ A ） 。A 对特定问题求解步骤的一种描述，是指令的有限序列。B 计算机程序C 解决问题的计算方法D 数据处理15. 算法分析的目的是(C)。A找出数据结构的合理性B研究算法中输入和输出的关系C分析算法的效率以求改进D分析算法的易读性和文档性16. 若某线性表中最常用的操作是取第 i 个元素和找第 i 个元素的前趋， 则采用（ A ）存储方法最节省时间。A 顺序表B 单链表C 双链表D 单循环链表17. 在一个单链表中，已知 q 所指结点是 p 所指结点的直接前驱，若在 q 和 p 之间插入 s 所指结

5、点，则执行（ B ）操作。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;(1)s-next=p-next;(2)p-next=s;(3)s=p-next;分别代表什么含义？1) 把 p 的下一个节点接到 s 的下一个节点上2) 把 s 接到 p 的下一个节点上3) 把 p 的一下个节点赋值给 s精选优质文档-倾情为你奉上专心-专注-专业18. 若一个栈的输入序列是 1，2，3，n，输出序列的第一个元素是 n，则第i 个输出元素是（ D ） 。A 不确定B

6、 n-iC n-i-1D n-i+119. 设有两个串 p 和 q，求 q 在 p 中首次出现的位置的运算称作（ B ） 。A 连接B 模式匹配C 求子串D 求串长20. 将数组称为随机存取结构是因为（ B ） 。A 数组元素是随机的B 对数组任一元素的存取时间是相等的C 随时可以对数组进行访问D 数组的存储结构是不定的21. 一个高度为 h 的满二叉树共有 n 个结点，其中有 m 个叶子结点，则有（ D ）成立。A n=h+mB h+m=2nC m=h-1D n=2m-122. 队列的操作原则是（ B ） 。A 先进后出B先进先出C 只能进行插入D 只能进行删除23. 散列技术中的冲突指的是

7、（ D ） 。A 两个元素具有相同的序号B 两个元素的键值不同，而其他属性相同C 数据元素过多D 不同键值的元素对应于相同的存储地址24. 在栈中，栈顶指针 top 指示 ( B )。A栈底元素的位置B栈顶元素的位置C栈中任何元素的位置D以上均不对25. 将数组称为随机存取结构是因为（ B ） 。A 数组元素是随机的B 对数组任一元素的存取时间是相等的C 随时可以对数组进行访问D 数组的存储结构是不定的26. 下面（ C ）不是算法所必须具备的特性。A 有穷性B 确切性C 高效性D 可行性27. 在一棵树中， （ B ）没有后继结点。A 根结点B 叶子结点C 分支结点D 所有结点28. 若链表

8、中最常用的操作是在最后一个结点之后插入一个结点和删除第一个结点，则采用（ D ）存储方法最节省时间。A 单链表B 带头指针的单循环链表C 双链表D 带尾指针的单循环链表精选优质文档-倾情为你奉上专心-专注-专业29. 设栈 S 和队列 Q 的初始状态为空，元素 e1、e2、e3、e4、e5、e6 依次通过栈 S， 一个元素出栈后即进入队列 Q， 若 6 个元素出队的顺序是 e2、 e4、 e3、e6、e5、e1，则栈 S 的容量至少应该是（ C ） 。A 6B 4C 3D 230. 二维数组 A 的每个元素是由 6 个字符组成的串，行下标的范围从 08，列下标的范围是从 09, A 的第 8

9、列和第 5 行共占（ C ）个字节。A 114B 54C 108D 54031. 在一棵树中，每个结点最多有 ( B ) 个前驱结点。A0B1C2D任意多个32. 一个队列的入队顺序是 1，2，3，4，则队列的输出顺序是（ B ） 。A 4321B 1234C 1432D 324133. 下面的说法中，不正确的是（ C ） 。A 数组是一种线性结构B 数组是一种定长的线性结构C 除了插入与删除操作外，数组的基本操作还有存取、修改、检索和排序等D 数组的基本操作有存取、修改、检索和排序等，没有插入与删除操作34. 队列的操作原则是( B )。A 先进后出B 先进先出C 只能进行插入D 只能进行删

10、除35. 如果结点 A 有 3 个兄弟，B 是 A 的双亲，则结点 B 的度是（ D ） 。A 1B 2C 3D 436. 静态查找与动态查找的根本区别在于（ B ） 。A 它们的逻辑结构不一样B 施加在其上的操作不同C 所包含的数据元素的类型不一样D 存储实现不一样37. 在一个具有 n 个单元的顺序栈中，假定以地址低端（即下标为 0 的单元）作为栈底，以 top 作为栈顶指针，当出栈时，top 的变化为（ B ） 。A 不变B top=top-1C top=0D top=top+138. 算法是指（ C ）A计算方法B排序方法C解决问题的有限运算步骤D查找方法39. 算法能正确地实现预定功

11、能的特性称为 ( A ) 。A 正确性B 易读性C 健壮D 高效率精选优质文档-倾情为你奉上专心-专注-专业40. 线性表的顺序存储结构是一种（ A ）的存储结构。A 随机存取B 顺序存取C 索引存取D 散列存取41. 假设有如下遗产继承规则：丈夫和妻子可以相互继承遗产；子女可以继承父亲或母亲的遗产；子女间不能相互继承。 则表示该遗产继承关系的最合适的数据结构应该是（ B ） 。A 树B 图C 线性表D 集合42. 数组通常具有两种基本运算，即（ B ）A创建和删除B读取和修改C插入和删除D排序和查找43. 线性表采用链接存储时，其地址（ D ） 。A 必须是连续的B 部分地址必须是连续的 C

12、 一定是不连续的D 连续与否均可以44. 下面（ C ）不属于特殊矩阵。A 对角矩阵B 三角矩阵C 稀疏矩阵E 对称矩阵45. 线性表的第一个元素叫做（A） 。A表头元素B表尾元素C前驱元素D后继元素46. 线性表的最后一个元素叫做（ B ） 。A表头元素B表尾元素C前驱元素D后继元素47. 设二叉树有 n 个结点，则其深度为（ C ） 。A n-1B nC log2n 向下取整+1D 不能确定当深度（高度）为 h 时，结点数 n 满足：hhn221,可知hnh2log1，所以其深度 h 为n2log向下取整+148. G 是一个非连通无向图，共有 28 条边，则该图至少有（ D ）个顶点。A

13、 6B 7C 8D 9取出一个点作为一个无向图，其余点作为另一个无向图，则其点连线最多，使用的点最少，8282)1(282nnnCn，共需 9 个点49. 在以下哪种情况下，不能执行出栈操作？（ B ）精选优质文档-倾情为你奉上专心-专注-专业A栈满B栈空C任何情况均可D任何情况均不可50. 下列数据结构中， （ D ）不是线性结构。A栈B队列C数组D树51. 栈又称为（ B ）表。A 先进先出B 后进先出D 不进不出D 以上均不对52. 在以下哪种情况下，不能执行入栈操作？（ A ）A栈满B栈空C任何情况均可D任何情况均不可53. 下面（ C ）不属于特殊矩阵。A 对角矩阵B三角矩阵C 稀疏

14、矩阵D 对称矩阵54. 一个队列的入队顺序是 1，2，3，4，则队列的输出顺序是（ B ） 。A4321B 1234C1432D324155. 在一棵树中，每个结点最多有（ B ）个前驱结点。A0B 1C 2D 任意多个56. 非空树有（ B ）个根结点。A 0B1C2D 任意多个57. 串是一种特殊的线性表，其特殊性体现在 ( B )A可以顺序存储B数据元素是一个字符C可以链接存储D数据元素可以是多个字符58. 在以下哪种情况下，不能执行出栈操作？( B )A栈满B栈空C任何情况均可D任何情况均不可59. 数组中的数据元素的类型（ A ） 。A必须相同B不必相同C一定不能相同D以上都不对60

15、. 下列数据结构中，( D )不都是线性结构。A栈和队列B队列和数组C数组和串D树和队列61. 关于空串与空格串，下面说法正确的是( C )。A空串与空格串是相同的B空串与空格串长度是相同的C空格串中存放的都是空格D空串中存放的都是 NULL62. 递归可采用下面哪种结构实现（ B ）/栈实现了递归A队列B栈C树D图精选优质文档-倾情为你奉上专心-专注-专业63. 栈操作的原则是( B )A先进先出B后进先出C只能进行插入D只能进行删除64. 在关键字序列(4, 12, 23, 55, 56，67，88)中，使用折半查找法查找 56，需要比较多少次（ C ）A. 1B.2C.3D.465. 如

16、果一个函数在其函数体中调用自己本身，则该函数叫做 ( B )。A重载函数B递归函数C普通函数D成员函数66. 线性表若采用链式存储结构时，要求内存中可用存储单元的地址 ( D )A必须是连续的B部分地址必须是连续的C一定是不连续的D连续或不连续都可以67. 设计一个判别表达式中左右括号是否配对的算法，采用（ B ）数据结构最佳。A 顺序表B 栈C 队列D 链表68. 下面的说法中，不正确的是（ D ） 。A 对称矩阵只须存放包括主对角线元素在内的下（或上）三角的元素即可。B 对角矩阵只须存放非零元素即可。C 稀疏矩阵中值为零的元素较多，因此可以采用三元组表方法存储。D 稀疏矩阵中大量值为零的元

17、素分布有规律，因此可以采用三元组表方法存储。69. 按（ B ）遍历二叉排序树得到的序列是一个有序序列。A 前序B 中序C 后序D 层次二应用题1. 计算下列式子的时间复杂度。(1) 2n3+100log2n+12)(3nO(2) 5+n2+n!)!(nO(3) 10+20n+2n)2(nO2. 有三个元素按 a、b、c 的次序依次进栈，且每个元素只允许进一次栈，列出所有可能的出栈序列。abc,acb,bca,bac,cba精选优质文档-倾情为你奉上专心-专注-专业3. 栈 S=(a，b，c)，在栈中插入 1 个元素 d，再从栈中删除一个元素，请写出 S的变化过程。S=(a,b,c,d)- S

18、=(a,b,c)4. 队列 Q=(a，b，c)，在队列中插入 1 个元素 d，再从队列中删除一个元素，请写出 Q 的变化过程。Q=(a,b,c,d)- Q=(b,c,d)5. 假设下图是一棵二叉树，请根据下图回答下列问题1哪个是根结点?A2哪些是叶子结点?DEG3哪个是结点 C 的双亲?A4哪些是结点 C 的孩子?EF5C 的兄弟是哪个结点？ B6F 的堂兄弟是哪个结点？D7哪些结点是 C 的子孙结点？ EFG8树的深度是多少?49树的度是多少？210请写出该树的先根遍历序列、中根序列、后根序列、层次遍历序列。先序：ABDCEFG中序：BDAECGF后序：DBEGFCA层序：ABCDEFG6.

19、 分别用 prim 算法和 kruskal 算法构造下图的最小生成树。7. 若对序列(56，23，67，4，88，12，55)采用直接插入排序法和冒泡排序法ABCGFED精选优质文档-倾情为你奉上专心-专注-专业进行排序，请写出每一趟的结果。直接插入排序法：（23,56）67,4,88,12,55（23,56,67）4,88,12,55（4,23,56,67）88,12,55（4,23,56,67,88）12,55（4,12,23,56,67,88）55（4,12,23,55,56,67,88）冒泡排序法:(23,56,4,67,12,55,88)(23,4,56,12,55,67,88)(4

20、,23,12,55,56,67,88)(4,12,23,55,56,67,88)8.写出利用线性表求集合交集、并集和差集的算法(1) 求并集1 初始化集合 A、B、CA=new List() ; B=new List() ; C=new List() ;2 for(i=0;in;i+)A.insert(e);/输入集合 A 的数据元素for(i=0;im;i+)B.insert(e);/输入集合 B 的数据元素3 for(i=0;iA.size();i+)/逐个取出集合 A 中的数据元素，放入到集合C 中e=A.get(i); C.insert(e);4 个取出集合 B 中的元素，判断该元素是

21、否已存在集合 C 中4.1 该元素如果不在集合 C 中，则将其放入集合 C 中4.2 该元素如果已在集合 C 中，则重复第 4 步for(i=0;iB.size();i+)e=B.get(i);if(A.contains(e)=false)C.insert(e);5 出集合 C 中的所有数据元素C.toString();(2) 求交集1、初始化集合 A、B、CA=new List() ; B=new List() ; C=new List() ;2、for(i=0;in;i+)A.insert(e);/输入集合 A 的数据元素精选优质文档-倾情为你奉上专心-专注-专业for(i=0;im;i+

22、)B.insert(e);/输入集合 B 的数据元素3、逐个取出集合 B 中的元素，判断该元素是否已存在集合 C 中3.1 该元素如果在集合 A 中，则将其放入集合 C 中3.2 该元素如果不在集合 A 中，则重复第 3 步for(i=0;iB.size();i+)e=B.get(i);if(A.contains(e)=true)C.insert(e);4、/输出集合 C 中的所有数据元素C.toString();(3) 求差集1、初始化集合 A、B、CA=new List() ;B=new List() ;C=new List() ;2、for(i=0;in;i+)A.insert(e);/

23、输入集合 A 的数据元素for(i=0;im;i+)B.insert(e);/输入集合 B 的数据元素3、逐个取出集合 A 中的元素，判断该元素是否已存在集合 B 中4.1 该元素如果不在集合 B 中，则将其放入集合 C 中4.2 该元素如果已在集合 B 中，则重复第 4 步for(i=0;iA.size();i+)e=A.get(i);if(B.contains(e)=false)C.insert(e);4、/输出集合 C 中的所有数据元素C.toString();9. 写出对字符串中的字符 ASCII 值进行运算来进行加密和解密的算法。1.从键盘中输入并初始化字符串Scanner sc=n

24、ew Scanner(System.in);StringBuffer s=new StringBuffer(sc.next();2. 定义一个变量 char ch;定义一个变量 int i;3. 加密过程对字符串中每个字符的 ASCII 值+1for(i=0;is.length();i+)ch=s.charAt(i);ch=(char)(int)(ch)+1);精选优质文档-倾情为你奉上专心-专注-专业s.setCharAt(i,ch);4.输出加密之后的结果System.out.println(加密之后的字符串是:+s);5.解密过程对加密串中每个字符的 ASCII 值执行-1 操作for(

25、i=0;is.length();i+)ch=s.charAt(i);ch=(char)(int)(ch)-1);s.setCharAt(i,ch);6.输出加密之后的结果System.out.println(解密之后的字符串是:+s);10. 写出利用栈，将非负的十进制整数 M 转化为基于 N 的 N 进制数的算法。1.定义变量int m,n,e,i;定义栈SeqStack s=new SeqStack();2.从键盘获取非负的十进制整数System.out.println(请输入要转换的十进制正数 ：);Scanner sc=new Scanner(System.in);m=sc.nextI

26、nt();3.获取转化为基于 N 的 N 进制数System.out.println(请输入要转换的数制：);n=sc.nextInt();4.用 M 除 N，得到商数和余数，将余数放入栈中；当商数不为 0，继续用商数除 N，得到新的商数和余数，余数入栈。当商数为 0，循环结束。while(m!=0)e=m%n;s.push(e);m=m/n;5.输出转化结果，若 N 为 16 时则按照如下规则输出结果System.out.println(转化结果为：);while(s.isEmpty()!=true)i=s.pop();if(n=16)if(i=10) System.out.print(A+

27、);else if(i=11) System.out.print(B+);精选优质文档-倾情为你奉上专心-专注-专业else if(i=12) System.out.print(C+);else if(i=13) System.out.print(D+);else if(i=14) System.out.print(E+);else if(i=15) System.out.print(F+);else System.out.print(i+);elseSystem.out.print(i+);System.out.println();11. 写出利用栈和队列，判断一个字符串是否是回文串的算法。

28、1.取出字符串中的一个字符，分别入栈和入队列。boolean pal(String str)for(i=0;iAn-1?max(A,n-1):An-1);3.结束算法求数组中的最小值1.定义递归函数int min(int A, int n)2.判断 n 是否为 12.1 若 n 为 1 则返回结果 A0跳转至 32.2 若 n 不为 1 则执行递归体并跳转至 2if(n=1) return A0;elsereturn (min(A,n-1)An-1?min(A,n-1):An-1);3.结束算法求数组平均值1.定义递归函数double avg(int A,int n)2.判断 n 是否为 12

29、.1 若 n 为 1 则返回结果 A0跳转至 32.2 若 n 不为 1 则执行递归体并跳转至 2if(n=1) return A0;else return (An-1+avg(A,n-1)*(n-1)/n);3.结束算法15. 写出判断字符串是否是回文串的递归算法。1.定义递归函数booleanpalindrome(StringBuffer s)精选优质文档-倾情为你奉上专心-专注-专业2.判断 s 的长度是否为 0 或为 12.1 若 s 的长度为 0 或为 1 则返回结果 true 并跳转至 32.2 若 s 的头尾不相等则返回 false 并跳转至 32.3 若 s 的头尾相等则判断原

30、来的字符串去掉头尾字符之后剩余的部分并跳转至 2if(s.length()=0 | s.length()=1 )return true;elseif(s.charAt(0)!=s.charAt(s.length()-1)return false;elsereturnpalindrome(newStringBuffer(s.substring(1,s.length()-1);3.结束算法输出字符串是否为回文串16. 写出实现字符串的逆转操作的递归算法。1.定义递归函数String reverseString(String s)2.判断字符串是否为空串，或者字符串中只有一个字符,若是跳转至 4if

31、(s.isEmpty() return s;3. 将字符串头尾字符交换；并交换字符串去掉头尾字符之后的字串后跳转至 2。return reverseString(s.substring(1)+s.charAt(0);4.结束算法并输出 s三问答题1. 什么是数据结构？数据的结构指的是数据元素之间存在的关系，一个数据结构是由 n（n0）个数据元素组成的有限集合，数据元素之间具有某种特定的关系。数据结构概念包括三个方面：数据的逻辑结构、数据的存储结构和对数据的操作。2. 什么是逻辑结构？数据的逻辑结构分为几类？数据的逻辑结构就是来表示数据之间的逻辑关系的。逻辑结构有四种基本类型：集合结构、线性结构

32、、树状结构和图状结构精选优质文档-倾情为你奉上专心-专注-专业3. 什么是存储结构？数据的存储结构有哪些？数据的逻辑结构在计算机中的表示。主要分顺序存储结构和链式存储结构两种。4. 顺序存储结构和链式存储结构的优缺点？顺序表中的数据元素是如何存储的？链表中的数据元素是如何存储的？在什么情况下使用顺序表和链表比较好？链式存储结构:(1)占用额外的空间以存储指针(浪费空间)(2)存取某个元素速度慢(3)插入元素和删除元素速度快(4)没有空间限制,存储元素的个数无上限,基本只与内存空间大小有关.顺序存储结构:(1)空间利用率高(2)存取某个元素速度快(3)插入元素和删除元素存在元素移动,速度慢,耗时

33、(4)有空间限制,当需要存取的元素个数可能多于顺序表的元素个数时,会出现溢出问题.当元素个数远少于预先分配的空间时,空间浪费巨大.顺序存储占用物理地址连续的一块空间来存储元素， 元素之间的关系就是相邻元素间的关系；链式存储占用的物理地址可连续可不连续，所以要找到某个元素的后继必须用指针来指示。以查找为主用顺序表，以插入为主用链表。5. 什么是算法？算法的五大特性是什么？怎么描述算法？1.有穷性，算法是执行时候运行的有穷性，程序只是一段实现算法的代码2.确定性，算法对于特定的输入有特定的输出，程序提供了确定算法结果的平台3.可行性，算法需要考虑设计的可能，程序则具体是实现算法上的设计4.输入，算法有输入，算法的输入依靠程序的平台提供5.输出，算法的输出也靠代码的支持。可以用伪代码，用自然语言也可以描述算法的方法有多种，常用的有自然语言、结构化流程图、伪代码和 PAD图等，其中最普遍的是流程图。6. 栈是什么？请描述栈的操作特性，并画图说明。栈是一种特殊的线性表，其插入和删除操作只