数据结构第12章习题

1、第一章一选择题1.下面属于逻辑结构的是(c)备注：其他都是存储结构，包括循环队列A 顺序表 B哈希表 C 有序表D 单链表2.下面关于算法说法错误的是（ D ）A算法最终必须由计算机程序实现（不见得，有些算法是NP完全问题，计算机程序只能实现低数量的值，对于高数量的是实现不了的）B.为解决某问题的算法同为该问题编写的程序含义是相同的C. 算法的可行性是指指令不能有二义性 D. 以上几个都是错误的3从逻辑上可以把数据结构分为（ C ）两大类。A没有此种分法；不按照存储结构划分；DA动态结构、静态结构 B顺序结构、链式结构 C线性结构、非线性结构 D初等结构、构造型结构4.线性表的静态链表存储结构

2、与顺序存储结构相比优点是（ C ）。A. 所有的操作算法实现简单 B. 便于随机存取C. 便于插入和删除D. 节省存储空间5.采用顺序搜索方法查找长度为n的顺序表时，搜索成功的平均搜索长度为（ D ）。A. n B. n/2 C. (n-1)/2 D. (n+1)/2备注：顺序表的平均查找长度等于所有长度和除以总的次数：(1+2+3+.+n)/n = (1+n)/2；失败的平局查找次数：(0+1+2+.+n-1)/n=(n-1)/2所以答案为(1+n)/26.数据结构的定义为(D，S)，其中D是( B )的集合。备注：S是D上关系的集合A. 算法 B. 数据元素C. 数据操作 D. 逻辑结构7

3、.以下数据结构中，哪一个是线性结构（ D ）？ A广义表 B. 二叉树 C. 稀疏矩阵 D. 串备注：对于数据结构课程而言，简单地说，线性结构是一个数据元素的有序(次序)集合。它有四个基本特征: 1.集合中必存在唯一的一个第一个元素; 2.集合中必存在唯一的一个最后的元素; 3.除最后元素之外，其它数据元素均有唯一的后继; 4.除第一元素之外，其它数据元素均有唯一的前驱。 数据结构中线性结构指的是数据元素之间存在着“一对一”的线性关系的数据结构。 如(a1,a2,a3,.,an),a1为第一个元素，an为最后一个元素，此集合极为一个线性结构的集合。8.在数据结构中，从逻辑上可以把数据结构分成

4、( C )备注：非线性包裹树形和图形结构两种；A. 动态结构和静态结构 B. 紧凑结构和非紧凑结构C. 线性结构和非线性结构 D. 内部结构和外部结构9下段程序段的时间复杂度是 ( D ).备注：怎么求时间复杂度 i1；while(i=n) i=i*2； A.O(n/3)B. O(n2) C. O(log3n) D. O(log2n)10算法分析的目的是( C ).A找出数据结构的合理性B. 研究算法中输入输出的关系C. 分析算法的效率以求改进D. 分析算法的易懂性和文档备注：分析算法的目的就是要降低算法的时间复杂度和空间复杂度，提高算法的执行效率。11在下面的程序段中，对x的赋值语句的频度为

5、（ C ）怎样求频度FOR i:=1 TO n DO FOR j:=1 TO n DO x:=x+1;A O(2n) BO(n) CO(n2) DO(log2n) 12以下数据结构中，（ A ）是非线性数据结构A树 B字符串 C队 D栈13连续存储设计时，存储单元的地址（A ）。A一定连续 B一定不连续 C不一定连续 D部分连续，部分不连续二.填空题1.数据结构是一门研究（ 非数值计算 ）的程序设计问题中计算机的操作对象以及它们之间的关系和操作等的学科。2.根据数据元素之间关系的不同特性，通常有四类基本数据结构：集合、线性结构、（ 树形结构 ）和图状结构。3.一种抽象数据类型包括（ 数据 ）和

6、基本操作两个部分。4.一个“好”的算法应该考虑达到以下目标：（ 正确性 ）、可读性、健壮性、效率和低存储量需求。5. 一个算法的时间复杂度是用该算法操作时重复使用次数的多少来度量的，一个算法的空间复杂度是用该算法在运行过程中所占用的_存储空间_的大小来度量的。6算法具有如下特点：有穷性、可执行性、确定性、结果性、一般性。有穷性、确定性 、可行性、输入和输出。7下面程序段的时间复杂度为。（log3n） i=1;while(i=n)i=i*3; 8.在有n个元素的顺序表中插入一个元素，所需要移动元素的平均个数是（ n/2 ），具体移动元素的个数与（ 元素个数 ）有关。第二章一选择题1下述哪一条是顺

7、序存储结构的优点？（ A）A存储密度大 B插入运算方便 C删除运算方便 D可方便地用于各种逻辑结构的存储表示2下面关于线性表的叙述中，错误的是哪一个？（B ）A线性表采用顺序存储，必须占用一片连续的存储单元。B线性表采用顺序存储，便于进行插入和删除操作。(缺点，要移动大量元素)C线性表采用链接存储，不必占用一片连续的存储单元。D线性表采用链接存储，便于插入和删除操作。3若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ A ）存储方式最节省时间。A顺序表 B双链表 C带头结点的双循环链表 D单循环链表备注：存取任一指定序号 最好是随机存取，则可采用顺序表，而且，

8、删除和插入都是在最后进行的，所以不用移动大量元素即可；4. 若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（ C ）(1=inext=p; p-next=s; B. s-next=p-next; p-next=s; C. s-next=p-next; p=s; D. p-next=s; s-next=p;9.在循环双链表的p所指结点之后插入s所指结点的操作是( B ).A. p-next=s;s-prior=p;p-next-prior=s;s-next=p-next;B. s-prior=p;s-next=p-next;p-next-prior=s;p-

9、next=s; C. s-prior=p;s-next=p-next;p-next=s;p-next-prior=s; D. p-next=s;p-next-prior=s;s-prior=p;s-next=p-next;10在单链表指针为p的结点之后插入指针为s的结点，正确的操作是：（B）。Ap-next=s;s-next=p-next; B s-next=p-next;p-next=s;Cp-next=s;p-next=s-next; D p-next=s-next;p-next=s;11对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是（ B ）Ahead=NULL Bh

10、eadnext=NULL Cheadnext=head Dhead!=NULL二、算法设计1. A和B是两个单链表，表中元素递增有序。试写一算法将A和B归并成一个按元素值递减有序的单链表C。编写一个函数，实现上述算法。 node *mergelink(node *p, node *q) node *h, *r; h = (node*) malloc (sizeof(node); h-next = NULL; r = h; while (p != NULL & q != NULL) if (p-data data) r-next = p; r = p; p = p-next; else r-ne

11、xt = q; r = q; q = q-next; if (p = NULL) r-next = q; if (q = NULL) r-next = p; p = h-next; h = h-next; free(p); return h; 2. 有一个单链表L（至少有1个结点），其头结点指针为head，编写一个过程将L逆置，即最后一个结点变成第一个结点，原来倒数第二个结点变成第二个结点，如此等等。3. 在一个递增有序的线性表中，有数值相同的元素存在。若存储方式为单链表，设计算法去掉数值相同的元素，使表中不再有重复的元素。例如：（7，10，10，21，30，42，42，42，51，70）将变作（7，10，21，30，42，51，70），分析算法的时间复杂度。4.有一有序单链表（按元素值升序排列），表头指针为head，单链表的结点类型如下：typedefstructLnode