当前位置:首页 >> 其它课程 >>

《c语言数据结构》自测题试卷


第一章概论自测题姓名班级
题号 题分 得分 一 33 二 15 三 9 四 8 五 20 六 15 总分 100

一、填空题(每空 1 分,共 33 分)
1. 一个计算机系统包括和两大部分。 2. 一台计算机中全部程序的集合,称为这台计算机的。 3. 计算机软件可以分为软件和软件两大类。科学计算程序包属于,诊断程序属于。 4. 一种用助

忆符号来表示机器指令的操作符和操作数的语言是。 5. 数据结构是一门研究非数值计算的程序设计问题中计算机的以及它们之间的和运算等的学科。 6. 数据结构被形式地定义为(D, R) ,其中 D 是的有限集合,R 是 D 上的有限集合。 7. 数据结构包括数据的、数据的和数据的这三个方面的内容。 8. 数据结构按逻辑结构可分为两大类,它们分别是和。 9. 线性结构中元素之间存在关系,树形结构中元素之间存在关系,图形结构中元素之间存在关系。 10.在线性结构中,第一个结点前驱结点,其余每个结点有且只有 1 个前驱结点;最后一个结 点后续结点,其余每个结点有且只有 1 个后续结点。 11. 在树形结构中,树根结点没有结点,其余每个结点有且只有个前驱结点;叶子结点没有结点,其余每 个结点的后续结点数可以。 12. 在图形结构中,每个结点的前驱结点数和后续结点数可以。 13.数据的存储结构可用四种基本的存储方法表示,它们分别是。 14. 数据的运算最常用的有 5 种,它们分别是。 15. 一个算法的效率可分为效率和效率。 16.任何一个 C 程序都由和若干个被调用的其它函数组成。 17. 变量一经说明,就确定该变量的取值范围及。

二、单项选择题(每小题 1 分,共 15 分)
() 1. 通常所说的主机是指∶ A) CPU B) CPU 和内存

C) CPU、内存与外存

D) CPU、内存与硬盘

1

()2.在计算机内部,一切信息的存取、处理和传送的形式是∶ A)ACSII 码 B) BCD 码 C)二进制 D)十六进制 ()3.软件与程序的区别是∶ A) 程序价格便宜、软件价格昂贵; B) 程序是用户自己编写的,而软件是由厂家提供的; C) 程序是用高级语言编写的,而软件是由机器语言编写的; D) 软件是程序以及开发、 使用和维护所需要的所有文档的总称, 而程序只是软件的一部分。 ()4.所谓“裸机”是指∶ A) 单片机 B)单板机 机

C) 不装备任何软件的计算机

D) 只装备操作系统的计算

()5. 应用软件是指∶ A)所有能够使用的软件 C)所有微机上都应使用的基本软件

B) 能被各应用单位共同使用的某种软件 D) 专门为某一应用目的而编制的软件

()6. C 语言中的常量可分为整型常量、实型常量、字符型常量及四种。 (A) 符号常量(B)长整型常量(C)逻辑常量(D)二进制整数 ()7. 编译程序的功能是∶ A)发现源程序中的语法错误 B)改正源程序中的语法错误 C)将源程序编译成目标程序 D)将某一高级语言程序翻译成另一种高级语言程序 ()8. 系统软件中最重要的是∶ A) 操作系统 B) 语言处理系统 ()9.可移植性最好的计算机语言是∶ A) 机器语言 B)汇编语言

C) 工具软件

D) 数据库管理系统

C) 高级语言

D) 自然语言

()10. 非线性结构是数据元素之间存在一种: A)一对多关系 B)多对多关系

C)多对一关系

D)一对一关系

()11. 数据结构中,与所使用的计算机无关的是数据的结构; A)存储 B)物理 C)逻辑 ()12. 算法分析的目的是: A)找出数据结构的合理性 C) 分析算法的效率以求改进 ()13. 算法分析的两个主要方面是: A)空间复杂性和时间复杂性 C)可读性和文档性 ()14. 计算机算法指的是: A)计算方法

D)物理和存储

B)研究算法中的输入和输出的关系 D)分析算法的易懂性和文档性

B)正确性和简明性 D)数据复杂性和程序复杂性

B) 排序方法

C)解决问题的有限运算序列

D)调度方法

()15. 计算机算法必须具备输入、输出和等 5 个特性。 A)可行性、可移植性和可扩充性 B)可行性、确定性和有穷性

2

C)确定性、有穷性和稳定性

D)易读性、稳定性和安全性

三、简答题(每小题 3 分,共 9 分)
1.我们知道计算机只能执行机器指令,为什么它能运行用汇编语言和高级语言编写的程序?

2.数据结构和数据类型两个概念之间有区别吗?

3. 简述线性结构与非线性结构的不同点。

