当前位置：文档之家 › 2015陕西省JAVA版数据结构考试技巧重点

2015陕西省JAVA版数据结构考试技巧重点

  • 格式：rtf
  • 大小：74.49 KB
  • 文档页数：2

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

A) 单链表 B) 仅有头指针的单循环链表
C) 双链表 D) 仅有尾指针的单循环链表
2、已知广义表L=((x,y,z),a,(u,t,w))，从L 表中取出原子项t 的操作是（ D ）。

A) Head(Head(Tail(Tail(L))))
B) Tail(Head(Head(Tail(L))))
C) Head(Tail(Head(Tail(L))))
D)Head(Tail(Head(Tail(Tail(L)))))
3、栈进行插入和删除操作的特点是（ A ）。

A）LIFO B）FIFO
C）FCFS D）HPF
4、n个顶点的强连通图至少有（ A ）条边。

A）n B）n+1 C）n-1 D）n(n-1)
5、链式存储的存储结构所占存储空间（ A ）。

A）分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针
B）只有一部分，存放结点值
C）只有一部分，存储表示结点间关系的指针
D）分两部分，一部分存放结点值，另一部分存放结点所占单元数
6、广义表A=（A,B,(C,D),(E,(F,G))），则head(tail(head(tail(tail(A)))))=（ D ）。

A） (G) B） (D) C） C D） D
7、n个顶点，e条边的有向图的邻接矩阵中非零元素有（ C ）个。

A）n B）2e C）e D） n+e
8、在一个链队列中，假定front和rear分别为队首和队尾指针，则删除一个结点的操作为（ B ）。

A) rear=rear->next; B) front=front->next;
C) rear=front->next; D) front=rear->next ;
9、在一个链队列中，假定front和rear分别为队首和队尾指针，则删除一个结点的操作为（ B ）。

A) rear=rear->next; B) front=front->next;
C) rear=front->next; D) front=rear->next ;
10、在一个单链表中，已知q结点是p结点的前趋结点，若在q和p之间插入s结点，则须执行（ A ）。

A）q->next=s; s->next=p; B）s->next=p->next; p->next=s;
C）p->next=s->next; s->next=p D）p->next=s; s->next=q;
11、已知广义表L=((x,y,z),a,(u,t,w))，从L 表中取出原子项t 的操作是（ D ）。

A) Head(Head(Tail(Tail(L))))
B) Tail(Head(Head(Tail(L))))
C) Head(Tail(Head(Tail(L))))
D)Head(Tail(Head(Tail(Tail(L)))))
12、在一个链队列中，假定front和rear分别为队首和队尾指针，则插入一个结点的操作为（ B ）。

A）front=front->next; B） rear=rear->next;
C） rear=front->next; D） front=rear->next ;
13、若采用邻接矩阵法存储一个n个顶点的无向图，则该邻接矩阵是一个（ D ）。

A）上三角矩阵 B) 稀疏矩阵
C) 对角矩阵 D) 对称矩阵
14、广义表A=（A,B,(C,D),(E,(F,G))），则head(tail(head(tail(tail(A)))))=（ D ）。

A） (G) B） (D) C） C D） D
15、有一个有序表{1，4，6，10，18，35，42，53，67，71，78，84，92，99}。

当用二分查找法查找键值为84的结点时，经（ B ）比较后查找成功。

A) 4 B)3 C)2 D)12
16、若采用邻接矩阵法存储一个n个顶点的无向图，则该邻接矩阵是一个（ D ）。

A）上三角矩阵 B) 稀疏矩阵
C) 对角矩阵 D) 对称矩阵
17、串的逻辑结构与（ D ）的逻辑结构不同。

A）线性表 B）栈
C）队列 D）树
18、设单链表中指针p指着结点A，若要删除A之后的结点（若存在），则需要修改指针的操作为（ A ）。

A）p->next=p->next->next B）p=p->next
C）p=p->nexe->next D）p->next=p
19、在一个单链表中，已知q结点是p结点的前趋结点，若在q和p之间插入s结点，则须执行（ A ）。

