《[2017年整理]数据结构单元自测题》由会员分享，可在线阅读，更多相关《[2017年整理]数据结构单元自测题（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) 静态链表与动态链表在元素的插入 ,删除上类似 ,不需做元素的移动 .以上错误的是 _. 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) pnextp
3、rior=pprior; 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
4、=pnext; pnextprior=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) 表中诸元素的排列顺序必
5、须是由小到大或由大到小D) 除第一个和最后一个元素外,其余每个元素都有一个且仅有一个直接前驱和直接后继11 对单链表表示法,以下说法错误的是_.A) 数据域用于存储线性表的一个数据元素B) 指针域(或链域)用于存放一个指向本结点所含数据元素的直接后继所在结点的指针C) 所有数据通过指针的链接而组织成单链表D) NULL 称为空指针,它不指向任何结点只起标志作用12 若给定有 n 个元素的向量,则建立一个有序单向链表的时间复杂度的量级是_. A) O(l) B) O(n) C) O(n2) D) O(nlog2n)13 以下说法正确的是_.A) 顺序存储方式的优点是存储密度大且插入,删除运算效率
6、高B) 链表的每个结点中都恰好包含一个指针C) 线性表的顺序存储结构优于链式存储结构D) 顺序存储结构属于静态结构而链式结构属于动态结构14 以下说法错误的是_.A) 对循环链表来说,从表中任一结点出发都能通过前后移操作扫描整个循环链表 B) 对单链表来说,只有从头结点开始才能扫描表中全部结点PS图 1.10 插入结点示意C) 双链表的特点是找结点的前驱和后继都很容易D) 对双链表来说,结点*p 的存储位置既存放在其前驱结点的后继指针域中,也存放在它的后继结点的前驱指针中15 以下说法错误的是_.A) 求表长,定位这两种运算在采用顺序存储结构时实现的效率不比采用链式存储结构时实现的效率低B)
7、顺序存储的线性表可以随机存取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)/22 便于插入和删除操作的是 _. A) 静态链表 B) 单链表 C) 顺序表 D) 双链表 E)循环链表3 从表中任一结点出发都能扫描整个表的是 _. A) 静态链表 B)
8、 单链表 C) 顺序表 D) 双链表 E)循环链表三 填空题1 在单链表中设置头结点的作用是_.2 设单链表的结点结构为(data,next),next 为指针域.已知指针 px 指向单链表中 data 为 x 的结点,指针 py 指向data 为 y 的新结点,若将结点 y 插入结点 x 之后,则需要执行以下语句:_;_.3 对于双向链表,在两个结点之间插入一个新结点时需修改的指针共有_个,单链表为_个。4 顺序存储结构使线性表中逻辑上相邻的数据元素在物理位置上也相邻.因此,这种表便于_访问,是一种_结构.5 对一个线性表分别进行遍历和逆置运算,其最好的时间复杂性量级分别为_和_.6 在一个
9、循环单链表中,表尾结点的指针域与表头指针_.7 求顺序表和单链表长度的时间复杂性的量级分别为_和_.8 在一个不带头结点的单链表中,在表头插入或删除与在其他位置插入或删除其操作过程_.9 在线性表的顺序存储中,元素之间的逻辑关系是通过_决定的;在线性表的链式存储中,元素之间的逻辑关系是通过_决定的.10 单链表表示法的基本思想是用_表示结点间的逻辑关系.四 判断题1 线性表采用链表存储时,结点和结点内部的存储空间可以是不连接的. ( )2 在具有头结点的链式存储结构中,头指针指向链表中的第一个数据结点. ()3 顺序存储的线性表可以随机存取. ( )4、在单链表中，要访问某个结点，只要知道该结
10、点的指针即可；因此，单链表是一种随机存取结构。 ( )5、在线性表的顺序存储结构中，插入和删除元素时，移动元素的个数与该元素的位置有关。 ( )6. 顺序存储结构属于静态结构，链式结构属于动态结构。 ( )五 算法设计题*2、在下列程序中，函数 difference(A,B)用于求两集合之差 C=A-B，即当且仅当 e 是 A 中的一个元素，但不是 B 中的元素时 ,e 是 C 中的一个元素。集合用有序链表实现，用一个空链表表示一个空集合，表示非空集合的链表根据元素之值按递增排列。执行 C=A-B 之后，表示集合 A 和 B 的链表不变，若结果集合 C 非空，则表示它的链表根据元素之值按递增排
11、列。函数 append()用于在链表中添加结点。#includeStruct nodeInt element;Struct node *link;Typedef 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)
12、;While( ( 1 ) )If(Aelementai+1an.五 算法设计题 1 可用一个数组 S(设大小为 MAX)作为两个堆栈的共享空间.请说明共享方法,栈满/栈空的判断条件,用 C 语言设计公用的入栈操作 push(I,x),其中 I 为 0 或 1,用于表示栈号,x 为入栈值. 2 试各举一个例子,用示意图和简要说明阐述栈和队列在程序设计中所起的作用. 3 已知 Q 是一个非空队列,S 是一个空栈。使用 C 语言编写一个算法，仅用队列和栈的 ADT 函数和少量工作变量，将队列 Q 中的所有元素逆置.栈的 ADT 函数有: makeEmpty(s:stack); 置空栈 push(s
13、:stack;value:datatype); 新元素 value 进栈pop(s:stack):datatype; 出栈,返回栈顶值isEmpty(s:stack):Boolean; 判栈空否队列的 ADT 函数有:enqueue(q:queue;value:datatype); 元素 value 进队deQueur(q:queue):datatype; 出队列,返回队头值isEmpty(q:queue):Boolean; 判队列空否4 有递归算法如下: int sum(int n) if(n=0) sum=0;else cinx;sum=sum(n-1)+x; 设初值 n=4,读入 x=4
14、,9,6,2.问:(1)若 x 为局部变量时,该函数递归结束时返回调用程序的 sum=?并画出在递归过程中栈状态的变化过程.(2)若 x 为全程变量,递归结束时返回调用程序的 sum=?5 已知 Fibonacci 数列的递归定义如下: 试写出求解 fib(n)的递归和非递归算法.fib(n)= 1)2()1(00nfibnfi第三章 串 一 单选题 1 若串 S=software,其子串的数目是_. A)8 B)37 C)36 D)92 设串长为 n,模式串长为 m, 则 KMP 算法所需的附加空间为_.A)O(m) B)O(n) C)O(n*log2m) D)O(m*n) E)其他 3 设 S 为一个长度为 n 的字符串,其中的字符各不相同,则 S 中互异的非平凡子串(非空且不同于 S 本身)的个数为_.A)2n-1 B)n2 C)(n2/2)+(n/2) D)(n2/2)+(n/2)-1 E) (n2/2)-(n/2)-1 4 字符串ababaabab的 nextval 为_. A)(0,1,0,1,0,4,1,0,1)