四、阅读下列 C 程序段,写出相应的执行结果(每小题 4 分,共 8 分)
1. printf(“Input x”); scanf(“%d”,&x); if (x<=30) if(x>20) y=x; else if (x>10) y=2*x; if (x>0&&x<30)printf(“x=%d,y=%d”,x,y); else printf(“输入数据错!”); 试写出当 x 分别为 18,8 时的执行结果。 } main() {int n; long y; n=5; y=fact(n); printf(“%d,%ld\n”,n,y); } 2. long int fact(n) int n; {long f; if(n>1)f=n*fact(n-1); else f=1; return(f);

3

五、分析下面各程序段的时间复杂度(每小题 5 分,共 20 分)
1. for (i=0; i<n; i++) for (j=0; j<m; j++) A[i][j]=0; 2. s=0; for (i=0; i<n; i++) for(j=0; j<n; j++) s+=B[i][j]; sum=s;

3.

x=0; for(i=1; i<n; i++) for (j=1; j<=n-i; j++) x++;

4.

i=1; while(i<=n) i=i*3;

六、设有数据逻辑结构 S=(D,R) ,试按各小题所给条件画出这些逻辑结构的图示,并确定 相对于关系 R,哪些结点是开始结点,哪些结点是终端结点?(每小题 5 分,共 15 分)
1. D={d1,d2,d3,d4} R={(d1,d2),(d2,d3),(d3,d4) }

2.

D={d1,d2,?,d9} R={(d1,d2),(d1,d3),(d3,d4),(d3,d6),(d6,d8),(d4,d5), (d6,d7),(d8,d9) }

3.

D={d1,d2,?,d9} R={(d1,d3),(d1,d8),(d2,d3),(d2,d4),(d2,d5),(d3,d9), (d5,d6),(d8,d9),(d9,d7), (d4,d7),(d4,d6)}

4

第 2 章线性表自测卷姓名班级
题号 题分 得分 一 13 二 10 三 10 四 10 五 7 六 10 七 40 总分 100

一、填空(每空 1 分,共 13 分)
1. 在顺序表中插入或删除一个元素,需要平均移动元素,具体移动的元素个数 与有关。 2. 线性表中结点的集合是的,结点间的关系是的。 3. 向一个长度为 n 的向量的第 i 个元素(1≤i≤n+1)之前插入一个元素时,需向后移动个元素。 4. 向一个长度为 n 的向量中删除第 i 个元素(1≤i≤n)时,需向前移动个元素。 5. 在顺序表中访问任意一结点的时间复杂度均为,因此,顺序表也称为的数据结构。 6. 顺序表中逻辑上相邻的元素的物理位置相邻。单链表中逻辑上相邻的元素的物理位置相邻。 7. 在单链表中,除了首元结点外,任一结点的存储位置由指示。 8.在 n 个结点的单链表中要删除已知结点*p,需找到它的,其时间复杂度为。

二、判断正误(在正确的说法后面打勾,反之打叉) (每小题 1 分,共 10 分)
()1. 链表的每个结点中都恰好包含一个指针。 ()2.链表的物理存储结构具有同链表一样的顺序。 ()3.链表的删除算法很简单,因为当删除链中某个结点后,计算机会自动将后续各个单元向前移动。 ()4.线性表的每个结点只能是一个简单类型,而链表的每个结点可以是一个复杂类型。 ()5. 顺序表结构适宜于进行顺序存取,而链表适宜于进行随机存取。 ()6. 顺序存储方式的优点是存储密度大,且插入、删除运算效率高。 ()7. 线性表在物理存储空间中也一定是连续的。 ()8. 线性表在顺序存储时,逻辑上相邻的元素未必在存储的物理位置次序上相邻。 ()9. 顺序存储方式只能用于存储线性结构。 ()10. 线性表的逻辑顺序与存储顺序总是一致的。

三、单项选择题(每小题 1 分,共 7 分)
()1.数据在计算机存储器内表示时,物理地址与逻辑地址相同并且是连续的,称之为: (A)存储结构(B)逻辑结构(C)顺序存储结构(D)链式存储结构 ()2. 一个向量第一个元素的存储地址是 100,每个元素的长度为 2,则第 5 个元素的地址是 (A)110 (B)108 (C)100 (D)120 ()3. 在 n 个结点的顺序表中,算法的时间复杂度是 O(1)的操作是: (A) 访问第 i 个结点(1≤i≤n)和求第 i 个结点的直接前驱(2≤i≤n) (B) 在第 i 个结点后插入一个新结点(1≤i≤n) (C) 删除第 i 个结点(1≤i≤n) (D) 将 n 个结点从小到大排序 ()4. 向一个有 127 个元素的顺序表中插入一个新元素并保持原来顺序不变,平均要移动个元素 (A)8 (B)63.5 (C)63 (D)7 ()5. 链接存储的存储结构所占存储空间:

5

(A) 分两部分,一部分存放结点值,另一部分存放表示结点间关系的指针 (B) 只有一部分,存放结点值 (C)只有一部分,存储表示结点间关系的指针 (D)分两部分,一部分存放结点值,另一部分存放结点所占单元数 ()6. 链表是一种采用存储结构存储的线性表; (A)顺序(B)链式(C)星式(D)网状 ()7. 线性表若采用链式存储结构时,要求内存中可用存储单元的地址: (A)必须是连续的(B)部分地址必须是连续的 (C)一定是不连续的(D)连续或不连续都可以 ()8.线性表L在情况下适用于使用链式结构实现。 (A)需经常修改L中的结点值(B)需不断对L进行删除插入 (C)L中含有大量的结点(D)L中结点结构复杂 ()9.单链表的存储密度 (A)大于 1; (B)等于 1; (C)小于 1; (D)不能确定 ()10.设 a1、a2、a3 为 3 个结点,整数 P0,3,4 代表地址,则如下的链式存储结构称为
? ? P0 a1 3 a2 4 A3 0 (A)循环链表(B)单链表(C)双向循环链表(D)双向链表 P0 ? 3 4

四、简答题(每小题 5 分,共 10 分)
1. 试比较顺序存储结构和链式存储结构的优缺点。在什么情况下用顺序表比链表好?

2 . 描述以下三个概念的区别:头指针、头结点、首元结点(第一个元素结点) 。在单链表中设置头结点 的作用是什么?

6

五、 分)线性表具有两种存储方式,即顺序方式和链接方式。现有一个具有五个元素的线性表 L={23, (7 17,47,05,31},若它以链接方式存储在下列 100~119 号地址空间中,每个结点由数据(占 2 个字节) 和指针(占 2 个字节)组成,如下所示: 05 U 17 X 23 V 31 Y 47 Z ^ ^ 100 120 其中指针 X, Z 的值分别为多少?该线性表的首结点起始地址为多少?末结点的起始地址为多少? Y,

六、阅读分析题(10 分)
指出以下算法中的错误和低效(即费时)之处,并将它改写为一个既正确又高效的算法。 Status DeleteK(SqList&a, int i, int k){ //本过程从顺序存储结构的线性表 a 中删除第 i 个元素起的 k 个元素 if ( i<1 || k<0 || i+k> a.length ) return INFEASIBLE; //参数不合法 else{ for(count = 1; count <k; count ++ ) { //删除一个元素 for ( j = a.length; j>=i+1; j--) a.elem[j-1] = a.elem[j]; a.length - -; } return OK; } // DeleteK

注:上题涉及的类型定义如下: # define LIST INIT SIZE 100 # define LISTINCREMENT 10 typedef struct { Elem Type *elem; Int length; Int listsize; }SqList;

//存储空间基址 //当前长度 //当前分配的存储容量

7

七、编程题(每题 10 分,共 40 分)
1. 写出在顺序存储结构下将线性表逆转的算法,要求使用最少的附加空间。

2. 已知 L 是无表头结点的单链表,且 P 结点既不是首元结点,也不是尾元结点,请写出在 P 结点后插入 S 结点的核心语句序列。

3.编写程序,将若干整数从键盘输入,以单链表形式存储起来,然后计算单链表中结点的个数(其中指针 P 指向该链表的第一个结点) 。

4. 请编写 26 个字母按特定字母值插入或删除的完整程序, 可自行选用顺序存储或链表结构。

附:第一次上机安排
内容 线性表的插入与 删除 要求 用链表存储方式制作福利彩票(36 选 7)和体育彩票(10 选 7) 的选号器。 时间 第 4 周二晚 6:30-9:50

两点说明: 1. 福利彩票(36 选 7)的 7 个号不能重复,而体育彩票(10 选 7)的 7 个号可以重复; 2. 建议用首尾相连的链式结构,这样可以更逼真地模拟“摇奖”过程;而每个号的“摇动”次数可用随 机数来确定。 3. 怎样产生随机数?可以利用 C 语言中的种子函数 srand()和伪随机函数 rand( )来实现。 ① 首先,给 srand(m )提供一个“种子”m,它的取值范围是从 0~65535。 ② 然后,调用 rand( ),是伪随机数,它会根据提供给 srand()的“种子”值返回一个随机数(在 0~ 32767 之间) 。 ③ 根据需要多次调用 rand(),从而不断地得到新的随机数。 ④ 无论何时,你都可以给 srand()提供一个新的“种子” ,从而进一步“随机化”rand()的输出结果。 例如,取 m=17,则执行了 srand(17)之后,再执行 rand( )函数,将得到输出值 94;第二次调用 rand(), 会得到 26,??反复调用 rand()就能产生一系列的随机数。 注意:若 m 不变,则 rand()的输出系列也不变,总是 94,26,602,??等等。所以,建议摇号的“种子” 选为当前日期或时间,以保证每天的摇号值都不相同。

8

第 3 章栈和队列自测卷姓名班级
题号 题分 得分 一 15 二 10 三 20 四 20 五 20 六 15 总分 100

一、填空题(每空 1 分,共 15 分)
1. 向量、栈和队列都是结构,可以在向量的位置插入和删除元素;对于栈只能在插入和删除元素;对于 队列只能在插入和删除元素。 2. 栈是一种特殊的线性表,允许插入和删除运算的一端称为。不允许插入和删除运算的一端称为。 3. 是被限定为只能在表的一端进行插入运算,在表的另一端进行删除运算的线性表。 4. 在一个循环队列中,队首指针指向队首元素的位置。 5. 在具有 n 个单元的循环队列中,队满时共有个元素。 6. 向栈中压入元素的操作是先,后。 7. 从循环队列中删除一个元素时,其操作是先,后。 8. 带表头结点的空循环双向链表的长度等于。

二、判断正误(判断下列概念的正确性,并作出简要的说明。(每小题 1 分,共 10 分) )
()1.线性表的每个结点只能是一个简单类型,而链表的每个结点可以是一个复杂类型。 ()2.在表结构中最常用的是线性表,栈和队列不太常用。 ()3. 栈是一种对所有插入、删除操作限于在表的一端进行的线性表,是一种后进先出型结构。 ()4.对于不同的使用者,一个表结构既可以是栈,也可以是队列,也可以是线性表。 ()5.栈和链表是两种不同的数据结构。 ()6.栈和队列是一种非线性数据结构。 ()7. 栈和队列的存储方式既可是顺序方式,也可是链接方式。 ()8. 两个栈共享一片连续内存空间时,为提高内存利用率,减少溢出机会,应把两个栈的栈底分别设 在这片内存空间的两端。 ()9. 队是一种插入与删除操作分别在表的两端进行的线性表,是一种先进后出型结构。 ()10. 一个栈的输入序列是 12345,则栈的输出序列不可能是 12345。

三、单项选择题(每小题 1 分,共 20 分)
()1.栈中元素的进出原则是 A.先进先出B.后进先出C.栈空则进D.栈满则出

9

()2.若已知一个栈的入栈序列是 1,2,3,?,n,其输出序列为 p1,p2,p3,?,pn,若 p1=n,则 pi 为 A.iB.n=iC.n-i+1D.不确定 ()3.判定一个栈 ST(最多元素为 m0)为空的条件是 A.ST->top<>0B.ST->top=0C.ST->top<>m0D.ST->top=m0 ()4.判定一个队列 QU(最多元素为 m0)为满队列的条件是 A.QU->rear - QU->front = = m0B.QU->rear - QU->front -1= = m0 C.QU->front = = QU->rearD.QU->front = = QU->rear+1 ()5.数组Q[n]用来表示一个循环队列,f为当前队列头元素的前一位置,r为队尾元素的位置, 假定队列中元素的个数小于n,计算队列中元素的公式为 (A)r-f;(B) (n+f-r)%n; (C)n+r-f;(D) (n+r-f)%n 6. 设有 4 个数据元素 a1、a2、a3 和 a4, 对他们分别进行栈操作或队操作。 在进栈或进队操作时, a1、 按 a2、a3、a4 次序每次进入一个元素。假设栈或队的初始状态都是空。 现要进行的栈操作是进栈两次,出栈一次,再进栈两次,出栈一次;这时,第一次出栈得到的元素是 A , 第二次出栈得到的元素是 B ; 类似地, 考虑对这四个数据元素进行的队操作是进队两次, 出队一次,再进队两次,出队一次;这时,第一次出队得到的元素是 C ,第二次出队得到的元素 是 D 。经操作后,最后在栈中或队中的元素还有 E 个。 供选择的答案: A~D:①a1②a2③a3④a4E:①1 ②2 ③3 ④0 答:A、B、C、D、E 分别为、、 、、 7. 栈是一种线性表,它的特点是 A 。设用一维数组 A[1,…,n]来表示一个栈,A[n]为栈底,用整型变 量 T 指示当前栈顶位置,A[T]为栈顶元素。往栈中推入(PUSH)一个新元素时,变量 T 的值 B ;从 栈中弹出(POP)一个元素时,变量 T 的值 C 。设栈空时,有输入序列 a,b,c,经过 PUSH,POP, PUSH,PUSH,POP 操作后,从栈中弹出的元素的序列是 D ,变量 T 的值是 E 。

供选择的答案:
A:①先进先出②后进先出 ③进优于出 ④出优于进⑤随机进出 B,C: ①加 1 ②减 1 ③不变 ④清 0 ⑤加 2 D:①a,b②b,c ③c,a ④b,a ⑤ c,b ⑥ a,c E:① n+1 ②n+2 ③ n ④ n-1 ⑤ n-2 答:A、B、C、D、E 分别为、、 、、 8. 在做进栈运算时,应先判别栈是否 A ;在做退栈运算时,应先判别栈是否 B 。当栈中元素为 n 个,做进栈运算时发生上溢,则说明该栈的最大容量为 C 。 为了增加内存空间的利用率和减少溢出的可能性,由两个栈共享一片连续的内存空间时,应将两栈的 D 分别设在这片内存空间的两端,这样,只有当 E 时,才产生上溢。 ⑥减 2

供选择的答案:
A,B:①空②满③上溢④下溢 C: ①n-1②n③n+1④n/2 D:①长度②深度③栈顶④栈底 E:①两个栈的栈顶同时到达栈空间的中心点②其中一个栈的栈顶到达栈空间的中心点 ③两个栈的栈顶在达栈空间的某一位置相遇④两个栈均不空,且一个栈的栈顶到达另一个栈的栈底 答:A、B、C、D、E 分别为、、 、、

四、简答题(每小题 4 分,共 20 分)
1. 说明线性表、栈与队的异同点。

10

2. 设有编号为 1,2,3,4 的四辆列车,顺序进入一个栈式结构的车站,具体写出这四辆列车开出车站 的所有可能的顺序。

3. 假设正读和反读都相同的字符序列为 “回文” 例如, , ‘abba’ ‘abcba’ 和 是回文, ‘abcde’ ‘ababab’ 和 则不是回文。假设一字符序列已存入计算机,请分析用线性表、堆栈和队列等方式正确输出其回文的可能 性?

4. 顺序队的“假溢出”是怎样产生的?如何知道循环队列是空还是满?

5. 设循环队列的容量为 40(序号从 0 到 39) ,现经过一系列的入队和出队运算后,有 ① front=11,rear=19; ② front=19,rear=11;问在这两种情况下,循环队列中各有元素多少个?

五、阅读理解(每小题 5 分,共 20 分)
1. 按照四则运算加、减、乘、除和幂运算(↑)优先关系的惯例,并仿照教材例 3-2 的格式,画出对下 列算术表达式求值时操作数栈和运算符栈的变化过程: A-B×C/D+E↑F

2. 写出下列程序段的输出结果(栈的元素类型 SElem Type 为 char) 。 void main( ){ Pop(S,x); Push(S,’t’); Push(S,x); Stack S; Pop(S,x); Push(S,’s’); Char x,y; while(!StackEmpty(S)){ Pop(S,y);printf(y); }; InitStack(S); Printf(x); X=’c’;y=’k’; } Push(S,x); Push(S,’a’); Push(S,y); 3. 写出下列程序段的输出结果 (队列中 QElem Type 为 char) 。 void main( ){ Queue Q; Init Queue (Q); Char x=’e’; y=’c’; EnQueue (Q,’h’); EnQueue (Q,’r’); EnQueue (Q,’y’); DeQueue (Q,x); EnQueue (Q,x); DeQueue (Q,x); EnQueue (Q,’a’); while(!QueueEmpty(Q)){ DeQueue (Q,y);printf(y); }; Printf(x);

的元素类型

11

} 4. 简述以下算法的功能(栈和队列的元素类型均为 int) 。 void algo3(Queue &Q){ Stack S; int d; InitStack(S); while(!QueueEmpty(Q)){ DeQueue (Q,d); Push(S,d); }; while(!StackEmpty(S)){ Pop(S,d); EnQueue (Q,d); } }

六、算法设计(每小题 5 分,共 15 分。至少要写出思路)
1. 假设一个算术表达式中包含圆括弧、方括弧和花括弧三种类型的括弧,编写一个判别表达式中括弧是 否正确配对的函数 correct(exp,tag);其中:exp 为字符串类型的变量(可理解为每个字符占用一个数 组元素) ,表示被判别的表达式,tag 为布尔型变量。

2. 假设一个数组 squ[m]存放循环队列的元素。若要使这 m 个分量都得到利用,则需另一个标志 tag,以 tag 为 0 或 1 来区分尾指针和头指针值相同时队列的状态是“空”还是“满” 。试编写相应的入队和出队的 算法。

3.试写一个算法,判别读入的一个以‘@’为结束符的字符序列是否是“回文” 。

第 4~5 章串和数组自测卷姓名班级
题号 题分 得分 一 20 二 15 三 20 四 15 五 30 总分 100

一、填空题(每空 1 分,共 20 分) 1. 称为空串;称为空白串。

12

2. 设 S=“A;/document/Mary.doc” ,则 strlen(s)=, “/”的字符定位的位置为。 4. 子串的定位运算称为串的模式匹配;称为目标串,称为模式。 5. 设目标 T=”abccdcdccbaa”,模式 P=“cdcc” ,则第次匹配成功。 6. 若 n 为主串长,m 为子串长,则串的古典匹配算法最坏的情况下需要比较字符的总次数为。 7. 假设有二维数组 A6×8,每个元素用相邻的 6 个字节存储,存储器按字节编址。已知 A 的起始存储位置 (基地址)为 1000,则数组 A 的体积(存储量)为;末尾元素 A57 的第一个字节地址为;若按行存储时, 元素 A14 的第一个字节地址为;若按列存储时,元素 A47 的第一个字节地址为。 8.设数组 a[1?60, 1?70]的基地址为 2048,每个元素占 2 个存储单元,若以列序为主序顺序存储,则元素 a[32,58]的存储地址为。 9. 三元素组表中的每个结点对应于稀疏矩阵的一个非零元素,它包含有三个数据项,分别表示该元素 的、和。 10.求下列广义表操作的结果: (1)GetHead【((a,b),(c,d))】===; (2)GetHead【GetTail【((a,b),(c,d))】 】===; (3)GetHead【GetTail【GetHead【((a,b),(c,d))】】===; 】 (4)GetTail【GetHead【GetTail【((a,b),(c,d))】】===; 】 二、单选题(每小题 1 分,共 15 分) ()1.串是一种特殊的线性表,其特殊性体现在: A.可以顺序存储B.数据元素是一个字符 C.可以链式存储D.数据元素可以是多个字符 ()2.设有两个串 p 和 q,求 q 在 p 中首次出现的位置的运算称作: A.连接B.模式匹配C.求子串D.求串长 ()3.设串 s1=’ABCDEFG’,s2=’PQRST’,函数 con(x,y)返回 x 和 y 串的连接串,subs(s,i,j)返回串 s 的从 序号 i 开始的 j 个字符组成的子串,len(s)返回串 s 的长度,则 con(subs(s1,2,len(s2)),subs(s1,len(s2),2))的结 果串是: A.BCDEF B.BCDEFG C.BCPQRST D.BCDEFEF ()4.假设有 60 行 70 列的二维数组 a[1?60, 1?70]以列序为主序顺序存储,其基地址为 10000,每个元 素占 2 个存储单元,那么第 32 行第 58 列的元素 a[32,58]的存储地址为。 (无第 0 行第 0 列元素) A.16902 B.16904 C.14454 D.答案 A, B, C 均不对 ( )5. 设矩阵 A 是一个对称矩阵,为了节省存储,将其下三角部分(如 右图所示) 按行序存放在一维数组 B[ 1, n(n-1)/2 ]中, 对下三角部分中任一 元素 ai,j(i≤j),在一维数组 B 中下标 k 的值是: A.i(i-1)/2+j-1B.i(i-1)/2+j C.i(i+1)/2+j-1D.i(i+1)/2+j

?a1,1 ? a2,1 A? ? ?? ? ?an ,1 ?

a2 , 2 an , 2

? ? ? ? ? ? a n ,n ? ?

6. 从供选择的答案中,选出应填入下面叙述?内的最确切的解答,把相应编号写在答卷的对应栏内。
有一个二维数组 A,行下标的范围是 0 到 8,列下标的范围是 1 到 5,每个数组元素用相邻的 4 个字 节存储。存储器按字节编址。假设存储数组元素 A[0,1]的第一个字节的地址是 0。

13

存储数组 A 的最后一个元素的第一个字节的地址是 A 。若按行存储,则 A[3,5]和 A[5,3]的第一个字 节的地址分别是 B 和 C 。若按列存储,则 A[7,1]和 A[2,4]的第一个字节的地址分别是 D 和 E 。 供选择的答案 A~E:①28 ② 44 ③ 76 ④ 92 ⑤ 108⑥ 116 ⑦ 132 ⑧ 176 ⑨ 184 ⑩ 188 答案:A= B= C= D= E= 7. 从供选择的答案中,选出应填入下面叙述?内的最确切的解答,把相应编号写在答卷的对应栏内。 有一个二维数组 A,行下标的范围是 1 到 6,列下标的范围是 0 到 7,每个数组元素用相邻的 6 个字 节存储,存储器按字节编址。那么,这个数组的体积是 A 个字节。假设存储数组元素 A[1,0]的第一 个字节的地址是 0, 则存储数组 A 的最后一个元素的第一个字节的地址是 B 。 若按行存储, A[2,4] 则 的第一个字节的地址是 C 。若按列存储,则 A[5,7]的第一个字节的地址是 D 。 供选择的答案 A~D:①12 ②66 ③72 ④96 ⑤114 ⑥120⑦156 ⑧234 ⑨276 ⑩282 (11)283 (12)288 答案:A= B= C= D= E=

三、简答题(每小题 5 分,共 15 分)
1. KMP 算法的设计思想是什么?它有什么优点?

2. 已知二维数组 Am,m 采用按行优先顺序存放,每个元素占 K 个存储单元,并且第一个元素的存储地址 为 Loc(a11),请写出求 Loc(aij)的计算公式。如果采用列优先顺序存放呢?

3.递归算法比非递归算法花费更多的时间,对吗?为什么?

14

四、计算题(每题 5 分,共 20 分) 1. 【严题集 4.3①】设 s=’I AM A STUDENT’, t=’GOOD’, q=’WORKER’, 求 Replace(s,’STUDENT’,q)和 Concat(SubString(s,6,2), Concat(t,SubString(s,7,8)))。

2. 【严题集 4.8②】已知主串 s=’ADBADABBAABADABBADADA’,模式串 pat=’ADABBADADA’。写出 模式串的 nextval 函数值,并由此画出 KMP 算法匹配的全过程。

3. 用三元组表表示下列稀疏矩阵:

?00000000 ? ?00000000 ? ?00000? 2? ? ? ?03000800 ?00009 0? ? ? ? ? ? 00000000 ?00000 0? ? ( 2) (1) ? ?00060000 ?00500 0? ? ? ? ? ? 00000000 ?00000 0? ? ? ?00000005 ?00003 0 ? ? ? ? ? ? ?20000000 ?

4. 下列各三元组表分别表示一个稀疏矩阵,试写出它们的稀疏矩阵。

?6 4 6 ? ?4 5 5 ? ?1 2 2 ? ?1 1 1 ? ? ? ? ? ?2 1 12? ?2 4 9? ? ? (1) ?3 1 3 ? ( 2) ? ? ?3 2 8 ? ?4 4 4 ? ?3 5 6 ? ? ? 5 3 6? ? ? ? ?4 3 7 ? ?6 1 16 ? ? ?
五、算法设计题(每题 10 分,共 30 分) 1. 【严题集 4.12③】编写一个实现串的置换操作 Replace(&S, T, V)的算法。

15

2. 【严题集 4.10③】写出将字符串反序的递推或递归算法,例如字符串为“abcsxw” ,反序为“wxscba”

3. 【严题集 5.18⑤】试设计一个算法,将数组 An 中的元素 A[0]至 A[n-1]循环右移 k 位,并要求只用一 个元素大小的附加存储,元素移动或交换次数为 O(n)

附加题:利用 C 的库函数 strlen,strcpy(或 strncpy)写一个算法 void StrDelete(char *S,int t,int m) ,删 除串 S 中从位置 i 开始的连续的 m 个字符。若 i≥strlen(S),则没有字符被删除;若 i+m≥strlen(S),则将 S 中从位置 i 开始直至末尾的字符均被删去。 提示:strlen 是求串长(length)函数:int strlen(char s); //求串的长度 strcpy 是串复制(copy)函数:char *strcpy(char to,char from);//该函数将串 from 复制到串 to 中,并且返回一个指向串 to 的开始处的指针。

第6章

树和二叉树 自测卷
一 10 二 15 三 11

姓名
四 20

班级
五 20 六 24 总分 100

题号 题分 得分

一、下面是有关二叉树的叙述,请判断正误(每小题 1 分,共 10 分)
( ( ( ( ( ( )1. 若二叉树用二叉链表作存贮结构,则在 n 个结点的二叉树链表中只有 n—1 个非空指针域。 )2.二叉树中每个结点的两棵子树的高度差等于 1。 )3.二叉树中每个结点的两棵子树是有序的。 )4.二叉树中每个结点有两棵非空子树或有两棵空子树。 )5.二叉树中每个结点的关键字值大于其左非空子树(若存在的话)所有结点的关键字值,且小于 其右非空子树(若存在的话)所有结点的关键字值。 k-1 )6.二叉树中所有结点个数是 2 -1,其中 k 是树的深度。

16

( ( ( (

)7.二叉树中所有结点,如果不存在非空左子树,则不存在非空右子树。 i )8.对于一棵非空二叉树,它的根结点作为第一层,则它的第 i 层上最多能有 2 -1 个结点。 )9.用二叉链表法(link-rlink)存储包含 n 个结点的二叉树,结点的 2n 个指针区域中有 n+1 个为 空指针。 )10. 具有 12 个结点的完全二叉树有 5 个度为 2 的结点。

二、填空(每空 1 分,共 15 分)
1. 由3个结点所构成的二叉树有种形态。 2. 一棵深度为 6 的满二叉树有个分支结点和个叶子。

3. 一棵具有257个结点的完全二叉树,它的深度为。 4. 设一棵完全二叉树有 700 个结点,则共有个叶子结点。

5. 设一棵完全二叉树具有 1000 个结点,则此完全二叉树有个叶子结点,有个度为 2 的结点,有个结点只 有非空左子树,有个结点只有非空右子树。 6. 【严题集 6.7③】 一棵含有 n 个结点的 k 叉树,可能达到的最大深度为,最小深度为。 7. 二叉树的基本组成部分是:根(N) 、左子树(L)和右子树(R) 。因而二叉树的遍历次序有六种。最 常用的是三种:前序法(即按 N L R 次序) ,后序法(即按次序)和中序法(也称对称序法,即按 L N R 次序) 。这三种方法相互之间有关联。若已知一棵二叉树的前序序列是 BEFCGDH,中序序列是 FEBGCHD,则 它的后序序列必是。 8.中序遍历的递归算法平均空间复杂度为。 9. 用 5 个权值{3, 2, 4, 5, 1}构造的哈夫曼(Huffman)树的带权路径长度是。

17

三、选择题(每小题 1 分,共 11 分)
( )1. 不含任何结点的空树。 (A)是一棵树; (C)是一棵树也是一棵二叉树; (B)是一棵二叉树; (D)既不是树也不是二叉树



)2.二叉树是非线性数据结构,所以。 (A)它不能用顺序存储结构存储; (B)它不能用链式存储结构存储; (C)顺序存储结构和链式存储结构都能存储; (D)顺序存储结构和链式存储结构都不能使

用 ( )3. 具有 n(n>0)个结点的完全二叉树的深度为。 (A) ?log2(n)?(B) ? log2(n)?(C) ? log2(n) ?+1(D) ?log2(n)+1? )4.把一棵树转换为二叉树后,这棵二叉树的形态是。 (A)唯一的 (B)有多种 (C)有多种,但根结点都没有左孩子 (D)有多种,但根结点都没有右孩子



