2022年数据结构绪论试题 .pdf

《2022年数据结构绪论试题 .pdf》由会员分享，可在线阅读，更多相关《2022年数据结构绪论试题 .pdf（8页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、一、选择题1. 算法的计算量的大小称为计算的（）。【北京邮电大学2000 二、 3 （ 20/8 分）】A效率 B. 复杂性 C. 现实性 D. 难度2. 算法的时间复杂度取决于（）【中科院计算所 1998 二、 1 （2 分）】A问题的规模 B. 待处理数据的初态 C. A 和B 3. 计算机算法指的是（1），它必须具备（2） 这三个特性。(1) A 计算方法 B. 排序方法 C. 解决问题的步骤序列 D. 调度方法(2) A 可执行性、可移植性、可扩充性 B. 可执行性、确定性、有穷性C. 确定性、有穷性、稳定性 D. 易读性、稳定性、安全性【南京理工大学 1999 一、 1（2 分）【武

2、汉交通科技大学 1996 一、 1（ 4 分）】4一个算法应该是（）。【中山大学 1998 二、 1（2 分）】A程序 B问题求解步骤的描述 C要满足五个基本特性 DA 和C. 5. 下面关于算法说法错误的是（）【南京理工大学 2000 一、 1（1.5 分）】A算法最终必须由计算机程序实现B.为解决某问题的算法同为该问题编写的程序含义是相同的C. 算法的可行性是指指令不能有二义性 D. 以上几个都是错误的6. 下面说法错误的是（）【南京理工大学 2000 一、 2 （1.5 分）】(1）算法原地工作的含义是指不需要任何额外的辅助空间（2）在相同的规模n 下，复杂度 O(n) 的算法在时间上总

3、是优于复杂度O(2n) 的算法（3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界（4）同一个算法，实现语言的级别越高，执行效率就越低A(1) B.(1),(2) C.(1),(4) D.(3) 7从逻辑上可以把数据结构分为（ ）两大类。 【武汉交通科技大学 1996 一 、4（2 分）】A动态结构、静态结构 B 顺序结构、链式结构C线性结构、非线性结构 D初等结构、构造型结构8以下与数据的存储结构无关的术语是（）。【北方交通大学 2000 二、 1（2 分）】A循环队列 B. 链表 C. 哈希表 D. 栈9以下数据结构中，哪一个是线性结构（）？【北方交通大学 2001 一、 1（2

4、 分）】A广义表 B. 二叉树 C. 稀疏矩阵 D. 串10以下那一个术语与数据的存储结构无关？（）【北方交通大学 2001 一、 2（ 2 分）】A栈 B. 哈希表 C. 线索树 D. 双向链表11 在下面的程序段中，对x 的赋值语句的频度为 （ ） 【北京工商大学 2001 一、10 （3 分）】FOR i:=1 TO n DO FOR j:=1 TO n DO x:=x+1; A O(2n) B O(n) C O(n2) D O(log2 n) 12程序段 FOR i:=n-1 DOWNTO 1 DO FOR j:=1 TO i DO IF AjAj+1 THEN Aj 与 Aj+1 对

5、换；其中 n 为正整数，则最后一行的语句频度在最坏情况下是（）数据结构 1800 题2 郴州都市网www.0735.cc 郴州人才网www.CZHR.com www.989.org 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 8 页 - - - - - - - - - A. O （n） B. O(nlogn) C. O(n3) D. O(n2) 【南京理工大学1998 一、 1(2 分) 】13以下哪个数据结构不是多型数据类型（）【中山大学 1999 一、 3（1 分

6、）】A栈 B广义表 C有向图 D字符串14以下数据结构中，（）是非线性数据结构【中山大学 1999 一、 4】A树 B字符串 C队 D 栈15. 下列数据中，（）是非线性数据结构。【北京理工大学 2001 六、 1（2 分）】A栈 B. 队列 C. 完全二叉树 D. 堆16连续存储设计时，存储单元的地址（）。【中山大学 1999 一、 1（1 分）】A一定连续 B一定不连续 C不一定连续 D部分连续，部分不连续17以下属于逻辑结构的是（）。【西安电子科技大学应用 2001 一、 1】A顺序表 B. 哈希表 C. 有序表 D. 单链表二、判断题1. 数据元素是数据的最小单位。( ) 【北京邮电大

7、学 1998 一、 1（2 分）】【青岛大学 2000 一、 1 （1 分）】【上海交通大学 1998 一、 1】 【山东师范大学 2001 一、 1 （2 分）】2. 记录是数据处理的最小单位。 ( ) 【上海海运学院 1998 一、 5（1 分）】3. 数据的逻辑结构是指数据的各数据项之间的逻辑关系；( ) 【北京邮电大学2002 一、 1（1 分）】4算法的优劣与算法描述语言无关，但与所用计算机有关。( ) 【大连海事大学 2001 一、10（ 1 分）】5健壮的算法不会因非法的输入数据而出现莫名其妙的状态。( )【大连海事大学 2001 一、11（ 1 分）】6算法可以用不同的语言描述

8、，如果用 C 语言或 PASCAL 语言等高级语言来描述，则算法实际上就是程序了。 ( ) 【西安交通大学 1996 二、 7（3 分）】7程序一定是算法。( ) 【燕山大学 1998 二、 2（2 分）并改错】8数据的物理结构是指数据在计算机内的实际存储形式。( ) 【山东师范大学2001 一、 2（2 分）】9. 数据结构的抽象操作的定义与具体实现有关。( )【华南理工大学 2002 一、 1（1 分）】10. 在顺序存储结构中，有时也存储数据结构中元素之间的关系。( ) 【华南理工大学 2002 一、 2 （1 分）】11. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。 (

9、)【上海海运学院 1999 一、 1（1 分）】12. 数据结构的基本操作的设置的最重要的准则是，实现应用程序与存储结构的独立。( ) 【华南理工大学 2002 一、 5（1 分）】13. 数据的逻辑结构说明数据元素之间的顺序关系, 它依赖于计算机的储存结构. ( ) 【上海海运学院 1998 一、 1（1 分）】三、填空1数据的物理结构包括的表示和的表示。【燕山大学 1998 一、 1（2 分）】2. 对于给定的 n 个元素 , 可以构造出的逻辑结构有（1） ， （2） ， （3） ，_（4）_四种。【中科院计算所 1999 二、 1（4 分）】3数据的逻辑结构是指。【北京邮电大学 2001

10、 二、 1（ 2 分）】4一个数据结构在计算机中称为存储结构。【华中理工大学 2000 一、 1（1 分）】名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 8 页 - - - - - - - - - 5抽象数据类型的定义仅取决于它的一组_（1）_，而与 _（2）_无关，即不论其内部结构如何变化，只要它的 _（3）_不变，都不影响其外部使用。【山东大学 2001 三、 3（2 分）】6数据结构中评价算法的两个重要指标是【北京理工大学 2001 七、 1（ 2 分）】7. 数

11、据结构是研讨数据的_（1）_和_（2）_，以及它们之间的相互关系，并对与这种结构定义相应的 _（3）_，设计出相应的（4）_。【西安电子科技大学 1998 二、 2（3 分）】8 一个算法具有 5 个特性 : （1） 、 （2） 、 （3） ，有零个或多个输入、有一个或多个输出。数据结构 1800 题郴州都市网www.0735.cc 郴州人才网www.CZHR.com www.989.org 3 【华中理工大学 2000 一、 2（5 分）】【燕山大学 1998 一、 2（5 分）】9已知如下程序段FOR i:= n DOWNTO 1 DO 语句 1 BEGIN x:=x+1 ； 语句 2 F

12、OR j:=n DOWNTO i DO 语句 3 y:=y+1; 语句 4 END ；语句 1 执行的频度为（1） ；语句 2 执行的频度为（2） ；语句 3 执行的频度为（3） ；语句 4 执行的频度为（4） 。【北方交通大学 1999 二、 4（5 分）】10在下面的程序段中，对的赋值语句的频度为_（表示为 n 的函数）FOR i： TO n DO FOR j： TO i DO FOR k： 1 TO j DO ： delta ；【北京工业大学 1999 一、 6（2 分）】11. 下面程序段中带下划线的语句的执行次数的数量级是：【合肥工业大学1999 三、 1（2 分）】i ：=1； W

13、HILE in DO i：=i*2; 12. 下面程序段中带下划线的语句的执行次数的数量级是( )。【合肥工业大学 2000 三、1（2 分）】i:=1; WHILE in BEGIN FOR j:=1 TO n DO x:=x+1;i:=i*2 END；13. 下面程序段中带有下划线的语句的执行次数的数量级是( ) 【合肥工业大学 2001 三、1（2 分）】i ：=n*n WHILE i1 DO i:=i div 2; 14. 计算机执行下面的语句时，语句s 的执行次数为 _ 。【南京理工大学2000 二、1（1.5 分）】FOR(i=l ；i=i;j-) s; 15. 下面程序段的时间复

14、杂度为_。(n1) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 8 页 - - - - - - - - - sum=1 ；for (i=0;sumn;i+) sum+=1; 【南京理工大学 2001 二、 1（2 分）】16设 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。以下是该函数的程序段，请将未完成的部

15、分填入，使之完整int f(m,n) int m,n; if(m=1) 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) ); 数据结构 1800 题4 郴州都市网www.0735.cc 郴州人才网www.CZHR.com www.989.org 执行程序， f(6,4)= 。 【中科院软件所 1997 二、 1 （9 分）】17. 在有 n 个选手参加的单循环赛中，总共将进行 _场比赛。 【合肥工业大学1999 三、8（2 分）

