数据结构——C语言描述习题及答案

数据结构（C语言版）1800道题及答案[完整版]数据结构(C语言版)1800道题及答案[完整版]数据结构1800例题与答案第一章绪论一、选择题（每小题2分）1．算法的计算量的大小称为计算的（B ）。

【北京邮电大学2000 二、3 （20/8分）】A．效率 B．复杂性 C．现实性 D．难度2．算法的时间复杂度取决于（C）。

【中科院计算所 1998 二、1 （2分）】A．问题的规模 B．待处理数据的初态 C．A和B D．都不是3．计算机算法指的是（① C ），它必须具备（② B ）这三个特性。

① A．计算方法B．排序方法C．解决问题的步骤序列 D．调度方法② A．可执行性、可移植性、可扩充性B．可执行性、确定性、有穷性C．确定性、有穷性、稳定性 D．易读性、稳定性、安全性【南京理工大学1999 一、1（2分）【武汉交通科技大学1996 一、1（4分）】4．一个算法应该是（ B ）。

【中山大学 1998 二、1（2分）】A．程序 B．问题求解步骤的描述C．要满足五个基本特性 D．A和C.5．下面关于算法说法错误的是（ D ）【南京理工大学 2000 一、1（1.5分）】A．算法最终必须由计算机程序实现B.为解决某问题的算法同为该问题编写的程序含义是相同的C. 算法的可行性是指指令不能有二义性D. 以上几个都是错误的6. 下面说法错误的是（C ）【南京理工大学2000 一、2 （1.5分）】(1）算法原地工作的含义是指不需要任何额外的辅助空间（2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法（3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界（4）同一个算法，实现语言的级别越高，执行效率就越低A．(1) B.(1),(2) C.(1),(4) D.(3)7．从逻辑上可以把数据结构分为（ C ）两大类。

【武汉交通科技大学 1996 一、4（2分）】A．动态结构、静态结构 B．顺序结构、链式结构C．线性结构、非线性结构 D．初等结构、构造型结构8．以下与数据的存储结构无关的术语是（D ）。

数据结构课后习题参考答案第一章绪论1.3 (1) O(n)(2)(2)O(n)(3)(3)O(n)(4)(4)O(n1/2)(5)(5)执行程序段的过程中，x,y值变化如下：循环次数x y0（初始）91 1001 92 1002 93 100………………9 100 10010 101 10011 91 9912 92 100………………20 101 9921 91 98………………30 101 9831 91 97到y=0时，要执行10*100次，可记为O（10*y）=O（n）1.5 2100 , (2/3)n , log2n , n1/2 ,n3/2, (3/2)n , n log2n , 2 n ,n! , n n第二章线性表(参考答案)在以下习题解答中，假定使用如下类型定义：（1）顺序存储结构：#define MAXSIZE 1024typedef int ElemType;// 实际上，ElemType可以是任意类型typedef struct{ ElemType data[MAXSIZE];int last; // last表示终端结点在向量中的位置}sequenlist;（2）链式存储结构（单链表）typedef struct node{ElemType data;struct node *next；}linklist;（3）链式存储结构（双链表）typedef struct node{ElemType data;struct node *prior,*next；}dlinklist;（4）静态链表typedef struct{ElemType data;int next;}node;node sa[MAXSIZE];2.1 头指针：指向链表的指针。

因为对链表的所有操均需从头指针开始，即头指针具有标识链表的作用，所以链表的名字往往用头指针来标识。

如：链表的头指针是la，往往简称为“链表la”。

数据结构c语言版试题大全(含答案)数据结构C语言版试题大全（含答案）第一章：基本概念与算法设计1.1 数据结构的定义与特点数据结构是指相互之间存在一种或多种特定关系的数据元素的集合，它包括了数据的存储、组织和管理方式。

数据结构的特点包括以下几个方面：- 数据元素之间存在某种关系，构成逻辑结构- 对数据元素的操作对应于对其逻辑结构的操作- 数据结构有存储结构，包括顺序存储结构和链式存储结构- 算法是对数据结构的操作步骤的描述和实现1.2 算法的基本概念算法是解决特定问题或完成特定任务的一系列操作步骤。

算法的基本概念包括以下几个方面：- 有穷性：算法必须能在有限步骤内完成- 确定性：算法的每一步骤必须有确定的含义和结果- 可行性：算法的每一步骤必须可行，能够通过执行有限次数实现- 输入：算法接受的输入数据是原始问题的实例- 输出：算法产生的输出数据与输入有明确的关系1.3 算法的描述方法算法可以用自然语言、伪代码或流程图来描述。

常用的伪代码描述方法包括结构化语言和算法描述语言，结构化语言包括顺序结构、分支结构和循环结构。

第二章：线性结构2.1 线性表的定义与基本操作线性表是n个数据元素的有限序列，其中相邻元素之间存在唯一的前驱和后继关系。

线性表的基本操作包括插入、删除、查找和修改等。

2.2 数组与广义表数组是指具有相同数据类型的一组数据元素的集合，可以通过下标访问元素。

广义表是线性表的推广，其中元素可以是基本数据类型或另一个广义表。

第三章：树与二叉树3.1 树的定义与基本术语树是n（n≥0）个结点的一个有限集合，其中满足以下条件：- 有且仅有一个特定的称为根的结点- 其余结点可分为m（m≥0）个互不相交的有限集合，每个集合本身又是一棵树3.2 二叉树的定义与性质二叉树是指每个结点最多有两个子结点的树结构。

二叉树的性质包括以下几个方面：- 深度为k的二叉树最多有2^k-1个结点- 一棵二叉树的第i层最多有2^(i-1)个结点- 在二叉树的第i层上至多有2^(n-i+1)-1个结点（n为树的深度）第四章：图4.1 图的基本概念与术语图是由顶点的有穷非空集合和边的有穷集合组成的。

数据结构(C语言)【经典题库】含答案数据结构（C语言）【经典题库】含答案数据结构是计算机科学中的重要基础，对于程序员和软件工程师来说，熟练掌握数据结构是必不可少的。

在C语言中，有许多经典的数据结构题目，通过解答这些题目，可以深入理解数据结构的原理和应用。

本文将介绍一些经典的数据结构题目，同时附上详细的答案。

一、数组题目1. 给定一个整型数组arr和一个整数target，找出数组中两个数的和为target的所有组合。

```C#include <stdio.h>void findPairs(int arr[], int n, int target) {int i, j;for (i = 0; i < n - 1; i++) {for (j = i + 1; j < n; j++) {if (arr[i] + arr[j] == target) {printf("%d, %d\n", arr[i], arr[j]);}}}}int main() {int arr[] = {2, 4, 6, 8, 10};int target = 14;int n = sizeof(arr) / sizeof(arr[0]);findPairs(arr, n, target);return 0;}```答案解析：使用两层循环遍历数组中的每对元素，判断它们的和是否等于目标值target，如果是则输出。

时间复杂度为O(n^2)。

2. 给定一个整型数组arr和一个整数k，求出数组中连续子数组的最大和。

```C#include <stdio.h>int maxSubArraySum(int arr[], int n) {int maxSum = arr[0];int currentSum = arr[0];for (int i = 1; i < n; i++) {currentSum = (currentSum + arr[i] > arr[i]) ? currentSum + arr[i] : arr[i];if (currentSum > maxSum) {maxSum = currentSum;}}return maxSum;}int main() {int arr[] = {-2, 1, -3, 4, -1, 2, 1, -5, 4};int n = sizeof(arr) / sizeof(arr[0]);int maxSum = maxSubArraySum(arr, n);printf("最大和为：%d\n", maxSum);return 0;}```答案解析：使用动态规划的思想，定义两个变量`maxSum`和`currentSum`，分别表示当前的最大和和累加和。

数据结构c语言版试题及答案一、选择题（每题2分，共10分）1. 在C语言中，以下哪个关键字用于定义结构体？A. structB. unionC. enumD. typedef答案：A2. 若有一个结构体数组，下列哪个函数可以用来初始化数组中的每个元素？A. memsetB. memcpyC. strcpyD. bzero答案：A3. 在C语言中，以下哪个函数用于动态分配内存？A. mallocB. callocC. reallocD. all of the above答案：D4. 对于一个链表，以下哪个操作是正确的？A. 插入节点B. 删除节点C. 遍历链表D. all of the above答案：D5. 在C语言中，以下哪个函数用于释放动态分配的内存？A. freeB. mallocC. callocD. realloc答案：A二、填空题（每题3分，共15分）1. 结构体定义的关键字是______。

答案：struct2. 在C语言中，动态分配内存失败时，malloc函数返回______。

答案：NULL3. 单链表的头节点指针通常初始化为______。

答案：NULL4. 双向链表中，每个节点包含______个指针。

答案：两个5. 树的深度优先遍历包括______、中序遍历和后序遍历。

答案：前序遍历三、简答题（每题5分，共20分）1. 请简述C语言中结构体和联合体的区别。

答案：结构体（struct）可以包含不同类型的数据，并且可以有多个实例；联合体（union）可以包含不同类型的数据，但是只能有一个实例，即在任意时刻只能存储其中一个成员的值。

2. 动态内存分配的优点是什么？答案：动态内存分配允许程序在运行时根据需要分配内存，这样可以更有效地使用内存资源，并且可以创建大小不固定的数据结构。

3. 链表相比于数组有哪些优点？答案：链表的优点包括动态大小，可以灵活地插入和删除节点，不需要预先知道数据的大小。

耿国华《数据结构》程序算法课后答案第二章线性表2．4 设线性表存于a(1:arrsize)的前elenum 个分量中且递增有序。

试写一算法，将X 插入到线性表的适当位置上，以保持线性表的有序性。

Status Insert_SqList(SqList &va,int x)//把x 插入递增有序表va 中{if(va.length+1>va.listsize) return ERROR;va.length++;for(i=va.length-1;va.elem[i]>x&&i>=0;i--)va.elem[i+1]=va.elem[i];va.elem[i+1]=x;return OK;}//Insert_SqList2．6 已知线性表中的元素（整数）以值递增有序排列，并以单链表作存储结构。

试写一高效算法，删除表中所有大于mink且小于maxk的元素（若表中存在这样的元素），分析你的算法的时间复杂度（注意：mink和maxk是给定的两个参变量，它们的值为任意的整数）。

Status Delete_Between(Linklist &L,int mink,int maxk)//删除元素递增排列的链表L中值大于mink 且小于maxk 的所有元素{p=L;while(p->next->data<=mink) p=p->next; //p 是最后一个不大于mink 的元素if(p->next) //如果还有比mink 更大的元素{q=p->next;while(q->data<maxk) q=q->next; //q 是第一个不小于maxk 的元素p->next=q;}}//Delete_Between2．7 试分别以不同的存储结构实现线性表的就地逆置算法，即在原表的存储空间将线性表（a, a ..., a ）逆置为（a, a ,..., a ）。

数据结构试题及答案c语言版一、选择题（每题2分，共20分）1. 在C语言中，以下哪个选项是正确的链表定义？A. struct Node { int data; struct Node *next; };B. struct Node { int data; Node *next; };C. struct Node { int data; struct Node *next; } *Node;D. struct Node { int data; Node *next; };答案：A2. 下列关于栈的描述中，错误的是？A. 栈是一种后进先出（LIFO）的数据结构。

B. 栈的插入操作称为push。

C. 栈的删除操作称为pop。

D. 栈可以存储任意数量的数据。

答案：D3. 在C语言中，以下哪个关键字用于定义一个结构体？A. structB. unionC. enumD. typedef答案：A4. 下列关于队列的描述中，正确的是？A. 队列是一种先进先出（FIFO）的数据结构。

B. 队列只能从队尾进行插入操作。

C. 队列的插入操作称为pop。

D. 队列的删除操作称为push。

答案：A5. 在C语言中，以下哪个函数用于创建一个动态数组？A. mallocB. callocC. reallocD. all of the above答案：D6. 下列关于二叉树的描述中，错误的是？A. 二叉树的每个节点最多有两个子节点。

B. 二叉树的子节点被称为左子树和右子树。

C. 二叉树的遍历方式包括前序、中序、后序。

D. 二叉树的每个节点只能有一个子节点。

答案：D7. 在C语言中，以下哪个函数用于释放动态分配的内存？A. freeB. mallocC. callocD. realloc答案：A8. 下列关于图的描述中，错误的是？A. 图是由顶点和边组成的数据结构。

B. 图的边可以是有向的，也可以是无向的。

C. 图的顶点可以是孤立的，没有边与之相连。

第一章客观习题1.D2.D3.B4. C5.D6.B7.D8.D9.A 10.C 11. A12.B简答题：1.存储实现是设计数据的存储结构，是建立数据的机内表示，包括数据元素和数据元素之间关系的存储。

运算实现是在某种存储实现的基础上具体实现各种运算，其运算实现的核心(即算法设计)是设计实现某一运算的处理步骤。

2. 算法的时间复杂度反映的是算法执行时间的数量级，并不是绝对执行时间。

两个时间复杂度都为O(n2)的算法，对于相同的问题规模n，它们的绝对执行时间也不一定一定相同。

3. 数据的逻辑结构包含两个要素，分别是数据元素和关系。

其中，关系是指数据元素间的逻辑关系。

根据数据元素之间关系的不同特性，通常有四类基本结构构关系，它们的复杂程度依次递进，如图1.1所示。

1) 集合结构2) 线性结构3) 树结构4) 图结构图1.1 四类基本逻辑结构关系图1) 集合结构：数据元素之间除了“属于同一集合”的关系外，无其他关系。

