数据结构单元自测题

第一章 线性表 一 单选题

1 线性表是具有n个____的有限序列。 A) 表元素 B) 字符 C) 数据元素 D) 数据项 E)信息项

**2 线性表的静态链表存储结构与顺序存储结构相比优点是_____。 A) 所有的操作算法实现简单 B) 便于随机存储 C) 便于插入和删除 D) 便于利用零散的存储器空间 3 若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素算法的时间复杂度为____。

2

A) O(n ) B ) O(l) C) O(n) D) O(n)

**4 (1) 静态链表既有顺序存储的优点，又有动态链表的优点。所以，它存取表中第i个元素的时间与i无关; (2) 静态链表中能容纳元素个数的最大数在定义是就确定了,以后不能增加; (3) 静态链表与动态链表在元素的插入,删除上类似,不需做元素的移动. 以上错误的是_____. A) (1),(2) B) (1) C) (1),(2),(3) D) (2) P 5 将图1.10所示的s所指结点加到p所指结点之后,其语句应为____.

A) s?next=p+1; p?next=s; B) (*p).next=s; (*s).next=(*p).next; C) s?next=p?next; p?next=s?next; D) s?next=p?next; p?next=s; S 6 在双向链表存储结构中,删除p所指的结点时须修改指针______

图1.10插入结点示意

A) p?next?prior=p?prior; p?prior?next=p?next; B) p?next=p?next?next; p?next?prior=p;. C) p?prior?next=p; p?prior=p?prior?prior; D) p?prior=p?next?next; p?next=p?prior?prior;

7在双向循环链表中,在p指针所指的结点后插入一个指针q所指向的新结点,其修改指针的操作是____. A) p?next=q; q?prior=p; p?next?prior=q; q?next=q;

B) p?next=q; p?next?prior=q; q?prior=p; q?next=p?next;

C) q?prior=p; q?next=p?next; p?next?prior=q; p?next=q; D) q?next=p?next; q?prior=p; p?next=q; p?next=q;

8 将两个各有n个元素的有序表归并成一个有序表,其最少的比较次数是____. A) n B) 2n-1 C)2n D) n-1

9 在一个长度为n的顺序表中,在第i个元素(l≤i≤n+1)之前插入一个新元素时须向后移动___个元素. A) n –1 B ).n-i+1 C)n-i-1 D) .i

10 线性表L=(a1 ,a2,…an),下列说法正确的是____.

A) 每个元素都有一个直接前驱和一个直接后继 B) 线性表中至少有一个元素

C) 表中诸元素的排列顺序必须是由小到大或由大到小

D) 除第一个和最后一个元素外,其余每个元素都有一个且仅有一个直接前驱和直接后继 11 对单链表表示法,以下说法错误的是_____. A) 数据域用于存储线性表的一个数据元素

B) 指针域(或链域)用于存放一个指向本结点所含数据元素的直接后继所在结点的指针

C) 所有数据通过指针的链接而组织成单链表

D) NULL称为空指针,它不指向任何结点只起标志作用

12 若给定有n个元素的向量,则建立一个有序单向链表的时间复杂度的量级是____. A) O(l) B) O(n) C)

2)

O(n D) O(nlog2n)

13 以下说法正确的是____.

A) 顺序存储方式的优点是存储密度大且插入,删除运算效率高 B) 链表的每个结点中都恰好包含一个指针 C) 线性表的顺序存储结构优于链式存储结构

D) 顺序存储结构属于静态结构而链式结构属于动态结构 14 以下说法错误的是____.

A) 对循环链表来说,从表中任一结点出发都能通过前后移操作扫描整个循环链表 B) 对单链表来说,只有从头结点开始才能扫描表中全部结点

C) 双链表的特点是找结点的前驱和后继都很容易

D) 对双链表来说,结点*p的存储位置既存放在其前驱结点的后继指针域中,也存放在它的后继结点的前驱指针

中

15以下说法错误的是____.

A) 求表长,定位这两种运算在采用顺序存储结构时实现的效率不比采用链式存储结构时实现的效率低 B) 顺序存储的线性表可以随机存取

C) 由于顺序存储要求连续的存储区域,所以在存储管理上不够灵活 D) 线性表的链式存储结构优于顺序存储结构

**二 多选题 1 表长为n的顺序存储的线性表,当在任何位置上插入或删除一个元素的概率相等时,插入一个元素所需移动的元素平均个数为____,删除一个元素所需移动的平均个数为____. A) (n-1)/2 B) n C) n+1 D) n-1 E) n/2 F) (n+1)/2 G) (n-2)/2 2 便于插入和删除操作的是____. A) 静态链表 B) 单链表 C) 顺序表 D) 双链表 E)循环链表 3 从表中任一结点出发都能扫描整个表的是____. A) 静态链表 B) 单链表 C) 顺序表 D) 双链表 E)循环链表

三 填空题

1 在单链表中设置头结点的作用是____.

2 设单链表的结点结构为(data,next),next为指针域.已知指针px指向单链表中data为x的结点,指针py指向data为y的新结点,若将结点y插入结点x之后,则需要执行以下语句:________;_________. 3 对于双向链表,在两个结点之间插入一个新结点时需修改的指针共有____个,单链表为____个。

4 顺序存储结构使线性表中逻辑上相邻的数据元素在物理位置上也相邻.因此,这种表便于_____访问,是一种_____结构.

5 对一个线性表分别进行遍历和逆置运算,其最好的时间复杂性量级分别为____和____. 6 在一个循环单链表中,表尾结点的指针域与表头指针_____.

7 求顺序表和单链表长度的时间复杂性的量级分别为_____和_____.

