- 1. 数据结构与算法
- 2. 目录页第2页1234温习知识点和知识结构关于我们的考试一些训练答疑及其它
- 3. 知识结构知识结构第3页计算机世界的研究问题:建模+算法+实现
数据结构的研究视角:(1)数据的逻辑结构和物理结构;
(2)基于特定结构的通用操作描述。
抽象数据类型:数据+数据间联系+数据上的操作集合
- 4. 大礼包大礼包第4页不属于考核范围的内容:
Chapter 2: 2.5、 2.6
Chapter 3: 3.3
Chapter 6: 6.2
Chapter 7: 7.4、7.5、7.6
Chapter 9: 9.5.2、9.6、9.7
Chapter 10
- 5. 内容温习Chapter1 知识点第5页数据结构
数据+关系:前驱、后继
数据逻辑结构:(线性结构+非线性结构)
线性、树型、集合、图
数据存储结构
顺序、链接、散列、索引
算法及其分析
输入+输出+步骤
算法性能评价: 时间复杂度 + 空间复杂度
O()
- 6. 温故知新Chapter1 测试一下第6页数据结构在计算机内存中的表示是 ( )
A. 数据的存储结构 B. 数据结构
C. 数据的逻辑结构 D. 数据元素之间的关系
为规模n的问题设计了一个算法,其中最频繁操作的执行次数是n的函数: f(n)=3n3+100n2+9n+10000,则该算法的时间复杂度是多少。
- 7. 内容温习Chapter2 知识点第7页逻辑结构视角
线性表:(直接)前驱、(直接)后继
抽象数据类型: 插入操作、删除操作
物理结构视角
顺序表
数据元素存储地址的计算
顺序存储的线性表,插入或删除一个元素,平均移动多少个元素?
链接表(插入+删除)
结点结构:数据域 + 指针域
单链表
双向链表
循环链表
问题分析1: 链表中头结点的用途?判定带头结点的单链表是空表的条件?
问题分析2: 顺序表和链接表的优缺点对比
- 8. 温故知新Chapter2 测试一下第8页请分析下面代码段的功能。
typedef struct Node{
Elemtype data;
Struct Node *next;
} Node;
int count ( Node *list, ElemType x)
{
int i=0;
Node *p=list;
while(p!=NULL) {
if (p->data = = x)
i++;
p=p->next;
}
return i;
}
- 9. 温故知新Chapter2 测试一下第9页2. 请分别给出删除结点b和结点c的操作1. 请分别给出删除结点c和插入结点x的操作
- 10. 温故知新Chapter2 测试一下第10页P168 16
list1和list2分别是两个带有头结点的有序(升序)单向链表的头指针,请写出将两个有序链表合并为一个有序链表(升序)的算法。(要求在原表基础上合并)
- 11. 温故知新Chapter2 测试一下第11页P168 16//升序合并为升序
PList mergeList(PList list1, PList list2)
{
PList p1=list1, p2=list2, head=NULL, tail=NULL, temp;
if(p1->value<p2->value)
{
head=p1; tail=p1;
p1=p1->next; tail->next=NULL;
}
else
{
head=p2; tail=p2;
p2=p2->next; tail->next=NULL;
}
while((p1!=NULL)&&(p2!=NULL))
{
if(p1->value>p2->value)
{
temp=p2->next; tail->next=p2;
tail=p2; tail->next=NULL; p2=temp;
}
else
{
temp=p1->next; tail->next=p1;
tail=p1; tail->next=NULL; p1=temp;
}
}
if(p1!=NULL) tail->next=p1;
if(p2!=NULL) tail->next=p2;
return head;
}请问升序转降序如何实现?
- 12. 内容温习Chapter3 知识点第12页字符串是一种线性表,可以采用顺序存储结构和链式存储结构。其与普通线性表的区别在于:表中的每个元素是一个字符。
两个字符串相等的充要条件是:两个字符串的长度相等 + 两个字符串中对应位置上的字符相同
- 13. 内容温习Chapter4 知识点第13页栈
特点:FILO;
栈顶、出栈、入栈;
顺序栈和链栈;
栈在递归中的作用;
队列
特点:FIFO;
队头、队尾、出队列、入队列;
队列的顺序存储实现和链接存储实现;
循环队列: 假溢出;
队列满和空的条件;
栈和队列的综合应用
- 14. 温故知新Chapter4 测试一下第14页若已知一个栈的入栈序列是1, 2, 3, …, n,其输出序列是p1, p2, p3, …, pn,若p1=n,则pi是( )
A. 1
B. n-1
C. n-i+1
D. 不确定
- 15. 温故知新Chapter4 测试一下第15页下图描述的队列
(1)如何在队列中进行删除操作;
(2)如何插入current指向的结点。
- 16. 温故知新Chapter4 测试一下第16页循环单链表,head和tail分别是头指针和尾指针。
1. 请给出该循环单链表的定义
2. 若将其作为一个栈,如何实现入栈和出栈操作
3. 若将其作为一个队列,如何实现入队列和出队列操作
- 17. 温故知新Chapter4 测试一下第17页采用循环单链表作为队列,只有尾指针tail的三种状态。
- 18. 温故知新Chapter4 测试一下第18页采用循环单链表作为队列,只有尾指针tail的三种状态。typedef struct QueueElement{
int value;
struct QueueElement *next;
}QueueElement;
typedef QueueElement *PQueue;
PQueue initQueue()
{
PQueue queueTail;
queueTail=(PQueue)malloc(sizeof(QueueElement));
queueTail->value=-1;
queueTail->next=queueTail;
return queueTail;
}PQueue insertElement(PQueue queueTail, int v)
{
QueueElement *q=(QueueElement *)malloc(sizeof(QueueElement));
q->value=v;
q->next=queueTail->next;
queueTail->next=q;
queueTail=q;
return queueTail;
}
请问删除操作如何实现?
- 19. 内容温习Chapter5 知识点第19页二叉树的基本术语
根结点、树叶、分支结点
父结点、孩子结点、兄弟结点
路径、路径长度
结点的层数(根结点的层数为0)、树的高度
结点的度、树的度
二叉树是一棵有序树
只有三个结点的二叉树有多少种不同形态
完全二叉树、满二叉树及其性质
父结点和孩子结点编号的对应关系
二叉树中度为0的结点和度为2的结点之间的关系
深度k的二叉树最少(多)有多少个结点
扩充二叉树
- 20. 内容温习Chapter5 知识点第20页二叉树的存储结构
顺序存储:适合完全二叉树
二叉链表
三叉树表
二叉树的遍历(周游)
深度优先周游:先序、中序、后序遍历
广度优先周游
线索二叉树:二叉树结点的左右指针赋予了新的含义
采用二叉链表存储,n个结点的空指针数目是多少。
哈夫曼树(最优二叉树)
前缀编码
最优(短)编码
如何构造哈夫曼树和计算WPL
- 21. 内容温习Chapter5 知识点第21页树及其遍历
深度优先遍历、广度优先遍历
树、树林与二叉树的相互转换
- 22. 温故知新Chapter5 测试一下第22页下列编码中属前缀码的是( )
(A){1,01,000,001} (B){1,01,011,010}
(C){0,10,110,11} (D){0,1,00,11}
一棵深度为6的满二叉树有___________个分支结点和___________个叶子结点。
设一棵完全二叉树有700个结点,则共有__________个叶子结点。
某二叉树结点的中序序列为ABCDEFG,后序序列为BDCAFGE,则其左子树中结点数目为( )
A. 3 B. 2 C. 4 D. 5
- 23. 温故知新Chapter5 测试一下第23页P168 13
已知一棵度为m的树中有n1个度为1的结点,n2个度为2的结点,……,nm个度为m的结点,请问该树中有多少个叶子结点?
- 24. 温故知新Chapter 5 测试一下第24页P169 算法题 1
采用二叉链表存储二叉树,请写一个算法,统计二叉树中结点值在20到50之间的叶子结点的数目。int countNode(PBinTree root)
{
if(root==NULL) return 0;
if((root->lchild==NULL)&&(root->rchild==NULL)
&&(root->value>20)&&(root->value<50))
return 1;
return countNode(root->lchild)+countNode(root->rchild);
}
- 25. 内容温习Chapter6 知识点第25页集合与字典的基本概念
查找操作与(等概率)平均查找长度
字典的顺序存储结构(有序顺序表)
二分检索法
字典的散列表示
散列函数、负载因子
散列冲突: (同义词)碰撞、(非同义词)堆积
解决散列冲突的方法
开地址法:线性探测法
拉链法
散列表的构造和平均查找长度计算
- 26. 温故知新Chapter6 测试一下第26页设散列表容量为8(散列地址空间0..7),给定字典的关键字序列(30,36,47,52,34,40),散列函数H(k) = k mod 7,分别采用线性探查法和拉链法解决冲突,要求:
(1)构造散列表;
(2)等概率情况下查找成功时的平均查找长度ASL。
有序表为{16,40,82,105,132,246,285,362,375,390,882,995,1008},当二分查找值为82和395的结点时,查找的次数分别是多少?
- 27. 内容温习Chapter7 知识点第27页索引: 提高查找速度
二叉排序树
基于二叉排序树的查找
二叉排序树的插入、删除
二叉排序树的中序遍历具有什么特征
最佳二叉排序树、平衡二叉排序树(平衡因子)的基本概念
B树、B+树的基本定义和结构
- 28. 温故知新Chapter 7 测试一下第28页P248 复习题7
已知元素个数为12的字典,其元素集合为{Jan, Feb, Mar, Apr, May, June, July, Aug, Sep, Oct, Nov, Dec},按元素的次序依次插入一棵初始时为空的二叉排序树,请:
(1)画出插入完成之后的二叉排序树;
(2)等概率下的平均检索长度ASL;
(3)画出删除Mar之后的二叉排序树。
- 29. 内容温习Chapter8 知识点第29页插入排序
直接插入排序、二分插入排序、希尔排序
选择排序
直接选择排序
堆:构造大(小)根堆、筛选
交换排序
冒泡排序、快速排序
分配排序
基数排序
归并排序
各算法的平均时间复杂度,最好(坏)情况时间复杂度
- 30. 温故知新Chapter8 测试一下第30页设一组初始记录关键字序列(15, 22, 6, 13, 8,5,32,4,56),分别以每个区间第一个记录关键字为基准进行快速排序,请给出每一趟的排序结果。
- 31. 温故知新Chapter 8 测试一下第31页P285 算法题3
设计一个有效的算法,在1000个无序的元素中,挑选出其中前5个最大的元素。
堆排序的实现算法。考核点:堆排序的实现算法
- 32. 温故知新第32页P285 算法题3
void griddle(Heap heap, int index, int bound)
{
int lchild=2*index+1; int rchild=2*index+2;
while((lchild<=bound)||(rchild<=bound))
{
int maxKeyIndex=index;
if((lchild<=bound)&&(heap.pvector[maxKeyIndex].key<heap.pvector[lchild].key)) maxKeyIndex=lchild;
if((rchild<=bound)&&(heap.pvector[maxKeyIndex].key<heap.pvector[rchild].key)) maxKeyIndex=rchild;
if(maxKeyIndex==index) return;
Record temp=heap.pvector[maxKeyIndex]; heap.pvector[maxKeyIndex]=heap.pvector[index]; heap.pvector[index]=temp;
lchild=2*maxKeyIndex+1; rchild=2*maxKeyIndex+2; index=maxKeyIndex;
}
}
Chapter 8 测试一下
- 33. 温故知新第33页P285 算法题3
void createHeap(Heap heap)
{
for(int i=heap.n-1;i>=0;i--)
griddle(heap, i, heap.n-1);
}
void sortByHeap(Heap heap)
{
for(int i=heap.n-1;i>0;i--)
{
Record temp=heap.pvector[i];
heap.pvector[i]=heap.pvector[0];
heap.pvector[0]=temp;
griddle(heap, 0, i-1);
}
}
Chapter 8 测试一下
- 34. 温故知新第34页P285 算法题3
void find5MaxKey(Heap heap)
{
for(int i=heap.n-1;i>=heap.n-5;i- -)
{
Record temp=heap.pvector[i];
heap.pvector[i]=heap.pvector[0];
heap.pvector[0]=temp;
griddle(heap, 0, i-1);
}
for(int i=heap.n-5;i<heap.n;i++)
printf("%d ",heap.pvector[i].key);
}Chapter 8 测试一下
- 35. 温故知新第35页P285 算法题5
试设计一个算法,在尽可能少的时间内重排数组,将所有取负值的排序码放在所有取非负值的排序码之前。考核点:快速排序的实现算法
int dividByFirstElement(int a[], int i, int j)
{
int temp=a[i];
while(i<j)
{
while((i<j)&&(a[j]>temp)) j- -;
if(i<j) a[i++]=a[j];
while((i<j)&&(a[i]<=temp)) i++;
if(i<j) a[j--]=a[i];
}
a[i]=temp;
return i;
}void quickSort(int a[], int i, int j)
{
int m=dividByFirstElement(a, i, j);
if(i<m-1)
quickSort(a, i, m-1);
if(m+1<j)
quickSort(a, m+1, j);
}
Chapter 8 测试一下
- 36. 温故知新第36页P285 算法题5
//key为指定的分割点(即选取的基准关键字)
void splitByZero(int a[], int i, int j, int key)
{
while(i<j)
{
while((i<j)&&(a[j]>key)) j--;
while((i<j)&&(a[i]<=key)) i++;
if(i<j)
{ int temp=a[i]; a[i]=a[j]; a[j]=temp; i++; j--; }
}
}Chapter 8 测试一下
- 37. 内容温习Chapter9 知识点第37页图的定义及相关术语
有向图、无向图
顶点的度
简单路径
连通图、连通分量
完全图:n个结点的无向完全图和有向完全图各有多少条边
网络(带权的连通图)
图的存储结构
邻接矩阵: 无向图对应邻接矩阵的特点
邻接表、逆邻接表
- 38. 主标题Chapter9 知识点第38页图的周游
深度优先周游
广度优先周游
最小生成树
克鲁斯卡尔算法
普里姆算法
最短路径的概念
拓扑排序与关键路径的相关概念
AOV网与AOE网
- 39. 温故知新Chapter9 测试一下第39页具有n个结点的连通图至少有( )条边。
A. n-1 B. n C. n(n-1)/2 D. 2n
- 40. 目录页这里填写二级标题第40页1234温习知识点和知识结构关于我们的考试一些训练答疑及其它
- 41. 关于考试试题类型第41页应用题
占50%算法与程序设计
占20%填空题
占10%选择题
占20%
- 42. 关于考试考试时间与地点第42页考试时间壹数据结构与算法: 20周 周二 15:00~17:00考试地点贰17312Nothing叁
- 43. 休息一下休息一下第43页
- 44. 目录页目录页第44页1234温习知识点和知识结构关于我们的考试一些训练答疑及其它
- 45. 温故知新测试与训练第45页设有5000个待排序的记录关键字,如果需要用最快的方法选出其中最小的10个记录关键字,则用下列( )方法可以达到此目的。
A. 快速排序 B. 堆排序 C. 归并排序 .D 插入排序
有8个结点的无向图最多有( )边。
14 B. 28 C. 56 D. 112
设栈S和队列Q的初始状态为空,元素a,b,c,d ,e,f依次进栈,一个元素出栈后即进入队列Q。如果6个元素出队列的顺序是b,d,c,f,e,a,则栈S的容量至少应该是 。
现有存储n个元素的一维数组,则
(1)读取数组中第i个元素的平均时间复杂度是多少;
(2)查找数组中元素x的平均时间复杂度是多少。
- 46. 温故知新测试与训练第46页有一份电文中共使用7个字符:a、b、c、d、e、f、g,它们的出现频率依次为4,5,6,12,8,10,18。要求:
(1)试画出对应的哈夫曼树;
(2)每个字符的哈夫曼编码;
(3)求带权外部路径长度(WPL)。
- 47. 温故知新测试与训练第47页一组记录的关键字集合如下:{70, 67, 75, 61, 86, 69},请给出采用直接插入排序法对该序列进行升序排序时每一趟的结果,其时间复杂度是多少?
给定一组关键字,4,2,58,3,6,10,14,请构造一棵小根堆。
构造大根堆呢?
- 48. 温故知新测试与训练第48页已知一个图的顶点集V和边集E分别为:
V={1, 2, 3, 4, 5, 6, 7, 8};
E={(1,2,19), (1,3,8), (2,4,12), (2,5,30),(3,4,8), (3,6,6), (3,7,5),(4,6,9), (4,8,12), (5,8,10), (6,8,5), (7,8,4)};
(1)分别给出该图的邻接矩阵、邻接表、逆邻接表表示;
(2)给出从1号顶点出发按深度优先搜索遍历的顶点序列;
(3)给出从1号顶点出发按广度优先搜索遍历的顶点序列;
(4)采用PRIM算法,从1号顶点出发,构造该图的最小生成树。
- 49. 温故知新测试与训练第49页某无向图G采用如图1所示的邻接表存储,则从顶点A开始的深度优先遍历序列为 ;从顶点A开始的广度优先遍历序列为 。
- 50. 课后习题测试与训练第50页P168 8
已知二叉树的先根周游序列为ABDEGCFHIJ,对称序周游序列为DBGEAHFIJC,
请给出该二叉树的后根周游序列。
P167 3
请将下图所示的二叉树转换成树林。
- 51. 主标题测试与训练第51页P168 14
根据下图,
(1)给出图的先根、中根和后根遍历序列
(2)将其转换为二叉树
- 52. 主标题测试与训练第52页P327 7
根据下图
1. 请给出该图的邻接表表示(顶点表+出边表(出边表结点));
2.以顶点v0为起点的深度优先周游序列及对应的生成树;
3.以顶点v0为起点的广度优先周游序列及对应的生成树;
4. 以v0为原点,采用Dijstra算法到其它各顶点的最短路径。
- 53. 温故知新测试与训练第53页建立带头结点且有n个结点的单向链表的程序,结点中的数据域从前向后依次为1,2,3,……,n,要求创建过程中的结点的数据域依次为n, n-1, ……, 2, 1。/* 单链表结点的定义 */
typedef struct Node{
int data;
struct Node *next;
} Node;
Node *create(n)
{
Node *head , *p; int i;
p=(Node *)malloc(sizeof(Node));
head= ;
pnext=NULL;
for(i=n; i>=1; i--)
{ p= ;
p->data=i;
p->next= ;
;
}
return(head);
}
- 54. 目录页这里填写二级标题第54页1234温习知识点和知识结构关于我们的考试一些训练答疑及其它
- 55. 答疑及其它答疑时间与地点第55页All teachers’ time19周
周三 下午
14:00~16:005教505
软件工程系办公室
- 56. 答疑及其它Your time第56页Pay AttentionWelcome any question.
- 57. 感谢大家对这门课程的参与祝大家考试顺利!