例如，确定一名学生是否为班级成员，只需要将班级看作一个集合结构；2) 线性结构：数据元素之间存在一对一的关系。

例如，将学生信息数据按照其入学报到的时间先后顺序进行排列，组成一个线性结构；3) 树形结构：数据元素之间存在一对多的关系。

例如，在班级管理体系中，班长管理多个组长，每位组长管理多名组员，从而形成树形结构；4) 图结构/网状结构：数据元素之间存在多对多的关系。

例如，多位朋友之间的朋友关系，任何两位同学都可以是朋友，从而形成图结构或者网状结构。

4. 存储结构是由两种种基本的存储方式实现，分别为顺序存储结构和链式存储结构。

1) 顺序存储结构：借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系，通常借助程序设计语言的数组类型来描述；2) 链式存储不像顺序存储结构要求所有元素依次存放在一段连续的存储空间中，而是无需占用一整块存储空间。

由于为了表示结点之间的关系，需要给每个结点附加指针字段，用于存放后继元素的存储地址，通常借助程序设计语言的指针类型来描述。

附录习题参考答案习题1参考答案1.1.选择题(1). A. (2). A. (3). A. (4). B.,C. (5). A. (6). A. (7). C. (8). A. (9). B. (10.)A.1.2.填空题(1). 数据关系(2). 逻辑结构物理结构(3). 线性数据结构树型结构图结构(4). 顺序存储链式存储索引存储散列表（Hash）存储(5). 变量的取值范围操作的类别(6). 数据元素间的逻辑关系数据元素存储方式或者数据元素的物理关系(7). 关系网状结构树结构(8). 空间复杂度和时间复杂度(9). 空间时间(10). Ο(n)1.3 名词解释如下：数据：数据是信息的载体，是计算机程序加工和处理的对象，包括数值数据和非数值数据。

