18. 对于一个具有n个顶点和e条边的连通图，其生成树中的顶点数和边数分别为________和________。
二、应用题
1. 对于下图G4和G5，按下列条件试分别写出从顶点v0出发按深度优先搜索遍历得到的顶点序列和按广度优先搜索遍历得到的顶点序列。 (1) 假定它们均采用邻接矩阵表示; (2) 假定它们均采用邻接表表示，并且假定每个顶点邻接表中的结点是按顶点序号从大到小的次序链接的。
2. 对于下图G6，试给出一种拓扑序列，若在它的邻接表存储结构中，每个顶点邻接表中的边结点都是按照终点序号从大到小链接的，则按此给出唯一一种拓扑序列。
第七部分 查找
一、填空题 1．以顺序查找方法从长度为n的线性表中查找一个元素时，平均查找长度为________，时间复杂度为________。
2．以二分查找方法从长度为n的线性有序表中查找一个元素时，平均查找长度小于等于________，时间复杂度为________。 3．以二分查找方法从长度为12的有序表中查找一个元素时，平均查找长度为________。 4．以二分查找方法查找一个线性表时，此线性表必须是________存储的________表。 5．从有序表(12,18,30,43,56,78,82,95)中依次二分查找43和56元素时，其查找长度分别为________和________。
6．对于二分查找所对应的判定树，它既是一棵_______，又是一棵________。
7．假定对长度n=50的有序表进行二分查找，则对应的判定树高度为________，判定树中前5层的结点数为________，最后一层的结点数为________。
8．在索引表中，每个索引项至少包含有________域和________域这两项。 9．假定一个线性表为(12,23,74,55,63,40,82,36)，若按Key % 3条件进行划分，使得同一余数的元素成为一个子表，则得到的三个子表分别为________、________和________。
10. 假定一个线性表为(”abcd”,”baabd”,”bcef”,”cfg”,”ahij”,”bkwte”,”ccdt”,
”aayb”)，若按照字符串的第一个字母进行划分，使得同一个字母被划分在一个子表中，则得到的a,b,c三个子表的长度分别为________、________和________。
11．在线性表的________存储中，无法查找到一个元素的前驱或后继元素。 12．在线性表的________存储中，对每一个元素只能采用顺序查找。
13．假定对线性表(38,25,74,52,48)进行散列存储，采用H(K)=K % 7作为散列函数，若分别采用线性探查法和链接法处理冲突，则对各自散列表进行查找的平均查找长度分别为_______和________。
14．假定要对长度n=100的线性表进行散列存储，并采用链接法处理冲突，则对于长度m=20的散列表，每个散列地址的单链表的长度平均为________。
15. 在线性表的散列存储中，处理冲突有________和________两种方法。
16．对于线性表(18,25,63,50,42,32,90)进行散列存储时，若选用H(K)=K % 9作为散列函数，则散列地址为0的元素有________个，散列地址为5的元素有________个。
二、应用题
1. 假定查找有序表A[25]中每一元素的概率相等，试分别求出进行顺序、二分查找每一元素时的平均查找长度。 2. 假定一个待散列存储的线性表为(32,75,29,63,48,94,25,46,18,70)，散列地址空间为HT[13]，若采用除留余数法构造散列函数和线性探查法处理冲突，试求出每一元素的散列地址，画出最后得到的散列表，求出平均查找长度。 3. 假定一个待散列存储的线性表为(32,75,29,63,48,94,25,46,18,70)，散列地址空间为HT[11]，若采用除留余数法构造散列函数和链接法处理冲突，试求出每一元素的散列地址，画出最后得到的散列表，求出平均查找长度。
三、算法设计
设计在有序表A[n]中按二分查找关键字为K的递归和非递归算法。
第八部分 排序
一、填空题
1．每次从无序表中取出一个元素，把它插入到有序表中的适当位置，此种排序方法叫做________排序；每次从无序表中挑选出一个最小或最大元素，把它交换到有序表的一端，此种排序方法叫做________排序。 2．每次直接或通过基准元素间接比较两个元素，若出现逆序排列时就交换它们的位置，此种排序方法叫做________排序；每次使两个相邻的有序表合并成一个有序表的排序方法叫做________排序。
3．在直接选择排序中，记录比较次数的时间复杂度为________，记录移动次数的时间复杂度为________。
4. 在堆排序的过程中，对n个记录建立初始堆需要进行________次筛运算，由初始堆到堆排序结束，需要对树根结点进行_______次筛运算。
5．在堆排序的过程中，对任一分支结点进行筛运算的时间复杂度为________，整个堆排序过程的时间复杂度为________。 6．假定一组记录的排序码为(46,79,56,38,40,84)，则利用堆排序方法建立的初始堆为________________。
7. 快速排序在平均情况下的时间复杂度为________，在最坏情况下的时间复杂度为________。
8．快速排序在平均情况下的空间复杂度为________，在最坏情况下的空间复杂度为________。
9．在快速排序方法中，进行每次划分时，是从当前待排序区间的________向________依次查找出处于逆序的元素并交换之，最后将基准元素交换到一个确定位置，从而以该位置把当前区间划分为前后两个子区间。
10. 假定一组记录的排序码为(46,79,56,38,40,80)，对其进行快速排序的一次划分的结果为________________。
11. 假定一组记录的排序码为(46,79,56,38,40,80)，对其进行快速排序的过程中，对应二叉搜索树的深度为________，分支结点数为________。
12．在二路归并排序中，对n个记录进行归并的趟数为________。 13. 在归并排序中，进行每趟归并的时间复杂度为________，整个排序过程的时间复杂度为________，空间复杂度为________。
14．对20个记录进行归并排序时，共需要进行________趟归并，在第三趟归并时是把长度为________的有序表两两归并为长度为________的有序表。
15．假定一组记录的排序码为(46,79,56,38,40,80)，对其进行归并排序的过程中，第二趟归并后的结果为________________。
二、应用题
已知一组元素的排序码为
(46，74，16，53，14，26，40，38，86，65，27，34)
(1) 利用直接插入排序的方法写出每次向前面有序表插入一个元素后的排列结果。 (2) 利用直接选择排序方法写出每次选择和交换后的排列结果。 (3) 利用堆排序的方法写出在构成初始堆和利用堆排序的过程中，每次筛运算后的排列结果，并画出初始堆所对应的完全二叉树。 (4) 利用快速排序的方法写出每一层划分后的排列结果，并画出由此快速排序得到的二叉搜索树。
(5) 利用归并排序的方法写出每一趟二路归并排序后的结果。
三、算法设计
完成从一维数组A[n]上进行快速排序的递归算法。
void QuickSort( ElemType A[] , int s , int t ) {
int i = s, j = t+1; ElemType x = A[s]; do {
do i++; while ( ) ; tn > );
if ( i { ElemType temp = A[i] ; A[i] = A[j] ; A[j] = temp; } } while ( i A[s] = A[j]; A[j] = x; if ( s 数据结构练习题参考答案 第一部分 绪 论 一、单选题 1. A 2. C 3. B 4. C 5. D 6. B 二、填空题 1. 集合结构、线性结构、树型结构、图形结构 2. 顺序、链接、索引、散列 3. 1:1、1:N、M:N 4. 数据定义、操作声明 5. 引用形参 ( 或 指针形参 ) 6. 引用类型 ( 或 指针类型 ) 7. 实参、值 8. 、 9. 、rand( ) ! 10. sizeof(a)、a+i*sizeof(a[0])、a+i 11. 参数类型、数量、次序 12. 2、用户自定义 13. = = 、ra 、rb 14. O(n)、O(m*n) 15. n、n(n+1)/2、O(n2 ) 16. O(n) 第二部分 线性表 一、单选题 1. B 2. A 3. C 4. B 5. D 6. C 二、填空题 1. 元素值、指针 2. ( 38 , 56 , 25 , 60 , 42 , 74 ) 3. O(n)、O(1) 4. (1)、O(n) 5. i-1、i+1 6. p->next 、a[p].next 7. 表头 8. 前驱、后继 9. 表尾、表头 10．HL->next = = NULL 、HL->next = = HL 三、应用题 1. (1) ( 79 , 62 , 34 , 57 , 26 , 48 ) (2) ( 26 , 34 , 48 , 57 , 62 , 79 ) (3) ( 26, 34 , 39 , 48 , 57 , 62 ) 2． （12，26，9，8，15，30，50） 3．(1) ElemType DMValue( List & L ) { if ( ListEmpty(L) ) { A 2. B 3. C 4. A 5. B 6. D 二、填空题 1. 队尾、队首 2. 后进先出(LIFO)、先进先出(FIFO) 3. 栈顶指针、存储 4. 栈顶元素、栈顶指针 5. front = = rear 、(rear+1)%QueueMaxSize = = front 6. –1 、StackMaxSize-1 7. 栈空、空队、队列只有一个元素 8. 新结点的指针域、栈顶指针 9. 指针域、栈顶指针 10. 队尾指针、存储 11. top = = 0 12. p->next = HS 、HS = p 13. HS = HS->next B 7. D 8.
相关推荐：
loading