数据结构期末练习题.doc

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 在进行插入、删除操作时，能更好地保证链表不断开。 此题的解决步骤是如果出现一个三元素顺序是a、b、c，且acb,则为不可能序列6. 一个栈的入栈序列是1，2，3，4，5，则栈的不可能的输出序列是( C )。 A 54321 B 45321 C 43512 D 12345 7. 常对数组进行的两种基本操作是( B )A建立和删除B 索引和修改C插入和修改D插入和索引8. 算法分析的两个主要方面是（ A ）。A空间性能和时间性能 B正确性和简明性 C 可读性和文档性 D 数据复杂性和程序复杂性 9. 在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印缓冲区， 该缓冲区应该是一个（ B ）结构。 /需满足先进先出原则A 栈 B 队列 C 数组 D 线性表 10. 二维数组A的每个元素是由6个字符组成的串，行下标的范围从08，列下标的范围是从09，则存放A至少需要（ D ）个字节。 A 90 B 180 C 240 D 540 11. 讨论树、森林和二叉树的关系，目的是为了（ B ）。 A 借助二叉树上的运算方法去实现对树的一些运算 B 将树、森林按二叉树的存储方式进行存储并利用二叉树的算法解决树的有关问题 C 将树、森林转换成二叉树 D 体现一种技巧，没有什么实际意义 12. 算法在发生非法操作时可以作出处理的特性称为（ A ）。 A 健壮性 B 确定性 C 可行性 D 正确性 13. 二叉排序树中，最小值结点的（ A ）。 A 左指针一定为空 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所指结点，则执行（ 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的一下个节点赋值给s18. 若一个栈的输入序列是1，2，3，n，输出序列的第一个元素是n，则第i个输出元素是（ D ）。 A 不确定 B n-i C n-i-1 D n-i+1 19. 设有两个串p和q，求q在p中首次出现的位置的运算称作（ 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-1 D n=2m-1 22. 队列的操作原则是（ B ）。A 先进后出 B先进先出 C 只能进行插入 D 只能进行删除23. 散列技术中的冲突指的是（ 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. 若链表中最常用的操作是在最后一个结点之后插入一个结点和删除第一个结点，则采用（ 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 6 B 4 C 3 D 2 30. 二维数组A的每个元素是由6个字符组成的串，行下标的范围从08，列下标的范围是从09, A的第8列和第5行共占（ C ）个字节。 A 114 B 54 C 108 D 540 31. 在一棵树中，每个结点最多有 ( B ) 个前驱结点。A0 B1 C2 D任意多个32. 一个队列的入队顺序是1，2，3，4，则队列的输出顺序是（ B ）。 A 4321 B 1234 C 1432 D 3241 33. 下面的说法中，不正确的是（ C ）。 A 数组是一种线性结构 B 数组是一种定长的线性结构 C 除了插入与删除操作外，数组的基本操作还有存取、修改、检索和排序等 D 数组的基本操作有存取、修改、检索和排序等，没有插入与删除操作 34. 队列的操作原则是( B )。A 先进后出 B 先进先出 C 只能进行插入 D 只能进行删除35. 如果结点A有3个兄弟，B是A的双亲，则结点B的度是（ D ）。 A 1 B 2 C 3 D 4 36. 静态查找与动态查找的根本区别在于（ B ）。 A 它们的逻辑结构不一样 B 施加在其上的操作不同 C 所包含的数据元素的类型不一样 D 存储实现不一样 37. 在一个具有n个单元的顺序栈中，假定以地址低端（即下标为0的单元）作为栈底，以top作为栈顶指针，当出栈时，top的变化为（ B ）。 A 不变 B top=top-1 C top=0 D top=top+1 38. 算法是指（ C ）A计算方法 B排序方法 C解决问题的有限运算步骤 D查找方法39. 算法能正确地实现预定功能的特性称为 ( 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 一定是不连续的 D 连续与否均可以 44. 下面（ C ）不属于特殊矩阵。 A 对角矩阵 B 三角矩阵 C 稀疏矩阵 E 对称矩阵 45. 线性表的第一个元素叫做（ A ）。A表头元素B表尾元素C前驱元素D后继元素46. 线性表的最后一个元素叫做（ B ）。A表头元素B表尾元素C前驱元素D后继元素47. 设二叉树有n个结点，则其深度为（ C ）。 A n-1 B n C log2n向下取整+1 D 不能确定 当深度（高度）为h时，结点数n满足：,可知，所以其深度h为向下取整+148. G是一个非连通无向图，共有28条边，则该图至少有（ D ）个顶点。 A 6 B 7 C 8 D 9 取出一个点作为一个无向图，其余点作为另一个无向图，则其点连线最多，使用的点最少，共需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 ）。 A4321 B 1234 C1432 D3241 55. 在一棵树中，每个结点最多有（ B ）个前驱结点。A 0 B 1 C 2 D 任意多个56. 非空树有（ B ）个根结点。A 0 B1C2D 任意多个57. 串是一种特殊的线性表，其特殊性体现在 ( B )A可以顺序存储B数据元素是一个字符C可以链接存储D数据元素可以是多个字符58. 在以下哪种情况下，不能执行出栈操作？( B )A栈满B栈空C任何情况均可D任何情况均不可59. 数组中的数据元素的类型（ A ）。A必须相同B不必相同C一定不能相同D以上都不对60. 下列数据结构中，( 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. 如果一个函数在其函数体中调用自己本身，则该函数叫做 ( B )。A重载函数B递归函数C普通函数D成员函数66. 线性表若采用链式存储结构时，要求内存中可用存储单元的地址 ( D )A必须是连续的 B部分地址必须是连续的C一定是不连续的 D连续或不连续都可以67. 设计一个判别表达式中左右括号是否配对的算法，采用（ B ）数据结构最佳。 A 顺序表 B 栈 C 队列 D 链表 68. 下面的说法中，不正确的是（ D ）。 A 对称矩阵只须存放包括主对角线元素在内的下（或上）三角的元素即可。 B 对角矩阵只须存放非零元素即可。 C 稀疏矩阵中值为零的元素较多，因此可以采用三元组表方法存储。 D 稀疏矩阵中大量值为零的元素分布有规律，因此可以采用三元组表方法存储。 69. 按（ B ）遍历二叉排序树得到的序列是一个有序序列。 A 前序 B 中序 C 后序 D 层次 二应用题1. 计算下列式子的时间复杂度。(1) 2n3+100log2n+12(2) 5+n2+n! (3) 10+20n+2n2. 有三个元素按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)，在队列中插入1个元素d，再从队列中删除一个元素，请写出Q的变化过程。Q=(a,b,c,d)- Q=(b,c,d)5. 假设下图是一棵二叉树，ABCGFED请根据下图回答下列问题 哪个是根结点?A 哪些是叶子结点? DEG 哪个是结点C的双亲? A 哪些是结点C的孩子? EF C的兄弟是哪个结点？B F的堂兄弟是哪个结点？D 哪些结点是C的子孙结点？EFG 树的深度是多少? 4 树的度是多少？2 请写出该树的先根遍历序列、中根序列、后根序列、层次遍历序列。 先序：ABDCEFG中序：BDAECGF后序：DBEGFCA层序：ABCDEFG6. 分别用prim算法和kruskal算法构造下图的最小生成树。7. 若对序列(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. 写出利用线性表求集合交集、并集和差集的算法(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中的元素，判断该元素是否已存在集合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+) 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、C A=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、逐个取出集合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=new 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(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.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()!=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+); 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;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;else return (min(A,n-1)An-1?min(A,n-1):An-1);3.结束算法求数组平均值1.定义递归函数double avg(int A,int n)2.判断n是否为12.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.定义递归函数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;else if(s.charAt(0)!=s.charAt(s.length()-1)return false;else return palindrome(new StringBuffer(s.substring(1,s.length()-1); 3.结束算法输出字符串是否为回文串16. 写出实现字符串的逆转操作的递归算法。1.定义递归函数String reverseString(String s)2.判断字符串是否为空串，或者字符串中只有一个字符,若是跳转至4if(s.isEmpty() return s;3. 将字符串头尾字符交换；并交换字符串去掉头尾字符之后的字串后跳转至2。return reverseString(s.substring(1)+s.charAt(0);4.结束算法并输出s三问答题1. 什么是数据结构？数据的结构指的是数据元素之间存在的关系，一个数据结构是由n（n0）个数据元素组成的有限集合，数据元素之间具有某种特定的关系。数据结构概念包括三个方面：数据的逻辑结构、数据的存储结构和对数据的操作。2. 什么是逻辑结构？数据的逻辑结构分为几类？数据的逻辑结构就是来表示数据之间的逻辑关系的。逻辑结构有四种基本类型：集合结构、线性结构、树状结构和图状结构3. 什么是存储结构？数据的存储结构有哪些？数据的逻辑结构在计算机中的表示。主要分顺序存储结构和链式存储结构两种。4. 顺序存储结构和链式存储结构的优缺点？顺序表中的数据元素是如何存储的？链表中的数据元素是如何存储的？在什么情况下使用顺序表和链表比较好？链式存储结构:(1)占用额外的空间以存储指针(浪费空间) (2)存取某个元素速度慢(3)插入元素和删除元素速度快 (4)没有空间限制,存储元素的个数无上限,基本只与内存空间大小有关. 顺序存储结构: (1)空间利用率高 (2)存取某个元素速度快 (3)插入元素和删除元素存在元素移动,速度慢,耗时 (4)有空间限制,当需要存取的元素个数可能多于顺序表的元素个数时,会出现溢出问题.当元素个数远少于预先分配的空间时,空间浪费巨大.顺序存储占用物理地址连续的一块空间来存储元素，元素之间的关系就是相邻元素间的关系；链式存储占用的物理地址可连续可不连续，所以要找到某个元素的后继必须用指针来指示。以查找为主用顺序表，以插入为主用链表。5. 什么是算法？算法的五大特性是什么？怎么描述算法？1.有穷性，算法是执行时候运行的有穷性，程序只是一段实现算法的代码2.确定性，算法对于特定的输入有特定的输出，程序提供了确定算法结果的平台3.可行性，算法需要考虑设计的可能，程序则具体是实现算法上的设计4.输入，算法有输入，算法的输入依靠程序的平台提供5.输出，算法的输出也靠代码的支持。可以用伪代码，用自然语言也可以描述算法的方法有多种，常用的有自然语言、结构化流程图、伪代码和PAD图等，其中最普遍的是流程图。6. 栈是什么？请描述栈的操作特性，并画图说明。栈是一种特殊的线性表，其插入和删除操作只允许在线性表的一段进行。允许操作的一段称为栈顶，不允许操作的一段称为栈底。操作特性为：后进先出7. 队列是什么？队列的操作特性？队列是一种特殊的线性表，特殊之处在于它只允许在表的前端进行删除操作，而在表的后端进行插入操作。先进先出8. 请阐述栈和队列的异同点。栈是限定只能在表的一端进行插入和删除操作的线性表。队列是限定只能在表的一端进行插入和在另一端进行删除操作的线性表。从数据结构的角度看，它们都是线性结构，即数据元素之间的关系相同。但它们是完全不同的数据类型。除了它们各自的基本操作集不同外，主要区别是对插入和删除操作的限定。栈和队列是在程序设计中被广泛使用的两种线性数据结构，它们的特点在于基本操作的特殊性，栈必须按后进先出的规则进行操作，而队列必须按先进先出的规则进行操作。和线性表相比，它们的插入和删除操作受更多的约束和限定，故又称为限定性的线性表结构。9. 什么是递归？递归的两个基本要素是什么？请阐述递归程序和非递归程序的优缺点。序和非递归程序的优缺点。递归：就是一个函数直接或间接的调用函数本身，这就是递归。递归的两个基本要素：递归体和递归出口。递归程序和非递归程序优缺点递归程序：1.结构清晰过程简洁明了，程序体较小2.堆栈占用内存较大，递归算法的运行效率较低。非递归：1.过程更加有条理 2.程序体较大10. 请阐述线性结构和树状结构的异同点。同：都是逻辑结构异：线性结构是一对一的结构,是最简单的结构.它只有一个没有前驱、只有后继的结点,叫着首结点；只有一个没有后继、只有前驱的结点,叫着尾结点；其余的结点都只有一个直接前驱和一个直接后继.树形结构是一对多的结构,是比较复杂的非线性结构.它只有一个没有前驱、只有后继的结点,叫着根结点；可有多个没有后继、只有前驱的结点,叫着叶子结点；其余的结点都只有一个直接前驱和多个直接后继.11. 二叉树的五种形态？1.0个结点空二叉树2.1个结点，根结点3.由根结点和左子树组成，根的右子树为空4.由根结点和右子树组成，根的左子树为空5.由根结点，左子树右子树组成12. 简述顺序查找算法和折半查找算法的优缺点和各自的适用范围。顺序查找的效率很低，但是对于待查的结构没有任何要求，而且算法非常简单，当待查表中的记录个数较少时，采用顺序查找较好.折半查找法的平均查找长度小，查找速度快，但是它要求表中的记录是有序的，且只能用于顺序存储结构。若表中的记录经常变化，为保持表的有序性，需要不断进行调整，这在一定程度上要降低查找效率。因此，对于不常变动的有序表，采用折半查找是比较理想的。