数据项：数据项指不可分割的、具有独立意义的最小数据单位，数据项有时也称为字段或域。

数据元素：数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理，一个数据元素可由若干个数据项组成。

数据逻辑结构：数据的逻辑结构就是指数据元素间的关系。

数据存储结构：数据的物理结构表示数据元素的存储方式或者数据元素的物理关系。

数据类型：是指变量的取值范围和所能够进行的操作的总和。

算法：是对特定问题求解步骤的一种描述，是指令的有限序列。

1.4 语句的时间复杂度为：(1) Ο(n2)(2) Ο(n2)(3) Ο(n2)(4) Ο(n-1)(5) Ο(n3)1.5 参考程序：main(){int X,Y,Z；scanf(“%d, %d, %d”,&X,&Y,Z)；if (X>=Y)if(X>=Z)if (Y>=Z){ printf(“%d, %d, %d”,X,Y,Z);}else{ printf(“%d, %d, %d”,X,Z,Y);}else{ printf(“%d, %d, %d”,Z,X,Y);}elseif(Z>=X)if (Y>=Z){ printf(“%d, %d, %d”,Y,Z,X);}else{ printf(“%d, %d, %d”,Z,Y,X);}else{ printf(“%d, %d, %d”,Y,X,Z);}}1.6 参考程序：main(){int i,n;float x,a[],p;printf(“\nn=”);scanf(“%f”,&n);printf(“\nx=”);scanf(“%f”,&x);for(i=0;i<=n;i++)scanf(“%f ”,&a[i]);p=a[0];for(i=1;i<=n;i++){ p=p+a[i]*x;x=x*x;}printf(“%f”,p)’}习题2参考答案2.1选择题(1). C. (2). B. (3). B. (4). B. 5. D. 6. B. 7. B. 8. A. 9. A. 10. D.2.2.填空题(1). 有限序列(2). 顺序存储和链式存储(3). Ｏ(n) O(n)(4). n-i+1 n-i(5). 链式(6). 数据指针(7). 前驱后继(8). Ο(1) Ο(n)(9). s->next=p->next; p->next=s ;(10). s->next2.3. 解题思路：将顺序表A中的元素输入数组a，若数组a中元素个数为n,将下标为0，1,2,…,（n-1）/2的元素依次与下标为n,n-1,…, （n-1）/2的元素交换，输出数组a的元素。

