数据结构习题

第一章1．在数据结构中，从逻辑上可以把数据结构分为(C )A．动态结构和静态结构B。

紧凑结构和非紧凑结构C．线性结构和非线性结构D。

内部结构和外部结构● 2.在数据结构中，与所使用的计算机无关的是( A )A。

逻辑结构 B. 存储结构C。

逻辑和存储结构 D. 物理结构3。

下面程序的时间复杂度为____O(mn）_______。

for (int i=1；i〈=m; i++）for （int j=1；j〈=n；j++ ）S+=i第二章线性表●链表不具备的特点是（A)A 可以随机访问任一结点（顺序）B 插入删除不需要移动元素C 不必事先估计空间D 所需空间与其长度成正比2。

不带头结点的单链表head为空的判定条件为（A )，带头结点的单链表head为空的判定条件为（B ）A head==nullB head—〉next==nullC head-〉next==headD head！=null●3.在线性表的下列存储结构中,读取元素花费时间最少的是（D)A 单链表B 双链表C 循环链表D 顺序表● 4.对于只在表的首、尾两端进行手稿操作的线性表，宜采用的存储结构为（C）A 顺序表B 用头指针表示的单循环链表C 用尾指针表示的单循环链表D 单链表●5。

在一个具有n 个结点的有序单链表中插入一个新的结点，并保持链表元素仍然有序，则操作的时间复杂度为（ D ）A O(1）B O(log2n)C O(n2)D O(n）● 6.在一个长度为n （n〉1）的单链表上，设有头和尾两个指针，执行（B）操作与链表的长度有关A 删除单链表中第一个元素B 删除单链表中最后一个元素C 在第一个元素之前插入一个新元素D 在最后一个元素之后插入一个新元素●7。

与单链表相比，双向链表的优点之一是（D)A 插入删除操作更简单B 可以进行随机访问C 可以省略表头指针或表尾指针D 顺序访问相邻结点更容易●8。

若list是某带头结点的循环链表的头结点指针，则该链表最后那个链结点的指针域（头结点的地址）中存放的是（ B )A list的地址B list的内容C list指的链结点的值D 链表第一个链结点的地址●9.若list1和list2分别为一个单链表与一个双向链表的第一个结点的指针,则（ B )A list2比list1占用更多的存储单元B list1与list2占用相同的存储单元C list1和list2应该是相同类型的指针变量D 双向链表比单链表占用更多的存储单元10。

数据结构习题习题一一、选择题1、数据结构是一门研究非数值计算的程序设计问题中的操作对象以及它们之间的（B）和运算的学科。

A．结构B．关系C．运算D．算法2、在数据结构中，从逻辑上可以把数据结构分成（C）。

A．动态结构和静态结构B．紧凑结构和非紧凑结构C．线性结构和非线性结构D．逻辑结构和存储结构3、线性表的逻辑顺序和存储顺序总是一致的，这种说法（B）。

A．正确B．不正确C．无法确定D．以上答案都不对4、算法分析的目的是（C）。

A．找出算法的合理性B．研究算法的输人与输出关系C．分析算法的有效性以求改进D．分析算法的易懂性二、填空题1、数据是信息的载体，是对客观事物的符号表示，它能够被计算机识别、存储、加工和处理，数据是对能够有效的输人到计算机中并且能够被计算机处理的符号的总称。

例如，数学中所用到的整数和实数，文本编辑所用到的字符串等。

2、数据元素是数据的基本单位，有些情况下也称为元素、结点、顶点、记录等。

3、数据项是数据不可分割的最小单元，是具有独立含义的最小标识单位。

例如构成一个数据元素的字段、域、属性等都可称之为_数据项。

4、简而言之，数据结构是数据之间的相互关系，即数据的组织形式。

5、数据的逻辑结构是指数据之间的逻辑关系。

逻辑结构是从逻辑关系上描述数据，它与具体存储无关，是独立于计算机的。

因此逻辑结构可以看作是从具体问题抽象出来的数学模型。

6、数据的存储结构指数据元素及其关系在计算机存储器内的表示。

存储结构是逻辑结构在计算机里的实现，也称之为映像。

7、数据的运算是指对数据施加的操作。

它定义在数据的逻辑结构之上，每种逻辑结构都有一个数据的运算。

常用的有：查找、排序、插人、删除、更新等操作。

8、数据逻辑结构可以分为四种基本的类型，集合结构中的元素除了仅仅只是同属于一个集合_，不存在什么关系。

9、数据逻辑结构的四种基本类型中，线性结构_中的元素是一种一对一的关系，这种结构的特征是：若结构是非空集，则有且只有一个开始结点和一个终端结点，并且所有结点最多只能有一个直接前驱和一个直接后继。

第 1 章绪论课后习题讲解1. 填空⑴（）是数据的基本单位，在计算机程序中通常作为一个整体进行考虑与处理。

【解答】数据元素⑵（）是数据的最小单位，（）是讨论数据结构时涉及的最小数据单位。

【解答】数据项，数据元素【分析】数据结构指的是数据元素以及数据元素之间的关系。

⑶从逻辑关系上讲，数据结构主要分为（）、（）、（）与（）。

【解答】集合，线性结构，树结构，图结构⑷数据的存储结构主要有（）与（）两种基本方法，不论哪种存储结构，都要存储两方面的内容：（）与（）。

【解答】顺序存储结构，链接存储结构，数据元素，数据元素之间的关系⑸算法具有五个特性，分别是（）、（）、（）、（）、（）。

