考研数据结构填空题整合_做题版

考研数据结构填空题整合

---

---

一、ZYL组

ZYL组一

1.顺序存储结构实现的队列存在着 假溢出 现象，因而采用环形的结构来克服。

---

2.共有n个叶子的二叉树，每个叶子的权值为Wi（1≦i≦n），其中带权路径长度最小的二叉树被称之为 哈夫曼树 。

---

3．图的遍历方式有 深度优先 和 广度优先 两种。

---

4．快速排序在最坏情况下的时间复杂度为 O(n²) 。

---

5．在有n个元素的线性表中，可删除的元素有__n__个，可插入元素的位置有__n+1___个

---

6．设有一个空栈，栈顶指针为1000H（十六进制），现有输入序列为1，2，3，4，5，PUSH，PUSH，POP，PUSH，POP，PUSH，PUSH后，输出序列为__2 3_______，栈顶指针是__1003H____。

---

7．设F是一个森林，B是由F转换得到的二叉树，F中有n个非终端结点，则B中右指针域为空的结点有__n+1____个。

非终端节点的意思是指在树结构中度不为0的结点
1

---

ZYL组二

1．线性表可采用的存储结构有____顺序存储___和___链式存储____二种。

---

2．有n个结点的完全二叉树的深度为____lb(n+1)-1__。

lb 在计算机算法中，lb 就是 log based binary ，即以2为底的对数。
在计算机中采用二进制，所以 lb 经常被使用。例如，lb(2)=1，lb(1024)=10。
1
2

---

3．二叉树的遍历方式有___先序遍历__、___中序遍历______和_____后序遍历____三种。

---

4．两个字符串相等的充分必要条件是___两个串长度相等且对应位置的每个字符相同_______ 。

---

5．一个无序序列可以通过构造一棵__二叉排序____树而变成一个有序序列,构造树的过程即为对无序序列进行排序的过程.

---

6．如果结点A有3个兄弟,而且B是A的双亲,则B的度是____4_____.

---

7．广义表运算式HEAD(TAIL((a,b,c),(x,y,z))))的结果为___(x,y,z)__。

A =(a,b,(c,d),(e,(f,g)));

Tail(A)=(b,(c,d),(e,(f,g)));

Tail(Tail(A))=((c,d),(e,(f,g)));

Head(Tail(Tail(A)))=(c,d);

Tail(Head(Tail(Tail(A))))=(d);

Head(Tail(Head(Tail(Tail(A)))))=d;
1
2
3
4
5
6
7
8
9
10
11

---

ZYL组三

1．假定一棵树的广义表表示为A(B(E),C(F(H,I,J),G),D), 则该树的度为__3____，树的深度为___3___，终端结点的个数为__6____。（空树的深度为0）。

因题目而已
1

---

2．将５个不同的数据进行排序，至少需要比较__4____次，至多需要比较__10___次。

---

3．基于关键字比较大小的排序算法中, __快速____排序算法的平均时间复杂度最优。

---

4．N个顶点的连通无向图,其边的条数至少为___n-1___
无向图中，如果任意两个顶点之间都能够连通，则称此无向图为连通图。
例如，图 2 中的无向图就是一个连通图，因为此图中任意两顶点之间都是连通的。

---

5.线索二叉树的左线索指向其__前驱结点___, 右线索指向其__后继节点__

---

6.有N个顶点的有向图, 至少需要___n___条弧才能保证是连通

有向图中，若任意两个顶点 Vi 和 Vj，满足从 Vi 到 Vj 以及从 Vj 到 Vi 都连通，也就是都含有至少一条通路，则称此有向图为强连通图。如图 4 所示就是一个强连通图。

---

ZYL组四

1、 算法是一个有穷的指令集，它为解决某一特定任务规定了一个运算序列。它应当具有输入、输出、有穷性_、_确定性____和可执行性等特性。

确定性确定性确定性确定性确定性确定性确定性确定性确定性确定性确定性确定性确定性确定性确定性确定性
1

---

2、 从一维数组a[n]中顺序查找出一个最大值元素的时间复杂度为__O（n）___。

---

3、 对于一个二维数组A[m][n]，若采取按行存放（行优先存储）的方式，则任一数组元素A[i][j]相对于A[0][0]的地址为__i*n+j___。

---

4、 当用长度为n的数组顺序存储一个栈时，若用topn 表示栈空，则表示栈满的条件为__top0___。

---

5、 中缀表达式3*(x+2)-5所对应的后缀表达式为__3x2+*5-___。

---

6、 假定一棵三叉树的结点个数为50，则它的最小高度为__4__，最大高度为__49___。