5. 树是结点的有限集合,它 A 根结点,记为 T。其余的结点分成为 m(m≥0)个 B 的集合 T1, T2, ?, Tm, 每个集合又都是树, 此时结点 T 称为 Ti 的父结点, i 称为 T 的子结点 T (1≤i≤m) 。 一个结点的子结点个数为该结点的 C 。 供选择的答案 A: ①有 0 个或 1 个 ②有 0 个或多个 ③有且只有 1 个 ④有 1 个或 1 个以上 B: ①互不相交 ② 允许相交 ③ 允许叶结点相交 ④ 允许树枝结点相交 C: ①权 ② 维数 ③ 次数 ④ 序 答案:A= B= C= 6. 二叉树 A 。在完全的二叉树中,若一个结点没有 B ,则它必定是叶结点。每棵树都能惟一地 转换成与它对应的二叉树。 由树转换成的二叉树里, 一个结点 N 的左子女是 N 在原树里对应结点的 C , 而 N 的右子女是它在原树里对应结点的 D 。 供选择的答案 A: ①是特殊的树 ②不是树的特殊形式 ③是两棵树的总称 ④有是只有二个根结点的树形结构 B: ①左子结点 ② 右子结点 ③ 左子结点或者没有右子结点 ④ 兄弟 C~D: ①最左子结点 ② 最右子结点 ③ 最邻近的右兄弟 ④ 最邻近的左兄弟 ⑤ 最左的兄弟 ⑥ 最右的兄弟 答案:A= B= C= D=

