浙江工商大学数据结构期末复习题2.pdf

数 据 结 构 习 题 集一、选择题一、选择题.在一个长度为在一个长度为 n n 的顺序表中，向第的顺序表中，向第i i 个元素个元素(1(1i in+1)n+1)之前插入一个新元素时，需之前插入一个新元素时，需向后移动向后移动B B个元素。个元素。A.n-1B.n-i+1C.n-i-1D.i.在一个具有 n 个单元的顺序栈中，假定以地址低端作为栈底，以 top 作为栈顶指针，则当做退栈处理时，top 变化为C。A.top 不变.top-nC.toptop-1D.top=top+1.向顺序栈中压入元素时，是A。A.先存入元素，后移动栈顶指针B.先移动栈顶指针，后存入元素.在一个顺序存储的循环队列中，队首指针指向队首元素的A。A.前一个位置B.后一个位置C.队首元素位置D.队尾元素位置.若进栈序列为 1,2,3,4,进栈过程中可以出栈，则C不可能是一个出栈序列。A.3,4,2,1B.2,4,3,1C.1,4,2,3D.3,2,1,4.在具有 n 个单元的顺序存储的循环队列中，假定 front 和 rear 分别为队首指针和队尾指针，则判断队空的条件是C。A.front=rear+1B.front+1=rearC.front=rearD.front=0.在具有 n 个单元的顺序存储的循环队列中，假定 front 和 rear 分别为队首指针和队尾指针，则判断队满的条件是D。A.rear%n=frontB.(rear-1)%n=frontC.(rear-1)%n=rearD.(rear+1)%n=front.从一个具有 n 个节点的单链表中查找其值等于x 结点时，在查找成功的情况下，需平均比较D个结点。.在一个单链表中，已知*q 结点是*p 结点的前驱结点，若在*q 和*p 之间插入*s结点，则执行C。A.s-next=p-next;p-next=s;B.p-next=s-next;s-next=p;C.q-next=s;s-next=p;D.p-next=s;s-next=q;10.向一个栈项指针为 hs 的链栈中插入一个*s 结点时，则执行C。A.hs-next=s;B.s-next=hs-next;hs-next=s;C.s-next=hs；hs=s;D.s-next=hs;hs=hs-next;11.在一个链队列中，假定 front 和 rear 分别为队首指针和队尾指针，则进行插入*s 结点的操作时应执行B。A.front-next=s;front=s;B.rear-next=s;rear=s;C.front=front-next;D.front=rear-next;12.线性表是A。A.一个有限序列，可以为空B.一个有限序列，不能为空C.一个无限序列，可以为空D.一个无限序列，不能为空13.对顺序存储的线性表，设其长度为 n，在任何位置上插入或删除操作都是等概率的，删除一个元素时大约要移动表中的C个元素。A.n+1B.n-1C.(n-1)/2D.n14.线性表采用链式存储时，其地址D。A.必须是连续的B.部分地址必须是连续的C.一定是不连续的D.连续与否均可以15.设单链表中指针 p 指着结点(数据域为 m)，指针f 指着将要插入的新结点(数据域为x)，当 x 插在结点 m 之后时，只要先修改B后修改 p-link=f 即可。A.f-link=p;B.f-link=p-link;C.p-link=f-link;D.f=nil;16.在双向链表存储结构中，删除p 所指的结点时需修改指针B。A.(p-rlink)-rlink)-link=p;p-rlink=(p-rlink)-rlink;B.(p-llink)-rlink=p-rlink;(p-rlink)-llink=p-llink;C.p-llink=(p-llink)-llink;(p-llink)-llink)-rlink=p;D.(p-llink)-llink)-rlink=p;p-llink=(p-llink)-llink;17.在双向链表存储结构中，删除 p 所指的结点的前趋结点（若存在）时需修改指针A。A.(p-llink)-llink)-rlink=p;p-llink=(p-llink)-llink;B.(p-rlink)-rlink)-llink=p;p-rlink=(p-rlink)-rlink;C.(p-llink)-rlink=p-rlink;(p-rlink)-llink=p-llink;D.p-llink=(p-llink)-llink;(p-llink)-llink)-rlink=p;18.根据线性表的链式存储结构，每个结点所含指针的个数，链表分为单链表和B。A.循环链表B.多重链表C.普通链表D.无头结点链表19.在数据结构中，与所使用的计算机无关的数据叫C结构。A.存储B.物理C.逻辑D.物理和存储20.二分法查找A存储结构。A.只适用于顺序B.只适用于链式C.既适用于顺序也适用于链式D.既不适合于顺序也不适合于链式21.在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上B。A.一定相邻B.不一定相邻C.有时相邻23.假定在一棵二叉树中，双分支结点数为15 个，单分支结点数为32 个，则叶子结点数为B。A.15B.16C.17D.4724.假定一棵二叉树的结点数为18 个，则它的最小高度B。性质 2A.4B.5C.6D.1825.在一棵二叉树中第五层上的结点数最多为C。性质 1A.8B.15C.16D.3226.在一棵具有五层的满二叉树中，结点总数为A。性质 3A.31B.32C.33D.1627.已知 8 个数据元素为(34、76、45、18、26、54、92、65)，按照依次插入结点的方法生成一棵二叉排序树后，最后两层上的结点总数为B。不理解？A.1B.2C.3D.428.由分别带权为 9、2、5、7 的四个叶子结点构造一棵哈夫曼树，该树的带权路径长度为C。A.23B.37C.44D.46 为什么不是 46？29.在树中除根结点外，其余结点分成 m(m0)个A的集合 T1,T2,T3.Tm,每个集合又都是树，此时结点T 称为 Ti 的父结点，Ti 称为 T 的子结点(1im)。A.互不相交B.可以相交C.叶结点可以相交D.树枝结点可以相交30.下面答案D是查找二叉树（又称二叉排序树）。A.二叉树中的每个结点的两棵子树的高度差的绝对值不大于B.二叉树中的每个结点的两棵子树的高度差等于C.二叉树中的每个结点的两棵子树是有序的D.二叉树中的每个结点的关键字大于其左子树（如果存在）所有结点的关键字值，且小于其右子树（如果存在）所有结点的关键字值。31.如果结点 A 有三个兄弟，而且B 是 A 的双亲，则 B 的出度是B。A.3B.4C.5D.132.一个深度为 L 的满 K 叉树有如下性质：第 L 层上的结点都是叶子结点，其余各层上每个结点都有 K 棵非空子树。如果按层次顺序从开始对全部结点编号，编号为n 的有右兄弟的条件是B。A.(n-1)%k=0B.(n-1)%k!=0C.n%k=0D.n%k!=033.在完全二叉树中，当 i 为奇数且不等于时，结点 i 的左兄弟是结点D，否则没有左兄弟。A.2i-1B.i+1C.2i+1D.i-134.某二叉树 T 有 n 个结点，设按某种遍历顺序对T 中的每个结点进行编号，编号值为1,2,n 且有如下性质：T 中任一结点 V，其编号等于左子树上的最小编号减1，而 V 的右子树 的结点中，其最小编号等于V 左子树上结点的最大编号加1。这时按B编号。A.中序遍历序列B.前序遍历序列C.后序遍历序列D.层次遍历序列35.在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的B倍。A.1/2B.1C.2D.436.对于一个具有 n 个顶点和 e 条边的无向图，若采用邻接表表示，则表头向量的大小为A。A.nB.n+1C.n-1D.n+e37.具有 n 个顶点的无向完全图，边的总数为D条。A.n-1B.nC.n+1D.n*(n-1)/238.设图 G 有 n 个顶点和 e 条边，当 G 是非孤立顶点的连通图时有 2e=n,故可推得深度优先搜索的时间复杂度为A。A.O(e)B.O(n)C.O(ne)D.O(n+e)39.最小代价生成树D。A.是唯一的B.不是唯一的 C.唯一性不确定D.唯一性与原因的边的权数有关40.在无向图 G 的邻接矩阵 A 中，若 Ai,j等于 1，则 Aj,i等于C。A.i+jB.i-jC.1D.041.图的深度优先或广度优先遍历的空间复杂性均为A。(访问标志位数组空间)A.O(n)B.O(e)C.O(n-e)D.O(n+e)42.已知一个有序表为(12、18、24、35、47、50、62、83、90、115、134)，当二分查找值为 90 的元素时，B次比较后查找成功；当二分查找值为 47 的元素时，D次比较后查找成功。A.1B.2C.3D.443.散列函数有一个共同性质，即函数值应当以D取其值域的每个值。A.最大概率B.最小概率C.平均概率D.同等概率44.设散列地址空间为 0m1,k 为关键字，用 p 去除 k，将所得的余数作为 k 的散列地址，即 H(k)k%p。为了减少发生冲突的频率，一般取p 为D。A.小于 m 的最大奇数B.小于 m 的最大偶数C.mD.小于 m 的最大素数45.目前以比较为基础的内部排序时间复杂度 T(n)的范围是A；其比较次数与待 排序的记录的初始排列状态无关的是B。A.O(log2 n)O(n)O(lon2 n)O(n2)O(nlog2 n)O(n2)O(n)O(n2)O(n)O(nlog2 n)B.插入排序先用二分法查找，找到后插入排序快速排序冒泡排序46.设关键字序列为：3,7,6,9,8,1,4,5,2。进行排序的最小交换次数是A。A.6B.7C.8D.2047.在归并排序过程中，需归并的趟数为C。A.nB.nC.log2n 向上取整D.log2n 向下取整48.一组记录排序码为(46、79、56、38、40、84)，则利用堆排序的方法建立的初始堆为B。A.(79、46、56、38、40、80)B.(84、79、56、38、40、46)C.(84、79、56、46、40、38)D.(84、56、79、40、46、38)49.一组记录的关键码为(46、79、56、38、40、84)，则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为C。A.(38、40、46、56、79、84)B.(40、38、46、79、56、84)C.(40、38、46、56、79、84)D.(40、38、46、84、56、79)50.在平均情况下快速排序的时间复杂性为C，空间复杂性为B；在最坏情况下（如初始记录已有序），快速排序的时间复杂性为D，空间复杂性为A。A.O(n)B.O(log2 n)C.O(nlog2 n)D.O(n2)选择题参考答案：.B.C.A.A.C.C.D.D.C10.C11.B12.A13.C14.D15.B16.B17.A18.B19.C20.A21.B22.D23.B24.B25.C26.A27.B28.C29.A30.D31.B32.B33.D34.B35.B36.A37.D38.A39.D40.C41.A42.B,D 43.D44.D45.A:B:46.A采用选择排序对给定的关键字序列进行排序，只需次。47.C48.B49.C50.C B D A二、填空题1.在线性结构中第一结点1 无前驱结点，其余每个结点有且只有2 一个前驱结点；最后一个结点3 无后继结点，其余每个结点有且只有4 一个后继结点。2.在树型结构中，树根结点没有1 前趋结点，其余每个结点有且仅有2 一个前驱结点；树叶结点没有3 后继结点，其余每个结点的4 后继结点数不受限制。3.一个数据结构用二元组表示时，它包括1 数据元素的集合 K 和 K 上2二元关系的集合 R。4.对于一个二维数组A1.m,1.n，若按行序为主序存储，则任一元素 Ai,j的相对地址（即偏移地址）为1(i-1)*n+j-1。5.对于顺序存储的线性表，当随机插入或删除一个元素时，约需平均移动表长1 一半的元素。6.对于长度为 n 的顺序表，插入或删除元素的时间复杂性为1 O(n)；对于顺序栈或队列，插入或删除元素的时间复杂性为2 O(1)。7.在具有 n 个单元、顺序存储的循环队列中，队满时共有1 n-1个元素。8.从顺序表中删除第 i 个元素时，首先把第 i 个元素赋给1 变参或函数名带回，接着从2 链接指针开始向后的所有元素均3 前移一个位置，最后使线性表的长度4 减 1。9.在线性表的顺序存储中，元素之间的逻辑关系是通过1 相邻位置决定的；在线性表的链接存储中，元素之间的逻辑关系是通过2 链接指针决定的。10.一个单链表中删除*p 结点时，应执行如下操作:(1)q=p-next;(2)p-data=p-next-data;(3)p-next=1 q-next 或 p-next-next;(4)free(q);11.若要在一个单链表中的*p 结点之前插入一个*s 结点时，可执行如下操作:(1)s-next=1 p-next;(2)p-next=s;(3)t=p-data;(4)p-data=2 s-data;(5)s-data=3 t;12.对于线性表的顺序存储，需要预先分配好存储空间，若分配太多则容易造成存储空间的1 浪费，若分配太少又容易在算法中造成2 溢出，因此适应于数据量变化不大的情况；对于线性表的链接存储(假定采用动态结点)，不需要3 预先分配存储空间，存储器中的整个4 动态存储区都可供使用，分配和回收结点都非常方便，能够有效地利用存储空间，在算法中不必考虑5 溢出的发生，因此适应数据量变化较大的情况。13.无论对于顺序存储还是链接存储的栈和队列来说，进行插入或删除运算的时间复杂性均相同，则为1 O(1)。0020*14.一个稀疏矩阵为 3000，则对应的三元组线性表为00-15(1,3,2),(2,1,3),(3,3,-1),(3,4,5)。000015.对于一棵具有 n 个结点的树，则该树中所有结点的度之和为n-1。16.在一棵二叉树中，度为0 的结点的个数为n0，度为 2 的结点的个数为 n2，则：n0=n2+1。17.在二叉树的顺序存储中，对于下标为5 的结点，它的双亲结点的下标为1 2，若它存在左孩子，则左孩子结点的下标为2 10，若它存在右孩子，则右孩子结点的下标为3 11。18.假定一棵二叉树的广义表表示为A(B(，D)，C(E(G)，F)，则该树的深度为 14，度为 0 的结点数为 23，度为 1 的结点数为3 2，度为 2 的结点数为42；C 结点是 A 结点的5 右孩子，E 结点是 C 结点的6 左 孩子。19.在一棵二叉排序树中，按中序遍历得到的结点序列是一个有序序列。20.由分别带权为 3,9,6,2,5 的共五个叶子结点构成一棵哈夫曼树，则带权路径长度为55。21.假定在二叉树的链接存储中，每个结点的结构为leftdataright，其中data 为值域，left 和 right 分别为链接左、右孩子结点的指针域，请在下面中序遍历算法中画有横线的地方填写合适的语句。void inorder(bt);if bt!=nil(1)1 inorder(bt-left)；(2)2 printf(bt-data)；(3)3 inorder(bt-right)；22.在图 G 的邻接表表示中，每个顶点邻接表中所含的结点数，对于无向图来说等于该顶点的1 度数，对于有向图来说等于该顶点的2 出度数。23.假定一个图具有 n 个顶点和 e 条边，则采用邻接矩阵表示的空间复杂性为1O(n2)，采用邻接表表示的空间复杂性为2 O(n+e)。24.已知一个无向图的邻接矩阵如下所示，则从顶点 A 出发按深度优先搜索遍历得到的顶点序列为1 ABCDFE，按广度优先搜索遍历得到的顶点序列为2ABCEFD。ABCDEF011010A101011B110100C001001D110001E010110F25.已知一个图如下所示，在该图的最小生成树中，各边的权值之和为20。101552812326.假定在有序表 A1.20上进行二分查找，则比较一次查找成功的结点数为 11，比较两次查找成功的结点数为 22，比较三次查找成功的结点数为 34，比较四次查找成功结点数为 48，比较五次查找成功的结点数为 55，平均查找长度为 63.7。27.在索引查找或分块查找中，首先查找1 索引表，然后再查找相应的2子表或块，整个索引查找的平均查找长度等于查找索引表的平均查找长度与查找相应子表的平均查找长度之3 和。28.在散列存储中，装填因子的值越大，存取元素时发生冲突的可能性就 1 越大，当的值越小，存取元素时发生冲突的可能性就2 越小。29.给定线性表(18,25,63,50,42,32,90)，用散列方式存储，若选用h(K)=K%9 作为散列函数，则元素18 的同义词元素共有12个，元素25 的同义词元素共有 20 个，元素50 的同义词元素共有31个。30.在对一组记录(54,38,96,23,15,72,60,45,83)进行直接选择排序时，第四次选择和交换后，未排序记录(即无序表)为(54,72,60,96,83)。31.在对一组记录(54,38,96,23,15,72,60,45,38)进行冒泡排序时，第一趟需进行相邻记录交换的次数为17，在整个冒泡排序过程中共需进行25趟后才能完成。32.在归并排序中，若待排序记录的个数为20，则共需要进行15趟归并，在第三趟归并中，是把长度为24的有序表归并为长度为38的有序表。33.在直接插入和直接选择排序中，若初始数据基本正序，则选用1 直接插入排序，若初始数据基本反序，则选用2 直接选择排序。34.在堆排序、快速排序和归并排序中，若只从节省空间考虑，则应首先选取1 堆排序方法，其次选取2 快速排序方法，最后选取3 归并排序方法；若只从排序结果的稳定性考虑，则应选取4 归并排序；若只从平均情况下排序最快考虑，则应选取5 快速排序方法；若只从最坏情况下排序最快并且要节省内存考虑，则应选取6 堆排序方法。填空题参考答案1.1无2一3无4一2.1前趋2一3后继4后继3.1数据元素2二元关系4.1(i-1)*n+j-15.1一半6.1O(n)2O(1)7.1n-1预先8.1变参或函数名2第 i+1 个元素3前移4减 19.1相邻位置2链接指针10.1q-next 或 p-next-next11.1p-next2s-data3t12.1浪费2溢出3 预先分配4动态存储区5溢出13.1O(1)14.1(1,3,2),(2,1,3),(3,3,-1),(3,4,5)15.1n-116.1n2+117.1221031118.142332425右6左19.1中序20.15521.1inorder(bt-left)2printf(bt-data)3inorder(bt-right)22.1度数2出度数23.1O(n2)2O(n+e)24.1ABCDFE2ABCEFD25.12026.112234485563.727.1索引表2子表或块3和28.1越大2越小29.12203130.1(54,72,60,96,83)31.172532.15243833.1直接插入排序2直接选择排序34.1堆排序2快速排序3归并排序4归并排序5快速排序6堆排序三、判断题1数据元素是数据的最小单位（）。2数据项是数据的基本单位（）。3顺序存储的线性表可以随机存取（）。4线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此，是属于同一数据对象（）。5在单链表中，任何两个元素的存储位置之间都有固定的联系，因为可以从头结点查找任何一个元素（）。6在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构（）。7链表的每个结点中，都恰好包含一个指针（）。*8数组是同类型值的集合（）。/不是集合/*9使用三元组表示稀疏矩阵的元素，有时并不能节省存储时间（）。*10.线性表可以看成是广义表的特例，如果广义表中的每个元素都是原子，则广义表便成为线性表（）。11.由树转换成二叉树，其根结点的右子树总是空的（）。12.后序遍历树和中序遍历与该树对应的二叉树，其结果不同（）。13.若有一个结点是某二叉树子树的中序遍历序列中的最后一个结点，则它必是该子树的前序遍历序列中的最后一个结点（）。14.若一个树叶是某子树的中序遍历序列中的最后一个结点，则它必是该子树的前序遍历序列中的最后一个结点（）。15.已知二叉树的前序遍历和后序遍历序列并不能唯一地确定这棵树，因为不知道树的根结点是哪一个（）。16.在哈夫曼编码中，当两个字符出现的频率相同时，其编码也相同，对于这种情况应作特殊处理（）。17.有回路的图不能进行拓扑排序（）。18.连通分量是无向图中的极小连通子图（）。/极大/19.散列法存储的基本思想是由关键码的值决定数据的存储地址（）。20.散列表的查找效率取决于散列表造表时选取的散列函数和处理冲突的方法（）。21.m 阶 B-树每一个结点的子树个数都小于或等于m（）。22.中序遍历二叉排序树的结点就可以得到排好序的结点序列（）。23.在二叉排序树上插入新的结点时，不必移动其它结点，仅需改动某个结点的指针，由空变为非空即可（）。24.当待排序的元素很多时，为了交换元素的位置，移动元素要占用较多的时间，这是影响时间复杂性的主要因素（）。25.对于 n 个记录的集合进行快速排序，所需要的平均时间是O(nlog2n)（）。26.对于 n 个记录的集合进行归并排序，所需要的平均时间是O(nlog2n)（）。27.堆中所有非终端结点的值均小于或等于（大于或等于）左右子树的值（）。*28.磁盘上的顺序文件中插入新的记录时，必须复制整个文件（）。*29.在索引顺序文件中插入新的记录时，必须复制整个文件（）。*30.索引顺序文件是一种特殊的顺序文件，因此通常存放在磁带上（）。判断题参考答案.10.11.12.13.14.15.16.17.18.19.20.21.22.23.24.25.26.27.28.29.30.四、综合题1.线性表有两种存储结构：一是顺序表，二是链表。试问：(1)两种存储表示各有哪些主要优缺点?(2)如果有 n 个线性表同时并存，并且在处理过程中各表的长度会动态发生变化，线性表的总数也会自动地改变。在此情况下，应选用哪种存储结构?为什么?(3)若线性表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取线性表中的元素，那么，应采用哪种存储结构?为什么?1.解答:(1)顺序存储是按索引（隐含的）直接存取数据元素，方便灵活，效率高，但插入、删除操作时将引起元素移动，因而降低效率；链接存储内存采用动态分配，利用率高，但需增设指示结点之间有序关系的指针域，存取数据元素不如顺序存储方便，但结点的插入、删除操作十分简单。(2)应选用链接表存储结构。其理由是，链式存储结构用一组任意的存储单元依次存储线性表里各元素，这里存储单元可以是连续的，也可以是不连续的。这种存储结构，在对元素作插入或删除运算时，不需要移动元素，仅修改指针即可。所以很容易实现表的容量扩充。(3)应选用顺序存储结构。其理由是，每个数据元素的存储位置和线性表的起始位置相差一个和数据元素在线性表中的序号成正比的常数。由此，只要确定了起始位置，线性表中任一数据元素都可随机存取，所以线性表的顺序存储结构是一种随机存取的存储结构。而链表则是一种顺序存取的存储结构。2.用线性表的顺序结构来描述一个城市的设计和规划合适吗?为什么?2.解答:不合适。因为一个城市的设计和规划涉及非常多的项目，很复杂，经常需要修改、扩充和删除各种信息，才能适应不断发展的需要。有鉴于此，顺序线性表不能很好适应其需要，故是不合适的。3.在单链表和双向表中，能否从当前结点出发访问到任一结点?3.解答:在单链表中只能由当前结点访问其后的任一结点，因为没有指向其前驱结点的指 针。而在双向链表中，既有指向后继结点的指针又有指向前驱结点的指针，故可由当前结点出发访问链表中任一结点。4.试述栈的基本性质?4.解答:由栈的定义可知，这种结构的基本性质综述如下：(1)集合性。栈是由若干个元素集合而成，当没有元素的空集合称为空栈；(2)线性结构。除栈底元素和栈顶元素外，栈中任一元素均有唯一的前驱元素和后继元素；(3)受限制的运算。只允许在栈顶实施压入或弹出操作，且栈顶位置由栈指针所指示；(4)数学性质。当多个编号元素依某种顺序压入，且可任意时刻弹出时，所获得的编号元素排列的数目，恰好满足卡塔南数列的计算，即：n n 2n/(n1)其中，n 为编号元素的个数，Cn是可能的排列数目。5.何谓队列的上溢现象?解决它有哪些方法，且分别简述其工作原理。5.解答:在队列的顺序存储结构中，设队头指针为front,队尾指针为 rear,队的容量（存储空间的大小）为 m。当有元素要加入队列时，若 rearm（初始时 reat0），则发生队列的上溢现象，该元素不能加入队列。这里要特别注意的是：队列的假溢出现象，队列中还有空余的空间，但元素不能进队列。造成这种现象的原因是由于队列的操作方式所致。解决队列的上溢有以下几种方法：(1)建立一个足够大的存储空间，但这样做往往会造成空间使用的效率低。(2)当出现假溢出时，可采用以下几种方法：采用平移元素的方法。每当队列中加入一个元素时，队列中已有的元素向队头移动一个位置（当然要有空余的空间可移）；每当删去一个队头元素时，则依次序移队中的元素，始终使front 指针指向队列中的第一个位置；采用循环队列方式。把队头队尾看成是一个首尾相邻的循环队列，虽然物理上队尾在队首之前，但逻辑上队首依然在前，作插入和删除运算时仍按“先进先出”的原则。6.两个字符串相等的充要条件是什么?6.解答:两个字符串相等的充要条件是：两个串的长度相等，且对应位置的字符相等。*7.画出广义表(A(B(E，F(J)，C，D(G(K，L)，H，I)对应的树型结构。7.解答:根据广义表的结构可知，该树的根结点为A；而B、C、D 为 A 的子树，B 又有两棵子 树等等，该广义表对应的树型结构见下图。ABCDEFGHIJKL*8.对于二叉排序树，当所有结点的权都相等的情况下，最佳二叉排序树有何特点。8.解答:其特点是只有最下面的二层结点可以小于，其它结点的度数必须为。9.试证明：已知一棵二叉树的前序序列和中序序列，则可唯一地确定一棵二叉树。9.证明利用前序遍历的结果序列能够得到各子树的根，即从左到右检查前序遍历序列，当得到根结点之后，利用根结点在中序遍历序列中的位置可以确定其左右子树，这样便可逐次确定整个二叉树。假设 BT 为二叉树的根，P1，P2，Pn为前序遍历序列，I1，I2，In为中序遍历序列。由前序遍历序列可以得到BTP1。在中序遍历序列中查找等于P1的结点，设该结点为 Ii，则有 IiP1。根据二叉树中序遍历的原理，则该二叉树可被分成左右两棵子树：对于左子树，在中序遍历序列中有 I1，I2，Ii1，依此序列在前序遍历序列中可以得到其左子树为P2，P3，Pi；同理，对于右子树有Ii1，Ii2，InPi1，Pi2，Pn对于这两棵子树而言，其左子树的根为P2，其右子树的根为Pi1。依此类推，用同样的方法就可以确定整个二叉树。10.证明 n 个顶点的无向完全图的边数的n(n1)/2。10.证明方法一：用归纳法证明当 n1 时，边数为 0，结论成立。当 n2 时，边数为 1，结论成立。当 n1,2,k 时均成立，即当 nk 时，边数为 k(k1)/2。现证明当 nk1 时若仍然 成立，则结论正确。由前面证得，对于有 k 个顶点时，其边数总和为 k(k1)/2。当再增加一个新顶点时，由于是无向完全图，故该顶点到原来各个顶点均有一条边，这样就共有边数为k(k1)/2kk(k1)/2(k1)(k1)1/2可知当顶点数 k1 时，结论仍然成立，故具有n 个顶点的无向完全图的这数为n(n1)/2方法二：在 n 个顶点的无向完全图中，每个顶点与其余各顶点均有一条边。第一个顶点到其余各顶点的边数为 n1，第二个顶点到其余各顶点的边数为n1，但它与第一个顶点之间的边已在第一个顶点的边中，故第二个顶点到其它n2 个顶点的边为 n2,，第 n1 个到余下的第 n 个顶点为边数为 1，所以总的边数为(n1)(n2)(n3)21n(n1)/2所以其结论成立。11.证明一个有 n 个顶点，e 条边的无向图 G，必有dj2e其中 dj为顶点 j 的度。11.证明由度的定义可知，顶点 j 所联接的边数必为 dj条，另一方面，图 G 中的任一条边均关联 G 中的两个顶点，即一条边均要分别计入两个不同的dj和 di中，故dj中的边数应为G 中边数的两倍，即有nj2ei-112.证明：若无向图 G 的顶点度数的最小值大于或等于2，则 G 有一条回路。12.证明方法一：设 G(V，E)，任取一顶点v1V，因V1的度大于或等于 2,在 v1的邻接顶点中任取一个不同于 v1的顶点作为 v2。因 v2的度大于或等于 2,在 v2的邻接顶点中任取一个不同于 v2的顶 点作为 v3。若 v1、v2、v3不构成回路，则在再 v3的邻接顶点中任取一个不同于 v3的的顶点 作为 v4，。因为图中顶点的集合 V 是有限的，当取得某个顶点 vi 后，vi1 一定为 v1，v2，vi-1 之一，因而构成回路。命题得证。方法二：设图 G 有 n 个顶点，整个图 G 的度数之和为 N，则有N2n我们知道，图中每条边涉及二个顶点，也就是每条边含有 2 个度，这样一来，该图 G至少有 n 条边。由于一个 n 个顶点的树图只有 n1 条边，多于 n1 条边时则树图就不存在，图中会出现回路。由前面推得，该图至少有n 条边，故会出现回路。13.若对大小均为 n 的有序的顺序表和无序的顺序表分别进行顺序查找，试问在下面三 种情况下，分别讨论两者在等概率时，平均查找长度是否相同?(1)查找不成功，即表中没有关键字等于给定值k 的记录；(2)查找成功，且表中只有一个关键字等于给定值k 的记录；(3)查找成功，且表中有若干个关键字等于给定值k 的记录，一次查找要求找出所有记录，此时的平均查找长度应考虑找到所有记录时所用的比较次数。13.(1)解答:不相同。对于有序的顺序表而言，当表中无此关键字时，只要在查找过程中发现顺序表中的某个关键字大于待查的关键字时，查找过程就可以结束（假定顺序表是由小到大排列的，对于由大到小排列的情况类似），没有必要查找到表中最后一个关键字才确定查找不成功。而对于非有序的顺序表，只有对表中的每一个关键字比较完之后，才能说明查找不成功。显然在等概率时两种顺序的平均查找长度是不相同的。有序顺序表的平均长度为(n1)/2，而无序顺序表的平均查找长度为n。但从数量级上两者是相同的,即 O(n)。(2)解答:相同的。其分析类似于(1)。两者在等概率下的平均长度为(n1)/2，数量级上为 O(n)。(3)解答:不相同。其分析完全与(1)相同，其结论也完全相同。14.假定有 n 个关键字，它们具有相同的 Hash 函数值，用线性探测方法把这 n 个关键字 存入到 Hash 地址空间中要做多少次探测?14.解答:由于线性探测的查找次数主要取决于装载因子，即与 Hash 地址空间的占用情况 有关。假定初始时 Hash 地址空间为空，在此情况下连续装入 n 个具有相同的Hash 函数值的 关键字所需的总探测次数为12nn(n1)/215.有一个 2000 项的表，欲采用等分区间顺序查找方法进行查找，问(1)每块的理想长度是多少?(2)分成多少块最为理想?(3)平均查找长度是多少?(4)若每块长度为 20，平均查找长度是多少?15.解答：(1)在给定 n 的前提下，理想的块长 d 为n200045(2)因查找方法为等分区间顺序查找，长度为 n 的表被分成 bn/d块，d 为块长，故有bn/d2000/4545(3)平均查找长度为ASLbd/21(4545)/2146(4)因每块的长度为 20，所以表被分成 b 块，其平均查找 ASL 长度为bn/d2000/20100ASL(bd)/21(10020)/216116.在执行某种排序算法的过程中，出现了排序码朝着最终排序序列相反的方向移动，从而认为该排序算法是不稳定的，这种说法对吗?为什么?16.解答:这种说法不对。因为排序的不稳定性是指排序前两个排序码相同的元素的相对次 序经过排序后发生了变化，而题中未涉及到元素的相对次序（特别是相同排序码的元素）的改变，只有移动方向，所以此种说法不对。17.设有 5000 个无序的元素，希望用最快速度挑选出其中前10 个最大的元素。在以下 的排序方法中，采用哪种方法最好?为什么?快速排序，堆排序，归并排序，基数排序的Shell 排序。17.解答:上面所列的几种排序方法的速度都很块，但快速排序、归并排序、基数排序和希尔排序都是在排序结束后才能确定数据元素的全部顺序，而无法知道排序过程中部分元素的有序性。而堆排序则每次输入一个最大（或最小）的元素，然后对堆进行调整，保证堆顶的元素总是余下元素中最大（或最小）的。根据题意，只要选取前10 个最大的元素，故采用堆排序方法是合适的。*18.证明对一个长度为 n 的任意文件进行排序，至少需要作nlog2n 比较。18.证明在排序过程中，每次时行元素的比较产生两种路径。如果排序过程至少需作 t 次比较，则有 2t条路径。由于 n 个结点总共有 n 种不同的排列,因而必须有 n 种不同的比较路径。于是2tn!即tlog2n!因为log2n!nlog2nn/ln21/2log2nO(1)故有log2n!nlog2ntnlog2n证毕。19.判断下列序列是否是堆。若不是堆，则把它们依次调整为堆。(1)(100，85，98，77，80，60，82，40，20，10，66)；(2)(100，98，85，82，80，77，66，60，40，20，10)(3)(100，85，40，77，80，60，66，98，82，10，20)；(4)(10，20，40，60，66，77，80，82，85，98，100)；19.解答:根据堆的定义可知堆中元素满足下面中的某一个式子的关系，k2ik2iki或 kik2i1k2i1因此(1)、(2)和(4)序列是堆。(3)不是堆。(3)调整为 100,98,66,85,80,60,40,77,82,10,20后成为堆。*20.试列出文件的存储结构以及其相应文件类型，并简略回答其特点。20.解答:(1)顺序结构，相应的文件为顺序文件。这种文件中的记录按存入文件的时间先后次序顺序存放。当记录的物理存取顺序与它们的关键码大小顺序一致时，则物理顺序和逻辑顺序是一致的。顺序文件适合顺序存取。(2)计算寻址结构，相应的文件为散列文件。这种文件中的记录，在存放时，是根据它的关键码值经过散列函数计算来确定其地址的，散列函数把一个记录的关键码值经过计算转化为该记录所对应的地址。散列文件适合于随机存取。(3)带索引的结构，相应的文件为带索引文件。这种文件带有一个索引表，索引表中的每一项内容包含一个关键码值和对应于该关键码值的相应地址。一般情况下，索引表本身是按关键码值的大小顺序排列的，而带索引文件本身内容的物理顺序与其逻辑顺序可以是一致的，也可以是不一致的。带索引文件是以索引表的物理顺序来体现文件的逻辑次序的，即索引表的物理顺序实现了文件的线性结构。由以上三种文件可以派生出其它类型的文件。21.编写下列算法(1)向类型有 list 的线性表 L 的第 i 个元素（0iL.len）之后插入一个新元素 x。(1)解答:status insert(SqList L,int i,ElemType x)/向线性表 L 中第 i 个元素之后插入值为x 的新元素(1)if(L.len=m0)error(overflow);(2)if(iL.len)error