【解答】有零个或多个输入，有一个或多个输出，有穷性，确定性，可行性⑹算法的描述方法通常有（）、（）、（）与（）四种，其中，（）被称为算法语言。

【解答】自然语言，程序设计语言，流程图，伪代码，伪代码⑺在一般情况下，一个算法的时间复杂度是（）的函数。

【解答】问题规模⑻设待处理问题的规模为n，若一个算法的时间复杂度为一个常数，则表示成数量级的形式为（），若为n*log25n，则表示成数量级的形式为（）。

【解答】Ο(1)，Ο(nlog2n)【分析】用大O记号表示算法的时间复杂度，需要将低次幂去掉，将最高次幂的系数去掉。

2. 选择题⑴顺序存储结构中数据元素之间的逻辑关系是由（）表示的，链接存储结构中的数据元素之间的逻辑关系是由（）表示的。

A 线性结构B 非线性结构C 存储位置D 指针【解答】C，D【分析】顺序存储结构就是用一维数组存储数据结构中的数据元素，其逻辑关系由存储位置（即元素在数组中的下标）表示；链接存储结构中一个数据元素对应链表中的一个结点，元素之间的逻辑关系由结点中的指针表示。

⑵假设有如下遗产继承规则：丈夫与妻子可以相互继承遗产；子女可以继承父亲或母亲的遗产；子女间不能相互继承。

则表示该遗产继承关系的最合适的数据结构应该是（）。

数据结构习题及答案第1章算法一、选择题1.算法的时间复杂度是指（）。

A）执行算法程序所需要的时间B）算法程序中的指令条数C）算法执行过程中所需要的基本运算次数D）算法程序的长度2.算法的空间复杂度是指（）。

A）算法程序的长度B）算法程序所占的存储空间C）算法执行过程中所需要的存储空间D）算法程序中的指令条数3.下面（）的时间复杂度最好（即执行时间最短）。

logn)O(）O(n ) B）A2logn2 ) D）O(n)C）O(n24.下面累加求和程序段的时间复杂度为（）。

int sum(int a[],int n){int i, s=0;for (i=0;i<n;i++)< p="">s+=a[i];return s;}logn ) ）O(A）O(1 ) B22)）O(nC）O(n ) D中的算法，c[][]相加的结果存放到b[][]n阶矩阵5.下面是将两个n阶矩阵a[][]与。

该算法的时间复杂度为（）void matrixadd(int a[][],intb[][],c[][],int n){int i,j;for (i=0;i<n;i++)< p="">for(j=0;j<n;j++)< p="">c[i][j]=a[i][j]+b[i][j];}nlog) ）O(1 ) B）O(A22) ）O(nO( n ) DC）。

6.下面程序段的时间复杂度为（） 1int i=0,s1=0,s2=0;while(i<n)< p="">{if(i%2)s1+=i;elses2+=i;i++;}nlog) O(A）O(1 ) B）22) ）O(nC）O(n ) D ）。

7.下面程序段的时间复杂度为（int prime(int n){int i=1;int x=(int)sqrt(n);while(i<=x){i++;if(n%i==0)break;}if(i>x)return 1;elsereturn 0;}nlog) O(O(1 ) BA））2n) O(）CO(n ) D））下面程序段的时间复杂度为（8.int fun(int n){int i=1,s=1;while(s<n)< p="">{i++;s+=i;}return i;}nlog)O(n/2) BA））O(2 2n) ）O(C）O(n ) D9.下面程序段的时间复杂度为（）int i,j,m,n,a[][];for(i=0;i<m;i++)< p="">for(j=0;j<n;j++)< p="">a[i][j]=i*j;22) ）O(nA）O(m) BO(m+n) ）C）O(m*n ) D ）10. 下面程序段的时间复杂度为（int sum1(int n){int i,p=1,s=0;for(i=1;i<=n;i++){p*=i;s=s+p;}return s;}nlog) ）O(A）O(1 ) B22)O(n ) D）O(nC）二、填空题复杂度。

数据结构练习题（一）一、单选题1.栈和队列的共同特点是( )。

A.只允许在端点处插入和删除元素B.都是先进后出C.都是先进先出D.没有共同点2.用链接方式存储的队列，在进行插入运算时( )。

A. 仅修改头指针B. 头、尾指针都要修改C. 仅修改尾指针D.头、尾指针可能都要修改3.以下数据结构中( )是非线性结构。

A. 队列B. 栈C. 线性表D. 二叉树4.设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每个元素占一个空间，问A[3][3](10)存放在（）位置。

脚注(10)表示用10进制表示。

A．688 B．678 C．692 D．6965.树最适合用来表示( )。

A.有序数据元素B.无序数据元素C.元素之间具有分支层次关系的数据D.元素之间无联系的数据6.二叉树的第k层的结点数最多为( )。

A．2k-1 +1 D. 2k-17.若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二分查找，则查找A［3］的比较序列的下标依次为( )。

A. 1，2，3B. 9，5，2，3C. 9，5，3D. 9，4，2，38.对于线性表（7，34，55，25，64，46，20，10）进行散列存储时，若选用H（K）=K %9作为散列函数，则散列地址为1的元素有（）个。

A．1 B．2 C．3 D．49.设有6个结点的无向图，该图至少应有( )条边才能确保是一个连通图。

二、填空题1.通常从四个方面评价算法的质量：_________、_________、_________和_________。

2.一个算法的时间复杂度为(n3+n2log2n+14n)/n2，其数量级表示为________。

3.假定一棵树的广义表表示为A（C，D（E，F，G），H（I，J）），则树中所含的结点数为__________个，树的深度为___________，树的度为_________。

第1章绪论一、选择题1. 算法的计算量的大小称为计算的（）。

A．效率 B. 复杂性 C. 现实性 D. 难度2. 算法的时间复杂度取决于（）A．问题的规模 B. 待处理数据的初态 C. A和B3. 下面说法错误的是（）(1）算法原地工作的含义是指不需要任何额外的辅助空间（2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法（3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界（4）同一个算法，实现语言的级别越高，执行效率就越低A．(1) B.(1),(2) C.(1),(4) D.(3)4. 以下数据结构中，哪一个是线性结构（）A．广义表 B. 二叉树 C. 稀疏矩阵 D. 串5. 在下面的程序段中，对x的赋值语句的频度为（）for (int i=1; i<=n; i++)for (int j=1; i<=n;j++)x+=1;A．2n B．n C．n2D．log2n二、判断题1. 数据元素是数据的最小单位。

( )2. 算法的优劣与算法描述语言无关，但与所用计算机有关。

( )3. 数据的物理结构是指数据在计算机内的实际存储形式。

( )4. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。

( )5. 数据结构的抽象操作的定义与具体实现有关。

( )三、填空1．数据的物理结构包括的表示和的表示2. 数据结构中的逻辑结构有（1），（2），（3），__（4）_四种。

3. 一个数据结构在计算机中称为存储结构4. 数据结构中评价算法的两个重要指标是5. 一个算法具有5个特性: （1）、（2）、（3），有零个或多个输入、有一个或多个输出。

6. 已知如下程序段, 语句1执行的频度为（1）；语句2执行的频度为（2）；for (int i=n; i>=1; i--) {x = x+1; //语句1for (int j = n; j>=1; j--)y = y+1; //语句2}7. 下面程序段中带下划线的语句的执行次数的渐进时间复杂度为int i=1; while (i<n) i = i*2;四、应用题1. 解释和比较以下各组概念（1）抽象数据类型及数据类型（2）数据结构、逻辑结构、存储结构（3）抽象数据类型（4）算法的时间复杂性（5）算法（6）频度2. 若有100个学生，每个学生有学号，姓名，平均成绩，采用什么样的数据结构最方便，写出这些结构？3. 有实现同一功能的两个算法A1和A2，其中A1的时间复杂度为Tl=O(2n)，A2的时间复杂度为T2=O(n2)，仅就时间复杂度而言，请具体分析这两个算法哪一个好.4. 下列算法对一n位二进制数加1，假如无溢出，该算法的最坏时间复杂性是什么？并分析它的平均时间复杂性。

1.数据结构是研究数据的( C )以及它们之间的相互关系。

A)存储结构，物理结构 B)理想结构，抽象结构 C)物理结构，逻辑结构 D)抽象结构，逻辑结构2.在数据结构中，与所使用的计算机无关的是数据的( C )结构。

