1、 1 1 数据结构习题答案 2 第一节 概 论 2 第二节 线性表 5 第三节 栈和队列 16 第五节 树 19 第七节 查找 25 第八节 排序 29 操作系统练习题参考答案 32 2 2 数据结构习题答案 第一节 概 论 一、选择题 1要求同一逻辑结构的所有数据元素具有相同的特性，这意味着 ( )。 A数据元素具有同一的特点 B不仅数据元素包含的数据项的个数要相同，而且对应数据项的类型要一致 C每个数据元素都一样 D数据元素所包含的数据项的个数要相等 2数据结构是一门研究非数值计算的程序设计问题中计算机的 ( (1) )以及它们之间的 ( (2) )和运算的学科。 (1) A操作对象 B计
2、算方法 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线性表的顺序存储结构是一种 ( )的存储结构。 A随机存 取 B顺序存取 C索引存取 D Hash 存取 6算法分析的目的是 ( )。 A找出数据结构的合理性 B研究
3、算法中的输入和输出的关系 C分析算法的效率以求改进 D分析算法的易懂性和文档性 7计算机算法指的是 ( (1) )，它必须具备输入、输出和 ( (2) )等五个特征。 (1) A计算方法 B排序方法 C解决某一问题的有限运算序列 D调度方法 (2) A可行性、可移植性和可扩充性 B可行性、确定性和有穷性 C确定性，有穷性和稳定性 D易读性、稳定性和安全性 8线性表若采用链表存储结构，要求内存中可用存储单元的地址 ( )。 A必须是连续的 B部分必须是连续的 C一定是不连续的 D连续不连续都可以 9在以下的叙述中，正确的是 ( )。 A线性表的线性存储结构优于链式存储结构 B二维数组是它的每个数
4、据元素为一个线性表的线性表 C栈的操作方式是先进先出 D队列的操作方式是先进后出 10根据数据元素之间关系的不同特性，以下四类基本的逻辑结构反映了四类基本的数据组织形式，其中解 释错误的是 ( )。 A集合中任何两个结点之间都有逻辑关系但组织形式松散 B线性结构中结点按逻辑关系依次排列形成一条“锁链” C树形结构具有分支、层次特性，其形态有点像自然界中的树 D图状结构中的各个结点按逻辑关系互相缠绕，任何两个结点都可以邻接 11以下说法正确的是 ( )。 A数据元素是数据的最小单位 B数据项是数据的基本单位 C数据结构是带有结构的各数据项的集合 D数据结构是带有结构的数据元素的集合 3 3 二、
5、判断题 1数据元素是数据的最小单位。 2数据结构是带有结构的数据元素的集合。 3数据结构、数据元素、数据项在计算机中的映像分别称为存储结构、结点、数据域。 4数据项是数据的基本单位。 5数据的逻辑结构是指各数据元素之间的逻辑关系，是用户按使用需要建立的。 6数据的物理结构是数据在计算机中实际的存储形式。 7算法和程序没有区别，所以在数据结构中二者是通用的。 8顺序存储结构属于静态结构，链式存储结构属于动态结构。 三、填空题 1所谓数据的逻辑结构指的是数据元素之间的 _逻辑关系 _。 2，数据结构是相互之间 存在一种或多种特定关系的数据元素的集合，它包括三方面的内容 _数据的逻辑结构、数据的存储
6、结构、对数据施加的操作 _。 3数据的逻辑结构包括 _集合结构 _、 _线性结构 _、 _树型结构 _和 _图状结构 _四种类型。 4在线性结构中，开始结点 _没有 _前驱结点，其余每个结点有且只有 _一个 _个前驱结点。 5在树形结构中，根结点只有 _一个 _，其余每个结点有且只有 _一个 _前驱结点；叶结点没有 _后继 _结点，其余每个结点的后继结点可以有 _任意个 _ 6在图形结构中，每个结点的前驱结点和后继结点可以有 _任意个 _。 7算法的五个重要特性是 _可行性 _、 _确定性 _、 _有穷性 _、 _输入 _、 _输出_。 8下列程序段的时间复杂度是 _O（ n） _。 for
7、(i=1； i， ， ， ， ， ， ， ， ， ，画出这个逻辑结构的图示，并确定相对于关系 R，哪些结点是开始结点，哪些 结点是终端结点？ 答：图略。开始结点 k1、 k2，终端结点 k6、 k7。 7设有如图 1.1 所示的逻辑结构图，给出它的逻辑结构，并说出它是什么类型的逻辑结构。 答：数据逻辑结构为： D=k1， k2， k3， k8， R=， ， ， ， ， ， ，其逻辑结构类型为树型结构。 8分析下列程序的时间复杂度 (设 n为正整数 )。 (1)int rec(int n) if(n=1)return(1)； else return(nrec(n-1)； (2)x=91； y=1
8、00； While (y0) if(x10) y-； (3)i=1； j=0； while(i+jj)j+； else i+; (4)x=n； y=0； while(x=(y+1)(y+1) y+； 答： (1) O(n) (2) O(1) (3) O(n) (4) O(n1/2) 9设 n 为正数。试确定下列各 程序段中前面加记号 的语句的频度： (1)i=1； k=0； 5 5 while(inext=NULL C head-next=head D head!=NULL 10非空单循环链表 head 的尾结点 p 满足 ( )。 A p-next=NULL B p=NULL C p-nex
9、t=head D p=head 11在双循环链表的 p 结点之后插入 s结点的操作是 ( )。 A p-next=s； s-prior=p； p-next-prior=s； s-next=p-next； B p-next=s； p-next-prior=s； s-prior=p： s-next=p-next； C s-prior=p； s-next=p-next； p-next=s； p-next-prior=s； D s-prior=p； s-next=p-next； p-next-pror=s； p-next=s； 12. 在一个单链表中，已知 q 结点是 p结点的前驱结点，若在 q和 p
10、 之间插入结点 s，则执行( )。 6 6 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； 13. 在一个单链表中，若 p结点不是最后结点。在 p之后插入结点 s，则执行 ( )。 A s-next=p； p-next=s; B s-next=p-next； p-next=s； C s-next=p-next； p=s； D p-next=s； s-next=p; 14. 若某线性表中最常用的操作是取第 i 个元素和找第 i 个元素的前驱元素，则采
11、用 ( )存储方式最节省时间。 A顺序表 B. 单链表 C双链表 D单循环链表 15设 rear 是指向非空带头结点的单循环链表的尾指针，则删除表头结点的操作可表示为( )。 A p=rear； rear=rear-next； free(p) B rear=rear-next； free(rear)； C rear=rear-next-next； free(rear)； D p=rear-next-next； rear-next-next=p-next； free(p)； 16在一个单链表中，若删除 p结点的后继结点，则执行 ( )。 A q=p-next； p-next=q-next； fr
12、ee(q)； B p=p-next； p-next=p-next-next；free(p)； C p-next=p-next； free(p-next)； D p=p-next-next； free(p-next)； 17设指针 p指向双链 表的某一结点，则双链表结构的对称性可用 ( )式来刻画。 A p-prior-next-=p-next-next B p-prior-prior=p-next-prior C p-prior-next-=p-next-prior D p-next-next=p-prior-prior 18在循环链表中，将头指针改设为尾指针 rear 后，其头结点和尾结点的
13、存储位置分别是 ( )。 A rear 和 rear-next-next B rear-next 和 rear C rear-next-next 和 rear D rear 和 rear-next 19循环链表的主要优点是 ( )。 A不再需要头指针了 B已知某个结点的位置后，容易找到它的直接前驱 C在进行插入、删除操作时，能更好地保证链表不断开 D从表中任一结点出发都能扫描到整个链表 20在线性表的下列存储结构中，读取元素花费时间最少的是 ( )。 A单链表 B双链表 C循环链表 D顺序表 二、判断题 1顺序存储的线性 表可以随机存取。 2顺序存储的线性表的插入和删除操作不需要付出很大的代价
14、，因为平均每次操作只有近一半的元素需要移动。 3线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此是属于同一数据对象。 4在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上不一定相邻。 5在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻。 6在单链表中，可以从头结点开始查找任何一个元素。 7线性表的链式存储结构优于顺序存储结构。 8在线性表的顺序存储结构中，插 入和删除元素时，移动元素的个数与该元素的位置有关。 9在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。 10顺序存储方式只能用于存储线性结构。 三
15、、填空题 1为了便于讨论，有时将含 n(n0)个结点的线性结构表示成 (a1， a2， an)，其中每个 ai 代表一个 _结点 _。 a1 称为 _第一个 _结点， an称为 _最后一个 _结点， i称为 ai在线性表中的 _位置_。对任意一对相邻结点 ai、 ai+1(1 inext； p-next=q-next；free(q)； _ 6非空的单循环链表 head 的尾结 点 (由指针 p所指 )满足 _ p-next= head _。 7 rear 是指向非空带头结点的单循环链表的尾指针，则删除起始结点的操作可表示为 _ p=rear-next； q=p-next； p-next=q-n
16、ext； free(q)； _。 8对于一个具有 n 个结点的单链表，在 p 所指结点后插入一个结点的时间复杂度为 _O(1)_，在给定值为 x 的结点后插入新结点的时间复杂度为 _ O(n)_。 9单链表表示法的基本思想是用 _指针 _表示结点间的逻辑关系。 10在顺序表中插入或 删除一个元素，平均需要移动 _一半 _元素，具体移动的元素个数与 _元素的位置 _有关。 11在一个长度为 n的向量的第 i(1 i n+1)个元素之前插入一个元素时，需向后移动 _ n-i+1_个元素。 12在一个长度为 n的向量中删除第 i(1 i n)个元素时，需向前移动 _ n-i _个元素。 13在双链表
17、中，每个结点有两个指针域，一个指向 _前驱 _，另一个指向 _后继 _。 14在一个带头结点的单循环链表中， p指向尾结点的直接前驱，则指向头结点的指针 head 可用p 表示为 head=_ p-next-next ； _。 15设 head 指向单链表的表头， p 指向单链表的表尾结点，则执行 p-next=head 后，该单链表构成 _单循环链表 _。 16在单链表中，若 p 和 s是两个指针，且满足 p-next 与 s相同，则语句 p-next=s-next 的作用是 _删除 _s 指向的结点。 17设 r指向单循环链表的最后一个结点，要在最后一个结点之后插入 s所指的结点，需执行的
18、三条语句是 _s-next= r-next _； r-next=s； r=s； 18在单链表中，指针 p所指结点为最后 一个结点的条件是 _ p-next=NULL_。 19在双循环链表中，若要在指 p 所指结点前插入 s 所指的结点，则需执行下列语句： s-next=p； s-prior=p-prior； _ p-prior-next _=s； p-prior=s； 20在单链表中，若要在 p所指结点之前插入 s所指的结点，可进行下列操作： s-next=_ p-next _； p-next=s； temp=p-data； p-data=_ s-data _； s-data=_ temp _
19、； 四、应用题 1描述以下三个概念的区别：头指针，头结点，首元结点 (第一个元素结点 )。 答：首元结点是指链表中存储的线性表中的第一个数据元素的结点。为了操作方便，通常在链表的首元结点之前附设一个结点，称为头结点。头指针是指向链表中的第一个结点的指针。 2何时选用顺序表，何时选用链表作为线性表的存储结构为宜？ 答：从空间上来看，当线性表的长度变化较大、难以估计其规模时，选用动态的链表作为存储结构比较合适，但链表除了需要设置数据域外，还要额外设置指针域，因此当线性表长度变 化不大、易于事先确定规模时，为了节约存储空间，宜采用顺序存储结构。从时间上来看，若线性表的操作主要是查找，很少进行插入和删
20、除操作时，应选用顺序表。对于频繁进行插入和删除操作的线性表，宜采用链表作为存储结构。 3在顺序表中插入和删除一个结点需平均移动多少个结点？具体的移动次数取决于哪两个因素？ 答：平均移动表中大约一半的结点，插入操作平均移动 n/2 个结点，删除操作平均移动（ n-1） /2 个结点。具体移动的次数取决于表长和插入、删除的结点的位置。 4为什么在单循环链表中设置尾指针比设置头指针更好？ 8 8 答：单 循环链表中无论设置尾指针还是头指针都可以遍历表中任一个结点，但设置尾指针时，若在表尾进行插入或删除操作可在 O(1)时间内完成，同样在表头进行插入或删除操作也可在 O(1)时间内完成。但若设置的是头
21、指针，表尾进行插入或删除操作，需要遍历整个链表，时间复杂度为O(n)。 5双链表和单循环链表中，若仅知道指针 p 指向某个结点，不知道头指针，能否将结点 p 从相应的链表中删除？若可以，其时间复杂度各为多少？ 答：能删除。双链表上删除 p 所指向的结点的时间复杂度为 O(1)，单循环链表上删除 p所指向的结点的时间复杂度为 O(n)。 6下列算法的功能是什么？ LinkList testl(LinkList L) /L 是无头结点的单链表 ListNode q， p； if(L while(p-next) p=p-next； p-next=q; q-next=NULL； return L； 答
22、： 如果长度大于 1，则将首元结点删除并插入到表尾。 7如果有 n个线性表 同时共存，并且在处理过程中各表的长度会发生动态变化，线性表的总长度也会自动地改变。在此情况下，应选择哪一种存储结构？为什么？ 答：应选用链式存储结构。因为顺序表是静态存储结构，只能预先分配，不能随着线性表长度的改变而变化。而链表则可根据需要动态地申请空间，因此适用于动态变化表长的线性表。 8若线性表的总数基本稳定，且很少进行插入、删除操作，但要求以最快的方式存取线性表的元素，应该用哪种存储结构？为什么？ 答：应选用顺序存储结构。因为顺序存储结构存取元素操作的时间复杂度为 O(1)。 五、算法设计题 1试用 顺序表作为存
23、储结构，实现将线性表 (a0， a1， a2， an-1)就地逆置的操作，所谓“就地”是指辅助空间为 O(1)。 答： (1)顺序表的就地逆置 分析：分别用两个整型变量指向顺序表的两端，同时向中间移动，移动的同时互换两个下标指示的元素的值。 void Seqreverse(SeqList L)顺序表的就地逆置 for(i=0； j=L.1ength-1； inext； L-next=NULL； while(p!=NULL) r=p， p=p-next； r 指向当前待逆置的结点， p记下下 个结点 r-next=L next； L-next=r； 放到表头 2设顺序表 L 是一个递增 (允许有
24、相同的值 )有序表，试写一算法将 x插入 L中，并使 L仍为一个有序表。 答：分析：先找到 x的正确插入位置，然后将大于 x 的元素从后向前依次向下移动，最后将 x 插入到其位置上，同时顺序表长度增 1。 void SeqListinsert(SeqList L， int x) x插入到递增有序的顺序表 L中 9 9 i=0; while(i=L.datai) i+； 找正确的插入位置 for(k=L.length-1;k=i； k-) 元素从后往前依次后移 L.datak+1： L.datak； L.data(i x； x插入到正确位置 L.1ength+； ) 3.设单链表 L是一个非递减
25、有序表，试写一个算法将 x插入其中后仍保持 L 的有序性。 答：分析：此问题的关键是在链表中找到 x的插入位置，因此需要两个指针一前一后地依次向后移动。 void LinkListinsert(LinkedList L， int x) x 插入有序链表 L 中 q=L； p=q next； while(p!=NULL while(p!=NULL k+； if(!p) exit(0)； q=p； k=l； p指向 la表中第 i 个结点 while(q k=1； j1 时 while(r&knext； k+； 查找 Lb 表中第 i 1 个元素 if(!r) exit(0)； q next=r
26、next； r next=p； 完成插入 7单链表 L是一个递减有序表，试写一高效算法，删除表中值大于 min 且小于 max 的结点 (若表中有这样的结点 )，同时释放被 删结点空间，这里 min 和 max 是两个给定的参数。 答： LinkedList delete(LinkedList L， int min， int max) 删除递减有序单链表 L中值大于 min 且小于 max 的结点 q=L； if(minmax) printf(” minmax n” )； exit(0)； else p=L next； q始终指向 p的前驱 while(p data=max) 当前元素大于或等于 max，则 p、 q 依次向后移动 q=p； p=p next； while(p!=NULL)&(p 一 datamin) 当前元素的值比 min 大同时比 max 小，删除 p 指向的结点 q next=p next， free(p)； p=q next； return L；
