平时积累的数据结构题_在一个链队中,设front和rear分别为队首和队尾指针,则插入p所指结点时,应执行

一、数据结构基本概念

1、数据的逻辑结构不包括（）

A、图状结构

B、树状结构

C、总线结构

D、线性结构

2 、以下有关抽象数据类型的描述中，正确的是（）

A、抽象数据类型只能用Java描述

B、抽象数据类型的操作可以没有操作结果

C、抽象数据类型是数据的逻辑结构及操作的组合

D、抽象数据类型是一个值的集合

3 、数据结构课程中，讨论计算机数据处理的基本单位是（）

A、字节

B、数据项

C、数据元素

D、位

4 、每个结点只含有一个数据元素，所有存储结点相继存放在一个连续的存储区里，这种存储结构称为（ ）结构。

A、索引存储

B、链式存储

C、散列存储

D、顺序存储

5 、链式存储结构的最大优点是（ ）。

A、存储密度高

B、便于随机存取

C、无需预分配空间

D、便于进行插入和删除操作

二、算法和算法分析

1、算法在发生非法操作时可以作出处理的特性称为算法的（ ）。

A、正确性

B、高效性

C、健壮性

D、易读性

2 、下列算法的时间复杂度是( )。

public static int rSearch(int[] a,int x){
 
    int n=a.length;
 
    for(int i=0; i<n&&!x.equals(a[i]);i++);
 
        if (i==n)
 
               return -1;
 
        else
 
               return i;
 
 }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

A、O(n)

B、O(n3)

C、O(n2)

D、O(1)

3 、某算法的时间复杂度为O(n2)，表明该算法的（ ）。

A、执行时间与n2成正比

B、问题规模与n2成正比

C、执行时间等于n2

D、问题规模是n2

4 、算法应该是（ ）。

A、问题求解步骤的描述

B、A和C

C、程序

D、要满足五个基本特性

5 、求整数n (n>=0)阶乘的算法如下，其时间复杂度是（ ）。

int fact(int n){
 
    if (n<=l) return 1;
 
    return n*fact(n-1);
 
}
1
2
3
4
5
6
7

A、O(n2)

B、O(n)

C、O(nlog2n)

D、O(log2n)

三、顺序表

1、要将一个顺序表{a0,a1,……,an-1}中第i个数据元素ai(0≤i≤n-1)删除，需要移动（ ）个数据元素。

A、n-i

B、n-i-1

C、n-i+1

D、i

2、在有n个结点的顺序表上做查找结点运算的时间复杂度为（ ）。

A、O(n2)

B、O(n)

C、O(log2n)

D、O(1)

3、一个数组首个元素(第0个元素)的存储地址是100,每个元素的长度为2,则第5个 元素的地址是？

A、100

B、108

C、120

D、110

4、在一个长度为n的顺序表中,在第i个元素(0≤i≤n)之前插入一个新元素时需向后 移动( )个元素。

A、n-i-1

B、i

C、n-i

D、n-i+1

5、关于线性表,下列说法正确的是( )。

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

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

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

D、除第一个和最后一个元素,其余每个元素都有一个且仅有一个直接前驱和直接后继

四、单链表

1、在线性表的单链表存储结构中，用于存储数据元素值本身的是（ ）

A、数据域

B、头结点

C、指针域

D、后继结点的值

2、在含有n个结点的单链表中，若要删除一个指定的结点p，则首先必须找到( )。

A、头结点

B、后继结点

C、首结点

D、前驱结点

3、链表不具有的特点是( )。

A、可随机访问任一元素

B、所需空间与线性长度成正比

C、不必事先估计存储空间

D、插入、删除不需要移动元素

4、在一个单链表中,结点指针域为next,已知q所指结点是p所指结点的前驱结点,若在q和p之间插入s结点,则执行语句( )。

A、p->next=s->next;s->next=p;

B、p->next=s;s->next=q;

C、q->next=s;s->next=p;

D、s->next=p->next;p->next=s;

5、在一个含有n个结点的有序单链表中插入一个新结点，使单链表仍然保持有序的算法的时间复杂度是（ ）。

A、O(log2n)

B、O(n2)

C、O(1)

D、O(n)

五、其他链表

1、关于单循环链表的描述，正确的是（ ）。

A、将单链表的最后一个结点的后继指针指向第一个结点

B、存在由前驱指针和后继指针连接而成的两个环

C、每一个结点有两个数值域

D、每一个结点有两个指针域

