(C) 84，79，56，46，40，38 (D)A,B,C都不对 21. 下面四个序列中， 是一个堆。
(A)16，72，31，23，94，53 (B)94，53，31，72，16，23 (C) 16，53，23，94，31，72 (D) 16，31，23，94，53，72
22. 一组记录的关键码为(46，79，56，38，40，84)，则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为
。
(A)38，40，46，56，79，84 (B)40，38，46，79，56，84 (C)40，38，46，56，79，84 (D)40，38，46，84，56，79
23. 用某种排序方法对线性表(25，84，21，47，15，27，68，35，20) )进行排序时，元素序列的变化情况如下：
(1)25，84，21，47，15，27，68，35，20 (2)20．15．21．25，47，27，68，35，84 (3)15，20，21，25，35，27，47，68，84 (4)15，20，21，25，27，35，47，68，84
则所采用的排序方法是
。
(A)选择排序 (B)希尔排序 (C)归并排序 (D)快速排序
24. 对序列（15，9，7，8，20，-1，4）进行排序，进行一趟后数据的排列变为（4，9，-1，8，20，7，15）则采用的是 排序。
(A) 选择 (B) 快速 (C) 希尔 (D) 起泡
25. 对（05，46，13，55，94，17，42）进行基数排序，一趟排序的结果是 。
(A)（05，46，13，55，94，17，42） (B)（05，13，17，42，46，55，94） (C)（42，13，94，05，55，46，17） (D)（05，13，46，55，17，42，94） 二、填空题
1、若待排序的序列中存在多个记录具有相同的键值，经过排序，这些记录的相对次序仍然保持不变，则称这种排序方法是________的，否则称为________的。
2、按照排序过程涉及的存储设备的不同，排序可分为________排序和________排序。 3、按排序过程中依据的不同原则对内部排序方法进行分类，主要有：________、________、________、________等四类。
4、简单选择排序算法在最好情况下和最坏情况下的时间复杂度分别为_________和
- 41 -
_________。
5、高度为h的堆中，最多有_______ 个元素，最少有_______个元素。
6、若不考虑基数排序，则在排序过程中，主要进行的两种基本操作是关键字的___________ 和记录的___________。
7、在堆入排序、希尔排序、选择排序、快速排序、堆排序、归并排序和基数排序中，排序是不稳定的有______________________ 。
8、设表中元素的初始状态是按键值递增的，分别用堆排序、快速排序、冒泡排序和归并排序方法对其仍按递增顺序进行排序，则___________最省时间，___________最费时间。 9、直接插入排序用监视哨的作用是_________________。
10、在对一组记录(54，38，96，23，15，72，60，45，83)进行直接插入排序时，当把第7个记录60插入到有序表时，为寻找插入位置需比较________次。
11、利用快速排序方法对记录（50，40，95，20，15，70，60，45，80）进行快速排序，其需递归调用的次数为________，其中第二次递归调用是对________组记录进行快速排序。 12、在堆排序，快速排序和归并排序中，若只从存储空间考虑，则首先选取________方法，其次选取________方法；若只从排序结果的稳定性考虑，则应选取________方法；若只 从平均情况下排序最快考虑，则应选取________方法；若只从最坏情况下排序最快并且要节省内存考虑，则应选取________方法。
13、对于关键字序列（12，13，11，18，60，15，7，20，25，100），用筛选法建堆，必须从键值为 的关键字开始
三、判断题
1、 直接选择排序在最好情况下的时间复杂度是O(n）。
2、 在初始数据表已经有序时，快速排序算法的时间复杂度为O（nlogn）。 3、 在用堆排序算法排序时，如果要进行增序，则需要采用“大顶堆”。 4、 在待排数据基本有序的情况下，快速排序的效果最好。 5、 两分法插入排序所需比较次数与待排序记录的初始状态相关。 6、 希尔排序的最后一趟与直接插入排序过程相同。 7、 在任何情况下，归并排序都比简单排序速度快。 8、 堆是满二叉树。
9、堆肯定是一棵平衡二叉树。
- 42 -
10、内排序要求数据一定要以顺序方式存储。
11、快速排序和归并排序在最坏情况下的比较次数都是O（nlogn）。 12、用希尔排序法时，若关键字的初始排序杂乱无序，则排序效率就低。 13、基数分类只适用于以数字为关键字的情况，不适用以字符串为关键字的情况。 14、若中序遍历平衡的二叉排序树，可得到排好序的关键字序列。
15、在执行某个排序算法过程中，出现了排序码朝着最终排序序列位置相反方向移动，则该算法是不稳定的。
四、解答题
1．已知数据序列为（12，5，9，20，6，31，24），对该数据序列进行排序，试写出插入排序和冒泡排序每趟的结果。
2．判断下列两序列是否为堆？如不是，按照建堆的思想把它调整为堆，并用图表示建堆的过程。
（1）（100,90,80,60,85,75,20,25,10,70,65,50）； （2）（100,70,50,20,90,75,60,25,10,85,65,80）。
3．对于下列一组关键字(12，2，16，30，8，28，4，10，20，6，18），试写出用下列算法从小到大排序时第一趟结束时的序列。 （1)希尔排序（第一趟排序的增量为5） （2）快速排序（选第一个记录为枢纽） （3)基数排序。
4.有n个不同的英文单词，它们的长度相等，均为m，若n＞＞50,m＜5，试问采用什么排序方法时间复杂性最佳?为什么?
5. 已知序列（54，21，52，14，98，47，41，75，5，62），请给出采用堆排序法对该序列作升序排序时的每一趟结果。
6.已知序列（53，82，62，71，93，70，34，25，47，29），请给出采用二路归并排序法对该序列作升序排序时的每一趟结果。
五、算法设计题
1．以下是直接选择排序的算法，请补充完整。
- 43 -
void selectSort(list r,int n)
{//对于包含n个元素的待排序列r进行直接选择排序
for(i=1;i<=________;i++) {k=i;
for(j=i+1;j<=n;j++)if(r[j].key 2．以下对进行一趟快速排序，请补充完整。 int quickpass(list r,int h,int p) {//对子序列r[h],r[h+1],……r[p]进行一趟快速排序，以第一个记录的键值为枢纽 i=h;j=p;x=r[i]; while(i {while((r[j].key>=x.key)&&(i {________;i++; while((r[i].key<=x.key)&&(i r[i]=________;return(i); } 3．设带头结点的单链表L，结点数据值为整型。试写出对链表L按“插入方法”排序的算法：LINSORT(L). 4．冒泡排序算法是把大的元素向上移（起泡的上浮），也可把小的元素向下移（起泡的下沉），请给出上浮和下沉过程交替的起泡排序算法。 5.一个线性表中的元素为正整数或负整数。设计一个算法，将正整数和负整数分开，使线性表前一半为负整数，后一半为正整数。不要求对这些元素排序，但要求尽量减少交换次数。 6.已知排序码序列{k1,k2,...,kn}是小顶堆，试写一算法，增加排序码x到堆中{k1,k2,...,kn，x}后，将其调整为小顶堆的算法。（排序码值为ki的记录存于r[i-1]中） 7．请用快速排序思想，设计递归算法实现求n(n>1)个不同元素集合中的第i（0 - 44 - 8、有一种简单的排序算法，叫做计数排序。这种排序算法对一个待排序的表（用数组表示）进行排序，并将排序结果存放到另一个新的表中。必须注意的是，表中所有待排序的关键字互不相同，计数排序算法针对表中的每个记录，扫描待排序的表一趟，统计表中有多少个记录的关键字比该记录的关键字小。假设对某一个记录，统计出数值为c，那么这个记录在新的有序表中的合适的存放位置即为c。 （1）给出适用于计数排序的数据表定义。 （2）编写实现计数排序的算法。 （3）对于有n个记录的表，比较次数是多少？ （4）与简单选择排序相比，这种方法是否更好？为什么？ - 45 - 2009年全国硕士研究生入学统一考试 计算机科学与技术学科联考 计算机学科专业基础综合 考试大纲 教育部考试中心 中国学位与研究生教育学会工科工作委员会 目 录 I. 考查目标 II. 考试形式和试卷结构考查范围 III. 考查范围 数据结构 计算机组成原理 操作系统 计算机网络 IV. 试题示例 Ⅰ.考查目标 计算机学科专业基础综合考试涵盖数据机构、计算机组成原理、操作系统和计算机网络等学科专业基础课程。要求考生比较系统地掌握上述专业基础课程的概念、基本原理和方法，能够运用所学的基本原理和基本方法分析、判断和解决有关理论问题和实际问题。 Ⅱ.考试形式和试卷结构 一、试卷满分及考试时间 本试卷满分为150分，考试时间为180分钟 二、答题方式 答题方式为闭卷、笔试 三、试卷内容结构 数据结构 45分 计算机组成原理 45分 - 1 - 操作系统 35分 计算机网络 25分 四、试卷题型结构 单项选择题 80分（40小题，每小题2分） 综合应用题 70分 Ⅲ.考查范围 数据结构 【考查目标】 1.理解数据结构的基本概念；掌握数据的逻辑结构、存储结构及其差异，以及各种基本操作的实现。 2.掌握基本的数据处理原理和方法的基础上，能够对算法进行设计与分析。 3.能够选择合适的数据结构和方法进行问题求解。 一、线性表 （一）线性表的定义和基本操作 （二）线性表的实现 1.顺序存储结构 2.链式存储结构 3.线性表的应用 二、栈、队列和数组 （一）栈和队列的基本概念 （二）栈和队列的顺序存储结构 （三）栈和队列的链式存储结构 （四）栈和队列的应用 （五）特殊矩阵的压缩存储 三、树与二叉树 （一）树的概念 - 2 - （二）二叉树 1.二叉树的定义及其主要特征 2.二叉树的顺序存储结构和链式存储结构 3.二叉树的遍历 4.线索二叉树的基本概念和构造 5.二叉排序树 6.平衡二叉树 （三）树、森林 1.书的存储结构 2.森林与二叉树的转换 3.树和森林的遍历 （四）树的应用 1.等价类问题 2.哈夫曼（Huffman）树和哈夫曼编码 四、 图 （一） 图的概念 （二） 图的存储及基本操作 1.邻接矩阵法 2.邻接表法 （三）图的遍历 1. 深度优先搜索 2. 广度优先搜索 （四）图的基本应用及其复杂度分析 1. 最小（代价）生成树 2. 最短路径 3. 拓扑排序 4. 关键路径 五、查找 - 3 - （一）查找的基本概念 （二）顺序查找法 （三）折半查找法 （四） B-树 （五）散列（Hash）表及其查找 （六）查找算法的分析及应用 六、内部排序 （一）排序的基本概念 （二）插入排序 1.直接插入排序 2.折半插入排序 （三）气泡排序（bubble sort） （四）简单选择排序 （五）希尔排序（shell sort） （六）快速排序 （七）堆排序 （八）二路归并排序（merge sort） （九）基数排序 （十）各种内部排序算法的比较 （十一）内部排序算法的应用 Ⅳ．试题示例 一、单项选择题：1~40小题，每小题2分，共80分。在每小题给出的四个选项中， 请选出一项最符合题目要求的。 试题示例： 1、 下列排序算法中，时间复杂度为O（nlog2n）且占用额外空间最少的是 Ａ．堆排序 C．快速排序 - 4 - Ｂ．起泡排序 D．希尔排序 2、 下列序列中，满足堆定义的是 A．（100，86，48，73，35，39，42，57，66，21） B．（12，70，33，65，24，56，48，92，86，33） C．（103，97，56，38，66，23，42，12，30，52，6，26） D．（5，56，20，23，40，38，29，61，35，76，28，100） 二、综合应用题：41~47小题，共70分。 试题示例： 41．（10分）设无向图G=（V，E），其中V={1，2，3，4，5}，E={（1，2，4），（2，5，5），（1，3，2），（2，4，4），（3，4，1），（4，5，3），（1，5，8）}，每条边由一个三元组表示，三元组中前两个元素为与该边关联的顶点，第三个元素为该边的权。请写出图G中从顶点1到其余各点的了短路径的求解过程。要求列出最短路径上的顶点，并计算路径长度。 42.(15分)已知一棵二叉树采用二叉链表存储,结点构造为: LeftChild Data RightChild ,root指向根结点。现定义二叉树中结点X0 的根路径为从根结点到X0 结点的一条路径，请编写算法输出该二叉树中最长的根路径（多条最长根路径中只输出一条即可。算法可使用C或C + +或JAVA语言实现）。 - 5 - 5.在具有24个元素的有序表上进行二分查找，则比较一次查找成功的结点数为______，比较二次查找成功的结点数为________，比较三次查找成功的结点数为_________，比较四次查找成功的结点数为________，比较五次查找成功的结点数为__________。总的比较查找长度为__________。 6．使用分块查找时，除表本身外，尚需建立一个 及该块的起始位置。 7.采用散列技术来实现查找，需要解决的问题有: ; ; 。 ，用来存放每一块中的最大值以 8.、在各种查找方法中，平均查找长度与结点个数无关的查找方法是 9.含有12个结点的平衡二叉树的最大深度是 。（设根结点深度为1） 10.如果将n个元素，按其关键字递增的顺序依次插入到二叉排序树中，则对这样的二叉排序树检索时，平均比较次数为 。 个，除根 11.在一个127阶的B-树上，每个结点中包含的关键字数目最多允许为 结点外的非终端至少有 棵子树。 12. 一棵深度为k的平衡二叉树，其每个非终端结点的平衡因子均为0，则该树共有 个结点。 个；最少可以是 13.高度为5的平衡二叉树；其结点数最多可以有 个。 14．在一棵m阶的B-树中，当一关键字插入某结点而引起该结点分裂时，此结点原有 个关键字。若删去某结点中的一个关键字，而导致该结点合并时，该结点中原有 个关键字。 15.一个待散列存储的线性表为（18，34，58，26，75，67，48，93，81），哈希函数为H(key)=key ,若采用线性探测法解决冲突，则平均查找长度为 地址法解决冲突，则平均查找长度为 。 ；若采用链16.假定有k个关键字互为同义词，若用线性探测法把这k个关键字存入散列表中，至少要进行 四、解答题 1．简述顺序查找法，折半查找法和分块查找法对被查找表中元素的要求。 - 36 - 探测。 2．假定对有序表(3,4,5,7,24,30,42,54,63,72,87,95)进行折半查找，试回答下列问题： （1）画出描述折半查找过程的判定树。 （2）若查找元素54，需依次与那些元素比较。 （2）若查找元素90，需依次与那些元素比较。 （3）求查找成功时的平均查找长度。 3、对下面的关键字集{30，15，21，40，25，26，36，37}若查找表的装填因子为0.8，采用线性探测再散列方法解决冲突，哈希函数为H（key）＝key％ 7，画出该哈希表，并计算查找成功的平均查找长度。 4．设有一组关键字{ 9，1，23，14，55，20，84，27 }．采用哈希函数：H(key)＝key％7。 采用开放地址法的二次探测再散列方法解决冲突 Hi?(H(key)?di)mod10(di?12,22,?)，试对该关键字序列构造哈希表，并计算查找 成功的平均查找长度。 5．输入一个正整数序列（17，31，13，11，20，35，25，8，4，11，24，40，27）画出该二叉排序树。依此二叉排序树，如何得到一个递增序列？ 6．一棵二叉排序树结构如下图所示，各结点的值分别为1，2，3,...9,请在图中标出各结点的值。 第6第第 7．已知插入结点的序列为（17，31，13，11，20，35，25，8，4，11，24，40，27）,请画出该二叉排序树，并分别给出下列操作后的二叉排序树： (1)插入数据9； （2）删除数据17； （3）再删除结点13； 8．按下列次序输入关键字：（E,F,P,K,M,L,B）,请画出AVL树的构造和调整过程。要求画出每插入一个关键字后查找树的形状及调整后的结果，并标明调整类型。 - 37 - 9.深度为6的平衡二叉树中最少应包含多少个结点，并画出这样一棵平衡二叉树。 10.从空树开始，依次输入结点20，30，50，52，60，68，70，画出建立3阶B-树的过程。并画出删除结点50和68后的B-树状态。 五、算法设计题 1．设顺序表中关键字是递增有序的，试写一顺序查找算法，将哨兵设在表的高下标端。然后求出等概率情况下查找成功与失败时的ASL。 2.试编写一个判别给定的二叉树是否为二叉排序树的算法。设此二叉树以二叉链表为存储结构，且树中结点的关键字均不相同. 3. 试写一递归算法，从大到小输出二叉排序树中所有其值不小于X的关键字。 4.设二叉排序树的各元素均不相同，试分别采用递归和非递归算法按递减顺序打印所有左子．．树为空，右子树非空的结点的数据域的值。 5. 试编写一个算法，删除二叉排序树中所有关键字不小于x的结点，并释放该结点空间。 6. 试编写一个算法，将两棵二叉排序树合并为一棵二叉排序树。 7.写出从哈希表中删除关键字为k的一个记录的算法；设哈希函数为H,解决冲突的方法为链地址法。 - 38 - 第 10 章 内部排序 一、单选题 1．在所有排序方法中，关键字比较的次数与记录的初始排列次序无关的是 （A）希尔排序 （B）起泡排序 （C）插入排序 （D）选择排序 2．在待排序的元素序列基本有序的前提下，效率最高的排序方法是 (A)插入排序 (B)选择排序 (C)快速排序 (D)归并排序 3．设有5000个无序的元素，希望用最快的速度挑选出其中前l0个最大的元素，最好选 用 排序法。 。 。 (A)起泡排序 (B)快速排序 (C)堆排序 (D)基数排序 4．排序方法中，从未排序序列中依次取出元素与已排序序列(初始为空)中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为 。 (A)希尔排序 (B)起泡排序 (C)插入排序 (D)选择排序 5.下列排序算法中，稳定的是 。 (A)直接插入排序和快速排序 (B)折半插入排序和冒泡排序 (C)简单选择排序和四路归并排序 (D)树形选择排序和希尔排序 6．下述几种排序方法中，平均查找长度最小的是 。 (A)插入排序 (B)直接选择排序 (C)快速排序 (D)归并排序 7．下述几种排序方法中，要求内存量最大的是 。 (A)插入排序 (B)选择排序 (C)快速排序 (D)、归并排序 8．快速排序方法在 情况下最不利于发挥其长处。 (A)要排序的数据量太大 (B)要排序的数据中含有多个相同值 (C)要排序的数据已基本有序 (D)要排序的数据个数为奇数 9．下列排序方法中， 可能出现这种情况：在最后一趟开始之前，所有元素都不在 其最终应在的正确位置上。 (A)快速排序 (B)冒泡排序 (C)堆排序 (D)插入排序 10．当初始序列已按健值有序时，用直接插入算法进行排序，需要比较的次数为 (A) n-1 (B)log2n (C) 1 (D)n2 - 39 - 11．快速排序在最坏的情况下的时间复杂度是 。 (A) O(log2n) (B)O(nlog2n) (C) O(n2) (D)O(n3) 12.在排序过程中，健值比较的次数与初始序列的排列顺序无关的是 (A)直接插入排序和快速排序 (B)直接插入排序和归并排序 (C)直接选择排序和归并排序 (D)快速排序和归并排序 13．下列排序方法中，哪一个是稳定的排序方法 。 。 (A)直接选择排序 (B)二分法插入排序 (C)希尔排序 (D)快速排序 14．在文件“有序”或文件长度较小的情况下，最佳内部排序的方法是 (A)直接插入排序 (B)选择排序 (C)冒泡排序 (D)快速排序 15．对一个由n个整数组成的序列，借助排序过程找出其中的最大值，希望比较次数和移动次数最少，应选用 方法。 。 (A)归并排序 (B)直接插入排序 (C)直接选择排序 (D)快速排序 16.下列排序算法中 排序在一趟结束后不一定能选出一个元素在其最终位置上。 (A) 选择排序 (B)冒泡排序 (C)归并排序 (D)堆排序 17.一组记录的关键字为（25，50，15，35，80，85，20，40，36，70），其中含有5个长度为2的有序表，用归并排序方法对该序列进行一趟归并后的结果为 (A)．15，25，35，50，20，40，80，85，36，70 (B)15，25，35，50，80，20，85，40，70，36 (C)15，25，50，35，80，85，20，36，40，70 (D)15，25，35，50，80，20，36，40，70，85 18. 一组记录的关键字为(56,34,23,38,40,69)，则利用直接插入排序的方法，经过 3趟排序之后，其关键字序列为 。 。 (A) 34,56,23,38,40,69 (B) 34,38,23,56,40,69 (C) 23,34,56,38,40,69 (D) 23,34,38,56,40,69 19. 数据序列(8，9，10，4，5，6，20，1，2)只能是下列排序算法中的 排序后的结果。 (A)选择排序 (B)冒泡排序 (C)插入排序 (D)堆排序 20. 一组记录的关键码为(46，79，56，38，40，84)，用堆排序的筛选方法建立的初始堆为 。 的两趟 (A) 79，46，56，38，40，80 (B) 84，79，56，38，40，46 - 40 - 11、对如图所示的有向图 G ,它的拓扑序列是 。 A. a , b , c , d B. a , d , b , c C. a , b , d , c D. b , a , d , c 12、对如下所示的图，它的生成树有 棵。 A. 1 B. 5 C. 6 D．不确定 13、如图所示的有向图的顶点可以排成 个不同的拓扑序列。 A．3 B．5 C. 7 D.9 14、一个有n个结点的图，最少有 个连通分量，最多有 个连通分量。 A．0 B．1 C．n-1 D．n 15、用有向无环图描述表达式(A+B)*（（A+B）/A），至少需要顶点的数目为 A．5 B．6 C．8 D．9 16、下列说法不正确的是 。 。 A．图的遍历是从给定的源点出发每一个顶点仅被访问一次 B．遍历的基本算法有两种：深度遍历和广度遍历 - 26 - C．图的深度遍历不适用于有向图 D．图的深度遍历是一个递归过程 17、无向图G=(V,E),其中：V={a,b,c,d,e,f}, E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)}，对该图进 行深度优先遍历，得到的顶点序列正确的是 。 A．a,b,e,c,d,f B．a,c,f,e,b,d C．a,e,b,c,f,d D．a,e,d,f,c,b 18、下面 方法可以判断出一个有向图是否有环（回路）： A．深度优先遍历 B. 拓扑排序 C. 求最短路径 D. 求关键路径 19、在图采用邻接表存储时，求最小生成树的 Prim 算法的时间复杂度为 A. O(n) B. O(n+e) C. O(n2) D. O(n3) 20、求解最短路径的Floyd算法的时间复杂度为 。 。 A．O（n） B. O（n+c） C. O（n*n） D. O（n*n*n） 21、已知有向图G=(V,E)，其中V={V1,V2,V3,V4,V5,V6,V7}， E={ 。 A．V1,V3,V4,V6,V2,V5,V7 B．V1,V3,V2,V6,V4,V5,V7 C．V1,V3,V4,V5,V2,V6,V7 D．V1,V2,V5,V3,V4,V6,V7 22、在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形不可能出现的是 。 A．G中有弧 A. O(n) B. O(n＋e) C. O(n*n) D. O(n*n*n) 二、判断题 1、 在n个结点的无向图中，若边数大于n-1,则该图必是连通图。 2、 有e条边的无向图，在邻接表中有e个结点。 3、 有向图中顶点V的度等于其邻接矩阵中第V行中的1的个数。 4、 强连通图的各顶点间均可达。 5、 用邻接矩阵法存储一个图所需的存储单元数目与图的边数有关。 6、 有n个顶点的无向图, 采用邻接矩阵表示, 图中的边数等于邻接矩阵中非零元素之和的 - 27 - 一半。 7、 有向图的邻接矩阵是对称的。 8、 任何无向图都存在生成树。 9、 一个有向无环图的拓扑排序序列是唯一的。 10、关键路径是AOE网中从源点到终点的最长路径。 三、填空题 1、 设有一稀疏图 G ，则 G 采用__________存储比较节省空间； 设有一稠密图 G ，则 G 采用__________存储比较节省空间。 2、 n 个顶点 e 条边的图采用邻接矩阵存储，深度优先搜索遍历算法的时间复杂度为 ____________，采用邻接表存储，深度优先搜索遍历算法的时间复杂度为___________。 3、 n 个顶点的完全图有___________条边。 4、 有 n 个顶点的无向连通图至少有 条边，有 n 个顶点的有向强连通图至少 有 条弧。 5、 用邻接矩阵表示无向图时，若图中有 n = 500 个顶点， m = 500 条边，则形成的邻接 矩阵共有 个元素，其中 个为非零元素。 6、 判断一个无向图是一棵树的条件是 。 7、 若用n表示图中顶点数目，则有_______条边的无向图成为完全图。 8、 G是一个非连通无向图，共有28条边，则该图至少有______个顶点。 9、 在图G的邻接表表示中，每个顶点邻接表中所含的结点数，对于无向图来说等于该顶 点的______；对于有向图来说等于该顶点的______。 10、 对于一个具有n个顶点e条边的无向图的邻接表的表示，则表头向量大小为______，邻接表的边结点个数为______。 11、已知一无向图G=（V，E），其中V={a,b,c,d,e } E={(a,b),(a,d),(a,c),(d,c),(b,e)}现用某一 种图遍历方法从顶点a开始遍历图，得到的序列为abecd，则采用的是______遍历方法。 12、为了实现图的广度优先搜索，除了一个标志数组标志已访问的图的结点外，还需______存放被访问的结点以实现遍历。 13、Prim（普里姆）算法适用于求______的网的最小生成树；kruskal（克鲁斯卡尔）算法适 用于求______的网的最小生成树。 14、克鲁斯卡尔算法的时间复杂度为______,它对______图较为适合。 - 28 - 四、解答题 1、 已知无向图的邻接表如下，①在给出顶点的图上，画出这个图的边；②写出该图的邻接 矩阵A；③根据邻接表，写出从顶点V1出发，深度优先遍历该图所得到的顶点序列。 1 2 3 4 5 提示： V1 V3 V4 V2 V5 2、 己知一无向图有 6 个结点， 9 条边，这 9 条边依次为（ 0 , l ) , ( 0 , 2 ) , ( 0 , 4 ) , ( 0 , 5 ) ,( l , 2 ) , ( 2 , 3 ) , ( 2 , 4 ) , ( 3 , 4 ) , ( 4 , 5 ）。试画出该无向图，并从顶点 0 出发分别写出按深度优先搜索和广度优先搜索进行遍历的结点序列。 3、 已知如图1 所示的有向图，给出该图的： ① 每个顶点的出度和入度； ② 强连通分量； ③ 最长的简单路径； ④ 最长的简单回路； ⑤ 进行拓扑排序，给出顶点的拓扑序列。 4、 对如图2所示的连通图，列出分别从顶点 A 、 D 开始，深度优先和广度优先搜索遍 历该图所得到的顶点序列，画出相应的生成树。 图1 图2 5、 设无向图G=（V，E），其中V={1，2，3，4，5}，E={（1，2，4），（2，5，5）， （1，3，2），（2，4，4），（3，4，1），（4，5，3），（1，5，8）}，每条边由一个三元组表示，三元组中前两个元素为与该边关联的顶点，第三个元素为该边的权。请写出图G中从顶点1到其余各点的了短路径的求解过程。要求列出最短路径上的顶点，并计算路径长度。 - 29 - 6、 下图是以边为活动的网（AOE_网），以V1为开始点，以V10为终止点，计算该AOE_ 网的关键路径长度（即，从开始点到终止点的最长路径长度）。 7、 对如下无向图，试给出： ① 用普里姆算法构造最小生成树的过程 ② 用克鲁斯卡尔算法构造最小生成树的过程 五、算法设计题 1、 图G为有向无权图，试在邻接矩阵存储结构上实现删除一条边(v,w)的操作： DeleteArc(G,v,w)。若无顶点v或w，返回“ERROR”；若成功删除，则边数减1，并返回“OK”。（提示：删除一条边的操作，可以将邻接矩阵的第i行全部置0 ），完成该算法。 Status DeleteArc(MGraph &G,char v,char w) //在邻接矩阵表示的图G上删除边(v,w) { if ((i=LocateVex(G, v))<0) return if ((j=LocateVex(G, w))<0) return if (G.arcs[i][j].adj) { G.arcs[i][j].adj= ; G.arcnum ; （或 G.arcnum=G.arcnum-1 ） } return } ; ; ; 3 E B 5 6 6 4 F 6 A 1 C 5 2 5 D - 30 - 2、 一个图采取以下结构，完成下列遍历算法。 void BFSTraverse(Graph G, Status (*Visit)(int v)) { for (v=0; v visited[v] = FALSE; //初始化访问标志 InitQueue(Q); // 置空的辅助队列Q for ( v=0; v if ( ) { // v 尚未访问 visited[v] = TRUE; Visit(v); // 访问u EnQueue(Q, v); // v入队列 while (!QueueEmpty(Q)) { DeQueue(Q, u); // 队头元素出队并置为u for(w=FirstAdjVex(G, u); w>=0; w=NextAdjVex(G,u,w)) if ( ! visited[w]) { visited[w]= ; Visit(w); EnQueue(Q, w); // 访问的顶点w入队列 } // if } // while } //if } // BFSTraverse 3、编程实现：用邻接表的存储方法创建一个图。 4、编程实现：对3题建立的图进行深度优先搜索。 - 31 - 第 9 章 查找 一、单选题 1、静态查找表与动态查找表两者的根本差别在于 A、逻辑结构不同 B、 存储实现不同 C、施加的操作不同 D、 数据元素的类型不同 2、采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为 Ａ、n B、n/2 C、(n+1)/2 D、(n-1)/2 。 。 。 3、对线性表进行二分查找时，要求线性表必须 A、以顺序方式存储 B、以链式方式存储 C、以顺序方式存储，且结点按关键字有序排序 D、以链式方式存储，且结点按关键字有序排序 4、在表长为n的顺序表中进行顺序查找，在查找不成功时，与关键字比较的次数为 。 A、n B、1 C、 n+1 D、n-1 5、对于有序表（2，5，7，11，22，45，49，62，71，77，90，93，120），折半查找值为90的结点时，经过 比较后查找成功。 A、 1 B、 2 C、4 D、5 6.快速排序在最坏情况下的时间复杂度是( )。 A、O(log2n) B、O(nlog2n) C、O(n2) D、O(n3) 7、如果要求一个线性表既能较快地查找，又能适应动态变化的要求，可以采用 查找方法。 A、分块 B、顺序 C、二分 D、散列 8、有一个长度为12的有序表，按二分查找法对该表进行查找，在表内各元素等概率情 况下查找成功所需的平均比较次数为 。 A、35／12 B、37／12 C、39／12 D、43／12 9、当采用分块查找时，数据的组织方式为 A、数据分为若干块，每块内数据有序 B、数据分为若干块，每块内数据不必有序，但块间必须有序，每块内最大（或最小） - 32 - 。 的数据组成索引块 C、数据分成若干块，每块内数据有序，每块内最大（或最小）的数据组成索引块 D、数据分为若干块，每块（除最后一块外）中数据个数需相同 10.在排序过程中，键值比较的次数与初始序列的排列顺序无关的是()。 A、直接插入排序和快速排序 B、直接插入排序和归并排序 C、直接选择排序和归并排序 D、快速排序和归并排序和归并排 11、从键盘依次输入关键字的值：t,u,r,b,o,p,a,s,c,l。建立二叉排序树，则先序遍历序列为 。 A、 abcloprstu B、 alcpobsrut C、 trbaoclpsu D、 trubsaocpl 12、设有一组记录的关键字为{19，24，23，1，68，20，84，27，55，11，10，79}，用链地址法构造哈希表，哈希函数为H(KEY)=KEY MOD 13 ,哈希地址为1的链中有 个记录。 A、1 B、2 C、3 D、4 13、在采用线性探测法处理冲突所构成的闭散列表上进行查找，可能要探测多个位置，在查找成功的情况下，所探测的这些位置上的健值 。 A、一定都是同义词 B、 一定都不是同义词 C、都相同 D 、健值不一定有序的顺序表 14、设哈希表长为14，哈希函数为H(key)= key mod 11,表中已经有4个结点：addr(14)=3, addr(38)=5, addr(61)=6, addr(85)=8,其余地址为空,用线性探测再散列法解决冲突，关键字为49的结点的地址为 。 A、7 B、3 C、5 D、 4 15、设有序表的关键字序列为{1，4，6，10，18，35，42，53，67，71，78，84，92，99}，当用二分查找法查找健值为84的结点时，经 次比较后查找成功。 A、2 B、 3 C、 4 D、 12 16、已知一采用开放地址法解决Hash表冲突，要从此Hash表中删除一个记录，正确的做法是 。 A、将该元素所在的存储单元清空。 B、将该元素用一个特殊的元素代替 C、将与该元素有相同Hash地址的后继元素顺次前移一个位置。 D、用与该元素有相同Hash地址的最后插入表中的元素替代。 - 33 - 17、以下说法错误的是 。 A、数字分析法对健值的各位进行分析，选择分布较均匀的若干位组成散列地址。 B、除余法选择一个适当的正整数p,以p除健值以所得的余数作为散列地址。 C、平方取中法以健值平方的中间几位作为散列地址。 D、基数转换法将健值看成另一种进制的数再转换成原来进制的数，然后选择其中几位作为散列地址。 18、下面关于B-树和B+树的叙述中，不正确的是 。 A、B-树和B+树都是平衡的多叉树 B、B-树和B+树都可用于文件的索引结构 C、B-树和B+树都能有效地支持顺序检索 D、B-树和B+树都能有效地支持随机检索 19、下列关于m阶B-树的说法错误的是 。 A、根结点至多有m棵子树。 B、 所欲叶子都在同一层 C、非叶子结点至少有m/2(m为偶数)或m/2+1（m为奇数）棵子树 D、根结点中的数据都是有序的。 20、一棵3阶B-树中含有2047个关键字，包含叶结点层，该树的最大深度为 A、11 B、12 C、13 D、 14 21、一棵深度为k的平衡二叉树，其每个非终端结点的平衡因子均为0，则该树共有 个结点。 。 A、2k-1-1 B、 2k-1 C、2k-1+1 D、2k-1 22、分别以下列序列构造二叉排序树，与用其他三个序列所构造的结果不同的是 。 A、 (100,80,90,60,120,110,130) B 、(100,120,110,130,80,60,90) C 、(100,60,80,90,120,110,130) D 、(100,80,60,90,120,130,110) 23、设二叉排序树中关键字由1至1000的整数构成,现要查找关键字为363的结点，下述关键字序列哪一个不可能是在二叉排序树上查到的序列？ A、2，252，401，398，330，344，397，363； B、924，220，911，244，898，258，362，363； C、925，202，911，240 ，912，245，363； D、2，399，387，219，266，382，381，278，363。 - 34 - 24、在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点的左孩子的平衡因子为0，右孩子的平衡因子为1，则应作 A 、LL B、 LR C、 RL D、 RR 二、判断题 1、n个数放在一维数组中，在进行顺序查找时，这n个数的排列有序或无序其平均查找长度不同。 2、若散列表的装填因子小于1，则可避免碰撞的产生。 3、哈希表的平均查找长度与处理冲突的方法无关。 4、对无序表用折半法查找比顺序查找法快。 5、在二叉排序树中插入一个新结点，总是插入到叶节点下面。 6、平衡二叉树中，若某个结点的左、右孩子的平衡因子为零，则该结点的平衡因子一定是零。 7、对两棵具有相同关键字而形状不同的二叉排序树，按中序遍历得到的序列却是一致的。 8、完全二叉树肯定是平衡二叉树 9、在9阶B-树中，除叶子以外的任意结点的分支数介于5和9之间。 10、如果完全二叉树从根结点开始按层次遍历的序列为1，2，3，4，5，6，7，则该完全二叉树是二叉排序树。 11、m阶B-树的任何一个结点的左右子树高度都相等。 12、设二叉排序树中关键字互不相同，则其中最小元必无左孩子，最大元必无右孩子。 13、对给定的关键字集合,以不同的次序插入初始为空的树中,将得到同一棵二叉排序树。 三、填空题 1． 动态查找表和静态查找表的重要区别在于前者包含有 后者不包含这两种运算。 2．对n个记录的表中进行折半查找，最大比较次数是 。 和 运算，而 型调整以使其平衡。 3．顺序查找n个元素的顺序表，若查找成功，则比较关键字的次数最多为 次；当使用监视哨时，若查找失败，则比较关键字的次数为 。 4．已知有序表为（12，18，24，35，47，50，62，83，90，115，134），当用二分法查找90时，需 次查找成功，查找47时需 次成功，查找100时，需 次才能确定不成功。 - 35 - 百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库2008年数据结构习题集在线全文阅读。
相关推荐：