数据结构算法背诵
一、线性表
1. 逆转顺序表中的所有元素
算法思想：第一个元素和最后一个元素对调，第二个元素和倒数第二个元素对调，……，依此类推。
void Reverse(int A[], int n)
{
int i, t;
for (i=0; i < n/2; i++)
{
t = A[i];
A[i] = A[n-i-1];
A[n-i-1] = t;
}
}
2. 删除线性链表中数据域为item 的所有结点
算法思想：先从链表的第2 个结点开始，从前往后依次判断链表中的所有结点是否满足条件，若某个
结点的数据域为item，则删除该结点。最后再回过头来判断链表中的第1 个结点是否满足条件，若
满足则将其删除。
void PurgeItem(LinkList &list)
{
LinkList p, q = list;
p = list->next;
while (p != NULL)
{
if (p->data == item) {
q->next = p->next;
free(p);
p = q->next;
} else {
q = p;
p = p->next;
}
}
if (list->data == item)
{
q = list;
list = list->next;
free(q);
}
}
3. 逆转线性链表
void Reverse(LinkList &list)
{
LinkList p, q, r;
p = list;
q = NULL;
while (p != NULL)
{
r = q;
q = p;
p = p->next;
q->next = r;
}
list = q;
}
4. 复制线性链表（递归）
LinkList Copy(LinkList lista)
{
LinkList listb;
if (lista == NULL)
return NULL;
else {
listb = (LinkList)malloc(sizeof(LNode));
listb->data = lista->data;
listb->next = Copy(lista->next);
return listb;
}
}
5. 将两个按值有序排列的非空线性链表合并为一个按值有序的线性链表LinkList MergeList(LinkList lista, LinkList listb)
{
LinkList listc, p = lista, q = listb, r;
// listc 指向lista 和listb 所指结点中较小者
if (lista->data <= listb->data) {
listc = lista;
r = lista;
p = lista->next;
} else {
listc = listb;
r = listb;
q = listb->next;
}
while (p != NULL && q != NULL)
if (p->data <= q->data) {
r->next = p;
r = p;
p = p->next;
} else {
r->next = q;
r = q;
q = q->next;
}
}
// 将剩余结点（即未参加比较的且已按升序排列的结点）链接到整个链表后面
r->next = (p != NULL) ? p : q;
return listc;
}
3
二、树
1. 二叉树的先序遍历（非递归算法）
算法思想：若p 所指结点不为空，则访问该结点，然后将该结点的地址入栈，然后再将p 指向其左孩
子结点；若p 所指向的结点为空，则从堆栈中退出栈顶元素（某个结点的地址），将p 指向其右孩子
结点。重复上述过程，直到p = NULL 且堆栈为空，遍历结束。
#define MAX_STACK 50
void PreOrderTraverse(BTree T)
{
BTree STACK[MAX_STACK], p = T;
int top = -1;
while (p != NULL || top != -1)
{
while (p != NULL)
{
VISIT(p);
STACK[++top] = p;
p = p->lchild;
}
p = STACK[top--];
p = p->rchild;
}
}
2. 二叉树的中序遍历（非递归算法）
算法思想：若p 所指结点不为空，则将该结点的地址p 入栈，然后再将p 指向其左孩子结点；若p 所
指向的结点为空，则从堆栈中退出栈顶元素（某个结点的地址）送p，并访问该
结点，然后再将p 指
向该结点的右孩子结点。重复上述过程，直到p = NULL 且堆栈为空，遍历结束。#define MAX_STACK 50
void InOrderTraverse(BTree T)
{
BTree STACK[MAX_STACK], p = T;
int top = -1;
while (p != NULL || top != -1);
{
while (p != NULL)
{
STACK[++top] = p;
p = p->lchild;
}
p = STACK[top--];
VISIT(p);
p = p->rchild;
}
}
4
3. 二叉树的后序遍历（非递归算法）
算法思想：当p 指向某一结点时，不能马上对它进行访问，而要先访问它的左子树，因而要将此结点
的地址入栈；当其左子树访问完毕后，再次搜索到该结点时（该结点地址通过退栈得到），还不能对
它进行访问，还需要先访问它的右子树，所以，再一次将该结点的地址入栈。只有当该结点的右子
树访问完毕后回到该结点时，才能访问该结点。为了标明某结点是否可以访问，引入一个标志变量
flag，当flag = 0 时表示该结点暂不访问，flag = 1 时表示该结点可以访问。flag 的值随同该结点的地
址一起入栈和出栈。因此，算法中设置了两个堆栈，其中STACK1 存放结点的地址，STACK2 存放
标志变量flag，两个堆栈使用同一栈顶指针top，且top 的初始值为?1。
#define MAX_STACK 50
void PostOrderTraverse(BTree T)
{
BTree STACK1[MAX_STACK], p = T;
int STACK2[MAX_STACK], flag, top = -1;
while (p != NULL || top != -1)
{
while (p != NULL) {
STACK1[++top] = p;
STACK2[top] = 0;
p = p->lchild;
}
p = STACK1[top];
flag = STACK2[top--];
if (flag == 0) {
STACK1[++top] = p;
STACK2[top] = 1;
p = p->rchild;
} else {
VISIT(p);
p = NULL;
}
}
}
4. 二叉树的按层次遍历
算法思想：设置一个队列，首先将根结点（的地址）入队列，然后依次从队列中退出一个元素，每
退出一个元素，先访问该元素所指的结点，然后依次将该结点的左孩子结点（若存在的话）和右孩
子结点（若存在的话）入队列。如此重复下去，直到队列为空。
#define MAX_QUEUE 50
void LayeredOrderTraverse(BTree T)
{
BTree QUEUE[MAX_QUEUE], p;
int front, rear;
if (T != NULL)
{
QUEUE[0] = T;
front = -1;
rear = 0;
while (front < rear)
{
p = QUEUE[++front];
VISIT(P);
if (p->lchild != NULL)
QUEUE[++rear] = p->lchild;
if (p->rchild != NULL)
QUEUE[++rear] = p->rchild;
}
}
}
5
5. 建立二叉树（从键盘输入数据，先序遍历递归算法）
BTree CreateBT()
char ch;
BTree T;
sacnf("%c", &ch);
if (ch == ' ')
return NULL;
else {
T = (BTree)malloc(sizeof(BTNode));
T->data = ch;
T->lchild = CreateBT();
T->rchild = CreateBT();
return T;
}
}
6. 建立二叉树（从数组获取数据）
BTree CreateBT(int A[], int i, int n)
{
BTree p;
if (i > n)
return NULL;
else {
p = (BTree)malloc(sizeof(BTNode));
p->data = A[i];
p->lchild = CreateBT(A, 2*i, n);
p->rchild = CreateBT(A, 2*i+1, n);
return p;
}
}
T = CreateBT(A, 1, n);
-------------------------------------------------------- BTree CreateBT(int A[], int n)
{
int i;
BTree *pT;
// 对应n 个结点申请可容纳n 个指针变量的内存空间
pT = (BTree *)malloc(sizeof(BTree)*n);
// 若数组中的某个元素不等于零，则申请相应的结点空间并进行赋值
for (i=1; i <= n; i++)
{
if (A[i] != 0) {
pT[i] = (BTree)malloc(sizeof(BTNode));
pT[i]->data = A[i];
} else {
pT[i] = NULL;
}
// 修改结点的指针域的内容，使父结点指向左、右孩子结点
for (i=1; i <= n; i++)
{
if (pT[i] != NULL)
{
pT[i]->lchild = pT[2*i];
pT[i]->rchild = pT[2*i+1];
}
}
}
6
7. 求二叉树的深度（递归算法）
int Depth(BTree T)
{
int ldepth, rdepth;
if (T == NULL)
return 0;
else {
ldepth = Depth(T->lchild);
rdepth = Depth(T->rchild);
if (ldepth > rdepth)
return ldepth+1;
else
return rdepth+1;
}
}
8. 求二叉树的深度（非递归算法）
算法思想：对二叉树进行遍历，遍历过程中依次记录各个结点所处的层次数以及当前已经访问过的
结点所处的最大层次数。每当访问到某个叶子结点时，将该叶子结点所处的层次数与最大层次数进
行比较，若前者大于后者，则修改最大层次数为该叶子结点的层次数，否则不作修改。遍历结束时，
所记录的最大层次数即为该二叉树的深度。本算法使用的是非递归的中序遍历算法（其它遍历顺序
也可以）。
#define MAX_STACK 50
int Depth(BTree T)
{
BTree STACK1[MAX_STACK], p = T;
int STACK2[MAX_STACK];
int curdepth, maxdepth = 0, top = -1;
{
curdepth = 1;
while (p != NULL || top != -)
{
while (p != NULL)
{
STACK1[++top] = p;
STACK2[top] = curdepth;
p = p->lchild;
curdepth++;
}
p = STACK1[top];
curdepth = STACK2[top--];
if (p->lchild == NULL && p->rchild == NULL)
if (curdepth > maxdepth)
maxdepth = curdepth;
p = p->rchild;
curdepth++;
}
}
return maxdepth;
}
7
9. 求结点所在层次
算法思想：采用后序遍历的非递归算法对二叉树进行遍历，遍历过程中对每一个结点判断其是否为
满足条件的结点，若是满足条件的结点，则此时堆栈中保存的元素个数再加1 即为该结点所在的层次。
#define MAX_STACK 50
int LayerNode(BTree T, int item)
{
BTree STACK1[MAX_STACK], p = T;
int STACK2[MAX_STACK], flag, top = -1;
while (p != NULL || top != -1)
{
while (p != NULL)
{
STACK1[++top] = p;
STACK2[top] = 0;
p = p->lchild;
}
p = STACK1[top];
flag = STACK2[top--];
STACK1[++top] = p;
STACK2[top] = 1;
p = p->rchild;
} else {
if (p->data == item)
return top+2;
p = NULL;
}
}
}
10.交换二叉树中所有结点的左右子树的位置
算法思想：按层次遍历二叉树，遍历过程中每当访问一个结点时，就将该结点的左右子树的位置对
调。
#define MAX_QUEUE 50
void ExchangeBT(BTree T)
{
BTree QUEUE[MAX_QUEUE], temp, p = T;
int front, rear;
if (T != NULL)
{
QUEUE[0] = T;
front = -1;
rear = 0;
while (front < rear)
{
p = QUEUE[++front];
temp = p->lchild;
p->lchild = p->rchild;
p->rchild = temp;
if (p->lchild != NULL)
QUEUE[++rear] = p->lchild;
if (p->rchild != NULL)
QUEUE[++rear] = p->rchild;
}
}
}
8
11.删除二叉树中以某个结点为根结点的子树
算法思想：先序遍历找到符合条件的结点（其它遍历方法亦可），然后删除以该结点为根结点的子树。
最后把该结点的父结点的相应的指针域置为NULL。为此，需在算法中设置一个指针变量用以指示当
前结点的父结点。
#define MAX_STACK 50
BTree DeleteSubtree(BTree &T, int item)
{
BTree STACK[MAX_STACK], q, p = T;
int top = -1;
if (T->data == item)
{
DestroyBT(T);
T = NULL;
return NULL;
}
else
{
while (p != NULL || top != -1)
{
while (p != NULL)
{
if (p->data == item)
{
if (q->lchild == p)
q->lchild = NULL;
else
q->rchild = NULL;
DestroyBT(p);
return T;
}
STACK[++top]= p;
q = p;
p = p->lchild;
}
q = STACK[top--];
p = q->rchild;
}
}
}
9
三、查找
1. 顺序查找的递归算法
int RecurSeqSearch(int A[], int n, int key, int i) {
if (i >= n)
return -1;
if (A[i] == key)
return i;
else
return RecurSeqSearch(A, n, key, i+1);
}
pos = RecurSeqSearch(A, n, key, 0);
2. 折半查找
int BinSearch(int A[], int n, int key)
{
int low=0, high=n-1, mid;
while (low <= high)
{
mid = (low+high)/2;
if (key == A[mid])
return mid;
if (key > A[mid])
low = mid + 1;
else
high = mid – 1;
}
return -1;
}
3. 折半查找的递归算法
int RecurBinSearch(int A[], int low, int high, int key) {
int mid;
if (low > high)
return -1;
else {
mid = (low+high)/2;
if (key == A[mid])
return mid;
if (key > A[mid])
return RecurBinSearch(A, mid+1, high, key);
else
return RecurBinSearch(A, low, mid-1, key);
}
}
pos = RecurBinSearch(A, 0, n-1, key);
10
4. 在按值递增排列且长度为n 的线性表中折半查找并插入一元素void BinInsert(int A[], int &n, int key)
{
int j, low=0, high=n-1, mid;
while (low <= high)
{
mid = (low+high)/2;
if (key > A[mid])
low = mid + 1;
else
high = mid – 1;
}
for (j=n; j > low; j--)
A[j] = A[j-1];
A[low] = key;
n++;
}
5. 在按值递增排列且长度为n 的线性表中折半查找值不小于key 的最小元素void BinSearch(int A[], int n, int key)
{
int low=0, high=n-1, mid;
while (low <= high)
{
mid = (low+high)/2;
if (key == A[mid])
return mid;
if (key > A[mid])
low = mid + 1;
else
high = mid – 1;
}
if (low <= n-1)
return low;
else
return -1;
}
11
四、排序
1. 插入排序
算法思想：第i 趟插入排序为：在含有i ? 1 个元素的有序子序列中插入一个元素，使之成为含有i
个元素的有序子序列。在查找插入位置的过程中，可以同时后移元素。整个过程为进行n ? 1 趟插入，
即先将整个序列的第1 个元素看成是有序的，然后从第2 个元素起逐个进行插入，直到整个序列有序
为止。
void InsertSort(int A[], int n)
{
int i, j, temp;
for (i=1; i <= n-1; i++)
{
if (A[i] < A[i-1])
{
j = i-1;
temp = A[i];
while (j >= 0 && temp < A[j])
{
A[j+1] = A[j];
j--;
}
A[j+1] = temp;
}
}
}
2. 折半插入排序
算法思想：算法同直接插入排序，只不过使用折半查找的方法来寻找插入位置。void BinInsertSort(int A[], int n)
{
int i, j, low, high, mid, temp;
for (i=1; i <= n-1; i++)
{
temp = A[i];
low = 0;
high = i – 1;
while (low <= high)
{
mid = (low+high)/2;
if (temp > A[mid])
low = mid + 1;
else
high = mid – 1;
}
for (j=i; j > low; j--)
A[j] = A[j-1];
A[low] = temp;
}
}
12
3. 冒泡排序
算法思想：首先将第1 个元素和第2 个元素进行比较，若前者大于后者，则两者交换位置，然后比较
第2 个元素和第3 个元素。依此类推，直到第n ? 1 个元素和第n 个元素进行过比较或交换为止。上
述过程称为一趟冒泡排序，其结果是使得n 个元素中值最大的那个元素被安排在最后一个元素的位置
上。然后进行第二趟排序，即对前n ? 1 个元素进行同样的操作，使得前n ? 1 个元素中值最大的那
个元素被安排在第n ? 1 个位置上。一般地，第i 趟冒泡排序是从前n ?i + 1 个元素中的第1 个元素
开始，两两比较，若前者大于后者，则交换，结果使得前n ?i + 1 个元素中最大的元素被安排在第n
?i + 1 个位置上。显然，判断冒泡排序结束的条件是“在一趟排序中没有进行过交换元素的操作”，
为此，设立一个标志变量flag，flag = 1 表示有过交换元素的操作，flag = 0 表示没有过交换元素的操
作，在每一趟排序开始前，将flag 置为0，在排序过程中，只要有交换元素的操作，就及时将flag 置
为1。因为至少要执行一趟排序操作，故第一趟排序时，flag = 1。
void BubbleSort(int A[], int n)
{
int i, j, temp, flag = 1;
for (i=n-1; i >= 1 && flag == 1; i--)
{
flag = 0;
for (j=0; j < i; j++)
{
if (A[j] > A[j+1])
{
temp = A[j];
A[j] = A[j+1];
A[j+1] = temp;
flag = 1;
}
}
}
}
4. 选择排序
算法思想：第i 趟排序从序列的后n ?i + 1（i = 1, 2, …, n ? 1）个元素中选择一个值最小的元素与该
个元素的第1 个元素交换位置，即与整个序列的第i 个元素交换。依此类推，直到i = n ? 1 为止。也
就是说，每一趟排序从从未排好序的那些元素中选择一个值最小的元素，然后将其与这些未排好序
的元素中的第1 个元素交换位置。
void SelectSort(int A[], int n)
{
int i, j, min, temp;
for (i=0; i < n; i++)
{
min = i;
for (j=i+1; j < n; j++)
{
if (A[min] > A[j])
min = j;
}
if (min != i)
{
temp = A[min];
A[min] = A[i];
A[i] = temp;
}
}
}
13
5. 快速排序
算法思想：在参加排序的序列中任意选择一个元素（通常称为分界元素或基准元素），把小于或等于
分界元素的所有元素都移到分界元素的前面，把大于分界元素的所有元素都移到分界元素的后面，
这样，当前参加排序的序列就被划分成前后两个子序列，其中前一个子序列中的所有元素都小于后
一个子序列的所有元素，并且分界元素正好处于排序的最终位置上。然后分别对这两个子序列递归
地进行上述排序过程，直到所有元素都处于排序的最终位置上，排序结束。void QuickSort(int A[], int n)
{
QSort(A, 0, n-1);
}
void QSort(int A[], int low, int high)
{
int pivotloc;
if (low < high)
{
pivot = Partition(A, low, high);
QSort(A, low, pivotloc-1);
QSort(A, pivotloc+1, high);
}
}
int Partition(int A[], int low, int high)
{
int pivot;
pivot = A[low];
// 从线性表的两端交替地向中间扫描
while (low < high)
{
while (low < high && A[high] >= pivot)
high--;
A[low] = A[high];
while (low < high && A[low] <= pivot)
low++;
A[high] = A[low];
}
A[low] = pivot;
return low;
}
14
6. 堆排序
void HeapSort(int A[], int n)
{
int i, temp;
// 建立大顶堆
for (i = n/2; i >= 1; i--)
HeapAdjust(A,i,n);
for (i = n-1; i >= 1; i--)
{
temp = A[1];
A[1] = A[i+1];
A[i+1] = temp;
// 将A[1..i] 重新调整为大顶堆
HeapAdjust(A,1,i);
}
}
void HeapAdjust(int A[], int low, int high) {
int i, temp;
temp = A[low];
for (i=2*low; i <= high; i=i*2)
{
// 令i 为关键字较大的记录的下标
if (i < high && A[i] < A[i+1])
i++;
if (temp >= A[i])
break;
else {
A[low] = A[i];
low = i;
}
}
A[low] = temp; // 插入}__
数据结构与算法基础知识总结 1 算法 算法：是指解题方案的准确而完整的描述。 算法不等于程序，也不等计算机方法，程序的编制不可能优于算法的设计。 算法的基本特征：是一组严谨地定义运算顺序的规则，每一个规则都是有效的，是明确的，此顺序将在有限的次数下终止。特征包括： （1）可行性； （2）确定性，算法中每一步骤都必须有明确定义，不充许有模棱两可的解释，不允许有多义性； （3）有穷性，算法必须能在有限的时间内做完，即能在执行有限个步骤后终止，包括合理的执行时间的含义； （4）拥有足够的情报。 算法的基本要素：一是对数据对象的运算和操作；二是算法的控制结构。 指令系统：一个计算机系统能执行的所有指令的集合。 基本运算和操作包括：算术运算、逻辑运算、关系运算、数据传输。 算法的控制结构：顺序结构、选择结构、循环结构。 算法基本设计方法：列举法、归纳法、递推、递归、减斗递推技术、回溯法。 算法复杂度：算法时间复杂度和算法空间复杂度。 算法时间复杂度是指执行算法所需要的计算工作量。 算法空间复杂度是指执行这个算法所需要的内存空间。 2 数据结构的基本基本概念 数据结构研究的三个方面： （1）数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构； （2）在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构；（3）对各种数据结构进行的运算。 数据结构是指相互有关联的数据元素的集合。 数据的逻辑结构包含： （1）表示数据元素的信息； （2）表示各数据元素之间的前后件关系。 数据的存储结构有顺序、链接、索引等。 线性结构条件：
（1）有且只有一个根结点； （2）每一个结点最多有一个前件，也最多有一个后件。 非线性结构：不满足线性结构条件的数据结构。 3 线性表及其顺序存储结构 线性表由一组数据元素构成，数据元素的位置只取决于自己的序号，元素之间的相对位置是线性的。 在复杂线性表中，由若干项数据元素组成的数据元素称为记录，而由多个记录构成的线性表又称为文件。 非空线性表的结构特征： （1）且只有一个根结点a1，它无前件； （2）有且只有一个终端结点an，它无后件； （3）除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。结点个数n称为线性表的长度，当n=0时，称为空表。 线性表的顺序存储结构具有以下两个基本特点： （1）线性表中所有元素的所占的存储空间是连续的； （2）线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。 ai的存储地址为：adr(ai)=adr(a1)+(i-1)k,，adr(a1)为第一个元素的地址，k代表每个元素占的字节数。 顺序表的运算：插入、删除。（详见14--16页） 4 栈和队列 栈是限定在一端进行插入与删除的线性表，允许插入与删除的一端称为栈顶，不允许插入与删除的另一端称为栈底。 栈按照“先进后出”（filo）或“后进先出”（lifo）组织数据，栈具有记忆作用。用top表示栈顶位置，用bottom表示栈底。 栈的基本运算：（1）插入元素称为入栈运算；（2）删除元素称为退栈运算；（3）读栈顶元素是将栈顶元素赋给一个指定的变量，此时指针无变化。 队列是指允许在一端（队尾）进入插入，而在另一端（队头）进行删除的线性表。rear指针指向队尾，front指针指向队头。 队列是“先进行出”（fifo）或“后进后出”（lilo）的线性表。 队列运算包括（1）入队运算：从队尾插入一个元素；（2）退队运算：从队头删除一个元素。循环队列：s=0表示队列空，s=1且front=rear表示队列满
习 9解答 判断题： 1．用向量和单链表表示的有序表均可使用折半查找方法来提高查找速度。 答：FALSE (错。链表表示的有序表不能用折半查找法。) 2.有n 个数据放在一维数组A[1..n]中，在进行顺序查找时，这n 个数的排列有序或无序其平均查找长度不同。 答：FALSE (错。因顺序查找既适合于有序表也适合于无序表；对这两种表，若对于每个元素的查找概率相等，则顺序查找的ASL 相同，并且都是(n+1)/2；对于查找概率不同的情况，则按查找概率由大到小排序的无序表其ASL 要比有序表的ASL 小。) 3.折半查找是先确定待查有序表记录的范围，然后逐步缩小范围，直到找到或找不到该记录为止。( ) 答：TRUE 4.哈希表的查找效率主要取决于哈希表哈希表造表时选取的哈希函数和处理冲突的方法。 答：TRUE 5.查找表是由同一类型的数据元素(或记录)构成的集合。 答：TRUE 单选题： 6.对于18个元素的有序表采用二分(折半)查找，则查找A[3]的比较序列的下标为( )。 A. 1、2、3 B. 9、5、2、3 C. 9、5、3 D.9、4、2、3 答：D (第一次??2/)181(+ = 9,第二次??2/)81(+ = 4，第三次??2/)31(+ = 2, (第四次??2/)33(+ = 3，故选D. 7. 顺序查找法适合于存储结构为____________的线性表。 A.散列存储 B.顺序存储或链式存储 C.压缩存储 D.索引存储 答：B 8.对线性表进行二分查找时，要求线性表必须( )。 A ．以顺序方式存储 B. 以链接方式存储 C ．以顺序方式存储，且结点按关键字有序排序 D. 以链接方式存储，且结点按关键字有序排序 答：C 9.设哈希表长m=14，哈希函数为H(k) = k MOD 11。表中已有4个记录(如下图
前端如何搞定数据结构与算法(先导篇) 「观感度：?」 「口味：锅包肉」 「烹饪时间：20min」 本文已收录在Github? 为什么要学习数据结构与算法？ 在0202年的今天，由于每天被无数的信息轰炸，大多数人已经变得越来越浮躁了，并且丧失了独立思考的能力。 你可能会经常听到这样的感慨： 技术人究竟能走多远？我遇到了天花板 35岁的程序员要如何面对中年危机？ 技术更新太快，好累，学不动了 然后，你也变得焦虑起来。那你有没有静下心来想过，如何才能抵御年龄增长并且使自己增值呢？ 无非是终身学习，持续修炼自己的内功。内功也就是基础知识和核心概念，这些轰轰烈烈发展的技术本质，其实都是基础知识，也就是我们在大学里学过的基础课-程。 操作系统 计算机组成原理 计算机网络 编译原理
设计模式 数据结构与算法 这也就是为什么越靠谱的面试官越注重你基础知识的掌握程度，为什么越牛的的企业越重视你的算法能力。因为当你拥有了这些，你已经比大多数人优秀了。你的天花板由你自己来决定，大家口中的中年危机可能并不会成为你的危机。新技术来临时，你对它的本质会看得更加透彻，学起来会一通百通。这样的人才，公司培养你也会花费更少的成本。 (不过，一辈子做个开开心心的 CRUD Boy 也是一种选择。) 数据结构与算法之间的关系 Rob Pikes 5 Rules of Programming中的第五条是这样说的： Data dominates. If youve chosen the right data structures and organized things well, the algorithms will almost always be self-evident. Data structures, not algorithms, are central to programming. 数据占主导。如果您选择了正确的数据结构并组织得当，那么这些算法几乎总是不言而喻的。数据结构而非算法是编程的核心。 瑞士计算机科学家，Algol W，Modula，Oberon 和 Pascal 语言的设计师 Niklaus Emil Wirth 写过一本非常经典的书《Algorithms + Data Structures = Programs》，即算法 + 数据结构 = 程序。 我们可以得出结论，数据结构与算法之间是相辅相成的关系。数据结构服务于算法，算法作用于特定的数据结构之上。 数据结构与算法好难，怎么学？
数据结构例题（及答案） 项目一习题(答案) 一选择题 1. 算法的计算量的大小称为计算的(B )。 A( 效率 B. 复杂性 C. 现实性 D. 难度 2.算法的时间复杂度取决于(C ) A(问题的规模 B. 待处理数据的初态 C. A和B 3(从逻辑上可以把数据结构分为(C )两大类。 A(动态结构、静态结构 B(顺序结构、链式结构 C(线性结构、非线性结构 D(初等结构、构造型结构 4(连续存储设计时，存储单元的地址(A )。 A(一定连续 B(一定不连续 C(不一定连续 D(部分连续，部分不连续 5. 以下属于逻辑结构的是(C )。 A(顺序表 B. 哈希表 C.有序表 D. 单链表 二、判断题 1. 数据元素是数据的最小单位。(×) 2. 记录是数据处理的最小单位。(×) 3. 数据的逻辑结构是指数据的各数据项之间的逻辑关系;(×) 4(程序一定是算法。(×) 5. 在顺序存储结构中，有时也存储数据结构中元素之间的关系。(×) 6. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。(×) 7. 数据结构的基本操作的设置的最重要的准则是，实现应用程序与存储结构的独立。(?)
8. 数据的逻辑结构说明数据元素之间的顺序关系,它依赖于计算机的储存结构. (×) 三、填空 1(数据的物理结构包括数据元素的表示和数据元素间关系的表示。 2. 对于给定的n个元素,可以构造出的逻辑结构有集合，线性结构，树形 结构，图状结构或网状结构四种。 3(数据的逻辑结构是指数据的组织形式，即数据元素之间逻辑关系的总体。而 逻辑关系是指数据元素之间的关联方式或称“邻接关系”。 4(一个数据结构在计算机中表示(又称映像) 称为存储结构。 5(抽象数据类型的定义仅取决于它的一组逻辑特性，而与在计算机内部如何表 示和实现无关，即不论其内部结构如何变化，只要它的数学特性不变，都不影响 其外部使用。 6(数据结构中评价算法的两个重要指标是算法的时间复杂度和空间复杂度。 7. 数据结构是研讨数据的逻辑结构和物理结构，以及它们之间的相互 关系，并对与这种结构定义相应的操作(运算)，设计出相应的算法。 ( 一个算法具有5个特性: 有穷性、确定性、可行性，有零个或多个输入、 有一个或多个输8 出。 四、应用题 1. 1. 数据结构是一门研究什么内容的学科, 答:数据结构是一门研究在非数值计算的程序设计问题中，计算机的操作对象 及对象间的关系和施加于对象的操作等的学科 2. 2. 数据元素之间的关系在计算机中有几种表示方法,各有什么特点, 答:四 种表示方法
算法与数据结构复习资料 一、单选题 在一个带有附加表头结点的单链表HL中，若要向表头插入一个由指针p指向的结点，则执行( B)。 A. HL=p;p->next=HL; B.p->next=HL->next;HL->next=p; C.p->next=HL;p=HL; D.p->next=HL;HL=p; 若顺序存储的循环队列的QueueMaxSize=n,则该队列最多可存储（B）个元素. A. n B.n-1 C.n+1 D.不确定 下述哪一条是顺序存储方式的优点？（A） A．存储密度大B.插入和删除运算方便 C. 获取符合某种条件的元素方便 D.查找运算速度快 设有一个二维数组A[m][n]，假设A[0][0]存放位置在600 (10)，A[3][3]存放位置在678 (10) ， 每个元素占一个空间，问A[2][3] (10)存放在什么位置？(脚注 (10) 表示用10进制表示,m>3)C A．658 B．648 C．633 D．653 下列关于二叉树遍历的叙述中，正确的是( D) 。 A. 若一个树叶是某二叉树的中序遍历的最后一个结点，则它必是该二叉树的前序遍历最后一个结点 B．若一个点是某二叉树的前序遍历最后一个结点，则它必是该二叉树的中序遍历的最后一个结点 C．若一个结点是某二叉树的中序遍历的最后一个结点，则它必是该二叉树的前序最后一个结点 D．若一个树叶是某二叉树的前序最后一个结点，则它必是该二叉树的中序遍历最后一个结点 k层二叉树的结点总数最多为(A). A．2k-1 B.2K+1 C.2K-1 D. 2k-1 对线性表进行二分法查找，其前提条件是( C). A.线性表以链接方式存储，并且按关键码值排好序 B.线性表以顺序方式存储，并且按关键码值的检索频率排好序 C. 线性表以顺序方式存储，并且按关键码值排好序 D. 线性表以链接方式存储，并且按关键码值的检索频率排好序 对n个记录进行堆排序，所需要的辅助存储空间为（C） A. O（1og2n） B. O（n） C. O（1） D.O（n2） 对于线性表（7，34，77，25，64，49，20，14）进行散列存储时，若选用H（K）=K%7作为散列函数，则散列地址为0的元素有（D）个， A．1 B．2 C．3 D．4 下列关于数据结构的叙述中，正确的是( D). A. 数组是不同类型值的集合 B. 递归算法的程序结构比迭代算法的程序结构更为精炼 C. 树是一种线性结构 D. 用一维数组存储一棵完全二叉树是有效的存储方法 在决定选取何种存储结构时，一般不考虑（ A ）。 A．各结点的值如何B．结点个数的多少 C．对数据有哪些运算D．所用的编程语言实现这种结构是否方便 需要分配较大空间，插入和删除不需要移动元素的线性表，其存储结构是（B）。A．单链表B．静态链表C．线性链表D．顺序存储结构 设指针变量p指向单链表中结点A，若删除单链表中结点A，则需要修改指针的操作序列为（A）。 A．q=p->next；p->data=q->data；p->next=q->next；free(q)； B．q=p->next；q->data=p->data；p->next=q->next；free(q)； C．q=p->next；p->next=q->next；free(q)；
数据结构-各类排序算法总结 原文转自： https://www.doczj.com/doc/ba10988815.html,/zjf280441589/article/details/38387103各类排序算法总结 一. 排序的基本概念 排序(Sorting)是计算机程序设计中的一种重要操作，其功能是对一个数据元素集合或序列重新排列成一个按数据元素 某个项值有序的序列。 有n 个记录的序列{R1，R2，…，Rn}，其相应关键字的序列是{K1，K2，…，Kn}，相应的下标序列为1，2，…，n。通过排序，要求找出当前下标序列1，2，…，n 的一种排列p1，p2，…，pn，使得相应关键字满足如下的非递减（或非递增）关系，即：Kp1≤Kp2≤…≤Kpn，这样就得到一个按关键字有序的记录序列{Rp1，Rp2，…，Rpn}。 作为排序依据的数据项称为“排序码”，也即数据元素的关键码。若关键码是主关键码，则对于任意待排序序列，经排序后得到的结果是唯一的；若关键码是次关键码，排序结果可
能不唯一。实现排序的基本操作有两个： （1）“比较”序列中两个关键字的大小； （2）“移动”记录。 若对任意的数据元素序列，使用某个排序方法，对它按关键码进行排序：若相同关键码元素间的位置关系，排序前与排序后保持一致，称此排序方法是稳定的；而不能保持一致的排序方法则称为不稳定的。 二.插入类排序 1.直接插入排序直接插入排序是最简单的插入类排序。仅有一个记录的表总是有序的，因此，对n 个记录的表，可从第二个记录开始直到第n 个记录，逐个向有序表中进行插入操作，从而得到n个记录按关键码有序的表。它是利用顺序查找实现“在R[1..i-1]中查找R[i]的插入位置”的插入排序。
《数据结构与算法》复习题 选择题 1．在数据结构中，从逻辑上可以把数据结构分为 C 。 A．动态结构和静态结构 B．紧凑结构和非紧凑结构 C．线性结构和非线性结构 D．内部结构和外部结构 2．数据结构在计算机内存中的表示是指 A 。 A．数据的存储结构 B．数据结构 C．数据的逻辑结构 D．数据元素之间的关系 3．在数据结构中，与所使用的计算机无关的是数据的 A 结构。 A．逻辑 B．存储 C．逻辑和存储 D．物理 4．在存储数据时，通常不仅要存储各数据元素的值，而且还要存储 C 。A．数据的处理方法 B．数据元素的类型 C．数据元素之间的关系 D．数据的存储方法 5．在决定选取何种存储结构时，一般不考虑 A 。 A．各结点的值如何 B．结点个数的多少 C．对数据有哪些运算 D．所用的编程语言实现这种结构是否方便。 6．以下说法正确的是 D 。 A．数据项是数据的基本单位 B．数据元素是数据的最小单位
C．数据结构是带结构的数据项的集合 D．一些表面上很不相同的数据可以有相同的逻辑结构 7．算法分析的目的是 C ，算法分析的两个主要方面是 A 。（1）A．找出数据结构的合理性 B．研究算法中的输入和输出的关系C．分析算法的效率以求改进 C．分析算法的易读性和文档性（2）A．空间复杂度和时间复杂度 B．正确性和简明性 C．可读性和文档性 D．数据复杂性和程序复杂性 8．下面程序段的时间复杂度是 O(n2) 。 s =0; for( I =0; i 复习题集─参考答案 一判断题 （√）1. 在决定选取何种存储结构时，一般不考虑各结点的值如何。 （√）2. 抽象数据类型与计算机部表示和实现无关。 （×）3. 线性表采用链式存储结构时，结点和结点部的存储空间可以是不连续的。 （×）4. 链表的每个结点中都恰好包含一个指针。 （×）5.链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动地将后续的各个单元向前移动。（×）6. 线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。 （×）7. 顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。 （×）8. 线性表在物理存储空间中也一定是连续的。 （×）9. 顺序存储方式只能用于存储线性结构。 （√）10.栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。 （√）11.对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表。 （√）12.栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。 （√）13.两个栈共享一片连续存空间时，为提高存利用率，减少溢出机会，应把两个栈的栈底分别设在这片存空间的两端。 （×）14.二叉树的度为2。 （√）15.若二叉树用二叉链表作存贮结构，则在n个结点的二叉树链表中只有n—1个非空指针域。 （×）16.二叉树中每个结点的两棵子树的高度差等于1。 （√）17.用二叉链表法存储包含n个结点的二叉树，结点的2n个指针区域中有n+1个为空指针。 （√）18.具有12个结点的完全二叉树有5个度为2的结点。 （√）19.二叉树的前序遍历序列中，任意一个结点均处在其孩子结点的前面。 （×）20.在冒泡法排序中，关键值较小的元素总是向前移动，关键值较大的元素总是向后移动。 （×）21.计算机处理的对象可以分为数据和非数据两大类。[计算机处理的对象都是数据] （×）22.数据的逻辑结构与各数据元素在计算机中如何存储有关。 （×）23.算法必须用程序语言来书写。 （×）24.判断某个算法是否容易阅读是算法分析的任务之一。 （×）25.顺序表是一种有序的线性表。[任何数据结构才用顺序存储都叫顺序表] （√）26.分配给顺序表的存单元地址必须是连续的。 （√）27.栈和队列具有相同的逻辑特性。[它们的逻辑结构都是线性表] （√）28.树形结构中每个结点至多有一个前驱。 （×）29.在树形结构中，处于同一层上的各结点之间都存在兄弟关系。 （×）30.如果表示图的邻接矩阵是对称矩阵，则该图一定是无向图。 （×）31.如果表示图的邻接矩阵是对称矩阵，则该图一定是有向图。 （×）32.顺序查找方法只能在顺序存储结构上进行。 （×）33.折半查找可以在有序的双向链表上进行。 数据结构经典例题 1.设计一个算法将L拆分成两个带头节点的单链表L1和L2。 void split(LinkList *&L,LinkList *&L1,LinkList *&L2) { LinkList *p=L->next,*q,*r1; //p指向第1个数据节点 L1=L; //L1利用原来L的头节点 r1=L1; //r1始终指向L1的尾节点 L2=(LinkList *)malloc(sizeof(LinkList));//创建L2的头节点 L2->next=NULL; //置L2的指针域为NULL while (p!=NULL) { r1->next=p; //采用尾插法将*p(data值为ai)插入L1中 r1=p; p=p->next; //p移向下一个节点(data值为bi) q=p->next; //由于头插法修改p的next域,故用q保存*p的后继节点 p->next=L2->next; //采用头插法将*p插入L2中 L2->next=p; p=q; //p重新指向ai+1的节点 } r1->next=NULL; //尾节点next置空 } 2.查找链表中倒数第k个位置上的节点（k为正整数）。若查找成功，算法输出该节点的data域的值，并返回1；否则，只返回0。 typedef struct LNode {int data; struct LNode *link; } *LinkList; int Searchk(LinkList list,int k) { LinkList p,q; int count=0; p=q=list->link; while (p!=NULL) { if (count 数据结构与方法 1、算法的基本特征:可行性、确定性、有穷性、拥有足够的情报 2、算法的基本运算与操作:算术运算、逻辑运算、关系运算、数据传输 3、算法的基本控制结构:顺序结构、选择结构、循环(重复)结构 4、算法设计的基本方法:列举法、归纳法、递推、递归、减半递推技术、回溯法 5、算法的复杂度主要包括:时间复杂度、空间复杂度 6、算法的时间复杂度:指执行算法所需要的计算工作量 7、算法的空间复杂度:指执行这个算法所需要的内存空间 8、数据结构主要研究:数据的逻辑结构、数据的存储结构、对各种数据结构进行的运算 9、数据结构研究的目的:提高数据处理的效率 10、数据处理的效率:数据处理的速度、减少处理过程中占用计算机的存储空间 11、数据处理:指对数据集合中的各元素以各种方式进行运算 12、数据元素:指在数据处理中,每一个需要处理的对象都可以抽象成数据元素 13、数据结构:指反映数据元素之间关系的数据元素集合的表示 14、数据的逻辑结构:指反映数据元素之间逻辑关系的数据结构,两要素:数据元素的集合、数据元素在集合上的关系 15、数据的存储结构:指数据的逻辑结构在计算机存储空间的存放形式,常用的存储结构有:顺序、链接、索引等 16、数据结构的图形表示中每个元素加上方框成为结点 17、数据结构一般分为:线性结构、非线性结构 18、线性结构满足:有且仅有一个根结点、每个结点最多有一个前件与后件、在一个线性结构中插入与删除任何一个结点后还就是线性结构 19、线性表定义:线性表就是由n个数据元素a1、a2、a3、a4……an组成的一个有限序列,表中每一个数据元素,除了第一个外,有且仅有一个前件,除了最后一个外,有且仅有一个后件20、非线性表的特征:有且只有一个根节点a1,它无前件、有且只有一个终结点an,它无后件、除了第一个与最后一个外,其她所有结点只有一个前件与一个后件 21、线性表的长度:线性表中的结点的个数n成为线性表的长度,当n=0时,成为空表 22、线性表的顺序存储的特点:所有元素所占的存储空间就是连续的、各数据元素在存储空间中就是按逻辑顺序一次存放的 23、线性表的随机存取地址计算公式:ADD(ai)=ADD(a1)+(i-1)*k 24、线性表的主要操作:插入、删除、查找、排序、分解、合并、复制、逆转 25、栈的定义:栈就是限定在一端进行插入与删除的线性表,它按照“先进后出,后进先出”的原则组织数据 26、栈的顺序存储:在程序设计语言中,一般一维数组S(1:m)作为栈的顺序存储空间,其中m 为栈的最大容量 27、栈的基本运算:入栈、退栈、读栈顶元素 28、入栈运算:首先将栈顶指针(top)加1,然后将新元素插入到栈顶指针指向的位置。当栈顶指针已经指向存储空间的最后一个位置时,说明栈空间已满,称为“上溢”错误 29、退栈运算:首先将栈顶元素赋给一个指定的变量,然后将栈顶指针(top)减1。当栈顶指针为0时,说明栈空,成为“下溢”错误 30、队列的定义:队列就是指允许在一端进行插入,而在另一端进行删除的线性表,它按照“先进先出”的原则组织数据 31、循环队列:在实际应用中,队列的顺序存储结构一般采用循环队列的形式。所谓循环队列, 排序算法有：插入排序，合并排序，冒泡排序，选择排序，希尔排序，堆排序，快速排序，计数排序，基数排序，桶排序(没有实现) 。比较一下学习后的心得。我不是很清楚他们的时间复杂度，也真的不知道他们到底谁快谁慢，因为书上的推导我确实只是小小了解，并没有消化。也没有完全理解他们的精髓，所以又什么错误的还需要高手指点。呵呵。 1. 普及一下排序稳定，所谓排序稳定就是指：如果两个数相同，对他们进行的排序结果为他们的相对顺序不变。例如A={1,2,1,2,1}这里排序之后是 A = {1,1,1,2,2}稳定就是排序后第一个 1 就是排序前的第一个1，第二个1 就是排序前第二个1，第三个1 就是排序前的第三个1。同理 2 也是一样。这里用颜色标明了。不稳定呢就是他们的顺序不应和开始顺序一致。也就是可能会是A={1,1,1,2,2}这样的结果。 2. 普及一下原地排序：原地排序就是指不申请多余的空间来进行的排序，就是在原来的排序数据中比较和交换的排序。例如快速排序，堆排序等都是原地排序，合并排序，计数排序等不是原地排序。 3. 感觉谁最好，在我的印象中快速排序是最好的，时间复杂度：n*log(n) ，不稳定排序。原 地排序。他的名字很棒，快速嘛。当然快了。我觉得他的思想很不错，分治，而且还是原地排序，省去和很多的空间浪费。速度也是很快的，n*log(n) 。但是有一个软肋就是如果已经是排好的情况下时间复杂度就是n*n, 不过在加入随机的情况下这种情况也得以好转，而且他可以做任意的比较，只要你能给出两个元素的大小关系就可以了。适用范围广，速度快。 4. 插入排序：n*n 的时间复杂度，稳定排序，原地排序。插入排序是我学的第一个排序，速 度还是很快的，特别是在数组已排好了之后，用它的思想来插入一个数据，效率是很高的。因为不用全部排。他的数据交换也很少，只是数据后移，然后放入要插入的数据。(这里不 是指调用插入排序，而是用它的思想) 。我觉得，在数据大部分都排好了，用插入排序会给你带来很大的方便。数据的移动和交换都很少。 插入排序主要思想是：把要排序的数字插入到已经排好的数据中。(我自己理 解的哈)。例如12356 是已经排好的序，我们将4插入到他们中，时插入之后也是排好序的。这里显而易见是插入到 3 的后面。变为123456. 实现思路：插入排序就是先是一个有序的数据，然后把要插入的数据插到指定的位置，而排序首先给的就是无序的，我们怎么确定先得到一个有序的数据呢？答案就是：如果只有一个，当然是有序的咯。我们先拿一个出来，他是有序的，然后把数据一个一个插入到其中，那么插入之后是有序的，所以直到最后都是有序的。。哈哈。结果就出来了！ 当然在写的时候还是有一个技巧的，不需要开额外的数组，下标从第二个元素开始遍历直到最后一个，然后插入到前面已经有序的数据中。这样就不会浪费空间了。插入排序用处还是 很多的，特别是链表中，因为链表是指针存放的，没有数组那么好准确的用下标表示，插入是简单有效的方法。嘻嘻。。废话少说， 源代码奉上： 1 #include //插入排序法 void InsertSort() { int s[100]; int n,m,j,i=0,temp1,temp2; printf("请输入待排序的元素个数："); scanf("%d",&n); printf("请输入原序列："); for (i=0; i //堆排序 static a[8] = {0,25,4,36,1,60,10,58,}; int count=1; void adjust(int i,int n) { int j,k,r,done=0; k = r = a[i]; j = 2*i; while((j<=n)&&(done==0)) { if(j 数据结构与算法设计知识点 试题类型： 本课程为考试科目（闭卷笔试），试题类型包括：概念填空题（10 %），是非判断题（10 %），单项选择题（40 %），算法填空题（10%），算法应用题（20 %)，算法设计题（10 %）。 第一章绪论 重点内容及要求： 1、了解与数据结构相关的概念（集合、数据、数据元素、数据项、关键字、元 素之间的关系等）。 数据：所有能被输入到计算机中，且能被计算机处理的符号的 集合。是计算机操作的对象的总称。是计算机处理的信息的某种特定 的符号表示形式。 数据元素：是数据（集合）中的一个“个体”，数据结构中的基本 单位，在计算机程序中通常作为一个整体来考虑和处理。 数据项：是数据结构中讨论的最小单位，数据元素可以是一个或 多个数据项的组合 关键码：也叫关键字（Key），是数据元素中能起标识作用的数 据项。 其中能起到唯一标识作用的关键码称为主关键码（简称主码）； 否则称为次关键码。通常，一个数据元素只有一个主码，但可以有多 个次码。 关系：指一个数据集合中数据元素之间的某种相关性。 数据结构：带“结构”的数据元素的集合。这里的结构指元素之 间存在的关系。 数据类型：是一个值的集合和定义在此集合上的一组操作的总 称。 2、掌握数据结构的基本概念、数据的逻辑结构（四种）和物理结构（数据元素 的表示与关系的表示、两类存储结构：顺序存储结构和链式存储结构）。 数据结构包括逻辑结构和物理结构两个层次。 数据的逻辑结构：是对数据元素之间存在的逻辑关系的一种抽象的描述，可以用一个数据元素的集合和定义在此集合上的若干关系来表示 逻辑结构有四种：线性结构、树形结构、图状结构、集合结构数据的物理结构：是其逻辑结构在计算机中的表示或实现，因此又称其为存储结构。 存储结构：顺序存储结构和链式存储结构 顺序存储结构：利用数据元素在存储器中相对位置之间的某种特定的关系来表示数据元素之间的逻辑关系； 链式存储结构：除数据元素本身外，采用附加的“指针”表示数据元素之间的逻辑关系。 3、了解算法分析的基本方法，掌握算法时间复杂度相关的概念。 算法：是为了解决某类问题而规定的一个有限长的操作序列 或处理问题的策略 一个算法必须满足以下五个重要特性：1．有穷性2．确定性3．可行性4．有输入5．有输出 设计算法时，通常还应考虑满足以下目标： 1.正确性， 2.可读性， 3.健壮性 4.高效率与低存储量需求 北京交通大学考试试题（A卷） 课程名称:数据结构与算法2011-2012学年第一学期出题教师:张勇 (请考生注意:（1）本试卷共有六道大题，（2）答案一律写在答题纸上，（3）试卷不得带出考场) 一、填空题（每空2分，共20分） 1. 在顺序表中访问任意一个元素的时间复杂度均为，因此顺序表也称为 的数据结构。 2．三维数组a[4][3][2](下标从0开始)，假设a[0][0][0]的地址为50，数据以行序优先方式存储，每个元素的长度为2字节，则a[2][1][1]的地址是。 3. 直接插入排序用监视哨的作用是。 4. 已知广义表Ls=(a, (b, c), (d, e)), 运用head和tail函数取出Ls中的原子d的运算 是。 5．对有14个元素的有序表A[1..14]进行折半查找，当比较到A[4]时算法结束。被比较元素除A[4]外，还有。 6. 在AOV网中，顶点表示，边表示。 7. 有向图G可进行拓扑排序的判别条件是。 8. 若串S1=‘ABCDEFGHIJK’,S2=‘451223’,S3=‘####’,则执行 Substring(S1,Strlength(S3),Index(S2,‘12’,1))的结果是。 二、选择题（每空2分，共20分） 1.在下列存储形式中，哪一个不是树的存储形式？（） A．双亲表示法B．孩子链表表示法 C．孩子兄弟表示法D．顺序存储表示法 2.查找n个元素的有序表时，最有效的查找方法是（）。 A．顺序查找B．分块查找 C．折半查找D．二叉查找 3.将所示的s所指结点加到p所指结点之后，其语句应为（）。 p (A) s->next=p+1 ; p->next=s; (B) (*p).next=s; (*s).next=(*p).next; (C) s->next=p->next ; p->next=s->next; (D) s->next=p->next ; p->next=s; 4. 在有向图的邻接表存储结构中，顶点v 在链表中出现的次数是（ ）。 A. 顶点v 的度 B. 顶点v 的出度 C. 顶点v 的入度 D. 依附于顶点v 的边数 5. 算法的时间复杂度为O （nlog 2n ）、空间复杂度为O(1)的排序算法是（ ）。 A. 堆排序 B. 快速排序 C. 归并排序 D.直接选择 6. 设矩阵A 是一个对称矩阵，为了节省存储，将其下三角部分（如右图所示）按行序存放在一维数组B[ 1, n(n-1)/2 ]中，对下三角部分中任一元素ai,j(i ≤j), 在一维数组B 中下标k 的值是（ ）： Ａ．i(i-1)/2+j-1 Ｂ．i(i-1)/2+j Ｃ．i(i+1)/2+j-1 Ｄ．i(i+1)/2+j 7. 由一个长度为11的有序表，按二分查找法对该表进行查找，在表内各元素等概率情况下，查找成功的平均查找长度是（ ）。 A ．29/11 B. 31/11 C. 33/11 D.35/11 8. AVL 树是一种平衡的二叉排序树，树中任一结点的（ ）。 A. 左、右子树的高度均相同 B. 左、右子树高度差的绝对值不超过1 C. 左子树的高度均大于右子树的高度 D. 左子树的高度均小于右子树的高度 9. 下列四种排序方法中，不稳定的方法是（ ）。 A. 直接插入排序 B. 冒泡排序 C. 归并排序 D. 堆排序 10. 设树的度为4，其中度为1,2,3,4的结点个数分别为4, 2, ,1, 1, 则T 中的叶子数为（ ）。 A ．5 B ．6 C ．7 D ．8 三、 判断题（10分，每小题1分） 1. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。（ ） 2. 数组不适合作任何二叉树的存储结构。（ ） ????? ?????????=n n n n a a a a a a A ,2,1,2,21,21,1 基本概念典型例题 一、单项选择题 [例6-1]数据结构用集合的观点可以表示为一个二元组DS＝(D，R)。其中，D是( ①)的有穷集合，R是D上( ②)的有限集合。 ①A.算法B. 数据元素C. 数据操作D. 逻辑结构 ②A. 操作B. 映像C. 存储D．关系 解析：由数据结构的集合形式化定义可知，本题答案为：①B；②D。 [例6-2]数据的常用存储结构中不包括( )。 A．顺序存储结构B．线性结构C．索引存储结构D．散列存储结构 解析：数据通常有四种基本的存储方法，即顺序存储方法、链式存储方法、索引存储 方法和散列存储方法。由此可知，本题答案为：B。 [例6-3] 算法指的是( ①)，它必须具备( ②)这三个特性。 ①A．计算方法B．排序方法C．解决问题的步骤序列D．调度方法 ②A．可执行性、可移植性、可扩充性B．可执行性、确定性、有穷性 C．确定性、有穷性、稳定性D．易读性、稳定性、安全性 解析：算法是对特定问题求解步骤的一种描述，是由若于条指令组成的有限序列。它 必须满足以下性质：输人性、输出性、有穷性、确定性、无二义性和可行性。由此可知，本 题答案为：①㈠②B。 [例6-4] 在下面的程序段中，对x的赋值语句的执行频度为( )。 for(i=0；i 1．假设有两个按元素值递增次序排列的线性表，均以单链表形式存储。请编写算法将这两个单链表归并为一个按元素值递减次序排列的单链表，并要求利用原来两个单链表的结点存放归并后的单链表。【北京大学1998 三、1 （5分）】 LinkedList Union(LinkedList la,lb) { pa=la->next; pb=lb->next; la->next=null; while(pa!=null && pb!=null) ∥当两链表均不为空时作 if(pa->data<=pb->data) { r=pa->next; pa->next=la->next; ∥将pa结点链于结果表中，同时逆置。 la->next=pa; pa=r; } else {r=pb->next; pb->next=la->next; ∥将pb结点链于结果表中，同时逆置。 la->next=pb; pb=r; } while(pa!=null) ∥将la表的剩余部分链入结果表，并逆置。 {r=pa->next; pa->next=la->next; la->next=pa; pa=r; } while(pb!=null) {r=pb->next; pb->next=la->next; la->next=pb; pb=r; } } 1）设有两个无头结点的单链表,头指针分别为ha,hb,链中有数据域data,链域next,两链表的数据都按递增序存放,现要求将hb表归到ha表中,且归并后ha仍递增序,归并中ha表中已有的数据若hb中也有,则hb中的数据不归并到ha中,hb的链表在算法中不允许破坏。【南京理工大学1997 四、3（15分）】 LinkedList Union(LinkedList ha, hb)∥ha和hb是两个无头结点的数据域值递增有序的单链 ｛LinkedList 表，本算法将hb中并不出现在ha中的数据合并到ha中，合并中不能破坏hb链表。 la; la=(LinkedList)malloc(sizeof(LNode)); la->next=ha; pa=ha; pb=hb; pre=la; while(pa&&pb) if(pa->data数据结构与算法复习题及参考答案
数据结构经典例题
数据结构与算法知识点必备
数据结构算法大全有代码
数据结构经典算法 C语言版
数据结构与算法设计知识点
【精选资料】北京交通大学数据结构与算法期末考试参考答案
数据结构典型例题
数据结构经典算法试题
相关主题
文本预览