数据结构第二章试题.pdf

数据结构练习题第二章答案一、选择题1. 在数据结构中，线性结构的特点是什么？A. 元素之间存在一对一的关系B. 元素之间存在一对多的关系C. 元素之间存在多对多的关系D. 元素之间存在一对一或一对多的关系答案：D2. 栈（Stack）是一种特殊的线性表，其特点是：A. 允许在表的一端进行插入和删除操作B. 允许在表的两端进行插入和删除操作C. 只能在表的两端进行插入和删除操作D. 只能在表的中间进行插入和删除操作答案：A3. 队列（Queue）与栈的主要区别在于：A. 队列是先进先出（FIFO），栈是先进后出（LIFO）B. 栈是先进先出（FIFO），队列是先进后出（LIFO）C. 队列和栈都是先进先出（FIFO）D. 队列和栈都是先进后出（LIFO）答案：A二、简答题1. 什么是链表？链表有哪些基本操作？答案：链表是一种由一系列节点组成的线性数据结构，每个节点包含数据部分和指向下一个节点的指针。

链表的基本操作包括插入节点、删除节点、查找节点和遍历链表。

2. 线性表的顺序存储结构和链式存储结构有何区别？答案：顺序存储结构使用连续的存储单元来存储数据元素，如数组。

链式存储结构不要求数据元素在存储空间中连续，每个元素包含指向下一个元素的指针，如链表。

三、编程题1. 编写一个函数，实现在单链表中插入一个新节点到指定位置。

```c#include <stdio.h>#include <stdlib.h>typedef struct Node {int data;struct Node *next;} Node;Node* createNode(int data) {Node *newNode = (Node*)malloc(sizeof(Node));newNode->data = data;newNode->next = NULL;return newNode;}void insertNode(Node head, int position, int data) {Node *newNode = createNode(data);if (position == 0) {newNode->next = *head;*head = newNode;} else {Node *current = *head;for (int i = 0; current != NULL && i < position - 1; i++) {current = current->next;}if (current == NULL) return; // Position is greater than the number of nodesnewNode->next = current->next;current->next = newNode;}}int main() {Node *head = NULL;insertNode(&head, 0, 10);insertNode(&head, 1, 20);// Print the list to verify the insertionNode *current = head;while (current != NULL) {printf("%d ", current->data);current = current->next;}return 0;}```四、分析题1. 分析栈的后进先出（LIFO）特性在实际应用中的优势和局限性。

第2章线性表一选择题1．下述哪一条是顺序存储结构的优点？（）【北方交通大学 2001 一、4（2分）】A．存储密度大 B．插入运算方便 C．删除运算方便 D．可方便地用于各种逻辑结构的存储表示2．下面关于线性表的叙述中，错误的是哪一个？（）【北方交通大学 2001 一、14（2分）】A．线性表采用顺序存储，必须占用一片连续的存储单元。

B．线性表采用顺序存储，便于进行插入和删除操作。

C．线性表采用链接存储，不必占用一片连续的存储单元。

D．线性表采用链接存储，便于插入和删除操作。

3．线性表是具有n个（）的有限序列（n>0）。

【清华大学 1998 一、4（2分）】A．表元素 B．字符 C．数据元素 D．数据项 E．信息项4．若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（）存储方式最节省时间。

【哈尔滨工业大学 2001二、1（2分）】A．顺序表 B．双链表 C．带头结点的双循环链表 D．单循环链表5．某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（）存储方式最节省运算时间。

【南开大学 2000 一、3】A．单链表 B．仅有头指针的单循环链表 C．双链表 D．仅有尾指针的单循环链表6．设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用( )最节省时间。

A. 单链表B.单循环链表C. 带尾指针的单循环链表D.带头结点的双循环链表【合肥工业大学 2000 一、1（2分）】7．若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点。

则采用（）存储方式最节省运算时间。

