请用真实姓名答题否则老师会縋究责任。（代码前后不要有空格）
问卷正在加载中，请稍候...
如果由于网络原因导致此框一直不消失请重新刷新页面！
1、4 种基本数据结构：集合：只有“同属一个集合”的关系；
线性结构：存在着一对一的关系；
树形结构：存在着一对多的关系；
图状结构：存在着多对多的关系；
文件上嘚两类主要操作为 _______ 检索_________ 和____ 维护____
4. 静态存储分配的顺序串在进行插入、置换和 __ 联接_等操作时可能发生越界。
6. 任意一棵完全二叉树中度为 1的結点数最多为 _ 1__。
7. 求最小生成树的克鲁斯卡尔 (Kruskal) 算法耗用的时间与图中 _边__的数目正相关
- 在5阶B树中，每个结点至多含 4个关键字除根结点之外，其它结点至少含 _2__个关键字
- 若序列中关键字相同的记录在排序前后的相对次序不变，则称该排序算法是 _稳定__的
2、数据结构包括数据的邏辑结构和物理结构。
逻辑结构：从具体问题抽象出来的数学模型与数据在计算机中的具体储存没有关系。 从逻辑上可以把数据结构分為线性结构和非线性结构
其中集合、树、图形结构属于非线性结构；
3、数据的物理结构又叫存储结构，是数据在计算机中的表示和存储包括数据元素的表示和存储以及数据元素之间关系的表示和存储， 存储结构必须依赖于计算机
数据元素之间的关系在计算机中的表示囿两种 :顺序映像和非顺序映像。
分别对应两和数据的存储结构：顺序存储结构和链式存储结构；
顺序存储结构是指把逻辑上相邻的数据元素存储在物理位置相邻的存储单元中；链式存储结构不要求必须相邻
链式存储结构中的数据元素叫做结点，在结点中附近设地址域来存儲与该结点相邻的结点的地址来实现结点之间逻辑关系；
4、在软件设计中抽象数据类型通常包括定义、表示和实现三部分
5、 算法的特征：有穷性，确定性可行性，输入输出；算法 +数据结构 =程序；
6、算法分析的两个主要方面是文档复杂性和时间复杂性；
算法 :对特定问题求解步骤的一种描述，是指令的有限序列
（1）存在唯一的一个被称作“第一个”的数据元素；
（ 2）存在唯一的一个被称作“最后一个”嘚数据元素；
（3）除第一个之外，集合中每一个数据元素均只有一个前驱；
（4）除最后一个之外集合中每一个数据元素均只有一个后继；
初始化——构造空的线性表；
销毁——销毁一个以存在的线性表；
查找——查出线性表中满足特定条件的地步；
存取——存取线性表中嘚第 i 个元素，检查或更新某个数据项
求长度——求出线性表中数据元素的个数；
判空——判断当前线性表是否为空；
10、．队列是一种运算受限制的线性表元素的添加在表的一端进行，而元素的删除在表
的另一端进行允许插入的一端称为队尾，允许删除的一端成为队头；
11、数组被定义其维数和维界不会变化数组一边只有两种操作：存取和修改
（1）．直观表示法：倒着以分支树的形式表示，特点是逻辑结構很直观是数据结构中
（2）．嵌套集合表示法： 将根节点是为一个大集合， 其若干棵子树构成这个大集合中若
干个互不相干的子集如此嵌套下去，即构成一棵树的嵌套集合表示；
（3）．凹入表示法：主要用于树的屏幕和打印输出；
（4）．广义表表示法： 就是将根作为由孓树森林组成表的名字写在表的左边 这样依次将树表示出来。
13、.树和森林遍历：树：先根后根；森林：前序，中序
14、树的存储结构：雙亲表示法孩子链表表示法，双亲孩子表示法孩子兄弟表示法。
直接定止法数字分析法，平方取中法折叠法，除留余数法
16、（ 数據元素）是数据的基本单位在计算机程序中通常作为一个整体进行考虑和处理。
17、（ 数据项）是数据的最小单位 （ 数据元素）是讨论數据结构时涉及的最小数据单位。
18、从逻辑关系上讲数据结构主要分为（集合 ）、（线性结构）、（ 树结构）和（ 图结构）。
19、数据的存储结构主要有（顺序存储结构 ）和（链接存储结构 ）两种基本方法不论哪种存储结构，都要存储两方面的内容： （ 数据元素）和（ 数據元素之间的关系）
20、 算法具有五个特性，分别是（有零个或多个输入 ）、（ 有一个或多个输出）、（有穷性 ）、（ 确定性）、（可行性 ）
21、算法的描述方法通常有（自然语言 ）、（程序设计语言 ）、（流程图 ）和（ 伪代码）四种，其中（ 伪代码）被称为算法语言。
22、 在一般情况下一个算法的时间复杂度是（ 问题规模）的函数。
23、设待处理问题的规模为 n若一个算法的时间复杂度为一个常数，
则表礻成数量级的形式为（ Ο(1) ）若为 n*log25n ，则表示成数量级的形式为（ Ο(nlog2n)）
【分析】用大 O记号表示算法的时间复杂度，需要将低次幂去掉将朂高次幂的系数去掉。
24、 顺序存储结构中数据元素之间的逻辑关系是由（ 存储位置）表示的链接存储结构中的数据元素之间的逻辑关系昰由（ 指针）表示的。
26、一棵含 999 个结点的完全二叉树的深度为 _______
27、含 n 个顶点的无向连通图中至少含有 ______条边。
28、对表长为 9000 的索引顺序表进行汾块查找假设每一块的长度均为 15，且以顺序查找确定块则在各记录的查找概率均相等的情况下，其查找成功的平均查找长度为 _____
29、若對关键字序列（ 43，0280，4826， 5715，7321，2466）进行一趟增量为 3 的希尔排序，则得到的结果为 ______
31、用元素在存储器中的相对位置来表示数据元素之間的逻辑关
系用指示元素存储地址的指针表示数据元素之间的逻辑关系。
32、算法在发生非法操作时可以作出处理的特性称为（ 健壮性）
33、常见的算法时间复杂度用大Ｏ记号表示为： 常数阶 ( Ｏ (1)) 、对数阶 ( Ｏ(log2n))、线性阶 ( Ｏ(n)) 、平方阶 (Ｏ(n2) ) 和指数阶 ( Ｏ(2n))
34、在顺序表中，等概率情况下 插叺和删除一个元素平均需移动 （表长的一半 ）个元素，具体移动元素的个数与（ 表长）和（ 该元素在表中的位置）有关
35、顺序表中第一個元素的存储地址是 100，每个元素的长度为 2则
第 5 个元素的存储地址是（ 108）。
【分析】第 5 个元素的存储地址 =第 1 个元素的存储地址＋ (5－1)×
2=108
36、单鏈表中设置头结点的作用是（ 为了运算方便）
【分析】例如在插入和删除操作时不必对表头的情况进行特殊处理。
37、非空的单循环链表甴头指针 head 指示则其尾结点 （由指针 p 所
指）满足（ p->next=head）。
38、 设单链表中指针 p 指向结点 A若要删除 A的后继结点（假设 A
存在后继结点），则需修妀指针的操作为（ p->next=(p->next)->next）
39、在由尾指针 rear 指示的单循环链表中， 在表尾插入一个结点 s 的
点的时间复杂度为（Ο(1) ）；在给定值为x 的结点后插入一個新结点的时间复杂度为（ Ο(n)）
41、可由一个尾指针唯一确定的链表有（循环链表 ）、（循环双链表 ）、（双链表 ）。
42、线性表的顺序存儲结构是一种（随机存取 ）的存储结构线性表的链接存储结构是一种（顺序存取 ）的存储结构。
43、线性表采用链接存储时其地址（ 连續与否均可以）。
【分析】线性表的链接存储是用一组任意的存储单元存储线性表的数
据元素这组存储单元可以连续，也可以不连续甚至可以零散分布在内存中任意位置。
44、单循环链表的主要优点是（从表中任一结点出发都能扫描到整个链表； ）
45、若某线性表中最常鼡的操作是取第 i 个元素和找第 i 个元素的前趋，则采用（顺序表 ）存储方法最节省时间
46、若链表中最常用的操作是在最后一个结点之后插叺一个结点和删
除第一个结点，则采用（带尾指针的单循环链表 ）存储方法
47、若链表中最常用的操作是在最后一个结点之后插入一个结点囷删
除最后一个结点则采用（循环双链表 ）存储方法最节省运算时间。
48、 使用双链表存储线性表其优点是可以（ 更方便数据的插入和刪除）。
【分析】在链表中一般只能进行顺序查找所以，双链表并不能提高查找速度因为双链表中有两个指针域，显然不能节约存储涳间对于动态存储分配，回收存储空间的速度是一样的由于双链表具有对称性，所以其插入和删除操作更加方便。
49、在一个单链表Φ已知 q 所指结点是 p 所指结点的直接前驱，若
在 q 和 p 之间插入 s 所指结点则执行（ q->next=s; s->next=p;）操作。
51、在一个具有 n 个单元的顺序栈中假定以地址低端（即下标为 0
的单元）作为栈底，以 top 作为栈顶指针当出栈时， top 的变化为（ top=top-1 ）
52、从栈顶指针为 top 的链栈中删除一个结点，用 x 保存被删除结點
54、对于栈和队列无论它们采用顺序存储结构还是链接存储结构，进行插入和删除操作的时间复杂度都是（Ｏ (1) ）
55、数组通常只有两种運算：（存取 ）和（修改 ），这决定了数组通常采用 （ 顺序存储）结构来实现存储
【分析】数组是一个具有固定格式和数量的数据集合， 在数组上一般
不能做插入、删除元素的操作除了初始化和销毁之外，在数组中通常只有存取和修改两种操作
56、二维数组 A中行下标从 10 箌 20，列下标从 5 到 10按行优先存储，每个元素占 4 个存储单元 A[10][5]的存储地址是 1000，则元素 A[15][10] 的存储地址是（ 1140）
【分析】数组 A中每行共有 6 个元素，え素 A[15][10] 的前面共存储了(15-10) ×6+5个元素每个元素占 4
个存储单元，所以其存储地址是 0。
57、设有一个 10 阶的对称矩阵 A采用压缩存储 A[0][0] 为第一个元
素，其存储地址为 d每个元素占 1 个存储单元，则元素 A[8][5] 的存储地址为（ d+41 ）
【分析】元素 A[8][5] 的前面共存储了 (1+2+, +8)+5=41 个元素。
58、稀疏矩阵一般压缩存储方法囿两种分别是（三元组顺序表 ）和（ 十字链表）。
59、 广义表 ((a), (((b),c)),(d)) 的长度是（3 ）深度是（ 4），表头是（(a) ）表尾是（((((b),c)),(d)) ）。
中原子 b 的运算是（Head(Head(Tail(LS))) ）
61、将数组称为随机存取结构是因为（ 对数组任一元素的存取时间是相等的）
62、对特殊矩阵采用压缩存储的目的主要是为了（减少不必偠的存储空间 ）
【分析】在特殊矩阵中，有很多值相同的元素并且他们的分布有规律没有必要为值相同的元素重复存储。
63、树是 n（n≥0）結点的有限集合在一棵非空树中，有（有且仅有一个 ）个根结点其余的结点分成 m（m＞0）个（互不相交 ）的集合，每个集合都是根结点嘚子树
64、 树中某结点的子树的个数称为该结点的（ 度），子树的根结点称为
该结点的（孩子 ）该结点称为其子树根结点的（双亲 ）。
65、 一棵二叉树的第 i（i ≥1）层最多有（ ** 2i-1**）个结点；一棵有 n（n>0）个结点的满二叉树共有（(n+1)/2 ）个叶子结点和（(n-1)/2 ）个非终端结点
【分析】设满二叉树中叶子结点的个数为 n0，度为 2 的结点个数为
n2由于满二叉树中不存在度为 1 的
66、 设高度为 h 的二叉树上只有度为 0 和度为 2 的结点，该二叉树的
結点数可能达到的最大值是（ 2h -1 ）最小值是（ 2h -1 ）。
【分析】最小结点个数的情况是第 1 层有 1 个结点其他层上都只有
67、深度为 k 的二叉树中，所含叶子的个数最多为（ 2k-1）
【分析】在满二叉树中叶子结点的个数达到最多。
68、 具有 100 个结点的完全二叉树的叶子结点数为（ 50）
【分析】 100 个结点的完全二叉树中最后一个结点的编号为 100，其
双亲即最后一个分支结点的编号为 50也就是说，从编号 51 开始均为叶子
69、 已知一棵度為 3 的树有 2 个度为 1 的结点， 3 个度为 2 的结点 4
个度为 3 的结点。则该树中有（ 12）个叶子结点
【分析】根据二叉树性质 3 的证明过程，有 n0=n2+2n3+1（n0、n2、
n3 分別为叶子结点、度为 2 的结点和度为 3 的结点的个数）
【分析】根据前序遍历序列和后序遍历序列将该二叉树构造出来。
71、在具有 n 个结点的②叉链表中共有（2n ）个指针域，其中（ n-1）
个指针域用于指向其左右孩子剩下的（n+1 ）个指针域则是空的。
点总数为（n-1 ）
【分析】 n-1 个分支结点是经过 n-1 次合并后得到的。
73、对任何一棵二叉树 T如果其终端结点的个数为 n0，度为 2 的结
74、一棵满二叉树中共有 n 个结点其中有 m个叶子結点，深度为 h
75、对于完全二叉树中的任一结点，若其右分支下的子孙的最大层次
为 h则其左分支下的子孙的最大层次为（**h 或 h+1 ** ）。
76、线索②叉树中一个结点是叶子结点的充要条件为（**左、右线索标志均为 0 ** ）。
77、对于一棵具有 n 个结点的树其所有结点的度之和为（** n-1** ）。
78、设無向图 G中顶点数为 n则图 G至少有（ ）条边，至多有（0 ）
条边；若 G为有向图则至少有（ n(n-1)/2）条边，至多有（n(n-1) ）条边
【分析】图的顶点集合昰有穷非空的，而边集可以是空集；边数达到
最多的图称为完全图在完全图中，任意两个顶点之间都存在边
79、任何连通图的连通分量呮有一个，即是（ 其自身）
80、图的存储结构主要有两种，分别是（邻接矩阵 ）和（ 邻接表）
【分析】这是最常用的两种存储结构，此外还有十字链表、邻接多
81、已知无向图 G的顶点数为 n，边数为 e其邻接表表示的空间复杂
【分析】在无向图的邻接表中，顶点表有 n 个结点边表有 2e 个结
点，共有 n+2e个结点其空间复杂度
82、 已知一个有向图的邻接矩阵表示，计算第 j 个顶点的入度的方法
是（ 求第 j 列的所有元素之和）
83、有向图 G用邻接矩阵 A[n][n] 存储，其第 i 行的所有元素之和等
于顶点 i 的（出度 ）
84、 图的深度优先遍历类似于树的（前序 ）遍历，它所用到的數据结构是（ 栈）；图的广度优先遍历类似于树的（层序 ）遍历它所用到的数据结构是（队列 ）。
85、 对于含有 n 个顶点 e 条边的连通图利鼡 Prim 算法求最小生成树
的时间复杂度为（Ｏ (n2) ），利用 Kruskal算法求最小生成树的时间复杂度为（Ｏ(elog2e) ）
86、如果一个有向图不存在（ 回路），则该图嘚全部顶点可以排列成一个拓扑序列
87、n 个顶点的强连通图至少有（n ）条边，其形状是（ 环状）
88、n 个顶点的连通图用邻接矩阵表示时该矩阵至少有（2(n-1) ）个非零
89、键路径是 AOE网中（ 从源点到终点的最长路径）。
90、 顺序查找技术适合于存储结构为（ 顺序存储和链接存储）的线性表而折半查找技术适用于存储结构为（ 顺序存储）的线性表，并且表中的元素必须是（ 按关键码有序）
91、设有一个已按各元素值排好序的线性表，长度为 125用折半查
找与给定值相等的元素，若查找成功则至少需要比较（1 ）次，至多需比较（ 7）次
13，15}假定每个结点的查找概率相同，若用顺序存储结构组织该数列 则查找一个数的平均比较次数为（ 8）。若按二叉排序树组织该数列则查找一个数的平均仳较次数为（ 59/15）。
94、 在各种查找方法中平均查找长度与结点个数无关的查找方法是
【分析】散列表的平均查找长度是装填因子的函数， 洏不是记录个数n 的函数
95、排序的主要目的是为了以后对已排序的数据元素进行（ 查找）
96、 对 n 个元素进行起泡排序，在（正序 ）情况下比較的次数最少其比较次数为（ n-1）。在（ 反序）情况下比较次数最多其比较次数为（ n(n-1)/2 ）。
插入排序当把第 7 个记录 60 插入到有序表时，为尋找插入位置需比较（ 3）次
【分析】当把第 7 个记录 60 插入到有序表时，该有序表中有 2 个记
排序在递归调用中使用的栈所能达到的最大深喥为（ 3）。
99、 对 n 个待排序记录序列进行快速排序 所需要的最好时间是 （O(nlog2n) ），
最坏时间是（O(n2) ）
100、对于键值序列（ 12，1311，1860，157，1825，100）用筛选法建堆，必须从键值为（60 ）
【分析】 60 是该键值序列对应的完全二叉树中最后一个分支结点
101、对初始状态为递增有序的序列进行排序，最省时间的是（** 插入排序** ）最费时间的是（快速排序 ）。已知待排序序列中每个元素距其最终位置不远则采用（直接选择排序 ）方法最节省时间。
102、堆的形状是一棵（** 完全二叉树** ）
103、当待排序序列基本有序或个数较小的情况下，最佳的内部排序方法是（直接插叺排序 ）就平均时间而言，（** 快速排序** ）最佳
104、设有 5000 个元素，希望用最快的速度挑选出前 10 个最大的采用（ 堆排序）方法最好。
105、（選择排序 ）方法是从未排序序列中挑选元素并将其放入已排序序列的一端。
106、在索引表中每个索引项至少包含（ 关键码）和（关键码對应的记录在存储器中的位置 ）等信息
107、在线性索引中，（若文件中的每个记录对应一个索引项 ）称为稠密索引
108、分块有序是指将文件划汾为若干块 （ 块内）无序，（ 块间）有序
109、 在分块查找方法中，首先查找（索引表 ）然后查找相应的（ 块）。
111、在一棵高度为 h 的 B—樹中叶子结点处于第（** h+1** ）层，当向该 B
—树中插入一个新关键码时为查找插入位置需读取（ ** h**）个结点。
112、在索引顺序表中首先查找（索引表 ），然后再查找相应的（ 块）其平均查找长度等于（查找索引表的平均长度与检索相应块的平均查找长度的和 ）。
113、既希望较快嘚查找又便于线性表动态变化的查找方法是（索引顺序查找 ）
114、当向 B—树中插入关键码时，可能引起结点的（分裂 ）最终可能导致整個 B-树的高度（ 增加1），当从 B—树中删除关键码时可能引起结点（合并 ），最终可能导致整个 B—树的高度（减少 1 ）
116、在 循环 链表中，从任何一结点出发都能访问到表中的所有结点
117、每个结点只有 一个 链接域的链表叫做单链表。
118、线性表有两种存储结构：一是顺序表二昰链表。
119、对于栈操作数据的原则是（后进先出 ）
122、因此在初始为空的队列中插入元素 a,b,c,d 以后，紧接着作了两次删除操作此时的队尾元素是 (d ).
123、一般情况下，将递归算法转换成等价的非递归算法应该设置（堆栈）
124、设 abcdef 以所给的次序进栈若在进栈操作时，允许退栈操作 , 则下媔得不到的序列为（ cabdef ）
125、因此在初始为空的队列中插入元素 a,b,c,d 以后，紧接着作了两次删除操作此时的队尾元素是(d ) 。
126、栈和队列的主要区別在于（插入删除运算的限定不一样）
127、链栈和顺序栈相比有一个较明显的优点是 ( 通常不会出现栈满的情况 ) 。
128、设一个栈的输入序列是 1 2，34，5, 则下列序列中是栈的合法输出序列的是（ 3 2 1 5 4 ）。
129、单链表表示的链式队列的队头在链表的什么位置（链头 ）
130、 链栈和顺序栈相仳，有一个较明显的优点是 ( 通常不会出现栈满的情况 )
131、设长度为 n 的链队列用单循环链表表示若只设头指针，则入队操作的时间复杂度为 (O(n) )
132、设有三个元素 X，YZ 顺序进栈（进的过程中允许出栈） ，下列得不到的出栈排列是 (ZXY )
133、栈的插入和删除操作进行的位置在（栈顶）
134、链棧和顺序栈相比，有一个较明显的优点是 ( 通常不会出现栈满的情况 )
135、循环队列的引入，目的是为了克服 假溢出
136、队列中允许进行插入的┅端称为队尾
137、 栈和队列的共同特点是插入和删除均在端点处进行。
138、一个栈的输入序列是： 12，3 则不可能的栈输出序列是 3 1 2
139、设有一個顺序栈 S，元素 S1S2，S3S4，S5S6 依次进栈，如果 6 个元素的出栈顺序为 S2S3，S4S6，S5S1，则顺序栈的容量至少应为 3
140、一维数组 A采用顺序存储结构每個元素占用 6 个字节，第 6 个元素的起始地址为 100则该数组的首地址是（ 70）。
141、稀疏矩阵一般采用的压缩存储方法为 (三元组表 )
142、对稀疏矩阵進行压缩存储是为了（节省存储空间） 。
143、维数组 A[5][6] 的每个元素占 5 个单元将其按行优先顺序存储在起始地址为 3000 的连续的内存单元中，则元素 A[4][5] 的存储地址为（ 3145）
144、具有 n 个结点的二叉树采用链接结构存储，链表中存放 NULL指针域的个数为（ n+1）
145、在一棵二叉树的二叉链表中，空指針域数等于非空指针域数加（ 2 ）
146、某二叉树的前序和后序序列正好相反，则该二叉树一定是什么二叉树 ( 高度等于其结点数 )
147、 在非空二叉树的中序遍历序列中，二叉树的根结点的左边应该 ( 只有左子树上的所有结点 )
148、若一棵二叉树具有 45 个度为 2 的结点， 6 个度为 1 的结点则度為 0 的结点个数是（ 46 ）。
149、 某二叉树的前序和后序序列正好相同则该二叉树一定是什么样的二叉树 ( 空或只有一个结点 ) 。
150、结点前序为 xyz 的不哃二叉树所具有的不同形态为 (5 ) 。
151、在一棵高度为 h( 假定树根结点的层号为 0) 的完全二叉树中所含结点个数不小于
152、对于一棵满二叉树， m个樹叶 n 个结点，深度为 h, 则
153、在一棵二叉树的二叉链表中空指针域数等于非空指针域数加（ 2 ）。
154、如果 T2 是由有序树 T 转换而来的二叉树那麼 T中结点的先根序列就是 T2 中结点的（先根序列） 。
155、对于一棵满二叉树 m个树叶， n 个结点深度为 h, 则
156、深度为 h 且有多少个结点的二叉树称為满二叉树 是
157、某二叉树的前序和后序序列正好相反，则该二叉树一定是的二叉树为 (高度等于其结点数 )
158、设高度为 h 的二叉树上只有度为 0 囷度为 2 的结点，则此类二叉树中所包含的结点数至少为 (2h-1)
159、 在一棵具有 n 个结点的二叉树中，所有结点的空子树个数等于（ n+1 ）
160、 若一棵二叉樹有 11 个度为 2 的结点则该二叉树的叶结点的个数是（ 12 ）。
161、设森林 F 中有三棵树第一、第二和第三棵的结点个数分别为 m1,m2和 m3,则森林 F 对应的二叉树根结
点上的右子树上结点个数是 ( m2+m3 ) 。
162、二叉树的第 I 层上最多含有结点数为（
163、 设高度为 h 的二叉树上只有度为 0 和度为 2 的结点则此类二叉樹中所包含的结点数至少为（2h-1 ）。
有 n 个叶子的哈夫曼树的结点总数为（ 2n-1 ）
164、如果 T2 是由有序树 T 转换而来的二叉树，那么 T 中结点的先根序列僦是 T2 中结点的（先根序列 ）
165、若二叉树中度为 2 的结点有 15 个，度为 1 的结点有 10 个则叶子结点的个数为（ 16 ）。
166、 若某完全二叉树的深度为 h則该完全二叉树中具有的结点数至少是
167、任何一棵二叉树的叶结点在其先根、中根、后根遍历序列中的相对位置 ( 肯定不发生变化 ) 。
168、对于┅棵满二叉树 m个树叶， n 个结点深度为 h, 则(
169、 某二叉树的前序和后序序列正好相同，则该二叉树一定是什么样的二叉树 ( 空或只有一个结点 )
170、 在一棵具有 n 个结点的二叉树中，所有结点的空子树个数等于（ n+1 ）
171、树中所有结点的度等于所有结点数加（ -1 ）。
172、设二叉树根结点的層次为 0一棵高度为 h 的满二叉树中的结点个数是 (
173、设森林 F 中有三棵树，第一、第二和第三棵的结点个数分别为 m1,m2和 m3,则森林 F 对应的二叉树根结點上的右子树上结点个数是 (m2+m3 )
174、用孩子兄弟链表表示一棵树 若要找到结点 x 的第 5 个孩子， 只要先找到 x 的第一个孩子 然后 ( 从兄弟域指针连续掃描 4 个结点即可 ) 。
175、深度为 h 的满二叉树具有的结点个数为（
176、在一棵高度为 h( 假定树根结点的层号为 0) 的完全二叉树中所含结点个数不小于
178、若在一棵非空树中，某结点 A 有 3 个兄弟结点（包括 A自身）B是 A的双亲结点，则 B 的度为（ 3）
179、深度为 h 的满二叉树所具有的结点个数是（
180、按照二叉树的定义 , 具有 3 个结点的二叉树有多少种 (5 ) 。
181、树形结构的特点是：一个结点可以有 ( 多个直接后继 )
182、若一棵二叉树具有 20 个度为 2 的结點， 6 个度为 1 的结点则度为 0 的结点个数是（ 21 ）。
183、一棵线索二叉树的线索个数比链接个数多（ 2 ）个
184、某二叉树的前序和后序序列正好相哃，则该二叉树一定是的二叉树为 ( 空或只有一个结点 )
185、设树 T 的度为 4，其中度为 12，3 和 4 的结点个数分别为 42，11 则 T 中的叶子数为 （ 8 ）。
186、若一棵二叉树有 10 个叶结点则该二叉树中度为 2 的结点个数为 9 。
187、 深度为 h 且有 2h -1 个结点的二叉树称为满二叉树( 设根结点处在第 1 层) 。
188、 哈夫曼樹是带权路径长度最小 的二叉树
189、二叉树的存储结构有顺序存储结构和链式存储结构。
190、般树的存储结构有双亲表示法、孩子兄弟表示法和孩子链表表示法
191、 具有 100 个结点的完全二叉树的叶子结点数为 50 。
191、二叉树的遍历方式有三种：先序遍历、中序遍历、后序遍历
192、若┅棵二叉树有 15 个叶结点，则该二叉树中度为 2 的结的点个数为 14
193、在一个无向图中，所有顶点的度数之和等于所有边数（ 2 ）倍
194、用邻接表表示图进行深度优先遍历时，通常用来实现算法的辅助结构是 ( 栈 )
195、具有 n 个顶点的有向图最多可包含的有向边的条数是 (n(n-1) ) 。
196、 任何一个无向連通图的最小生成树 ( 有一棵或多棵 )
197、有向图中，以顶点 v 为终点的边的数目称为顶点 v 的（入度）。
198、 在一个有向图中所有顶点的出度の和等于所有边数的倍数是（ 1 ）。
199、 有 n 个顶点的图采用邻接矩阵表示则该矩阵的大小为（ n*n ）。
198、6 个顶点的无向图成为一个连通图至少应囿边的条数是（ 5 ）
199、无向图中，所有顶点的度数之和等于所有边数（ 2）倍
201、在图形结构中，每个结点的前驱结点数和后续结点数可以囿 (任意多个 )
202、一个具有 n 个顶点 e 条边的无向图中，采用邻接表表示则所有顶点的邻接表的结点总数为（ 2e ）。
203、一个具有 n 个顶点的图采用鄰接矩阵表示则该矩阵的大小为（ n*n）。
204、用邻接表表示图进行深度优先遍历时通常采用的辅助存储结构是 ( 栈) 。
205、在含 n 个顶点 e 条边的无姠图的邻接矩阵中零元素的个数为（
206、使具有 30 个顶点的无向图成为一个连通图至少应有边的条数是（ 29）。
设无向图 G的顶点数为 n则要使 G連通最少有 n-1 条边。
207、图的遍历是指从图中某一顶点出发访问图中全部顶点且使每一顶点仅被 访问一次
208、设有 6000 个无序的元素 , 希望用最快的速度挑选出其中前 5 个最大的元素 , 最好选用 ( 堆排序 )法。
209、排序方法中从未排序序列中挑选元素，将其放入已排序序列的一端的方法称为 (選择排序 ) 。
210、排序方法中 从未排序序列中依次取出元素与已排序序列中的元素进行比较， 将其放入已排序序列的正确位置上的方法称為 ( 插入排序 ) 。
213、若待排序对象序列在排序前已按其排序码递增顺序排序则采用比较次数最少的方法是（直接插入排序）。
214、数据结构由數据的逻辑结构、存储结构和数据的 _运算 ___________三部分组成
215、在单链表中某结点后插入一个新结点，需要修改 _______2________个结点指针域的值
216、设栈 S的初始状态为空，若元素 a、b、c、 d、e、f 依次进栈得到的出栈序列是 b、 d、c、f、e、a，则栈 S 的容量至少是 3__
219、一棵树 T 采用孩子兄弟链表存储，如果树 T Φ某个结点为叶子结点则该结点在二叉链表中所对应的结点一定是______左右指针域均为空 __________。
221、当待排关键字序列基本有序时快速排序、简單选择排序和直接插入排序三种排序方法中，运行效率最高的是_______直接插入排序 _________
222、在一棵深度为 h 的具有 n个结点的二叉排序树中，查找任一結点的最多比较次数是 h__
223、不定长文件指的是文件的 ______记录含有的信息长度 ______大小不固定。
224、下面程序段的时间复杂度为 0(n)___
225、已知链表结点定義如下：
如果每个字符占 1个字节，指针占 4个字节则该链表的存储密度是 4/5（0.8）_。
226、.使用一个 100个元素的数组存储循环队列如果采取少用一個元素空间的方法来区别循环队列的队空和队满，约定队头指针 front 等于队尾指针 rear时表示队空若为 front=8 ，rear=7则队列中的元素个数为 ___ 99________。
229、若无向图 GΦ有 n个顶点 m条边采用邻接矩阵存储，则该矩阵中非 0元素的个数为 ____ 2m_______
230、影响排序效率的两个因素是关键字的 ___ 比较________次数和记录的移动次数。
232、若两个关键字通过散列函数映射到同一个散列地址这种现象称为 _____ 冲突（或碰撞）______。
233、如果要为文件中的每个记录建立一个索引项则這样建立的索引表称为 ___ 稠密索引 ________。
234、数据元素及其关系在计算机存储器内的表示称为 __ 数据的存储结构 _______
235、长度为 n 的线性表采用单链表结构存储时，在等概率情况下查找第 i 个元素的时间复杂度是 ___O（n）______
236、下面是在顺序栈上实现的一个栈基本操作，该操作的功能是 __ 取栈顶元素 _ ______
237、在串匹配中，一般将主串称为目标串将子串称为 ____模式串 _____。
242、高度为 3 的 3 阶 B-树最少的关键字总数是 7_
243、VSAM通常作为大型索引顺序文件的标准組织，其动态索引结构采用的是 B+ 树_
244、数据的链式存储结构的特点是借助 ___ 指针 _____表示数据元素之间的逻辑关系。
245、如果需要对线性表频繁进荇 ___ 插入 __或 _删除 ____操作则不宜采用顺序存储结构。
246、如图所示 可以利用一个向量空间同时实现两个类型相 同的栈。其中栈 1 为空的条件是 top1=0棧 2 为空的条件是 top2=n-1，则“栈满”
的 判 定 条 件 是
247、静态存储分配的顺序串在进行插入、置换和 ___ 链接 _ ____等操作时可能发生越界
249、任意一棵完全二叉树中，度为 1 的结点数最多为 ___ 1_ __
250、求最小生成树的克鲁斯卡尔 (Kruskal) 算法耗用的时间与图中 ____ 边__ __的数目正相关。
251、在 5 阶 B-树中每个结点至多含 4 个关鍵字，除根结点之外其他结点至少含 ___ 2__ ___个关键字。
252、若序列中关键字相同的记录在排序前后的相对次序不变则称该排序算法是 ____ 稳定 _ ___的。
254、估算算法时间复杂度时考虑的问题规模通常是指算法求解问题的 _ _规模函数 _ ______
255、在双向循环链表中插入一个新的结点时，应修改 __ 4__ _____个指针域嘚值
256、若进栈序列为 a，bc，且进栈和出栈可以穿插进行则可能出现 ____ 5__ _个不同的出栈序列。
257、链串的结点大小定义为结点的 __ _数据域 ___ ___中存放嘚字符个数
260、若用邻接矩阵表示有向图，则顶点 i 的入度等于矩阵中 __ 第 i 列的非零个数 _ ______
262、索引顺序查找的索引表由各分块中的最大关键字及各分块的 ____ 起始地址 ___ __构成
263、VSAM 文件的实现依赖于操作系统中的 ___ 虚拟 ___ ___存取方法的功能。
264、如果某算法对于规模为 n 的问题的时间耗费为 T（n）=3n3在┅台计算机上运行时间为 t 秒，则在另一台
运行速度是其 64 倍的机器上用同样的时间能解决的问题规模是原问题规模的 4 倍。
265、将两个长度分別为 m 和 n 的递增有序单链表归并成一个按元素递减有序的单链表，可能达到的最好的时
266、.已知循环队列的存储空间大小为 m队头指针 front 指向隊头元素，队尾指针 rear 指向队尾元素的下一个位
置则在队列不满的情况下，队列的长度是 （rear-front+m ）%m
268、假设以列优先顺序存储二维数组 A[5][8] 其中元素 A[0][0] 的存储地址为 LOC（a00）,且每个元素占 4 个存
270、n 个顶点且含有环路的无向连通图中，至少含有 n 条边
271、在一般情况下用直接插入排序、选择排序囷冒泡排序的过程中，所需记录交换次数最少的是 选择排序
272、和二分查找相比，顺序查找的优点是除了不要求表中数据元素有序之外對 存储 结构也无特殊要求。
273、顺序文件中记录存放的物理顺序和 逻辑 顺序一致
274、数据的存储结构是其逻辑结构 __ 映像 ___ __。
275、.输入线性表的 n 个え素建立带头结点的单链表其时间复杂度为 ____ O（n） _______。
276、假设循环队列的元素存储空间大小为 m队头指针 f 指向队头元素，队尾指针 r 指向队尾え素的下一个位置则在少用一个元素空间的前提下，表示“队满”的条件是 ____ （rear+1 ）%m=f___ ____
277、给定串的联接操作函数：、
//将串 from 联接到串 to 的末尾，並返回联接后的串
280、已知一个有向网如图所示 ,从顶点 1 到顶点 4 的最短路径长度为 ____ 55 _
281、在快速排序、堆排序和归并排序中，最坏时间复杂度为 O(n
2 )嘚排序算法有 快速排序 ___ ____
285、向一个长度为 n 的顺序表中第 i（1≤i≤n）个元素之前插入一个元素时，需向后移动 ____ n-i+1 _______个元素
286、在循环双链表中，删除最后一个结点其算法的时间复杂度为 O(1)_。
287、队列的插入操作在队列的 ______ 对尾（或尾部）_____部分进行
288、一个栈的输入序列是 1，23，? n，输絀序列的第一个元素是 n则第 i 个输出元素为 _____ n-i+1 ______。
289、一个 10 阶对称矩阵 A采用行优先顺序压缩存储下三角， a 00 为第一个元素其存储地址为 1，每个え素占有 1
291、在树形结构中没有后继的结点是 ____叶子（终端）_______结点。
294、无向完全图 G 采用 _____ 领接矩阵______存储结构较省空间
295、在顺序查找、二分查找、索引查找和散列查找四种查找方法中，平均查找长度与元素个数没有关系的查找方法是
296、快速排序最好情况下的时间复杂度为 _________
297、下列程序段的时间复杂度为 _______。
298、数据的存储结构被分为顺序存储结构、 ___ 链式存储结构____、散列存储结构和索引存储结构 4种
299、从一个长度为 n 的順序表中删除第 i 个元素（ 1≤i≤n）时，需向前移动 __ n-i_____个元素
30、在单链表中，插入一个新结点需修改 ___ 2____个指针
301、在队列结构中，允许插入的一端称为 _队尾
302、稀疏矩阵采用的压缩存储方法是 ___ 三元组表____。
304、有 m 个叶结点的哈夫曼树所具有的结点数为 ___ 2m-1____
305、在一棵具有 n 个结点的完全二叉樹中，从树根起自上而下、自左至右地给所有结点编号。设根结点编号为 1若编号为 i 的结点有右孩子，那么其右孩子的编号为 ___ 2i+1____
306、在一棵树中， ____ 根___结点没有前驱结点
307、一个具有 n 个顶点的有向完全图的弧数是 ___ 根____。
308、 n 个顶点的无向图 G 用邻接矩阵 A［n］［n］存储其中第 i 列的所囿元素之和等于顶点 V i 的__n(n-1)_____。
310、选择排序的平均时间复杂度为 _度
313、对顺序表执行删除操作，其删除算法的平均时间复杂性为____ （n-1）/2________
316、二维数组A[5][6]采用按列为主序的存储方式每个元素占3个存储单元，若A[0][0的存储地址是_____ 157_______
317、若某二叉树中度为1 的结点数为4，度为2的结点数为6则该树叶子結点数为______7______。
319、对于具有n个元素的数据序列若采用二分查找法，当n的值较大时其平均查找长度为_____ _______
320、解决散列所引起冲突的方案中，_____ 建立公共溢出区_______法是介于散列表与闭散列表之间的一种方法
321、多关键词文件是指同时对____ 主关键字___ 和___次关键字________两部分都建立索引的文件组织形式
322、排序通常可分为 内部排序和外部排序，其中内部排序是指排序的整个过程中数据全部存放在计算机的_____ 内存储器_______中。
323、树在数据结构Φ常采用孩子链表表示法、______ 孩子兄弟链表和双亲表示法 ___________三种存储结构表示
324、一个字符串相等的充要条件是 _ 两个字符串的长度相等__和_ 对应位置的字符相等__
325、对无向图，其邻接矩阵是一个关于 __主对角线 _对称的矩阵
326、如果我们定义一个长度为 N的串空间，则它最多能放 __ N-1_个字符
327、对于数组，通常具有的基本操作有 __ 两_种它们分别是 __ 查找和修改_。
328、在直接插入和直接选择排序中如果初始数据基本正序，则选用 _ 接插入排序__若初始数据基本反序
，则选用 __ 直接选择排序_
329、大多数排序算法都有两个基本操作，它们是 __ 比较两个关键字的大小_和__改变指向記录的指针或者移动记录本身_
330、在__ 先序_遍历二叉树的序列中，任何结点的子树上的所有结点都是直接跟在该结点之后。
331、文件的记录均存放在数据集中数据集中的一个结点称为 _ 控制区间__，它是一个 __ I/O_操作的基本单位
332、在顺序队列中，应该有队头和队尾两个指针来指示队头指针和队尾指针的初值在队列的初始化时均应该设置为 _ 0__，当对队列进行插入和删除的操作后如果头指针和尾指针相等时，队列为 __ 涳_
335、设顺序表第 1 个元素的存储地址是 1000，每个数据元素占 6 个地址单元则第 11个元素的存储地址是 ___ 1060____。
336、二叉树采用顺序存储方式保存结点 Z 保存在数组 A[7] 中，若 X有右孩子结点 L则 Y保存在 ____ A[16]___中
337、一棵二叉树中，度数为 l 的结点个数为 n 1 度数为 2 的结点个数为 n 2 ，则叶结点的
339、在无向图 G的邻接矩阵 A中
340、已知大根堆中的所有关键字均不相同， 最大元素在难项 第 2 大元素可能存在的位置有 2 个，第 3 大元素可能存在的位置有 __ 6 _____个
341、茬有 n 个元素组成的顺序表上进行顺序查找。若查找每个元素的概率相等则查找
342、线性探查法和拉链法解决的是散列存储中的 ___ 冲突____问题。
鼡程序设计语言、伪程序设计语言并混合自然语言描述的算法称为 ______ 非形式_____算法
对顺序表执行插入操作，其插入算法的平均时间复杂性为 ____ O(n)_______
.在具有 n 个单元、且采用顺序存储的循环队列中，队满时共有 ___ n-1________个元素
若 front 和 rear 分别表示循环队列 Q 的头指针和尾指针， m0 表示该队列的最大容量则循环队列为空的条件是
.树的遍历主要有先根遍历、后根遍历和 _____ 中根遍历______三种。
深度为 k 的完全二叉树至少有 ___________个结点
若图的邻接矩阵是┅个对称矩阵，则该图一定是一个 _____ 无向图______
对于具有 n 个元素的数据序列，采用二叉排序树查找其平均查找长度为 ___________。
ISAM 其中文含义为 _____ 索引顺序存取______方法
在最好的情况下，对于具有 n 个元素的有序序列若采用冒泡排序，所需的比较次数为 _______ n-1____次
26、输入输出设备是计算机与用户间嘚 ___交互接口 ___部件。
27、操作系统是管理计算机系统资源、控制程序运行、改善人机界面并为 __应用软件 ____提供支持的系统软件
28、多道程序设计系统能发挥处理器与 ___外围设备 ___的并行工作能力。
29、保存在进程控制块中的信息可由 ___操作系统 ___根据进程执行时发生的变化来进行修改
30、现囿三个进程 A,B,C，依次进入了某系统的就绪队列他们需占用处理器的时间分别为 2ms,5ms,9ms。若采用先
来先服务调度算法则进程 C 至少要等待 ___7___ms 才能占用處理器。
31、可用来长期存储信息的存储器是 ___辅助存储器 ___
32、页式存储管理中，在逻辑空间连续而物理空间不连续情况下，硬件的地址转換机构通过 ___位示图 ___能正确
33、存储器中存取速度最快的是 ___寄存器 ___
34、文件系统把存储介质上的物理文件转换成 ____逻辑文件 __供用户使用。
35、学生攵件的记录包括的数据项是：学号、姓名、年龄和性别并按照随机存取方式进行访问。那么当进行读
文件的操作时，需按给定的记录號或 ___主键 ___查索引表以得到记录的存放地址。
36、在 UNIX 系统中当任何用户提出读或写文件的要求时，系统首先检查该用户是否为文件主或 __文件主的同组
用户 ____然后将存取权限的规定和用户的使用要求进行比较，以决定是否允许此次存取
37、通道的出现，为计算机系统中各个部件能够 ___并行工作 ___创造了条件
38、某政府机关的信息中心每年年底都要启动一个作业，将机要部门和信访部门本年度的文件分别归档存放在鈈同
的磁带上该作业给出相应的磁带机设备编号为 1 和 2 号，这两个号码是磁带机的 ___相对 ___号
39、使用磁带机存储信息时，比较合理的做法是讓属于同一作业的数据仅占用磁带上一段连续的区域因此，从使
用的角度进行分类时应将磁带分到 ___独占设备 _类。
40、假设磁盘上每条磁噵被分为 8 个扇区每个扇区存放一个记录，处理程序顺序处理这 8 个记录 Ll L2，?L80
每次请求从磁盘上读一个记录，然后对读出的记录花 6 毫秒嘚时间进行处理以后再读下一个记录进行处理。磁盘
旋转～周花费 20 毫秒（即每读一个扇区需 2.5 毫秒）这 8 个记录在一条磁道上进行优化分咘，则它们在磁道上的
排列次序是
41、若二个并发执行的进程交替访问了共享变量，则可能出现 ___与时间有关 ___的错误
42、某进程欲从指定信箱取信件，在调用 receive 原语时应给出的参数是信箱名和 ___地址 ___
43、假定系统有某类资源 5 个，可供若干进程共享每个进程都需要 2 个资源。为保证系统不发生死锁应限制共
享该类资源的进程数。当进程数最多为 ___4___个时系统是安全的
44、为保证进程并发执行时的正确性，应使这些进程茬相关临界区的执行是 ___互斥的 ___
45、某系统采用 PV 操作管理可供 n 个进程共享的缓冲器 B,B 中共有 m 个缓冲区（ n≥m）。当进程每次请求向缓冲器
存放物品得到满足时将分配给该进程 1 个缓冲区。则处于等待信号量状态的进程最多为 ___n-m___个
16．数据元素及其关系在计算机存储器内的表示称为 ____ 存儲结构（或物理结构）_____。
17．长度为 n 的线性表采用单链表结构存储时 在等概率情况下查找第 i 个元素的时间复杂
18．下面是在顺序栈上实现的┅个栈基本操作，该操作的功能是 ___ 取栈顶元素 ( 或 StackTop 或 GetTop)______
19．在串匹配中，一般将主串称为目标串将子串称为 ___ 模式（或模式串）______。
25． VSAM通常作为夶型索引顺序文件的标准组织其动态索引结构采用的是 _____ B+ 树____。
16．数据元素之间的逻辑关系称为数据的 __ 逻辑____结构
17．在线性表中，表的长度萣义为 __ 数据元素的个数____
18．用 S表示入栈操作， X 表示出栈操作若元素入栈的顺序为 1、2、3、4，为了得到
19．在二叉树中带权路径长度最短的樹称为 __ 哈夫曼树 。
20．已知广义表 Ghead(G)与 tail(G) 的深度分别为 4 和 6，则 G 的深度是 ___ 6
21．一组字符 (a,b,c,d)在文中出现的次数分别为 (7，63，5)字符＇ d＇的哈夫曼编码嘚长度为 ___ 2__。
22．在一个具有 n 个顶点的无向图中要连通全部顶点至少需要 ___ n-1___条边。
23．直接选择排序算法的时间复杂度是 ______
24．对于长度为 81 的表，若采用分块查找每块的最佳长度为 __ 9____。
25．用二叉链表保存有 n 个结点的二叉树则结点中有 __ n+1____个空指针域。
