《数据结构》练习题（1~4章）

 

 

第一部分 选择题

1、             数据的基本单位，即数据集合中的个体。

A．数据对象    B.数据元素    C.数据项     D.数据结构

2、  线性表采用链式存储时，其地址

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

3、若一个序列的进栈顺序为1，2，3，4，那么       是一个对应的出栈序列

A. 3，2，1，4   B.4，2，3，1    C 4，3，2，1，    D. 1，2，3，4

4、  线性表是      

A. 一个有限序列，可以为空            B. 一个有限序列，不能为空

C. 一个无限序列，可以为空            D. 一个无限序列，不能为空

5、  若一个栈的输入序列是1，2，3，…….n，输出序列的第一个元素是n,则第i个输出元素是       

A.  n-i        B. n-i+1      C. i       D. 不确定

6、  队列操作的原则是        

A. 先进先出     B. 后进先出      C. 只能进行插入     D. 只能进行删除

7、链表不具有的特点是         

A. 随机访问                               B. 不必事先估计存储空间    

C. 插入删除时不必移动元素              D.所需要空间与线性表成正比

8、  如果以链表作为栈的存储结构，则退栈操作时

A. 必须判断栈是否为空      B. 判别栈元素的类型

C．必须判别栈是否为满      D. 对栈不性作任何判别。

9、  在一个顺序存储的循环队列中，队首指针指向队首元素的         

A. 前一个位置     B. 后一个位置    C. 队首元素位置    D. 任意位置

10、              向顺序栈中压入元素时，        

A．先移动栈顶指针，后存入元素     B. 先存入元素，后移动栈顶指针

C. 谁先谁后无关紧要                D. 同时进行

11、              用链表示线性的优点是           

A. 便于随机存取     B. 花费的存储空间比顺序表少

C. 便于插入和删除   D. 数据元素的物理顺序与逻辑顺序相同

12、              与数据元素本身的形式、内容、相对位置、个数无关的是数据的     

A. 存储结构   B. 存储实现      C. 逻辑结构     D. 运算实现

13、              链栈与顺序栈相比，有一个比较明显的优点是       

A. 插入操作更加方便          B. 通常不会出现栈满的情况

C. 不会出现栈空的情况        D. 删除操作更加方便

14、              在单链表中，增加一个头结点的目的是       

A. 使单链表至少有一结点        B. 标志表中有首结点位置

C. 方便运算的实现              D. 说明单链表是线性表的链式存储实现

15、              在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度为 

A．O(1)         B. O(n)        C. O(n²)       D. O(log₂n)

16、              在一个单链表中，若要删除p->结点的后继结点，则执行      

A. p->next=p->next->next     B. p=p->next; p->next=p->next->next

c. free(p->next)              D. p=p->next->next

17、              在数据结构中，从逻辑上可以把数据分成             

A. 动态结构和静态结构         B. 紧凑结构和非紧凑结构

C．线性结构和非线性结构       D. 内部结构和外部结构

18、              下述哪一条是顺序存储方式的优点？

A. 存储密度大                 B. 插入方便

C. 删除方便                   D. 可方便用于各种逻辑结构的存储表示

19、在具有n个单元顺序存储的循环队列中，队满时共有元素        个。

A. n+1    B  n-1     C. n     D. n-2

20、下列关于线性表的叙述中，正确的是           

A. 性表中的元素之间是线性关系   B. 线性表中至少有一个元素

C. 线性表中任何一个元素有且仅有一个直接前趋。

D. 线性表中任何一个元素有且仅有一个直接后继。

21、对于一个栈，给定输入序列1，2，3，则下列不可能为输出序列的是        

A. 1,2,3       B.  3,2,1     C. 3,1,2    D. 2,1,3

22、在线性表的下列存储结构中，读取元素花费时间最少的是_________-

A、单链表    B、双链表    C、循环链表     D、顺序表

23、在单链表中，若*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;

24、设一个栈的输入序列为A、B、C、D，则借助一个栈得到的输出序列不可能的是_______

A、 ABCD        B、DCBA     C、ACDB      D、DABC

25、数组A[0..5,0..6]的每个元素占5个单元，将其按列优先次序存储在起始地址为1000的连续内存单元中，则元素a[5][5]的地址为________

A、 1175     B、 1180     C、 1205    D、1210

26、设有一个10阶的对称矩阵A，a[0][0]为第一元素，其存储地址为d,每个元素点1个存储单元，则元素a[8][5]的存储地址为_________

A、 d+41     B、 d+40       C、d+42     D、d+43

 

 

第二部分 判断题

1、  顺序存储方式的优点是存储密度大，且插入和删除运算效率高（ 错  ）

2、  循环队列中无上溢现象    （ 错   ）

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

4、  栈和队列都是运算受限的线性表，只允许在表的两端进行运算。   （ 错  ）

5、  数据元素是数据的最小单位。  （ 错   ）

6、  顺序存储的线性表可以随机存储。  （ 对    ）

7、线性表采用顺序存储，必须占用一片连续的存储单元。  （ 对   ）

8、算法和程序没有区别，在数据结构中二者是通用的。   （ 错  ）

9、顺序存储结构方式只能用于存储线性结构。  （ 错  ）

10、线性表的链式存储结构优于顺序存储结构。   （ 错   ）

11、线性表的链接存储，表中元素的逻辑顺序与物理顺序一定相同。（错  ）

12、由于顺序存储要求连续的存储区域，所以在存储管理上不够灵活。 （错 ）

13、循环队列只有下溢，没有上溢。    （ 错  ）

14、如果单链表带有头结点，则插入操作永远不会改变头结点指针的值。（对   ）

15、在循环单链表中，任何一个结点的指针字段值都不可能为空。（  对  ）

16、空栈没有栈顶指针。  （   错   ）

17、无论是顺序队列还是链接队列，插入、删除运算的时间复杂度都是O（1） 。（对）

18、在表示稀疏矩阵的三元组顺序表中，各元素的排列顺序与矩阵元素值的大小有关 （错  ）

19、线性表可以看成是广义表的特例，如果广义表中的每个元素都是单元素，则广义表便成为线性表。（  对   ）

20、稀疏矩阵的特点是矩阵中元素较少。  （   错  ）

第三部分 填空题

1、q[1..maxsize]为一个顺序存储的栈，变量top指示栈顶元素的位置。作进栈操作时必须判别    栈满          。如果要把栈顶元素取到x中，需执行下列语句：  q[++top]=x     。

2、带有表头结点的双链表L中，指针P所指结点是第一个结点的条件是    L-->next==p       。

3、数据结构的三个要素是  逻辑结构     、   存储结构        、   操作       。

4、单链表中引入头结点的作用是     为了方便操作                                         。

5、算法的主要特性有：有穷性、  确定性   、  可行性    、输入和输出。

6、设循环队列存放在向量sq.data[0…m]中，队头指针sq.front在循环意义下的加1操作可用模运算表示为  (sq.front+1)%(m+1)         ；若用牺牲一个单元的办法来区分队满和队空的条件，则队满条件可以表示为  (sq.rear+1)%(m+1)==sq.front           。

8、可以仅由一个尾指针来唯一确定，即从尾指针出发能访问到链表上任何一个结点的链表有  双向链表           和    循环链表          。

9、单链表中，指针p所指结点为最后一个结点的条件是   p-->next==NULL          。

10、数据的逻辑结构包括  线性结构     、  树型结构      和  图型结构      三种类型。

11、对于长度为n的线性表A[1..n]，插入和删除一个元素的时间复杂度为     O（n)    。

12、用二元组（D，R）来表示数据结构，那么D指   数据的集合       ，R指  这些数据之间的关系的集合           。

13、一条语句重复执行的次数称为 频度       

14、栈的运算主要有入栈、   出栈     、取栈顶元素、 判断栈空    、  销毁栈     等几种。

15、在带头结点的单链表L中，第一个元素结点的指针为   L-->next       。

16、为了最快的存取某元素，数据结构宜用 顺序存储    结构；为了方便插入一个元素，宜用  链接存储    结构。

17、带头结点的双链表为空的条件是 head-->next==NULL             。

18、在进栈运算时，应先判别栈是否为   满    ；作退栈运算时，应先判别栈是否为 空   。

19、 在线性表的顺序存储中，元素之间的逻辑关系是通过_位置____决定的；在线性表的链接存储中，元素之间的逻辑关系是通过_指针____决定的。

20、顺序队列在实现的时候，通常将数组看成是一个首尾相连的环，这样做的目的是为了避免产生__假溢出_____现象。

 

 

第四部分 应用题

1、  指出头指针、头结点、首结点三个概念的区别。

 

 

 

 

 

2、  在单链表和双向链表中，能否从当前结点出发访问到任一结点？

 

 

 

3、已知两个4X5的稀疏矩阵的三无组表分别为

1	4	16
2	2	18
3	4	-25
4	2	28

 

1	1	32
2	2	-22
2	5	69
3	4	25
4	2	51

 

请画出这两个稀疏矩阵之和三元组表。

 

 

 

 

 

 

 

3、  已知L1和L2分别指向两个单链表的头结点，且已知其长度分别为m和n,试写一算法将两个链表链表在一起，并请分析算法的时间复杂度。