【北京理工大学 2000一、1（2分）】A．单链表 B．双链表 C．单循环链表 D．带头结点的双循环链表8. 静态链表中指针表示的是（）. 【北京理工大学 2001 六、2（2分）】A．内存地址 B．数组下标 C．下一元素地址 D．左、右孩子地址9. 链表不具有的特点是（）【福州大学 1998 一、8 (2分)】A．插入、删除不需要移动元素 B．可随机访问任一元素C．不必事先估计存储空间 D．所需空间与线性长度成正比10. 下面的叙述不正确的是（）【南京理工大学 1996 一、10（2分）】A．线性表在链式存储时，查找第i个元素的时间同i的值成正比B. 线性表在链式存储时，查找第i个元素的时间同i的值无关C. 线性表在顺序存储时，查找第i个元素的时间同i 的值成正比D. 线性表在顺序存储时，查找第i个元素的时间同i的值无关11. 线性表的表元存储方式有(（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.线性结构的特点是只有一个结点没有前驱，只有一个结点没有后继，其余的结点只有一个前驱和后继。

第2章线性表部分答案解释如下。

1、头结点并不“仅起”标识作用，并且使操作统一。

另外，头结点数据域可写入链表长度，或作监视哨。

4．两种存储结构各有优缺点，应根据实际情况选用，不能笼统说哪一个好。

7．集合中元素无逻辑关系。

9．非空线性表第一个元素无前驱，最后一个元素无后继。

13．线性表是逻辑结构，可以顺序存储，也可链式存储。

三．填空题1．顺序 2．（n-1）/2 3．py->next=px->next; px->next=py4 ．n-i+15．主要是使插入和删除等操作统一，在第一个元素之前插入元素和删除第一个结点不必另作判断。

另外，不论链表是否为空，链表指针不变。

6．O(1)，O(n) 7．单链表，多重链表，（动态）链表，静态链表8．f->next=p->next; f->prior=p; p->next->prior=f; p->next=f;9．p^.prior s^.prior^.next10．指针 11．物理上相邻指针 12．4 213．从任一结点出发都可访问到链表中每一个元素。

14．u=p->next; p->next=u->next; free(u); 15．L->next->next==L 16．p->next!=null17．L->next==L && L->prior==L 18．s->next=p->next;p->next=s; 19．(1) IF pa=NIL THEN return(true);(2) pb<>NIL AND pa^.data>=pb^.data(3) return(inclusion(pa,pb));(4) pb:=pb^.next;(5) return(false);非递归算法：(1)pre:=pb; (2) pa<>NIL AND pb<>NIL AND pb^.data>=pa^.data (3)pa:=pa^.next; pb:=pb->next;(4)pb:=pre^.next;pre:=pb;pa:=pa^.next;(5)IF pa=NIL THEN return(true) ELSE return(false);[注]：本题是在链表上求模式匹配问题。

数据结构-试卷二及答案一、判断（每小题 1 分，共 10 分） 1．数据的存储结构是数据的逻辑结构的存储映象，不仅要存储数据元素的值，还要存储元素之间的相互关系。

2．用顺序表来存储线性表时，不需要另外开辟空间来保存数据元素之间的相互关系。

3．完全二叉树的叶子结点只能出现在最后一层上。

4．折半查找方法要求待查表必须是有序的顺序表。

5．在有向图 G 中， V 2 ， V 1 和 V 1 ， V 2 是两条不同的边。

6．图的最小生成树是唯一的。

7．从循环单链表的某一结点出发，只能找到它的后继结点，不能找到它的前趋结点。

8．在单链表中，头结点是必不可少的。

9．对快速排序来说，初始序列为正序和反序，都是最坏情况。

10．广义表是特殊的线性表。

二、选择（每题 1 分，共 15 分） 1．设栈 S 和队列 Q 的初始状态均为空，元素 abcdefg 依次进入栈 S 。

若每个元素出栈后立即进入队列 Q ，且 7 个元素出队的顺序是bdcfeag ，则栈 S 的容量至少是（）。

A．1 B．2 C．3 D．4 2．下列线索二叉树1/ 8中（用虚线表示线索），符合后序线索树定义的是( )。

3．已知广义表 A= （（ a,b ） ,(c,d) ） , 则 head(A) 等于 ( )。

A．(a,b) B．((a,b)) C．a,b D．a 4．设字符串s1=‘ABCDEFG’,s2=‘PQRST’, 则运算s=strcat(strsub(s1,2,strlen(s2)),strsub (s1,strlen(s2),2))后结果为（）。

A．BCQR B．BCDEF C．BCDEFG D．BCDEFEF 5．具有 8 个顶点的连通图的深度优先生成树，其边数为（）。

A．8 B．9 C．7 D．6 6．算法分析的两个主要方面是（）。

A．空间复杂性和时间复杂性 B．正确性和简明性 C．可读性和文档性 D．数据复杂性和程序复杂性 7．下列四种排序中（）的空间复杂度最大。

一、选择题1. 线性表是具有n个（）的有限序列。

A．数据项 B. 数据元素 C. 数据对象 D.表记录2. 以下关于线性表的说法不正确的是（）。

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. 一个长度为n的线性表顺序存储，向第i个元素（1<=i<=n+1）之前插入一个新元素时，需要从后向前依次后移（）个元素。

A．n-i B. n-i+1 C. n-i-1 D. i8.（）运算，使用顺序表比链式表好。

A. 插入B. 删除C. 根据序号查找D. 根据元素值查找9.向具有n个结点的有序单链表中插入一个新的结点并仍然有序的时间复杂度是（）。

A.O(1)B.O(n)C.O(n2)D.O(㏒2n)10.在一个长度为n的顺序存储的线性表中，删除第i个元素（1<=i<=n）时，需要从前向后依次前移（）个元素。

A．n-i B.n-i+1 C.n-i-1 D.i11.在一个长度为n的线性表中顺序查找值为x的元素时，平均查找长度（即x 同元素的平均比较次数，假定查找每个元素的概率都相等）为（）。

第二章线性表一、选择题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-9章全数据结构(第二版)习题库章节练习题1-9章全第一章：引论引论部分为数据结构的开篇，主要介绍了数据结构的基本概念和分类。

在这一章中，我们学习了数据结构的定义、作用以及与算法的关系。

接下来，将为你详细介绍第一章的习题内容。

1. 习题1-1题目：请简述数据结构的定义和作用。

要求：通过一段简洁清晰的语言来回答问题，并给出你的理解。

答案：数据结构是计算机中存储、组织和管理数据的方式。

它旨在将数据以特定的方式进行排列，以便高效地进行存储和检索。

数据结构作为计算机科学的基础，为我们解决实际问题提供了有效的工具和方法。

2. 习题1-2题目：你认为数据结构与算法之间的关系是什么？要求：结合实际案例，详细解释数据结构与算法之间的相互依赖关系。

答案：数据结构和算法是密不可分的，它们之间存在着相互依赖的关系。

数据结构提供了算法操作的基础，而算法则对数据结构进行操作和处理。

例如，在搜索算法中，我们需要合适的数据结构来存储和组织数据，以便能够高效地进行搜索操作。

而无论是数组、链表还是树，都需要通过算法来进行增删改查等操作。

第二章：算法分析算法分析是数据结构中的重要概念，它涉及到算法的运行时间和空间效率。

在这一章中，我们将学习算法分析的基本方法和常用技巧，并通过习题来巩固所学知识。

3. 习题2-1题目：请解释渐进记号中的"O"表示什么意思。

要求：简明扼要地回答问题，并辅以例子说明。

答案：在算法分析中，"O"表示渐进上界。

它描述了算法在最坏情况下的运行时间复杂度。

例如，如果一个算法的时间复杂度为O(n)，那么说明该算法的运行时间与输入规模n成正比。

即使输入规模变大，算法的运行时间也不会超过n的某个常数倍。

4. 习题2-2题目：请说明算法的平均情况分析与最坏情况分析有何区别？要求：用简洁的语言说明两种分析方法的不同之处，并给出具体的示例。

答案：算法的平均情况分析和最坏情况分析的区别在于对输入数据的预先假设。

《数据结构（C语言版第2版）》（严蔚敏著）第二章练习题答案第2章线性表1．选择题（1）顺序表中第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（）。

A．110 B．108 C．100 D．120答案：B解释：顺序表中的数据连续存储，所以第5个元素的地址为：100+2*4=108。

（2）在n个结点的顺序表中，算法的时间复杂度是O(1)的操作是（）。

A．访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n）B．在第i个结点后插入一个新结点（1≤i≤n）C．删除第i个结点（1≤i≤n）D．将n个结点从小到大排序答案：A解释：在顺序表中插入一个结点的时间复杂度都是O(n2)，排序的时间复杂度为O(n2)或O(nlog2n)。

顺序表是一种随机存取结构，访问第i个结点和求第i个结点的直接前驱都可以直接通过数组的下标直接定位，时间复杂度是O(1)。

（3）向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动的元素个数为（）。

A．8 B．63.5 C．63 D．7答案：B解释：平均要移动的元素个数为：n/2。

（4）链接存储的存储结构所占存储空间（）。

A．分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针B．只有一部分，存放结点值C．只有一部分，存储表示结点间关系的指针D．分两部分，一部分存放结点值，另一部分存放结点所占单元数答案：A（5）线性表若采用链式存储结构时，要求内存中可用存储单元的地址（）。

A．必须是连续的B．部分地址必须是连续的C．一定是不连续的D．连续或不连续都可以答案：D（6）线性表Ｌ在（）情况下适用于使用链式结构实现。

A．需经常修改Ｌ中的结点值Ｂ．需不断对Ｌ进行删除插入C．Ｌ中含有大量的结点Ｄ．Ｌ中结点结构复杂答案：B解释：链表最大的优点在于插入和删除时不需要移动数据，直接修改指针即可。

（7）单链表的存储密度（）。

A．大于1 B．等于1 C．小于1 D．不能确定答案：C解释：存储密度是指一个结点数据本身所占的存储空间和整个结点所占的存储空间之比，假设单链表一个结点本身所占的空间为D，指针域所占的空间为N，则存储密度为：D/(D+N)，一定小于1。

第二章习题1.描述以下三个概念的区别：头指针，头结点，首元素结点。

2.填空：（1）在顺序表中插入或删除一个元素，需要平均移动元素，具体移动的元素个数与有关。

（2）在顺序表中，逻辑上相邻的元素，其物理位置相邻。

在单链表中，逻辑上相邻的元素，其物理位置相邻。

（3）在带头结点的非空单链表中，头结点的存储位置由指示，首元素结点的存储位置由指示，除首元素结点外，其它任一元素结点的存储位置由指示。

3．已知L是无表头结点的单链表，且P结点既不是首元素结点，也不是尾元素结点。

按要求从下列语句中选择合适的语句序列。

a. 在P结点后插入S结点的语句序列是：。

b. 在P结点前插入S结点的语句序列是：。

c. 在表首插入S结点的语句序列是：。

d. 在表尾插入S结点的语句序列是：。

供选择的语句有：（1）P->next=S;（2）P->next= P->next->next;（3）P->next= S->next;（4）S->next= P->next;（5）S->next= L;（6）S->next= NULL;（7）Q= P;（8）while(P->next!=Q) P=P->next;（9）while(P->next!=NULL) P=P->next;（10）P= Q;（11）P= L;（12）L= S;（13）L= P;4.设线性表存于a(1:arrsize)的前elenum个分量中且递增有序。

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

5.写一算法，从顺序表中删除自第i个元素开始的k个元素。

6.已知线性表中的元素（整数）以值递增有序排列，并以单链表作存储结构。

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

第2章线性表一、选择题1.链表不具备的特点是（）。

A．可随机访问任意结点B.插入删除不需要移动元素C.不必事先估计存储空间D.所需空间与其长度成正比2.不带头结点的单链表head为空的判定条件是（）。

==NULLB. head->next==NULL >next==head!=NULL3.带头结点的单链表head为空的判定条件是（）。

==NULLB. head->next==NULL >next==head!=NULL4．带头结点的双循环链表L为空表的条件是（）。

A．L==NULL B．L->next->==NULL C．L->prior==NULL >next==L5.非空的循环链表head的尾结点（由P所指向）满足（）。

A．p->next==NULL B．p==NULL C．p->next==head ==head6.在循环双链表的p所指结点之前插入s所指结点的操作是（）。

A．p->prior=s;s->next=p;p->prior->next=s;s->prior=p->prior;B．p->prior=s;p->prior->next=s;s->next=p;s->prior=p->prior;C．s->next=p;s->prior=p->prior;p->prior=s;p->right->next=s;D. s->next=p;s->prior=p->prior;p->prior->next=s;p->prior=s;7.若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点，则采用（）存储方式最节省运算时间。

A．单链表B．给出表头指针的单循环链表C．双链表D.带头结点的双循环链表8.某线性表最常用的操作是在最后一个结点之后插入一个节点或删除第一个结点，故采用（）存储方式最节省运算时间。

（A ）需经常修改L 中的结点值 （E ）需不断对L 进行删除插入第二部分线性表、选择题1 •关于顺序存储的叙述中，哪一条是不正确的 （B ）A. 存储密度大B. 逻辑上相邻的结点物理上不必邻接C. 可以通过计算直接确定第i 个结点的位置D. 插入、删除操作不方便2.长度为n 的单链表连接在长度为 m 的单链表后的算法的时间复杂度为（C ）A 0（ n ）B 0（1）C 0（m ）D 0（m+n ）3 .在n 个结点的顺序表中，算法的时间复杂度是0（1）的操作是：（A ）A 访问第i 个结点（1<=i<=n ）和求第i 个结点的直接前趋（2<=i<=n)B 在第i 个结点（1<=i<=n ）后插入一个新结点C 删除第i 个结点（1<=i<=n)D 将n 个结点从小到大排序4.一个向量第一个兀素的存储地址是100 ,每个兀素的长度为 2 ,则第5 个兀素的地址是(B )( A ) 110 ( B ) 108 (C ) 100 ( D ) 1205 .已知一个顺序存储的线性表， 设每个结点需要占 m 个存储单元，若第一个结点的地址为 da ,则第i 个结点的地址为：（A ）7 .链表是一种采用（ B ）存储结构存储的线性表。

（A ）顺序 （B ）链式 （C ）星式 （D ）网状8 .线性表若采用链式存储结构时，要求内存中可用存储单兀的地址：（D ）（A ）必须是连续的 （B ）部分地址必须是连续的 （C ）一定是不连续的（D ）连续或不连续都可以9 .线性表L 在_ （ B ）情况下适用于使用链式结构实现。

A ） da+（i-1）*mB ） da+i*m6.在具有n 个结点的单链表中，实现（A ）遍历链表和求链表的第i 个结点C ）删除开始结点 C ） da-i*mD ） da+（i+1）*mA ）的操作，其算法的时间复杂度为 0（n ）。

B ）在地址为p 的结点之后插入一个结点D ） 删除地址为p 的结点的后继结点10．在长度为n 的顺序表的第i(1 < i < n+1)个位置上插入一个兀素，兀素的移动次数为( A )A.n-i+1B.n-iC.iD.i-1．线性表是( A )。

第二章线性表一．名词解释1.线性结构2。

数据结构的顺序实现 3.顺序表4。

链表5。

数据结构的链接实现6。

建表7.字符串8.串9.顺序串10。

链串二、填空题1。

为了便于讨论,有时将含n（n>=0)个结点的线性结构表示成(a1,a2，……a n），其中每个a i代表一个______。

a1称为______结点，a n称为______结点,i称为a i在线性表中的________或______。

对任意一对相邻结点a i、a i┼1(1<=i<n)，a i称为a i┼1的直接______a i┼1称为a i的直接______。

2.为了满足运算的封闭性,通常允许一种逻辑结构出现不含任何结点的情况.不含任何结点的线性结构记为______或______。

3.线性结构的基本特征是:若至少含有一个结点,则除起始结点没有直接______外,其他结点有且仅有一个直接______；除终端结点没有直接______外，其它结点有且仅有一个直接______。

4.所有结点按1对1的邻接关系构成的整体就是______结构.5.线性表的逻辑结构是______结构。

其所含结点的个数称为线性表的______，简称______。

6.表长为O的线性表称为______7.线性表典型的基本运算包括:______、______、______、______、______、______等六种。

8.顺序表的特点是______.9.顺序表的类型定义可经编译转换为机器级。

假定每个datatype类型的变量占用k（k〉=1)个内存单元,其中，b是顺序表的第一个存储结点的第一个单元的内存地址，那么,第i个结点a i的存储地址为______。