A)存储 B)物理 C)逻辑 D)物理与存储3.数据结构课程主要研究以下三方面的内容，它们是(D)。

A)数据、数据元素、数据类型B)数据元素、数据类型、算法实现 C)数据元素、数据的逻辑结构、数据的存储结构D)数据的逻辑结构、数据的存储结构、数据的运算4.在以下的复杂度量级中，量级最低的是(B)。

A) O(n) B) O(log2n) C) O(nlog2n) D) O(n2)5.在下列叙述中，正确的是(C)。

A)数据的逻辑结构要考虑数据元素本身的内容 B)不同类型的数据元素可以归类到同一的逻辑结构中 C)数据元素之间的关联关系在数据的逻辑结构中体现D)数据元素是数据不可分割的最小标识单位6.计算机算法必须具备输入、输出和(B)等五个特性。

A)可行性、可移植性和可扩充性 B)可行性、确定性和有穷性 C)确定性、稳定性和有穷性 D)易读性、稳定性和安全性7.算法分析的目的是(D)。

A)找出数据结构的合理性 B)研究算法中的输入/输出关系C)分析算法的易读性 D)分析算法的效率以求改进8.设 n>=10，下面程序段的时间复杂度是(D)。

for(i=10; i<n; i++){ j=k=0;while(j+k<=i)if (j>k) k++;else j++;}A) O (log2n) B) O(n) C) O(nlog2n) D) O(n2)9.计算机算法是指( D )A)计算方法 B)排序方法 C)调度方法 D)解决问题的有限运算序列10.数据的定义取决于数据的逻辑结构，而数据的实现取决于数据的物理结构(A)。

A)正确 B) 不正确11.下面说法错误的是(AD )A)算法原地工作的含义是指不需要任何额外的辅助空间B)在相同的规模 n 下，复杂度 O(n)的算法在时间上总是优于复杂度 O(2n)的算法C)所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界D)同一个算法，实现语言的级别越高，执行效率就越低1. 数据元素是数据的最小单位。

数据结构习题及参考答案部门： xxx时间： xxx整理范文，仅供参考，可下载自行编辑数据结构习题及参考答案一、判断下列叙述的对错。

<1）线性表的逻辑顺序与物理顺序总是一致的。

<2）线性表的顺序存储表示优于链式存储表示。

<3）线性表若采用链式存储表示时所有结点之间的存储单元地址可连续可不连续。

<4）二维数组是其数组元素为线性表的线性表。

<5）每种数据结构都应具备三种基本运算：插入、删除和搜索。

