数据结构习题集.pdf

颈湄结混沏题更一、选择题1.在一个长度为n的顺序表中，向第i个元素(IWiWn+l)之前插入一个新元素时，需 向后移动 B 个元素。A.n-1 B.n-i+1 C.n-i-1 D.i2.在一个具有n个单元的顺序栈中，假定以地址低端作为栈底，以t op作为栈顶指针,则当做退栈处理时，t OD变化为 C。A.t op 不变 B.t op=-n C.t op=t op-1 D.t op=t op+l3.向顺序栈中压入元素时，是一 A。A.先存入元素，后移动栈顶指针 B.先移动栈顶指针，后存入元素4.在一个顺序存储的循环队列中，队首指针指向队首元素的 A。A.前一个位置 B.后一个位置 C.队首元素位置 D.队尾元素位置5.若进栈序列为1,2,3,4,进栈过程中可以出栈，则 C 不可能是一个出栈序列。A.3,4,2,1 B.2,4,3,1 C.1,4,2,3 D.3,2,1,46.在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队首指针和队 尾指针，则判断队空的条件是 C。A.front=rear+l B.front+l=rear C.front=rear D.front=07.在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队首指针和队 尾指针，则判断队满的条件是 D。A.rear%n=front B.(rear-1)%n=frontC.(rear-1)%n=rear D.(rear+1)%n=front8.从一个具有n个节点的单链表中查找其值等于x结点时，在查找成功的情况下，需 平均比较 D 个结点。A.n B.n/2 C.(n-1)/2 D.(n+l)/29.在一个单链表中，已知*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;IL在一个链队列中，假定front和war分别为队首指针和队尾指针，则进行插入*s结点的操作时应执行 B。A.front-next=s;front=s;C.front=front-next;B.rear-next=s;rear=s;D.front=rear-next;12.线性表是 AA.一个有限序列，可以为空B.一个有限序列，不能为空C.一个无限序列，可以为空 D.一个无限序列，不能为空13.对顺序存储的线性表，设其长度为n,在任何位置上插入或删除操作都是等概率的，删除一个元素时大约要移动表中的_个元素。A.n+1 B.n-1 C.(n-l)/2 D.n14.线性表采用链式存储时，其地址3_oA.必须是连续的 B.部分地址必须是连续的C.一定是不连续的 D.连续与否均可以15.设单链表中指针p指着结点(数据域为m),指针f指着将要插入的新结点(数据域为 x),当x插在结点m之后时，只要先修改 B 后修改Iink=f即可。A.f-iink=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.(p-llink)-Hink)-rlink=p;p-llink=(p-nink)-Hink;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.在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上oA.一定相邻 B.不一定相邻 C.有时相邻22.设字符串 sl=abcdefg,s2=pq rst,则运算s=concat(sub(sl,2J en(s2),sub(sl,len(s2),2)后串值为 D。A.bedef B.bedefg*C.*bcpq rsf D.bedefef,23.假定在一棵二叉树中，双分支结点数为15个，单分支结点数为32个，则叶子结点数为 B。A.15 B.16 C.17 D.4724.假定一棵二叉树的结点数为18个，则它的最小高度 B。A.4 B.5 C.6 D.1825.在一棵二叉树中第五层上的结点数最多为 C。A.8 B.15 C.16 D.3226.在一棵具有五层的满二叉树中，结点总数为 A。A.31 B.32 C.33 D.1627.已知8个数据元素为(34、76、45、18、26、54、92、65),按照依次插入结点的方法生成一棵二叉排序树后，最后两层上的结点总数为 BA.1 B.2 C.3 D.428.由分别带权为9、2、5、7的四个叶子结点构造一棵哈夫曼树，该树的带权路径长 度为 C。A.23 B.37 C.44 D.4629.在树中除根结点外，其余结点分成m(m20)个 A 的集合Tl,T2,T3.Tm,每个集合又都是树，此时结点T称为Ti的父结点，Ti称为T的子结点(IWiWm)。A.互不相交 B.可以相交C.叶结点可以相交 D.树枝结点可以相交30.下面答案 D 是查找二叉树(又称二叉排序树)。A.二叉树中的每个结点的两棵子树的高度差的绝对值不大于1B.二叉树中的每个结点的两棵子树的高度差等于1C.二叉树中的每个结点的两棵子树是有序的D.二叉树中的每个结点的关键字大于其左子树(如果存在)所有结点的关键字值，且小于其右子树(如果存在)所有结点的关键字值。31.如果结点A有三个兄弟，而且B是A的双亲，则B的出度是B。A.3 B.4 C.5 D.132.一个深度为L的满K叉树有如下性质：第L层上的结点都是叶子结点，其余各层 上每个结点都有K棵非空子树。如果按层次顺序从1开始对全部结点编号，编号为n的有 右兄弟的条件是 B。A.(n-1)%k=0 B.(n-l)%k!=0 C.n%k=0 D.n%k!=033.在完全二叉树中，当i为奇数且不等于1时，结点i的左兄弟是结点 D,否则没有左兄弟。A.2i-l B.i+1 C.2i+l D.M34.某二叉树T有n个结点，设按某种遍历顺序对T中的每个结点进行编号，编号值 为1,2,n且有如下性质：T中任一结点V,其编号等于左子树上的最小编号减1,而V的 右子树的结点中，其最小编号等于V左子树上结点的最大编号加lo这时按 B 编 号。A.中序遍历序列 B.前序遍历序列 C.后序遍历序列 D.层次遍历序列35.在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的 B 倍。A.1/2 B.1 C.2 D.436.对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则表头向量的大小 为 A。A.n B.n+1 C.n-1 D.n+e37.具有n个顶点的无向完全图，边的总数为 D 条。A.n-1 B.n C.n+1 D.n*(n-l)/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中，若Aij等于1,则AW1等于 C。A.i+j B.i-j C.1 D.O41.图的深度优先或广度优先遍历的空间复杂性均为 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.l B.2 C.3 D.443.散列函数有一个共同性质，即函数值应当以 D 取其值域的每个值。A.最大概率 B.最小概率 C.平均概率 D.同等概率44.设散列地址空间为0m l,k为关键字，用p去除k,将所得的余数作为k的散列 地址，即H（k）=k%p。为了减少发生冲突的频率，一般取D为 D。A.小于m的最大奇数 B.小于m的最大偶数C.m D.小于m的最大素数45.目前以比较为基础的内部排序时间复杂度T（n）的范围是一 A：其比较次数与 待排序的记录的初始排列状态无关的是 BA.O（log2 n）O（n）O（】on2 n）O（n2）O（nlog2 n）O（n2）O（n）O（n2）O（n）O（nlog2B.插入排序 先用二分法查找，找到后插入排序快速排序 冒泡排序46.设关键字序列为：376,9,8,1,4,5,2。进行排序的最小交换次数是 AA.6 B.7 C.8 D.2047.在归并排序过程中，需归芝四趟数为 C。A.n B.V n C.log211 向上取整D.Iog2 n向下取整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；在最 坏情况下（如初始记录已有序），快速排序的时间复杂性为_,空间复杂性为_A_oA.O(n)B.O(log2 n)C.O(nlog2 n)D.O(n2)选择题参考答案：1.B 2.C3.A 4.A5.C 6.C7.D 8,D 9,C 10.C11.B 12.A13.C 14.D15.B 16.B17.A 18.B 19.C 20.A21.B 22.D23.B 24.B25.C 26.A27.B 28.C 29.A 30.D31.B 32.B33.D 34.B35.B 36.A37.D 38.A 39.D 40.C41.A 42.B,D 43.D 44.D45.A:B:46.A 采用选择排序对给定的关键字序列进行排序，只需6次。47.C 48.B49.C 50.C BDA二、填空题1.在线性结构中第一结点11无前驱结点,其余每个结点有且只有12 一个前 驱结点；最后一个结点后继结点，其余每个结点有且只有41 一 个后继结点。2.在树型结构中，树根结点没有11前趋结点,其余每个结点有且仅有，个前驱结点；树叶结点没有F31后继 结点,其余每个结点的41后继 结点数不受限 制。3.一个数据结构用二元组表示时，它包括 数据元素 的集合K和K上 二 元关系的集合Ro*4.对于一个二维数组AL.m,L.n,若按行序为主序存储，则任一元素AiH的相对地 址(即偏移地址)为叩(i-l)*n+j)。5.对于顺序存储的线性表，当随机插入或删除一个元素时，约需平均移动表长11 一 半的元素。6.对于长度为n的顺序表，插入或删除元素的时间复杂性为11 O(n):对于顺序栈 或队列，插入或删除元素的时间复杂性为 1210(1)7.在具有n个单元、顺序存储的循环队列中，队满时共有11 nJ 个元素。8.从顺序表中删除第i个元素时，首先把第i个元素赋给11变参或函数名 带回,接着从2链接指针 开始向后的所有元素均31前移 一个位置,最后使线性表的长度 减1。9.在线性表的顺序存储中，元素之间的逻辑关系是通过 11相邻位置 决定的:在 线性表的链接存储中，元素之间的逻辑关系是通过 121链接指针决定的。10.一个单链表中删除*P结点时，应执行如下操作：(l)q=p-next;(2)p-dat a=p-next-dat a;(3)D-next=1 q onext 或 p-next-next;(4)free(q);11.若要在一个单链表中的*p结点之前插入一个*s结点时，可执行如下操作：(1)s-next=|lp-next;(2)p-next=s;(3)t=p-dat a;(4)p-dat a=21 s-dat a;(5)s-dat a=311;12.对于线性表的顺序存储，需要预先分配好存储空间，若分配太多则容易造成存储空 间的浪费,若分配太少又容易在算法中造成 21溢出，因此适应于数据量变 化不大的情况；对于线性表的链接存储(假定采用动态结点)，不需要 31预先分配 存 储空间，存储器中的整个的动态存储区都可供使用,分配和回收结点都非常方便，能 够有效地利用存储空间，在算法中不必考虑.151溢出的发生,因此适应数据量变化较 大的情况。13.无论对于顺序存储还是链接存储的栈和队列来说，进行插入或删除运算的时间复 杂性均相同，则为 F11O。0 0 2 0-1*14.一个稀疏矩阵为|3 0 0 0|,则对应的三元组线性表为|0 0-1 5 I5 0 0 015.对于一棵具有n个结点的树，则该树中所有结点的度之和为16.在一棵二叉树中，度为0的结点的个数为询,度为2的结点的个数为112,贝IJ：110=i12+1。17.在二叉树的顺序存储中，对于下标为5的结点，它的双亲结点的下标为 112,若它存在左孩子，则左孩子结点的下标为21 10,若它存在右孩子，则右孩子结点的下标为 11。18.假定一棵二叉树的广义表表示为A(B(,D),C(E(G),F),则该树的深度为皿,度为0的结点数为213,度为1的结点数为32,度为2的结点数为42；C结点 是A结点的 右 孩子,E结点是C结点的61左孩子。19.在一棵二叉排序树中，按中序 遍历得到的结点序列是一个有序序列。20.由分别带权为3,9,6,2,5的共五个叶子结点构成一棵哈夫曼树，则带权路径长度为55。21.假定在二叉树的链接存储中，每个结点的结构为I left|dat a|right|,其中dat a为值域，left和right分别为链接左、右孩子结点的指针域，请在下面中序遍历算法 中画有横线的地方填写合适的语句。void inorder(bt);if bt!=nil(1)1 inorder(bt-】eft)；print f(bt-dat a)；(3)inorder(bt-rieht)；)22.在图G的邻接表表示中，每个顶点邻接表中所含的结点数，对于无向图来说等于 该顶点的11度数，对于有向图来说等于该顶点的21出度数。23.假定一个图具有n个顶点和e条边，则采用邻接矩阵表示的空间复杂性为 0(7),采用邻接表表示的空间复杂性为f21O(n+e)。24.已知一个无向图的邻接矩阵如下所示,则从顶点A出发按深度优先搜索遍历得到的 顶点序列为11ABCDFE,按广度优先搜索遍历得到的顶点序列为 21ABCEFD。25.已知一个图如下所示，在该图的最小生成树中，各边的权值之和为 示1026.假定在有序表A1.2O上进行二分查找,则比较一次查找成功的结点数为ILL，比 较两次杳找成功的结点数为1212,比较三次查找成功的结点数为驻L，比较四次查找成 功结点数为1418,比较五次查找成功的结点数为1515,平均查找长度为613.7。27.在索引查找或分块查找中，首先查找 弓索引表，然后再查找相应的2 子表或块，整个索引查找的平均查找长度等于查找索引表的平均查找长度与查找相应子 表的平均查找长度之 31和。28.在散列存储中，装填因子a的值越大，存取元素时发生冲突的可能性就11越大,当a的值越小，存取元素时发生冲突的可能性就21越小。29.给定线性表(18,25,63,50,42,32,90),用散列方式存储，若选用h(K)=K%9作为散列 函数，则元素18的同义词元素共有”2 个,元素25的同义词元素共有120个,元素 50的同义词元素共有个。30.在对一组记录(54,38,96,23,15,72,60,45,83)进行直接选择排序时，第四次选择和交换 后，未排序记录(即无序表)为(54,72,60,96,83)。31.在对一组记录(54,38,96,23,15,72,60,458)进行冒泡排序时，第一趟需进行相邻记录 交换的次数为17,在整个冒泡排序过程中共需进行25 趟后才能完成。32.在归并排序中，若待排序记录的个数为20,则共需要进行“15趟归并,在第三 趟归并中，是把长度为124的有序表归并为长度为-318的有序表。33.在直接插入和直接选择排序中，若初始数据基本正序，则选用11直接插入排 序，若初始数据基本反序，则选用-2直接选择排序.34.在堆排序、快速排序和归并排序中，若只从节省空间考虑，则应首先选取J 11堆 排序 方法，其次选取21快速排序 方法,最后选取 131归并排序 方法:若只从 排序结果的稳定性考虑，则应选取4归并排序；若只从平均情况下排序最快考虑，则 应选取 51快速排序 方法:若只从最坏情况下排序最快并且要节省内存考虑，则应选 取 61堆排序方法。填空题参考答案1.1无一3无一2.1前趋一3后继4后继3.1数据元素2二元关系4.l(i-l)*n+j-l5.1一半6.lO(n)2O(l)7.ln-l 预先8.1变参或函数名第i+1个元素3前移减19.1相邻位置链接指针10.lq-next 或 p-next-nextll.lp-next2s-dat a3t12口浪费溢出3预先分配4动态存储区溢出13.lO(l)14.1(1,3,2),(2,1,3)式33,-1),(3,4,5)15.ln-l16.ln2+117.121031118.14332425右 6左19.口中序20.15521.linorder(bt-Ieft)2print f(bt-dat a)3inorder(bt-right)22.1度数2出度数23.lO(n2)O(n+e)24.1ABCDFE2ABCEFD25.12026.11234485563.727.1索引表子表或块3和28.1越大越小29.12203130.1(54,72,60,96,83)31.172532.15243833.1直接插入排序直接选择排序34.1堆排序快速排序3归并排序4归并排序5快速排序6堆排序三、判断题1.数据元素是数据的最小单位（X）。2.数据项是数据的基本单位（X）。3.顺序存储的线性表可以随机存取（V）04.线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性,因此，是属于同一数据对象（V）o5.在单链表中，任何两个元素的存储位置之间都有固定的联系，因为可以从头结点查 找任何一个元素（X）06.在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机 存取的存储结构（X）。7.链表的每个结点中，都恰好包含一个指针（X）。*8.数组是同类型值的集合（X）。不是集合*9.使用三元组表示稀疏矩阵的元素，有时并不能节省存储时间（J）。*10.线性表可以看成是广义表的特例，如果广义表中的每个元素都是原子，则广义表便 成为线性表（J）。11.由树转换成二叉树，其根结点的右子树总是空的（J）。12.后序遍历树和中序遍历与该树对应的二叉树，其结果不同（X13.若有一个结点是某二叉树子树的中序遍历序列中的最后一个结点，则它必是该子 树的前序遍历序列中的最后一个结点（X）。14.若一个树叶是某子树的中序遍历序列中的最后一个结点，则它必是该子树的前序 遍历序列中的最后一个结点（V）o15.已知二叉树的前序遍历和后序遍历序列并不能唯一地确定这棵树，因为不知道树 的根结点是哪一个（X）。16.在哈夫曼编码中，当两个字符出现的频率相同时，其编码也相同，对于这种情况应 作特殊处理（X）。17.有回路的图不能进行拓扑排序（V）018.连通分量是无向图中的极小连通子图（X）。极大19.散列法存储的基本思想是由关键码的值决定数据的存储地址（V）。20.散列表的查找效率取决于散列表造表时选取的散列函数和处理冲突的方法（V）o21.m阶B-树每一个结点的子树个数都小于或等于m（V）。22.中序遍历二叉排序树的结点就可以得到排好序的结点序列（V）。23.在二叉排序树上插入新的结点时，不必移动其它结点，仅需改动某个结点的指针，由空变为非空即可（J）o24.当待排序的元素很多时，为了交换元素的位置，移动元素要占用较多的时间，这是 影响时间复杂性的主要因素（V）o25.对于n个记录的集合进行快速排序，所需要的平均时间是O（nlog2 n）（J）。26.对于n个记录的集合进行归并排序，所需要的平均时间是O（nlog2 n）（V）。27.堆中所有非终端结点的值均小于或等于（大于或等于）左右子树的值（V）o*28.磁盘上的顺序文件中插入新的记录时，必须复制整个文件（X）。*29.在索引顺序文件中插入新的记录时，必须复制整个文件（X）。*30.索引顺序文件是一种特殊的顺序文件，因此通常存放在磁带上（X）。判断题参考答案1.X2.X3.J4.V5.X6.X7.X8.X9.J10.V11.V12.X13.X14.V15.X16.X17.V18.X19.V20.V21.V22.V23.V24.V25.J26.V27.V28.X29.X30.X四、综合题1.线性表有两种存储结构：一是顺序表，二是链表。试问：（1）两种存储表示各有哪些主要优缺点？（2）如果有n个线性表同时并存，并且在处理过程中各表的长度会动态发生变化，线性 表的总数也会自动地改变。在此情况下，应选用哪种存储结构?为什么？（3）若线性表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取线性 表中的元素，那么，应采用哪种存储结构?为什么？1.解答：（1）顺序存储是按索引（隐含的）直接存取数据元素，方便灵活，效率高，但插入、删 除操作时将引起元素移动，因而降低效率；链接存储内存采用动态分配，利用率高，但需增 设指示结点之间有序关系的指针域，存取数据元素不如顺序存储方便，但结点的插入、删除 操作十分简单。（2）应选用链接表存储结构。其理由是，链式存储结构用一组任意的存储单元依次存储 线性表里各元素，这里存储单元可以是连续的，也可以是不连续的。这种存储结构，在对元 素作插入或删除运算时，不需要移动元素，仅修改指针即可。所以很容易实现表的容量扩充。（3）应选用顺序存储结构。其理由是，每个数据元素的存储位置和线性表的起始位置相 差一个和数据元素在线性表中的序号成正比的常数。由此，只要确定了起始位置，线性表中 任一数据元素都可随机存取，所以线性表的顺序存储结构是一种随机存取的存储结构。而链 表则是一种顺序存取的存储结构。_2.用线性表的顺序结构来描述一个城市的设计和规划合适吗?为什么?2.解答：不合适。因为一个城市的设计和规划涉及非常多的项目，很复杂，经常 需要修改、扩充和删除各种信息，才能适应不断发展的需要。有鉴于此，顺序线性表不能很好适应其需要，故是不合适的。_3在单链表和双向表中，能否从当前结点出发访问到任一结点?3.解答：在单链表中只能由当前结点访问其后的任一结点，因为没有指向其前 驱结点的指针。而在双向链表中，既有指向后继结点的指针又有指向前驱结点的指针，故 可由当前结点出发访问链表中任一结点。_4.试述栈的基本性质?4.解答：由栈的定义可知，这种结构的基本性质综述如下：(1)集合性。栈是由若干个元素集合而成，当没有元素的空集合称为空栈；(2)线性结构。除栈底元素和栈顶元素外，栈中任一元素均有唯一的前驱元素和后继元 素；(3)受限制的运算。只允许在栈顶实施压入或弹出操作，且栈顶位置由栈指针所指示；(4)数学性质。当多个编号元素依某种顺序压入，且可任意时刻弹出时，所获得的编号元素 排列的数目，恰好满足卡塔南数列的计算，即：C n=C n 2n/(n+l)其中，n为编号元素的个数，Cn是可能的排列数目。5.何谓队列的上溢现象?解决它有哪些方法，且分别简述其工作原理。5.解答：在队列的顺序存储结构中，设队头指针为队尾指针为rear,队的容 量(存储空间的大小)为m。当有元素要加入队列时，若uar=m(初始时irat=O),赈 生队列的上溢现象，该元素不能加入队列。这里要特别注意的是：队列的假溢出现象，队列中还有空余的空间，但元素不能进队 列。造成这种现象的原因是由于队列的操作方式所致。解决队列的上溢有以下几种方法：(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又有两棵子树等等，该广义表对应的树型结构见下图。*8.对于二叉排序树，当所有结点的权都相等的情况下，最佳二叉排序树有何特点。_8.解答:其特点是只有最下面的二层结点可以小于2,其它结点的度数必须为2。9.试证明：已知一棵二叉树的前序序列和中序序列，则可唯一地确定一棵二叉树。9.证明利用前序遍历的结果序列能够得到各子树的根，即从左到右检查前序遍历序列，当得 到根结点之后，利用根结点在中序遍历序列中的位置可以确定其左右子树，这样便可逐次确 定整个二叉树。假设BT为二叉树的根，Pi,P2,，Pn为前序遍历序列，h，功，In为 中序遍历序列。由前序遍历序列可以得到RT=Pi。在中序遍历序列中查找等于P1的结点，设该结点为li,则有li=P1。根据二叉树中序遍历的原理，则该二叉树可被分成左右两棵子树：对于左子树，在中 序遍历序列中有II,12,Ii-1,依此序列在前序遍历序列中可以得到其左子树为 P2,P3,，Pi；同理，对于右子树有Ii+1,Ii+2,，InPi+1,Pi+2,，Pn对于这两棵子树而言，其左子树的根为P2,其右子树的根为Pi+1。依此类推，用同样的方法就可以确定整个二叉树。10.证明n个顶点的无向完全图的边数的n(n1)/2。10.证明方法一：用归纳法证明当n=l时，边数为0,结论成立。当n=2时，边数为1,结论成立。当n=l,2,k时均成立，即当n=k时，边数为k(k1)/2。现证明当n=k+l时若仍 然成立，则结论正确。由前面证得，对于有k个顶点时，其边数总和为k(k-l)/2o当再增加一个新顶点时，由于是无向完全图，故该顶点到原来各个顶点均有一条边，这 样就共有边数为k(k-l)/2+k=k(k+l)/2=(k+l)(k+1)-1/2可知当顶点数k+1时，结论仍然成立，故具有n个顶点的无向完全图的这数为n(n1)/2方法二：在n个顶点的无向完全图中，每个顶点与其余各顶点均有一条边。第一个顶点到其余 各顶点的边数为nl,第二个顶点到其余各顶点的边数为nL但它与第一个顶点之间的 边已在第一个顶点的边中，故第二个顶点到其它n-2个顶点的边为n-2,，第nl个到 余下的第n个顶点为边数为1,所以总的边数为(nl)+(n-2)+(n3)+2+l=n(n-1)/2所以其结论成立。11.证明一个有n个顶点，e条边的无向图G,必有Ldj=2e其中dj为顶点j的度。11.证明由度的定义可知，顶点j所联接的边数必为dj条，另一方面，图G中的任一条边均 关联G中的两个顶点，即一条边均要分别计入两个不同的dj和di中，故dj中的边数 应为G中边数的两倍，即有n4=2ei-112.证明：若无向图G的顶点度数的最小值大于或等于2,则G有一条回路。12.证明方法一：设G=(V,E),任取一顶点vi eV,因Vi的度大于或等于2,在vi的邻接顶点中任 取一个不同于vi的顶点作为V2。因V2的度大于或等于2,在V2的邻接顶点中任取一个不 同于V2的顶点作为V3。若V、V2、V3不构成回路，则在再V3的邻接顶点中任取一 个不同于V3的的顶点作为V4,o因为图中顶点的集合V是有限的，当取得某个顶 点vi后，vi+1 一定为vl,v2，vi-1之一，因而构成回路。命题得证。方法二：设图G有n个顶点，整个图G的度数之和为N,则有N22n我们知道，图中每条边涉及二个顶点，也就是每条边含有2个度，这样一来，该图G 至少有n条边。由于一个n个顶点的树图只有nl条边，多于nl条边时则树图就不存 在，图中会出现回路。由前面推得，该图至少有n条边，故会出现回路。_13.若对大小均为n的有序的顺序表和无序的顺序表分别进行顺序查找，试问在下面三种情 况下，分别讨论两者在等概率时，平均查找长度是否相同？(1)查找不成功，即表中没有关键字等于给定值k的记录；(2)查找成功，且表中只有一个关键字等于给定值k的记录；(3)查找成功，且表中有若干个关键字等于给定值k的记录，一次查找要求找出所有记 录，此时的平均查找长度应考虑找到所有记录时所用的比较次数。13.(1)解答:不相同。对于有序的顺序表而言，当表中无此关键字时，只要在查找 过程中发现顺序表中的某个关键字大于待查的关键字时，查找过程就可以结束(假定顺序表 是由小到大排列的，对于由大到小排列的情况类似)，没有必要查找到表中最后一个关键字 才确定查找不成功。而对于非有序的顺序表，只有对表中的每一个关键字比较完之后，才能 说明查找不成功。显然在等概率时两种顺序的平均查找长度是不相同的。有序顺序表的平均 长度为(n+l)/2,而无序顺序表的平均查找长度为n0但从数量级上两者是相同的，即O(n)。(2)解答:相同的。其分析类似于(1)。两者在等概率下的平均长度为(n+l)/2,数量级 上为O(n)。(3)解答:不相同。其分析完全与(1)相同，其结论也完全相同。_14.假定有n个关键字，它们具有相同的Hash函数值，用线性探测方法把这n个关键字存 入到Hash地址空间中要做多少次探测？14.解答:由于线性探测的查找次数主要取决于装载因子a,即与Hash地址空间 的占用情况 有关。假定初始时Hash地址空间为空，在此情况下连续装入n个具有相同的 Hash函数值的关键字所需的总探测次数为H-2+,+n=n(n+l)/215.有一个2000项的表，欲采用等分区间顺序查找方法进行查找，问(1)每块的理想长度是多少？(2)分成多少块最为理想？(3)平均查找长度是多少？(4)若每块长度为20,平均查找长度是多少？15.解答：(1)在给定n的前提下，理想的块长d为右=71而(2)因查找方法为等分区间顺序查找，长度为n的表被分成b=n/d块，d为块长，故 有b=n/d=2000/45=45(3)平均查找长度为ASL=b+d/2+1=(45+45)/2+1=46(4)因每块的长度为20,所以表被分成b块，其平均查找ASL长度为b=n/d=2000/20=100ASL=(b+d)/2+l=(100+20)/2+l=6116.在执行某种排序算法的过程中，出现了排序码朝着最终排序序列相反的方向移动，从而 认为该排序算法是不稳定的，这种说法对吗?为什么？16.解答:这种说法不对。因为排序的不稳定性是指排序前两个排序码相同的元 素的相对次序经过排序后发生了变化，而题中未涉及到元素的相对次序(特别是相同排序 码的元素)的改变，只有移动方向，所以此种说法不对。17.设有5000个无序的元素，希望用最快速度挑选出其中前10个最大的元素。在以下 的排 序方法中，采用哪种方法最好?为什么？快速排序，堆排序，归并排序，基数排序的Shell排序。17.解答:上面所列的几种排序方法的速度都很块，但快速排序、归并排序、基数排 序和希尔排序都是在排序结束后才能确定数据元素的全部顺序，而无法知道排序过程中部分 元素的有序性。而堆排序则每次输入一个最大(或最小)的元素，然后对堆进行调整，保证 堆顶的元素总是余下元素中最大(或最小)的。根据题意，只要选取前10个最大的元素，故采用堆排序方法是合适的。*18.证明对一个长度为n的任意文件进行排序，至少需要作nlog2 n比较。18.证明在排序过程中，每次时行元素的比较产生两种路径。如果排序过程至少需作t次比较，则有2t条路径。由于n个结点总共有n种不同的排列，因而必须有n种不同的比较路径。于是 2tn!即 t elog2 n!因为 log2 n!=nlog2 nn/ln2+l/21og2 n+O(l)故有 log2 n!=nlog2 ntnlog2 n证毕。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.解答:根据堆的定义可知堆中元素满足下面中的某一个式子的关系,-42i 2k2ikg 或 3-Wk2i+1 L2k2i+l因此(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个元素(OWiWLJ en)之