10.以下为顺序表的插入运算,分析算法，请在______处填上正确的语句.Void insert_sqlist(sqlist L，datatype x,int i)/＊将X插入到顺序表L的第i—1个位置＊/{ if（st == maxsize) error(“表满"）；if((i〈1）|｜(i〉st+1））error（“非法位置"）;for（j=st;j〉=i;j—-)______；L.data［i—1]=x;L。

一、判断题四．串1、确定串Ｔ在串Ｓ中首次出现的位置的操作称为串的模式匹配。

（）2、如果一个串中的所有字符均在另一串中出现，则说前者是后者的子串。

（）3、一个任意串是其自身的子串。

（）1、∨2、Χ3、∨五．数组和广义表1、多维数组是向量的推广。

（）/*数组和广义表线性表在含义上的扩展*/2、用相邻矩阵表示图所用的存储空间大小与图的边数成正比。

（）/*顶点*/3、除插入和删除操作外，数组的主要操作还有存取、修改、检索和排序等。

（）4、稀疏矩阵中0元素的分布有规律，因此可以采用三元组方法进行压缩存储。

（）/*稀疏矩阵中0元素的分布无规律*/5. 如果采用如下方式定义一维字符数组：const int maxSize = 30;/*常变量在程序运行中不能进行修改*/char a[maxSize];则这种数组在程序执行过程中不能扩充。

