《数据结构》综合练习一Word下载.doc

1、D） 两者长度均可变7.单链表L中，P所指结点为尾结点的条件为 _B_ 。A） PL B） P-next=NULLC） P.next:L D） Pnil8.与数据元素本身的形式、内容、相对位置及个数无关的是数据的 _C_ 。A） 存储结构B） 存储实现 C） 逻辑结构D） 运算实现9.单链表中，增加头结点的目的是 _C_ 。A） 使单链表至少有一个结点B） 表示单链表中首结点的位置C） 方便运算的实现 D） 说明单链表是线性表的链式存储结构10. 数据结构是一门研究非数值计算的程序设计问题中计算机的_A_以及它们之间的关系和运算等的学科。 A）操作对象 B）计算方法 C）逻辑存储 D）数据映像

2、11.算法分析的目的是_B_。 A）找出数据结构的合理性 B）分析算法的效率以求改进 C）研究算法中的输入和输出的关系 D）分析算法的易懂性和文档性12.在长度为n的顺序表的第i（1in+1）个位置上插入一个元素，元素的移动次数为_A_。A）n-i+1 B）n - i C）i D）i-113. 不带头结点的单链表 head为空的判断条件为_A_。 A）head =Null B） head -next = Null C） head -next = head D） head ! = Null 14. 数据结构被形式地定义为（D，S），其中D是数据元素的有限集合，S是D上_B_的有限结合。A）操作

3、B）关系 C）存储D）映像15.线性结构的顺序存储结构是一种 A 的存储结构。A）随机存取B）顺序存取C）索引存取D）散列存取16.组成数据的基本单位是_C_。 A）数据项B）数据类型C）数据元素D）数据变量17. 双循环链表的*p结点之后插入*s结点的操作是 -DA）p-next=s，s-prior=p，p-next-prior=s，s-next=p-next；B）p-next=s，p-prior=s，s-prior=p，s-C）s-next，prior=s；D）s-prior=s，p-next=s；18.一维数组和线性表的共同点是 A 。A） 两者都是相同类型数据的集合B） 两者都允许不同

4、类型数据共存C） 两者长度均固定19. 线性链表中各链接结点之间的地址_A_。A）连续与否都可以 B）必须连续C）一定不连续D）部分地址必须连续20. 对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构为 C 。A）单链表B）用头指针表示的单循环链表 C）用带尾指针表示的单循环链表D）顺序表二.多选题1. 下列关于链式存储结构的叙述中，正确的是_ACD_。 A） 结点除自身信息外还包括指针域，因此存储密度小于 顺序存储结构 B） 可以通过计算直接确定第i个结点的存储地址 C） 逻辑上相邻的结点物理上不必相邻 D） 插入、删除操作方便，不必移动结点2. 下面的叙述正确的是_AD_。（0

5、6）A）线性表在链式存储时，查找第i个元素的时间同i的值成正比B）线性表在链式存储时，查找第i个元素的时间同i的值无关C）线性表在顺序存储时，查找第i个元素的时间同i 的值成正比D）线性表在顺序存储时，查找第i个元素的时间同i的值无关3. 链表具有的特点是_ABD_。A）插入、删除不需要移动元素B）不必事先估计存储空间C）可随机访问任一元素D）所需空间与链表长度成正比4. 下列关于链式存储结构的叙述中，正确的是_AD_。A） 结点除自身信息外还包括指针域，因此存储密度小于顺序存储结构B） 可以通过计算可以直接确定第i个结点的存储地址C） 逻辑上相邻的结点物理上必须相邻D） 插入、删除操作方便，

6、不必移动结点5. 数据元素之间的关系在计算机中的表示方法有_AD_。A）顺序映像 B）线性结构 C）非线性结构D） 非顺序映像三、判断题1. 数据结构中与所使用的计算机无关的是数据的逻辑结构。2. 线性表是一个有序序列，其中可包含相同的元素，也允许各个元素可以是不同的数据类型。3. 链表的每个结点都含有两个指针。4.线性结构的基本特征是：每个结点有且仅有一个直接前趋和一个后继。5.线性表中各元素类型必须是相同的。 6.数据结构的操作一定是定义在逻辑结构上，实现在存储结构上。7.数据的逻辑结构指的是数据元素之间的逻辑关系的整体。正确 1 5 6 7四、填空题1. 数据结构包括的三个方面的内容是

