数据结构习题库(c语言版)
- 格式：doc
- 大小：17.91 MB
- 文档页数：103
精品
第一章 绪 论一、基本内容
数据、数据元素、数据对象、数据结构、存储结构和数据类型等概念术语的确定含义、抽象数据类型的定义、表示和实现方法、描述算法的类C语言、算法设计的基本要求。
二、学习要点
1、熟悉各名词、术语的含义，掌握基本概念，特别是数据的逻辑结构和存储结构之间的关系。分清哪些是逻辑结构的性质，哪些是存储结构的性质。
2、了解抽象数据类型的定义、表示和实现方法。
3、熟悉类C语言的书写规范，特别要注意值调用和引用调用的区别，输入、输出的方式以及错误处理方式。
4、理解算法五个要素的确切含义。
1.1 基础知识
一 、填空题
1、数据的逻辑结构包括 ① ， ② ， ③ 和 ④ 四种类型，树型结构和图型结构合称为 ⑤ ，数据的存储结构即物理结构包括： ⑥
， ⑦ 等两种基本类型。
2、在线性结构中元素之间存在 ① 关系，树形结构中元素间存在 ② 关系，图形结构中元素间存在 ③ 关系。
3、一个数据结构用二元组表示时，它包括 ① 集合D和D上 ② 的集合S。
4、一个算法应具有 ① ， ② ， ③ ， ④ 和 ⑤ 这五个特性。
5、在图形结构中，每个节点的前驱节点和后继节点可以有 ① 个。
6、一个抽象数据类型用三元组（D，S，P）表示时，D是 ① ，S是 ② ，P是 ③ 。
7、数据元素在计算机中的映象是 ① 。
8、算法的设计取决于 ① ，算法的实现取决于 ② 。
二、选择题
1、数据元素是数据的 单位。
(A)基本 (B)最小
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)哈夫曼树
解答：
一、 填空题 精品
1、①线性 ②集合 ③树 ④图或网 ⑤非线性结构 ⑥顺序存储 ⑦链式存储
2、①1：1 ②1：n ③m：n
3、①数据元素 ②关系
4、①有穷性 ②确定性 ③可行性 ④输入 ⑤输出
5、①多个
6、①数据对象 ②D上的关系集合 ③对D的基本操作集合
7、①元素或结点
8、①数据（逻辑）结构 ②采用的存储结构
二、 选择题
1、A 2、B 3、C 4、B 5、B 6、A
l.2 应用知识
1、什么是算法？算法的特性是什么？算法设计的要求是什么?
解答: （略）
2、设有数据结构USER_STRU表示如下：
USER_STRU =（D，S）
D = { a1，a2，…，a9 }
S = { ，，，，，，，，，， }
画出这个数据结构的图示，并确定其类型。
解答：该结构的图示如下，该结构为图形结构。
3、设有数据结构USER_STRU表示如下：
USER_STRU =（D，S）
D = { a1，a2，…，a9 }
S = { ，，，，，，， }
画出这个数据结构的图示，并确定其类型。
解答：该结构的图示如下，该结构为树形结构。
a2
a4 a5
a6
a7 a3 a1
a9 a8
a1
a2 a3
a6 a4 精品
4、影响高级语言程序运行消耗时间的因素有哪些？
解答：主要有以下因素：
(1)算法选用的策略；
(2)问题的规模；
(3)书写程序的语言；
(4)编译程序产生的机器代码质量；
(5)机器执行指令的速度。
5、选择解决某种问题的最佳数据结构的标准是什么?
解答：一般有两条标准：
(1)所需的存储空间量；
(2)算法所需要的时间；
而算法所需要的时间又包括以下几点：
(1)程序运行时所需要的数据总量；
(2)源程序进行编译所需要的时间；
(3)计算机执行每条指令所需要的时间；
(4)程序中的指令重复执行的次数，而本条正是讨论算法中的重点内容。
6、设三个函数f,g,h分别为 f(n)=100n3+n2+1000 , g(n)=25n3+5000n2 , h(n)=n1.5+5000nlgn
请判断下列关系是否成立：
(1) f(n)=O(g(n))
(2) g(n)=O(f(n))
(3) h(n)=O(n1.5)
(4) h(n)=O(nlgn)
解答：（1）成立； （2）成立；（3）成立；（4）不成立。
7、设n为正整数，利用大"O"记号，将下列程序段的执行时间表示为n的函数。
(1) i=1; k=0;
while(i
{ k=k+10*i;i++;
}
(2) i=0; k=0;
do{
k=k+10*i; i++;
}
while(i
(3) i=1; j=0;
while(i+j<=n)
{
if (i>j) j++; 精品
else i++;
}
(4)x=n; // n>1
while (x>=(y+1)*(y+1))
y++;
(5) x=91; y=100;
while(y>0)
if(x>100)
{x=x-10;y--;}
else x++;
解答：（1）为T(n)=O(n)；（2）为T(n)=O(n)；（3）为T(n)=O(n)
（4）由x=n且x的值在程序中不变，又while的循环条件(x>=(y+1)*(y+1))可知：当(y+1)*(y+1)刚超过n的值时退出循环。
由(y+1)*(y+1)
所以，该程序段的执行时间为：
向下取整(n^0.5-1)
（5）为T(n)=O(1)
8、算法的时间复杂度仅与问题的规模相关吗?
解答：算法的时间复杂度不仅与问题的规模相关，还与输入实例中的初始状态有关。但在最坏的情况下，其时间复杂度就是只与求解问题的规模相关的。我们在讨论时间复杂度时，一般就是以最坏情况下的时间复杂度为准的。
9、按增长率由小至大的顺序排列下列各函数：
2100, (3/2)n，(2/3)n， nn ,n0.5 , n! ，2n ，lgn ,nlgn, n(3/2)
解答：常见的时间复杂度按数量级递增排列,依次为:常数阶0(1)、对数阶0(log2n)、线性阶0(n)、线性对数阶0(nlog2n)、平方阶0(n2)、立方阶0(n3)、k次方阶0(nk)、指数阶0(2n)。
先将题中的函数分成如下几类：
常数阶：2100
对数阶：lgn
K次方阶：n0.5、n(3/2)
指数阶 (按指数由小到大排)：nlgn、(3/2)n、2n、 n!、 nn
注意：(2/3)^n由于底数小于1，所以是一个递减函数，其数量级应小于常数阶。 根据以上分析按增长率由小至大的顺序可排列如下：
(2/3)n < 2100 < lgn < n0.5 < n(3/2) < nlgn < (3/2)n < 2n < n! < nn
10、设有两个算法在同一机器上运行，其执行时间分别为100n2和2n,要使前者快于后者，n至少要多大?
解答：要使前者快于后者，即前者的时间消耗低于后者，即：
100n2<2n
求解上式，可得 n=15
精品
第二章 线性表
一、基本内容
线性表的逻辑结构定义、抽象数据类型定义和各种存储结构的描述方法；在线性表的两类存储结构（顺序的和链式的）上实现基本操作、稀疏多项式的抽象数据类型定义、表示和加法的实现。
二、学习要点
1、了解线性表的逻辑结构特性是数据元素之间存在着线性关系，在计算机中表示这种关系的两类不同的存储结构是顺序存储结构和链式存储结构。用前者表示的线性表简称为顺序表，用后者表示的线性表简称为链表。
2、 熟练掌握这两类存储结构的描述方法，如一维数组中一个区域[i…j]的上、下界和长度之间的变换公式(L=j-i+1，i=j-L+1，j=i+L-1)，链表中指针p和结点*p的对应关系(结点*（p->next)是结点*p的后继等)，链表中的头结点、头指针和首元结点的区别及循环链表、双向链表的特点等。链表是本章的重点和难点。扎实的指针操作和内存动态分配的编程技术是学好本章的基本要求。
3、熟练掌握线性表在顺序存储结构上实现基本操作：查找、插入和删除的算法。
4、熟练掌握在各种链表结构中实现线性表操作的基本方法，能在实际应用中选用适当的链表结构。了解静态链表，能够加深对链表本质的理解。
2.1 基础知识
一、填空题
1、对于双向循环链表，在两个结点间插入一个新结点时需修改的指针共有 ① 个，单链表为 ② 个。
2、当向一个顺序表插入一个元素时，被插入元素之后的所有元素均需向 ① 移动一个位置，元素的移动顺序是从 ② 向 ③ 依次移动。
3. 要从一个顺序表删除一个元素时，被删除元素之后的所有元素均需向 ① 移动一个位置，元素的移动顺序是从 ② 向 ③ 依次移动。
4、在一个循环单链表中，表尾结点指针域与表头指针值 ① 。
5、在线性表的顺序存储中，元素之间的逻辑关系是通过 ① 表示的；在线性表的链接存储中，元素之间的逻辑关系是通过 ② 表示的。
6、在双向链表中，每个结点含有两个指针域，一个指向 ① 结点，另一个指向 ② 结点。
7、在一个单链表中删除p所指结点时，应执行下列操作:
q=p->next;
p->data=p->next->data;
p->next= ① ;
free(q);
8、若要在一个不带表头结点的单链表的首结点*p之前插入一个*s结点时，可执行下列操作：
s->next= ① ；
p->next=S；
t=p->data；