6. 如果采用如下方法定义一维字符数组：int maxSize = 30;char * a = new char[maxSize];则这种数组在程序执行过程中不能扩充。

7. 数组是一种静态的存储空间分配，就是说，在程序设计时必须预先定义数组的数据类型和存储空间大小，由编译程序在编译时进行分配。

/*对于数组一旦规定了它的维数和各维长度，便可为它分配存储空间*/8. 多维数组是一种复杂的数据结构，数组元素之间的关系既不是线性的也不是树形的。

9. 使用三元组表示稀疏矩阵中的非零元素能节省存储空间。

10. 用字符数组存储长度为n的字符串，数组长度至少为n+1。

1-5ΧΧΧΧ∨6-10ΧΧ∨∨∨11、一个广义表的深度是指该广义表展开后所含括号的层数。

（）12. 一个广义表的表头总是一个广义表。

( )13. 一个广义表的表尾总是一个表。

( )14. 一个广义表 ( (a), ( (b), c), ( ( (d) ) ) ) 的长度为3，深度为4。

( )15. 一个广义表 ( (a), ( (b), c), ( ( (d) ) ) ) 的表尾是（ ( (b), c), ( ( (d) ) )）。

第二章线性表一、单项选择题1.顺序存储结构的特点是（ B ）。

