tceic.com
简单学习网 让学习变简单
当前位置:首页 >> 学科竞赛 >>

奥赛数据结构题汇总


数据结构练习一
一、单项选择题 1.若某链表中最常用的操作是在最后一个结点之后插入一个结点和删除最后一个结点,则 采用 存储方式最节省运算时间。 (1)单链表 (2)双链表 (3)单循环链表 (4)带头结点的双循环链表 2.设一个栈的输入序列为 A,B,C,D,则借助一个栈所得到的输出序列不可能是 (1)A,B,C,D (2)D,C,B,A (3)A,C,D,B (4)

D,A,B,C 3.串是 。 (1)不少于一个字母的序列 (2)任意个字母的序列 (3)不少于一个字符的序列 (4)有限个字符的序列 4.链表不具有的特点是 。 (1)可随机访问任一元素 (2)插入删除不需要移动元素 (3)不必事先估计存储空间 (4)所需空间与线性表长度成正比 5.在有 n 个叶子结点的哈夫曼树中,其结点总数为 。 (1)不确定 (2)2n (3)2n+1 (4)2n-1 6.任何一个无向连通图的最小生成树 (1)只有一棵 (2)有一棵或多棵 (3)一定有多棵 (4)可能不存在 7. 将一棵有 100 个结点的完全二叉树从根这一层开始, 每一层上从左到右依次对结点进行编 号,根结点的编号为 1,则编号为 49 的结点的左孩子编号为 。 (1)98 (2)99 (3)50 (4)48 8.下列序列中, 是执行第一趟快速排序后得到的序列(排序的关键字类型是字 符串)。 (1)[da,ax,eb,de,bb]ff[ha,gc] (2)[cd,eb,ax,da]ff[ha,gc,bb] (3)[gc,ax,eb,cd,bb]ff[da,ha] (4)[ax,bb,cd,da]ff[eb,gc,ha] 9.用 n 个键值构造一棵二叉排序树,最低高度为 。 (1)n/2 (2)n (3)[log2n] (4)[log2n+1] 10.二分查找法要求查找表中各元素的键值必须是 排列。 (1)递增或递减 (2)递增 (3)递减 (4)无序 11.对于键值序列(12,13,11,18,60,15,7,18,25,100),用筛选法建堆,必须从键值 为 的结点开始。 (1)100 (2)12 (3)60 (4)15 三、填空题 1.在带有头结点的单链表 L 中,第一个元素结点的指针是 。 2.在双循环链表中,在指针 P 所指结点前插入指针 S 所指的结点,需执行下列语句: S↑.next:= P; S↑.prior:= P↑.prior; P↑.prior:= S; := S; 3.[1..maxsize]为一个顺序存储的栈,变量 top 指示栈顶位置,栈为空的条件是 , 栈为满的条件是 。 A 4.具有 100 个结点的完全二叉树的深度为 。 /\ 5.有向图 G 用邻接矩阵 A[1. .n,1..n]存储,其第 i 行的所有元素之和 B C 等于顶点 i 的 。 /\ \ 6. 在顺序文件中, 要存取第 i 个记录, 必须先存取 。 D E F / H
1

7.对于下面的二叉树,按中序遍历所得到的结点序列为 。 8.分别采用堆排序、快速排序、插入排序和归并排序算法对初始状态为递增序列的表按递增 顺序排序,最省时间的是 算法,最费时间的是 算法。 9.对下图所示的网,执行 prim 算法可得到最小生成树,试在下表的空白处填上括当的内容, 以说明该算法的执行过程。 顶点 1 3 (2,3) 4 (2,3) 4 (3,1) 1 4 (2,4) 2 U {2} {2,4} {2,3,4} {2,3,4,1} V {1,3,4} {1,3} {1}

(U,V) (2,1) 代价 ∞ (U,V) 代价 (U,V) 代价 (U,V) 代价

10.设散列函数为 H(key) ,用拉链(链地址)法解决冲突,H 的值域为 0,?,n-1,构造的 散列表类型如下: TYPE link = ↑node; Node = RECORD key:keytype; next:link; ? END; Openhash = array[0. .n-1] of link; 请在下列算法划线处填上适当内容, 以完成在散列表 HP 中查找键值等于 K 的结点, 若查 找成功,返回该结点的指针,否则返回空指针。 Function research(K:keytype;HP:openhash):link; BEGIN I:= H(K);SUC:= false; ; while(P<>NIL)and(not suc)do if P↑.key<>K then else suc:= true; return(P) END 四、应用题 1.已知二叉树的后序和中序序列如下,构造出该二叉树。 后序序列: ABCDEFG 中序序列:ACBGEDF 2.有一组关键码序列(38,19,65,13,97,49,41,95,1,73),采用冒泡排序方法由小 到大进行排序,请写出每趟的结果。
2

3.设图 G=(V,E),V={1,2,3,4,5,6},E={<1,2>,<1,3>,<2,5>,<3,6>,<6,5>, <5,4>,<6,4>}。请写出图 G 中顶点的所有拓扑序列。 4.设散列函数为 H(K)= K mod 7,闭散列表的地址空间为 0,?,6,开始时散列表为空,用 线性探测法解决冲突,请画出依次插入键值 23,14,9,6,30,12,18 后的散列表。 5.对下面两棵二叉树,分别画出它们的顺序存储结构。 A /\ B C /\ /\ D E F G /\ / I J K A /\ B C /\ \ D E F /\ I J

6.已知图 G 的邻接表如下,画出图 G 的所有连通分量。

数据结构练习二
一、选择题 1.在下列备选答案中选出一个正确的,将其号码填在“ ”上。 1.若线性表最常用的操作是存取第 i 个元素及其前趋的值,则采用 存储 方式节省时间。 a.单链表 b.双链我 c.单循环链表 d.顺序表 2.对二叉树从 1 开始进行连续编号,要求每个结点的编号大于其左右孩子的编号,同一 个结点的左右孩子中, 其左孩子的编号小于其右孩子的编号, 则可采用 次 序的遍历实现编号。 a.先序 b.中序 c.后序 d.从根开始的层次遍历 3.某二叉树的先序序列和后序序列正好相反,则该二叉树一定是 的二叉树。 a.空或只有一个结点 b.高度等于其结点数 c.任一结点无左孩子 d.任一结点无右孩子 4. 下列排序算法中, 时间复杂度不受数据初始状态影响, 恒为 O(nlogzn)的是 。 a.堆排序 b.冒泡排序 c.直接选择排序 d.快速排序

