当前位置：文档之家 › 数据结构课后习题答案第八章

数据结构课后习题答案第八章

  • 格式：doc
  • 大小：867.50 KB
  • 文档页数：9

第八章 排序（参考答案） 本章所用数据结构 #define N 待排序记录的个数 typedef struct { int key; ElemType other; }rectype; rectype r[n+1]; // r为结构体数组 8.2 稳定排序有：直接插入排序、起泡排序、归并排序、基数排序 不稳定排序有：希尔排序、直接选择排序、堆排序 希尔排序例：49，38， 49，90，70，25 直接选择排序例：2， 2，1 堆排序例：1，2，2

8.3 void StlinkedInsertSort(s , n); // 对静态链表s[1..n]进行表插入排序， 并调整结果，使表物理上排序 { #define MAXINT 机器最大整数 typedef struct { int key; int next; }rec; rec s[n+1]; // s为结构体数组 s[0].key=maxint; s[1].next=0; //头结点和第一个记录组成循环链表 i=2; //从第2个元素开始，依次插入有序链表中 while (i<=n) {q=0; p=s[0].next; // p指向当前最小元素，q是p的前驱 while (p!=0 && s[p].key { q=p; p=s[p].next; } s[i].next=p; s[q].next=i; // 将第个元素链入 i++； } // while(i<=n) 静态链表的插入 // 以下是重排静态链表，使之物理有序 i=1; p=s[0].next; while (i<=n) {WHILE (p q=s[p].next; if (i!=p) { s[i]s[p]; s[i].next=p; p=q; i++; } } 2

}//算法结束 8.4 void TwoWayBubbleSort( rectype r[n+1]; int n) // 对r[1..n]进行双向冒泡排序。即相邻两遍向两个相反方向起泡 { int i=1, exchange=1; // 设标记 while (exchange) { exchange=0; // 假定本趟无交换 for (j=n-i+1 j>=i+1;j--) // 向前起泡，一趟有一最小冒出 if (r[j]r[j-1]; exchange=1;} // 有交换 for (j= i+1;j>=n-I;j++) // 向后起泡，一趟有一最大沉底 if (r[j]>r[j+1]) {r[j]>r[j+1]; exchange=1;} // 有交换 i++; } // end of WHILE exchange }//算法结束 8.5 （1）在n=7时，最好情况下进行10次比较。6次比较完成第一趟快速排序，将序列分成 相等程度的序列（各3个元素），再各进行2次比较，完成全部排序。 （2）最好的初始排列：4，1，3，2，6，5，7

8.6 void QuickSort(rectype r[n+1]; int n) // 对r[1..n]进行快速排序的非递归算法 { typedef struct { int low,high; }node node s[n+1]； int top; int quickpass(rectype r[],int,int); // 函数声明 top=1; s[top].low=1; s[top].high=n; while (top>0) {ss=s[top].low; tt=s[top].high; top--; if (ss{ k=quickpass(r,ss,tt); if (k-ss>1) {top++; s[top].low=ss; s[top].high=k-1;} if (tt-k>1) {top++; s[top].low=k+1; s[top].high=tt;} } } // 算法结束 int quickpass(rectype r[];int s,t) {i=s; j=t; rp=r[i]; x=r[i].key; while （i {while (i if (i while (i=r[j].key) i++; if (i ] 3