2、从顺序表上删除第i个元素，该算法中的循环语句for(int j = i; j<curLen-i; j++)的循环体语句是（ ），其中curLen表示顺序表长度，listElem[ ]中存放顺序表。

A、listElem[j-1]=listElem[j]

B、listElem[j]=listElem[j+1]

C、listElem[j]=listElem[j-1]

D、istElem[j+1]=listElem[j]

3、指针p、q和r依次指向某循环链表中三个相邻的结点,结点指针域为 next,交换结点q和结点r在表中次序的程序段是( )。

A、r->next=q;p->next=r; q->next=r->next;

B、p->next=r;q->next=r->next;r->next=q;

C、p->next=r;r->next=q; q->next=r->next;

D、r->next=q;q->next=r->next;p->next=r;

4、若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运 算,则利用( )存储方式最节省时间。

A、双链表

B、顺序表

C、单循环链表

D、带头结点的双循环链表

5、在头指 针 为 head 的 非 空 单 循 环 链 表 中,指 针 p 指 向 尾 结 点,下 列 关 系 成 立 的 是( )

A、p==head

B、p->next==head

C、p->next->next==head

D、p->next==NULL

六、顺序栈

1、若将字符A、B、C、D依次进栈，则不可能得到的出栈序列是（ ）。

A、DCBA

B、ADBC

C、ABCD

D、ACBD

2、已知栈的最大容量为4,若进栈序列为1,2,3,4,5,6,且进栈和出栈可以穿插进行,则 可能出现的出栈序列为( )

A、5,4,3,2,1,6

B、2,3,5,6,1,4

C、3,2,5,4,1,6

D、1,4,6,5,2,3

3、若一个栈以数组 V 存储(数组下标0至n-1),初始栈顶指针top为n-1,则下面x进栈的正确操作是( )

A、V[–top]=x;

B、V[top–]=x;

C、V[top++]=x;

D、V[++top]=x;

4、若一个栈以数组 V 存储(数组下标0至n-1),初始栈顶指针top为n,则下面x进栈的正确操作是( )。

A、V[top++]=x;

B、V[++top]=x;

C、V[–top]=x;

D、V[top–]=x;

5、有六 个 元 素 按 6,5,4,3,2,1 的 顺 序 进 栈,问 下 列 哪 一 个 不 是 合 法 的 出 栈 序 列? ( )

A、453126

B、346521

C、234156

D、543612

七、线性表

1、在存储数据时，不仅要存取数据元素的值，还要存储（）

A、数据元素的大小

B、数据的存储方法

C、数据元素之间的关系

D、数据元素的类型

2、在线性表的单链表存储结构中，用于存储后继结点地址的是（ ）。

A、指针域

B、头结点

C、数据元素

D、数据域

3、关于双向循环链表的描述，正确的是（ ）。

A、将单链表的最后一个结点的后继指针指向第一个结点

B、每一个结点只有一个指针域

C、存在由前驱指针和后继指针连接而成的两个环

D、每一个结点 有两个数值域

4、要将一个顺序表{a0,a1,……,an-1}中第i个数据元素ai(0≤i≤n-1)删除，需要移动（ ）个数据元素。

A、n-i-1

B、n-i+1

C、n-i

D、i

5、在一个单链表中的p和q两个结点之间插入一个新结点，假设新结点为s，则修改链的java语句序列是（ ）。

A、q.next=s.next; s.next=p;

B、p.next=s; s.next=q;

C、s.next=p; q.next=s;

D、p.next=s; s.next=p;

6、算法分析的两个主要方面是( )。

A、可读性和文档性

B、正确性和简明性

C、数据复杂性和程序复杂性

D、空间复杂性和时间复杂性

7、在含有n个结点的单链表中，若要删除一个指定的结点p，则首先必须找到( )。

A、前驱结点

B、首结点

C、头结点

D、后继结点

8、在一个单链表中,结点指针域为next,p指向的结点不是尾结点,若删除p所指结点 的后续结点,则应执行语句( )。

A、p=p->next;p->next=p->next->next;

B、p->next=p->next->next;

C、p->next=p->next;

D、p=p->next->next;

9、某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素,则采用( )存储方式最节省运算时间。

A、双链表

B、仅有头指针的单循环链表

C、单链表

D、仅有尾指针的单循环链表

10、数据结构课程中，讨论计算机数据处理的基本单位是（）

A、字节

B、位

C、数据项

D、数据元素

八、栈与队列

1、在循环顺序队列中，假设以少用一个存储单元的方法来区分队列判满和判空的条件，front和rear分别为队首和队尾指针，它们分别指向队首元素和队尾元素的下一个存储单元，队列的最大存储容量为maxSize，则队列置空语句是（ ）。

