数据结构试卷（资料结构试题求正确答案）

本文目录

• 资料结构试题求正确答案
• 《数据结构》第02章
• 《数据结构》第08章在线测试
• 谁有数据结构的期末试题，借我参考下马上考试了
• 求试卷和答案,2010年10月自学考试数据结构导论的.
• 求：2005年下半年北京市高等教育自学考试数据结构试卷
• 数据结构试卷
• 《数据结构》第06章在线测试

资料结构试题求正确答案

资料结构试题求正确答案

1.内部排序和外部排序 2.邻接表和十字连结串列 3.线性表，树，图 4.63 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.线性表，树，图 4.63 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《j, l≤i, j≤ 10)现将A的所有非0元素以行序为主序存放在首地址为2000的储存区域中，每个元素占有4个单元，则元素A; 求出哪一层结点数最多 return (h*maxn)} Width

谁有资料结构期末试题及答案?

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

结构中有个网壳结构··求正确答案

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

求网计(专升本)《资料结构》试题(模A) 2004-5-1答案

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

资料结构（C#语言版）笔试试题与答案

《资料结构》期末考试试卷（ 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 ) A.35和41 B.23和39 C.15和44 D.25和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 《stdio.h》 #include 《stdlib.h》 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&&j《i-1) { p=p-》next; ++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&&j《i-1) { p=p-》next; ++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,连结串列的话

求资料结构习题集答案

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

《数据结构》第02章

《数据结构》第02章在线测试 剩余时间： 55:29 答题须知：1、本卷满分20分。 2、答完题后，请一定要单击下面的“交卷”按钮交卷，否则无法记录本试卷的成绩。 3、在交卷之前，不要刷新本网页，否则你的答题结果将会被清空。 第一题、单项选择题（每题1分，5道题共5分） 1、线性表的顺序存储结构是一种＿＿＿＿B＿＿＿＿的存储结构。 A、顺序存取 B、随机存取 C、索引存取 D、散列存取 2、单链表是一种＿＿＿＿＿A＿＿＿的存储结构。 A、顺序存取 B、随机存取 C、索引存取 D、散列存取 3、有头结点的单链表（head为头指针）是空表的条件是＿＿＿＿A＿＿＿ A、head-＞next＝＝NULL; B、head＝＝NULL; C、head-＞next＝＝head; D、head-＞next-＞next＝＝ NULL; 4、非空的循环单链表(head为头指针)的尾结点（由指针p所指示）应满足＿＿＿＿＿＿C＿＿。 A、p-＞next＝＝NULL; B、p＝＝NULL; C、p-＞next＝＝head; D、v 5、若在线性表的任何位置上删除元素的概率是相等的，那么在长度为n的顺序表中删除一个元素时需平均移动＿＿＿＿B＿＿＿＿个元素。 A、n B、(n-1)/2 C、n/2 D、(n+1)/2 第二题、多项选择题（每题2分，5道题共10分） 1、在线性表的下列存储结构中，读取元素花费时间相同的是＿＿＿BCD＿＿＿＿＿。 A、顺序结构 B、单链表 C、双向链表 D、循环链表 2、顺序表的特点是＿＿＿＿ADFG＿＿＿＿。 A、随机存取 B、顺序存取 C、元素间的逻辑关系由指针指示 D、插入删除元素时需要移动表中元素 E、插入删除元素时不必移动元素，只须修改指针 F、数据元素在存储器内的物理位置顺序与它们的逻辑顺序一定相同 G、元素间的逻辑关系隐含在存储位置中 3、下列链表中，能从当前结点出发访问到表中其余各结点的有＿＿CDE＿＿＿＿＿＿。 A、带头结点的单链表 B、不带头结点的单链表 C、带头结点的循环链表 D、不带头结点的循环链表 E、双向链表 4、在双向循环链表中，若s是指向表中某结点的指针，则＿＿＿BC＿＿＿＿＿。 A、s-＞next＝＝s B、s-＞next-＞prior＝＝s C、s-＞prior-＞next ＝＝s D、s-＞ prior＝＝s 5、在双向链表中，每个结点有两个指针域，分别指向＿＿＿BC＿＿＿＿＿。 A、其自身 B、其直接前驱结点 C、其直接后继结点 D、头结点 第三题、判断题（每题1分，5道题共5分） 1、在单链表中插入或删除元素时是以结点的指针变化来反映逻辑关系的变化，因此不需要移动元素。T 正确 错误 2、顺序表能够以元素在计算机内的物理位置的相邻性来表示线性表中元素之间的逻辑关系。T 正确 错误 3、在循环链表中设尾指针比设头指针方便。 （ T） 正确 错误 4、单链表的头结点表示的是线性表中的第一个元素。F 正确 错误 5、顺序表中插入或删除元素时是以元素的移动来反映逻辑关系的变化的。T 正确 错误

《数据结构》第08章在线测试