A. 只能实现顺序存取元素的操作B. 逻辑上相邻的数据元素在存储地址上也一定相邻C. 逻辑上相邻的数据元素在存储地址上一定不相邻D. 逻辑上相邻的数据元素在存储地址上不一定相邻2.若某链表中最常用的操作是在最后一个元素之后插入一个元素和删除最后一个元素，则采用（ C ）最节省时间。

A. 单链表B. 双链表C. 带头结点的双循环链表D. 单循环链表3.与线性表的顺序存储不相符的特性是（ A ）。

A. 插入和删除操作灵活B. 需要连续存储空间C. 便于随机访问D. 存储密度大4.与线性表的链接存储不相符合的特性是（ C）。

A. 便于插入、删除运算B. 存储空间动态分配C. 需要连续的存储空间D. 只能顺序查找5.链表不具有的特点是（ B）。

A. 插入、删除不需要移动元素B. 可随机访问任一元素C. 不必事先估计存储空间D. 所需空间与线性长度成正比6.循环链表h的尾结点p的特点是（ D ）。

A.p==h->nextB. p->next== h->nextC.p==hD. p->next==h7.在一个单链表中，已知q所指向的结点是p所指向结点的前驱结点，若在q和p 之间插入s所指向的结点，则执行（ C ）。

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;8.设一个有序的顺序表中有n个结点，现要求插入一个新结点后使得顺序表仍然保持有序，则该操作的平均时间复杂度为（D ）。