A、rear=front=0

B、rear=front

C、rear=front=null

D、front=0

2、若将整数3、4、5、6依次进栈，则不可能得到的出栈序列是（ ）。

A、3456

B、6543

C、3645

D、3546

3、若一个栈以数组 V 存储(数组下标0至n-1),初始栈顶指针top为0,则下面x进栈的正确操作是( )。

A、V[top–]=x;

B、V[top++]=x;

C、V[++top]=x;

D、V[–top]=x;

4、从一个栈顶指针为top的链栈中执行出栈操作，用x保存出栈结点的值，应执行下列 ( )命令。

A、x=top.data;

B、x=top.data; top=top.next;

C、top=top.next; x=top.data;

D、x=top; top=top.next;

5、在循环顺序队列中，假设以少用一个存储单元的方法来区分队列判满和判空的条件，front和rear分别为队首和队尾指针，它们分别指向队首元素和队尾元素的下一个存储单元，队列的最大存储容量为maxSize，使用queueElem[ ]数组存储循环顺序队列，则入队操作的java语句是（ ）。

A、queueElem[rear]=x; rear=rear+1;

B、queueElem[rear-1]=x; rear=rear+1;

C、queueElem[rear]=x; rear=(rear+1)%queueElem.length;

D、queueElem[rear-1]=x; rear=(rear+1)%queueElem.length;

6、在循环顺序队列中，假设以少用一个存储单元的方法来区分队列判满和判空的条件，front和rear分别为队首和队尾指针，它们分别指向队首元素和队尾元素的下一个存储单元，使用queueElem[ ]数组存储循环顺序队列，使用t保存出队结点，则出队操作的java语句是（ ）。

A、t=queueElem[front]; front=(front+1)%queueElem.length;

B、front=front+1; t=queueElem[front];

C、front=(front+1)%queueElem.length; t=queueElem[front];

D、t=queueElem[front]; front=front+1;

7、在链队列中，front和rear分别为队首和队尾指针，它们分别指向队首元素和队尾元素，则取队首元素的语句是（ ）。

A、front.data；

B、front.next.data;

C、rear.data;

D、rear.next.data;

8、用不带头结点的单链表存储队列时,其队头指针指向队头结点,其队尾指针指向队尾结点,则在进行删除操作时( )。

A、队头、队尾指针都要修改

B、仅修改队头指针

C、队头、队尾指针都可能要修改

D、仅修改队尾指针

9、用不带头结点的链表存储队列,在进行插入运算时( )。

A、仅修改队头指针

B、队头、队尾指针都可能要修改

C、仅修改队尾指针

D、队头、队尾指针都要修改

10、在一个栈顶指针为top的链栈中执行链栈操作时，通常会再初始化一个指向栈顶的指针p，则下面描述不正确的是（ ）。

A、在遍历链栈的过程中执行p=p.next;语句完成访问后继结点的功能。

B、也可以将p初始化为栈底指针。

C、top指针始终指向栈顶。

D、可以使用p！=null;来判断是否访问到栈尾。

九、循环顺序队列

1、循环顺序队列中，采用以下哪一种方法不能区分队列判满和判空的条件（ ）。

A、采用少用一个存储单元的方法

B、采用多一个存储空间的方法

C、采用设置计数器的方法

D、采用设置标志变量的方法


2、在循环顺序队列中，假设以少用一个存储单元的方法来区分队列判满和判空的条件，front和rear分别为队首和队尾指针，它们分别指向队首元素和队尾元素的下一个存储单元，队列的最大存储容量为maxSize，则队列的长度是（ ）。

A、rear-front

B、rear-front+1

C、(rear-front+1)%maxSize

D、(rear-front+maxSize)%maxSize

3、在循环队列中，元素的排列顺序（）。

A、与队中数组大小有关

B、与元素值的大小有关

C、由元素进队的先后顺序确定

D、与队头和队尾指针的取值有关


4、若某循环队列有队首指针front和队尾指针rear，在队不空时出队操作仅会改变（）。

A、front和rear

B、rear

C、front

D、以上都不对


5、在循环顺序队列中，假设以少用一个存储单元的方法来区分队列判满和判空的条件，front和rear分别为队首和队尾指针，它们分别指向队首元素和队尾元素的下一个存储单元，队列的最大存储容量为maxSize，则队列的判空条件是（ ）。

A、front==rear+1

B、front==rear

C、front!=rear

D、front==(rear+1)% maxSize

---

总结

数据结构很重要，好好听课多做题！