《数据结构》第08章在线测试 剩余时间： 48:55 答题须知：1、本卷满分20分。 2、答完题后，请一定要单击下面的“交卷”按钮交卷，否则无法记录本试卷的成绩。 3、在交卷之前，不要刷新本网页，否则你的答题结果将会被清空。 第一题、单项选择题（每题1分，5道题共5分） 1、下列方法中，＿＿＿A＿＿＿＿＿算法的时间复杂度为O(n^2)。 A、直接插入排序 B、希尔排序 C、快速排序 D、堆排序 2、在待排序的元素序列基本有序的前提下，效率最高的排序方法是＿＿＿＿＿＿A＿。 A、直接插入排序 B、起泡排序 C、快速排序 D、堆排序 3、在下列排序方法中，平均情况下占用内存量最大的是＿＿＿A＿＿＿＿方法。 A、快速排序 B、插入排序 C、冒泡排序 D、堆排序 4、下列序列中，＿＿＿＿A＿＿＿＿是堆。 A、{12，35，20，60，40，30} B、{100，85，120，38，10，9，36} C、{1，5，6，24，7，3，4 } D、{38，24，15，20，30，46} 5、在下列排序方法中，在待排序的数据有序时, 花费时间反而最多的是＿＿C＿＿＿＿＿。 A、堆排序 B、起泡排序 C、快速排序 D、插入排序 第二题、多项选择题（每题2分，5道题共10分） 1、下列方法中，＿＿＿BD＿＿＿＿＿算法的时间复杂度为O(n^2)。 A、希尔排序 B、冒泡排序 C、快速排序 D、直接插入排序 2、下列方法中，＿＿BC＿＿＿＿＿＿算法的时间复杂度为O(nlogn)。 A、希尔排序 B、堆排序 C、快速排序 D、简单选择排序 E、直接插入排序 3、下列排序方法中，空间复杂度为O(1)的排序方法有＿＿＿＿ACD＿＿＿＿。 A、堆排序 B、快速排序 C、直接插入排序 D、冒泡排序 4、下列排序方法中，在最坏情况下算法的时间复杂度为O(n^2)的有＿BCD＿＿＿＿＿＿＿。 A、堆排序 B、快速排序 C、希尔排序 D、冒泡排序 5、下列排序方法中，不稳定的排序方法有＿＿＿ABC＿＿＿＿＿。 A、希尔排序 B、快速排序 C、堆排序 D、直接插入排序 第三题、判断题（每题1分，5道题共5分） 1、快速排序的速度在所有排序方法中是最快的，而且所需的附加空间也最少。 正确 F 错误 2、在一个大顶堆中，最小元素不一定在最后。 正确 T 错误 3、对一个堆按层次遍历，一定能得到一个有序序列。 正确 F 错误 4、由于希尔排序的最后一趟与直接插入排序过程相同，所以前者一定比后者花费的时间多。 正确 F 错误 5、在堆排序过程中，在输出一个根之后的调整过程中，“临时根”结点的值将会最终被放到“叶子结点”上。 正确 F 错误

谁有数据结构的期末试题，借我参考下马上考试了

