72．从V1出发，对右图按广度优先搜索遍历，则可能得到的一种顶点序列为 （ ） A）V1V2V3V5V4V6 B）V1V2V3V5V6V4 C）V1V5V2V3V6V4 D）V1V3V6V4V5V2
73．图的邻接表如下所示，从顶点V1出发采用深度优先搜索法遍历该图，则可能的顶点序列是 （ ）
A）V1V2V3V4V5 B）V1V2V3V5V4 C）V1V4V3V5V2 D）V1V3V4V5V2 74．若采用邻接表存储结构，则图的深度优先搜索类似于二叉树的 （ ） A）先根遍历 B）中根遍历 C）后根遍历 D）层次遍历
75．右图所示带权无向图的最小生成树的权为 ( ) A）14 B）15 C）17 D）18
76．对关键字序列(56，23，78，92，88，67，19，34)进行增量为3的一趟希尔排序的结果为 （ ） A） (19，23，56，34，78，67，88，92) B） (23，56，78，66，88，92，19，34) C） (19，23，34，56，67，78，88，92) D） (19，23，67，56，34，78，92，88)
77．已知10个数据元素为（54，28，16，34，73，62，95，60，26，43），对该数列按从小到大排序，经过一趟冒泡排序后的序列为 （ ） A）16，28，34，54，73，62，60，26，43，95 B）28，16，34，54，62，73，60，26，43，95 C）28，16，34，54，62，60，73，26，43，95 D）16，28，34，54，62，60，73，26，43，95
78．设有一组初始关键字值序列为（49，81，55，36，44，88），则利用快速排序的方法，以第一个关键字值为基准得到的一次划分为 （ ） A）36，44，49，55，81，88 B）44，36，49，55，81，88 C）44，36，49，81，55，88 D）44，36，49，55，88，81
79．对序列（22，86，19，49，12，30，65，35，18）进行一趟排序后得到的结果如下：（18，12，19，22，49，30，65，35，86），则可以认为使用的排序方法是 （ ） A）选择排序 B）冒泡排序 C）快速排序 D）插入排序
80．若对序列（26，90，23，53，16，34，69，39，22）进行一趟排序后所得到的结果为（22，16，23，26，53，34，69，39，90），则该排序可能使用的方法是 （ ） A）选择排序 B）冒泡排序 C）快速排序 D）插入排序 81．一组记录的键值为（46，74，18，53，14，20，40，38，86，65），利用堆排序的方法建立的初始堆为 （ ） A）（14，18，38，46，65，40，20，53，86，74）
6
B）（14，38，18，46，65，20，40， 53，86，74） C）（14，18，20，38，40，46，53，65，74，86） D）（14，86，20，38，40，46，53，65，74，18）
82．下列关键码序列中，属于堆的是 （ ） A）（15，30，22，93，52，71） B）（15，71，30，22，93，52） C）（15，52，22，93，30，71） D）（93，30，52，22，15，71） 83．下列序列中，不构成堆的是 （ ） A）（1，2，5，3，4，6，7，8，9，10） B）（10，5，8，4，2，6，7，1，3） C）（10，9，8，7，3，5，4，6，2） D）（1，2，3，4，10，9，8，7，6，5） 84．对记录序列(314，298，508，123，486，145)依次按个位和十位进行两趟基数排序之后所得结果为 （ ） A）123，145，298，314，486，508 B）508，314，123，145，486，298 C）486，314，123，145，508，298 D）298，123，508，486，145，314
85．已知数据表A中每个元素距其最终位置不远，为节省时间，应采用的算法是 （ ） A）堆排序 B）直接插入排序 C）快速排序 D）直接选择排序 86．如果在排序过程中，每次均将一个待排序的记录按关键字大小加入到前面已经有序的子表中的适当位置，则该排序方法称为 （ ）
A）插入排序 B）归并排序 C）冒泡排序 D）堆排序
87．在待排关键字序列基本有序的前提下，效率最高的排序方法是 ( ) A）堆排序 B）直接插入排序 C）快速排序 D）直接选择排序 88．下列排序算法中，其时间复杂度和记录的初始排列无关的是 （ ） A）插入排序 B）堆排序 C）快速排序 D）冒泡排序
89．对n个关键字的序列进行快速排序，平均情况下的空间复杂度为 （ ） A）O(1) B）O(logn) C）O(n) D）O(n logn) 90．直接插入排序算法，其时间复杂性为 （ ） A）O(1) B）O(n) C）O(nlog2n) D）O(n2)
91．堆排序属于一种选择排序，其时间复杂性为 （ ） A）O(1) B）O(n) C）O(nlog2n) D）O(n2) 92．快速排序在最坏情况下的时间复杂度是（ ） A）O(n2log2n) B）O(n2) C）O(nlog2n) D）O(log2n) 93．下列二叉树中，不平衡的二叉树是 （ ）
94．对表长为n的顺序表进行顺序查找，在查找概率相等的情况下，查找成功的平均查找长度为 （ ） A）（n－1）/2 B）n/2 C）（n+1）/2 D）n 95．已知一个有序表为（13，18，24，35，47，50，62，83，90，115，134），当二分检索值为90的元素时，检索成功需比较的次数是 （ ） A）1 B）2 C）3 D）4
96．在关键字序列(12，23，34，45，56，67，78，89，91)中二分查找关键字为45、89和12的结点时，所需进行的比较次数分别为 （ ） A）4，4，3 B）4，3，3 C）3，4，4 D）3，3，4 97．若有序表的关键字序列为（b,c,d,e,f,g,q,r,s,t），则在二分查找关键字b的过程中，先后进行比较的关键字依次为 （ ）
A）f,c,b B）f,d,b C）g,c,b D）g,d,b
7
98．在下列各棵二叉树中，二叉排序树是 （ ）
99．当在二叉排序树中插入一个新结点时，若树中不存在与待插入结点的关键字相同的结点，且新结点的关键字小于根结点的关键字，则新结点将成为 （ ） A）左子树的叶子结点 B）左子树的分支结点 C）右子树的叶子结点 D）右子树的分支结点
100．设一组记录的关键字key值为{62，50，14，28，19，35，47，56，83}，散列函数为H(key)=key mod 13，则它的开散列表中散列地址为1的链中的结点个数是 （ ） A）1 B）2 Ｃ）3 D）4
二、填空题
1．数据结构包括数据的逻辑结构、数据的______以及对数据的操作运算。
2．在数据结构中，数据的逻辑结构分为集合、________、树形结构和图状结构等四类。 3．数据的逻辑结构在计算机存储器内的表示，称为数据的____________。
4．表示逻辑关系的存储结构可以有四种方式，即顺序存储方式、链式存储方式、_______________和散列存储方式。
5．抽象数据类型是指数据逻辑结构及与之相关的___________。
6．顺序存储方法是把逻辑上相邻的结点存储在物理位置______的存储单元中。
7．通常从正确性、易读性、________和高效率等4个方面评价算法（包括程序）的质量。 8．一个算法通常可从正确性、易读性、健壮性和________________等四个方面评价、分析。 9．在算法正确的前提下，评价一个算法的两个标准是______。
10．对顺序表执行插入操作，其插入算法的平均时间复杂性为___________。
11．在顺序存储的线性表（a1,a2?，an）中的第i (1≤i≤n)个元素之前插入一个元素，则需向后移动_____________个元素。
12．链式存储结构的特点是借助_______来表示数据元素之间的逻辑关系。 13．已知指针p指向某单链表中的一个结点，则判别该结点有且仅有一个后继结点的条件是______。
14．双链表中前驱指针为prior，后继指针为next，在指针P所指结点前插入指针S所指的结点，需执行下列语句：
S→next=P;S→prior=P→prior;P→prior=S;_______;
15.若head表示循环链表的头指针，t表示尾结点，则头指针head与尾结点t之间的关系可表示为__________。
16. 删除双向循环链表中*p的前驱结点(存在)应执行的语句是____________。 17. 栈下溢是指在____________时进行出栈操作。
18．假设S和X分别表示进栈和出栈操作，由输入序列“ABC”得到输出序列“BCA”的操作序列为SSXSXX，则由“a*b+c/d”得到“ab*cd/+”的操作序列为___________。 19.我们通常把队列中允许插入的一端称为________________。 20.我们通常把队列中允许删除的一端称为__________。
21．链队列实际上是一个同时带有头指针和尾指针的单链表，尾指针指向该单链表的_____________。
8
22.在具有n个单元、且采用顺序存储的循环队列中，队满时共有___________个元素。
23．假设为循环队列分配的向量空间为Q[20]，若队列的长度和队头指针值分别为13和17，则当前尾指针的值为______。
24.空串的长度是________；空格串的长度是________。
25.对于顺序存储结构的二维数组，通常采用___________两种存放方式存储数据元素。 26．若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为__________。
27．假设按行优先顺序将一个20阶的三对角矩阵A压缩存储在一维数组Q中，其中Q[0]存放矩阵的第1个元素a1,1，那么矩阵元素a3,4在Q中的存储位置k=_______。
28. 设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4,e5和e6依次通过栈S，一个元素出栈后即进队列Q，若6个元素出队的序列是e2，e4，e3,e6,e5,e1则栈S的容量至少应该是____________。
29．设一棵二叉树中度为2的结点数为10，则该树的叶子数为________________。
30.在一棵度为3的树中，度为2的结点个数是1，度为0的结点个数是6，则度为3的结点个数是________。
31.对于一棵具有n个结点的二叉树，当进行链接存储时，其二叉链表中的指针域的总数为2n个，其中________个用于链接孩子结点。
32. 已知完全二叉树T的第5层只有7个结点，则该树共有____________个叶子结点。 33．在含100个结点的完全二叉树中，叶子结点的个数为___________。 34．在含有n个顶点的连通图中，任意两个不同顶点之间的简单路径的最大长度为_______。 35．一个具有10个顶点的完全无向图中有_______条边。 36．含n个顶点的无向连通图中至少含有______条边。 37.有向图G用邻接矩阵A［1··n，1··n］存储，其第i列的所有元素之和等于顶点Vi的________。
38.对于n个顶点的生成树，其边的个数为__________ 。
39．顶点数为n、边数为n(n-1)/2的无向图称为_____________。
40．用_______排序方法对关键字序列（20，25，12，47，15，83，30，76）进行排序时，前三趟排序的结果为：
20，12，25，15，47，30，76，83 12，20，15，25，30，47，76，83 12，15，20，25，30，47，76，83
41.快速排序最好情况下的时间复杂度为________，最坏情况下的时间复杂度为________。 42.利用筛选法将关键字序列(37，66，48，29，31，75)建成的大根堆为(________)。 43．在待排序的n个记录中任取一个记录，以该记录的键值作为标准，将所有记录分为两组，使得第一组中各记录的键值均小于或等于该键值，第二组中的各记录的键值均大于该键值；然后将该记录排在两组中间。再对所分成的两组分别使用上述方法，直到所有记录都排在适当位置为止。这种排序方法称为________________。
44．哈希表常用的两类解决冲突的方法是_______和_______。 45．一棵平衡二叉树中任一结点的平衡因子只可能是_______。
46.对二叉排序树进行________遍历，可得到排好序的递增结点序列。 47．5阶B树的根结点至少含有_________个关键字。
48. 产生冲突现象的两个关键字称为该散列函数的____________。
49．长度为L的顺序表，采用设置岗哨方式顺序查找，若查找不成功，其查找长度为________________。
50．若序列中关键字相同的记录在排序前后的相对次序不变，则称该排序算法是________
的。
三、判断题
9
1．数据的逻辑结构是指各数据元素之间的逻辑关系，是用户根据应用需要建立的。 2．存储相同数据元素，顺序存储比链式存储少占空间。
3．线性链表存储空间不一定是连续，且前件元素一定存储在后件元素的前面。 4．顺序表和一维数组一样，都可以按下标随机(或直接)访问。 5．二维数组可以视为数组元素为一维数组的一维数组。
6．在一个顺序存储的循环队列中，队头指针指向队头元素的后一个位置。 7．在用单链表表示的链式队列中．队头在链表的链尾位置。 8．用非递归方法实现递归算法时一定要使用递归工作钱。 9．凡是递归定义的数据结构都可以用递归算法来实现它的操作。
10．在一棵二叉树中，假定每个结点只有左子女，没有右子女，对它分别进行中序遍历和后序遍历，则具有相同的结果。
11．在二叉搜索树中，若各结点的搜索概率不等，使得搜索概率越小的结点离树根越近，则得到的是最优二叉搜索树。
12.用邻接矩阵法存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中结点个数有关，而与图的边数无关。
13.邻接表法只能用于有向图的存储，而相临矩阵法对于有向图和无向图的存储都适用。(错) 14.任何有向网络(AOV-网络)拓扑排序的结果是唯一的。 15．对于AOE网络，加速任一关键活动都能使整个工程提前完成。 16．直接选择排序是一种稳定的排序方法。
17．当向一个小根堆(最小堆)中插入一个具有最小值的元素时，该元素需要逐层向上调整，直到微调整到堆顶位置为止。 18．进行折半查找的表必须是顺序存储的有序表。
19．一棵m阶B树中每个结点最多有m个关健码，最少有2个关键码。
20．在散列法中采取开散列(链地址)法来解决冲突时，其装载因子的取值一定在(0，1)之间。
四、应用题
1. 假设以数组seqn［m］存放循环队列的元素，设变量rear和quelen分别指示循环队列中队尾元素的位置和元素的个数。
(1)写出队满的条件表达式； (2)写出队空的条件表达式；
(3)设m=40,rear=13,quelen=19,求队头元素的位置； (4)写出一般情况下队头元素位置的表达式。 2．某广义表的表头和表尾均为（a,(b,c)），画出该广义表的图形表示。 3.已知某二叉树的顺序存储结构如图所示，试画出该二叉树。 A B C D E F G 4．已知二叉树的先序序列和中序序列分别为HDACBGFE和ADCBHFEG。 （1）画出该二叉树；
（2）画出该二叉树的中序线索链表的存储表示。 （3）画出与（1）求得的二叉树对应的森林。
5．某二叉树的先根遍历序列为ABIJCDFGHE，中根遍历序列为IJBADGFHCE，试画出该二叉树，并写出它的后序遍历序列。
6．已知树如右图所示，
（1）写出该树的后序序列； （2）画出由该树转换得到的二叉树。
10