数据结构(C语言版)第一二章习题答案

不思，故有惑；不求，故无得；不问，故不知。
第1章 绪论
习题
1．简述下列概念：数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型

2．试举一个数据结构的例子
叙述其逻辑结构和存储结构两方面的含义和相互关系

3．简述逻辑结构的四种基本关系并画出它们的关系图

4．存储结构由哪两种基本的存储方法实现？
5．选择题
（1）在数据结构中
从逻辑上可以把数据结构分成（ ）

A．动态结构和静态结构 B．紧凑结构和非紧凑结构
C．线性结构和非线性结构 D．内部结构和外部结构
（2）与数据元素本身的形式、内容、相对位置、个数无关的是数据的（ ）

A．存储结构 B．存储实现
C．逻辑结构 D．运算实现
（3）通常要求同一逻辑结构中的所有数据元素具有相同的特性
这意味着（ ）

A．数据具有同一特点
B．不仅数据元素所包含的数据项的个数要相同
而且对应数据项的类型要一致
C．每个数据元素都一样
D．数据元素所包含的数据项的个数要相等
（4）以下说法正确的是（ ）

A．数据元素是数据的最小单位
B．数据项是数据的基本单位
C．数据结构是带有结构的各数据项的集合
D．一些表面上很不相同的数据可以有相同的逻辑结构
（5）以下与数据的存储结构无关的术语是（ ）

A．顺序队列 B. 链表 C. 有序表 D. 链栈
（6）以下数据结构中
（ ）是非线性数据结构
A．树 B．字符串 C．队 D．栈
6．试分析下面各程序段的时间复杂度