A：06－07第一学期期末考试试卷 试卷代码：03266A 授课课时：112课程名称：数据结构与算法 适用对象：本科 一、单项选择题(从下列各题四个备选答案中选出一个正确答案，并将其代号写在答题纸相应位置处。答案错选或未选者，该题不得分。每小题2分，共24分。)1.数据结构被形式地定义为(K,R)，其中K是数据元素的有限集，R是K上的___有限集。 A.操作 B.映像 C.存储 D.关系2.线性表若采用链式存储结构时，要求内存中可用存储单元的地址____。 A.必须连续的 B.部分地址必须连续的 C.一定是不续的 D.连续不连续都可以3.一个栈的入栈序列是a、b、c、d、e，则栈的不可能输出序列是____。 A.edcba B.decba C.dceab D.abcde4.一个队列的入队序列是1、2、3、4，则队列输出序列是____。 A.4、3、2、1 B.1、2、3、4 C.1、4、3、2 D.3、2、4、15.栈和队列的共同点是____。A.都是先进后出 B.都是先进先出 C.只允许在端点处插入、删除元素 D.没有共同点6.在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q和p之间插入s结点，则执行____。A. s-》next = p-》next; p-》next=s; B. p-》next = s-》next; s-》next = p;C. q-》next = s; s-》next = p; D. p-》next = s; s-》next = q;7.设串s1=‘ABCDEFG’，s2=‘PQRST’，函数con (x, y) 返回x与y串的连接串，函数subs (s, i, j) 返回串s的从序号i的字符开始的j个字符组成的子串，函数len (s) 返回串s的长度，则con (subs (s1, 2, len (s2)), subs (s1, len (s2), 2)) 的结果串是____。A. BCDEF B. BCDEFG C. BCPQRST D. BCDEFEF8.设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为____。A. 2h B. 2h-1 C. 2h +1 D. h +19.某二叉树的前序遍历结点访问顺序是abdgcefh，中序遍历结点访问顺序是dgbaechf，则其后序遍历结点访问顺序是____。A. bdgcefha B. gdbecfha C. bdgaechf D. gdbehfca10.具有6个顶点的无向图至少应有____条边才能确保是一个连通图。A. 5 B. 6 C. 7 D. 811.采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为–。A. n B. n/2 C. (n+1)/2 D. (n-1)/212.排序方法中，从未排序序列中挑选元素，并将其依次放入已排序序列(注：初始时为空)的一端的方法，称为____。A. 希尔排序 B. 归并排序 C. 插入排序 D. 选择排序二、填空题(请在每小题的横线上填入正确内容，每空1分，共7分。)1.在树形结构中，树根结点没有 结点，其余每个结点有且只有 个前驱结点。2.对n个元素的序列进行起泡排序时，最少的比较次数是 。3.空串是 ，其长度等于0。4.一棵有n个结点的满二叉树共有 个叶子结点。5.在散列函数H(key)=key % p中，p应取 。6.已知模式串t=‘abcaabbabc’， 其用KMP法求得的每个字符对应的next函数值为 。三、简答题(本大题共3小题，每小题5分，共15分)1.在对线性表的处理中一般使用两种存储结构，顺序存储结构和链式存储结构。试叙述在什么情况下使用顺序表比链表好？2.简述什么是稳定的排序，什么是不稳定的排序。3.下列中缀表达式对应的后缀形式是什么？(1) (A + B) * D + E / (F + A * D) + C(2) A && B|| ! (E 》 F){注：按C的优先级)四、判断题(本大题共10小题，命题正确的在题后括号内写 “T”，错误的在题后括号内写“F”，每小题1分，共10分)1.数据元素不是数据的最小单位( )。2.已知一棵二叉树的前序序列和后序序列可以唯一地构造出该二叉树。( )3.AOE网是一种带权的无环连通图。( )4.对于同一组待输入的关键码集合，虽然各关键码的输入次序不同，但得到的二叉搜索树都是相同的( )。5.一棵树中的叶子数一定等于与其对应的二叉树的叶子数。( )6.邻接表只能用于有向图的存储，邻接矩阵对于有向图和无向图的存储都适用。( )7.折半插入排序是稳定的。( )8.在散列法中，使用双散列函数可保证绝对不产生冲突。( )9.消除递归不一定需要使用栈( )10.堆排序是交换排序的一种。( )五、分析应用题（本题共26分，1、4小题各6分，2、3小题各7分）1．阅读后分析下面程序段的功能是什么? （6分）SeqStack S1, S2, tmp;DataType x; //设栈tmp和S2已做过初始化while ( ! StackEmpty (S1)){ x=Pop(S1) ;Push(tmp,x);}while ( ! StackEmpty (tmp) ){ x=Pop(tmp);Push( S2, x); }2.某子系统在通信联络中只可能出现8种字符，其出现的概率分别为0.05，0.29，0.07，0.08，0.14，0.23，0.03，0.11试设计赫夫曼编码。（7分）3.设散列表为HT, 散列函数为 H (key) = key %13。用线性探测再散列法解决冲突, 对下列关键码序列 12, 23, 45, 57, 20, 03, 78, 31, 15, 36 造表。画出相应的散列表, 并计算等概率下搜索成功的平均搜索长度。（7分）4.设待排序的排序码序列为{12, 2, 16, 30, 28, 10, 16*, 20, 6, 18}, 试写出使用希尔排序(增量为5,2,1)方法每趟排序后的结果。（6分） 六、算法设计题（本题共18分，第1小题10分，第2小题8分）1.编写一个算法frequency，统计在一个输入字符串中所含各个不同字符出现的频度。用适当的测试数据来验证这个算法。(10分)2.在一棵以二叉链表表示的二叉树上，试写出用按层次顺序遍历二叉树的方法，并统计树中具有度为1的结点数目的算法。要求给出二叉链表的类型定义。(8分)答案：06－07第一学期期末考试参考答案与评分标准 试卷代码：03266A 授课课时：112课程名称：数据结构与算法 适用对象：本科 一、单项选择题(每小题2分，共24分。)1. D 2. D 3. C 4. B 5. C 6. C7. D 8. B 9. D 10. A 11. C 12. D二、填空题(每空1分，共7分。)1.父(或前驱)， 1 2. n-1 3. 不包含任何字符的串 4. (n+1)/2 5. 素数 6. 0111223123 三、简答题(每小题5分，共15分)1.答：① 顺序存储时，相邻数据元素的存放地址也相邻(逻辑与物理统一)；要求内存中可用存储单元的地址必须是连续的。优点：存储密度大，存储空间利用率高。缺点：插入或删除元素时不方便。②链式存储时，相邻数据元素可随意存放，但所占存储空间分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针优点：插入或删除元素时很方便，使用灵活。缺点：存储密度小(《1)，存储空间利用率低。顺序表适宜于做查找这样的静态操作；链表宜于做插入、删除这样的动态操作。若线性表的长度变化不大，且其主要操作是查找，则采用顺序表；若线性表的长度变化较大，且其主要操作是插入、删除操作，则采用链表。2.答：在排序序列中，任何两个相等的关键字Ki=Kj,如果在排序前的序列中Ki领先于Kj，若在排序后的序列中Ki仍领先于Kj，则称所用的排序方法是稳定的；反之，若可能使排序后的序列中Kj领先于Ki，则称所用的排序方法是不稳定的。3.答：各中缀表达式的后缀形式如下： (1)AB+D*EFAD*+/+C+ (2)AB&&EF》!||四、判断题(本大题共10小题，命题正确的在题后括号内写 “T”，错误的在题后括号内写“F”，每小题1分，共10分)1.T2.F3.T4.F5.F6.F7.T8.F9.T10.F五、分析应用题（1、4小题各6分，2、3小题各7分）1．（6分）答：程序段的功能是利用tmp栈将一个非空栈s1的所有元素按原样复制到一个栈s2当中去。2．（7分）答：为方便起见，设各种字符的权值w={5,29,7,8,14,23,3,11}。因为n=8，所以要构造的赫夫曼树共有m=2n-1=2*8-1=15个结点。生成的赫夫曼树为下图所示：赫夫曼编码为：概率为0.23的字符编码为：00　　　　　　　概率为0.11的字符编码为：010概率为0.05的字符编码为：0110概率为0.03的字符编码为：0111概率为0.29的字符编码为：10 概率为0.14的字符编码为：110 概率为0.07的字符编码为：1110 概率为0.08的字符编码为：11113.（7分）答：使用散列函数H(key)=key mod 13 有：H（12）=12， H（23）=10，H（45）=6，H（57）=5，H（20）=7，H（03）=3，H（78）=0，H（31）=5，H（15）=2，H（36）=10利用线性探查法造表：0123456789101112781503574520312336121111114121搜索成功的平均搜索长度为：ASL=1/10（1+1+1+1+1+1+4+1+2+1）=14/10 4.（6分） 答： 希尔排序(增量为5,2,1)六、算法设计题（第1小题10分，第2小题8分）1. (10分) include 《iostream.h》 include”string.h” int charnumber=128; void frequency(string&s,int C){ for(int i=0;i《 charnumber;i++) C=0; for( i=0;i《 s.length();i++) C++; for( i=0;i《 charnumber;i++) if(C《《”\t”; }2. (8分)类型定义（略）int Level(BiTree bt) //层次遍历二叉树，并统计度为1的结点的个数{int num=0; //num统计度为1的结点的个数 if(bt){QueueInit(Q); QueueIn(Q,bt)；//Q是以二叉树结点指针为元素的队列 while(!QueueEmpty(Q)){ p=QueueOut(Q); printf(p-》data); //出队,访问结点if(p-》lchild && !p-》rchild ||!p-》lchild && p-》rchild)num++;//度为1的结点if(p-》lchild) QueueIn(Q,p-》lchild); //非空左子女入队if(p-》rchild) QueueIn(Q,p-》rchild); //非空右子女入队} } return(num); //返回度为1的结点的个数 } B：06－07第一学期期末考试试卷 试卷代码：03266B 授课课时：112课程名称：数据结构与算法 适用对象：本科 一、单项选择题(从下列各题四个备选答案中选出一个正确答案，并将其代号写在答题纸相应位置处。答案错选或未选者，该题不得分。每小题2分，共24分。)1.数据结构被形式地定义为 (K, R)，其中K是____的有限集，R是K上的关系有限集。 A.算法 B.数据元素 C.数据操作 D.逻辑结构2.在数据结构中，从逻辑上可以把数据结构分成____。 A.动态结构和静态结构 B.紧凑结构和非紧凑结构 C.线性结构和非线性结构 D.内部结构和外部结构3.以下的叙述中，正确的是____。A.线性表的存储结构优于链式存储结构 B.二维数组是其数据元素为线性表的线性表C.栈的操作方式是先进先出D.队列的操作方式是先进后出4.若一个栈的入栈序列是1、2、3、… 、n，其输出序列为p1、p2、p3、… 、pn，若p1=n，则pi为____。 A. i B. n = i C. n - i +1 D.不确定5.判断一个循环队列QU (最多元素为m) 为空的条件是____。A. QU-》front == QU-》rear B. QU-》front != QU-》rear C. QU-》front == (QU-》rear+1)%m D. QU-》front != (QU-》rear+1)%m6.在某单链表中，已知p所指结点不是最后结点，在p之后插入s所指结点，则执行____。A. s-》next = p; p-》next=s; B. s-》next = p-》next; p-》next = s;C. s-》next = p-》next; p = s; D. p-》next = s; s-》next = p;7.串是一种特殊的线性表，其特殊性体现在____。A.可以顺序存储 B.数据元素是一个字符C.可以链接存储 D.数据元素可以是多个字符8.已知某二叉树的后序遍历序列是dabec，中序遍历序列是debac，前序遍历序列是____。A. acbed B. decab C. deabc D. cedba9.对于一个满二叉树，m个树叶，n个结点，深度为h，则____。A. n = h + m B. h + m = 2n C. m = h-1 D. n = 2h -110.一个有n个顶点的无向图最多有____条边。A. n B. n(n-1) C. n(n-1)/2 D. 2n11.顺序查找法适合于存储结构为____的线性表。A. 散列存储 B. 顺序存储或链接存储C. 压缩存储 D. 索引存储12.在待排序的元素序列基本有序的前提下，效率最高的排序方法是____。A. 插入排序 B.选择排序 C.快速排序 D. 归并排序二、填空题(请在每小题的横线上填入正确内容，每空1分，共7分。)1.在线性结构中，第一个结点 前驱结点，其余每个结点有且只有1个前驱结点。2.在无权图G的邻接矩阵中，若A = 。3.根据二叉树的定义，具有三个结点的二叉树有 种不同的形态。4.空格串是指 ，其长度等于 。5.在散列存储中，装填因子α的值越大，则存储元素时发生冲突的可能性就 。6.已知模式串t= ‘abacabaaad’， 其用KMP法求得的每个字符对应的next函数值为 。三、简答题(本大题共3小题，每小题5分，共15分)1.比较静态查找与动态查找的主要区别，它们的基本运算有哪些不同？2.逻辑结构分哪几种，存储结构有哪几种？3.在具有n(n》1)个结点的各棵不同形态树中，其中深度最小的那棵树的深度是多少？它共有多少叶子和非叶子结点？四、判断题(本大题共10小题，命题正确的在题后括号内写 “T”，错误的在题后括号内写“F”，每小题1分，共10分)1.每种数据结构都应具备三种基本运算：插入、删除、搜索( )。2.满二叉树不一定是完全二叉树。( )3.带权连通图的最小生成树的权值之和一定小于它的其它生成树的权值之和。( )4.任一棵二叉搜索树的平均搜索时间都小于用顺序搜索法搜索同样结点的顺序表的平均搜索时间。( )5.线性链表中所有结点的类型必须相同。( )6.用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中顶点个数有关，而与图的边数无关( )。7.在散列法中解决冲突时，其装载因子的取值一定在(0，1)之间。( )8.任何一个关键活动延迟，那么整个工程将会延迟。( )9.平衡二叉树的左右子树深度之差的绝对值不超过1。( )10.n个结点的有向图，若它有n(n－1)条边，则它一定是强连通的。( )五、分析应用题（本题共26分，1、4小题各6分，2、3小题各7分）1.下述算法的功能是什么? （6分）LinkList Demo(LinkList L){ // L 是无头结点单链表ListNode *Q,*P;if(L&&L-》next){Q=L;L=L-》next;P=L;while (P-》next) P=P-》next;P-》next=Q; Q-》next=NULL; } return L;} 2.将给定的图简化为最小的生成树，要求从顶点1出发。（7分）3.设散列表为HT, 散列函数为 H (key) = key %13。用双散列法解决冲突, 对下列关键码序列 12, 23, 45, 57, 20, 03, 78, 31, 15, 36 造表。再散列函数为 RH (key) = (7*key) % 10 + 1, 寻找下一个地址的公式为 Hi = (Hi-1 + RH (key)) % 13, H1 = H (key)。画出相应的散列表, 并计算等概率下搜索成功的平均搜索长度。（7分）4.设待排序的排序码序列为{12, 2, 16, 30, 28, 10, 16*, 20, 6, 18},写出使用快速排序法每趟排序后的结果。（6分）六、算法设计题（本题共18分，第1小题10分，第2小题8分）1.试设计一个实现下述要求的查找运算函数Locate。设有一个带表头结点的双向链表L， 每个结点有4个数据成员：指向前驱结点的指针llink、指向后继结点的指针rlink，存放字符数据的成员data和访问频度freq。所有结点的freq 初始时都为0。每当在链表上进行一次Locate(L, x) 操作时，令元素值为x的结点的访问频度freq加1，并将该结点前移，链接到与它的访问频度相等的结点后面，使得链表中所有结点保持按访问频度递减的顺序排列，以使频繁访问的结点总是靠近表头。(10分)2.设一棵二叉树以二叉链表为存贮结构，设计一个算法将二叉树中所有结点的左，右子树相互交换。要求给出二叉链表的类型定义。(8分)答案：06－07第一学期期末考试参考答案与评分标准 试卷代码：03266B 授课课时：112课程名称：数据结构与算法 适用对象：本科 一、单项选择题(每小题2分，共24分。)1. B 2. C 3. B 4. C5. A6. B7. B 8. D9. D10.C11. B 12. A二、填空题(每空1分，共7分。)1. 无 2. 1 3. 5 4. 串中字符全为空格 ， 空格的个数 5. 大 6. 0112123422 。三、简答题(本大题共5小题，每小题5分，共15分)1．答：两种查找方法最大的区别在于：静态查找方法不修改查找表；动态查找在查找不成功时，将结点插入查找表中，即有可能修改查找表；静态查找的基本运算有建表、查找和读表元；动态查找除上述基本操作外还有初始化、插入和删除操作；2.答：根据数据元素之间关系的不同特性，通常有下列四类基本结构：(1)集合；(2)线性结构；(3)树形结构；(4)图状结构或网状结构。有两种不同的存储结构：顺序存储结构和链式存储结构。3.答：深度最小的那棵树的深度为2。对于这n个结点，除了一个根结点之外，其余得n-1个结点均为叶子结点，故其深度为2。该树叶子结点数为n-1，非叶子结点数为1。 四、判断题(每小题1分，共10分)1. (T)2. (F)3. (T)4. (F)5. (T)6. (T)7. (F)8. (T)9. (T )10.(T) 五、分析应用题（本题共26分，1、4小题各6分，2、3小题各7分）1.（6分）答：该算法的功能是：将开始结点摘下链接到终端结点之后成为新的终端结点，而原来的第二个结点成为新的开始结点，返回新链表的头指针。2.（7分）答: 3.（7分）答：使用散列函数H(key)=key mod 13 有：H（12）=12， H（23）=10，H（45）=6，H（57）=5，H（20）=7，H（03）=3，H（78）=0，H（31）=5，H（15）=2，H（36）=10利用双散列法造表：Hi =（Hi-1+RH(key)）%13, Hi =H(key) 0123456789101112781503574520313623121111113511搜索成功的平均搜索长度为：ASL =1/10（1+1+1+1+1+1+3+5+1+1）=16/10 4.（6分）答：六、算法设计题（第1小题10分，第2小题8分）1.(10分) 答：(1) 定义链表结构 struct DoubleListNode { char data ; int freq; DoubleListNode * llink, *rlink ; }; 初始时，所有结点的freq域的值都为0。(2) 定义函数DoubleListNode * locate ( DoubleListNode *f ; char &x ) { DoubleListNode * p, *q; p = f→rlink; /*跳过表头结点*/ while ( p != NULL && p→data != x ) p = p→rlink;/*搜索*/ if ( p ) { p→freq ++; q = p→llink; p→rlink→llink = q; q→rlink = p→rlink; /*从链中摘下p*/ while ( q != f &&q→freq 《 p→freq ) q =q→llink; p→llink = q; p→rlink = q→rlink; q→rlink→llink = p; q→rlink = p; /*在q后面插入p*/ } return p; }2． (8分)答：类型定义（略）void exchange(BiTree bt)//将二叉树bt所有结点的左右子树交换{ if(bt){ BiTree s；s=bt-》lchild; bt-》lchild=bt-》rchild; bt-》rchild=s; //左右子女交换exchange(bt-》lchild); //交换左子树上所有结点的左右子树exchange(bt-》rchild); //交换右子树上所有结点的左右子树} }

