内容发布更新时间 : 2024/11/15 20:47:38星期一 下面是文章的全部内容请认真阅读。

李春葆编著：数据结构（C语言篇）――习题与解析（修订版） 清华大学出版社

一、绪论

选择题

1.数据结构是一门研究非数值计算的程序设计问题中计算机的 1 以及它们之间的 2 和运算等的学科。

1 A.数据元素 B.计算方法 C.逻辑存储 D.数据映像 2 A.结构 B.关系 C.运算 D.算法

2.数据结构被形式地定义为 (K, R)，其中K是 1 的有限集，R是K上的 2 有限集。 1 A.算法 B.数据元素 C.数据操作 D.逻辑结构 2 A.操作 B.映像 C.存储 D.关系 3.在数据结构中，从逻辑上可以把数据结构分成 。

A.动态结构和静态结构 B.紧凑结构和非紧凑结构 C.线性结构和非线性结构 D.内部结构和外部结构

4.线性结构的顺序存储结构是一种 1 的存储结构，线性表的链式存储结构是一种 2 的存储结构。

A.随机存取 B.顺序存取 C.索引存取 D.散列存取 5.算法分析的目的是 1 ，算法分析的两个主要方面是 2 。

1 A.找出数据结构的合理性 B.研究算法中的输入和输出的关系

C.分析算法的效率以求改进 D.分析算法的易懂性和文档性 2 A.空间复杂度和时间复杂度 B.正确性和简单性

C.可读性和文档性 D.数据复杂性和程序复杂性

6.计算机算法指的是 1 ，它必须具备输入、输出和 2 等 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，其输出序列为p1、p2、p3、… 、pn，若p1=n，则pi为 。

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所指结点的操作是 。