当前位置：文档之家 › 数据结构练习题

数据结构练习题

  • 格式：pdf
  • 大小：384.73 KB
  • 文档页数：6

下载文档原格式

  / 6

合集下载

数据结构练习题

数据结构练习题

. . . . .一、单选题第1章绪论1、在数据结构中，从逻辑上可以把数据结构分成A、动态结构和静态结构C、线性结构和非线性结构2、算法分析的两个主要方面是A、空间复杂性和时间复杂性C、可读性和文档性3、数据的不可分割的最小单位是B、紧凑结构和非紧凑结构D、内部结构和外部结构B、正确性和简明性D、数据复杂性和程序复杂性A、结点B、数据元素C、数据项D、数据对象4、在任何问题中，数据元素都不是孤立存在的，而是在它们之间存在着某种关系，这种数据元素相互之间的关系称为A、规则B、集合C、结构D、运算5、与程序运行时间有关的因素主要有以下四方面，其中与算法关系密切的是A、问题的规模C、机器执行速度二、判断题1、数据结构是带有结构的数据元素的集合。

2、程序越短，运行的时间就越少。

3、处理同一问题的算法是唯一的。

B、机器代码质量的优劣D、语句的执行次数4、一个完整算法可以没有输入，但必须有输出。

三、填空题1、______________是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。

2、______________结构的数据元素之间存在一对多的关系。

3、数据结构的形式化定义为(D，S)，其中D 是______________的有限集，S 是 D 上关系的有限集。

4、数据结构在计算机中的______________称为存储结构。

5、数据元素之间的关系在计算机中有两种不同的表示方法：顺序映象和非顺序映象，由此- 1 -得到两种不同的存储结构是______________存储结构和______________存储结构。

6、一个算法具有五个特性：______________、______________、______________、有零个或多个输入、有一个或多个输出。

7、评价一个算法的好坏应该从算法的正确性、可读性、___________和_________________等几方面进行。

四、解答题1、设n 为正整数。

数据结构练习(附答案)

数据结构练习(附答案)

习题一绪论.1.1 单项选择题1. 数据结构是一门研究非数值计算的程序设计问题中计算机的① A 以及它们之间的② B 和运算等的学科。

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

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

A．动态结构和静态结构Ｂ．紧凑结构和非紧凑结构Ｃ．线性结构和非线性结构Ｄ．内部结构和外部结构4. 线性表的顺序存储结构是一种① A 的存储结构，线性表的链式存储结构是一种② B 的存储结构。

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

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

①A. 计算方法 B. 排序方法C. 解决问题的有限运算序列D. 调度方法②A. 可行性、可移植性和可扩充性 B. 可行性、确定性和有穷性C. 确定性、有穷性和稳定性D. 易读性、稳定性和安全性7. 线性表的逻辑顺序与存储顺序总是一致的，这种说法 B 。

A. 正确B. 不正确8. 线性表若采用链式存储结构时，要求内存中可用存储单元的地址 D 。

A. 必须是连续的B. 部分地址必须是连续的C. 一定是不连续的D. 连续或不连续都可以9. 在以下的叙述中，正确的是 B 。

A.线性表的线性存储结构优于链表存储结构B.二维数组是其数据元素为线性表的线性表C.栈的操作方式是先进先出D.队列的操作方式和先进后出10. 每种数据结构都具备三个基本运算：插入、删除和查找，这种说法 B 。

数据结构 练习题

