第一关 - 线性表

• 技能点：线性表的顺序和链式存储

下面关于线性表的叙述错误的是( )

A. 线性表采用顺序存储必须占用一片连续的存储空间

B. 线性表采用链式存储不必占用一片连续的存储空间

C. 线性表采用链式存储便于插入和删除操作的实现

D. 线性表采用顺序存储便于插入和删除操作的实现

• 技能点：线性表的前驱和后继

线性表L=(ai，a2,………an)，下列说法正确的是( )

A．每个元素都有一个直接前驱和一个直接后继

B. 线性表中至少有一个元素

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

D. 除第一个和最后一个元素外，其余每个元素都有一个且仅有一个直接前驱和直接后继。

• 技能点：链式结构存储空间

链接存储的存储结构所占存储空间( )

A. 分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针

B. 只有一部分，存放结点值

C. 只有一部分，存储表示结点间关系的指针

D. 分两部分，一部分存放结点值，另一部分存放结点所占单元数

• 技能点：链式存储结构的存储单元

线性表若采用链式存储结构时，要求内存中可用存储单元的地址( )

A. 必须是连续的

B. 部分地址必须是连续的

C. 一定是不连续的

D. 连续或不连续都可以

• 技能点：线性表链式存储结构

线性表L在( )情况下适用于使用链式结构实现.

A. 需经常修改L中的结点值

B. 需不断对L进行删除插入

C. L中含有大量的结点

D. L中结点结构复杂

• 技能点：单链表存储密度

单链表的存储密度( )

A. 大于1

B. 等于1

C. 小于1

D. 不能确定

• 技能点：线性表的顺序存储操作时间复杂度

在n个结点的顺序表中，算法的时间复杂度是O(1)的操作是( )

A. 访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n)

B. 在第i个结点后插入一个新结点（1≤i≤n)

C. 删除第i个结点（1≤i≤n)

D. 将n个结点从小到大排序

• 技能点：单链表时间复杂度

设一个有序的单链表中有n个结点，现要求插入一个新结点后使得单链表仍然保持有序，则该操作的时间复杂度为( )

A. O(log2n)

B. O(1)

C. O(n^2)

D. O(n)

• 技能点：有序单链表

若指定有n个元素的向量，则建立一个有序单链表的时间复杂性的量级是( )

A. O(1)

B. O(n)

C. O(n^2)

D. O(nlog2n)

• 技能点：顺序表的插入操作

向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动的元素个数为( )

B. 63.5

In [12]:

1
answer.append('B')

• 技能点：顺序表的删除操作

设顺序线性表中有n个数据元素，则删除表中第i个元素需要移动( )个元素.

A. n-i

B. n+1-i

C. n-1-i

In [13]:

1
answer.append('A')

• 技能点：顺序表的插入操作

在一个长度为n的顺序表中，在第i个元素（1≤i≤n+1）之前插入一个新元素时须向后移动( )个元素.

A. n-i

B. n-i+1

C. n-i-1

In [14]:

1
answer.append('B')

• 技能点：双向循环链表的插入操作

在带头结点的双向循环链表中插入一个新结点，需要修改的指针域数量是( )

In [15]:

1
answer.append('C')

• 技能点：单链表的判空条件

设一条单链表的头指针变量为head且该链表没有头结点，则其判空条件是( )

A. head==0

B. head->next==0

C. head->next==head

D. head != 0

In [16]:

1
answer.append('A')

• 技能点：单链表的插入操作

在单链表中，要将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;

• 技能点：双向链表的删除操作

在双向链表存储结构中，删除p所指的结点时须修改指针( )

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;

• 技能点：双向链表的插入操作

在双向循环链表中，在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->prior=p; q->next=p->next; p->next=q; p->next->prior=q;

• 技能点：散列表

设某散列表的长度为100，散列函数H(k) = k % P，则Р通常情况下最好选择( )

• 技能点：散列表的存储

设散列表中有m个存储单元，散列函数H(key)= key % p，则p最好选择( )

