当前位置:首页 >> 政史地 >>

数据结构期末复习练习题


数据结构期末复习练习题
第一章 绪 论
一、单选题 1. 一个数组元素 a[i]与___ _____的表示等价。 A、 *(a+i) B、 a+i C、 *a+i D、 &a+i 2. 对于两个函数,若函数名相同,但只是__ _________不同则不是重载函数。 A、 参数类型 B、 参数个数 C、 函数类型 3. 若需要利用形参直接访问实参,则应把

形参变量说明为__ _____参数 A、 指针 B、 引用 C、 值 4. 下面程序段的时间复杂度为__________。 for(int i=0; i<m; i++) for(int j=0; j<n; j++) a[i][j]=i*j; 2 2 A、 O(m ) B、 O(n ) C、 O(m*n) D、 O(m+n) 5. 执行下面程序段时,执行 S 语句的次数为__________。 for(int i=1; i<=n; i++) for(int j=1; j<=i; j++) S; 2 2 A、 n B、 n /2 C、 n(n+1) D、 n(n+1)/2 6. 下面算法的时间复杂度为__________。 int f( unsigned int n ) { if ( n==0 || n==1 ) return 1; else return n*f(n-1); } 2 A、 O(1) B、 O(n) C、 O(n ) D、 O(n!) 二、填空题 1. 数据的逻辑结构被分为 集合结构、线性结构、树型结构、图形结构_四种。 2. 数据的存储结构被分为 _顺序、链接、索引、散列 四种。 3. 在线性结构、树形结构和图形结构中,前驱和后继结点之间分别存在着__ 1:1、1:N、 M:N ___的联系。 4. 一种抽象数据类型包括 数据定义、操作声明_两个部分。 5. 当一个形参类型的长度较大时, 应最好说明为__引用形参 ( 或 指针形参 )_______, 以节省参数值的传输时间和存储参数的空间。 6. 当需要用一个形参访问对应的实参时,则该形参应说明为___引用类型 ( 或 指针类 型_______。 7. 在函数中对引用形参的修改就是对相应___实参_____的修改,对___值_________形 参的修改只局限在该函数的内部,不会反映到对应的实参上。 8. 当需要进行标准 I/O 操作时,则应在程序文件中包含___ iostream.h _____________ 头文件, 当需要进行文件 I/O 操作时, 则应在程序文件中包含____ fstream.h ____________ 头文件。 9. 在包含有______ stdlib.h __________头文件的程序文件中,使用____ rand( ) %21



____________能够产生出 0~20 之间的一个随机整数。 10. 一个数组 a 所占有的存储空间的大小即数组长度为__ sizeof(a)__________,下标 为 i 的元素 a[i]的存储地址为____ a+i*sizeof(a[0])______,或者为___ a+i ___。 11. 函数重载要求______参数类型、数量 _或___次序_________有所不同。 12. 对于双目操作符,其重载函数带有_____2_____个参数,其中至少有一个为_____ 用户自定义_______的类型。 13. 若对象 ra 和 rb 中至少有一个是属于用户定义的类型,则执行 ra==rb 时,需要调 用_____= =_____重载函数,该函数的第一个参数应与____ra______的类型相同,第二个参 数应与______rb____的类型相同。 14. 从一维数组 a[n]中顺序查找出一个最大值元素的时间复杂度为__ O(n) ____,输 出一个二维数组 b[m][n]中所有元素值的时间复杂度为__ O(m*n)_ ___。 15. 在下面程序段中, s=s+p 语句的执行次数为__n______, p*=j 语句的执行次数为____ 2 n(n+1)/2___,该程序段的时间复杂度为__O(n )_______。 int i=0,s=0; while(++i<=n) { int p=1; for(int j=1;j<=i;j++) p*=j; s=s+p; } 16. 一个算法的时间复杂度为(3n2+2nlog2n+4n-7)/(5n),其数量级表示为___ O(n) _____。

第二章 线性表
一、单选题 1.在一个长度为 n 的顺序存储线性表中,向第 i 个元素(1≤i≤n+1)之前插入一个新元 素时,需要从后向前依次后移 个元素。 A、n-i B、n-i+1 C、n-i-1 D、i 2.在一个长度为 n 的顺序存储线性表中,删除第 i 个元素(1≤i≤n+1)时,需要从前向 后依次前移 个元素。 A、n-i B、n-i+1 C、n-i-1 D、i 3.在一个长度为 n 的线性表中顺序查找值为 x 的元素时,查找时的平均查找长度(即 x 同元素的平均比较次数,假定查找每个元素的概率都相等)为 。 A、n B、n/2 C、(n+1)/2 D、(n-1)/2 4.在一个单链表 HL 中,若要向表头插入一个由指针 p 指向的结点,则执行 。 A、HL = p; p->next = HL; B、p->next = HL; HL = p; C、p->next = HL; p = HL; D、p->next = HL->next; HL->next = p; 5.在一个单链表 HL 中,若要在指针 q 所指的结点的后面插入一个由指针 p 所指的结 点,则执行 。 A、q->next = p->next ; p->next = q;



B、p->next = q->next; q = p; C、q->next = p->next; p->next = q; D、p->next = q->next ; q->next = p; 6.在一个单链表 HL 中,若要删除由指针 q 所指向结点的后继结点,则执行 A、p = q->next ; p->next = q->next; B、p = q->next ; q->next = p; C、p = q->next ; q->next = p->next; D、q->next = q->next->next; q->next = q;



二、填空题 1.在线性表的单链接存储结构中,每个结点包含有两个域,一个叫 域,另 一个叫 域。 2.在下面数组 a 中链接存储着一个线性表,表头指针为 a[0].next,则该线性表为 。

a data next

0 4

1 60 3

2 56 7

3 42 6

4 38 2

5

6 74 0

7 25 1

8

3.对于一个长度为 n 的顺序存储的线性表,在表头插入元素的时间复杂度为 , 在表尾插入元素的时间复杂度为 。 4.对于一个长度为 n 的单链接存储的线性表,在表头插入元素的时间复杂度为 , 在表尾插入元素的时间复杂度为 。 5.在线性表的顺序存储中,若一个元素的下标为 i,则它的前驱元素的下标为 , 后继元素的下标为 。 6.在线性表的单链接存储中,若一个元素所在结点的地址为 p,则其后继结点的地址 为 ,若假定 p 为一个数组 a 中的下标,则其后继结点的下标为 。 7.在循环单链表中,最后一个结点的指针指向 结点。 8.在双向链表中每个结点包含有两个指针域,一个指向其 结点,另一个指 向其 结点。 9. 在循环双向链表中表头结点的左指针域指向 结点, 最后一个结点的右指 针域指向 结点。 10.在以 HL 为表头指针的带表头附加结点的单链表和循环单链表中,链表为空的条件 分别为 和 。 三、应用题 1.在下面的每个程序段中,假定线性表 La 的类型为 List,元素类型 ElemType 为 int, 并假定每个程序段是连续执行的,试写出每个程序段执行后所得到的线性表 La。 (1) InitList(La); int a[]={48,26,57,34,62,79}; for(i=0; i<6; i++) InsertFront(La,a[i]); TraverseList(La); (2) InitList(La);



for(i=0; i<6; i++) TraverseList(La); (3) ClearList(La); for(i=0; i<6; i++) Delete(La, a[5]); Sort(La); Insert(La,a[5]/2); TraverseList(La);

Insert(La,a[i]);

InsertRear(La,a[i]);

2.写出下面函数被调用执行后,得到的以 HL 为表头指针的单链表中的数据元素序列。 vo id AA(LNode * & HL) { In itList(H L); In sertRear(H L, 30 ); In sertRear(H L, 50 ); int a [5] = {15,8 ,9,26, 12}; for ( int i=0; i<5; i++ ) InsertFron t(H L,a[i]); } 3.对于 List 类型的线性表,编写出下列每个算法。 (1) 从线性表中删除具有最小值的元素并由函数返回,空出的位置由最后一个元素填 补,若线性表为空则显示出错信息并退出运行。 (2) 从线性表中删除第 i 个元素并由函数返回。 (3) 向线性表中第 i 个元素位置插入一个元素。 (4) 从线性表中删除具有给定值 x 的所有元素。 4.对于结点类型为 LNode 的单链表,编写出下列每个算法。 (1) 删除单链表中的第 i 个结点。 (2) 在有序单链表中插入一个元素 x 的结点。 (3) 从单链表中查找出所有元素的最大值,该值由函数返回,若单链表为空,则显示出 错信息并停止运行。 (4) 统计出单链表中结点的值等于给定值 x 的结点数。

第三章 稀疏矩阵和广义表
一、单选题 1. 在稀疏矩阵的带行指针向量的链接存储中,每个行单链表中的结点都具有相同的 ________。 A、 行号 B、 列号 C、 元素值 D、 地址 2. 设一个广义表中结点的个数为 n,则求广义表深度算法的时间复杂度为_______。 2 A、 O(1) B、 O(n) C、 O(n ) D、 O(log2n) 二、填空题



1. 在一个稀疏矩阵中, 每个非零元素所对应的三元组包括该元素的________、 ________ 和________三项。 2. 在稀疏矩阵所对应的三元组线性表中, 每个三元组元素按________为主序、 ________ 为辅序的次序排列。 3. 在初始化一个稀疏矩阵的函数定义中,矩阵形参应说明为________参数。 4. 在稀疏矩阵的顺序存储中, 利用一个数组来存储非零元素, 该数组的长度应________ 对应三元组线性表的长度。 5.在稀疏矩阵的带行指针向量的链接存储中,每个结点包含有________个域,在相应 的十字链接存储中,每个结点包含有________个域。 6. 在稀疏矩阵的十字链接存储中, 每个结点的 down 指针域指向________相同的下一个 结点,right 指针域指向________相同的下一个结点。 7.一个广义表中的元素分为________元素和________元素两类。 8.一个广义表的深度等于________嵌套的最大层数。 9.在广义表的存储结构中,每个结点均包含有________个域。 10.在广义表的存储结构中,单元素结点与表元素结点有一个域对应不同,各自分别为 ________域和________域。 11.若把整个广义表也看为一个表结点,则该结点的 tag 域的值为________,next 域 的值为________。 三、应用题 1. 已知一个稀疏矩阵如下图所示: 0 4 0 0 0 0 0 0 0 0 -3 0 0 1 8 0 0 0 0 0 0 0 0 0 5 0 0 0 0 -7 0 0 0 2 0 0 0 0 6 0 0 0 具有 6 行×7 列的一个稀疏矩阵 (1) 写出它的三元组线性表; (2) 给出它的顺序存储表示; (3) 给出它的转置矩阵的三元组线性表和顺序存储表示; 2. 画出下列每个广义表的带表头附加结点的链接存储结构图并分别计算出它们的长度 和深度。 (1) A=(()) (2) B=(a,b,c) (3) C=(a,(b,(c))) (4) D=((a,b),(c,d)) (5) E=(a,(b,(c,d)),(e)) (6) F=((a,(b,(),c),((d),e)))

第四章 栈和队列


一、单选题 1.栈的插入与删除操作在 进行。 A、栈顶 B、栈底 C、任意位置 D、指定位置 2.当利用大小为 N 的一维数组顺序存储一个栈时,假定用 top==N 表示栈空,则向这个 栈插入一个元素时,首先应执行 语句修改 top 指针。 A、top++ B、top-C、top=0 D、top 3.若让元素 1,2,3 依次进栈,则出栈次序不可能出现 种情况。 A、3,2,1 B、2,1,3 C、3,1,2 D、1,3,2 4.在一个循环顺序队列中,队首指针指向队首元素的 位置。 A、前一个 B、后一个 C、当前 D、后面 5.当利用大小为 N 的一维数组顺序存储一个循环队列时,该队列的最大长度为 。 A、N-2 B、N-1 C、N D、N+1 6.从一个循环顺序队列删除元素时,首先需要 。 A、前移一位队首指针 B、后移一位队首指针 C、取出队首指针所指位置上的元素 D、取出队尾指针所指位置上的元素 7.假定一个循环顺序队列的队首和队尾指针分别为 f 和 r,则判断队空的条件是 。 A、f+1==r B、r+1==f C、f==0 D、f==r 8.假定一个链队的队首和队尾指针分别为 front 和 rear,则判断队空的条件是 。 A、front==rear B、front!=NULL C、rear!=NULL D、front==NULL 二、填空题 1.队列的插入操作在 进行,删除操作在 进行。 2.栈又称为 表,队列又称为 表。 3.向一个顺序栈插入一个元素时,首先使 后移一个位置,然后把待插入元素 到这个位置上。 4.从一个栈中删除元素时,首先取出 ,然后再前移一位 。 5.在一个循环顺序队列 Q 中,判断队空的条件为 ,判断队满的条件 为 。 6.在一个顺序栈中,若栈顶指针等于 ,则为空栈;若栈顶指针等于 ,则 为满栈。 7.在一个链栈中,若栈顶指针等于 NULL,则为 ;在一个链队中,若队首指 针与队尾指针的值相同,则表示该队列为 或该队列为 。 8.向一个链栈插入一个新结点时,首先把栈顶指针的值赋给 ,然后把新结点 的存储位置赋给 。 9.从一个链栈中删除一个结点时,需要把栈顶结点 的值赋给 。 10.向一个顺序队列插入元素时,需要首先移动 ,然后再向所指位置 新 插入的元素。 11、当用长度为 N 的一维数组顺序存储一个栈时,假定用 top==N 表示栈空,则表示栈 满的条件为 。 12.向一个栈顶指针为 HS 的链栈中插入一个新结点*P 果,应执行 和 操作。 13.从一个栈顶指针为 HS 的非空链栈中删除结点并不需要返回栈顶结点的值和回收结 点时,应执行 操作。 14.假定 front 和 rear 分别为一个链队的队首和队尾指针,则该链队中只有一个结点



的条件为 。 15. 中缀算术表达式 3+4/(25-(6+15))*8 所对应的后缀算术表达式为 16. 后缀算术表达式 24 8 + 3 * 4 10 7 - * / 所对应的中缀算术表达式为 其值为 。 三、应用题 执行下面函数调用后得到的输出结果是什么? vo id A F(Q u e u e & Q ) { In i tQ u e u e (Q ); in t a [4 ] = { 5 , 8 , 1 2 , 1 5 } ; fo r ( in t i=0; i< 4 ; i+ + ) Q In se rt (Q , a[i]) ; Q In se rt (Q , QD e le te(Q )); Q In se rt (Q , 3 0 ); Q In se rt (Q , QD e le te(Q )+ 1 0 ); wh i le ( ! Q u e u e E mp t y(Q ) ) co u t < < QD elete(Q )< < ’ ‘; }

。 ,

四、编程题 裴波那契(Fibonacci)数列的定义为:它的第 1 项和第 2 项均为 1,以后各项为其前两 项之和。若裴波那契数列中的第 n 项用 Fib(n)表示,则计算公式为: ? 1 (n=1 或 2) Fib(n)=? ? Fib(n-1)+Fib(n-2) (n>=2) 试编写出计算 Fib(n)的递归算法和非递归算法,并分析它们的时间复杂度和空间复杂 度。

第五章 树和二叉树
一、填空题 1.对于一棵具有 n 个结点的树,该树中所有结点的度数之和为______。 2. 假定一棵三叉树的结点个数为 50, 则它的最小深度为________, 最大深度为_______。 3.在一棵三叉树中,度为 3 的结点数有 2 个,度为 2 的结点数有 1 个,度为 1 的结点 数为 2 个,那么度为 0 的结点数有________个。 4.一棵深度为 5 的满二叉树中的结点数为________个,一棵深度为 3 的满三叉树中的 结点数为________个。 5.假定一棵树的广义表表示为 A(B(C,D(E,F,G),H(I,J))),则树中所含的结点数为 ________个,树的深度为________,树的度为________。 6.假定一棵树的广义表表示为 A(B(C,D(E,F,G),H(I,J))),则度为 3、2、1、0 的结点 数分别为______、______、______和______个。 7. 假定一棵树的广义表表示为 A(B(C,D(E,F,G),H(I,J))),则结点 H 的双亲结点为 ________,孩子结点为___________。 8.在一棵二叉树中,假定双分支结点数为 5 个,单分支结点数为 6 个,则叶子结点数



为________个。 9.对于一棵二叉树,若一个结点的编号为 i,则它的左孩子结点的编号为________, 右孩子结点的编号为________,双亲结点的编号为________。 10.在一棵二叉树中,第 5 层上的结点数最多为______。 11. 假定一棵二叉树的结点数为 18, 则它的最小深度为________, 最大深度为________。 12.一棵二叉树的广义表表示为 a(b(c,d),e(f(,g))),则 e 结点的双亲结点为______, 左孩子结点为________,右孩子结点为________。 13. 一棵二叉树的广义表表示为 a(b(c,d),e(f(,g))),它含有双亲结点______个,单 分支结点______个,叶子结点______个。 14. 假定一棵二叉树顺序存储在一维数组 a 中,则 a[i]元素的左孩子元素为________, 右孩子元素为________,双亲元素(i>1)为________。 15.假定一棵二叉树顺序存储在一维数组 a 中,但让编号为 1 的结点存入 a[0]元素中, 让编号为 2 的结点存入 a[1]元素中,其余类推,则编号为 i 结点的左孩子结点对应的存储 位置为________, 若编号为 i 结点的存储位置用 j 表示, 则其左孩子结点对应的存储位置为 ________。 16.若对一棵二叉树从 0 开始进行结点编号, 并按此编号把它顺序存储到一维数组 a 中, 即编号为 0 的结点存储到 a[0]中,其余类推,则 a[i]元素的左孩子元素为________,右孩 子元素为________,双亲元素(i>0)为________。 17.对于一棵具有 n 个结点的二叉树,对应二叉链表中指针总数为________个,其中 ________个用于指向孩子结点,________个指针空闲着。 18. 一棵二叉树广义表表示为 a(b(d(,h)),c(e,f(g,i(k)))), 该树的结点数为________ 个,深度为________。 19. 假定一棵二叉树广义表表示为 a(b(c),d(e,f)),则对它进行的先序遍历结果为 ____________,中序遍历结果为____________,后序遍历结果为____________,按层遍历结 果为____________。 20. 假定一棵普通树的广义表表示为 a(b(e),c(f(h,i,j),g),d),则先根遍历结果为 ____________,按层遍历结果为___________。 二、应用题 1. 已知一棵具有 n 个结点的完全二叉树被顺序存储于一维数组的 A[1]?A[n]元素中, 试编写一个算法打印出编号为 i 的结点的双亲和所有孩子。 2. 编写一算法,求出一棵二叉树中所有结点数和叶子结点数,假定分别用变参 C1 和 C2 统计所有结点数和叶子结点数,初值均为 0。

a
3. 对于右图所示的树: (1) 写出先根遍历得到的结点序列; (2) 写出按层遍历得到的结点序列; (3) 画出转换后得到的二叉树和二叉链表。

b e f

c g k h l

d i m j

第六章 二叉树的应用


一、单选题 1. 从二叉搜索树中查找一个元素时,其时间复杂度大致为________。 2 A、 O(n) B、 O(1) C、 O(log2n) D、 O(n ) 2. 向二叉搜索树中插入一个元素时,其时间复杂度大致为________。 A、 O(1) B、 O(log2n ) C、 O(n) D、 O(nlog2n) 3. 根据 n 个元素建立一棵二叉搜索树时,其时间复杂度大致为________。 2 A、 O(n) B、 O(log2n ) C、 O(n ) D、 O(nlog2n) 4. 从堆中删除一个元素的时间复杂度为________。 A、 O(1) B、 O(n) C、 O(log2n) D、 O(nlog2n) 5. 向堆中插入一个元素的时间复杂度为________。 A、 O(log2n) B、 O(n) C、 O(1) D、 O(nlog2n) 6. 由权值分别为 3,8,6,2,5 的叶子结点生成一棵哈夫曼树,它的带权路径长度为 ________。 A、 24 B、 48 C、 72 D、 53 二、填空题 1. 在一棵二叉搜索树中,每个分支结点的左子树上所有结点的值一定________该结点 的值,右子树上所有结点的值一定________该结点的值。 2.对一棵二叉搜索树进行中序遍历时,得到的结点序列是一个________。 3. 从一棵二叉搜索树中查找一个元素时, 若元素的值等于根结点的值, 则表明_______, 若元素的值小于根结点的值,则继续向________查找,若元素的大于根结点的值,则继续向 ________查找。 4. 在一个堆的顺序存储中, 若一个元素的下标为 i, 则它的左孩子元素的下标为______, 右孩子元素的下标为________。 5. 在一个小根堆中,堆顶结点的值是所有结点中的________,在一个大根堆中,堆顶 结点的值是所有结点中的________。 6.当从一个小根堆中删除一个元素时,需要把________元素填补到________位置,然 后再按条件把它逐层________调整。 三、应用题 1. 已知一组元素为(46,25,78,62,12,37,70,29), 画出按元素排列顺序输入生成的一棵 二叉搜索树。 2. 空堆开始依次向堆中插入线性表 (38,64,52,15,73,40,48,55,26,12) 中的每个元素, 请以线性表的形式给出每插入一个元素后堆的状态。 3. 已知一个堆为(12,15,40,38,26,52,48,64) ,若需要从堆中依次删除四个元素,请 给出每删除一个元素后堆的状态。 4. 有七个带权结点,其权值分别为 3,7,8,2,6,10,14,试以它们为叶子结点构造一棵 哈夫曼树,并计算出带权路径长度 WPL。 四、算法设计 1.编写在以 BST 为树根指针的二叉搜索树上进行查找值为 item 的结点的非递归算法,



若查找成功则由 item 带回整个结点的值并返回 true,否则返回 false。 bool Find( BTreeNode * BST , ElemType & item ) 2.下面的算法功能是向 HBT 堆中插入一个值为 item 的元素,使得插入后仍是一个堆。 请在画有横线的地方填上合适的语句,完成其功能。 vo id AH(Heap & HBT , con st E lemType item) // 形 参 HBT 为 一 个 小 根 堆 { HBT.heap[HBT.size]= item; HBT.size++; Ele mType x =ite m int i=HBT.size -1; while ( i != 0 ){ in t j= ; if ( x> =HBT.heap[j]) break ; ; ; } HBT.heap[i]= x; }

第七章 图
一、填空题 1.在一个图中,所有顶点的度数之和等于所有边数的________倍。 2.在一个具有 n 个顶点的无向完全图中,包含有________条边,在一个具有 n 个顶点 的有向完全图中,包含有________条边。 3. 在一个具有 n 个顶点的无向图中,要连通所有顶点则至少需要________条边。 4.表示图的三种存储结构为________、________和________。 5. 对于一个具有 n 个顶点的图,若采用邻接矩阵表示,则矩阵大小为________。 6.对于一个具有 n 个顶点和 e 条边的有向图和无向图,在其对应的邻接表中,所含边 结点分别为________和________条。 7. 在有向图的邻接表和逆邻接表表示中,每个顶点邻接表分别链接着该顶点的所有 ________和________结点。 8.对于一个具有 n 个顶点和 e 条边的有向图和无向图,若采用边集数组表示,则存于 数组中的边数分别为________和________条。 9.对于一个具有 n 个顶点和 e 条边的无向图,当分别采用邻接矩阵、邻接表和边集数 组表示时,求任一顶点度数的时间复杂度依次为________、________和________。 10. 假定一个图具有 n 个顶点和 e 条边,则采用邻接矩阵、邻接表和边集数组表示时, 其相应的空间复杂度分别为________、________和________。

10

11. 对用邻接矩阵表示的图进行任一种遍历时,其时间复杂度为________,对用邻接表 表示的图进行任一种遍历时,其时间复杂度为________。 12.对于下面的无向图 G1,假定用邻接矩阵表示,则从顶点 v0 开始进行深度优先搜索 遍历得到的顶点序列为____________,从顶点 v0 开始进行广度优先搜索遍历得到的顶点序 列为____________。 13. 对于下面的有向图 G2,假定用邻接矩阵表示,则从顶点 v0 开始进行深度优先搜索 遍历得到的顶点序列为____________,从顶点 v0 开始进行广度优先搜索遍历得到的顶点序 列为____________。 14. 对于下面的带权图 G3,其最小生成树的权为________。 15.对于下面的带权图 G3,若从顶点 v0 出发,则按照普里姆算法生成的最小生成树中, 依次得到的各条边为_______________。 16. 对于下面的带权图 G3,若按照克鲁斯卡尔算法产生最小生成树,则得到的各条边 依次为_______________。

0 A 1 2 4 图G1 5 3 C D 图G2 E B 7

0

5

1 3

8

12
2 6

15
3 图G3

4

17.假定用一维数组 d[n]存储一个 AOV 网中用于拓扑排序的顶点入度,则值为 0 的元 素被链接成为一个________。 18. 对于一个具有 n 个顶点和 e 条边的连通图,其生成树中的顶点数和边数分别为 ________和________。 二、应用题 1. 对于下图 G4 和 G5,按下列条件试分别写出从顶点 v0 出发按深度优先搜索遍历得到 的顶点序列和按广度优先搜索遍历得到的顶点序列。 (1) 假定它们均采用邻接矩阵表示; (2) 假定它们均采用邻接表表示, 并且假定每个顶点邻接表中的结点是按顶点序号从大 到小的次序链接的。
0 1 7 8 2 图G4 3 6 5 9 6 7 图G5 8 4 0 1 2

3

4

5

2. 对于下图 G6,试给出一种拓扑序列,若在它的邻接表存储结构中,每个顶点邻接表 中的边结点都是按照终点序号从大到小链接的,则按此给出唯一一种拓扑序列。

11

20

2 0 3 1 4 图G6 6 8 5 7 9

第八章 查找
一、填空题 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]中每一元素的概率相等,试分别求出进行顺序、二分查找每