3

5.下列排序算法中, 算法可能会出现下面情况:初始数据有序时,花费 的时间反而最多。 a.堆排序 b.冒泡排序 c.快速排序 d.SHELL 排序 三、填空 1. 在单链表中,删除指针 P 所指结点的后继结点的语句是 。 2. 取出广义表 A:((x,y,2),(a,b,c,d))中原子 b 的函数是 。 3. 已知完全-y.树的第八层有 8 个结点,则其叶子结点数是 。 4. 将下三角矩阵 A[1. .8,L.8]的下三角部分逐行地存储到起始地址为 1000 的内存单 元中,已知每个元素占 4 个单元,则 A[?,5]的地址为 。 5. 有 n 个顶点的强连通有向图 G 至少有 条弧。 6. 求最短路径的 DIJKSTRA 算法的时间复杂度为 。 7. 高度为 5 的三阶 B 树至少有 个结点。 8. 在有序表 A[1..20]中,采用二分查找算法查找元素值等于 A[12]的元素,所比较过 的元素的下标依次为 。 9. 直接选择排序算法所执行的元素交换次数最多为 。 10.下列排序算法中, 稳定的排序算法是 (选择排序, 堆排序, 快速排序, 直接插入排序)。 四、解答下列各题(30 分) 1.一棵二叉树的先序序列和中序序列分别如下,画出该二叉树。(5 分) 先序序列 ABCDEFGHIJ 中序序列 CBEDAGHFJl 2.对下面给出的数据序列,构造一棵哈夫曼树,并求出其带权路径长度。(6 分) 4, 5, 6, 7, 10, 12, 15, 18, 23 3.图 G 的邻接表如下页,完成下列各题:(7 分) (1)画出从顶点 5 出发进行广度遍历所生成的生成树。 (2)判断其中是否存在有向回路,若不存在,求出其拓扑序列。 4.对下列数据表,写出采用快速排序算法排序的每一趟的结果。(6 分) (60,20,3l,1,5,44,55,61,200,30,80,150,4,29)

4

5.已知哈希表地址空间为 0..8, 哈希函数为 H(k)=k mod 7, 采用线性探查法处理冲突。 将下面数据序列依次存入该散列表中,并求出在等概率下的平均查找长度。 (6 分) 100,20,21,35,3,78,99,45 0 1 2 3 4 5 6 7 8 A: 五、算法设计(共 30 分) 1.已知单循环链表 L 中至少有两个结点,每个结点的两个字段为 data 和 next,其中字 段 data 的类型为整型。 设计算法以判断该链表中的每个元素的值是否小于其后续两个结点的 值的和,若满足,返回 true,否则返回 false。(8 分) 2.设计算法按后序次序打印二叉树 T 中所有叶子结点的值,并返回其结点数。 (8 分) 3.写出在二叉排序树中查找值为 x 的元素的算法。(6 分) 4.设计算法按层次遍历二叉树 T。(8 分)

模拟试卷三
一、选择题(每小题 2 分,共 20 分), 在下列备选答案中选出一个正确的,将其号码填在“ ”上。 1. 一 个 栈 的 输 入 序 列 为 1 2 3 4 5 , 则 下 列 序 列 中 不 可 能 是 栈 的 输 出 序 列 的 是 。 a.2 3 4 1 5 b.5 4 1 3 2 c.2 3 1 4 5 d.1 5 4 3 2
5

2.设循环队列中数组的下标范围是 l~n,其头尾指针分别为 f 和 r,则其元素个数为 。 a. r-f b。r-f+1 c.(r-f)mod n+l d.(r-f+n) mod n 3.若某链表最常用的操作是在最后一个结点之后插入一个结点和删除最后一个结点,则 采用 存储方式最节省时间。 a.单链表 b.双链表 c.带头结点的双循环链表 d.单循环链表 4. 一棵非空的二叉树的先序序列和后序序列正好相反, 则该二叉树一定满足 。 a.其中任意一结点均无左孩子 b.其中任意一结点均无右孩子 c.其中只有一个叶子结点 d.是任意一棵-y.树 5.一棵左右子树均不空的二叉树在先序线索化后,其空指针域数为 。 a.0 b.1 c.2 d.不确定 6.数组 A[l..5,1..6]的每个元素占 5 个单元,将其按行优先次序存储在起始地址为 lOOO 的连续的内存单元中,则元素 A[5,5]的地址为 。 a.1140 b.1145 c.1120 d.1125 7.求最短路径的 DIJKSTRA 算法的时间复杂度为 。 2 a.O(n) b.O(n+e) c.O(n ) d.O(n*e) 8.对有 18 个元素的有序表作二分查找,则查找 A[3]的比较序列的下标为 。 a.1,2,3 b.9,5,2,3 c.9,5,3 d.9,4,2,3 9.快速排序算法在最好情况下的时间复杂度为 。 2 a.O(n) b.O(nlog2n) c.O(n ) d.O(1Og2n) 10 . 下 列 排 序 算 法 中 , 某 一 趟 结 束 后 未 必 能 选 出 一 个 元 素 放 在 其 最 终 位 置 上 的 是 。 a.堆排序 b.冒泡排序 c.快速排序 d.直接插入排序 二、判断题(每小题 1 分,共 10 分) 判断下列各题是否正确,若正确,在()内打“√” ,否则打“×” 。 1. ( )线性表的长度是线性表所占用的存储空间的大小。 2. ( )双循环链表中,任意一结点的后继指针均指向其逻辑后继。 3. ( )在对链队列做出队操作时,不会改变 front 指针的值。 4. ( )如果两个串含有相同的字符,则说它们相等。 5. ( )如果二叉树中某结点的度为 1,则说该结点只有一棵子树。 6. ( )已知一棵树的先序序列和后序序列,一定能构造出该树。 7. ( )图 G 的一棵最小代价生成树的代价未必小于 G 的其他任何一棵生成树的代价。 8. ( )图 G 的拓扑序列唯一,则其弧数必为 n 一 1(其中 n 为 G 的顶点数)。 9. ( )对一个堆按层次遍历,不一定能得到一个有序序列。 2 10. ( )直接选择排序算法满足:其时间复杂度不受数据的初始特性影响,为 O(n )。 三、填空(每小题 2 分,共 20 分) 1. 在双循环链表 L 中,指针 P 所指结点为尾结点的条件是 。 2. 在单链表中,删除指针 P 所指结点的后继结点的语句是 。 3. 队列的特性是 。 4. 若某串的长度小于一个常数,则采用 存储方式最节省空间。 5. 在有 n 个叶子结点的哈夫曼树中,总结点数是 。 6. 一棵树 T 采用二叉链表 BT 存储, 如果树 T 中某结点为叶子结点, 则在二叉链表 BT 中所对应的结点一定满足 。