不同教材定义不同h
1

---

7、 对于一个具有n个顶点和e条边的连通图，其生成树中的顶点数和边数分别 为__n___和___n-1__。

通常定义为没有回路的连通图,或者定义为最小连通图,(即删去任意一条边就会不连通的连通图),
n个顶点的最小连通图至少有n-1条边,
如果少于n-1条边一定不会是连通的,如两个顶点的图必有1条边才能确保它连通,3个顶点的图必有2条边才能确保它连通,等等,
又n个顶点的最小连通图至多有n-1条边,否则一定会有回路,
如果有了回路,删去回路中的任意一条边仍会连通,这样它就不是最小连通图了,
故生成树不多不少恰有n-1条边.
1
2
3
4
5
6

---

ZYL组五

1、从逻辑关系上讲，数据结构分为两大类：各个数据成员依次排列在一个线性序列中的结构称为（ 线性结构 ）；各个数据成员不再保持在一个线性序列中，每个数据成员可能与零个或多个其他数据成员发生联系，这种结构称为（_非线性结构 ）。

此处不能写顺序存储和链式存储，比如说树和图这种结构
1

---

2、对于一个二维数组A[m][n]，若采取按行存储的方式，每个数组元素占1个存储字，则任一数组元素A[i][j]相对于A[0][0]的地址为（ i*n+j ）。

---

3、设整数1, 2, 3, 4, 5, 6依次进栈，则可能的出栈序列有（132___）种

1/(n+1)*c(2n,n)
讲道理，背公式吧
1
2

---

4、顺序搜索算法适合于存储结构为（顺序存储或链式存储_ ）的线性表。

注意还有个链式存储，比如二叉排序树
1

---

5、对于一棵具有n个结点的树，该树中所有结点的度数之和为（n-1 ）。

---

6、对于一个具有n个结点和e条边的无向图，若采用邻接表表示，则顶点表的大小为（ n ），所有边链表中边结点的总数为（ 2e ）。

---

7、在无向图的邻接矩阵A中，若A[i][j] = 1，则A[j][i] = （ 1 ）。

---

8、n (n﹥0) 个顶点的连通无向图各顶点的度之和最少为（ 2(n-1) ）.

---

ZYL组六

1.抽象数据类型的特点是____数据封装____、信息隐蔽、使用与实现分离。

---

2.算法的一个特性是____有穷性____，即算法必须执行有限步就结束。

---

3、一维数组所占用的空间是连续的。但数组元素不一定顺序存放，而是按元素的___下标______存放的。

---

4、将一个n阶对称矩阵的上三角部分或下三角部分压缩存放于一个一维数组中，则一维数组需要存储____n(n+1)/2_____个矩阵元素。

---

5、在单链表中设置表头结点的作用是在插入和删除表中第一个元素时不必对______头指针__进行特殊处理。

---

6、中缀表达式3*(x+2)-5所对应的后缀表达式为___3x2+*5-_____。

---

7、广义表A ( (a, b, c), (d, e, f ) ) 的表尾为__((d, e, f ))______。

---

8、假定一棵三叉树（即度为3的树）的结点个数为50，则它的最小高度为__4____。假定根结点的高度为0。

---

9、 101个顶点的连通网络N有100条边，其中权值为1, 2, 3, 4, 5, 6, 7, 8, 9, 10的边各10条，则网络N的最小生成树各边的权值之和为____550_____。

---

ZYL组七

1、算法的一个特性是___确定性_____，即针对一组确定的输入，算法应始终得出一组确定的结果。

---

2、二维数组是一种非线性结构，其中的每一个数组元素最多有_____2____个直接前驱（或直接后继）。

从行向量角度有一组，从列向量角度又有一组。
1

---

3、在链表中进行 __插入和删除__操作的效率比在顺序存储结构中进行相同操作的效率高。

---

4、从一个顺序栈中删除元素时，需要将____栈顶指针____前移一位位置。

---

5、主程序第一次调用递归函数被称为外部调用，递归函数自己调用自己被称为内部调用，它们都需要建立____递归工作_____记录。

1

---

6、一棵树的广义表表示为a (b (c, d (e, f), g (h) ), i (j, k (x, y) ) )，结点k的所有祖先的结点数为___2___个。

---

7、从有序表 (12, 18, 30, 43, 56, 78, 82, 95) 中折半搜索元素56时，其搜索长度为____3____。

---

8、若3个顶点的图G的邻接矩阵为 ，则图G一定是____有____向图。

---

9、第i (i = 1, 2, …, n-1) 趟从参加排序的序列中取出第i个元素，把它插入到由第0个～第i-1个元素组成的有序表中适当的位置，此种排序方法叫做___插入_____排序。