四、简答题(每小题 4 分,共 20 分)
1. 【严题集 6.2①】一棵度为 2 的树与一棵二叉树有何区别?

18

2. 设如下图所示的二叉树 B 的存储结构为二叉链表, root 为根指针, 结点结构为:lchild,data,rchild) ( 。 其中 lchild, rchild 分别为指向左右孩子的指针, data 为字符型, root 为根指针,试回答下列问题: C 的结点类型定义如下: 1. 对下列二叉树 B,执行下列算法 traversal(root),试指出其输 struct node 出结果; {char data; struct node *lchild, rchild; 2. 假定二叉树 B 共有 n 个结点, 试分析算法 traversal(root)的时 }; 间复杂度。 (每问 4 分,两问共 8 分) A B 二叉树 B C E F D G C 算法如下: void traversal(struct node *root) {if (root) {printf(“%c”, root->data); traversal(root->lchild); printf(“%c”, root->data); traversal(root->rchild); } }

3.【类似严题集 6.27③】给定二叉树的两种遍历序列,分别是: 前序遍历序列:D,A,C,E,B,H,F,G,I; 中序遍历序列:D, C,B,E,H,A,G,I,F, 试画出二叉树 B, 并简述由任意二叉树 B 的前序遍历序列和中序遍历 序列求二叉树 B 的思想方法。

4. 给定如图所示二叉树 T,请画出与其对应的中序线索二叉树。 25 40 60 55

28 33 08 54

五、阅读分析题(每题 5 分,共 20 分)
1. 试写出如图所示的二叉树分别按先序、 中序、 后序遍历时得 到的结点序列。

2.

把如图所示的树转化成二叉树。

19

3.【严题集 6.17③】阅读下列算法,若有错,改正之。 BiTree InSucc(BiTree q){ //已知 q 是指向中序线索二叉树上某个结点的指针, //本函数返回指向*q 的后继的指针。 r=q->rchild; if(!r->rtag) while(!r->rtag)r=r->rchild; return r; }//ISucc

4.【严题集 6.21②】画出和下列二叉树相应的森林。

六、算法设计题(前 5 题中任选 2 题,第 6 题必做,每题 8 分,共 24 分)
1.【严题集 6.42③】编写递归算法,计算二叉树中叶子结点的数目。 2. 写出求二叉树深度的算法,先定义二叉树的抽象数据类型。 3. 【严题集 6.44④】编写递归算法,求二叉树中以元素值为 x 的结点为根的子树的深度。 4. 【严题集 6.47④】编写按层次顺序(同一层自左至右)遍历二叉树的算法。 5. 【严题集 6.49④】编写算法判别给定二叉树是否为完全二叉树。 6.【严题集 6.26③】 假设用于通信的电文仅由 8 个字母组成, 字母在电文中出现的频率分别为 0.07, 0.19, 0.02,0.06,0.32,0.03,0.21,0.10。试为这 8 个字母设计哈夫曼编码。使用 0~7 的二进制表示形式 是另一种编码方案。对于上述实例,比较两种方案的优缺点。

20

第 7 章图自测卷姓名班级
题号 题分 得分 一 16 二 20 三 24 四 10 五 30 总分 100

一、单选题(每题 1 分,共 16 分)
()1. 在一个图中,所有顶点的度数之和等于图的边数的倍。 A.1/2 B. 1 C. 2 D. 4

()2. 在一个有向图中,所有顶点的入度之和等于所有顶点的出度之和的倍。 A.1/2 B. 1 C. 2 D. 4 ()3. 有 8 个结点的无向图最多有条边。 A.14 B. 28 ()4. 有 8 个结点的无向连通图最少有条边。 A.5 B. 6 ()5. 有 8 个结点的有向完全图有条边。 A.14 B. 28 C. C. 56 7 C. 56 D. D. 8 D. 112 112

()6. 用邻接表表示图进行广度优先遍历时,通常是采用来实现算法的。 A.栈 B. 队列 C. 树 ()7. 用邻接表表示图进行深度优先遍历时,通常是采用来实现算法的。 A.栈 B. 队列 C. 树

D. 图 D. 图

()8. 已知图的邻接矩阵,根据算法思想,则从顶点 0 出发按深度优先遍历的结点序列是

?0 ?1 ? ?1 ? ?1 ?1 ? ?0 ?1 ?

1 1 1 1 0 1? 0 0 1 0 0 1? ? 0 0 0 1 0 0? ? 1 0 0 1 1 0? 0 1 1 0 1 0? ? 0 0 1 1 0 1? 1 0 0 0 1 0? ?

()9. 已知图的邻接矩阵同上题 8,根据算法,则从顶点 0 出发,按深度优先遍历的结点序列是 A. 0 2 4 3 1 5 6 B. 0 1 3 5 6 4 2 C. 0 4 2 3 1 6 5 D. 0 1 3 4 2 5 6 ()10.已知图的邻接矩阵同上题 8,根据算法,则从顶点 0 出发,按广度优先遍历的结点序列是 A. 0 2 4 3 6 5 1 B. 0 1 3 6 4 2 5 C. 0 4 2 3 1 5 6 D. 0 1 3 4 2 5 6 ()11. 已知图的邻接矩阵同上题 8,根据算法,则从顶点 0 出发,按广度优先遍历的结点序列是 A. 0 2 4 3 1 6 5 B. 0 1 3 5 6 4 2 C. 0 1 2 3 4 6 5 D. 0 1 2 3 4 5 6

21

()12. 已知图的邻接表如下所示,根据算法,则从顶点 0 出发按深度优先遍历的结点序列是 A.0 1 3 2 C. 0 3 2 1 B. 0 2 3 1 D. 0 1 2 3

()13. 已知图的邻接表如下所示,根据算法,则从顶点 0 出发按广度优先遍历的结点序列是 A.0 3 2 1 C. 0 1 3 2 B. 0 1 2 3 D. 0 3 1 2

()14. 深度优先遍历类似于二叉树的 A.先序遍历 B.中序遍历 ()15. 广度优先遍历类似于二叉树的 A.先序遍历 B.中序遍历 ()16. 任何一个无向连通图的最小生成树 A.只有一棵 B.一棵或多棵

C. 后序遍历 D. 层次遍历 C. 后序遍历 D. 层次遍历 C. 一定有多棵 D. 可能不存在

二、填空题(每空 1 分,共 20 分)
1. 图有、等存储结构,遍历图有、等方法。 2. 有向图 G 用邻接表矩阵存储,其第 i 行的所有元素之和等于顶点 i 的。 3. 如果 n 个顶点的图是一个环,则它有棵生成树。 4. n 个顶点 e 条边的图,若采用邻接矩阵存储,则空间复杂度为。 5. n 个顶点 e 条边的图,若采用邻接表存储,则空间复杂度为。 6. 设有一稀疏图 G,则 G 采用存储较省空间。 7. 设有一稠密图 G,则 G 采用存储较省空间。 8. 图的逆邻接表存储结构只适用于图。 9. 已知一个图的邻接矩阵表示,删除所有从第 i 个顶点出发的方法是。 10. 图的深度优先遍历序列惟一的。 11. n 个顶点 e 条边的图采用邻接矩阵存储,深度优先遍历算法的时间复杂度为;若采用邻接表存储时, 该算法的时间复杂度为。

22

12. n 个顶点 e 条边的图采用邻接矩阵存储,广度优先遍历算法的时间复杂度为;若采用邻接表存储,该 算法的时间复杂度为。 13. 图的 BFS 生成树的树高比 DFS 生成树的树高。 14. 用普里姆(Prim)算法求具有 n 个顶点 e 条边的图的最小生成树的时间复杂度为; 用克鲁斯卡尔(Kruskal) 算法的时间复杂度是。 15. 若要求一个稀疏图 G 的最小生成树,最好用算法来求解。 16. 若要求一个稠密图 G 的最小生成树,最好用算法来求解。 17. 用 Dijkstra 算法求某一顶点到其余各顶点间的最短路径是按路径长度的次序来得到最短路径的。 18. 拓扑排序算法是通过重复选择具有个前驱顶点的过程来完成的。

三、简答题(每题 6 分,共 24 分)
1. 【严题集 7.1①】已知如图所示的有向图,请给出该图的: (1) 每个顶点的入/出度; (2) 邻接矩阵; (3) 邻接表; (4) 逆邻接表。

2. 【严题集 7.7②】请对下图的无向带权图: (1) 写出它的邻接矩阵,并按普里姆算法求其最小生成树; (2) 写出它的邻接表,并按克鲁斯卡尔算法求其最小生成树。

3. 【严题集 7.5②】已知二维数组表示的图的邻接矩阵如下图所示。 试分别画出自顶点 1 出发进行遍历所得的深度优先生成树和广度优先生成树。

23

4. 【严题集 7.11②】试利用 Dijkstra 算法求图中从顶点 a 到其他各顶点
间的最短路径,写出执行算法过程中各步的状态。

四、给定下列网 G: (10 分)

1 试着找出网 G 的最小生成树,画出其逻辑结构图; 2 用两种不同的表示法画出网 G 的存储结构图; 3 用 C 语言(或其他算法语言)定义其中一种表示法(存储结构)的数据类型。

五、算法设计题(每题 10 分,共 30 分)
1. 【严题集 7.14③】编写算法,由依次输入的顶点数目、弧的数目、各顶点的信息和各条弧的信息建立 有向图的邻接表。 解:Status Build_AdjList(ALGraph &G) //输入有向图的顶点数,边数,顶点信息和边的信息,以建立邻接 表 {

return OK; }//Build_AdjList 2. 【严题集 7.15③】试在邻接矩阵存储结构上实现图的基本操作:DeleteArc(G,v,w),即删除一条边的操 作。 (如果要删除所有从第 i 个顶点出发的边呢?提示:将邻接矩阵的第 i 行全部置 0 ) 解://设本题中的图 G 为有向无权图 Status DeleteArc(MGraph &G, char v, char w) //在邻接矩阵表示的图 G 上删除边(v,w) {

24

} return OK; }//Delete_Arc