A）q->next=s; s->next=p; B）s->next=p->next; p->next=s;
C）p->next=s->next; s->next=p D）p->next=s; s->next=q;。

合集下载

2015年陕西省JAVA最新版本摘要

2015年陕西省JAVA最新版本摘要

}
else if (i==n-1) //根结点无右子树，遍历序列的1—n-1是左子树
{p->rchild=null;
s.lvl=++R; s.l=1; s.h=i-1; s.f=p; s.lr=1; enqueue(Q,s);
}
else //根结点有左子树和右子树
typedef struct
{ int lvl; //层次序列指针，总是指向当前“根结点”在层次序列中的位置
int l,h; //中序序列的下上界
int f; //层次序列中当前“根结点”的双亲结点的指针
int lr; // 1—双亲的左子树 2—双亲的右子树
for (i=0; i<n; i++) //在中序序列中查找根结点，然后，左右子女信息入队列
if (in[i]==level[0]) break;
if (i==0) //根结点无左子树，遍历序列的1—n-1是右子树
{p->lchild=null;
s.lvl=++R; s.l=i+1; s.h=n-1; s.f=p; s.lr=2; enqueue(Q,s);
2、有一种简单的排序算法，叫做计数排序（count sorting）。这种排序算法对一个待排序的表(用数组表示)进行排序，并将排序结果存放到另一个新的表中。必须注意的是，表中所有待排序的关键码互不相同，计数排序算法针对表中的每个记录，扫描待排序的表一趟，统计表中有多少个记录的关键码比该记录的关键码小，假设针对某一个记录，统计出的计数值为c，那么，这个记录在新的有序表中的合适的存放位置即为c。
init(Q); int R=0; //R是层次序列指针，指向当前待处理的结点
2015年陕西省JAVA最新版本纲要

2015年陕西省JAVA最新版本纲要

1、两棵空二叉树或仅有根结点的二叉树相似；对非空二叉树，可判左右子树是否相似，采用递归算法。

int Similar(BiTree p,q) //判断二叉树p和q是否相似{if(p==null && q==null) return (1);else if(!p && q || p && !q) return (0);else return(Similar(p->lchild,q->lchild) && Similar(p->rchild,q->rchild)) }//结束Similar2、连通图的生成树包括图中的全部n个顶点和足以使图连通的n-1条边，最小生成树是边上权值之和最小的生成树。

故可按权值从大到小对边进行排序，然后从大到小将边删除。

每删除一条当前权值最大的边后，就去测试图是否仍连通，若不再连通，则将该边恢复。

若仍连通，继续向下删；直到剩n-1条边为止。

void SpnTree (AdjList g)//用“破圈法”求解带权连通无向图的一棵最小代价生成树。

{typedef struct {int i,j,w}node; //设顶点信息就是顶点编号，权是整型数node edge[];scanf( "%d%d",&e,&n) ; //输入边数和顶点数。

for (i=1;i<=e;i++) //输入e条边：顶点，权值。

scanf("%d%d%d" ,&edge[i].i ,&edge[i].j ,&edge[i].w);for (i=2;i<=e;i++) //按边上的权值大小，对边进行逆序排序。

{edge[0]=edge[i]; j=i-1;while (edge[j].w<edge[0].w) edge[j+1]=edge[j--];edge[j+1]=edge[0]; }//fork=1; eg=e;while (eg>=n) //破圈，直到边数e=n-1.{if (connect(k)) //删除第k条边若仍连通。

java数据结构笔试题目

java数据结构笔试题目

java数据结构笔试题目Java数据结构笔试题目⒈数组●数组的基本概念●数组的声明和初始化●数组的访问和修改●多维数组●数组的常见操作（排序、查找、插入、删除）⒉链表●链表的基本概念●链表的实现（单链表、双链表、循环链表）●链表的插入和删除●链表的反转●链表的常见操作（查找、更新、合并）⒊栈和队列●栈的基本概念和特点●栈的实现和应用●队列的基本概念和特点●队列的实现和应用●栈和队列的比较⒋树●树的基本概念和术语●二叉树的基本概念和实现●二叉树的遍历（前序、中序、后序）●二叉搜索树●平衡二叉树和红黑树⒌图●图的基本概念和术语●图的表示方法（邻接矩阵、邻接表）●图的遍历算法（深度优先搜索、广度优先搜索）●最短路径算法（Dijkstra、Floyd-Warshall）●最小树算法（Prim、Kruskal）⒍散列表●散列函数的定义和特点●散列表的基本概念和实现●冲突解决方法（开放寻址法、链表法）●散列表的性能分析和优化●哈希算法和应用⒎堆●堆的基本概念和特点●堆的实现（二叉堆、斐波那契堆）●堆的应用（优先队列、堆排序）●堆的性能分析和优化●堆与其他数据结构的联系⒏排序算法●冒泡排序●插入排序●选择排序●快速排序●归并排序●堆排序●希尔排序●桶排序和基数排序⒐搜索算法●顺序搜索●二分搜索●插值搜索●哈希搜索●广度优先搜索●深度优先搜索●A搜索算法⒑字符串匹配算法●暴力匹配算法●KMP算法●Boyer-Moore算法●Rabin-Karp算法●后缀树和后缀数组1⒈复杂度分析●时间复杂度●空间复杂度●最好、最坏和平均情况复杂度●复杂度的比较和选择●复杂度分析的实例附件：无法律名词及注释：⒈版权：著作权法所赋予作品创作者对其原创作品的独占权利。

⒉商标：商标法所保护的一种标识，用于区分和识别特定商品或服务的来源。

⒊专利：专利法所赋予的一种权利，用于保护发明者的发明创造，限制他人在专利权期限内制造、使用、销售、进口该发明。

数据结构的精髓：掌握常用数据结构的15个要点

数据结构的精髓：掌握常用数据结构的15个要点

数据结构的精髓：掌握常用数据结构的15个要点数据结构是计算机科学中的重要基础知识，它描述了数据元素之间的关系以及对这些关系进行操作的方法。

掌握常用数据结构的关键要点，将有助于我们更好地理解和应用这些数据结构，提高程序的效率和性能。

以下是常用数据结构的15个要点，它们分别是：数组、链表、栈、队列、树、二叉树、堆、图、哈希表、集合、树状数组、字典树、并查集、线段树和红黑树。

1.数组：数组是由相同类型的元素组成的集合，使用连续的内存地址进行存储和访问。

数组的要点包括访问任意位置的时间复杂度为O(1)，插入和删除元素的时间复杂度较高为O(n)。

2.链表：链表通过节点之间的指针连接来存储数据，可以实现动态存储和删除数据元素。

链表的要点包括插入和删除元素的时间复杂度为O(1)，访问任意位置的时间复杂度较高为O(n)。

3.栈：栈是一种后进先出（LIFO）的数据结构，只允许在栈顶进行插入和删除操作。

栈的要点包括插入和删除元素的时间复杂度为O(1)，只能访问栈顶元素。

4.队列：队列是一种先进先出（FIFO）的数据结构，允许在队尾插入元素，在队头删除元素。

队列的要点包括插入和删除元素的时间复杂度为O(1)，只能访问队头和队尾元素。

5.树：树是一种非线性数据结构，由节点和边组成。

树的要点包括节点之间存在唯一的一对多关系，节点之间通过边相连，树的深度为根节点到叶子节点的最长路径。

6.二叉树：二叉树是一种特殊的树结构，每个节点最多有两个子节点。

二叉树的要点包括左子树和右子树的顺序不可颠倒，可以为空树。

7.堆：堆是一种特殊的二叉树结构，一般指的是二叉堆。

二叉堆的要点包括堆的顶部元素为最小值或最大值，插入和删除操作的时间复杂度为O(log n)。

8.图：图是一种非线性数据结构，由节点和边组成。

图的要点包括节点之间存在多对多关系，边可以有权重，可以是有向的或无向的。

9.哈希表：哈希表是一种基于哈希函数的数据结构，用于存储键值对。