由于我实在是太菜了,于是就有了这篇文章,仅供参考,不说了,充电了~

练习题一

选择题
  1. 线性结构中数据元素之间是( )关系。
    A.一对多 B.多对多 C.多对一 D.一对一
    答:D
  2. 数据结构中与所使用的计算机无关的是数据的( )结构。
    A.存储 B.物理 C.逻辑 D.物理和存储
    答:C
  3. 算法分析的目的是( )。
    A.找出数据结构的合理性
    B.研究算法中的输入和输出的关系
    C.分析算法的效率以求改进
    D.分析算法的易懂性和文档性
    答:C
  4. 算法分析的两个主要方面是( )。
    A.空间复杂性和时间复杂性
    B.正确性和简明性
    C.可读性和文档性
    D.数据复杂性和程序复杂性
    答:A
  5. 计算机算法指的是( )。
    A.计算方法
    B. 排序方法
    C.求解问题的有限运算序列
    D.调度方法
    答:C
  6. 计算机算法必须具备输入、输出和( )等 5 个特性。
    A.可行性、可移植性和可扩充性
    B.可行性、确定性和有穷性
    C.确定性、有穷性和稳定性
    D.易读性、稳定性和安全性
    答:B
填空题
  1. 数据结构包括数据的逻辑结构、数据的存储结构和数据的运算这三个方面的内容。

  2. 数据结构按逻辑结构可分为两大类,它们分别是线性结构非线性结构

  3. 数据结构被形式地定义为(D,R),其中 D 是数据元素的有限集合,R 是 D 上的关系有限集合。

  4. 线性结构中,第一个结点没有前驱结点,其余每个结点有且只有 1 个前驱结点;最后一个结点没有后继结点,其余每个结点有且只有 1 个后继结点。

  5. 树形结构中,树根结点没有前驱结点,其余每个结点有且只有1个前驱结点;叶子结点没有后继结点,其余每个结点的后继结点数可以是任意多个

  6. 图形结构中,每个结点的前驱结点数和后继结点数可以是(任意多个)。

  7. 数据的存储结构主要有四种,它们分别是顺序链式索引哈希存储结构。

  8. 一个算法的效率可分为时间效率和空间效率。

简答题
  1. 数据结构和数据类型两个概念之间有区别吗?
    简单地说,数据结构定义了一组按某些关系结合在一起的数组元素的集合。数据类型不仅定义了一组数据元素,而且还在其上定义了一组操作。

  2. 简述线性结构、树形结构和图形结构的不同点。
    线性结构反映结点间的逻辑关系是一对一的,树形线性结构反映结点间的逻辑关系是一对多的,图在结构反映结点间的逻辑关系是多对多的。

  3. 设有采用二元组表示的数据逻辑结构 S=(D,R),其中 D={a,b,…,i},R={(a,b),(a,c),(c,d),(c,f),(f,h),(d,e),(f,g),(h,i)},问相对于关系 R,哪些结点是开始结点,哪些结点是终端结点?
    该逻辑结构为树形结构,其中 a 结点没有前驱结点,称为根结点,b、e、g、i 结点没有后继结点,是终端结点,也称为叶子结点。

  4. 以下各函数是算法中语句的执行频度,n 为问题规模,给出对应的时间复杂度:

1
2
3
4
T1(n)=nlog2n-1000log2n
T2(n)=n的log2为底3次方-1000log2n
T3(n)=n2-1000log2n
T4(n)=2nlog2n-1000log2n

T1(n)=O(nlog2n),T2(n)=O(n的log2为底3次方),T3(n)=O(n2),T4(n)=O(nlog2n)。

  1. 分析下面程序段中循环语句的执行次数。
1
2
3
4
5
6
int j=0,s=0,n=100;
do
{
j=j+1;
s=s+10*j;
} while (j<n && s<n);

j=0,第 1 次循环:j=1,s=10。第 2 次循环:j=2,s=30。第 3 次循环:j=3,s=60。第 4 次循环:j=4,s=100。while 条件不再满足。所以,其中循环语句的执行次数为 4。

  1. 执行下面的语句时,语句 s++的执行次数为多少?
1
2
3
4
int s=0;
for (i=1;i<n-1;i++)
for (j=n;j>=i;j--)
s++;

语句 s 的执行次数。(n+3)(n-2)/2

  1. 设 n 为问题规模,求以下算法的时间复杂度。
1
2
3
4
5
6
void fun1(int n)
{ int x=0,i;
for (i=1;i<=n;i++)
for (j=i+1;j<=n;j++)
x++;
}

其中 x++语句属基本运算语句,n(n-1)/2=O(n2)。

  1. 设 n 为问题规模,是一个正偶数,试计算以下算法结束时 m 的值,并给出该算法的时间复杂度。
1
2
3
4
5
6
7
void fun2(int n)
{
int m=0;
for (i=1;i<=n;i++)
for (j=2\*i;j<=n;j++)
m++;
}

由于内循环 j 的取值范围,所以 i≤n/2,则m=n的平方/4,该程序段的时间复杂度为 O(n2)。