java常见笔试题Java常见数据结构⾯试题（带答案）
1.栈和队列的共同特点是（只允许在端点处插⼊和删除元素）
4.栈通常采⽤的两种存储结构是（线性存储结构和链表存储结构）
5.下列关于栈的叙述正确的是（D）
A.栈是⾮线性结构
B.栈是⼀种树状结构
C.栈具有先进先出的特征
D.栈有后进先出的特征
6.链表不具有的特点是（B）A.不必事先估计存储空间      B.可随机访问任⼀元素strokes什么意思中文
C.插⼊删除不需要移动元素
D.所需空间与线性表长度成正⽐
7.⽤链表表⽰线性表的优点是（便于插⼊和删除操作）
8.在单链表中，增加头结点的⽬的是（⽅便运算的实现）
9.循环链表的主要优点是（从表中任⼀结点出发都能访问到整个链表）
10.线性表L＝（a1,a2,a3,……ai,……an），下列说法正确的是（D）
A.每个元素都有⼀个直接前件和直接后件
B.线性表中⾄少要有⼀个元素
C.表中诸元素的排列顺序必须是由⼩到⼤或由⼤到⼩
D.除第⼀个和最后⼀个元素外，其余每个元素都有⼀个且只有⼀个直接前件和直接后件
11.线性表若采⽤链式存储结构时，要求内存中可⽤存储单元的地址（D）
A.必须是连续的
B.部分地址必须是连续的
C.⼀定是不连续的
D.连续不连续都可以
12.线性表的顺序存储结构和线性表的链式存储结构分别是（随机存取的存储结构、顺序存取的存储结构）
13.树是结点的集合，它的根结点数⽬是（有且只有1）
14.在深度为5的满⼆叉树中，叶⼦结点的个数为（31）
15.具有3个结点的⼆叉树有（5种形态）
16.设⼀棵⼆叉树中有3个叶⼦结点，有8个度为1的结点，则该⼆叉树中总的结点数为（13）
17.已知⼆叉树后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是（cedba）
18.已知⼀棵⼆叉树前序遍历和中序遍历分别为ABDEGCFH和DBGEACHF，则该⼆叉树的后序遍历为（DGEBHFCA）
19.若某⼆叉树的前序遍历访问顺序是abdgcefh，中序遍历访问顺序是dgbaechf，则其后序遍历的结点
访问顺序是（gdbehfca）
20.数据库保护分为：安全性控制、完整性控制、并发性控制和数据的恢复。
1. 在计算机中，算法是指（解题⽅案的准确⽽完整的描述）
2.在下列选项中，哪个不是⼀个算法⼀般应该具有的基本特征（⽆穷性）
说明：算法的四个基本特征是：可⾏性、确定性、有穷性和拥有⾜够的情报。
3. 算法⼀般都可以⽤哪⼏种控制结构组合⽽成（顺序、选择、循环）
4.算法的时间复杂度是指（算法执⾏过程中所需要的基本运算次数）
5. 算法的空间复杂度是指（执⾏过程中所需要的存储空间）
6. 算法分析的⽬的是（分析算法的效率以求改进）
7. 下列叙述正确的是（C）
A．算法的执⾏效率与数据的存储结构⽆关
B．算法的空间复杂度是指算法程序中指令（或语句）的条数
C．算法的有穷性是指算法必须能在执⾏有限个步骤之后终⽌
D．算法的时间复杂度是指执⾏算法程序所需要的时间
8.数据结构作为计算机的⼀门学科，主要研究数据的逻辑结构、对各种数据结构进⾏的运算，以及（数据的存储结构）
9. 数据结构中，与所使⽤的计算机⽆关的是数据的（C）
A．存储结构  B．物理结构    C．逻辑结构    D．物理和存储结构
10. 下列叙述中，错误的是（B）
A．数据的存储结构与数据处理的效率密切相关
B．数据的存储结构与数据处理的效率⽆关
C．数据的存储结构在计算机中所占的空间不⼀定是连续的
D．⼀种数据的逻辑结构可以有多种存储结构
11. 数据的存储结构是指（数据的逻辑结构在计算机中的表⽰）
12. 数据的逻辑结构是指（反映数据元素之间逻辑关系的数据结构）
13. 根据数据结构中各数据元素之间前后件关系的复杂程度，⼀般将数据结构分为（线性结构和⾮线性结构）
14. 下列数据结构具有记忆功能的是（C）A．队列B．循环队列C．栈D．顺序表
15. 下列数据结构中，按先进后出原则组织数据的是（B）
A．线性链表  B．栈            C．循环链表        D．顺序表
16. 递归算法⼀般需要利⽤（队列）实现。
17. 下列关于栈的叙述中正确的是（D）A．在栈中只能插⼊数据B．在栈中只能删除数据
C．栈是先进先出的线性表            D．栈是先进后出的线性表
20. 由两个栈共享⼀个存储空间的好处是（节省存储空间，降低上溢发⽣的机率）
21. 应⽤程序在执⾏过程中，需要通过打印机输出数据时，⼀般先形成⼀个打印作业，将其存放在硬盘中的⼀个指定（队列）中，当打印机空闲时，就会按先来先服务的⽅式从中取出待打印的作业进⾏打印。
22.下列关于队列的叙述中正确的是（C）A．在队列中只能插⼊数据 B．在队列中只能删除数据  C．队列是先进先出的线性表            D．队列是先进后出的线性表
23.下列叙述中，正确的是（D）A．线性链表中的各元素在存储空间中的位置必须是连续的
B．线性链表中的表头元素⼀定存储在其他元素的前⾯ C．线性链表中的各元素在存储空间中的位置不⼀定是连续的，但表头元素⼀定存储在其他元素的前⾯ D．线性链表中的各元素在存储空间中的位置不⼀定是连续的，且各元素的存储顺序也是任意的
24.下列叙述中正确的是（A）A．线性表是线性结构      B．栈与队列是⾮线性结构
C．线性链表是⾮线性结构                                D．⼆叉树是线性结构
25. 线性表L＝（a1,a2,a3,……ai,……an），下列说法正确的是（D）
A．每个元素都有⼀个直接前件和直接后件      B．线性表中⾄少要有⼀个元素
C．表中诸元素的排列顺序必须是由⼩到⼤或由⼤到⼩D．除第⼀个元素和最后⼀个元素外，其余每个元素都有⼀个且只有⼀个直接前件和直接后件
26.线性表若采⽤链式存储结构时，要求内存中可⽤存储单元的地址（连续不连续都可以）
27. 链表不具有的特点是（B）A．不必事先估计存储空间            B．可随机访问任⼀元素
C．插⼊删除不需要移动元素            D．所需空间与线性表长度成正⽐
28. ⾮空的循环单链表head的尾结点（由p所指向），满⾜（p->next=head）
29.与单向链表相⽐，双向链表的优点之⼀是（更容易访问相邻结点）
30. 在（D）中，只要指出表中任何⼀个结点的位置，就可以从它出发依次访问到表中其他所有结点。A．线性单链表
B．双向链表            C．线性链表            D．循环链表
31. 以下数据结构属于⾮线性数据结构的是（C）A．队列      B．线性表C．⼆叉树      D．栈
32.树是结点的集合，它的根结点数⽬是（有且只有1）
33.具有3个结点的⼆叉树有（5种形态）
34. 在⼀棵⼆叉树上第8层的结点数最多是（128）注：2K-1
35. 在深度为5的满⼆叉树中，叶⼦结点的个数为（16）注：2n-1
子程序编程实例100例36. 在深度为5的满⼆叉树中，共有（31）个结点。注：2n－1
37.设⼀棵完全⼆叉树共有699个结点，则在该⼆叉树中的叶⼦结点数为（350）
说明：完全⼆叉树总结点数为N，若N为奇数，则叶⼦结点数为（N+1）/2；若N为偶数，则叶⼦结点数为N/2。
38. 设有下列⼆叉树，对此⼆叉树中序遍历的结果是（B）
A．ABCDEF
gitbranch只显示了部分分支B．DBEAFC
C．ABDECF
D．DEBFCA
39.已知⼆叉树后序遍历序列是dabec，中序遍历序列debac，它的前序遍历序列是（cedba）
40. 已知⼀棵⼆叉树前序遍历和中序遍历分别为ABDEGCFH和DBGEACHF，则该⼆叉树的后序遍历为（DGEBHFCA）
41.若某⼆叉树的前序遍历访问顺序是abdgcefh，中序遍历访问顺序是dgbaechf，则其后序遍历的结点访问顺序是（gdbehfca）
42. 串的长度是（串中所含字符的个数）
43.设有两个串p和q，求q在p中⾸次出现位置的运算称做（模式匹配）
44. N个顶点的连通图中边的条数⾄少为（N-1）
45.N个顶点的强连通图的边数⾄少有（N）
46.对长度为n的线性表进⾏顺序查，在最坏情况下所需要的⽐较次数为（N）
47. 最简单的交换排序⽅法是（冒泡排序）
48.假设线性表的长度为n，则在最坏情况下，冒泡排序需要的⽐较次数为（n(n-1)/2）
49. 在待排序的元素序列基本有序的前提下，效率最⾼的排序⽅法是（冒泡排序）
50. 在最坏情况下，下列顺序⽅法中时间复杂度最⼩的是（堆排序）
51. 希尔排序法属于（插⼊类排序）
52. 堆排序法属于（选择类排序）
53. 在下列⼏种排序⽅法中，要求内存量最⼤的是（归并排序）
54. 已知数据表A中每个元素距其最终位置不远，为节省时间，应采⽤（直接插⼊排序）
55. 算法的基本特征是可⾏性、确定性、有穷性和拥有⾜够的情报。
1.⼀个算法通常由两种基本要素组成：⼀是对数据对象的运算和操作，⼆是算法的控制结构。
1. 算法的复杂度主要包括时间复杂度和空间复杂度。
2. 实现算法所需的存储单元多少和算法的⼯作量⼤⼩分别称为算法的空间复杂度和时间复杂度。
3.所谓数据处理是指对数据集合中的各元素以各种⽅式进⾏运算，包括插⼊、删除、查、更改等运算，也包括对数据元素进⾏分析。
4.数据结构是指相互有关联的数据元素的集合。
5.数据结构分为逻辑结构与存储结构，线性链表属于存储结构。
6.数据结构包括数据的逻辑结构和数据的存储结构。
7. 数据结构包括数据的逻辑结构、数据的存储结构以及对数据的操作运算。
8.数据元素之间的任何关系都可以⽤前趋和后继关系来描述。
9.数据的逻辑结构有线性结构和⾮线性结构两⼤类。
10.常⽤的存储结构有顺序、链接、索引等存储结构。
11. 顺序存储⽅法是把逻辑上相邻的结点存储在物理位置相邻的存储单元中。
12. 栈的基本运算有三种：⼊栈、退栈与读栈顶元素。
13. 队列主要有两种基本运算：⼊队运算与退队运算。
14. 在实际应⽤中，带链的栈可以⽤来收集计算机存储空间中所有空闲的存储结点，这种带链的栈称为可利⽤栈。
15.栈和队列通常采⽤的存储结构是链式存储和顺序存储。
16.当线性表采⽤顺序存储结构实现存储时，其主要特点是逻辑结构中相邻的结点在存储结构中仍相邻。
17. 循环队列主要有两种基本运算：⼊队运算与退队运算。每进⾏⼀次⼊队运算，队尾指针就进1 。
18.当循环队列⾮空且队尾指针等于对头指针时，说明循环队列已满，不能进⾏⼊队运算。这种情况称为上溢。
19.当循环队列为空时，不能进⾏退队运算，这种情况称为下溢。
20. 在⼀个容量为25的循环队列中，若头指针front=16，尾指针rear=9，则该循环队列中共有 18 个元素。注：当rear<front 时，元素个数＝总容量－（front－rear）；
当rear>front时，元素个数＝rear－front。
1.判断链表是否存在环型链表问题：判断⼀个链表是否存在环，例如下⾯这个链表就存在⼀个环：
例如N1->N2->N3->N4->N5->N2就是⼀个有环的链表，环的开始结点是N5这⾥有⼀个⽐较简单的解法。设置两个指针
p1，p2。每次循环p1向前⾛⼀步，p2向前⾛两步。直到p2碰到NULL指针或者两个指针相等结束循环。如果两个指针相等则说明存在环。
struct link
{
int data;
link* next;
};
bool IsLoop(link* head)
{
link* p1=head, *p2 = head;
if (head ==NULL || head->next ==NULL)
{
return false;
}
do{
p1= p1->next;
p2 = p2->next->next;
} while(p2 && p2->next && p1!=p2);
if(p1 == p2)
return true;
else
return false;
}
2，链表反转单向链表的反转是⼀个经常被问到的⼀个⾯试题，也是⼀个⾮常基础的问题。⽐如⼀个链表是这样的： 1->2->3->4->5 通过反转后成为5->4->3->2->1。最容易想到的⽅法遍历⼀遍链表，利⽤⼀个辅助指针，存储遍历过程中当前指针指向的下⼀个元素，然后将当前节点元素的指针反转后，利⽤已经存储的指针往后⾯继续遍历。源代码如下：
struct linka {
int data;
linka* next;
};
void reverse(linka*& head)
{
if(head ==NULL)
return;
linka*pre, *cur, *ne;
pre=head;
cur=head->next;
while(cur)
{
ne = cur->next;
cur->next = pre;
动态css教程pre = cur;
cur = ne;
}
head->next = NULL;
head = pre;
}
还有⼀种利⽤递归的⽅法。这种⽅法的基本思想是在反转当前节点之前先调⽤递归函数反转后续节点。源代码如下。不过这个⽅法有⼀个缺点，就是在反转后的最后⼀个结点会形成⼀个环，所以必须将函数的返回的节点的next域置为NULL。因为要改变head指针，所以我⽤了引⽤。算法的源代码如下：
linka* reverse(linka* p,linka*& head)
{
if(p == NULL || p->next == NULL)
{
head=p;
return p;
}
else
{
linka* tmp = reverse(p->next,head);
tmp->next = p;
return p;
}
}
3，判断两个数组中是否存在相同的数字给定两个排好序的数组，怎样⾼效得判断这两个数组中存在相同的数字？
这个问题⾸先想到的是⼀个O(nlogn)的算法。就是任意挑选⼀个数组，遍历这个数组的所有元素，遍历过程中，在另⼀个数组中对第⼀个数组中的每个元素进⾏binary search。⽤C++实现代码如下：
bool findcommon(int a[],int size1,int b[],int size2)
{
int i;
for(i=0;i<size1;i++)
{
int start=0,end=size2-1,mid;
while(start<=end)
{
mid=(start+end)/2;
if(a[i]==b[mid])
return true;
else if (a[i]<b[mid])
end=mid-1;
else
start=mid+1;
}
}
return false;
}
后来发现有⼀个 O(n)算法。因为两个数组都是排好序的。所以只要⼀次遍历就⾏了。⾸先设两个下标，分别初始化为两个数组的起始地址，依次向前推进。推进的规则是⽐较两个数组中的数字，⼩的那个数组的下标向前推进⼀步，直到任何⼀个数组的下标到达数组末尾时，如果这时还没碰到相同的数字，说明数组中没有相同的数字。
bool findcommon2(int a[], int size1, int b[], int size2)
{
int i=0,j=0;
while(i<size1 && j<size2)
{
if(a[i]==b[j])
return true;
if(a[i]>b[j])
j++;
if(a[i]<b[j])
i++;
}
return false;
}
4，最⼤⼦序列问题：
给定⼀整数序列A1， A2，... An （可能有负数），求A1~An的⼀个⼦序列Ai~Aj，使得Ai到Aj的和最⼤
例如：
整数序列-2, 11, -4, 13, -5, 2, -5, -3, 12, -9的最⼤⼦序列的和为21。
对于这个问题，最简单也是最容易想到的那就是穷举所有⼦序列的⽅法。利⽤三重循环，依次求出所有⼦序列的和然后取最⼤的那个。当然算法复杂度会达到O(n^3)。显然这种⽅法不是最优的，下⾯给出⼀个算法复杂度为O(n)的线性算法实现，算法的来源于Programming Pearls⼀书。在给出线性算法之前，先来看⼀个对穷举算法进⾏优化的算法，它的算法复杂度为
O(n^2)。其实这个算法只是对对穷举算法稍微做了⼀些修改：其实⼦序列的和我们并不需要每次都重
新计算⼀遍。假设Sum(i, j)是A[i] ... A[j]的和，那么Sum(i, j+1) = Sum(i, j) + A[j+1]。利⽤这⼀个递推，我们就可以得到下⾯这个算法：
int max_sub(int a[],int size)
{
int i,j,v,max=a[0];
for(i=0;i<size;i++)
{
v=0;
for(j=i;j<size;j++)
{
v=v+a[j];//Sum(i, j+1) = Sum(i, j) + A[j+1]
if(v>max)
max=v;
}
}
return max;
}
那怎样才能达到线性复杂度呢？这⾥运⽤动态规划的思想。先看⼀下源代码实现：
int max_sub2(int a[], int size)
{
int i,max=0,temp_sum=0;
for(i=0;i<size;i++)
{
temp_sum+=a[i];
if(temp_sum>max)
max=temp_sum;
else if(temp_sum<0)
temp_sum=0;
}
return max;
}
6，按单词反转字符串并不是简单的字符串反转，⽽是按给定字符串⾥的单词将字符串倒转过来，就是说字符串⾥⾯的单词还是保持原来的顺序，这⾥的每个单词⽤空格分开。
如果只是简单的将所有字符串翻转的话，可以遍历字符串，将第⼀个字符和最后⼀个交换，第⼆个和倒数第⼆个交换，依次循环。其实按照单词反转的话可以在第⼀遍遍历的基础上，再遍历⼀遍字符串，
对每⼀个单词再反转⼀次。这样每个单词⼜恢复了原来的顺序。
char* reverse_word(const char* str)
{
int len = strlen(str);
char* restr = new char[len+1];
strcpy(restr,str);
int i,j;
for(i=0,j=len-1;i<j;i++,j--)
{
char temp=restr[i];
restr[i]=restr[j];
restr[j]=temp;
}
int k=0;
while(k<len)
{
i=j=k;
while(restr[j]!=' ' && restr[j]!='' )
j++;
k=j+1;
j--;
for(;i<j;i++,j--)
{
char temp=restr[i];
restr[i]=restr[j];
restr[j]=temp;
controller dao}
}
return restr;
}
如果考虑空间和时间的优化的话，当然可以将上⾯代码⾥两个字符串交换部分改为异或实现。
例如将
char temp=restr[i];
restr[i]=restr[j];
restr[j]=temp;
改为

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。