数据结构上机作业

《数据结构》上机作业

(黑色--必做；蓝色--选作)

线性表

1、某软件公司大约有30名员工，每名员工有姓名、工号、职务等属性，每年都有员工离

职和入职。

把所有员工按照顺序存储结构建立一个线性表，建立离职和入职函数，当有员工离职或入职时，修改线性表，并且打印最新的员工名单。（动态分配存储，malloc，realoc）2、约瑟夫（Josephus）环问题：编号为1,2,3,…,n的n个人按顺时针方向围坐一圈，每

人持有一个密码（正整数）。一开始任选一个正整数作为报数的上限值m，从第一个人开始按顺时针方向自1开始顺序报数,报到m时停止。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一人开始重新从1报数，如此下去，直到所有人全部出列为止。

建立n个人的单循环链表存储结构，运行结束后，输出依次出队的人的序号。（必须用链表）

3、已知线性表中的元素以值递增有序排列，并以单链表作存储结构。试写一高效的算法，

删除表中所有值大于mink且小于maxk的元素（若表中存在这样的元素），同时释放被删结点空间，并分析你的算法的时间复杂度（注意：mink和maxk是给定的两个参变量，他们的值可以和表中相同，也可以不同）

4、试写一个算法，对单链表实现就地逆置。

5、设有一个双向循环链表，每个结点中除有prior, data和next三个域外，还增设了一个访

问频度域freq。在链表被起用之前，频度域freq的值均初始化为零，而每当对链表进行一次locate(L, x)的操作后，被访问的结点（即元素值等于x的结点）中的频度域freq的值便增1，同时调整链表中结点之间的次序，使其按访问频度非递减的次序顺序排列，以便始终保持被频繁访问的结点总是靠近表头结点。试编写符合上述要求的locate操作的算法。

（注意：如果没有特别说明，链表均带头结点）

栈和队列

6、某商场有一个100个车位的停车场，当车位未满时，等待的车辆可以进入并计时；当车

位已满时，必须有车辆离开，等待的车辆才能进入；当车辆离开时计算停留的的时间，并且按照每小时1元收费。汽车的输入信息格式可以是（进入/离开，车牌号，进入/离开时间），要求可以随时显示停车场内的车辆信息以及收费历史记录。（选作，用指针轮询数组，有空位就入，利用时间函数计时）

7、某银行营业厅共有6个营业窗口，设有排队系统广播叫号，该银行的业务分为公积金、

银行卡、理财卡等三种。公积金业务指定1号窗口，银行卡业务指定2、3、4号窗口，理财卡业务指定5、6号窗口。但如果5、6号窗口全忙，而2、3、4号窗口有空闲时，理财卡业务也可以在空闲的2、3、4号窗口之一办理。客户领号、业务完成可以作为输入信息，要求可以随时显示6个营业窗口的状态。（复杂，选作）

8、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。

9、八皇后问题：设8皇后问题的解为(x1, x2, x3, …,x8), 约束条件为：在8x8的棋盘上，

其中任意两个xi 和xj不能位于棋盘的同行、同列及同对角线。要求用一位数组进行存储，输出所有可能的排列。

10、迷宫求解：用二维矩阵表示迷宫，自动生成或者直接输入迷宫的格局，确定迷宫是否能

走通，如果能走通，输出行走路线。

