《数据结构与算法习题及答案》由会员分享，可在线阅读，更多相关《数据结构与算法习题及答案（55页珍藏版）》请在金锄头文库上搜索。
1、第 1 章 绪论习题1简述下列概念：数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储 结构、抽象数据类型。 2试举一个数据结构的例子，叙述其逻辑结构和存储结构两方面的含义和相互关系。 3简述逻辑结构的四种基本关系并画出它们的关系图。 4存储结构由哪两种基本的存储方法实现？ 5选择题 （1）在数据结构中，从逻辑上可以把数据结构分成（ ） 。 A动态结构和静态结构 B紧凑结构和非紧凑结构 C线性结构和非线性结构 D内部结构和外部结构 （2）与数据元素本身的形式、内容、相对位置、个数无关的是数据的（ ） 。 A存储结构 B存储实现 C逻辑结构 D运算实现 （3）通常要求同一逻辑结构中的所有
2、数据元素具有相同的特性，这意味着（ ） 。A数据具有同一特点 B不仅数据元素所包含的数据项的个数要相同，而且对应数据项的类型要一致 C每个数据元素都一样 D数据元素所包含的数据项的个数要相等 （4）以下说法正确的是（ ） 。 A数据元素是数据的最小单位 B数据项是数据的基本单位 C数据结构是带有结构的各数据项的集合 D一些表面上很不相同的数据可以有相同的逻辑结构 （5）以下与数据的存储结构无关的术语是（ ） 。 A顺序队列 B. 链表 C. 有序表 D. 链栈 （6）以下数据结构中， （ ）是非线性数据结构 A树 B字符串 C队 D栈 6试分析下面各程序段的时间复杂度。 （1）x=90; y=
3、100; while(y0) if(x100)x=x-10;y-; else x+; （2）for (i=0; i1 y=0;while(x(y+1)* (y+1)y+;（1）O（1） （2）O（m*n） （3）O（n2） （4）O（log3n） （5）因为 x+共执行了 n-1+n-2+1= n(n-1)/2，所以执行时间为 O（n2）（6）O()n第 2 章 线性表1选择题 （1）一个向量第一个元素的存储地址是 100，每个元素的长度为 2，则第 5 个元素的 地址是（ ） 。 A110 B108 C100 D120 （2）在 n 个结点的顺序表中，算法的时间复杂度是 O(1)的操作是（
4、） 。 A访问第 i 个结点（1in）和求第 i 个结点的直接前驱（2in） B在第 i 个结点后插入一个新结点（1in） C删除第 i 个结点（1in） D将 n 个结点从小到大排序 （3） 向一个有 127 个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要 移动 的元素个数为（ ） 。 A8 B63.5 C63 D7 （4）链接存储的存储结构所占存储空间（ ） 。 A分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针 B只有一部分，存放结点值 C只有一部分，存储表示结点间关系的指针 D分两部分，一部分存放结点值，另一部分存放结点所占单元数 （5）线性表若采用链式存储结构时
5、，要求内存中可用存储单元的地址（ ） 。 A必须是连续的 B部分地址必须是连续的 C一定是不连续的 D连续或不连续都可以 （6）线性表在（ ）情况下适用于使用链式结构实现。 A需经常修改中的结点值 需不断对进行删除插入 C中含有大量的结点 中结点结构复杂 （7）单链表的存储密度（ ） 。 A大于 1 B等于 1 C小于 1 D不能确定 （8）将两个各有 n 个元素的有序表归并成一个有序表，其最少的比较次数是（ ） 。 An B2n-1 C2n Dn-1 （9）在一个长度为 n 的顺序表中，在第 i 个元素（1in+1）之前插入一个新元素 时须向后移动（ ）个元素。 An-i Bn-i+1 Cn
6、-i-1 Di (10) 线性表 L=(a1，a2,an)，下列说法正确的是（ ） 。 A每个元素都有一个直接前驱和一个直接后继 B线性表中至少有一个元素 C表中诸元素的排列必须是由小到大或由大到小 D除第一个和最后一个元素外，其余每个元素都有一个且仅有一个直接前驱和直 接后继。 (11) 若指定有 n 个元素的向量，则建立一个有序单链表的时间复杂性的量级是（ ） 。AO(1) BO(n) CO(n2) DO(nlog2n) (12) 以下说法错误的是（ ） 。 A求表长、定位这两种运算在采用顺序存储结构时实现的效率不比采用链式存储 结构时实现的效率低 B顺序存储的线性表可以随机存取 C由于顺
7、序存储要求连续的存储区域，所以在存储管理上不够灵活 D线性表的链式存储结构优于顺序存储结构 (13) 在单链表中，要将 s 所指结点插入到 p 所指结点之后，其语句应为（ ） 。 As-next=p+1; p-next=s; B(*p).next=s; (*s).next=(*p).next; Cs-next=p-next; p-next=s-next; Ds-next=p-next; p-next=s; (14) 在双向链表存储结构中，删除 p 所指的结点时须修改指针（ ） 。 Ap-next-prior=p-prior; p-prior-next=p-next; Bp-next=p-nex
8、t-next; p-next-prior=p; Cp-prior-next=p; p-prior=p-prior-prior; Dp-prior=p-next-next; p-next=p-prior-prior; (15) 在双向循环链表中，在 p 指针所指的结点后插入 q 所指向的新结点，其修改指针 的操作是（ ） 。 Ap-next=q; q-prior=p; p-next-prior=q; q-next=q; Bp-next=q; p-next-prior=q; q-prior=p; q-next=p-next; Cq-prior=p; q-next=p-next; p-next-pr
9、ior=q; p-next=q; Dq-prior=p; q-next=p-next; p-next=q; p-next-prior=q;2算法设计题 （1）将两个递增的有序链表合并为一个递增的有序链表。要求结果链表仍使用原来两 个链表的存储空间, 不另外占用其它的存储空间。表中不允许有重复的数据。void MergeList_L(LinkList pb=Lb-next;Lc=pc=La; /用 La 的头结点作为 Lc 的头结点 while(pa pc=pa;pa=pa-next;else if(pa-datapb-data) pc-next=pb; pc=pb; pb=pb-next;el
10、se / 相等时取 La 的元素，删除 Lb 的元素pc-next=pa;pc=pa;pa=pa-next;q=pb-next;delete pb ;pb =q;pc-next=pa?pa:pb; /插入剩余段 delete Lb; /释放 Lb 的头结点 （2）将两个非递减的有序链表合并为一个非递增的有序链表。要求结果链表仍使用原 来两个链表的存储空间, 不另外占用其它的存储空间。表中允许有重复的数据。void union(LinkList pb = Lb-next; / 初始化Lc=pc=La; /用 La 的头结点作为 Lc 的头结点 Lc-next = NULL;while ( pa
11、| pb ) if ( !pa ) q = pb; pb = pb-next; else if ( !pb ) q = pa; pa = pa-next; else if (pa-data data ) q = pa; pa = pa-next; else q = pb; pb = pb-next; q-next = Lc-next; Lc-next = q; / 插入delete Lb; /释放 Lb 的头结点 （3）已知两个链表 A 和 B 分别表示两个集合，其元素递增排列。请设计算法求出 A 与 B 的交集，并存放于 A 链表中。void Mix(LinkListpb=lb-next;设
12、工作指针 pa 和 pb； Lc=pc=La; /用 La 的头结点作为 Lc 的头结点whilewhile(papc=pa;pa=pa-next;u=pb;pb=pb-next; delete u;elseelse ifif(pa-datadata) u=pa;pa=pa-next; delete u; elseelse u=pb; pb=pb-next; delete u; whilewhile(pa) u=pa; pa=pa-next; delete u; 释放结点空间 whilewhile(pb) u=pb; pb=pb-next; delete u;释放结点空间 pc-next=nu
13、ll;置链表尾标记。 delete Lb; 注： 本算法中也可对 B 表不作释放空间的处理（4）已知两个链表 A 和 B 分别表示两个集合，其元素递增排列。请设计算法求出两个 集合 A 和 B 的差集（即仅由在 A 中出现而不在 B 中出现的元素所构成的集合） ，并以同样 的形式存储，同时返回该集合的元素个数。 voidvoid Difference（LinkedList A，B，*n） A 和 B 均是带头结点的递增有序的单链表，分别存储了一个集合，本算法求两集合的 差集，存储于单链表 A 中，*n 是结果集合中元素个数，调用时为 0 p=A-next； p 和 q 分别是链表 A 和 B
14、的工作指针。q=B-next； pre=A； pre 为 A 中 p 所指结点的前驱结点的指针。whilewhile（p!=null pmax=L-next; /假定第一个结点中数据具有最大值p=L-next-next; while(p != NULL )/如果下一个结点存在if(p-data pmax-data) pmax=p; p=p-next; return pmax-data;（7）设计一个算法，通过遍历一趟，将链表中所有结点的链接方向逆转，仍利用原表 的存储空间。void inverse(LinkList L-next=NULL;while ( p) q=p-next; / q 指向*p 的后继p-next=L-next;L-next=p; / *p 插入在头结点之后p = q; （8）设计一个算法，删除递增有序链表中值大于 mink 且小于 maxk 的所有元素（mink 和