3. 【严题集 7.22③】试基于图的深度优先搜索策略写一算法,判别以邻接表方式存储的有向图中是否存 在由顶点 vi 到顶点 vj 的路径(i≠j) 。

附加题: 【严题集 7.27④】采用邻接表存储结构,编写一个判别无向图中任意给定的两个顶点之间是否存 在一条长度为 k 的简单路径的算法。 (注 1:一条路径为简单路径指的是其顶点序列中不含有重现的顶点。 注 2:此题可参见严题集 P207-208 中有关按“路径”遍历的算法基本框架。 )

第 8 章查找自测卷姓名班级
题号 题分 得分 一 10 二 27 三 16 四 24 五 23 总分 100

25

一、填空题(每空 1 分,共 10 分)
1.在数据的存放无规律而言的线性表中进行检索的最佳方法是。 2. 线性有序表(a1,a2,a3,?,a256)是从小到大排列的,对一个给定的值 k,用二分法检索表中与 k 相 等的元素,在查找不成功的情况下,最多需要检索次。设有 100 个结点,用二分法查找时,最大比较次数 是。 3. 假设在有序线性表 a[20]上进行折半查找,则比较一次查找成功的结点数为 1;比较两次查找成功的结 点数为;比较四次查找成功的结点数为;平均查找长度为。 4.折半查找有序表(4,6,12,20,28,38,50,70,88,100) ,若查找表中元素 20,它将依次与表中 元素比较大小。 5.在各种查找方法中,平均查找长度与结点个数 n 无关的查找方法是。 6. 散列法存储的基本思想是由决定数据的存储地址。 7. 有一个表长为 m 的散列表,初始状态为空,现将 n(n<m)个不同的关键码插入到散列表中,解决冲 突的方法是用线性探测法。如果这 n 个关键码的散列地址都相同,则探测的总次数是。

