李春葆编著：数据结构（C 语言篇）――习题与解析（修订版）语言篇）――习题与解析（修订版）
清华大学出版社清华大学出版社
一、绪论一、绪论
选择题选择题
1.数据结构是一门研究非数值计算的程序设计问题数据结构是一门研究非数值计算的程序设计问题  计算机的计算机的  以及它们之间的以及它们之间的  和运算等的学科。算等的学科。
1 A.数据元素数据元素  B.计算方法计算方法  C.逻辑存储逻辑存储      D.数据映像数据映像
2 A.结构结构    B.关系关系    C.运算运算        D.算法算法
2.数据结构被形式地定义为数据结构被形式地定义为  (K, R)，其中，其中K 是  的有限集，R 是K 上的上的  有限集。有限集。  1 A.算法算法    B.数据元素数据元素  C.数据操作数据操作      D.逻辑结构逻辑结构
2 A.操作操作    B.映像映像    C.存储存储        D.关系关系
3.在数据结构中，从逻辑上可以把数据结构分成在数据结构中，从逻辑上可以把数据结构分成    。
A.动态结构和静态结构动态结构和静态结构
B.紧凑结构和非紧凑结构紧凑结构和非紧凑结构
C.线性结构和非线性结构线性结构和非线性结构
D.内部结构和外部结构内部结构和外部结构
4.线性结构的顺序存储结构是一种线性结构的顺序存储结构是一种  的存储结构，线性表的链式存储结构是一种线性表的链式存储结构是一种  的存储结构。储结构。
A.随机存取随机存取
B.顺序存取顺序存取
C.索引存取索引存取
D.散列存取散列存取
5.算法分析的目的是算法分析的目的是  ，算法分析的两个主要方面是，算法分析的两个主要方面是  。
1  A.出数据结构的合理性出数据结构的合理性    B.研究算法中的输入和输出的关系研究算法中的输入和输出的关系
C.分析算法的效率以求改进分析算法的效率以求改进
D.分析算法的易懂性和文档性分析算法的易懂性和文档性
2  A.空间复杂度和时间复杂度空间复杂度和时间复杂度    B.正确性和简单性正确性和简单性
C.可读性和文档性可读性和文档性
D.数据复杂性和程序复杂性数据复杂性和程序复杂性
6.计算机算法指的是计算机算法指的是  ，它必须具备输入、输出和，它必须具备输入、输出和  等 5个特性。个特性。
1  A.计算方法计算方法    B.排序方法排序方法  C.解决问题的有限运算序列解决问题的有限运算序列  D.调度方法调度方法  2  A.可执行性、可移植性和可扩充性可执行性、可移植性和可扩充性    B.可行性、确定性和有穷性可行性、确定性和有穷性
C.确定性、有穷性和稳定性确定性、有穷性和稳定性
D.易读性、稳定性和安全性易读性、稳定性和安全性
7.线性表的逻辑顺序与存储顺序总是一致的，这种说法线性表的逻辑顺序与存储顺序总是一致的，这种说法    。
A.正确正确
B.不正确不正确
8线性表若采用链式存储结构时，要求内存中可用存储单元的地址线性表若采用链式存储结构时，要求内存中可用存储单元的地址    。
A.必须连续的必须连续的
B.部分地址必须连续的部分地址必须连续的
C.一定是不续的一定是不续的  D 连续不连续都可以连续不连续都可以  9.以下的叙述中，正确的是以下的叙述中，正确的是    。
A.线性表的存储结构优于链式存储结构线性表的存储结构优于链式存储结构
B.二维数组是其数据元素为线性表的线性表二维数组是其数据元素为线性表的线性表
C.栈的操作方式是先进先出栈的操作方式是先进先出
D.队列的操作方式是先进后出队列的操作方式是先进后出
10.每种数据结构都具备三个基本运算：插入、删除和查，这种说法每种数据结构都具备三个基本运算：插入、删除和查，这种说法    。
A.正确正确
B.不正确不正确
填空题填空题
1.数据逻辑结构包括三种类型数据逻辑结构包括三种类型        、      和    ，树形结构和图形结构合称为    。
2.在线性结构中，第一个结点在线性结构中，第一个结点    前驱结点，其余每个结点有且只有前驱结点，其余每个结点有且只有  个前驱结点；最后一个结点最后一个结点    后续结点，其余每个结点有且只有后续结点，其余每个结点有且只有    个后续结点。个后续结点。
3.在树形结构中，树根结点没有在树形结构中，树根结点没有    结点，其余每个结点有且只有结点，其余每个结点有且只有  个前驱结点；叶子结点没有子结点没有    结点，其余每个结点的后续可以结点，其余每个结点的后续可以    。
4.在图形结构中，每个结点的前驱结点数和后续结点数可以在图形结构中，每个结点的前驱结点数和后续结点数可以      。
5.线性结构中元素之间存在线性结构中元素之间存在    关系，树形结构中元素之间存在关系，树形结构中元素之间存在    关系，图形结构中元素之间存在构中元素之间存在    关系。关系。
6.算法的五个重要特性是算法的五个重要特性是    、    、    、    、    。
7.下面程序段的时间复杂度是下面程序段的时间复杂度是    。
for( i = 0; i < n; i++) 
for( j = 0; j < m; j++) 
A[i][j] = 0; 
8.下面程序段的时间复杂度是下面程序段的时间复杂度是    。
i = s = 0; 
while ( s < n) 
{ 
i ++;        /* i = i +1*/ 
s += i;      /* s = s + i*/ 
} 
9.下面程序段的时间复杂度是下面程序段的时间复杂度是    。
s = 0; 
for( i = 0; i < n; i++) 
for( j = 0; j < n; j++) 
s += B[i][j]; 
sum = s; 
10.下面程序段的时间复杂度是下面程序段的时间复杂度是    。
i = 1; 
while ( i <= n ) 
i = i * 3; 二、线性表
二、线性表  单项选择题单项选择题
1.一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是个元素的地址是  。  A.110    B.108  C.100      D.120 
2.一个栈的入栈序列是a 、b 、c 、d 、e ，则栈的不可能输出序列是，则栈的不可能输出序列是        。  A.edcba    B.decba      C.dceab      D.abcde 
3.若一个栈的入栈序列是1、2、3、…、…  、n ，其输出序列为p 1、p 2、p 3、…、…
、p n ，若p 1=n ，则p i 为      。
A. i
B. n = i 
C. n - i +1
D.不确定不确定
4.栈结构通常采用的两种存储结构是栈结构通常采用的两种存储结构是      。
A.线性存储结构和链表存储结构线性存储结构和链表存储结构
B.散列方式和索引方式散列方式和索引方式
C.链表存储结构和数组链表存储结构和数组
D.线性存储结构和非线性存储结构线性存储结构和非线性存储结构
5.判断一个栈ST (最多元素为m) 为空的条件是为空的条件是      。
A.ST->top!=0
B. ST->top==0 
C. ST->top!= m 
D. ST->top== m 
6.判断一个栈ST (最多元素为m) 为满栈的条件是为满栈的条件是      。
A.ST->top!=0
B. ST->top==0 
C. ST->top!= m-1 
D. ST->top== m-1 7.栈的特点是栈的特点是  1 ，队列的特点是，队列的特点是  2 。
A.先进先出先进先出
B.先进后出先进后出
8.一个队列的入队序列是1、2、3、4，则队列输出序列是，则队列输出序列是    。
A.4、3、2、1
B.1、2、3、4
C.1、4、3、2 
D.3、2、4、1 
9.判断一个队列QU (最多元素为最多元素为m) 为空的条件是为空的条件是      。
A. QU->rear －QU->front == m
B. QU->rear －QU->front －1 == m 
C. QU->front == QU->rear 
D. QU->front －QU->rear + 1 10.判断一个队列QU (最多元素为最多元素为m) 为满队列的条件是为满队列的条件是      。
A. QU->rear －QU->front == m
B. QU->rear －QU->front －1 == m 
C. QU->front == QU->rear 
D. QU->front －QU->rear + 1 
11.判断一个循环队列QU (最多元素为最多元素为m) 为空的条件是为空的条件是      。
A. QU->front == QU->rear 
B. QU->front != QU->rear 
C. QU->front == (QU->rear + 1) %m 
D. QU->front != (QU->rear + 1) %m 
12.判断一个循环队列QU (最多元素为最多元素为m) 为满队列的条件是为满队列的条件是      。 A. QU->front == QU->rear        B. QU->front != QU->rear 
C. QU->front == (QU->rear + 1) %m 
D. QU->front != (QU->rear + 1) %m 
13循环队列用数组A[0, m-1]存放其元素值，已知其头尾指针分别是存放其元素值，已知其头尾指针分别是front 和rear ，则当前队列中的元素个数是列中的元素个数是    。
A.(rear －front + m) %m 
B. rear －front + 1 
C. rear －front －1
D. rear －front  14.栈和队列的共同点是栈和队列的共同点是    。
A.都是先进后出都是先进后出
B.都是先进先出都是先进先出
C.只允许在端点处插入、删除元素只允许在端点处插入、删除元素
D.没有共同点没有共同点
填空题填空题
1.向量、栈和队列都是向量、栈和队列都是    结构，可以在向量的结构，可以在向量的        位置插入和删除元素；对于栈只能在栈只能在        插入和删除元素；对于队列只能在对于队列只能在        插入元素和插入元素和      删除元素。元素。
2.在一个长度为n 的向量中的第i 个元素(1≤i ≤n)之前插入一个元素时，需向后移动需向后移动    个元素。元素。
3.在一个长度为n 的向量中的删除第i 个元素(1≤i ≤n)时，需要向前移动需要向前移动      个元素。
4.向栈中压入元素的操作是向栈中压入元素的操作是            。
5.对栈进行退栈时的操作是对栈进行退栈时的操作是            。
6.在一个循环队列中，队首指针指向队首元素的在一个循环队列中，队首指针指向队首元素的            。
7.从循环队列中删除一个元素时，其操作是从循环队列中删除一个元素时，其操作是            。
8.在具有n 个单元的循环队列中，队满时共有个单元的循环队列中，队满时共有          个元素的。个元素的。
9.一个栈的输入序列是12345，则栈的输出序列43512是    。
10.一个栈的输入序列是12345，则栈的输出序列12345是    。
三、链表三、链表
单项选择题单项选择题
1.不带头结点的单链表head 为空的判定条件是为空的判定条件是    。
A.head==NULL
B.head->nxt==NULL
C.head->next==head
D.head!=NULL 2.带头结点的单链表head 为空的判定条件是为空的判定条件是    。
A.head==NULL
B.head->nxt==NULL
C.head->next==head
D.head!=NULL 3.非空的循环单链表head 的尾结点（由p 所指向）满足所指向）满足    。
A.p->next==NULL
B.p==NULL
C.p->next==head
D.p==head 
4.在循环双链表的p 所指结点之后插入s 所指结点的操作是所指结点的操作是      。
A. p->right=s;s->left=p;p->right->left=s;s->right=p->right; 
B. p->right=s;p->right->left=s;s->left=p;s->right=p->right; 
C. s->left=p;s->right=p->right;p->right=s;p->right->left=s; 
D. s->left=p;s->right=p->right; p->right->left=s;p->right=s; 
5.在一个单链表中，已知q 所指结点是p 所指结点的前驱结点，若在q 和p 之间插入s 结点， 则执行则执行    。 A. s->next = p->next; p->next=s;  B. p->next = s->next; s->next = p; 
C. q->next = s; s->next = p;
D. p->next = s; s->next = q; 
6.在一个单链表中，已知p 所指结点不是最后结点，在p 之后插入s 所指结点，则执行则执行    。
A. s->next = p; p->next=s;
B. s->next = p->next; p->next = s; 
C. s->next = p->next; p = s;
D. p->next = s; s->next = p; 
7.在一个单链表中，若删除p 所指结点的后续结点，则执行所指结点的后续结点，则执行    。
A. p->next = p->next->next;
B. p = p->next; p->next=p->next->next; 
C. p->next = p->next; 
D. p =p->next ->next; 
9.从一个具有n 个结点的单链表中查其值等于x 结点时，在查成功的情况下，需平均比较    个结点。个结点。
A. n
B. n/2 
C. (n-1)/2 
D. (n+1)/2 
10.在一个具有n 个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是    。
A. O(1)
B. O(n) 
C. O(n 2) 
D. O(nlog 2n) 
11.给定有n 个元素的向量，建立一个有序单链表的时间复杂度是个元素的向量，建立一个有序单链表的时间复杂度是    。 A. O(1)    B. O(n)      C. O(n 2)        D. O(nlog 2n) 
12.向一个栈顶指针为HS 的链栈中插入s 所指结点，则执行所指结点，则执行    。
A. HS->next = s; 
B. s->next = HS->next; HS->next = s; 
C. s->next = HS; HS = s;
D. s->next = HS; HS = HS->next; 
13.从一个栈顶指针为HS 的链栈中删除一个结点，用x 保存被删除结点的值，则执行则执行    。
A. x = HS; HS = HS->next; 
B. x = HS->data; 
C. HS = HS->next; x = HS->data; 
D. x = HS->data; HS = HS->next; 
14.在一个链队中，假设f 和r 分别为队首和队尾指针，插入s 所指结点，则执行所指结点，则执行    。
A. f->next = s; f = s; 
B. r->next = s; r = s; 
C. s->next = r; r = s;
D. s->next = f; f = s; 
15. 在一个链队中，假设f 和r 分别为队首和队尾指针，删除一个结点，则执行分别为队首和队尾指针，删除一个结点，则执行    。
数组和链表A. r = f->next; 
B. r = r->next; 
C. f = f->next;
D. f = r->next; 
填空题填空题
1.单链表是单链表是      的链接存储表示。的链接存储表示。
2.可以使用可以使用          表示树形结构。表示树形结构。
3.在双链表中，每个结点有两个指针域，一个指向在双链表中，每个结点有两个指针域，一个指向      ，另一个指向，另一个指向      。
4. 在一个单链表中，p 所指结点之前插入s 所指向结点，可执行如下操作：所指向结点，可执行如下操作：
（1）s->next =    ；
（2）p->next = s ；
（3）t = p->data ；
（4）p->data =    ；
（5）s->data =    ；
5.在一单链表中，删除p 所指结点时，应执行以下操作：所指结点时，应执行以下操作：
（1）q = p->next ；
（2）p->data = p->next->data ；
（3）p->next =        ；
（4）free (q)；
6.带头结点的单链表head 为空的条件是为空的条件是            。
7.在一个单链表中，p 所指结点之后插入s 所指向结点，应执行s->next =      和 p->next =          的操作。的操作。
8.非空的循环单链表head 的尾结点（由p 所指向），满足，满足      。
9.在栈顶指针为HS 的链栈中，判定栈空的条件是的链栈中，判定栈空的条件是        。
10. 在栈顶指针为HS 的链栈中，计算该链栈中结点个数的函数是的链栈中，计算该链栈中结点个数的函数是        。 11.在HQ 的链队中，判定只有一个结点的条件是的链队中，判定只有一个结点的条件是   
      。
12.在HQ 的链队中，计算该栈链中结点个数的函数是的链队中，计算该栈链中结点个数的函数是          。
四、串四、串  单项选择题单项选择题
1.空串与空格串是相同的，这种说法空串与空格串是相同的，这种说法    。
A.正确正确
B.不正确不正确
2.串是一种特殊的线性表，其特殊性体现在串是一种特殊的线性表，其特殊性体现在        。
A.可以顺序存储可以顺序存储
B.数据元素是一个字符数据元素是一个字符
C.可以链接存储可以链接存储
D.数据元素可以是多个字符数据元素可以是多个字符
3.设两个字符串p 和q ，求q 在p 中首次出现的位置的运算称作中首次出现的位置的运算称作    。
A.连接连接
B.模式匹配模式匹配
C.求子串求子串
D.求串长求串长
4.设串s1=s1=’’ABCDEFG ABCDEFG’’，s2=s2=’’PQRST PQRST’’，函数con (x, y) 返回返回x 与y 串的连接串，串的连接串，函数函数subs (s, i, j) 返回串s 的从序号i 的字符开始的j 个字符组成的子串，函数len (s) 返回串s 的长度，则con (subs (s1, 2, len (s2)), subs (s1, len (s2), 2)) 的结果串是的结果串是      。
A. BCDEF 
B. BCDEFG 
C. BCPQRST 
D. BCDEFEF 
填空题填空题
1.串的两种最基本的存储方式是串的两种最基本的存储方式是                。
2.两个串相等的充分必要条件是两个串相等的充分必要条件是                。
3.空串是空串是          ，其长度等于，其长度等于      。
4.空格串是空格串是          ，其长度等于，其长度等于      。
5.设s = ‘I  AM  A  TEACHER TEACHER’’，其长度是，其长度是      。
6.设s1 = ‘GOOD GOOD’’，s2 = ‘  ’，s3 = ‘BYE!BYE!’’，则s1、s2和s3连接后的结果是          。
五、数组与稀疏矩阵五、数组与稀疏矩阵
单项选择题单项选择题
1.常对数组进行的两种基本操作是常对数组进行的两种基本操作是    。
A.建立与删除建立与删除
B.索引和修改索引和修改
C.查和修改查和修改
D.查与索引查与索引
2.二维数组M 的成员是6个字符（每个字符占一个存储单元）（每个字符占一个存储单元）组成的串，组成的串，组成的串，行下标行下标i 的范围从的范围从  0到8，列下标j 的范围从1到10，则存放M 至少需要至少需要  1  个字节；M 的第8列和第5 行共占行共占  2  个字节；若M 按行优先方式存储，元素M[8][5]的起始地址与当M 按列优先按列优先  方式存储时的方式存储时的  3 元素的起始地址一致。元素的起始地址一致。
1  A.90        B.180          C.240          D.540 
2  A.108        B.114          C.54          D.60 
3  A.M[8][5]  B.M[3][10]      C.M[5][8]      D.M[0][9] 
3.二维数组M 的成员是4个字符（每个字符占一个存储单元）（每个字符占一个存储单元）组成的串，组成的串，组成的串，行下标行下标i 的范围从的范围从  0到4，列下标j 的范围从0到5，M 按行存储时元素M[3][5]的起始地址与M 按列存储时元按列存储时元  素的素的    元素的起始地址一致。元素的起始地址一致。