《数据结构》课后题及答案

第一章 绪论

一、选择题

1、( )是数据的基本单位。

A) 数据结构 B)数据元素 C)数据项 D)数据类型 2、以下说法不正确的是( )。

Ａ)数据结构就是数据之间的逻辑结构。

Ｂ)数据类型可看成是程序设计语言中已实现的数据结构。 Ｃ)数据项是组成数据元素的最小标识单位。 Ｄ)数据的抽象运算不依赖具体的存储结构。

3、计算机算法是解决问题的有限运算序列,它具备输入、输出和（ ）等5个特性。 A)可执行性、可移植性和可扩充性 B)可行性、确定性和有穷性 C)确定性、有穷性和稳定性 D)易读性、稳定性和安全性 4、一般而言，最适合描述算法的语言是( )。

A)自然语言 B)计算机程序语言 C)介于自然语言和程序设计语言之间的伪语言 D)数学公式 5、通常所说的时间复杂度指( )。

A)语句的频度 B)算法的时间消耗 C)渐近时间复杂度 D)最坏时间复杂度

6、A算法的时间复杂度为O(n3)，B算法的时间复杂度为O(2n)，则说明( )。 A)对于任何数据量，A算法的时间开销都比B算法小 B)随着问题规模n的增大，A算法比B算法有效 C)随着问题规模n的增大，B算法比A算法有效 D)对于任何数据量，B算法的时间开销都比A算法小 7、算法分析的目的是（ ）。

A)找出数据结构的合理性 B)研究算法中的输入和输出的关系 C)分析算法的效率以求改进 D)分析算法的易懂性和文档性 8、下面程序段的时间复杂度为（ ）。 for( i=0; i

A)O(m2) B) O(n2) C) O(m*n) D) O(m+n) 9、下面算法的时间复杂度为( )。 int f ( int n )

{ if ( n= =0 || n= =1 ) return 1; else return n*f (n-1); }

2

A) O(1) B) O(n) C) O(n) D) O(n!)

二、填空题

1、数据的( )结构依赖于计算机语言。

2、在线性结构中，第一个结点（ ）前驱结点,其余每个结点有且只有（ ）个前驱结点；最后一个结点（ ）后继结点；其余每个结点有且只有（ ）个后继结点。

41

3、在树形结构中,树根结点没有（ ）结点，其余每个结点有且只有（ ）个前驱结点；叶子结点没有（ ）结点，其余每个结点的后继结点可以（ ）。

4、在线性结构、树形结构和图形结构中，前驱和后继结点之间分别存在着( ) 、（ ）和（ ）的关系。

5、评价一个算法优劣的两个主要指标是（ ）和（ ）。

6、数据的逻辑结构被分为( )、( )、( )和( )四种。 7、数据的存储结构被分为( )、（ ）、（ ）、（ ）四种. 8、算法的时间复杂度除了与问题的规模有关外，还与输入实例的( )有关。

三、问答题与算法题

1、 简述下列概念：

数据元素： 数据结构： 数据类型：

数据的逻辑结构及其4种类型： 数据的存储结构及其4种方式：

2、设两个算法在同一台机器上执行，其执行时间分别是 n2和2 n ，要使前者快于后者，n至少需要多大？

3、有时为比较两个同数量级的算法优劣，须突出主项的常数因子，而将低次项用”O”记号表示。如：设T1 ( n ) = 1.39 n log n + 100 n + 256 = 1.39 n log n + O ( n ) ; T2 ( n ) = 2.0 n log n -2 n = 2.0 n log n –O( n ) ;

这两个式子表示，当n足够大时，T1 ( n )优于T2 ( n )，因为前者的系数因子小于后者。请用此方法表示下列函数，并指出当n足够大时，哪一个较优，哪一个较劣。 (1 ) T1 ( n ) = 5n 2 -3 n +60 log n ; (2 ) T2 ( n ) = 3 n 2 +1000 n + 3 log n ; (3 ) T3 ( n ) = 8 n 2 + 3 log n ; (4 ) T4 ( n ) = 1.5 n 2 + O ( n ) 。

4、计算执行下面程序段时，执行S语句的次数为。 for(i=1; i<=n; i++)

for( j=1; j<=i; j++) S;

第二章 线性表

一、 选择题

1、线性表是具有n个（ ）的有限序列。

A) 数据项； B) 数据元素； C) 数据对象； D) 表元素。 2、以下关于线性表的说法不正确的是( )。

A) 线性表中的数据元素可以是数字、字符、记录等不同类型。 B) 线性表中包含的数据元素个数不是任意的。

C) 线性表中的每个结点都有且只有一个直接前趋和直接后继。

42

D) 存在这样的线性表：表中各结点都没有直接前趋和直接后继。 3、线性表的顺序存储结构是一种( )的存储结构。

A) 随机存取 B) 顺序存取 C) 索引存取 D) 散列存取

4、在顺序表中，只要知道( )，就可在相同时间内求出任一结点的存储地址。 A) 基地址 B) 结点大小 C) 线性表大小 D) 基地址和结点大小 5、下面关于线性表的叙述中，错误的是哪一个？（ ） A) 线性表采用顺序存储，必须占用一片连续的存储单元。 B) 线性表采用顺序存储，便于进行插入和删除操作。 C) 线性表采用链接存储，不必占用一片连续的存储单元。 D) 线性表采用链接存储，便于插入和删除操作。 6、线性表采用链表存储时其存储地址要求（ ）。 A) 必须是连续的； B) 部分地址必须是连续的； C) 必须是不连续的； D) 连续和不连续都可以。

7、一个长度为n的线性表顺序存储，向第i个元素(1≤i≤n+1)之前插入一个新元素时，需要从后向前依次后移 ( ) 个元素。

A) n-i B) n-i+1 C) n-i-1 D) i 8、( )运算中，使用顺序表比链表好。

A) 插入 B) 删除 C) 根据序号查找 D) 根据元素值查找

9、向具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是( )。 A) O(1) B) O(n) C) O(n2) D) O(log2n)

10、在一个长度为n的顺序存储的线性表中，删除第i个元素(1≤i≤n)时，需要从前向后依次前移( )个元素。

A) n-i B) n-i+1 C) n-i-1 D) i

11、在一个长度为n的线性表中顺序查找值为x的元素时，平均查找长度（即x同元素的平均比较次数，假定查找每个元素的概率都相等）为 ( )。 A) n B) n/2 C) (n+1)/2 D) (n-1)/2

12、在一个带头结点的单链表HL中，若要向表头插入一个由指针p指向的结点，则 执行的语句是( )。

A) HL = p; p->next = HL; B) p->next = HL; HL = p;

C) p->next = HL; p = HL; D) p->next = HL->next; HL->next = p;

13、在一个单链表HL中，若要在指针q所指的结点的后面插入一个由指针p所指的结点，则执行( )。

A) q->next = p->next ; p->next = q; B) p->next = q->next; q = p;

C) q->next = p->next; p->next = q; D) p->next = q->next ; q->next = p;

14、在一个单链表HL中，若要删除由指针q所指向结点的后继结点，则执行( )。 A) p = q->next ; p->next = q->next; B) p = q->next ; q->next = p;

C) p = q->next ; q->next = p->next; D) q->next = q->next->next; q->next = q;

15、在双向链表中，在指针p所指的结点前插入一个指针q所指的结点，操作是（ ）。

A) p->Prior=q; q->Next=p; p->Prior->Next=q; q->Prior=q；

B) p->Prior=q; p->Prior->Next=q; q->Next=p; q->Prior=p->Prior; C) q->Next=p; q->Prior=p->Prior; p->Prior->Next=q; p->Prior=q; D) q->Prior=p->Prior; q->Next=q; p->Prior=q; p->next=q;

二、 填空题

43

1、对于一个具有n个结点的单链表，在已知结点*p的后插入一个新结点的时间复杂度为（ ）,在给定值为x的结点后插入一个新结点的时间复杂度为（ ）。 2、根据线性表的链式存储结构中每一个结点包含的指针个数，将线性链表分成

（ ）和（ ）。

3、顺序存储结构是通过( )表示元素之间的关系的;链式存储结构是通过( )表示元素之间的关系的。

4、对于双向链表,在两个结点之间插入一个新结点需修改( )个指针，单链表为 ( )个。

5、循环单链表的最大优点是( ) 。

6、在无头结点的单链表中，第1个结点的地址存放在头指针中，其他结点的存储地址存放在( )结点的next域中。

7、带头结点的双循环链表L为空表的条件是（ ）。

8、当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用( )存储结构。

9、求顺序表和单链表的长度算法的时间复杂度分别是 ( )和 ( )。 10、顺序表存储结构的优点是( )、( )、

( )；缺点是 ( )。

11、单链表存储结构的优点是( )、 ( )；缺点是

( )、 ( )。

12、在单链表中，设置头结点的作用是 ( ) 。

13、链接存储的特点是利用( )来表示数据元素之间的逻辑关系。 14、带头结点的双循环链表DL为空表的条件是：( )。

15、以下算法的功能是：在一个非递减的顺序表中，删除所有值相等的多余元素。在画线处填上适当的语句，将程序补充完整。 # define maxlen 100 typedef struct {

elemtype a[ maxlen ] ; int length ; } sqlist ;

void delequil ( sqlist & S ) { int j=1 , i = 2 ;

while ( _________________ ) { if ( S.a[ i ] != S.a[ j ] ) { ____________ ; ______________ ; } i ++ ; }

______________ ; }

16．设双链表的结点的存储结构如下：删除链表中指针p所指结点的两步主要操作是：

p Llink Data Rlink

44