11、英国人格思里于1852年提出四色问题(four colour problem，亦称四色猜想），即在为一

平面或一球面的地图着色时，假定每一个国家在地图上是一个连通域，并且有相邻边界线的两个国家必须用不同的颜色，问是否只要四种颜色就可完成着色。现在给定一张地图，要求对这张地图上的国家用不超过四种的颜色进行染色。

要求建立地图的邻接矩阵存储结构，输入国家的个数和相邻情况，输出每个国家的颜色代码。

数组与广义表

12、鞍点问题：若矩阵A中的某一元素A[i,j]是第i行中的最小值，而又是第j列中的最

大值，则称A[i,j]是矩阵A中的一个鞍点。写出一个可以确定鞍点位置的程序。

13、稀疏矩阵转置：输入稀疏矩阵中每个元素的行号、列号、值，建立稀疏矩阵的三元组

存储结构，并将此矩阵转置，显示转置前后的三元组结构。

树和二叉树

以下问题要求统一在一个大程序里解决。

14、按先序遍历的扩展序列建立二叉树的存储结构

15、二叉树先序、中序、后序遍历的递归算法

16、二叉树中序遍历的非递归算法

17、二叉树层次遍历的非递归算法

18、求二叉树的深度(后序遍历)

19、建立树的存储结构

20、求树的深度

图

21、输入任意的一个网，用普里姆(Prim)算法构造最小生成树。

22、要求建立图的存储结构（邻接表或邻接矩阵），输入任意的一个图，显示图的深度优先

搜索遍历路径。

23、要求建立图的存储结构（邻接表或邻接矩阵），输入任意的一个图，显示图的广度优先

搜索遍历路径。

查找

24、设计一个读入一串整数构成一颗二叉排序树的程序，从二叉排序树中删除一个结点，使

该二叉树仍保持二叉排序树的特性。

25、设定哈希函数H(key) = key MOD 11 ( 表长=11 )，输入一组关键字序列，根据线性探测

再散列解决冲突的方法建立哈希表的存储结构，显示哈希表，任意输入关键字，判断是否在哈希表中。

排序

以下问题要求统一在一个大程序里解决。

26、折半插入排序

27、冒泡排序

28、快速排序

29、简单选择排序

30、归并排序

31、堆排序

《结构力学》作业答案

[0729]《结构力学》 1、桁架计算的结点法所选分离体包含几个结点 A. 单个 2、固定铰支座有几个约束反力分量 B. 2个 3、从一个无多余约束的几何不变体系上去除二元体后得到的新体系是 A. 无多余约束的几何不变体系 4、两刚片用三根延长线交于一点的链杆相连组成 A. 瞬变体系 5、定向滑动支座有几个约束反力分量 B. 2个 6、结构的刚度是指 C. 结构抵抗变形的能力 7、桁架计算的截面法所选分离体包含几个结点 B. 最少两个 8、对结构进行强度计算的目的，是为了保证结构 A. 既经济又安全 9、可动铰支座有几个约束反力分量 A. 1个 10、固定支座(固定端)有几个约束反力分量 C. 3个 11、改变荷载值的大小，三铰拱的合理拱轴线不变。 A.√ 12、多余约束是体系中不需要的约束。 B.× 13、复铰是连接三个或三个以上刚片的铰 A.√ 14、结构发生了变形必然会引起位移，结构有位移必然有变形发生。 B.×

15、如果梁的截面刚度是截面位置的函数，则它的位移不能用图乘法计算。 A.√ 16、一根连杆相当于一个约束。 A.√ 17、单铰是联接两个刚片的铰。 A.√ 18、连接四个刚片的复铰相当于四个约束。 B.× 19、虚功原理中的力状态和位移状态都是虚设的。 B.× 20、带拉杆三铰拱中拉杆的拉力等于无拉杆三铰拱的水平推力。 A.√ 21、瞬变体系在很小的荷载作用下会产生很大的内力，所以不能作为结构使用。 A.√ 22、一个无铰封闭框有三个多余约束。 A.√ 23、三铰拱的水平推力不仅与三铰的位置有关，还与拱轴线的形状有关。 B.× 24、三铰拱的主要受力特点是：在竖向荷载作用下产生水平反力。 A.√ 25、两根链杆的约束作用相当于一个单铰。 B.× 26、不能用图乘法求三铰拱的位移。 A.√ 27、零杆不受力，所以它是桁架中不需要的杆，可以撤除。 B.× 28、用图乘法可以求等刚度直杆体系的位移。 A.√ 29、连接四个刚片的复铰相当于四个约束。

华农数据结构上机实验答案

华农数据结构上机实验答案

数据结构上机答案 1.1顺序线性表的基本操作 #include #include #define OK 1 #define ERROR 0 #define LIST_INIT_SIZE 100 #define LISTINCREMENT 10 #define ElemType int typedef struct { int *elem,length,listsize; }SqList; int InitList_Sq(SqList &L) { L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType)); L.length=0; L.listsize=LIST_INIT_SIZE; return OK; } int Load_Sq(SqList &L) { int i; if(L.length==0) printf("The List is empty!"); else { printf("The List is:"); for(i=0;iL.length+1) return ERROR; ElemType *newbase,*q,*p; if(L.length>=L.listsize)

{ 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.wendangku.net/doc/3b2290478.html,，将四次上机汇总打印纸版笔试前1周交西1楼711室)；请按时提交注意上交电子版与纸版应一致。 4. 请按照附件给定报告内容格式安排。

国家二级ACCESS机试选择题(数据结构与算法)模拟试卷3

国家二级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 int fun(int *a, int *b) { if (*a*(*b)>0) return(1); else return(0); } main() { int x,y; scanf("%d%d",&x,&y); if (fun(&x,&y)) printf("yes\n"); else printf("no"); } 2、计算1+2+3+……+100，要求用指针进行设计。即设计函数int fun(int *n)实现求 1+2+3+……+*n，在主函数中输入、调用、输出结果。 #include int fun(int *n) { int i,sum=0; for (i=1;i<=*n;i++) sum+=i; return(sum); } main() { int x,sum; scanf("%d",&x); printf("the sum is %d\n",fun(&x)); } 3、函数的功能是求数组a中最大数的位置（位序号）。在主函数中输入10个整数、调用函

数fun、输出结果。 #define N 10 #include void input(int *a,int n) { int i; for (i=0;i*max) max=a+i; return(max-a); } main() {int a[N],maxi; input(a,N); maxi=fun(a,N); printf("\n the max position is %d\n",maxi); } 4、请编写函数fun(int *a,int n, int *odd, int *even),函数的功能是分别求出数组a 中所有奇数之和和所有偶数之和。形参n给出数组中数据的个数；利用指针odd和even分别返回奇数之和和偶数之和。在主函数中输入10个整数、调用函数fun、输出结果。 #define N 10 #include void input(int *a,int n) { int i; for (i=0;i

数据结构书面作业练习题

习题六树和二叉树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所示，其中序遍历的序列为

数据结构上机例题及答案

习题二 ⒉１描述以下四个概念的区别：头指针变量，头指针，头结点，首结点（第一个结点）。解：头指针变量和头指针是指向链表中第一个结点（头结点或首结点）的指针；在首结点之前附设一个结点称为头结点；首结点是指链表中存储线性表中第一个数据元素的结点。若单链表中附设头结点，则不管线性表是否为空，头指针均不为空，否则表示空表的链表的头指针为空。 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，亦称四色猜想），即在为一平 面或一球面的地图着色时，假定每一个国家在地图上是一个连通域，并且有相邻边界线的两个国家必须用不同的颜色，问是否只要四种颜色就可完成着色。现在给定一张地图，要求对这张地图上的国家用不超过四种的颜色进行染色。 要求建立地图的邻接矩阵存储结构，输入国家的个数和相邻情况，输出每个国家的颜色代码。 数组与广义表

经典数据结构上机题_答案解析

数据结构上机实验题目 实验一线性表的顺序存储结构 实验学时 2学时 背景知识:顺序表的插入、删除及应用。 目的要求： 1．掌握顺序存储结构的特点。 2．掌握顺序存储结构的常见算法。 实验容 1．输入一组整型元素序列，建立顺序表。 2．实现该顺序表的遍历。 3．在该顺序表中进行顺序查找某一元素,查找成功返回1,否则返回0。4．判断该顺序表中元素是否对称,对称返回1,否则返回0。 5．实现把该表中所有奇数排在偶数之前,即表的前面为奇数,后面为偶数。 6．输入整型元素序列利用有序表插入算法建立一个有序表。 7．利用算法6建立两个非递减有序表并把它们合并成一个非递减有序表。 8. 利用该顺序结构实现循环队列的入队、出队操作。 8．编写一个主函数,调试上述算法。 #include #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

数据结构上机答案(c语言版)

实习一： 1、编写一个读入一个字符串，把它存入一个链表，并按相反的次序打印的程序。 2、设有一个单位的人员工资有如下信息：name、department、 base pay、allowance、total。现从键盘输入一组人员工资数据并将它们存储到名为paydata的文件中；再从paydata取出工资数据并给每个人的base pay增加100元，增加后将工资数据显示于屏幕(每行1人)。请编写能够完成上述工作的程序。 代码如下： 1.#include #include #include void main() { char x; struct node //定义个结构node { char c; struct node *next; }; struct node *head,*pb,*pf,*p,*s,*t; //定义指针 printf("请输入字符串，按Enter结束！\n"); for(int i=0;x!='\n';i++) { pb=(struct node *)malloc(sizeof(struct node));//动态分配n字节的内存空间 scanf("%c",&pb->c); //输入字符 x=pb->c; if(i==0){ //输入的首个字符作为头结点pf head=pb; pf=head;} else if(pb->c!='\n'){ //如果输入的是Enter，输入终止，否则把字符依次存入链表 pf->next=pb; //把输入的字符pb存在pf后，pb后为空 pb->next=NULL;

数据结构上机考试题

注意事项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 #include #include #define OK 1 #define ERROR 0 #define INFEASIBLE -1 #define OVERFLOW -2 typedef int ElemType; typedef int Status; #define LIST_INIT_SIZE 100 #define LISTTINCREMENT 10 typedef struct{ ElemType *elem; int length; int listsize; }SqList; //创建空顺序表 Status InitList_Sq(SqList &L){ L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType)); if(!L.elem)exit(OVERFLOW); L.length=0; L.listsize=LIST_INIT_SIZE; return OK; } //创建顺序表，插入元素 void ListInput_Sq(SqList &L){ int n,i; printf("input the length of Sqlist:"); scanf("%d",&n); L.length=n; for(i=0;i

结构力学专升本作业题参考答案

结构力学专升本作业题参考答案 一、选择题 1、图示结构中，A 支座的反力矩A M 为（ ）。 A. 0 B. 1kN.m （右侧受拉） C. 2kN.m （右侧受拉） D. 1kN.m （左侧受拉） 答案：C 2、图示组合结构中，杆1的轴力1N F 为（ ）。 A. 0 B. 2 ql - C. ql - D. q 2- q 答案：B 3、图示结构的超静定次数为（ ）。 A. 1 B. 5 C. 6 D. 7 答案：D 4、图示对称结构的半边结构应为（ ）。

答案：A 5、图示结构中， BA M（设左侧受拉为正）为（）。 A. a F P 2 B. a F P C. a F P 3 D. a F P 3 - 答案：C 6、图示桁架中，B支座的反力 HB F等于（）。 A. 0 B. P F 3 - C. P F 5.3 D. P F 5 答案：D 7、图示结构的超静定次数为（）。 A. 1 B. 3 C. 4 D. 5

答案：B 8、图示对称结构的半边结构应为（ ）。 答案：C 二、填空题 1、图示桁架中，有 根零杆。 答案：10 2、图示为虚设的力状态，用于求C 、D 两结点间的 。 答案：相对水平位移 3、超静定刚架结构在荷载作用下采用力法求解时，当各杆EI 值增加到原来的n 倍时，则力法方程中的系数和自由项变为原来的 倍；各杆的内力变为原来的 倍。 答案： n 1 ；1 4、写出下列条件下，等截面直杆传递系数的数值：远端固定=C ，远端铰支=C ，远端滑动 =C 。 答案：2/1；0；1- 5、图示桁架中，有 根零杆。

国家二级MS+Office高级应用机试(数据结构与算法)模拟试卷8

国家二级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 #include #include #include #include #define null 0 #define M 100 //typedef int Elemtype;这里定义了却没用，可见思维不连惯struct Lnode { // int num; char data; struct Lnode *next; }; int lenth(struct Lnode **L) { int n=0; struct Lnode *t; t=*L; while(t!=null) { n++; t=t-> next; } return n; } /* int lenth1(char r[]) { int n=0; n=sizeof(r); return n-1; }*/ void creat(struct Lnode**L) { *L=null; }

//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 next!=null) { t2=t2-> next; j++; } if(j==n-1) { t1-> next=t2-> next; t2-> next=t1; } else { cout < < "Insert error! ";

数据结构上机考试(含答案)

《数据结构》上机练习题 1、设有两个有序序列，利用归并排序将它们排成有序表，并输出。 2、设有一有序序列，从键盘输入一个数，判别是否在序列中，如果在输出“YSE”；否则，将它插入到序列中使它仍然有序，并输出排序后的序列。 3、设有一有序序列，从键盘输入一个数，判别是否在序列中，如果不在，则输出“NO”，否则，将它从序列中删除它，并输出删除后的序列。 4、从键盘输入一组任意数据，建立一个有序链表，并从链头开始输出该链，使输出结果是有序的。 5、从键盘输入一组任意数据，建立一个包含所有输入数据的单向循环链表，并从链表的任意开始，依次输出该链表中的所有结点。 10、设有一个链表，（自己建立，数据从键盘输入），再从键盘输入一个数，判别是否在链表中，如果不在，则输出“NO“，否则，将它从链表中删除，并输出删除后的链表。 11、设有一个链表，（自己建立，数据从键盘输入），再从键盘输入一个数，判别是否在链表中，如果在输出“YSE”，否则，将它从插入到链头，并输出插入后的链表。 12、设有一个链表，（自己建立，数据从键盘输入），再从键盘输入一个数，判别是否在链表中，如果在输出“YSE”，否则，将它从插入到链尾，并输出插入后的链表。 13、编写栈的压栈push、弹栈pop函数，从键盘输入一组数据，逐个元素压入堆栈，然后再逐个从栈中弹出它们并输出。 14、编写栈的压栈push、弹栈pop函数，用它判别（）的匹配问题。 15、按类似先序遍历结果输入一序列，建立一棵二叉树（算法6、4），输出二叉树中序遍历的结果。 16、按类似先序遍历结果输入一序列，建立一棵二叉树（算法6、4），输出二叉树先序遍历的结果。 17、按类似先序遍历结果输入一序列，建立一棵二叉树（算法6、4），输出二叉树后序遍历的结果。 18、按类似先序遍历结果输入一序列，建立一棵二叉树（算法6、4），输出二叉树的总结点数。 19、按类似先序遍历结果输入一序列，建立一棵二叉树（算法6、4），输出二叉树叶子结点数。 20、按类似先序遍历结果输入一序列，建立一棵二叉树（算法6、4），输出此二叉树的高度。 21、给出一个无向图的邻接矩阵，输出各个顶点的度。 22、给出一个有向图的邻接矩阵，输出各个顶点的入度与出度。 23、输入一个有序序列，利用折半查找来查找一个数是否在序列中，如在，则输出其位置，否则输出“NO”。 24、用插入排序方法对一组数据进行排序，并输出每趟排序的结果。 25、用选择排序方法对一组数据进行排序，并输出每趟排序的结果。 26、用希尔（SHELL）排序方法对一组数据进行排序，并输出每趟排序的结果。 27、用快速排序方法对一组数据进行排序，并输出每趟排序的结果。． 答案： 1. #include #include #define N 5 #define NULL 0

数据结构作业及答案汇总

第一章绪论 一、选择题 1.数据结构是一门研究非数值计算的程序设计问题中计算机的1以及它们之间的2和运算等的学科。1 A.数据元素 B.计算方法 C.逻辑存储 D.数据映像 2 A.结构 B.关系 C.运算 D.算法 2.数据结构被形式地定义为(K, R)，其中K是1的有限集，R是K上的2有限集。 1 A.算法 B.数据元素 C.数据操作 D.逻辑结构 2 A.操作 B.映像 C.存储 D.关系 3.在数据结构中，从逻辑上可以把数据结构分成。 A.动态结构和静态结构 B.紧凑结构和非紧凑结构 C.线性结构和非线性结构 D.内部结构和外部结构 4.线性结构的顺序存储结构是一种1的存储结构，线性表的链式存储结构是一种2的存储结构。A.随机存取 B.顺序存取 C.索引存取 D.散列存取 5.算法分析的目的是1，算法分析的两个主要方面其一是指2，其二是指正确性和简单性。1 A.找出数据结构的合理性 B.研究算法中的输入和输出的关系 C.分析算法的效率以求改进 D.分析算法的易懂性和文档性 2 A.空间复杂度和时间复杂度 B.研究算法中的输入和输出的关系 C.可读性和文档性 D.数据复杂性和程序复杂性k 6.计算机算法指的是1，它必须具备输入、输出和2等5个特性。 1 A.计算方法 B.排序方法 C.解决问题的有限运算序列 D.调度方法 2 A.可执行性、可移植性和可扩充性 B.可行性、确定性和有穷性 C.确定性、有穷性和稳定性 D.易读性、稳定性和安全性 7.线性表的逻辑顺序与存储顺序总是一致的，这种说法。A.正确 B.不正确 8线性表若采用链式存储结构时，要求内存中可用存储单元的地址。 A.必须连续的 B.部分地址必须连续的 C.一定是不续的D连续不连续都可以 9.以下的叙述中，正确的是。A.线性表的存储结构优于链式存储结构 B.二维数组是其数据元素为线性表的线性表C.栈的操作方式是先进先出D.队列的操作方式是先进后出10.每种数据结构都具备三个基本运算：插入、删除和查找，这种说法。A.正确B.不正确 二、填空题1.数据逻辑结构包括三种类型、和，树形结构和图形结构合称为。2.在线性结构中，第一个结点前驱结点，其余每个结点有且只有个前驱结点；最后一个结点后续结点，其余每个结点有且只有个后续结点。3.算法的五个重要特性是、、、、。 4.下面程序段的时间复杂度是。 for( i = 0; i < n; i++) for( j = 0; j < m; j++) A[i][j] = 0; 5.下面程序段的时间复杂度是。 i = s = 0; while ( s < n) { i ++; /* i = i +1*/ s += i; /* s = s + i*/ } 6.下面程序段的时间复杂度是。 s = 0; for( i = 0; i < n; i++) for( j = 0; j < n; j++) s += B[i][j]; sum = s; 7.下面程序段的时间复杂度是。 i = 1; while ( i <= n ) i = i * 3;