二、设单链表中结点的结构为typedef struct node { file://链表结点定义ElemType data； file://数据struct node * Link； file://结点后继指针} ListNode；<1）已知指针p所指结点不是尾结点，若在*p之后插入结点* s，则应执行下列哪一个操作？A. s->link = p； p->link = s；B. s->link = p->link； p->link = s；C. s->link = p->link； p = s；D. p->link = s； s->link = p；<2）非空的循环单链表first的尾结点<由p所指向）满足：A. p->link == NULL；B. p == NULL；C. p->link == first；D. p == first；三、设有一个顺序栈S，元素s1， s2， s3， s4， s5， s6依次进栈，如果6个元素的出栈顺序为s2， s3， s4， s6， s5， s1，则顺序栈的容量至少应为多少？b5E2RGbCAP四、一棵具有n个结点的理想平衡二叉树<即除离根最远的最底层外其他各层都是满的，最底层有若干结点）有多少层？若设根结点在第0层，则树的高度h如何用n来表示<注意n可能为0）？p1 EanqFDPw五、从供选择的答案中选择与下面有关图的叙述中各括号相匹配的词句，将其编号填入相应的括号内。

《数据结构》练习题习题一一.单项选择题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)等五个特性.(1)A. 计算方法 B．排序方法 C.解决问题的有限运算序列 D.调度方法(2)A．可行性、可移植性和可扩充性 B．可行性、确定性和有穷性C. 确定性、有穷性和稳定性 D．易读性、稳定性和安全性5．线性表的顺序存储结构是一种(1)的存储结构，线性表的链式存储结构是一种(2)的存储结构.(1)(2)A.随机存取 B.顺序存取 C．索引存取 D．散列存取6．线性表的逻辑顺序与存储顺序总是一致的，这种说法( )A．正确 B.不正确7．线性表若采用链式存储结构时，要求内存中可用存储单元的地址( )A．必须是连续的 B.部分地址必须是连续的C. 一定是不连续 D．连续或不连续都可以8.在以下的叙述中，正确的是( )A．线性表的线性存储结构优于链表存储结构B．二维数组是其数据．元素为线性表的线性表C. 栈的操作方式是先进先出D．队列的操作方式是先进后出9．一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是( ). A．110 B．108 C．100 D．12010．一个栈的入栈序列是a,b,c,d,e，则栈的不可能的输出序列是( ).A.edcba B．decba C. dceab D．abcde11.栈结构通常采用的两种存储结构是( ).A．顺序存储结构和链表存储结构B．散列方式和索引方式C. 链表存储结构和数组D.线性存储结构和非线性存储结构12．判定一个栈ST(最多元素为mO)为空的条件是(①)；判定ST为满的条件是(②).A．ST-->top<>0 B.ST-->top=0 C. ST-->mp<>m0 D．ST-->top=mO12．栈的特点是(①)，队列的特点是(②).A．先进先出 B，先进后出13．一个队列的入列序列是1，2，3，4，则队列的输出序列是( ).A. 4，3，2，1B.1，2，3，4 C．1，4，3，2 D．3，2，4，114．判定一个队列QU(最多元素为mO)为空的条件是(①)；判定QU为满的条件是(②).A. QU->rear-QU->front==m0B. QU->rear-QU->front-1==m0C. QU->front==QU->rearD. QU->front==QU->rear+115.判定一个循环队列QU(最多元素为mO)为空的条件是(①)；判定QU为满的条件是(②).A. QU->front==QU->rearB. QU->front!=QU->rearC. QU->front==(QU->rear+1)%m0D. QU->front!=(QU->rear+1)%m016.栈和队列的共同点是( ).A．都是先进后出 B．都是先进先出C. 只允许在端点处插入和删除元素 D．没有共同点17.不带头结点的单链表head为空的判定条件是( ).A. head=NULLB. head->next=NULLC. head->next=headD.head!=NULI18.带头结点的单链表head为空的判定条件是( ).A. head=NULLB. head->next=NULLC. head->next=headD. head!=NULL19.非空的循环单链表head的尾结点是(由p所指向)满足( ).A. p->next=NULLB. p=NULLC. p->next=headD. p=head20. 在循环双链表的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；21. 在一个单链表中，已知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;22. 在一个单链表中，若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;23.在一个单链表中，若删除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；24. 假设双链表结点的类型如下：typedef struct linknode{int data;struct linknode *llink；struct linknode *rlink；}bnode；下面给出的算法段是要把一个q所指新结点作为非空双向链表中的p所指结点的前驱结点插入到该双链表中，能正确完成要求的算法段是( ).A．q->rlink=p； q->llink=p->llink; p->llink=q； p->llink->rlink=q；B．p->llink=q； q->rlink=p； p->llink->rlink=q； q->llink=p->llink;C. q->llink=p->llink; q->rlink=p； p->llink->rlink=q； p->llink=q；D．以上都不对25．从一个具有n个结点的单链表中查找等于x结点时．在查找成功的情况下，需平均比较( )个结点.A. n B．n/2 C．(n-1)/2 D．(n+1)/226．在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是( ).A. O(1) B．O(n) C．O(n2) D. O(nlog2n)27．向一个栈顶指针为16的链栈中插入一个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；28.从一个栈顶指针为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；29．在一个链队中，假如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;30．在一个链队中，假如f和r分别为队首和队尾指针.要删除一个结点，则执行( )oA．r=f->next； B．r=f->next； C.f=f->next； D．f=r->next；31.空串与空格串是相同的，这种说法( ).A．正确 B.不正确32.设有两个串p和q,求q在p中首次出现的位置的运算称作( ).A.连接 B，模式匹配 C.求子串 D．求串长33．串是一种特殊的线性表，其特殊性体现在( ).A．可以顺序存储 B．数据元素是一个字符C．可以链接存储 D.数据元素可以是多个字符34.设串s1='ABCDEFG’，s2='PQRST'，函数CONCAT(x，y)返回x和y串的连接串，SUBSTR(s，i，j)返回串s的从序号i的字符开始的j个字符组成的子串，STRLEN(s)返回串s的长度，则CONCAT(SUBSTR(s1，2，STRLEN(s2))，SUBSTR(s1，STRLEN(s2)，2)的结果串是( ).A.BCDEF B．BCDEFG C．BCPQRST D.BCDEFEF35．常对数组进行的两种基本操作是( ).A．建立与删除 B．索引和修改 C查找和修改 D．查找与索引36.二维数组M的成员是6个字符(每个字符占一个存储单元)组成的串，行下标i的范围从0到8，列下标j 的范围从1到10,则存放M至少需要(①)个字节；M的第8列和第5行共占(②)个字节；若M按行优先方式存储，元素M[8][5]的起始地址与当M按列优先方式存储时的( ③)元素的起始地址一致.①A．90 B.180 C.240 D.540②A．108 B．114 C．54 D．60③A．M[8][5] B．M[3][10] C.M[5][8] D．M[0][9]37.数组A中每个元素的长度为3个字节，行下标i从1到8，列下标从l到10，从首地址SA开始连续存放在存储器内，存放该数组至少需要的单元数是( ).A．80 B．100 C．240 D．27038.数组A中每个元素的长度为3个字节，行下标i从l到8,列下标从1到10，从首地址SA开始连续存放在存储器内，该数组按行存放时，元素A[8][5]的起始地址是(①)；按列存放时，元素A[5][8]的起始地址是(②).①A．SA+141 B．SA+144 C.SA+222 D．SA+225②A. SA+141 B．SA+180 C.SA+222 D．SA+22539．稀疏矩阵一般的压缩存储方法有两种，即( ).A．二维数组和三维数组 B．三元组和散列C. 三元组和十字链表 D．散列和十字链表40.若采用三元组压缩技术存储稀疏矩阵，只要把每个元素的行下标和列下标互换，就完成了对该矩阵的转置运算，这种观点( ).A．正确 B.不正确二、填空题1．数据逻辑结构包括___________、_______________和______________三种类型，树型结构和图型结构合称为 _____________________2．在线性结构中，第一个结点______________前驱结点，其余每个结点有且只有________个前驱结点，最后一个结点_______后继结点，其余每个结点有且只有__________个后继结点.3．算法的五个重要特性是________ 、_________、______________、___________ 、_________ 和___________. 4．向量、栈和队列都是__________结构，可以在向量_________位置插入和删除元素；对于栈只能在_________ 插入和删除元素：对于队列只能在___________插入元素和在________删除元素.5.向一个长度为n的向量的第i个元素(1<=i<=n+1)之前插入一个元素时，需向后移动_______个元素.若要删除第j个元素(1<=j<=n)时，需向前移动______________个元素.6. 向栈中压入元素的操作是先____________________________,后存入元素.出栈的操作是先取出元素，后__________________.7．在一个循环队列中，队首指针指向队首元素的_____________;从该队列中删除一个元素时，其操作是先_________________，后取出元素.8.在具有n个单元的循环队列中，队满时共有_____________元素.9．单链表是_________________ 的链式存储表示.10．在双链表，每个结点有两个指针域，通常一个指向___________，另一个指向_________________.11．在一个单链表中的p所指结点之前插入一个s所指结点时，可执行如下操作：(1)s->next=_____________ (2)p->next=s； (3)t=p->data;(4)p->data=_______________; (5)s->data=_______________；12．在一个单链表中删除p所指结点时，应执行以下操作：(1)q=p->next; (2)p->data=p->next->data；(3)p->next=_________________; (4)free(q);13．带有一个头结点的单链表head为空的条件是____________________.14．在一个单链表中p所指结点之后插入一个s所指结点时，应执行(1)s->next=______________； (2)p->next=_________________；15．在栈项指针为HS的链栈中，判定栈空的条件是______________ .16．在HQ的链队中，判定只有一个结点的条件是__________________ ．17．串的两种最基本的存储方式是________________ 和_____________.18．两个串相等的充分必要条件是 ____________________.19．空串是_________________,且其长度等于________________.20.已知二维数组A[m][n]采用以行优的存储方式，每个元素占k个存储单元，并且第一个元素的存储地址是LOC(A[0][0])，则A[i][j]的地址是_________________________.21. 广义表是____________________. 如G=(al,a2,a3,…,ai,...,an)，其中G是___________，n是_______________________，ai也可以是___________________________.22．广义表(((a)))的表头是_________________，表尾是__________;广义表((a),((b),c),(((d))))的长度是____________；深度是_____________________ .23.设HEAD[P]为求广义表P的表头函数，TAIL[P]为求广义表P的表尾函数.求下列的运算结果：(1)HEAD[(a,b,c)]= _________________； (2)TAIL[(a,b,c)]=__________________;(3)HEAD[((a),(b))]=_________________; (4)TAIL[((a),(b))]=____________________.习题二一、选择题1. 如下图所示的4棵二叉树中，( )不是完全二叉树.2.A.正确 B ．不正确3.设高度为h 的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为 ( ).A ．2h B. 2h-1 C ．2h+1 O ．h+l4.已知某二叉树后序遍历序列是dabec ，中序遍历序列是debac ，它的前序遍历序列是( ).A ．acbed B.decab C.deabc D ．cedba5．二叉树为二叉排序树的充分必要条件是其任一结点的值均大于其左孩子的值、小于其右孩子的值.这种说法( ).A ．正确 B.不正确6.按照二叉树的定义，具有3个结点的二叉树有( )种形态A.3 B ．4 C ．5 D ．67.深度为5的二叉树至多有( )个结点.A ．16B ．32C ．21 D.108在一非空二叉树的中序遍历序列中，根结点的右边( ).A ．只有右子树上的所有结点B ．只有右子树上的部分结点C ．只有左子树上的部分结点 D.只有左子树上的所有结点9.树最适合用来表示( ).A ．有序数据元素B ．无序数据元素C ．元素之间具有分支层次关系的数据D ．元素之间无联系的数据10．由于二叉树中每个结点的度最大为2，所以二叉树是一种特殊的树，这种说法( ).A ．正确 B.不正确11.对于一个满二叉树,m 个树叶，n 个结点，深度为h ，则( )， A ．n=h+m B. h+m=2n C ．m=h-1 D ．n=2h -112．在一个图中，所有顶点的度数之和等于所有边数的( )倍.A.1/2B.1C.2D.413．在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的( )倍.A.1/2 B ．1 C.2 D.414．一个有n 个顶点的无向图最多有( )条边.A ．n B.n(n-1) C ．n(n-1)/2 D ．2n15．具有4个顶点的无向完全图有( )条边.A.6B.12 C ．16 D ．2016．具有6个顶点的无向图至少应有( )条边才能确保是一个连通图.A. 5B. 6 C ． 7 D ． 817．在一个具有n 个顶点的无向图中，要连通全部顶点至少需要( )条边.A. nB. n+1 C ． n-1 D ． n/218．对于一个具有n 个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是( ).A ．n B.(n-1)2 C ．n-1 D ．n 219．对于一个具有n 个顶点和e 条边的无向图，若采用邻接矩阵表示，则表头向量的大小为(①)；所有邻接表中的结点总数是(②).A ．nB ．n+l C. n-1 D.n+eA.e/2 B ．e C ．2e D.n+e20．已知一个图G(见下图)，若从顶点a 出发按深度搜索法进行遍历，则可能得到的一种顶点序列为(①)；按宽度搜索法进行遍历，则可能得到的一种顶点序列为(②).A ．a, b ，e ，c ，d, fB ．a ，c, f ，e ，b ，dC ．a ，e ，b ，c ，f, dD ．a ，e ，d ，f ，c ，bA ．a, b, c ，e ，d ，fB ．a, b, c, e, f, dC ．a ，e ，b, c ，f ，dD ．a ，c ，f, d ，e, b二、填空题1.指出树和二叉树的主要差别________________________________________________________ .2．深度为k 的完全二叉树至少存_________个结点.至多有______________个结点，若按自上而下，从左 到右次序给结点编号(从1开始)，则编号最小的叶子结点的编号是___________________________.3．在一棵二叉树中，度为零的结点的个数为n.，度为2的结点的个数为n2，则有 n0=___________________4．结点最少的树为__________________； 结点最少的二叉树为________________；一棵二叉树的第i 层最多有__________________个结点.5．现有按中序遍历二叉树的结果为abc ，则有__________________棵二叉树可以得到这一遍历结果；这些二叉树分别是：6．树有三种常用的存储方法：__________________、________________ ，______________8．n 个顶点的连通图至少有________________________条边.9. 在无向图G 的邻接矩阵A 中，若A[i][j]等于1，，则A[j][i]等于_________________.10．已知一个图的邻接矩阵表示，计算第 i 个结点的入度的方法是_____________________________11．已知一个图的邻接矩阵表示，删除所有从第i 个结点出发的边的方法是____________________________12．已知无向图G 的邻接链表如下图所示,求：（1）画出对应的无向图G 。

