资源预览内容
第1页 / 共11页
第2页 / 共11页
第3页 / 共11页
第4页 / 共11页
第5页 / 共11页
第6页 / 共11页
第7页 / 共11页
第8页 / 共11页
第9页 / 共11页
第10页 / 共11页
亲,该文档总共11页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
第一章概论 自测题答案 一、填空题1. 数据结构是一门研究非数值计算的程序设计问题中计算机的 操作对象 以及它们之间的 关系 和运算等的学科。2. 数据结构被形式地定义为(D, R),其中D是 数据元素 的有限集合,R是D上的 关系 有限集合。3. 数据结构包括数据的 逻辑结构 、数据的 存储结构 和数据的 运算 这三个方面的内容。4. 数据结构按逻辑结构可分为两大类,它们分别是 线性结构 和 非线性结构 。5. 线性结构中元素之间存在一对一关系,树形结构中元素之间存在一对多关系,图形结构中元素之间存在多对多关系。6 在线性结构中,第一个结点 没有 前驱结点,其余每个结点有且只有 1个前驱结点;最后一个结点 没有 后续结点,其余每个结点有且只有1个后续结点。7. 在树形结构中,树根结点没有 前驱 结点,其余每个结点有且只有 1 个前驱结点;叶子结点没有 后续 结点,其余每个结点的后续结点数可以任意多个 。8. 在图形结构中,每个结点的前驱结点数和后续结点数可以 任意多个 。9数据的存储结构可用四种基本的存储方法表示,它们分别是顺序 、 链式 、 索引 和 散列 。10. 数据的运算最常用的有5种,它们分别是插入 、 删除、修改、 查找 、排序。11. 一个算法的效率可分为 时间 效率和 空间 效率。二、单项选择题( B )1. 非线性结构是数据元素之间存在一种:A)一对多关系 B)多对多关系 C)多对一关系 D)一对一关系( C )2. 数据结构中,与所使用的计算机无关的是数据的 结构;A) 存储 B) 物理 C) 逻辑 D) 物理和存储( C )3. 算法分析的目的是:A) 找出数据结构的合理性 B) 研究算法中的输入和输出的关系C) 分析算法的效率以求改进 D) 分析算法的易懂性和文档性( A )4. 算法分析的两个主要方面是:A) 空间复杂性和时间复杂性 B) 正确性和简明性C) 可读性和文档性 D) 数据复杂性和程序复杂性( C )5. 计算机算法指的是:A) 计算方法 B) 排序方法 C) 解决问题的有限运算序列 D) 调度方法( B )6. 计算机算法必须具备输入、输出和 等5个特性。A) 可行性、可移植性和可扩充性 B) 可行性、确定性和有穷性C) 确定性、有穷性和稳定性 D) 易读性、稳定性和安全性三、简答题2.【严题集1.2】数据结构和数据类型两个概念之间有区别吗?答:简单地说,数据结构定义了一组按某些关系结合在一起的数组元素。数据类型不仅定义了一组带结构的数据元素,而且还在其上定义了一组操作。3. 简述线性结构与非线性结构的不同点。答:线性结构反映结点间的逻辑关系是 一对一的,非线性结构反映结点间的逻辑关系是多对多的。四、【严题集1.8】分析下面各程序段的时间复杂度2. s=0; for i=0; in; i+)for(j=0; jn; j+) s+=Bij;sum=s;答:O(n2)1. for (i=0; in; i+)for (j=0; jm; j+)Aij=0;答:O(m*n)3. x=0;for(i=1; in; i+) for (j=1; j=n-i; j+)x+;解:因为x+共执行了n-1+n-2+1= n(n-1)/2,所以执行时间为O(n2)4. i=1; while(i=n) i=i*3;答:O(log3n)五、设有数据逻辑结构S=(D,R),试按各小题所给条件画出这些逻辑结构的图示,并确定相对于关系R,哪些结点是开始结点,哪些结点是终端结点? 1. 【严蔚敏习题集P7 1.3】D=d1,d2,d3,d4 R=(d1,d2),(d2,d3),(d3,d4) 答: d1d2d3d4 d1无直接前驱,是首结点 d4无直接后继是尾结点2。D=d1,d2,d9 R=(d1,d2),(d1,d3),(d3,d4),(d3,d6),(d6,d8),(d4,d5), (d6,d7),(d8,d9) 答: 此图为树形结构 d1无直接前驱,是根结点 d2,d5,d7,d9无直接后继是叶子结点3D=d1,d2,d9 R=(d1,d3),(d1,d8),(d2,d3),(d2,d4),(d2,d5),(d3,d9), (d5,d6),(d8,d9),(d9,d7), (d4,d7), (d4,d6)答: 此图为图形结构 d1,d2无直接前驱,是开始结点 d6,d7无直接后继是终端结点 (2) (3)第2章 自测卷答案 一、填空1. 【严题集2.2】在顺序表中插入或删除一个元素,需要平均移动 表中一半元素,具体移动的元素个数与 表长和该元素在表中的位置 有关。2. 线性表中结点的集合是 有限 的,结点间的关系是 一对一 的。3. 向一个长度为n的向量的第i个元素(1in+1)之前插入一个元素时,需向后移动 n-i+1 个元素。4. 向一个长度为n的向量中删除第i个元素(1in)时,需向前移动 n-i 个元素。5. 在顺序表中访问任意一结点的时间复杂度均为 O(1) ,因此,顺序表也称为 随机存取 的数据结构。6. 【严题集2.2】顺序表中逻辑上相邻的元素的物理位置 必定相邻。单链表中逻辑上相邻的元素的物理位置 不一定 相邻。7. 【严题集2.2】在单链表中,除了首元结点外,任一结点的存储位置由 其直接前驱结点的链域的值 指示。8 在n个结点的单链表中要删除已知结点*p,需找到它的前驱结点的地址,其时间复杂度为O(n)。二、判断正误(在正确的说法后面打勾,反之打叉)( )1. 链表的每个结点中都恰好包含一个指针。 答:错误。链表中的结点可含多个指针域,分别存放多个指针。例如,双向链表中的结点可以含有两个指针域,分别存放指向其直接前趋和直接后继结点的指针。( )2. 链表的物理存储结构具有同链表一样的顺序。错,链表的存储结构特点是无序,而链表的示意图有序。( )3. 链表的删除算法很简单,因为当删除链中某个结点后,计算机会自动地将后续的各个单元向前移动。错,链表的结点不会移动,只是指针内容改变。( )4. 线性表的每个结点只能是一个简单类型,而链表的每个结点可以是一个复杂类型。错,混淆了逻辑结构与物理结构,链表也是线性表!且即使是顺序表,也能存放记录型数据。( )5. 顺序表结构适宜于进行顺序存取,而链表适宜于进行随机存取。 错,正好说反了。顺序表才适合随机存取,链表恰恰适于“顺藤摸瓜”( )6. 顺序存储方式的优点是存储密度大,且插入、删除运算效率高。错,前一半正确,但后一半说法错误,那是链式存储的优点。顺序存储方式插入、删除运算效率较低,在表长为n的顺序表中,插入和删除一个数据元素,平均需移动表长一半个数的数据元素。( )7. 线性表在物理存储空间中也一定是连续的。错,线性表有两种存储方式,顺序存储和链式存储。后者不要求连续存放。( )8. 线性表在顺序存储时,逻辑上相邻的元素未必在存储的物理位置次序上相邻。错误。线性表有两种存储方式,在顺序存储时,逻辑上相邻的元素在存储的物理位置次序上也相邻。( )9. 顺序存储方式只能用于存储线性结构。错误。顺序存储方式不仅能用于存储线性结构,还可以用来存放非线性结构,例如完全二叉树是属于非线性结构,但其最佳存储方式是顺序存储方式。(后一节介绍)( )10. 线性表的逻辑顺序与存储顺序总是一致的。错,理由同7。链式存储就无需一致。三、单项选择题( C )1数据在计算机存储器内表示时,物理地址与逻辑地址相同并且是连续的,称之为:(A)存储结构 (B)逻辑结构 (C)顺序存储结构 (D)链式存储结构( B )2.一个向量第一个元素的存储地址是100,每个元素的长度为2,则第5个元素的地址是 (A)110 (B)108 (C)100 (D)120( A )3. 在n个结点的顺序表中,算法的时间复杂度是O(1)的操作是:(A) 访问第i个结点(1in)和求第i个结点的直接前驱(2in) (B) 在第i个结点后插入一个新结点(1in)(C) 删除第i个结点(1in)(D) 将n个结点从小到大排序( B )4. 向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变,平均要移动 个元素(A)8 (B)63.5 (C)63 (D)7( A )5. 链接存储的存储结构所占存储空间:(A) 分两部分,一部分存放结点值,另一部分存放表示结点间关系的指针(B) 只有一部分,存放结点值(C) 只有一部分,存储表示结点间关系的指针(D) 分两部分,一部分存放结点值,另一部分存放结点所占单元数( B )6. 链表是一种采用 存储结构存储的线性表;(A)顺序 (B)链式 (C)星式 (D)网状( D )7. 线性表若采用链式存储结构时,要求内存中可用存储单元的地址:(A)必须是连续的 (B)部分地址必须是连续的(C)一定是不连续的 (D)连续或不连续都可以( B )8 线性表在 情况下适用于使用链式结构实现。()需经常修改中的结点值 ()需不断对进行删除插入 ()中含有大量的结点 ()中结点结构复杂( C )9 单链表的存储密度()大于1; ()等于1; ()小于1; ()不能确定( B )10 设a1、a2、a3为3个结点,整数P0,3,4代表地址,则如下的链式存储结构称为P034P0a13a24A30()循环链表 ()单链表 ()双向循环链表 ()双向链表四、简答题1. 【严题集2.3】试比较顺序存储结构和链式存储结构的优缺点。在什么情况下用顺序表比链表好?答: 顺序存储时,相邻数据元素的存放地址也相邻(逻辑与物理统一);要求内存中可用存储单元的地址必须是连续的。优点:存储密度大(1?),存储空间利用率高。缺点:插入或删除元素时不方便。链式存储时,相邻数据元素可随意存放,但所占存储空间分两部
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号