12

一元素时的平均查找长度。 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 个记录进行归并排序时,共需要进行________趟归并,在第三趟归并时是把

13

长度为________的有序表两两归并为长度为________的有序表。 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]上进行快速排序的递归算法。 vo id Q u ic k S o r t( E le mTyp e A [] , in t s , in t t ) { in t i = s, j = t+1; E le mTyp e x = A [s]; do { do i+ + ; wh ile ( ) ; // 填写一个循环条件 do j --; wh ile ( A [j]. s tn > x . stn ) ; if ( i< j ) { E le mTyp e te mp = A [i] ; A [i] = A [j ] ; A [j] = te mp ; } } wh ile ( i< j ); A [s] = A [j] ; A [j] = x ; if ( s< j -1 ) ; if ( j+ 1 < t ) ; }

14


相关文章:
数据结构期末复习章节试题(附答案)
数据结构期末复习章节试题(附答案)_计算机硬件及网络_IT/计算机_专业资料。1 1 第一章概论 自测题答案 一、填空题 1. 数据结构是一门研究非数值计算的程序设计...
必看!!!!!数据结构期末复习题及部分答案解析
必看!!!数据结构期末复习题及部分答案解析_理学_高等教育_教育专区。0 一.是非...数据结构期末复习题及答... 12页 1下载券 数据结构期末试题及答案 9页 2下...
数据结构期末考试试题及答案
数据结构期末考试试题及答案_理学_高等教育_教育专区。数据结构期末考试试题及答案...数据结构期末考试复习题 4页 免费 数据结构期末考试试题 6页 1下载券 ©...
《数据结构》期末考试试题及答案
数据结构期末考试试题及答案 (2003-2004 学年第 2 学期) 贵州大学理学院数学系信息与计算科学专业 一、 单项选择题 1.对于一个算法,当输入非法数据时,也...
数据结构期末复习练习题
数​据​结​构​期​末​复​习​练​习​题 暂无评价|0人阅读|0次下载|举报文档数据结构期末复习练习题第一章 绪论一、单选题 1. 一个...
数据结构期末复习题及部分答案解析
数据结构期末复习题及部分答案解析_理学_高等教育_教育专区。一.是非题 1. 数据...数据结构期末复习题及答... 35页 1下载券 数据结构 期末试题1 含... 21页...
数据结构期末考试题
数据结构期末考试题_从业资格考试_资格考试/认证_教育专区。一、 单选题(每题 ...a1。 Void contrary (Lnode * & HL) 数据结构试题(答案)一、单选题(每小题...
2015年数据结构期末考试题及答案
2012 年数据结构期末考试题及答案 一、选择题 1.在数据结构中,从逻辑上可以把数据结构分为 A.动态结构和静态结构 C.线性结构和非线性结构 C 。 B.紧凑结构和...
数据结构期末复习题
校园网-数据结构试题及答... 50页 免费 数据结构期末复习题 5页 免费 数据结构(c语言版)复习资... 5页 1下载券数​据​结​构​期​末​复​...
数据结构C语言版期末考试试题(附带复习资料)
数据结构期末考试试题 一、单选题(每小题 2 分,共 12 分) 1.在一个单链表 HL 中,若要向表头插入一个由指针 p 指向的结点,则执行( )。 A. HL=...
更多相关标签: