数据结构练习12综述

1、测试一、选择题1. 算法的时间复杂度取决于（ ）A问题的规模 B. 待处理数据的初态 C. A 和 B2一个算法应该是（）。A 程序 B 问题求解步骤的描述 C 要满足五个基本特性 D A和C.）两大类。顺序结构、链式结构初等结构、构造型结构3从逻辑上可以把数据结构分为（A动态结构、静态结构BC线性结构、非线性结构D双向链表4以下那一个术语与数据的存储结构无关？（）A栈B. 哈希表 C. 顺序表 D.5在下面的程序段中，对 x 的赋值语句的频度为（ ）FOR i:=1TO nDOFOR j:=1TO nDOx:=x+1;A O(2n)BO(n) CO(n2)DO(log 2n)6以下数据结构中

2、， （ ）是非线性数据结构A树B 字符串 C 队列 D 栈7、下面关于算法说法错误的是（）A算法最终必须由计算机程序实现B. 为解决某问题的算法同为该问题编写的程序含义是相同的C. 算法的可行性是指指令不能有二义性 D. 以上几个都是错误的8程序段 FOR i:=n-1 DOWNTO 1 DOFOR j:=1 TO i DOIF AjAj+1 THEN Aj 与 Aj+1 对换； 其中 n 为正整数，则最后一行的语句频度在最坏情况下是( ) 32A. O(n) B. O(nlogn) C. O(n3) D. O(n 2)9下面关于线性表的叙述中，错误的是哪一个？（）A线性表采用顺序存储，必须占

3、用一片连续的存储单元。B线性表采用顺序存储，便于进行插入和删除操作。C线性表采用链接存储，不必占用一片连续的存储单元。D线性表采用链接存储，便于插入和删除操作。10线性表是具有 n个（）的有限序列（ n0）。A表元素 B字符C 数据元素 D 数据项E信息项111若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删 除运算，则利用( )存储方式最节省时间。A顺序表 B 双链表 C 带头结点的双循环链表 D 单循环链表12. 链表不具有的特点是( ) A插入、删除不需要移动元素 B 可随机访问任一元素C 不必事先估计存储空间 D 所需空间与线性长度成正比13. 若长度为 n 的线性表

