数据结构第二版吴陈课后答案，数据结构习题4

本文目录一览

1，数据结构习题4
2，数据结构习题
3，数据结构考试答案
4，自考数据结构答案
5，数据结构在线作业

1，数据结构习题4

根据T(n) = T(en) + O(n) (0 < e <1) 则有 T(n) = O(n) 因此关键问题是怎样解决划分标准的问题, 因此产生下列线性时间找中位数的算法: 将数组a有n个元素, 划分成5个一组, 则共有[n/5]个元素, 对于每组用一般的排序找中位数,需要25次, 则总共需要O(25*[n/5]) = O(n), 然后在这些中位数中递归找其中位数需要T(n/5)次,然后以找到的中位数x来作为划分标准则显然划分时间为O(n), 再递归的划分, 显然最多有3n/4的元素小于或大于x, 则选择中位数的总复杂度为: T(n) = O(n) + T(n/5) + T(3n/4) 有T(n) = O(n)。因此快速排序的复杂度为T(n) = 2T(n/2) + O(n) 有:T(n) = nlogn。但最坏情况下复杂度为O(n^2)，出现此条件的情况是N个数原来就已经按照规定要求排好序了。

太多了写不下，去这个链接看： http://student.zjzk.cn/course_ware/data_structure/web/paixu/paixu8.1.1.1.htm

数据结构习题4

2，数据结构习题

一、选择题1．C2．D解析：A．完全二叉树可以用数组存储，树是非线性结构 B．链表且插入和删除运算效率高 C．链表也有双向链表，有两个指针域3．A4．A．顺序表可随机访问任一元素5．D6．这道题你是不是弄错了全都对啊7．D 满二叉树：结点总数目N=2^H -1 H为数高度，求出结点总数为255 满二叉树，只有度为0 和度为2 的结点，度为0 的结点等于度为1 结点数目+1 因此选D 8．C 这题不用画图就可做出来，后序遍历序列是dabec，------》得到根节点是：c 前序遍历；根左右所以第一个一定是c 只有A项符合 9. A 虽然你没给图但是一般都是A相因为见过好多这个题中序遍历和层次遍历结果一样10. D11.C12.B 在最坏情况:比较次数为___每次查找都要从第一个比较到最后一个，都要遍历N次：总的比较次数N*N,平均比较次数就是N 13. C二、填空题1．出栈2．n/2+n/(n+1) 1+2+3……n+n)/(n+1)=．n/2+n/(n+1) 3．14．设待排数据元素的关键字为（67，24，14，22，33，15，11，15），用选择法将其按升序排序，需要比较的次数为【】。5．136．11 3+6+2=11 *7．15 方法同选择题上那个满二叉树8．无图9. 16 和第七题一样的方法

根据t(n) = t(en) + o(n) (0 < e <1) 则有 t(n) = o(n) 因此关键问题是怎样解决划分标准的问题, 因此产生下列线性时间找中位数的算法: 将数组a有n个元素, 划分成5个一组, 则共有[n/5]个元素, 对于每组用一般的排序找中位数,需要25次, 则总共需要o(25*[n/5]) = o(n), 然后在这些中位数中递归找其中位数需要t(n/5)次,然后以找到的中位数x来作为划分标准则显然划分时间为o(n), 再递归的划分, 显然最多有3n/4的元素小于或大于x, 则选择中位数的总复杂度为: t(n) = o(n) + t(n/5) + t(3n/4) 有t(n) = o(n)。因此快速排序的复杂度为t(n) = 2t(n/2) + o(n) 有:t(n) = nlogn。但最坏情况下复杂度为o(n^2)，出现此条件的情况是n个数原来就已经按照规定要求排好序了。

数据结构习题

3，数据结构考试答案