6

7. 高度为 K 的 2 - 3 树的结点数至少是 。 8. 在有 n 个结点的无向图中,其边数最多为 。 9. 取出广义表 A=(x,(a,b,c,d))中原子 b 的函数是 10. 对矩阵采用压缩存储是为了 。 四、解答下列各题(20 分) 1.分别画出满足下列条件的所有二叉树。(4 分) (1)先序序列和中序序列均为 ABCDE。 (2)先序序列为 ABCDE,并且与其相对应的树的高度为 5。 2.对下面 3 阶 B 树依次执行下列操作,画出每步的操作结果。(6 分) (1) 插入 300



(2)插入 70 (3)插入 30 (4)删除 150 3.对下列数据表,写出采用 SHELL 排序算法排序的每一趟的结果。(5 分) (100,12,20,31,1,5,44,66,61,200,30,80,150,4,8) 4.求出下面 AOE 网中的关键路径(要求标明每个顶点的最早和最迟发生时间,并画出关 键路径)。(5 分)

五、算法设计(共 30 分) 1.设计算法求中序线索二叉树中指针 P 所指结点的后继结点的指针。(6 分) 2. 设计算法以判断二叉树 T 是否为二叉排序树(设 T 中任意两个结点的值均不相等)。 (8 分) 3.设计算法将一个带有头结点的单循环链表 A 分解为两个具有相同结构的链表 B,C,

7

其中 B 表中结点为 A 表中值为奇数的结点, 而 C 表中结点为 A 表中值为偶数的结点(要求利用 原表结点)。(8 分) 4.设计算法以判断无向图 G 是否是连通的,若连通则返回 true,否则返回 false。 (注:可以使用以下几个函数调用; firstadj(G,v)——返回图 G 中顶点 v 的第一个邻接点,若不存在则返回 0; nextadj(G,v,w)——返回图 G 中顶点 v 的邻接点中处于 w 之后的邻接点,若不存 在则返回 0; nodes(G)——返回图 G 中的顶点数) (8 分)

模拟试卷四
一、选择题(每小题 2 分,共 16 分) 在下列备选答案中选出一个正确的,将其号码填在“ ”上。 1.一个栈的输入序列为 1 2 3 4 5,则下列序列中是栈的输出序列的是 。 a. 2 3 4 1 5 b. 5 4 1 3 2 c. 3 1 2 4 5 d. 1 4 2 5 3 2. 若某线性表最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素, 则 采用下列 存储方式最节省时间。 a.单链表 b.双链表 c.带头结点的双循环链表 d.单循环链表 3.二叉树在线索化后,仍不能有效求解的问题是 。 a.先序线索-二叉树中求先序后继 b.中序线索二叉树中求中序后继 c.中序线索二叉树中求中序前趋 d.后序线索二叉树中求后序后继 4.求最短路径的 FLOYD 算法的时间复杂度为 。 2 3 a.O(n) b.O(n+e) c.O(n ) d.O(n ) 5.下列排序算法中,在待排序的数据表已经为有序时,花费时间反而最多的 是 。 a.快速排序 b.希尔排序 c.冒泡排序 d.堆排序 6.下列排序算法中, 每一趟都能选出一个元素放在其最终位置上,并且是不 稳定的。 a.冒泡排序 b.希尔排序 c.直接选择排序 d.直接插入排序 7.在平衡二叉树中插入一个结点后造成了不平衡,设最低的不平衡结点为 A,并已知 A 的左孩子的平衡因子为一 1,右孩子的平衡因子为 0,则应作 型调整以使其平衡。 a.LL b. LR c.RL d.RR 8.数据表 A 中有 10000 个元素,如果仅要求求出其中最大的 10 个元素,则采用 排序算法最节省时间。 a.堆排序 b.希尔排序 c.快速排序 d.直接选择排序 二、判断题(每小题 1 分,共 10 分) 判断下列各题是否正确,若正确,在()内打“√” ,否则打“X” 。 1.( )线性表的唯一存储形式是链表。 2.( )已知指针 P 指向链表 L 中的某结点,执行语句 P:=P^.next 不会删除该链 表中的结点。 3.( )在链队列中,即使不设置尾指针也能进行入队操作。 4.( )如果一个串中的所有字符均在另一串中出现,则说前者是后者的子串。

8

5.( )设与一棵树 T 所对应的二叉树为 BT,则与 T 中的叶子结点所对应的 BT 中的结 点也一定是叶子结点。 6.( )9 阶 B 树中,除根以外的任何一个非叶子结点中的关键字数目均在 5~9 之间。 7.( )任一 AOE 网中至少有一条关键路径,且是从源点到汇点的路径中最长的一条。 8.( )若图 G 的最小生成树不唯一,则 G 的边数一定多于 n-1,并且权值最小的边有 多条(其中 n 为 G 的顶点数)。 9.( )给出不同的输入序列建造二叉排序树,一定得到不同的二叉排序树。 10.( )由于希尔排序的最后一趟与直接插入排序过程相同,因此前者一定比后者花 费的时间多。 三、填空(每空 2 分,共 20 分) 1.带头结点的双循环链表 L 为空表的条件是 。 2.在双链表中,在指针 P 所指结点前面插入一个结点 S↑的语句序列是: S↑.next:= P;S↑.prior:= P↑.prior;P↑.prior = S; 。 3.对广义表 A=(x,((a,b),c,d))的运算 head(head(tail(A)))的结果是 。 4. 已知完全二叉树的第 7 层有 10 个叶子结点, 则整个二叉树的结点数最多是 。 5.有 n 个结点并且其高度为 n 的二叉树的数目是 。 6.循环队列采用数组 data[l. .n]来存储元素的值,并用 front 和 rear 分别作为其头 尾指针。为区分队列的满和空,约定:队中能够存放的元素个数最大为 n-1,也即至少有一 个元素空间不用,则在任意时刻,至少可以知道一个空的元素的下标是 。入队 时,可用语句 求出新元素在数组 data 中的下标。 7.高度为 8 的平衡二叉树的结点数至少是 。 8.在有 n 个顶点的有向图中,每个顶点的度最大可达 。 9.数组 A[l. .10,1. .10]的每个元素占 5 个单元,将其按列优先次序存储在起始地址 为 1000 的连续的内存单元中,则元素 A[5,6]的地址为 。 四、解答下列各题(26 分) 1.已知二叉树的中序序列和后序序列如下,画出该二叉树。(5 分) 中序序列为:DCEFBHGAKJLIM 后序序列为:DFECHGBKLJMIA 2.以下面数据作为叶子结点的权值构造一棵哈夫曼树,并计算出其带权路径长度。 (6 分,) {5,6,7,8,9,10,15,18,22} 3.对下面数据表,写出采用快速排序算法排序的每一趟的结果,并标明第一趟排序过程 中的数据移动情况。(5 分) (50,12,20,31,1,5,44,166,61,100,30,80,150,4,8) 4.求出下图的所有拓扑序列,并指出哪一个是拓扑排序算 法的运行结果 (设算法中搜索顶点的邻接点均是按从小到大的 次序进行的)。(5 分) 5.画出在递增有序表 A[1. .21]中进行二分查找的判定树。 (5 分) 五、算法设计(共 28 分) 1. 已知带头结点的单循环链表 L 中至少有一个元素, 设计算法判断 L 中各元素的值是否 均是其序号的两倍,若满足,返回 true,否则返回 false,同时返回该链表中的结点数。 (6 分)