一、是非题1. 数据结构概念包括数据之间的逻辑结构，数据在计算机中的存储方式和数据的运算三个方面。

.......................( T )2. 线性表的逻辑顺序与物理顺序总是一致的........( F )3. 线性表中的每个结点最多只有一个前驱和一个后继。

......( T )4. 线性的数据结构可以顺序存储，也可以链接存储。

非线性的数据结构只能链接存储。

.......................( F )5. 栈和队列逻辑上都是线性表。

..........................( T )6. 单链表从任何一个结点出发，都能访问到所有结点........( F )7. 单链表形式的队列，头指针F指向队列的第一个结点，尾指针R指向队列的最后一个结点。

.................................................( T )8. 在用单链表表示的链式队列中，队头在链表的链尾位置。

....( F )9. 多维数组是向量的推广。

..............................( T )10. 栈是一种先进先出的线性表。

....( F )11. 凡是递归定义的数据结构都可以用递归算法来实现它的操作。

......( T )12. 设串S的长度为n,则S的子串个数为n(n+1)/2。

...........( F )13. 一般树和二叉树的结点数目都可以为0。

................( F )14. 按中序遍历二叉树时，某结点的直接后继是它的右子树中第1个被访问的结点。

....( T )15. 后序序列和中序序列能唯一确定一棵二叉树。