第一章1．在数据结构中，从逻辑上可以把数据结构分为（C ）A．动态结构和静态结构 B. 紧凑结构和非紧凑结构C．线性结构和非线性结构 D. 内部结构和外部结构● 2.在数据结构中,与所使用的计算机无关的是( A )A. 逻辑结构B. 存储结构C. 逻辑和存储结构D. 物理结构3.下面程序的时间复杂度为____O（mn）_______。

for (int i=1; i<=m; i++)for (int j=1; j<=n; j++ )S+=i第二章线性表●链表不具备的特点是（A）A 可以随机访问任一结点（顺序）B 插入删除不需要移动元素C 不必事先估计空间D 所需空间与其长度成正比2. 不带头结点的单链表head为空的判定条件为（A ），带头结点的单链表head为空的判定条件为（B ）A head==nullB head->next==nullC head->next==headD head!=null●3.在线性表的下列存储结构中，读取元素花费时间最少的是（D）A 单链表B 双链表C 循环链表D 顺序表● 4.对于只在表的首、尾两端进行手稿操作的线性表，宜采用的存储结构为(C)A 顺序表B 用头指针表示的单循环链表C 用尾指针表示的单循环链表D 单链表● 5.在一个具有n 个结点的有序单链表中插入一个新的结点，并保持链表元素仍然有序，则操作的时间复杂度为( D )A O(1)B O(log2n)C O(n2)D O(n)● 6.在一个长度为n (n>1)的单链表上，设有头和尾两个指针，执行(B)操作与链表的长度有关A 删除单链表中第一个元素B 删除单链表中最后一个元素C 在第一个元素之前插入一个新元素D 在最后一个元素之后插入一个新元素●7.与单链表相比，双向链表的优点之一是(D)A 插入删除操作更简单B 可以进行随机访问C 可以省略表头指针或表尾指针D 顺序访问相邻结点更容易●8.若list是某带头结点的循环链表的头结点指针，则该链表最后那个链结点的指针域(头结点的地址)中存放的是( B )A list的地址B list的内容C list指的链结点的值D 链表第一个链结点的地址●9.若list1和list2分别为一个单链表与一个双向链表的第一个结点的指针，则( B )A list2比list1占用更多的存储单元B list1与list2占用相同的存储单元C list1和list2应该是相同类型的指针变量D 双向链表比单链表占用更多的存储单元10.链表中的每个链结点占用的存储空间不必连续，这句话正确吗？ (不正确)11. 某线性表采用顺序存储结构，元素长度为4，首地址为100，则下标为12的（第13个）元素的存储地址为148。

