数据结构期末练习题

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

2、5,则栈的不可能的输出序列是（C ）A 54321 B 45321 C 43512 D 12345此题的解决步骤是如果出现一个三元素顺序是a、b、c,且a>c>b,则为不可能序列7. 常对数组进行的两种基本操作是（B ）A.建立和删除B.索引和修改C.插入和彳改D.插入和索引8. 算法分析的两个主要方面是（A ）。A空间性能和时间性能B正确性和简明性C可读性和文档性D数据复杂性和 程序复杂性9. 在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印缓冲区，该缓冲区应该是一个（B ）结构。需满足先进先出原则A栈B队列C数组D线性表10. 二维数组A的每个元素是由6个字符组成的

3、用，行下标的范围从 08,列下 标的范围是从09,则存放A至少需要（D ）个字节。A 90 B 180 C 240 D 54011. 讨论树、森林和二叉树的关系，目的是为了（ B ）。A借助二叉树上的运算方法去实现对树的一些运算B将树、森林按二叉树的存储方式进行存储并利用二叉树的算法解决树的有关问题C将树、森林转换成二叉树D体现一种技巧，没有什么实际意义12. 算法在发生非法操作时可以作出处理的特性称为（ A ）。A健壮性 B 确定性 C 可行性 D 正确性13. 二叉排序树中，最小值结点的（A ）。A左指针一定为空B右指针一定为空C左、右指针均为空D左、右指针均 不为空14. 算法指的是（A

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

5、t=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的一下个节点赋值给 s18. 若一个栈的输入序列是1,2, 3,，n,输出序列的第一个元素是n,则第 i 个输出元素是（ D ） 。A 不确定 B n-i C n-i-1D n-i+119. 设有两个用p和q,求q在p

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

7、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的初始状态为空，元素 el、e2、e3、e4、e5、e6依次通过栈 S， 一个元素出栈后即进入队列Q， 若 6 个元素出队的顺序是e2、 e4、 e3、e6、e5、el,则栈S的容量至少应该是（C ）。A 6 B 4 C 3 D 230. 二维数组 A 的每个元素是由 6 个字符组成的串，行下标的范围从08，列下标的范围是从09, A 的第 8 列和第 5 行共占（ C ）个字节。A 114 B 54C 108 D 54031. 在一棵树中，每个结点最多有（

9、 B ） 个前驱结点。A 0 B 1 C 2 D 任意多个32. 一个队列的入队顺序是1， 2， 3， 4，则队列的输出顺序是（B ） 。A 4321 B 1234 C 1432 D 324133. 下面的说法中，不正确的是（ C ） 。A 数组是一种线性结构 B 数组是一种定长的线性结构C 除了插入与删除操作外，数组的基本操作还有存取、修改、检索和排序等D 数组的基本操作有存取、修改、检索和排序等，没有插入与删除操作34. 队列的操作原则是（ B ） 。A 先进后出 B 先进先出 C 只能进行插入 D 只能进行删除35. 如果结点A有3个兄弟，B是A的双亲，则结点B的度是（D ）。A 1 B

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

11、表的顺序存储结构是一种（A ）的存储结构。A随机存取B 顺序存取C索引存取D 散列存取41. 假设有如下遗产继承规则：丈夫和妻子可以相互继承遗产；子女可以继承父亲或母亲的遗产；子女间不能相互继承。则表示该遗产继承关系的最合适的数据结构应该是（B ）。A树 B图C 线性表 D 集合42. 数组通常具有两种基本运算，即（B ）A.创建和删除B.读取和修改C.插入和删除D.排序和查找43. 线性表采用链接存储时，其地址（D ）0A必须是连续的B部分地址必须是连续的 C 一定是不连续的D连续与否均可以44. 下面（C ）不属于特殊矩阵。A对角矩阵 B 三角矩阵 C稀疏矩阵E 对称矩阵45. 线性表的第

12、一个元素叫做（A ）。A.表头元素B.表尾元素C前驱元素D.后继元素46. 线性表的最后一个元素叫做（B ）。A.表头元素B.表尾元素C前驱元素D.后继元素47. 设二叉树有n个结点，则其深度为（C ）。A n-1 B nC log2n 向下取整+1 D 不能确定当深度（高度）为h时，结点数n满足：2h 1 n 2h,可知h 1 log 2 n h,所以其深度h为log 2 n向下取整+148. G是一个非连通无向图，共有28条边，则该图至少有（D ）个顶点。A 6 B 7 C 8D 9取出一个点作为一个无向图，其余点作为另一个无向图，则其点连线最多,使用的点最少，C；28n（n2 1）28

13、n 8,共需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 稀疏矩阵 D 对称矩阵54. 一个队列的入队顺序是1， 2， 3， 4，则队列的输出顺序是（B ） 。A 4321 B 1234 C 14

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

