《数据结构》期末考试题型及分值
（1）简答题6题*5分=30分简要回答要点
（2）分析题6题*5分=30分给出结果
（3）设计题1题*10分=10分设计思想及结果
（4）编程题1题*10分=10分完整代码
（5）综合题1题*20分=20分抽象数据类型的定义、表示、实现、算法分析{定义=功能（ADT）表示=存储结构体实现=算法（基本操作）算法分析=时间、空间复杂度}
考试概念有：1.数据结构{一、线性表（栈-队-列-串-数组-广义表-逻辑结构-存储结构-运算结构）
二、非线性表（集合-树-图）}
2.抽象数据类型数据对象-数据关系-基本操作
3.算法性质-要求（设计）-效率（度量）
4.实例查找：高效查找算法
排序：高效的排序算法
分析题考试题目参考
（1）1-2-3-4-5-6顺序建BBST （2）6-5-4-3-2-1顺序建BBST
简答题实例
（1）
（2）
数据结构试卷（一）
三、计算题（每题 6 分，共24分）
1. 在如下数组A 中链接存储了一个线性表，表头指针为A [0].next ，试写出该线性表。 A 0 1 2 3 4 5 6 7
data 60 50 78 90 34 40
next
3 5 7 2 0 4
1
线性表为：（78，50，40，60，34，90）???????
??
???????01
1
1
1010111011101010111
2. 请画出下图的邻接矩阵和邻接表。
3. 已知一个图的顶点集
V 和边集E 分别为：
V={1,2,3,4,5,6,7}; E={(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15,
(3,5)12,(3,6)9,(4,6)4,(4,7)20,(5,6)18,(6,7)25};
用克鲁斯卡尔算法得到最小生成树，试写出在最小生成树中依次得到的各条边。
用克鲁斯卡尔算法得到的最小生成树为：
(1,2)3, (4,6)4, (1,3)5, (1,4)8, (2,5)10, (4,7)20
4.画出向小根堆中加入数据4, 2, 5, 8, 3时，每加入一个数据后堆的变化。见图12
图12
图11
四、阅读算法（每题7分，共14分）
1. LinkList mynote(LinkList L)
{//L 是不带头结点的单链表的头指针 if(L&&L->next){
q=L ；L=L －>next ；p=L ； S1： while(p －>next) p=p －>next ； S2： p －>next=q ；q －>next=NULL ； }
return L ； }
请回答下列问题：
（1）说明语句S1的功能；
查询链表的尾结点
（2）说明语句组S2的功能；
将第一个结点链接到链表的尾部，作为新的尾结点
（3）设链表表示的线性表为（a 1,a 2, …,a n ）,写出算法执行后的返回值所表示的线性表。
返回的线性表为（a 2,a 3,…,a n ,a 1）
2. void ABC(BTNode * BT) {
if BT {
ABC (BT->left); ABC (BT->right); cout<
4 4 4 4 4 2 2 2
5 5 5
2 2
8 8 4 3
5
2 8
3 4
该算法的功能是：
递归地后序遍历链式存储的二叉树
五、算法填空（共8分）
二叉搜索树的查找——递归算法:
bool Find(BTreeNode* BST,ElemType& item)
{
if (BST==NULL)
return false; //查找失败
else {
if (item==BST->data){
item=BST->data;//查找成功
return __ true __;}
else if(item
return Find(___BST->left __,item);
else return Find(____BST->right__,item);
}//if
}
六、编写算法（共8分）
统计出单链表HL中结点的值等于给定值X的结点数。
int CountX(LNode* HL,ElemType x)
int CountX(LNode* HL,ElemType x)
{ int i=0; LNode* p=HL;//i为计数器
while(p!=NULL)
{ if (P->data==x) i++;
p=p->next;
}//while, 出循环时i中的值即为x结点个数
return i;
}//CountX
数据结构试卷（二）
三、应用题(36分)
1．设一组初始记录关键字序列为(45，80，48，40，22，78)，则分别给出第4趟简单选择排序和第4趟直接插入排序后的结果。
(22，40，45，48，80，78)，(40，45，48，80，22，78)
2．设指针变量p指向双向链表中结点A，指针变量q指向被插入结点B，要求给出在结点A的后面插入结点B的操作序列（设双向链表中结点的两个指针域分别为llink和rlink）。
q->llink=p; q->rlink=p->rlink; p->rlink->llink=q; p->rlink=q;
3．设一组有序的记录关键字序列为(13，18，24，35，47，50，62，83，90)，查找方法用二分查找，要求计算出查找关键字62时的比较次数并计算出查找成功时的平均查找长度。
2,ASL=91*1+2*2+3*4+4*2)=25/9
4．设一棵树T中边的集合为{(A，B)，(A，C)，(A，D)，(B，E)，(C，F)，(C，G)}，要求用孩子兄弟表示法（二叉链表）表示出该树的存储结构并将该树转化成对应的二叉树。
树的链式存储结构略，二叉树略
5．设有无向图G，要求给出用普里姆算法构造最小生成树所走过的边的
集合。
E={(1，3)，(1，2)，(3，5)，(5，6)，(6，4)}
6．设有一组初始记录关键字为(45，80，48，40，22，78)，要求构造一棵二叉排序树并给出构造过程。
四、算法设计题(16分)
1．设有一组初始记录关键字序列（K1，K2，…，K n），要求设计一个算法能够在O(n)的时间复杂度内将线性表划分成两部分，其中左半部分的每个关键字均小于K i，右半部分的每个关键字均大于等于K i。
设有一组初始记录关键字序列（K1，K2，…，K n），要求设计一个算法能够在O(n)的时间复杂度内将线性表划分成两部分，其中左半部分的每个关键字均小于K i，右半部分的每个关键字均大于等于K i。
void quickpass(int r[], int s, int t)
{
int i=s, j=t, x=r[s];
while(i while (i while (i } r[i]=x; } 2．设有两个集合A和集合B，要求设计生成集合C=A∩B的算法，其中集合A、B和C用链式存储结构表示。 设有两个集合A和集合B，要求设计生成集合C=A∩B的算法，其中集合A、B和C用链式存储结构表示。 typedef struct node {int data; struct node *next;}lklist; void intersection(lklist *ha,lklist *hb,lklist *&hc) { lklist *p,*q,*t; for(p=ha,hc=0;p!=0;p=p->next) { for(q=hb;q!=0;q=q->next) if (q->data==p->data) break; if(q!=0){ t=(lklist *)malloc(sizeof(lklist)); t->data=p->data;t->next=hc; hc=t;} } } 数据结构试卷（三） 三、计算题(每题10分，共30分) 1.已知二叉树的前序遍历序列是AEFBGCDHIKJ ，中序遍历序列是EFAGBCHKIJD ，画出此二叉树，并画出它的后序线索二叉树。 A E B F G C D H F K J NULL 2．已知待散列的线性表为（36，15，40，63，22），散列用的一维地址空间为[0..6]，假定选用的散列函数是H （K ）= K mod 7，若发生冲突采用线性探查法处理，试： H(36)=36 mod 7=1; H １(22)=(1+1) mod 7=2; ….冲突 H(15)=15 mod 7=1;….冲突 H 2(22)=(2+1) mod 7=3; H １(15)=(1+1) mod 7=2; H(40)=40 mod 7=5; H(63)=63 mod 7=0; H(22)=22 mod 7=1; ….冲突 （1）计算出每一个元素的散列地址并在下图中填写出散列表： ` 0 1 2 3 4 5 6 63 36 15 22 40 （2）求出在查找每一个元素概率相等情况下的平均查找长度。 ASL= 6.15 3 1121=++++ 3．已知序列（10，18，4，3，6，12，1，9，18，8）请用快速排序写出每一趟排序的结果。 (8,9,4,3,6,1),10,(12,18,18) (1,6,4,3),8,(9),10,12,(18,18) 1,(3,4,6),8,9,10,12,18,(18) 1,3,(4,6),8,9,10,12,18,18 1,3, 4,6,8,9,10,12,18,18 四、算法设计题(每题15分，共30分) 1． 设计在单链表中删除值相同的多余结点的算法。 设计在单链表中删除值相同的多余结点的算法。 typedef int datatype; typedef struct node {datatype data; struct node *next;}lklist; void delredundant(lklist *&head) { lklist *p,*q,*s; for(p=head;p!=0;p=p->next) { for(q=p->next,s=q;q!=0; ) if (q->data==p->data) {s->next=q->next; free(q);q=s->next;} else {s=q,q=q->next;} } } 2． 设计一个求结点x 在二叉树中的双亲结点算法。 设计一个求结点x 在二叉树中的双亲结点算法。 typedef struct node {datatype data; struct node *lchild,*rchild;} bitree; bitree *q[20]; int r=0,f=0,flag=0; void preorder(bitree *bt, char x) { if (bt!=0 && flag==0) if (bt->data==x) { flag=1; return;} else {r=(r+1)% 20; q[r]=bt; preorder(bt->lchild,x); preorder(bt->rchild,x); } } void parent(bitree *bt,char x) { int i; preorder(bt,x); for(i=f+1; i<=r; i++) if (q[i]->lchild->data==x || q[i]->rchild->data) break; if (flag==0) printf("not found x\n"); else if (i<=r) printf("%c",bt->data); else printf("not parent"); } 数据结构试卷（四） 三、计算题(每题10分，共30分) 1、画出广义表LS=(( ) , (e) , (a , (b , c , d )))的头尾链表存储结构。 1 ---->---->---->---->---->11 11 1 11 11^ ^^ ^00^000e a b c d LS 2、下图所示的森林： (1) 求树（a ）的先根序列和后根序列； (1) ABCDEF; BDEFCA ；(2) ABCDEFGHIJK; BDEFCAIJKHG 林转换为相应的二叉树； A G B C D E F H I J K (2) 求森林先序序列和中序序列； ABCDEF; BDEFCA； （3）将此森林转换为相应的二叉树； A B C D E F G H I J K (a)(b) (2) ABCDEFGHIJK; BDEFCAIJKHG林转换为相应的二叉树； A G B C D E F H I J K 3、设散列表的地址范围是[ 0..9 ]，散列函数为H（key）= （key 2 +2）MOD 9,并采用链 表处理冲突，请画出元素7、4、5、3、6、2、8、9依次插入散列表的存储结构。 H(4)=H(5)=0,H(3)=H(6)=H(9)=2,H(8)=3,H(2)=H(7)=6 0 1 2 3 4 5 6 7 8 9 45 369 8 27 ^ ^ ^ ^ ^ ^ ^ ^ ^ 四、算法设计题(每题10分，共30分) 1．设单链表中有仅三类字符的数据元素(大写字母、数字和其它字符)，要求利用原单链表中结点空间设计出三个单链表的算法，使每个单链表只包含同类字符。 设单链表中有仅三类字符的数据元素(大写字母、数字和其它字符)，要求利用原单链表中结点空间设计出三个单链表的算法，使每个单链表只包含同类字符。 typedef char datatype; typedef struct node {datatype data; struct node *next;}lklist; void split(lklist *head,lklist *&ha,lklist *&hb,lklist *&hc) { lklist *p; ha=0,hb=0,hc=0; for(p=head;p!=0;p=head) { head=p->next; p->next=0; if (p->data>='A' && p->data<='Z') {p->next=ha; ha=p;} else if (p->data>='0' && p->data<='9') {p->next=hb; hb=p;} else {p->next=hc; hc=p;} } } 2.设计在链式存储结构上交换二叉树中所有结点左右子树的算法。 设计在链式存储结构上交换二叉树中所有结点左右子树的算法。 typedef struct node {int data; struct node *lchild,*rchild;} bitree; void swapbitree(bitree *bt) { bitree *p; if(bt==0) return; swapbitree(bt->lchild); swapbitree(bt->rchild); p=bt->lchild; bt->lchild=bt->rchild; bt->rchild=p; } 3.在链式存储结构上建立一棵二叉排序树。 在链式存储结构上建立一棵二叉排序树。 #define n 10 typedef struct node{int key; struct node *lchild,*rchild;}bitree; void bstinsert(bitree *&bt,int key) { if (bt==0){bt=(bitree *)malloc(sizeof(bitree)); bt->key=key;bt->lchild=bt->rchild=0;} else if (bt->key>key) bstinsert(bt->lchild,key); else bstinsert(bt->rchild,key); } void createbsttree(bitree *&bt) { int i; for(i=1;i<=n;i++) bstinsert(bt,random(100)); } 数据结构试卷（五） 三、应用题(32分) 1.设某棵二叉树的中序遍历序列为DBEAC，前序遍历序列为ABDEC， 要求给出该二叉树的的后序遍历序列。 DEBCA 2.设无向图G（如右图所示），给出该图的最小生成树上边的集合并 计算最小生成树各边上的权值之和。 E={(1,5),(5,2),(5,3),(3,4)},W=10 3.设一组初始记录关键字序列为(15，17，18，22，35，51，60)，要求计算出成功查找时 的平均查找长度。 ASL=(1*1+2*2+3*4)/7=17/7 4.设散列表的长度为8，散列函数H(k)=k mod 7，初始记录关键字序列为(25，31，8，27， 13，68)，要求分别计算出用线性探测法和链地址法作为解决冲突方法的平均查找长度。ASL1=7/6，ASL2=4/3 四、算法设计题(28分) 1．设计判断两个二叉树是否相同的算法。 设计判断两个二叉树是否相同的算法。 typedef struct node {datatype data; struct node *lchild,*rchild;} bitree; int judgebitree(bitree *bt1,bitree *bt2) { if (bt1==0 && bt2==0) return(1); else if (bt1==0 || bt2==0 ||bt1->data!=bt2->data) return(0); else return(judgebitree(bt1->lchild,bt2->lchild)*judgebitree(bt1->rchild,bt2->rchild)); } 2．设计两个有序单链表的合并排序算法。 设计两个有序单链表的合并排序算法。 void mergelklist(lklist *ha,lklist *hb,lklist *&hc) { lklist *s=hc=0; while(ha!=0 && hb!=0) if(ha->data else {if(s==0) hc=s=hb; else {s->next=hb; s=hb;};hb=hb->next;} if(ha==0) s->next=hb; else s->next=ha; } 数据结构试卷（六） 四、算法设计题(20分) １．设计在顺序有序表中实现二分查找的算法。 设计在顺序有序表中实现二分查找的算法。 struct record {int key; int others;}; int bisearch(struct record r[ ], int k) { int low=0,mid,high=n-1; while(low<=high) { mid=(low+high)/2; if(r[mid].key==k) return(mid+1); else if(r[mid].key>k) high=mid-1; else low=mid+1; } return(0); } ２．设计判断二叉树是否为二叉排序树的算法。 设计判断二叉树是否为二叉排序树的算法。 int minnum=-32768,flag=1; typedef struct node{int key; struct node *lchild,*rchild;}bitree; void inorder(bitree *bt) { if (bt!=0) {inorder(bt->lchild); if(minnum>bt->key)flag=0; minnum=bt->key;inorder(bt->rchild);} } 3.在链式存储结构上设计直接插入排序算法 在链式存储结构上设计直接插入排序算法 void straightinsertsort(lklist *&head) { lklist *s,*p,*q; int t; if (head==0 || head->next==0) return; else for(q=head,p=head->next;p!=0;p=q->next) { for(s=head;s!=q->next;s=s->next) if (s->data>p->data) break; if(s==q->next)q=p; else{q->next=p->next; p->next=s->next; s->next=p; t=p->data;p->data=s->data;s->data=t;} } } 数据结构试卷（七） 四、算法设计题(20分) 1.设计在链式结构上实现简单选择排序算法。 设计在链式结构上实现简单选择排序算法。 void simpleselectsorlklist(lklist *&head) { lklist *p,*q,*s; int min,t; if(head==0 ||head->next==0) return; for(q=head; q!=0;q=q->next) { min=q->data; s=q; for(p=q->next; p!=0;p=p->next) if(min>p->data){min=p->data; s=p;} if(s!=q){t=s->data; s->data=q->data; q->data=t;} } } 2.设计在顺序存储结构上实现求子串算法。 设计在顺序存储结构上实现求子串算法。 void substring(char s[ ], long start, long count, char t[ ]) { long i,j,length=strlen(s); if (start<1 || start>length) printf("The copy position is wrong"); else if (start+count-1>length) printf("Too characters to be copied"); else { for(i=start-1,j=0; i } 3.设计求结点在二叉排序树中层次的算法。 设计求结点在二叉排序树中层次的算法。 int lev=0; typedef struct node{int key; struct node *lchild,*rchild;}bitree; void level(bitree *bt,int x) { if (bt!=0) {lev++; if (bt->key==x) return; else if (bt->key>x) level(bt->lchild,x); else level(bt->rchild,x);} } 数据结构试卷（八） 四、算法设计题(20分) 1.设计一个在链式存储结构上统计二叉树中结点个数的算法。 设计一个在链式存储结构上统计二叉树中结点个数的算法。 void countnode(bitree *bt,int &count) { if(bt!=0) {count++; countnode(bt->lchild,count); countnode(bt->rchild,count);} } 2.设计一个算法将无向图的邻接矩阵转为对应邻接表的算法。 设计一个算法将无向图的邻接矩阵转为对应邻接表的算法。 typedef struct {int vertex[m]; int edge[m][m];}gadjmatrix; typedef struct node1{int info;int adjvertex; struct node1 *nextarc;}glinklistnode; typedef struct node2{int vertexinfo;glinklistnode *firstarc;}glinkheadnode; void adjmatrixtoadjlist(gadjmatrix g1[ ],glinkheadnode g2[ ]) { int i,j; glinklistnode *p; for(i=0;i<=n-1;i++) g2[i].firstarc=0; for(i=0;i<=n-1;i++) for(j=0;j<=n-1;j++) if (g1.edge[i][j]==1) { p=(glinklistnode *)malloc(sizeof(glinklistnode));p->adjvertex=j; p->nextarc=g[i].firstarc; g[i].firstarc=p; p=(glinklistnode *)malloc(sizeof(glinklistnode));p->adjvertex=i; p->nextarc=g[j].firstarc; g[j].firstarc=p; } } 数据结构试卷（九） 五、算法设计题(20分) 1．设计计算二叉树中所有结点值之和的算法。 设计计算二叉树中所有结点值之和的算法。 void sum(bitree *bt,int &s) { if(bt!=0) {s=s+bt->data; sum(bt->lchild,s); sum(bt->rchild,s);} } 2．设计将所有奇数移到所有偶数之前的算法。 设计将所有奇数移到所有偶数之前的算法。 void quickpass(int r[], int s, int t) { int i=s,j=t,x=r[s]; while(i { while (i while (i } r[i]=x; } 3．设计判断单链表中元素是否是递增的算法。 设计判断单链表中元素是否是递增的算法。 int isriselk(lklist *head) { if(head==0||head->next==0) return(1);else for(q=head,p=head->next; p!=0; q=p,p=p->next)if(q->data>p->data) return(0); return(1); } 数据结构试卷（十） 三、算法设计题(22分) 1． 设计在链式存储结构上合并排序的算法。 设计在链式存储结构上合并排序的算法。 void mergelklist(lklist *ha,lklist *hb,lklist *&hc) { lklist *s=hc=0; while(ha!=0 && hb!=0) if(ha->data 2． 设计在二叉排序树上查找结点X 的算法。 设计在二叉排序树上查找结点X 的算法。 bitree *bstsearch1(bitree *t, int key) { bitree *p=t; while(p!=0) if (p->key==key) return(p);else if (p->key>key)p=p->lchild; else p=p->rchild; return(0); } 3． 设关键字序列(k 1，k 2，…，k n-1)是堆，设计算法将关键字序列(k 1，k 2，…，k n-1，x)调 整为堆。 设关键字序列(k 1，k 2，…，k n-1)是堆，设计算法将关键字序列(k 1，k 2，…，k n-1，x)调整为堆。 void adjustheap(int r[ ],int n) { int j=n,i=j/2,temp=r[j-1]; while (i>=1) if (temp>=r[i-1])break; else{r[j-1]=r[i-1]; j=i; i=i/2;} r[j-1]=temp; } 数据结构试卷（一）参考答案 三、计算题（每题6分，共24分） 1. 线性表为：（78，50，40，60，34，90） 2. 邻接矩阵：????????? ???????01 1 1 10101110111010101110 邻接表如图11所示： 图11 3. 用克鲁斯卡尔算法得到的最小生成树为： (1,2)3, (4,6)4, (1,3)5, (1,4)8, (2,5)10, (4,7)20 4. 见图12 图12 四、读算法（每题7分，共14分） 1. （1）查询链表的尾结点 （2）将第一个结点链接到链表的尾部，作为新的尾结点 （3）返回的线性表为（a 2,a 3,…,a n ,a 1） 2. 递归地后序遍历链式存储的二叉树。 五、法填空（每空2分，共8 分） true BST->left BST->right 六、编写算法（8分） int CountX(LNode* HL,ElemType x) { int i=0; LNode* p=HL;//i 为计数器 while(p!=NULL) { if (P->data==x) i++; p=p->next; }//while, 出循环时i 中的值即为x 结点个数 return i; }//CountX 数据结构试卷（二）参考答案 四、算法设计题 1. 设有一组初始记录关键字序列（K 1，K 2，…，K n ），要求设计一个算法能够在O(n)的时 间复杂度内将线性表划分成两部分，其中左半部分的每个关键字均小于K i ，右半部分的每个关键字均大于等于K i 。 void quickpass(int r[], int s, int t) { int i=s, j=t, x=r[s]; while(i while (i 4 4 4 4 4 2 2 2 5 5 5 2 2 8 8 4 3 5 2 8 3 4 while (i r[i]=x; } 2. 设有两个集合A 和集合B ，要求设计生成集合C=A ∩B 的算法，其中集合A 、B 和C 用 链式存储结构表示。 typedef struct node {int data; struct node *next;}lklist; void intersection(lklist *ha,lklist *hb,lklist *&hc) { lklist *p,*q,*t; for(p=ha,hc=0;p!=0;p=p->next) { for(q=hb;q!=0;q=q->next) if (q->data==p->data) break; if(q!=0){ t=(lklist *)malloc(sizeof(lklist)); t->data=p->data;t->next=hc; hc=t;} } } 数据结构试卷（三）参考答案 三、计算题 1． A E B F G C D H F K J NULL 2、H(36)=36 mod 7=1; H １(22)=(1+1) mod 7=2; ….冲突 H(15)=15 mod 7=1;….冲突 H 2(22)=(2+1) mod 7=3; H １(15)=(1+1) mod 7=2; H(40)=40 mod 7=5; H(63)=63 mod 7=0; H(22)=22 mod 7=1; ….冲突 （1） 0 1 2 3 4 5 6 63 36 15 22 40 （2）ASL= 6.15 3 1121=++++ 3、(8,9,4,3,6,1),10,(12,18,18) (1,6,4,3),8,(9),10,12,(18,18) 1,(3,4,6),8,9,10,12,18,(18) 1,3,(4,6),8,9,10,12,18,18 1,3, 4,6,8,9,10,12,18,18 四、算法设计题 1. 设计在单链表中删除值相同的多余结点的算法。 typedef int datatype; typedef struct node {datatype data; struct node *next;}lklist; void delredundant(lklist *&head) { lklist *p,*q,*s; for(p=head;p!=0;p=p->next) { for(q=p->next,s=q;q!=0; ) if (q->data==p->data) {s->next=q->next; free(q);q=s->next;} else {s=q,q=q->next;} } } 2. 设计一个求结点x 在二叉树中的双亲结点算法。 typedef struct node {datatype data; struct node *lchild,*rchild;} bitree; bitree *q[20]; int r=0,f=0,flag=0; void preorder(bitree *bt, char x) { if (bt!=0 && flag==0) if (bt->data==x) { flag=1; return;} else {r=(r+1)% 20; q[r]=bt; preorder(bt->lchild,x); preorder(bt->rchild,x); } } void parent(bitree *bt,char x) { int i; preorder(bt,x); for(i=f+1; i<=r; i++) if (q[i]->lchild->data==x || q[i]->rchild->data) break; if (flag==0) printf("not found x\n"); else if (i<=r) printf("%c",bt->data); else printf("not parent"); } 数据结构试卷（四）参考答案 三、计算题 1． 1 ---->---->---->---->---->11 11 1 11 11^ ^^ ^00^000e a b c d LS 2． (1) ABCDEF; BDEFCA；(2) ABCDEFGHIJK; BDEFCAIJKHG林转换为相应的二叉树； A G B C D E F H I J K 3．H(4)=H(5)=0,H(3)=H(6)=H(9)=2,H(8)=3,H(2)=H(7)=6 0 1 2 3 4 5 6 7 8 9 45 369 8 27 ^ ^ ^ ^ ^ ^ ^ ^ ^ 四、算法设计题 1.设单链表中有仅三类字符的数据元素(大写字母、数字和其它字符)，要求利用原单链表 中结点空间设计出三个单链表的算法，使每个单链表只包含同类字符。 typedef char datatype; typedef struct node {datatype data; struct node *next;}lklist; void split(lklist *head,lklist *&ha,lklist *&hb,lklist *&hc) { lklist *p; ha=0,hb=0,hc=0; for(p=head;p!=0;p=head) { head=p->next; p->next=0; if (p->data>='A' && p->data<='Z') {p->next=ha; ha=p;} else if (p->data>='0' && p->data<='9') {p->next=hb; hb=p;} else {p->next=hc; hc=p;} } } 2.设计在链式存储结构上交换二叉树中所有结点左右子树的算法。 typedef struct node {int data; struct node *lchild,*rchild;} bitree; void swapbitree(bitree *bt) { bitree *p; if(bt==0) return; swapbitree(bt->lchild); swapbitree(bt->rchild); p=bt->lchild; bt->lchild=bt->rchild; bt->rchild=p; } 3.在链式存储结构上建立一棵二叉排序树。 填空题 1.文件可按其记录的类型不同而分成两类，即( 操作系统文件 )和( 数据库 )文件。 2.数据库文件按记录中关键字的多少可分成( 单关键字文件 )和( 多关键字文件 )两种文件。 3.文件由( 记录 )组成，记录由( 数据项 )组成。 4.从用户观点看，文件的逻辑结构通常可以区分为两类：一类是如dBASE中数据库文件那样的文件组织结构，称为( 数据库 )文件；另一种是诸如用各种文字处理软件编辑成的文本文件，称为( 文本 )文件。 从文件在存储器上的存放方式来看，文件的物理结构往往可区分为三类，即( 顺序组织 )、 ( 随机组织 )、( 链组织 )。 B+树适用于组织( 随机组织 )的索引结构， m阶B+树每个结点至多有( m ) 除根结点外每个结点至少有( (m/2)向上取整 )个儿子，根结点至少有( 2 )个儿子，有k个儿子的结点必有( k )个关键码。 5.物理记录之间的次序由指针相链表示的顺序文件称为( 串联文件) 6.顺序文件中，要存取第I个记录，必须先存取( 第I-1 )个记录。 7.索引顺序文件既可以顺序存取，也可以( 随机 )存取。 8.建立索引文件的目的的( 提高查找速度 )。 9.索引顺序文件是最常用的文件组织之一，通常用( 树 )结构来组织索引。 10.倒排文件的主在优点在于( 检索记录块 )。 11.检索是为了在文件中满足一定条件的记录而设置的操作。检索可以按( 关 键字 )检索，也可以按( 记录号 ) 检索； 按( 记录号 ) 检索又可以有( 顺序 ) 检索和( 直接 ) 检索。 12.哈希检索的技术的关键是( 构造哈希函数 )和( 解决冲突的方法 )。结构来组织索引。 13.VSAM系统是由( 索引集 )、( 顺序集 ) 、( 数据集 )构成的。 14.VSAM( 虚拟存储存取方法 )文件的优点是：动态地( 分配和释放存储空间 ) ，不需要文件进行( 重组 ) ，并能较快地( 对插入的记录 ) 进行查找。 一～五章选择题 一 1.学习数据结构的主要目的是( C )。 A．处理数据计算问题 B．研究程序设计技巧 C．选取合适数据结构，写出更有效的算法 D．是计算机硬件课程的基础2.数据结构是一门研究非数值计算的程序设计问题中计算机的逻辑存储以及 它们之间的( B )和运算的科学。 A．结构 B．关系 C．运算 D．算法 3.在计算机中存储一个数据元素的位串称为 ( A ) 。 A. 结点 B. 数据项 C. 数据字段 D. 字符串 4.算法指的是( C ) A.计算机程序 B.排序算法 C.解决问题的有限运算序列 D.解决问题的计算方法 5.( D )是数据不可分割的最小单位。 A．数据结构 B．数据对象 C．数据元素 D．数据项 6.数据结构有 ( D ) 种基本逻辑结构。 A. 1 B. 2 C. 3 D. 4 7.在数据结构中，从逻辑上可以把数据结构分成( C )。 A．动态结构和静态结构 B．紧凑结构和非紧凑结构 C．线性结构和非线性结构 D．内部结构和外部结构 8.通常所说的时间复杂度是指( B )。 期末考试总结大全 期末考试结束了，同学们有没考好？没考好原因是什么？下面是小雅整理的期末考试总结大全，欢迎阅读参考！ 期末考试总结一 期末考试成绩公布了。我的成绩是：语文96、数学79分。语文成绩列全班第20名，数学成绩列第一名——倒数第一名。闭幕式后我把成绩册丢在班级不敢带回家给爸爸妈妈看。 回到家，我赶忙躲到自己的房间里关起门来，眼泪也不由自主的从眼角溜了出来…… 爸爸下班回到家里，知道了我的期末考试情况，没有想到他没有责备我，他说： 要为成功总结经验，不要为失败找借口。语文能考96分是因为我将要求背诵的课文、抄写的生字都掌握了，而且还在爸爸的辅导下做了三份期末模拟试卷。而数学考试考成这个样子的原因就恰好相反：老师布置的作业没有完成，考试的时候粗心大意…… 知道这些使我落后的原因了，我一定会针对它们加以改正，争取当上“三好学生”。 期末考试总结二 光阴似箭、日月如梭。四年级学习生活不知不觉结束了，在这个学期里，老师为我们的学习付出了许多心血，我们也为自己 的学习洒下了辛勤的汗水。这次期末考试，我的每门功课都达到老师和家长满意的成绩：数学100分、英语100分、语文98分，总结这个学期的学习，我想主要有以下几个方面： 第一，学习态度比较端正。能够做到上课认真听讲，不与同学交头接耳，不做小动作，自觉遵守课堂纪律;对老师布置的课堂作业，能够当堂完成;对不懂的问题，主动和同学商量，或者向老师请教。 第二，改进了学习方法。为了改进学习方法，我给自己订了一个学习计划：（1）做好课前预习。也就是要挤出时间，把老师还没有讲过的内容先看一遍。尤其是语文课，要先把生字认会，把课文读熟;对课文要能分清层次，说出段意，正确理解课文内容。要求背诵的课文提前背过。坚持写日记，记录生活笔记。（2）上课要积极发言。对于没有听懂的问题，要敢于举手提问。积极发言，大胆思考。（3）每天的家庭作业认真检查，再让家长检查一遍，把做错了的和不会做的，让家长讲一讲，记在错题集上，考前几天再把以前做错了的题目，经常拿出来看一看，复习复习。（4）要多读一些课外书，了解课外知识，每天中午吃完饭，看半个小时课外书;每天晚上做完作业，只要有时间，多看几篇作文。 第三，课外特长不放松。能够利用星期天和节假日，到课外辅导班学习绘画，在学校的想象画评比中，我荣获“艺术之星”的称号。 期末考试总结作文 导读：篇一：期末考试总结_250字 今天，我要去学校拿期末考试成绩单。到了学校，我的心里非常紧张，因为我想知道语文和数学能考多少分。成绩单发下来了，我看到语文作文是满分，考试成绩是96.5分，数学是100分。太好啦，我的玩具有希望啦!因为妈妈答应我只要有一科考了满分，就给我买“面包工坊”的玩具。 我对这次考试不是太满意，但是妈妈夸奖了我，认为我考的很好，因为我没有犯马虎的坏习惯，错的都是我不会的题，所以妈妈下午要带我去买我想要的玩具和我喜欢的好吃的，我真开心。 我下学期一定要好好学习，争取考双百。 天津市河东区中心东道小学二年级：张周瑶 篇二：期末考试总结500字 这个学期结束了。在这个学期里，老师为我们的学习付出了许多心血，我们也为自己的学习洒下了许多辛勤的汗水。这次期末考试，我的每门功课，都取得了比较好的成绩。 总结这个学期的学习，我想，主要有以下几个方面： 第一，学习态度比较端正。能够做到上课认真听讲，不与同学交头接耳，不做小动作，自觉遵守课堂纪律;对老师布置的课堂作业，能够当堂完成;对不懂的问题，主动和同学商量，或者向老师请教。 第二，改进了学习方法。为了改进学习方法，我给自己订了一个学习计划：(1)做好课前预习。也就是要挤出时间，把老师还没有讲 过的内容先看一遍。尤其是语文课，要先把生字认会，把课文读熟;对课文要能分清层次，说出段意，正确理解课文内容。(2)上课要积极发言。对于没有听懂的问题，要敢于举手提问。(3)每天的家庭作业，做完后先让家长检查一遍，把做错了的和不会做的，让家长讲一讲，把以前做错了的题目，经常拿出来看一看，复习复习。要多读一些课外书。每天中午吃完饭，看半个小时课外书;每天晚上做完作业，只要有时间，再看几篇作文。 第三，课外学习不放松。能够利用星期天和节假日，到少年宫去学习作文、奥数、英语和书法，按时完成老师布置的作业，各门功课都取得了好的成绩。参加少儿书法大赛，还获得了特金奖。 经过自己的不懈努力，这学期的各门功课，都取得了比较好的成绩。自己被评为三好学生，还获得了“小作家”的荣誉称号。 虽然取得了比较好的成绩，但我决不骄傲，还要继续努力，争取百尺竿头，更进一步，下学期还要取得更好的成绩。 篇三：期末考试总结800字 各位同学，老师： 大家好! 85个人，两个多月，七轮考试，终于尘埃落定。在这过程中绿有一句话，我特别喜欢“每一次考试，我们要注重的，不是分数，而是过程。”的确，细细盘算下来，我不由得开始敬佩这里的每一个人，在这七轮考试中，我们每个人克服了36次自己心里和生理上的压力来参加考试，遭受了36次来自不同程度的打击。但如今，我们仍然 数据结构知识点概括 第一章概论 数据就是指能够被计算机识别、存储和加工处理的信息的载体。 数据元素是数据的基本单位，可以由若干个数据项组成。数据项是具有独立含义的最小标识单位。 数据结构的定义： ·逻辑结构：从逻辑结构上描述数据，独立于计算机。·线性结构：一对一关系。 ·线性结构：多对多关系。 ·存储结构：是逻辑结构用计算机语言的实现。·顺序存储结构：如数组。 ·链式存储结构：如链表。 ·索引存储结构：·稠密索引：每个结点都有索引项。 ·稀疏索引：每组结点都有索引项。 ·散列存储结构：如散列表。 ·数据运算。 ·对数据的操作。定义在逻辑结构上，每种逻辑结构都有一个运算集合。 ·常用的有：检索、插入、删除、更新、排序。 数据类型：是一个值的集合以及在这些值上定义的一组操作的总称。 ·结构类型：由用户借助于描述机制定义，是导出类型。 抽象数据类型ADT：·是抽象数据的组织和与之的操作。相当于在概念层上描述问题。 ·优点是将数据和操作封装在一起实现了信息隐藏。 程序设计的实质是对实际问题选择一种好的数据结构，设计一个好的算法。算法取决于数据结构。 算法是一个良定义的计算过程，以一个或多个值输入，并以一个或多个值输出。 评价算法的好坏的因素：·算法是正确的； ·执行算法的时间； ·执行算法的存储空间（主要是辅助存储空间）； ·算法易于理解、编码、调试。 时间复杂度：是某个算法的时间耗费，它是该算法所求解问题规模n的函数。 渐近时间复杂度：是指当问题规模趋向无穷大时，该算法时间复杂度的数量级。 评价一个算法的时间性能时，主要标准就是算法的渐近时间复杂度。 算法中语句的频度不仅与问题规模有关，还与输入实例中各元素的取值相关。 时间复杂度按数量级递增排列依次为：常数阶O（1）、对数阶O（log2n）、线性阶O（n）、线性对数阶O（nlog2n）、平方阶O （n^2）、立方阶O（n^3）、……k次方阶O（n^k）、指数阶O（2^n）。 《数据结构》期末考试题型及分值 （1）简答题6题*5分=30分简要回答要点 （2）分析题6题*5分=30分给出结果 （3）设计题1题*10分=10分设计思想及结果 （4）编程题1题*10分=10分完整代码 （5）综合题1题*20分=20分抽象数据类型的定义、表示、实现、算法分析{定义=功能（ADT）表示=存储结构体实现=算法（基本操作）算法分析=时间、空间复杂度} 考试概念有：1.数据结构{一、线性表（栈-队-列-串-数组-广义表-逻辑结构-存储结构-运算结构） 二、非线性表（集合-树-图）} 2.抽象数据类型数据对象-数据关系-基本操作 3.算法性质-要求（设计）-效率（度量） 4.实例查找：高效查找算法 排序：高效的排序算法 分析题考试题目参考 （1）1-2-3-4-5-6顺序建BBST （2）6-5-4-3-2-1顺序建BBST 简答题实例 设计题： （1） （2） 数据结构试卷（一） 三、计算题（每题6分，共24分） 1. 在如下数组A 中链接存储了一个线性表，表头指针为A[0].next ，试写出该线性表。 A01234567 dat a 60 50 78 90 34 40 nex t 3 5 7 2 0 4 1 线性表为：（78，50，40，60，34，90）??????? ?????????01110 10 1 11101 11010101110 2. 请画出下图的邻接矩阵和邻接表。 3. 已知一个图的顶点集V 和边集E 分别为：V={1,2,3,4,5,6,7}; E={(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15, (3,5)12,(3,6)9,(4,6)4,(4,7)20,(5,6)18,(6,7)25}; 用克鲁斯卡尔算法得到最小生成树，试写出在最小生成树中依次得到的各条边。 用克鲁斯卡尔算法得到的最小生成树为： (1,2)3,(4,6)4,(1,3)5,(1,4)8,(2,5)10,(4,7)20 4.画出向小根堆中加入数据4,2,5,8,3时，每加入一个数据后堆的变化。见图12 图12 图11 四、阅读算法（每题7分，共14分） 4 4 4 4 4 2 2 2 5 5 5 2 2 8 8 4 3 5 2 8 3 4 期末考试总结作文600字 导读：紧张的期末考试已经过去了，下面就自己的表现做个总结吧。 期末考试总结作文一 自背上书包，成为一名学生后，我经历了无数次的考试，他们犹如过眼云烟在脑海里给抹掉了。但是，五年级上学期的期末考试却令我久久不能忘怀。从这次的期末考试中，我看到了自己的优点和缺点。 虽然这次语文试卷我得了95。5分，但是我并不满足。有好多题都是因为马虎而做错的。其中有一道题，是因为我不复习错的。还有就是因为我不经常看新闻联播答错的。所以，我以后要多看新闻联播，多关心国家大事! 这次的数学卷子我真不应该得85分，我应该得满分。有一道判断题老师已经讲过无数次了，但我还是做错了，一个判断题，就这样被减了一分!另一分是因为我检查时的疏忽，被扣掉的`。所以，以后老师讲课时，我要更加留心做好笔记，绝不三心二意。 这次英语我得了80分。有的是因为我不好好背课文，填空错了。有的是因为我不按老师的要求做，翻译词组错了。以后，我要听老师话，多背课文。 科学，品社试卷体现出我犯了一个天大的错误!那就是——我没有意识到这个科目的重要性，答完试卷后而不检查试卷!导致科学只得了91分，品社只得了84分。我以后争取取得一个更好的成绩! 通过这次考试，我发现自己的优点是能及时的发现自己的不足， 总结经验，为以后的考试提供借鉴。缺点是做完试卷后，检查的不到位。还有一个总也“陪伴”我的“小马虎”!我决定，从此以后，我再也不和“小马虎”做朋友了。我要总结经验，争取在以后的考试中取得更好的成绩!!!! 期末考试总结作文二 期末考试结束了，试卷发下来了，这次考试题量不大，也不难，只要上课认真听讲，平时认真完成老师布置的作业，做好这三张卷子并不难。我的语文考了95。5分，数学和英语都考了98。5分。 我自认为数学和英语是能考100分的，结果还是出了点问题。数学是因为有一道估算的题“八千加一千等于多少?”我把答案写成了“八千”，考试检查的时候，总认为这些题第一次已经算过了，是对的，因为检查不够细心造成丢分。 英语是因为两道选择题出错而失分。第一道是选“there”的意思，应该是“那里、那儿”，可是我选成了“这里、这儿”;第二道题是选“不能在课堂上睡觉”用英语怎么说，正确答案应该是：“Don't sleep in class。”，可我选成了“Not sleep in class。”。又是因为检查时不细心，造成失分，下次考试我一定要做到细心、细心、再细心。这样才能考出自己的最好水平。妈妈也说过：“一道题错了，要是不会是可以原谅的，以后学会就行;但是因为粗心而出错，是不能原谅的。” 这次语文考试在作文方面我是吃了亏的，内容还不错，就是因为写了几个错字，我把“旗”错写成了“旅”，把“拔”错写成了“拨”， 第一章数据结构概述 基本概念与术语 1．数据：数据是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序所处理的符号的总称。 2. 数据元素：数据元素是数据的基本单位，是数据这个集合中的个体，也称之为元素，结点，顶点记录。 (补充：一个数据元素可由若干个数据项组成。数据项是数据的不可分割的最小单位。 ) 3．数据对象：数据对象是具有相同性质的数据元素的集合，是数据的一个子集。(有时候也 叫做属性。) 4．数据结构：数据结构是相互之间存在一种或多种特定关系的数据元素的集合。 (1)数据的逻辑结构：数据的逻辑结构是指数据元素之间存在的固有逻辑关系，常称为数据结构。 数据的逻辑结构是从数据元素之间存在的逻辑关系上描述数据与数据的存储无关，是独立于计算机的。 依据数据元素之间的关系，可以把数据的逻辑结构分成以下几种： 1. 集合：数据中的数据元素之间除了“同属于一个集合“的关系以外，没有其他关系。 2. 线性结构：结构中的数据元素之间存在“一对一“的关系。若结构为非空集合，则除了第一个元素之外，和最后一个元素之外，其他每个元素都只有一个直接前驱和一个直接后继。 3. 树形结构：结构中的数据元素之间存在“一对多“的关系。若数据为非空集，则除了第一个元素 (根)之外，其它每个数据元素都只有一个直接前驱，以及多个或零个直接后继。 4. 图状结构：结构中的数据元素存在“多对多”的关系。若结构为非空集，折每个数据可有多个(或零个)直接后继。 (2)数据的存储结构：数据元素及其关系在计算机内的表示称为数据的存储结构。想要计算机处理数据，就必须把数据的逻辑结构映射为数据的存储结构。逻辑结构可以映射为以下两种存储结构： 1. 顺序存储结构：把逻辑上相邻的数据元素存储在物理位置也相邻的存储单元中，借助元素在存储器中的相对位置来表示数据之间的逻辑关系。 2. 链式存储结构：借助指针表达数据元素之间的逻辑关系。不要求逻辑上相邻的数据元素物理位置上也相邻。 5. 时间复杂度分析：1.常量阶：算法的时间复杂度与问题规模n 无关系T(n)=O(1) 2. 线性阶：算法的时间复杂度与问题规模 n 成线性关系T(n)=O(n) 3. 平方阶和立方阶：一般为循环的嵌套，循环体最后条件为i++ 时间复杂度的大小比较： O(1)< O(log 2 n)< O(n )< O(n log 2 n)< O(n2)< O(n3)< O(2 n ) 2011-2012学年第一学期期末考查 《数据结构》试卷 （答案一律写在答题纸上，在本试卷上做答无效） 一、选择（每题1分，共10分） 1.长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法时间复杂度为（） A.O(0) B.O(1) C.O(n) D.O(n2) 2.六个元素按照6，5，4，3，2，1的顺序入栈，下列哪一个是合法的出栈序列？（） A.543612 B.453126 C.346512 D.234156 3.设树的度为4，其中度为1、2、3、4的结点个数分别是4、2、1、2，则树中叶子个数为（） A.8 B.9 C.10 D.11 4.设森林F对应的二叉树B有m个结点，B的右子树结点个数为n，森林F中第一棵树的结点个数是（） A. m-n B.m-n-1 C.n+1 D.m+n 5.若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（） A.9 B.11 C.15 D.不确定 6.下列哪一个方法可以判断出一个有向图是否有环。（） A.深度优先遍历 B.拓扑排序 C.求最短路径 D.求关键路径 7.第7层有10个叶子结点的完全二叉树不可能有（）个结点。 A.73 B.234 C.235 D.236 8.分别用以下序列构造二叉排序树，与用其他三个序列构造的结果不同的是（） A.（100,80,90,60,120,110,130） B.（100, 120, 110,130,80, 60,90） C.（100,60,80,90,120,110,130） D.（100,80, 60,90, 120, 130,110） 9.对一组数据（84，47，25，15，21）排序，数据的排列次序在排序过程中变化如下：（1）84 47 25 15 21 （2）15 47 25 84 21 （3）15 21 25 84 47（4）15 21 25 47 84则采用的排序方法是（） 复习提纲 第一章数据结构概述 基本概念与术语（P3） 1．数据结构是一门研究非数值计算程序设计问题中计算机的操作对象以及他们之间的关系和操作的学科. 2．数据是用来描述现实世界的数字,字符,图像,声音,以及能够输入到计算机中并能被计算机识别的符号的集合 2．数据元素是数据的基本单位 3．数据对象相同性质的数据元素的集合 4．数据结构包括三方面内容:数据的逻辑结构.数据的存储结构.数据的操作. （1）数据的逻辑结构指数据元素之间固有的逻辑关系. （2）数据的存储结构指数据元素及其关系在计算机内的表示 ( 3 ) 数据的操作指在数据逻辑结构上定义的操作算法,如插入,删除等. 5.时间复杂度分析 -------------------------------------------------------------------------------------------------------------------- 1、名词解释：数据结构、二元组 2、根据数据元素之间关系的不同，数据的逻辑结构可以分为 集合、线性结构、树形结构和图状结构四种类型。 3、常见的数据存储结构一般有四种类型，它们分别是___顺序存储结构_____、___链式存储结构_____、___索引存储结构_____和___散列存储结构_____。 4、以下程序段的时间复杂度为___O(N2)_____。 int i,j,x; for(i=0;i 期末考试总结作文「推荐」 本文是关于考试的话题作文，仅供大家参考！ 导语：光阴似箭，日月如梭。”一转眼，又一个学期即将结束，期末考试成绩也出来了。下面是小编整理的一些关于期末考试的优秀作文，欢迎查阅! 篇一：期末考试总结_250字今天，我要去学校拿期末考试成绩单。到了学校，我的心里非常紧张，因为我想知道语文和数学能考多少分。成绩单发下来了，我看到语文作文是满分，考试成绩是96.5分，数学是100分。太好啦，我的玩具有希望啦!因为妈妈答应我只要有一科考了满分，就给我买“面包工坊”的玩具。 我对这次考试不是太满意，但是妈妈夸奖了我，认为我考的很好，因为我没有犯马虎的坏习惯，错的都是我不会的题，所以妈妈下午要带我去买我想要的玩具和我喜欢的好吃的，我真开心。 我下学期一定要好好学习，争取考双百。 天津市河东区中心东道小学二年级：张周瑶 篇二：期末考试总结500字这个学期结束了。在这个学期里，老师为我们的学习付出了许多心血，我们也为自己的学习洒下了许多辛勤的汗水。这次期末考试，我的每门功课，都取得了比较好的成绩。 总结这个学期的学习，我想，主要有以下几个方面： 第一，学习态度比较端正。能够做到上课认真听讲，不与同学交头接耳，不做小动作，自觉遵守课堂纪律;对老师布置的课堂作业， 能够当堂完成;对不懂的问题，主动和同学商量，或者向老师请教。 第二，改进了学习方法。为了改进学习方法，我给自己订了一个学习计划：(1)做好课前预习。也就是要挤出时间，把老师还没有讲过的内容先看一遍。尤其是语文课，要先把生字认会，把课文读熟;对课文要能分清层次，说出段意，正确理解课文内容。(2)上课要积极发言。对于没有听懂的问题，要敢于举手提问。(3)每天的家庭作业，做完后先让家长检查一遍，把做错了的和不会做的，让家长讲一讲，把以前做错了的题目，经常拿出来看一看，复习复习。要多读一些课外书。每天中午吃完饭，看半个小时课外书;每天晚上做完作业，只要有时间，再看几篇作文。 第三，课外学习不放松。能够利用星期天和节假日，到少年宫去学习作文、奥数、英语和书法，按时完成老师布置的作业，各门功课都取得了好的成绩。参加少儿书法大赛，还获得了特金奖。 经过自己的不懈努力，这学期的各门功课，都取得了比较好的成绩。自己被评为三好学生，还获得了“小作家”的荣誉称号。 虽然取得了比较好的成绩，但我决不骄傲，还要继续努力，争取百尺竿头，更进一步，下学期还要取得更好的成绩。 篇三：期末考试总结800字各位同学，老师： 大家好! 85个人，两个多月，七轮考试，终于尘埃落定。在这过程中绿有一句话，我特别喜欢“每一次考试，我们要注重的，不是分数，而是过程。”的确，细细盘算下来，我不由得开始敬佩这里的每一个人， 自考02331数据构造重点总结(最后修订) 第一章概论 1.瑞士计算机科学家沃思提出：算法+数据构造=程序。算法是对数据运算描述，而数据构造涉及逻辑构造和存储构造。由此可见，程序设计实质是针对实际问题选取一种好数据构造和设计一种好算法，而好算法在很大限度上取决于描述实际问题数据构造。 2.数据是信息载体。数据元素是数据基本单位。一种数据元素可以由若干个数据项构成，数据项是具备独立含义最小标记单位。数据对象是具备相似性质数据元素集合。 3.数据构造指是数据元素之间互有关系，即数据组织形式。 数据构造普通涉及如下三方面内容：数据逻辑构造、数据存储构造、数据运算 ①数据逻辑构造是从逻辑关系上描述数据，与数据元素存储构造无关，是独立于计算机。 数据逻辑构造分类：线性构造和非线性构造。 线性表是一种典型线性构造。栈、队列、串等都是线性构造。数组、广义表、树和图等数据构造都是非线性构造。 ②数据元素及其关系在计算机内存储方式，称为数据存储构造（物理构造）。 数据存储构造是逻辑构造用计算机语言实现，它依赖于计算机语言。 ③数据运算。最惯用检索、插入、删除、更新、排序等。 4.数据四种基本存储办法：顺序存储、链接存储、索引存储、散列存储 （1）顺序存储：普通借助程序设计语言数组描述。 （2）链接存储：普通借助于程序语言指针来描述。 （3）索引存储：索引表由若干索引项构成。核心字是能唯一标记一种元素一种或各种数据项组合。 （4）散列存储：该办法基本思想是：依照元素核心字直接计算出该元素存储地址。 5.算法必要满足5个准则：输入，0个或各种数据作为输入；输出，产生一种或各种输出；有穷性，算法执行有限步后结束；拟定性，每一条指令含义都明确；可行性，算法是可行。 算法与程序区别：程序必要依赖于计算机程序语言，而一种算法可用自然语言、计算机程序语言、数学语言或商定符号语言来描述。当前惯用描述算法语言有两类：类Pascal和类C。 6.评价算法优劣：算法"对的性"是一方面要考虑。此外，重要考虑如下三点： ①执行算法所耗费时间，即时间复杂性； ②执行算法所耗费存储空间，重要是辅助空间，即空间复杂性； ③算法应易于理解、易于编程，易于调试等，即可读性和可操作性。 数据结构复习要点带答案 算法的五大特性：（有零个或多个输入）、（有一个或多个输出）、（有穷性）、（确定性）、（可行性）。 算法指的是（）。 A 对特定问题求解步骤的一种描述，是指令的有限序列；算法分析的目的是（分析算法的效率以求改 进），算法分析的两个主要方面是（空间性能和时间性能）。 1.算法质量的标准：时间复杂度是测量一个算法优劣的重要标准。 时间复杂度的计算：设待处理问题的规模为n，若一个算法的时间复杂度为一个常数，则表示成数量级的形式为（Ο(1)），若为n*log25n，则表示成数量级的形式为（Ο(nlog2n)）。 【分析】：用大O记号表示算法的时间复杂度，需要将低次幂去掉，将最高次幂的系数去掉。 2.数据、数据元素、数据项的关系：（数据元素）是数据的基本单位，在计算机程序中通常作为一个整体 进行考虑和处理；（数据项）是数据的最小单位，（数据元素）是讨论数据结构时涉及的最小数据单位。 【分析】数据结构指的是数据元素以及数据元素之间的关系。 3.设有数据结构（D，R），其中D={1, 2, 3, 4, 5, 6}，R={(1,2),(2,3),(2,4),(3,4),(3,5),(3,6),(4,5),(4,6)}。 试画出其逻辑结构图并指出属于何种结构。 【解答】其逻辑结构图如图1-3所示，它是一种图结构。 4.栈的特性：栈是限定仅在表尾进行插入和删除操作的线性表，允许插入和删除的一段叫做栈顶，另一 端叫做栈底，不含任何数据元素的栈叫做空栈。（栈）可作为实现递归函数调用的一种数据结构。 【分析】递归函数的调用和返回正好符合后进先出性。 栈的特点是先进后出，即：进去的早，出来的晚！ 54321进栈，5在栈底，1在栈顶！ 出一次栈，则栈顶的1先出来，2成为新的栈顶。 ABCD入栈，D成为新的栈顶。 全部出栈：D C B A 2 3 4 5 综上，所有元素退栈顺序为：1 D C B A 2 3 4 5 5.入栈：template 期中考试分析总结日记 关于期中考试的分析总结大家了解过多少呢？可能很 多人都不是很清楚，而XX在这里为大家分享下期中考试分 析总结日记，大家都一起来看一下吧。 这次我班学生考试成绩一般，平均86分多一点，有几个没有考好的，总结原因如下： 1、有些同学很聪明，但很粗心，平时没有养成细致认 真的习惯，考试的时候答题粗心大意、马马虎虎，导致很多 题目会做却被扣分甚至没有做对。 2、认识不到位，准备不充分。毛主席说，不打无准备 之仗。言外之意，无准备之仗很难打赢，我却没有按照这句 至理名言行事，导致这次考试吃了亏。 3.没有解决好兴趣与课程学习的矛盾。自己有很多兴趣， 作为一个人，一个完整的人，一个明白的人，当然不应该同 机器一样，让自己的兴趣被平白无故抹煞，那样不仅悲惨而 且无知，但是，如果因为自己的兴趣严重耽搁了学习就不好 了，不仅不好，有时候真的是得不偿失。 今后我将对我的学生提出如下要求，并经常提醒、检查。 一、课内重视听讲，课后及时复习。 新知识的接受，数学能力的培养主要在课堂上进行，所 以要特点重视课内的学习效率，寻求正确的学习方法。上课 时要紧跟老师的思路，积极展开思维预测下面的步骤，比较 自己的解题思路与教师所讲有哪些不同。特别要抓住基础知 识和基本技能的学习，课后要及时复习不留疑点。首先要在 做各种习题之前将老师所讲的知识点回忆一遍，正确掌握各 类公式的推理过程，庆尽量回忆而不采用不清楚立即翻书之 举。认真独立完成作业，勤于思考，从某种意义上讲，应不 造成不懂即问的学习作风，对于有些题目由于自己的思路不 清，一时难以解出，应让自己冷静下来认真分析题目，尽量 自己解决。在每个阶段的学习中要进行整理和归纳总结，把 知识的点、线、面结合起来交织成知识网络，纳入自己的知 识体系。 二、适当多做题，养成良好的解题习惯。 要想学好数学，多做题目是难免的，熟悉掌握各种题型 的解题思路。刚开始要从基础题入手，以课本上的习题为准，反复练习打好基础，再找一些课外的习题，以帮助开拓思路，提高自己的分析、解决能力，掌握一般的解题规律。对于一 些易错题，可备有错题集，写出自己的解题思路和正确的解 题过程两者一起比较找出自己的错误所在，以便及时更正。 在平时要养成良好的解题习惯。让自己的精力高度集中，使 大脑兴奋，思维敏捷，能够进入最佳状态，在考试中能运用 自如。实践证明：越到关键时候，你所表现的解题习惯与平 时练习无异。如果平时解题时随便、粗心、大意等，往往在 大考中充分暴露，故在平时养成良好的解题习惯是非常重要 期末考试总结作文550字 期末考试总结作文550字1 考试后，我最关心的事莫过于各科的成绩了。成绩很不理想。其实分数只不过是检测我们对知识掌握了多少而已，不必耿耿于怀，而是要明白自己在哪里失分了，找出原因，及时弥补。我们必须总结失分的原因，采取措施，加以补救。 这次考试不理想的原因如下： 1、考前没有好好复习。临急抱佛脚。正如毛泽东所说，不打无准备之战。言外之意是没有准备过得事很难做好，而我却没有好好准备，导致失分了。 2、平时没有养成认真检查的习惯。答完卷之后，没有认真检查试卷，马马虎虎、粗心大意，导致失分严重。 认证弥补，加以改正。采取正确的方法学习。 语文，要多看课外书，提高作文水平。因为现在语文写作占很多分。想要语文成绩变好，首先要想法设法提高作文水平，这样才能拿到高分。 数学，是我最好的一科也是最致命的一科。因为有时做完卷子，没有认真检查，导致失分。所以我们做数学的时候 要细心、不马虎、不掉以轻心。 英语，是我最薄弱的一科。特别是听力和句型，所以我要在周末多听英语，多做题目，不会就问，希望英语不再那么差。 政治，是我有史以来，考的最好的一次了。 物理，要多背物理公式，多做习题，不过不要搞“题海战术”要适可而止。 这次考试虽然没有考好，但是我相信，只要坚持，我的成绩一定有所提高。 世上无难事，只怕有心人。 期末考试总结作文550字2 总结这个学期的学习，我想，主要有以下几个方面： 第一，学习态度比较端正。能够做到上课认真听讲，不与同学交头接耳，不做小动作，自觉遵守课堂纪律;对老师布置的课堂作业，能够当堂完成;对不懂的问题，主动和同学商量，或者向老师请教。 第二，改进了学习方法。为了改进学习方法，我给自己订了一个学习计划：(1)做好课前预习。也就是要挤出时间，把老师还没有讲过的内容先看一遍。尤其是语文课，要先把 第一章概论 1.数据结构描述的是按照一定逻辑关系组织起来的待处理数据元素的表示及相关操作，涉及数据的逻辑结构、存储结构和运算 2.数据的逻辑结构是从具体问题抽象出来的数学模型，反映了事物的组成结构及事物之间的逻辑关系 可以用一组数据（结点集合K）以及这些数据之间的一组二元关系（关系集合R）来表示：(K, R) 结点集K是由有限个结点组成的集合，每一个结点代表一个数据或一组有明确结构的数据 关系集R是定义在集合K上的一组关系，其中每个关系r（r∈R）都是K×K上的二元关系 3.数据类型 a.基本数据类型 整数类型(integer)、实数类型(real)、布尔类型(boolean)、字符类型（char）、指针类型（pointer）b.复合数据类型 复合类型是由基本数据类型组合而成的数据类型；复合数据类型本身，又可参与定义结构更为复杂的结点类型 4.数据结构的分类：线性结构（一对一）、树型结构（一对多）、图结构（多对多） 5.四种基本存储映射方法：顺序、链接、索引、散列 6.算法的特性：通用性、有效性、确定性、有穷性 7.算法分析：目的是从解决同一个问题的不同算法中选择比较适合的一种，或者对原始算法进行改造、加工、使其优化 8.渐进算法分析 a．大Ο分析法：上限，表明最坏情况 b．Ω分析法：下限，表明最好情况 c．Θ分析法：当上限和下限相同时，表明平均情况 第二章线性表 1.线性结构的基本特征 a.集合中必存在唯一的一个“第一元素” b.集合中必存在唯一的一个“最后元素” c.除最后元素之外，均有唯一的后继 d.除第一元素之外，均有唯一的前驱 2.线性结构的基本特点:均匀性、有序性 3.顺序表 a.主要特性：元素的类型相同；元素顺序地存储在连续存储空间中，每一个元素唯一的索引值；使用常数作为向量长度 b. 线性表中任意元素的存储位置：Loc(ki) = Loc(k0) + i * L（设每个元素需占用L个存储单元） c. 线性表的优缺点： 优点：逻辑结构与存储结构一致；属于随机存取方式，即查找每个元素所花时间基本一样 缺点：空间难以扩充 d.检索：ASL=【Ο（1）】 e.插入：插入前检查是否满了，插入时插入处后的表需要复制【Ο（n）】 f.删除：删除前检查是否是空的，删除时直接覆盖就行了【Ο（n）】 4.链表 4.1单链表 a.特点：逻辑顺序与物理顺序有可能不一致；属于顺序存取的存储结构，即存取每个数据元素所花费的时间不相等 b.带头结点的怎么判定空表：head和tail指向单链表的头结点 c.链表的插入（q->next=p->next; p->next=q;）【Ο（n）】 d.链表的删除（q=p->next; p->next = q->next; delete q;）【Ο（n）】 e.不足：next仅指向后继，不能有效找到前驱 4.2双链表 a.增加前驱指针，弥补单链表的不足 b.带头结点的怎么判定空表:head和tail指向单链表的头结点 c.插入：（q->next = p->next; q->prev = p; p->next = q; q->next->prev = q;） d.删除：（p->prev->next = p->next; p->next->prev = p->prev; p->prev = p->next = NULL; delete p;） 4.3顺序表和链表的比较 4.3.1主要优点 a.顺序表的主要优点 没用使用指针，不用花费附加开销；线性表元素的读访问非常简洁便利 b.链表的主要优点 无需事先了解线性表的长度；允许线性表的长度有很大变化；能够适应经常插入删除内部元素的情况 4.3.2应用场合的选择 a.不宜使用顺序表的场合 经常插入删除时，不宜使用顺序表；线性表的最大长度也是一个重要因素 b.不宜使用链表的场合 当不经常插入删除时，不应选择链表；当指针的存储开销与整个结点内容所占空间相比其比例较大时，应该慎重选择 第三章栈与队列 1.栈 a.栈是一种限定仅在一端进行插入和删除操作的线性表；其特点后进先出；插入：入栈（压栈）；删除：出栈（退栈）；插入、删除一端被称为栈顶（浮动），另一端称为栈底（固定）；实现分为顺序栈和链式栈两种 b.应用： 1）数制转换 while (N) { N%8入栈； N=N/8;} while (栈非空){ 出栈； 输出；} 2）括号匹配检验 不匹配情况：各类括号数量不同；嵌套关系不正确 算法： 逐一处理表达式中的每个字符ch： ch=非括号：不做任何处理 ch=左括号：入栈 ch=右括号：if (栈空) return false else { 出栈，检查匹配情况， if (不匹配) return false } 如果结束后，栈非空，返回false 3）表达式求值 3.1中缀表达式： 计算规则：先括号内，再括号外；同层按照优先级，即先乘*、除/,后加+、减-；相同优先级依据结合律，左结合律即为先左后右 3.2后缀表达式： <表达式> ::= <项><项> + | <项><项>－|<项> <项> ::= <因子><因子> * |<因子><因子>/|<因子> <因子> ::= <常数> ?<常数> ::= <数字>|<数字><常数> <数字> ∷= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 3.3中缀表达式转换为后缀表达式 InfixExp为中缀表达式，PostfixExp为后缀表 达式 初始化操作数栈OP，运算符栈OPND； OPND.push('#'); 读取InfixExp表达式的一项 操作数：直接输出到PostfixExp中； 操作符： 当‘（’：入OPND; 当‘）’：OPND此时若空，则出错；OPND若 非空，栈中元素依次弹出，输入PostfixExpz 中，直到遇到‘（’为止；若为‘（’，弹出即 可 当‘四则运算符’：循环（当栈非空且栈顶不是 ‘（’&& 当前运算符优先级>栈顶运算符优先 级），反复弹出栈顶运算符并输入到 PostfixExp中，再将当前运算符压入栈 3.4后缀表达式求值 初始化操作数栈OP； while （表达式没有处理完) { item = 读取表达式一项; 操作数：入栈OP； 运算符：退出两个操作数， 计算，并将结果入栈} c.递归使用的场合：定义是递归的；数据结构是 递归的；解决问题的方法是递归的 2.队列 a.若线性表的插入操作在一端进行，删除操作 在另一端进行，则称此线性表为队列 b.循环队列判断队满对空： 队空：front==rear；队满： (rear+1)%n==front 第五章二叉树 1.概念 a. 一个结点的子树的个数称为度数 b.二叉树的高度定义为二叉树中层数最大的叶 结点的层数加1 c.二叉树的深度定义为二叉树中层数最大的叶 结点的层数 d.如果一棵二叉树的任何结点，或者是树叶， 或者恰有两棵非空子树，则此二叉树称作满二 叉树 e.如果一颗二叉树最多只有最下面的两层结点 度数可以小于2；最下面一层的结点都集中在 该层最左边的位置上，则称此二叉树为完全二 叉树 f.当二叉树里出现空的子树时，就增加新的、特 殊的结点——空树叶组成扩充二叉树，扩充二 叉树是满二叉树 外部路径长度E：从扩充的二叉树的根到每个 外部结点（新增的空树叶）的路径长度之和 内部路径长度I：扩充的二叉树中从根到每个内 部结点（原来二叉树结点）的路径长度之和 2.性质 a. 二叉树的第i层（根为第0层，i≥0）最多有 2^i个结点 b. 深度为k的二叉树至多有2k+1-1个结点 c. 任何一颗二叉树，度为0的结点比度为2的 结点多一个。n0 = n2 + 1 d. 满二叉树定理：非空满二叉树树叶数等于其 分支结点数加1 e. 满二叉树定理推论：一个非空二叉树的空子 树(指针)数目等于其结点数加1 f. 有n个结点（n>0）的完全二叉树的高度为 ?log2(n+1)?，深度为?log2(n+1)?? g. 对于具有n个结点的完全二叉树，结点按层 次由左到右编号，则有： 1) 如果i = 0为根结点；如果i>0，其父结点 编号是(i-1)/2 2) 当2i+1数据结构复习题总结
期末考试总结大全
期末考试总结作文
(完整版)非常实用的数据结构知识点总结
数据结构期末考试复习总结,DOC
期末考试总结作文600字
数据结构复习要点(整理版).docx
《数据结构》期末考试题带答案(99%能过)
数据结构复习提纲(整理)
期末考试总结作文「推荐」
2021年自考02331数据结构重点总结最终修订
数据结构期末复习总结超详细1
期中考试分析总结日记
期末考试总结作文550字
大学数据结构期末知识点重点总结
相关主题
文本预览