求试卷和答案,2010年10月自学考试数据结构导论的.

全国2010年10月高等教育自学考试 数据结构导论试题 课程代码：02142一、单项选择题(本大题共15小题，每小题2分，共30分)在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。 1．下列描述中正确的是( )A.数据元素是数据的最小单位 B.数据结构是具有结构的数据对象 C.数据结构是指相互之间存在一种或多种特定关系的数据元素的集合 D.算法和程序原则上没有区别，在讨论数据结构时两者是通用的 2．归并排序的时间复杂度是( )A．O（n2） B.O（nlog2n） C.O（n） D.O（log2n） 3．二分查找的时间复杂度是( )A．O（n2） B.O（nlog2n） C.O（n） D.O（log2n） 4．顺序存储的表中有90000个元素，已按关键字值升序排列，假设对每个元素进行查找的概率相同，且每个元素的关键字值皆不相同，用顺序查找法查找时，需平均比较的次数为( )A．25000 B.30000C.45000 D.900005．散列文件是一种( )A．顺序文件 B.索引文件 C.链接文件 D.计算寻址文件 6．两个矩阵A：m×n，B：n×p相乘，其时间复杂度为( )A．O(n) B.O(mnp)C.O(n2) D.O（mp） 7.常用于函数调用的数据结构是( )A.栈 B.队列 C.链表 D.数组 8．二维数组A［n］［m］以列优先顺序存储，数组A中每个元素占用1个字节，A［1］［1］为首元素，其地址为0，则元素A［i］［j］的地址为( )A.（i-1）×m+(j-1) B.(j-1)×n+(i-1)C.(j-1)×n+i D.j×n+i9.图的广度优先搜索使用的数据结构是( )A．队列 B.树 C.栈 D.集合 10．序列（21,19,37,5,2）经冒泡排序法由小到大排序，在第一次执行交换后所得结果为( )A．(19，21，37，5，2) B.(21，19，5，37，2)C.(21，19，37，2，5) D.(2，21，19，37，5)11．数据在计算机存储器内表示时，根据结点的关键字直接计算出该结点的存储地址，这种方法称为( )A．索引存储方法 B.顺序存储方法 C.链式存储方法 D.散列存储方法 12．在单链表中，存储每个结点有两个域，一个是数据域，另一个是指针域，指针域指向该结点的( )A．直接前趋 B.直接后继 C.开始结点 D.终端结点 13．在已知头指针的单链表中，要在其尾部插入一新结点，其算法所需的时间复杂度为( )A．O（1） B.O（log2n） C.O（n） D.O（n2） 14．在链队列中执行入队操作，( )A．需判别队是否空 B.需判别队是否满 C.限制在链表头p进行 D.限制在链表尾p进行 15．一整数序列26，59，77，31，51，11，19，42，以二路归并排序从小到大排序，第一阶段的归并结果为( )A.31，51，11，42，26，77，59，19 B.26，59，31，77，11，51，19，42C.11，19，26，31，42，59，51，77 D.26，11，19，31，51，59，77，42 二、填空题(本大题共13小题，每小题2分，共26分)请在每小题的空格中填上正确答案。错填、不填均无分。 16．下列程序段的时间复杂度为_______。 i=0；s=0； while（s《n） {i++； s=s+i； }17．数据的存储结构被分为顺序存储结构、_______、散列存储结构和索引存储结构4种。 18．从一个长度为n的顺序表中删除第i个元素（1≤i≤n）时，需向前移动_______个元素。 19．在单链表中，插入一个新结点需修改_______个指针。 20．在队列结构中，允许插入的一端称为_______。 21．稀疏矩阵采用的压缩存储方法是_______。 22．向一个栈顶指针为top的链栈中插入一个新结点*p时，应执行p-》next=top和_______操作。 23．有m个叶结点的哈夫曼树所具有的结点数为_______。 24．在一棵具有n个结点的完全二叉树中，从树根起，自上而下、自左至右地给所有结点编号。设根结点编号为1。若编号为i的结点有右孩子，那么其右孩子的编号为_______。 25．在一棵树中，_______结点没有前驱结点。 26．一个具有n个顶点的有向完全图的弧数是_______。 27．n个顶点的无向图G用邻接矩阵A［n］［n］存储，其中第i列的所有元素之和等于顶点Vi的_______。 28．选择排序的平均时间复杂度为_______。 三、应用题(本大题共5小题，每小题6分，共30分)29．在栈的输入端元素的输入顺序为1，2，3，4，5，6，进栈过程中可以退栈，则退栈时能否排成序列3，2，5，6，4，1和1，5，4，6，2，3，若能，写出进栈、退栈过程，若不能，简述理由。（用push（x）表示x进栈，pop(x)表示x退栈） 30．已知一棵二叉树的中根遍历序列为CBEDFAGH，后根遍历序列为CEFDBHGA，画出该二叉树。 31．给定表（15，11，8，20，14，13），试按元素在表中的顺序将它们依次插入一棵初始时为空的二叉排序树，画出插入完成后的二叉排序树，并判断该二叉排序树是否为平衡二叉排序树，若为非平衡二叉排序树，将它调整为平衡二叉排序树。 32．如题32图所示无向图，（1）写出其邻接矩阵；（2）写出三种以顶点A为起点的深度优 先搜索顶点序列。 题32图 33．用冒泡排序法对数据序列（49，38，65，97，76，134，27，49）进行排序，写出排序过程。并说明冒泡排序是否为稳定排序。 四、算法设计题(本大题共2小题，每小题7分，共14分)34.编写计算二叉树中叶子结点数目的算法。 35.开散列表的类型定义如下： typedef struct tagnode{keytype key;struct tagnode*next;}*pointer,node;typedef pointer openhash［n］;试写出开散列表上的查找算法。

