《数据结构课后练习题汇编》由会员分享，可在线阅读，更多相关《数据结构课后练习题汇编（55页珍藏版）》请在金锄头文库上搜索。
1、数据结构课后练习题第一章 绪论一、选择题1、数据结构被形式定义为（D ，S ） ，其中 D 是（ ）的有限集合， S 是 D 上的（ ）有限集合。A、 算法 B、数据元素 C、数据操作 D、逻辑关系 E、操作 F、映象 G、存储 H、关系2、数据结构是一门研究非数值计算的程序设计问题中计算机的（ （1） ）以及它们之间的（ ）和运算的学科。（1）A、操作对象 B、计算方法 C、逻辑存储 D、数据映象（2）A、结构 B、关系 C、运算 D、算法3、算法分析的目的是（ ） ，算法分析的二个主要方面是（ ） 。A、给出数据结构的合理性 B、研究算法中输入输出的关系C、空间复杂性和时间复杂性 D、分析
2、算法的效率以求改进E、正确性和简明性 F、分析算法的易懂性和文档性4、在数据结构中，从逻辑上可以把数据结构分成（ ） 。A、 动态和静态结构 B、紧凑接和非紧凑结构C、线性与非线性结构 D、内部结构和外部结构5、计算机算法指的是（ ） ，它必具备输入、输出和（ ）5 个特性。A、计算方法 B、排序方法 C、解决问题的有限运算序列 D、可行性、可移植性和可扩充性 E、可行性、确定性和有穷性6、线性表的顺序存储结构是一种（ ）的存储结构，线性表的链式存储结构是一种（ ）A、随机存取 B、顺序存取 C、索引存取 D、散列存取7、算法的时间复杂度取决于（ ）A、 问题的规模 B、待处理数据的初态 C、
3、问题的规模和待处理数据的初态8、线性表若采用链表存储结构时，要求内存中可用存储单元的地址（ ）A、必须是连续的 B、部分地址必须是连续的C、一定是不连续的 D、连续不连续都可以9、在以下的叙述中，正确的是（ ）A、线性表的线性存储结构优于链式存储结构B、二维数组是它的每个数据元素为一个线性表的线性表C、栈的操作方式是先进先出D、队列的操作方式是先进后出10、根据数据元素之间关系的不同特性，以下四类基本的逻辑结构反映了四类基本的数据组织形式。以下解释错误的是 ( )A、集合中任何两个结点之间都有逻辑关系但组织形式松散B、线性结构中结点按逻辑关系依次排列形成一条锁链C、树形结构具有分支、层次特性，
4、其形态有点像自然界中的树D、图状结构中的各个结点按逻辑关系互相缠绕，任何两个结点都可以邻接11、以下说法正确的是( )A、数据元素是数据的最小单位B、数据项是数据的基本单位C、数据结构是带有结构的各数据项的集合D、数据结构是带有结构的数据元素的集合二、填空题1、数据逻辑结构包括（ ）四种类型，树型和图型结构合称（ ） 。2、对于给定的 n 个元素，可以构造出的逻辑结构有（ ） 、 （ ） 、 （ ）和（ ）四种。3、算法的五个重要特性是（ ） 。4、评价算法的性能从利用计算机资源角度看主要从（ ）方面进行分析。5、线性结构中元素之间存在（ ）关系，树型结构中元素之间存在（ ）关系，图型结构中元
5、素之间存在（ ）关系。6、下面程序段的时间复杂度是（ ） 。i=s=0; while(sj)j+;else I+;2、写出下面算法中带标号语句的频度。Void perm(int a,k,n) int x,I;(1) if(k=n)(2) for(I=1;I,(2) B=(K,R),其中：K=a,b,c,d,e,f,g,h R=(r) r=,(3)C=(K,R),其中：k=1,2,3,4,5,6 R=r r=(1,2),(2,3),(2,4),(3,4),(3,5),(3,6),(4,5),(4,6)(4)D=(K.R), K=48,25,64,57,82,36,75,R=r1,r2r1=,r2
6、=,5、设有如图所示的逻辑结构图，给出它的逻辑结构。6、简述下列术语：数据，数据元素，数据结构，数据对象。7、逻辑结构与存储结构是什么关系?8、将数量级 ，n，n 2，n 3，nlog 2n，log 2n，2 n， ， n!， ， ，按增长率进行排列。10 n3232五、算法设计题1. 已知输入 x,y,z 三个不相等的整数，设计一个算法，使得这三个数按从大到小输出，并考虑所用算法的比较次数和元素移动次数。2. 编写在输入 10 个数中找出最小或最大的数的算法。3. 在数组 An中查找值为 k 的元素,若找到则输出其位置 i(1i n), 否则输出 0 作为标志。设计求解此问题的类 C 语言算
7、法，并分析其最坏情况时间复杂度。第二章 线性表练习题一、选择题1、表长为 N 的顺序表，当在任何位置上插入或删除一个元素的概率相等时，插入一个元素所需移动元素的平均次数为（ ） ，删除一个元素需要移动的元素个数为（ ） 。A. (N-1)/2 B. N C. N+1 D. N-1 E. N/2 F. (N+1)/2 G. (N-2)/22、线性表是具有 N 个（ ）的有限序列。A、表元素 B、字符 C、数据元素 D、数据项 E、信息3、 “线性表的逻辑顺序和物理顺序总是一致的。 ”这个结论是（ ） 。A、正确的 B、错误的 C、不一定，与具体结构有关。4、线性表采用链式存储结构时，要求内存中可
8、用存储单元的地址（ ） 。A、必须是连续的 B、部分地址必须是连续的 C、一定是不连续的 D、连续或不连续都可以。5、带头结点的单链表为空的判定条件是（ ） 。 A、head=NULL B、head-next=NULL C、head-next=head D、head!=NULL6、不带头结点的单链表 head 为空的判定条件是（ ） 。 A、head=NULL B、head-next=NULL C、head-next=head D、head!=NULL7、非空的循环单链表 head 的尾结点 P 满足（ ） 。A、P-NEXT=NULL B、p=NULL C、p-next=head D、p=h
9、ead8、在一个具有 n 个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是（ ） 。A、O(1) B、O(n) C、O(n 2) D、O(nlog 2n)9、在一个单链表中，若删除 P 所指结点的后继结点，则执行（） 。、p-next=p-next-next 、p=p-next;p-next=p-next-next 、p-next=p-next; 、p=p-next-next; 10、在一个单链表中，若在所指结点之后插入所指结点，则执行（） 。、s-next=p;p-next=s; 、s-next=p-next;p-next=s; 、s-next=p-next;p=s; 、p-nex
10、t=s;s-next=p;11、在一个单链表中，已知 q 是 p 的前趋结点，若 q 和 p 之间插入结点 s，则执行（） 。、s-next=p-next;p-next=s; 、p-next=s-next;s-next=p; 、q-next=s;s-next=p;、p-next=s;s-next=q;12、假设双链表结点的类型如下：typedef struct linknodeint data;数据域struct linknode *llink;指向前趋结点的指针域struct linknode *rlink;指向后继结点的指针域bnode现将一个 q 所指新结点作为非空双向链表中的 p 所指
11、结点的前趋结点插入到该双链表中，能正确完成此要求的语句段是（） 。、q-rlink=p;q-llink=p-llink;p-llink=q;p-llink-rlink=q;、p-llink=q;q-rlink=p;p-llink-rlink=q;q-llink=p-llink、q-llink=p-rlink;q-rlink=p;p-llink-rlink=q;p-llink=q;、以上都不对、如上题结点结构，如在此非空循环双向链表的结点 p 之后插入结点 s 的操作序列是（） 。、p-rlink=s;s-llink=p;p-rlink-llink=s;s-rlink=p-rlink;、p-rl
12、ink-s;p-rlink-llink=s;s-llink=p;s-rlink=p-rlink;、s-llink=p;s-rlink=p-rlink;p-rlink=s;p-rlink-llink=s;、s-llink=p;s-rlink=p-rlink;p-rlink-llink=s;p-rlink=s;14、在一个长度为 n 的单链表上，设有头和尾两个指针，执行（）操作与链表的长度无关。、删除单链表中的第一个元素、删除单链表中最后一个元素、在单链表第一个元素前插入一个新元素、在单链表最后一个元素后插入一个新元素15、线性结构中的一个结点代表一个（ ）A、数据元素 B、数据项 C、数据 D、
13、数据结构16、非空线性表 L=(a1,a2,ai,an)，下列说法正确的是（ ）A、每个元素都有一个直接前驱和直接后继B、线性表中至少要有一个元素C、表中诸元素的排列顺序必须是由小到大或由大到小的D、除第一个元素和最后一个元素外其余每个元素都有一个且仅有一个直接前驱和直接后继17、顺序表是线性表的（ ）A、链式存储结构 B、顺序存储结构 C、索引存储结构 D、散列存储结构18、对于顺序表，以下说法错误的是（ ）A、顺序表是用一维数组实现的线性表，数组的下标可以看成是元素的绝对地址 B、顺序表的所有存储结点按相应数据元素间的逻辑关系决定的次序依次排列C、顺序表的特点是:逻辑结构中相邻的结点在存储
14、结构中仍相邻D、顺序表的特点是:逻辑上相邻的元素，存储在物理位置也相邻的单元中19、对顺序表上的插入、删除算法的时间复杂性分析来说，通常以（ ）为标准操作。A、插入操作 B、结点移动 C、算术表达式 D、删除操作20、对于顺序表的优缺点，以下说法错误的是（ ）A、无需为表示结点间的逻辑关系而增加额外的存储空间B、可以方便地随机存取表中的任一结点C、插入和删除运算较方便D、由于顺序表要求占用连续的空间，存储分配只能预先进行( 静态分配)21、若某线性表中最常用的操作是取第 i 个元素和找第 i 个元素的前趋元素，则采用（ ）存储方式最节省时间。A、顺序表 B、单链表 C、双链表 D、单循环链表22、循环链表主要优点是（ ）A、不再需要头指针了B、已知某个结点的位置后，能够容易找到它的直接前趋C、在进行插入、删除运算时，能更好地保证链表不断开D、从表中任一结点出发都能扫描到整个链表23、在线性表的下列存储结构中，读取元素花费时间最少的是（ ）A、单链表
