平时积累的数据结构题
文章目录
- 一、数据结构基本概念
- 二、算法和算法分析
- 三、顺序表
- 四、单链表
- 五、其他链表
- 六、顺序栈
- 七、线性表
- 总结
一、数据结构基本概念
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; }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); }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、数据元素
总结
数据库很重要，好好听课多做题！