数据结构期末考试试题及答案

1 下列数据结构中，能用二分法进行查找的是__A____。 A、顺序存储的有序线性表 B、线性链表 C、二叉链表 D、有序线性链表 解析：二分法查找只适用于顺序存储的有序表。在此所说的有序表是指线性表中的元素按值非递减排列(即从小到大，但允许相邻元素值相等)。 2 在软件设计中，不属于过程设计工具的是__D____。 A、PDL(过程设计语言) B、PAD图 C、N-S图 D、DFD图 解析：软件设计工具包括：程序流程图、N-S、PAD、HIPO，判定表，PDL(伪码)。而DFD(数据流图)属于结构化分析工具。 3 在switch(expression)语句中，expression的数据类型不能是__A____。 A、double B、char C、byte D、short 解析：表达式expression只能返回这个几种类型的值：int、byte、short和char。多分支语句把表达式返回的值依次与每个case子句中的值相比较，如果遇到匹配的值，则执行该case子句后的语句序列。 4 下列叙述中，错误的是__D____。 A、父类不能替代子类 B、子类能够替代父类 C、子类继承父类 D、父类包含子类 5 通过继承实现代码复用： Java中所有的类都是通过直接或间接地继承类得到的。继承而得到的类称为子类，被继承的类称为父类。子类不能继承父类中访问权限为private的成员变量和方法，子类可以重写父类的方法，及命名与父类同名的成员变量。 子类通过隐藏父类的成员变量和重写父类的方法，把父类的状态和行为改变为自身的状态和行为。注意：子类中重写的方法和父类中被重写的方法要具有相同的名字，相同的参数表和相同的返回类型，只是函数体不同。 由于子类继承了父类所有的属性(私有的除外)，所以子类对象可以作为父类对象使用。程序中凡是使用父类对象的地方，都可以用子类对象来代替。一个对象可以通过引用子类的实例来调用子类的方法。 java运行时系统根据调用该方法的实例，来决定调用哪个方法。对子类的一个实例，如果子类重写了父类的方法，则运行时系统调用子类的方法;如果子类继承了父类的方法(未重写)，则运行时系统调用父类的方法。 6 自定义表格类中的model部分应实现的接口是___A___。 A、AbstractTableModel B、JTable C、TableModel D、TableModelable 7 下列代码中，将引起编译错误的行是__B____。 1)public class Exercise{ 2) public static void main(String args[]){ 3) float f=; 4) f+=; 5) } 6) } A、第2行 B、第3行 C、第4行 D、第6行 解析：float定义变量赋值时，需要在数值后面加f以标识它为浮点型，让系统知道该给它精确到多少位。

1.内部排序和外部排序 2.邻接表和十字连结串列 3.线性表，树，图 5.θ（n），θ（lg n），θ（n lg n） 6.直接定址法，随机法 7.连结串列 8.根节点0，叶节点4,9,10,7,8，最大度的是0，节点0的后代是1,2,3 9.空的条件栈顶位置是m-1.满的条件是栈顶位置是-1 10，资料结构和抽象资料型别关系：a.“资料结构”定义为一个二元组（D，S），即两个集合，D是资料元素的集合，S是资料元素之间一个或多个关系的集合。 b.“抽象资料型别”本质是“资料型别”，与计算机相关，涉及资料的储存及如何用储存来反应资料元素之间的关系。它定义为一个三元组（D，S，P），加上的P是定义的一组针对储存的资料操作（如插入，删除，排序等）。 c.总之“抽象资料型别”是“物理”概念，“资料结构”是“逻辑”概念。“抽象资料型别”来实现“资料结构”。 以上回答你满意么？