---

10、在线性表的散列存储中，装载因子 a 又称为装载系数，若用m表示散列表的长度，n表示待散列存储的元素的个数，则 a等于___n/m_____。

---

ZYL组八

1、将一个n阶对称矩阵A的下三角部分按行压缩存放于一个一维数组B中，A[0][0]存放于B[0]中，则A[I][J]在I≥J时将存放于数组B的_____i(2n-i-1)/2 + j____位置。

答案应该是有问题，或者题目有问题
1

---

2、顺序表的所有元素必须集中存储于表的_____前部____，这是它与一般的一维数组的不同之处。

前部比较好听~~~
1

---

3、在不带表头结点的线性链表中删除表的第一个结点时，必须改变链表的____头指针____，然后再执行删除。

最好是表头指针
1

---

4、栈是一种限定在表的一端插入和删除的线性表，它的特点是___后进先出_____。

先进后出
1

---

5、非空广义表的第一个表元素称为广义表的___表头_____。

---

6、一棵树按照左子女-右兄弟表示法转换成对应的二叉树，则该二叉树中____根__结点肯定没有右子女。

---

7、假定一个顺序表的长度为40，并假定搜索每个元素的概率都相同，则在搜索成功情况下的平均搜索长度为___20.5_____。

---

8、求解带权连通图最小生成树的Prim算法适合于___稠密_____图的情形，而Kruskal算法适合于____稀疏____图的情形。

---

9、给定一组数据对象的排序码为 { 46, 79, 56, 38, 40, 84 }，则利用堆排序方法建立的初始堆（最大堆）为___{84，79，56，38，40，46}_____。

---

10、在一棵B树中，所有叶结点都处在_____同一层___上。

---

二、TJP组

TJP组一

1．任何基于关键字__比较_____的排序算法，其时间复杂度即使在最坏的情况下也都大于或等于O(nlog2n)。

---

2．平衡二叉树（又称AVL树）的一个典型问题是平衡的二叉排序树（又称二叉查找树），保持二叉排序树的平衡形态可避免在查找等操作中使其退化为单枝树，即避免相应算法的时间性能由O(log2n)降低为___O（n）____。

只是查找，所以最坏也就n，不需要平方，那个是排序
1

---

3．可用迭代法将递归算法转换为非递归算法，也可利用___栈___来模拟递归过程使递归算法转换为非递归算法。

---

4．若一个有向图G中的所有顶点可排成一个线性序列，使得G中任一对顶点u和v若满足 < u , v >∈E ( G ) 则u在该序列中出现在v之前，那么该序列称为图G的___拓扑序列____。

---

5．在伙伴系统中记录所占用的内存区（块）大小必为___2____的k次幂。

---

6．复杂数据结构中的不相交集合类主要是为了解决___等价____问题。

(并查集)是解决等价问题的一种有效数据结构
1

---

7．在哈希表（散列）中填入的记录个数n，与哈希表的表长m之比称为哈希表的___装载因子____。

---

8．表达式由运算数与运算符（二元运算）序列构成，若某二叉树的中序遍历恰恰反映为这种序列，则表达式的运算符均应为二叉树的____非终端___结点。

---

9．广义表的元素可能有各种结构，但广义表自身应是____多层次___的结构

---

10．从稳定性看，快速（分划交换）排序和堆排序相对来说是___不稳定____的。

---

TJP组二

1．算法中所有语句的频度之和记做T(n)，它是算法所求解问题规模的函数,当问题的规模n趋向无穷大时，T(n)的数量级（阶）称为该算法的_____时间复杂度_____。

---

2．已知某问题可按相同的规律去逐步简化为若干个性质相同、解法相同的小问题，且当问题的规模降低到一定程度时即可直接求解，那么用_______递归____________方法来设计该问题的求解算法，可更好地针对并利用该问题的上述特点。

---

3．以“孩子兄弟表示法”存储一棵树，其二叉链表所对应的树之形态将缺少__________右子树_________。

---

4．对于非连通的图G进行遍历，从连通性的角度看，每进行一次深度优先搜索或广度优先搜索，都是对图G的一个_______连通子图____________的所有顶点遍历一次。

---

5．构造哈希表（散列）必须同时考虑设计哈希函数和_______解决冲突____________两个问题。

---

6．内存管理的目的是为了有效地利用计算机内存中的______可用资源_____________。

---

7．基本数据结构中的队列是一种先进先出结构，而复杂数据结构中的优先级队列与队列的不同，主要是在于________出队___________操作的处理。

---

