2012新疆维吾尔自治区C与数据结构链表考试技巧与口诀

c语言入门必背单词口诀变量常量与标识符：
名字记下来，常量不变更。

变量有类型，标识符自取。

算术运算符与赋值运算：
加减乘除余，自增自减要。

等于号赋值，不等号判断。

关系运算与逻辑运算：
大于小于等于，关系运算清楚。

逻辑运算也很关键，与或非三种不忘记。

条件语句与循环语句：
if else是条件语，三目运算也要会。

while do while for，三种循环要熟记。

函数调用与参数传递：
函数调用不偏离，参数传递要清楚。

值传递、引用传递，二者要分清。

数组与指针：
数组定义要规范，指针运算要清晰。

下标从零开始，指针加减要正确。

结构体与链表：
结构体定义要注意，链表遍历要谨慎。

单链表双链表，二者区别要清楚。

数据结构 – Data Structures
第三章 栈和队列
本章内容：
3.1 栈 3.1.1 栈的定义 3.1.2 栈的表示和实现
3.2 栈的应用举例 3.3 栈与递归 3.4 队列
3.4.1 队列的定义 3.4.2 链队列 3.4.3 循环队列
西安电子科技大学 - Xidian University, China 18
}SLink,*LinkList;
LinkList head,tail;
西安电子科技大学软件学院 - School of Software, Xidian University, China
例题
数据结构 – Data Structures
1. 顺序表中，逻辑上相邻的数据元素在物理位置上( 也相邻 ) 。 线性表L=(a1,a2,...,an)采用顺序存储，假定在不同的n+1个位置 上的插入概率相同，则插入一个新元素平均需要移动的元素个
例题
数据结构 – Data Structures
6. 编写算法，将一个带头结点的单链表就地逆置。（请先说明算法思路，再用类高级 语言编写算法。 ）
head
…
…
∧
a1
a2
ai-1
ai
ai+1
an-1
an
单链表逆置
head
∧
…
…
a1
a2
ai-1
ai
ai+1
an-1
an
西安电子科技大学 - Xidian University, China
if (s%2)
② n2 ③n
print(s);
}
西安电子科技大学 - Xidian University, China

一、填空题（一）链表类型题目包括：15、42、43、50、56、75、79、85、86、87技巧解析：1、首先看清楚题目要求和意思。

看清楚链表有没有带头结点，如果带有头结点，指向数据源的指针内容是p=h—>next;如果是不带有头结点，则填写的是p=h;2、如果所要填写的空在循环语句while的括号中的时候，里面的内容填写的是p或者是q,以最近出现的为主;如果是在循环语句的里面的时候，填写的是q=p —>next;3、如果是排序的时候，从小到大的时候是大于号，从大到小的时候是小于号。

4、如果链表题目中考到调用函数，一般只需要填入实参head,例如：fun(head);在构造链表的时候都会有头结点，一般用head来表示，head指向了链表中的第一个数据的地址。

细化分类：1.将数据域中的数据进行排序，类似题目：15、42void fun(NODE *h){ NODE *p, *q; int t;/**********found**********/p = __1__ ;指向数据源，由于h是带头结点的链表，因此需要填入h->next while (p) {判断链表p是否已经到末尾/**********found**********/q = __2__ ; 比较两个数的大小，因此需要q指向p中的下一个数据需要填入p->next，也就是说p指向了第一个数据，q指向了第二个数据。

while (q) {判断q是否指向了末尾/**********found**********/if (p->data __3__ q->data)从小到大排序，因此填入大于符号{ t = p->data; p->data = q->data; q->data = t; }交换数据 q = q->next; q自增，目的是比较出最小的数据}p = p->next; p自增}}联想记忆分析1：对一维数组进行从小到大排序void fun(int b[N]){ int i, j, a;for(i=0;i<N-1;i++)for(j=i;j<N;j++){if(b[i]>b[j]){a=b[i];b[i]=b[j];b[j]=a;}}}联想记忆分析2：对结构体数组按照姓名进行从小到大排序for(i=0;i<N-1;i++)for(j=i;j<N;j++){if(strcmp(a[i].name,a[j].name)>0){a=b[i];b[i]=b[j];b[j]=a;}2.将数据域中的元素逆置，类似的题目：43、50链表中数据域中的元素逆置，首先将第一个数据取出来放在最后一个位置，也就是将其next置空，表示已经到了末尾。

1、对待排序的元素序列进行划分，将其分为左、右两个子序列，再对两个子序列施加同样的排序操作，直到子序列为空或只剩一个元素为止。

这样的排序方法是（ A ）。

A）直接选择排序 B）直接插入排序C）快速排序 D）起泡排序2、队列的操作的原则是（ A ）。

A）先进先出 B) 后进先出C) 只能进行插入 D) 只能进行删除3、设有一个栈，元素的进栈次序为A, B, C, D, E,下列是不可能的出栈序列是（ C ）。

A） A, B, C, D, EB） B, C, D, E, AC） E, A, B, C, DD） E, D, C, B, A4、串的逻辑结构与（ D ）的逻辑结构不相同。

A）线性表 B）栈C）队列 D）集合5、下列序列中，执行第一趟快速排序后得到的序列是（ A ）。

A）[d,a,e,d,b]f[h,g] B) [c,e,a,d]f[h,g,b]C) [g,a,e,c,b]f[d,h] D) [a,b,c,d,]f[e,g,h]6、若采用邻接矩阵法存储一个n个顶点的无向图，则该邻接矩阵是一个（ D ）。

A）上三角矩阵 B) 稀疏矩阵C) 对角矩阵 D) 对称矩阵7、二叉树第i(i≥1)层上至多有（ C ）结点。

A）2i B）2i C）2i-1 D）2i-18、栈进行插入和删除操作的特点是（ A ）。

A）LIFO B）FIFOC）FCFS D）HPF9、在一个链队列中，假定front和rear分别为队首和队尾指针，则插入一个结点的操作为（ B ）。

A）front=front->next; B） rear=rear->next;C） rear=front->next; D） front=rear->next ;10、与无向图相关的术语有（ C ）。

A）强连通图 B）入度C）路径 D）弧11、已知栈的最大容量为4。

若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行,则可能出现的出栈序列为（ C ）。