数据结构原理和分析-01343-18日下-复习题资料全

...wd......wd......wd...数据构造原理与分析-01343-18日下-复习资料一、填空1.线性表是具有n个什么的有限序列〔数据元素〕。2.邻接表的存储构造以以下列图的深度优先遍历类似于二叉树的(先序遍历)。3.在一棵二叉树的二叉链表中，空指针域数等于非空指针域数加〔2〕。4.某二叉树的前序和后序序列正好相反，那么该二叉树一定是什么二叉树(高度等于其结点数)。5.对于栈操作数据的原那么是〔后进先出〕。6.结点前序为xyz的不同二叉树，所具有的不同形态为(5)。7.设长度为n的链队列用单循环链表表示，假设只设头指针，那么入队操作的时间复杂度为(O(n))。8.在一棵高度为h(假定树根结点的层号为0)的完全二叉树中，所含结点个数不小于(2h)。9.具有n个顶点的有向无环图最多可包含有向边的条数是(n(n-1)/2)。10.因此在初始为空的队列中插入元素a,b,c,d以后，紧接着作了两次删除操作，此时的队尾元素是(d).11.假设二叉树中度为2的结点有15个，度为1的结点有10个，那么叶结点的个数〔16〕。12.对于一棵满二叉树，m个树叶，n个结点，深度为h,那么(n=2h＋1-1)。13.在一棵具有n个结点的二叉树中，所有结点的空子树个数等于〔n+1〕14.用邻接表表示图进展深度优先遍历时，通常用来实现算法的辅助构造是(栈)。15.堆的形状是一棵(完全二叉树)。16.假设在一棵非空树中，某结点A有3个兄弟结点〔包括A自身〕，B是A的双亲结点，那么B的度为(4)。17.任何一个无向连通图的最小生成树(有一棵或多棵)18.在非空二叉树的中序遍历序列中，二叉树的根结点的左边应该(只有左子树上的所有结点)。19.排序方法中，从未排序序列中依次取出元素与已排序序列中的元素进展比较，将其放入已排序序列的正确位置上的方法，称为(插入排序)。20.对于一棵满二叉树，m个树叶，n个结点，深度为h,那么(n=2h＋1-1)。21.具有n个顶点的有向图最多可包含的有向边的条数是(n(n-1))。22.某二叉树的前序和后序序列正好一样，那么该二叉树一定是什么样的二叉树(空或只有一个结点)。23.栈和队列的主要区别在于(插入删除运算的限定不一样)。24.串是〔任意有限个字符构成的序列〕。25.对有14个数据元素的有序表R[14]进展折半搜索，搜索到R[3]的关键码等于给定值，此时元素比较顺序依次为〔R[6]，R[2]，R[4]，R[3]〕。26.深度为h且有多少个结点的二叉树称为满二叉树(2h+1-1)。27.在含n个顶点e条边的无向图的邻接矩阵中，零元素的个数为〔n2-2e〕。28.在一个有向图中，所有顶点的入度之和与所有顶点出度之和的倍数为(1)。29.邻接表的存储构造以以下列图的广度优先遍历类似于二叉树的(按层遍历)。30.设高度为h的二叉树上只有度为0和度为2的结点，那么此类二叉树中所包含的结点数至少为(2h-1)。31.假设一棵二叉树具有10个度为2的结点，5个度为1的结点，那么度为0的结点个数是〔11〕32.在一棵具有n个结点的二叉树中，所有结点的空子树个数等于〔n+1〕33.假设一棵二叉树有11个度为2的结点，那么该二叉树的叶结点的个数是〔12〕。34.对有n个记录的表按记录键值有序建设二叉查找树，在这种情况下，其平均查找长度的量级为〔O(n)〕。35.设森林F中有三棵树，第一、第二和第三棵的结点个数分别为m1,m2和m3,那么森林F对应的二叉树根结点上的右子树上结点个数是(m2+m3)。36.对有18个元素的有序表作二分〔折半〕查找，那么查找A[3]的比较序列的下标为〔9、4、2、3〕。37.假设要在O〔1〕的时间复杂度上实现两个循环链表头尾相接，那么应对两个循环链表各设置一个指针，分别指向(各自的尾结点)。38.深度为h的满二叉树所具有的结点个数是〔2h+1-1〕。39.设高度为h的二叉树上只有度为0和度为2的结点，那么此类二叉树中所包含的结点数至少为〔2h-1〕。40.如果T2是由有序树T转换而来的二叉树，那么T中结点的先根序列就是T2中结点的〔先根序列〕。41.有n个叶子的哈夫曼树的结点总数为〔2n-1〕。42.设长度为n的链队列用单循环链表表示，假设只设头指针，那么入队操作的时间复杂度为(O(n))。43.假设二叉树中度为2的结点有15个，度为1的结点有10个，那么叶子结点的个数为〔16〕。44.假设某完全二叉树的深度为h，那么该完全二叉树中具有的结点数至少是(2h－1)。45.叉树的前序和后序序列正好相反，那么该二叉树一定是什么二叉树(度等于其结点数)。46.初始序列已经按键值有序时，用直接插入算法进展排序，需要比较的次数为(n-1)。47.接表表示图进展广度优先遍历时，为实现算法通常采用的辅助构造是(队列)。48.用冒泡排序法对序列{18,16,14,12,10,8}从小到大进展排序，需要进展的比较次数是(15)。49.有n个顶点的图采用邻接矩阵表示，那么该矩阵的大小为〔n*n〕。50.6个顶点的无向图成为一个连通图至少应有边的条数是〔5〕。51.单链表中，增加头结点的目的是为了〔方便运算的实现〕。52.在线索二叉树中,结点(*t)没有左子树的充要条件是(t->ltag==1)。53.按照二叉树的定义,具有3个结点的二叉树有多少种(5)。54.对待排序的元素序列进展划分，将其分为左、右两个子序列，再对两个子序列施加同样的排序操作，直到子序列为空或只剩一个元素为止。这样的排序方法是〔快速排序〕55.二分查找法要求查找表中各元素的键值必须是(递增或递减)。56.线性表的长度是指〔表中的元素个数〕57.将长度为m的单链表连接在长度为n的单链表之后的算法的时间复杂度为(O(n))。58.有一个有序表为{1，3，9，12，32，41，45，62，75，77，82，95，100}，当二分查找值为82的结点时，查找成功的比较次数是〔4〕。.59.假设在一棵非空树中，某结点A有3个兄弟结点〔包括A自身〕，B是A的双亲结点，那么B的度为〔4〕。60.深度为h的满二叉树具有的结点个数为〔2h+1-1〕。61.用二叉链表存储树，那么根结点的右指针是〔空〕。62.个无向图中，所有顶点的度数之和等于所有边数〔1〕倍。63.单链表表示的链式队列的队头在链表的什么位置〔链头〕。64.线性表的长度是指〔表中的元素个数〕65.某二叉树的前序和后序序列正好一样，那么该二叉树一定是什么样的二叉树(空或只有一个结点)。66.在一棵具有n个结点的二叉树中，所有结点的空子树个数等于〔n+1〕。67.一个具有n个顶点e条边的无向图中，采用邻接表表示，那么所有顶点的邻接表的结点总数为〔2e〕。68.链栈和顺序栈相比，有一个较明显的优点是(通常不会出现栈满的情况)。69.对于键值序列{72,73,71,23,94,16,5,68,76,103}用筛选法建堆，开场结点的键值必须为(94)。70.在图形构造中，每个结点的前驱结点数和后续结点数可以有(任意多个)。71.对有n个记录的有序表采用二分查找，其平均查找长度的量级为(O(log2n))。72.在一棵高度为h(假定树根结点的层号为0)的完全二叉树中，所含结点个数不小于(2h)。73.假设一棵二叉树有10个叶结点，那么该二叉树中度为2的结点个数为9。74.设有一个顺序栈S，元素S1，S2，S3，S4，S5，S6依次进栈，如果6个元素的出栈顺序为S2，S3，S4，S6，S5，S1，那么顺序栈的容量至少应为3。75.对于一棵二叉树，设叶子结点数为n0,次数为2的结点数为n2,那么n0和n2的关系是n0=n2＋1。76.假设一棵二叉树有12个叶结点，那么该二叉树中度为2的结点个数为11。77.二叉树的存储构造有顺序存储构造和链式存储构造。78.深度为h且有2k-1个结点的二叉树称为满二叉树。(设根结点处在第1层)。79.图的深度优先搜索方法类似于二叉树的先序遍历。80.哈夫曼树是带权路径长度最小的二叉树。81.在线索二叉树中，线索是指向结点在某遍历次序下的前驱或后继结点的指针。82.栈可以作为实现递归函数调用的一种数据构造。83.一般树的存储构造有双亲表示法、孩子兄弟表示法和孩子链表表示法。84.将数据元素2,4,6,8,10,12,14,16,18,20依次存于一个一维数组中，然后采用折半查找元素12，被比较过的数组元素的下标依次为5，7，6。。85.图的深度优先遍历序列不是唯一的。86.假设二叉树的一个叶子结点是某子树的中根遍历序列中的第一个结点，那么它必是该子树的后跟遍历中的第一个结点。87.图的遍历是指从图中某一顶点出发访问图中全部顶点且使每一顶点仅被_访问一次。88.在一个图中，所有顶点的度数之和等于所有边的数目的2倍。89.由一棵二叉树的后序序列和中序序列可唯一确定这棵二叉树。90.在有序表(12,24,36,48,60,72,84)中二分查找关键字72时所需进展的关键字比较次数为2。91.设根结点的层数为0，定义树的高度为树中层数最大的结点的层数加1，那么高度为k的二叉树具有的结点数目，最少为k，最多为2k-1。92.在直接插入排序、直接选择排序、分划交换排序、堆排序中稳定的排序方法有直接插入排序。93.具有100个结点的完全二叉树的叶子结点数为50。94.普里姆(Prim)算法适用于边稠密图。95.在有n个叶子结点的哈夫曼树中,其结点总数为2n-1。96.将一棵树转换成一棵二叉树后，二叉树根结点没有右子树。97.矩阵采用压缩存储是为了节省空间98.假设连通网络上各边的权值均不一样，那么该图的最小生成树有1棵。99.设无向图G的顶点数为n，那么要使G连通最少有n-1条边。100.栈和队列的共同特点是插入和删除均在端点处进展。101.克鲁斯卡尔(Kruskar)算法适用于边稀疏图。102.假设连通图的顶点个数为n，那么该图的生成树的边数为n-1。103.图的存储构造最常用的有邻接矩阵和邻接表。104.由一棵二叉树的前序序列和中序序列可唯一确定这棵二叉树。105.队列中允许进展插入的一端称为队尾。106.拓扑排序输出的顶点数小于有向图的顶点数，那么该图一定存在环。107.在有序表(15,23,24,45,48,62,85)中二分查找关键词23时所需进展的关键词比较次数为2。108.树中所有结点的度等于所有结点数加〔-1〕。109.在一个具有n个顶点的完全无向图的边数为(n(n-1)/2)。110.用分划交换排序方法对包含有n个关键的序列进展排序，最坏情况下执行的时间杂度为(O(n2))111.一棵高度为h(假定树根结点的层号为0)的完全二叉树中，所含结点个数不小于(2h)。112.假设长度为n的非空线性表采用顺序存储构造，删除表的第i个数据元素，首先需要移动表中数据元素的个数是〔n-i〕。113.在非空二叉树的中序遍历序列中，二叉树的根结点的左边应该(只有左子树上的所有结点)。114.假设一棵二叉树具有45个度为2的结点，6个度为1的结点，那么度为0的结点个数是〔46〕。115.在一个有向图中，所有顶点的入度之和等于所有边数〔4〕倍。116.设输入序列为A,B,C,D,借助一个栈不可以得到的输出序列是(D,A,B,C)。117.一维数组A采用顺序存储构造，每个元素占用6个字节，第6个元素的起始地址为100，那么该数组的首地址是〔70〕。118.设abcdef以所给的次序进栈，假设在进栈操作时，允许退栈操作,那么下面得不到的序列为〔cbdef〕。119.一般情况下，将递归算法转换成等价的非递归算法应该设置〔堆栈〕。120.假设长度为n的非空线性表采用顺序存储构造，删除表的第i个数据元素，i的合法值应该121.是〔C.1≤i≤n〕。122.假设某线性表中最常用的操作是取第i个元素和删除最后一个元素，那么采用什么存储方123.式最节省时间〔顺序表〕。124.一组记录的关键字为{45,80,55,40,42,85}，那么利用堆排序的方法建设的初始堆为〔85,80,55,40,42,45〕。125.设有6000个无序的元素,希望用最快的速度挑选出其中前5个最大的元素,最好选用(堆排序)法。126.排序方法中，从未排序序列中挑选元素，将其放入已排序序列的一端的方法，称为(选择排序)。127.带头结点的单链表head为空的判断条件是(head->next==NULL)。128.在一个单链表中，假设删除(*p)结点的后继结点，那么执行(p->next=p->next->next)。129.在一棵具有n个结点的二叉树中，所有结点的空子树个数等于〔n+1〕130.有向图中，以顶点v为终点的边的数目，称为顶点v的〔入度〕。131.假设频繁地对线性表进展插入和删除操作，该线性表应该采用的存储构造是〔链式〕。132.设一个栈的输入序列是1，2，3，4，5,那么以下序列中，是栈的合法输出序列的是〔32154〕。133.有数据{53，30，37，12，45，24，96}，从空二叉树开场逐个插入数据来形成二叉查找树，假设希望高度最小，那么应选择下面输入序列是〔37,24,12,30,53,45,96〕。134.二叉树的第I层上最多含有结点数为〔2I〕。135.稀疏矩阵一般采用的压缩存储方法为(三元组表)。136.某二叉树的前序和后序序列正好一样，那么该二叉树一定是什么样的二叉树(空或只有一个结点)。137.假设长度为n的线性表采用顺序存储构造，在表的第i个位置插入一个数据元素，需要移动表中元素的个数是〔n-i+1〕。138.设有数组A[i,j]，数组的每个元素长度为3字节，i的值为1到8，j的值为1到10，数组从内存首地址BA开场顺序存放，当用以列为主存放时，元素A[5，8]的存储首地址为(BA+180)。139.二维数组A[5][6]的每个元素占5个单元，将其按行优先顺序存储在起始地址为3000的连续的内存单元中，那么元素A[4][5]的存储地址为〔3145〕。140.一个具有n个顶点的图采用邻接矩阵表示，那么该矩阵的大小为〔n*n〕。141.假设字符串“1234567〞采用链式存储，假设每个字符占用1个字节，每个指针占用2个字节，那么该字符串的存储密度为〔33.3﹪〕。142.假设在一棵非空树中，某结点A有3个兄弟结点〔包括A自身〕，B是A的双亲结点，那么B的度为〔3〕。143.设有三个元素X，Y，Z顺序进栈〔进的过程中允许出栈〕，以下得不到的出栈排列是(ZXY)。144.树形构造的特点是：一个结点可以有(多个直接后继)。145.使具有30个顶点的无向图成为一个连通图至少应有边的条数是〔29〕。146.使具有9个顶点的无向图成为一个连通图至少应有边的条数是〔8〕。147.在顺序表〔n足够大〕中进展顺序查找，其查找不成功的平均长度是〔n+1〕。148.设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1那么T中的叶子数为〔8〕。149.栈的插入和删除操作进展的位置在〔栈顶〕。150.假设一棵二叉树具有20个度为2的结点，6个度为1的结点，那么度为0的结点个数是〔21〕。151.一棵线索二叉树的线索个数比链接个数多〔2〕个。152.在循环链表中，从任何一结点出发都能访问到表中的所有结点。153.在n个结点的顺序表中插入一个结点需平均移动n/2个结点。154.循环队列的引入，目的是为了抑制假溢出。155.假设连通网络上各边的权值均不一样，那么该图的最小生成树有1棵。156.二叉树的遍历方式有三种：先序遍历、中序遍历、后序遍历。157.假设一棵二叉树有15个叶结点，那么该二叉树中度为2的结的点个数为14。158.设某二叉树的后序遍历序列为ABKCBPM，那么可知该二叉树的根为M。159.数据构造的三个方面：数据的逻辑构造、物理构造、运算。160.每个结点只有一个链接域的链表叫做单链表。161.组成串的数据元素只能是字符。162.具有n个结点的二叉树采用链接构造存储，链表中存放NULL指针域的个数为〔n+1〕。163.在一个无向图中，所有顶点的度数之和等于所有边数〔2〕倍。164设二叉树根结点的层次为0，一棵高度为h的满二叉树中的结点个数是(2h+1-1)。165.将一棵有50个结点的完全二叉树按层编号，那么对编号为25的结点x，该结点(有左孩子，无右孩子)。166.树〔或树形〕的定义是什么答：一个树〔或树形〕就是一个有限非空的结点集合T，其中有一个特别标出的称为该树之根root〔T〕的结点；其余〔除根外〕的结点划分成个不相交集合,而且这些集合的每一个又都是树。167在图形构造中，每个结点的前驱结点数和后续结点数可以有(任意多个)。168.什么是树的路径长度答：树的路径长度是指从根结点到树中每个叶结点的路径长度之和。二、选择1.假设某线性表中最常用的操作是取第i个元素和删除最后一个元素，那么采用什么存储方式最节省时间〔A〕。A.顺序表B.单链表C.双链表D.单循环链表2.在下述的排序方法中，不属于内排序方法的是〔C〕。A.插入排序法B.选择排序法C.拓扑排序法D.归并排序法3.以下四个关键词序列中,不是堆的序列为(C)。A.{05,23,16,68,94,72,71,73}B.{05,16,23,68,94,72,71,73}C.{05,23,16,73,94,72,71,68}D.{05,23,16,68,73,71,72,94}4.以下排序算法中,某一趟完毕后未必能选出一个元素放其最终位置上的是(D)。A.堆排序B.冒泡排序C.快速排序D.直接插入排序5.用孩子兄弟链表表示一棵树，假设要找到结点x的第5个孩子，只要先找到x的第一个孩子，然后(D)。A.从孩子域指针连续扫描5个结点即可B.从孩子域指针连续扫描4个结点即可C.从兄弟域指针连续扫描5个结点即可D.从兄弟域指针连续扫描4个结点即可6.链栈和顺序栈相比，有一个较明显的优点是(A)。A.通常不会出现栈满的情况B.通常不会出现栈空的情况C插入操作更加方便D.删除操作更加方便7.任何一棵二叉树的叶结点在其先根、中根、后根遍历序列中的相对位置(C)。A.肯定发生变化B.有时发生变化C.肯定不发生变化D.无法确定8.排序方法中，从未排序序列中挑选元素，将其放入已排序序列的一端的方法，称为(D)。A.希尔排序B.冒泡排序C.插入排序D.选择排序9.堆是一种什么排序〔B〕。A.插入B.选择C.交换D.归并10.以下排序方法中不稳定的排序是(C)。A.直接插入排序B.冒泡排序C.堆排序D.归并排序11.一个无向连通图的生成树是含有该连通图的全部顶点的(A)。A.极小连通子图B.极大连通子图C.极小子图D.极大子图12.如下陈述中正确的选项是(A)。A.串是一种特殊的线性表B.串的长度必须大于零B.串中元素只能是字母D.空串就是空白串13.快速排序不利于发挥其长处的情况是〔C〕。[A]待排序数据量太大[B]待排序数据一样值过多[C]待排序数据已基本有序[D]待排序数据值差过大14.性表中采用折半查找法查找元素，该线性表必须满足〔C〕。[A]元素按值有序[B]采用顺序存储构造[C]元素按值有序，且采用顺序存储构造[D]元素按值有序，且采用链式存储构造15.r在排序前已按元素键值递增顺序排列，那么比较次数较少的排序方法是(A)。A.直接插入排序B.快速排序C.归并排序D.选择排序16.一个递归的定义可以用递归过程求解，也可以用非递归过程求解，但单从运行时间来看，通常递归过程比非递归过程〔B〕A．较快B．较慢C．一样D.不确定17.如果待排序序列中两个数据元素具有一样的值，在排序后它们的位置发生颠倒，那么称该排序是不稳定的。不稳定的排序方法是〔D〕。A．起泡排序B．归并排序C．直接插入法排序D．简单项选择择排序18.将一棵有50个结点的完全二叉树按层编号，那么对编号为25的结点x，该结点(B)。A.无左、右孩子B.有左孩子，无右孩子C.有右孩子，无左孩子D.有左、右孩子19.假设某链表最常用的操作是在最后一个结点之后插入一个结点和删除最后一个结点，那么采用那种存储方式最节省时间(C)。A.单链表B.双链表C.带头结点的双循环链表D.单循环链表20.以下排序算法中,第一趟排序完毕后,其最大或最小元素一定在其最终位置上的算法是(D)。A.归并排序B.直接插入排序C.快速排序D.冒泡排序21.树形构造最适合用来描述〔C〕。[A]有序的数据元素[B]无序的数据元素[C]数据元素之间具有层次关系的数据[D]数据元素之间没有关系的数据22.设有7000个无序的元素,希望用最快的速度挑选出其中前5个最大的元素,最好选用方法是(C)。A.冒泡排序B.快速排序C.堆排序D.基数排序23.链表不具有的特点是(A)。A.可随机访问任一元素B.插入删除不需要移动元素C.不必事先估计存储空间D.所需空间与线性表长度成正比24.假设待排序对象序列在排序前已按其排序码递增顺序排序，那么比较次数最少的方法排序是〔A〕。A．直接插入排序B．快速排序C．归并排序D．直接选择排序25.以下关键字序列中是堆的序列为(D)。A.16,72,31,23,94,53B.94,23,31,72,16,53B.16,53,23,94,31,72D.16,23,53,31,94,7226.以下四个关键字序列中,那个序列不是堆(C)。A.{05,23,16,68,94,72,71,73}B.{05,16,23,68,94,72,71,73}C.{05,23,16,73,94,72,71,68}D.{05,23,16,68,73,71,72,94}27.下面4个序列中，满足堆的定义是〔D〕。A.13,27,49,76,76,38,85,97B.76,38,27,49,76,85,13,97C.13,76,49,76,27,38,85,97D.13,27,38,76,49,85,76,9728.采用线性探查法处理冲突所构成的散列表上进展查找，可能要探测到多个位置，在查找成功情况下，所探测的这些位置上的键值〔D〕。A.一定都是同义词B.一定都不是同义词C.都一样D.不一定都是同义词29.性表中采用折半查找法查找元素，该线性表必须满足〔C〕。[A]元素按值有序[B]采用顺序存储构造[C]元素按值有序，且采用顺序存储构造[D]元素按值有序，且采用链式存储构造三、简答1.对于一个队列，如果输入项序列由1,2,3,4所组成，试给出全部可能的输出序列。答：1,2,3,4。2.将表达式(a+b)*c+d-(e+g)*h改写成后缀表达式。答：后缀表达式为：ab+c*d+eg+h*-3.对于一个栈，给出输入序列A，B，C，试给出全部可能的输出序列。答：解：输出序列为：ABC，CBA,ACB,BAC,BCA。4．将算术表达式a+b*〔c+d/e〕转为后缀表达式。答：B．abcde/+*+5.由权值为12，6，5，9,10的五个叶子结点构造一棵哈夫曼树，请问该树的带权路径长度是多少答：权值为95。6.由二叉树的前序和后序遍历序列能否唯一确定一棵二叉树。假设不能请举出反例。答：不能唯一确定一棵二叉树。如以以下列图。11231237.求出以以下列图所示有向图的邻接矩阵。VV0V4V3V2V1213457答：有向图的邻接矩阵为：027027∞1∞0∞∞∞∞∞05∞∞∞∞0∞3∞∞4001234012348.有个顶点的无向连通图至少有多少条边有个顶点的有向连通图至少有多少条边答：有个顶点的无向连通图至少有n-1条边，有个顶点的有向连通图至少有n条边。9．下面列举的是常用的排序方法：直接插入排序，起泡排序，快速排序，直接选择排序，堆排序，归并排序。试问，哪些排序方法是稳定的答：起泡排序,直接插入排序，归并排序是稳定的。10.为什么说树是一种非线性构造树中的每个结点除了根结点外，其余每个结点有一个直接前驱，但有多个直接后继，所以说树是一种非线性构造。11．一棵二叉树的前序和中序序列，求该二叉树的后序序列。前序序列：A,B,C,D,E,F,G,H,I,J中序序列：C,B,A,F,E,D,I,H,J,G答：后序序列为：C,B,F,E,I,J,H,G,D,A12．试述顺序存储和链式存储的区别及各自的优缺点。答：数组占用连续的内存空间，链表不要求结点的空间连续。1〕插入与删除操作：由于数组在插入与删除数据时需移动大量的数据元素，而链表只需要改变一些指针的链接，因此，链表比数组易于实现数据的插入和删除操作。2〕内存空间的占用情况：因链表多了一个指针域，故较浪费空间，因此，在空间占用方面，数组优于链表。3〕数据的存取操作：访问链表中的结点必须从表头开场，是顺序的存取方式，而数组元素的访问是通过数组下标来实现的，是随机存取方式，因此，在数据存取方面，数组优于链表。数据的合并与别离：链表优于数组，因为只需要改变指针的指向13.将表达式((a+b)-c*(d+e)-f)*(g+h)改写成后缀表达式。答：后缀表达式为：ab+cde+*-f-gh+*14．将算术表达式a*(b+c)-d转为后缀表达式。答：abc+*d-15.求出以以下列图所示有向图的邻接表。VV0V4V3V2V1213457答：有向图的邻接表为：VV0V1∧V2V3∧V4122741∧35∧34∧03Head16．试找出中序序列和后序序列一样的所有二叉树。答：空树或缺右子树的单支树。17.用邻接矩阵存储一个包含1000个顶点和1000条边的图，那么该图的邻接矩阵中有多少元素有多少非零元素答：该图的邻接矩阵中有1000*1000个元素。该图的邻接矩阵中有2000个非零元素。18.画出以以下列图中二叉树的顺序存储构造示意图。113715答：二叉树的顺序存储构造示意图为：113715A[0]A[2]A[6]A[14]19.写出中缀表达式A-(B+C/D)*E的后缀形式。答：中缀表达式A-(B+C/D)*E的后缀形式是：ABCD/+E*-。20．为什么用二叉树表示一般树答：树的最直观表示是为树中结点设置指向子结点的指针域，对k叉树而言，每个结点除data域外，还有k个链接域。这样，对一个有n个结点的k叉树来说，共有n*k个指针域，其中n-1个不空，另外n(k-1)+1个指针域为空，因此，空链接域的比例约为〔k-1〕/k，于是导致大量的空间浪费。然而，如果采用二叉树表示一棵n个结点的树，那么树中共有2n个链接域，其中未用到的有n+1个，占所有指针域的比例约为1/2，空间浪费少很多。另外，因为任何树型构造都可以转换成二叉树，因此，通常用二叉树表示树型构造。21．请指出一组权值〔7，5，2，4〕对应的哈夫曼树的带权路径长度。答：哈夫曼树的带权路径长度是35。22．试找出前序序列和中序序列一样的所有二叉树。解答：空树或缺左子树的单支树。23．完全二叉树用什么数据构造实现最适宜，为什么答：完全二叉树用一维数组实现最适宜。因为完全二叉树保存在一维数组中时，数组内没有空洞，不存在空间浪费问题；另外，顺序存储方式下，父子结点之间的关系可用公式描述，即父〔或子〕结点寻找子〔或父〕结点只需计算一个公式，访问结点方便。但采用链表存储时就存在空间浪费问题，因为每个结点要另外保存两个链接域，并且寻找结点也不容易。24.求出以以下列图所示无向图的邻接矩阵。VV0V1V2V30012301111001100111100123答：无向图的邻接矩阵为：5539132541805513571221183025.请构造权值为{5，13，21，7，18，30，41}的哈夫曼树。答：哈夫曼树为：26．我们已经知道，树的先根序列与其对应的二叉树的先根序列一样，树的后根序列与其对应的二叉树的中根序列一样。那么利用树的先根遍历次序与后根遍历次序，能否唯一确定一棵树请说明理由。答：能。因为树的先根序列与其对应的二叉树的先根序列一样，树的后根序列与其对应的二叉树的中根序列一样，而二叉树的先根序列与二叉树的中根序列能唯一确定一棵二叉树，所以利用树的先根遍历次序与后根遍历次序，能唯一确定一棵树。27．请给出如以以下列图所示的权图的邻接矩阵。VV0V4V3V2V1213457答：解：027∞1027∞1∞0∞∞∞∞∞05∞∞∞∞0∞3∞∞40012340123428．一棵二叉树的中序和前序序列如下，求该二叉树的后序序列。中序序列：c，b，d，e，a，g，i，h，j，f前序序列：a，b，c，d，e，f，g，h，i，j答：该二叉树的后序序列为：c,e,d,b,i,j,h,g,f,a29．对半查找是否适合于以链接构造组织的表答：对半查找不适合于以链接构造组织的表。。30.请指出中序遍历二叉查找树的结点可以得到什么样的结点序列。答：中序遍历二叉查找树的结点就可以得到从小到大排序的结点序列。31．把以以下列图中的森林转化为一棵二叉树。112684735解答：森林转化成的二叉树如以以下列图。11268473532.指出一般树的存储构造有哪几种答：树的存储构造有双亲表示法、孩子链表表示法和孩子兄弟表示法33.试找出前序序列和后序序列一样的所有二叉树。答：空树或只有根结点的二叉树。34.线性表有两种存储构造：一是顺序表，二是链表。试问：如果有n个线性表同时并存，并且在处理过程中各表的长度会动态变化，线性表的总数也会自动地改变。在此情况下，应选用哪种存储构造为什么答：选链式存储构造。它可动态申请内存空间，不受表长度〔即表中元素个数〕的影响，插入、删除时间复杂度为O35.求出以以下列图所示无向图的邻接表。VV0V1V2V3VV0V1V2V313∧203∧03∧02∧1Head答：无向图的邻接表为：36.一个图如下所示，假设从顶点0出发求出其广度优先搜索序列。003425167解答：广度优先搜索序列：0123456737.一组记录的关键字为(52,56,26,12,69,85,33,48,70)，给出快速排序的过程。解答：解：52,56,26,12,69,85,33,48,70第一趟排序33,48,26,12,52,85,69,56,70第二趟排序26,12,33,48,52,69,56,70,85第三趟排序12,26,33,48,52,56,70,69,85第四趟排序12,26,33,48,52,56,70,69,85第五趟排序12,26,33,48,52,56,70,69,8538．下面列举的是常用的排序方法：直接插入排序，起泡排序，快速排序，直接选择排序，堆排序，归并排序。试问，哪些排序方法是稳定的起泡排序,直接插入排序，归并排序是稳定的。39．一棵二叉树的前序和中序序列，求该二叉树的后序序列。前序序列：A,B,C,D,E,F,G,H,I,J中序序列：C,B,A,F,E,D,I,H,J,G答：后序序列为：C,B,F,E,I,J,H,G,D,A40．把以以下列图中的二叉树转化成森林。112684735112684735答案：41.给定表〔43,36,56,6,64,32,8,41〕，按数据元素在表中的次序构造一棵二叉查找树，并求其平均查找长度。解答：根据给定表〔43,36,56,6,64,32,8,41〕，构造的二叉查找树如以以下列图；其平均查找长度为：23/8。646483241656364342．将以以下列图中的二叉树，转换成相应的森林。AABCHFDJEILKGNM答：森林转化成的二叉树如以以下列图。JJCHEKFILNMABDG43.知二叉树按中根遍历所得到的结点序列为DCBGEAHFIJK，按后根遍历所得到的结点序列为DCEGBFHKJIA，画出该树形构造，并按中根遍历序列进展线索化。答：HHKFGCIBAJED44.对于以以下列图所示的二叉树，试分别写出先根遍历、中根遍历该树所得到的先根序列、中根序列。GGFEDCBALKJIH答：先根遍历的结点序列：ABCEIFJDGHKL，中遍历的结点序列：EICFJBGDKHLA46．把以以下列图中的二叉树转化成森林。126126847351268473547.一组记录的关键字为(52,56,26,12,69,85,33,48,70)，给出快速排序的过程。解答：解：52,56,26,12,69,85,33,48,70第一趟排序33,48,26,12,52,85,69,56,70第二趟排序26,12,33,48,52,69,56,70,85第三趟排序12,26,33,48,52,56,70,69,85第四趟排序12,26,33,48,52,56,70,69,85第五趟排序12,26,33,48,52,56,70,69,8548.设记录的关键字集合key={51,28,38,86,70,90,7,30,40,25}，试写出对key进展渐减增量排序〔增量d=5，3，1〕时，各趟排序完毕后的结果。解答：各趟排序完毕后的结果。初始状态：5128388670907304025第一趟排序(d=5):5173040259028388670第二趟排序(d=3):2873040258651389070第三趟排序(d=1):7252830384051708690〕49.有一棵二叉树如以以下列图所示，分别指出其前序、中序遍历的结点序列。AABHGFEDCIJ答：它的前序序列为：ABCDEFGHIJ,它的中序序列为：CDBAFGEIHJ。50.8个记录，对应的关键词为：{25,84,21,47,15,27,68,35,20}写出快速排序的第一趟排序过程图示。答：初始键值序列[258421471527683520]第一次交换[258421471527683520]↑i=2↑j=9第二次交换[252021471527683584]i↑↑j扫描穿插[252021154727683584]j↑↑iRm与Rj互换[252021154727683584]Rm↑j↑分划表[152021]25[4727683584]51.给定表〔40,9,56,6,39,73,8,23〕，按数据元素在表中的次序构造一棵二叉查找树。答：.二叉排序树如下。40409563986237352.有二叉树先序序列为：ABCDEF,中序序列为：CBAEDF,试画出该二叉树。答：二叉树如以以下列图。AACDFEB53.给定表〔40,36,56,6,64,73,8,23〕，按数据元素在表中的次序构造一棵二叉查找树，并求其平均查找长度。答：二叉查找树如下，平均查找长度为3。404036566486237353．根据以以下列图给出的二叉树，求出先序、中序遍历的结点序列。aacedfb答：先序遍历为：abdcef中序遍历为：dbaefc54.一组记录的关键字为〔50，79，8，56，32，41，85〕，给出利用重建堆方法建设的初始堆〔堆顶最大〕，并给出堆排序的过程。答：1〕建设的初始堆为:85，79，50，56，32，41，82〕堆排序的过程如下：858579328504156〔C〕第2次交换85418541328505679〔B〕第1次交换8413256507985〔A〕初始建堆858579565041832〔f〕第5次交换85798579565032841〔e〕第4次交换8579568324150〔D〕第3次交换858579565041328〔g〕第6次交换55.答：把以下森林转化为一棵二叉树。112684735答：森林转化成的二叉树如以以下列图。11268473556.数据序列为12,5,9,20,6,31,24，对该数据序列进展排序，试写出冒泡排序每趟的结果。答：初始键值序列12592063124第一趟排序[591262024]31第二趟排序[5961220]2431第三趟排序[59612]202431第四趟排序5691220243157.给定表〔40,36,55,6,64,77,9,41〕，按数据元素在表中的次序构造一棵二叉查找树，并求其平均查找长度。答：构造的二叉查找树如以以下列图，其平均查找长度为11/4。404035556496417758.对于以以下列图所示的二叉树，试分别写出先根遍历、中根遍历和后根遍历该树所得到的先根序列、中根序列和后根序列。GGFEDCBALKJIH解答：先根遍历的结点序列：ABCEIFJDGHKL中遍历的结点序列：EICFJBGDKHLA后根遍历的结点序列：IEJFCGKLHDBA59.数据序列为12,5,9,20,6,31,24，对该数据序列进展排序，试写出归并排序每趟的结果。解答：初始键值序列12592063124第一趟排序[512][920][631][24]第二趟排序[591220][62431]第三趟排序56912202431〔〕60.序表(5,12,17,19,23,25,30,36,45,49,58)中，用二分法查找关键词36，进展多少次比较后查找成功写出查找过程。解答：经过4次比较查找成功。查找过程如下：5,12,17,19,23,25,30,36,45,49,58j=115,12,17,19,23,25,30,36,45,49,58j=11m=6i=1〔A〕第1次与25进展比较j=115,12,17,19,23,25,30,36,45,49,585,12,17,19,23,25,30,36,45,49,58i=7m=9〔B〕第2次与45进展比较5,12,17,19,23,25,30,36,45,49,58j=8i=7m=7〔C〕第3次与30进展比较i=8i=85,12,17,19,23,25,30,36,45,49,58j=8m=8〔D〕第4次与36进展比较61.一组记录的关键字为(52,56,26,12,69,85,33,48,70)，给出快速排序的过程。解答：52,56,26,12,69,85,33,48,70第一趟排序33,48,26,12,52,85,69,56,70第二趟排序26,12,33,48,52,69,56,70,85第三趟排序12,26,33,48,52,56,70,69,85第四趟排序12,26,33,48,52,56,70,69,85第五趟排序12,26,33,48,52,56,70,69,8562.某二叉树的后序序列为：ABCDEFG,中序序列为：ACBGEDF,给出它的前序序列。解：它的前序序列为：GCABFED。63．根据以以下列图给出的二叉树，求出中序和后序遍历的结点序列。aacedfb解答：中序遍历为：dbaefc后序遍历为：dbfeca00342516764.一个图如下所示，假设从顶点0出发求出其深度优先搜索序列。解答：深度优先搜索序列：0137425665．给定表〔45,36,56,6,64,32,8,41〕，按数据元素在表中的次序构造一棵二叉查找树。解答：按数据元素在表中的次序构造一棵二叉查找树为：646483241656364566.找出所有这样的二叉树形，其结点在先根次序遍历和中根次序遍历下的排列是一样的。答：为空树，或为任一结点至多只有右子树的二叉树。下面程序段的时间复杂度是O〔mn〕。for(inti=1;i<=n;i++)for(intj=1;j<=m;j++)a[i][j]=0;67.设有序顺序表为{10,20,30,40,50,60,70,80}，采用折半查找时，查找成功和查找失败的平均查找长度分别是多少答：包含这8个元素的二叉判定树为：303010204070608050很明显，查找成功的平均比较次数是；查找失败的平均比较次数是。68.给定表〔43,36,56,6,64,32,8,41〕，按数据元素在表中的次序构造一棵二叉查找树，并求其平均查找长度。解答：根据给定表〔43,36,56,6,64,32,8,41〕，构造的二叉查找树如以以下列图；其平均查找长度为：23/8。646483241656364369.什么是增长树答：当二叉树中结点没有左子树形或没有右子树形时，增加特殊的结点，由此生成的二叉树称为增长的二叉树，简称增长树。70.什么是线性表答：一个线性表是由零个或多个具有一样类型的结点组成的有序集合。71.什么是一维数组答：一维数组是假设干个元素的一个有限序列，每个元素都通过一个下标来指定，所有的数组元素都具有一样的数据类型，占据一样大小的存储空间.72.什么是森林答：一个森林就是一组〔0个或多个〕不相交的树形〔通常诸树形间还有次序〕。73.什么是强连通图答：假设G为有向图，且对于V(G)中任意两个不同的顶点和，与连通，与也连通，那么称G为强连通图。74.什么是图中两点的简单路径答：如果一条路径上除了起点和终点可以一样外，再无一样的顶点，那么称此路径为简单路径。75.设单链表中存放着n个字符，设计算法判断字符串是否中心对称，如xyzzyx即为中心对称的字符串。答：将全部字符进栈，然后将栈中的字符逐个与链表中的字符比较队列的定义是什么答：队列是一种操作受限的线性表，它只允许在表的一端进展插入，在表的另一端进展删除。76.字符串的定义是什么答：字符串是由零个或多个字符〔字母、数字及其它一些符号〕组成的有限连续序列，简称为串。77.二叉树的定义是什么答：二叉树是结点的有限集合，它必须满足下面的一个条件：它是空集。它由一个根结点和根结点的左右子树构成，且其左右子树满足二叉树定义。78.有向图的定义是什么答：图G由两个集合V和E组成，记为G=(V,E).其中V是顶点的有限集合，E是连接V中两个不同顶点〔顶点对〕的边的有限集合。如果E中的顶点对是有序的，即E中的每条边都是有方向的，那么称G为有向图。79.AOV网的定义是什么答：用顶点表示活动，有向边表示活动之间先后关系的有向图简称为AOV网。80.设计一个算法，求出无向无权连通图中距离顶点v的最短路径长度为k的所有顶点，路径长度以变数为单位计算。答：算法中须用从顶点v出发广度优先遍历的层次特性来求解，因此，访问顶点时要知道一个顶点相对于v的层数，而每个顶点的层数是由其前驱顶点决定的。可以从顶点v开场，每访问到一个顶点就根据其前驱的层数计算该顶点的层数，并将层数值与顶点编号一起入队和出队。算法中可以使用两个队列，一个记录入队的顶点编号，另一个记录该顶点的层数，并保持二者的同步。81.两个整数序列A=a1,a2,a3,…,am和B=b1,b2,b3,…,bn已经存入两个单链表中，设计一个算法，判断序列B是否是序列A的子序列。1)给出算法的基本设计思想(4分)；2)用算法描述语言描述算法，并要求对算法中的关键步骤给出注释。答：1〕此题实质上是一个模式匹配问题，这里匹配的元素是整数而不是字符。因两整数序列已存入两个链表中，操作从两链表的第一个结点开场，假设对应数据相等，那么后移指针；假设对应数据不等，那么A链表从上次开场比较结点的后继开场，B链表仍从第一结点开场比较，直到B链表到尾表示匹配成功。A链表到尾B链表未到尾表示失败。操作中应记住A链表每次的开场结点，以便下趟匹配时好从其后继开场。2〕intPattern〔LinkedListA，B〕∥A和B分别是数据域为整数的单链表，本算法判断B是否是A的子序列。如是，返回1；否那么，返回0表示失败。{p=A；∥p为A链表的工作指针，此题假定A和B均无头结点。pre=p；∥pre记住每趟比较中A链表的开场结点。q=B；∥q是B链表的工作指针。while〔p&&q〕if〔p->data==q->data〕{p=p->next；q=q->next；}else{pre=pre->next；p=pre；∥A链表新的开场比较结点。q=B；}∥q从B链表第一结点开场。if〔q==null〕return〔1〕；∥B是A的子序列。elsereturn〔0〕；∥B不是A的子序列。}∥算法完毕。82.设一棵二叉树的先序、中序遍历序列分别为：先序遍历序列：ABDFCEGH中序遍历序列：BFDAGEHC请画出这棵二叉树。83.什么是权图答：设G=(V，E)是图，假设将图中的每条边L都赋上一个实数w(L)作为边的权值，那么称G为权图。84.画出后缀表达式ab+cde+*-f-gh+*对应的二叉表达式树。答：85.用序列(46,88,45,39,70,58,101,10,66,34)建设一棵二叉查找树，画出该树。答：4545883970101103458664686什么是队列的顺序存储答：队列的顺序存储是指利用一组地址连续的存储单元依次存放自队头到队尾的数据元素。87.什么是数组答：数组通常被定义为具有一样数据类型的元素的集合。88.什么是满二叉树答：一棵高度为的满二叉树，是具有个结点且高度为的二叉树89.什么是连通图答：设G是无向图，假设从顶点到顶点有路径，那么称与连通。假设G为无向图，且V(G)中任意两顶点都连通，那么称G为连通图。90.什么是拓扑排序答：拓扑序列把AOV网中的所有顶点排成一个线性序列，该序列满足如下条件：假设AOV网中存在边，那么在该序列中，必位于之前。构造AOV网的拓扑序列的操作被称为拓扑排序。91.什么是子串答：一个串的子串系指该串中的任意一个连续子序列92.基于关键词比较的排序算法的下界是什么请指明直接插入排序、希尔排序、冒泡排序、快速排序、直接选择排序、堆排序、两路合并排序算法中，哪些算法的时间复杂度到达了排序下界，并简单分析其能够到达下界的原因。答：O(nlogn).快速排序，堆排序，合并排序到达下界。主要原因分别是，快速排序的分划方法一次消除多个反序对，堆排序采用基于树形的最大元查找策略，合并排序采用分治法。93.一个栈的输入序列是：1，2，3那么不可能的栈输出序列是312。94.什么是单向循环链表答：单向循环链表系指将单链表中表尾结点的next域指向表头结点，而不是存放空指针NULL，形成一个环形链表。95.什么是串的长度答：串包含的字符总数被称为串的长度。96.什么是线性表的链接存储答：线性表的链接存储是指线性表中的结点在内存中任意存放，相邻结点间用指针链接。四、解答1.写出计算单链表head〔head为单链表的表头〕中数据域data值为m的结点个数的算法。intcount(Node*head)//计算单链表head中数据域data值为m的结点个数{Node*p=head->next;intn=0;while(p!=NULL){if(p->data==m)n++；p=p->next;}returnn;}//count2.非空单链表head，试设计一个算法，交换p所指结点与其后继结点在链表中的位置。解答：intrevers(listnode*head,listnode*p)/*交换p所指结点与其后继结点在链表中的位置*/{if(p->next==NULL)return0;listnode*q=head;while(q->next!=p)q=q->next;{r=p->next；q->next=r;p->next=r->next;r->next=p;return1;}//revers3.线性表用带头结点的单向链表示，试写出删除表中所有data域为零的元素的算法。解：intDeleteItem(Node*head){Node*p=head;//声明指针p，并令其指向链表头结点while(p->nextNode()!=NULL){if(p->nextNode()->data==0)p->next=p->nextNode()->next.elsep=p->nextNode();//指针下移}}4．试设计一算法，计算带头结点的单链表head(head指向表头)的结点个数。解答：intLength()//计算带表头结点的单链表head的长度{Node*p=head->next;intcount=1;while(p->next!=NULL){p=p->next;count++;}returncount;}5．判断单链表head(head指向表头)是否是递增的。解答：intorder(Node*head){Node*p=head;while(p->next!=NULL)if(p->data<p->next->data)p=p->next;elsebreak;if(p->next==NULL)return1;elsereturn0;}6.设计一个算法，在一个单链表head中找出值最小的元素。解答：intMin(Node*head)//在单链表head中找出值最小的元素{Node*p=head;intmin=p->data;while(p->next!=NULL)阿{if(p->next->data<min)min=p->next->data;p=p->next;}returnmin;}nextdata7设有两个单链表L和L1,其结点构造为,试编写算法判断链表L1中的各元素是否都是单链表L中的元素。nextdata解答：intSubLnk(Node*L,Node*L1){Node*p1=L1;while(p1!=NULL){Node*p=L;while((p!=NULL)&&(p1->data!=p->data)){p=p->next;if(p==NULL)return0;elsep1=p1->next;}return1;}}8.设一棵二叉树以二叉链表为存储构造，设计一个算法交换二叉树中每个结点的左子女和右子女。〔12分〕解答：voidexchange(BinTreeNode*t){if(t!=NULL)BinTreeNode*temp;if((t->lchild!=NULL)||(t->rchild!=NULL)){temp=t->lchild;t->lchild=t->rchild;t->rchild=temp;exchange(t->lchild);exchange(t->rchild);}}9.设有一个正整数序列组成带头结点的单链表head，试编写算法确定在序列中比正整数x大的数有几个。〔8分〕解答：intcount〔Node*head，intx〕∥在带头结点的单链表head中，确定序列中比正整数x大的数有几个{Node*p=head->next;intcount=0;while(p!=NULL){if(p->data>x)count++;p=p->next;}returncount;}∥算法count完毕10.设一棵二叉树以二叉链表为存储构造，试设计一个算法计算二叉树中叶子结点的个数。〔12分〕解答：voidcountleaf(BinTreeNode*t,int&count){if(t!=NULL){if((t->lchild==NULL)&&(t->rchild==NULL))count++;〔2分〕countleaf(t->lchild,count);countleaf(t->rchild,count);}}11.设一棵二叉树以二叉链表为存储构造，试写一算法求该二叉树上度为2的结点个数。〔12分〕解答：voidcount2(bitreptrt，intcount){if(t!=NULL){if((t->lchild!=NULL)&&(t->rchild!=NULL))count++;count2(t->lchild,count)；count2(t->rchild,count)；}}//count212.设一棵二叉树以二叉链表为存储构造，试写一算法求该二叉树中最大值〔元〕。〔12分〕解答：voidmaxnode(bitreptrt，intmax){if(t!=NULL)〔2分〕{if(t->data>max)max=t->data;〔4分〕max=maxnode(t->lchild,max)；〔2分〕max=maxnode(t->rchild,max)；〔2分〕}returnmax;〔2分〕}//maxnode13.编写一个将二叉树中每个结点的左右孩子交换的算法。(1)给出算法的基本设计思想；(2)用算法描述语言描述算法，并要求对算法中的关键步骤给出注释。答：〔1〕用前根遍历的递归算法交换二叉树中各结点的左、右子树。〔2〕算法的C++实现：BintreeNode*swap(BintreeNode*b){BintreeNode*t,*t1,*t2;//t为交换后的二叉树if(b==NULL)t=NULL;else{t=newBintreeNode;//复制一个根节点t->data=b->data;t1=swap(b->left);t2=swap(b->right);t->left=t2;t->right=t1;}return(t);}14．假定整型数组A[n]中有多个零元素，试设计一个算法将A中所有非零元素依次移到A的前端。(1)给出算法的基本设计思想；(2)用算法描述语言描述算法，并要求对算法中的关键步骤给出注释。答：〔1〕方法1：因为数组是一种根据元素下标可以直接存取的数据构造，设置一