15、组 C .数组和用D.树和队列61. 关于空串与空格串，下面说法正确的是（ C ） 。A.空用与空格用是相同的B.空用与空格用长度是相同的C.空格用中存放的都是空格D.空用中存放的都是NULL62. 递归可采用下面哪种结构实现（ B ） / 栈实现了递归A.队列 B.栈 C.树 D.图63. 栈操作的原则是( B )A.先进先出B.后进先出C.只能进行才S入D.只能进行删除64. 在关键字序列 (4, 12, 23, 55, 56， 67， 88) 中，使用折半查找法查找56，需要比较多少次( C )A. 1B.2C.3D.465. 如果一个函数在其函数体中调用自己本身，则该函数叫做( B )

16、 。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+100log 2n+12O(n3)(2) 5+n2+n!O( n! )(3) 10+20n+2nO( 2n )2. 有三个元素按a、 b、 c 的次序依次进栈，且每个元素只允许进一次栈，列出所有可能的出栈序列。 abc,acb,bca,bac,cba3 .栈S=(a, b, c),在栈中插入1个元素d,再从栈中删除一个元素，请写出 S 的变化过程。S=(a,b,c,d)-> S=(a,b,c)4 .队列Q=(a, b, c)

18、,在队列中插入1个元素d,再从队列中删除一个元素，请写出Q的变化过程。Q=(a,b,c,d)-> Q=(b,c,d)5 .假设下图是一棵二叉树，请根据下图回答下列问题哪个是根结点？ A哪些是叶子结点？ DEG哪个是结点C的双亲？ A哪些是结点C的孩子？ EFC的兄弟是哪个结点？BF的堂兄弟是哪个结点？D哪些结点是C的子孙结点？ EFG树的深度是多少？ 4请写出该树的先根遍历序列、中根序列、后根序列、层次遍历序列树的度是多少？2先序：ABDCEFG 中序：BDAECGF 后序：DBEGFCA 层序：ABCDEFG6 .分别用prim算法和kruskal算法构造下图的最小生成树。7 .若对序

19、列(56, 23, 67, 4, 88, 12, 55)采用直接插入排序法和冒泡排序法进行排序，请写出每一趟的结果。直接插入排序法：(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,23,12,55,56,67,88)(4,12,23,55,56,67,88)8. 写出利用线性表求集

20、合交集、并集和差集的算法(1) 求并集1 初始化集合A、 B、 CA=new List() ; B=new List() ; C=new List() ;输入集合 A 的数据元素输入集合B 的数据元素逐个取出集合A 中的数据元素，放入2 for(i=0;i<n;i+) A.insert(e); /for(i=0;i<m;i+) B.insert(e); /3 for(i=0;i<A.size();i+)/到集合 C 中 e=A.get(i); C.insert(e); 4 个取出集合 B 中的元素，判断该元素是否已存在集合 C 中4.1 该元素如果不在集合 C 中，则将其放入

21、集合C 中4.2 该元素如果已在集合C中，则重复第4步for(i=0;i<B.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;i<n;i+) A.insert(e); /输入集合 A 的数据元素for(i=0;i<m;i+) B.insert(e); /输入集合B 的数据元素3、逐个取出集合B 中的元素，判

22、断该元素是否已存在集合C 中3.1 该元素如果在集合A 中，则将其放入集合C 中3.2 该元素如果不在集合 A 中，则重复第3 步for(i=0;i<B.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;i<n;i+)A.insert(e); / 输入集合 A 的数据元素for(i=0;i<m;i+)B.in

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

24、fer s=new StringBuffer(sc.next();2. 定义一个变量char ch;定义一个变量int i;3. 加密过程对字符串中每个字符的 ASCII 值+1for(i=0;i<s.length();i+) ch=s.charAt(i);ch=(char)(int)(ch)+1);s.setCharAt(i,ch);4. 输出加密之后的结果System.out.println(" 加密之后的字符串是:"+s);5. 解密过程对加密串中每个字符的 ASCII 值执行 -1 操作for(i=0;i<s.length();i+) ch=s.char

25、At(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<Integer> s=new SeqStack<Integer>();2. 从键盘获取非负的十进制整数 System.out.println(" 请输入要转换的十进制正数： ");Scanner sc=new Scan

26、ner(System.in); m=sc.nextInt();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()

27、!=true) i=s.pop(); if(n=16) if(i=10) System.out.print('A'+"");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'+"

28、");else if(i=15) System.out.print('F'+""); else System.out.print(i+"");else System.out.print(i+"");System.out.println();11. 写出利用栈和队列，判断一个字符串是否是回文串的算法。1. 取出字符串中的一个字符，分别入栈和入队列。boolean pal(String str)for(i=0;i<str.length();i+)ch=str.charAt(i);S.push(ch); Q.