二、单项选择题(每小题 1 分,共 27 分)
()1.在表长为n的链表中进行线性查找,它的平均查找长度为 A. ASL=n;B. ASL=(n+1)/2; C. ASL= n +1;D. ASL≈log2(n+1)-1 ()2.折半查找有序表(4,6,10,12,20,30,50,70,88,100) 。若查找表中元素 58,则它将依次 与表中比较大小,查找结果是失败。 A.20,70,30,50 B.30,88,70,50 C.20,50 D.30,88,50 ()3.对 22 个记录的有序表作折半查找,当查找失败时,至少需要比较次关键字。 A.3 B.4 C.5 D. 6 ()4. 链表适用于查找 A.顺序 B.二分法 C.顺序,也能二分法 D.随机 ()5. 折半搜索与二叉搜索树的时间性能 A.相同 B. 完全不同 C. 有时不相同 D.数量级都是 O(log2n) 6. 要进行线性查找, 则线性表 A ; 要进行二分查找, 则线性表 B ; 要进行散列查找, 则线性表 C 。 某顺序存储的表格,其中有 90000 个元素,已按关键项的值的上升顺序排列。现假定对各个元素进行查找 的概率是相同的, 并且各个元素的关键项的值皆不相同。 当用顺序查找法查找时, 平均比较次数约为 D , 最大比较次数为 E 。 供选择的答案: A~C:①必须以顺序方式存储②必须以链表方式存储③必须以散列方式存储 ④既可以以顺序方式,也可以以链表方式存储 ⑤必须以顺序方式存储且数据元素已按值递增或递减的次序排好 ⑥必须以链表方式存储且数据元素已按值递增或递减的次序排好 D,E:① 25000 ② 30000 ③ 45000 ④ 90000 答案: A= B= C=D= E= 7. 数据结构反映了数据元素之间的结构关系。 链表是一种 A , 它对于数据元素的插入和删除 B 。 通常查找线性表数据元素的方法有 C 和 D 两种方法, 其中 C 是一种只适合于顺序存储结 构但 E 的方法;而 D 是一种对顺序和链式存储结构均适用的方法。 供选择的答案:

