第一章
◆1.16②试写一算法，如果三个整数X，Y和Z的值不是依次非递增的，则通过交换，令其为非递增。void Descend(int &x, int &y, int &z)
/* 按从大到小顺序返回x，y和z的值*/
{ int t;
if(x { t=x; x=y; y=t; } if(x { t=x; x=z; z=t; } if(y { t=y; y=z; z=t;} } 1.17③已知k阶裴波那契序列的定义为 f0=0, f1=0, ..., fk-2=0, fk-1=1; fn=fn-1+fn-2+...+fn-k, n=k,k+1,... 试编写求k阶裴波那契序列的第m项值的函数算法，k和m均以值调用的形式在函数参数表中出现。要求实现下列函数： Status Fibonacci(int k, int m, int &f) /* 求k阶斐波那契序列的第m项的值f */ { int tempd; int temp[100]; int i,j,sum=0; if(k<2||m<0) return ERROR; if(m else if (m==k-1) f=1; else { for(i=0;i<=k-2;i++) temp[i]=0; temp[k-1]=1; for(i=k;i<=m;i++) { for(j=i-1;j>=i-k;j--) sum=sum+temp[j]; temp[i]=sum; sum=0; f=temp[m]; } return OK; } 1.18③假设有A、B、C、D、E五个高等院校进行田径对抗赛， 各院校的单项成绩均以存入计算机并构成一张表，表中每一行的形式为项目名称性别校名成绩得分.编写算法，处理上述表格，以统计各院校的男、女总分和团 体总分，并输出。 void Scores(ResultType *result, ScoreType *score) /* 求各校的男、女总分和团体总分, 并依次存入数组score */ /* 假设比赛结果已经储存在result[ ]数组中, */ /* 并以特殊记录{"", male, ' ', "", 0 }（域scorce=0）*/ /* 表示结束*/ { int i = 0; while( result[i].sport ) { switch( result[i].schoolname ) { case 'A': score[0].totalscore+= result[i].score; if( result[i].gender == female ) score[0].femalescore+=result[i].score; break; case 'B': score[1].totalscore += result[i].score; if( result[i].gender == female ) score[1].femalescore+=result[i].score; else score[1].malescore+= result[i].score; break; case 'C': score[2].totalscore += result[i].score; if( result[i].gender == female ) score[2].femalescore+=result[i].score; else score[2].malescore += result[i].score; break; case 'D': score[3].totalscore+= result[i].score; if( result[i].gender == female ) score[3].femalescore+=result[i].score; else score[3].malescore+=result[i].score; break; if( result[i].gender == female ) score[4].femalescore+=result[i].score; else score[4].malescore+=result[i].score; break; } i++; } } ◆1.19④试编写算法，计算i!×2^i的值并存入数组 a[0..ARRSIZE-1]的第i-1个分量中(i=1,2,…,n)。 假设计算机中允许的整数最大值为MAXINT，则当n>ARRSIZE或对某个k(1≤k≤n)使k!×2^k>MAXINT 时，应 按出错处理。注意选择你认为较好的出错处理方法。 1.19 Status Series(int ARRSIZE, int a[]) /* 求i!*2^i序列的值并依次存入长度为ARRSIZE的数组a；*/ /* 若所有值均不超过MAXINT，则返回OK，否则返回OVERFLOW */ { int i=1; int t=1; for(n=1;n { i=i*n; t=2*n; a[i]=i*t; } for(i=0;i { if(a[i]>MAXINT) return OVERFLOW; break; } return OK; } ◆1.20④试编写算法求一元多项式 P(x) = a0 + a1x + a2x^2 + ... + anx^n 的值P(x0)，并确定算法中每一语句的执行次数和整个算法的时间复杂度。注意选择你认为较好的输入和输出方法。 1.20 float Polynomial(int n, int a[], float x) /* 求一元多项式的值P(x)。*/ /* 数组a的元素a[i]为i次项的系数，i=0,...,n */ float s=0; for(i=n;i>=0;i--) s=s*x+a[i]; return s; } 第二章 ◆2.11②设顺序表L中的数据元素递增有序。试写一算法，将x插入到L的适当位置上，并保持该表的有序性。 2.11 void InsertOrderList(SqList &L, ElemType x) // 在有序的顺序表L 中保序插入数据元素x { int j; j=L.length-1; while(L.elem[j]>x) { L.elem[j+1]=L.elem[j]; j--; } L.elem[j+1]=x; L.length++; ◆2.12③设A=(a1,…,am)和B=(b1,…,bn)均为有序顺序表， A'和B'分别为A和B中除去最大共同前缀后的子表（例如， A=(x,y,y,z,x,z)，B=(x,y,y,z,y,x,x,z)，则两者中最大 的共同前缀为(x,y,y,z)，在两表中除去最大共同前缀后 的子表分别为A'=(x,z)和B'=(y,x,x,z)）。若A'=B'=空表，则A=B；若A'=空表，而B'≠空表，或者两者均不为空表，且A'的首元小于B'的首元，则A char Compare(SqList A, SqList B) // 比较顺序表A和B, // 返回'<', 若A // '=', 若A=B; // '>', 若A>B { int i=0; while((i<=A.length-1)&&(i<=B.length-1)&&(A.elem[i]=B.elem[i])) ++i; if(i==A.length&&i==B.length) return '='; else if(i==A.length&&i!=B.length&&A.elem[i] else if(i!=A.length&&i!=B.length&&A.elem[i] else return '>'; } 2.13②试写一算法在带头结点的单链表结构上实现线性表操作 Locate(L,x)。 实现下列函数： // If 'x' in the linked list whose head node is pointed // by 'L', then return pointer pointing node 'x', // otherwise return 'NULL' LinkList Locate(LinkList &L, ElemType x) // If 'x' in the linked list whose head node is pointed // by 'L', then return pointer ha pointing node 'x', // otherwise return 'NULL' { LinkList ha; ha=L->next; while(ha!=NULL&&ha->data!=x) ha=ha->next; if(ha==NULL) return NULL; else return ha; } 2.14②试写一算法在带头结点的单链表结构上实现线性表操作Length(L)。 int Length(LinkList L) // Return the length of the linked list // whose head node is pointed by 'L' int i=0; p=L; while(p->next!=NULL) { p=p->next; i++; } return i; } 2.17②试写一算法，在无头结点的动态单链表上实现线性表操作INSERT(L,i,b)，并和在带头结点的动态单链表上实现相同操作的算法进行比较。 void Insert(LinkList &L, int i, ElemType b) { LinkList p,s; if(!L&&i==1) { L=(LinkList)malloc(sizeof(LNode)); L->data=b; L->next=NULL; } else { if(i==0) { } else if(i==1) s=(LinkList)malloc(sizeof(LNode)); s->data=b; s->next=L; L=s; } else { p=L; int j=1; while(p&&j { p=p->next; j++ ; } s=(LinkList)malloc(sizeof(LNode)); s->data=b; s->next=p->next; p->next=s; } } } 2.18②同2.17题要求。试写一算法，实现线性表操作DELETE(L,i)。 void Delete(LinkList &L, int i) LinkList p,q; if(i==0) { } else if(i==1) { p=L; L=L->next; free(p); } else { int j=1; p=L; while(p->next!=NULL&&j p=p->next; j++; } q=p->next; p->next=q->next; free(q); } 2.20②同2.19题条件，试写一高效的算法，删除表中所有值相同的多余元素(使得操作后的线性表中所有元素的值均不相同) 同时释放被删结点空间，并分析你的算法的时间复杂度。 void Purge(LinkList &L) { LinkList p,q; p=L->next; q=p->next; while(q) { if(p->data==q->data) { q=q->next; p->next=q; } q=q->next; p=p->next; } } ◆2.21③试写一算法，实现顺序表的就地逆置， 即利用原表的存储空间将线性表(a1,a2,…,an) 逆置为(an,an-1,…,a1)。 void Inverse(SqList &L) { int temp; int i,j; { temp=L.elem[i]; L.elem[i]=L.elem[j]; L.elem[j]=temp; } } ◆ 2.22③试写一算法，对单链表实现就地置。 void Inverse(LinkList &L) /* 对带头结点的单链表L实现就地逆置*/ { LinkList p,q,r; p=L->next;q=NULL; while(p) { r=q; q=p; p=p->next; q->next=r; } L->next=q; } 2.23③设线性表A=(a1,...,am), B=(b1,...,bn)，试写一个按下列规则合并A、B为线性表C的算法，即使得C=(a1,b1,...,am,bm,bm+1,...,bn) 当m≤n时；或者C=(a1,b1,...,an,bn,an+1,...,am) 当m＞n时。线性表A、B和C均以单链表作存储结构，且C表利用A表和B表中的结点空间构成。注意：单链表的长度值m和 void Merge(LinkList ha, LinkList hb, LinkList &hc) /* 依题意，合并带头结点的单链表ha和hb为hc */ { LinkList pa,pb,pc; pa=ha->next;pb=hb->next;pc=hc=ha; while(pa&&pb) { pc->next=pa;pc=pa;pa=pa->next; pc->next=pb;pc=pb;pb=pb->next; } while(pa) { pc->next=pa; pc=pa; pa=pa->next; } while(pb) { pc->next=pb; pc=pb; pb=pb->next; } } 并要求利用原表（即A表和B表）的结点空间构造C表。 void Union(LinkList &lc, LinkList &la, LinkList &lb) { LinkList p,q,s,t; lc=la; p=la->next; q=lb->next; lc->next=NULL; while (p && q) if (p->data { s=p->next; p->next=lc->next; lc->next=p; p=s; } else { t=q->next; q->next=lc->next; lc->next=q; q=t; } while (p) {s=p->next; p->next=lc->next; lc->next=p; p=s;} while (q) {t=q->next; q->next=lc->next; lc->next=q; q=t;} free(lb); } 2.31②假设某个单向循环链表的长度大于1，且表中既无头结点也无头指针。已知s为指向链表中某个结点的指针，试编写算法在链表中删除指针s所指结点的前驱结点。 ElemType DeleteNode(LinkList s) /* 删除指针s所指结点的前驱结点，并返回被删结点的元素值*/ LinkList p,q; nt i; p=s; while(p->next->next!=s) p=p->next; q=p->next; i=q->data; p->next=q->next; free(q); return i; } 2.32②已知有一个单向循环链表，其每个结点中 含三个域：prev、data和next，其中data为数据域，next为指向后继结点的指针域，prev也为指针域，但它的值为空(NULL)，试编写算法将此单向循环链表改为双向循环链表，即使prev成为指向前驱结点的指针域。 void PerfectBiLink(BiLinkList &CL) { BiLinkList p; for(p=CL;!p->next->prev;p=p->next) p->next->prev=p; } ◆2.33③已知由一个线性链表表示的线性表中含有三类字符的数据元素（如：字母字符、数字字符和其它字符），试编写算法将该线性链表分割为三个循环链表，其中每个循环链表表示的线性表中均只含一类字符。 void Split(LinkList &lc, LinkList &ld, LinkList &lo, LinkList ll) LinkList p,q,r,s; p=lc;q=lo; r=ld,s=ll->next; while(s) { if(s->data>='0'&&s->data<='9') { r->next=s; r=r->next; } else if(s->data>='A'&&s->data<='Z'||s->data>='a'&&s->data<='z') { p->next=s; p=p->next; } else { q->next=s; q=q->next; } s=s->next; } q->next=NULL; r->next=NULL; } 2.37④设以带头结点的双向循环链表表示的线性表L=(a1,a2,...,an)。试写一时间复杂度为O(n)的算法，将L改造为L=(a1,a3,...,an,...,a4,a2)。 void ReverseEven(BiLinkList &L) { BiLinkList p; p=L->next; if(p->next==L){} else { while(p->next!=L&&p->next->next!=L) { p->next=p->next->next; p=p->next; } if(p->next==L) p->next=L->prev->prev; else p->next=L->prev; p=p->next; while(p->prev->prev!=L) { p->next=p->prev->prev; } p->next=L; for(p=L;p->next!=L;p=p->next) p->next->prev=p; L->prev=p; } } ◆2.39③试对稀疏多项式Pn(x)采用存储量同多项式项数m成正比的顺序存储结构，编写求Pn(x0)的算法（x0为给定值），并分析你的算法的时间复杂度。 float f(float x,int j) { int i; float s = 1; for( i = 0 ; i < j; ++i ){ s *= x; } return s; } float Evaluate(SqPoly pn, float x) /* pn.data[i].coef 存放ai，*/ /* pn.data[i].exp存放ei (i=1,2,...,m) */ /* 本算法计算并返回多项式的值。不判别溢出。*/ /* 入口时要求0≤e1 { int i; float s = 0; 华农数据结构上机实验答案 数据结构上机答案 1.1顺序线性表的基本操作 #include { newbase=(ElemType*)realloc(L.elem,(L.listsize+LISTINCREMENT)*size of(ElemType)); L.elem=newbase; L.listsize+=LISTINCREMENT; } q=&(L.elem[i-1]); for(p=&(L.elem[L.length-1]);p>=q;--p) *(p+1)=*p; *q=e; ++L.length; return OK; } int ListDelete_Sq(SqList &L,int i,int &e) { ElemType *q,*p; if(i<1||i>L.length) return ERROR; p=&(L.elem[i-1]); e=*p; q=L.elem+L.length-1; for(++p;p<=q;p++) *(p-1)=*p; L.length--; return OK; } int main() { SqList T; int a,i; ElemType e,x; if(InitList_Sq(T)) { printf("A Sequence List Has Created.\n"); } while(1) { printf("1:Insert element\n2:Delete element\n3:Load all elements\n0:Exit\nPlease choose:\n"); scanf("%d",&a); switch(a) 2011上机实习基本要求及内容 上机实习基本目标 计算机学科分为理论、抽象、设计三个形态。 数据结构是计算机学科的重要分支研究领域之一。在算法分析与设计、操作系统、软件工程、数据库概论、编译技术、计算机图形学、人机交互等专业基础课和专业课程中均有涉及。对特定领域或应用要使用到头特定的数据结构：编译系统要使用栈、散列表及语法树；操作系统中要用队列、存储管理表及目录树等；数据库系统要用线性表、多链表及索引树等；在人工智能领域依求解问题性质的差异将涉及到各种不同的数据结构，如广义表，集合、搜索树及各种有向图等等。 通过数据结构上机实习要让学生掌握链表、树、图是如何实现的，进一步从理论、抽象、设计的角度来考虑问题。第一，让学生真正理解“数据结构＋算法＝程序”。程序不仅仅是求解算法的实现，也要配有恰当的数据结构；第二，培养学生数据抽象的能力。让学生了解链表、树、图等数据结构是如何实现的，特别要加强对数据逻辑关系的分析与认识；第三，培养学生使用数据结构的能力。要把数据结构与算法的理论分析与编程实践相结合，灵活运用于实际解题中。 需要强调以下几个方面的知识和能力： （1）掌握并能够灵活应用基本数据结构的抽象数据类型、存储方法、主要的算法，特别是线性结构、二叉树、树、图、文件等； （2）掌握并应用常用的排序、检索和索引算法和方法； （3）掌握基本的算法设计和分析技术，并结合具体的设计，对所设计的数据结构和算法进行分析； （4）在进行程序设计、调试中，注意综合应用，将所学到的数据结构和算法知识应用到对具体数据对象的特性分析。结合实际例子进行设计，选择合适的数据结构和存贮结构以及相应的算法。 上机实习基本要求 1．合理地选用组织数据、有效地表示数据、正确地处理数据，清晰地表述算法。 2．完成选定题目，按照规范格式（附件一）写出实习报告(原问题、设计算法、DS、程序、给出实例并分析结果、讨论T(n))。 3．线性关系、非线性关系、算法三部分的实习报告电子版提交日期在上机后2日内提交；第四次机考电子版在上机结束时提交(电子版交liuxd@https://www.doczj.com/doc/17790439.html,，将四次上机汇总打印纸版笔试前1周交西1楼711室)；请按时提交注意上交电子版与纸版应一致。 4. 请按照附件给定报告内容格式安排。 国家二级ACCESS机试选择题（数据结构与算法）模拟试卷3 (总分：60.00，做题时间：90分钟) 一、选择题(总题数：30，分数：60.00) 1.在最坏情况下 （分数：2.00） A.快速排序的时间复杂度比冒泡排序的时间复杂度要小 B.快速排序的时间复杂度比希尔排序的时间复杂度要小 C.希尔排序的时间复杂度比直接插入排序的时间复杂度要小√ D.快速排序的时间复杂度与希尔排序的时间复杂度是一样的 解析：解析：按平均时间将排序分为四类：①平方阶(O(n 2 ))排序：各类简单排序，例如直接插入、直接选择和冒泡排序；②线性对数阶(O(n。log2n))排序：如快速排序、堆排序和归并排序；③O(n1+§))排序：§是介于0和1之间的常数。希尔排序便是一种；④线性阶(O(n))排序：本程序中的基数排序，此外还有桶、箱排序。 2.在深度为7的满二叉树中，度为2的结点个数为 （分数：2.00） A.64 B.63 √ C.32 D.31 解析：解析：因为在任意的二叉树中，度为O的结点(即叶子结点)总比度为2的结点的个数多1个，而度为0的结点数n 0 =2 m-1 (其中m为二叉树的深度)。本题的度为0的结点个数n 0 =2 7-1 =2 6 =64。因此，度为2的结点数n 2 =n 0 -1=63。所以选项B正确 3.设栈的顺序存储空间为S(1：m)，初始状态为top=m+1。现经过一系列入栈与退栈运算后，top=20，则当前栈中的元素个数为 （分数：2.00） A.30 B.20 C.m-19 √ D.m-20 TOP指针向上移动一位。当压入第一个元素时，TOP指针指向m+1-1=m；当压入第二个元素时，TOP指针指向 1n+1．2=m．1；…以此类推，当压入第N个元素时，TOP指针指向m+1-N=20；则N=m+1-20=m-19。因此选项C正确。 4.算法空间复杂度的度量方法是 （分数：2.00） A.算法程序的长度 B.算法所处理的数据量 C.执行算法所需要的工作单元 D.执行算法所需要的存储空间√ 解析：解析：算法空间复杂度是对一个算法在运行过程中临时占用存储空间大小的度量，因此选项D正确。 5.设循环队列为Q(1：m)，其初始状态为front=rear=m。经过一系列入队与退队运算后，front=15，rear=20。现要在该循环队列中寻找最大值的元素，最坏情况下需要比较的次数为 （分数：2.00） A.4 √ B.6 C.m-5 《数据结构实验指导书》答案 实验一： 1、请编写函数int fun(int *a, int *b),函数的功能是判断两个指针a和b所指存储单 元的值的符号是否相同；若相同函数返回1，否则返回0。这两个存储单元中的值都不为0。在主函数中输入2个整数、调用函数fun、输出结果。 #include 数fun、输出结果。 #define N 10 #include 习题六树和二叉树6.1 单项选择题 (A) (B) (C) (D) 图8.7 4棵二叉树 1. 如图8.7所示的4棵二叉树，_ _不是完全二叉树。 图8.8 4棵二叉树 2. 如图8.8所示的4棵二叉树，__B_是平衡二叉树。 3. 在线索化二叉树中，t所指结点没有左子树的充要条件是B__o A. t —> left二NULL B. t —> ltag=1 C. t —> ltag=1 且t —> left=NULL D. 以上都不对 4. 二叉树按某种顺序线索化后，任一结点均有指向其前驱和后续的线索，这种说 法_B__ o A.正确 B. 错误 5. 二叉树的前序遍历序列中，任意一个结点均处在其子女结点的前面，这种说法 _A__。 A.正确 B. 错误 6. 由于二叉树中每个结点的度最大为2,所以二叉树是一种特殊的树，这种说法 _B_o A.正确 B. 错误 7. 设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为—B__o A. 2h B. 2h-1 C. 2h+1 D. h+1 a 8. 如图8.9所示二叉树的中序遍历序列 B o 图8.9 一棵二叉树 A. abcdgef B. dfebagc C. dbaefcg D. defbagc 9. 已知某二叉树的后序遍历序列是d abec，中序遍历序 列是debac，它的前序遍历 序列是D ___ 。 A. acbed B. decab C. deabc D. cedba 10. 设a,b为一棵二叉树上的两个结点，在中序遍历时，a在b前的条件是 B 。 A. a在b的右方 B. a在b的左方 C. a是b的祖先 D. a是b的子孙 11?假定在一棵二叉树中，双分支结点数为15,单分支结点数为30个，则叶子结 点数为个。B A. 15 B. 16 C. 17 D. 47 12. 某二叉树的前序遍历结点访问顺序是abdgcefh，中序遍历的结点访问顺序是 dgbaechf，则其后序遍历的结点访问顺序是D _____ 。 A. bdgcefha B. gdbecfha C. bdgaechf D. gdbehfca 13. 二叉树为二叉排序树的充分必要条件是其任一结点的值均大于其左孩子的值、 小于其右孩子的值。这种说法__B__ o A.正确 B. 错误 14. 按照二叉树的定义，具有3个结点的二叉树有_。__种。 A. 3 B. 4 C. 5 D. 6 15. 一棵二叉树如图8.10所示，其中序遍历的序列为 数据结构上机实验报告 学院：电子工程学院 专业：信息对抗技术 姓名： 学号： 教师：饶鲜日期： 目录 实验一线性表................................................. - 4 - 一、实验目的................................................ - 4 - 二、实验代码................................................ - 4 - 三、实验结果............................................... - 14 - 四、个人思路............................................... - 15 -实验二栈和队列.............................................. - 15 - 一、实验目的............................................... - 15 - 二、实验代码............................................... - 16 - 三、实验结果............................................... - 24 - 四、个人思路............................................... - 25 -实验三数组.................................................. - 26 - 一、实验目的............................................... - 26 - 二、实验代码............................................... - 26 - 三、实验结果............................................... - 28 - 四、个人思路............................................... - 28 -实验四树.................................................... - 29 - 一、实验目的............................................... - 29 - 二、实验代码............................................... - 29 - 习题二 ⒉１描述以下四个概念的区别：头指针变量，头指针，头结点，首结点（第一个结点）。解：头指针变量和头指针是指向链表中第一个结点（头结点或首结点）的指针；在首结点之前附设一个结点称为头结点；首结点是指链表中存储线性表中第一个数据元素的结点。若单链表中附设头结点，则不管线性表是否为空，头指针均不为空，否则表示空表的链表的头指针为空。 2.2简述线性表的两种存储结构有哪些主要优缺点及各自使用的场合。 解：顺序存储是按索引直接存储数据元素，方便灵活，效率高，但插入、删除操作将引起元素移动，降低了效率；而链式存储的元素存储采用动态分配，利用率高，但须增设表示结点之间有序关系的指针域，存取数据元素不如顺序存储方便，但结点的插入和删除十分简单。顺序存储适用于线性表中元素数量基本稳定，且很少进行插入和删除，但要求以最快的速度存取线性表中的元素的情况；而链式存储适用于频繁进行元素动态插入或删除操作的场合。 2.3 在头结点为h的单链表中，把值为b的结点s插入到值为a的结点之前，若不存在a，就把结点s插入到表尾。 Void insert(Lnode *h,int a,int b) {Lnode *p,*q,*s; s=(Lnode*)malloc(sizeof(Lnode)); s->data=b; p=h->next; while(p->data!=a&&p->next!=NULL) {q=p; p=p->next; } if (p->data==a) {q->next=s; s->next=p;} else {p->next=s; s->next=NULL; } } 2.4 设计一个算法将一个带头结点的单链表A分解成两个带头结点的单链表A和B，使A中含有原链表中序号为奇数的元素，而B中含有原链表中序号为偶数的元素，并且保持元素原有的相对顺序。 Lnode *cf(Lnode *ha) {Lnode *p,*q,*s,*hb; int t; p=ha->next; q=ha; t=0; hb=(Lnode*)malloc(sizeof(Lnode)); s=hb; while(p->next!=NULL) {if (t==0) {q=p;p=p->next;t=1;} else {q->next=p->next; p->next=s->next; s->next=p; s=p; p=p->next; t=0; } } s->next=NULL; return (hb); } 《数据结构》上机作业 (黑色--必做；蓝色--选作) 线性表 1、某软件公司大约有30名员工，每名员工有姓名、工号、职务等属性，每年都有员工离 职和入职。 把所有员工按照顺序存储结构建立一个线性表，建立离职和入职函数，当有员工离职或入职时，修改线性表，并且打印最新的员工名单。（动态分配存储，malloc，realoc）2、约瑟夫（Josephus）环问题：编号为1,2,3,…,n的n个人按顺时针方向围坐一圈，每 人持有一个密码（正整数）。一开始任选一个正整数作为报数的上限值m，从第一个人开始按顺时针方向自1开始顺序报数,报到m时停止。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一人开始重新从1报数，如此下去，直到所有人全部出列为止。 建立n个人的单循环链表存储结构，运行结束后，输出依次出队的人的序号。（必须用链表） 栈和队列 3、某商场有一个100个车位的停车场，当车位未满时，等待的车辆可以进入并计时；当车 位已满时，必须有车辆离开，等待的车辆才能进入；当车辆离开时计算停留的的时间，并且按照每小时1元收费。汽车的输入信息格式可以是（进入/离开，车牌号，进入/离开时间），要求可以随时显示停车场内的车辆信息以及收费历史记录。（选作，用指针轮询数组，有空位就入，利用时间函数计时） 4、某银行营业厅共有6个营业窗口，设有排队系统广播叫号，该银行的业务分为公积金、 银行卡、理财卡等三种。公积金业务指定1号窗口，银行卡业务指定2、3、4号窗口，理财卡业务指定5、6号窗口。但如果5、6号窗口全忙，而2、3、4号窗口有空闲时，理财卡业务也可以在空闲的2、3、4号窗口之一办理。客户领号、业务完成可以作为输入信息，要求可以随时显示6个营业窗口的状态。（复杂，选作） 5、4阶斐波那契序列如下：f0=f1=f2=0, f3=1,…,f i=f i-1+f i-2+f i-3+f i-4， 利用容量为k=4的循环队列，构造序列的前n+1项（f0, f1 , f2 ,… fn ），要求满足f n≤200而f n+1 >200。 6、八皇后问题：设8皇后问题的解为(x1, x2, x3, …,x8), 约束条件为：在8x8的棋盘上， 其中任意两个xi 和xj不能位于棋盘的同行、同列及同对角线。要求用一位数组进行存储，输出所有可能的排列。 7、迷宫求解：用二维矩阵表示迷宫，自动生成或者直接输入迷宫的格局，确定迷宫是否能 走通，如果能走通，输出行走路线。 8、英国人格思里于1852年提出四色问题(four colour problem，亦称四色猜想），即在为一平 面或一球面的地图着色时，假定每一个国家在地图上是一个连通域，并且有相邻边界线的两个国家必须用不同的颜色，问是否只要四种颜色就可完成着色。现在给定一张地图，要求对这张地图上的国家用不超过四种的颜色进行染色。 要求建立地图的邻接矩阵存储结构，输入国家的个数和相邻情况，输出每个国家的颜色代码。 数组与广义表 班级：：学号： 实验一线性表的基本操作 一、实验目的 1、掌握线性表的定义； 2、掌握线性表的基本操作，如建立、查找、插入和删除等。 二、实验容 定义一个包含学生信息（学号，，成绩）的顺序表和链表（二选一），使其具有如下功能： (1) 根据指定学生个数，逐个输入学生信息； (2) 逐个显示学生表中所有学生的相关信息； (3) 根据进行查找，返回此学生的学号和成绩； (4) 根据指定的位置可返回相应的学生信息（学号，，成绩）； (5) 给定一个学生信息，插入到表中指定的位置； (6) 删除指定位置的学生记录； (7) 统计表中学生个数。 三、实验环境 Visual C++ 四、程序分析与实验结果 #include typedef int Status; // 定义函数返回值类型 typedef struct { char num[10]; // 学号 char name[20]; // double grade; // 成绩 }student; typedef student ElemType; typedef struct LNode { ElemType data; // 数据域 struct LNode *next; //指针域 }LNode,*LinkList; Status InitList(LinkList &L) // 构造空链表L { L=(struct LNode*)malloc(sizeof(struct LNode)); L->next=NULL; return OK; 数据结构上机实验题目 实验一线性表的顺序存储结构 实验学时 2学时 背景知识:顺序表的插入、删除及应用。 目的要求： 1．掌握顺序存储结构的特点。 2．掌握顺序存储结构的常见算法。 实验容 1．输入一组整型元素序列，建立顺序表。 2．实现该顺序表的遍历。 3．在该顺序表中进行顺序查找某一元素,查找成功返回1,否则返回0。4．判断该顺序表中元素是否对称,对称返回1,否则返回0。 5．实现把该表中所有奇数排在偶数之前,即表的前面为奇数,后面为偶数。 6．输入整型元素序列利用有序表插入算法建立一个有序表。 7．利用算法6建立两个非递减有序表并把它们合并成一个非递减有序表。 8. 利用该顺序结构实现循环队列的入队、出队操作。 8．编写一个主函数,调试上述算法。 #include #define OVERFLOW 0 #define MAXSIZE 100 typedef int ElemType; typedef struct list {ElemType elem[MAXSIZE]; int length; }Sqlist; void Creatlist(Sqlist &L) {int i; printf("请输入顺序表的长度："); //输入一组整型元素序列，建立一个顺序表。 scanf("%d",&L.length); for(i=0;i 实习一： 1、编写一个读入一个字符串，把它存入一个链表，并按相反的次序打印的程序。 2、设有一个单位的人员工资有如下信息：name、department、 base pay、allowance、total。现从键盘输入一组人员工资数据并将它们存储到名为paydata的文件中；再从paydata取出工资数据并给每个人的base pay增加100元，增加后将工资数据显示于屏幕(每行1人)。请编写能够完成上述工作的程序。 代码如下： 1.#include 注意事项1. 考试时间2小时，13：00-15：00 2. 题目4选2 3. 所有题目均使用标准输入和标准输出3. 只提交源程序，文件后缀名只能是.C或.CPP 4. 源文件大小不能超过10K，否则会被当作恶意提交而扣分5. 严格按照题目要求输出，去掉不需要的提示信息或调试信息6. 在程序中不要使用fflush(stdin)函数，否则会导致结果错误另外注意：本次是模拟测试，上机时间是4个小时，我们考试时间从14点开始到17点30分结束。同学视自己的能力，能做几道做几道。 哈夫曼树 时间限制: 100 second 内存限制: 100 Kb 描述 构造哈夫曼树（最优二叉树） 输入 输入n个结点每个结点的权值 输出 构造哈夫曼树（是最优二叉树）得到每个结点的哈夫曼编码 输入样例 23 186 64 13 22 32 103 21 15 47 57 1 5 32 20 57 63 15 1 48 51 80 23 8 输出样例 1( 186):00 2( 64):1001 3( 13):101100 4( 22):110010 5( 32):11100 6( 103):011 7( 21):110001 8( 15):101101 9( 47):11010 10( 57):0101 11( 1):101111000 12( 5):10111101 13( 32):11101 14( 20):110000 15( 57):1010 16( 63):1000 17( 15):101110 18( 1):101111001 19( 48):11011 20( 51):0100 21( 80):1111 22( 23):110011 23( 8):1011111 提示 输入第一行是结点数23 第二行是这几个结点的权值输出格式为结点号（权值）：哈夫曼编码 数据结构上机考试试题（C++语言版） 考试要求：本次考试共列考核试题4大题，考生可以在所列4个考核试题中任选3个小题（即可能只属于2个大题），作为上机考核试题。 考核原则：所选题目在上机编程调试通过后即为考核通过。监考教师依据学生编程及调试通过与否情况给予考核成绩。 考核成绩评分标准： 所选3个题目全部编写出程序并调试通过：优 所选3个题目全部编写出程序，但只有2个上机调试通过：良 所选3个题目全部编写出程序，但只有1个上机调试通过：及格 所选3个题目全部编写出程序但都没有上机调试通过，或没有编写出全部程序：不及格。考核时间：2小时。 考核试题： 1、建立一个顺序方式存储的线性表，向表中输入若干元素后进行以下操作： （1）向线性表的表头、表尾或合适位置插入元素 （2）对线性表按升序或降序输出 2、建立一个动态链接方式存储的线性表，向表中输入若干元素后进行以下操作： （1）从单链表中查找指定元素 （2）返回单链表中指定序号的结点值 3、建立一个动态链接结构存储的二叉树，向这棵二叉树进行以下操作： （1）按任中序遍历次序输出二叉树中的所有结点 （2）求二叉树的叶子数 4、编写一个对整型数组A[n+1]中的A[1]至A[n]元素进行选择排序的算法，使得首先从待排序区间中选择出一个最大值并同最后一个元素交换，再从待排序区间中选择出一个最小值并同最第一个元素交换，反复进行直到待排序区间中元素的个数不超过1为止。 #include<> #include<> #include"" //初始化线性表 void InitList(LinearList& L, int ms) { =new ElemType[ms]; if(! { cerr<<"Memory allocation failure!"< 1．将顺序表逆置，要求用最少的附加空间。 参考答案 #include 数据结构基础及深入及考试 复习资料 习题及实验参考答案见附录 结论 1、数据的逻辑结构是指数据元素之间的逻辑关系。即从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。 2、数据的物理结构亦称存储结构，是数据的逻辑结构在计算机存储器内的表示（或映像）。它依赖于计算机。存储结构可分为4大类：顺序、链式、索引、散列 3、抽象数据类型：由用户定义，用以表示应用问题的数据模型。它由基本的数据类型构成，并包括一组相关的服务（或称操作）。它与数据类型实质上是一个概念，但其特征是使用与实现分离，实行封装和信息隐蔽（独立于计算机）。 4、算法：是对特定问题求解步骤的一种描述，它是指令的有限序列，是一系列输入转换为输出的计算步骤。 5、在数据结构中，从逻辑上可以把数据结构分成（ C ） A、动态结构和表态结构 B、紧凑结构和非紧凑结构 C、线性结构和非线性结构 D、内部结构和外部结构 6、算法的时间复杂度取决于（ A ） A、问题的规模 B、待处理数据的初态 C、问题的规模和待处理数据的初态 线性表 1、线性表的存储结构包括顺序存储结构和链式存储结构两种。 2、表长为n的顺序存储的线性表，当在任何位置上插入或删除一个元素的概率相等时，插入一个元素所需移动元素的平均次数为（ E ），删除一个元素需要移动的元素的个数为（ A ）。 A、(n-1)/2 B、n C、n+1 D、n-1 E、n/2 F、(n+1)/2 G、(n-2)/2 3、“线性表的逻辑顺序与存储顺序总是一致的。”这个结论是（ B ） A、正确的 B、错误的 C、不一定，与具体的结构有关 4、线性表采用链式存储结构时，要求内存中可用存储单元的地址（ D ） A、必须是连续的 B、部分地址必须是连续的C一定是不连续的D连续或不连续都可以 5、带头结点的单链表为空的判定条件是（ B ） A、head==NULL B、head->next==NULL C、head->next=head D、head!=NULL 6、不带头结点的单链表head为空的判定条件是（ A ） A、head==NULL B、head->next==NULL C、head->next=head D、head!=NULL 7、非空的循环单链表head的尾结点P满足（ C ） A、p->next==NULL B、p==NULL C、p->next==head D、p==head 8、在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是（ B ） A、O(1) B、O(n) C、O(n2) D、O(nlog2n) 9、在一个单链表中，若删除p所指结点的后继结点，则执行（ A ） 国家二级MS Office高级应用机试（数据结构与算法）模拟试卷 8 (总分：56.00，做题时间：90分钟) 一、选择题(总题数：28，分数：56.00) 1.下列结构中属于线性结构链式存储的是 （分数：2.00） A.双向链表√ B.循环队列 C.二叉链表 D.二维数组 解析：解析：数据元素之间的关系有两种不同的表示方法：顺序映象和非顺序映象，并由此得到两种不同的存储结构：顺序存储结构和链式存储结构。数据的存储结构是指数据的逻辑结构在计算机中的表示。双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱，它的存储方式是线性结构链式。循环队列、二叉链表和二维数组都是顺序存储结构。 2.下列叙述中错误的是 （分数：2.00） A.循环链表中有一个表头结点 B.循环链表的存储空间是连续的√ C.循环链表实现了空表与非空表运算的统一 D.循环链表的表头指针与循环链表中最后一个结点的指针均指向表头结点 解析：解析：循环链表是另一种形式的链式存储结构。它的特点是表中最后一个结点的指针域指向头结点，整个链表形成一个环。循环链表的结点是指针指向，它不一定要是连续的存储空间，也可以是断开的空间。 3.度为3的一棵树共有30个结点，其中度为3、1的结点个数分别为3、4。则该树中的叶子结点数为 （分数：2.00） A.14 B.15 √ C.16 D.不可能有这样的树 解析：解析：根据题目可知本树中还有度为2的结点。树的总结点＝(度1*个数＋度2*个数…)＋1，这里我们设度为2的结点数为x，那么30＝3*3＋2*x＋1*4＋1＝2*x＋14，由此可计算出x＝8。树的叶子结点数等于总结点减去所有度不为0的结点，也就是30－3－8－4＝15。 4.在长度为97的顺序有序表中作二分查找，最多需要的比较次数为 （分数：2.00） A.7 √ B.96 C.48 D.6 解析：解析：二分查找又称折半查找，优点是比较次数少，查找速度快，平均性能好；其缺点是要求待查表为有序表，且插入删除困难。最多比较次数的计算方式：k＝log 2 n。其中n代表长度，k为比较次数。本题中可以计算出k＝7。 5.下列结构中属于非线性结构的是 （分数：2.00） A.二叉链表 B.二维数组√ C.循环队列 数据结构与算法上机作业 第三章树 一、选择题 1、在一棵树中,如果结点A有3个兄弟,B就是A得双亲,则B得度为 D A、1 B、2 C、3 D、4 2、深度为h得完全二叉树至少有 D 个结点,至多有 B 个结点 A、2h B、2h-1 C、2h+1 D、2h-1 3、具有n个结点得满二叉树有 C 个叶结点。 A、n/2 B、(n-1)/2 C、(n+1)/2 D、n/2+1 4、一棵具有25个叶结点得完全二叉树最多有 C 个结点。 A、48 B、49 C、50 D、51 5、已知二叉树得先根遍历序列就是ABCDEF,中根遍历序列就是CBAEDF,则后根遍历序列就是 A 。 A、CBEFDA B、FEDCBA C、CBEDFA D、不定 6、具有10个叶结点得二叉树中有 B 个度为2得结点。 A、8 B、9 C、10 D、11 7、一棵非空二叉树得先序遍历序列与后序遍历序列正好相反,则该二叉树一定满足 B 。 A、所有非叶结点均无左孩子 B、所有非叶结点均无右孩子 C、只有一个叶子结点 D、A与B同时成立 8、在线索二叉树中,t所指结点没有左子树得充要条件就是 D 。 A、t->left=NULL B、t->ltag=TRUE C、t->ltag=TRUE且t->left=NULL D、以上都不对 9、n个结点得线索二叉树上含有得线索数为 C 。 A、2n B、n-1 C、n+1 D、n 10、二叉树按照某种顺序线索化后,任一结点都有指向其前驱与后继得线索,这种说法 B 。 A、正确 B、错误 C、不确定 D、都有可能 11、具有n(n>1)个结点得完全二叉树中,结点i(2i>n)得左孩子结点就是 D 。 A、2i B、2i+1 C、2i-1 D、不存在 12、具有64个结点得完全二叉树得深度为 C 。 A、5 B、6 C、7 D、8 13、将一颗有100个结点得完全二叉树从上到下、从左到右一次对结点进行编号,根结点得编号为1,则编号为45得结点得右孩子得编号为 D 。 A、46 B、47 C、90 D、91 14、在结点数为n得堆中插入一个结点时,复杂度为 C 。 A、O(n) B、O(n2) C、O(log2n) D、O(log n2) 15、两个二叉树就是等价得,则它们满足 D 。 A、它们都为空 B、它们得左右子树都具有相同得结构 C、它们对应得结点包含相同得信息 D、A、B与C 16、包含n个元素得堆得高度为 C 。(符号「a表示取不小a最小整数) A、n B、「log2n C、「log2(n+1) D、n+1 17、以下说法错误得就是 B 。 #include //void insert(struct Lnode**L,int n, char d) //从功能化分上，这个函数不需要知道现在插入第几个字符//困为你init函数中是先对一个串的字符进行了排序，所以//这里直接插入链表的尾部就行了 void insert(struct Lnode**L, char d) { struct Lnode *t1,*t2; int j=1; t1=(struct Lnode*)malloc(sizeof(struct Lnode)); t1-> data=d; t1-> next=NULL; if(*L==NULL) { *L=t1; return; } t2=*L; while(t2-> next!=NULL) { t2=t2-> next; } t2-> next=t1; /* if(n==1) { t1-> next=t2; *L=t1; } else { while(j 华农数据结构上机实验答案
数据结构上机作业模板
国家二级ACCESS机试选择题(数据结构与算法)模拟试卷3
数据结构上机实验答案
数据结构书面作业练习题
数据结构上机实验报告
数据结构上机例题及答案
数据结构上机作业
数据结构实验一 实验报告
经典数据结构上机题_答案解析
数据结构上机答案(c语言版)
数据结构上机考试题
数据结构上机考试试题
大连理工大学数据结构(一)上机作业答案——张老师
数据结构(第4版)习题及实验参考答案数据结构复习资料完整版(c语言版)
国家二级MS+Office高级应用机试(数据结构与算法)模拟试卷8
数据结构与算法上机作业
数据结构上机题
相关主题
文本预览