*链表*/#include <stdlib.h>typedef struct node int data; struct node *next;}*Listlink;/*后插法创建单链表*/void hou_create(Listlink *head,int n) int i; Listlink p,q; *head=(Listlink )malloc(sizeof(struct node)); (*head)->next=NULL;/*建立头结点*/ q=*head; for(i=0;i<n;i++) p=(Listlink)malloc(sizeof(struct node)); scanf("%d",&(p->data)); p->next=q->next; q->next=p; q=p; }}/*将两个递增单链表合并为一个递增的单链表*/void merge(Listlink la,Listlink lb,Listlink *lc) Listlink pa,pb,pc; *lc=la; /*合并后的链表头结点使用a链表的*/ pa=la->next; pb=lb->next; pc=*lc; while(pa!=NULL&&pb!=NULL) if(pa->data<pb->data) pc->next=pa; pa=pa->next; pc=pc->next; } else pc->next=pb; pb=pb->next; pc=pc->next; } } if(pa!=NULL)pc->next=pa; else pc->next=pb;}void print_list(Listlink head) Listlink p; p=head->next; while(p!=NULL) printf(" %d",p->data); p=p->next; }}main() Listlink la,lb,lc; puts("houcha:"); hou_create(&lb,10); puts("houcha:"); hou_create(&la,10); merge(la,lb,&lc); print_list(lc); getch();}不用开辟新的空间

数据结构考试答案

4，自考数据结构答案

全国2003年上半年自考数据结构答案及标准评分 http://www.xpbook.com/soft/14519.shtml2006年10月自学考试"数据结构"试题参考答案 http://edu.qq.com/a/20061129/000168.htm很多数据结构试题 http://www.bkzyk.com/test/search.asp?act=Topic&classid=&keyword=%CA%FD%BE%DD%BD%E1%B9%B9&btn=+%CB%D1%CB%F7+http://www.kaoti8.com/query.asp?q=%CA%FD%BE%DD%BD%E1%B9%B9&x=79&y=17自考用的数据结构课后答案 DOC文件，很大，现只复制最前面的一小部分，如需要，提供邮箱，我发给你(还有“数据结构试题及答案”) 第一章绪论 1.1 简述下列概念：数据、数据元素、数据类型、数据结构、逻辑结构、存储结构、线性结构、非线性结构。 ● 数据：指能够被计算机识别、存储和加工处理的信息载体。 ● 数据元素：就是数据的基本单位，在某些情况下，数据元素也称为元素、结点、顶点、记录。数据元素有时可以由若干数据项组成。 ● 数据类型：是一个值的集合以及在这些值上定义的一组操作的总称。通常数据类型可以看作是程序设计语言中已实现的数据结构。 ● 数据结构：指的是数据之间的相互关系，即数据的组织形式。一般包括三个方面的内容:数据的逻辑结构、存储结构和数据的运算。 ● 逻辑结构：指数据元素之间的逻辑关系。 ● 存储结构：数据元素及其关系在计算机存储器内的表示，称为数据的存储结构. ● 线性结构：数据逻辑结构中的一类。它的特征是若结构为非空集，则该结构有且只有一个开始结点和一个终端结点，并且所有结点都有且只有一个直接前趋和一个直接后继。线性表就是一个典型的线性结构。栈、队列、串等都是线性结构。 ● 非线性结构：数据逻辑结构中的另一大类，它的逻辑特征是一个结点可能有多个直接前趋和直接后继。数组、广义表、树和图等数据结构都是非线性结构。 1.2 试举一个数据结构的例子、叙述其逻辑结构、存储结构、运算三个方面的内容。答：例如有一张学生体检情况登记表，记录了一个班的学生的身高、体重等各项体检信息。这张登记表中，每个学生的各项体检信息排在一行上。这个表就是一个数据结构。每个记录(有姓名，学号，身高和体重等字段)就是一个结点，对于整个表来说，只有一个开始结点(它的前面无记录)和一个终端结点(它的后面无记录)，其他的结点则各有一个也只有一个直接前趋和直接后继(它的前面和后面均有且只有一个记录)。这几个关系就确定了这个表的逻辑结构是线性结构。这个表中的数据如何存储到计算机里，并且如何表示数据元素之间的关系呢? 即用一片连续的内存单元来存放这些记录(如用数组表示)还是随机存放各结点数据再用指针进行链接呢? 这就是存储结构的问题。在这个表的某种存储结构基础上，可实现对这张表中的记录进行查询，修改，删除等操作。对这个表可以进行哪些操作以及如何实现这些操作就是数据的运算问题了。 1.3 常用的存储表示方法有哪几种? 答：常用的存储表示方法有四种: ● 顺序存储方法：它是把逻辑上相邻的结点存储在物理位置相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现。由此得到的存储表示称为顺序存储结构，通常借助程序语言的数组描述。 ● 链接存储方法：它不要求逻辑上相邻的结点在物理位置上亦相邻，结点间的逻辑关系是由附加的指针字段表示。由此得到的存储表示称为链式存储结构,通常借助于程序语言的指针类型描述。 ● 索引存储方法：除建立存储结点信息外，还建立附加的索引表来标识结点的地址。组成索引表的索引项由结点的关键字和地址组成。若每个结点在索引表中都有一个索引项，则该索引表称之为稠密索引（Dense Index）。若一组结点在索引表中只对应一个索引项，则该索引表称为稀疏索引。 ● 散列存储方法：就是根据结点的关键字直接计算出该结点的存储地址。 1.4 设三个函数f,g,h分别为 f(n)=100n3+n2+1000 , g(n)=25n3+5000n2 , h(n)=n1.5+5000nlgn 请判断下列关系是否成立： (1) f(n)=O(g(n)) (2) g(n)=O(f(n)) (3) h(n)=O(n1.5) (4) h(n)=O(nlgn) 分析：数学符号"O"的严格的数学定义：若T（n）和f（n）是定义在正整数集合上的两个函数，则T（n）=O（f（n））表示存在正的常数C和n0，使得当n≥n0时都满足0≤T（n）≤C?f（n）。通俗地说，就是当n→∞时，f(n)的函数值增长速度与T（n)的增长速度同阶。一般，一个函数的增长速度与该函数的最高次阶同阶。即： O(f(n))=n3 O(g(n))=n3 O(h(n))=n1.5 所以答案为：答： ●（1）成立。 ●（2）成立。 ●（3）成立。 ●（4）不成立。