r[i]=rp; return (i); } // 一次划分算法结束 8.7 void QuickSort(rectype r[n+1]; int n) // 对r[1..n]进行快速排序的非递归算法 对8.6算法的改进 { typedef struct { int low,high; }node node s[n+1]； int top; int quickpass(rectype r[],int,int); // 函数声明 top=1; s[top].low=1; s[top].high=n; ss=s[top].low; tt=s[top].high; top--; flag=true; while (flag || top>0) {k=quickpass(r,ss,tt); if (k-ss>tt-k) // 一趟排序后分割成左右两部分 {if (k-ss>1) // 左部子序列长度大于右部，左部进栈 {top++; s[top].low=ss; s[top].high=k-1; } if (tt-k>1) ss=k+1; // 右部短的直接处理 else flag=false; // 右部处理完，需退栈 } else if (tt-k>1) //右部子序列长度大于左部，右部进栈 {top=top+1; s[top].low=k+1; s[top].high=tt; } if (k-ss>1) tt=k-1 // 左部短的直接处理 else flag=false // 左部处理完，需退栈 } if (!flag && top>0) {ss=s[top].low; tt=s[top].high; top--; flag=true;} } // end of while (flag || top>0) } // 算法结束 int quickpass(rectype r[];int s,t) // 用“三者取中法”对8.6进行改进 { int i=s, j=t, mid=(s+t)/2; rectype tmp; if (r[i].key>r[mid].key) {tmp=r[i];r[i]=r[mid];r[mid]=tmp } if (r[mid].key>r[j].key) {tmp=r[j];r[j]=r[mid]; if (tmp>r[i]) r[mid]=tmp; else {r[mid]=r[i];r[i]=tmp } } {tmp=r[i];r[i]=r[mid];r[mid]=tmp } // 三者取中：最佳2次比较3次移动；最差3次比较10次移动 rp=r[i]; x=r[i].key; while （i {while (i4

if (i while (i=r[j].key) i++; if (i ] r[i]=rp; return (i); } // 一次划分算法结束 8.8 viod searchjrec（rectype r[]，int j） //在无序记录r[n]中，找到第j（0<=j//轴元素的位置i，若i=j则查找结束。否则根据ji在0~i、1或i+1~n+1之间查 //找，直到/i=j为止。 { int quichpass (rectype r[],int,int) // 函数声明 i=quichpass(r,0,n-1); // 查找枢轴位置 whilehile(i!=j) if (jelse i=quichpass(r,i+1.n-1); }// searchjrec算法结束

8.9 viod rearrange (rectype r[],int n) //本算法重排具有n个元素的数r，使取负值的关键字放到取非负值的关键字之前。 { int i=0,j=n-1; rp=r[0]; while(i{while(i=0) j--; if(iwhile(iif(i}//while(i8.9 void arrange(rectype r[n+1]; int n) // 对r[1..n]进行整理，使关键字为负值的记录排在非负值的记录之前 [ int i=0, j=-1;rp=r[0]; while (i { while (i=0) j--; if (i while (i if (i } r[i]=rp;// }//算法结束 //本算法并未判断轴枢的关键字的正负，在排序中并未和轴枢 //记录比较，而是按正负区分，提高了效率 8.10

合集下载

数据结构(c语言版)课后习题答案完整版

数据结构(c语言版)课后习题答案完整版

数据结构(c语言版)课后习题答案完整版数据结构(C语言版)课后习题答案完整版一、数据结构概述数据结构是计算机科学中一个重要的概念，用来组织和存储数据，使之可以高效地访问和操作。

在C语言中，我们可以使用不同的数据结构来解决各种问题。

本文将提供完整版本的C语言数据结构的课后习题答案。

二、顺序表1. 顺序表的定义和基本操作顺序表是一种线性表，其中的元素在物理内存中连续地存储。

在C 语言中，我们可以通过定义结构体和使用指针来实现顺序表。

以下是顺序表的一些基本操作的答案：（1）初始化顺序表```ctypedef struct{int data[MAX_SIZE];int length;} SeqList;void InitList(SeqList *L){L->length = 0;}```（2）插入元素到顺序表中```cbool Insert(SeqList *L, int pos, int elem){if(L->length == MAX_SIZE){return false; // 顺序表已满}if(pos < 1 || pos > L->length + 1){return false; // 位置不合法}for(int i = L->length; i >= pos; i--){L->data[i] = L->data[i-1]; // 向后移动元素 }L->data[pos-1] = elem;L->length++;return true;}```（3）删除顺序表中的元素```cbool Delete(SeqList *L, int pos){if(pos < 1 || pos > L->length){return false; // 位置不合法}for(int i = pos; i < L->length; i++){L->data[i-1] = L->data[i]; // 向前移动元素 }L->length--;return true;}```（4）查找顺序表中的元素```cint Search(SeqList L, int elem){for(int i = 0; i < L.length; i++){if(L.data[i] == elem){return i + 1; // 找到元素，返回位置 }}return -1; // 未找到元素}```2. 顺序表习题解答（1）逆置顺序表```cvoid Reverse(SeqList *L){for(int i = 0; i < L->length / 2; i++){int temp = L->data[i];L->data[i] = L->data[L->length - 1 - i]; L->data[L->length - 1 - i] = temp;}}```（2）顺序表元素去重```cvoid RemoveDuplicates(SeqList *L){for(int i = 0; i < L->length; i++){for(int j = i + 1; j < L->length; j++){if(L->data[i] == L->data[j]){Delete(L, j + 1);j--;}}}}```三、链表1. 单链表单链表是一种常见的链式存储结构，每个节点包含数据和指向下一个节点的指针。