8．广义表可以为其它广义表所共享，如广义表A是B的子表，则在B中不必列出A的值，只需通过________子表名______引用即可。

---

9．哈夫曼编码可形成通讯所需的二进制不等长码，以通讯信息中字符出现的频度作权值，则频度越高的结点在哈夫曼树中所处的层越__________靠近根_________。

---

10．从稳定性看，希尔（缩小增量）排序和堆排序相对来说是___________不稳定________的。

---

TJP组三

1．对以查找定位操作为主的线性表，可考虑其存储结构以____顺序结构___ 为好。

---

2．对长度为n的顺序存储线性表，若在表中任何位置上删除或插入一个元素的概率均相等，则每次删除或插入一个元素时，都将引起表中元素的平均移动次数，大约为原表元素个数的____1/2___ 。

---

3．对具有9876个之点的完全二叉树的结点进行1至9876的编号（按层次从上到下，同层从左到右地编号），则7025号结点的双亲结点是___3512____ 号。

---

4．最优二叉树（哈夫曼树）是所有叶结点的__加权路劲长度_____ 之和最短的二叉树。

---

5．二元运算表达式由运算数与运算符序列构成，若某二叉树的中序遍历结果恰反映为这种序列，则式中运算数结点均为运算符结点的____孩子___ 结点。

---

6．当算法中所有语句的频度之和T（n），与求解问题的规模无关时，那么该算法的时间复杂度为____O（1）___ 阶（即T（n）的数量级）。

---

7．对n个结点的二叉树，利用其二叉链表的n+1个空域，来存指向其遍历序列中相应的直接前驱或直接后继的指针，以使该树成为___线索____ 二叉树。

---

8．串的定位操作：若在主串s中存在子串p，则返回p在s中的起始位置，否则返回某特定值。那么，实现该功能的算法又称为__模式匹配_____ 算法。

---

9．在完全二叉树的顺序存储空间中若约定：任何非叶结点的Key值均不大于其左右孩子的Key值，可用此约定来实现该空间中数据的___堆____ 排序。

---

10．平衡二叉树上的所有平衡因子只能是-1、1和____0___ 三个值。

---

三、LZH组

LZH 组一

1．对于一个以顺序实现的循环队列Q[0…m-1]， 队头、队尾指针分别是f，r，其判空的条件是____f = r_______ ，判满的条件是_______（f + 1）%m=r___________。

注意此处是循环队列
1

---

2．前序序列和中序序列相同的二叉树为________单右枝二叉树或孤立节点________ 。

---

3．设根结点处在第一层，那么具有n个结点的完全二叉树，其高度为_______log₂（n）+1_____________。

---

4．快速排序方法的最坏时间复杂度为_______O(n²)_________ ；平均时间复杂度为______O(nlog₂n)__________ 。

---

5．给定表（55，63，44，38，75，80，31，56），用筛选法建立初始堆，则初始堆表为________________{31,38,44,56,75,80,55,63}或 （80，75，55， 56，63，44，31，38）______________ 。

---

6．已知二叉树中叶子数为50，仅有一个孩子的结点数为30，则总结点数为
129 。

---

7．已知8个数据元素由（35，75，40，15，20，55，95，65）按照依次插入结点的方法生成一棵二叉排序树后，最后两层上的结点总数为_____2_______

---

8．假设有n个关键字，它们具有相同的Hash函数值，用线性探测方法解决冲突，把这n个关键字散列到大小为n的地址空间中，共计需要做___n(n+1)/2_ 次插入和探测操作。

---

9．设图G有n个顶点e条边，采用邻接表存储，则拓扑排序算法的时间复杂度为_______O(n+e)_________________。

---

10．已知有序表为（12，18，24，35，47，50，62，83，90，115，134），当用二分法查找100时，需进行____3____次查找时才能确定不成功。。

---

LZH 组二

1．检查AOV网中是否存在回路的方法是___对AOV网进行拓扑排序______ 若按该方法操作，网中顶点未被全部输出，则说明______存在回路_________ ；

---

2．复杂度为O(nlog2n)的排序方法有____快速排序___、希尔排序、归并排序__ 、堆排序_ 等。

---

3．已知某二叉树的后序遍历结果是dabec，中序遍历结果是debac，其先序遍历结果是_____cedba_______。

---

4．在一个具有n个结点的无向图中，要连通全部顶点至少需要__n-1__ 条边。

---

5．有一个有序表为{1,3,9,12,32,41,45,62,75,77,82,95,100}，当用折半法查找值为82的结点时，经过__4____ 次比较查找成功。

---

6．一组记录的关键码为(46,79,56,38,40,84)，则利用快速排序方法，以第一个记录为基准得到的第一次划分结果是________{40,38,46,56,79,84}__________

