Description
## 一.链表
1. 以下哪个是链表的优点?
* 信息储存密度大
* 可以随机访问
* 插入,删除元素方便
* 排序效率高
2. 以下哪个不是链表的特点
* 可以随机访问
* 插入元素不必移动元素
* 删除元素不必移动元素
* 创建链表不必预估储存空间
3. 以下关于线性表的说法中，哪个是正确的？
* 链表的信息储存密度比顺序表大
* 单链表的最后一个节点没有后继
* 单链表的最后一个节点是空指针
* 顺序表中的元素没有前驱和后继
4. 以下关于线性表的说法中,哪个是错误的?
* 顺序表必须占用内存中的一片连续空间
* 链表可以占用内存中的一片连续空间
* 链表可以不占用内存中的一片连续空间
* 链表不可以占用内存中的一片连续空间
5. 设计一个线性表,需求的常用操作是删除第一个元素以及在最后一个元素后面插入元素.则4种结构中哪个最节省运算时间？
* 单链表
* 双链表
* 只有头指针的单循环链表
* 只有尾指针的单循环链表
6. 设计一个线性表,需求的常用操作是删除最后一个元素以及访问任意序号的元素.则4种结构中哪个最节省运算时间
* 顺序表
* 双链表
* 单链表
* 双循环链表
7. 设计一个线性表，需求的常用操作是删除尾元素以及在第一个元素之前插入元素。则4种结构中哪个最节省运算时间?
* 只有头指针的单循环链表
* 只有尾指针的单循环链表
* 顺序表
* 双循环链表
8. 下列说法哪个是正确的？
* 如果插入操作频繁发生在表头部，顺序表和单链表效率接近
* 如果删除操作频繁发生在表头部，顺序表比单链表效率更高
* 如果插入操作频繁发生在表尾部，顺序表比单链表效率更高
* 如果删除操作频繁发生在表尾部，顺序表和单链表效率接近
9. 如果一个线性表有n个元素，以下哪种操作单链表的效率高于顺序表
* 删除所有值为x的元素
* 打印输出前k个元素
* 交换第i个元素和第n-i-1个元素的值
* 在最后一个元素后面插入新元素
10. 循环链表的主要优点是
* 不再需要头指针了
* 已知某个节点的位置后,能够容易找到它的直接前驱
* 在进行插入,删除运算时,能更好地保证链表断开
* 从表中任意一个节点出发都能扫描到整个链表
11. 以下解析错误的是
* 头指针：指向链表第一个节点的指针
* 尾指针：指向链表最后一个节点的指针
* 循环链表：尾指针指向头指针的链表
* 双链表：节点既有前驱指针又有后继指针的链表
12. 以下哪个说法是错误的
* 头节点是链表的第一个元素
* 单链表可以没有头节点
* 双链表可以没有头节点
* 头节点的后继指针指向链表的第一个元素
13. 用head代表一个链表的头指针，以下哪个说法是错误的（判空是指判断一个链表是否为空）
* 带有头节点的单链表的判空方法是：head->next==NULL
* 不带头节点的单链表的判空方法是：head==NULL
* 带有头节点的双链表的判空方法是：head->next==head->prior
* 带有头节点的循环单链表的判空方法是：head->next==head
14. 用head代表一个链表的头指针，tail代表尾指针，以下哪种情况可以判断p是链表的最后一个元素
* 循环单链表情况中：p->next==tail
* 循环单链表中：p->next==head
* 单链表中：p==NULL
* 双链表中：p==tail->prior
15. 在一个长度为n的顺序表中,删除第m个元素的时间复杂度最少是?
* O(1)
* O(m)
* O(n+m)
* O(n-m)
16. 在一个长度为n的顺序表中,访问第m个元素的时间复杂度最少是?
* O(1)
* O(n)
* O(m)
* O(n-m)
17. 在一个长度为n的只有头指针的单链表中,访问第m个元素的时间复杂度最少是?
* O(n)
* O(m)
* O(n-m)
* min( O(m) , O(n-m) )
18. 在一个长度为n的只有头指针的单链表中,删除第m个元素的时间复杂度最少是?
* O(n-m)
* O(m)
* O(1)
* O(n)
19. 建立一个长度为n的单链表，时间复杂度最少是？
* O(1)
* O(n)
* O(2\*n)
* O(n^2)
20. 清空一个长度为n的单链表，时间复杂度最少是？
* O(1)
* O(n)
* O(2\*n)
* O(n^2)
21. 某单链表用next表示后继指针，将s节点插入到p节点后面应该如何操作？
* p->next=s;s->next=p->next;
* s->next=p->nexr;p->next=s;
* p->next->next=s;s->next=p;
* s->next=p->next->next;p->next=s;
22. 某单链表带有头节点,用head表示头指针,删除该链表的第一个元素应该如何操作?
* p=head;head->next=head->next->next;delect p;
* p=head->next;head->next=head->next->next;delect p;
* p=head;head=head->next;delect p;
* p=head->next;head=p;delect p;
23. 某单链表用next表示后继指针,删除p节点后面的元素应该如何操作?
* s=p->next;p->next=p->next->next;delect p;
* s=p->next;p->next->next=p->next;delect s;
* s=p->next;p->next=p->next->next;delect s;
* s=p;p->next->next=s->next;delect p->next;
24. 某双链表用next表示后继指针,prior表示前驱指针,把s节点插入到p节点的后面应该如何操作?
* p->next->prior=s;p->next=s;s->prior=p;s->next=p->next;
* s->prior=p;s->next=p->next;p->next=s;p->next->prior=s;
* p->prior->next=s;p->prior=s;s->next=p;s->prior=p->prior;
* s->prior=p;s->next=p->next;p->next->prior=s;p->next=s;
25.某双链表用next表示后继指针,prior表示前驱指针,把s节点插入到p节点的前面应该如何操作?
* s->next=p;s->prior=p->prior;p->prior->next=s;p->prior=s;
* p->prior->next=s;p->prior=s;s->next=p;s->prior=p->prior;
* s->next=p;s->prior=p->prior;p->next->prior=s;p->prior=s;
* s->next=p->next;s->prior=p;p->prior->next=s;p->prior=s;
# 二.队列
26. 允许对队列进行的操作有
* 对队列中的元素排序
* 删除队尾元素
* 在队列元素之间插入元素
* 访问队头元素
27. 对于队列操作数据的原则是
* 先进先出
* 后进先出
* 先进后出
* 不分顺序
28. 队列是限定在()进行操作的线性表
* 中间
* 队首
* 队尾
* 两端
29. 若进队序列为a,b,c,d,以下哪个出队序列是合法的
* b,c,d,a
* a,c,b,d
* a,b,c,d
* c,b,d,a
30. 用数组q[n]模拟一个循环队列,f指向队头元素,r指向队尾后面一个元素,队列中最多有几个元素?
* n-1
* n
* n+1
* 无穷
31. 用数组q[n]模拟一个循环队列,f指向队头元素,r指向队尾后面一个元素,计算队列中元素个数的公式为()
* r-f
* (n+f-r)%n
* n+r-f
* (n+r-f)%n
32. 用数组q[n]模拟一个循环队列,f指向队头元素,r指向队尾后面一个元素,把元素x入队的操作为:
* q[r]=x;r++
* q[r]=x;r=(r+1)%n
* q[r]=x;r--;
* q[r]=x;r=(r-1)%n
33. 用数组q[n]模拟一个循环队列,f指向队头元素,r指向队尾后面一个元素,判断队列为空的公式是:
* r==f
* r+1==f
* (r+1)%n==f
* r==(f+1)%n
34. 用数组q[n]模拟一个循环队列,f指向队头元素,r指向队尾后面一个元素,判断队列为满的公式是:
* r==f
* r==f+1
* (r+1)%n==f
* r==(f+1)%n
35.已知循环队列的储存空间为数组a[21],front指向头元素的前一个位置,rear指向队尾元素,假设当前front和rear的值分别是8和3,则该队列的长度为()
* 5
* 6
* 16
* 17
36. 用数组q[6]来实现循环队列,当前rear和front的值分别是1和5,进行1次出队操作和2次入队操作之后,rear和front的值分别为
* 3 5
* 3 0
* 5 0
* 5 1
37. 用数组q[6]来实现循环队列,当前rear和front的值分别是4和0,进行2次出队操作和2次入队操作之后,rear和front的值分别为
* 2 4
* 2 6
* 2 2
* 0 2
38. 已知循环队列储存在一维数组A[n]中,且队列非空时,front和rear分别指向队头元素和队尾元素.若初始时队列为空,且要求第一个进入队列的元素储存在A[0]处,则初始时front和rear的值分别是()
* 0,0
* 0,n-1
* n-1,0
* n-1,n-1
39. 以下四种链表哪一个最适合当队列
* 只队首指针的非循环双链表
* 带队首指针和队尾指针的非循环单链表
* 只带队首指针的非循环单链表
* 只带队首指针的循环单链表
40. 以下四种链表哪一个最不适合当队列
* 只带队首指针的非循环双链表
* 只带队首指针的循环双链表
* 只带队尾指针的循环双链表
* 只带队尾指针的循环单链表
41. 单循环链表表示的队列长度为n,如果只设头指针,则入队的时间复杂度为()
* O(1)
* O(n)
* O(n*logn)
* O(n*n)
42. 单循环链表表示的队列长度为n,如果只设头指针,则出队的时间复杂度为()
* O(1)
* O(n)
* O(n*logn)
* O(n*n)
43. 使用链表实现的队列在进行删除操作时
* 只需要操作头指针
* 只需要操作尾指针
* 可能需要既操作头指针也操作尾指针
* 一定需要既操作头指针也操作尾指针
44. 用单链表实现一个队列,rear指针指向最后一个元素,以下哪个是元素p入队操作?
* rear->next=p;rear=p;
* rear->next=p;p=rear;
* rear=p;rear->next=p;
* p=rear;rear->next=p;
45. 某队列允许在其两端进行入队操作,但仅允许在队头进行出队操作.若元素a,b,c,d,e依次进入队列后再进行出队操作,则不可能得到的出队序列是
* b a c d e
* d b a c e
* e c b a d
* b d c a e
# 三.栈
46.对于栈操作数据的原则是
* 先进先出
* 后进先出
* 后进后出
* 不分顺序
47. 队列和栈的共同点是
* 都是先进先出
* 都是先进后出
* 只允许在端点处插入和删除元素
* 没有共同点
48. 入栈和出栈发生在哪里?
* 栈底和栈底
* 栈底和栈顶
* 栈顶和栈底
* 栈顶和栈顶
49. 和顺序栈相比,链栈的显著优点是
* 不易出现空栈情况
* 不易出现满栈情况
* 入栈操作更方便
* 出栈操作更方便
50. 若让元素1,2,3,4,5依次进栈,则出栈序列不可能出现()情况
* 54321
* 21543
* 43125
* 23541
51. 对于入栈顺序为a,b,c,d,e,f,g的序列,下列()不可能是合法的出栈序列
* abcdefg
* adcbegf
* adbcgfe
* gfedcba
52. 已知一个栈的入栈序列是1,2,3,...,n,如果第1个出栈的元素是i,那么第j个出栈的元素是
* i-j-1
* i-j
* j-i+1
* 不确定
53. 已知一个栈的入栈序列是1,2,3,...,n,如果第1个出栈的元素是n,那么第i个出栈的元素是
* i
* n-i
* n-i+1
* 不确定
54. 已知一个栈的入栈序列是1,2,3,...,n,如果第1个出栈的元素是3,那么第2个出栈的元素
* 一定是2
* 不可能是1
* 不可能是4
* 以上都不对
55. 如果一个栈初始时为空,且当前栈中的元素从栈顶到栈底依次为c,b,a,另外有元素d已经出栈,则可能入栈顺序是
* adcb
* abdc
* acbd
* bacd
56. 输入序列为ABC,经过栈处理后输出序列变成CBA,经过的操作为
* push,pop,push,pop,push,pop
* push,push,push,pop,pop,pop
* push,push,pop,pop,push,pop
* push,pop,push,push,pop,pop
57. 如果入栈序列是1,1,1,2,3,出栈序列也是1,1,1,2,3,请问有多少种出入栈方案?
* 6
* 5
* 4
* 3
58. 以下四种链表都不带头节点,请问哪个最不适合做栈?
* 只有头指针,没有尾指针的双向循环链表
* 只有尾指针,没有头指针的双向循环链表
* 只有头指针,没有尾指针的单向循环链表
* 只有尾指针,没有头指针的单向循环链表
59. 某个链式栈中的节点用data表示数据域,用link表示指针域,top是指向栈顶的指针.如果要把栈顶元素保存在变量x中并弹出,应该如何操作?
* x=top->data;top=top->link;
* top=top->link;x=top->data;
* x=top;top=top->link;
* x=top->link;
60. next表示某个链式栈中的指针域,top是指向栈顶的指针.如果要把元素p入栈,应该如何操作?
* top->next=p;top=p;
* top=p;top->next=p;
* p->next=top;top=p;
* p->next=top;p=top;
61. 有一个入栈序列是123456,出栈序列是243651,请问栈的容量最少要多大?
* 2
* 3
* 4
* 5
62. 用数组v[n]模拟栈,且栈中已有m个元素(m<n),请问出栈操作的时间复杂度是多少?
* O(1)
* O(n)
* O(m)
* O(n-m)
63. 用数组v[n]模拟栈,把栈顶指针top初始化为n,那么元素x进栈应该如何操作?
* v[top++]=x
* v[++top]=x
* v[top--]=x
* v[--top]=x
64. 用数组v[n]模拟栈,把栈顶指针top初始化为0,请问如何判断满栈?
* top==n-1
* top==n
* top==n+1
* top==NULL
65. 后缀表达式3 5 + 6 4 - *的计算结果是:
* 16
* -16
* 8
* -8