没的。我找了好多。自己买本练习册吧。。。

你可以上衡水自考网或者在www.4juan.com里面去找一下答案.应该能找到一两年答案,但想要这几年全部的答案真的比较困难希望你好运

5，数据结构在线作业

1. D2 D cedba3. A4. C. nx(n+1)／25. A6. A应该是第一层元素的个数7. C8. C9B10 A

大工11秋《数据结构》在线作业1一,单选题1. b2. b3. b4. a5. a6. c7. b8. b9. c10.b二,判断题1.b2.a3.b4.b5.b6.a7.b8.b9.b10.a 大工11秋《数据结构》在线作业2一,单选题1. difference(a,b,c)表示求集合a和b的差集c.若a=a. b. c. d. 正确答案：c2. 具有6个顶点的无向图至少应有（）条边才能确保是一个连通图.a. 5b. 6c. 7d. 8正确答案：a3. min(a),函数的返回值是集合a的所有元素中按线性序最小的那个元素.则min(a. 2b. 3c. 4d. 0正确答案：a4. index(s,t)表示子串定位运算.若串t是串s的子串,则函数返回值是串t在串s中第一次出现的开始位置,否则返回值是0.若s="ababa",t="ba",则index(s,t)=( ).a. 0b. 1c. 2d. 3正确答案：c5. 在一棵二叉树上第5层的结点数最多为（）,设树根为第1层.a. 16b. 15c. 8d. 32正确答案：a6. intersection(a,b,c)表示求集合a和b的交集c.若a=a. b. c. d. 正确答案：b7. 在一个具有n个顶点和e条边的无向图的邻接表中,边结点的个数为（）.a. nb. nec. ed. 2e正确答案：d8. union(a,b,c)表示求集合a和b的并集c.若a=a. b. c. d. 正确答案：a9. 在一个具有n个顶点和e条边的有向图的邻接表中,保存顶点单链表的表头指针向量的大小至少为（）.a. nb. 2nc. ed. 2e正确答案：a10. concat(s,t)表示连接运算.将串t连接在串s之后,形成新的串s.若s="beg",t="in",则concat(s,t)之后,s="( )".a. beginb. beinc. begnd. beggin正确答案：a二,判断题1. 树中的结点数等于所有结点的度数加1.a. 错误b. 正确正确答案：b2. 有向图用邻接表表示,顶点i的度是对应顶点i链表中结点个数.a. 错误b. 正确正确答案：a3. 字典是一种特殊的集合,其中每个元素由关键码和属性组成.a. 错误b. 正确正确答案：b4. 有向图用邻接表表示,顶点i的出度是对应顶点i链表中结点个数.a. 错误b. 正确正确答案：b5. 一个图的邻接矩阵表示是惟一的.a. 错误b. 正确正确答案：b6. 有向图的邻接矩阵一定是对称矩阵.a. 错误b. 正确正确答案：a7. 无向图的邻接矩阵一定是对称矩阵.a. 错误b. 正确正确答案：b8. 一个图的邻接表表示是惟一的.a. 错误b. 正确正确答案：a9. 非空二叉树上叶子结点数等于双分支结点数加1.a. 错误b. 正确正确答案：b10. 连通图的生成树不一定是惟一的.a. 错误b. 正确正确答案：b大工11秋《数据结构》在线作业3一,单选题1. 下述几种排序方法中,要求内存量最大的是（）.a. 插入排序b. 选择排序c. 堆排序d. 归并排序正确答案：d2. 堆排序是一种（）排序.a. 插入b. 选择c. 交换d. 归并正确答案：b3. 在长度为n的顺序表中进行顺序查找,查找失败时需与关键字比较次数是( ).a. nb. 1c. n-1d. n+1正确答案：d4. 用起泡排序方法对n个记录按排序码从小到大排序时,当初始序列是按排序码从大到小排列时,与排序码总比较次数是（）.a. n-1b. nc. n+1d. n(n-1)/2正确答案：d5. 对线性表进行顺序查找时,要求线性表的存储结构是（）.a. 倒排表b. 索引表c. 顺序表或链表d. 散列表正确答案：c6. 对于顺序存储的有序表(5,12,20,26,37,42,46,50,64),若采用折半查找,则查找元素26的查找长度为( ).a. 2b. 3c. 4d. 5正确答案：c7. 哈希表的平均查找长度和（）无直接关系.a. 哈希函数b. 装填因子c. 哈希表记录类型d. 处理冲突的方法正确答案：c8. 排序方法中,从未排序序列中挑选元素,并将其依次放入已排序序列（初始时为空）的一端的方法,称为（）.a. 希尔排序b. 归并排序c. 插入排序d. 选择排序正确答案：d9. 磁带适合存储的文件类型是（）.a. 索引文件b. 顺序文件c. 散列文件d. 倒排文件正确答案：b10. 排序方法中,从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比较,将其放入已排序序列的正确位置上的方法,称为（）.a. 插入排序b. 冒泡排序c. 希尔排序d. 选择排序正确答案：a二,判断题1. 散列表既是一种查找方法,又是一种存储方法.a. 错误b. 正确正确答案：b2. 在散列文件中删除记录时,只要对被删记录作一标记即可.a. 错误b. 正确正确答案：b3. 散列文件中存放一组记录的存储单位称为桶.a. 错误b. 正确正确答案：b4. 二分查找对线性表的存储结构无任何要求.a. 错误b. 正确正确答案：a5. 直接选择排序属于选择类排序,是一种稳定的排序方法.a. 错误b. 正确正确答案：a6. 哈希表查找无须进行关键字的比较.a. 错误b. 正确正确答案：a7. 对快速排序来说,初始序列为正序和反序都是最坏情况.a. 错误b. 正确正确答案：b8. 在执行某个排序过程中,出现排序码朝着最终位置相反方向移动,则该算法是不稳定的.a. 错误b. 正确正确答案：a9. 堆排序是一种不稳定的排序方法.a. 错误b. 正确正确答案：b10. 若待排序记录已按排序码基本有序,则应采用直接插入排序或起泡排序.a. 错误b. 正确正确答案：b