16、】四、应用题1. 数据结构是一门研究什么内容的学科？【燕山大学 1999 二、 1 （4 分）】2. 数据元素之间的关系在计算机中有几种表示方法？各有什么特点？【燕山大学1999 二、2（4 分）】3. 数据类型和抽象数据类型是如何定义的。二者有何相同和不同之处，抽象数据类型的主要特点是什么？使用抽象数据类型的主要好处是什么？【北京邮电大学 1994 一（ 8 分）】4. 回答问题（每题2 分）【山东工业大学 1997 一 （8 分）】（1）在数据结构课程中，数据的逻辑结构，数据的存储结构及数据的运算之间存在着怎样的关系？（2）若逻辑结构相同但存储结构不同，则为不同的数据结构。这样的说法对吗？

17、举例说明之。（3）在给定的逻辑结构及其存储表示上可以定义不同的运算集合，从而得到不同的数据结构。这样说法对吗？举例说明之。（4）评价各种不同数据结构的标准是什么？5评价一个好的算法，您是从哪几方面来考虑的？【大连海事大学 1996 二、 3 （2 分）】【中山大学 1998 三、 1 （5 分）】6解释和比较以下各组概念【华南师范大学 2000 一（ 10 分）】（1）抽象数据类型及数据类型（2）数据结构、逻辑结构、存储结构（3）抽象数据类型【哈尔滨工业大学 2000 一、 1（3 分）】名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - -

18、- - 名师精心整理 - - - - - - - 第 4 页，共 8 页 - - - - - - - - - （4）算法的时间复杂性【河海大学 1998 一、 2（3 分）】（5）算法【吉林工业大学1999 一、 1（2 分）】（6）频度【吉林工业大学 1999 一、 2（2 分）】7. 根据数据元素之间的逻辑关系，一般有哪几类基本的数据结构？【北京科技大学 1998 一、 1】【同济大学 1998 】8对于一个数据结构，一般包括哪三个方面的讨论？【北京科技大学 1999 一、1（2 分）】9. 当你为解决某一问题而选择数据结构时，应从哪些方面考虑？【西安电子北京科技大学2000】10. 若将

19、数据结构定义为一个二元组（D ， R）, 说明符号 D，R 应分别表示什么？【北京科技大学 2001 一、 1（2 分）】11数据结构与数据类型有什么区别？【哈尔滨工业大学 2001 三、 1（3 分）】12数据的存储结构由哪四种基本的存储方法实现？【山东科技大学 2001 一、1（4 分）】13若有 100 个学生，每个学生有学号，姓名，平均成绩，采用什么样的数据结构最方便，写出这些结构？【山东师范大学 1996 二、 2（2 分）】14. 运算是数据结构的一个重要方面。试举一例， 说明两个数据结构的逻辑结构和存储方式完全相同，只是对于运算的定义不同。因而两个结构具有显著不同的特性，是两个不

20、同的结构。【北京大学 1998 一、 1（ 5 分）】15. 在编制管理通讯录的程序时, 什么样的数据结构合适? 为什么 ?【 长沙铁道学院 1998 四、 3(6 分) 】16. 试举一例，说明对相同的逻辑结构,同一种运算在不同的存储方式下实现，其运算效率不同。【北京理工大学 2000 三、 1（4.5 分）】17. 有实现同一功能的两个算法A1 和A2，其中 A1 的时间复杂度为Tl=O(2n) ，A2 的时间复杂度为 T2=O(n2) ，仅就时间复杂度而言，请具体分析这两个算法哪一个好。【北京航空航天大学 2000 二（ 10 分）】18设计一数据结构，用来表示某一银行储户的基本信息：账