A. 小于等于m的最大奇数

B. 小于等于m的最大素数

C. 小于等于m的最大偶数

D. 小于等于m的最大合数

• 技能点：哈希表

设有n 个关键字具有相同的Hash函数值，则用线性探测法把这n个关键字映射到HASH表中需要做( )次线性探测.

B. n(n+1)

C. n(n+1)/2

D. n(n-1)/2

• 技能点：有序表合并

将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是( )

B. 2n-1

D. n-1

• 技能点：数组顺序存储结构

设有一个10阶的下三角矩阵A(包括对角线)，按照从上到下、从左到右的顺序存储到连续的55个存储单元中,每个数组元素占1个字节的存储空间,则A[5][4]地址与A[0][0]的地址之差为( )

• 技能点：链表比较

设某链表中最常用的操作是在链表的尾部插入或删除元素，则选用下列( )存储方式最节省运算时间.

A. 单向链表

B. 单向循环链表

C. 双向链表

D. 双向循环链表

• 技能点：线性表顺序和链式存储比较

以下说法错误的是( )

A. 求表长、定位这两种运算在采用顺序存储结构时实现的效率不比采用链式存储结构时实现的效率低

B. 顺序存储的线性表可以随机存取

C. 由于顺序存储要求连续的存储区域，所以在存储管理上不够灵活

D. 线性表的链式存储结构优于顺序存储结构

• 技能点：线性表顺序和链式存储比较

在以下的叙述中，正确的是( ).

A. 线性表的顺序存储结构优于链表存储结构　

B. 线性表的顺序存储结构适用于频繁插入/删除数据元素的情况

C. 线性表的链表存储结构适用于频繁插入/删除数据元素的情况

D. 线性表的链表存储结构优于顺序存储结构

D D A D B
C A D C B
A B C A D
A C B B C
A B D D C

a1,a5,a9,a14,a20,a23,a25

第二关 - 栈和队列

• 技能点：递归算法

一个递归算法必须包括( )

A. 递归部分

B. 终止条件和递归部分

C. 迭代部分

D. 终止条件和迭代部分

• 技能点：递归算法

def fact(n):
    if(n <= 0):
        return 1
    else:
        return n*fact(n-1)

设有一个递归算法如上代码，则计算fact(n)需要调用该函数的次数为( )

A. n+1

B. n-1

D. n+2

• 技能点：进栈出栈

设输入序列为1、2、3、4、5、6，则通过栈的作用后可以得到的输出序列为( )

A. 5，3，4，6，1，2

B. 3，2，5，6，4，1

C. 3，1，2，5，4，6

D. 1，5，4，6，2，3

• 技能点：进栈出栈

若让元素1，2，3，4，5依次进栈，则出栈次序不可能出现在( )种情况.

A. 5，4，3，2，1

B. 2，1，5，4，3

C. 4，3，1，2，5

D. 2，3，5，4，1

• 技能点：进栈出栈

若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为( )

B. n-i

C. n-i+1

D. 不确定

• 技能点：链栈的存储结构

设链表不带头结点且所有操作均在表头进行，则下列最不适合作为链栈的是( )

A. 只有表头结点指针，没有表尾指针的双向循环链表

B. 只有表尾结点指针，没有表头指针的双向循环链表

C. 只有表头结点指针，没有表尾指针的单向循环链表

D. 只有表尾结点指针，没有表头指针的单向循环链表

• 技能点：链栈的删除操作

链式栈结点为:(data,link)，top指向栈顶，若想摘除栈顶结点，并将删除结点的值保存到x中,则应执行操作( )

A. x=top->data;top=top->link;

B. top=top->link;x=top->link;

C. x=top;top=top->link;

D. X=top->link;

• 技能点：顺序栈

在一个具有n个单元的顺序栈中，假设以地址高端作为栈底，以top作为栈顶指针，则当作进栈处理时，top的变化为( )

A. top不变

B. top-0

C. top—

