下载文档原格式
数据结构试卷（二）一、选择题(24分)1．下面关于线性表的叙述错误的是（）。
(A) 线性表采用顺序存储必须占用一片连续的存储空间(B) 线性表采用链式存储不必占用一片连续的存储空间(C) 线性表采用链式存储便于插入和删除操作的实现(D) 线性表采用顺序存储便于插入和删除操作的实现2．设哈夫曼树中的叶子结点总数为m，若用二叉链表作为存储结构，则该哈夫曼树中总共有（）个空指针域。
(A) 2m-1 (B) 2m (C) 2m+1 (D) 4m3．设顺序循环队列Q[0：M-1]的头指针和尾指针分别为F和R，头指针F总是指向队头元素的前一位置，尾指针R总是指向队尾元素的当前位置，则该循环队列中的元素个数为（）。
(A) R-F (B) F-R (C) (R-F+M)％M (D) (F-R+M)％M4．设某棵二叉树的中序遍历序列为ABCD，前序遍历序列为CABD，则后序遍历该二叉树得到序列为（）。
(A) BADC (B) BCDA (C) CDAB (D) CBDA5．设某完全无向图中有n个顶点，则该完全无向图中有（）条边。
(A) n(n-1)/2 (B) n(n-1) (C) n2(D) n2-16．设某棵二叉树中有2000个结点，则该二叉树的最小高度为（）。
(A) 9 (B) 10 (C) 11 (D) 127．设某有向图中有n个顶点，则该有向图对应的邻接表中有（）个表头结点。
(A) n-1 (B) n (C) n+1 (D) 2n-18．设一组初始记录关键字序列(5，2，6，3，8)，以第一个记录关键字5为基准进行一趟快速排序的结果为（）。
(A) 2，3，5，8，6 (B) 3，2，5，8，6(C) 3，2，5，6，8 (D) 2，3，6，5，8二、填空题(24分)1.为了能有效地应用HASH查找技术，必须解决的两个问题是____________________和__________________________。
数据结构试卷（一）一、选择题(30分)1．设一维数组中有n个数组元素，则读取第i个数组元素的平均时间复杂度为（）。
(A) O(n)(B) O(nlog2n)(C) O(1)(D) O(n2)2．设一棵二叉树的深度为k，则该二叉树中最多有（）个结点。
(A) 2k-1(B) 2k(C) 2k-1(D) 2k-13．设某无向图中有n个顶点e条边，则该无向图中所有顶点的入度之和为（）。
(A) n(B) e(C) 2n(D) 2e4．在二叉排序树中插入一个结点的时间复杂度为（）。
(A) O(1)(B) O(n)(C) O(log2n)(D) O(n2)5．设某有向图的邻接表中有n个表头结点和m个表结点，则该图中有（）条有向边。
(A) n(B) n-1(C) m(D) m-16．设一组初始记录关键字序列为(345，253，674，924，627)，则用基数排序需要进行（）趟的分配和回收才能使得初始关键字序列变成有序序列。
(A) 3(B) 4(C) 5(D) 87．设用链表作为栈的存储结构则退栈操作（）。
(A) 必须判别栈是否为满(B) 必须判别栈是否为空(C) 判别栈元素的类型(D) 对栈不作任何判别8．下列四种排序中（）的空间复杂度最大。
(A) 快速排序(B) 冒泡排序(C) 希尔排序(D) 堆9．设某二叉树中度数为0的结点数为N0，度数为1的结点数为N l，度数为2的结点数为N2，则下列等式成立的是（）。
(A) N0=N1+1(B) N0=N l+N2(C) N0=N2+1(D) N0=2N1+l10.设有序顺序表中有n个数据元素，则利用二分查找法查找数据元素X的最多比较次数不超过（）。
(A) log2n+1(B) log2n-1(C) log2n(D) log2(n+1)二、填空题(42分)1．1．设有n个无序的记录关键字，则直接插入排序的时间复杂度为________，快速排序的平均时间复杂度为_________。
计算机专业数据结构试题一、选择题（每小题1分，共10分）1、在一个长度为n的顺序表的表尾插入一个新元素的渐进时间复杂度为（）A．O (n) B．O (1) C．O (n2 ) D．O (log2 n)2、设单链表中结点的结构为（data , link）。
已知指针q所指结点是指针p所指结事业的直接前驱，若在*q与*p之间插入结点*s，则应执行下列哪一个操作？（）A．s ->link= p->link ; p->link=s B．q->link=s ;s->link=pC．p->link=s->link ;s->link=p D．p->link=s ;s->link=q3、若让元素1，2，3依次进栈，则出栈次序不可能出现（）种情况。
A．3，2，1 B．2，1，3 C．3，1，2 D．1，3，24、一个递归的定义可以用递归过程求解，也可以用非递归过程求解，但单从运行时间来看，通常递归过程比非递归过程（）A．较快B．较慢C．相同5、树中所有结点的度等于所有结点数加（）A．0 B．1 C．-1 D．26、在一棵具有n个结点的二叉树中，所有结点的空子树个数等于（）A．n B．n-1 C．n+1 D．2*n7、对长度为n的有序单链表，若搜索每个元素的概率相等，则顺序搜索到表中任一元素的平均搜索长度为（）A．n/2 B．(n+1)/2 C．(n –1)/2 D．n/48、在无向图中定义顶点V i与V j之间的路径为从V i到达V j的一个（）A．顶点序列B．边序列C．权值总和D．边的条数9、如果只想得到1024个元素组成的序列中的前5个最小元素，那么用（）方法最快。
A．起泡排序B．快速排序C．堆排序D．直接选择排序10、设有一个含200个表项的散列表，用线性探查法解决冲突，按关键码查询时找到一个表项的平均探查次数不超过1.5，则散列表项应能够至少容纳（）个表项。
数据结构试题一、单选题（每题 2 分，共20分）1.1. 对一个算法的评价，不包括如下（ B ）方面的内容。
A．健壮性和可读性B．并行性 C．正确性 D．时空复杂度2.2. 在带有头结点的单链表HL中，要向表头插入一个由指针p指向的结点，则执行( A )。
A. p->next=HL->next; HL->next=p;B. p->next=HL; HL=p;C. p->next=HL; p=HL;D. HL=p; p->next=HL;3.3. 对线性表，在下列哪种情况下应当采用链表表示？( B )A.经常需要随机地存取元素B.经常需要进行插入和删除操作C.表中元素需要占据一片连续的存储空间D.表中元素的个数不变4.4. 一个栈的输入序列为 1 2 3，则下列序列中不可能是栈的输出序列的是( C )A. 2 3 1B. 3 2 1C. 3 1 2D. 1 2 35.5. AOV网是一种（ D ）。
A．有向图 B．无向图 C．无向无环图D．有向无环图6.6. 采用开放定址法处理散列表的冲突时，其平均查找长度（ B ）。
A．低于链接法处理冲突 B. 高于链接法处理冲突C．与链接法处理冲突相同 D．高于二分查找7.7. 若需要利用形参直接访问实参时，应将形参变量说明为（ D ）参数。
A．值 B．函数 C．指针 D．引用8.8. 在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结点都具有相同的（ A ）。
A．行号B．列号 C．元素值 D．非零元素个数9.9. 快速排序在最坏情况下的时间复杂度为（ D ）。
A．O(log2n) B．O(nlog2n) C．O(n) D．O(n2)10.10. 从二叉搜索树中查找一个元素时，其时间复杂度大致为( C )。
A. O(n)B. O(1)C. O(log2n) D. O(n2)二、运算题（每题 6 分，共24分）1. 1. 数据结构是指数据及其相互之间的_对应关系(联系)。
第二章线性表一、选择题1.一个线性表第一个元素的存储地址是100,每个元素的长度为2,则第5个元素的地址是( )（A）110 （B）108（C）100 （D）120参考答案：B2. 向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动（）个元素。
（A）64（B）63 （C）63.5 （D）7参考答案：C3.线性表采用链式存储结构时，其地址（）。
(A) 必须是连续的 (B) 部分地址必须是连续的(C) 一定是不连续的 (D) 连续与否均可以参考答案：D4. 在一个单链表中，若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;参考答案：B5.在一个单链表中，若删除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;参考答案：A6.下列有关线性表的叙述中，正确的是（）（A）线性表中的元素之间隔是线性关系（B）线性表中至少有一个元素（C）线性表中任何一个元素有且仅有一个直接前趋（D）线性表中任何一个元素有且仅有一个直接后继参考答案：A7.线性表是具有n个（）的有限序列（n≠0)（A）表元素（B）字符（C）数据元素（D）数据项参考答案：C二、判断题1.线性表的链接存储，表中元素的逻辑顺序与物理顺序一定相同。
（）2.如果没有提供指针类型的语言，就无法构造链式结构。
（）3.线性结构的特点是只有一个结点没有前驱，只有一个结点没有后继，其余的结点只有一个前驱和后继。
数据结构练习（二）答案一、填空题：1．若一棵树的括号表示为A（B（E，F），C（G（H,I,J,K）,L）,D（M（N））），则该树的度为（1）4，树的深度为（2）4 ，树中叶子结点的个数为（3）8。
2．一棵满二叉树中有m个叶子，n个结点，深度为h，请写出m、n、h之间关系的表达式（4）n=2h-1,m=n+1-2h-1 n=2m-1 。
3．一棵二叉树中如果有n个叶子结点，则这棵树上最少有（5）2n-1 个结点。
一棵深度为k的完全二叉树中最少有2k-1（6）个结点，最多有（7）2k-1个结点。
4．具有n个结点的二叉树，当它是一棵(8)完全二叉树时具有最小高度（9） log2n」+1，当它为一棵单支树时具有高度(10) n 。
5．对具有n个结点的完全二叉树按照层次从上到下，每一层从左到右的次序对所有结点进行编号，编号为i的结点的双亲结点的编号为_(11)__[i/2]__，左孩子的编号为___2i____，右孩子的编号为__2i+1______。
6．若具有n个结点的二叉树采用二叉链表存储结构，则该链表中有__2n_个指针域，其中有_n-1_个指针域用于链接孩子结点，__n+1_个指针域空闲存放着NULL 。
7．二叉树的遍历方式通常有__先序__、___中序__、__后序__和___层序___四种。
8．已知二叉树的前序遍历序列为ABDCEFG，中序遍历序列为DBCAFEG，其后序遍历序列为___DCBFGEA__。
9．已知某完全二叉树采用顺序存储结构，结点的存放次序为A,B,C,D,E,F,G,H,I,J，该完全二叉树的后序序列为___HIDJEBFGCA____。
10．若具有n个结点的非空二叉树有n0个叶结点，则该二叉树有__n0-1_个度为2的结点，____n-2n0+1____个度为1的结点。
11．任何非空树中有且仅有一个结点没有前驱结点，该结点就是树的__根____。
度为k的树中第i层最多有___k i-1_______个结点(i>=1)，深度为h的k叉树最多有___k0+k1+....+k h-1____个结点。
第1章绪论一、选择题1. 算法的计算量的大小称为计算的（）。
【北京邮电大学2000 二、3 （20/8分）】A．效率 B. 复杂性 C. 现实性 D. 难度2. 算法的时间复杂度取决于（）【中科院计算所1998 二、1 （2分）】A．问题的规模 B. 待处理数据的初态 C. A和B3.计算机算法指的是（1），它必须具备（2）这三个特性。
(1) A．计算方法 B. 排序方法 C. 解决问题的步骤序列 D. 调度方法(2) A．可执行性、可移植性、可扩充性 B. 可执行性、确定性、有穷性C. 确定性、有穷性、稳定性D. 易读性、稳定性、安全性【南京理工大学1999 一、1（2分）【武汉交通科技大学1996 一、1（4分）】4．一个算法应该是（）。
【中山大学1998 二、1（2分）】A．程序B．问题求解步骤的描述C．要满足五个基本特性D．A和C.5. 下面关于算法说法错误的是（）【南京理工大学2000 一、1（1.5分）】A．算法最终必须由计算机程序实现B. 为解决某问题的算法同为该问题编写的程序含义是相同的C. 算法的可行性是指指令不能有二义性D. 以上几个都是错误的6. 下面说法错误的是（）【南京理工大学2000 一、2 （1.5分）】(1）算法原地工作的含义是指不需要任何额外的辅助空间（2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法（3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界（4）同一个算法，实现语言的级别越高，执行效率就越低A．(1) B.(1),(2) C.(1),(4) D.(3)7．从逻辑上可以把数据结构分为（）两大类。
【武汉交通科技大学1996 一、4（2分）】A．动态结构、静态结构B．顺序结构、链式结构C．线性结构、非线性结构D．初等结构、构造型结构8．以下与数据的存储结构无关的术语是（）。
【北方交通大学2000 二、1（2分）】A．循环队列 B. 链表 C. 哈希表 D. 栈9．以下数据结构中，哪一个是线性结构（）？【北方交通大学2001 一、1（2分）】A．广义表 B. 二叉树 C. 稀疏矩阵 D. 串10．以下那一个术语与数据的存储结构无关？（）【北方交通大学2001 一、2（2分）】A．栈 B. 哈希表 C. 线索树 D. 双向链表11．在下面的程序段中，对x的赋值语句的频度为（）【北京工商大学2001 一、10（3分）】FOR i:=1 TO n DOFOR j:=1 TO n DOx:=x+1;A．O(2n) B．O(n) C．O(n2) D．O (log2n)12．程序段FOR i:=n-1 DOWNTO 1 DOFOR j:=1 TO i DOIF A[j]>A[j+1]THEN A[j]与A[j+1]对换；其中n为正整数，则最后一行的语句频度在最坏情况下是（）A. O（n）B. O(nlogn)C. O(n3)D. O(n2) 【南京理工大学1998一、1(2分)】13．以下哪个数据结构不是多型数据类型（）【中山大学1999 一、3（1分）】A．栈B．广义表C．有向图D．字符串14．以下数据结构中，（）是非线性数据结构【中山大学1999 一、4】A．树B．字符串C．队D．栈15. 下列数据中，（）是非线性数据结构。
一、填空题1.数据结构包括、和三方面的内容。
2.数据的逻辑结构分为、、、。
3.数据的逻辑结构分为和两大类。
4.数据的存储结构被分为、、、。
5.数据的存储方式有、、和四种基本存储方式。
6.顺序存储和链式存储相比较的存储密度大，的插入删除方便。
7.在线性表的单链接存储结构中，每个结点包含有两个域，一个叫域，另一个叫域。
8.在线性表的单链接存储中，若一个元素所在结点的地址为P，则其后继结点的地址为，若假定P为一个数组a中的下标，则其后继结点的下标为。
9.在顺序存储的向量中，设第一个元素的地址为loc(k1)，每个元素占用的空间为M，则第i个元素ki的地址为loc(ki)=loc(k1)+(i-1)*M 。
10.在循环单链表中，最后一个结点的指针域指向结点。
11.队列的插入操作在进行，删除操作在进行。
12.一棵n个结点的树，其边数为条。
13.设二叉树根结点的层数为0，则第i层上最多有个结点。
14.在一棵二叉树中，第5层上的结点数最多为。
15.深度为 K 的完全二叉树，至少有个结点，至多有个结点。
16.深度为 8 (根的层次号为 1 )的满二叉树有个叶子结点。
17.深度为K的二叉树结点总数最大为。
18.深度为 k (根的层次号为 1 )的满二叉树有个叶子结点。
19.在完全二叉树中，对结点按层次编号，根结点编号为1。
若结点i有右子女，则右子女的编号为，左子女的编号为。
20.按后根次序周游树林，正好等同于按次序周游与之对应的二叉树。
21.按先根次序周游树林，正好等同于按次序周游对应的二叉树。
22.对一棵二叉排序树进行中序遍历时，得到的结点序列是一个。
23.在一个具有n个顶点的无向完全图中，包含有条边。
24.设有m个结点的无向图中，如果其边数为就称为完全图。
25.在图中，与结点相关的边的数目称为该结点的。
26.在有向图的邻接表和逆邻接表表示中，每个顶点邻接表分别链接着该顶点的所有和结点。
27.对于一个长度为n的顺序存储的线性表，在表头插入元素的时间复杂度为，在表尾插入元素的时间复杂度为。
模拟试题二模拟试题二一、选择题（28分）1.设一数列的顺序为l，2，3,4，5,通过栈结构不可能排成的顺序数列为( )。
A)3,2，5，4，l B)1，5,4，2，3C）2，4，3,5,l D）4，5，3，2,l2。
二叉树的第3层最少有（)个结点。
A)0 B）1 C)2 D）33。
—个n个顶点的连通无向图，其边的个数至少为( )。
A) n-l B)n C）n+l D）nlogn4。
下列排序方法中，( ）的比较次数与记录的初始排列状态无关。
A）直接插入排序 B）起泡排序C）快速排序 D）直接选择排序5.-棵哈夫曼树总共有II个结点，则叶子结点有( ）个。
A）5 B）6 C）7 D)96.已知某算法的执行时间为（n+n2)+log2(n+2)，n为问题规模,则该算法的时间复杂度是( ）。
A)O（n）B）O（n2) C）O（log2n）D）O(nlog2n)7。
如果一棵树有10个叶子结点，则该树总共至少有( )个结点。
A）lO B）11 C）19 D) 218。
—个100×100的三角矩阵a采用行优先压缩存储后，如果首元素a[0]［0]是第一个元素，那么a[4] [2］是第( )个元素。
A）13 B) 401 C) 402 D）4039.有一棵二叉树如题图1,该树是（）。
A）二叉平衡树B)二叉排序树C)堆的形状D)以上都不是10。
对于含有n个顶点e条边的无向连通图，利用Prim算法生成最小代价生成树，其时间复杂度为（)，利用Kruska算法的时间复杂度为（).A）O（log2n) B）0(n2) C)O（ne) D）O（elog2ne)11.具有n个顶点的完全有向图的边数为( ）.A）n（n—l)/2 B）n（n-l） C) n2 D）n2—112。
设有100个元素，用折半查找时,最大比较次数为（)，最小比较次数为（）。
A）25 B)7 C) 10 D)l13。
在内部排序中，排序时不稳定的有（).A）插入排序B）冒泡排序C）快速排序D）归并排序14.串是一种特殊的线性表，其特殊性体现在（)。
期末样卷参考答案期末样卷参考答案一．是非题（每题2分共20分）分）1. 1. 线性表的链式存储结构优于顺序存储结构。
线性表的链式存储结构优于顺序存储结构。
线性表的链式存储结构优于顺序存储结构。
F2. 2. 栈和队列也是线性表。
如果需要，可对它们中的任一元素进行操作。
栈和队列也是线性表。
如果需要，可对它们中的任一元素进行操作。
F3． 字符串是数据对象特定的线性表。
T4． 在单链表P 指针所指结点之后插入S 结点的操作是：P->next= S ; S-> next = P->next; F 5． 一个无向图的连通分量是其极大的连通子图。
T6． 邻接表可以表示有向图，也可以表示无向图。
T7． 假设B 是一棵树，B ′是对应的二叉树。
则B 的后根遍历相当于B ′的中序遍历。
T 8． 通常，二叉树的第i 层上有2i-1个结点。
F9． 对于一棵m 阶的B -树,树中每个结点至多有m 个关键字。
除根之外的所有非终端结点至少有┌m/2┐个关键字。
F10．对于任何待排序序列来说，快速排序均快于起泡排序。
F 二．选择题（每题2分共28分） 1． 在下列排序方法中，在下列排序方法中，（ c ）方法平均时间复杂度为0(nlogn)0(nlogn)，最坏情况下时间复，最坏情况下时间复杂度为0(n 2)；（ d ）方法所有情况下时间复杂度均为0(nlogn)0(nlogn)。
a. a. 插入排序插入排序插入排序b. b. b. 希尔排序希尔排序希尔排序c. c. c. 快速排序快速排序快速排序d. d. d. 堆排序堆排序堆排序2. 2. 在有在有n 个结点的二叉树的二叉链表表示中，空指针数为（个结点的二叉树的二叉链表表示中，空指针数为（ b ）。
a. a.不定不定不定 b.n+1 c.n d.n-1 b.n+1 c.n d.n-13. 3. 下列二叉树中，下列二叉树中，（ a ）可用于实现符号不等长高效编码。
一、选择题(共20分，共10题，每题2分)1. 关于顺序表的叙述错误的是（D ）。
A．要占用连续存储空间 B.单个数据所需内存空间比链表少C．随机存取功能比链表强D.插入与删除不需要移动大量元素2. 在线索化二叉树中，T所指结点没有左子树的充要条件是（ B ）。
A. T->Lchild=NULLB. T->LTag=1C. T->RTag=0D. T->RTag=13. 能够在AOE网络中计算源点到汇点最长路径的算法是（ A ）。
A. 关键路径算法B. 深度优先搜索C. 拓扑排序D. Prim4. 在长度为n的顺序线性表中顺序查找值为x的元素时，查找成功时的平均查找长度(等概率情况下)为( C )。
A. nB. n/2C. (n+1)/2D. (n-1)/25. 以下排序算法中不稳定的是（B ）。
A. 冒泡排序B. 希尔排序C. 直接插入排序D. 归并排序6. 若长度为n的线性表采用顺序存储结构，删除表中1个数据元素的平均算法时间复杂度是( A )。
A. O( (n-1)/2 )B. O( (n+1)/2 )C. O( (n2-1)/2 )D. O( (n+1)/2 )7. 下列几种二叉树中任意交换其左右子树仍然保持性质不变的是( A )。
A. 最优二叉树B.排序二叉树C. 平衡二叉树D. 以上都不是8. 下面的说法中，正确的是( A )。
A. 全源最短路径Floyd算法非常类似矩阵的自乘运算B. 从源点到终点的最短路径是唯一的C. 无向图最小生成树权值之和一定小于其它生成树权值之和D. 任意一个AOV网中的关键路径是唯一的9. 希尔排序的时间复杂度是( D )。
A. O( n·log n )B. O( n2·log n )C. O(n2)D. 以上都不是10. 根据大顶堆的定义，下列四个序列中，是一个堆积的是( C )。
A. 7565301525452010B. 7565451030252015C. 7545653015252010D. 7545651025302015二、填空题(共20分，共5题，每空2分)1.为了区分循环队列判空的条件，循环队列判满的方法有计数器法、设置标志位法、牺牲一个存储单元法。
数据结构复习题一、单项选择题1．数据结构在计算机中的表示称为数据的（）。
A）存储结构B）抽象结构C）顺序结构D）逻辑结构2．对于下面程序段的时间复杂度为（）。
for(i=1;i<=n;i++)for(j=1;j<=i;j++)x=x+1;A）O(n) B）O(n2) C）O(n*i) D）O(n+i)3．数据结构是（）。
A）相互之间存在一种或多种特定关系的数据元素的集合B）相互之间存在一种特定关系的数据元素的集合C）数据元素的集合D）前面都不正确4．数据结构可形式地定义为(D,S)，其中S是D上（）的有限集。
A）操作B）存储映像C）关系D）数据元素5．数据结构在计算机中存储器内表示时，物理地址和逻辑地址相同并且是连续的，称之为（）。
A）逻辑结构B）顺序存储结构C）链式存储结构D）以上都对6．如一个结构中的数据元素之间存在一个对多个的关系，则此结构为（）。
A）集合结构B）线性结构C）树形结构D）图状结构7．在数据类型中，值不可分解的类型为（）。
A）原子类型B）结构类型C）固定聚合类型D）可变聚合类型8．下面程序段的时间复杂度为（）。
for(i=n;i>=1;i--)for(j=1;j<=i;j++)x=x+1;A）O(n) B）O(n2) C）O(n*i) D）O(n+i)9．数据类型为（）。
A）数据项的集合B）值的集合及定义在其上的一组操作的总称C）数据元素的集合D）关键字的集合10．网状结构的特征是（）。
A）结构中数据元素之间只存在“同属于一个集合”的关系B）结构中数据元素之间存在一个对应一个的关系C）结构中数据元素之间存在一个对应多个的关系D）结构中数据元素之间存在多个对应多个的关系11．设计一个“好”的算法应达到的目标为（）。
A）正确性、可读性、健壮性及效率与低存储量需求B）正确性、可读性、健壮性及有穷性C）正确性、可读性、健壮性及可行性D）正确性、可读性、健壮性及确定性13．线性链表中各链结点之间的地址（）。
《数据结构》复习题及参考答案数据结构复习题及参考答案1. 什么是数据结构？数据结构是一种组织和存储数据的方式，它涉及到数据的组织方式、存储方式、访问方式以及对数据进行操作的算法等。
数据结构的选择对于解决不同类型的问题非常重要。
2. 数据结构有哪些常见的分类？数据结构可以分为以下几类：(1) 线性结构：线性结构是一种有序排列的数据结构，其中数据元素之间存在着一对一的关系。
常见的线性结构有数组、链表、栈和队列等。
(2) 非线性结构：非线性结构是一种数据元素之间存在多对多关系的结构，常见的非线性结构有树和图等。
(3) 逻辑结构：逻辑结构是指数据元素之间的逻辑关系，主要包括集合结构、线性结构、树形结构和图形结构等。
(4) 物理结构：物理结构是指数据的逻辑结构在计算机存储中的表示方式，主要包括顺序存储结构和链式存储结构等。
3. 什么是算法？算法是解决特定问题的一系列步骤或操作的有限序列。
一个算法通常包括输入、输出、基本操作、控制结构和定义算法执行的约定等。
4. 数据结构和算法之间的关系是什么？数据结构是算法的基础，而算法又依赖于数据结构。
只有选择合适的数据结构，才能实现高效的算法。
同时，算法的设计也会对数据结构的选择产生影响。
5. 请解释什么是时间复杂度和空间复杂度？时间复杂度是衡量算法执行时间消耗的度量，表示算法的运行时间与问题规模之间的关系。
通常用大O符号来表示时间复杂度，如O(n)、O(nlogn)等。
空间复杂度是衡量算法执行所需存储空间的度量，表示算法所需的额外空间与问题规模之间的关系。
同样也使用大O符号来表示，如O(1)、O(n)等。
6. 请简要描述以下数据结构的特点及应用场景：(1) 数组：数组是一种连续存储数据元素的线性结构，具有随机访问性能。
适用于知道元素位置的查找和修改操作。
(2) 链表：链表是一种通过指针连接的数据结构，具有插入、删除元素方便的特点。
适用于频繁插入、删除操作以及不知道具体位置的查找操作。
一．判断题（下列各题，正确的请在前面的括号内打√；错误的打×）第1章（√）（1）数据的逻辑结构与数据元素本身的内容和形式无关。
（√）（2）一个数据结构是由一个逻辑结构和这个逻辑结构上的一个基本运算集构成的整体。
（×）（3）数据元素是数据的最小单位。
（×）（4）数据项是数据的基本单位。
（×）（5）数据的逻辑结构和数据的存储结构是相同的。
（√）（6）数据的逻辑结构是各数据元素之间的逻辑关系，是用户按使用需要而建立的。
（√）（7）数据的物理结构是指数据在计算机内实际的存储形式。
（√）（8）从逻辑关系上讲，数据结构主要分为线性结构和非线性结构两类。
（√）（9）数据的存储结构是数据的逻辑结构的存储映像。
（√）（10）算法是对解题方法和步骤的描述。
第2章（×）（1）链表的物理存储结构具有同链表一样的顺序。
（×）（2）链表的每个结点都恰好包含一个指针域。
（√）（3）线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此属于同一数据对象。
（×）（4）链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动地将后续的各个单元向前移动。
（×）（5）顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。
（√）（6）数组元素的存储位置是下标的线性函数。
（√）（7）在单链表中，元素的存储位置用指针联系，所以可以从头结点开始查找任何一个元素。
（×）（8）顺序存储线性表的插入和删除操作不需要付出很大的代价，因为平均每次移动仅一半的元素。
（×）（9）顺序存储方式的优点是存储密度大，插入、删除效率高。
（×）（10）在单链表中，要取得某个元素，只要知道该元素的指针即可，因此单链表是随机存取的存储结构。
第3章（√）（1）大多数排序算法都有比较关键字大小和改变指向记录的指针或移动记录本身两种基本操作。
（×）（2）快速排序在任何情况下都比其它排序方法速度快。
（√）（3）快速排序算法在每一趟排序中都能找到一个元素放在其最终位置上。
（×）（4）如果某种排序算法不稳定，则该排序方法就没有实际应用价值。
（√）（5）对n个记录的进行快速排序，所需要的平均时间是O（nlog2n）。
（×）（6）冒泡排序是不稳定的排序。
（√）（7）冒泡排序的时间复杂度是O（n2）。
（×）（8）堆排序所需的时间与待排序的记录个数无关。
（√）（9）对快速排序来说，初始序列为正序或反序都是最坏情况。
（√）（10）对于n个记录的集合进行归并排序，所需的平均时间为O (nlog2n)。
第4章（√）（1）栈是运算受限制的线性表。
（√）（2）在栈空的情况下，不能作出栈操作，否则产生下溢出。
（×）（3）栈一定是顺序存储的线性结构。
（×）（4）空栈就是所有元素都为0的栈。
（×）（5）一个栈的输入序列为：A，B，C，D，可以得到输出序列：C，A，B，D。
（√）（6）一个栈的输入序列为：A，B，C，D，通过入出栈操作可以输出序列：A，B，C，D。
（×）（7）在C或C++语言中设顺序栈的长度为MAXLEN，则top=MAXLEN时表示队满。
（√）（8）链栈与顺序栈相比，其特点之一是通常不会出现栈满的情况。
（√）（9）在栈中插入或删除一个元素应遵守的“后进先出”的原则。
（√）（10）进位制的换算算法是栈的应用。
（√）（11）队列是限制在两端进行操作的线性表。
（√）（12）判断顺序队列为空的标准是头指针和尾指针均指向同一个结点。
（×）（13）在链队列做出队操作时，会改变front指针的值。
（√）（14）在循环队列中，若尾指针rear大于头指针front，其元素个数为rear- front。
（√）（15）队列是一种“先进先出”的线性表。
（×）（16）在循环链队列中无上溢出现象。
（×）（17）栈和队列都是顺序存储的线性结构。
（√）（18）栈和队列都是属于线性结构。
（×）（19）顺序队和循环队的队满和队空的判断条件是一样的。
（√）（20）在队列中插入或删除一个元素应遵守的”先进先出”的原则。
第5章（×）（1）串的长度是指串中不同字符的个数。
（×）（2）串是n个字母的有限序列。
（√）（3）空串不等于空格串。
（×）（4）如果两个串含有相同的字符，则说明它们相等。
（×）（5）如果一个串中所有的字母均在另一个串中出现，则说明前者是后者的子串。
（√）（6）串的堆分配存储是一种动态存储结构。
（×）（7）“DT”是“DA TA”的子串。
（×）（8）空串与空格串是相同的。
（×）（9）串中任意个字符组成的子序列称为该串的子串。
（√）（10）子串的定位运算称为模式匹配。
（√）（11）n维的多维数组可以视为n-1维数组元素组成的线性结构。
（√）（12）稀疏矩阵中非零元素的个数远小于矩阵元素的总数。
（ㄨ）（13）若采用三元组压缩技术存储稀疏矩阵，只要把每个元素的行下标和列下标互换，就完成了对该矩阵的转置运算。
（ㄨ）（14）在稀疏矩阵的三元组表表示法中，每个三元组表示矩阵中数据元素的行号、列号和值。
（ㄨ）（15）上三角矩阵主对角线以上（不包括主对角线中的元素），均为常数C。
（√）（16）对称矩阵、三角矩阵、稀疏矩阵都可以进行压缩存储。
（ㄨ）（17）任何矩阵都可以进行压缩存储。
（√）（18）在稀疏矩阵的三元组表表示法中，每个三元组表示矩阵中非零元素的行号、列号和值。
（√）（19）数组元素可以由若干个数据项组成。
（√）(20）稀疏矩阵压缩存储就是为矩阵中非零元素分配一个存储空间。
第6章（√）（1）树结构中每个结点最多只有一个直接前驱。
（×）（2）完全二叉树一定是满二查树。
（√）（3）由树转换成二叉树，其根结点的右子树一定为空。
（√）（4）在前序遍历二叉树的序列中，任何结点的子树的所有结点都是直接跟在该结点之后。
（×）（5）用一维数组来存储二叉树时，总是以前序遍历存储结点。
（×）（6）已知二叉树的前序遍历和后序遍历并不能唯一确定这棵二叉树，因为不知道根结点是哪一个。
（√）（7）二叉树的前序遍历中，任意一个结点均处于其子女结点的前面。
（√）（8）由二叉树的前序遍历序列和中序遍历序列，可以推导出后序遍历的序列。
（√）（9）不使用递归，也可以实现二叉树的前序、中序和后序遍历。
（√）（10）在完全二叉树中，若一个结点没有左孩子，则它必然是叶子结点。
第7章（√）（1）图可以没有边，但不能没有顶点。
（×）（2）在无向图中，（V1，V2）与（V2，V1）是两条不同的边。
（×）（3）邻接表只能用于有向图的存储。
（√）（4）用邻接矩阵法存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中顶点个数有关，而与图的边数无关。
（√）（5）一个图的邻接矩阵表示是唯一的。
（×）（6）有向图不能进行广度优先遍历。
（√）（7）一个图的最小生成树是该图所有生成树中权最小的生成树。
（√）（8）存储无向图的邻接矩阵是对称的，因此只要存储邻接矩阵的上三角（或下三角）部分就可以了。
（×）（9）有向图的邻接矩阵一定是对称的。
（×）（10）一个图的深度优先遍历的序列是唯一的。
第8章（√）（1）二分查找法要求待查表的关键字值必须有序。
（√）（2）哈希法是一种将关键字转换为存储地址的存储方法。
（×）（3）在二叉排序树中，根结点的值都小于孩子结点的值。
（×）（4）对有序表而言采用二分查找总比采用顺序查找法速度快。
（√）（5）二叉排序树是一种特殊的线性表。
（√）（6）散列存储法的基本思想是由关键字的值决定数据的存储地址。
（√）（7）哈希法的查找效率主要取决于哈希表构造时选取的哈希函数和处理冲突的方法。
（√）（8）一般说来用哈希函数得到的地址，冲突不可能避免，只能尽可能减少。
（×）（9）选择好的哈希函数就可以避免冲突的发生。
（×）（10）在二叉排序树上删除一个结点时，不必移动其它结点，只要将该结点的父结点的相应的指针域置空即可。
二．填空题第1章1．数据结构是一门研究非数值计算程序设计中计算机的操作对象以及它们之间的关系和运算的学科。
2．数据的存储结构形式包括：顺序存储、链式存储、散列存储、索引存储。
3．数据结构按逻辑结构可分为两大类，它们分别是：线性结构和非线性结构。
4．一个算法的空间复杂度是指该算法所耗费的存储空间，它是该算法求解问题规模n 的函数。
5．数据结构有逻辑结构和存储结构两种结构。
6．数据的存储结构形式包括：顺序存储、链式存储、散列存储、索引存储。
7．一个算法的效率可分为时间效率和空间效率。
8．数据元素是数据的基本单位。
9．数据结构主要研究数据的逻辑结构、存储结构和算法。
11．数据的逻辑结构是独立于计算机的。
12．数据结构被定义为(D，R)，其中D是数据的有限集合，R是D上的关系的有限集合。
13．树形结构结构中的元素之间存在一对多的关系。
14．若一个算法中的语句频度之和为T（n）=125n+3nlog2n，则算法的时间复杂度为O （nlog2n）。
15．数据结构主要研究数据的逻辑结构、存储结构和算法。
第2章1．顺序表中逻辑上相邻的元素在物理位置上必须相连。
2．在单链表中要在已知结点*P之前插入一个新结点，需找到*P的直接前趋结点的地址，其查找的时间复杂度为O (n) 。
3．线性表是n个结点的有限集合。
4．链表相对于顺序表的优点有插入、删除方便；缺点是存储密度小。
5．链表相对于顺序表的优点有插入、删除方便；缺点是存储密度小。
6．顺序表相对于链表的优点是：节省存储和随机存取。
7．对于一个具有n个结点的单链表，在已知p所指结点后插入一个新结点的时间复杂度是O （1）。
8．在链表中逻辑上相邻的元素的物理位置不必相连。
9．线性表中第一个结点没有直接前趋，称为开始结点。
10．在顺序表中访问任意一个结点的时间复杂度均为O (1) 。
11．在n个结点的单链表中要删除已知结点*P，其时间复杂度为O (1) 。
12．在单链表中需知道头指针才能遍历整个链表。
13．在一个单链表中，在指针p所指向的结点之后插入指针s所指向的结点时，应执行s->next=p->next和p->next=s 操作。
14．在一个长度为n的顺序表中，如果要在第i个元素前插入一个元素，要后移n- i +1 个元素。
15．在双向链表中，每个结点都有两个指针域，它们一个指向其前趋结点，另一个指向其后继结点。
