数据结构1-3章复习重点资料
一、填空
1、一种数据结构的二元组表示如下：
K={a,b,c,d}
R=(a,b),(b,c),(c,d),(a,d)}
此数据结构是 图 。
2、在定义某种数据结构时，其数据域的数据类型可分为和 结构体类型 两种，为增强其通用性，应将其再定义为 通用数据 类型。
3、如果将线性数据结构关系描述为1：1，那么树型和图型数据结构应分别为 、 。
4、数据结构简单地说是指 以及相互之间的 系 。
5、算法应具备以下5个特性： 、 、输入和输出。
6、在分析各种算法的时间复杂度时，一般只讨论相应的数量级，用f(n)表示，请问其中n 的含义是 处理问题的样本量 。
7、 在稀疏矩阵中，元素的个数远远少于零元素的个数。
8、的运算规则为，队列的运算规则为。
9、对于一个单链表在表头插入结点的时间复杂度为 ，在表尾插入元素的时间复杂度为 O(n) 。
10、在单链表中每个结点包含二个域，一个叫值域（或data ），另一个叫
11、顺序表中用
12、在顺序表中删除一个元素，必须执行的语句是：。
二、选择题
1、下面程序段的时间复杂度为（ B ）。
for (int i=1;i
for (int j=1;j
printf(“%d*%d=%d\n”,i,j,i*j);
1
A ．O (n) B. O (n2) C ．O (1) B. O (n3)
2、顺序表物理结构中的存储单元（ A ）。
A. 一定是连续的
C. 不一定是连续的
A.S.top= =-1 B.S.top= =0
C.S.top= =MaxSize D. S.top= =MaxSize-1
4、若循环队列有 n 个顺序存储单元，front 、rear 分别为队首和队尾指针则判断队满的条件是(C)
A. (front+1)%n= =rear B. (front-1)%n= =rear
C. (rear+1) %n= =front D. (rear-1)%n= = front
5、下列是顺序存储线性表排序的算法
void Sort(List& L)
{
}
问：此算法的时间复杂性为： B
A. O(n) B.(n2) C. (n*i) D. (n*j)
6、向一个顺序栈S （栈顶指针为top ）中插入元素x 时，首先要（ B ）。 2
B. 一定是不连续的 D. 经删除操作后不连续 3、对一个顺序存储结构的栈，栈满的判断条件是（ D ） int i,j; ElemType x; for(i=1;i=0;j--) L.list[j+1]=x; if(x
A ．S->stack[S->top]=x;
C ．S ->top--; B ．S->top++; D ．x= S->stack[S->top];
7、从一个循环队列中删除元素时，首先需要（ D ）。
A ．队尾指针循环减1 B ．队首指针循环减1
C ．队尾指针循环加1 D ．队首指针循环加1
8．关于栈的插入和删除操作，正确的说法是（ C ）。
A ．插入在栈顶、删除在栈底进行
行
C ．插入和删除都在栈顶进行 D ．插入和删除都在栈底进行
9．队的插入操作在（ C ）进行。
A ．队首 B ．队首或队尾 C ．队尾 D ．任意位置
10. 若要在一个单链表HL 中的由指针p 所指结点的后面插入一个指针q 所指的结点，则应执行（ D ）。
A ．p->next= q->next； q->next=p；
B ．q->next= p->next； p = q；
C ．p->next= q->next；q->next=HL；
D ．q->next= p->next； p->next=q；
三、简答题
1、简述线性表的顺序存储和链接存储实现的异同。
【答案要点】
1) 两者的存储结构不同。顺序用物理相邻实现逻辑相邻，大多用数组实现，链接存储用链接的方式实现逻辑相邻，物理上不一定相邻；
2) 存储相同数量的数据，顺序存储占用空间小，链接存储占用空间大；
3) 读取操作：顺序存储为按元素序号随机访问，效率较高；链接存储为按元素序号顺序访问，效率较低；
4) 插入和删除操作：顺序存储要移动约半数元素，效率较低；链接存储不需移动现有元素，效率较高；
2、举例说明顺序存储的栈在元素出栈和进栈时栈顶指针的变化。
3
B ．插入在栈底，删除在栈顶进
1）由于顺序栈是由数组存储，元素进栈出栈只能在栈顶进行，用top 表示栈顶元素的下标，每次进栈top++;出栈top--。
2）用ABCD 四个元素按顺序进、出栈，其top 值变化如下：
初始状态：top=-1 4
3
2`
1
0`
ABC 进栈后：
4
3
2top
10
CB 出栈
4
3
2
1
D 再进栈
4
3
2
10
3、说明顺序存储的队列，在解决队满与队空的判断条件时，为什么将队首指针指向第一个元素之前？这样解决后存储容量有什么变化？
4
1）如果f 指向队首元素，r 指向队尾元素，由于队空和队满条件一样（r+1）%MaxSize==f，所以要将队首指针指向第一个元素之前（或其他方法）。
2）这样，队列中始终有一个存储空间不能用于存储元素，于是存储容量变为MaxSize-1。
四、判断题，并简单说明原因：
1、线性表的逻辑顺序和存储顺序总是一致的。
【解答】错。顺序表的逻辑顺序和存储顺序一致，链表的逻辑顺序和存储顺序 不一定一致。
2、线性表的顺序存储结构优于链接存储结构。
【解答】错。两种存储结构各有优缺点。
3、顺序表中的元素可以存储于任何位置。
【解答】错。顺序表中的元素必须按照逻辑顺序存储于对应的数组位置上。
4、 线性结构的基本特征是：每个元素有且仅有一个直接前驱和一个直接后继。
【解答】错。每个元素最多只有一个直接前驱和一个直接后继，第一个元素没 有前驱，最后一个元素没有后继。
5、 在单链表中，要取得某个元素，只要知道该元素所在结点的地址即可，因 此单链表是随机存取结构。
【解答】错。要找到该结点的地址，必须从头指针开始查找，所以单链表是顺 序存取结构。
五、有一个顺序循环队列，最大存储空间为MAXSIZE=5，队首指针f 指向队首元素的前一单元，队尾指针r 指向队尾元素，初始时状态如图所示。现有A, B, C, D, E, F等元素入队，试按下列要求添画图形或回答问题。（12分，①—③各2分，④6分）
初始状态
5
`123
4
① A, B, C三元素依次入队后队列中的状况和队首队尾指针位置；
01
A 2B 3C
4`
② 接下来两个元素出队后队列中的状况和队首队尾指针位置
(出队的元素不要画出
)
0123
C
4`
③ 接下来剩余尚未入队的所有元素入队后队列中的状况和队首队尾指针位置
E 1F
23C 4D
6
④ 该队列的数据结构定义为：
struct QueueSq{
};
不考虑健壮性条件，写出下列入队算法中缺失的语句：
void EnQueue(struct QueueSq* Q, ElemType x)
{
}
不考虑健壮性条件，写出下列出队算法中缺失的语句：
ElemType OutQueue(struct QueueSq* Q)
{
…
}
参考以上两算法和数据结构，写出队满的条件：
(Q->rear+1)%Q->MaxSize==Q->front
和队空的条件：
Q->front==Q->rear
六、用f(n)=2为例，说明栈与递归算法之间的关系。 n ElemType *queue; int front,rear; int MaxSize; … Q->queue[Q->rear]=x; … Q->rear=(Q->rear+1)%Q->MaxSize; … return Q->queue[Q->front]; Q->front=(Q->front+1)%Q->MaxSize;
要点1：栈只能在栈顶操作；
7
要点2：递归算法是解决一个问题时，是通过解决与它具有相同解法的子问题而得到的；
要点3：在进行递归调用时，计算机系统自动建立栈，用于存储递归调用参数（下例中的）n 和返回地址（下例中的r ）, 进栈；
要点4：当在一定条件下结束递归调用时，系统按照栈中存储的系数和返回地址逐步返回（出栈）到最初调用处，并得到最终结果。
例：求f(n)= 2n f(n)=1 n=0
f(n)=2*f(n-1) n>0 当 n=3时
七、
已知线性表A={a1、a 2、……an}采用顺序存储结构，其数据域为整型 要求：
1、定义单链表结点（包括对数据域的定义）；
2、从顺序表的表尾删除一个结点。
（参考答案）
答1：
typedef int ElemType;
struct List{
ElemType *list;
int size;
int MaxSize;
};
答2：
8
退栈
ElemType DeleteLastList(struct List *L) {
}
八、
已知线性表A={a1、a 2、……an}采用链接存储结构，其数据域为整型 要求：
1、定义单链表结点（包括对数据域的定义）；
2、从单链表的表尾删除一个结点。 （参考答案）
答1：
typedef int ElemType;
struct sNode {
ElemType data;
struct sLNode *next;
{
}
9
if(L->size==0) { } ; L->size--; return L->list[L->size]; exit(1); printf("线性表为空，删除无效\n"); }; sNode *p=HL; while(p->next!=NULL) p=p->next; temp=p->data; delete p; return temp; 答2：ElemType Delete(struct sLNode *HL)
10