《计算机软件技术基础》课后题答案

1 数据结构习题答案 第一节 概 论 一、选择题 1要求同一逻辑结构的所有数据元素具有相同的特性，这意味着 ( )。 A数据元素具有同一的特点 *B不仅数据元素包含的数据项的个数要相同，而且对应数据项的类型要一致 C每个数据元素都一样 D数据元素所包含的数据项的个数要相等 2数据结构是一门研究非数值计算的程序设计问题中计算机的 ( (1) )以及它们之间的 ( (2) )和运算的学科。 (1) A操作对象 B计算方法 *C物理存储 D数据映像 (2) A结构 *B关系 C运算 D算法 3数据结构被形式地定义为 (D， R)，其中 D 是 ( (1) )的有限集合， R 是 D 上 ( (2) )的有限集合。 (1) A算法 *B数据元素 C数据操作 D逻辑结构 (2)A操作 B映像 C存储 *D关系 4在数据结构中，从逻辑上可以把数据结构分为 ( )。 A动态结构和静态结构 B紧凑结构和非紧凑结构 *C线性结构和非线性结构 D内部结构和外部结构 5线性表的顺序存储结构是一种 ( )的存储结 构。 2 *A随机存取 B顺序存取 C索引存取 D 6算法分析的目的是 ( )。 A找出数据结构的合理性 B研究算法中的输入和输出的关系 *C分析算法的效率以求改进 D分析算法的易懂性和文档性 7计算机算法指的是 ( (1) )，它必须具备输入、输出和 ( (2) )等五个特征。 (1) A计算方法 B排序方法 *C解决某一问题的有限运算序列 D调度方法 (2) A可行性、可移植性和可扩充性 *B可行性、确定性和有穷性 C 确定性，有穷性和稳定性 D易读性、稳定性和安全性 8线性表若采用链表存储结构，要求内存中可用存储单元的地址 ( )。 A必须是连续的 B部分必须是连续的 C一定是不连续的 *D连续不连续都可以 9在以下的叙述中，正确的是 ( )。 A线性表的线性存储结构优于链式存储结构 *B二维数组是它的每个数据元素为一个线性表的线性表 C栈的操作方式是先进先出 D队列的操作方式是先进后出 10根据数据元素之间关系的不同特性，以下四类基本的逻辑结构反映了四类基本的数 据组织形式，其中 3 解释错误的是 ( )。 *A集合中任何两个结点之间都有逻辑关系但组织形式松散 B线性结构中结点按逻辑关系依次排列形成一条“锁链” C树形结构具有分支、层次特性，其形态有点像自然界中的树 D图状结构中的各个结点按逻辑关系互相缠绕，任何两个结点都可以邻接 11以下说法正确的是 ( )。 A数据元素是数据的最小单位 B数据项是数据的基本单位 C数据结构是带有结构的各数据项的集合 *D数据结构是带有结构的数据元素的集合 二、判断题 1数据元素是 数据的最小单位。 2数据结构是带有结构的数据元素的集合。 3数据结构、数据元素、数据项在计算机中的映像分别称为存储结构、结点、数据域。 4数据项是数据的基本单位。 5数据的逻辑结构是指各数据元素之间的逻辑关系，是用户按使用需要建立的。 6数据的物理结构是数据在计算机中实际的存储形式。 7算法和程序没有区别，所以在数据结构中二者是通用的。 8顺序存储结构属于静态结构，链式存储结构属于动态结构。 4 三、填空题 1所谓数据的逻辑结构指的是数据元素之间的 _逻辑关系 _。 2， 数据结构是相互之间存在一种或多种特定关系的数据元素的集合，它包括三方面的内容 _数据的逻辑结构、数据的存储结构、对数据施加的操作 _。 3数据的逻辑结构包括 _集合结构 _、 _线性结构 _、 _树型结构 _和 _图状结构 _四种类型。 4在线性结构中，开始结点 _没有 _前驱结点，其余每个结点有且只有 _一个 _个前驱结点。 5在树形结构中，根结点只有 _一个 _，其余每个结点有且只有 _一个 _前驱结点；叶结点没有 _后继 _结点，其余每个结点的后继结点可 以有 _任意个_ 6在图形结构中，每个结点的前驱结点和后继结点可以有 _任意个 _。 7算法的五个重要特性是 _可行性 _、 _确定性_、 _有穷性 _、 _输入 _、 _输出 _。 8下列程序段的时间复杂度是 _O（ n） _。 (i=1； i， ， ， ， ， ， ， ， ， ，画出这个逻辑结构的图示，并确定相对于关系 R，哪些结点是开始结点，哪些结点是终端结点？ 答：图略。开始结点 端结点 7设有如图 示的逻辑结构图，给出它的逻辑结构，并说出它是什么类型的逻辑结构。 答：数据逻辑结构为： D=， R=， ， ， ， ， ， ，其逻辑结构类型为树型结构。 8分析下列程序的时间复杂度 (设 n 为正整数 )。 (1)n) if(n=1) ； n*； (2)x=91； y=100； y0) if(x10) (3)i=1； j=0； i+jj)j+； i+; (4)x=n； y=0； x=(y+1)*(y+1) y+； 答： (1) O(n) (2) O(1) (3) O(n) (4) O() 9 设 n 为正数。试确定下列各程序段中前面加记号 的语句的频度： (1)i=1； k=0； C D 0非空单循环链表 尾结点 *p 满足 ( )。 A p- B p= *C p- D p=1在双循环链表的 *p 结点之后插入 *s 结点的操作是( )。 A p-s； s-p； p-s；s-p- B p-s ；p-s； s-p： s-p- C s-p ； s-p- p-s ； 11 p-s ； *D s-p ；s-p-p-s； p-s； 12. 在一个单链表中，已知 *q 结点是 *p 结点的前驱结点，若在 *q 和 *p 之间插入结点 *s，则执行 ( )。 A s-p- p-s ； B p-s-s-p； *C q-s; s-p； D p-s; s-q； 13. 在一个单链表中，若 *p 结点不是最后结点。在 *s，则执行 ( )。 A s-p； p-s; *B s-p-p-s； C s-p- p=s； D p-s； s-p; 14. 若某线性表中最常用的操作是取第 i 个元素和找第 i 个元素的前驱元素，则采用 ( )存储方式最节省时间。 *A顺序表 B. 单链表 C双链表 D单循环链表 15设 删除表头结点的操作可表示为 ( )。 A p= p) B ； C ； *D p= 12 p-p)； 16在一个单链表中，若删除 *p 结点的后继结点，则执行 ( )。 *A q=p- p-q- q) ； B p=p-p-p-p)； C p-p- p-； D p=p-p- 17 设指针 p 指向双链表的某一结点，则双链表结构的对称性可用 ( )式来刻画。 A p-=p-B p-p-*C p-=p-D p-p-8在循环链表中，将头指针改设为尾指针 ，其头结点和尾结点的存储位置分别是 ( )。 A *B C D 9循环链表的主要优点是 ( )。 A不再需要头指针了 B已知某个结点的位置后，容易找到它的直接前驱 C在进行插入、删除操作时，能更好地保证链表不断开 *D从表中任一结点出发都能扫描到整个链表 20在线性表的下列存储结构中，读取元素花费时间 13 最少的是 ( )。 A单链表 B双链表 C循环链表 *D顺序表 二、判断题 1顺序存储的线性表可以随机存取。 2顺序存储的线性表的插入和删除操作不需要付出很大的代价，因为平均每次操作只有近一半的元素需要移动。 3线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此是属于同一数据对象。 4在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上不一定相邻。 5在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻。 6在单链表中，可以从头结点开始查找任何一个元素。 7线性表的链式存储结构优于顺序存储结构。 8在线性表的顺 序存储结构中，插入和删除元素时，移动元素的个数与该元素的位置有关。 9在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。 10顺序存储方式只能用于存储线性结构。 三、填空题 14 1为了便于讨论，有时将含 n(n0)个结点的线性结构表示成 (， 其中每个 表一个 _结点 _。 为 _第一个 _结点， 为 _最后一个 _结点，i 称为 线性表中的 _位置 _。对任意一对相邻结点(1 p-q-q)； _ 6非空的单循环链 表 尾结点 (由指针 p 所指 )满足 _ p-_。 7 指向非空带头结点的单循环链表的尾指针，则删除起始结点的操作可表示为 _ p=q=p-p-q-q)； _。 8对于一个具有 n 个结点的单链表，在 p 所指结点后插入一个结点的时间复杂度为 _O(1)_，在给定值为 _ O(n)_。 15 9单链表表示法的基本思想是用 _指针 _表示结点间的逻辑关系。 10 在顺序表中插入或删除一个元素，平均需要移动 _一半 _元素，具体移动的元素个数与 _元素的位置 _有关。 11在一个长度为 n 的向量的第 i(1 i n+1)个元素之前插入一个元素时，需向后移动 _ _个元素。 12在一个长度为 n 的向量中删除第 i(1 i n)个元素时，需向前移动 _ _个元素。 13在双链表中，每个结点有两个指针域，一个指向_前驱 _，另一个指向 _后继 _。 14在一个带头结点的单循环链表中， p 指向尾结点的直接前驱，则指向头结点的指针 用 p 表示为_ p- _。 15设 向单链表的表头， p 指向单链表的表尾结点，则执行 p-，该单链表构成 _单循环链表 _。 16在单链表中，若 p 和 s 是两个指针，且满足 p-语句 p-s-删除 _ 17设 r 指向单循环链表的最后一个结点，要在最后一个结点之后插入 s 所指的结点，需执行的三条语句是 _s-r-_； r-s； r=s； 18在单链表中，指针 p 所指结点为最后一个结点的 16 条件是 _ p- 19在双循环链表中，若要在指 p 所指结点前插入 需执行下列语句： s-p； s-p- _ p-_=s ；p-s； 20在单链表中，若要在 p 所指结点之前插入 s 所指的结点，可进行下列操作： s-_ p-_； p-s； p- p-_ s-_； s-_ ； 四、应用题 1描述以下三个概念的区别：头指针，头结点，首元结点 (第一个元素结点 )。 答：首元结点是指链表中存储的线性表中的第一个数据元素的结点。为了操作方便，通常在链表的首元结点之前附设一个结点，称为头结点。头指针是指向链表中的第一个结点的指针。 2何时选用顺序表，何时选用链表作为线性表的存储结构为宜？ 答：从空间上来看，当线性表的长度变化较大、难以估计其规模时，选用动态的链表作为存储结构比较合适，但链表除了需要设置数据域外，还要额外设置指针域，因 此当线性表长度变化不大、易于事先确定规 17 模时，为了节约存储空间，宜采用顺序存储结构。从时间上来看，若线性表的操作主要是查找，很少进行插入和删除操作时，应选用顺序表。对于频繁进行插入和删除操作的线性表，宜采用链表作为存储结构。 3在顺序表中插入和删除一个结点需平均移动多少个结点？具体的移动次数取决于哪两个因素？ 答：平均移动表中大约一半的结点，插入操作平均移动 n/2 个结点，删除操作平均移动（ 。具体移动的次数取决于表长和插入、删除的结点的位置。 4为什么在单循环链表中设置尾指针比设置头指 针更好？ 答：单循环链表中无论设置尾指针还是头指针都可以遍历表中任一个结点，但设置尾指针时，若在表尾进行插入或删除操作可在 O(1)时间内完成，同样在表头进行插入或删除操作也可在 O(1)时间内完成。但若设置的是头指针，表尾进行插入或删除操作，需要遍历整个链表，时间复杂度为 O(n)。 5双链表和单循环链表中，若仅知道指针 p 指向某个结点，不知道头指针，能否将结点 *p 从相应的链表中删除？若可以，其时间复杂度各为多少？ 答：能删除。双链表上删除 p 所指向的结点的时间复杂度为 O(1)，单循环链表上删除 p 所指向的结点的 时间复杂度为 O(n)。 18 6下列算法的功能是什么？ *L) /L 是无头结点的单链表 *q， *p； &L- q=L； L=L- p=L; p- p=p- p-q; q- ； 答：如果长度大于 1，则将首元结点删除并插入到表尾。 7如果有 n 个线性表同时共存，并且在处理过程中各表的长度会发生动态变化，线性表的总长度也会自动地改变。在此情况下，应选择哪一种存储结构？为什么？ 答：应选用链式存储结构。因为顺序表是静态存储结构，只能预先分配，不能随着线性表长度的改变而变化。而链表则可根据需要动态地申请空间，因此适用于动态变化表长的线性表。 8若线性表的总数基本稳定，且很少进行插入、删除操作，但要求以最快的方式存取线性表的元素，应该用哪种存储结构？为什么？ 答：应选用顺序存储结构。因为顺序存储结构存取元素操作的时间复杂度为 O(1)。 五、 算法设计题 19 假设算法中用到的顺序表和链表结构如下： #00; 1试用顺序表作为存储结构，实现将线性表 (a1， 地逆置的操作，所谓“就地”是指辅助空间为 O(1)。 答： (1)顺序表的就地逆置 分析：分别用两个整型变量指向顺序表的两端，同时向中间移动，移动的同时互换两个下标指示的元素的值。 *L)顺序表的就地逆置 i=0； j=L-i; L-i=j; L-j=t; (2)链表的就地逆置 分析：本算法的思想是逐个地把 L 的当前元素 *L)链表的就地逆置 p=L-L- 20 p!=r=p， p=p- r 指向当前待逆置的结点， p 记下下 个结点 r- L-r； 放到表头 2设顺序表 L 是一个递增 (允许有相同的值 )有序表，试写一算法将 x 插入 L 中，并使 L 仍为一个有序表。 答 ：分析：先找到 x 的正确插入位置，然后将大于 后将 x 插入到其位置上，同时顺序表长度增 1。 L， x) 中 i=0; &(x=L-i) i+； 找正确的插入位置 k=L-k=i； 元素从后往前依次后移 L-k+1=L-k； L-i=x； x 插入到正确位置 L-； ) 是一个递减有序表，试写一个算法将 的有序性。 21 答：分析：此问题的关键是在链表中找到 x 的插入位置，因此需要两个指针一前一后地依次向后移动。 L， x) x 插入有序链表 L 中 q=L； p=q p!=p x) 找到插入的位置 q=p； p=p s=(； 生成新结点 S x； S p； q s； 4. 试写出在不带头结点的单链表的第 答：分析：对不带头结点的链表操作时，要注意对第一个结点和其他结点操作的不同。 *L， x，i) 不带头结点的单链表的第 i 个元素之前插入一个元素 p=L： j=1; p!=j+； if(x； if(i=1) q ； L=q； 在第一个元素之前插入 q p p q； 在其他位置插入 5设 A、 B 是两个线性表，其表中元素递增有序，长度分别为 m 和 n。试写一算法分别以顺序存储和链式存储将 A 和 B 归并成一个仍按元素值递增有序的线性表C。 答： (1)分析：用三个变量 i、 j、 k 分别指示 A、 B、 A、 B 表中较小的元素写入C 中，直到有一个表先结束。最后将没结束的表的剩余元素写入 C 表中。 ， ， C)有序顺序表 A 和 B 归并成有序顺序表 C i=0； j=0； k=0； i， i， k 分别为顺序表 A， B，C 的下标 k=i+； C-k=j;j+； k+； i=m) t=j ； k=t;k+； B 表长度大于 t=i； k=t；k+； A 表长度大于 B 表 C-m+n； ; (2) A， B，C) 有序链表 A 和 B 归并成有序链表 C C=A； ； A 和 B 都不为空时 if( A 当前结点值较小 qa= pc= pa= qb=pc=pb= B 当前结点值较小 if(pa) A 没有结束，将 A 表 24 剩余元素链接到 C 表 if(pb) B 没有结束，将 B 表剩余元素链接到 C 表 )； 释放 B 表的头结点 本算法需要遍历两个线性表，因此时间复杂度为O(m+n)。 6设指针 别指向两个不带头结点的单链表的首结点，设计从表 删除第 i 个元素起共 元素，并将这些元素插入到 第 j 个结点之前的算法。 答：分析：先在 找到第 i 个结点，分别用两个指针 p 指向第 第 i 个结点，然后用指针 i 个结点起向后走 元素，使 q 指向此位置。然后在 找到第 j 个结点，将 p 所指向的 中的第 i 个及 q 所指向的最后一个共 结点插入到。 i， j, 删除不带头结点的单链表 第 i 个元素起共并将这峰元素插入到单链表 if( k+； p) )； q=p； k=l； p 指向 中第 i 个结点 q& k+； 查找 中第 i+q) )； if( la=q i=1 的情况 q 完成删除 将从 删除的结点插入到 if(j=1) q- lb=p； j=1时 r= k=1； j1 时 r& k+； 查找 中第 i 1 个元素 r) )； q r r p； 完成插入 7单链表 L 是一个递减有序表，试写一高效算法，删除表中值大于 若表中有这样的结点 )，同时释放被删结点空间，这里 两个给定的参数。 答： *L， 26 删除递减有序单链表 L 中值大于 小于结点 q=L； if( ” n ” ) ；)； p=L p 的前驱 p 当前元素大于或等于 p、 q 依次向后移动 q=p； p=p p!=&(p 一 当前元素的值比 同时比 ，删除p 指向的结点 q p p) ； p=q ； 8编写一个算法将一个头结点指针为 单链表 和 B，其头结点指针分别为 得 A 链表中含有原链表 A 中序号为奇数的元素，而 B 链表中含有原链表 A 中序号为偶数的元素，且保持原来的相对顺序。 答：分析：用两个 工作指针 p 和 q 分别指示序号为奇数和序号为偶数的结点，将 q 所指向的结点从 A 表删除，并链接到 B 表。 27 *A， *B) 单链表 和元素序号为偶数的单链表 B p=A- B=(； r=B； p!=p-q=p q 指向偶数序号的结点 p q 将 q 从 A 表中删除 r q； 将 q 结点链接到 B 链表的末尾 r=q； r 总是指向 B 链表的最后 个结点 p=p p 指向原链表 A 中的奇数序号的结点 r 将生成 B 链表中的最后一个结点的 置为空 9假设以两个元素值递增有序排列的线性表 A、 B 分别表示两个集合，要求另辟空间构造一个线性表 C，其元素为两集合的交集，且表 C 中的元素值也递增有 序排列。用顺序表实现并写出 C 的算法。 答：分析：用三个变量 i、 j、 k 分别指示 A、 B、 C 三个顺序表的当前位置，若 A、 B 表中当前元素值相同， 28 则写入 C 中，并使 i、 j、 k 值增 1；若 A 表元素值较小，则使 i 增 1；若 B 表元素值较小，则使 j 增 1，直到有一个表先结束。 *A， B，*C) 求元素依值递增有序排列的顺序表 A、 B 的交集 C i=0； j=0； k=0； k=i； 相同元素写入 C 表中 k+； i+； j+； ik； ； 11假设在长度大于 1 的 单循环链表中，既无头结点也无头指针。 s 为指向链表中某个结点的指针，试编写算法删除结点 *s 的直接前驱结点。 答：分析：因为既不知道此单循环链表的头指针，也不知道其尾指针，所以找 s 的前驱就只能从 s 开始，顺次向后寻找。 29 s) 删除单循环链表中结点 s 的直接前驱 p=s； p s) p=p 找到 s 的前驱的前驱 p q=p q 是 p 的后继，即 s 的前驱 p s； 将 q 删除 q)； 12计算带头结点的循环链表的结点个数。 答： *计算单循环链表中结点的个数 p= i=0； p!= i+； p=p- i； 13已知由单链表表示的线性表中，含有三类字符的数据元素 (如：字母字符、数字字符和其他字符 )，试编写算法构造三个以循环链表表示的 线性表，使得每个表中只含有同一类的字符，且利用原表中的结点空间作为这三个表的结点空间，头结点可另辟空间。 答：分析： p 指向待处理的单链表的首元结点，构造三个空的单循环链表，分别存储三类字符，其中一个表可使用原来的单链表。 q 指向 p 的下一个结点，根据 *把 q 的值给 p，处理下一个结点。 30 L ， 分解含有三类字符的单链表为三个以循环链表表 示的线性表，使其分别含有三类字符 p=L ； 分别构造三个单循环链表 ； ； p!=L) q=p q 记下 L 中下一个结点的位置 if(p a ) 链接到字母链表的头部 p p； p 0 ) 链接到数字链表的头部 p p； p-p； 链接到其他字母链表的头部 p=q； 14、己知 A、 B 和 C 为三个递增有序的线性表 ，现要求对 A 表进行如下操作：删去那些既在 B 表中出现又在 对顺序表编写实现上述操作的算 31 法 (注：题中未特别指明同一表中的元素值各不相同 )。 答：分析：先从 B 和 C 中找出共有元素，记为 在 A 中从当前位置开始，凡小于 元素均保留(存到新的位置 )，等于 就跳过，到大于 A， ，) 对顺序表 A 删去那些既在 B 表中出现又在 C 表中出现的元素 i=0； j=0； k=0； m=0; i 指示 A 中元素原来的位置， m 为移动后的位置 k) k+; j； 找到了相同元素 j= j+； k= k+； j、k 后移到新的元素 A-im+=A-i+；需保留的元素移动到新位置 32 A-i=i+；跳过相同的元素 A-m+=A-i+； A 的剩余元素重新存储 m； 15双循环链表中，设计满足下列条件的算法。 (1)在值为 x 的结点之前插入值为 y 的结点。 (2)删除值为 x 的结点。 答：分析：在双循环链表中插入和删除结点要注意修改双向的指针。 * ， x， y) 在双循环链表中插入结点 p=L- p!=L&p-x) p=p- 在链表中查找值为 x 的结点 if(p-x) 找到值为 x 的结点 q=p- q 指向值为 x 的结点的前驱 s=(； 33 s-y； s-p； s-q； 将 y 插入到q 与 p 指向的结点之间 p-s； q-s； ”没有值为 x 的结点” ) ；)； ， x) 在双循环链表中删除结点 p=L- p!=L&p-x)p=p- if(p-x) p-p-p-p-p)； 没有值为 x 的结点” )； )； 16设有一个双循环链表，其中有一结点的指针为 p，编写算法将 p 与其右边的一个结点进行交换。 答： * p) 将双循环链表中 q=p q 指向 p 的后继 p q； q p 将 p 的前驱与 q 相链接 34 p q p q； 将 q 之后 q-p； q p； 17设有一个双链表，每个结点中除有 个域外，还有一个可访问频度域 链表启用之前，其初始值均为 0。每当链表进行一次， x)操作时 令元素值为 x 的结点中 l，并调整表中结点的次序，使其按访问频度的递减次序排列，以便使频繁访问的结点总是靠近表头。试写一符合上述要求的 作的算法。 答：分析：先在双链表中查找值为 x 的结点，若找到则使其 增 1，然后从头至尾扫描链表，将此结点插入到按 减顺序排列的正确位置。 * x) 双链表按访问频度域 减次序排列 p2= p1= 前， 查找单链表中值为 x 的结点 if(x) ； 使值为 x 的结点的 1 p2=p1= 35 if( n” )； if( 在链表中找 指向的结点，按 递减应插入的位置 插入链表中间的某一位置 p2= p1=p2=pl=插入 if( 18给出用单链表存储多项式的结构，并编写一个按指数值递增次序输入所产生的多项式链表的过程。 答： 系数 指数 * ) 建立多项式 36 ； r= 输入系数和指数：” )； n， &m)； n!=0) 若 n=0 则退出循环 s=(； s-n； s-m； r-s； r=s；把s 链接到 r 的后面 输入系数和指数 :” )； n，&m)； r- 删除头结点 19根据上题的多项式链表结构，编写一个过程实现两个多项式相加的运算。 答：分析：对所有指数相同的项，将其对应系数相加，若和不为 0，则构造新“和多项式”的结点；将所有指数不同的项复制到和多项式中。 多项 式相加 p= q= ； r= p!=q!=if(p-q-两结点的指数相同时，将两系数相加生成新结点插入