D. top++

• 技能点：队列的链式存储

用链接方式存储的队列，在进行插入运算时( )

A. 仅修改头指针

B. 头、尾指针都要修改

C. 仅修改尾指针

D. 头、尾指针可能都要修改

• 技能点：栈求表达式

利用栈求表达式的值时，设立运算数栈OPEN.假设OPEN只有两个存储单元，则在下列表达式中，不会发生溢出的是( )

A. A-B*(C-D)

B. (A-B)*C-D

C. (A-B*C)-D

D. (A-B)*(C-D)

• 技能点：共享栈的好处

采用共享栈的好处是( )

A. 减少存取时间，降低发生上溢的可能

B. 节省存储空间，降低发生上溢的可能

C. 减少存取时间，降低发生下溢的可能

D. 节省存储空间，降低发生下溢的可能.

• 技能点：链式队列的操作

设指针变量front表示链式队列的队头指针，指针变量rear表示链式队列的队尾指针指针变量s指向将要入队列的结点X，则入队列的操作序列为( )

A. front->next=s; front=s;

B. s->next=rear; rear=s;

C. rear->next=s; rear=s;

D. s->next=front; front=s;

• 技能点：双端队列的输入输出

若以1234作为双端队列的输入序列，则既不能由输入受限的双端队列得到，也不能由输出受限的双端队列得到的输出序列是( )

A. 1234

B. 4132

C. 4231

D. 4213

• 技能点：循环队列

已知循环队列的存储空间为数组A[21]，front指向队头元素的前一个位置，rear指向队尾元素，假设当前front和rear的值分别为8和3，则该队列的长度为( )

• 技能点：循环队列

设顺序循环队列Q[0:M-1]的头指针和尾指针分别为F和R，头指针F总是指向队头元素的前一位置，尾指针R总是指向队尾元素的当前位置，则该循环队列中的元素个数为( )

A.R-F

B.F-R

C.(F-R+M)%M

D.(R-F+M)%M

• 技能点：循环队列的入队操作

循环队列存储在数组A[0..m]中，则入队时的操作为( )

A. rear=rear+1

B. rear=(rear+1)%(n-1)

C. rear=(rear+1) %m

D. rear= (rear+1)%(m+1)

• 技能点：循环队列的删除操作

若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为多少？

A. 1和 5

B. 2和4

C. 4和2

D. 5和1

• 技能点：栈和队列的共同点

栈和队列的共同点是( )

A. 都是先进先出

B. 都是先进后出

C. 只允许在端点处插入和删除元素

D. 没有共同点

• 技能点：栈的应用

栈在( )中有所应用.

A．递归调用

B．函数调用

C．表达式求值

D. 前三个选项都有

• 技能点：线性表、栈、队列的比较

为解决计算机主机与打印机间速度不匹配问题，通常设一个打印数据缓冲区。主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是( )

c．线性表

D．有序表

• 技能点：栈和队列

设栈S和队列Q的初始状态为空，元素e1、e2、e3、e4、e5和e6依次进入栈S，一个元素出栈后即进入Q，若6个元素出队的序列是e2、e4、e3、e6、e5和e1，则栈S的容量至少应该是( )

• 技能点：栈和队列的应用

设计一个判别表达式中左，右括号是否配对出现的算法，采用( )数据结构最佳.

A．线性表的顺序存储结构

C．线性表的链式存储结构

• 技能点：循环队列的判空条件

最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是( )

A. (rear+1)%n=front

B. rear==front

C. rear+1==front

D. (rear-l)%n==front

• 技能点：双向队列（注：本题为多选题）

已知输入序列为abcd经过输出受限的双向队列后能得到的输出序列有( )

A. dacb

B. cadb

C. dbca

D. bdac

E. 以上答案都不对

• 技能点：进栈出栈（注：本题为多选题）

依次读入数据元素序列{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}

B A B C C

C A C D B

B C C C D

D B C D A

B D B BD AD

a17,a23,a24