....( T )16. 对于一棵具有n个结点，其高度为h的二叉树，进行任—种次序遍历的时间复杂度为O(n) .............( T )17. 网络的最小代价生成树是唯一的。

...( T )18. 图的拓扑有序序列不是唯一的。

1.3设n是正整数。

试写出下列程序段中用记号“△”标注的语句的频度：(2) i=1; k=0;do {△k+=10*i;i++;}while(i<=n-1)当n=1时，执行1；当n>=2时，执行n-1次；(3)i=1; k=0;do {△k+ = 10*i; i++;}while(i==n);当n=2时，执行2次；当n!=2时，执行1次；(4) i=1; j=0;while(i+j≤n) {△if(i<j) i++; else j++;}执行n次；(5) x=n; y=0; //n是不小于1的常数while(x>=(y+1)*(y+1)){△y++;}执行向下取整)(6) x=91; y=100;while ( y>0 )△if(x>100) { x-=10; y--; }else x++ ;}If语句执行100次(7) for( i=0; i<n; i++)for( j=i; j<n; j++)for( k=j; k<n; k++)△x+=2;过程：n1n1i0j in(n1)(n2) (n j)6--==++ -=∑∑第二章2.3 已知顺序表La中数据元素按非递减有序排列。

试写一个算法，将元素x插到La的合适位置上，保持该表的有序性。

思路：先判断线性表的存储空间是否满，若满返回Error；否则从后向前先移动数据，找到合适的位置插入。

Status Insert_SqList(SqList &La,int x)//把x 插入递增有序表La 中{if(La.length==La.listsize) return ERROR;for(i=La.length-1;La.elem[i]>x&&i>=0;i--)La.elem[i+1]=La.elem[i];La.elem[i+1]=x;La.length++;return OK;}//Insert_SqList2.5 试写一个算法，实现顺序表的就地逆置，即在原表的存储空间将线性表（a1,a2, ..., an-1,an）逆置为(an,an-1, ..., a2,a1)//思路就是两个指示变量i，j同时分别从顺序表的开始和结尾处相向改变void reverse(SqList &A)//顺序表的就地逆置{ElemType p;for(i=1,j=A.length;i<j;i++,j--){//A.elem[i]<->A.elem[j];p=A.elem[i];A.elem[i[=A.elem[j];A.elem[j]=p;}}//reverse2.7 已知线性表L采用顺序存储结构存放，对两种不同情况分别写出算法，删除L中多余的元素，使得L中没有重复元素：（1）L中数据元素无序排列；(2)L中数据元素非递减有序排列。