数据结构练习题习题1 绪论1.1 单项选择题1. 数据结构是一门研究非数值计算的程序设计问题中,数据元素的①、数据信息在计算机中的②以及一组相关的运算等的课程。

① A．操作对象Ｂ．计算方法Ｃ．逻辑结构Ｄ．数据映象② A．存储结构Ｂ．关系Ｃ．运算Ｄ．算法2. 数据结构DS(Data Struct)可以被形式地定义为DS=（D，R），其中D是①的有限集合，R是D上的②有限集合。

① A．算法Ｂ．数据元素Ｃ．数据操作Ｄ．数据对象② A．操作Ｂ．映象Ｃ．存储Ｄ．关系3. 在数据结构中，从逻辑上可以把数据结构分成。

A．动态结构和静态结构Ｂ．紧凑结构和非紧凑结构Ｃ．线性结构和非线性结构Ｄ．内部结构和外部结构4. 算法分析的目的是①，算法分析的两个主要方面是②。

① A. 找出数据结构的合理性 B. 研究算法中的输入和输出的关系C. 分析算法的效率以求改进D. 分析算法的易懂性和文档性② A. 空间复杂性和时间复杂性 B. 正确性和简明性C. 可读性和文档性D. 数据复杂性和程序复杂性5. 计算机算法指的是①，它必具备输入、输出和②等五个特性。

