数据结构复习题

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

2、个结点有两两个指针域，一一个指向前驱驱结点，另一一个指向后继继结点。数据结构通常包包括四种基本本结构：集合合、线性结构构、树形结构、图图形结构、线线性表线性表（a1 ,a2.an）k , aa1 称表头元素， an称表尾元素，线线性表有两种种存储结构：顺序存储结结构 和 链式存储结结构。在一个顺序存储储的线性表中中，第1个元元素的地址是是100，每每个元素的长长度为2，则则第5个元素素的地址是1108。在线性结构中，第第一个结点没没有前驱结点点，其余每个个结点有且只只有1个前驱结点点；最后一个个结点没有后续结点点，其余每个个结点有且只只有1个后续结点点。二、选择题具有6个顶点的的无向图至少少应

3、有A条边边才能确保是是一个连通图图。A、d B.cc C.b D.e2、在初始状态态为空的堆栈栈中依次插入入元素f,ee,d,c,a,b后，连连续进行了三三次删除操作作，则此时的的栈顶元素是是DA、5 BB、6 C、7 D、83、后序遍历的的顺序是DA、根结点，左左子树，右子子树 B、左子树树，根结点，右右子树C、右子树，根根结点，左子子树 DD、左子树，右右子树，根结结点4、设结点X有有左孩子结点点Y，右孩子子结点Z，用用三种基本遍遍历方法得到到的遍历序列列中X （B） 是Y的前驱，X（B）是Z的后继，Y（A）是Z的前驱。A、一定， B、不一一定 CC、一定不5、串是指BA、少于一个字字母的

4、序列 BB、有限个字字符的序列 C、不不少于一个字字符的序列 D、任意意个字母的序序列6、一个栈的输输入序列为11，2，3，44， 则下列列序列中不可可能是栈的输输出序列的是是 CA、2，3，44，1，5 B、22，3，1，44，5 C、5，44，1，2，33 D、11，5，4，33，27、如果结点AA有3个兄弟弟，且B是AA的双亲，则则B的度是AAA、4 BB、5 C、1 D、38、通常对数组组进行的两种种基本操作是是CA、插入和删除除 B、索索引和修改 C、查查找和修改 D、删删除和修改9、一个队列的的入队序列是是1，2，33，4，则队队列的输出序序列是BA、4，3，22，1 BB、1，2

5、，33，4 C、1，44，3，2 D、33，2 ，44 ，1计算机算法必须须具备输入、输输出和B等五五个基本特性性A、可行性、可可移植性、和和可扩充性BB、可行性、确确定性和可穷穷性C、确定定性、可穷必必和稳定性DD、易读性、稳稳定性和安全全性11、树最适合合用来表示CCA、有序数据元元素B、无序序数据元素CC、元素之间间具有分支层层次关系的数数据D、元素素之间无联系系的数据12、排序方法法中，从未排排序序列中依依次取出元素素与已排序序序列（初始时时为空）中的的元素进行比比较，将其放放入已排序的的正确位置上上的方法，称称为：（C）A、希尔排序BB、起泡排序序C、插入排排序D、选择择排序13、N

6、个顶点点的强连通图图至少有 （A） 条边HA、N B、N+11 C、N-11 D、NN（N-1）H14、栈通常采采用的两种存存储结构是（AA）A、顺序存储结结构和链表存存储结构B、散散列方式和索索引方式C、链链表存储结构构和数组D、线线性存储结构构和非线性存存储结构15、深度为44的二叉树至至多有（D）个个结点A、8 B、166 C、7 D、11516、对线性表表进行二分查查找时，要求求线性表必须须（C）A、以顺序方式式存储B、以以链接方式存存储C、以顺顺序方式，且且结点按关键键字有序排序序D、以链接接方式存储，且且结点按关键键字有序排序序17、线性表的的顺序存储结结构是一种（AA）的存储结结

7、构、A、随机存取BB、顺序存取取C、索引存存取D、散列列存取18、串是一种种特殊的线性性表，其特殊殊性体现在（BB）A、可以顺序存存储B、数据据元素是一个个字符C、可可以链接存储储D、数据元元素可以是多多个字符19、任何一个个无向连通图图的最小生成成树有BA、只有一棵BB、有一棵或或多棵C、一一定有多棵DD、可能不存存在20、在一棵非非空二叉树的的中序遍历序序列中，根结结点的右边AA只有右子树上的的所有结点BB、只有右子子树上的部分分结点C、只只有左子树上上的部分结点点D、只有左左子树上的所所有结点、三、试分别按先先根遍历，中中根遍历，后后根遍历法写写出二叉树的的遍历序列CEIGFJBAD先根

8、序列：ABBDHIEJJCFGCEIGFJBAD中根序列：HDDIBEJAAFCGH后根序列：HIIDJEBFFGCAH 四、画出含有三三个结点的二二叉树的所有有形态。五、给出图中每每个顶点的入入度，出度和和顶点的度41415 顶点 入度 出度度 度5 22 1 36 22 2 4623 11 3 423 33 0 3 22 3 5 1 2 3六、用Dijkkstra算算法求图中VV1到其余各各顶点的最短短路径1 8 13 最最短路径 长度123 V11 V2 1323 322 7 VV1 V3 874 5 30 7 V1 V4(经V3) 1374 V1 V5(经经V3,V44) 1965 6

9、6 17 9 V1 VV6(经V33,V4,VV5) 21165 2 V1 V7(经经V2) 20七、已知无向图图，试给出：1.从A出发的的“深度优先”遍历序列2.从A出发的的“广度优先”遍历序列3.该图是连通通图吗？答：ABDCCEGFABCDEEFG是EBEBAGDAGDFCFC八、对照图未的的树回答下列列问题CACAB BEDHGFEDHGFLKJNILKJNIMM1.树中哪些是是叶结点？哪哪个是根结点点？答：叶结点D M N FF J K L；根结点点：A2.结点C的双双亲结点是哪哪一个？A3.结点C的孩孩子有哪些？F G HH4.哪些是G的的兄弟？F、HHC的深度是多多少？3树的深度

10、是多多少？5E的子孙哪些些？I M N九、用krusskal算法法求图的最小小生成树。21 144 2136 1 200 9 236 21 11 6 7 54 54 116 22213 22133 1 11 1 66 23455511 11 455511122 12241 9 22 14 22 414365365 1 6 1 9 64365365十、对于给定的的一组权W=14，115，7，44，20，113，5，88，10，试试画出一棵哈哈夫曼树，并并算出带权路路径长度WPPL答：WPL=2292 1010573996202730199151514135487573996202730199151514135487十一、用Priim算法求图图的最小生成成树2151155216452 114 14 1442151155216452 2 3 1 20 9 1 1 11 2233