1.内部排序和外部排序 2.邻接表和十字连结串列 3.线性表，树，图 5.θ（n），θ（lg n），θ（n lg n） 6.直接定址法，随机法 7.连结串列 8.根节点0，叶节点4,9,10,7,8，最大度的是0，节点0的后代是1,2,3 9.空的条件栈顶位置是m-1.满的条件是栈顶位置是-1 10，资料结构和抽象资料型别关系：a.“资料结构”定义为一个二元组（D，S），即两个集合，D是资料元素的集合，S是资料元素之间一个或多个关系的集合。 b.“抽象资料型别”本质是“资料型别”，与计算机相关，涉及资料的储存及如何用储存来反应资料元素之间的关系。它定义为一个三元组（D，S，P），加上的P是定义的一组针对储存的资料操作（如插入，删除，排序等）。 c.总之“抽象资料型别”是“物理”概念，“资料结构”是“逻辑”概念。“抽象资料型别”来实现“资料结构”。 希望对你能有所帮助。

《资料结构》试题一、选择题（每小题2分，共30分）1． 若某线性表中最常用的操作是取第i 个元素和找第i个元素的前趋元素，则采用（ ）储存方式最节省时间。A、单链表 B、双链表 C、单向回圈 D、顺序表2． 串是任意有限个（ ）A、符号构成的序列 B、符号构成的集合C、字元构成的序列 D、字元构成的集合3． 设矩阵A（aij ，l≤i,j≤ 10）的元素满足：aij≠0(i≥j, l≤i, j≤ 10)aij=0 (i。( )i6．对有向图G，如果从任一顶点出发进行一次深度优先或广度优先搜寻就能访问每个顶点，则该图一定是完全图。( )7．“顺序查询法”是指在顺序表上进行查询的方法。（ ）8．向二叉排序树插入一个新结点时，新结点一定成为二叉排序树的一个叶子结点。（）9．键值序列{A，C，D，E，F，E，F}是一个堆。10．二路归并时，被归并的两个子序列中的关键字个数一定要相等。（） 三、填空题（每小题2分，共20分）1．在带有头结点的单链表L中，若要删除第一个结点，则需执行下列三条语句：＿＿＿＿＿＿＿＿；L->next=U->next；free(U)；2．有一个长度为20的有序表采用二分查询方法进行查询，共有＿＿＿＿＿＿个元素的查询长度为3。3．采用气泡排序对有n个记录的表A按键值递增排序，若L的初始状态是按键值递增，则排序过程中记录的比较次数为＿＿＿＿＿。若A的初始状态为递减排列，则记录的交换次数为＿＿＿＿＿＿＿。4．在无头结点的双链表中，指标P所指结点是第一个结点的条件是＿＿＿＿＿＿。5．G为无向图，如果从G的某个顶点出发，进行一次广度优先搜寻，即可访问图的每个顶点，则该图一定是＿＿＿＿＿图。6．如果一个有向图中没有＿＿＿＿＿＿，则该图的全部顶点可能排成一个拓扑序列。7．深度为8（根的层次号为1）的满二叉树有＿＿＿＿＿＿个叶子结点。 8．将一棵有100个结点的完全二叉树按层编号，则编号为49的结点X，其双亲PARENT（X）的编号为＿＿＿＿＿＿＿。9．设某闭散列表HT未满，杂凑函式H（KEY）为键值第一字母在字母表中的序号，处理冲突方法为线性探测法，请在下列演算法划线处填上适当内容，以实现按键值第一字母的顺序输出闭散列表中所有键值的演算法。void prinord(keytype HT[m]) { for(i=1;i<=26;i++) { j=i; while(____________________) { if (____________________) printf(“datatype”,HT[j]); j=(j+1)% m; } } }10．设有一个链队，结点结构为data|next，front为队头指标，rear为队尾指标，当执行入队操作时需执行下列语句：malloc(p)；p->data=x; p->next=NULL；＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿；＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿； 四、简答题：（每小题4分，共20分）1. 对于一个有10000个结点的二叉树，树叶最多有多少个？最少有多少个？2. 已知一棵二叉树的中序序列和后序序列分别为： DBGEACHF和DGEBHFCA，则该二叉树的前序序列是什么？3. 设有1000个无序的元素，需排出前10个最大（小）的元素，你认为采用哪种排序方法最快？为什么？4. 在KMP演算法中，已知模式串为ADABCADADA ，请写出模式串的next[j]函式值。5. 中序遍历的递回演算法平均空间复杂度为多少？ 五、 演算法设计题（每小题10分，共20分）1. 试编写一个演算法，判断一给定的整型阵列a[n]是不是一个堆。2. 一棵二叉树的繁茂度定义为各层结点数的最大值与树的高度的乘积。试写一高效演算法，求二叉树的繁茂度。参考答案一、选择题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、B14、C15、D二、判断题 1. √ 2. × 3. √ 4. √ 5. × 6. × 7. × 8. √ 9. √ 10. × 三、填空题1．U=L - > next2．4。3．n-1、n(n-1)/2。4．p - > prior = NULL。5．连通6．回路或环7．28-1 = 27 = 1288．249．HT[j]!=NULL或HT[j]不为空、H(HT[j])=I10．rear - > next = p、rear = p四、简答题：1. 答： 最多是完全二叉树的形态，即5000个叶子；最少是单支树的形态，即1个叶子。2.答：是：ABDEGCFH3. 答：用锦标赛排序或堆排序很合适，因为不必等全部元素排完就能得到所需结果，时间效率为O(nlog2n)； 即O（1000log21000）=O(10000) 锦标赛排序的准确比较次数为：n-1+9log2n=999+9log21000=999+9×10=1089堆排序的准确比较次数为：n-1+9log2n=999+9log21000=999+9×10=1089若用气泡排序也较快，最多耗费比较次数为（n-1+n-2+……＋n-10）=10n-55=10000-55=9945（次）4. 答： 01121123435. 答： 要考虑递回时占用了栈空间，但递回次数最多不超过树的高度，所以空间复杂度为O(log2n) 五、 演算法设计题1.解：提示：堆的定义是：kia[2*i]|| a[i]>a[2*i+1])return(-1);return(minleap)};else { for( i=1; i<=n/2; i++) if (a[i]lchild) EnQueue(Q,{>lchild, }); if(>rchild) EnQueue(Q,{>rchild, }); } 按层序入队时要随时标注结点所在层号 h=; 最后一个伫列元素所在层就是树的高度 for(maxn=count[0], i=1; h; i++) if(count[i]>maxn) maxn=count[i]; 求出哪一层结点数最多 return (h*maxn)} Width