（1）x=90; y=100;
while(y>0)
if(x>100)
{x=x-10;y--;}
else x++;
（2）for (i=0; ifor (j=0; ja[i][j]=0;
（3）s=0;
for i=0; ifor(j=0; j s+=B[i][j];
sum=s;
（4）i=1;
while(i<=n)
i=i*3;
（5）x=0;
for(i=1; i for (j=1; j<=n-i; j++)
x++;
（6）x=n; //n>1
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()


第2章 线性表
1．选择题
（1）一个向量第一个元素的存储地址是100
每个元素的长度为2
则第5个元素的地址

是（ ）

A．110 B．108 C．100 D．120
（2）在n个结点的顺序表中
算法的时间复杂度是O(1)的操作是（ ）

A．访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n）
B．在第i个结点后插入一个新结点（1≤i≤n）
C．删除第i个结点（1≤i≤n）
D．将n个结点从小到大排序
（3） 向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变
平均要移动 的元素个数为（ ）

A．8 B．63.5 C．63 D．7
（4）链接存储的存储结构所占存储空间（ ）

A．分两部分
一部分存放结点值
另一部分存放表示结点间关系的指针
B．只有一部分
存放结点值
C．只有一部分
存储表示结点间关系的指针
D．分两部分
一部分存放结点值
另一部分存放结点所占单元数
（5）线性表若采用链式存储结构时
要求内存中可用存储单元的地址（ ）

A．必须是连续的 B．部分地址必须是连续的
C．一定是不连续的 D．连续或不连续都可以
（6）线性表Ｌ在（ ）情况下适用于使用链式结构实现

A．需经常修改Ｌ中的结点值 Ｂ．需不断对Ｌ进行删除插入
C．Ｌ中含有大量的结点 Ｄ．Ｌ中结点结构复杂
（7）单链表的存储密度（ ）

A．大于1 B．等于1 C．小于1 D．不能确定
（8）将两个各有n个元素的有序表归并成一个有序表
其最少的比较次数是（ ）

A．n B．2n-1 C．2n D．n-1
（9）在一个长度为n的顺序表中
在第i个元素（1≤i≤n+1）之前插入一个新元素时须向后移动（ ）个元素

A．n-i B．n-i+1 C．n-i-1 D．i
(10) 线性表L=(a1
a2
......an)
下列说法正确的是（ ）

A．每个元素都有一个直接前驱和一个直接后继
B．线性表中至少有一个元素
C．表中诸元素的排列必须是由小到大或由大到小
D．除第一个和最后一个元素外
其余每个元素都有一个且仅有一个直接前驱和直接后继

(11) 若指定有n个元素的向量
则建立一个有序单链表的时间复杂性的量级是（ ）

A．O(1) B．O(n) C．O(n2) D．O(nlog2n)
(12) 以下说法错误的是（ ）

A．求表长、定位这两种运算在采用顺序存储结构时实现的效率不比采用链式存储结构时实现的效率低
B．顺序存储的线性表可以随机存取
C．由于顺序存储要求连续的存储区域
所以在存储

管理上不够灵活
D．线性表的链式存储结构优于顺序存储结构
(13) 在单链表中
要将s所指结点插入到p所指结点之后
其语句应为（ ）

A．s->next=p+1; p->next=s;
B．(*p).next=s; (*s).next=(*p).next;
C．s->next=p->next; p->next=s->next;
D．s->next=p->next; p->next=s;
(14) 在双向链表存储结构中
删除p所指的结点时须修改指针（ ）

A．p->next->prior=p->prior; p->prior->next=p->next;
B．p->next=p->next->next; p->next->prior=p;
C．p->prior->next=p; p->prior=p->prior->prior;
D．p->prior=p->next->next; p->next=p->prior->prior;
(15) 在双向循环链表中
在p指针所指的结点后插入q所指向的新结点
其修改指针的操作是（ ）

A．p->next=q; q->prior=p; p->next->prior=q; q->next=q;
B．p->next=q; p->next->prior=q; q->prior=p; q->next=p->next;
C．q->prior=p; q->next=p->next; p->next->prior=q; p->next=q;
D．q->prior=p; q->next=p->next; p->next=q; p->next->prior=q;

2．算法设计题
（1）将两个递增的有序链表合并为一个递增的有序链表
要求结果链表仍使用原来两个链表的存储空间
不另外占用其它的存储空间
表中不允许有重复的数据

void MergeList_L(LinkList &La
LinkList &Lb
LinkList &Lc){
pa=La->next; pb=Lb->next;
Lc=pc=La; //用La的头结点作为Lc的头结点
while(pa && pb){
if(pa->datadata){ pc->next=pa;pc=pa;pa=pa->next;}
else if(pa->data>pb->data) {pc->next=pb; pc=pb; pb=pb->next;}
else {// 相等时取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& La
LinkList& Lb
LinkList& Lc
) {
pa = La->next; pb = Lb->next; // 初始化
Lc=pc=La; //用La的头结点作为Lc的头结点
Lc->next = NULL;
while ( pa || pb ) {
if ( !pa ) { q = pb; pb = pb->next; }
else if ( !pb ) { q = pa; pa = pa->next; }
else if (pa->data <= pb->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(LinkList& La
LinkList& Lb
LinkList& Lc
) {
pa=la->next;pb=lb->next;∥设工作指针pa和pb；
Lc=pc=La; //用La的头结点作为Lc的头结点
while(pa&&pb)
if(pa->data==pb->data)∥交集并入结果表中

{ pc->next=pa;pc=pa;pa=pa->next;
u=pb;pb=pb->next; delete u;}
else if(pa->datadata) {u=pa;pa=pa->next; delete u;}
else {u=pb; pb=pb->next; delete u;}
while(pa){ u=pa; pa=pa->next; delete u;}∥ 释放结点空间
while(pb) {u=pb; pb=pb->next; delete u;}∥释放结点空间
pc->next=null;∥置链表尾标记

delete Lb; ∥注： 本算法中也可对B表不作释放空间的处理

（4）已知两个链表A和B分别表示两个集合
其元素递增排列
请设计算法求出两个集合A和B 的差集（即仅由在A中出现而不在B中出现的元素所构成的集合）
并以同样的形式存储
同时返回该集合的元素个数

　void Difference（LinkedList A
B
*n）
　∥A和B均是带头结点的递增有序的单链表
分别存储了一个集合
本算法求两集合的差集
存储于单链表A中
*n是结果集合中元素个数
调用时为0
{p=A->next； ∥p和q分别是链表A和B的工作指针

q=B->next； pre=A； ∥pre为A中p所指结点的前驱结点的指针

while（p!=null && q!=null）
if（p->datadata）{pre=p；p=p->next；*n++；} ∥ A链表中当前结点指针后移

else if（p->data>q->data）q=q->next； ∥B链表中当前结点指针后移

else {pre->next=p->next； ∥处理A
B中元素值相同的结点
应删除

u=p； p=p->next； delete u；} ∥删除结点

（5）设计算法将一个带头结点的单链表A分解为两个具有相同结构的链表B、C
其中B表的结点为A表中值小于零的结点
而C表的结点为A表中值大于零的结点（链表A的元素类型为整型
要求B、C表利用A表的结点）

（6）设计一个算法
通过一趟遍历在单链表中确定值最大的结点

ElemType Max (LinkList L ){
if(L->next==NULL) return 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) {
// 逆置带头结点的单链表 L
p=L->next; L->next=NULL;
while ( p) {
q=p->next; // q指向*p的后继
p->next=L->next;
L->next=p; // *p插入在头结点之后
p = q;
}
}
（8）设计一个算法

删除递增有序链表中值大于mink且小于maxk的所有元素（mink和maxk是给定的两个参数
其值可以和表中的元素相同
也可以不同 ）

void delete(LinkList &L
int mink
int maxk) {
p=L->next; //首元结点
while (p && p->data<=mink)
{ pre=p; p=p->next; } //查找第一个值>mink的结点
if (p) {
while (p && p->datanext;
// 查找第一个值 ≥maxk 的结点
q=pre->next; pre->next=p; // 修改指针
while (q!=p)
{ s=q->next; delete q; q=s; } // 释放结点空间
}//if
}
（9）已知p指向双向循环链表中的一个结点
其结点结构为data、prior、next三个域
写出算法change(p)
交换p所指向的结点和它的前缀结点的顺序

知道双向循环链表中的一个结点
与前驱交换涉及到四个结点（p结点
前驱结点
前驱的前驱结点
后继结点）六条链

void Exchange（LinkedList p）
∥p是双向循环链表中的一个结点
本算法将p所指结点与其前驱结点交换

{q=p->llink；
q->llink->rlink=p； ∥p的前驱的前驱之后继为p
p->llink=q->llink； ∥p的前驱指向其前驱的前驱

q->rlink=p->rlink； ∥p的前驱的后继为p的后继

q->llink=p； ∥p与其前驱交换
p->rlink->llink=q； ∥p的后继的前驱指向原p的前驱
p->rlink=q； ∥p的后继指向其原来的前驱
}∥算法exchange结束


（10）已知长度为n的线性表A采用顺序存储结构
请写一时间复杂度为O(n)、空间复杂度为O(1)的算法
该算法删除线性表中所有值为item的数据元素

[题目分析] 在顺序存储的线性表上删除元素
通常要涉及到一系列元素的移动（删第i个元素
第i+1至第n个元素要依次前移）
本题要求删除线性表中所有值为item的数据元素
并未要求元素间的相对位置不变
因此可以考虑设头尾两个指针（i=1
j=n）
从两端向中间移动
凡遇到值item的数据元素时
直接将右端元素左移至值为item的数据元素位置

void Delete（ElemType A[ ]
int n）
∥A是有n个元素的一维数组
本算法删除A中所有值为item的元素

{i=1；j=n；∥设置数组低、高端指针（下标）

while（i {while（i左移指针

if（i指针左移
if（i }
[算法讨论] 因元素只扫描一趟
算法时间复杂度为O（n）
删除元素未使用其它辅助空间
最后线性表中的元素个数是j