精选-数据结构总复习题(JAVA).doc

一、填空题1. 栈和队列的共同特点是（只允许在端点处插入和删除元素）。2. 在深度为5的满二叉树中，叶子结点的个数为（31）3. 算法分析的目的是（分析算法的效率以求改进）。4. 由两个栈共享一个存储空间的好处是（节省存储空间，降低上溢发生的机率）。5.串的长度是（串中所含字符的个数） 。6.设有两个串p和q，求q在p中首次出现位置的运算称做（模式匹配）7. N个顶点的连通图中边的条数至少为（N-1）。8.N个顶点的强连通图的边数至少有（N）。9.对长度为n的线性表进行顺序查找，在最坏情况下所需要的比较次数为（N）。P25910.假设线性表的长度为n，则在最坏情况下，冒泡排序需要的比较次数为（n(n-1)/2） 。P29211. 在n个结点的单链表中要删除已知结点*p，需找到它的前驱结点的地址，其时间复杂度为O（n）。12. 在具有n个单元的循环队列中，队满时共有 n-1 个元素。13. 有向图G用邻接表矩阵存储，其第i行的所有元素之和等于顶点i的 出度 。14. 用Dijkstra算法求某一顶点到其余各顶点间的最短路径是按路径长度 递增 的次序来得到最短路径的。15. 在图形结构中，每个结点的前驱结点数和后续结点数可以 任意多个 。16在一个循环队列中，队首指针指向队首元素的 前一个 位置。17在顺序表中插入或删除一个元素，需要平均移动 表中一半元素，具体移动的元素个数与 表长和该元素在表中的位置 有关。18. 线性表中结点的集合是 有限 的，结点间的关系是 一对一 的。19.数据结构被形式地定义为（D, R），其中D是 数据元素 的有限集合，R是D上的 关系 有限集合。20. 线性结构中元素之间存在一对一关系，树形结构中元素之间存在一对多关系，图形结构中元素之间存在多对多关系。21. 一个算法的效率可分为 时间 效率和 空间 效率。22. 在顺序表中访问任意一结点的时间复杂度均为 O(1) ，因此，顺序表也称为 随机存取 的数据结构。23. 在n个结点的单链表中要删除已知结点*p，需找到它的前驱结点的地址，其时间复杂度为O（n）。24. 在具有n个单元的循环队列中，队满时共有 n-1 个元素。25. 对于栈只能在 栈顶 插入和删除元素；对于队列只能在 队尾 插入和 队首 删除元素。26. 一棵深度为6的满二叉树有 n1+n2=0+ n2= n0-1=31 个分支结点和 26-1 =32 个叶子。27. 有向图G用邻接表矩阵存储，其第i行的所有元素之和等于顶点i的 出度 。27. 用Dijkstra算法求某一顶点到其余各顶点间的最短路径是按路径长度 递增 的次序来得到最短路径的。29. n个顶点e条边的图，若采用邻接矩阵存储，则空间复杂度为 O(n2) 。二、单项选择题1. 线性表L（a1,a2,a3,ai,an），下列说法正确的是（） A.每个元素都有一个直接前件和直接后件 B.线性表中至少要有一个元素C.表中诸元素的排列顺序必须是由小到大或由大到小D.除第一个和最后一个元素外，其余每个元素都有一个且只有一个直接前趋和直接后继（ A ）2. 算法分析的两个主要方面是：A) 空间复杂性和时间复杂性 B) 正确性和简明性C) 可读性和文档性 D) 数据复杂性和程序复杂性（ A ）3.判定一个队列QU（最多元素为m0）为满队列的条件是 QU-front = = (QU-rear+1)% m0 QU-rear QU-front 1= = m0 QU-front = = QU-rear QU-front = = QU-rear+1（ B ）4 线性表在 情况下适用于使用链式结构实现。.需经常修改中的结点值 .需不断对进行删除插入 .中含有大量的结点 .中结点结构复杂5. 从供选择的答案中，选出应填入下面叙述 ？ 内的最确切的解答，把相应编号写在答卷的对应栏内。设有4个数据元素a1、a2、a3和a4，对他们分别进行栈操作或队操作。在进栈或进队操作时，按a1、a2、a3、a4次序每次进入一个元素。假设栈或队的初始状态都是空。现要进行的栈操作是进栈两次，出栈一次，再进栈两次，出栈一次；这时，第一次出栈得到的元素是 A ，第二次出栈得到的元素是 B 是；类似地，考虑对这四个数据元素进行的队操作是进队两次，出队一次，再进队两次，出队一次；这时，第一次出队得到的元素是 C ，第二次出队得到的元素是 D 。经操作后，最后在栈中或队中的元素还有 E 个。供选择的答案：AD：a1 a2 a3 a4E： 1 2 3 0答案：A=（） B=（ ） C= （ ） D（ ） E=（） （ B ）6. 有8个结点的无向图最多有 条边。 A14 B. 28 C. 56 D. 112 7从供选择的答案中，选出应填入下面叙述 内的最确切的解答，把相应编号写在答卷的对应栏内。栈是一种线性表，它的特点是 A 。设用一维数组A1,n来表示一个栈，An为栈底，用整型变量T指示当前栈顶位置，AT为栈顶元素。往栈中推入（PUSH）一个新元素时，变量T的值 B ；从栈中弹出（POP）一个元素时，变量T的值 C 。设栈空时，有输入序列a，b，c，经过PUSH，POP，PUSH，PUSH，POP操作后，从栈中弹出的元素的序列是 D ，变量T的值是 E 。供选择的答案：A： 先进先出 后进先出 进优于出 出优于进 随机进出B，C： 加1 减1 不变 清0 加2 减2D： a,b b,c c,ab,a c,b a,cE： n+1 n+2 n n-1 n-2答案：A=（） B=（） C= （ ） D（） E=（）（ C ）6. 算法分析的目的是：A) 找出数据结构的合理性 B) 研究算法中的输入和输出的关系C) 分析算法的效率以求改进 D) 分析算法的易懂性和文档性（ A ）7. 在n个结点的顺序表中，算法的时间复杂度是O（1）的操作是：（A） 访问第i个结点（1in）和求第i个结点的直接前驱（2in） （B） 在第i个结点后插入一个新结点（1in）（C） 删除第i个结点（1in）（D） 将n个结点从小到大排序（ C ）8.若已知一个栈的入栈序列是1，2，3，n，其输出序列为p1，p2，p3，pn，若p1=n，则pi为i n=i n-i+1 不确定（ A ）9.判定一个队列QU（最多元素为m0）为满队列的条件是 QU-front = = (QU-rear+1)% m0 QU-rear QU-front 1= = m0 QU-front = = QU-rear QU-front = = QU-rear+1（ C ）10. 具有n(n0)个结点的完全二叉树的深度为 。() log2(n) () log2(n) () log2(n) +1 () log2(n)+111.从供选择的答案中，选出应填入下面叙述 内的最确切的解答，把相应编号写在答卷的对应栏内。二叉树 A 。在完全的二叉树中，若一个结点没有 B ，则它必定是叶结点。每棵树都能惟一地转换成与它对应的二叉树。由树转换成的二叉树里，一个结点N的左子女是N在原树里对应结点的 C ，而N的右子女是它在原树里对应结点的 D 。供选择的答案A： 是特殊的树 不是树的特殊形式 是两棵树的总称 有是只有二个根结点的树形结构 B: 左子结点 右子结点 左子结点或者没有右子结点 兄弟CD： 最左子结点 最右子结点 最邻近的右兄弟 最邻近的左兄弟 最左的兄弟 最右的兄弟答案：A=（） B=（ ） C= （ ） D（ ） （ B ）12. 在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的 倍。 A1/2 B. 1 C. 2 D. 4 13从供选择的答案中，选出应填入下面叙述 内的最确切的解答，把相应编号写在答卷的对应栏内。栈是一种线性表，它的特点是 A 。设用一维数组A1,n来表示一个栈，An为栈底，用整型变量T指示当前栈顶位置，AT为栈顶元素。往栈中推入（PUSH）一个新元素时，变量T的值 B ；从栈中弹出（POP）一个元素时，变量T的值 C 。设栈空时，有输入序列a，b，c，经过PUSH，POP，PUSH，PUSH，POP操作后，从栈中弹出的元素的序列是 D ，变量T的值是 E 。供选择的答案：A： 先进先出 后进先出 进优于出 出优于进 随机进出B，C： 加1 减1 不变 清0 加2 减2D： a,b b,c c,ab,a c,b a,cE： n+1 n+2 n n-1 n-2答案：A=（） B=（） C= （ ） D（） E=（）三、判断题（ ）1. 链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动地将后续的各个单元向前移动。（ ）2. 链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动地将后续的各个单元向前移动。（ ）3. 栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。（ ）4. 栈和队列的存储方式既可是顺序方式，也可是链接方式。（ ）5. 若二叉树用二叉链表作存贮结构，则在n个结点的二叉树链表中只有n1个非空指针域。（ ）6.二叉树中每个结点的两棵子树的高度差等于1。 （ ）7. 图的深度优先遍历序列是惟一的。（ ）8用普里姆(Prim)算法求具有n个顶点e条边的图的最小生成树的时间复杂度为 O(n2) ；（ ）9在线性结构中，每个结点有且只有 1个前驱结点和1个后续结点。（ ）10. 数据的运算最常用的有5种，它们分别是插入 、 删除、修改、 查找 、排序。（ ）11. 链表的每个结点中都恰好包含一个指针。 （ ）12. 顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。 （ ）13. 栈和队列都是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。（ ）14. 栈和队列的存储方式既可是顺序方式，也可是链接方式。（ ）15. 若二叉树用二叉链表作存贮结构，则在n个结点的二叉树链表中只有n1个空指针域。（ ）16.平衡二叉树中每个结点的两棵子树的高度差等于1。 （ ）17. 图的深度优先遍历序列不是惟一的。（ ）18用普里姆(Prim)算法求具有n个顶点e条边的图的最小生成树的时间复杂度为 O(n2) ；（ ）19.对于一棵非空二叉树，它的根结点作为第一层，则它的第i层上最多能有2i1个结点。（ ）20. 数据的运算最常用的有5种，它们分别是插入 、 删除、修改、 查找 、排序。四、简单应用题1、 用二元组表示的数据结构如下，画出其逻辑图表示，并指出其属于何种结构。DS= D=a,b,c,d,e,f,g,h,S=R,R=,解答：abcdefgh它是一种线性结构。2设s1=”There is a books on the desk.”,s2=”note”,则Insert(s1,12,s2)和Delete(s1,11,6)的结果分别是什么？Insert(s1,12,s2)的结果为s1=”There is a notebooks on the desk.”Delete(s1,11,6)的结果为s1=”There is a oks on the desk.”3.已知一棵二叉树的先序遍历的序列为STUWV，中序遍历的序列为UWTVS，则其后序遍历的序列是什么？解答：WUVTS4有一段电文“CASTTATASA” （“”代表空格），根据每个字符的频度构造其哈夫曼（Huffman）树，给每个字符进行哈夫曼编码。解答：C 000 S 001 T 01 10 A 115设有一组关键字19,1,23,14,55,20,84,27,68,11,10,77,采用散列函数：H(key)=key%13采用开放地址法的线性探测再散列方法解决冲突，试在018的散列地址空间中对该关键字序列构造散列表。解答：0123456789101112131415161718114552768192084231110776.采用二叉链表作为二叉树的存储结构，写出求二叉树中叶子结点个数并打印出叶子结点的算法。/求叶子结点的个数并打印出叶子结点int LeafCount(BTNode *p)if(!p) return 0;else if(!p-lchild &!p-rchild ) Print(p-data );return 1;else return LeafCount(p-lchild )+LeafCount(p-rchild );7.假设图用邻接矩阵表示,设计一个算法,判定从顶点vi到顶点vj是否可达。int visitedMAXVEX;void connected(AdjMaxix adj,int i,int j,int &c)int k;if(i=j) c=1;elsek=0;c=0;while(kadj.n & c=0)if(adj.edgesik=1 & visitedk=0)visitedk=1;connected(adj,k,j,c);elsek+;8.写出实现折半查找的算法或程序代码。/折半查找template int BinarySearch(StaticTable &R, const KeyType key)int low = 0,high = R.m_size - 1; /low表示所查区间的下界，high表示所查区间的上界while(low key) high = mid-1; /在前半区间继续查找else low = mid +1; /在后半区间继续查找return -1; /查找失败9.用二元组表示的数据结构如下，画出其逻辑图表示，并指出其属于何种结构。DS= D=a,b,c,d,e,f ,S=R1,R2,R1=,R2=,解答：(树略)它是一种树性结构。10描述34，28，81，79，22进行简单排序的过程。初始 第一趟 第二趟第三趟 第四趟34 32 22 22 2228 28 28 28 2881 81 81 34 3479 79 79 79 7922 34 34 81 8111.已知一棵二叉树的后序遍历的序列为WUVTS，中序遍历的序列为UWTVS，则其先序遍历的序列是什么？解答：STUWV12有一段电文“BESTTETESE” （“”代表空格），根据每个字符的频度构造其哈夫曼（Huffman）树，给每个字符进行哈夫曼编码。解答：B 000 S 001 T 01 10 E 1114对给定的数列R=7，16，4，8，20，9，6，18，5构造一棵二叉排序树，并给出按中序遍历得到的数列R1。解答：4，5，6，7，8，9，16，18，2014.采用二叉链表作为二叉树的存储结构，写出求二叉树中结点总个数的算法。/求二叉树结点的个数int Count(BTNode *p)if(!p) return 0;elsereturn Count(p-lchild)+Count(p-rchild )+1;15.假设图用邻接矩阵表示,设计一个算法,判定从顶点vi到顶点vj是否存在路径。int visitedMAXVEX;void connected(AdjMaxix adj,int i,int j,int &c)int k;if(i=j) c=1;elsek=0;c=0;while(kadj.n & c=0)if(adj.edgesik=1 & visitedk=0)visitedk=1;connected(adj,k,j,c);elsek+;16.写出实现折半插入排序的算法或程序代码。/折半插入排序templatevoid BInsertSort(ElemType data, int n) ElemType tmp;int i, j, mid, low, high; for (i = 1; i n; i+) tmp = datai; / 保存待插入的元素 low = 0; high = i-1; while (low = high) / 在datalow.high中折半查找有序插入的位置 mid = (low + high) / 2; / 折半 if( tmp = low; j-) dataj + 1 = dataj; / 元素后移 datalow = tmp; / 插入到正确位置 17将一个字符串逆置。void change(char str,int n) int i;char temp; for(i=0;in/2;i+) temp=stri;stri=strn-1-i;strn-1-i=temp; （注：专业文档是经验性极强的领域，无法思考和涵盖全面，素材和资料部分来自网络，供参考。可复制、编制，期待你的好评与关注）