7、、 和 。2. 通常衡量算法效率的一般标准为 和 。3. 算法是对特定问题求解步骤的一种描述，它具有有穷性、确定性、可行性、_及一个或多个输出等重要特征。4. 数据结构是相互之间存在一种或多种关系的_集合。5. 线性结构中元素的关系是_的关系。答案：1 逻辑结构、存储结构、运算 2 时间复杂度、空间复杂度 3 具有零个或多个输入 4 数据元素 5 一对一6. 用一维数组表示线性表L=（a1,a2,an），假定删除表中任一元素的概率相同（都为1/n），则删除一个元素平均需移动的元素个数为_ 。（n-1）/2 7.当线性表采用顺序存储结构进行存储时，其主要特点是 _ 。逻辑结构相邻的结点存储结构也

8、相邻8.链式存储结构最显著的优点是 _。 方便插入、删除操作9.单循环链表的最显著的优点是 _ 。答：从任意结点出发都可以访问链表中的每个元素10.一个线性表第一个元素的存储地址是100，每个元素的长度为2，则第6个元素的地址是_ 。110五、简答题1解释数据结构、逻辑结构、存储结构的概念，并讨论他们之间的关系；参考答案：数据结构：相互之间存在一种或多种特定关系的数据元素的集合。逻辑结构：逻辑结构描述数据之间的逻辑关系。包括集合、线性、树形和网状结构。存储结构：数据结构在计算机中的表示称存储结构。包括顺序、索引、链式和散列。三者关系：在数据结构中，数据的逻辑结构和存储结构密切相关的；存储结构不

9、仅存储数据元素，还要存储数据元素的逻辑关系；逻辑结构与计算机无关；逻辑结构相同但存储结构不同，可以是不同的数据结构。2线性表的顺序存储具有如下缺点：（1）.在进行插入或删除操作时，需要移动大量元素；（2）.由于难以估计其大小，必须预先分配较大的存储空间，往往使存储空间得不到充分利用；（3）.表的容量难以扩充。试问线性表的链式存储结构是否一定能克服上述缺点？试做简要讨论。链式存储结构一般克服的顺序结构的三个弱点：首先，链式存储结构插入、删除不需要移动元素，只需修改指针，时间复杂度为O（1）；其二，不需要预先分配存储空间，可根据需要动态申请；其三，表容量只受内存空间的限制缺点：因指针增加了内存空间

10、开销，当空间不允许时，就不能克服顺序存储的优点。六、编程题1已知两个带头结点的单链表La和Lb中的元素按非递减顺序排列，试用C语言编写一个函数将这两个有序表合并成一个有序单链表保存在La中，而不改变其排序性。设带头结点的单链表的结点结构说明及函数名如下：n typedef struct node /*定义结点结构*/ datatype data; struct node next; lklist;n typedef struct node *pointer;n 函数首部为： pointer mergelklist（lklist ha,lklist hb）1题参考答案pointer mergel

11、klist（lklist ha,lklist hb） pointer *h, *pa, *pb ; pa=ha-next, pb=hb- h= r = ha； while（pa & pb） If（pa-data data） /*移动ha, hb头指针, 修改r指向 r-next =pa; r=pa; pa= pa-next ； else next =pb; r=pb; pb= pb-next ； if（pa=NULL） r-next=pb; if（pb=NULL） r-next=pa; return h； 2 设计算法求两个递增有序的顺序表L1和L2中的公共元素，并将其置入顺序表L3中，用C语

12、言实现。设顺序表存储结构说明如下：n typedef struct ElemType *elem; Int length ;sqlist;n sqlist L1,L2,L3; status complist（sqlist L1, sqlist L2, sqlist L3）2题参考答案status complist（sqlist L1, sqlist L2, sqlist L3） i1=0,i2=0,i3=0; L3.length=0; while（i1=L1.length-1）& （i2=L2.length-1） if（L1.elemi1 L2.elemi2） i2=i2+1; if（L1.elemi1 = L2.elemi2） L3.elemi3= L1.elemi1; i3=i3+1; i1=i1+1; i2=i2+1; L3.length=i3;