① A. 计算方法 B. 排序方法C. 解决问题的有限运算序列D. 调度方法② A. 可行性、可移植性和可扩充性 B. 可行性、确定性和有穷性C. 确定性、有穷性和稳定性D. 易读性、稳定性和安全性1.2 填空题（将正确的答案填在相应的空中）1. 数据逻辑结构包括、和三种类型，树形结构和图形结构合称为。

2. 在线性结构中，第一个结点前驱结点，其余每个结点有且只有个前驱结点；最后一个结点后续结点，其余每个结点有且只有个后续结点。

3. 在树形结构中，树根结点没有结点，其余每个结点有且只有个直接前驱结点，叶子结点没有结点，其余每个结点的直接后续结点可以。

4. 在图形结构中，每个结点的前驱结点数和后续结点数可以。

5. 线性结构中元素之间存在关系，树形结构中元素之间存在关系，图形结构中元素之间存在关系。

第一章绪论一．选择题1．数据结构被形式地定义为（K，R），其中K是①的有限集合，R是K上的②的有限集合。

①A．算法B．数据元素C．数据操作D．逻辑结构②A．操作B．映象C．存储D．关系2．算法分析的目的是①，算法分析的两个主要方面是②。

①A．找出数据结构的合理性B．研究算法中的输入和输出的关系C．分析算法的效率以求改进D．分析算法的易懂性和文档性②A．空间复杂性和时间复杂性B．正确性和简明性C．可读性和文档性D．数据复杂性和程序复杂性3．在计算机存储器内表示时，物理地址和逻辑地址相同并且是连续的，称之为A．逻辑结构B．顺序存储结构C．链表存储结构D．以上都不对4．数据结构中，在逻辑上可以把数据结构分成：( ）。

A．动态结构和静态结构B．紧凑结构和非紧凑结构C．线性结构和非线性结构D．内部结构和外部结构5．以下属于顺序存储结构优点的是（）。

A．存储密度大B．插入运算方便C．删除运算方便D．可方便地用于各种逻辑结构的存储表示6．数据结构研究的内容是（）。

A．数据的逻辑结构B．数据的存储结构C．建立在相应逻辑结构和存储结构上的算法D．包括以上三个方面7．链式存储的存储结构所占存储空间（）。

A．分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针B．只有一部分，存放结点值C．只有一部分，存储表示结点间关系的指针D．分两部分，一部分存放结点值，另一部分存放结点所占单元数8．一个正确的算法应该具有5 个特性，除输入、输出特性外，另外3 个特性是（）。

A．确定性、可行性、有穷性B．易读性、确定性、有效性C．有穷性、稳定性、确定性D．可行性、易读性、有穷性9．以下关于数据的逻辑结构的叙述中正确的是（）。

A．数据的逻辑结构是数据间关系的描述B．数据的逻辑结构反映了数据在计算机中的存储方式C．数据的逻辑结构分为顺序结构和链式结构D．数据的逻辑结构分为静态结构和动态结构10．算法分析的主要任务是（）。

A．探讨算法的正确性和可读性B．探讨数据组织方式的合理性C．为给定问题寻找一种性能良好的解决方案D．研究数据之间的逻辑关系二、填空题1.下面程序段的时间复杂度是_____O(n2)_______。

数据结构练习题第一部分绪论一、单选题1. 一个数组元素a[i]与________的表示等价。

A、 *(a+i)B、 a+iC、 *a+iD、 &a+i2. 对于两个函数，若函数名相同，但只是____________不同则不是重载函数。

A、参数类型B、参数个数C、函数类型3. 若需要利用形参直接访问实参，则应把形参变量说明为________参数A、指针B、引用C、值4. 下面程序段的时间复杂度为____________。

for(int i=0; i<m; i++)for(int j=0; j<n; j++)a[i][j]=i*j;A、 O(m2)B、 O(n2)C、 O(m*n)D、 O(m+n)5. 执行下面程序段时，执行S语句的次数为____________。

for(int i=1; i<=n; i++)for(int j=1; j<=i; j++)S;A、 n2B、 n2/2C、 n(n+1)D、 n(n+1)/26. 下面算法的时间复杂度为____________。

int f( unsigned int n ) {if ( n==0 || n==1 ) return 1; else return n*f(n-1);}A、 O(1)B、 O(n)C、 O(n2)D、 O(n!)二、填空题1. 数据的逻辑结构被分为__________、_________、__________和__________四种。

2. 数据的存储结构被分为__________、_________、__________和__________四种。

3. 在线性结构、树形结构和图形结构中，前驱和后继结点之间分别存在着________、________和________的联系。

4. 一种抽象数据类型包括__________和__________两个部分。

5. 当一个形参类型的长度较大时，应最好说明为_________，以节省参数值的传输时间和存储参数的空间。

一、单选题（每小题3分，共30分）1．在逻辑上可以把数据结构分成。

( ) A．动态结构和静态结构B．紧凑结构和非紧凑结构C．线性结构和非线性结构D．内部结构和外部结构2．串是_________。

( ) A．不少于一个字母的序列B．任意个字母的序列C．不少于一个字符的序列D．有限个字符的序列3．在n个元素的顺序表中，时间复杂度是O(1)的操作是______。

( ) A．获得第i个数据元素值B．查找给定值C．在第i个位置上插入数据元素D．删除第i个数据元素4．线性表若采用链式存储结构时，要求内存中可用存储单元的地址________。

( )A. 必须是连续的B. 部分地址必须是连续的C. 一定是不连续的D. 连续或不连续都可以5．单链表中，在p结点之后插入q结点，操作的语句为。

( ) A．q->next=p->next，p->next=q B．p=q->next，q->next=pC．p->next=q->next，q->next=p D．q=p->next，p->next=q6．栈中数据元素的插入和删除操作是在表的进行的。

( )A．一端B．两端C．中间D．任意位置7．队列的特点是。

( )A．先进先出B．后进先出C．先进后出D．随机存取8．树中结点A有3个兄弟，结点B是A的双亲，则B的度是。

( )A．1B．2C．3D．49．下面关于图的存储结构的叙述中正确的是____________。

( )A.用邻接矩阵存储图，占用空间大小只与图中顶点数有关，而与边数无关B.用邻接矩阵存储图，占用空间大小只与图中边数有关，而与顶点数无关C.用邻接表存储图，占用空间大小只与图中顶点数有关，而与边数无关D.用邻接表存储图，占用空间大小只与图中边数有关，而与顶点数无关10．对于不带权的有向图，其邻接矩阵的每一列包含的“1”的个数为。

( )A．图中每个顶点的入度B．图中每个顶点的出度C．图中弧的条数D．图中连通分量的数目二、判断题（每小题1分，共10分）对于正确的说法，请在题前的括号内打√，错误的说法则打×。

数据结构练习题第一部分绪论一、单选题1. 一个数组元素a[i]与________的表示等价。

A、 *(a+i)B、 a+iC、 *a+iD、 &a+i2. 对于两个函数，若函数名相同，但只是____________不同则不是重载函数。

A、参数类型B、参数个数C、函数类型3. 若需要利用形参直接访问实参，则应把形参变量说明为________参数A、指针B、引用C、值4. 下面程序段的时间复杂度为____________。

for(int i=0; i<m; i++)for(int j=0; j<n; j++)a[i][j]=i*j;A、 O(m2)B、 O(n2)C、 O(m*n)D、 O(m+n)5. 执行下面程序段时，执行S语句的次数为____________。

for(int i=1; i<=n; i++)for(int j=1; j<=i; j++)S;A、 n2B、 n2/2C、 n(n+1)D、 n(n+1)/26. 下面算法的时间复杂度为____________。

int f( unsigned int n ) {if ( n==0 || n==1 ) return 1; else return n*f(n-1);}A、 O(1)B、 O(n)C、 O(n2)D、 O(n!)二、填空题1. 数据的逻辑结构被分为__________、_________、__________和__________四种。

2. 数据的存储结构被分为__________、_________、__________和__________四种。

3. 在线性结构、树形结构和图形结构中，前驱和后继结点之间分别存在着________、________和________的联系。

4. 一种抽象数据类型包括__________和__________两个部分。

5. 当一个形参类型的长度较大时，应最好说明为_________，以节省参数值的传输时间和存储参数的空间。