吉林大学数据结构

1、3. （分数：2.00）_4. （分数：2.00）_二、分析题(总题数：2，分数：4.00)5.请写一非递归算法，该算法在按值严格递增排列的顺序表 A1n中采用折半查找法查找值不小于item 的最小元素。
若表中存在这样的元素，则算法给出该最小元素在表中的位置，否则，给出信息（分数：2.00）_。

2、最多能存储多少个关键字？（分数：2.00）_2008 年北京大学考研计算机专业基础综合（数据结构）真题试卷答案解析(总分：4.00，做题时间：90 分钟)一、设计题(总题数：2，分数：4.00)1. （分数：2.00）_正确答案：(正确答案： )解析：2.5 阶 B+树，最少能存储多少个关键字，最多能存储多少个关键字？（分数：2.00）_正确答案：(正确答案： )解析：。

3、 _。
6 具有 n个结点的完全二叉树的深度为 _。
7 简单排序算法 (即直接插 入排序 )的平均时间为 _，它是一种 _的排序方法。
8 设有序表 L的长度为 132对给定的 k值，用二分法查找与 k相等的元素，若查找成功，最少需要比较 _次，最多需要比较 _次。
9 有 n个结点的哈夫曼树，其叶子结点总数是 _。
10 在含有 n个空链域的二叉链表中有 _个结点， n个结点的二又链表中有个空链域。
11 树的存储结构有 _结构和 _结构。
二、判断题 12 当用二叉链表作树的存储结构时，树的先序遍 历可以由二叉树的先序遍历实现。
（ A）正确 （ B）错误 13 在线性链表中，逻辑上相邻的数据元素其物理地址也是相邻的。
（ A）正确 （ B）错误 14 对同一组关键字，设定相同的哈希函数，即使采用不同的处理冲突的方法，哈希表的平均查找长度也是相同的。
（ A）正确 （ B）错误 15 线性表的顺序存储结构是一种随机存取的存储结构。
（ A）正确 （ B）错误 。

4、2.邻接表是一种链式存储结构，一般由_构成。
（分数：2.00）_3.一个连通图的生成树含有图中全部 n 个顶点，但有且仅有_条边。
（分数：2.00）_4.树形结构中数据元素之间存在_的关系。
（分数：2.00）_5.线性链表的节点至少包含两个域，即_。
（分数：2.00）_。

5、80），对其进行起泡排序的过程中，第二趟排序的结果为（ ）。
5在有序表 A118 中，采用折半查找算法查找元素值等于 A7的元素，所比较过的元素的下标依次为（ ）。
6 设有一棵 Huffman 树的节点总数为 35， 则该 Huffman 树共有 （ ） 个叶子节点 。
7 高度为 h的完全二叉树最少有 （ ） 个节点 。
8在一个具有 n个顶点的无向完全图中，包含有（ ）条边。
9已知一个栈的输入序列为 1、 2、 3 n，则其输出的第一个元素为 n的输出序列的个数是（ ）。
10简单选择排序算法所执行的元素交换次数最少为（ ）。
二、单项选择题（ 1130题，每题 2分，共 40分） 11一个算法的执 行时间为 T(3n2+2nlog2n+4n-7)/(10n)，其时间复杂度为 _。
A O(3n2) B O(2nlog2n) C O(3n/10) D O(n) 12设 n是描述问题规模的非负整数，下面程序片段的时间复杂度为 _。
x=2; while (xnext ; 。

6、正好等于按（ ）遍历对应的二叉树。
4衡量一个查找算法效率的主要标准是（ ）。
5快速排序的时间复杂度是（ ）。
6两个串相等的充分必要条件是两个串的长度相等且（ ）。
7已知广义表 LS为空表，则其深度为（ ）。
8如果排序过程不改变（ ）之间的相对次序，则称该排序方法是稳定的。
9能够成功完全拓扑排序的图一定是一个（ ）。
10在含 100个结点的完全二叉树中，叶子结点的个数为（ ）。
二、单项选择题（ 1130题，每题 2分，共 40分） 11如果在数据结构中每个数据元素只可能有一个直接前驱，但可以有多个直接后继，则该结构是（ ） A栈 B队列 C树 D图 12算法指的是（ ） A计算机程序 B解决问题的计算方法 C排序算法 D解决问题的有限运算序列 13在按层次遍历二叉树的算法中，需要借助的辅助数据结构是（ ） A队列 B栈 C线性表 D有序表 14算术表达式 a+b*(c+d/e)转为后缀表达式后为（ ） A ab+cde/* B abcde/+*+ C。

7、据元素之间关系的不同特性，通常有下列四类基本结构：集合、 _、树形结构和图状结构。
2、算法具有五个重要特性：有穷性、确定性、 _、输入和输出。
3、以下程序段中语句“ +x;”的频度是 _。
for(i=1;i=n;+i)for(j=1;j=n;+j)+x;s+=x;4、在长度为 n 的顺序表中，在第 i(1 i n)个元素之前插入一个元素时，需将_个元素依次向后移动一个位置。
5、已知队列的入队序列是 ABCD，则出队序列是 _。
6、树中结点 A 有 8 个兄弟，结点 B 是结点 A 的双亲，结点 B 的度是 _。
7、在含有 100 个结点的二叉链表中有 _个空链域。
共页第页共 4 页；第 1 页8、在有 200 个顶点的无向图中，边的数目最少是 0，最多是 _。
9、在以下有序表中，采用“折半查找” ，找到 32 需比较 _次。
(5, 8, 11, 12, 15, 20, 32, 41, 57, 60, 80)10、设待排序序列中记录的个数为 n，则堆排序在最坏情况下，其时间复杂度为_。
二、解答。

8、DCBA(10 )2 (10 )AB DCE F GHI KJL MN3 15 8 3 20 36 25 10(Huffman) (10 )4 45 24 53 12 37 93(10 )5(Prim) C (10 )(Kruskal) (10 )ABCDE F21 39 104 75 686 10 30 50 20 40 60(10 )(10 )3 220 401 1002 100 t 1 x x-1 x 3 3。