26

A:①顺序存储线性表②非顺序存储非线性表 ③顺序存储非线性表 ④非顺序存储线性表 B: ①不需要移动结点,不需改变结点指针②不需要移动结点,只需改变结点指针 ③只需移动结点,不需改变结点指针 ④既需移动结点,又需改变结点指针 C:①顺序查找②循环查找 ③条件查找 ④二分法查找 D:①顺序查找②随机查找 ③二分法查找 ④分块查找 E:①效率较低的线性查找②效率较低的非线性查找 ③效率较高的非线性查找④效率较高的线性查找 答案:A= B= C= D= E= 8. 在二叉排序树中,每个结点的关键码值 A , B 一棵二叉排序,即可得到排序序列。同一个结点集 合,可用不同的二叉排序树表示,人们把平均检索长度最短的二叉排序树称作最佳二叉排序,最佳二叉排 序树在结构上的特点是 C 。 供选择的答案 A:①比左子树所有结点的关键码值大,比右子树所有结点的关键码值小 ②比左子树所有结点的关键码值小,比右子树所有结点的关键码值大 ③比左右子树的所有结点的关键码值都大 ④与左子树所有结点的关键码值和右子树所有结点的关键码值无必然的大小关系 B: ①前序遍历②中序(对称)遍历③后序遍历④层次遍历 C:①除最下二层可以不满外,其余都是充满的②除最下一层可以不满外,其余都是充满的 ③每个结点的左右子树的高度之差的绝对值不大于 1 ④最下层的叶子必须在最左边 答案:A= B= C= 9. 散列法存储的基本思想是根据 A 来决定 B ,碰撞(冲突)指的是 C 方法是 D 。 供选择的答案 A,B:①存储地址②元素的符号③元素个数④关键码值 ⑤非码属性⑥平均检索长度⑦负载因子⑧散列表空间 C: ①两个元素具有相同序号②两个元素的关键码值不同,而非码属性相同 ③不同关键码值对应到相同的存储地址④负载因子过大⑤数据元素过多 D:①线性探查法和双散列函数法②建溢出区法和不建溢出区法 ③除余法和折叠法 ④拉链法和开地址法 答案:A= B= C= D= ,处理碰撞的两类主要