8 在一个不带头结点的单链表中,在表头插入或删除与在其他位置插入或删除其操作过程_____.

9 在线性表的顺序存储中,元素之间的逻辑关系是通过___决定的;在线性表的链式存储中,元素之间的逻辑关系是通过____决定的.

10 单链表表示法的基本思想是用______表示结点间的逻辑关系.

四 判断题

1 线性表采用链表存储时,结点和结点内部的存储空间可以是不连接的. ( ) 2 在具有头结点的链式存储结构中,头指针指向链表中的第一个数据结点. ( ) 3 顺序存储的线性表可以随机存取. ( )

4、在单链表中，要访问某个结点，只要知道该结点的指针即可；因此，单链表是一种随机存取结构。 ( ) 5、在线性表的顺序存储结构中，插入和删除元素时，移动元素的个数与该元素的位置有关。 ( ) 6. 顺序存储结构属于静态结构，链式结构属于动态结构。 ( )

五 算法设计题

**2、在下列程序中，函数difference(A,B)用于求两集合之差C=A-B，即当且仅当e是A中的一个元素，但不是B中的元素时,e是C中的一个元素。集合用有序链表实现，用一个空链表表示一个空集合，表示非空集合的链表根据元素之值按递增排列。执行C=A-B之后，表示集合A和B的链表不变，若结果集合C非空，则表示它的链表根据元素之值按递增排列。函数append()用于在链表中添加结点。 #include Struct node{ Int element; Struct node *link; } Typedef struct node NODE; NODE *A,*B,*C; NODE *append(last,e); NODE *last; Int e; {Last?link=(NODE*)malloc(sizeof(NODE)); last?link?element=e; return(last?link); } NODE *difference(A,B) NODE *A,*B; {NODE *C,*last; C=last=(NODE*)malloc(sizeof(NODE)); While( ( 1 ) ) If(A?element

llink data rlink 5 给定(已生成)一个带头结点的单链表,设head为头指针,结点的结构为(data,next),data为整数元素,next为指针.试写出算法:按递增次序输出单链表中各结点的数据元素并释放结点所占的存储空间.(要求:不允许使用数组作辅助空间).

第二章 栈和队列

一 单选题

1 若用单链表表示队列，则应该选用______.

A) 带尾指针的非循环链表 B) 带尾指针的循环链表 C) 带头指针的非循环链表 D) 带头指针的循环链表 2 若用一个大小为6的数组来实现循环队列，且当rear和front的植分别为0和3.当从队列中删除一个元素,再加入两个元素后,rear和front的值分别为多少? A)1和5 B)2和4 C)4和2 D)5和1

3 设栈的输入序列为1,2,3,…,n,输出序列为a1,a2,….,an,若存在l≤k≤n使得ak=n,则当k≤i≤n时,ai为_____. A)n-i +1 B)n-( i-k) C)不确定

4 设栈的输入序列是(1,2,3,4),则____不可能是其出栈序列. A)1243 B)2134 C)1432 D)4312 E)3214 5 设栈S和队列Q的初始状态为空,元素e1,e2,e3,e4,e5和e6依次通过栈S,一个元素出栈后即进入队列Q,若6个

元素出队的序列是e2,e4,e3,e6,e5,e1,则栈S的容量至少应该是_____. A )6 B)4 C)3 D)2

6 一般情况下,将递归算法转换成等价的非递归算法应该设置_____ A)堆栈 B)队列 C)堆栈或队列 D)

数组

7 已知一算术表达式的中缀形式为A+B*C-D/E,后缀形式为ABC*+DE/-,其前缀形式为_____. A)-A+B*C/DE B)-A+B*CD/E C)-+*ABC/DE D)-+A*BC/DE

8 设栈的输入序列为1,2,…,n,若输出序列的第一个元素是n,则第i个输出元素是_____. A)不确定

B)n-i+1 C)i D)n-i

** 9 已知输入序列为,经过输出受限的双向队列后能得到的输出序列有____. A)dacb B)cadb C)dbca D)bdac E)以上答案都不对 ** 10 如图2.10所示的循环队列中元素数目是____.其中tail=32指向队尾元素,head=15指向队头元素的前一个空位置,队列空间m=60. A)42 B)16 C)17 D)41 tail 12345 30 输出端 输入端 head 15 45 栈S 0

图2.11 栈S示意

图2.10 循环队列

11假定一个顺序循环队列的队首和队尾指针分别用front和rear表示,则判队空的条件是______. A)front+1==rear B)front==rear+1 C)front==0 D)front==rear

12 假定一个顺序循环队列存储于数组A[n]中,其队首和队尾指针分别用front和rear表示,则判断队满的条件是____.

A)(rear-1)%n==front B)(rear+1)%n==front C)rear==(front-1)%n D)rear==(front+1)%n

** 二 多选题 1 依次读入数据元素序列(a,b,c,d,e,f,g)进栈,每进一个元素,机器可要求下一个元素进栈或出栈;如此进行,则栈空时弹出的元素构成的序列是以下哪些序列? A)(d,e,c,f,b,g,a) B)(f,e,g,d,a,c,b) C)(e,f,d,g,b,c,a) D)(c,d,b,e,f,a,g) 2 循环队列是____. A)顺序存储结构 B)不会产生下溢 C)不会产生上溢 D)队满时rear==front E)不会产生假溢 3 一个输入序列abcd经过一个栈到达输出序列,并且一旦离开输入序列后就不能再返回到输入序列,则下面____为正确的输出序列. A)bcad B)cbda C)dabc D)acbd E)dcba 4 已知输入序列为1234,则输入受限(仅由一端输入)但输出不受限(两端均可输出)的双端队列不可以得到____为输出序列.