第1章 绪论
1.1 简述下列术语：数据，数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。 解：数据是对客观事物的符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。
数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 数据对象是性质相同的数据元素的集合，是数据的一个子集。 数据结构是相互之间存在一种或多种特定关系的数据元素的集合。 存储结构是数据结构在计算机中的表示。
数据类型是一个值的集合和定义在这个值集上的一组操作的总称。
抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。是对一般数据类型的扩展。
1.2 填空题：
1.常见的数据结构有_线性__结构，__树形___结构，__图形__结构等三种。 2.常见的存储结构有__顺序存储_______结构，__链式存储____结构等两种。 3.数据的基本单位是_数据元素___，它在计算机中是作为一个整体来处理的。4.数据结构中的结构是指数据间的逻辑关系，常见的结构可分为两大类，__线性结构____和__非线性结构___。
5.《数据结构》课程讨论的主要内容是数据的逻辑结构、存储结构和_____算法
1.2 设有数据结构(D,R)，其中
D??d1,d2,d3,d4?，R??r?，r???d1,d2?,?d2,d3?,?d3,d4??
试按图论中图的画法惯例画出其逻辑结构图。
解：
1.3设有以下三个函数：
f?n??21n4?n2?1000，g?n??15n4?500n3，h?n??500n3.5?nlogn
请判断以下断言正确与否：
(1) f(n)是O(g(n)) (2) h(n)是O(f(n)) (3) g(n)是O(h(n)) (4) h(n)是O(n3.5
) (5) h(n)是O(nlogn)
解：(1)对 (2)错 (3)错 (4)对 (5)错
___。
_ 第二章 序列
2.1 描述以下三个概念的区别：头指针，头结点，首元结点（第一个元素结点）。
解：头指针是指向链表中第一个结点的指针。首元结点是指链表中存储第一个数据元素的结点。头结点是在首元结点之前附设的一个结点，该结点不存储数据元素，其指针域指向首元结点，其作用主要是为了方便对链表的操作。它可以对空表、非空表以及首元结点的操作进行统一处理。
2.2 填空题。
(1) 在顺序表中插入或删除一个元素，需要平均移动表中一半元素，具体移动的元素个数与元素在表中的位置有关。
(2) 顺序表中逻辑上相邻的元素的物理位置必定紧邻。单链表中逻辑上相邻的元素的物理位置不一定紧邻。
(3) 在单链表中，除了首元结点外，任一结点的存储位置由其前驱结点的链域的值指示。
(4) 在单链表中设置头结点的作用是插入和删除首元结点时不用进行特殊处理。
(5) 线性表按照存储结构不同主要有两种实现方式，一种是__顺序_表，另一种是___链___表。 (6)顺序表采用__随机___访问机制对数据元素进行访问。
(7)在单向链表中，若要删除某个结点p，一般要找到__p的前趋__结点，才能实现该操作。 （8）若频繁地对线性表进行插入与删除操作，该线性表应采用______链式_____存储结构。 （9）判断带头结点head的循环链表是空链表的条件是_____head->next==head______。
（10）已知指针p指向单链表中某个结点，语句p->next=p->next->next的作用是__删除P后面的结点_____。
(11)从一个具有100个结点的单链表中查找其值等于x结点时，在查找成功的情况下，需要平均比较的结点数是___50.5_ 。
（12）在一个长度为n的顺序表中，删除第i个元素时，需要移动___n-i____个元素。
2.3选择题、判断题：
1.若长度为n的线性表采用顺序存储结构，在其第i个位置删除一个元素的算法的平均时间复杂度为( C )。(1≤i≤n)
A．O(0) B．O(1) C.O(n) D．O(n2)
2. 若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素需要移动的元素个数为( B )。(1≤i≤n+1)
A．n-i B．n-i+1 C. i D．n-i-1
3.线性表中每一个元素都有一个前驱和一个后继。（ × ） 4.线性表的逻辑顺序与物理顺序总是一致的。(× )
5． 判断带头指针head的单向循环链表是否为空链表的条件是head->next==NULL。（×）
6.带头结点的单链表A长度为m，带头结点的单链表B长度为n，若将B链接在A的末尾，其时间复杂度应为 （ A ） 。
A、 O(1) B、O(m) C、O(n) 域的值。
A、1 B、2 C、3 D、4
D、O(m+n)
7.在一个双向链表中，若要在p所指向的结点之后插入一个新结点，则需要相继修改（ C ）个结点的指针
2.4 已知L是无表头结点的单链表，且P结点既不是首元结点，也不是尾元结点，试从下列提供的答案中选择合适的语句序列。
a. 在P结点后插入S结点的语句序列是__________________。 //b. 在P结点前插入S结点的语句序列是__________________。 c. 在表首插入S结点的语句序列是__________________。 //d. 在表尾插入S结点的语句序列是__________________。 (1) P->next=S;
(2) P->next=P->next->next; (3) P->next=S->next; (4) S->next=P->next; (5) S->next=L; (6) S->next=NULL; (7) Q=P;
(8) while(P->next!=Q) P=P->next; (9) while(P->next!=NULL) P=P->next; (10) P=Q; (11) P=L; (12) L=S; (13) L=P; 解：a. (4) (1)
b. (7) (11) (8) (4) (1) c. (5) (12) d. (9) (1) (6)
2.5在如下数组A中链接存储了一个线性表，表头指针为A[0].next，试写出该线性表。 其中数组A的定义如下：
struct node {
int data;
struct node *next; }A[8];
A 0 1 2 3 4 5 6 7 data next
解：70,50,40,60,30,90
3 60 5 50 7 70 2 90 0 30 4 40 1
2.6设指针变量p指向双向链表中结点A，指针变量q指向被插入结点B，要求给出在结点A的后面插入结点B的操作序列（设双向链表中结点的两个指针域分别为llink和rlink）。 解：略。
第三章 队列和栈
1、填空题
1.栈和队列在本质上都是___线性表__________。
2.栈的操作特点是__后进先出_。队列的操作特点是_先进先出__。 3、栈结构中允许进行插入、删除操作的一端为___栈顶____。
4、已知循环队列的存储空间为数组data[21]，且头指针和尾指针分别为8和3，则该队列的当前长度为__16__。
2、选择题
1．消除递归不一定需要使用栈，此说法___A____。 A. 正确 B. 错误
2．对于栈，输入序列为（1，2，3，4），不可能得到的输出序列有__D_____。 (A)（1，2，3，4） (B)（4，3，2，1） (C)（1，3，4，2） (D)（3，1，2，4）
3．用单循环链表表示队列，正确的说法是 B 。 (A)可设一个头指针使入队、出队都方便； (B)可设一个尾指针使入队、出队都方便； (C)必须设头尾指针才能使入队、出队都方便； (D)无论如何,只可能使入队方便。
4．在栈中存取数据的原则是 。
A、先进先出 B、后进后出 C、先进后出 D、随意进出
5．用长度为MAX的数组来存储循环队列，用front和rear分别表示队首和队尾指针，则队列长度为_____D_____。
A、(rear+front+MAX)%MAX B、 rear-front C、(rear-front-MAX)%MAX D、(rear-front+MAX)%MAX 6．链式栈与顺序栈相比，一个比较明显的优点是___B___。
A、插入操作更加方便 B、通常不会出现栈满的情况
C、 不会出现栈空的情况 D、删除操作更加方便
7．在队列中存取数据的原则是 A 。
A、 先进先出 B、后进先出 C、先进后出 D、随意进出
8．设输入序列是1、2、3、……、n，经过栈的作用后输出序列的第一个元素是n，则输出序列中第i个输出元素是__B__。
A、n-i B、n-i+1 C、n-i-1 D、不能确定
3、判断题
1.栈的特点是先进先出。（ × ） 2.可以在队列的任意位置插入元素。（ ×） 3.递归程序化非递归程序必须用到栈。（ × ） 4.如果进栈的序列为（1，2，3，4），则（4，2，3，1）不可能是出栈序列。（√） 5.在用顺序表表示的循环队列中，可用标志位来区分队空或队满的条件。（√） 6.栈是一种线性结构。（√ ）
7.单向循环链表从任何一个结点出发，都能访问到所有结点。（ √）
8.顺序栈是线性结构，链栈不是线性结构。（×） 9.堆的形状是一棵完全二叉树。（√ ）
4、综合题：
1.简述栈和线性表的差别。
解：线性表是具有相同特性的数据元素的一个有限序列。栈是限定仅在表尾进行插入或删除操作的线性表。