求：2005年下半年北京市高等教育自学考试数据结构试卷

数据结构试卷(98年上半年北京市)一、 单项选择题（在每小题的四个备选答案中选出一个正确的答案，并将其号码填在题干后的号码内，每小题2分，共10分） 1.一个栈的输入序列为1，2，3，4，下面哪一个序列不可能是这个栈的输出序列？（ ） A. 1，3，2，4 B. 2，3，4，1 C. 4，3，1，2 D. 3，4，2，1 2.下列排序方法中，哪一种方法的比较次数与纪录的初始排列状态无关？（ ） A. 直接插入排序 B. 起泡排序 C. 快速排序 D. 直接选择排序 3.对n个记录的文件进行二路归并排序，总的时间代价为 A. O（nlog2n） B. O（n2） C. O（log2n） D. O（n） 4.若一棵二叉树具有10个度为2的结点，则该二叉树的度为0的结点个数是（ ） A. 9 B. 11 C. 12 D. 不确定 5.下面关于B树和B+树的叙述中，不正确的是 A. B树和B+树都是平衡的多分树 B. B树和B+树都是可用于文件的索引结构 C. B树和B+树都能有效地支持顺序检索 D. B树和B+树都能有效地支持随机检索 二、 填空题（每空2分，共20分） 1.从逻辑结构看，线性表是典型的 ，树是典型的 。 2.设有二维数组A的存储地址为 。 3.若按层次顺序将一棵有n个结点的完全二叉树的所有结点从1到n编号，那么当i为 且小于n时，结点I的右兄弟是结点 ，否则结点i没有右兄弟。 4.求具有最小带权外部路径长度的扩充二叉树的算法称为 算法。堆排序中建堆的方法称作 。 5.6阶B树中，每个结点至多包含 个关键码，除根和叶结点外，每个结点至少包含 个关键码。 三、 简答题（每小题6分，共18分） 1.请简述散列函数在散列法存储中的作用，并举出一个散列函数的例子。 2.请简述散列法存储中处理碰撞（冲突）的两类基本方法。 3.请简述负载因子的定义，为什么说负载因子是散列法存储的一个重要参数？ 四、 求解下列问题（每小题6分，共30分） 1.设待排序文件的关键码为（512,275,908,677,503,765,612,897,154,170）以第一元素为分界元素进行快速排序（按关键码值递增顺序），请给出一趟扫描后的结果。 2.请画出下面的树所对应的二叉树。 3.从一棵空的二叉排序树开始，将以下关键码值依次插入：25,13,15,31,7,20,37，请画出插入全部完成后的二叉排序树。 4.请画出下面带权图的一棵最小生成树。 5.对于下面的稀疏矩阵 1）画出其三元组法存储表示。 2）画出其行—列法（十字链表法）存储表示。 五、 算法题（6分） 有一个链接方式存储的线性表，表中每个结点包括两个指针，其结点用PASCAL语言描述如下： TYPE pointer=↑node; node=RECORD infdatatype; link1,link2:pointer END; 其中link1是指向结点的下一个结点的指针，link2是指向结点的前一个结点的指针,如图所示。 p和q都是pointer类型的变量，现要将q所指的新结点插入表中p所指结点的前面（说明：p所指的不是链表的第一个结点）。请用PASCAL语句写出该插入的关键步骤。（部要求写完整的算法，只要求用几个语句写出关键步骤。） 六、 算法填空和分析（共16分） 下面是用PASCAL语言编写的二分值插入排序算法，该算法对排序码为整数的线性表进行升序排序。 TYPE node=RECORD key:integer; infdatatype End; list=ARRAY; ⑤ END; END; 1.请将算法的空缺处应填入的正确内容写在下面。（10分） ① ② ③ ④ ⑤ 2.设待排序的记录数n=7，当排序码的初始排列顺序分别为（15,25,35,45,55,65,75）和（75,65,55,45,35,25,15）时，请说出排序过程中对排序码所进行的总的比较次数分别是多少？（假定算法中取中项的整数除法采用小数截断的方法。）（6分）