21、号、姓名、开户年月日、储蓄类型、存入累加数、利息、帐面总数。【浙江大学 1994 一 、3（5 分）】19. 写出下面算法中带标号语句的频度。数据结构 1800 题郴州都市网www.0735.cc 郴州人才网www.CZHR.com www.989.org 5 TYPE ar=ARRAY1.n OF datatype; PROCEDURE perm ( a: ar; k, n: integer); VAR x: datatype; i:integer; BEGIN （1）IF k=n THEN BEGIN （2）FOR i:=1 TO n DO （3）write (ai); writeln;

22、END 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 8 页 - - - - - - - - - ELSE BEGIN （4） FOR i:=k TO n DO （5）ai:=ai+i*i; （6） perm (a, k+1, n); END; END; 设k 的初值等于 1。【北京邮电大学 1997 二（ 10 分）】20. 分析下面程序段中循环语句的执行次数。i:=0;s:=0;n:=100; REPEAT i:=i+1; s:=s+10*i; UNTIL NOT(

23、in) AND (sn); 【北京邮电大学 1998 四、 1（5 分）】21下列算法对一n 位二进制数加1，假如无溢出，该算法的最坏时间复杂性是什么？并分析它的平均时间复杂性。TYPE num=ARRAY 1.n of 0.1；PROCEDURE Inc （ VAR a： num ）；VAR i ：integer；BEGIN i ：=n；WHILE Ai=1 DO BEGIN Ai ：=0； i ：=i-1 ；END ；END ；Ai：=1；END Inc ；【东南大学 1998 三 (8 分 ) 1994 二（ 15 分）】22. 阅读下列算法，指出算法A 的功能和时间复杂性PROCEDU

24、RE A (h,g:pointer); (h,g 分别为单循环链表（single linked circular list）中两个结点指针) PROCEDURE B(s,q:pointer)；VAR p:pointer; BEGIN p:=s; 数据结构 1800 题6 郴州都市网www.0735.cc 郴州人才网www.CZHR.com www.989.org WHILE p.nextq DO p:=p.next; p.next:=s; END;(of B) BEGIN B(h,g); B(g,h); END;（of A ）【东南大学 1999 二（ 10 分）】名师资料总结 - - -精品

25、资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 8 页 - - - - - - - - - 23. 调用下列 C 函数 f(n) 或PASACAL 函数 f(n) 回答下列问题 : （1） 试指出 f(n)值的大小，并写出f(n) 值的推导过程 ; （2） 假定 n= 5 ，试指出 f(5) 值的大小和执行f(5) 时的输出结果。C 函数： int f(int n) int i,j， k,sum= 0; for(i=l; ii-1; j-) for(k=1;kj+1;k+ ) sum+; print

26、f(sum=%dn,sum)； return (sum); 【华中理工大学 2000 六（ 10 分）】24设 n 是偶数，试计算运行下列程序段后m 的值并给出该程序段的时间复杂度。m:=0; FOR i:=1 TO n DO FOR j:=2*i TO n DO m:=m+1; 【南京邮电大学 2000 一、 1】25有下列运行时间函数：（1）T1 (n)=1000; （2）T2(n)=n2+1000n; （3）T3(n)=3n3+100n2+n+1; 分别写出相应的大O 表示的运算时间。【吉林工业大学 1999 二（ 12 分）】26. 试给出下面两个算法的运算时间。（1） for i1

27、to n do x x+1 END （2） for i 1 to n do for j1 to n do x x+1 end end 【中科院自动化研究所 1995 二、 2 （6 分）】27. 斐波那契数列Fn 定义如下F0=0， Fl=1， Fn=Fn-1+Fn-2, n=2,3. 请就此斐波那契数列，回答下列问题。(1) (7 分 ) 在递归计算 Fn 的时候，需要对较小的Fn-1，Fn-2， , Fl, F0 精确计算多少次? 数据结构1800 题_ (2) (5 分 ) 如果用大 O 表示法，试给出递归计算Fn 时递归函数的时间复杂度录多少? 【清华大学 2000 二（ 12 分）】

28、28将下列函数，按它们在n时的无穷大阶数，从小到大排序。n, n-n3+7n5, nlogn, 2n/2, n3, logn, n1/2+logn, (3/2)n, ? ? ?名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 8 页 - - - - - - - - - ?n 2n ,n!, n2+logn 【中科院计算所 1995 】名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 8 页 - - - - - - - - -