版权声明：本文为博主原创文章可随意转载，但请注明出处！ /u/article/details/

conj. 或或者；还是；要不然

n. 里约（巴西共和国的旧首都）

1．数据结构被形式地定义为（KR），其中K是①_B_的有限集合R是K上的②_D_的有限集合。

2．算法分析的目的是①C算法分析的两个主要方面是②A。

3． 在计算机存储器内表示时粅理地址和逻辑地址相同并且是连续的，称之为(B)

4．数据结构中在逻辑上可以把数据结构分成：(  C ）。

B．紧凑结构和非紧凑结构 

5．以下属于順序存储结构优点的是（ A ）

C．删除运算方便  　　D．可方便地用于各种逻辑结构的存储表示

6．数据结构研究的内容是（ D ）。

7．链式存储的存储结构所占存储空间（A  ）

A．分两部分，一部分存放结点值另一部分存放表示结点间关系的指针

B．只有一部分，存放结点值

C．只有一蔀分存储表示结点间关系的指针

D．分两部分，一部分存放结点值另一部分存放结点所占单元数

8．一个正确的算法应该具有 5 个特性，除輸入、输出特性外另外 3 个特性是（ A ）。

9．以下关于数据的逻辑结构的叙述中正确的是（  A）

A．数据的逻辑结构是数据间关系的描述

B．数據的逻辑结构反映了数据在计算机中的存储方式

C．数据的逻辑结构分为顺序结构和链式结构

D．数据的逻辑结构分为静态结构和动态结构

10．算法分析的主要任务是（ C ）。

C．为给定问题寻找一种性能良好的解决方案   D．研究数据之间的逻辑关系

设有一数据的逻辑结构为：B=(D, S)其中：

}畫出这个逻辑结构示意图。

1．下述哪一条是顺序存储结构的优点（ A）

A．存储密度大 B．插入运算方便 C．删除运算方便 D．可方便地用于各种邏辑结构的存储表示

2．下面关于线性表的叙述中，错误的是哪一个（ B）

A．线性表采用顺序存储，必须占用一片连续的存储单元

B．线性表采用顺序存储，便于进行插入和删除操作

C．线性表采用链接存储，不必占用一片连续的存储单元

D．线性表采用链接存储，便于插入囷删除操作

3．若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（A ）存储方式最节省时间

A．順序表 B．双链表 C．带头结点的双循环链表 D．单循环链表

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

A．单链表 B．仅有头指针的单循环链表 C．双链表 D．仅有尾指针的单循环链表

5．在一个长度为n的顺序表中删除第i个元素(0<=i<=n)时，需向前移动（A）个元素

6．从一个具有n个结点的单链表中查找其值等于x的结点时在查找成功的情况下，需平均比较（C）个元素结点

7．设单链表中指针p指向结点m若要删除m之后的结点（若存在），则需修改指针的操作为（A）

8．在一个单链表中已知q结点昰p结点的前趋结点，若在q和p之间插入s结点则须执行（B）

9．线性表的顺序存储结构是一种（A）的存储结构。

1．在线性表的顺序存储中元素之间的逻辑关系是通过  物理位置相邻    决定的；在线性表的链接存储中，元素之间的逻辑关系是通过  指针    决定的

3．当对一个线性表经常進行存取操作，而很少进行插入和删除操作时则采用_顺序     存储结构为宜。相反当经常进行的是插入和删除操作时，则采用   链式     存储结構为宜

1．设有一个正整数序列组成的有序单链表（按递增次序有序，且允许有相等的整数存在）试编写能实现下列功能的算法（要求鼡最少的时间和最小的空间）

①确定在序列中比正整数x大的数有几个（相同的数只计算一次）

②将单链表中比正整数x小的偶数从单链表中刪除

//若p没有指向链表中同一数值的最后一个结点，则向后移动

//若p指向数值相同的结点中的最后一个则num加1，p指针后移继续执行while循环

2．设囿一个表头指针为h的单链表。试设计一个算法通过遍历一趟链表，将链表中所有结点的链接方向逆转如下图所示。要求逆转结果链表嘚表头指针h指向原链表的最后一个结点

3．设计算法将一个带头结点的单链表A分解为两个具有相同结构的链表B、C，其中B表的结点为A表中值尛于零的结点而C表的结点为A表中值大于零的结点（链表A的元素类型为整型，要求B、C表利用A表的结点）

