《数据结构》复习题(doc9页)(正式)

1、ZH 计 0520 九州 0520数据结构复习一、填空题：1、 空用的长度是0,空格串的长度是串中包含的容格的个数。2、 队列是一种先进先出表、在队列中允许插入的一端称队尾也许删除的另一端称队头。3、 两串相等是指两个字符串的长度相等，且各对应位置上的字符相等。4、 组成数据的最小单位是数据项。5、 线性结构中元素之间存在一对一的关系、树形结构中元素之间存在一对多的关系、图形结构中元素之间存在多对多的关系。6、 向栈中压入元素的操作是：先移动栈顶指针，后存入元素。7、 栈的逻辑结构是线性结构，其特点是后进先出，先进后出，栈中允许插入和删除的一端称栈顶。8、 在双向链表中，每个结点有两个指针域，

2、一个指向前驱结点，另一个指向后继结点。9、 数据结构通常包括四种基本结构：集合、线性结构、树形结构、图形结构、线性表10、 线性表(ai ,攵.金)k , ai称表头元素,小称表尾元素,线性表有两种存储结构：顺序存储结构和链式存储结构。11、 在一个顺序存储的线性表中，第1个元素的地址是100,每个元素的长度为2,则第5个元素的地址是108。12、 在线性结构中，第一个结点没有前驱结点、其余每个结点有且只有1个前驱结点；最后一个结点没有后续结点,其余每个结点有且只有1个后续结点。二、选择题1、 具有6个顶点的无向图至少应有 A条边才能确保是一个连通图。A、dB.c C.b D.e2、在初始状态

3、为空的堆栈中依次插入元素 f,e,d,c,a,b后，连续进行了三次删除操作，则此时的 栈顶元素是DA、5 B、6 C、7 D、83、后序遍历的顺序是DA、根结点，左子树，右子树B、左子树，根结点，右子树C、右子树，根结点，左子树 D、左子树，右子树，根结点4、设结点X有左孩子结点Y,右孩子结点乙用三种基本遍历方法得到的遍历序列中 X (由 是Y的前驱，X (B)是Z的后继，Y (A)是Z的前驱。A、一定，B、不一定 C、一定不5、用是指BA、少于一个字母的序列B、有限个字符的序列C、不少于一个字符的序列D、任意个字母的序列6、一个栈的输入序列为1, 2, 3, 4,则下列序列中不可能是栈的输出

4、序列的是 C A、2,3,4,1, 5B、2,3, 1, 4, 5C、5, 4, 1,2,3D、1, 5, 4,3,27、如果结点A有3个兄弟，且B是A的双亲，则B的度是AA、4 B、5 C、1D、38、通常对数组进行的两种基本操作是 CA、插入和删除 B、索引和修改 C、查找和修改D、删除和修改9、一个队列的入队序列是1, 2, 3, 4,则队列的输出序列是BA、4, 3, 2, 1 B、1, 2, 3, 4 C、1, 4, 3, 2D、3, 2 , 4 , 110、计算机算法必须具备输入、输出和 B等五个基本特性A、可行性、可移植性、和可扩充性 B、可行性、确定性和可穷性 C、确定性、可穷

5、必和稳定性D、易读性、稳定性和安全性11、树最适合用来表示CA、有序数据元素B、无序数据元素C、元素之间具有分支层次关系的数据 D、元素之间无联系 的数据12、排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比 较，将其放入已排序的正确位置上的方法，称为： eA、希尔排序B、起泡排序C、插入排序D、选择排序13、N个顶点的强连通图至少有（A）条边A、NB、N+1 C、N-1 D、N （N-1）14、栈通常采用的两种存储结构是（A）A、顺序存储结构和链表存储结构 B、散列方式和索引方式C、链表存储结构和数组D、线性存 储结构和非线性存储结构15、深度为4的二叉树至多有

6、（D）个结点A、8B、16C、7 D、15 16、对线性表进行二分查找时，要求线性表必须（C）A、以顺序方式存储B、以链接方式存储C、以顺序方式，且结点按关键字有序排序 D、以链接 方式存储，且结点按关键字有序排序17、线性表的顺序存储结构是一种（A）的存储结构、A、随机存取B、顺序存取C、索引存取D、散列存取 18、申是一种特殊的线性表，其特殊性体现在（B）A、可以顺序存储B、数据元素是一个字符C、可以链接存储D、数据元素可以是多个字符19、任何一个无向连通图的最小生成树有 BA、只有一棵B、有一棵或多棵C、一定有多棵D、可能不存在 20、在一棵非空二叉树的中序遍历序列中，根结点的右边 AA

7、、只有右子树上的所有结点B、只有右子树上的部分结点 C、只有左子树上的部分FH的所有结点、卜艮遍历法写出二叉树的遍历序列先根序列：ABDHIEJCFG中根序歹U: HDIBEJAFCG后根序歹U: HIDJEBFGCA四、画出含有三个结点的村的所有形态。五、给出图中每出度和颂点的度顶点入度出度度 213 224 134 303 235 123六、用 Dijkstra算法求图中V1到其余各顶点的最短路径最短路径长度V1 V2 13V1 V3 8V1 一V4（经 V3） 13V1V5（经 V3,V4） 19V1*V6（经 V3,V4,V5） 21V1V7（经 V2）20七、已知无向图，试给出:1 .从A出发的“深度优先”遍历序列2 .从A出发的“广度优先”遍历序列3 .该图是连通图吗？答： ABDCEGFABCDEFG是答：叶结点D M N F J K L ;根结点：A2 .结点C的双亲结点是哪一个？ A3 .结点C的孩子有哪些？ F G H4 .哪些是G的兄弟？ F、HC的深度是多少？ 3树的深度是多少？ 5E的子孙哪些？ IM N九、用kruskal算法求图的最小生成树。1；OqJ© Or16° q A 9 ( 1>116o ©2 (O QZ X-> Cp14- /A (X) d <D Aa GT