第一章概论 一、填空题
1、数据的存储结构可用四种基本的存储方法表示，分别是顺序、 链式 、 索引 和 散列。 2、一个算法具有有穷性、确定性、可行性，有零个或多个输入、有一个或多个输出5个特性。 3、数据结构包括数据的 逻辑结构 、存储结构 和 运算（或基本操作）三个方面的内容。 4、数据结构中评价算法的两个重要指标是 时间 效率和 空间 效率。 5、一个数据结构在计算机中的表示称为 存储结构 。 6、从逻辑上可以把数据结构分为线性结构、非线性结构两大类
7、数据项是数据中不可再分割的最小单位；数据元素是数据集合中的一个“个体”，是计算
机程序中加工处理的基本单位。
8、健壮性指算法对非法输入能适当地做出反应或进行处理，而不会产生莫名其妙的输出结果。 9、下列语句的时间复杂度是O（n2） for(i=1;i<=n;i++) for(j=1;j<=n;j++) {++x;}
二、单项选择题
1、数据结构中，与所使用的计算机无关的是数据的（ C ）结构。 A、存储 B、 物理 C、逻辑 D、物理和存储 2、算法分析的目的是（ C ）。
A、找出数据结构的合理性 B、 研究算法中的输入和输出的关系 C、 分析算法的效率以求改进 D、 分析算法的易懂性和文档性 3、计算机算法指的是（ C ）。
A、计算方法 B、排序方法 C、 解决问题的有限运算序列 D、调度方法 4、计算机算法必须具备输入、输出和（ B ）等5个特性。
A、可行性、可移植性和可扩充性 B、可行性、确定性和有穷性 C、确定性、有穷性和稳定性 D、易读性、稳定性和安全性 5、从逻辑上可以把数据结构分为（ C ）两大类。 A、动态结构、静态结构 B、顺序结构、链式结构 C、线性结构、非线性结构 D、初等结构、构造型结构 6、下列数据中，（ C ）是非线性数据结构。 A、栈 B、队列 C、完全二叉树 D、堆 7、算法分析的两个主要方面是（ A ）。
A、空间复杂性和时间复杂性 B、正确性和简明性
1
C、可读性和文档性 D、数据复杂性和程序复杂性 8、在下面程序段的时间复杂度（ D ）。 i=1; while(i<=n) i=i*3;
A、O(3n) B、O(n) C、O(n3) D、O(log3n) 9、在下面的程序段中，对x的赋值语句的频度为（ C ）。
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
x=x+1;
A、O(2n) B、O(n) C、O(n2) D、O(log2n) 10、下面关于算法说法错误的是（ D ）。
A、算法最终必须由计算机程序实现
B、为解决某问题的算法同为该问题编写的程序含义是相同的 C、算法的可行性是指指令不能有二义性 D、以上几个都是错误的
三、判断题
1、数据的逻辑结构说明数据元素之间的顺序关系,它依赖于计算机的储存结构.(×) 2、数据的逻辑结构是指数据的各数据项之间的逻辑关系；(×) 3、数据的物理结构是指数据在计算机内的实际存储形式。(√) 4、算法的优劣与算法描述语言无关，但与所用计算机有关。(×) 5、健壮的算法不会因非法的输入数据而出现莫名其妙的状态。(√)
6、算法可以用不同的语言描述，如果用C 语言或PASCAL语言等高级语言来描述，则算法实际上就是程序了。(×)
7、数据元素是数据中不可再分割的最小单位。(×)
8、算法中的每一步，必须有确切的含义，不能产生理解上的二义性。(√)
9、采用事后统计法进行算法分析时，不会因为软硬件环境的改变而影响分析结果。(×)
10、算法的时间与空间效率是指将算法变换为程序后，该程序在计算机上运行时所花费的时间及所占据空间的度量。(√)
四、简答题
1、当为解决某一问题而选择数据结构时，应从哪些方面考虑？
答：通常考虑算法所需要的存储空间量和算法所需要的时间量。后者又涉及到四方面：程序运行时所需输入的数据总量，对源程序进行编译所需时间，计算机执行每条指令所需时间和程序中指令重复执行的次数。
2
第2章 线性表 一、填空
1、当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用 顺序 存储结构。
2、顺序存储的线性表存储结构的特点是：用 物理位置的相邻 表示元素之间的关系的，在顺序表中插入或删除一个元素，移动的元素个数与 表长 和 该元素在表中的位置 有关。 3、设单链表的结点结构为(data，next)，next为指针域，指针p指向单链表中data为x的结点，指针q指向data为y的新结点，若将结点y插入结点x之后，则需要依次执行以下语句：__ q->next=p->next; _ p->next=q
4、在顺序表中访问任意一结点的时间复杂度均为 O(1) ，因此，顺序表也称为 随机存取的数据结构。
5、链式存储结构的特点是利用__指针 来表示数据元素之间的逻辑关系。在单链表中，除了首元结点外，任一结点的存储位置由 其直接前驱结点的链域的值 指示，查找结点都必须从头结点开始，因此，链表也称为 顺序存取 的数据结构。
6、已知指针p指向单链表L中的某结点，u是P的直接后继，删除u的语句是：p->next=u->next; free(u);
7、带头结点的双循环链表L中只有一个元素结点的条件是：L->next->next==L；
8、在顺序表L=（a1,a2,?,an）中，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是（n-1）/2_；第i个元素（1<=i<=n）之前插入一个元素时，需向后移动n-i+1_个元素。如果要在第1个元素前插入一个元素，要后移 n 个元素；删除第i个元素(1≤i≤n)时，需向前移动 n-i 个元素。
9、在n个结点的单链表中要删除已知结点*p，需找到它的前驱结点的地址，其时间复杂度为O（n），在给定值为x的结点后插入一个新结点的时间复杂度为 O(n)_。
10、在非空的线性表中，有且仅有一个没有直接前趋的开始结点 a1 ；有且仅有一个没有直接后继的终端结点 an ；其余的内部结点ai(2≤i≤n-1)都有且仅有一个直接前趋ai-1和一个直接后继ai+1。
11、双向链表结构的对称性可用下式描述：p->prior)->next=p=(p->next)->prior
二、判断正误
1、线性表的特点是每个元素都有一个前驱和一个后继。（×） 2、链表的物理存储结构具有同链表一样的顺序。（×）
3、链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动地将后续的各个单元向前移动。（×）
4、取线性表的第i个元素的时间同i的大小有关。 （×）
3
5、顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。（×） 6、顺序存储方式的优点是存储密度大，且插入、删除运算效率高。（×）
7、链表是采用链式存储结构的线性表,进行插入、删除操作时，在链表中比在顺序存储结构中效率高。(√)
8、线性表在顺序存储时，逻辑上相邻的元素未必在存储的物理位置次序上相邻。（×） 9、顺序存储方式只能用于存储线性结构。（×） 10、线性表的逻辑顺序与存储顺序总是一致的。（×） 11、链表中的头结点仅起到标识的作用。（×）
12、顺序存储结构的主要缺点是不利于插入或删除操作。(√)
13、线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。(√) 14、顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好。（×） 15、对任何数据结构链式存储结构一定优于顺序存储结构。（×） 16、顺序存储的线性表，优点是空间利用率很高。(×)
17、在单链表上插入、删除一个结点，必须知道其前驱结点。(√)
18、遍历操作时，循环链表和非循环链表的终止条件判断是一样的。(×)19、顺序表能按元素序号随机访问，而链表只能顺序查找。(√)
20、在顺序表中做插入删除操作时，平均移动大约表中一半的元素，因此对n较大的顺序表效率低。(√)
三、单项选择题
1、数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称之为（ C ）。 A、存储结构 B、逻辑结构 C、顺序存储结构 D、链式存储结构
2、一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（ B ）
A、110 B、108 C、100 D、120
3、在n个结点的顺序表中，算法的时间复杂度是O（1）的操作是（ A ）。 A、访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n） B、在第i个结点后插入一个新结点（1≤i≤n） C、删除第i个结点（1≤i≤n） D、将n个结点从小到大排序
4、向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动（ B ）个元素。
A、8 B、63.5 C、63 D、7
5、线性表（ a1,a2,?,an）以链接方式存储时，访问第i位置元素的时间复杂性为（ C ）。
A、O（i） B、O（1） C、O（n） D、O（i-1）
6、链表是一种采用（ B ）存储结构存储的线性表。
4
A、顺序 B、链式 C、星式 D、网状
7、线性表若采用链式存储结构时，要求内存中可用存储单元的地址（ D ）。 A、必须是连续的 B、部分地址必须是连续的 C、一定是不连续的 D、连续或不连续都可以
8、线性表Ｌ在（ B ）情况下适用于使用链式结构实现。 A、需经常修改Ｌ中的结点值 B、需不断对Ｌ进行删除插入 C、Ｌ中含有大量的结点 D、Ｌ中结点结构复杂 9、单链表的存储密度（ C ）。
A、大于1 B、等于1 C、小于1 D、不能确定
10、对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是（ B ） A、head==NULL B、head→next==NULL C、head→ext==head D、head!=NULL 11、下面关于线性表的叙述中，错误的是哪一个？（ B ） A、线性表采用顺序存储，必须占用一片连续的存储单元。 B、线性表采用顺序存储，便于进行插入和删除操作。 C、线性表采用链接存储，不必占用一片连续的存储单元。 D、线性表采用链接存储，便于插入和删除操作。
12、某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ D ）存储方式最节省运算时间。 A、单链表 B、仅有头指针的单循环链表 C、双链表 D、仅有尾指针的单循环链表 13、链表不具有的特点是（ B ）。
A、插入、删除不需要移动元素 B、可随机访问任一元素
C、不必事先估计存储空间 D、所需空间与线性长度成正比
14、设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用( D )最节省时间。 A、单链表 B、单循环链表 C、带尾指针的单循环链表 D、带头结点的双循环链表 15、若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（ C ）(1<=i<=n+1)。
A、O(0) B、O(1) C、 O(n) D、O(n) 16、下述（A ）是顺序存储结构的优点。
A、存储密度大 B、插入运算方便
C、删除运算方便 D、可方便地用于各种逻辑结构的存储表示
17、在单链表指针为p的结点之后插入指针为s的结点，正确的操作是（ B ）。
A、p->next=s;s->next=p->next; B、s->next=p->next;p->next=s; C、p->next=s;p->next=s->next; D、p->next=s->next;p->next=s; 18、线性表是具有n个（ C ）的有限序列（n>0）。
2
5