数据结构c语言描述课后习题答案数据结构是计算机科学的基础课程之一，它研究的是如何组织和管理数据以及设计高效的算法来操作这些数据。

在学习数据结构的过程中，解答课后习题是提高自己对知识掌握程度的重要途径。

本文将针对一些常见的数据结构课后习题，给出C语言描述的答案。

一、线性表1. 实现一个顺序表的插入操作。

```cvoid insert(SeqList *list, int index, int value) {if (index < 0 || index > list->length) {printf("插入位置错误");return;}if (list->length == MAX_SIZE) {printf("顺序表已满");return;}for (int i = list->length - 1; i >= index; i--) {list->data[i + 1] = list->data[i];}list->data[index] = value;list->length++;```2. 实现一个链表的删除操作。

```cvoid delete(ListNode **head, int value) { ListNode *p = *head;ListNode *pre = NULL;while (p != NULL) {if (p->data == value) {if (pre == NULL) {*head = p->next;} else {pre->next = p->next;}free(p);return;}pre = p;p = p->next;}printf("链表中不存在该元素");}二、栈和队列1. 实现一个栈的入栈操作。

习题配套第一章2．C、A、B、B、A、A、D3．D={A,B,C,E,F,G,H,I,J};R={<A,B>,<A,C>,<A,E>,<B,F>,<B,G>,<E,H>,<E,I>,<E,J>,<H,I>,<I,J>}题1-3图4．顺序、链式、索引、哈希。

*5．解：100n2>2n n至少要多大6.Ｏ(n)、Ｏ(n)、Ｏ(n)、Ｏ(n)、(5)当n>m，Ｏ(n),当m>n，Ｏ(m)7．n!2100>lgn>n1/2>n3/2>(3/2)n>2n>n lgn>n n第二章1．×、√、×、√、√2．AAD4．顺序表void Delete_SeqListx(SeqList *L,ElemType x)/*删除表中值为x元素*/{inti,j;for(i=1;i<=L->length;i++){if(L->elem[i]==x){for(j=i;j<=L->length-1;j++)L->elem[j]=L->elem[j+1];L->length--;}/*向上移动*/}O(n2)链表void del_link(LinkList H，int x)/*删除数据域为x的结点*/ {LNode *p，*q;p=H;q=H->next;while(q!=NULL){if(q->data==x){p->next=q->next;free(q);q=p->next;}else{p=q;q=q->next;}}}O(n)5．int Delete_SeqListx(SeqList *L,int i,int k)/*删除表中删除自第i个结点开始的k个结点*/{intj;if(i<1||k<0||i+k-1>L->length)/*检查空表及删除位置的合法性*/{printf(＂不存在第i个元素＂);return ERROR;}for(j=i;j<=L->length-k;j++)L->elem[j]=L->elem[j+k]; /*向上移动*/L->length-=k;Return OK;/*删除成功*/}O(n)6．void Delete_SeqListx(SeqList *L,ElemType x)/*将表中值为x元素换成y*/{inti,j;for(i=1;i<=L->length;i++){if(L->elem[]==x){L->elem[i]=y;}/* */}O(n)7．写一算法在循环单链表上实现线性表的CList_length(L)运算。

同步训练5-6 参考答案一、单项选择题1．在有向无环图G 的拓扑序列中，对图G 中任意一对顶点u 和v ，若<u,v>∈E(G)，则（ A ）。

A ．u 一定出现在v 之前B ．u 一定出现在v 之后C ．u 不一定出现在v 之前D ．u 不一定出现在v 之后2．一个有向无环图G 的拓扑序列（ D ）。

A ．只有一个 B ．有且只有一个 C ．可能有多个D ．有且可能有多个3．一个有向图G 的拓扑序列（ C ）。

A ．只有一个 B ．有且只有一个 C ．可能没有、可能有多个D ．有且可能有多个4．如果一个有向图G 有拓扑序列，则该图一定（ B ）。

A ．有环 B ．无环 C ．有唯一拓扑序列D ．有多个拓扑序列5．为便于判别有向图中是否存在回路，可借助于（ D ）。

A ．广度优先搜索算法 B ．最小生成树算法 C ．最短路径算法D ．拓扑排序算法6．如图所示的有向无环图可以得到的不同拓扑序列的个数为（ C ）。

A ．1B ．2C ．3D ．47．如图所示的有向无环图可以得到的拓扑序列的个数是（ C ）。

A ． 3B ． 4C ． 5D ． 6EE8．如图所示有向图的一个拓扑序列是（ B ）。

A ．EFABCDB ．FCBEADC ．FEABCDD ．EAFCBD9．如图所示的有向图的拓扑序列是（ B ）。

A ．cdbaeB ．cadbeC ．cdeabD ．cabde10．对下面有向图给出了四种可能的拓扑序列，其中错误的是（ C ）。

A ．1，5，2，6，3，4B ．1，5，6，2，3，4C ．5，1，6，3，4，2D ．5，1，2，6，4，311．已知有向图G=(V ，E)，其中V={V1，V2，V3，V4}，E={<V1，V2>，<V1，V3>，<V2，V3>，<V2，V4>，<V3，V4>}，图G 的拓扑序列是（ A ）。

数据结构C语言版部分习题及标准答案————————————————————————————————作者：————————————————————————————————日期：第二章习题与解答一判断题1．线性表的逻辑顺序与存储顺序总是一致的。

2．顺序存储的线性表可以按序号随机存取。

3．顺序表的插入和删除操作不需要付出很大的时间代价，因为每次操作平均只有近一半的元素需要移动。

4．线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此是属于同一数据对象。

5．在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上并不一定紧邻。

6．在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻。

7．线性表的链式存储结构优于顺序存储结构。

8．在线性表的顺序存储结构中，插入和删除时，移动元素的个数与该元素的位置有关。

9．线性表的链式存储结构是用一组任意的存储单元来存储线性表中数据元素的。

10．在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。

二单选题 (请从下列A，B，C，D选项中选择一项)1．线性表是( ) 。

(A) 一个有限序列，可以为空；(B) 一个有限序列，不能为空；(C) 一个无限序列，可以为空；(D) 一个无序序列，不能为空。

2．对顺序存储的线性表，设其长度为n，在任何位置上插入或删除操作都是等概率的。

插入一个元素时平均要移动表中的（）个元素。

(A) n/2 (B) n+1/2 (C) n -1/2 (D) n3．线性表采用链式存储时，其地址( ) 。

(A) 必须是连续的；(B) 部分地址必须是连续的；(C) 一定是不连续的；(D) 连续与否均可以。

4．用链表表示线性表的优点是（）。

(A)便于随机存取(B)花费的存储空间较顺序存储少(C)便于插入和删除(D)数据元素的物理顺序与逻辑顺序相同5．某链表中最常用的操作是在最后一个元素之后插入一个元素和删除最后一个元素，则采用( )存储方式最节省运算时间。

/computer/book/read/data-structure/h971111102.html 习题解答(唐策善版)(其他版本在上面)第一章绪论（参考答案）1.3 (1) O(n)(2)(2)O(n)(3)(3)O(n)(4)(4)O(n1/2)(5)(5)执行程序段的过程中，x,y值变化如下：循环次数x y0（初始）91 1001 92 1002 93 100………………9 100 10010 101 10011 91 9912 92 100………………20 101 9921 91 98………………30 101 9831 91 97到y=0时，要执行10*100次，可记为O（10*y）=O（1）1.5 2100 , (2/3)n , log2n , n1/2 ,n3/2, (3/2)n , n log2n , 2 n ,n! , n n第二章线性表(参考答案)在以下习题解答中，假定使用如下类型定义：（1）顺序存储结构：#define MAXSIZE 1024typedef int ElemType;// 实际上，ElemType可以是任意类型typedef struct{ ElemType data[MAXSIZE];int last; // last表示终端结点在向量中的位置}sequenlist;（2）链式存储结构（单链表）typedef struct node{ElemType data;struct node *next；}linklist;（3）链式存储结构（双链表）typedef struct node{ElemType data;struct node *prior,*next；}dlinklist;（4）静态链表typedef struct{ElemType data;int next;}node;node sa[MAXSIZE];2.1 头指针：指向链表的指针。

因为对链表的所有操均需从头指针开始，即头指针具有标识链表的作用，所以链表的名字往往用头指针来标识。