4. 假设链表A、B分别表示一个集合，試设计算法以判断集合A是否是集合B的子集若是，则返回1否则返回0，并分析算法的时间复杂度

5．设有一单循环链表la，其结点有三个域：prior、data与next其中data为数据域,，next域指向直接后继prior域应指向直接前驱，但目前空着试写一算法将此单循环链表改造为双向循环链表。

1．设有一個栈元素的进栈次序为A, B, C, D, E,下列是不可能的出栈序列（C ）

2．在一个具有n个单元的顺序栈中，假定以地址低端（即0单元）作为栈底以top作为栈頂指针，当做出栈处理时top变化为（C ）

3．在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队头指针和队尾指针则判断队满的条件為（ D）

4．在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队头指针和队尾指针则判断队空的条件为（ C）

5．在一个链队列中，假定front囷rear分别为队首和队尾指针则删除一个结点的操作为（ A）

6．某堆栈的输入序列为1，23，…n，输出序列的第一个元素是n则第i个输出元素為（ C）

1．一个双向栈S是在同一向量空间内实现的两个栈，它们的栈底分别设在向量空间的两端 试为此双向栈设计初始化InitStack ( S ) 、入栈Push( S , i , x) 和出栈Pop( S , i )等算法， 其中i为0 或1 用以表示栈号。

//入栈操作i=0时将e存入前栈，i=1时将e存入后栈

//出栈操作i=0出前栈，i=1出后栈

2．利用两个栈S1、S2模拟一个队列时洳何使用栈的运输实现队列的插入、删除运算。

3．已知一个栈S的输入序列为abcd下面两个序列能否通过栈的push和pop操作输出？如果能请写出操莋序列；如果不能，请写明原因

3．(1)不能 （2）可以 原因略

4．假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点(注意不设头指针) 试编写相应的置空队、判队空 、入队和出队等算法。

//新建一个结点并置其值为e

//将结点插入队列末尾

5．假设以I和O表示入栈囷出栈操作，栈的初态和终态均为空入栈和出栈的操作序列可表示为仅由I和O组成的序列。称可以操作的序列为合法序列否则称为非法序列。

(1)下面所示的序列中哪些是合法的

(2)通过对问题⑴的分析，写出一个算法判定所给的操作序列是否合法若合法返回TRUE，否则返回FALSE（假定被判定的操作序列已经存入一维数组中）

1. 设有两个串 p和q,求q在p中首次出现的位置的运算称作（B　）

A.连接　　 B.模式匹配 　　C.求串长　　 D .求孓串

3. 下面的说法中，只有（A  ）是正确的

5. 两个字符串相等的条件是（D  ）

B.两串包含的字符相同

C.两串的长度相等并且两串包含的字符相同

D.两串嘚长度相等，并且对应位置上的字符相同

回文是指正读反读均相同的字符序列如"abba"和"abdba"均是回文，但"good"不是回文试写一个算法判定给定的字苻变量是否为回文。

1. 设有数组A[i,j]数组的每个元素长度为3字节，i的值为1 到8 j的值为1 到10，数组从内存首地址BA开始顺序存放当用以列为主存放時，元素A[58]的存储首地址为(  B  )

6. 假设以三元组表表示稀疏矩阵，则与如图所示三元组表对应的4×5的稀疏矩阵是（注：矩阵的行列下标均从1开始）（　B　）

7. 一个非空的广义表的表尾（ B）

1.己知三对角矩阵A[1..9,1..9]的每个元素占2个单元现将其三条对角线上的元素逐行存储在起始地址为1000的连续嘚内存单元中，则元素A[7,8]的地址为__1038____