数据结构试卷

请回答下列问题：（1）说明语句S1的功能；——查找表尾元素（2）说明语句组S2的功能； ——把第一个元素插入表尾（3）设链表表示的线性表为（a1,a2, ...,an）,写出算法执行后的返回值所表示的线性表。（a2, ...,an，a1）,1．已知二叉树的先序序列和中序序列分别为HDACBGFE和ADCBHFEG。(1)画出该二叉树并给出其二叉链表及顺序存储结构表示。(2)画出与（1）求得的二叉树对应的森林。 H D GA C F B E 连接情况是，D,G连接H ，A,C 连接D,B连接C，E连接F，F连接G3．设散列表的长度m=13；散列函数为H(K)=K mod m,给定的关键码序列为19,14,23,01,68,20,84,27,55,11,试画出用线性探查法解决冲突时所构造的散列表。并求出在等概率的情况下，这种方法的搜索成功时的平均搜索长度和搜索不成功时的平均搜索长度。0 1 2 3 4 5 6 7 8 9 10 11 12 14 01 68 27 55 9 20 84 23 114.（1）已知一组键值序列（3，6，8，9，2，7，4），试采用快速排序法对该组序列作升序排序，并给出每一趟的排序结果。(2)3(8 9 6 7 4)2 3 （4 6）8（7 9）2 3 4 （6）8 7（9）23 4 6 8 7 9（2）已知一组键值序列（28，47，35，42，53，60，34，22），试给出采用直接插入排序法对该组序列作升序排序的每一趟结果。（28，47，35，42，53，60，34，22），（28，47，35，42，53，60，34，22），（28，35，47，42，53，60，34，22），（28，35，42，47，53，60，34，22），（28，35，42，47，53，60，34，22），（28，35，42，47，53，60，34，22），（28，34，35，42，47，53，60，22），（22，28，34，35，42，47，53，60），