9

2.已知数组 A[1. .n]的元素递增有序。设计算法以数组 A 中的元素构造一棵二叉排序 树,并使其满足平衡二叉树的条件。(8 分) 3.设计算法,打印连通图 G 中每个顶点一次且仅一次,并要求其打印次序满足条件:距 顶点 v0 近的顶点先于距离远的顶点(以边数为单位)。(8 分) 4.在下面冒泡排序算法中填入适当内容,以使该算法在发现有序时能及时停止。(6 分) procedure bubble(vara:array[1. .n] of integer); begin i:=1; repeat exchanged:=false; for j:= n downto do if a[j]<a[j-1] then begin a[j]<==>a[j-1]; {交换} end; ; until end; ;

模拟试卷五
一、选择题(20 分) 在下列备选答案中选出一个正确的,将其号码填在“ ”上。 1. 设循环队列中数组的下标范围是 1 ~ n ,头尾指针分别为 f 和 r, 则其元素个数 为 。 a.r-f b.r-f+1 c.(r - f+1)mod n d.(r-f+n)mod n 2.一个栈的输入序列为 1 2 3 4 5,则下列序列中不可能是栈的输出序列的是 。 a. 2 3 4 1 5 b. 5 4 2 3 1 c. 2 3 1 4 5 d. 1 5 4 3 2 3.用十字链表表示一个有 K 个非。元素的 mXn 的稀疏矩阵,则其总结点数为 。 a.m*n b.m*n+m+n c.K+max(m,n)+1 d.K+m+n+1 4.对矩阵压缩存储是为了 。 a.方便运算 b.节省空间 c.方便存储 d.提高运算速度 5. 一 棵 左 右 子 树 均 不 空 的 二 叉 树 在 先 序 前 趋 和 后 序 后 继 线 索 化 后 , 其 空 链 域 数 为 。 a.0 b.1 c.2 d.不确定 6.判断线索二叉树中某结点 P↑有左孩子的条件是 。 a.p<>nil b.p↑.1child<>nil c.P↑.1tag= 0 d.P↑.1tag=1 7. 在图 G 用邻接矩阵存储时, 求最短路径的 DIJKSTRA 算法的时间复杂度为 。 2 a.O(n) b.O(n+e) c.O(n ) d.O(n*e) 8.设图 G 采用邻接表存储,则拓扑徘序算法的时间夏杂度为 2 a.O(n) b.O(n+e) c.O(n ) d.O(n*e) 9.快速排序算法在最好情况下的时间复杂度为 。 2 a.O(n) b.O(n ) c.O(nlog2n) d.O(1og2n)

10

10. 下列排序算法中, 时间复杂度为 O(n1og2n)且占用额外空间最少的是 。 a.堆排序 b.冒泡排序 c.快速排序 d.SHELL 排序 二、填空(10 分) 1.双循环链表 L 中某结点 P↑为尾结点的条件是 。 2.已知二叉树中叶子数为 50,仅有一个孩子的结点数为 30,则总结点数为 。 3.高度为 K 的 m 阶 B 树至少有 个结点。 4.有 n 个顶点的连通图至少有 条边。 5.取出广义表 A:(x,(a,b,c,d))中原子 b 的函数是 。 三、解答下列题(20 分) 1.一棵二叉树的先序、中序和后序序列分别如下,其中有一部分未显示出来,试求出空 格处的内容,并画出该二叉树。(6 分) 先序: B F ICEH G 中序:D KFIA EJC 后序: K FBHJ G A 2.已知哈希表地址空间为 0. .14,哈希函数为 H(k)= k mod 13,采用线性探查法处理 冲突。将下面各数依次存入该散列表中,并求出在等概率下的平均查找长度和失败的查找长 度。(6 分) 240,29,345,189,100,20,21,35,3,208,78,99,45,350 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14

3.对下面的递归算法,要求:(8 分) (1)写出调用 p(4)的执行结果。 (2)将其转换为等价的非递归算法。 procedure p(w:integer); begin if w >O then begin write(W); p(w-1); p(w-1); end end; 四、算法设计(50 分,每题 10 分) 1.设计算法将数组 A[l. .N]按从大到小的次序进行排序,要求一旦发现有序即停止。 2.设计算法求两个带有头结点的递增单循环链表 A,B 的公共元素,并建成另一相同结 构的链表 C。要求时间尽可能少。 3.已知 T 为一棵二叉排序树。 (1)设计算法按递减次序打印各结点的值。 (2) 设计算法以产生一个序列,要求该序列满足:依次将这些元素插入到初值为 空的二叉排序树中所得的结果与原二叉排序树相同。 4.一棵树 T 采用二叉链表表示,其中指针及结点的类型说明如下: typetreelink =↑tnode; tnode = record
11

data:datatype; firstson,nextbrother:treelink;{第一个孩子和下一个兄弟} end; 设计算法按层次遍历树 t 的各结点,并给出离根结点最远的一个结点的指针。 5.设计算法判断图 G 中是否存在从顶点 Vi 到 Vj 的长度为 K 简单路径。