---

7．在长度为n的顺序存放的线性表中删除第i个元素（1<=i<=n）时，需向前移动_____n-i____个元素

---

8．已知有序表为（12，18，24，35，47，50，62，23，90，115，134），当用二分法查找90时，需进行_2__ 次查找可确定成功。

---

9．构造哈希（hash）函数的方法有__直接地址法____、数字分析法、___除留余数法___等。

*************************
1

---

10．具有n个结点的二叉树，采用二叉链表存储，共有 ___n+1___个空链域。

---

LZH 组三

1．在拓扑排序中，拓扑序列的第一个顶点必定是__ 入度为零__ 的顶点。

---

2.由四个分别带权值为5, 12, 9, 30, 7, 16的叶子结点构造一棵哈夫曼树，该树的结点个数为__11__，树的带权路径长度为__189___。

---

3．对表长为n的顺序表进行分块查找，若以顺序查找确定块，且每块长度为s，则在等概率查找的情况下，查找成功时的平均查找长度为_____（s2+2s+n）/2s_______。

---

4．如果结点A有3个兄弟，而且B是A的双亲，则B的度是__4__

---

5．一个无序序列可以通过构造一棵____二叉排序____ 树而变成一个有序序列，构造树的过程即为对无序序列进行排序的过程。

---

6．设有向图有n个顶点和e条边，进行拓扑排序时，总的计算时间为____O（n+e）__

---

7.求从某源点到其余各顶点的Dijkstra算法，当图的顶点数为10，用邻接矩阵表示图时计算时间约为10ms，则当图的顶点数为40时，计算时间为__160__ms