10.考虑具有如下性质的二叉树:除叶子结点外,每个结点的值都大于其左子树上的一切结点的值。并小 于等于其右子树上的一切结点的值。 现把 9 个数 1,2,3,?,8,9 填入下图所示的二叉树的 9 个结点中,并使之具有上述性质。此时, n1 的值是 A ,n2 的值是 B ,n9 的值是 C 。现欲把 10 放入此树并使该树保持前述性质,增 加的一个结点可以放在 D 或 E 。 供选择的答案 A~C:①1 ② 2 ③ 3 ④4 ⑤ 5 ⑥ 6 ⑦ 7 ⑧ 8 ⑨ 9 D~E:① n7 下面② n8 下面③ n9 下面 ④ n6 下面⑤ n1 与 n2 之间⑥ n2 与 n4 之间 ⑦ n6 与 n9 之间⑧ n3 与 n6 之间 答案:A= B= C= D= E=

27

三、简答题(每小题 4 分,共 16 分)
1.对分 (折半) 查找适不适合链表结构的序列, 为什么?用二分查找的查找速度必然比线性查找的速度快, 这种说法对吗?

2.假定对有序表: (3,4,5,7,24,30,42,54,63,72,87,95)进行折半查找,试回答下列问题: (1) 画出描述折半查找过程的判定树; (2) 若查找元素 54,需依次与哪些元素比较? (3) 若查找元素 90,需依次与哪些元素比较? (4) 假定每个元素的查找概率相等,求查找成功时的平均查找长度。

3. 用比较两个元素大小的方法在一个给定的序列中查找某个元素的时间复杂度下限是什么? 如果要求时 间复杂度更小,你采用什么方法?此方法的时间复杂度是多少?

4.设哈希(Hash)表的地址范围为 0~17,哈希函数为:H(K)=K MOD 16。 K 为关键字,用线性探测法再散列法处理冲突,输入关键字序列: (10,24,32,17,31,30,46,47,40,63,49) 造出 Hash 表,试回答下列问题: (1) 画出哈希表的示意图; (2) 若查找关键字 63,需要依次与哪些关键字进行比较? (3) 若查找关键字 60,需要依次与哪些关键字比较? (4) 假定每个关键字的查找概率相等,求查找成功时的平均查找长度。

28

四、分析题(每小题 6 分,共 24 分)
1. 【严题集 9.3②】画出对长度为 10 的有序表进行折半查找的判定树,并求其等概率时查找成功的平均 查找长度。

2. 在一棵空的二叉查找树中依次插入关键字序列为 12,7,17,11,16,2,13,9,21,4,请画出所得 到的二叉查找树。

3. 【严题集 9.9③】已知如下所示长度为 12 的表: (Jan, Feb, Mar, Apr, May, June, July, Aug, Sep, Oct, Nov, Dec) (1) 试按表中元素的顺序依次插入一棵初始为空的二叉排序树,画出插入完成之后的二叉排序树,并求其 在等概率的情况下查找成功的平均查找长度。 (2) 若对表中元素先进行排序构成有序表,求在等概率的情况下对此有序表进行折半查找时查找成功的平 均查找长度。 (3) 按表中元素顺序构造一棵平衡二叉排序树,并求其在等概率的情况下查找成功的平均查找长度。

4. 选取散列函数 H(key)=(3*key)%11,用线性探测法处理冲突,对下列关键码序列构造一个散列 地址空间为 0~10,表长为 11 的散列表,{22,41,53,08,46,30,01,31,66}。

五、算法设计题(4 中选 3,第 1 题 7 分必选,其余每题 8 分,共 23 分)
1. 已知 11 个元素的有序表为(05 13 19 21 37 56 64 75 80 88 92), 请写出折半查找的算
法程序,查找关键字为 key 的数据元素(建议上机调试)。 2. 【严题集 9.31④】试写一个判别给定二叉树是否为二叉排序树的算法,设此二叉树以二叉链表作存储 结构。且树中结点的关键字均不同。 3. 【严题集 9.22④】已知一个含有 1000 个记录的表,关键字为中国人姓氏的拼音,请给出此表的一个哈 希表设计方案,要求它在等概率情况下查找成功的平均查找长度不超过 3。 4. 【严题集 9.44④】已知某哈希表的装载因子小于 1,哈希函数 H(key)为关键字(标识符)的第一个字 母在字母表中的序号,处理冲突的方法为线性探测开放定址法。试编写一个按第一个字母的顺序输出 哈希表中所有关键字的算法。

29


相关文章:
《c语言数据结构》自测题试卷
《c语言数据结构》自测题试卷 隐藏>> 第一章概论自测题姓名班级题号 题分 得分 一 33 二 15 三 9 四 8 五 20 六 15 总分 100 一、填空题(每空 1 分...
数据结构C语言版期末考试试题(附带复习资料)
数据结构C语言版期末考试试题(附带复习资料)_文学_高等教育_教育专区。“数据结构”期末考试试题 一、单选题(每小题 2 分,共 12 分) 1.在一个单链表 HL 中...
数据结构C语言版期末考试试题(有答案)
数据结构C语言版期末考试试题(有答案)_其它_高等教育_教育专区。数据结构C语言...顺序,也能二分法 D.随机 D. 6 A.顺序 《数据结构与算法》复习题 一、选择...
《c语言数据结构》第一章概论 自测题答案
《c语言数据结构》第8章... 《c语言数据结构》第9章...1/2 相关文档推荐...第一章概论自测题答案姓名班级题号 题分 得分 一 33 二 15 三 9 四 8 ...
数据结构c语言版期末考试复习试题
数据结构c语言版期末考试复习试题_理学_高等教育_教育专区。《数据结构与算法》复习题一、选择题。 1.在数据结构中,从逻辑上可以把数据结构分为 C 。 A.动态结...
数据结构期中考试试题答案c语言版本
数据结构期中考试试题答案 一、 单选题(每小题 2 分,共 8 分) 1.在一个长度为 n 的线性表中顺序查找值为 x 的元素时, 查找成功时的平 均查找长度(即 ...
c语言版数据结构试题及答案
c语言数据结构试题及答案_其它考试_资格考试/认证_教育专区。新疆工程学院c语言数据结构试题数据结构习题一 1/8 习题一一、 单选题 1. 在一个带有附加表头结...
数据结构C语言版期末考试试题(有答案)
数据结构C语言版期末考试试题(有答案)_理学_高等教育_教育专区。心有多大,舞台...112 《数据结构与算法》复习题 一、选择题 1.在数据结构中 从逻辑上可以把...
《c语言数据结构》第7章 图 自测卷解答
《c语言数据结构》第7章 图 自测卷解答_理学_高等教育_教育专区。今日...《c语言数据结构》自测题... 《c语言数据结构》第一章... 《c语言数据结构...
数据结构习题集答案(C语言严版)
数据结构习题集答案(C语言严版)_工学_高等教育_教育专区 暂无评价|0人阅读|0次下载|举报文档数据结构习题集答案(C语言严版)_工学_高等教育_教育专区。1.1 ...
更多相关标签:
数据结构c语言版试卷 | 数据结构自测题 | 数据结构c语言版 | 数据结构c语言版答案 | c语言数据结构 | c语言数据结构与算法 | 数据结构c语言版视频 | 数据结构c语言版pdf |