我有资料结构那本书的答案，不知道你需不需要，需要的话发讯息联络。

嗨，你好！ 网壳是网架的曲面表现形式。网壳结构又包括单层网壳结构、预应力网壳结构、板锥网壳结构、肋环型索承网壳结构、单层叉筒网壳结构等。 ( l ）强度、刚度分析 网壳结构的内力和位移可按弹性阶段进行计算。网壳结构根据网壳型别、节点构造，设计阶段可分别选用不同的方法进行内力、位移计算： l ）双层网壳宜采用空间杆系有限元法进行计算； 2 ）单层网壳宜采用空间梁系有限元法进行计算； 3 ）对单、双层网壳在进行方案选择和初步设计时可采用拟壳分析法进行估算。 网壳结构的外荷载可按静力等效的原则将节点所辖区域内的荷载集中作用在该节点上。分析双层网壳时可假定节点为铰接，杆件只承受轴向力；分析单层网壳时假定节点为刚接，杆件除承受轴向力外，还承受弯矩、剪力等。当杆件上作用有区域性荷载时，必须另行考虑区域性弯曲内力的影响。对于单个球面网壳、圆柱面网壳和双曲抛物面网壳的风载体型系数，可按《建筑结构荷载规范》（GB 50009 一2001 ) 取值；对于多个连线的球面网壳、圆柱面网壳和双曲抛物面网壳，以及各种复杂体形的网壳结构，应根据模型风洞试验确定风载体型系数。 ( 2 ）稳定性分析 网壳的稳定性可按考虑几何非线性的有限元分析方法（荷载认一位移全过程分析）进行计算，分析中可假定材料保持为线弹性。用非线性理论分析网壳稳定性时，一般采用空间杆系非线性有限元法，关键是临界荷载的确定。单层网壳宜采用空间梁系有限元法进行计算。 球面网壳的全过程分析可按满跨均布荷载进行，圆柱面网壳和椭圆抛物面网壳宜补充考虑半跨活荷载分布。进行网壳全过程分析时应考虑初始曲面形状的安装偏差影响；可采用结构的最低屈曲模态作为初始缺陷分布模态，其最大计算值可按网壳跨度的1 /300 取值。 进行网壳结构全过程分析求得的第一个临界点处的荷载值，可作为该网壳的极限承载力。将极限承载力除以系数K 后，即为按网壳稳定性确定的容许承载力（标准值）。 ( 3 ）抗震分析 在设防烈度为7 度的地区，网壳结构可不进行竖向抗震计算，但必须进行水平抗震计算。在设防烈度为8 度、9 度地区必须进行网壳结构水平与竖向抗震计算。 摘录 百科

可以考试的，报班意义不大。把重要的知识点整理一下，准备好笔记本和错题集，错题集用来记录自己做错的题，笔记本记录一些容易忽略细节和重点。 做题不一定要做难题，基础是根本，每次考试不要着重在一个题目上，要放宽心态，不要急，总之，要自信，相信自己一定可

《资料结构》期末考试试卷（ A ） 一、 选择题（每小题2分，共24分） 1．计算机识别、储存和加工处理的物件被统称为( A ) A.资料 B.资料元素 C.资料结构 D.资料型别 2．栈和伫列都是（ A ） A．限制存取位置的线性结构 B．顺序储存的线性结构 C．链式储存的线性结构 D．限制存取位置的非线性结构 3．链栈与顺序栈相比，比较明显的优点是( D ) A.插入操作更加方便 B.删除操作更加方便 C.不会出现下溢的情况 D.不会出现上溢的情况 4．采用两类不同储存结构的字串可分别简称为( B ) A.主串和子串 B.顺序串和链串 C.目标串和模式串 D.变数串和常量串 5． 一个向量第一个元素的储存地址是100，每个元素的长度为2，则第5个元素的地址是：B A. 110 B .108 C. 100 D. 120 6．串是一种特殊的线性表，其特殊性体现在：B A.可以顺序储存 B .资料元素是一个字元 C. 可以连结储存 D. 资料元素可以是多个字元 7．设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为： C A. 2h B .2h-1 C. 2h+1 D. h+1 软体开发网 mscto. 8．树的基本遍历策略可分为先根遍历和后根遍历；二叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历。这里，我们把 由树转化得到的二叉树叫做这棵树对应的二叉树。下列结论哪个正确？ A A. 树的先根遍历序列与其对应的二叉树的先序遍历序列相同 B .树的后根遍历序列与其对应的二叉树的后序遍历序列相同 C. 树的先根遍历序列与其对应的二叉树的中序遍历序列相同 D. 以上都不对 9．一个有n个顶点的无向图最多有多少边？C A. n B .n(n-1) C. n(n-1)/2 D. 2n 10．在一个图中，所有顶点的度数之和等于所有边数的多少倍?C A. 1/2 B .1 C. 2 D. 4 11．当在二叉排序树中插入一个新结点时，若树中不存在与待插入结点的关键字相同的结点，且新结点的关键字小于根结点的关键字，则新结点将成为（ A ） A．左子树的叶子结点 B．左子树的分支结点 C．右子树的叶子结点 D．右子树的分支结点 软体开发网 mscto. 12．对于杂凑函式H(key)=key%13,被称为同义词的关键字是( D ) 和41 和39 和44 和51 二、已知某棵二叉树的前序遍历结果为A,B,D,E,G,C,F,H,I,J，其中中序遍历的结果为D,B,G,E,A,H,F,I,J,C。请画出二叉的具体结构。（注意要写出具体步骤）（10分） 原理见课本128页 三、有图如下，请写出从顶点c0出发的深度优先及宽度优先遍历的结果。(10分) 深度优先；C0-C1-C3-C4-C5-C2 宽度优先：C0-C1-C2-C3-C4-C5 四、有图如下，按Kruskal演算法求出其最小生成树。要求写出完整的步骤。（10分） 原理见课本250页 五、给定线性表（12，23，45，66，76，88，93，103，166），试写出在其上进行二分查询关键字值12，93，166的过程。并写出二分查询的演算法。（20分） 0 1 2 3 4 5 6 7 8 12 23 45 66 76 88 93 103 166 过程： mid=(0+8)/2=4 high=3,low=0 mid=1 high=0,low=0 mid=0（找到12） high=8,low=5,mid=6（找到93） high=8,low=7,mid=7 high=8 low=8 mid=8 演算法：见课本84页上 六、知单链表的结点结构为 Data next 下列演算法对带头结点的单链表L进行简单选择排序，使得L中的元素按值从小到大排列。 请在空缺处填入合适的内容，使其成为完整的演算法。 (可用文字说明该演算法的基本思想及执行的过程，10分) void SelectSort(LinkedList L) { LinkedList p,q,min; DataType rcd; p= (1) ; while(p!=NULL) { min=p; q=p->next; while(q!=NULL){ if( (2) )min=q; q=q->next; } if( (3) ){ rcd=p->data; p->data=min->data; min->data=rcd; } (4) ; } } 本题不会。嘿嘿。。。。 七、一个完整的演算法应该具有哪几个基本性质？分别简要说明每一性质的含意。(5分) 输入： 四个基本性质：1.输入：有零个或多个有外部提供的量作为演算法的输入 2：输出：演算法产生至少一个量作为输出 3.：确定性：组成演算法的每条指令是清晰的，无歧异的。 4.：有限性：演算法中每条指令的执行次数是有限的，执行每条指令的时间也是有限的 八、何谓伫列的"假溢"现象？如何解决？（5分） 伫列的假溢现象是指阵列实现的顺序伫列中，队尾指标已到达阵列的下表上界产生上溢而队头指标之前还有若干 空间闲置的现象。解决的办法之一是利用回圈伫列技术使阵列空间的首尾相连。 九、说明并比较档案的各种物理结构。（6分）

#include <> #include <> typedef struct lnode { int data; struct lnode *next; }lnode,*linklist; linklist listinsert_l(linklist l,int i,int e) { linklist p,s; int j; p=l; j=0; while(p&&jnext; ++j; } if(!p||j>i-1) exit(0); s=(linklist)malloc(sizeof(lnode)); s->data=e; s->next=p->next; p->next=s; l=l->next; printf("插入后的连结串列为：\n"); while(l) { printf("%d ",l->data); l=l->next; } return 0; } int listdelete_l(linklist l,int i,int b) { linklist p,q; int j; p=l; j=0; while(p->next&&jnext; ++j; } if(!(p->next)||j>i-1) exit(0); q=p->next; p->next=q->next; b=q->data; free(q); l=l->next; printf("删除后的连结串列为：\n"); while(l) { printf("%d ",l->data); l=l->next; } return b; } void main() { linklist l,p; int n,i,e,j,a,b; printf("输入结点的个数：\n"); scanf("%d",&n); l=(linklist)malloc(sizeof(lnode)); l->next=NULL; printf("输入连结串列的资料：\n"); for(i=n;i>0;--i) { scanf("%d",&a); p=(linklist)malloc(sizeof(lnode)); p->data=a; p->next=l->next; l->next=p; } printf("输入要插入的位置和数：\n"); scanf("%d%d",&j,&e); listinsert_l(l,j,e); printf("\n输入要删除的位置：\n"); scanf("%d",&i); b=listdelete_l(l,i,b); printf("\n删除的数为：%d\n",b); }

D,连结串列的话

资料下载网址：大学空间站（百度不让回答有网址的贴，所以没法给准确的资料地址） 下载方法：百度搜索下“大学空间站”，开启该网，注册大学空间站会员，下载。、、、、、、、、