发布时间 : 星期三 文章数据结构习题1更新完毕开始阅读0c9897303968011ca30091a9
数 据 结 构 习 题 册
（仅供计算机和信息专业同学参考）
计 算 机 科 学 技 术 教 研 室
二ＯＯ八年十一月
基
习
一、选择题
础
题
篇
1
1 计算机算法必须具备输入、输出、（B ）等5个特性。
A 可行性、可移植性和可扩展性 B 可行性、确定性和有穷性 C 确定性、有穷性和稳定性 D 易读性、安全性和稳定性
2 在数据结构中，从逻辑上可以把数据结构分为（D ）
A 动态结构和静态结构 B 紧凑结构和非紧凑结构 C 内容结构和外部结构 D 线性结构和非线性结构
3 下面程序段的时间复杂性的量级为（D ） For (i=1;i<=n;i++) For(j=1;j<=I;j++) For(k=1;k<=j;k++) x=x+1;
A O(1) B O(n) C O(n) D O(n)
4 在数据结构中，与所使用的计算机无关的是数据的（A ）结构 A 逻辑 B 存储 C 逻辑和存储 D 物理
5 数据结构在计算机中的表示是指（C ）
A 数据的逻辑结构 B 数据结构 C 数据的存储结构 D 数据元素之间的关系
6 下面（B ）的时间复杂性最好，即执行时间最短。 A O(n) B O(logn) C O(nlogn) D O(n)
7 下面程序段的时间复杂性的量级为（D ）。 Int fun(int n){ I=1,s=1; While(s s+=++I; return I; } A O(n/2) B O(logn) C O(n) D O(n) 8 下面程序段的时间复杂性的量级为（C）。 For(int i=0;i For(int j=0;j 1 1/2 2 2 3 A[i][j]=i*j; A O(m) B O(n) C O(m*n) D O(m+n) 9 执行下面程序段时，S 语句的执行次数为（A）。 For(int i=1;i For(int j=i+1;j<=n;j++) S; A n(n-1)/2 B n2/2 C n(n-1)/2 D n 3 2 二、简答题 1 数据的逻辑结构有哪几种？常用的存储有哪几种？ 集合 线性结构 树形结构 图状结构 顺序存储结构 链式存储结构 2 举一个数据结构的例子，叙述其逻辑结构、存储结构和运算三方面的内容。 3 什么叫算法？它有哪些特性 4 有下列几种用二元组表示的数据结构，画出它们分别对应的逻辑结构图，并指出它们分别以属于何种结构。 （1）A=(K,R),其中 K={a,b,c,d,e,f,g,h} R={r} r={ K＝{a,b,c,d,e,f,g,h} R={r} r={ R={r} r={(1,2),(2,3),(2,4),(3,4),(3,5),(3,6),(4,5),(4,6)} 三、计算题 设n为整数，求下列各程序段的时间复杂度 （1）i=1;k=2; While(i k=k+10*I; i=i+1; } (2)i=1;j=0; While(i+j<=n) If(i>j)j=j+1; Else i=i+1; (3)x=91;y=100 While(y>0) If(x>100){ 2 x=x-10; y=y-1; }else x=x+1; 习题1参考答案 一、选择题 1. B 2. D 3. D 4. A 5. C 6. B 7. D 8. C 9. A 二、简答题 1. 答：数据的逻辑结构通常有四种，即集合、线性结构、树形结构和图状结构。存储结构主要有顺序存储结构和链式存储结构。 2. 答：比如一分通讯录，记录了相关人员的电话号码，将其按姓名一人占一行构成表，这个表就是一个数据结构。每一行是一个记录，对于整个表来说，只有一个开始结点和一个终端结点，其它结点也只有一个前驱和一个后继。这几个关系就确定了表的逻辑结构。 3. 答：算法是对特定问题求解步骤的一种描述，是指令的有限序列，其中每一条指令表示一个或多个操作。算法具有有穷性、确定性、可行性、输入和输出5个特性。 4.答： (1) A对应的逻辑图形如下图左，它是一种线性结构。 h g f e c e f (2) B对应的逻辑图形如上图右所示，它是一种树型结构。 (3) C对应的逻辑图形如下图所示，它是一种图型结构。 3 1 2 4 5 6 h d a b c d b g a 三、计算题 解： (1) O(n) ； (2) O(n) ； (3) O(n1/2)。 习 一、选择题 题2 1 线性表是（A） A 一个有限序列，可以为空 B 一个有限序列，不能为空 C 一个无限序列，可以为空 D 一个无限序列，不能为空 3