模拟试卷六
一、选择题(每小题 2 分,共 10 分) 在下列备选答案中选出一个正确的,将其号码填在“ ”上。 1 .若某链表最常用的操作是在最后一个结点之后插入一个结点和删除第一个结点, 则采用 存储方式最节省时间。 a.单链表 b.双链表 c.单循环链表 d.带尾指针的单循环链表 2.一棵左右子树均不空的二叉树在后序线索化后,其空指针域数为 。 a.0 b.1 c.2 d.不确定 3.数组 A[o. .5,0. .6]的每个元素占 5 个单元,将其按列优先次序存储在起始地址为 1000 的连续的内存单元中,则元素 A[5,5]的地址为 。 a.1175 b.1180 c.1205 d.1210 2 4. 下列排序算法中时间复杂度不受数据初始状态影响, 恒为 O(n )的是 。 a.堆排序 b.冒泡排序 c.直接选择排序 d.快速排序 5.下列排序算法中, 算法可能会出现下面情况:在最后一趟开始之前, 所有元素都不在其最终的位置上。 a.堆排序 b.冒泡排序 c.快速排序 d.插入排序 二、判断题(每小题 1 分,共重 0 分) 判断下列各题是否正确,若正确,在()内打"√” ,否则打“×” 。 1.( )在对链队列作出队操作时,不会改变 front 指针的值。 2.( )若一个栈的输入序列为 123. . .n,其输出序列的第一个元素为 n,则其输出序 列的每个元素 ai 一定满足 ai=n—i+1。(I=1,2,...,n) 3.( )二叉树中的叶子结点就是二叉树中没有左右子树的结点。 4.( )一棵树中的叶子结点数一定等于与其对应的二叉树中的叶子结点数。 5.( )有向图用邻接矩阵表示后,顶点 i 的入度等于邻接矩阵中第 i 列的元素个数。 6.( )有向图的邻接表和逆邻接表中的结点数一定相同。 7. ( )删除二叉排序树中一个结点, 再重新插入上去, 一定能得到原来的二叉排序树。 8.( )图 G 的拓扑序列唯一,则其弧数必为 n 一 1(其中 n 为 G 的顶点数)。 9.( )快速排序是排序算法中最快的一种。 10.( )对一个堆,无论按二叉树层次遍历还是先序遍历,都不一定能得到有序序列。 三、填空(每小题 2 分,共 20 分) 1.在双循环链表中,删除指针 P 所指结点的语句序列是 。 2.取出广义表 A=((x,(a,b,c,d)))中原子 c 的函数是 。 3.已知完全二叉树的第七层有 8 个结点,则其叶子结点数是 。 4.在有 n 个叶子结点的哈夫曼树中,总结点数是二 。 5.有 n 个顶点的有向图 G 最多有 条弧。 6.求最短路径的 FLOYD 算法的时间复杂度为 。

12

7.高度为 7 的平衡二叉树至少有 个结点。 8.在有序表 A[l. .18]中,采用二分查找算法查找元素值等于 A[7]的元素,所比较过的 元素的下标依次为 。 9.冒泡排序算法在最好情况下的元素交换次数为 。 10.已知一个待排序序列已基本有序(每个元素离其最终位置不远),则采用下面几种算 法中的 最省时间(直接选择排序,堆排序,快速排序,直接插入排序)。 四、解答下列各题(20 分) 1.一棵树的先序序列和后序序列分别如下,画出该树。(4 分) 先序序列:ABCDEFGHIJKLMN 后序序列:CDEBHIGKMLNJFA 2.对下面数据表,写出采用快速排序算法排序的每一趟的结果。(4 分) (70,12,20,31,1,5,44,66,61,200,30,80,150,4,28) 3.求出下面图中顶点 1 到其余顶点的最短路径。(4 分)

4. 对下面的递归算法,要求:(8 分) (1)写出调用 P(4)的执行结果。 (2)将其转换为等价的非递归算法, procedure p(w:integer) begin if w>0 then begin p(w-1); write(w); p(w-1) end end; 五、算法设计(共 40 分) 1.巳知一个单链表中每个结点存放一个整数,并且其结点数不少于 2。设计算法以判断 该链表中从第二项起的每个元素值是否等于其序号的平方减去其前趋的值,若满足,返回 true,否则返回 false。(8 分) 2. 设计算法求先序线索二叉树中指针 P 所指结点的先序后继结点的指针, 并通过调用该 算法来写出先序遍历先序线索二叉树的非递归算法。(8 分) 3.设计算法以求出无向图 G 的连通分量的个数。(8 分) 4.分别写出在递增有序表 A[1. .n]中采用二分查找算法查找值为 x 的元素的递归和非 递归算法。(8 分) 5.设计算法打印出二叉树 T 的先序次序下的前 K 个结点的值。(8 分)

13

模拟试卷七
一、选择题(每小属 2 分,共 10 分) 在下列备选答案中选出一个正确的,将其号码填在“ ”上。 1.若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算, 则采用 存储方式最节省时间。 a.顺序表 b.双链表 c.带头结点的双循环链表 d.单循环链表 2.在用邻接表表示图时,求最短路径的 Dijkstra 算法的时间复杂度为 。 2 3 a.O(n) b.O(n+e) c.O(n ) d.O(n ) 3 . 依次 将待 排序 序 列 中 的元 素和 有序 子序列 合 并为 一个 新的 有序子 序 列的 算法 是 。 a.快速排序 b.插入排序 c.冒泡排序 d.堆排序 4.在平衡二叉树中插入一个结点后造成了不平衡,设最低的不平衡结点为 A,并已知 A 的左孩子的平衡因子为 0,右孩子的平衡因子为 1,则应作 型调整以使其平衡。 a.LL b.LR c.RL d.RR 5. 已知数据表 A 中每个元素距其最终位置不远, 则采用 排序算法最节省时间。 a.堆排序 b.插入排序 c.快速排序 d.直接选择排序 二、判断题(每小题 1 分,共 10 分) 判断下列各题是否正确,若正确,在( )内打“√” ,否则打“×” 。 1.( )线性表就是顺序表。 2.( )链表只能借助于指针和动态变量来实现。 3.( )线性表的长度是指其中元素所占用的存储空间的字节数。 4.( )对广义表 A=(a,(b,c),d)的运算 head(tail(A))的结果不是 b。 5.( )若一棵树中某结点的度为 1,则该结点仅有一棵子树。 6.( )所谓平衡二叉树是指左右子树的高度差的绝对值不大于 l 的二叉树。 7.( )AOE 网所表示的工程至少所需的时间等于从源点到汇点的最短路径的长度。 8.( )若从某顶点开始对有向图 G 进行深度遍历,所得的遍历序列唯一,则可断定其 弧数为 n 一 1。 9.( )理想情况下,在散列表中查找一个元素的时间复杂度为 O(1)。 10.( )快速排序算法在每一趟排序中都能找到一个元素放在其最终的位置上。 三、填空(每空 2 分,共 20 分) 1.在带头结点的双循环链表 L 中,最后一个结点的指针是 。 2 .在仅有尾指针 R 指示的单循环链表 R 中,在表尾插入一个结点 S ↑的语句序列 是 。 3。已知栈的输入序列为 l,2,3, . . . ,n,输出序列为 a1,a2,?,an,a2 = n 的输出序 列共有 种输出序列。 4.已知循环队列用数组 data[l..n]存储元素值,用 f,r 分别作为头尾指针,则当前元 素个数为 。 5.在左右子树均不空的先序线索二叉树中,空链域的数目是 。 6.在二叉链表中,判断某指针 P 所指结点为叶子结点的条件是 。 7.若某二叉树有 20 个叶子结点,有 30 个结点仅有一个孩子,则该二叉树的总结点数 是 。 8.在有 n 个顶点的连通图中,其边数至少为 。 9.已知数组 A[1..10,1. .10]为对称矩阵,其中每个元素占 5 个单元。现将其下三角