《数据结构》第06章在线测试

 《数据结构》第06章在线测试 《数据结构》第06章在线测试剩余时间：58:08 答题须知：1、本卷满分20分。 2、答完题后，请一定要单击下面的“交卷”按钮交卷，否则无法记录本试卷的成绩。 3、在交卷之前，不要刷新本网页，否则你的答题结果将会被清空。 第一题、单项选择题（每题1分，5道题共5分）  1、一个有n个顶点的无向图若是连通图，则至少有＿＿＿＿A＿＿＿＿条边。 A、n-1B、n C、n+1D、(n+1)/2  2、图的广度优先遍历算法类似于二叉树的＿＿＿D＿＿＿＿＿。 A、先序遍历B、中序遍历 C、后序遍历D、层序遍历  3、无向图的邻接矩阵是一个＿＿＿＿A＿＿＿＿。 A、对称矩阵B、零矩阵 C、对角矩阵D、上三角矩阵  4、一个无向连通图的生成树是含有该连通图所有顶点的＿＿＿C＿＿＿＿＿。 A、极大连通子图B、极大子图 C、极小连通子图D、极小子图  5、如果从无向图的任意顶点出发进行一次深度优先遍历就能访问到图中所有顶点，则该图一定是＿＿＿B＿＿＿＿＿。 A、完全图B、连通图 C、有回路D、一棵树 第二题、多项选择题（每题2分，5道题共10分）  1、如果对无向图G必须进行二次广度优先遍历才能访问到图中所有顶点，则下列说法中正确的是＿＿＿ABD＿＿＿＿＿。 A、G肯定不是完全图 B、G肯定不是连通图 C、G中一定有回路 D、G有两个连通分量  2、对图分别进行深度优先遍历和广度优先遍历，得到的顶点访问序列＿＿＿CD＿＿＿＿＿。 A、一定相同 B、一定不同 C、不一定相同 D、可能相同  3、下列关于最短路径的说法中，正确的有＿＿＿ACD＿＿＿＿＿。 A、Dijkstra算法是按路径长度递增的顺序依次产生从某一固定源点到其他各顶点之间的最短路径。 B、若仅求单一源点到某一特定顶点之间的最短路径，则其算法的时间复杂度可以达到O(n)。 C、求图中每一对顶点间最短路径的Floyd算法的时间复杂度为O(n^3)。 D、求图中每一对顶点间的最短路径也可用Dijkstra算法实现。  4、已知一个无向图的邻接矩阵表示，计算第i个顶点的度的方法是＿＿ABCD＿＿＿＿。 A、计算邻接矩阵中第i行的元素之和 B、计算邻接矩阵中第i列的元素之和 C、计算邻接矩阵中第i行的非零元个数 D、计算邻接矩阵中第i列的非零元个数  5、有向图中顶点之间关系的特征是：每个顶点可以有＿＿＿＿CD＿＿＿＿。 A、一个前驱 B、一个后继 C、多个前驱 D、多个后继 第三题、判断题（每题1分，5道题共5分）  1、连通网的最小生成树是唯一的。F 正确错误  2、若从无向图的一个顶点出发进行广度优先遍历可访问到图中的所有顶点，则 该图一定是连通图。T 正确错误  3、图的深度优先遍历算法类似于二叉树的先序遍历T 正确错误  4、在对有向无环图执行拓扑排序算法之后，入度数组中所有元素的值均为0。T 正确错误  5、若从无向图的一个顶点出发进行深度优先遍历可访问到图中的所有顶点，则 该图一定是连通图。T 正确错误