4、采用顺序存储结构， 在其第 i 个位置插入一个新元素的 算法的时间复杂度为() (1=iNEXTA P-NEXT=H B P-NEXT=H -NEXT C P=H D 16在一个以 h 为头的单循环链中， p 指针指向链尾的条件是()A. p-next=h B. p-next=NULL C. p-next-next=h D. p-data=-1 17在单链表指针为 p的结点之后插入指针为 s 的结点，正确的操作是：( )。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-n

5、ext;p-next=s;18对于头指针为 head 的带头结点的单链表， 判定该表为空表的条件是 ( ) Ahead=NULL Bhead next=NULL C headnext=head D head!=NULL19不带头结点的单链表 head 为空表的判定条件是()Ahead=NULL Bhead next=NULL C headnext=head D head!=NULL20下述哪一条是顺序存储结构的优点？()A存储密度大 B 插入运算方便 C 删除运算方便 D 可方便 地用于各种逻 辑结构的存储表示21某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个 元素，则采用

6、( )存储方式最节省运算时间。A单链表 B 仅有头指针的单循环链表 C 双链表 D 仅有尾 指针的单循环链表22若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结 点。则采用( )存储方式最节省运算时间。A单链表 B 双链表 C 单循环链表 D 带头结点的双循环链表23在双向链表指针 p 的结点前插入一个指针 q 的结点操作是( )。A. p-Llink=q;q-Rlink=p;p-Llink-Rlink=q;q-Llink=qB. p-Llink=q;p-Llink-Rlink=q;q-Rlink=p;q-Llink=p-Llink;C. q-Rlink=p;q-Llink=

7、p-Llink;p-Llink-Rlink=q;p-Llink=q;D. q-Llink=p-Llink;q-Rlink=q;p-Llink=q;p-Llink=q;24. 在双向链表存储结构中，删除 p 所指的结点时须修改指针( ) A (p.llink).rlink:=p.rlink (p.rlink).llink:=p.llink; B p.llink:=(p.llink).llink (p.llink).rlink:=p;C (p.rlink).llink:=pp.rlink:=(p.rlink).rlinkD p.rlink:=(p.llink).llink p.llink:=(p.

8、rlink).rlink;二、判断题1. 数据元素是数据的最小单位。 ( )2. 记录是数据处理的最小单位。 ( ) 3算法的优劣与算法描述语言无关，但与所用计算机有关。 ( ) 4健壮的算法不会因非法的输入数据而出现莫名其妙的状态。 ( ) 5算法可以用不同的语言描述，如果用 C 语言或 PASCAL语言等高级语言来描 述，则算法实际上就是程序了。 ( ) 6程序一定是算法。 ( ) 7数据的物理结构是指数据在计算机内的实际存储形式。 ( )8. 数据的逻辑结构是指数据的各数据项之间的逻辑关系； ( )9. 数据结构的抽象操作的定义与具体实现有关。 ( )10. 在顺序存储结构中，有时也存储

9、数据结构中元素之间的关系。 ( )11. 数据的逻辑结构说明数据元素之间的顺序关系 , 它依赖于计算机的储存结构。 ( )12. 链表中的头结点仅起到标识的作用。 ( )13线性表采用链表存储时， 结点和结点内部的存储空间可以是不连续的。 ( ) 14顺序存储方式插入和删除时效率太低， 因此它不如链式存储方式好。 ( ) 15顺序存储方式只能用于存储线性结构。 ( )16. 线性表的特点是每个元素都有一个前驱和一个后继。 ( )17. 循环链表不是线性表 . ( )18. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。 ( )19. 链表是采用链式存储结构的线性表 , 进行插入、删除

10、操作时，在链表中比在 顺序存储结构中效率高。 ( )20. 线性表只能用顺序存储结构实现。 ( )21. 线性表就是顺序存储的表。 ( ) 22集合与线性表的区别在于是否按关键字排序。 ( )填空1数据的物理结构包括的表示和 的表示。2. 对于给定的 n 个元素 , 可以构造出的逻辑结构有 (1) ， ( 2) ， (3) _(4)_四种。3数据结构中评价算法的两个重要指标是。4. 数据结构是研讨数据的 _(1)_和_(2)_，以及它们之间的相互关系，并对 与这种结构定义相应的 _( 3) _，设计出相应的( 4) _。5 一个算法具有 5 个特性 : (1) 、 ( 2) 、 (3) ，有零

11、个或多个输入、 有一个或多个输出。6一个数据结构在计算机中称为存储结构。7. 下面程序段中带下划线的语句的执行次数的数量级是：i ：=1； WHILE in DO i ： =i*2;8. 计算机执行下面的语句时，语句 s 的执行次数为 。FOR(i=l ； i=i;j-) s;9设 m.n 均为自然数， m可表示为一些不超过 n 的自然数之和， f(m,n) 为这种 表示方式的数目。例f(5,3)=5 ，有 5种表示方式：3+2，3+1+1，2+2+1，2+1+1+1， 1+1+1+1+1。以下是该函数的程序段，请将未完成的部分填入，使之完整 int f(m,n)int m,n; if(m=1

12、) return (1) ;if(n=1)return (2) ;if(mn)return f(m,m);if (m=n)return 1+ (3) ; return f(m.n-1)+f(m-n, (4) ); 执行程序， f(6,4)= 。10线性表 L=(a1,a2, ,an)用数组表示， 假定删除表中任一元素的概率相同， 则删除一个元素平均需要移动元素的个数是 。11在一个长度为 n 的顺序表中第 i 个元素( 1=i=n)之前插入一个元素时，需向后移动 个元素12链接存储的特点是利用 来表示数据元素之间的逻辑关系13. 带头结点的双循环链表 L 中只有一个元素结点的条件是： 14.

13、在单链表 L 中，指针 p 所指结点有后继结点的条件是： _15在单链表中设置头结点的作用是 。16. 带头结点的双循环链表 L 为空表的条件是： 。17. 在单链表 p 结点之后插入 s 结点的操作是： 。18. 已知指针 p 指向单链表 L中的某结点，则删除其后继结点的语句是： 四、简答题1、设有数据逻辑结构为：B=(K,R) K=k1,k2, ,k9R=, ,画出这个逻辑结构的图示，并确定相对于关系 R，哪些结点是开始结点，哪些结 点是终端结点。2、数据的存储结构由哪四种基本的存储方法实现？3、有实现同一功能的两个算法 A1和A2，其中 A1的时间复杂度为 Tl=O(2 n) ，A2 的

14、时间复杂度为 T2=O(n2) ，仅就时间复杂度而言， 请具体分析这两个算法哪一个 好。4分析下列程序段的时间复杂度1、for(i=0;in;i+)y=y+1;for(j=0;j=2*n;j+)x+;2、设 n 为偶数，试计算运行下列程序段后 m的值并给出该程序段的时间复杂度。 m=0;for(i=1;i=n;i+) for(j=2*i;j=n;j+) m+;3、阅读下列算法：void suanfa(int n)int i,j,k,s,x; for(s=0;i=0;in;i+) for(j=I;jn;j+)s+;i=1; j=n; x=0;while (inext-next=L 14、p-ne

15、xt!=null15、主要是使插入和删除等操作统一， 在第一个元素之前插入 元素 和删除第一个 结点不必另作判断。另外，不论链表是否为空，链表指针不变16 L-next=L & L-prior=L 17s-next=p-next;p-next=s;18 u=p-next; p-next=u-next; free（u）;四、1、2四种表示方法（1）顺序存储方式。数据元素顺序存放，每个存储结点只含一个元素。存储 位置反映数据元素间的逻辑关系。存储密度大，但有些操作（如插入、删除）效 率较差。（2）链式存储方式。每个存储结点除包含数据元素信息外还包含一组（至少 一个)指针。指针反映数据元素间的逻辑关

16、系。这种方式不要求存储空间连续， 便于动态操作(如插入、删除等) ，但存储空间开销大(用于指针) ，另外不能折 半查找等。(3) 索引存储方式。除数据元素存储在一地址连续的内存空间外，尚需建立 一个索引表，索引表中索引指示存储结点的存储位置 (下标)或存储区间端点 (下 标)，兼有静态和动态特性。(4) 散列存储方式。通过散列函数和解决冲突的方法，将关键字散列在连续 的有限的地址空间内， 并将散列函数的值解释成关键字所在元素的存储地址， 这 种存储方式称为散列存储。 其特点是存取速度快， 只能按关键字随机存取， 不能 顺序存取，也不能折半存取。3对算法 A1和 A2的时间复杂度 T1和 T2取

17、对数，得 nlog 2和2log n。显然，算 法 A2 好于 A1。4、221 、 n+1,n,n(2n+2), n(2n+1) T(n)=4n2+5n+1=O(n2)2 、设 n 为偶数，外循环 i=1 时，内循环 j 从 2 到 n, 语句 m+执行 n-1 次；外循环 i=2 时，内循环 j 从 4 到 n，语句 m+执行 n-3 次；外循环 i=n/2, 内循环 j从n到n，语句 m+执行 1次；当外循环 in/2 时，内循环不执行。而 m的值即为内循环执行的次数， 所以 m=n-1+n-3+.+1( 共 n/2 个元素，(n-1+1)/2/2)=n 2/4n/2 n n/ 2 n/

18、2或者： T(n) 1 (n 2i 1) n*n/2 2 i n/2 n2 /4i 1 j 2i i 1 i 1n 1n 1 n 13、(1)“s+；”语句的执行次数为：1 n i n(n 1)/2i 0 j i i 0(2)“x+=2；”语句的执行次数为 m,在退出 while 循环时 ,i 变为 m+1,j 变为 n-m，应满足条件 m+1=n-m，m=(n-1)/2=n/2( 向下取整 )(3)T(n)=O(n2)( 4) s=15,x=44、设 hanoi(n,) 算法的频度为 T(n), 则 hanoi(n-1,) 的频度为 T(n-1), 以 上述算法可知：T(n)=2*T(n-1)+12=2*(2*T(n-2)+1)+1=2 2 T(n-2)+2+1=2 2(T(n-