14

部分按行优先次序存储在起始地址为 1000 的连续的内存单元中,则元素 A[5,6]对应的地址 为 。 10.直接选择排序算法在最好情况下所作的交换元素的次数为 。 四、解答下列各题(每小题 5 分,共 20 分) 1.已知一树的双亲表示如下, 其中各兄弟结点是依次出现的, 画出该树及对应的二叉树。 1 Data parent A 0 2 B 1 3 C 1 4 D 1 5 E 2 6 F 2 7 G 3 8 H 3 9 I 4 10 J 4 11 K 5 12 L 6 13 M 6 14 N 7 15 O 8

2.一棵二叉排序树结构如下,各结点的值从小到大依次为 1~8,请标出各结点的值。

3.对下面数据表,写出采用冒泡排序算法排序的每一趟的结果。 (25 10 20 31 5 44 16 61 100 3) 4.求出下图的一棵最小生成树。

五、算法设计(每题 8 分,共 40 分) 1.已知某类集合中的元素个数不超过 maxnum,元素类型为 integer,试选择合适的数据 结构和约定, 并写出在这种结构下求解两个集合的交集的算法(要求算法的时间复杂度为两表 长之和的数量级)。 2.设计出在递增有序的数组 A[l. .n)中查找值为 x 的元素的二分查找算法。 3.已知一棵二叉树按顺序方式存储在数组 A[1. .n]中。设计算法求出下标分别为 i 和 j 的两个结点的最近的公共祖先结点的值。 4. 已知二叉树采用二叉链表存储。 设计算法以输出二叉树 T 中从根结点到每个叶子结点 的路径。下图即为一棵二叉树及所对应的输出结果的示例(设二叉树高度不超过 max)。

15

输出结果: D: A B D H: A B E H F: A C F G: A C G

5.设计算法,以判断有向图 G 是否是一棵以 v0 为根的有向树。

模拟试卷八
一、选择题(每小题 2 分,共 10 分) 在下列备选答案中选出一个正确的,将其号码填在“ ”上。 1.一个栈的输入序列为 1 2 3 4 5,则下列序列中不可能是栈的输出序列的 是 。 (1) l 2 3 4 5 (2) 5 4 3 2 1 (3) 2 3 4 5 l (4) 4 l 2 3 5 2.一棵左子树为空的二叉树在先序线索化后,其中的空链域的个数为 。 (1)0 (2)1 (3)2 (4)不确定 3.在用邻接表表示图的情况下,拓扑排序算法的时间复杂度为 。 2 3 (1)O(n+e) (2)O(n ) (3)O(n*e) (4)O(n ) 4.下列排序算法中,在每一趟都能选出一个元素放到其最终位置上,并且其时间性能受 数据初始特性影响的是 。 (1)直接插入排序 (2)快速排序 (3)直接选择排序 (4)堆排序 5. 下列排序算法中, 依次将待排序序列中的元素和前面有序序列合并为一个新的有序序 列的排序算法是 。 (1)直接插入排序 (2)冒泡排序 (3)快速排序 (4)直接选择排序 二、判断题(每小题 1 分,共 10 分) 判断下列各题是否正确,若正确,在()内打“√” ,否则打“×” 。 1. ( )设指针 P 指向单链表中一个结点,则语句序列 U:=P^.next;U:=U^.next 将删除一个结点。 2.( )栈和队列都是运算受限的线性表。 3.( )广义表的长度是指广义表中的原子个数。 4.( )若某二叉树的叶子结点数为 1,则其先序序列和后序序列一定相反。 5.( ) 二叉树在按任一种次序线索化后,都可以很容易地求出相应次序下的前趋和 后继。 6.( )在采用线性探测法处理冲突的散列表中,所有同义词在表中相邻。 7.( )对 B 树中任一非叶子结点中的某关键字 K,比 K 小的最大关键字和比 K 大的最 小关键字一定都在叶子结点中。 8.( )若一个无向图的以顶点 1 为起点的深度遍历序列唯一,则可唯一确定该图。 9.( )在对一有向无环图执行拓扑排序算法之后,入度数组中的所有元素的值为 0。 10.( )在数据表基本有序时,冒泡排序算法的时间复杂度一定接近 O(n)。 三、填空(每小题 2 分,共 20 分) 1. 在单链表中, 在指针 P 所指结点的后面插入一个结点 S↑的语句序列是: 。

16