2020智慧树知道网课《数据结构(中国海洋大学)》课后章节测试满分答案

2020智慧树知道网课《数据结构(中国海洋大学)》课后章节测试满分答案

第一章测试1【单选题】(2分)图书馆的数目检索系统采用关系的数据结构。

A.树形B.图状C.集合D.线性2【单选题】(2分)是相互之间存在一种或多种特定关系的数据元素的集合。

A.数据项B.数据结构C.数据元素D.数据3【单选题】(2分)（）是一个值的集合和定义在这个值集上的一组操作的总称。

A.数据项B.数据类型C.数据元素D.数据结构4【单选题】(2分)算法的确定性是指（）A.算法中没有逻辑B.在任何情况下，算法不会出现死循环C.算法中的每一条指令必须有确切的含义D.当输入数据非法时，算法也能作出反应或进行处理第二章测试1【单选题】(2分)线性表中的数据元素有一个前驱多个后继。

A.错B.对2【单选题】(2分)用顺序结构存储，删除最后一个结点时，（）A.其它B.会移动其它结点位置C.可能会移动其它结点位置D.一定不会移动其它结点位置3【单选题】(2分)链表中逻辑上相邻的元素的物理地址__________相邻。

A.一定不B.必定C.其它D.不一定4【单选题】(2分)1.假设有两个按元素值递增有序排列的线性表A和B，均以单链表作存储结构，请编写算法将A表和B表归并成一个按元素值递减有序(即非递增有序，允许表中含有值相同的元素)排列的线性表C，并要求利用原表(即A表和B表)的结点空间构造C表。

//将合并逆置后的结果放在C表中，并删除B表StatusListMergeOppose_L(LinkList&A,LinkList&B,LinkList&C){LinkListpa,pb,qa,qb;pa=A;pb=B;qa=pa;//保存pa的前驱指针qb=pb;//保存pb的前驱指针pa=pa->next;pb=pb->next;A->next=NULL;C=A;while(pa&&pb){if(pa->data<pb->data){qa=pa;pa=pa->next;qa->next=A->next;//将当前最小结点插入A表表头A->next=qa;}else{qb=pb;pb=pb->next;()//将当前最小结点插入B表表头A->next=qb;}}while(pa){qa=pa;pa=pa->next;qa->next=A->next;A->next=qa;}while(pb){qb=pb;pb=pb->next;qb->next=A->next;A->next=qb;}pb=B;free(pb);returnOK;}A.qa->next=A->nextB.qa->next=A;C.qb->next=A->nextD.qb->next=A;5【单选题】(2分)假设某个单向循环链表的长度大于1，且表中既无头结点也无头指针。

数据结构答案 第8章 图学习指导

数据结构答案 第8章 图学习指导

第8章图8.1 知识点分析1．图的定义图（Graph）是由非空的顶点（V ertices）集合和一个描述顶点之间关系——边（Edges）的有限集合组成的一种数据结构。

可以用二元组定义为：G＝（V，E）其中，G表示一个图，V是图G中顶点的集合，E是图G中边的集合。

2．图的相关术语（1）无向图在一个图中，如果每条边都没有方向，则称该图为无向图。

（2）有向图在一个图中，如果每条边都有方向，则称该图为有向图。

