大学数据结构测试卷
“广州牛杂批发”通过精心收集，向本站投稿了8篇大学数据结构测试卷，以下是小编整理后的大学数据结构测试卷，希望你喜欢，也可以帮助到您，欢迎分享！
篇1：大学数据结构测试卷
大学数据结构测试卷
一、选择题
1. 下面关于算法说法错误的是（ ） A．算法最终必须由计算机程序实现
B.为解决某问题的算法同为该问题编写的程序含义是相同的
C. 算法的可行性是指指令不能有二义性 D. 以上几个都是错误的
2. 下述哪一条是顺序存储结构的优点？（ A．插入运算方便 B．存储密度大 C．删除运算方便
D．可方便地用于各种逻辑结构的存储表示
3. 线性表是具有n个（ ）的有限序列（n>0）。
A．表元素 B．字符 C．数据项 D. 数据元素
4. 若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ ）存储方式最节省时间。
A．顺序表 B．双链表 C．带头结点的双循环链表 D．单循环链表 5. 下列排序算法中，在每一趟都能选出一个元素放到其最终位置上，并且其时间性能受数据初始特性影响的是：（ ）
A. 直接插入排序 B. 快速排序 C. 直接选择排序 D. 堆排序 6. 输入序列为ABC，可以变为CBA时，经过的栈操作为（ ）
A. push,pop,push,pop,push,pop B. push,push,push,pop,pop,pop C. push,push,pop,pop,push,pop D. push,pop,push,push,pop,pop 7. 设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为（ ）
A．求子串 B．联接 C．匹配 D．求串长
8. 二叉树的先序遍历和中序遍历如下： 先序遍历：EFHIGJK；中序遍历: HFIEJKG 。该二叉树根的右子树的根是： （ ）
A、E B、F C、G D、H
9. 对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为（ ） A．O(n) O(n) B. O(n) O(1) C. O(1) O(n) D. O(1) O(1) 10. 已知一算术表达式的中缀形式为 A+B*C-D/E，后缀形式为ABC*+DE/-，其前缀形式为( )
A．-A+B*C/DE B. -A+B*CD/E C．-+*ABC/DE D. -+A*BC/DE
A,并已0右孩子的'平衡因子为1,则应作（ ）型调整以使4，其中度为1，2，3和4的结点个数分别为4，2，1，1 则T中 ）
．6 C．7 D．8 D ） ．3 C．4 D．
14. 设如左图所示，在下面的5个序列中，符合深度优先遍历的序列有多少？（ ）
a e b d f c a c f d e b
a e d f c b a e f d c b a e f d b c
A．5个 B．4个 C．3个 D．2个
二、填空题
1. 在下面的程序段中，对x的赋值语句的频度为 _ _（表示为n的函数） For(i=1;i<=n;i++)
For(j=1;j<=i;j++) X+=3;
2. 循环队列的引入，目的是为了克服 ____________ ____ 3. 一个栈的输入序列是：1，2，3则不可能的栈输出序列是_______________ 4. 如果结点A有 3个兄弟，而且B是A的双亲，则B的度是_______________。 5. 当使用监视哨顺序查找n个元素的顺序表时，若查找失败，则比较关键字的次数为________________
6. 设一棵完全二叉树具有1000个结点，则它有________个叶子结点，有________个度为2的结点。
7. N个顶点的连通图的生成树含有 _条边
8. 已知一无向图G=（V，E），其中V={a,b,c,d,e } E={(a,b),(a,d),(a,c),(d,c),(b,e)}现用某一种图遍历方法从顶点a开始遍历图，得到的序列为abecd，则采用的是_______________遍历方法
9.分别采用堆排序，快速排序，冒泡排序和归并排序，对初态为有序的表，则最省时间的是 ___算法，最费时间的是 ____算法。 10.若不考虑基数排序，则在排序过程中，主要进行的两种基本操作是关键字的 _______和记录的 ____ 。
三、应用题
1.考查树和二叉树的应用（本题8分）
2.考查图的方面的应用（本题8分）
3.考查查找方面的应用（本题8分）
四、计算题
1.考查排序方面的应用
2.考查哈希表的应用（本题8分）
五、算法设计题
考查栈、树和二叉树、查找和排序的算法设计与填空。
篇2：数据结构实验报告
一、实验目的及要求
1)掌握栈和队列这两种特殊的线性表，熟悉它们的特性，在实际问题背景下灵活运用它们。
本实验训练的要点是“栈”和“队列”的观点;
二、实验内容
1) 利用栈，实现数制转换。
2) 利用栈，实现任一个表达式中的语法检查(选做)。
3) 编程实现队列在两种存储结构中的基本操作(队列的初始化、判队列空、入队列、出队列);
三、实验流程、操作步骤或核心代码、算法片段
顺序栈：
Status InitStack(SqStack &S)
{
S.base=(ElemType*)malloc(STACK_INIT_SIZE*sizeof(ElemType));
if(!S.base)
return ERROR;
S.top=S.base;
S.stacksize=STACK_INIT_SIZE;
return OK;
}
Status DestoryStack(SqStack &S)
{
free(S.base);
return OK;
}
Status ClearStack(SqStack &S)
{
S.top=S.base;
return OK;
}
Status StackEmpty(SqStack S)
{
if(S.base==S.top)
return OK;
return ERROR;
}
int StackLength(SqStack S)
{
return S.top-S.base;
}
Status GetTop(SqStack S,ElemType &e)
{
if(S.top-S.base>=S.stacksize)
{
S.base=(ElemType *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(ElemType));
if(!S.base) return ERROR;
S.top=S.base+S.stacksize;
S.stacksize+=STACKINCREMENT;
}
*S.top++=e;
return OK;
}
Status Push(SqStack &S,ElemType e)
{
if(S.top-S.base>=S.stacksize)
{
S.base=(ElemType *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(ElemType));
if(!S.base)
return ERROR;
S.top=S.base+S.stacksize;
S.stacksize+=STACKINCREMENT;
}
*S.top++=e;
return OK;
}
Status Pop(SqStack &S,ElemType &e)
{
if(S.top==S.base)
return ERROR;
e=*--S.top;
return OK;
}
Status StackTraverse(SqStack S)
{
ElemType *p;
p=(ElemType *)malloc(sizeof(ElemType));
if(!p) return ERROR;
p=S.top;
while(p!=S.base)//S.top上面一个...
{
p--;
printf(“%d ”,*p);
}
return OK;
}
Status Compare(SqStack &S)
{
int flag,TURE=OK,FALSE=ERROR;
ElemType e,x;
InitStack(S);
flag=OK;
printf(“请输入要进栈或出栈的元素：”);
while((x= getchar)!='#'&&flag)
{
switch (x)
{
case '(':
case '[':
case '{':
if(Push(S,x)==OK)
printf(“括号匹配成功!\n\n”);
break;
case ')':
if(Pop(S,e)==ERROR || e!='(')
{
printf(“没有满足条件\n”);
flag=FALSE;
}
break;
case ']':
if ( Pop(S,e)==ERROR || e!='[')
flag=FALSE;
break;
case '}':
if ( Pop(S,e)==ERROR || e!='{')
flag=FALSE;
break;
}
}
if (flag && x=='#' && StackEmpty(S))
return OK;
else
return ERROR;
}
链队列：
Status InitQueue(LinkQueue &Q)
{
Q.front =Q.rear=
(QueuePtr)malloc(sizeof(QNode));
if (!Q.front) return ERROR;
Q.front->next = NULL;
return OK;
}
Status DestoryQueue(LinkQueue &Q)
{
while(Q.front)
{
Q.rear=Q.front->next;
free(Q.front);
Q.front=Q.rear;
}
return OK;
}
Status QueueEmpty(LinkQueue &Q)
{
if(Q.front->next==NULL)
return OK;
return ERROR;
}
Status QueueLength(LinkQueue Q)
{
int i=0;
QueuePtr p,q;
p=Q.front;
while(p->next)
{
i++;
p=Q.front;
q=p->next;
p=q;
}
return i;
}
Status GetHead(LinkQueue Q,ElemType &e)
{
QueuePtr p;
p=Q.front->next;
if(!p)
return ERROR;
e=p->data;
return e;
}
Status ClearQueue(LinkQueue &Q)
{
QueuePtr p;
while(Q.front->next )
{
p=Q.front->next;
free(Q.front);
Q.front=p;
}
Q.front->next=NULL;
Q.rear->next=NULL;
return OK;
}
Status EnQueue(LinkQueue &Q,ElemType e)
{
QueuePtr p;
p=(QueuePtr)malloc(sizeof (QNode));
if(!p)
return ERROR;
p->data=e;
p->next=NULL;
Q.rear->next = p;
Q.rear=p; //p->next 为空
return OK;
}
Status DeQueue(LinkQueue &Q,ElemType &e)
{
QueuePtr p;
if (Q.front == Q.rear)
return ERROR;
p = Q.front->next;
e = p->data;
Q.front->next = p->next;
if (Q.rear == p)
Q.rear = Q.front; //只有一个元素时(不存在指向尾指针)
free (p);
return OK;
}
Status QueueTraverse(LinkQueue Q)
{
QueuePtr p,q;
if( QueueEmpty(Q)==OK)
{
printf(“这是一个空队列!\n”);
return ERROR;
}
p=Q.front->next;
while(p)
{
q=p;
printf(“%d<-\n”,q->data);
q=p->next;
p=q;
}
return OK;
}
循环队列：
Status InitQueue(SqQueue &Q)
{
Q.base=(QElemType*)malloc(MAXQSIZE*sizeof(QElemType));
if(!Q.base)
exit(OWERFLOW);
Q.front=Q.rear=0;
return OK;
}
Status EnQueue(SqQueue &Q,QElemType e)
{
if((Q.rear+1)%MAXQSIZE==Q.front)
return ERROR;
Q.base[Q.rear]=e;
Q.rear=(Q.rear+1)%MAXQSIZE;
return OK;
}
Status DeQueue(SqQueue &Q,QElemType &e)
{
if(Q.front==Q.rear)
return ERROR;
e=Q.base[Q.front];
Q.front=(Q.front+1)%MAXQSIZE;
return OK;
}
int QueueLength(SqQueue Q)
{
return(Q.rear-Q.front+MAXQSIZE)%MAXQSIZE;
}
Status DestoryQueue(SqQueue &Q)
{
free(Q.base);
return OK;
}
Status QueueEmpty(SqQueue Q) //判空
{
if(Q.front ==Q.rear)
return OK;
return ERROR;
}
Status QueueTraverse(SqQueue Q)
{
if(Q.front==Q.rear)
printf(“这是一个空队列!”);
while(Q.front%MAXQSIZE!=Q.rear)
{
printf(“%d<- ”,Q.base[Q.front]);
Q.front++;
}
return OK;
}
篇3：数据结构实验报告
一.实验内容：
实现哈夫曼编码的生成算法。
二.实验目的：
1、使学生熟练掌握哈夫曼树的生成算法。
2、熟练掌握哈夫曼编码的方法。
三.问题描述：
已知n个字符在原文中出现的频率，求它们的哈夫曼编码。
1、读入n个字符，以及字符的权值，试建立一棵Huffman树。
2、根据生成的Huffman树，求每个字符的Huffman编码。并对给定的待编码字符序列进行编码，并输出。
四.问题的实现
(1)郝夫曼树的存储表示
typedef struct{
unsigned int weight;
unsigned int parent,lchild,rchild;
}HTNode,*HuffmanTree; //动态分配数组存储郝夫曼树
郝夫曼编码的存储表示
typedef char* *HuffmanCode;//动态分配数组存储郝夫曼编码
(2)主要的实现思路：
a.首先定义郝夫曼树的存储形式，这里使用了数组
b.用select遍历n个字符，找出权值最小的两个
c.构造郝夫曼树HT，并求出n个字符的郝夫曼编码HC
总结
1.基本上没有什么太大的问题，在调用select这个函数时，想把权值最小的两个结点的序号带回HuffmanCoding，所以把那2个序号设置成了引用。
2.在编程过程中，在什么时候分配内存，什么时候初始化花的时间比较长
3.最后基本上实现后，发现结果仍然存在问题，经过分步调试，发现了特别低级的输入错误。把HT[i].weight=HT[s1].weight+HT[s2].weight;中的s2写成了i
附：
//动态分配数组存储郝夫曼树
typedef struct{
int weight; //字符的权值
int parent,lchild,rchild;
}HTNode,*HuffmanTree;
//动态分配数组存储郝夫曼编码
typedef char* *HuffmanCode;
//选择n个(这里是k=n)节点中权值最小的两个结点
void Select(HuffmanTree &HT,int k,int &s1,int &s2)
{ int i;
i=1;
while(i<=k && HT[i].parent!=0)i++;
//下面选出权值最小的结点，用s1指向其序号
s1=i;
for(i=1;i<=k;i++)
{
if(HT[i].parent==0&&HT[i].weight
}
//下面选出权值次小的结点，用s2指向其序号
for(i=1;i<=k;i++)
{
if(HT[i].parent==0&&i!=s1)break;
}
s2=i;
for(i=1;i<=k;i++)
{
if(HT[i].parent==0&&i!=s1&&HT[i].weight
}
}
//构造Huffman树，求出n个字符的编码
void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n)
{
int m,c,f,s1,s2,i,start;
char *cd;
if(n<=1)return;
m=2*n-1; //n个叶子n-1个结点
HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); //0号单元未用，预分配m+1个单元
HuffmanTree p=HT+1;
w++; //w的号单元也没有值，所以从号单元开始
for(i=1;i<=n;i++,p++,w++)
{
p->weight=*w;
p->parent=p->rchild=p->lchild=0;
}
for(;i<=m;++i,++p)
{
p->weight=p->parent=p->rchild=p->lchild=0;
}
for(i=n+1;i<=m;i++)
{
Select(HT,i-1,s1,s2); //选出当前权值最小的
HT[s1].parent=i;
HT[s2].parent=i;
HT[i].lchild=s1;
HT[i].rchild=s2;
HT[i].weight=HT[s1].weight+HT[s2].weight;
}
//从叶子到根逆向求每个字符的郝夫曼编码
HC=(HuffmanCode)malloc((n+1)*sizeof(char*)); //分配n个字符编码的头指针变量
cd=(char*)malloc(n*sizeof(char)); //分配求编码的工作空间
cd[n-1]='\0';//编码结束符
for(i=1;i<=n;i++) //逐个字符求郝夫曼编码
{
start=n-1; //编码结束符位置
for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent) //从叶子到根逆向求编码
{
if(HT[f].lchild==c)cd[--start]='0';
else
cd[--start]='1';
}
HC[i]=(char*)malloc((n-start)*sizeof(char)); //为第i个字符编码分配空间
strcpy(HC[i],&cd[start]);//从cd复制编码到HC
}
free(cd); //释放工作空间
}
void main
{ int n,i;
int* w; //记录权值
char* ch; //记录字符
HuffmanTree HT;
HuffmanCode HC;
cout<<“请输入待编码的字符个数n=”;
cin>>n;
w=(int*)malloc((n+1)*sizeof(int)); //记录权值，号单元未用
ch=(char*)malloc((n+1)*sizeof(char));//记录字符，号单元未用
cout<<“依次输入待编码的字符data及其权值weight”<
for(i=1;i<=n;i++)
{
cout<<“data[”<
}
篇4：数据结构试题答案
数据结构试题答案
一、单项选择题（每题2分，共30分）
1.若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用（ ）存储方式最节省时间。
A) 单链表 B) 双链表 C) 单向循环链表 D) 顺序表
2.串是任意有限个（ ）。
A) 符号构成的序列 B) 符号构成的集合
C) 字符构成的序列 D) 字符构成的集合
3.设矩阵A的任一元素aij(1≤i,j≤10)满足：
aij≠0；(i≥j,1≤i,j≤10)
aij=0； (i 现将A的所有非0元素以行序为主序存放在首地址为的存储区域中，每个元素占有4个单元，则元素A[9,5]的首地址为（ ）。 A) 2340 B) 2336 C) 2164 D) 2160 4.如果以链表作为栈的存储结果，则出栈操作时（ ）。 A) 必须判别栈是否为满 B) 对栈不作任何判别 C) 必须判别栈是否为空 D) 判别栈元素的类型 5.设数组Data[0..m]作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针,则执行出队操作的语句为（ ）。 A) front = front+1 B) front = (front+1) % m C) rear = (rear+1) % m D) front = (front+1) % (m+1) 6.深度为6(根的层次为1)的二叉树至多有（ ）结点。 A) 64 B) 32 C) 31 D) 63 7.将含100个结点的完全二叉树从根这一层开始，每层上从左到右依次堆结点编号，根结点的编号为1。编号为49的结点X的双亲的编号为（ ）。 A) 24 B) 25 C) 23 D) 无法确定 8.设有一个无向图 和 ，如果 为 的生成树，则下面不正确的说法是（ ）。 A) 为 的子图 B) 为 的连通分量 C) 为 的极小连通子图且 D) 为 的一个无环子图 9.用线性探测法查找闭散列表，可能要探测多个散列地址，这些位置上的键值（ ）。 A) 一定都是同义词 B) 一定都不是同义词 C) 多相同 D) 不一定都是同义词 10.二分查找要求被查找的表是（ ）。 A) 键值有序的链接表 B) 链接表但键值不一定有序 C) 键值有序的顺序表 D) 顺序表但键值不一定有序 11.当初始序列已经按键值有序，用直接插入算法对其进行排序，需要循环的次数为（ ）。 A) B) C) D) n－1 12.堆是一个键值序列 ,对 ，满足（ ）。 A) B) C) 且 ( ) D) 或 ( ) 13.使用双向链表存储数据，其优点是可以（ ）。 A) 提高检索速度 B) 很方便地插入和删除数据 C) 节约存储空间 D) 很快回收存储空间 14.设计一个判别表达式中左右括号是否配对出现地算法，采用（ ）数据结构最佳。 A) 线性表地顺序存储结构 B) 栈 C) 队列 D) 线性表达的链式存储结构 15.设深度为k的二叉树上只有度为0和2的结点，则此类二叉树中所含的结点数至少为（ ）。 A) k + 1 B) 2k C) 2k - 1 D) 2k + 1 二、填空题（每空2分，共28分） 1.设r指向单链表的最后一个结点，要在最后一个结点之后插入s所指的结点，需执行的三条语句是_____________________________________________r=s;r->next=NULL。 2.在单链表中，指针p所指结点为最后一个结点的条件是___________________。 3.设一个链栈的栈顶指针是ls，栈中结点格式为 ，栈空的条件为_____________。如果栈不为空，则出栈操作为p=ls;______________;free(p)。 4.已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的'结点，则该树有________个叶子结点。 5.树有三种常用的存储结构，即孩子链表法，孩子兄弟链表法和____________。 6.n个顶点的连通图的生成树有__________条边。 7.一个有向图G中若有弧 、和 ，则在图G的拓扑序列中，顶点 的相对位置为___________。 8.设表中元素的初始状态是按键值递增的，分别用堆排序、快速排序、冒泡排序和归并排序方法对其进行排序(按递增顺序)，________最省时间，__________最费时间。 9.下面是将键值为x的结点插入到二叉排序树中的算法，请在划线处填上适当的内容。 Typedef struct pnode { int key; struct node * left, * right; } Void search (int x; pnode t ) { if (_____________) {p = malloc (size); p->key=x;p->left=NULL; p->right=NULL; t=p; } else if (xkey) search (x,t->left) else _________________ } 10.线性表的____________的主要优点是从表中任意结点出发都能访问到所有结点。而使用____________，可根据需要在前后两个方向上方便地进行查找。 三、应用题（每题10分，共30分） 1.在双链表中，要在指针变量P所指结点之后插入一个新结点，请按顺序写出必要的算法步骤。(设：P所指结点不是链表的首尾结点，q是与p同类型的指针变量) 2.已知待排序文件各记录的排序码顺序如下： 72 73 71 23 94 16 05 68 请列出快速排序过程中每一趟的排序结果。 四、算法题(共12分) 编写算法，实现单链表上的逆置运算(说明：即将单链表中的元素次序反转) 参考答案： 一、单项选择题（每题2分，共30分） 1.D 2.C 3.D 4.C 5.D 6.D 7.A 8.B 9.D 10.C 11.D 12.C 13.A 14.B 15.C 二、填空题（每空2分，共28分） 1. r->next=s; 2. p->next=NULL; 3. ls = = NULL; ls=ls->link。 4. 12 5. 双亲表示法 6. n-1 7. i,j,k 8. 冒泡排序，快速排序 9. t= =NULL，search（x,t->right）； 10.循环链表，双向链表 三、应用题（每题10分，共30分） 1．new(q)； q↑.llink ← p； q↑.rlink ← p↑.rlink； p↑.rlink↑.llink ← q； p↑.rlink ← q。 评分细则：按顺序每对一个给2分，全对计10分。 2．各趟结果如下： [68 05 71 23 16] 72 [94 73] [16 05 23] 68 [71] 72 [94 73] [05] 16 [23] 68 [71] 72 [94 73] 05 16 [23] 68 [71] 72 [94 73] 05 16 23 68 71 72 [94 73] 05 16 23 68 71 72 [73] 94 05 16 23 68 71 72 73 94 四．算法题(共12分) void invert（ pointer head） {p=NULL; while ( headNULL) {u=head; head=head->next; u->next=p; p=u; } head=p; } 目前所在： 天河区 年 龄： 20 户口所在： 汕头 国 籍： 中国 婚姻状况： 未婚 民 族： 汉族 诚信徽章： 未申请 身 高： 157 cm 人才测评： 未测评 体 重： 人才类型： 在校学生 应聘职位： 幼教/保育员， 家教， 销售主管/销售代表/客户代表 工作年限： 1 职 称： 求职类型： 兼职 可到职日期： 随时 月薪要求： 面议 希望工作地区： 天河区,越秀区,广州 工作经历 无 起止年月：-10 ～ -05 公司性质： 所属行业： 担任职位： 作业指导 工作描述： 辅导小学生作业，照顾小学生 广州地铁 起止年月：2012-04 ～ 2012-05 担任职位： 地铁志愿者 工作描述： 毕业院校： 广东交通职业技术学院 最高学历： 大专 获得学位: 毕业日期： -06 专 业 一： 软件技术 专 业 二： 起始年月 终止年月 学校（机构） 所学专业 获得证书 证书编号 语言能力 外语： 英语 良好 粤语水平： 一般 其它外语能力： 国语水平： 优秀 工作能力及其他专长 熟悉计算机办公软件操作、C语言，数据结构，数据库原理，汇编语言，软件工程等Windows编程、网页制作 个人自传 性格开朗，成绩优良,乐于助人；善于与人交流、适应能力强、具有团体协作精神；喜欢运动 1.判断链表是否存在环型链表问题：判断一个链表是否存在环，例如下面这个链表就存在一个环： 例如N1->N2->N3->N4->N5->N2就是一个有环的链表，环的开始结点是N5这里有一个比较简单的解法，设置两个指针p1，p2。每次循环p1向前走一步，p2向前走两步。直到p2碰到NULL指针或者两个指针相等结束循环。如果两个指针相等则说明存在环。 struct link { int data; link* next; }; bool IsLoop(link* head) { link* p1=head, *p2 = head; if (head ==NULL || head->next ==NULL) { return false; } do{ p1= p1->next; p2 = p2->next->next; } while(p2 && p2->next && p1!=p2); if(p1 == p2) return true; else return false; } 2,链表反转 单向链表的反转是一个经常被问到的一个面试题，也是一个非常基础的问题。比如一个链表是这样的： 1->2->3->4->5 通过反转后成为5->4->3->2->1。最容易想到的方法遍历一遍链表，利用一个辅助指针，存储遍历过程中当前指针指向的下一个元素，然后将当前节点元素的指针反转后，利用已经存储的指针往后面继续遍历。源代码如下： struct linka { int data; linka* next; }; void reverse(linka*& head) { if(head ==NULL) return; linka*pre, *cur, *ne; pre=head; cur=head->next; while(cur) { ne = cur->next; cur->next = pre; pre = cur; cur = ne; } head->next = NULL; head = pre; } 还有一种利用递归的方法。这种方法的基本思想是在反转当前节点之前先调用递归函数反转后续节点。源代码如下。不过这个方法有一个缺点，就是在反转后的最后一个结点会形成一个环，所以必须将函数的返回的节点的next域置为NULL。因为要改变head指针，所以我用了引用。算法的源代码如下： linka* reverse(linka* p,linka*& head) { if(p == NULL || p->next == NULL) { head=p; return p; } else { linka* tmp = reverse(p->next,head); tmp->next = p; return p; } } 3,判断两个数组中是否存在相同的数字 给定两个排好序的数组，怎样高效得判断这两个数组中存在相同的数字？ 这个问题首先想到的是一个O(nlogn)的算法。就是任意挑选一个数组，遍历这个数组的所有元素，遍历过程中，在另一个数组中对第一个数组中的每个元素进行binary search。用C++实现代码如下： bool findcommon(int a[],int size1,int b[],int size2) { int i; for(i=0;i { int start=0,end=size2-1,mid; while(start<=end) { mid=(start+end)/2; if(a[i]==b[mid]) return true; else if (a[i] end=mid-1; else start=mid+1; } } return false; } 后来发现有一个 O(n)算法， 因为两个数组都是排好序的。所以只要一次遍历就行了。首先设两个下标，分别初始化为两个数组的起始地址，依次向前推进。推进的规则是比较两个数组中的数字，小的那个数组的下标向前推进一步，直到任何一个数组的下标到达数组末尾时，如果这时还没碰到相同的数字，说明数组中没有相同的数字。 bool findcommon2(int a[], int size1, int b[], int size2) { int i=0,j=0; while(i { if(a[i]==b[j]) return true; if(a[i]>b[j]) j++; if(a[i] i++; } return false; } 4,最大子序列 问题： 给定一整数序列A1， A2，... An （可能有负数），求A1~An的一个子序列Ai~Aj，使得Ai到Aj的和最大 例如： 整数序列-2, 11, -4, 13, -5, 2, -5, -3, 12, -9的最大子序列的和为21。 对于这个问题，最简单也是最容易想到的那就是穷举所有子序列的方法。利用三重循环，依次求出所有子序列的和然后取最大的那个。当然算法复杂度会达到O(n^3)。显然这种方法不是最优的，下面给出一个算法复杂度为O(n)的线性算法实现，算法的来源于Programming Pearls一书。 在给出线性算法之前，先来看一个对穷举算法进行优化的算法，它的算法复杂度为O(n^2)。其实这个算法只是对对穷举算法稍微做了一些修改：其实子序列的和我们并不需要每次都重新计算一遍。假设Sum(i, j)是A[i] ... A[j]的和，那么Sum(i, j+1) = Sum(i, j) + A[j+1]。利用这一个递推，我们就可以得到下面这个算法： int max_sub(int a[],int size) { int i,j,v,max=a[0]; for(i=0;i { v=0; for(j=i;j { v=v+a[j];//Sum(i, j+1) = Sum(i, j) + A[j+1] if(v>max) max=v; } } return max; } 那怎样才能达到线性复杂度呢？这里运用动态规划的思想。先看一下源代码实现： int max_sub2(int a[], int size) { int i,max=0,temp_sum=0; for(i=0;i { temp_sum+=a[i]; if(temp_sum>max) max=temp_sum; else if(temp_sum<0) temp_sum=0; } return max; } 在这一遍扫描数组当中，从左到右记录当前子序列的和temp_sum，若这个和不断增加，那么最大子序列的和max也不断增加(不断更新max)。如果往前扫描中遇到负数，那么当前子序列的和将会减小。此时temp_sum 将会小于max，当然max也就不更新。如果temp_sum降到0时，说明前面已经扫描的那一段就可以抛弃了，这时将temp_sum置为0。然后，temp_sum将从后面开始将这个子段进行分析，若有比当前max大的子段，继续更新max。这样一趟扫描结果也就出来了。 5, 找出单向链表的中间结点 这道题和解判断链表是否存在环，我用的是非常类似的方法，只不过结束循环的条件和函数返回值不一样罢了。设置两个指针p1，p2。每次循环p1向前走一步，p2向前走两步。当p2到达链表的末尾时，p1指向的时链表的中间。 link* mid(link* head) { link* p1,*p2; p1=p2=head; if(head==NULL || head->next==NULL) return head; do { p1=p1->next; p2=p2->next->next; } while(p2 && p2->next); return p1; } 来自：akalius.javaeye.com/blog/163319 浅谈《数据结构》教学 <数据结构>是高等院校计算机专业的一门重要专业基础课程,要求会分析和理解加工的数据对象特性,选择适当的.数据结构和存储结构及算法.要讲好这门课,可以从学生的听课率、课程的基础、重点和难点方面考虑,另外,师生之间的互动非常重要,最后要加强实践环节.篇5：数据结构简历
篇6：数据结构面试
篇7：浅谈《数据结构》教学
篇8：怎么学好数据结构
怎么学好数据结构
首先你要知道什么是数据结构，学习数据结构的意义。这将是你学习的动力所在。计算机软件都用到了数据结构。所以，学好数据结构对于你将来从事计算机编程类的工作有十分重要的作用。
数据结构中的基本概念，你要一定清楚。平时要多看书，要在计算机上去调试程序，在调试的过程中，你才能发现自己的问题，然后及时解决。在上机调试的过程中，更要大胆尝试，注重运用。拿到一个题时，更要深入分析，尝试用不同的算法去设计。当然编程的时候，要注意格式。比如：变量一定要先定义后使用。变量的定义不要定义在中间。
算法与数据结构是紧密联系，所以你算法一定要会。如果你是学生，只需把课本上出现的搞懂就好了，比如线性表的插入，删除，查找算法，它都是固定的。你就要理解，当然你要学会画图。对于书中的内容要熟悉。
数据结构的大纲如下：线性表、栈和队列，串、数组和广义表、树与森林、图、还有就是查找和排序。简单的总结一下也就是它的逻辑结构：线性结构和非线性结构。这些基本的内容你如果搞懂了，你的数据结构也就学好了。
要严格要求自己。在学习算法的过程中，你要想它为什么要这样设计?它的优点在哪里?想着去改进算法，慢慢的的你的逻辑思维能力也就提高了。你会发现其实数据结构也就那么回事，不是很难。
有不懂得地方要及时请教老师，不要不懂装懂。不要放过任何一个细节，因为我的专业就是计算机，所以有很多都是深有体会。
注意：
一、认真安排好你的时间
首先你要清楚一周内所要做的事情，然后制定一张作息时间表。在表上填上那些非花不可的时间，如吃饭、睡觉、上课、娱乐等。安排这些时间之后，选定合适的、固定的时间用于学习，必须留出足够的时间来完成正常的阅读和课后作业。当然，学习不应该占据作息时间表上全部的空闲时间，总得给休息、业余爱好、娱乐留出一些时间，这一点对学习很重要。一张作息时间表也许不能解决你所有的问题，但是它能让你了解如何支配你这一周的时间，从而使你有充足的时间学习和娱乐。
二、学习前先预习
这就意味着在你认真投入学习之前，先把要学习的内容快速浏览一遍，了解学习的大致内容及结构，以便能及时理解和消化学习内容。当然，你要注意轻重详略，在不太重要的地方你可以花少点时间，在重要的地方，你可以稍微放慢学习进程。
三、充分利用课堂时间
学习成绩好的学生很大程度上得益于在课堂上充分利用时间，这也意味着在课后少花些功夫。课堂上要及时配合老师，做好笔记来帮助自己记住老师讲授的内容，尤其重要的是要积极地独立思考，跟得上老师的思维。
四、学习要有合理的规律
课堂上做的笔记你要在课后及时复习，不仅要复习老师在课堂上讲授的重要内容，还要复习那些你仍感模糊的认识。如果你坚持定期复习笔记和课本，并做一些相关的习题，你定能更深刻地理解这些内容，你的记忆也会保持更久。定期复习能有效地提高你的考试成绩。
五、一个安静的、舒适的学习环境
选择某个地方作你的学习之处，这一点很重要。它可以是你的单间书房或教室或图书馆，但是它必须是舒适的，安静而没有干扰。当你开始学习时，你应该全神贯注于你的功课，切忌“身在曹营心在汉”。
六、树立正确的考试观
平时测验的目的主要看你掌握功课程度如何，所以你不要弄虚作假，而应心平气和地对待它。或许，你有一两次考试成绩不尽如人意，但是这不要紧，只要学习扎实，认真对待，下一次一定会考出好成绩来。通过测验，可让你了解下一步学习更需要用功夫的地方，更有助于你把新学的知识记得牢固。
【大学数据结构测试卷】相关文章：
1.数据结构实验报告
2.数据结构面试
3.数据结构试卷
6.九年语文测试卷
7.一年级拼音测试卷
8.六年级单元测试卷
10.语文下册期末测试卷
文档为doc格式