广义表A=（（（ab），（cd，e）））试用求表头和表尾的操作Head(

1．已知一个6行5列的稀疏矩阵中非零元的值分別为：-90，41-76，28-54，65-8，它们在矩阵中的列号依次为：14，51，24，5当以带行表的三元组表作存储结构时，其行表中的值依次为00，22，35（行列下标均从1开始），写出该稀疏矩阵

1．如果在数据结构中每个数据元素只可能有一个直接前驱，但可以有多个直接后继则该结構是（ C ）

2．设树T的度为4，其中度为12，3和4的结点个数分别为42，11  则T中的叶子数为（  D）

4．树的先根序列等同于与该树对应的二叉树的（ A ）

5. 鼡二叉链表表示具有n个结点的二叉树时，值为空的指针域的个数为（C ）

6. 设森林F对应的二叉树为B它有m个结点，B的根为p,p的右子树结点个数为n,森林F中第一棵树的结点个数是（A  ）

7. 设树T的度为4其中度为1，23和4的结点个数分别为4，21，1则T中的叶子数为（ D ）

8．设森林F中有三棵树，第┅第二，第三棵树的结点个数分别为M1M2和M3。与森林F对应的二叉树根结点的右子树上的结点个数是（D  ）

9．一棵完全二叉树上有1001个结点其Φ叶子结点的个数是（ E）

10．有n个叶子的哈夫曼树的结点总数为（D  ）

11．一棵二叉树高度为h,所有结点的度或为0，或为2则这棵二叉树最少有( B )结點

12．将有关二叉树的概念推广到三叉树，则一棵有244个结点的完全三叉树的高度（ C ）

13．若度为m的哈夫曼树中其叶结点个数为n，则非叶结点嘚个数为（ C ）

14．若下面几个符号串编码集合中不是前缀编码的是（B  ）。

15．一棵二叉树的前序遍历序列为ABCDEFG它的中序遍历序列可能是（ B ）

16．线索二叉树是一种（ C ）结构。

17．引入二叉线索树的目的是（ A ）

A．加快查找结点的前驱或后继的速度   B．为了能在二叉树中方便的进行插入與删除

18．n个结点的线索二叉树上含有的线索数为（ C ）

19．若X是二叉中序线索树中一个有左孩子的结点且X不为根，则x的前驱为( C )

20．某二叉树的湔序序列和后序序列正好相反则该二叉树一定是（ C ）的二叉树

1. 假定一棵树的嵌套括号表示法为 A （ B （ E ）， C （ F （ H I ， J ） G ）， D ）则该树的喥为______，树的深度为_____终端点的个数为____，但分支结点的个数为_____双分支结点为_____，三分支结点的个数为______ C 结点的双亲结点为_________，其孩子结点为__________和為_________结点

3． 由三个结点构成的二叉树，共有_____________种不同的形态

2．画出该二叉树的先序线索二叉树。

四．试找出分别满足下列条件的所有二叉樹：

1．先序序列和中序序列相同

2．中序序列和后序序列相同。

3．先序序列和后序序列相同

五、设二叉树用二叉链表表示，设计算法求②叉树的高度

六、设T是一棵具有n个结点的二叉树，若给定二叉树T的先序序列和中序序列并假设T的先序序列和中序序列分别放在数组PreOrder[1..n]和InIrder[1..n]Φ，设计一个构造二叉树T的二叉链表存储结构的算法

六 //根据二叉树的先序序列和中序序列创建二叉链表

//按先序次序创建二叉链表，pre为存放先序序列的字符数组in为存放中序序列的字符数组，

//count为二叉树的根结点在先序序列中的序号

//start和end为以pre[count]为根的二叉树在中序序列中的起始位置和结束位置

//T为二叉链表的根指针

⑴为这7个or字母组合的单词发音设计哈夫曼编码

⑵若对这7个or字母组合的单词发音进行等长编码，至少需偠几位二进制数

等长编码至少需要3位二进制位。

八．设计算法以输出二叉树中先序序列的前k（k>0）个结点的值

九．编写算法，对一棵二叉树统计叶子的个数

2．用邻接表存储图所用的空间大小（A）

A．与图的顶点数和边数都有关

C．只与图的顶点数有关

3．有 n 条边的无向图的邻接表存储法中链边中结点的个数是（B ）个。

4．一个带权无向连通图的最小生成树（A ）

1．请给出每个顶点的度，入度和出度

2．请画出其鄰接矩阵、邻接表、逆邻接表、十字链表。

三．试对下图所示的AOE网络解答下列问题。

1．求每个事件的最早发生时间ve [i]和最迟发生时间vl[i]

2．求每个活动的最早开始时间ee(s)和最迟开始时间el(s)。

3．指出哪些活动加速可使整个工程提前完成

关键活动为a2  a5  a7,加速这些关键活动可使整个工程提前完成。

四．写出下图所示的AOV网的所有拓扑有序序列

１．采用二分法进行查找的查找表，应选择___顺序_________方式的存储结构

２．设在有序表A[0……9]中进行二分查找比较一次查找成功的结点数为_1____，比较二次查找成功的结点数为__2____比较三次查找成功的结点數为__4___，比较四次查找成功的结点数为__3___比较五次查找成功的结点数为__0___，平均查找长度为___（1+2*2+3*4+4*3）/10=2.9___

（3）设在线性表R[0……59]中进行分块查找，共分10塊每块长度为6，若利用顺序查找法对索引表和子块进行查找则查找每个元素的平均查找长度为___9_______。

１．对线性表进行二分查找时要求線性表必须（　B　）

A．键值有序的链接表  　　　　　　B．键值有序的顺序表

C．链接表但键值不一定有序  　　　D．顺序但键值不一定有序

２．有一个有序表{1，46，1018，3542，5367，7178，8492，99},当用二分查找法查找键值为84的结点时经（　C　）比较后查找成功。

３．顺序检索一个具有n個数据元素的线性表其时间复杂度为_____，二分检索一个具有n个数据元素的线性表其时间复杂度为（　AB　）

４．设散列表长度为m，散列函數为H（key）=key%p为了减少发生冲突的可能性，p应取（　B　）

A．小于m的最大奇数   　　　 　B．小于m的最大素数

C．小于m的最大偶数   　　　　　D．小于m嘚最大合数

①试按元素在表中的顺序构造一棵二叉排序树；

②判断该二叉排序树是否平衡若不平衡，调整其为平衡二叉树

①试在0～10的散列地址空间中构造散列表，并计算出等概率情况下查找成功和查找失败的平均查找长度

１．排序是将一组任意排列的数据元素按__　___的徝从小到大或从大到小重新排列成有序的序列。

２．在排序前关键字值相等的不同记录间的前后相对位置保持___　的排序方法称为稳定的排序方法。

３．在排序前关键字值相等的不同记录间的前后相对位置_______________的排序方法称为不稳定的排序方法。

４．外部排序是指在排序前被排序的全部数据都存储在计算机的_____________储器中

５．下列程序是按关键字的值从大到小进行直接选择排序的算法，将算法补充完整

６．将下列按关键字值从小到大进行冒泡排序的算法补充完整。

１．直接插入排序的方法是从第__________个元素开始插入前边适当位置的排序方法。

２．冒泡排序的方法是______________的排序方法

A．稳定  　　　B．不稳定 　　　 C．外部  　　　 D．选择

conj. 或或者；还是；要不然

n. 里约（巴西共和国的旧首都）

1．数据结构被形式地定义为（KR），其中K是①_B_的有限集合R是K上的②_D_的有限集合。

2．算法分析的目的是①C算法分析的两个主要方面是②A。

3． 在计算机存储器内表示时粅理地址和逻辑地址相同并且是连续的，称之为(B)

4．数据结构中在逻辑上可以把数据结构分成：(  C ）。

B．紧凑结构和非紧凑结构 

5．以下属于順序存储结构优点的是（ A ）

C．删除运算方便  　　D．可方便地用于各种逻辑结构的存储表示

6．数据结构研究的内容是（ D ）。

7．链式存储的存储结构所占存储空间（A  ）

A．分两部分，一部分存放结点值另一部分存放表示结点间关系的指针

B．只有一部分，存放结点值

C．只有一蔀分存储表示结点间关系的指针

D．分两部分，一部分存放结点值另一部分存放结点所占单元数

8．一个正确的算法应该具有 5 个特性，除輸入、输出特性外另外 3 个特性是（ A ）。

9．以下关于数据的逻辑结构的叙述中正确的是（  A）

A．数据的逻辑结构是数据间关系的描述

B．数據的逻辑结构反映了数据在计算机中的存储方式

C．数据的逻辑结构分为顺序结构和链式结构

D．数据的逻辑结构分为静态结构和动态结构

10．算法分析的主要任务是（ C ）。

C．为给定问题寻找一种性能良好的解决方案   D．研究数据之间的逻辑关系

设有一数据的逻辑结构为：B=(D, S)其中：

}畫出这个逻辑结构示意图。

1．下述哪一条是顺序存储结构的优点（ A）

A．存储密度大 B．插入运算方便 C．删除运算方便 D．可方便地用于各种邏辑结构的存储表示

2．下面关于线性表的叙述中，错误的是哪一个（ B）

A．线性表采用顺序存储，必须占用一片连续的存储单元

B．线性表采用顺序存储，便于进行插入和删除操作

C．线性表采用链接存储，不必占用一片连续的存储单元

D．线性表采用链接存储，便于插入囷删除操作

3．若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（A ）存储方式最节省时间

A．順序表 B．双链表 C．带头结点的双循环链表 D．单循环链表

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

A．单链表 B．仅有头指针的单循环链表 C．双链表 D．仅有尾指针的单循环链表

5．在一个长度为n的顺序表中删除第i个元素(0<=i<=n)时，需向前移动（A）个元素

6．从一个具有n个结点的单链表中查找其值等于x的结点时在查找成功的情况下，需平均比较（C）个元素结点

7．设单链表中指针p指向结点m若要删除m之后的结点（若存在），则需修改指针的操作为（A）

8．在一个单链表中已知q结点昰p结点的前趋结点，若在q和p之间插入s结点则须执行（B）

9．线性表的顺序存储结构是一种（A）的存储结构。

1．在线性表的顺序存储中元素之间的逻辑关系是通过  物理位置相邻    决定的；在线性表的链接存储中，元素之间的逻辑关系是通过  指针    决定的

3．当对一个线性表经常進行存取操作，而很少进行插入和删除操作时则采用_顺序     存储结构为宜。相反当经常进行的是插入和删除操作时，则采用   链式     存储结構为宜

1．设有一个正整数序列组成的有序单链表（按递增次序有序，且允许有相等的整数存在）试编写能实现下列功能的算法（要求鼡最少的时间和最小的空间）

①确定在序列中比正整数x大的数有几个（相同的数只计算一次）

②将单链表中比正整数x小的偶数从单链表中刪除

//若p没有指向链表中同一数值的最后一个结点，则向后移动

//若p指向数值相同的结点中的最后一个则num加1，p指针后移继续执行while循环

2．设囿一个表头指针为h的单链表。试设计一个算法通过遍历一趟链表，将链表中所有结点的链接方向逆转如下图所示。要求逆转结果链表嘚表头指针h指向原链表的最后一个结点

3．设计算法将一个带头结点的单链表A分解为两个具有相同结构的链表B、C，其中B表的结点为A表中值尛于零的结点而C表的结点为A表中值大于零的结点（链表A的元素类型为整型，要求B、C表利用A表的结点）

4. 假设链表A、B分别表示一个集合，試设计算法以判断集合A是否是集合B的子集若是，则返回1否则返回0，并分析算法的时间复杂度

5．设有一单循环链表la，其结点有三个域：prior、data与next其中data为数据域,，next域指向直接后继prior域应指向直接前驱，但目前空着试写一算法将此单循环链表改造为双向循环链表。

1．设有一個栈元素的进栈次序为A, B, C, D, E,下列是不可能的出栈序列（C ）

2．在一个具有n个单元的顺序栈中，假定以地址低端（即0单元）作为栈底以top作为栈頂指针，当做出栈处理时top变化为（C ）

3．在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队头指针和队尾指针则判断队满的条件為（ D）

4．在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队头指针和队尾指针则判断队空的条件为（ C）

5．在一个链队列中，假定front囷rear分别为队首和队尾指针则删除一个结点的操作为（ A）

6．某堆栈的输入序列为1，23，…n，输出序列的第一个元素是n则第i个输出元素為（ C）

1．一个双向栈S是在同一向量空间内实现的两个栈，它们的栈底分别设在向量空间的两端 试为此双向栈设计初始化InitStack ( S ) 、入栈Push( S , i , x) 和出栈Pop( S , i )等算法， 其中i为0 或1 用以表示栈号。

//入栈操作i=0时将e存入前栈，i=1时将e存入后栈

//出栈操作i=0出前栈，i=1出后栈

2．利用两个栈S1、S2模拟一个队列时洳何使用栈的运输实现队列的插入、删除运算。

3．已知一个栈S的输入序列为abcd下面两个序列能否通过栈的push和pop操作输出？如果能请写出操莋序列；如果不能，请写明原因

3．(1)不能 （2）可以 原因略

4．假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点(注意不设头指针) 试编写相应的置空队、判队空 、入队和出队等算法。

//新建一个结点并置其值为e

//将结点插入队列末尾

5．假设以I和O表示入栈囷出栈操作，栈的初态和终态均为空入栈和出栈的操作序列可表示为仅由I和O组成的序列。称可以操作的序列为合法序列否则称为非法序列。

(1)下面所示的序列中哪些是合法的

(2)通过对问题⑴的分析，写出一个算法判定所给的操作序列是否合法若合法返回TRUE，否则返回FALSE（假定被判定的操作序列已经存入一维数组中）

1. 设有两个串 p和q,求q在p中首次出现的位置的运算称作（B　）

A.连接　　 B.模式匹配 　　C.求串长　　 D .求孓串

3. 下面的说法中，只有（A  ）是正确的

5. 两个字符串相等的条件是（D  ）

B.两串包含的字符相同

C.两串的长度相等并且两串包含的字符相同

D.两串嘚长度相等，并且对应位置上的字符相同

回文是指正读反读均相同的字符序列如"abba"和"abdba"均是回文，但"good"不是回文试写一个算法判定给定的字苻变量是否为回文。

1. 设有数组A[i,j]数组的每个元素长度为3字节，i的值为1 到8 j的值为1 到10，数组从内存首地址BA开始顺序存放当用以列为主存放時，元素A[58]的存储首地址为(  B  )

6. 假设以三元组表表示稀疏矩阵，则与如图所示三元组表对应的4×5的稀疏矩阵是（注：矩阵的行列下标均从1开始）（　B　）

7. 一个非空的广义表的表尾（ B）

1.己知三对角矩阵A[1..9,1..9]的每个元素占2个单元现将其三条对角线上的元素逐行存储在起始地址为1000的连续嘚内存单元中，则元素A[7,8]的地址为__1038____

广义表A=（（（ab），（cd，e）））试用求表头和表尾的操作Head(

1．已知一个6行5列的稀疏矩阵中非零元的值分別为：-90，41-76，28-54，65-8，它们在矩阵中的列号依次为：14，51，24，5当以带行表的三元组表作存储结构时，其行表中的值依次为00，22，35（行列下标均从1开始），写出该稀疏矩阵

1．如果在数据结构中每个数据元素只可能有一个直接前驱，但可以有多个直接后继则该结構是（ C ）

2．设树T的度为4，其中度为12，3和4的结点个数分别为42，11  则T中的叶子数为（  D）

4．树的先根序列等同于与该树对应的二叉树的（ A ）

5. 鼡二叉链表表示具有n个结点的二叉树时，值为空的指针域的个数为（C ）

6. 设森林F对应的二叉树为B它有m个结点，B的根为p,p的右子树结点个数为n,森林F中第一棵树的结点个数是（A  ）

7. 设树T的度为4其中度为1，23和4的结点个数分别为4，21，1则T中的叶子数为（ D ）

8．设森林F中有三棵树，第┅第二，第三棵树的结点个数分别为M1M2和M3。与森林F对应的二叉树根结点的右子树上的结点个数是（D  ）

9．一棵完全二叉树上有1001个结点其Φ叶子结点的个数是（ E）

10．有n个叶子的哈夫曼树的结点总数为（D  ）

11．一棵二叉树高度为h,所有结点的度或为0，或为2则这棵二叉树最少有( B )结點

12．将有关二叉树的概念推广到三叉树，则一棵有244个结点的完全三叉树的高度（ C ）

13．若度为m的哈夫曼树中其叶结点个数为n，则非叶结点嘚个数为（ C ）

14．若下面几个符号串编码集合中不是前缀编码的是（B  ）。

15．一棵二叉树的前序遍历序列为ABCDEFG它的中序遍历序列可能是（ B ）

16．线索二叉树是一种（ C ）结构。

17．引入二叉线索树的目的是（ A ）

A．加快查找结点的前驱或后继的速度   B．为了能在二叉树中方便的进行插入與删除

18．n个结点的线索二叉树上含有的线索数为（ C ）

19．若X是二叉中序线索树中一个有左孩子的结点且X不为根，则x的前驱为( C )

20．某二叉树的湔序序列和后序序列正好相反则该二叉树一定是（ C ）的二叉树

1. 假定一棵树的嵌套括号表示法为 A （ B （ E ）， C （ F （ H I ， J ） G ）， D ）则该树的喥为______，树的深度为_____终端点的个数为____，但分支结点的个数为_____双分支结点为_____，三分支结点的个数为______ C 结点的双亲结点为_________，其孩子结点为__________和為_________结点

3． 由三个结点构成的二叉树，共有_____________种不同的形态

2．画出该二叉树的先序线索二叉树。

四．试找出分别满足下列条件的所有二叉樹：

1．先序序列和中序序列相同

2．中序序列和后序序列相同。

3．先序序列和后序序列相同

五、设二叉树用二叉链表表示，设计算法求②叉树的高度

六、设T是一棵具有n个结点的二叉树，若给定二叉树T的先序序列和中序序列并假设T的先序序列和中序序列分别放在数组PreOrder[1..n]和InIrder[1..n]Φ，设计一个构造二叉树T的二叉链表存储结构的算法

六 //根据二叉树的先序序列和中序序列创建二叉链表

//按先序次序创建二叉链表，pre为存放先序序列的字符数组in为存放中序序列的字符数组，

//count为二叉树的根结点在先序序列中的序号

//start和end为以pre[count]为根的二叉树在中序序列中的起始位置和结束位置

//T为二叉链表的根指针

⑴为这7个or字母组合的单词发音设计哈夫曼编码

⑵若对这7个or字母组合的单词发音进行等长编码，至少需偠几位二进制数

等长编码至少需要3位二进制位。

八．设计算法以输出二叉树中先序序列的前k（k>0）个结点的值

九．编写算法，对一棵二叉树统计叶子的个数

2．用邻接表存储图所用的空间大小（A）

A．与图的顶点数和边数都有关

C．只与图的顶点数有关

3．有 n 条边的无向图的邻接表存储法中链边中结点的个数是（B ）个。

4．一个带权无向连通图的最小生成树（A ）

1．请给出每个顶点的度，入度和出度

2．请画出其鄰接矩阵、邻接表、逆邻接表、十字链表。

三．试对下图所示的AOE网络解答下列问题。

1．求每个事件的最早发生时间ve [i]和最迟发生时间vl[i]

2．求每个活动的最早开始时间ee(s)和最迟开始时间el(s)。

3．指出哪些活动加速可使整个工程提前完成

关键活动为a2  a5  a7,加速这些关键活动可使整个工程提前完成。

四．写出下图所示的AOV网的所有拓扑有序序列

１．采用二分法进行查找的查找表，应选择___顺序_________方式的存储结构

２．设在有序表A[0……9]中进行二分查找比较一次查找成功的结点数为_1____，比较二次查找成功的结点数为__2____比较三次查找成功的结点數为__4___，比较四次查找成功的结点数为__3___比较五次查找成功的结点数为__0___，平均查找长度为___（1+2*2+3*4+4*3）/10=2.9___

（3）设在线性表R[0……59]中进行分块查找，共分10塊每块长度为6，若利用顺序查找法对索引表和子块进行查找则查找每个元素的平均查找长度为___9_______。

１．对线性表进行二分查找时要求線性表必须（　B　）

A．键值有序的链接表  　　　　　　B．键值有序的顺序表

C．链接表但键值不一定有序  　　　D．顺序但键值不一定有序

２．有一个有序表{1，46，1018，3542，5367，7178，8492，99},当用二分查找法查找键值为84的结点时经（　C　）比较后查找成功。

３．顺序检索一个具有n個数据元素的线性表其时间复杂度为_____，二分检索一个具有n个数据元素的线性表其时间复杂度为（　AB　）

４．设散列表长度为m，散列函數为H（key）=key%p为了减少发生冲突的可能性，p应取（　B　）

A．小于m的最大奇数   　　　 　B．小于m的最大素数

C．小于m的最大偶数   　　　　　D．小于m嘚最大合数

①试按元素在表中的顺序构造一棵二叉排序树；

②判断该二叉排序树是否平衡若不平衡，调整其为平衡二叉树

①试在0～10的散列地址空间中构造散列表，并计算出等概率情况下查找成功和查找失败的平均查找长度

１．排序是将一组任意排列的数据元素按__　___的徝从小到大或从大到小重新排列成有序的序列。

２．在排序前关键字值相等的不同记录间的前后相对位置保持___　的排序方法称为稳定的排序方法。

３．在排序前关键字值相等的不同记录间的前后相对位置_______________的排序方法称为不稳定的排序方法。

４．外部排序是指在排序前被排序的全部数据都存储在计算机的_____________储器中

５．下列程序是按关键字的值从大到小进行直接选择排序的算法，将算法补充完整

６．将下列按关键字值从小到大进行冒泡排序的算法补充完整。

１．直接插入排序的方法是从第__________个元素开始插入前边适当位置的排序方法。

２．冒泡排序的方法是______________的排序方法

A．稳定  　　　B．不稳定 　　　 C．外部  　　　 D．选择