（3）无向完全图在一个无向图中，如果任意两顶点都有一条直接边相连接，则称该图为无向完全图。

在一个含有n个顶点的无向完全图中，有n(n-1)/2条边。

（4）有向完全图在一个有向图中，如果任意两顶点之间都有方向互为相反的两条弧相连接，则称该图为有向完全图。

在一个含有n个顶点的有向完全图中，有n (n-1) 条弧。

（5）顶点的度在无向图中，一个顶点拥有的边数，称为该顶点的度。

记为TD(v)。

在有向图中，一个顶点拥有的弧头的数目，称为该顶点的入度，记为ID(v)；一个顶点拥有的弧尾的数目，称为该顶点的出度，记为OD(v)；一个顶点度等于顶点的入度+出度，即：TD(v)=ID(v)＋OD(v)。

（6）权图的边或弧有时具有与它有关的数据信息，这个数据信息就称为权（Weight）。

（7）网边（或弧）上带权的图称为网（Network）。

（8）路径、路径长度顶点v i到顶点v j之间的路径（Path）是指顶点序列v i,v i1,v i2, …, v im,v j.。

其中，（v i,v i1），(v i1,v i2)，…,(v im,.v j)分别为图中的边。

路径上边的数目称为路径长度。

（9）回路、简单路径在一条路径中，如果其起始点和终止点是同一顶点，则称其为回路或者环（Cycle）。

如果一条路径上所有顶点除起始点和终止点外彼此都是不同的，则称该路径为简单路径。

(10）子图对于图G=（V，E），G’=（V’，E’），若存在V’是V的子集，E’是E的子集，则称图G’是G的一个子图。

数据库系统原理教程课后习题及答案(第八章)

数据库系统原理教程课后习题及答案(第八章)

第8章关系查询处理和查询优化1 ．试述查询优化在关系数据库系统中的重要性和可能性。

答：重要性：关系系统的查询优化既是RDBMS 实现的关键技术又是关系系统的优点所在。

它减轻了用户选择存取路径的负担。

用户只要提出“干什么”，不必指出“怎么干”。

查询优化的优点不仅在于用户不必考虑如何最好地表达查询以获得较好的效率，而且在于系统可以比用户程序的“优化’夕做得更好。

可能性：这是因为：( l ）优化器可以从数据字典中获取许多统计信息，例如关系中的元组数、关系中每个属性值的分布情况、这些属性上是否有索引、是什么索引（B ＋树索引还是HASH 索引或惟一索引或组合索引）等。

优化器可以根据这些信息选择有效的执行计划，而用户程序则难以获得这些信息。

( 2 ）如果数据库的物理统计信息改变了，系统可以自动对查询进行重新优化以选择相适应的执行计划。

在非关系系统中必须重写程序，而重写程序在实际应用中往往是不太可能的。

( 3 ）优化器可以考虑数十甚至数百种不同的执行计划，从中选出较优的一个，而程序员一般只能考虑有限的几种可能性。

( 4 ）优化器中包括了很多复杂的优化技术，这些优化技术往往只有最好的程序员才能掌握。

系统的自动优化相当于使得所有人都拥有这些优化技术。

2 ．对学生一课程数据库有如下的查询：SEI 王CT Cn 即ne FROM Student , Cou 拐e , SC WHERE Student . Sno = SC . Sno AND SC . Cllo = Coll 拐e . Cllo AND Stu 击nt . Sdept = ! 15 ! ; 此查询要求信息系学生选修了的所有课程名称。

试画出用关系代数表示的语法树，并用关系代数表达式优化算法对原始的语法树进行优化处理，画出优化后的标准语法树。

答：3 ．试述查询优化的一般准则。

答：下面的优化策略一般能提高查询效率：( l ）选择运算应尽可能先做；( 2 ）把投影运算和选择运算同时进行；( 3 ）把投影同其前或其后的双目运算结合起来执行；( 4 ）把某些选择同在它前面要执行的笛卡儿积结合起来成为一个连接运算；( 5 ）找出公共子表达式；( 6 ）选取合适的连接算法。