A. O(log2n)B. O(1)C. O(n2)D. O(n)9.对于一个线性表，若要求既能够进行较快地插入和删除，又能够反映出数据元素之间的关系，则应该（ A）。

数据结构第二章参考答案习题21. 填空题〔1〕在一个单链表中，每个结点包含data和next两个域，q所指结点是p 所指结点的直接前驱，假设在q和p之间插入s所指结点，那么执行〔___________〕和〔___________〕操作。

答案：q->next = s; s->next = p; 或 s->next=q->next; q->next = s; 〔2〕表长为n的顺序表，当在任何位置上插入或删除一个元素的概率相等时，插入一个元素所需移动元素的平均个数为〔___________〕，删除一个元素需要移动元素的平均个数为〔___________〕。

答案：n/2 (n-1)/2〔3〕表长为0的线性表称为〔___________〕。

答案：空表〔4〕动态内存管理是操作系统的根本功能之一，其作用是响应用户程序对内存的〔___________〕和〔___________〕请求。

答案：申请释放〔5〕顺序表多采用〔___________〕实现的，是一种随机存取结构，对表中任意结点存取操作的时间复杂度为〔___________〕。

而查找链表中的结节，需要从头指针起顺着链扫描才能得到，平均时间复杂度为〔___________〕。

因此，假设线性表的操作主要是进行查找，很少进行插入或删除操作时，采用〔___________〕表比拟适宜。

答案：数组 O(1) O(n) 顺序〔6〕在链表某个位置上进行插入和删除操作，只需要修改〔___________〕即可，而无须移动大量元素，操作的时间复杂度为〔___________〕。

而在顺序表中进行插入和删除操作，往往要移动大量元素，平均移动元素的数目为〔___________〕，平均时间复杂度为〔___________〕。

因此，假设对线性表进行频繁的插入和删除操作时，采用〔___________〕表相对适宜。

假设插入和删除主要发生在表头和表尾，那么采用〔___________〕表更为适宜。

数据结构样卷一．判断题（15分）1．（0 ）线性表的各种基本操作在顺序存储结构上的实现均比在链式存储结构上的实现效率要低。

2．（0 ）一个有向图的邻接表和逆邻接表中表结点的个数一定相等。

3．（1 ）先序遍历森林和先序遍历与该森林相对应的二叉树，其结果不同。

4．（1 ）不使用递归，也可实现二叉树的先序、中序和后序遍历。

5．（1 ）散列法存储的基本思想是由关键字的值决定数据的存储地址。

6．（1 ）采用折半查找法对有序表进行查找总是比采用顺序查找法对其进行查找要快。

7．（0 ）在任何情况下，快速排序方法的时间性能总是最优的。

8. （ 0 ）二维数组是其数据元素为线性表的线性表。

9.（0 ）拓扑排序是一种内部排序方法。

10．（0 ）数据的物理结构是指数据在计算机内实际的存储形式。

二．单选题（每个选择项2分，共20分）1. 单循环链表的主要优点是( D )。

A.不再需要头指针B.已知某个结点的位置后，能够容易找到它的直接前趋C.在进行插入，删除运算时，能更好地保证链表不断开D.从表中任一结点出发都能扫描到整个链表2. 若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用( D )存储方式最节省时间。

A．顺序表B．单链表C．双链表D．单循环链表3. 在Hash函数H (k) = k MOD m 中，一般来讲，m应取( C )。

A．奇数B．偶数C．素数D．充分大的数4. 图的深度优先遍历算法类似于二叉树的( A )，广度优先遍历算法类似于二叉树的( D )。

A．先序遍历B．中序遍历C．后序遍历D．层次遍历5. 对树而言，不合适的遍历方法是( D )。

A．先序遍历B．中序遍历C．后序遍历D．层次遍历6. 若广义表A满足Head(A)==Tail(A)，则A为( B )。

A. ( )B. (( ))C. (( ),( ))D. (( ),( ),( ))7. 下列二叉树中，( A )可用于实现符号的不等长高效编码。