《数据结构单元自测题》由会员分享，可在线阅读，更多相关《数据结构单元自测题（28页珍藏版）》请在金锄头文库上搜索。
1、第一章 线性表一 单选题1 线性表是具有n个_的有限序列。 A) 表元素 B) 字符 C) 数据元素 D) 数据项 E)信息项*2 线性表的静态链表存储结构与顺序存储结构相比优点是_。 A) 所有的操作算法实现简单 B) 便于随机存储 C) 便于插入和删除 D) 便于利用零散的存储器空间3 若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素算法的时间复杂度为_。 A) O(n ) B ) O(l) C) O(n) D) O(n2)*4 (1) 静态链表既有顺序存储的优点，又有动态链表的优点。所以，它存取表中第i个元素的时间与i无关;(2) 静态链表中能容纳元素个数的最大数在定义是
2、就确定了,以后不能增加;(3) 静态链表与动态链表在元素的插入,删除上类似,不需做元素的移动.PS图1.10插入结点示意 以上错误的是_. A) (1),(2) B) (1) C) (1),(2),(3) D) (2)5 将图1.10所示的s所指结点加到p所指结点之后,其语句应为_.A) snext=p+1; pnext=s; B) (*p).next=s; (*s).next=(*p).next; C) snext=pnext; pnext=snext; D) snext=pnext; pnext=s;6 在双向链表存储结构中,删除p所指的结点时须修改指针_A) pnextprior=ppr
3、ior; ppriornext=pnext;B) pnext=pnextnext; pnextprior=p;.C) ppriornext=p; pprior=ppriorprior;D) pprior=pnextnext; pnext=ppriorprior;7在双向循环链表中,在p指针所指的结点后插入一个指针q所指向的新结点,其修改指针的操作是_.A) pnext=q; qprior=p; pnextprior=q; qnext=q;B) pnext=q; pnextprior=q; qprior=p; qnext=pnext; C) qprior=p; qnext=pnext; pnex
4、tprior=q; pnext=q; D) qnext=pnext; qprior=p; pnext=q; pnext=q;8 将两个各有n个元素的有序表归并成一个有序表,其最少的比较次数是_. A) n B) 2n-1 C)2n D) n-19 在一个长度为n的顺序表中,在第i个元素(lin+1)之前插入一个新元素时须向后移动_个元素. A) n 1 B ).n-i+1 C)n-i-1 D) .i10 线性表L=(a1 ,a2,an),下列说法正确的是_.A) 每个元素都有一个直接前驱和一个直接后继 B) 线性表中至少有一个元素 C) 表中诸元素的排列顺序必须是由小到大或由大到小D) 除第一
5、个和最后一个元素外,其余每个元素都有一个且仅有一个直接前驱和直接后继11 对单链表表示法,以下说法错误的是_.A) 数据域用于存储线性表的一个数据元素 B) 指针域(或链域)用于存放一个指向本结点所含数据元素的直接后继所在结点的指针 C) 所有数据通过指针的链接而组织成单链表 D) NULL称为空指针,它不指向任何结点只起标志作用12 若给定有n个元素的向量,则建立一个有序单向链表的时间复杂度的量级是_.A) O(l) B) O(n) C) O(n2) D) O(nlog2n) 13 以下说法正确的是_.A) 顺序存储方式的优点是存储密度大且插入,删除运算效率高B) 链表的每个结点中都恰好包含
6、一个指针C) 线性表的顺序存储结构优于链式存储结构D) 顺序存储结构属于静态结构而链式结构属于动态结构14 以下说法错误的是_.A) 对循环链表来说,从表中任一结点出发都能通过前后移操作扫描整个循环链表 B) 对单链表来说,只有从头结点开始才能扫描表中全部结点C) 双链表的特点是找结点的前驱和后继都很容易D) 对双链表来说,结点*p的存储位置既存放在其前驱结点的后继指针域中,也存放在它的后继结点的前驱指针中15以下说法错误的是_.A) 求表长,定位这两种运算在采用顺序存储结构时实现的效率不比采用链式存储结构时实现的效率低B) 顺序存储的线性表可以随机存取C) 由于顺序存储要求连续的存储区域,所
7、以在存储管理上不够灵活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)/22 便于插入和删除操作的是_. A) 静态链表B) 单链表 C) 顺序表 D) 双链表 E)循环链表3 从表中任一结点出发都能扫描整个表的是_. A) 静态链表B) 单链表 C) 顺序表 D) 双链表 E)循环链表三 填空题1 在单链表中设置头结点的作
8、用是_.2 设单链表的结点结构为(data,next),next为指针域.已知指针px指向单链表中data为x的结点,指针py指向data为y的新结点,若将结点y插入结点x之后,则需要执行以下语句:_;_.3 对于双向链表,在两个结点之间插入一个新结点时需修改的指针共有_个,单链表为_个。4 顺序存储结构使线性表中逻辑上相邻的数据元素在物理位置上也相邻.因此,这种表便于_访问,是一种_结构.5 对一个线性表分别进行遍历和逆置运算,其最好的时间复杂性量级分别为_和_.6 在一个循环单链表中,表尾结点的指针域与表头指针_.7 求顺序表和单链表长度的时间复杂性的量级分别为_和_.8 在一个不带头结点
9、的单链表中,在表头插入或删除与在其他位置插入或删除其操作过程_.9 在线性表的顺序存储中,元素之间的逻辑关系是通过_决定的;在线性表的链式存储中,元素之间的逻辑关系是通过_决定的.10 单链表表示法的基本思想是用_表示结点间的逻辑关系.四 判断题1 线性表采用链表存储时,结点和结点内部的存储空间可以是不连接的. ( )2 在具有头结点的链式存储结构中,头指针指向链表中的第一个数据结点. ()3 顺序存储的线性表可以随机存取. ( )4、在单链表中，要访问某个结点，只要知道该结点的指针即可；因此，单链表是一种随机存取结构。 ( )5、在线性表的顺序存储结构中，插入和删除元素时，移动元素的个数与该
10、元素的位置有关。 ( )6. 顺序存储结构属于静态结构，链式结构属于动态结构。 ( )五 算法设计题*2、在下列程序中，函数difference(A,B)用于求两集合之差C=A-B，即当且仅当e是A中的一个元素，但不是B中的元素时,e是C中的一个元素。集合用有序链表实现，用一个空链表表示一个空集合，表示非空集合的链表根据元素之值按递增排列。执行C=A-B之后，表示集合A和B的链表不变，若结果集合C非空，则表示它的链表根据元素之值按递增排列。函数append()用于在链表中添加结点。#includeStruct nodeInt element;Struct node *link; Typedef
11、 struct node NODE;NODE *A,*B,*C;NODE *append(last,e);NODE *last;Int e;Lastlink=(NODE*)malloc(sizeof(NODE); lastlinkelement=e; return(lastlink); NODE *difference(A,B)NODE *A,*B;NODE *C,*last; C=last=(NODE*)malloc(sizeof(NODE); While( ( 1 ) ) If(AelementBelement); last=append(last,Aelement); A=Alink;
12、else if( ( 2 ) ) A=Alink; B=Blink; else( 3 );while( ( 4 ) )last=append(last,Aelement); A=Alink; ( 5 );last=C;C=Clink;Free(last);Return( C );/*call from:C=difference(A,B); */4 双向链表的结点形式为：删除此链表中由指针p所指的结点的主要两步操作是：(1)_; (2)_.llink data rlink 5 给定(已生成)一个带头结点的单链表,设head为头指针,结点的结构为(data,next),data为整数元素,next
13、为指针.试写出算法:按递增次序输出单链表中各结点的数据元素并释放结点所占的存储空间.(要求:不允许使用数组作辅助空间).第二章 栈和队列 一 单选题1 若用单链表表示队列，则应该选用_.A) 带尾指针的非循环链表 B) 带尾指针的循环链表 C) 带头指针的非循环链表 D) 带头指针的循环链表2 若用一个大小为6的数组来实现循环队列，且当rear和front的植分别为0和3.当从队列中删除一个元素,再加入两个元素后,rear和front的值分别为多少? A)1和5 B)2和4 C)4和2 D)5和13 设栈的输入序列为1,2,3,n,输出序列为a1,a2,.,an,若存在lkn使得ak=n,则当kin时,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