29、add(ch);2. 重复第 1 步，直到字符串结束。3. 栈顶元素出栈，队头元素出队列，两者比较是否相等3.1 如果不相等，则该字符串不是回文串3.2 如果相等，重复第3 步，直到栈为空或者队列为空。while(S.isEmpty()=false)ch1=S.pop(); ch2=Q.poll();if(ch1!=ch2) return false;4. 如果栈为空或者队列为空，则该字符串是回文串。if(S.isEmpty()=true) return true;12. 写出求 n! 的递归算法。int fun(int n)if(n=1|n=0)return 1;elsereturn n*f

30、un(n-1);13. 写出求 2 个正整数 m*n 的递归算法。int mul(int m,int n)if(m=0|n=0)return 0;else if(m=1)return n;else return n+mul(m-1,n);14. 写出递归算法求数组中最大值、最小值和平均值。求数组中的最大值1. 定义递归函数int max(int A, int n)2. 判断 n 是否为 12.1 若 n 为 1 则返回结果A0 跳转至 32.2 若 n 不为 1 则执行递归体并跳转至2if(n=1) return A0;elsereturn (max(A,n-1)>An-1?max(A,

31、n-1):An-1);3. 结束算法求数组中的最小值4. 定义递归函数int min(int A, int n)5. 判断 n 是否为 15.1 若 n 为 1 则返回结果A0 跳转至 35.2 若 n 不为 1 则执行递归体并跳转至2if(n=1) return A0; elsereturn (min(A,n-1)<An-1?min(A,n-1):An-1);6. 结束算法求数组平均值7. 定义递归函数double avg(int A,int n)8. 判断 n 是否为 18.1 若 n 为 1 则返回结果A0 跳转至 38.2 若 n 不为 1 则执行递归体并跳转至2if(n=1)

32、return A0;else return (An-1+avg(A,n-1)*(n-1)/n);9. 结束算法15. 写出判断字符串是否是回文串的递归算法。1. 定义递归函数boolean palindrome(StringBuffer s)2. 判断 s 的长度是否为 0 或为 12.1 若 s 的长度为 0 或为 1 则返回结果true 并跳转至 32.2 若 s 的头尾不相等则返回 false 并跳转至 32.3 若 s 的头尾相等则判断原来的字符串去掉头尾字符之后剩余的部分并跳转至 2if(s.length()=0 | s.length()=1 )return true;elseif(

33、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(s.isEmpty() return s;3. 将字符串头尾字符交换；并交换字符串去掉头尾字符之后的字串后跳转至 2。return rever

34、seString(s.substring(1)+s.charAt(0);4. 结束算法并输出 s三问答题1. 什么是数据结构？数据的结构指的是数据元素之间存在的关系，一个数据结构是由n (n>0)个数据元素组成的有限集合，数据元素之间具有某种特定的关系。数据结构概念包括三个方面：数据的逻辑结构、数据的存储结构和对数据的操作。2. 什么是逻辑结构？数据的逻辑结构分为几类？数据的逻辑结构就是来表示数据之间的逻辑关系的。逻辑结构有四种基本类型：集合结构、线性结构、树状结构和图状结构3. 什么是存储结构？数据的存储结构有哪些？数据的逻辑结构在计算机中的表示。 主要分顺序存储结构和链式存储结构两种

35、。4. 顺序存储结构和链式存储结构的优缺点？顺序表中的数据元素是如何存储的？链表中的数据元素是如何存储的？在什么情况下使用顺序表和链表比较好？链式存储结构:(1) 占用额外的空间以存储指针( 浪费空间 )(2) 存取某个元素速度慢(3) 插入元素和删除元素速度快(4) 没有空间限制 , 存储元素的个数无上限, 基本只与内存空间大小有关.顺序存储结构:(5) 空间利用率高(6) 存取某个元素速度快(7) 插入元素和删除元素存在元素移动 , 速度慢 , 耗时(8) 有空间限制 , 当需要存取的元素个数可能多于顺序表的元素个数时, 会出现"溢出 " 问题 . 当元素个数远少于预先

36、分配的空间时, 空间浪费巨大.顺序存储占用物理地址连续的一块空间来存储元素， 元素之间的关系就是相邻元素间的关系； 链式存储占用的物理地址可连续可不连续， 所以要找到某个元素的后继必须用指针来指示。以查找为主用顺序表，以插入为主用链表。5. 什么是算法？算法的五大特性是什么？怎么描述算法？1. 有穷性，算法是执行时候运行的有穷性，程序只是一段实现算法的代码2. 确定性，算法对于特定的输入有特定的输出，程序提供了确定算法结果的平台3. 可行性，算法需要考虑设计的可能，程序则具体是实现算法上的设计4. 输入，算法有输入，算法的输入依靠程序的平台提供5. 输出，算法的输出也靠代码的支持。可以用伪代码，用自然语言也可以描述算法的方法有多种，