1 绪论 绪论单元测验
1、 在链接存储结构中，要求 。
答案: 每个结点占用一片连续的存储区域
2、 对于数据结构的描述，下列说法中不正确的是 。
答案: 相同的逻辑结构对应的存储结构也必须相同
3、 以下关于链接存储结构的叙述中， 是不正确的。
答案: 可以通过计算得到第i个节点的存储地址
4、 可以用 、数据关系和基本操作定义一个完整的抽象数据类型。
答案: 数据元素
5、 算法指得是 。
答案: 对特定问题求解步骤的一种描述，是指令的有限序列
6、 下面 不是算法所必须具备的特性。
答案: 高效性
7、 某算法的时间复杂度是O(n^2)，表明该算法 。
答案: 执行时间与n^2成正比
8、 设某算法完成对n个元素进行处理，所需的时间是T(n)=100nlgn+200n+500，则该算法的时间复杂度是 。
答案: O(nlgn)
9、 算法的时间复杂度属于一种 。
答案: 事前分析估算的方法
2 线性表 线性表单元测验
1、 将两个各有n个元素的有序顺序表归并成一个有序顺序表，其最少的比较次数是 。
答案: n
2、 在长度为n的线性表中查找值为x的数据元素的时间复杂度为 。
答案: O(n)
3、 线性表的顺序存储结构是一种 的存储结构。
答案: 随机存取
4、 设线性表中有2n个元素，以下操作中， 在单链表上实现要比在顺序表上实现效率更高。
答案: 删除指定的元素
5、 如果最常用的操作是取第i个节点及其前驱，则采用 存储方式最节省时间。
答案: 顺序表
6、 与单链表相比，双链表的优点之一是 。
答案: 访问前后相邻结点更灵活
7、 带头结点的单链表L为空的判定条件是 。
答案: L->next==NULL
8、 在一个单链表中，已知q所指结点是p所指结点的直接前驱，若在q和p之间插入s所指结点，则执行 操作。
答案: q->next=s ; s->next=p;
9、 设指针rear指向带头结点的循环单链表的尾结点，若要删除链表的第一个元素结点，正确的操作是 。
答案: s=rear->next->next ; rear->next->next=s->next;
10、 经过以下栈运算后，x的值是 。InitStack(s);Push(s,a);Push(s,b);Pop(s,x);GetTop(s.x);
答案: a
11、 一个栈的进栈a,b,c,d,e则栈的不可能的输出序列是 。
答案: dceab
12、 已知一个栈的进栈序列是ABC，出栈序列是CBA，经过的栈操作是 。
答案: push,push,push,pop,pop,pop
答案: st.top==-1
14、 链栈与顺序栈相比有一个明显的优点，即 。
答案: 通常不会出现栈满的情况
15、 设环形队列中数组的下标是0～N-1，其头、尾指针分别为f和r，则其元素个数为 。
答案: (r-f+N)%N
16、 对于链队，在进行删除操作时， 。
答案: 头、尾指针可能都要修改
17、 对于含有n个字符的链串s，查找元素值为x的算法时间复杂度为 。
答案: O(n)
18、 已知t=”abcaabbcabcaabdab”，该模式串的特征数组值为 。
答案: 0,0,0,1,1,2,0,0,1,2,3,4,5,6,0,1,2
19、 一个线性表最常用的操作是存取任意指定序号的元素和最后进行插入删除操作，则利用（）存储方式可以节省时间。
答案: 顺序表
20、 在一个长度为n的顺序表中删除第i个元素（1≤i≤n）时，需向前移动（）个元素。
答案: n-i
21、 对于顺序表，访问第i个位置的元素和第i个位置插入一个元素的时间复杂度为（）
答案: O（1），O（n）
22、 单链表中，增加一个头结点的目的是（）
答案: 方便运算实现
23、 设链表不带头结点且所有操作均在表头进行，则下列最不适合链栈的是（）
答案: 只有表头结点指针，没有表尾指针的单向循环链表
24、 3个不同元素依次进栈，能得到（）种不同的出栈序列
答案: 5
25、 两个串相等必有串长度相等且 。
答案: 串中各位置字符均对应相等
26、 已知字符串S为”abaabaabacacaabaabcc”, 模式串t为”abaabc”。采用KMP算法进行匹配，笫一次出现匹配失败时，i=j=5, 则下次开始匹配时，i和j的值分别是
答案: i=5,j=2