2.已知一个栈的输入序列为 123. . .n,则其输出序列的第二个元素为 n 的输出序列的 个数是 。 3. 取出广义表 A=((a,x,y,2),(b,c))中的原子 c 的复合函数是 。 4 .若以 {4 , 5 , 6 , 7 , 8} 作为叶子结点的权值构造哈夫曼树,则其带权路径长度 是 。 5.在顺序存储的二叉树中,编号为 i 和 j 的两个结点处在同一层的条件 是 。 6.已知二叉树有 50 个叶子结点,则该二叉树的总结点数至少是 。 7.在按关键字递增的数组 A[l..20]中,按二分查找方法进行查找时,查找长度为 5 的 元素个数是 。 8.已知数组 A[1. .10,0. .9]中每个元素占 4 个单元,在按行优先方式将其存储起始 地址为 1000 的连续的存储区域时,A[5,9]的地址是 。 9. 有 n 个球队参加的足球联赛按主客场制进行比赛, 共需进行 场比赛。 10. 下列排序算法中,占用辅助空间最多的是 。(堆排序,希尔排序,快 速排序,归并排序)。 四、解答下列各题(20 分) 1.一棵二叉树的先序、中序和后序序列如下,其中一部分未标出,请构造出该二叉树。 先序序列: CDE GHI K 中序序列:CB FA JKIG 后序序列: EFDB JIH A 2.将下面数据表建成一个堆。 (70,12,20,31,1,5,44,66,6l,200,30,86,150,4,28) 3.求出下图中顶点 1 到其余各顶点的最短路径。

4.已知下面二叉排序树的各结点的值依次为 1~9,请标出各结点的值。

五、算法设计(共 40 分,每题 8 分) 1.已知递增有序的单链表 A,B 分别存储了一个集合。设计算法以求出两个集合 A,B 的差集 A—B(即仅由在 A 中出现而不在 B 中出现的元素所构成的集合), 并以同样的形式

17

存储,同时返回该集合的元素个数。 2.设计算法以返回二叉树 T 的后序序列的第一个结点的指针。要求采用非递归形式,且 不用栈。 3. 已知二叉树 T 以二叉链表形式作为其存储结构。 设计算法按先序次序输出各结点的值 及相应的层次数, 并以二元组的形式给出。 如下面的二叉树及对应的输出如下页图所示。 (A,1)(B,2)(C,3)(D,4)(E,5)(F,3)(G,2)(H,3)(I,4)

4.已知数组 A[1..n]的元素类型为 integer。设计算法将其调整为左右两部分,使得左 边所有元素为奇数,右边所有元素为偶数,并要求算法的时间复杂度为 O(n)。 5.设计算法以判断无向图 G 是否是一棵树,若是树,返回 true,否则返回 false。

模拟试卷九
一、单项选择题(每小题 2 分,共 20 分) 在下列备选答案中选出一个正确的,将其号码填在“ ”上。 1. 某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素, 则 采用 存储方式最节省运算时间。 (1)单链表 (2)仅有头指针的单循环链表 (3)双链表 (4)仅有尾指针的单循环链表 2.串的长度是 。 (1)串中不同字母的个数 (2)串中不同字符的个数 (3)串中所含字符的个数,且大于 0 (4)串中所含字符的个数 3.若用数组 S[1. .n]作为两个栈 S1 和 S2 的共用存储结构,对任何一个栈,只有当 S[1. .n]全满时才不能作入栈操作。为这两个栈分配空间的最佳方案是 。 (1)S1 的栈底位置为 0,S2 的栈底位置为 n+1 (2)S1 的栈底位置为 0,S2 的栈底位置为 n/2 (3)Sl 的栈底位置为 1,S2 的栈底位置为 n (4)S1 的栈底位置为 1,S2 的栈底位置为 n/2 4.队列操作的原则是 。 (1)先进先出 (2)后进先出 (3)只能进行插入 (4)只能进行删除 5.有 64 个结点的完全二叉树的深度为 (根的层次为 1)。 (1)8 (2) 7 (3) 6 (4) 5

18

6.在有 n 个结点的二叉链表中,值为非空的链域的个数为 (1)n-1 (2)2n-1 (3)n+1 (4)2n+1 7.带权有向图 G 用邻接矩阵 A 存储,则顶点 i 的入度等于 A 中 (1)第 i 行非∞的元素之和 (2)第 i 列非∞的元素之和 (3)第 i 行非∞且非 0 的元素个数 (4)第 i 列非∞且非 O 的元素个数 8. 在有 n 个结点且为完全二叉树的二叉排序树中查找一个键值, 其平均比较次数的数量 级为 。 2 (1)O(n) (2)O(1og2n) (3)O(n1og2n) (4)O(n ) 9.若表 R 在排序前已按键值递增顺序排列,则 算法的比较次数最少。 (1)直接插入排序 (2)快速排序 (3)归并排序 (4)选择排序 10. 下列排序算法中, 排序在某趟结束后不一定能选出一个元素放到其 最终的位置上。 (1)选择 (2)冒泡 (3)归并 (4)堆 二、判断题(每小题 1 分,共 10 分) 判断下列各题是否正确,若正确,在( )内打“√” ,否则打“×” 。 1.( )在带头结点的单循环链表中,任一结点的后继指针均不空。 2. ( )线性表采用链表方式和顺序表方式存储, 执行插入和删除运算的时间复杂度都 是 O(n),因而两种存储方式的插入、删除运算所花费的时间相同。 3.( )在栈为空的情况下,不能作出栈操作,否则产生下溢出。 4.( )对矩阵压缩存储的方法是用三元组表存储矩阵元素。 5.( )在一个有向图的邻接表或逆邻接表中,如果某个顶点的链表为空,则该顶点的 度一定为 0。 6.( )如果有向图 G=(V,E)的拓扑序列唯一,则图中必定仅有一个顶点的入度为 0, 一个顶点的出度为 0。 7. ( )向二叉排序树中插入一个结点, 所需比较的次数可能大于此二叉排序树的高度。 8.( )在索引顺序表的查找中,对索引表既可采用顺序查找方法,也可采用二分查找 方法。 9.( )在快速排序算法中,以待排序的 n 个记录中的第一个记录的键值为基准,将所 有记录分为两组,该记录就在这两组的中间,这也是该记录的最终位置。 10.( )在一个大根堆中,最小元素不一定在最后。 三、填空题(每小题 2 分,共 24 分) 1.在单链表中,若要在指针 P 所指结点之后插入由指针 S 所指的结点,则需执行下列语 句:S↑.next:= P↑.next; ; 2.在带有头结点的双链表 L 中,指针 P 所指结点是第一个元素结点的条件 是 。 3.设 sq[1. .maxsize]为一个顺序存储的栈,变量 top 指示栈顶元素的位置。能作入栈 操作的条件是 。 如要把栈顶元素弹出并送 到 x 中,则需执行下列 语 句: 。 4.3 个结点可构成 棵不同形态的树。 5 .树 t 的存储结构为二叉链表 bt ,树 t 中的一个非叶子结点在 bt 中满足条 件 。 6 . 设 有 向 图 G 的 邻 接 矩 阵 为 A , 如 果 图 中 不 存 在 弧 <Vi , Vj> , 则 A[i , j] 的 值 为 。 7.如果含 n 个顶点的图是一个环,则它有 棵生成树。

