数据结构试卷
“小鹿想念书”通过精心收集，向本站投稿了10篇数据结构试卷，这里小编给大家分享一些数据结构试卷，方便大家学习。
篇1：数据结构实验报告
一、实验目的及要求
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(“括号匹配成功!nn”);
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;
}
篇2：数据结构实验报告
一.实验内容：
实现哈夫曼编码的生成算法。
二.实验目的：
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]=' ';//编码结束符
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[”<
}
篇3：数据结构试题答案
数据结构试题答案
一、单项选择题（每题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 浅谈《数据结构》教学 <数据结构>是高等院校计算机专业的一门重要专业基础课程,要求会分析和理解加工的数据对象特性,选择适当的.数据结构和存储结构及算法.要讲好这门课,可以从学生的听课率、课程的基础、重点和难点方面考虑,另外,师生之间的互动非常重要,最后要加强实践环节.篇4：数据结构简历
篇5：数据结构面试
篇6：浅谈《数据结构》教学
篇7：怎么学好数据结构
怎么学好数据结构
首先你要知道什么是数据结构，学习数据结构的意义。这将是你学习的动力所在。计算机软件都用到了数据结构。所以，学好数据结构对于你将来从事计算机编程类的工作有十分重要的作用。
数据结构中的基本概念，你要一定清楚。平时要多看书，要在计算机上去调试程序，在调试的过程中，你才能发现自己的问题，然后及时解决。在上机调试的过程中，更要大胆尝试，注重运用。拿到一个题时，更要深入分析，尝试用不同的算法去设计。当然编程的时候，要注意格式。比如：变量一定要先定义后使用。变量的定义不要定义在中间。
算法与数据结构是紧密联系，所以你算法一定要会。如果你是学生，只需把课本上出现的搞懂就好了，比如线性表的插入，删除，查找算法，它都是固定的。你就要理解，当然你要学会画图。对于书中的内容要熟悉。
数据结构的大纲如下：线性表、栈和队列，串、数组和广义表、树与森林、图、还有就是查找和排序。简单的总结一下也就是它的逻辑结构：线性结构和非线性结构。这些基本的内容你如果搞懂了，你的数据结构也就学好了。
要严格要求自己。在学习算法的过程中，你要想它为什么要这样设计?它的优点在哪里?想着去改进算法，慢慢的的你的逻辑思维能力也就提高了。你会发现其实数据结构也就那么回事，不是很难。
有不懂得地方要及时请教老师，不要不懂装懂。不要放过任何一个细节，因为我的专业就是计算机，所以有很多都是深有体会。
注意：
一、认真安排好你的时间
首先你要清楚一周内所要做的事情，然后制定一张作息时间表。在表上填上那些非花不可的时间，如吃饭、睡觉、上课、娱乐等。安排这些时间之后，选定合适的、固定的时间用于学习，必须留出足够的时间来完成正常的阅读和课后作业。当然，学习不应该占据作息时间表上全部的空闲时间，总得给休息、业余爱好、娱乐留出一些时间，这一点对学习很重要。一张作息时间表也许不能解决你所有的问题，但是它能让你了解如何支配你这一周的时间，从而使你有充足的时间学习和娱乐。
二、学习前先预习
这就意味着在你认真投入学习之前，先把要学习的内容快速浏览一遍，了解学习的大致内容及结构，以便能及时理解和消化学习内容。当然，你要注意轻重详略，在不太重要的地方你可以花少点时间，在重要的地方，你可以稍微放慢学习进程。
三、充分利用课堂时间
学习成绩好的学生很大程度上得益于在课堂上充分利用时间，这也意味着在课后少花些功夫。课堂上要及时配合老师，做好笔记来帮助自己记住老师讲授的内容，尤其重要的是要积极地独立思考，跟得上老师的思维。
四、学习要有合理的规律
课堂上做的笔记你要在课后及时复习，不仅要复习老师在课堂上讲授的重要内容，还要复习那些你仍感模糊的认识。如果你坚持定期复习笔记和课本，并做一些相关的习题，你定能更深刻地理解这些内容，你的记忆也会保持更久。定期复习能有效地提高你的考试成绩。
五、一个安静的、舒适的学习环境
选择某个地方作你的学习之处，这一点很重要。它可以是你的单间书房或教室或图书馆，但是它必须是舒适的，安静而没有干扰。当你开始学习时，你应该全神贯注于你的功课，切忌“身在曹营心在汉”。
六、树立正确的考试观
平时测验的目的主要看你掌握功课程度如何，所以你不要弄虚作假，而应心平气和地对待它。或许，你有一两次考试成绩不尽如人意，但是这不要紧，只要学习扎实，认真对待，下一次一定会考出好成绩来。通过测验，可让你了解下一步学习更需要用功夫的地方，更有助于你把新学的知识记得牢固。
篇8：数据结构试题
数据结构试题
一、选择题(30分)
1.下列程序段的时间复杂度为( )。
(A) O(m*n*t) (B) O(m+n+t) (C) O(m+n*t) (D) O(m*t+n)
2.设顺序线性表中有n个数据元素，则删除表中第i个元素需要移动( )个元素。
(A) n-i (B) n+l -i (C) n-1-i (D) i
3.设F是由T1、T2和T3三棵树组成的森林，与F对应的二叉树为B，T1、T2和T3的结点数分别为N1、N2和N3，则二叉树B的根结点的左子树的结点数为( )。
(A) N1-1 (B) N2-1 (C) N2+N3 (D) N1+N3
4.利用直接插入排序法的思想建立一个有序线性表的时间复杂度为( )。
(A) O(n) (B) O(nlog2n) (C) O(n2) (D) O(1og2n)
5.设指针变量p指向双向链表中结点A，指针变量s指向插入的结点X，则在结点A的后面插入结点X的操作序列为( )。
(A) p->right=s; s->left=p; p->right->left=s; s->right=p->right;
(B) s->left=p;s->right=p->right;p->right=s; p->right->left=s;
(C) p->right=s; p->right->left=s; s->left=p; s->right=p->right;
(D) s->left=p;s->right=p->right;p->right->left=s; p->right=s;
6.下列各种排序算法中平均时间复杂度为O(n2)是( )。
(A) 快速排序 (B) 堆排序 (C) 归并排序 (D) 冒泡排序
7.设输入序列1、2、3、…、n经过栈作用后，输出序列中的第一个元素是n，则输出序列中的第i个输出元素是( )。
(A) n-i (B) n-1-i (C) n+l -i (D) 不能确定
8.设散列表中有m个存储单元，散列函数H(key)= key % p，则p最好选择( )。
(A) 小于等于m的最大奇数 (B) 小于等于m的最大素数
(C) 小于等于m的最大偶数 (D) 小于等于m的最大合数
9.设在一棵度数为3的树中，度数为3的结点数有2个，度数为2的结点数有1个，度数为1的结点数有2个，那么度数为0的结点数有( )个。
(A) 4 (B) 5 (C) 6 (D) 7
10.设完全无向图中有n个顶点，则该完全无向图中有( )条边。
(A) n(n-1)/2 (B) n(n-1) (C) n(n+1)/2 (D) (n-1)/2
11.设顺序表的长度为n，则顺序查找的平均比较次数为( )。
(A) n (B) n/2 (C) (n+1)/2 (D) (n-1)/2
12.设有序表中的元素为(13，18，24，35，47，50，62)，则在其中利用二分法查找值为24的元素需要经过( )次比较。
(A) 1 (B) 2 (C) 3 (D) 4
13.设顺序线性表的长度为30，分成5块，每块6个元素，如果采用分块查找，则其平均查找长度为( )。
(A) 6 (B) 11 (C) 5 (D) 6.5
14.设有向无环图G中的有向边集合E={<1，2>，<2，3>，<3，4>，<1，4>}，则下列属于该有向图G的一种拓扑排序序列的是( )。
(A) 1，2，3，4 (B) 2，3，4，1 (C) 1，4，2，3 (D) 1，2，4，3
15.设有一组初始记录关键字序列为(34，76，45，18，26，54，92)，则由这组记录关键字生成的二叉排序树的深度为( )。
(A) 4 (B) 5 (C) 6 (D) 7
二、填空题(30分)
1.设指针p指向单链表中结点A，指针s指向插入的结点X，则在结点A的前面插入结点X时的操作序列为：
1) s->next=___________;2) p->next=s;3) t=p->data;
4) p->data=___________;5) s->data=t;
2.设某棵完全二叉树中有100个结点，则该二叉树中有______________个叶子结点。
3.设某顺序循环队列中有m个元素，且规定队头指针F指向队头元素的前一个位置，队尾指针R指向队尾元素的当前位置，则该循环队列中最多存储_______队列元素。
4.对一组初始关键字序列(40，50，95，20，15，70，60，45，10)进行冒泡排序，则第一趟需要进行相邻记录的比较的次数为__________，在整个排序过程中最多需要进行__________趟排序才可以完成。
5.在堆排序和快速排序中，如果从平均情况下排序的速度最快的角度来考虑应最好选择_________排序，如果从节省存储空间的.角度来考虑则最好选择________排序。
6.设一组初始记录关键字序列为(20，12，42，31，18，14，28)，则根据这些记录关键字构造的二叉排序树的平均查找长度是_______________________________。
7.设一棵二叉树的中序遍历序列为BDCA，后序遍历序列为DBAC，则这棵二叉树的前序序列为____________________。
8.设用于通信的电文仅由8个字母组成，字母在电文中出现的频率分别为7、19、2、6、32、3、21、10，根据这些频率作为权值构造哈夫曼树，则这棵哈夫曼树的高度为________________。
9.设一组记录关键字序列为(80，70，33，65，24，56，48)，则用筛选法建成的初始堆为_______________________。
10. 10. 设无向图G(如右图所示)，则其最小生成树上所有边的权值之和为_________________。
三、判断题(20分)
1.有向图的邻接表和逆邻接表中表结点的个数不一定相等。( )
2.对链表进行插入和删除操作时不必移动链表中结点。( )
3.子串“ABC”在主串“AABCABCD”中的位置为2。( )
4.若一个叶子结点是某二叉树的中序遍历序列的最后一个结点，则它必是该二叉树的先序遍历序列中的最后一个结点。( )
5.希尔排序算法的时间复杂度为O(n2)。( )
6.用邻接矩阵作为图的存储结构时，则其所占用的存储空间与图中顶点数无关而与图中边数有关。( )
7.中序遍历一棵二叉排序树可以得到一个有序的序列。( )
8.入栈操作和入队列操作在链式存储结构上实现时不需要考虑栈溢出的情况。( )
9.顺序表查找指的是在顺序存储结构上进行查找。( )
10.堆是完全二叉树，完全二叉树不一定是堆。( )
四、算法设计题(20分)
1.设计计算二叉树中所有结点值之和的算法。
2.设计将所有奇数移到所有偶数之前的算法。
3.设计判断单链表中元素是否是递增的算法。
篇9：数据结构实验报告
数据结构实验报告
数据结构实验报告1
一、实验目的及要求
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(“括号匹配成功!nn”);
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)
篇10：数据结构实验报告
数据结构实验报告范例
篇一：数据结构实验报告范例
《数据结构与算法》实验报告
专业 班级 姓名 学号
实验项目
实验一 二叉树的应用
实验目的
1、进一步掌握指针变量的含义及应用。
2、掌握二叉树的结构特征，以及各种存储结构的`特点及使用范围。
3、掌握用指针类型描述、访问和处理二叉树的运算。
实验内容
题目1:编写一个程序，采用一棵二叉树表示一个家谱关系。要求程序具有如下功能：
（1）用括号表示法输出家谱二叉树，
（2）查找某人的所有儿子，
（3）查找某人的所有祖先。
算法设计分析
（一）数据结构的定义
为了能够用二叉树表示配偶、子女、兄弟三种关系，特采用以下存储关系，则能在二叉树上实现家谱的各项运算。
二叉树型存储结构定义为：
typedef struct SNODE
{char name[MAX]; //人名
struct SNODE *left;//指向配偶结点
struct SNODE *right; //指向兄弟或子女结点
}FNODE;
（二）总体设计
实验由主函数、家谱建立函数、家谱输出函数、儿子查找函数、祖先查找函数、结点定位函数、选择界面函数七个函数共同组成。其功能描述如下：
（1）主函数：统筹调用各个函数以实现相应功能
void main()
（2）家谱建立函数：与用户交互建立家族成员对应关系
void InitialFamily(FNODE *&head) //家谱建立函数
（3）家谱输出函数：用括号表示法输出家谱
输出形式为：父和母（子1和子妻1（孙1），子2和子妻2（孙2））
void PrintFamily(FNODE *head) //家谱输出函数
（4）儿子查找函数：在家谱中查找到某人所有的子女并输出，同时也能辨别出其是否为家族成员与是否有子女
void FindSon(FNODE *b,char p[]) //儿子查找函数
（5）祖先查找函数：在家谱中查找到某人所有的祖先并输出，同时也能辨别出其是否为家族中成员。
int FindAncestor(FNODE *head,char son[ ]) //祖先查找函数
（6）结点定位函数：在家谱中找到用户输入人名所对应的结点。
FNODE *findnode(FNODE *b,char p[]) //结点定位函数
（7）选择界面函数：为便于编写程序，将用户选择部分独立为此函数。
void PRINT(int &n)
（三）各函数的详细设计：
void InitialFamily(FNODE *&head) //家谱建立函数
1：首先建立当前人的信息，将其左右结点置为空，
2：然后让用户确定其是否有配偶，如果没有配偶，则当前程序结束，
3：如果有则建立其配偶信息，并将配偶结点赋给当前人的左结点；
4：再让用户确定其是否有子女，如果有则递归调用家谱建立函数建立子女结点，并将其赋给配偶结点的下一个右结点。
5：如无，则程序结束
void PrintFamily(FNODE *head) //家谱输出函数
1：首先判断当前结点是否为空，如果为空则结束程序；
2：如果不为空，则输出当前结点信息，
3：然后判断其左结点（配偶结点）是否为空，如不为空则输出“和配偶信息。
4：再判断配偶结点的右结点是否为空，如不为空则递归调用输出其子女信息，最后输出“）”；
5：当配偶结点为空时，则判断其右结点（兄弟结点）是否为空
6：如果不为空，则输出“，”，并递归调用输出兄弟信息
7程序结束
FNODE *findnode(FNODE *b,char p[]) //结点定位函数
1：当前结点是否为空，为空则返回空；
2：如果和查找信息相同，则返回当前结点；
3：如不然，则先后递归访问其左结点，再不是则递归访问右结点
void FindSon(FNODE *b,char p[]) //儿子查找函数
1：在家谱中定位到要查找的结点，如无则输出“查找不到此人”
2：判断其配偶结点与子女结点是否为空，为空则输出“无子女”
3：不为空则输出其配偶结点的所有右结点（子女结点）。
int FindAncestor(FNODE *head,char son[ ]) //祖先查找函数
1：先在家谱中定位到要查找的结点，如为空输出“不存在此人”，程序结束
2：先将父母结点入栈，当栈为空时程序结束，
3：栈不为空时，判断栈顶元素是否已访问过，
4：访问过，再判断是否为查找结点，如是则输出栈中保存的其祖先结点，并滤过其兄弟结点不输出；不是查找结点，则退栈一个元素
5：未访问过，则取当前栈顶元素，置访问标志——1，同时取其右结点
6：栈不为空或当前所取结点不为空时，转到2；
实验测试结果及结果分析
（一）测试结果
（二）结果分析
（略）
实验总结
（略）
【数据结构试卷】相关文章：
1.数据结构实验报告
2.数据结构面试
6.月考试卷
7.历史试卷
8.三年级试卷
9.成本会计试卷
10.试卷反思
文档为doc格式
