数据结构习题参考答案

数据结构习题参考答案

习题参考答案

习题1

一．名称解释

（1）数据是信息的载体，是对客观事物的符号表示。

通俗的说，凡是能被计算机识别、存取和加工处理的符号、字符、图形、图象、声音、视频信号等一切信息都可以称为数据。

（2）数据结构是相互之间存在的一种或多种特定关系的数据元素的集合。简言之，数据结构是指数据之间的关系，即数据的组织形式。

（3）数据元素之间的逻辑关系，称为数据的逻辑结构。

（4）数据元素及其关系在计算机存储器内的表示，称为数据的存储结构。

（5）线性结构是指数据元素之间存在“一对一”关系的逻辑结构。

（6）非线性结构是指数据元素之间存在“一对一”或“一对多”关系的逻辑结构。 （除了线性结构以外的树形结构和图形结构等统称为非线性结构）。

二．判断题（正确的请在前面的括号内打√；错误的打ㄨ） （1）√ （2）ㄨ （3）√ （4）ㄨ （5）√ （6）√

三．填空题 （1） 集合

线性结构

树形结构 索引存储 多对多 没有 可行性

图形结构 散列存储 多个 输入

输出 非线性结构

（2） 顺序存储 链式存储

（3） 一对一 一对多 （4） 没有 一 （5） 任意多个 任意多个 （6） 有穷性 确定性 （7） 操作对象 关系 （8） 数据元素 关系 （9） 逻辑结构 存储结构

四．选择题

（1）A （2）C （3）C （4）D （5）D （6）B （7）A （8）B

五．试分析下列程序段的时间复杂度 （1）O (n*m) （4）O (sqrt (n) )

252

算法

（10）有穷指令 事先估算法 事后统计法

（2）O (n) （3）O (n) （5）O (n) （6）O (n2)

2

数据结构习题参考答案

六．二元关系表示的数据结构如下，分别画出对应的逻辑图形，并指出它们属于何种数据结构。

（1）集合

（2）线性结构

（3）图结构

（4）树结构

线，而直接用直线画。

以后，凡不会对根结点引起误解的情况下，树形结构结点之间的关系一般不用带箭头

253

数据结构习题参考答案

习题2

一．名词解释

（1）线性表——线性表是具有相同数据类型的n（n>=0）个数据元素的有限序列。其逻辑特征反映了结点间一对一的关系，是一种线性结构。

（2）顺序表——用一组地址连续的存储单元依次顺序存储线性表的数据元素（相邻结点存放在相邻的物理位置），称为顺序表。它是一种随机存取结构，可以通过公式来计算结点的存取地址。

（3）单链表——单链表的每个结点都有两个域，一个数据域和一个指针域，称之为单链表。

（4）双链表——以链表形式存储的线性表，其结点包含一个数据域和两个指针域，称之为双链表。

（5）循环链表——若线性链表的最后一个结点的指针指向头结点，使得链表头尾结点相连，就构成了循环链表。

（6）存储密度——存储密度定义为结点数据本身所占的存储量与结点结构实际分配的存储量的比值。顺序表的存储密度等于1；链表结构存储密度小于1。

二．判断题（下列各题，正确的请在前面的括号内打√；错误的打ㄨ） （1）ㄨ （2）ㄨ （3）√ （4）ㄨ （5）ㄨ （6）√ （7）ㄨ （8）ㄨ （9）√ （10）√

三．填空题 1． 一定 2． 不必 3． 有限的 4． 节省存储 5． 插入

一对一关系 随机存取 删除

小

表长n和插入位置 表长n和删除位置

6． n/2 7． （n-1）/2 8． O (1) 9． 直接前驱

10．的直接前趋结点的地址 O (n)

O (1)

11．O (1)

12．*P的直接前驱结点的地址 O (n) 13．头指针

四．选择题 (1) B

254

(2) A (3) B (4) C (5) A

数据结构习题参考答案

(6) A (7) B 五．简答题

(8) B (9) D (10) B

1．顺序存储结构的长处是节约存储空间，可以随机存取。（缺点是插入、删除要作大量移动，不易扩充）； 链表存储结构优点是插入、删除操作容易，表的扩充方便。（缺点是存储密度低）。

2． 头指针——指向链表中第一个结点（头结点或无头结点时的开始结点）的指针。 头结点——在开始结点之前附加的一个结点。

开始结点——在链表中，存储第一个数据元素的结点。

3． 主要是简化操作。由于表的操作常在表的两端进行，所以对单循环链表，当知道其尾指针rear后，其另一端的头指针是rear->next->next（表中代头结点），仅改变两个指针值即可，运算时间为O(1)。

六．（1）返回结点*p的直接前趋结点地址。 （2）交换结点*p和结点*q（p和q的值不变）。 七． 程序设计题

1．解：void Show(ListNode *P)

{ }

ListNode *t=P; do { }

printf("%c",t->data); t=t->rear;

while(t!=P);

2．解：void delete(ListNode *L)

{ }

255

ListNode *p=L,*q;

if(L->next->data==X)

{ printf(“值为x的结点是第一个结点，没有直接前趋结点可以删除”);

return;

}

for(;p->next->data!=X;q=p,p=p->next); //删除指针p所指向的结点 q->next=p->next; delete p;

数据结构习题参考答案

3．解void Del(SeqList *L,int i,int k)

{ int j=i-1+k; for(j=0;j<k;j++)

{

L->data[i-1+j]=L->data[i+k-2+j]; if(i+k-2+j>L->last)

break;

} }

4． 解：本题是遍历该链表的每个结点，每遇到一个结点，结点个数加1，结点个数存储在变量n中。实现本题功能的函数如下： int counter(head) node *head； { node *p; int n＝0; p= head；

while(p!=NULL)

{ if(p->data==x) n++；

p= p->next;

}

return(n); }

5．解：本题的算法思想是：先找到两链表的尾指针，将第一个链表的尾指针与第二个链表的头结点链接起来，使之成为循环的。函数如下：

node *link(head1,head2) node *head1, *head2; { node *p, *q;

p=head1;

while(p->next!=head1) p=p->next; q=head2;

while(q->next!=head2) q=q->next; p->next=head2; q->next=head1; return(head1); }

256

数据结构习题参考答案

6．解：假设输入一组多项式的系数和指数，以输入系数为标志结束，在建立多项式链表时，总是按照指数从大到小顺序排列的。两个多项式链表A和B，其头指针分别是heada和headb，这两个多项的多项式链表为C，其头指针为headc。实现本题功能的函数如下： struct pnode *padd(heada，headb) struct pnode *heada, *headb； { struct pnode *headc, *p, *q,*s; int x;

p= heada;q=headb;

headc＝(struct pnode *)malloc(sizeof(struct pndoe));

r=headc;

while(p!=NULL&&q!=NULL)

{ if (p->exp==q->exp) //两结点指数相等时， …… 此处隐藏：8355字，全部文档内容请下载后查看。喜欢就下载吧 ……