数据结构习题第2章习题

数据结构习题第2章习题Tag内容描述：<p>1、第2章 线 性 表 习 题 1 设线性表存放在数组A arrsize 的前num个分量中 且递增有序 试写一算法 将x 插入到线性表的适当位置上 并保持线性表的有序性 分析算法的时间复杂度 2 已知一顺序表A 其元素值非递减有序排列 编写一个算法 删除顺序表中多余的值相同的元素 3 写一个算法 从一给定的顺序表A中删除值在x y x y 之间的所有元素 要求以较高的效率来实现 4 线性表中有n个元。</p><p>2、第2章习题答案 l 习题2-1 179 62 34 57 26 48 226 34 48 57 62 79 348 56 57 62 79 34 456 57 79 34 526 34 39 48 57 62 l 习题2-3 1 ElemType delete_min(List ElemType e; if(Emptylist(L) printf(线性表为空！n); exit(1); l。</p><p>3、第二章 习题一 判断题1线性表的逻辑顺序与存储顺序总是一致的。2顺序存储的线性表可以按序号随机存取。3顺序表的插入和删除操作不需要付出很大的时间代价，因为每次操作平均只有近一半的元素需要移动。 4线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此是属于同一数据对象。5在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上并。</p><p>4、27 第 2 章 数组 一一、复习要点复习要点 本章主要讨论数组抽象数据类型及利用数组实现的顺序表、 字符串等数据结构。 它们都 是线性结构。但数组是直接存取结构，可以根据数组元素的下标直接在数组中存取该元素， 而利用它实现的顺序表是顺序存取结构， 所有数据元素集中存储于表的前端。 字符串是顺序 表的特化。 本章复习的要点： 1、基本知识点 理解作为抽象数据类型定义的数组类，掌握在 C+ 中数组的定义和初始化方法，明确静态 数组和动态数组的不同特点和使用， 特别需要注意的是数组的存储结构不一定是一个连续的存储 空间，当数。</p><p>5、StatusInsert Sq SqList La ElemTypex 已知顺序表La中元素依值非递减有序排列 本算法 插入新的元素x并保持原表的有序性 返回OK 若顺序表空间已满 则不再插入并返回OVERFLOWif La length La listsize returnOVERFLOW i 0 while ilength Insert Sq 2 2设顺序表va中的数据元素递增有序 试写一算法。</p><p>6、第二章 习题 一 判断题 1 线性表的逻辑顺序与存储顺序总是一致的 2 顺序存储的线性表可以按序号随机存取 3 顺序表的插入和删除操作不需要付出很大的时间代价 因为每次操作平均只有近一半的元素需要移动 4 线性表中的元素可以是各种各样的 但同一线性表中的数据元素具有相同的特性 因此是属于同一数据对象 5 在线性表的顺序存储结构中 逻辑上相邻的两个元素在物理位置上并不一定紧邻 6 在线性表的链式存储。</p><p>7、7若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点。则采用（ ）存储方式最节省运算时间。【北京理工大学 2000 一、1（2分）】A单链表 B双链表 C单循环链表 D带头结点的双循环链表8. 静态链表中指针表示的是（ ）. 【北京理工大学 2001 六、2（2分）】A 内存地址 B数组下标 C下一元素地址 D左、右孩子地址9. 链表不具有的。</p><p>8、,0,1.对于栈操作数据的原则是（）。A.先进先出B.后进先出C.后进后出D.不分顺序2.在作进栈运算时,应先判别栈是否(),在作退栈运算时应先判别栈是否()。当栈中元素为n个,作进栈运算时发生上溢,则说明该栈的最大容量为()。为了增加内存空间的利用率和减少溢出的可能性,由两个栈共享一片连续的内存空间时,应将两栈的()分别设在这片内存空间的两端,这样,当()时，才产生上溢。,:A。</p><p>9、第一章 概论数据结构作业一、填空题01、数据结构是一门研究非数值计算的程序设计问题中计算机的( )以及它们之间的( )等的学科。02、数据结构被形式地定义为(D,R)，其中D是( )的有限集合，R是D上的( )有限集合。03、数据结构包括数据的( )、数据的( )和数据的( )这三个方面的内容。04、数据结构按逻辑结构可分为两大类，它们分别是( )和( )。05、线性结构中元素之间存在( )关系，树形结构中元素之间存在( )关系，图形结构中元素之间存在( )关系。06、在线性结构中，第一个结点( )前驱结点，其余每个结点有且只有1个前驱结点；最后一个结点(。</p><p>10、第2章 线性数据结构5有一线性表存储在一个带头结点的循环单链表L中，写出计算线性表元素个数的算法。解： int getLength(LinkList *L) LinkList *p = NULL;int len = 0;p = L-next; /带有头结点，所以从头节点的下一个节点开始计数 while( p ) len+; p。</p><p>11、1 L head头结点R head head 11 级计本 信本级计本 信本 第第 3 章章 栈和队列栈和队列 自测卷答案自测卷答案 一 填空题 每空一 填空题 每空 1 分 共分 共 15 分 分 1 向量 栈和队列都是向量 栈和队列都是 线性线性 结构 可以在向量的结构 可以在向量的 任何任何 位置插入和删除元素 对于栈只能在位置插入和删除元素 对于栈只能在 栈顶栈顶 插入和删除元素 对于队列。</p><p>12、计科系 2011 级网络工程 1 班 计算机科学与技术 2 班 算法与数据结构 课后习题 第 7 章 第 1 页 共 11 页 课后习题课后习题 第第 7 7 章章 图图 2011 级 班 学号 姓名 A 题 号一二三四五总分 得 分 一 判断题 如果正确 在对应位置写 T T 否则写 F F 每题 0 5 分 共 5 分 12345678910 1 图 G 由两个集合 V G 和 E G 所组成。</p><p>13、1. 一棵度为2的树与一棵二叉树有何区别？,2. 分别画出具有3个结点的树和具有3个结点的二叉树的所有不同形态。,3. 假设一棵二叉树的先序序列为EBADCFHGIKJ 和中序序列为ABCDEFGHIJK。请画出该树。,4. 编写算法，计算二叉树中叶子结点的数目。,5.构造一棵哈夫曼树（将概率作为节点的权值） 7， 19，2，6，32，3，21，10.,作业:,1. 一棵度为2的树与一棵二叉树有。</p><p>14、第7章 图 一、单项选择题 1在一个无向图G中，所有顶点的度数之和等于所有边数之和的______倍。 Al/2 B1 C2 D4 2在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的______倍。 Al/2 B1 C2 D4 3一个具有n个顶点的无向图最多包含______条边。 An Bn1 Cn-1 D。</p><p>15、第7章 图习题参考答案 一、单选题（每题1分，共16分） （ C ）1. 在一个图中，所有顶点的度数之和等于图的边数的 倍。 A1/2 B. 1 C. 2 D. 4 （ B ）2. 在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的 倍。 A1/2 B. 1 C. 2 D. 4。</p><p>16、第10章 习题 一、选择题 1下列内部排序算法中： 【北京工业大学 2000 一、1 (10分 每问2分)】 A快速排序 B.直接插入排序 C. 二路归并排 序 D. 简单选择排序 E. 起泡排序 F. 堆排序 （1） 其比较次数与序列初态无关的算法是（ dc ） （2）不稳定的排序算法是（ adf ） （3）在初始序列已基本有序（除去n个元素中的 某k个元素后即呈有序，k 快速排序 归并排序 E以上答案都 不对 【西安交通大学 1996 三、1 (3分)】 13将两个各有N个元素的有序表归并成一个有序 表,其最少的比较次数是( a ) AN B2N-1 C2N DN-1 二、判断题 1在执行某个排序算法。</p>