dijkstra算法的时间复杂度是O(n²),
不妨设为kn²,其中次数小于1的项忽略
k(10×10）=10ms
那么k(40×40）=16[k×（10×10）]=160ms
1
2
3
4

---

9.设一棵后序线索树的高度是50，结点x是树中的一个结点，其双亲是结点y， y的右子树高度是31，x是y的左孩子，则确定x的后继最多需经过__31 __ 个 中间结点（不含后继及x本身）

---

10．对于单向链表，在两个结点之间插入一个新结点时需修改的指针
共有______2____ 个。

---

LZH 组四

1．在双向循环链表中，设指针p指向待删除的结点，则删除结点p需执行的语句为__p->next-pre = p;p->prior->next = p->next__________。

---

2．由a, b, c三个结点构成的二叉树，共有___5____种不同的结构。

---

3．设根结点处在第一层，那么具有n个结点的完全二叉树，其高度为________|log₂ n |+1____________。

---

4．克鲁斯卡尔的时间复杂度为______O(elog2e)____________；它对________稀疏________图较为适合。

---

5．给定表（55，63，44，38，75，80，31，56），用筛选法建立初始堆，则初始堆表为________{31,38,44,56,75,80,55,63}_或 （80，75，55， 56，63，44，31，38）________。

---

6．已知二叉树中叶子数为50，仅有一个孩子的结点数为30，则总结点数为
__129 。

---

7．已知8个数据元素由（35，75，40，15，20，55，95，65）按照依次插入结点的方法生成一棵二叉排序树后，最后两层上的结点总数为______2________

---

8．假设有n个关键字，它们具有相同的Hash函数值，用线性探测方法解决冲突，把这n个关键字散列到大小为n的地址空间中，共计需要做_____n(n+1)/2_ 次插入和探测操作。

---

9．如果含n个顶点的图形成一个环，则它有____n____颗生成树。

n个顶点形成的环有n条边，若得到生成树只需要删除这n条边中的任意一条即可，
所以得到n棵生成树。
1
2

---

10．对有17个元素的有序表A[1…17]作二分查找，在查找其等于A[8]的元素时，被比较的元素的下标依次是____9,4,6,7,8________________________。

---

LZH 组五

1．如果要将序列{50,16,23,68,94,70,73}建成堆，则只需把16与__50___相互交换。

---

2._如果含n个顶点的图形成一个环，则它有____n_____棵生成树。

---

3．设有一个10阶的对称矩阵A，采用压缩存储方式以行序为主序存储，a00为第一个元素，其存储地址为0，每个元素占有1个存储地址空间，则a85的地址为_________41_________。

---

4．如果结点A有3个兄弟，而且B是A的双亲，则B的度是___4___

---

5．一个无序序列可以通过构造一棵_______二叉排序______树而变成一个有序序列，构造树的过程即为对无序序列进行排序的过程。

---

6．____直接定址______法构造的哈希函数肯定不会发生冲突。

---

7.求从某源点到其余各顶点的Dijkstra算法，当图的顶点数为10，用邻接矩阵表示图时计算时间约为10ms，则当图的顶点数为40时，计算时间为___160___ms

---

8._设一棵后序线索树的高度是50，结点x是树中的一个结点，其双亲是结点y，_y的右子树高度是31，x是y的左孩子，则确定x的后继最多需经过___31____个中间结点（不含后继及x本身）

---

9．对于单向链表，在两个结点之间插入一个新结点时需修改的指针
共有________2_________个。

---

10.利用直接选择排序算法对n个记录进行排序，最坏情况下，记录交换的次数为______n-1______。

---

LZH 组六

1．G是一个非连通无向图，共有28条边，则该图至少有____9______ 个顶点。

n个顶点的无向图中,边数e≤n(n-1)/2,将e=28代入,有n≥8,
现已知无向图非连通,则n=9。
1
2

---

2．复杂度为O(nlog2n)的排序方法有__________堆排序______、希尔排序 等。

---

3．若以{4,5,6,7,8}作为叶子结点的权值构造哈夫曼树，则其带权路径长度是__________69__________。

---

4．8层完全二叉树至少有___128_____ 个结点，拥有100个结点的完全二叉树的最大层数是___________7________。

最多的节点数是2^8^ -1，最少应该是2^7^
1

---

5．有一个有序表为{1,3,9,12,32,41,45,62,75,77,82,95,100}，当用折半法查找值为82的结点时，经过_____4_______次比较查找成功。

---

6．一组记录的关键码为(46,79,56,38,40,84)，则利用快速排序方法，以第一个记录为基准得到的第一次划分结果是________{40,38,46,56,79,84}________

---

7．在长度为n的顺序存放的线性表中删除第i个元素（1<=i<=n）时，需向前移动________n-i______ 个元素

---

8．用S表示入栈操作，X表示出栈操作，若元素入栈顺序为1234，为了得到1342的出栈顺序，相应的S和X操作串为___SXSSXSXX___________ 。

---

9．构造哈希（hash）函数的方法有_____直接定址法_____、数字分析法、_____除留余数法_____等。

---

10．具有n个结点的二叉树，采用二叉链表存储，共有_____n+1_____ 个空链域。

---

LZH 组七

1．具有10个顶点的无向图，边的总数最多为__45_____。

---

2.设n0为哈夫曼树的叶子结点数目，则该哈夫曼树共有__ 2n-1__ 个结点。

---

3．设有一个10阶的对称矩阵A，采用压缩存储方式以行序为主序存储，a00为第一个元素，其存储地址为0，每个元素占有1个存储地址空间，则a85的地址为_____41_ __ 。

---

4．如果结点A有3个兄弟，而且B是A的双亲，则B的度是_4__

---

5．一个无序序列可以通过构造一棵___二叉排序___ 树而变成一个有序序列，构造树的过程即为对无序序列进行排序的过程。

---

6．__直接定址法___法构造的哈希函数肯定不会发生冲突。

---

4.求从某源点到其余各顶点的Dijkstra算法，当图的顶点数为10，用邻接矩阵表示图时计算时间约为10ms，则当图的顶点数为40时，计算时间为_160__ms

---

5.设一棵后序线索树的高度是50，结点x是树中的一个结点，其双亲是结点y， y的右子树高度是31，x是y的左孩子，则确定x的后继最多需经过__31_ 个 中间结点（不含后继及x本身）

---

9．对于单向链表，在两个结点之间插入一个新结点时需修改的指针
共有___2_____ 个。

---

10 .有一个有序表为{1,3,9,12,32,41,45,62,75,77,82,95,100}，当用折半法查找值为82的结点时，经过__4____次比较查找成功。

---

四、LB组

LB组一

1． 若已知一个栈的入栈序列是1,2,3,…,n，其输出序列是p1,p2,p3,…,pn，若p1=n，则pi为___n-i+1_____

---

2． 多元树的先根序列和其对应的二叉树的____先序遍历序列____ 是一样的。

---

3．具有n个结点的二叉树，采用二叉链表存储，共有___n+1__ 个空链域。

---

4．在一个具有n个结点的无向图中，要连通全部顶点至少需要___n-1_ 条边。

---

5．有一个有序表为{1,3,9,12,32,41,45,62,75,77,82,95,100}，当用折半法查找值为82的结点时，经过__4____次比较查找成功。

---

6．一组记录的关键码为(46,79,56,38,40,84)，则利用快速排序方法，以第一个记录为基准得到的第一次划分结果是______{40,38,46,56,79,84}___________

---

7．在长度为n的顺序存放的线性表中删除第i个元素（1<=i<=n）时，需向前移动____n-i___ 个元素

---

8．操作系统不是算法，因为_____操作系统不满足有穷性_______________ 。

---

9．N.Wirth教授曾提出一个著名的公式：数据结构_+_算法 = 程序

---

LB组二

1．树的后根序列和其对应的二叉树的____中序遍历______是一样的。

---

2．在有n个关键字的、有序的、顺序存储的表中查找时，最有效的查找算法是___折半查找_____。

---

3．程序_ 是用计算机语言表述的算法，流程图 是图形化的算法。

---

4．在顺序表中插入或删除一个元素，需移动的元素个数与_____表的长度和元素的位置_____有关。

---

5．在解决计算机主机与打印机之间的速度不匹配问题时通常设置一个打印数据缓冲区，该缓冲区应是一个_____队列______结构。

---

6．结点A有三个兄弟，B是A的双亲结点，结点B的度是______4_____。

---

7．包含21个结点的二叉哈夫曼树的高度至多为____11____。（设根结点的高度为1）

---

8．三个结点的树的共有____2___种形态，三个结点的二叉树共有___5____种形态。

---

LB组三

1． 若一棵二叉树有10个叶结点，则该二叉树中度为2的结点的个数为____9____。

---

2． 若对线性表进行的操作主要不是插入和删除，则该线性表宜采用_____顺序表_______存储结构；若频繁地对线性表进行插入和删除操作，则该线性表宜采用_____链表_______存储结构。

---

3． 若完全二叉树中有1020个结点，则其中叶子结点数为_510__ ，有_ 510__个结点拥有左孩子，又有 511_ ___个结点没有右孩子。

---

4． 线性表的查找方法有__折半查找_____ 、顺序查找____ 和___索引查找____。

---

5． 一组记录的关键码为(46,79,56,38,40,84)，则利用快速排序方法，以第一个记录为基准得到的第一次划分结果是_______{40,38,46,56,79,84}_。

---

LB组四

1． 从一维数组a[n]中顺序查找出一个最大值元素的时间复杂度为__O(n)，输出一个二维数组b[m][n]中所有元素值的时间复杂度为__O(mn)。

---

2． 假定一棵树的广义表表示为A(B(C,D(E,F,G),H(I,J)))，则树中所含的结点数为__10__个，树的度为__3__。

---

3． 在一个具有n个顶点的无向图中，要连通所有顶点则至少需要__n-1__条边。

---

4． 在线性表的__链表__存储中，对每一个元素只能采用顺序查找。

---

5． 对于线性表(18,25,63,50,42,32,90)进行散列存储时，若选用H(K)=K % 9作为散列函数，则散列地址为0的元素有__3__个，散列地址为5的元素有__2__个。

---

6． 在稀疏矩阵所对应的三元组线性表中，每个三元组元素按__行__为主序、__列__为辅序的次序排列。

---

LB组五

1． 假定一棵树的广义表表示为A(B(C,D(E,F,G),H(I,J)))，则度为3、0的结点数分别为__2_____和____6____。

---

2． 假定一个线性表为(12,23,74,55,63,40,82,36)，若按Key % 3条件进行划分，使得同一余数的元素成为一个子表，则得到的三个子表分别为__{12，63,36}________________、{23，74}和{55,40,82}。

---

3． 在哈夫曼编码中，若编码长度只允许小于等于4，则除了已对两个字符编码为0和10外，还可以最多对____4____个字符编码。

最多还能对4个字符进行编码。它们的编码分别为：
1100
1101
1110
1111
1
2
3
4
5

---

4． 每次直接或通过基准元素间接比较两个元素，若出现逆序排列时就交换它们的位置，此种排序方法叫做___快速_____排序。

---

5． 在下面程序段中，s=s+p语句的执行次数为____n______，p*=j语句的执行次数为____n(n+1)/2______，该程序段的时间复杂度为_____O(n²)______。
int i=0,s=0;
while(++i<=n) {
_________ int p=1;
_________ for(int j=1;j<=i;j++) p*=j;
_________ s=s+p;
}

---

LB组六

1． 时间复杂度O(1)的意思是_______时间开销不随问题的规模变化______________。

---

2． 若长度为n的非空线性表采用顺序存储结构，删除表的第i个数据元素，需要移动表中_______n-i_________________个数据元素（设线性表的首元素是第1个元素）。

---

3． 设存储分配是从低地址到高地址进行的。若每个数据元素占用4个存储单元，则某数据元素的地址是指它所占用的单元的__________第一个单元的地址__________。

---

4． 将一个20阶的五对角矩阵中所有非零元素压缩存储到一个一维数组中，该一维数组至少应该有_______94__________个数组元素才行。

类似这种

---

5． 当队列的最大长度难以估计时，队列最好采用______链式_________存储结构。

---

6． 若某堆栈初始为空，PUSH与POP分别表示对堆栈进行一次进栈与出栈操作，那么，对于输入序列a,b,c,d,e，经过PUSH，PUSH，POP，PUSH，POP，PUSH，PUSh，POP以后，输出序列应该是____b,c,e__________。

---

7． 设n个数据元素的进栈序列为P1，P2，P3，……，Pn，出栈序列为1，2，3，……,n，若Pn_=1，则Pi(1≤i

---

8． 在建立散列表时，若散列函数为H(k),a和b分别为关键字值，则当
___________分别把a和b代入H
(k)得到的计算结果相同______________________时，称此现象为为散列冲突。

---

9． 若对序列(fang,deng,an,wang,shi,bai,tang,liu)采用快速排序法按字典顺序进行排序，并且以序列的第一个元素作为分界元素，当该分界元素的排序最终位置确定那一刻，序列的状态是______{bai，deng，an, fang,shi,wang,tang,liu}_____________________________。

---

10． 冒泡排序法、快速排序法、堆积排序法和二路归并排序法四种排序法中，要求辅助空间最多的方法是_______二路归并排序法___________________排序法。

---

LB组七

1． 已知二叉树的中序遍历序列为B,H,D,C,E,F,A,G，后遍历序列为H,D,F,E,C,B,G,A,其前序遍历列为_ABCDHEFG_。

---

2． 若一个非连通的无向图最多有21条边，则该无向图至少有 __8_个顶点。

---

3． 若具有n个顶点的无向连通图采用邻接矩阵表示，则邻接矩阵中至少有____2（n-1）____个非零元素。

---

4． 若从无向图的任意一个顶点出发进行一次深度优先搜索便可以访问该图的所有顶点，则该图一定是一个_________连通_______图。

---

5． 将数据元素2，4，6，8，10，12，14，16，18，20依次存放于一个一维数组中（设该数组第一个元素的下标为1），然后采用折半查找元素15，被比较过的数组元素的下标依次为___5,8,6,7__________。

---

6． 顺序查找法，折半查找法，树形查找法和散列查找法这四种方法中，只有________散列查找法_____________的平均查找长度与元素的个数n无关。

---

7． 设无向连通图G的顶点数与边数和一立方体相同，即有8个顶点和12条边。任意一棵G的生成树共有_________7_______条边

---

8． 字符串’abcd’中共有________9________个长度大于0小于4的子串。

---

9． 将字符数组a[0…7,0…7]按行优先次序存储在起始地址为1000的连续的内存单元中，则元素a[6,2]的地址是：1050____

---

10． 已知某带权连通无向图采用邻接矩阵存储方式，邻接矩阵以三元组表形式给出，部包括主对角线元素在内的下三角形部分元素对应的各三元组分别为(2,1,7),(3,1,6),(3,2,8),(4,1,9)(4,2,4),(4,3,6),(5,1, ),(5,2,4),(5,3, ),(5,4,2)。该连通图的最小生成树的权值之和是 18 。

---

LB组八

1． 以{5，6，8，10，15}作为叶子结点的权值所构造的哈夫曼树的带权路径长度是___99_____。

---

2． 判断一个无向图是一棵树的条件是________连通、无回路______________。

---

3． 设n0为哈夫曼树的叶子结点数目，则该哈夫曼树共有_____2n0-1______个结点。

---

4． 一个无序序列可以通过构造一棵_______二叉排序__________树而变成一个有序序列，构造树的过程即为对无序序列进行排序的过程。

---

5． 如果结点A有_3个兄弟，而且B是A的双亲，则B的度是_______4______。

---

6． 设有向图有n个顶点和e条边，进行拓扑排序时，总的时间复杂度为___O(n+e)__

---

7． 在排序算法中，每次从未排序的记录中挑出最小（或最大）关键码字的记录，加入到已排序记录的恰当位置，该排序方法叫______直接选择排序法____________。

---

8． 用一维数组存放的一棵完全二叉树；ABCDEFGHIJKL。后序遍历该二叉树的访问结点序列是________HIDJKEBLFGCA_______________。

---

9． 设散列函数H(k)=K_mod_7,散列表的地址空间为0—6，则关键字为32的元素在哈希表中的下标为_____4__________。

---

10． 一棵非空二叉树的先序序列和后序序列正好相反，则树的形状是
只有根节点或单左子树_。

---