logo资料库

算法与数据结构_C语言版_答案(1-8章).doc

发布时间：2022-06-09 发布人：admin 分类：说明书 资料大小：0.61M 资料格式：doc 举报 版权申诉
第1页 / 共83页
第2页 / 共83页
第3页 / 共83页
第4页 / 共83页
第5页 / 共83页
第6页 / 共83页
第7页 / 共83页
第8页 / 共83页
资料共83页，剩余部分请下载后查看
    第1章 绪论
    第2章 线性表
    第3章                     栈和队列
    第8章 动态存储结构
    第 1 章 绪论 一、基础知识题 1. 简述下列概念 数据，数据元素，数据类型，数据结构，逻辑结构，存储结构，算法。 【解答】数据是信息的载体，是描述客观事物的数、字符，以及所有能输入 到计算机中并被计算机程序识别和处理的符号的集合。数据元素是数据的基本单 位。在不同的条件下，数据元素又可称为元素、结点、顶点、记录等。 数据类型是对数据的取值范围、数据元素之间的结构以及允许施加操作的一 种总体描述。每一种计算机程序设计语言都定义有自己的数据类型。 “数据结构”这一术语有两种含义，一是作为一门课程的名称；二是作为一 个科学的概念。作为科学概念，目前尚无公认定义，一般认为，讨论数据结构要 包括三个方面，一是数据的逻辑结构，二是数据的存储结构，三是对数据进行的 操作（运算）。而数据类型是值的集合和操作的集合，可以看作是已实现了的数 据结构，后者是前者的一种简化情况。 数据的逻辑结构反映数据元素之间的逻辑关系（即数据元素之间的关联方式 或“邻接关系”），数据的存储结构是数据结构在计算机中的表示，包括数据元 素的表示及其关系的表示。数据的运算是对数据定义的一组操作，运算是定义在 逻辑结构上的，和存储结构无关，而运算的实现则依赖于存储结构。 数据结构在计算机中的表示称为物理结构，又称存储结构。是逻辑结构在存 储器中的映像，包括数据元素的表示和关系的表示。逻辑结构与计算机无关。 算法是对特定问题求解步骤的一种描述，是指令的有限序列。其中每一条指 令表示一个或多个操作。一个算法应该具有下列特性：有穷性、确定性、可行性、 输入和输出。 2. 数据的逻辑结构分哪几种，为什么说逻辑结构是数据组织的主要方面？ 【解答】数据的逻辑结构分为线性结构和非线性结构。（也可以分为集合、 线性结构、树形结构和图形即网状结构）。 逻辑结构是数据组织的某种“本质性”的东西： （1）逻辑结构与数据元素本身的形式、内容无关。 （2）逻辑结构与数据元素的相对位置无关。 （3）逻辑结构与所含数据元素的个数无关。 3. 试举一个数据结构的例子，叙述其逻辑结构、存储结构、运算三方 面的内容。 【解答】学生成绩表，逻辑结构是线性结构，可以顺序存储（也可以链 式存储），运算可以有插入、删除、查询、等等。 4. 简述算法的五个特性，对算法设计的要求。
    【解答】算法的五个特性是：有穷性、确定性、可行性、零至多个输入 和一至多个输出。 对算法设计的要求：正确性，易读性，健壮性，和高的时空间效率（运 算速度快，存储空间小）。 5. 设 n 是正整数，求下列程序段中带@记号的语句的执行次数。 (1)i=1;k=0; while(ij)j++; else i++; } @ @ (4)x=91;y=100; while(y>0) if(x>100) {x=x-10; y--; @ } else x++; (2)i=  n/2 j=n/2 (3)n+1, n(n+1), n2,(n+1)n2, n3 (4)100, 1000 6. 有实现同一功能的两个算法 A1 和 A2，其中 A1 的时间复杂度为 Tl=O(2n)，A2 的时间复杂度为 T2=O(n2)，仅就时间复杂度而言，请具 体分析这两个算法哪一个好。 【解答】对算法 A1 和 A2 的时间复杂度 T1 和 T2 取对数，得 nlog2 和 2logn。 显然，当 n<4 时，算法 A1 好于 A2；当 n=4 时，两个算法时间复杂度相同；当 n>4 时，算法 A2 好于 A1。 7. 选择题：算法分析的目的是（ ） A、找出数据结构的合理性 B、研究算法中的输入和输出的关系 C、分析算法的效率以求改进 D、分析算法的易懂性和文档特点 【解答】C 二、算法设计题
    8. 已知输入 x，y，z 三个不相等的整数，设计一个“高效”算法，使 得这三个数按从小到大输出。“高效”的含义是用最少的元素比较次 数、元素移动次数和输出次数。 void Best() {//按序输出三个整数的优化算法 int a,b,c,t; scanf(“%d%d%d”,&a,&b,&c); if(a>b) {t=a; a=b; b=t:} //a 和 b 已正序 if(b>c) {t=c; c=b; //c 已到位 if(a>t) {b=a; a=t;} //a 和 b 已正序 else b=t; } printf(“%d,%d,%d\n”,a,b,c); //最佳 2 次比较，无移动；最差 3 次比较，7 个赋值 } 9. 在数组 A[n]中查找值为 k 的元素，若找到则输出其位置 i(1≤i≤ n)，否则输出 0 作为标志。设计算法求解此问题，并分析在最坏情况 下的时间复杂度。 【题目分析】从后向前查找，若找到与 k 值相同的元素则返回其位置，否则 返回 0。 int Search(ElemType A[n+1], ElemType k) {i=n; wile(i>=1)&&(A[i]!=k)) i--; if(i>=1) return i; else return 0; } 当查找不成功时，总的比较次数为 n+1 次，所以最坏情况下时间复杂度 为 O(n)。
    第 2 章 线性表 一、基础知识题 2.1 试述头指针、头结点、元素结点、首元结点的区别，说明头指针和头结点的 作 【解答】指向链表第一个结点（或为头结点或为首元结点）的指针称为头指针。 “头指针”具有标识一个链表的作用，所以经常用头指针代表链表的名字，如链 表 L 既是指链表的名字是 L，也是指链表的第一个结点的地址存储在指针变量 L 中，头指针为“NULL”则表示一个空表。 有时，我们在整个线性链表的第一个元素结点之前加入一个结点，称为头结 点，它的数据域可以不存储任何信息（也可以做监视哨或存放线性表的长度等附 加信息），指针域中存放的是第一个数据结点的地址，空表时为空。 “头结点” 的加入，使插入和删除等操作方便统一。 元素结点即是数据结点，至少包括元素自身信息和其后继元素的地址两个 域。 首元结点是指链表中第一个数据元素的结点；为了操作方便，通常在链表的 首元结点之前附设一个结点，称为头结点。 2.2 分析顺序存储结构和链式存储结构的优缺点，说明何时应该利用何种结构。 【解答】①从空间上来看，当线性表的长度变化较大，难以估计其规模时， 选用动态的链表作为存储结构比较合适，但链表除了需要设置数据域外，还要额 外设置指针域，因此当线性表长度变化不大，易于事先确定规模时，为了节约存 储空间，宜采用顺序存储结构。 ②从时间上看，顺序表具有按元素序号随机访问的特点，在顺序表中按序号 访问数据元素的时间复杂度为 O(1)；而链表中按序号访问的时间复杂度为 O(n)。 所以如果经常按序号访问数据元素，使用顺序表优于链表。 在顺序表中做插入删除操作时，平均移动大约表中一半的元素，因此 n 较大 时顺序表的插入和删除效率低。在链表中作插入、删除，虽然也要找插入位置， 但操作主要是比较操作。从这个角度考虑显然链表优于顺序表。 总之，两种存储结构各有长短，选择那一种存储结构，由实际问题中的主要 因素决定。 2.3 分析在顺序存储结构下插入和删除结点时平均需要移动多少个结点。 【解答】平均移动表中大约一半的结点，插入操作平均移动 个结点，删除操作 平均移动 个结点。具体移动的次数取决于表长和插入、删除的结点的位置。 2.4 为什么在单循环链表中常使用尾指针，若只设头指针，插入元素的时间复杂 度如何？ 【解答】单循环链表中无论设置尾指针还是头指针都可以遍历表中任一个结点。 设置尾指针时，若在表尾进行插入元素或删除第一元素，操作可在 O(1)时间内
    完成；若只设置头指针，表尾进行插入或删除操作，需要遍历整个链表，时间复 杂度为 O(n)。 2.5 在单链表、双链表、单循环链表中，若知道指针 p 指向某结点，能否删除该 结点，时间复杂度如何？ 【解答：】以上三种链表中，若知道指针 p 指向某结点，都能删除该结点。双链 表删除 p 所指向的结点的时间复杂度为 O(1)，而单链表和单循环链表上删除 p 所指向的结点的时间复杂度均为 O(n)。 2.6 下面算法的功能是什么？ LinkedList Unknown(LinkedList la) {LNode *q，*p; if(la && la->next) {q=la; la=la->next; p=la; while(p->next) p=p->next; p->next=q; q->next=null; } return la; } 【解答】将首元结点删除并插入到表尾（设链表长度大于 1）。 2.7 选择题：在循环双链表的*p 结点之后插入*s 结点的操作是（ ） la、p->next=s; s->prior=p; p->next->prior=s; s->next=p->next; B、p->next=s; p->next->prior=s; s->prior=p; s->next=p->next; lc、s->prior=p; s->next=p->next; p->next:=s; p->next->prior=s; D、s->prior=p; s>next=p>next; p>next->prior =s; p->next=s; 【解答】D 2.8 选择题：若某线性表最常用的操作是存取任一指定序号的元素和在最后进行 插入和删除运算，则利用（ ）存储方式最节省时间。 la．顺序表 B．双链表 lc．带头结点的双循环链表 D．单循环 链表 【解答】la 二、算法设计题 2.9 设 ha和 hb分别是两个带头结点的非递减有序单链表的头指针，试设计算法， 将这两个有序链表合并成一个非递增有序的单链表。要求使用原链表空间，表中 无重复数据。
    【题目分析】因为两链表已按元素值非递减次序排列，将其合并时，均从第一个 结点起进行比较，将小的链入链表中，同时后移链表工作指针，若遇值相同的元 素，则删除之。该问题要求结果链表按元素值非递增次序排列，故在合并的同时， 将链表结点逆置。 LinkedList Union(LinkedList ha,hb) ∥ha,hb 分别是带头结点的两个单链表的头指针，链表中的元素值按递增序排 列 ∥本算法将两链表合并成一个按元素值递减次序排列的单链表,并删除重复元 素 { pa=ha->next; ∥pa 是链表 ha 的工作指针 pb=hb->next; ∥pb 是链表 hb 的工作指针 ha->next=null; ∥ha 作结果链表的头指针，先将结果链表初始化为空 while(pa!=null && pb!=null) ∥当两链表均不为空时作 {while(pa->next && pa->data==pa->next->data) {u=pa->next; pa->next=u->next; free(u)}∥删除 pa 链表中的 重复元素 重复元素 逆置 重复元素 while(pb->next && pb->data==pb->next->data) {u=pb->next; pb->next=u->next; free(u)}∥删除 pb 链表中的 if(pa->datadata) {r=pa->next; ∥将 pa 的后继结点暂存于 r pa->next=ha->next; ∥将 pa 结点链于结果表中，同时逆置 ha->next=pa; pa=r; } else if(pb->datadata) ∥恢复 pa 为当前待比较结点 {r=pb->next; ∥ 将 pb 的后继结点暂存于 r pb->next=ha->next; ∥将 pb 结点链于结果表中，同时 ha->next=pb; pb=r; } ∥恢复 pb 为当前待比较结点 else{u=pb;pb=pb->next;free(u)}∥删除链表 pb 和 pa 中的 }// while(pa!=null && pb!=null) if(pa) pb=pa; ∥避免再对 pa 写下面的 while 语句 while(pb!=null) ∥将尚未到尾的表逆置到结果表中 {r=pb->next; pb->next=ha->next; ha->next=pb; pb=r; }
    return ha }∥算法 Union 结束 2.10 设 la 是一个双向循环链表，其表中元素递增有序。试写一算法插入 元素 x，使表中元素依然递增有序。 【问题分析】双向链表的插入与单链表类似，但需修改双向指针。 DLinkedList DInsert(DLinkedList la, ElemType x) ∥在递增有序的双向循环链表 la 中插入元素 x，使表中元素依然递增有 序 {p=la->next; ∥p 指向第一元素 la->data=MaxElemType;∥MaxElemType 是和 x 同类型的机器最大值， 用做监视哨 while(p->datanext ; s=(DLNode *)malloc(sizeof(DLNode));∥申请结点空间 s->data=x; s->prior=p->prior; s->next=p; p->prior->next=s; p->prior=s; ∥将插入结点链入链表 } 2.11 设 p 指向头指针为 la 的单链表中某结点，试编写算法，删除结点*p 的 直接前驱结点。 【题目分析】设*p 是单链表中某结点，删除结点*p 的直接前驱结点，要找 到*p 的前驱结点的前驱*pre。进行如下操作：u=pre->next; pre->next=u->next;free(u); LinkedList LinkedListDel(LinkedList la，LNode *p) {∥删除单链表 la 上的结点*p 的直接前驱结点,假定*p 存在 pre=la; if(pre-next==p) printf(“*p 是链表第一结点，无前驱\n”) ; exit(0) ; } while(pre->next->next !=p) pre=pre->next; u=pre->next; pre->next=u->next; free(u); return(la); } 2.12 设计一算法，将一个用循环链表表示的稀疏多项式分解成两个多项式， 使这两个多项式各自仅有奇次幂或偶次幂项，并要求利用原链表中的结点空 间来构造这两个链表。 【题目分析】设循环链表表示的多项式的结点结构为： typedef struct node {int power; float coef; ElemType other; struct node *next; ∥指向后继的指针 ∥幂 ∥系数 ∥其他信息
    }PNode,*PolyLinkedList; 则可以从第一个结点开始，根据结点的幂是奇数或偶数而将其插入到奇次幂 或偶次幂项的链表中。假定用原链表保存偶次幂，要为奇次幂的链表生成一 个表头，为了保持链表中结点的原来顺序，用一个指针指向奇次幂链表的表 尾，注意链表分解时不能“断链”。 void PolyDis(PolyLinkedList poly) ∥将 poly 表示的多项式链表分解为各含奇次幂或偶次幂项的两个循环链 表 {PolyLinkedList poly2=(PolyLinkedList)malloc(sizeof(PNode)); r2=poly2; r1=poly; 结点的指针 p=poly->next; while(p!=poly) ∥poly2 表示只含奇次幂的多项式 ∥r2 是只含奇次幂的多项式链表的尾指针 ∥r1 是只含偶次幂的多项式链表当前结点的前驱 ∥链表带头结点，p 指向第一个元素 if(p->power % 2)∥处理奇次幂 {r=p->next; ∥暂存后继 r2->next=p; ∥结点链入奇次幂链表 r2=p; p=r; } ∥尾指针后移 ∥恢复当前待处理结点 else ∥处理偶次幂 {r1->next=p; r1=p; p=p->next;} } r->next=poly2; r1->next=poly; ∥构成循环链表 }∥PolyDis 2.13 以带头结点的双向链表表示的线性表 L=(a1，a2，…，an)，试写一时 间复杂度为 O(n)的算法，将 L 改造为 L=(a1，a3，…，an，…，a4，a2)。 【题目分析】分析结果链表，易见链表中位置是奇数的结点保持原顺序，而 位置是偶数的结点移到奇数结点之后，且以与原来相反的顺序存放。因此，可从 链表第一个结点开始处理，位置是奇数的结点保留不动，位置是偶数的结点插入 到链表尾部，并用一指针指向链表尾，以便对偶数结点“尾插入”。 DLinkedList DInvert (DLinkedList L) ∥将双向循环链表 L 位置是偶数的结点逆置插入到链表尾部 {p=L->next; ∥p 指向第一元素 ∥Q 指向最后一个元素 ; Q=p->prior; pre=L r=L i=0 while(p {i++ ; ; ∥pre 指向链表中位置为奇数的结点的前驱 ∥r 指向链表中偶数结点的尾结点 ∥i 记录结点序号 != Q) ∥寻找插入位置 ; if(i%2) ∥处理序号为奇数的结点 {p->prior=pre ;pre->next=p ;pre=p; p=p->next;}
    分享到：
    赞 收藏

    相关推荐

    资料库

    课程资源

    共收录17145份资料，累计13个分类，关注成员有19位，主要包括：PHP,网络管理,网页制作,Java,.Net,数据库,3G/移动开发,C/C++,游戏开发,嵌入式,讲义,软件测试,专业指导

    热门标签

    PHP 网络管理 网页制作 Java .Net 数据库 3G/移动开发 C/C++ 游戏开发 嵌入式 讲义 软件测试 专业指导

    最新资料