数据结构 练习题
A）10 B）110 C）1110 D）1111
6. 已知一棵二叉树的先序遍历序列为EFHIGJK，中序遍历序列为HFIEJGK，则该二叉树根的右子树的根是
A）E B）F C）G D）J
7. 设结点A有左孩子结点B，右孩子结点C，则在先序遍历、中序遍历、后序遍历这三种基本遍历序列中B一定是C的
图6-2 例6.3附图
6 自测习题
1. 简答题
1. *根据权值（1，2，3，4，5，6），构造哈夫曼树，并计算二叉树的带权路径长度。
2. 请
将下图6-1所示的森林转换成二叉树。
图6-1 简答题2的附图森林
3. *已知一棵二叉树的中序遍历序列为DHBEAIFCGJK，该二叉树的后序遍历序列是HDEBIFJKGCA，现请画出这棵二叉树。
第1章 概述
一、简答题
1．简述以下术语的含义并说明它们之间的关系。
数据类型、数据结构、逻辑结构、存储结构
2．简述算法时间效率和空间效率的概念。
3．简述数据结构课程的目的和意义。
二、选择题
1．以下数据结构中，逻辑结构属于线性结构的是
A）有向图 B）链式栈 C）二叉树 D）二叉排序树
四、算法及分析
1．写出交换两个整型变量值的算法，并分析算法的时间复杂度。
2．写出求n的阶乘 的算法，并分析算法的时间复杂度。
第2章 线性表
一、简答题
1．在处理某个问题时，需要存储的数据总量不能确定，并经常需要进行数据的添加和删除操作，此时应选用哪种存储结构？为什么？
3．设有结点定义
struct node
{ int data;
struct node *next;

数据结构(含答案)

数据结构(含答案)

数据结构综合练习一、选择题1．数据的存储结构包括顺序、链接、散列和（）4种基本类型。

A索引B数组C集合D向量2．下面程序的时间复杂性的量级为（）。

int i=0，s1=0，s2=0；while（i++<n）{if (i%2)s1+=i;…else s2+=i;}(1) (1bn) （n）(2n)3．下面程序段的时间复杂度为（）。

for(int i=0;i<m;i++)for(int j=0;j<n;j++)a[i][j]=i*j;(m2) (n2) (m+n) (m*n)4．在一个长度为n的顺序存储结构的线性表中，向第i个元素（1≤i≤n+1）位置插入一个元素时，需要从后向前依次后移（）个元素。

+l<5．在一个长度为n的顺序存储结构的线性表中，删除第i个元素（1≤i≤n+1）时，需要从前向后依次后移（）个元素。

+l6．在一个长度为n的线性表中，删除值为x的元素时需要比较元素和移动元素的总次数为（）。

A.(n+1)/2 2 +17．在一个顺序表中的任何位置插入一个元素的时间复杂度为（）。

A. O(n)B. O(n/2)C. O(1)D. O(n2)8. 线性表的链式存储比顺序存储更有利于进行（）操作。

A.查找B.表尾插入和删除C.按值插入和删除D.表头的插入和删除…9. 线性表的顺序存储比链式存储更有利于进行（）操作。

A.查找B.表尾插入和删除C.按值插入和删除D.表头的插入和删除10. 在一个表头指针为ph的单链表中，若要向表头插入一个由指针p指向的结点，则应执行（）操作。

A. ph=p; p->next=ph;B. p->next=ph; ph=p;C. p->next=ph; p=ph;D. p->next=ph->next; ph->next=p;11. 在一个表头指针为ph的单链表中，若要在指针q所指结点的后面插入一个由指针p所指向的结点，则执行（）操作。

数据结构练习题

数据结构练习题

1．顺序存储结构中数据元素之间的逻辑关系是由（存储位置）表示的。

2．若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（顺序表）存储方式最节省时间。

3. 执行下面程序段时，语句S的执行次数为(n+1)(n+2)/24 对于线性表最常用的操作是查找指定序号的元素和在末尾插入元素，则选择（顺序表）存储方式最节省时间。

5．在长度为n的顺序表的第i个位置上插入一个元素（1≤ i ≤n+1），元素的移动次数为：n – i + 16．非空的单循环链表由头指针head指示，p 指针指向链尾结点的条件是（p->next==head）。

7．下列选项中，（可以随机访问表中的任意元素）是链表不具有的特点。

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

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

9．栈和队列的共同点是（只允许在端点处插入和删除元素）10．一个队列的入队序列是a,b,c,d，则该队列的出队序列是（a,b,c,d）。

11.带头结点的单链表h为空的判断条件是（h->next== NULL）。

12. 下面关于串的叙述中，哪一个是不正确的？（空串是由空格构成的串）13．判断一个最大容量为m的循环队列Q为空的条件是（Q->front==Q->rear）。

14．在一棵树中，每个节点最多有（1）前驱节点？15．已知完全二叉树的第7层有10个叶子结点，则整个二叉树中结点数为（73）。

16. 下面的说法中，不正确的是（稀疏矩阵中大量值为零的元素分布有规律，因此可以采用三元组表方法存储）17．在一棵深度为k的满二叉树中，结点总数为（2k-1）18．数组A中，每个元素的长度为3个字节，行下标从1到5，列下标从1到6，从首地址SA开始连续存放在存储器内，存放该数组至少需要的字节数是（90）。

19. 如果从无向图的任一顶点出发进行一次深度优先搜索即可访问所有的顶点，则该图一定是（连通图）。

数据结构练习附答案

数据结构练习附答案

一、单项选择题1.逻辑关系是指数据元素间的（）A．类型 B．存储方式 C．结构 D．数据项2.对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构为( )A．顺序表 B.用头指针表示的单循环链表C. 用尾指针表示的单循环链表D. 单链表3.设数组data[m]作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行出队操作后其头指针front值为（）A．front=front+1 B．front= (front+1)%(m-1)C．front=(front-1)%m D．front=(fro nt+1)%m4.在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队头指针和队尾指针，则判断队满的条件为( )。

A．rear％n==front B．(front+l)％n==rearC．rear％n-1==front D．(rear+l)％n==front5.在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队头指针和队尾指针，则判断队空的条件为( )。

A．rear％n==front B．front+l=rearC．rear==front D．(rear+l)％n=front6.已知一颗二叉树上有92个叶子结点，则它有____个度为2的结点。

( )A. 90B. 91C. 92D. 937.在一棵非空二叉树的中序遍历序列中，根结点的右边_____。

A. 只有右子树上的所有结点B. 只有右子树上的部分结点C. 只有左子树上的所有结点D. 只有左子树上的部分结点8.有n条边的无向图的邻接表存储法中，链表中结点的个数是( )个。

A. nB. 2nC. n/2D. n*n9.判断有向图是否存在回路，除了可利用拓扑排序方法外，还可以利用（）。

A. 求关键路径的方法B.求最短路径的方法C. 深度优先遍历算法D.广度优先遍历算法10.对线性表进行二分查找时，要求线性表必须( )。

数据结构习题及答案

习题一1. 简述下列术语：数据、数据元素、数据对象、数据结构、逻辑结构、存储结构、基本运算、运算实现和数据类型。

2. 设有数据结构(D, R）,其中D={d1,d2,d3,d4},R={r},r={ (d1, d2 ) , (d2, d3 ) , (d3, d4 ) }. 试按图论中图的画法惯例画出其逻辑结构图。

3. 函数f（M，n）按下式定义（m，n为≥0的整数）：f （m，n）=﹛m+n+1 当m*n=0时f（m-1，（m，n-1））当 m*n≠0 时（1）试写出计算该函数的递归过程；（2）写出递归过程转换成非递归过程的转换规则。

4. 把数组 A[1…n]按递减顺序排序,并分析其最坏情况时间复杂性量级。

5. 为了用计算机实现学生档案管理, 需要经过哪些主要步骤?每个步骤的主要工作是什么?试用本章讲到的从“具体到抽象”、再“从抽象到具体”的观点加以分析。

6. 试设定若干n值,比较两函数n2和50nlog2n的增长趋势,并确定n在什么范围内,函数n2值大于50nlog2n 的值。

习题二1.设线性表存于a（1：n）的前elenum个分量中,且递增有序。

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

2.写一个逆置线性表的算法。

即由A[1：n]产生B[1：n],使得B[1]=A[n],B[2]=A[n-1] , … B[n]=A[1]。

要求用最少的附加空间。

3.设有编号为 1,2,3,4 的四辆列车,顺序进入一个栈式结构的站台,试写出这四辆列车开出车站的所有可能顺序。

4. 设有六辆火车编号为1，2，3，4，5，6 利用栈,将它们重新编成3，2，5，6，4，1的顺序。

请写出操作序列，设X 表示将一列火车从栈中开出；S 表示将一列火车从输入端开入栈中。

5.假设栈中每个数据项占K 个空间位置,试改写入栈和出栈的算法。

6. 假设有两个栈如图所示共享空间 [1..m]。

试写一个对任一栈作入栈 push（s,x ，i ）和出栈pop （s,i ）。

数据结构练习题


一、填空题
1.线性表、栈和队列都是 线性 结构，可以在线性表的 任意 位置插入和删除元素；对 于栈只能在 栈顶 插入和删除元素；对于队列只能在 队尾 插入和 队头 删除元素。 2. 栈是一种特殊的线性表，允许插入和删除运算的一端称为 栈顶 。不允许插入和删除 运算的一端称为 栈底 。 3. 队列 是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算的线性 表。 4. 在一个循环队列中，队首指针指向队首元素的 当前 位置。 5. 在具有n个单元的循环队列中，队满时共有 n-1 个元素。 6. 向栈中压入元素的操作是先 插入元素 ，后 移动指针 。 7. 从循环队列中删除一个元素时，其操作是 先 读取元素 ，后 移动指针 。
数据结构
武汉大学测绘学院虞晖
1. 假设有二维数组A6×8，每个元素用相邻的6个字节存储，存储器按字节编址。已知A 的起始存储位置（基地址）为1000，则数组A的体积（存储量）为 288 ；末尾元素A57 的第一个字节地址为 1282 ；若按行存储时，元素A14的第一个字节地址为 1072 ；若按 列存储时，元素A47的第一个字节地址为 1276 。 2. 设数组a[1…60, 1…70]的基地址为2048，每个元素占2个存储单元，若以列序为主序 顺序存储，则元素a[32,58]的存储地址为 8950 。 3. 三元素组表中的每个结点对应于稀疏矩阵的一个非零元素，它包含有三个数据项，分 别表示该元素的 行下标 、 列下标 和 元素值 。
数据结构
武 汉 大 学 测 绘 学 院 虞晖
单项选择题
（ C）1．数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续 的，称之为：
（A）存储结构 （B）逻辑结构 （C）顺序存储结构 （D）链式存储结构 （ B）2. 一个表第一个元素的存储地址是100，每个元素的长度为2，则第5个元 素的地址是 （A）110 （B）108 （C）100 （D）120 （ A）3. 在n个结点的顺序表中，算法的时间复杂度是O（1）的操作是：

数据结构练习题及答案

数据结构练习题（一）一、单选题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 B.2K+1 C.2K-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个结点的无向图，该图至少应有( )条边才能确保是一个连通图。

A.5B.6C.7D.8二、填空题1.通常从四个方面评价算法的质量：_________、_________、_________和_________。

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

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

数据结构试题库及答案

数据结构试题库及答案一、选择题1. 在数据结构中，线性结构的特点是：A. 元素之间存在一对一关系B. 元素之间存在一对多关系C. 元素之间存在多对多关系D. 元素之间存在一对一或多对多关系答案：A2. 栈（Stack）是一种特殊的线性表，其特点是：A. 只能在一端进行插入和删除操作B. 可以在两端进行插入和删除操作C. 只能在一端进行插入操作，另一端进行删除操作D. 可以在任意位置进行插入和删除操作答案：A3. 在二叉树中，度为1的节点数目为2，度为0的节点数目也为2，该二叉树的节点总数是：A. 5B. 6C. 7D. 8答案：B二、简答题1. 请简述什么是哈希表，并说明其主要优点。

答案：哈希表是一种通过哈希函数将键映射到表中一个位置来访问记录的数据结构。

其主要优点包括：平均情况下，查找、插入和删除操作的时间复杂度为O(1)，即常数时间内完成操作；空间效率高，能够存储大量数据。

2. 描述图的深度优先搜索（DFS）算法的基本思想。

答案：深度优先搜索算法的基本思想是从一个顶点开始，尽可能深地搜索图的分支。

搜索过程中使用一个栈来保存路径上的顶点。

当搜索到一个顶点时，先访问该顶点，然后依次搜索其所有未被访问过的邻接顶点。

如果当前顶点的所有邻接顶点都被访问过，则回溯到上一个顶点，继续搜索其他邻接顶点。

三、应用题1. 给定一个无向图，使用邻接表表示，请编写一个算法找出图中的所有连通分量。

答案：首先，创建一个访问过的顶点集合。

然后，从图中任意一个未被访问的顶点开始，执行深度优先搜索（DFS）。

每次DFS完成后，就找到了一个连通分量。

重复这个过程，直到所有顶点都被访问过，即可找到图中的所有连通分量。

2. 假设有一个数组，需要频繁地进行查找、插入和删除操作，请设计一个适合这种场景的数据结构，并说明其优势。

答案：对于这种场景，可以使用平衡二叉搜索树（如AVL树或红黑树）。

这些数据结构可以保证在最坏情况下，查找、插入和删除操作的时间复杂度为O(log n)。

  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

后， rear 的值为 ， front 的值 为 ，当前队列的 长 度 为 。 14.设循环队列的容量为 40(序号从 0 到 39)， 现经过一系列的入队和出队运算后， 有: ① front=11，rear=19; ② front=19，rear=11； 问在这两种情况下，循环队列中各有元素多少个？ 15.写出下列程序段的输出结果(队列中的元素类型 QElem Type 为 char)。 void main( ){ Queue Q; Init Queue (Q); Char x=’e’; y=’c’; EnQueue (Q,’h’); EnQueue (Q,’r’); EnQueue (Q, y); DeQueue (Q,x); EnQueue (Q,x); DeQueue (Q,x); EnQueue (Q,’a’); while(!QueueEmpty(Q)){ DeQueue (Q,y); printf(y); }; printf(x); } 16.简述以下算法的功能(栈和队列的元素类型均为 int) void algo3(Queue &Q){ Stack S; int d; InitStack(S); while(!QueueEmpty(Q)){ DeQueue (Q,d); Push(S,d); }; while(!StackEmpty(S)){ Pop(S,d); EnQueue (Q,d); } }
第一章 绪论
1.数据结构是研究数据的( )以及它们之间的相互关系。 A.物理结构，逻辑结构 B.理想结构，抽象结构 C.理想结构，物理结构 D.抽象结构，逻辑结构 2.从逻辑上可以把数据结构分为( )两大类。 A.动态结构、静态结构 B.顺序结构、链式结构 C.线性结构、非线性结构 D.初等结构、构造型结构 3.以下不属于算法要素的是( ) A. 有穷性 B. 可行性 C. 可读性 D. 输入 4.算法的时间复杂度与( )有关。 A.问题规模 B.计算机硬件性能 C.编译程序质 D.程序设计语言 2 5.某算法的时间复杂度为 O(n )，表明该算法的( ) 2 A.问题规模是 n B.执行时间等于 n2 C.执行时间与 n2 成正比 D.问题规模与 n2 成正比 6.假设某算法语句总的执行次数为 T(n)=2n³ +n² ,那么该算法的时间复杂性量级为 ( ) A.O(2) B.O(n³ ) C.O(n² ) D.O(1) 7.设 n 为正整数，下面程序段中标号为①的语句频度为 。 int i = 1; k = 0; while ( i <= n-1 ){ k += 10*i; ① i++; } 8.程序段 for( i=0; i<n; i++ ) for( j=0; j<i; j++ ) k++; 中，语句 k++的执行次数为 。 9.在下面的程序段中，对 x 的赋值语句的渐进时间复杂度为 。 for(k=1;k<=n;k++) for(j=1;j<=n;j++) x=x+1; 10.下面程序段的时间复杂度为 。 void fun(int n) { int y=1; while (y <=n) y=2*y; }
第四章 串
1.串是一种特殊的线性表，其特殊性体现在( ) A.可以顺序存储 B.数据元素是一个字符 C.可以链式存储 D.数据元素可以是多个字符 2.若串 S=sub ，以下( )不是 S 的子串。 A.空串 B.sub C.su D.sb 3.空串的长度为( ) A.1 B.2 C.0 D. 以上都不对 4.求串 T 在串 S 中首次出现位置的基本操作叫做( ) A.求子串 B.模式匹配 C.串替换 D.串连接 5.若串 S=“software”，其子串数目是 ( ) A.8 B.37 C.36 D.9 6.设串 S = ‘I AM A WORKER!’，T = ‘GOOD’，
Concat( SubString( S, 6, 2 ), Concat( T, SubString( S, 7, 6 ) ) = 7.设 s=‘数据结构 A'，则 StrLength(s)=( )。
ห้องสมุดไป่ตู้
。
第五章 数组和广义表
1.数组 A[0…5,0…6]的每个元素占 5 个单元，将其按列优先次序存储在起始地址 为 1000 的连续内存单元中，则元素 a[5][5]的地址为( ) A.1175 B.1180 C.1205 D.1210 2. 5 行 8 列的二维数组 A(行列下标均从 0 开始)按行存储在存储器中，每个元素 占 4 个存储单元，首地址为 100，则存储地址为 184 的元素是( ) A. A[2][5] B. A[2][6] C. A[3][5] D. A[3][6] 3.设二维数组 A[5][4](行列下标从 1 开始编号)的每个元素占 4 个单元，将其按行 优先顺序存放在起始地址为 680 的连续内存单元中， 则元素 a[4][2]的地址为( ) A.728 B.732 C.736 D.740 4.空的广义表，是指广义表( ) A.深度为 0 B.尚未赋值 C.不含任何原子 D.不含任何元素 5.对于广义表((a,b),(()),(a,(b)))来说，其( ) A.长度为 4 B.深度为 4 C.有 3 个元素 D.有 2 个元素 6.广义表(e,(d,a),b)的深度为( )(a、b、d、e 是原子) A.0 B.1 C.2 D.无穷 7.广义表 L = ( ( apple, pear ), ( banana, orange ) ) 的表尾是( ) A.( apple, pear ) B.( ( apple, pear ) ) C.( banana, orange ) D.( ( banana, orange ) ) 8.在广义表((a,b),c,((d),e),(f,j,(g),(h)))中，第 4 个元素的第 3 个元素是( ) A.原子 g B.子表(g) C.原子 e D.子表((d),e) 9.广义表 A=(a,b,(c,d),(e,(f,g)))，则下面式子的值是( ) Head[tail[head[tail[tail(A)]]]] A.(g) B.(d) C.(c) D.d 10.已知广义表 L=((x,y,z),a,(u,t,w))，从 L 表中取出原子项 t 的运算是 ( ) A.Head(Tail(Tail(L))) B.Tail(Head(Head(Tail(L)))) C.Head(Tail(Head(Tail(L)))) D.Head(Tail(Head(Tail(Tail(L)))))
第二章 线性表
1.在线性表的下列存储结构中，读取指定序号的元素花费时间最少的是( ) A.单链表 B.双链表 C.循环链表 D.顺序表
2.顺序表随机访问元素 ak 基本操作的时间复杂度为( ) A. O( 1 ) B. O( n ) C. O( logn ) D. O( k ) 3.线性表采用链式存储结构时，其地址( ) A.必须是连续的 B.一定是不连续的 C.部分地址必须是连续的 D.连续与否均可 4.带头结点的单链表 h 为空的判断条件是( ) A. h=NULL B.h->next=h C. h->next=NULL D.h!=NULL 5.在表头指针为 head 且表长大于 1 的单向循环链表中，指针 p 指向表中的某个 结点，若 p->next->next= =head,则( ) A.p 指向头结点 B.*p 的直接后继是尾结点 C.p 指向尾结点 D.*p 的直接后继是头结点 6.如果线性表长度变化较大，且经常进行插入删除操作，则采用( )更合适。 A.单链表 B.有序表 C.无序表 D.顺序表 7.在顺序线性表(a1 ,a2 ,•••,a29 ,a30 )中，在 a20 之前插入一个新的结点，需要将( ) 个结点后移。 A.11 B.20 C.19 D.10 8.在不带头结点的单链表 L 中的第一个结点前插入结点 S，以下正确的是( ) A. S->next=L;L =S; B. L->next=S;S->next=L->next; C. S->next=L->next;L->next=S; D. S->next=L->next; 9.在一个单链表中，若结点不是最后结点，在 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; 10.在单链表中，删除*p 结点的后一个结点的操作是( ) A.p->next=p B.p->next->next=p->next C.p->next->next=p D.p->next=p->next->next 11.设单链表的结点结构为(data,next)，next 为指针域，已知指针 p 指向单链表中 data 为 x 的结点，指针 q 指向 data 为 y 的新结点，若将结点 y 插入结点 x 之后， 则需要执行以下语句： ； ； 12.p 是指向单链表 L 的中间结点的指针， 补充下列删除 p 的后继结点的程序段。 s = p->next; __ ____ free( s ); 13.在一个长度为 n 的顺序表的最后插入一个数据元素， 其时间复杂度为( )， 在第 i 个元素(1≤i≤n+1)之前插入一个元素时，需向后移动( )个元素。 14.循环单链表 LA 中， 指针 P 所指结点为表尾结点的条件是( )。 15.以下是双向链表中结点 s(data，prior，next)插入到结点 p 之前的插入过程，请 补充完整。 s->next =( ); ( )= s; ( )= p->proir; ( ) = s;