数据结构习题解答

习题一 1 1填空题填空题 (1) ((1) (数据元素、或元素、或结点、或顶点、或记录数据元素、或元素、或结点、或顶点、或记录）是数据的基本单位，在计算机程序中作为一个）是数据的基本单位，在计算机程序中作为一个 整体进行考虑和处理。整体进行考虑和处理。 (2)(2)（（数据项、或字段数据项、或字段）是数据的最小单位，）是数据的最小单位， （（数据元素数据元素）是讨论数据结构时涉及的最小数据单位。）是讨论数据结构时涉及的最小数据单位。 (3)(3)从逻辑关系上讲，数据结构主要分为从逻辑关系上讲，数据结构主要分为( (集合集合) )、、( (线性结构线性结构) )、、( (树结构树结构) )和和( (图图) )。。 (4)(4)数据的存储结构主要有（数据的存储结构主要有（顺序存储结构顺序存储结构）和（）和（链式存储结构链式存储结构）两种基本方法，不论哪种存储结构，）两种基本方法，不论哪种存储结构， 都要存储两方面的内容：都要存储两方面的内容： （（数据元素数据元素）和（）和（它们之间的关系它们之间的关系 ）） 。。 (5) 算法具有算法具有 5 5 个特性，分别是（个特性，分别是（输入输入）） 、、 （（输出输出）） 、、 （（有穷性有穷性）） 、、 （（确定性确定性）） 、、 （（可行性可行性）） 。。 (6)(6) 算法的描述方法通常有算法的描述方法通常有( (自然语言自然语言) )、、( (流程图流程图) )、、( (程序设计语言程序设计语言) )、、( (伪代码伪代码)4)4 种，其中，种，其中，( (伪代伪代 码码) )被称为算法语言。被称为算法语言。 (7)(7) 一般情况下，一个算法的时间复杂度是算法（一般情况下，一个算法的时间复杂度是算法（输入规模输入规模）的函数。）的函数。 (8)(8) 设待处理问题的规模为设待处理问题的规模为n,n,若一个算法的时间复杂度为一个常数，则表示成数量级的形式为若一个算法的时间复杂度为一个常数，则表示成数量级的形式为 (O(1))(O(1))，若为，若为 n*logn*log 2 25n, 5n, 则表示成数量级的形式为则表示成数量级的形式为( (O(n*logO(n*log 2 2n) n)) )。。 2. 选择题: (1) C, D (2) B (3) B (4) A (5) D (6) A (7) C (8) C, E 习题二 1.1. 填空题填空题 (1)(1) 在顺序表中，在顺序表中，等概率情况下，等概率情况下，插入和删除一个元素平均需移动插入和删除一个元素平均需移动( (表长的一半表长的一半) )个元素，个元素，具体移动元具体移动元 素的个数与素的个数与( (表的长度表的长度) )和和( (数据元素所在的位置数据元素所在的位置) )有关。有关。 (2)(2) 一个顺序表的第一个元素的存储地址是一个顺序表的第一个元素的存储地址是 100100，每个数据元素的长度是，每个数据元素的长度是 2 2，则第，则第 5 5 个数据元素的存个数据元素的存 储地址是（储地址是（108108）） 。。 (3)(3) 设单链表中指针设单链表中指针 p p 指向单链表的一个非空结点指向单链表的一个非空结点 A A，若要删除结点，若要删除结点A A 的直接后继，则需要修改指针的直接后继，则需要修改指针 的操作为（的操作为（p-next=(p-next)-next,p-next=(p-next)-next, 或者或者 q=p-next; p-next=q-next q=p-next; p-next=q-next）） 。。 (4)(4) 单链表中设置头结点的作用是单链表中设置头结点的作用是( (方便运算方便运算, ,减少程序的复杂性，使得空表和非空表处理统一减少程序的复杂性，使得空表和非空表处理统一) )。。 (5)(5) 非空的循环单链表由头指针非空的循环单链表由头指针 headhead 指示，则其尾结点指示，则其尾结点( (由指针由指针 p p 所指所指) )满足满足( (p-next=headp-next=head) )。。 (6)(6) 在在 有有 尾尾 指指 针针 rearrear 指指 示示 的的 循循 环环 单单 链链 表表 中中 ，， 在在 表表 尾尾 插插 入入 一一 个个 结结 点点 s s 的的 操操 作作 序序 列列 是是 （（s-next=rear-next;s-next=rear-next; rear-next=s;rear-next=s; rear=srear=s）） ，， 删除开始结点的操作序列是删除开始结点的操作序列是 （（q=rear-next-next;q=rear-next-next; rear-next-next=q-next; delete q;rear-next-next=q-next; delete q;）） 。。 注：假设此循环单链表有表头结点注：假设此循环单链表有表头结点 (7)(7) 一个具有一个具有 n n 个结点的单链表，个结点的单链表，在在 p p 所指结点后插入一个新结点所指结点后插入一个新结点 s s 的时间复杂性为的时间复杂性为（（ O(1) O(1)）） ；；在给在给 定值定值 x x 的结点后插入一个新结点的时间复杂性为的结点后插入一个新结点的时间复杂性为( ( O(n O(n) ) ）） 。。 (8)(8) 可由一个尾指针惟一确定的链表有可由一个尾指针惟一确定的链表有( (循环链表循环链表) )、、( (双链表双链表) )、、( (双循环链表双循环链表) )。。 2. 选择题: (1) A,B (2) D (3) B (4) A (5) A (6) D (7) B (8) B (9) C (10) B (11) B (12) D (13) A (14) A 5.5. 算法设计算法设计 (1)设计一个时间复杂度为 O(n)的算法。实现将数组 A[n]中所有元素循环左移 k 个位置。 算法思想：要使 a 1…akak+1…an - ak+1…ana1…ak,可以先让 a1…akak+1…an-ak…a1an…ak+1,再让 ak… a1 a n…ak+1 - a k+1…ana1…ak ，参见第 1 章 16 页的思想火花 算法：void converse(T a[], int i, int j){ for(s=i; snext; first-next=NULL; first-next=NULL; while(p){ while(p){ q=p-next; p-next=first-next; q=p-next; p-next=first-next; first-next=p;p=q; first-next=p;p=q; } } } } (5) 假设在长度大于 1 的循环链表中，既无头结点也无头指针，s 为指向链表中某个结点的指针，试 编写算法删除结点 s 的前驱结点。 void LinkList::deleteS(Node *s) {p=s; while(p-next-next!=s) p=p-next; { q=p-next; p-next=q-next; dele