19

8.对有 17 个元素的有序表 A[1. .17]作二分查找,在查找值等于 A[8]的元素时,被比 较的元素的下标依次为 。 9.二叉排序树的结点及指针类型如下: type bitre =↑bnode; bnode = record data:datatype; Lchild,Rchild:bitre end; 请在下面算法划线处填上适当内容,以完成在二叉排序树 t 中查找键值为 K 的结点。 function search(t:bitre;K:datatype):bitre; //在 t 中查找键值为 K 的结点,成功时返回该结点的指针,否则返回 nil// begin if t=nil then return(t) else case t↑.data = K:return(t); t↑.data>K: ; t↑.data<K: ; end end; 10. 利用直接选择排序算法对 n 个记录进行排序,最坏情况下,记录的交换次数 为 。 四、解答下列各题(共 22 分) 1.对下边的树,分别画出其孩子链表和孩子兄弟链表存储结构。(4 分) 2.已知一棵二叉树的先序序列是 ABCDEFGHIJK,中序序列是 CDBGFEAHJIK,请构造出该 二叉树。(5 分) 3.一项工程 P 由 Pl,P2,P3,P4,P5,P6 六个子工程组成,这些工程之间有下列关系: Pl>P2,P1<P3,P1<P4,P2<P3,P2>P5,P3>P6,P4>P6,P5>P6。其中符号“>”表示先 于关系,例如 P1>P3 表示只有在 P1 完成之后才能进行 P3 的工作。请给出工程 P 的四种可能 的施工顺序。(4 分) 4.设散列表的长度为 9,散列函数为 H(x)= I div 3,其中 i 为键值 x 中第一个字母在字 母表中的序号,若键值的输入序列为 Jan,Feb,Mar,Apr,May,Jun,Jul,Aug,Sep,Oct, Nov,Dec,用拉链法处理冲突,要求:(5 分) (1)构造散列表。 (2)求出在等概率情况下,查找成功时的平均查找长度。 5.采用直接插入排序算法,对关键字序列(46,32,55,81,65,11,25,43)按从小到 大的次序进行排序,写出每趟排序的结果。(4 分) 五、算法设计(共 24 分) 1. 两个链表 L1 和 L2 分别表示两个集合, 其中每个结点有两个字段, 分别为 data 和 next, 请画出这种链表的结构, 并编写算法以判断集合 Ll 是否是集合 L2 的子集, 即判断 L1 中的元 素是否都是 L2 中的元素,若成立,返回 true,否则返回 false。(8 分) 2.设一棵二叉树以二叉链表作为存储结构,其中每个结点有三个字段,分别是 Lchild, data 和 rchild,其中 data 字段的类型为 char。设计算法以求出该二叉树中 data 域的值为 大写字母的结点个数。(6 分) 3.有 n 个顶点的有向图的邻接表定义如下:

20

Vertex=1. .n; eptr=↑enode; enode=record {边或弧结点} num:vertex; {邻接点} next:eptr end; vnode=record Vinfo:datatype; {顶点信息} firstE:eptr {第一条边的指针} end; adjlist=array[vertex]of vnode; 设计算法分别实现下列要求:(10 分) (1)求出图 G 中每个顶点的出度。 (2)求出 G 中出度最大的一个顶点,输出该顶点号及其信息。 (3)计算图中出度为 0 的顶点数。 (4)判断 G 中是否存在弧<i,j>。

type

21


推荐相关:

奥赛数据结构题汇总

奥赛数据结构题汇总_学科竞赛_高中教育_教育专区。数据结构练习一一、单项选择题 1.若某链表中最常用的操作是在最后一个结点之后插入一个结点和删除最后一个结点,...


数据结构第10章 习题答案

数据结构第10章 习题答案_IT认证_资格考试/认证_教育专区。1.下列排序算法中,其中( D )是稳定的。 A. 堆排序,冒泡排序 B. 快速排序,堆排序 C. 直接选择...


课题_ACM竞赛中数据结构题目心得:分块

课题_ACM竞赛中数据结构题目心得:分块_计算机软件及应用_IT/计算机_专业资料。ACM 竞赛中数据结构题目心得:分块我在 ACM 竞赛中,一般负责决定队伍的下限:水题能...


NOIP《 数据结构》练习题及答案

NOIP《 数据结构》练习题及答案_学科竞赛_初中教育_教育专区。NOIP 数据结构复习题习题: 1.设循环队列中数组的下标范围是 1–n,其头尾指针分别为 f 和 r,则...


2015研究生数学建模竞赛B题

2015研究生数学建模竞赛B题_研究生入学考试_高等教育_教育专区。数据的多流形结构分析我们已经进入了一个信息爆炸的时代,海量的数据不断产生, 迫切需要对这 些大...


信息学奥赛数据结构知识点归纳最新背诵版

信息学奥赛数据结构知识点归纳最新背诵版_IT/计算机_专业资料。信息学奥赛 信息学奥赛数据结构知识点归纳 数据结构知识点归纳数据结构的定义:数据在计算机中的组织。...


数据结构应用题四种

数据结构应用题四种_学科竞赛_小学教育_教育专区 暂无评价|0人阅读|0次下载|举报文档 数据结构应用题四种_学科竞赛_小学教育_教育专区。...


信息学奥赛数据结构教程PASCAL版

信息学奥赛数据结构教程 PASCAL 版 第二课 堆栈和队列一、堆栈 1.概述 栈(...[问题分析] 看到这道题, 许多人都马上判断出穷举是不可行的,因为数据都是以...


信息学奥赛中的特殊数据结构——并查集

信息学奥赛中的特殊数据结构——并查集 在一些有 N 个元素的集合应用问题中,我们...这一类问题近几年来反复出现在信息学的国际国内赛题中,其特点是看似并不 复杂...


信息竞赛复习资料4--数据结构(NOIP)

信息学奥赛数据结构 20页 2财富值 数据结构 75页 免费 ACM算法模板(吉林大学)...练习题: 1.约瑟夫问题: 12 p<>nil do 有 M 个猴子围成一圈,每个有一个...

网站首页 | 网站地图
All rights reserved Powered by 简单学习网 www.tceic.com
copyright ©right 2010-2021。
文档资料库内容来自网络,如有侵犯请联系客服。zhit325@126.com