2022年中南林业科技大学计算机科学与技术专业《数据结构与算法》
科目期末试卷A（有答案）
一、选择题
1、从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为（ ）排序法。 A.插入 B.选择 C.希尔 D.二路归并 2、下列说法不正确的是（ ）。
A.图的遍历是从给定的源点出发每个顶点仅被访问一次 B.遍历的基本方法有两种：深度遍历和广度遍历 C.图的深度遍历不适用于有向图 D.图的深度遍历是一个递归过程 3、链表不具有的特点是（ ）。
A.插入、删除不需要移动元素 B.可随机访问任一元素 C.不必事先估计存储空间 D.所需空间与线性长度成正比 4、动态存储管理系统中，通常可有（ ）种不同的分配策略。 A.1 B.2 C.3 D.4
5、最大容量为n的循环队列，队尾指针是rear，队头：front，则队空的条件是（ ）。 A.（rear+1）MOD n=front B.rear=front C.rear+1=front
D.（rear-1）MOD n=front
6、已知字符串S为“abaabaabacacaabaabcc”，模式串t为“abaabc”，采用KMP算法进行匹配，第一次出现“失配”（s!＝t）时，i＝j＝5，则下次开始匹配时，i和j的值分别（ ）。
A．i＝1，j＝0 B．i＝5，j＝0 C．i＝5，j＝2 D．i＝6，j＝2
7、若一棵二叉树的前序遍历序列为a，e，b，d，c，后序遍历序列为b， c，d，e，a，则根结点的孩子结点（ ）。
A．只有e B．有e、b C．有e、c D．无法确定
8、一棵哈夫曼树共有215个结点，对其进行哈夫曼编码，共能得到（ ）个不同的码字。
A.107 B.108 C.214 D.215 9、在下述结论中，正确的有（ ）。 ①只有一个结点的二叉树的度为0。 ②二叉树的度为2。
③二叉树的左右子树可任意交换。④深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。 A.①②③ B.⑦③④ C.②④ D.①④
10、若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL为（ ）。 A.(n-1)/2 B.n/2 C.(n+1)/2 D.n
二、填空题
11、属于不稳定排序的有______。
12、如果按关键码值递增的顺序依次将关键码值插入到二叉排序树中，则对这样的二叉排序树检索时，平均比较次数为______。
13、已知有序表为（12，18，24，35，47，50，62，83，90，115， 134）当用二分法查找90时，需______次查找成功，查找47时______成功，查找100时，需______次才能确定不成功。
14、在一棵m阶B-树中，若在某结点中插入一个新关键字而引起该结点，则此结点中原有的关键字的个数是______；若在某结点中删除一个关键字而导致结点合并，则该结点中原有的关键字的个数是______。
15、n个顶点的有向图用邻接矩阵array表示，下面是其拓扑排序算法，试补充完整。 注：(1)图的顶点号从0开始计。
(2)indegree是有n个分量的一维数组，放顶点的入度， (3)函数crein用于计算顶点入度。
(4)有三个函数push(data)，pop()，check()其含义为数据data入栈，出栈和测试栈是否空(不空返回l，否则0)。
16、当两个栈共享一存储区时，栈利用一维数组stack（1，n）表示，两栈顶指针为top[1]与top[2]，则当栈1空时，top[1]为______，栈2空时， top[2]为______，栈满时为______。 17、设数组A[0..8，1..10]，数组中任一元素A[i，j]均占内存48个二进制位，从首地址2000开始连续存放在主内存里，主内存字长为16位，那么
（1） 存放该数组至少需要的单元数是______。
（2） 存放数组的第8列的所有元素至少需要的单元数______。 （3） 数组按列存储时，元素A[5，8]的起始地址是______。
18、设T和P是两个给定的串，在T中寻找等于P的子串的过程称为______，又称P为______。
三、判断题
19、倒排文件的目的是为了多关键字查找。（ ） 20、倒排序文件的优点是维护简单。（ ） 21、数组不适合作为任何二叉树的存储结构。（ ） 22、串是一种数据对象和操作都特殊的线性表。（ ） 23、二叉树是一般树的特殊情形。（ ）
24、一般来说，若深度为k的n个结点的二叉树只有最小路径长度，那么
从根结点到第k-1层具有的最多结点数为2k-1-1，余下的n-2k-1+1个结点在第k层的任一位置上。（ ）
25、在外部排序过程中，对长度为n的初始序列进行“置换-选择”排序时，可以得到的最大初始有序段的长度不超过n/2。（ ）
26、为提高排序速度，进行外排序时，必须选用最快的内排序算法。（ ） 27、当改变网上某一关键路径上任一关键活动后，必将产生不同的关键路径。（ ） 28、无环有向图才能进行拓扑排序。（ ）
四、简答题
29、设有n个元素采用起泡排序法进行排序，通常需要进行多少趟排序? 对于第J趟起泡通常需要进行多少次关键字比较?在程序设计中如何设置判断条件，有可能使起泡趟数可以减少并且能完成排序。
30、假定对有序表：（3，4，5，7，24，30，42，54，63，72，87， 95）进行折半查找，试回答下列问题：
（1）画出描述折半查找过程的判定树。 （2）若查找元素54，需依次与哪些元素比较? （3）若查找元素90，需依次与哪些元素比较?
（4）假定每个元素的查找概率相等，求查找成功时的平均查找长度。
31、对下面的关键字集{30，15，21，40，25，26，36，37}若查找表的装填因子为0.8，采用线性探测再哈希方法解决冲突，做：（1）设计哈希函数；（2）画出哈希表；（3）计算查找成功和查找失败的平均查找长度；（4）写出将哈希表中某个数据元素删除的算法。
五、算法设计题
32、已知指针p指向带表头的中根次序线索二叉树中的某结点，试写一算法FFA（p，q），该算法寻找结点p的父亲结点q。设线索二叉树的结点结构、表头结点结构和空树结构分别为（LTAG，LLINK，INFO， RLlNK，RTAG），且规定线索树的最左下结点的LLINK域和最右下结点的RLINKt域指向表头。
33、线性表中元素存放在向量A（1，…，l）中，元素是整型数。试写出递归算法求出A中的最大和最小元素。
34、假设以I和O分别表示入栈和出栈操作。栈的初态和终态均为空，入栈和出栈的操作序列可表示为仅由I和O组成的序列，称可以操作的序列为合法序列，否则称为非法序列。 （1） 下面所示的序列中哪些是合法的? A．IOIIOIOO B．IOOIOIIO C．IIIOIOIO D．IIIOOIO
（2） 通过对（1）的分析，写出一个算法，判定所给的操作序列是否合法。若合法，返回true，否则返回false（假定被判定的操作序列已存入一维数组中）。
35、在二叉排序树的结构中，有些数据元素值可能是相同的，设计一个算法实现按递增有序打印结点的数据域，要求相同的数据元素仅输出一个，算法还应能报出最后被滤掉而未输出的数据元素个数，对如图所示的二叉排序树，输出为：10，12，13，15，18，21，27，35，42．滤掉3个元素。
参
一、选择题
1、【答案】A 2、【答案】C 3、【答案】B 4、【答案】C 5、【答案】B 6、【答案】C 7、【答案】A 8、【答案】B 9、【答案】D 10、【答案】C
二、填空题
11、【答案】希尔排序、简单选择排序、快速排序、堆排序等 12、【答案】（n+1）/2 13、【答案】2；4；3
【解析】二分法查找元素次数列表
查找100是找到115就停止了。 14、【答案】
【解析】m阶B-树除根结点和叶子结点外，结点中关键字个数最多是m1，最少15、【答案】0；j；i；0；indegree[i]=0；[vex][i]；k==l；indegree[i]=0
【解析】有向图用邻接矩阵表示时，顶点i的入度等于第i列的所有元素之和。拓扑排序过程：首先将入度为0的顶点全部进栈。然后弹出栈顶结点，并将与弹出的顶点相连的其他顶点的入度减一，然后判断这些顶点的入度是否为零，如果为零，继续进栈，重复这些操作，完成拓扑排序。
16、【答案】0；n+1；top[1]+1=top[2] 17、【答案】270；27；2204 18、【答案】模式匹配；模式串
三、判断题
19、【答案】√ 20、【答案】× 21、【答案】× 22、【答案】√ 23、【答案】× 24、【答案】√ 25、【答案】× 26、【答案】× 27、【答案】× 28、【答案】√
四、简答题
29、答：n个元素采用起泡排序法进行排序，通常需要进行n-1趟排序。第j趟起泡排序要进行n-j次比较。在一趟排序中，若没有记录交换，则表示排序完成。因而，可通过设标记来控制排序结束，下面语句段说明了标记 flag的使用。
30、答：（1）判定树如图所示：
（2） 若查找元素54，需依次和元素30、63、42、54比较，查找成功。 （3） 若查找元素90，需依次和元素30、63、87、95比较，查找失败。
（4）
31、答：（1）由于装填因子为0.8，关键字有8个，所以表长为8/0.8=10。用除留余数法设计哈希函数，哈希函数为14（key）=key%7。 （2）哈希表如表所示：
（3）计算查找失败时的平均查找长度，必须计算不在表中的关键字，当其哈希地址为i（0≤i≤m-1）时的查找次数。本例中m=10。故查找失败和查找成功时的平均查找长度分别为：
（4）算法如下：
五、算法设计题
32、答：算法如下：
33、答：算法如下：
34、答：（1）A和D是合法序列，B和C是非法序列。 （2）设被判定的操作序列已存入一维数组A中，算法如下：
35、答：算法如下：
