填空题
(1)数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和运算等的学科。
(2)数据结构被形式地定义为（D,R），其中D是数据元素的有限集合，R是D上的关系有限集合。
(3)数据结构包括数据的逻辑结构、数据的存储结构和数据的运算这三个方面的内容。
(4)数据结构按逻辑结构可分为两大类，它们分别是线性结构和非线性结构。
(5)线性结构中元素之间存在一对一关系，树形结构中元素之间存在一对多关系，图形结构中元素之间存在多对多关系。
(6)在线性结构中，第一个结点没有前驱结点，其余每个结点有且只有1个前驱结点；最后一个结点没有后续结点，其余每个结点有且只有1个后续结点。
(7)在树形结构中，树根结点没有前驱结点，其余每个结点有且只有1个前驱结点；叶子结点没有后续结点，其余每个结点的后续结点数可以任意多个。
(8)在图形结构中，每个结点的前驱结点数和后续结点数可以任意多个。
(9)数据的存储结构可用四种基本的存储方法表示，它们分别是顺序、链式、索引和散列。
(10)数据的运算最常用的有5种，它们分别是插入、删除、修改、查找、排序。
(11)一个算法的效率可分为时间效率和空间效率。
(12)对于给定的n个元素,可以构造出的逻辑结构有集合，线性表，树，图四种。
(13)顺序映象的特点是借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系。非顺序映象的特点是借助是指示元素存储地址的指针表示数据元素之间的逻辑关系。任何一个算法的设计取决于选定逻辑结构，而算法的实现依赖于采用的存储结构。
(14)数据类型是一组___________性质相同的值集合以及定义在这个值集合上的一组操作的总称。
(15)数据对象是___________性质相同的数据元素的集合，是数据的一个子集。
(16)如果操作不改变原逻辑结构的“值”，而只是从中提取某些信息作为运算结果，则称该类运算为型运算。引用
(17)算法的健壮特性是指做为一个好的算法，当输入的数据非法时，也能适当地做出正确反应或进行相应的处理，而不会产生一些莫名其妙的输出结果。
(18)算法分析不是针对实际执行时间的精确的算出算法执行具体时间的分析，而是针对算法中语句的执行次数做出估计，从中得到算法执行时间的信息。
(19)T(n)=O(f(n))，它表示随问题规模n的增大算法的执行时间的增长率和f(n)的增长率相同，称作算法的渐进时间复杂度，简称时间复杂度。
(20)若算法执行时所需要的辅助空间相对于输入数据量而言是个常数，则称这个算法为原地工作，辅助空间为O(1)。
(21)在带有头结点的单链表中L中，第一个元素结点的指针是。L-next
(22)在一个带头节点的单循环链表中，p指向尾结点的直接前驱，则指向头结点的指针head可用p表示为head=。p-next-next
(23)设单链表的结点结构为(data,next)，next为指针域，已知指针px指向单链表中data为x的结点，指针py指向data为y的新结点,若将结点y插入结点x之后，则需要执行以下语句:py-next=px-next;px-next=py。
(24)对于栈操作数据的原则是。后进先出
(25)设以数组A[m]存放循环队列的元素，其头尾指针分别为front和rear，则当前队列中的元素个数为。(rear-front+m)%m
(26)若已知一个栈的入栈序列是1,2,3,4……n，其输出序列为p1,p2,p3,……pn，若p1==n,则pi为。n-i+1
(27)队列是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。
(28)通常程序在调用另一个程序时，都需要使用一个栈来保存被调用程序内分配的局部变量。形式参数的存储空间以及返回地址。
(29)栈下溢是指在___栈空_____时进行出栈操作。
(30)用P表示入栈操作，D表示出栈操作，若元素入栈的顺序为，为了得到出栈顺序，相应的P和D的操作串为_______。PDPPDPDD
(31)在具有n个单元的循环队列中，队满共有n-1个元素。
(32)队列是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。
(33)循环队列的引入，目的是为了克服_______假溢出。
(34)所谓稀疏矩阵指的是_______非零元很少(tm*n)且分布没有规律。
(35)在稀疏矩阵表示所对应的三元组线性表中，每个三元组元素按行为主序，列号为辅序的次序排列。
(36)二位数组Am×n按行优先顺序存储在内存中，元素a00地址为loc(a00),每个元素在内存中占d个字节，元素aij的地址计算公式为loc(aij)=loc(a00)＋(i*n+j)*d。
(37)去除广义表LS=(a1,a2,a3,……，an)中第1个元素，由其余元素构成的广义表称为LS的____表尾_____。
(38)树内个结点的度最大值称为树的度。
(39)一个二叉树第5层节点最多有16个。
(40)已知完全二叉树T的第5层只有7个结点，则该树共有____11____个叶子结点。
(41)在一棵二叉树中，度为零的结点的个数为N0,度为2的结点的个数为N2,则有N0=______N2+1。
(42)假设用于通信的电文由8个字母组成，其频率分别为7,19,2,6,32,3,27,10。设计哈夫曼编码，其中字母的编码长度最大是5位。
(43)一棵具有个结点的完全二叉树，它的深度为。9
(44)图的深度优先遍历序列不是惟一的。
(45)在图中，任何两个结点之间都可能存在关系，因此图的数据元素之间时一种多对多的关系。
(46)在有向图中，以顶点v为终点的边的数目称为v的___入度_____。
(47)一个无向图有n个顶点，e条边，则所以顶点的度数之和为2e。
(48)图有邻接矩阵、邻接表等存储结构，遍历图有深度优先遍历、广度优先遍历等方法。
(49)
(50)有向图G用邻接表矩阵存储，其第i行的所有非零元素之和等于顶点i的。出度
(51)如果n个顶点的图是一个环，则它有棵生成树。n（以任意一顶点为起点，得到n-1条边）
(52)n个顶点e条边的图，若采用邻接矩阵存储，则空间复杂度为。O(n2)
(53)n个顶点e条边的图，若采用邻接表存储，则空间复杂度为。O(n+e)
(54)设有一稀疏图G，则G采用邻接表存储较省空间。
(55)设有一稠密图G，则G采用邻接矩阵存储较省空间。
(56)图的逆邻接表存储结构只适用于有向图。
(57)已知一个图的邻接矩阵表示，删除所有从第i个顶点出发的方法是将邻接矩阵的第i行全部置0。
(58)图的深度优先遍历序列不是惟一的。
(59)n个顶点e条边的图采用邻接矩阵存储，深度优先遍历算法的时间复杂度为O(n2)；若采用邻接表存储时，该算法的时间复杂度为O(n+e)。
(60)n个顶点e条边的图采用邻接矩阵存储，广度优先遍历算法的时间复杂度为O(n2)；若采用邻接表存储，该算法的时间复杂度为O(n+e)。
(61)图的BFS生成树的树高比DFS生成树的树高小或相等。
(62)用普里姆(Prim)算法求具有n个顶点e条边的图的最小生成树的时间复杂度为O(n2)；用克鲁斯卡尔(Kruskal)算法的时间复杂度是O(elog2e)。
(63)若要求一个稀疏图G的最小生成树，最好用克鲁斯卡尔(Kruskal)算法来求解。
(64)若要求一个稠密图G的最小生成树，最好用普里姆(Prim)算法来求解。
(65)用Dijkstra算法求某一顶点到其余各顶点间的最短路径是按路径长度递增的次序来得到最短路径的。
(66)拓扑排序算法是通过重复选择具有0个前驱顶点的过程来完成的。
(67)在各种查找方法中，平均查找长度与结点个数n无关的查找方法是散列查找 。
(68)散列法存储的基本思想是由关键字的值决定数据的存储地址。
(69)大多数排序算法都有两个基本的操作：。比较和移动
(70)由于查找算法的基本运算是关键字之间的比较操作，所以可用平均查找长度来衡量查找算法的性能。
(71)查找有静态查找和动态查找，当查找不成功时动态查找会将查找关键字插入在表中。
(72)顺序查找法中设置监视哨，可以起到防止越界的作用。
(73)假设列表长度为n，那么查找第i个数据元素时需进行n-i+1次比较。
(74)假设查找每个数据元素的概率相等，即Pi=1/n，则顺序查找算法的平均查找长度为：
ASL=(n+1)/2。
(75)折半查找法又称为二分法查找法，这种方法要求待查找的列表必须是按关键字大小有序排列的顺序表。
(76)假定将长度为n的表分成b块，且每块含s个元素，则b=n/s。又假定表中每个元素的查找概率相等，
(77)在有序表(12,24,36,48,60,72,84)中二分查找关键字72时所需进行的关键字比较次数为2。
(78)折半查找有序表（4,6,12,20,28,38,50,70,88,），若查找表中元素20，它将依次与表中元素28，6，12，20比较大小。
(79)在各种查找方法中，平均查找长度与结点个数n无关的查找方法是散列查找。
(80)散列法存储的基本思想是由关键字的值决定数据的存储地址。
(81)当关键字集合很大时，关键字值不同的元素可能会映象到哈希表的同一地址上，即k1≠k2，但H（k1）=H（k2），这种现象称为冲突.
(82)产生冲突现象的两个关键字称为该散列函数的____同义词________。
(83)在散列函数H(key)=keyMODp中，p应取素数。
(84)设哈希表长m=14,哈希函数H(key)=keyMOD11.表中已有4个结点；addr(15)=4,addr(38)=5,addr(61)=6,addr(84)=7,其余地址为空。如用二次探测再散列处理冲突，关键字为49的结点的地址是。9
(85)希尔排序是属于插入排序的改进方法。
(86)给出一组关键字T＝（20,4,34,5,16,33,18,29,2,40,7），要求从下到大进行排序，试给出快速排序（选一个记录为枢纽）第一趟排序结果。7,4,2,85,16,18,20,,29,33,40,34
(87)大多数排序算法都有两个基本的操作：比较和移动。
(88)在对一组记录（54,38,96,23,15,72,60,45,83）进行直接插入排序时，当把第7个记录60插入到有序表时，为寻找插入位置至少需比较次。6。
(89)在插入和选择排序中，若初始数据基本正序，则选用插入；若初始数据基本反序，则选用选择。
(90)在堆排序和快速排序中，若初始记录接近正序或反序，则选用堆排序；若初始记录基本无序，则最好选用快速排序。
(91)对于n个记录的集合进行冒泡排序，在最坏的情况下所需要的时间是O(n2)。若对其进行快速排序，在最坏的情况下所需要的时间是O(n2)
(92)
(93)
(94)
(95)
(96)
(97)
(98)
(99)
()
()
()对于n个记录的集合进行归并排序，所需要的平均时间是O(nlog2n)
，所需要的附加空间是O(n)。
7．对于n个记录的表进行2路归并排序，整个归并排序需进行┌log2n┐趟（遍）。
8.设要将序列（Q,H,C,Y,P,A,M,S,R,D,F,X）中的关键码按字母序的升序重新排列，则：
冒泡排序一趟扫描的结果是HCQPAMSRDFXY；
初始步长为4的希尔（shell）排序一趟的结果是PACSQHFXRDMY；
二路归并排序一趟扫描的结果是HQCYAPMSDRFX；
快速排序一趟扫描的结果是FHCDPAMQRSYX；
堆排序初始建堆的结果是ADCRFQMSYPHX。
9.在堆排序、快速排序和归并排序中，
若只从存储空间考虑，则应首先选取方法，其次选取快速排序方法，最后选取归并排序方法；
若只从排序结果的稳定性考虑，则应选取归并排序方法；
若只从平均情况下最快考虑，则应选取堆排序、快速排序和归并排序方法；
若只从最坏情况下最快并且要节省内存考虑，则应选取堆排序方法。
赞赏