1-4章习题答案 下载本文

一、名词解释(见教材)

数据结构、数据结构的逻辑结构、数据结构的物理结构、算法、算法评价、时间复杂度、大O表示法、线性表、栈、队列、广义表、稀疏矩阵 二、填空

1、数据的逻辑结构被分为_集合结构_、_线性结构___、_树形结构__、__图形结构__4种。

2、数据的存储结构被分为_顺序结构__、链接结构_、索引结构_、和__散列结构__4种。

3、在定义某种数据结构时,其数据域的数据类型可分为 简单类型 和 结构体类型 两种,为增强其通用性,应将其再定义为 通用数据 类型。

4、如果将线性数据结构关系描述为1:1,那么树型和图型数据结构应分别为 1:N 、 M:N 。

5、数据结构简单地说是指 数据 以及相互之间的 联系 。

6、算法应具备以下5个特性: 有穷性 、 正确性 、 可行性 、输入和输出。

7、在分析各种算法的时间复杂度时,一般只讨论相应的数量级,用f(n)表示,请问其中n的含义是 处理问题的样本量 。

8、对于一个单链表,在表头插入结点的时间复杂度为 O(1) ,在表尾插入元素的时间复杂度为 O(n) 。

9、 在表长为n的顺序表中,在等概率情况下,插入和删除一个元素平均需移动 表长的一半(即n/2 ) 个元素,具体移动元素的个数与表长(n) 和 该元素在表中的位置 有关。

10、顺序表的定义如下: typedef int ElemType;

1

struct List{

ElemType *list; int size; int MaxSize;

};

其中ElemType的含义是:通用数据 类型;size的含义是:顺序表中元素的个数。

11、 设单链表中指针p 指向结点A,q指针指向其后继结点。若要删除A的后继结点(假设A存在后继结点),则需修改指针的操作为p->next=q->next;。

12、栈的运算规则为 后进先出 ,队列的运算规则为 先进先出 。

13、一个函数调用了自身,这是 递归 调用。

14、非零元素个数远远少于零元素个数的矩阵称为 稀疏矩阵 。

15、顺序存储的稀疏矩阵采用三元组线性表存储,定义如下: struct Triple{ };

struct SMatrix{ };

其中row的含义是:非零元素所在的 行 ;t的含义是:非零元素的个数。

int m,n,t;

struct Triple sm[11]; int row,col; ElemType val;

三、选择题

1、顺序表物理结构中的存储单元( A )。

A. 一定是连续的 B. 一定是不连续的 C. 不一定是连续的 D. 经删除操作后不连续

2、对一个线性表的存取操作很少,而插入和删除操作较多时应采用 B 数据结构。

2

A.线性表 B. 队列 C. 图 D. 树

3、对一个线性表的随机存取操作较多时,应采用 B 存储结构。 A.静态顺序存储 B. 动态顺序存储 C. 动态链接存储 D. 静态链接存储

4、 顺序表适用于( A ) 的场合。

A. 频繁查询 B. 频繁插入与删除 C. 问题规模较小 D. 问题规模较大

5、 链表不具有的特点是(A )。

A. 可随机访问任一元素 B. 插入、删除不需要移动元素 C. 不必事先估计存储空间 D. 所需空间与线性表长度成正比

6、栈的插入和删除操作在( A )进行。

A.栈顶 B.栈底 C.栈顶或栈底 D.任意位置

7、向一个顺序栈S(栈顶指针为top)中插入元素x时,首先要( B )。 A.S->stack[S->top]=x;

C.S ->top--;

8、对一个顺序存储结构的栈,栈满的判断条件是( D ) A.S.top= =-1 B.S.top= =0

C.S.top= =MaxSize D. S.top= =MaxSize-1

9、若循环队列有 n个顺序存储单元,front、rear分别为队首和队尾元素的下标,front指向队首元素之前的一个位置,为则判断队满的条件是(C) A. front = =rear B. (front-1)%n= =rear C. (rear+1) %n= =front D. (rear-1)%n= = front

10、若循环队列有 n个顺序存储单元,front、rear分别为队首和队尾元素的下标,front指向队首元素之前的一个位置,为则判断队空的条件是(A) A. front = =rear B. (front-1)%n= =rear C. (rear+1) %n= =front D. (rear-1)%n= = front

3

B.S->top++;

D.x= S->stack[S->top];

11、队的插入操作在( C )进行。

A.队首 B.队首或队尾 C.队尾 D.任意位置

12、下面程序段的时间复杂度为( C )。 for (int i=0;i

for (int j=0;j

a[i][j]=i*j;

A.O(m2) B. O(n2) C.O(m×n) D. O(m+n)

13、一个求从1到正整数n之间所有正整数之和的单循环语句的时间复杂度为(A.O(1) B. O(n) C.O (n2) D. O(n3)

14、下列是顺序存储线性表排序的算法 void Sort(List& L) { int i,j; ElemType x; for(i=1;i=0;j--) if(x

L.list[j+1]=L.list[j];

else

break;

L.list[j+1]=x;

};

}

问:此算法的时间复杂性为: B A. O(n) B.(n2) C. (n*i) D. (n*j) 15、下面程序段的时间复杂度为( B )。

for (int i=1;i<=n;i++)

4

B )。