第一章绪论
单项选择题
1．数据对象是指______。
A. 描述客观事物且由计算机处理的数值、字符等符号的总称
B. 数据的基本单位
C. 性质相同的数据元素的集合
D. 相互之间存在一种或多种特定关系的数据元素的集合2．在数据结构中，数据的基本单位是_________。
A. 数据项
B. 数据类型
C. 数据元素
D. 数据变量
3．数据结构中数据元素之间的逻辑关系被称为______。
A. 数据的存储结构
B. 数据的基本操作
C. 程序的算法
D. 数据的逻辑结构
4．在数据结构中，与所使用计算机无关的是数据的_______。
A. 存储结构
B. 逻辑和物理结构
C. 逻辑结构
D. 物理结构
5．在链式存储结构中，数据之间的关系是通过________体现的。
A. 数据在内存的相对位置
B. 指示数据元素的指针
C. 数据的存储地址
D. 指针6．在定义ADT时，除数据对象和数据关系外，还需说明_______。
A. 数据元素
B. 算法
C. 基本操作
D. 数据项
7．计算算法的时间复杂度是属于一种_______。
A. 事前统计的方法
B. 事前分析估算的方法
C. 事后统计的方法
D. 事后分析估算的方法8．在对算法的时间复杂度进行估计的时候，下列最佳的时间复杂度是_______。
A. n2
B. nlogn
C. n
D. logn
9．设使用某算法对n个元素进行处理，所需的时间是T(n)=100nlog2n+200n+2000，则该算法的渐近时间复杂度为_______。
A. O(1)
B. O(n)
C. O(200n)
D. O(nlog2n)
10．有如下递归函数fact(a)，其时间复杂度为_________。
int fact(int a)
{
if(n==0)
retrun 1;
else
return(n*fact(n-1));
}
A. O(n)
B. O(n2)
C. O(n3)
D. O(n4)
11．线性表若采用链式存储结构时，要求内存中可用存储单元的地址_______。
A. 必须是连续的
B. 部分地址必须是连续的
C. 一定是不连续的
D. 连续不连续都可以12．线性结构的顺序存储结构是一种①的存储结构，线性表的链式存储结构是一种②的存储结构。
A. 随机存取
B. 顺序存取
C. 索引存取
D. 散列存取
填空题
1．数据结构由数据的①、②和③三部分组成。2．程序包括两个内容：①和②。
3．数据结构在物理上可分为①存储结构和②存储结构。
4．数据的物理结构，指数据元素在①中的表示，也即②。
5．数据逻辑结构包括①、②和③三种类型，树形结构和图形结构合称为④。
6．我们把每种数据结构均视为抽象类型，它不但定义了数据的①方式，还给出了处理数据的②。
7．一个算法的时间复杂度是用该算法①的多少来度量的，一个算法的空间复杂度是用该算法在运行过程中所占用的②___ _的大小来度量的。
8．算法具有如下特点：①、可执行性、②、结果性、一般性。
9．对于某一类特定的问题，算法给出了解决问题的一系列操作，每一操作都有它的①的意义，并在②内计算出结果。
10．下面程序段的时间复杂度为。
i=1;
while(i<=n)
i=i*3;
1 2 3 4 5 6 7 8 9 10
C C
D C B C B D D A
11 12①12②
D A B
填空题
1. ①逻辑结构；②存储结构；③操作
2. ①数据结构；②算法
3. ①顺序；②链式
4.
①计算机；②存储结构。5. ①线性结构；②树形结构；③图形结构；④非线性结构 6. ①表示；②实现方法7. ①所消耗的时间；②存储空间8. ①有穷性；②确定性9. ①确切；
②有穷时间10. log3n
第二章线性表
单项选择题
1．链表不具有的特点是________。
A. 可随机访问任一元素
B. 插入和删除时不需要移动元素
C. 不必事先估计存储空间
D. 所需空间与线性表的长度正比
2．线性链表（动态）是通过方式表示元素之间的关系的。
A. 保存后继元素地址
B. 元素的存储顺序
C. 保存左、右孩子地址
D. 保存后继元素的数组下标
3．设顺序表的每个元素占8个存储单元。第1个单元的存储地址是100，则第6个元素占用的最后一个存储单元的地址为。
A. 139
B. 140
C. 147
D. 148
4．设顺序表的长度为n，并设从表中删除元素的概率相等。则在平均情况下，从表中删除一个元素需移动的元素个数是。
A. (n-1)/2
B. n/2
C. n(n-1)/2
D. n(n+1)/2
5．在线性链表存储结构下，插入操作算法。
A. 需要判断是否表满
B. 需要判断是否表空
C. 不需要判断表满
D. 需要判断是否表空和表满
6．一个长度为n（n>1）的单链表，已知有头和尾两个指针，则执行操作与链表的长度有关。
A. 删除单链表中的第一个元素
B. 删除单链表中的最后一个元素
C. 在单链表第一个元素前插入一个新元素
D. 在单链表最后一个元素后插入一个新元素
7．在一个单链表中，若删除p所指结点的后继结点，则执行。
A. p->next = p->next->next;
B. p->next = p->next;
C. p = p->next->next;
D. p = p->next; p->next = p->next->next;
8．在非空线性链表中由p所指的链结点后面插入一个由q所指的链结点的过程是依次执行动作。
A. q->link = p; p->link = q;
B. q->link = p->link; p->link = q;
C. q->link = p->link; p = q;
D. p->link = q; q->link = p;
9．将长度为n的单链表接在长度为m的单链表之后的算法时间复杂度为。A. O(n) B. O(1) C. O(m) D. O(m+n)
10．非空的循环单链表head 的尾结点（由p 所指向）满足__________。
A. p->next == NULL
B.p == NULL
C. p->next == head
D.p == head
11．在非空双向循环链表中由q所指的那个结点前插入一个p所指的链结点的动作对应的语句依次为：p->rlink=q; p->llink= q->llink; q->llink=p; 。（空白处为一条赋值语句）
A. q->rlink=p;
B. q->llink->rlink=p;
C. p->llink->rlink=p;
D. p->rlink->rlink=p; 12．在双向循环链表中，在p所指的结点之后插入指针f所指的结点，其操作是__________。
A. p->rlink=f; f->rlink=p; (p->rlink)->llink=f; f->rlink=p->rlink;
B. p->rlink=f; (p->rlink)->llink=f; f->rlink=p; f->rlink=p->rlink;
C. f->rlink=p; f->rlink=p->rlink; p->rlink=f; (p->rlink)->llink=f;
D. f->rlink=p; f->rlink=p->rlink; (p->rlink)->llink=f; p->rlink=f;
13．需要预分较大空间，插入和删除不需要移动元素的线性表，其存储结构是。
A. 单链表
B. 静态链表
C. 线性链表
D. 顺序存储方式
14．若某链表最常用的操作是在最后一个结点之后插入一个元素和删除最后一个元素，则采用存储方式最节省运算时间。
A. 单链表
B. 双链表
C.单循环链表
D. 带头结点的双循环链表
15．若线性表最常用的操作是存取第i个元素及其前趋和后继元素的值，为节省时间应采用的存储方式是。
A. 单链表
B. 双向链表
C. 单循环链表
D. 顺序表
填空题
1．单链表中设置头结点的作用是。
2．在带表头结点的单链表中，当删除某一指定结点时，必须找到该结点的_____结点。3．在双链表中，每个结点有两个指针域，一个指向①，另一个指向②。4．带头结点的单链表L为空的判定条件是①，不带头结点的单链表L为空的判定条件是②。
5．在单链表中，指针p所指结点为最后一个结点的条件是。
6．带头结点的双向循环链表L为空表的条件是___________。
7．将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是。8．对一个长度为n的线性表，要删除第i个元素，则在顺序表示的情况下，计算复杂性为①，在链式表示的情况下，计算复杂性为②。
9．在一个长度为n的顺序表中第i个元素（1≤i≤n）之前插入一个元素时，需向后移动元素的个数是。
10．在长度为n的顺序表中插入一个元素的时间复杂度为。
1 2 3 4 5 6 7 8 9 10
A A C A C
B A
C B D
11 12 13 14 15
C D B D D
填空题
1. 简化操作，减少边界条件的判断
2. 前驱
3.①前驱结点；②后续结点；
4. ① L->next == NULL；② L== NULL；
5. p->next == NULL
6. L->priou==L->next
7. 1
8. ①O(n)；
②O(1) 9. n-i+1 10. O(n)
第三栈和队列
单项选择题
1．在初始为空的堆栈中依次插入元素f，e，d，c，b，a以后，连续进行了三次删除操作，此时栈顶元素是。
A. ｃ
B.ｄ
C.ｂ
D. ｅ
2．若某堆栈的输入序列是1，2，3，...，n，输出序列的第一个元素为n，则第i个输出元素为。
A. i
B. n-i
C. n-i+1
D. 哪个元素无所谓
3．如果用单链表表示链式栈，则栈顶一般设在链表的_______位置。
A. 链头
B. 链尾
C. 链头或链尾均可
D. 以上三种都不对
4．在后缀表达式求值算法中，需要用个栈。
A. 0
B. 1
C. 2
D. 3
5．5个圆盘的Hanoi塔，次小圆盘移到位时的步骤是第步。
A. 16
B. 30
C. 31
D. 32
6．在表达式求值的算符优先算法中，从栈顶到栈底运算符栈中的运算符优先级是。
A. 从高到低
B. 从低到高
C. 无序
D. 无序、有序均可以
7．向一个栈顶指针为h的带头结点链栈中插入指针s所指的结点时，应执行。
A. h->next = s;
B. s->next = h;
C. s->next = h; h = h->next;
D. s->next = h->next; h->next=s;
8．一个栈的入栈序列是a，b，c，d，e，则栈的不可能的输出序列是。
A. edcba
B. decba
C. dceab
D. abcde
9．栈和队列的共同点是。
A. 都是先进后出
B. 都是先进先出
C. 只允许在端点处插入和删除元素
D. 没有共同点10．对于循环队列。
A. 无法判断队列是否为空
B. 无法判断队列是否为满
C. 队列不可能满
D. 以上说法都不是
11. 设环形队列中数组的下标范围是1～n，头尾指针分别是f和r，则其元素个数为。
A. r-f
B. r-f+1
C. (r-f+1) mod n
D. (r-f+n) mod n
12. 若用一个大小为6的数组来实现循环队列，且当前队尾指针rear和队头指针front的值分别为0和3。当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为。
A. 1和5
B. 2和4
C. 4和2
D. 5和1
13. 判定一个循环队列QU（最多元素为m0）为满队列的条件是。
A. QU->front==QU->rear
B. QU->front!=QU->rear
C. QU->front==(QU->rear+1) % m0
D. QU->front!=(QU->rear+1) % m0
14. 判定一个队列QU（最多元素为m0）为空的条件是。
A. QU->rear-QU->front==m0
B. QU->rear-QU->front-1==m0
C. QU->front==QU->rear
D. QU->front==QU->rear+1
15. 判定一个队列QU（最多元素为m0）为满队列的条件是。
A. QU->rear-QU->front==m0
B. QU->rear-QU->front-1==m0
C. QU->front==QU->rear
D. QU->front==QU->rear+1
16.判定一个循环队列QU（最多元素为m0）为空的条件是。
A. QU->front==QU->rear
B. QU->front!=QU->rear
C. QU->front==(QU->rear+1) % m0
D. QU->front!=(QU->rear+1) % m0
填空题
1．在求表达式值的算符优先算法中使用的主要数据结构是。
2．设有一个顺序栈S，元素s1，s2，s3，s4，s5，s6依次进栈，如果6个元素的出栈顺序为s2，s3，s4，s6，s5，s1，则顺序栈的容量至少为。
3．设有一个空栈，现输入序列为1，2，3，4，5。经过push，push，pop，push，pop，push，pop，push后，输出序列是。
4．在按算符优先法求解表达式3-1+5*2时，最先执行的运算是①，最后执行的运算是____②____。
5．在栈的ADT定义中，除初始化操作外，其他基本操作的初始条件都要求。6．仅允许在同一端进行插入和删除的线性表称为。
7．在顺序栈s中，栈为空的条件是①，栈为满的条件是____ ②____。8．设有算术表达式x+a*(y-b)-c/d，该表达式的前缀表示为①。后缀表示为___②___。
9．用S表示入栈操作，X表示出栈操作，若元素入栈顺序为1234，为了得到1342出栈顺序，相应的S、X操作串为。
10．用一个大小为1000的数组来实现循环队列，当前rear和front的值分别为0和994，若要达到队满的条件，还需要继续入队的元素个数是。
1 2 3 4 5 6 7 8 9 10
B C A B B A D C C D
11 12 13 14 15 16
C A C C A A
填空题
1. 栈;
2. 3 ;
3. 2 3 4;
4. ① *；② -
5. 栈存在;
6. 栈
7. ① s.top == s.base；② s.top-s.base >= s.stacksize 8. ① -+x*a-yb/cd；② xayb-*+cd/- 9. SXSSXSXX 10. 993
第四章串
单项选择题
1．串的连接运算不满足。
A. 分配律
B. 交换律
C. 结合律
D. 都不满足
2．串是一种特殊的线性表，其特殊性体现在。
A. 可以顺序存储
B. 数据元素是一个字符
C. 可以链接存储
D. 数据元素可以是多个字符3．设有两个串p和q，求q在p中首次出现的位置的运算称作。
A. 连接
B. 模式匹配
C. 求子串
D. 求串长
4．串是一个的序列。
A. 不少于一个字母
B. 有限个字符
C. 不少于一个字符
D. 空格或字母
5．已知串s=?ABCDEFGH?，则s的所有不同子串的个数为。
A. 8
B. 9
C. 36
D. 37
6. 设串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
填空题
1．两个串相等的充分必要条件是。
2．空格串是①,其长度等于②。3．模式串…abaabade?的next函数值为。
4．在串S=?tuition?中，以t为首字符且值不相同的子串有个。
5. 使用“求子串”substring(S,pos,len)和“联接”concat(S1,S2)的串操作，可从串s=?conduction?中的字符得到串t=?cont?，则求t的串表达式为。
6. 已知字符串p=?abcabcabbac?，则next(3)和next(6)分别为①、②。
7.设对主串?bcdbcddabcdbcdbac?和模式串?bcdbcdb?进行KMP模式匹配。第1趟匹配失败后，若使用非改进的Next函数，则下一趟匹配将由主串的第①个字符与模式串的第__②___字符开始比较。若采用改进的Next函数，则下一趟匹配将由主串的第③个字符与模式串的第___④__字符开始比较。字符串中字符从1开始编号。
1 2 3 4 5 6
B B B B D D
填空题
1. 两个串的长度相等且对应位置的字符相同
2. ①由一个或多个空格字符组成的串②其包含的空格个数
3. 01122341
4. 10
5. concat(subString(s,1,3),substring(s,7,1))
6. ① 1；② 3
7. ① 7；② 4；③ 7；④ 1
第五章数组与广义表
单项选择题
1．在以下的叙述中，正确的是。
A. 线性表的线性存储结构优于链表存储结构
B. 二维数组是数据元素为线性表的线性表
C. 栈的操作方式是先进先出
D. 队列的操作方式是先进后出
2．常对数组进行的两种操作是。
A. 建立与删除
B. 索引和修改
C. 查找和修改
D. 查找与索引
3．在数组A中，每个数组元素A[i,j]占用3个存储字，行下标i从1到8，列下标j从1到10。所有数组元素相继存放在一个连续的存储空间，则存放该数组至少需要的存储字数是。
A. 80
B. 100
C. 240
D. 270
4．假设8行10列的二维数组a[1..8, 1..10]分别以行序为主序和以列序为主序顺序存储时，其首地址相同，那么以行序为主序时元素a[3][5]的地址与以列序为主序时元素_______的地址相同。
A. a[5][3]
B. a[8][3]
C. a[1][4]
D. 答案A、B、C均不对
5．如果只保存一个n阶对称矩阵a的下三角元素（含对角线元素），并采用行主序存储在一维数组b中，a[i][j]（或a[i,j]）存于b[k]，则对i A. B. C. D. 6．将一个A[1..100,1..100]的三对角矩阵以行序为主序存入一维数组B[1..298]中，元素A[66， 65]在B数组中的位置k等于_______。 A. 198 B. 197 C. 196 D. 195 7．稀疏矩阵一般的压缩存储方法有两种，即。 A. 二维数组和三维数组 B. 三元组和散列 C. 三元组和十字链表 D. 散列和十字链表 8. 一个非空广义表的表头_______。 A. 不可能是子表 B. 只能是子表 C. 只能是原子 D. 可以是原子或子表 9. 对广义表，通常采用的存储结构是______。 A. 数组 B. 链表 C. Hash表 D. 三元组 10. 一个三元组表用于表示一个_______。 A. 线性表 B. 广义表 C. 双向链表 D. 稀疏矩阵 11．广义表G=(a,b,(c,d,(e,f)),G)的长度是。 A. 3 B. 4 C. 7 D. ∞ 12. 设head(L)、tail(L)分别为取广义表表头、表尾操作，则从广义表L=((x,y,z),a,(u,v,w))中取出原子u的运算为_______。 A. head(tail(tail(head(L)))) B. tail(head(head(tail(L)))) C. head(tail(head(tail(L)))) D. head(head(tail(tail(L)))) 13. 若广义表A满足Head(A)=Tail(A)，则A为_______。 A. ( ) B. (( )) C. (( ) , ( )) D. (( ) , ( ) , ( )) 14. 设广义表上L=(a, (((f, g), e), (c, d)))，则表达式Tail(Head(Tail(L)))的值为______。 A. (d) B. (e) C. g D. e 15．广义表(a,((b,(c,d,(e,f))),g))的深度为_______。 A. 3 B. 4 C. 5 D. 6 填空题 1．将下三角矩阵A[1..8,1..8]的下三角部分逐行地存储到起始地址为1000的内存单元中，已知每个元素占四个单元，则元素A[7,5]的地址为。 2．二维数组A[0..9,0..19]采用列序为主方式存储，每个元素占一个存储单元，并且元素A[0,0]的存储地址是200，则元素A[6,12]的地址是。 3．二维数组A[10..20,5..10]采用行序为主方式存储，每个元素占4个存储单元，并且元素A[10,5]的存储地址是1000，则元素A[18,9]的地址是。 4．有一个10阶对称矩阵A，采用压缩存储方式（以行序为主序存储，且元素A[0,0]地址为1），则元素A[8,5]的地址是。 5．设n行n列的下三角矩阵A[0..n-1,0..n-1]已压缩到一维数组S[1..n*(n+1)/2]中，若按行序为主存储，则元素A[i,j]对应的S中的存储位置是。 6．广义表的深度定义为广义表中。 7．广义表((a)，((b)，c)，(((d))))的表头是①，表尾是②。 8．广义表((a)，((b)，c)，(((d))))的长度是①，深度是②。 9．Tail[Tail[Head[(((a, b), ((c))), (d), ((e, f)))]]]的运算结果是。其中“[]”是函数的符号。10．设HAED[p]为求广义表p的表头函数，TAIL[p]为求广义表p的表尾函数，其中[] 是函数的符号，给出下列广义表的运算结果： HEAD[(a，b，c)]的结果是①。 TAIL[(a，b，c)]的结果是②。 HEAD[((a)，(b))]的结果是③。 TAIL[((a)，(b))]的结果是④。 HEAD[TAIL[(a，b，c)]的结果是⑤。 TAIL[HEAD((a，b)，(c，d))]的结果是⑥。 HEAD[HEAD[(a，b)，(c，d))]]的结果是⑦。 TAIL[TAIL[(a，(c，d))]]的结果是⑧。 1 2 3 4 5 6 7 8 9 10 B C C D C D C D B D 11 12 13 14 15 B D B D C 填空题 1. 1100 2. 332 3. 1208 4. 42 5. i*(i+1)/2+j+1 6. 括弧的重数 7. ①(a)；②(((b)，c)，(((d)))) 8. ①3；②4 9. (e, f) 10. ①a；②(b，c)；③(a)；④((b))；⑤b；⑥(b)；⑦a；⑧( ) 第六章树和二叉树 选择题 1、以下说法错误的是。 A.树形结构的特点是一个结点可以有多个直接前趋 B.线性结构中的一个结点至多只有一个直接后继 C.树形结构可以表达(组织)更复杂的数据 D.树(及一切树形结构)是一种"分支层次"结构 2. 如下所示的4 棵二叉树中，不是完全二叉树。 3. 在线索化二叉树中，t 所指结点没有左子树的充要条件是。 A. t->left == NULL B. t->ltag==1 C. t->ltag==1 且t->left==NULL D .以上都不对 4. 以下说法错误的是。 A.二叉树可以是空集 B.二叉树的任一结点最多有两棵子树 C.二叉树不是一种树 D.二叉树中任一结点的两棵子树有次序之分 5. 以下说法错误的是。 A.完全二叉树上结点之间的父子关系可由它们编号之间的关系来表达 B.在三叉链表上，二叉树的求双亲运算很容易实现 C.在二叉链表上，求根，求左、右孩子等很容易实现 D.在二叉链表上，求双亲运算的时间性能很好 6. 如图6-3所示的4 棵二叉树，是平衡二叉树。 图6-3 4 棵二叉树 7. 如图6-4所示二叉树的中序遍历序列是。 A. abcdgef B. dfebagc C. dbaefcg D. defbagc 图6-4 1 棵二叉树 8. 已知某二叉树的后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是。 A. acbed B. decab C. deabc D. cedba 9. 如果T2 是由有序树T 转换而来的二叉树，那么T 中结点的前序就是T2 中结点的。 A. 前序 B.中序 C. 后序 D. 层次序 10. 某二叉树的前序遍历结点访问顺序是abdgcefh，中序遍历的结点访问顺序是dgbaechf，则其后序遍历的结点访问顺序是。 A. bdgcefha B. gdbecfha C. bdgaechf D. gdbehfca 11. 将含有83个结点的完全二叉树从根结点开始编号，根为1号，后面按从上到下、从左到右的顺序对结点编号，那么编号为41的双亲结点编号为。 A.42 B.40 C.21 D.20 12. 一棵二叉树如图6-5所示，其后序遍历的序列为。 A. abdgcefh B. dgbaechf C. gdbehfca D. abcdefgh 图6-5 1 棵二叉树 13. 深度为5 的二叉树至多有个结点。 A. 16 B. 32 C.31 D.10 14. 对一个满二叉树，m 个叶子，n 个结点，深度为h，则。 A. n=h+m B. h+m=2n C. m=h-1 D. n=2h-1 15. 如图6-6所示的二叉树是由有序树（森林）转换而来的，那么该有序树（森林）有个叶结点。 A. 4 B. 5 C. 6 D. 7 图6-6 1 棵二叉树 16. 设深度为k的二叉树上只有度为0和度为2的节点，则这类二叉树上所含结点总数最少个 A.k+1 B.2k C.2k-1 D.2k+1 17. 一棵二叉树满足下列条件：对任意结点，若存在左、右子树，则其值都小于它的左子树上所有结点的值，而大于右子树上所有结点的值。现采用遍历方式就可以得到这棵二叉树所有结点的递增序列。 A.先根 B.中根 C.后根 D.层次 18. 设森林T中有4棵树，第一、二、三、四棵树的结点个数分别是n1,n2,n3,n4,那么当把森林T转换成一棵二叉树后，且根结点的右子树上有个结点。 A.n1-1 B.n1 C.n1+n2+n3 D.n2+n3+n4 19. 森林T中有4棵树，第一、二、三、四棵树的结点个数分别是n1,n2,n3,n4,那么当把森林T转换成一棵二叉树后，且根结点的左孩子上有个结点。 A.n1-1 B.n1 C.n1+n2+n3 D.n2+n3+n4 20. 对含有个结点的非空二叉树，采用任何一种遍历方式，其结点访问序列均相同。 A.0 B.1 C.2 D.不存在这样的二叉树 填空题 1. 有一棵树如图6-7 所示，回答下面的问题： 图6-7 1 棵二叉树 （1）这棵树的根结点是①； （2）这棵树的叶子结点是②； （3）结点k3 的度是③； （4）这棵树的度为④； （5）这棵树的深度是⑤； （6）结点k3 的孩子是⑥； （7）结点k3 的双亲结点是⑦。 2. 深度为k 的完全二叉树至少有①个结点，至多有②个结点，若按自上而下，从左到右次序给结点编号（从1 开始），则编号最小的叶子结点的编号是③。 3. 一棵二叉树的第i（i≥1）层最多有①个结点；一棵有n（n>0）个结点的满二叉树共有②个叶子和③个非终端结点。 4. 结点最少的树为①，结点最少的二叉树为②。 5. 根据二叉树的定义，具有三个结点的二叉树有①种不同的形态，它们分别是②。 6. 具有n个结点的完全二叉树的深度为。 7. 已知一棵树如图6-8 所示，其孩子兄弟表示为。 图6-8 1棵二叉树 8. 以数据集{4，5，6，7，10，12，18}为结点权值所构造的哈夫曼树为①，其带权路径长度为②。 9. 哈夫曼树是带权路径度____①___的树，通常权值较大的结点离根___②____。 10．在________遍历二叉树的序列中，任何结点的子树上的所有结点，都是直接跟在该结点之后。 选择题 1 2 3 4 5 6 7 8 9 10 A C B C D B B D A D 11 12 13 14 15 16 17 18 19 20 D C C D C C B D A B 填空题 1.答：①k1 ②k2 k5 k7 k4 ③ 2 ④ 3 ⑤ 4 ⑥k5，k6 ⑦k1 2.答：①2②2-1 ③2+1 3.答：①2②③ 4.答：①只有一个结点的树②空的二叉树 5.答：① 5 ②如图6-10所示。 图6-10 5种二叉树 6.答：floor(log2n)+1 7.答：如图6-11所示 图6-11 1棵树的孩子兄弟表示 8.答：①如图6-5所示②165 图6-5 1棵哈夫曼树 9.答：①最短②较近 10．先根 第七章图 单项选择题 1．在一个图中，所有顶点的度数之和等于所有边数的倍。 A. 1/2 B. 1 C. 2 D. 4 2．在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的倍。 A. 1/2 B. 1 C. 2 D. 4 3．一个有n 个顶点的无向图最多有条边。 A. n B. n(n-1) C. n(n-1)/2 D. 2n 4．具有4 个顶点的无向完全图有条边。 A. 6 B. 12 C. 16 D. 20 5．具有6 个顶点的无向图至少应有条边才能确保是一个连通图。 A. 5 B. 6 C. 7 D. 8 6．在一个具有n 个顶点的无向图中，要连通全部顶点至少需要条边。 A. n B. n+1 C. n-1 D. n/2 7．对于一个具有n 个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是。 A. n B. (n-1)2 C. n-1 D. n2 8．对于一个具有n 个顶点和e 条边的无向图，若采用邻接表表示，则所有邻接表中的结点总数是。 A. e/2 B. e C. 2e D. n+e 9. 已知一个图如图7-1 所示，若从顶点a 出发按深度搜索法进行遍历，则可能得到的一种顶点序列为①；按宽度搜索法进行遍历，则可能得到的一种顶点序列为②。 图7-1 一个无向图 ① 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 ② A. a，b，c，e，d，f B. a，b，c，e，f，d C. a，e，b，c，f，d D. a，c，f，d，e，b 10．已知一有向图的邻接表存储结构如图7-2 所示。 （1）根据有向图的深度优先遍历算法，从顶点v1 出发，所得到的顶点序列是①。 A. v1，v2，v3，v5，v4 B. v1，v2，v3，v4，v5 C. v1，v3，v4，v5，v2 D. v1，v4，v3，v5，v2 （2）根据有向图的广度优先遍历算法，从顶点v1 出发，所得到的顶点序列是②。 A. v1，v2，v3，v4，v5 B. v1，v3，v2，v4，v5 C. v1，v2，v3，v5，v4 D. v1，v4，v3，v5，v2 图7-2一个有向图的邻接表存储结构 11．采用邻接表存储的图的深度优先遍历算法类似于二叉树的。 A. 先序遍历 B. 中序遍历 C. 后序遍历 D. 按层遍历 12．采用邻接表存储的图的广度优先遍历算法类似于二叉树的。 A. 先序遍历 B. 中序遍历 C. 后序遍历 D. 按层遍历 13. 判定一个有向图是否存在回路除了可以利用拓扑排序方法外，还可以利用。 A. 求关键路径的方法 B. 求最短路径的Dijkstra 方法 C. 广度优先遍历算法 D. 深度优先遍历算法 填空题 1．n 个顶点的连通图至少条边。 2．在无权图G的邻接矩阵A 中，若(vi，vj)或 3．在无向图G 的邻接矩阵A 中，若A[i][j]等于1，则A[j][i]等于。4．已知图G的邻接表如图7-3 所示，其从顶点v1 出发的深度优先搜索序列为①，其从顶点v1 出发的广度优先搜索序列为②。 图7-3 G的邻接表 5．设x,y是图G中的两顶点，则（x,y）与（y,x）被认为___①___边，但 6．已知一个图的邻接矩阵表示，删除所有从第i 个结点出发的边的方法是。7．在有向图的邻接矩阵上，由第i行可得到第___①___个结点的出度，而由第j列可得到第___ ②____个结点的入度。 8.在无向图中，如果从顶点v到顶点v?有路径，则称v和v?是___①___的。如果对于图中的任意两个顶点vi,vj∈V，且vi和vj都是连通的，则称G为__②____。 1 2 3 4 5 6 7 8 9①9② C B C A A C D C D B 10①10②11 12 13 C B A D D 填空题 1．答：n-1 2．答：①1 ②0 3．答：1 4. 答：①v1，v2，v3，v6，v5，v4 ②v1，v2，v5，v4，v3，v6 5. 答：①无向，②有向 6．答：将矩阵第i 行全部置为0 7．答：①i ②j 8.答：①连通，②连通图 第八章查找 单项选择题 1.顺序查找法适合于存储结构为的线性表。 A. 散列存储 B. 顺序存储或链接存储 C. 压缩存储 D. 索引存储 2.对线性表进行折半查找时，要求线性表的存储方式是。 A. 顺序存储 B. 链接存储 C. 以关键字有序排序的顺序存储 D. 以关键字有序排序的链接存储 3.顺序查找长度为n 的线性表时，每个元素的平均查找长度为。 A. n B. n/2 C. (n+1)/2 D. (n-1)/2 4.折半查找长度为n 的线性表时，每个元素的平均查找长度为。 A. O(n2) B. O(nlog2n) C. O(n) D. O(log2n) 5.对有18 个元素的有序表作二分（折半）查找，则查找A[3]的比较序列的下标为。 A. 1.2.3 B. 9.5.2.3 C. 9.5.3 D. 9.4.2.3 6.如果要求一个线性表既能较快地查找，又能适应动态变化的要求，可以采用查找方法。 A. 分块 B. 顺序 C. 二分 D. 散列 7.有一个有序表为{2，5，7，11，22，45，49，62，71，77，90，93，120}，当折半查找值为90 的结点时，经过次比较后查找成功。 A. 1 B. 2 C. 4 D. 8 8.设哈希表长m=14，哈希函数H(key)=key % 11。表中已有 4 个结点：addr(14)=3，addr(38)=5，addr(61)=6，addr(85)=8，其余地址为空，如用线性探测再散列处理冲突，关键字为49 的结点的地址是。 A. 7 B. 3 C. 5 D. 4 9.在采用链接法处理冲突的开散列表上，假定装填因子a 的值为4，则查找任一元素的平均查找长度为。 A. 3 B.3.5 C.4 D.2.5 10.具有5层结点的A VL树至少有个结点。 A. 10 B.12 C.15 D.17 11.有一个长度为12 的有序表，按二分查找法对该表进行查找，在表内各元素等概率情况下查找成功所需的平均比较次数为。 A. 35/12 B. 37/12 C. 39/12 D. 43/12 12.采用分块查找时，若线性表中共有2000个元素，查找每个元素的概率相同，假设采用顺序查找来确定结点所在的块时，每块应分个结点最佳。 A. 20 B. 30 C. 40 D. 45 填空题 1.顺序查找法的平均查找长度为①；哈希表查找法采用链接法处理冲突时的平均查找长度为②。 2.在各种查找方法中，平均查找长度与结点个数n 无关的查法方法是。 3.二分查找的存储结构仅限于。 4.长度为255 的表，采用分块查找法，每块的最佳长度是。 5.N个记录的有序顺序表中进行折半查找，最大的比较次数是___________。 6.对于长度为n 的线性表，若进行顺序查找，则时间复杂度为①；若采用二分法查找，则时间复杂度为②；若采用分块查找（假定总块数和每块长度均接近）， 则时间复杂度为③。 7.在散列存储中，装填因子α的值越大，则①；α的值越小，则②。 8.对于二叉排序树的查找，若根结点元素的键值大于被查元素的键值，则应该在二叉树的___________上继续查找。 9.高度为8的平衡二叉树至少有_______个结点。 10.在散列函数H(key)=key % p 中，p 应取。 1 2 3 4 5 6 7 8 9 10 11 12 B C C D D A C A A B B D 填空题 1.①(n+1)/2 ② 1+α(α为装填因子) 2.哈希表查找法 3.有序的顺序存储结构 4.15 5. log2N + 1 6.①O(n) ②O(log2n) ③O( n ) 7.①存取元素时发生冲突的可能性就越大②存取元素时发生冲突的可能性就越小 8.左子树 9.54 10.素数 第九章排序 单项选择题 1.在所有排序方法中，关键字比较的次数与记录的初始排列次序无关的是。 A. 希尔排序 B. 起泡排序 C. 插入排序 D. 选择排序 2.设有 10000 个无序的元素，希望用最快的速度挑选出其中前 10 个最大的元素，排序方法最好选用。 A. 起泡排序 B. 快速排序 C. 堆排序 D. 基数排序 3.在待排序的元素序列基本有序的前提下，效率最高的排序方法是。 A. 插入排序 B. 选择排序 C. 快速排序 D. 归并排序 4.一组记录的排序码为(46，79，56，38，40，84)，则利用堆排序的方法建立的初始堆为。 A. 79，46，56，38，40，80 B. 84，79，56，38，40，46 C. 84，79，56，46，40，38 D. 84，56，79，40，46，38 5.以下序列不是堆的是。 A．(100,85,98,77,80,60,82,40,20,10,66) B(100,98,85,82,80,77,66,60,40,20,10,) C．(10,20,40,60,66,77,80,82,85,98,100) D(100,85,40,77,80,60,66,98,82,10,20,) 6.在下列算法中，算法可能出现下列情况：在最后一趟开始之前，所有的元素都不在其最终的位置上。 A．堆排序 B．冒泡排序 C．插入排序 D.快速排序 7.一组记录的关键码为(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 8.一组记录的排序码为(48，16， 79，35，82，23，36，72)，按归并排序的方法对该序列进行一趟归并后的结果为。 A. 16 48 35 79 23 82 36 72 B. 16 35 48 79 82 23 36 72 C. 16 48 35 79 82 23 36 72 D. 16 35 48 79 23 36 72 82 9.排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为。 A. 希尔排序 B. 起泡排序 C. 插入排序 D. 选择排序 10.排序方法中，从未排序序列中挑选元素，并将其依次放入已排序序列（初始时为空）的一端的方法，称为。 A. 希尔排序 B. 归并排序 C. 插入排序 D. 选择排序 11.若需在 O(nlog2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是。 A．快速排序 B．堆排序 C．归并排序 D．直接插入排序 12.下述几种排序方法中，平均查找长度最小的是。 A. 插入排序 B. 选择排序 C. 快速排序 D. 归并排序 13.下述几种排序方法中，要求内存量最大的是。 A. 插入排序 B. 选择排序 C. 快速排序 D. 归并排序 填空题 1.在对一组记录(54，38，96，23，15，72，60，45，83)进行直接插入排序时，当把第 8 个记录 45 插入到有序表时，为寻找插入位置需比较次。 2.对于关键字序列（12，13，11，18，60，15，7，20，25，100），用筛选法建堆，必须从键值为的关键字开始。 3.对 n个记录的表 r[1..n]进行简单选择排序，所需进行的关键字间的比较次数为。 4.在插入排序、希尔排序、选择排序、快速排序、堆排序、归并排序和基数排序中，排序是不稳定的有。 5. 在插入排序、希尔排序、选择排序、快速排序、堆排序、归并排序和基数排序中，平均比较次数最少的排序是①，需要内存容量最多的是②。 6.在堆排序和快速排序中，若原始记录接近正序或反序，则选用①，若原始记录无序，则最好选用②。 7.在插入和选择排序中，若初始数据基本正序，则选用①；若初始数据基本反序则选用②。 8.对 n 个元素的序列进行起泡排序时，最少的比较次数是。 9、排序不需要进行记录关键字间的比较。 1 2 3 4 5 6 7 8 9 10 11 12 13 D C A B D C C A C D C C D 填空题 1.5 2.60 3.n（n-1）/2 4.希尔排序、选择排序、快速排序和堆排序 5.①快速排序②基数排序 6.①堆排序②快速排序 7-①插入排序②选择排序 8.n-1 9.基数 填空题(10 * 1 '= 10') 一、概念题 22当对一个线性表经常进行的是插入和删除操作时，采用链式存储结构为宜。 23当对一个线性表经常进行的是存取操作，而很少进行插入和删除操作时，最好采用顺序存储结构。 2.6. 带头结点的单链表L中只有一个元素结点的条件是L->Next->Next==Null。 36循环队列的引入，目的是为了克服假溢出。 4.2. 长度为0的字符串称为空串。 4.5. 组成串的数据元素只能是字符。 4.8. 设T和P是两个给定的串，在T中寻找等于P的子串的过程称为模式匹配，又称P为模式。 7.2. 为了实现图的广度优先搜索，除一个标志数组标志已访问的图的结点外，还需要队列存放被访问的结点实现遍历。 5.7. 广义表的深度是广义表中括号的重数 7.8. 有向图G可拓扑排序的判别条件是有无回路。 7.9. 若要求一个稠密图的最小生成树，最好用Prim算法求解。 8.8. 直接定址法法构造的哈希函数肯定不会发生冲突。 9.2. 排序算法所花费的时间，通常用在数据的比较和交换两大操作。 1.1. 通常从正确性、可读性、健壮性、时空效率等几个方面评价算法的(包括程序)的质量。 1.2. 对于给定的n元素，可以构造出的逻辑结构有集合关系、线性关系树形关系、图状关系四种。 1.3. 存储结构主要有顺序存储、链式存储、索引存储、散列存储四种。 1.4. 抽象数据类型的定义仅取决于它的一组逻辑特性，而与存储结构无关，即不论其内部结构如何变化，只要它的数学特性不 变，都不影响其外部使用。 1.5. 一个算法具有五大特性：有穷性、确定性、可行性，有零个或多个输入、有一个或多个输入。 2.8. 在双向链表结构中，若要求在p指针所指的结点之前插入指针为s所指的结点，则需执行下列语句： s_>prior= p_>prior; s->next= p; p_>prior- next= s; p_>prior= s;。 2.9. 在单链表中设置头结点的作用是不管单链表是否为空表，头结点的指针均不空，并使得对单链表的操作 (如插入和删除)在各种情况下统一。 3.1. 队列是限制在表的一端进行插入和在另一端进行删除的线性表，其运算遵循先进先出原则。 3.2 .栈是限定尽在表位进行插入或删除操作的线性表。 3.5. 在链式队列中，判定只有一个结点的条件是(Q->rear==Q->fro nt)&&(Q->rear!=NULL) 。 3.7. 已知链队列的头尾指针分别是f和r，则将x入队的操作序列是node *p=(node *)malloc(node); p->next=x;] p_>next=NULL; if(r) {r->next=p; r=p;} else {r=p; f=p;}。 3.8. 循环队列的满与空的条件是(rear+1)%MAXSIZE==fornt 和(fron t=-1 &&rear+ ^=MAXSIZE) 。 4.3. 串是一种特殊的线性表，其特殊性表现在数据元素都是由字符组成。 4.7. 字符串存储密度是串值所占存储位和实际分配位的比值，在字符串的链式存储结构中其结点大小是可变的。 5.3. 所谓稀疏矩阵指的是矩阵中非零元素远远小于元素总数，则称该矩阵为矩阵中非零元素远远小于元素总数，则称该矩阵为稀 疏矩阵。 5.4. —维数组的逻辑结构是线性结构，存储结构是顺序存储结构；对二维或多维数组，分别按行优先和列优先两种?不同的存储 方式。 7.4. 在有向图的邻接矩阵表示中，计算第i个顶点入度的方法是求邻接矩阵中第?i列非10元素的个数。 7.10. AOV网中，结点表示活动，边表示活动之间的优先关系，AOE网中，结点表示事件，边表示活动。 9.1. 按排序过程中依据不同原则对内部排序方法进行分类，主要有选择排序、交换排序、插入排序归并排序等4类。 9.3 .在堆排序、快速排序和归并排序中若只从排序结果的稳定性考虑，则应选择归并排序方法；若只从平均情况下 排序最快考虑，则应选择快速排序方法；若只从最坏情况下排序最快且要节省类存考虑，则应选择堆排序方法。 9.4. 直接插入排序用监视哨的作用是存当前要的插入记录，可又省去查找插入位置时对是否出界的判断。 9.6. 设表中元素的初始状态是按键值递增的，则直接插入排序最省时间，快速排序最费时间。 4.9. 下列程序判断字符串s是否对称，对称则返回1,否则返回0;如？(abba”返回1, ? (”abab”)返回0. Int f (char*s) { Int i=0,j=0; 数据结构习题 第一章绪论 1.6 在程序设计中，常用下列三种不同的出错处理方式： 1) 用exit语句终止执行并报告错误； 2) 以函数的返回值区别正确返回或错误返回； 3) 设置一个整形变量的函数参数以区别正确返回或某种错误返回。 试讨论这三种方法各自的优缺点。 1.7 在程序设计中，可采用下列三种方法实现输出和输入： 1) 通过scanf和printf语句； 2) 通过函数的参数显示传递； 3) 通过全局变量隐式传递。 试讨论这三种方法的优缺点。 1.8 设n为正整数。试确定下列各程序段中前置以记号@的语句的频度： 5) for (i = 1; i <= n; i++ ) { for (j = 1; j <= i; j++) { for (k = 1; k <= j; k++) { @ x += delta; } } } 答案：n*(n+1)*(n+2) =1+（1+2）+（1+2+3）+...+(1+2+3+...+n) =∑ =+ n i i i 1 2 / )1 ( * =1/2*∑ =+ n i i i i 1 * =n*(n+1)*(2n+1)/12 +n*(n+1)/4 =n*(n+1)*(n+2)/6 7) x = n; //n是不小于1的常数 y = 0; while (x >= (y + 1) * (y + 1)) { @ y++; } 答案：n向下取整 8) x = 91; y = 100; while (y > 0) { @ if (x > 100) { x -= 10; y--;} else { x++; } } 答案：if 执行次数为1100， if 判断内部执行为100次 1.19 试编写算法，计算i!·2i （i = 0, 1, …, n-1）的值并分别存入数组a[arrsize]的各个分量中。假设计算机中允许的整数最大值为MAXINT ，则当n > arrsize 或对某个k （0 ≤ k ≤ n-1）使k!·2k > MAXINT 时，应按出错处理。注意选择你认为较好的出错处理方法。 1.20 试编写算法求一元多项式∑==n i i i x a x 0n )(P 的值P n (x 0)，并确定算法中每一语句的执行 次数和整个算法的时间复杂度。注意选择你认为较好的输入和输出方法。本题的输入为a i （i=0, 1, …, n ）、x 0和n ，输出为P n (x 0)。 第1章绪论 一、选择题 1. 算法的计算量的大小称为计算的（）。 A．效率 B. 复杂性 C. 现实性 D. 难度 2. 算法的时间复杂度取决于（） A．问题的规模 B. 待处理数据的初态 C. A和B 3.计算机算法指的是（1），它必须具备（2）这三个特性。 (1) A．计算方法 B. 排序方法 C. 解决问题的步骤序列 D. 调度方法 (2) A．可执行性、可移植性、可扩充性 B. 可执行性、确定性、有穷性 C. 确定性、有穷性、稳定性 D. 易读性、稳定性、安全性 4．一个算法应该是（）。 A．程序 B．问题求解步骤的描述 C．要满足五个基本特性 D．A和C. 5. 下面关于算法说法错误的是（） A．算法最终必须由计算机程序实现 B.为解决某问题的算法同为该问题编写的程序含义是相同的 C. 算法的可行性是指指令不能有二义性 D. 以上几个都是错误的 6. 下面说法错误的是（） (1）算法原地工作的含义是指不需要任何额外的辅助空间 （2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法（3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界 （4）同一个算法，实现语言的级别越高，执行效率就越低 A．(1) B.(1),(2) C.(1),(4) D.(3) 7．从逻辑上可以把数据结构分为（）两大类。 A．动态结构、静态结构 B．顺序结构、链式结构 C．线性结构、非线性结构 D．初等结构、构造型结构 8．以下与数据的存储结构无关的术语是（）。 A．循环队列 B. 链表 C. 哈希表 D. 栈 9．以下数据结构中，哪一个是线性结构（）？ A．广义表 B. 二叉树 C. 稀疏矩阵 D. 串 10．以下那一个术语与数据的存储结构无关？（） A．栈 B. 哈希表 C. 线索树 D. 双向链表 11．在下面的程序段中，对x的赋值语句的频度为（） FOR i:=1 TO n DO FOR j:=1 TO n DO x:=x+1; A． O(2n) B．O(n) C．O(n2) D．O(log2n) 12．程序段 FOR i:=n-1 DOWNTO 1 DO FOR j:=1 TO i DO IF A[j]>A[j+1] THEN A[j]与A[j+1]对换； 7.1 选择题 1. 对于一个具有n个顶点和e条边的有向图，在用邻接表表示图时，拓扑排序算法时间复杂度为() A) O(n)B)O(n+e)C) O(n*n)D)O(n*n*n) 【答案】B 2. 设无向图的顶点个数为n,则该图最多有()条边。 A) n-1B)n(n-1)/2C)n(n+1)/2 【答案】B 3. 连通分量指的是() A) 无向图中的极小连通子图 B) 无向图中的极大连通子图 C) 有向图中的极小连通子图 D) 有向图中的极大连通子图 【答案】B 4. n 个结点的完全有向图含有边的数目() A) n*n B) n(n+1) C) n/2 【答案】D 5. 关键路径是() A) AOE网中从源点到汇点的最长路径 B) AOE网中从源点到汇点的最短路径 C) AOV网中从源点到汇点的最长路径D) n2 D) n* (n-1) D) AOV网中从源点到汇点的最短路径 【答案】 A 6．有向图中一个顶点的度是该顶点的() A)入度B)出度C)入度与出度之和D)(入度+出度)12 【答案】C 7．有e 条边的无向图，若用邻接表存储，表中有()边结点。 A) e B) 2eC) e-1D) 2(e-1) 【答案】B 8．实现图的广度优先搜索算法需使用的辅助数据结构为() A)栈B)队列C)二叉树D)树 【答案】B 9．实现图的非递归深度优先搜索算法需使用的辅助数据结构为() A)栈B)队列C)二叉树D)树 【答案】 A 10．存储无向图的邻接矩阵一定是一个() A)上三角矩阵B)稀疏矩阵C)对称矩阵D)对角矩阵 【答案】C 11．在一个有向图中所有顶点的入度之和等于出度之和的()倍 A) B) 1C) 2D) 4 答案】B 12．在图采用邻接表存储时，求最小生成树的Prim 算法的时间复杂度为( 数据结构习题集答案 第1章绪论 1.1 简述下列术语：数据，数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。 解：数据是对客观事物的符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。 数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 数据对象是性质相同的数据元素的集合，是数据的一个子集。 数据结构是相互之间存在一种或多种特定关系的数据元素的集合。存储结构是数据结构在计算机中的表示。 数据类型是一个值的集合和定义在这个值集上的一组操作的总称。抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。是对一般数据类型的扩展。 1.2 试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。 解：抽象数据类型包含一般数据类型的概念，但含义比一般数据类型更广、更抽象。一般数据类型由具体语言系统内部定义，直接提供给编程者定义用户数据，因此称它们为预定义数据类型。抽象数据 类型通常由编程者定义，包括定义它所使用的数据和在这些数据上所进行的操作。在定义抽象数据类型中的数据部分和操作部分时，要求只定义到数据的逻辑结构和操作说明，不考虑数据的存储结构和操作的具体实现，这样抽象层次更高，更能为其他用户提供良好的使用接口。 1.3 设有数据结构(D,R)，其中 {}4,3,2,1d d d d D =，{}r R =，()()(){}4,3,3,2,2,1d d d d d d r = 试按图论中图的画法惯例画出其逻辑结构图。 解： 1.4 试仿照三元组的抽象数据类型分别写出抽象数据类型复数和有理数的定义（有理数是其分子、分母均为自然数且分母不为零的分数）。 解：ADT Complex{ 数据对象：D={r,i|r,i 为实数} 数据关系：R={ 图 1. 填空题 ⑴ 设无向图G中顶点数为n，则图G至少有（）条边，至多有（）条边；若G为有向图，则至少有（）条边，至多有（）条边。 【解答】0，n(n-1)/2，0，n(n-1) 【分析】图的顶点集合是有穷非空的，而边集可以是空集；边数达到最多的图称为完全图，在完全图中，任意两个顶点之间都存在边。 ⑵ 任何连通图的连通分量只有一个，即是（）。 【解答】其自身 ⑶ 图的存储结构主要有两种，分别是（）和（）。 【解答】邻接矩阵，邻接表 【分析】这是最常用的两种存储结构，此外，还有十字链表、邻接多重表、边集数组等。 ⑷ 已知无向图G的顶点数为n，边数为e，其邻接表表示的空间复杂度为（）。 【解答】Ｏ(n+e) 【分析】在无向图的邻接表中，顶点表有n个结点，边表有2e个结点，共有n+2e个结点，其空间复杂度为Ｏ(n+2e)=Ｏ(n+e)。 ⑸ 已知一个有向图的邻接矩阵表示，计算第j个顶点的入度的方法是（）。 【解答】求第j列的所有元素之和 ⑹ 有向图G用邻接矩阵A[n][n]存储，其第i行的所有元素之和等于顶点i的（）。 【解答】出度 ⑺ 图的深度优先遍历类似于树的（）遍历，它所用到的数据结构是（）；图的广度优先遍历类似于树的（）遍历，它所用到的数据结构是（）。 【解答】前序，栈，层序，队列 ⑻ 对于含有n个顶点e条边的连通图，利用Prim算法求最小生成树的时间复杂度为（），利用Kruskal 算法求最小生成树的时间复杂度为（）。 【解答】Ｏ(n2)，Ｏ(elog2e) 【分析】Prim算法采用邻接矩阵做存储结构，适合于求稠密图的最小生成树；Kruskal算法采用边集数组做存储结构，适合于求稀疏图的最小生成树。 ⑼ 如果一个有向图不存在（），则该图的全部顶点可以排列成一个拓扑序列。 【解答】回路 ⑽ 在一个有向图中，若存在弧、、，则在其拓扑序列中，顶点vi, vj, vk的相对次序为（）。 【解答】vi, vj, vk 【分析】对由顶点vi, vj, vk组成的图进行拓扑排序。 2. 选择题 ⑴ 在一个无向图中，所有顶点的度数之和等于所有边数的（）倍。 A 1/2 B 1 C 2 D 4 【解答】C 【分析】设无向图中含有n个顶点e条边，则。 填空题（10 * 1’ = 10’） 一、概念题 .当对一个线性表经常进行的是插入和删除操作时，采用链式存储结构为宜。 .当对一个线性表经常进行的是存取操作，而很少进行插入和删除操作时，最好采用顺序存储结构。 .带头结点的单链表L中只有一个元素结点的条件是L->Next->Next==Null。 .循环队列的引入，目的是为了克服假溢出。 .长度为0的字符串称为空串。 .组成串的数据元素只能是字符。 .设T和P是两个给定的串，在T中寻找等于P的子串的过程称为模式匹配，又称P为模式。 .为了实现图的广度优先搜索，除一个标志数组标志已访问的图的结点外，还需要队列存放被访问的结点实现遍历。 .广义表的深度是广义表中括号的重数 .有向图G可拓扑排序的判别条件是有无回路。 .若要求一个稠密图的最小生成树，最好用Prim算法求解。 . 直接定址法法构造的哈希函数肯定不会发生冲突。 .排序算法所花费的时间，通常用在数据的比较和交换两大操作。 .通常从正确性﹑可读性﹑健壮性﹑时空效率等几个方面评价算法的（包括程序）的质量。 .对于给定的n元素，可以构造出的逻辑结构有集合关系﹑线性关系树形关系﹑图状关系四种。 .存储结构主要有顺序存储﹑链式存储﹑索引存储﹑散列存储四种。 .抽象数据类型的定义仅取决于它的一组逻辑特性，而与存储结构无关，即不论其内部结构如何变化，只要它的数学特性不变，都不影响其外部使用。 .一个算法具有五大特性：有穷性﹑确定性﹑可行性，有零个或多个输入﹑有一个或多个输入。 .在双向链表结构中，若要求在p指针所指的结点之前插入指针为s所指的结点，则需执行下列语句：s->prior= p->prior; s->next= p; p->prior- next= s; p->prior= s;。 .在单链表中设置头结点的作用是不管单链表是否为空表，头结点的指针均不空，并使得对单链表的操作（如插入和删除）在各种情况下统一。 .队列是限制在表的一端进行插入和在另一端进行删除的线性表，其运算遵循先进先出原则。 .栈是限定尽在表位进行插入或删除操作的线性表。 .在链式队列中，判定只有一个结点的条件是(Q->rear==Q->front)&&(Q->rear!=NULL)。 .已知链队列的头尾指针分别是f和r，则将x入队的操作序列是node *p=(node *)malloc(node); p->next=x; p->next=NULL; if(r) {r->next=p; r=p;} else {r=p; f=p;}。 .循环队列的满与空的条件是(rear+1)%MAXSIZE==fornt和(front=-1&&rear+1==MAXSIZE)。 .串是一种特殊的线性表，其特殊性表现在数据元素都是由字符组成。 .字符串存储密度是串值所占存储位和实际分配位的比值，在字符串的链式存储结构中其结点大小是可变的。 .所谓稀疏矩阵指的是矩阵中非零元素远远小于元素总数，则称该矩阵为矩阵中非零元素远远小于元素总数，则称该矩阵为稀疏矩阵。 .一维数组的逻辑结构是线性结构，存储结构是顺序存储结构；对二维或多维数组，分别按行优先和列优先两种不同的存储方式。 .在有向图的邻接矩阵表示中，计算第i个顶点入度的方法是求邻接矩阵中第i列非0元素的个数。 网中，结点表示活动，边表示活动之间的优先关系，AOE网中，结点表示事件，边表示活动。 .按排序过程中依据不同原则对内部排序方法进行分类，主要有选择排序﹑交换排序﹑插入排序归并排序等4类。 .在堆排序、快速排序和归并排序中若只从排序结果的稳定性考虑，则应选择归并排序方法；若只从平均情况下排序最快考虑，则应选择快速排序方法；若只从最坏情况下排序最快且要节省类存考虑，则应选择堆排序方法。 .直接插入排序用监视哨的作用是存当前要的插入记录，可又省去查找插入位置时对是否出界的判断。 .设表中元素的初始状态是按键值递增的，则直接插入排序最省时间，快速排序最费时间。 .下列程序判断字符串s是否对称，对称则返回1，否则返回0；如?(“abba”)返回1，?（”abab”）返回0. Int f (char*s) { Int i=0,j=0; 求串长*/ 第十一章文件 一、选择题 1. 散列文件使用散列函数将记录的关键字值计算转化为记录的存放地址，因为散列函数是一对一的关系，则选择好的（）方法是散列文件的关键。【哈尔滨工业大学 2001二、5 （2分）】 A. 散列函数 B. 除余法中的质数 C. 冲突处理 D. 散列函数和冲突处理 2. 顺序文件采用顺序结构实现文件的存储，对大型的顺序文件的少量修改，要求重新复制整个文件，代价很高，采用（）的方法可降低所需的代价。【北京邮电大学 2000 二、 8 （20/8分）】 A. 附加文件 B. 按关键字大小排序 C. 按记录输入先后排序 D. 连续排序 3. 用ISAM组织文件适合于（）。【中科院软件所 1998】 A．磁带 B．磁盘 4．下述文件中适合于磁带存储的是（）。【中科院计算所 2000 一、7（2分）】 A. 顺序文件 B. 索引文件 C. 散列文件 D. 多关键字文件 5. 用ISAM和VSAM组织文件属于（）。 A. 顺序文件 B. 索引文件 C. 散列文件 【中国科技大学 1998 二、5（2分）中科院计算所 1998 二、5（2分）】 6. ISAM文件和VASM文件属于（）。【山东大学 2001 二、5 (1分)】 A. 索引非顺序文件 B. 索引顺序文件 C. 顺序文件 D. 散列文件 7. B+树应用在（）文件系统中。【北京邮电大学 2001 一、1（2分）】 A. ISAM B. VSAM 二、判断题 1. 文件是记录的集合，每个记录由一个或多个数据项组成，因而一个文件可看作由多个记录组成的数据结构。【长沙铁道学院 1998 一、5 (1分)】 2. 倒排文件是对次关键字建立索引。【南京航空航天大学 1997 一、10（1分）】 3. 倒排序文件的优点是维护简单。【南京航空航天大学 1995 五、10（1分）】 4. 倒排文件与多重表文件的次关键字索引结构是不同的。【西安交通大学 1996 二、6 (3分)】 5. Hash表与Hash文件的唯一区别是Hash文件引入了‘桶’的概念。【南京航空航天大学1996六10(1分）】 6. 文件系统采用索引结构是为了节省存储空间。【北京邮电大学 2000 一、10 （1分）】 7. 对处理大量数据的外存介质而言，索引顺序存取方法是一种方便的文件组织方法。 【东南大学 2001 一、1-10 （1分）】 8. 对磁带机而言，ISAM是一种方便的稳健组织方法。【中科院软件所 1997 一、10（1分）】 9. 直接访问文件也能顺序访问，只是一般效率不高。【北京邮电大学 2002 一、10（1分）】 10. 存放在磁盘，磁带上的文件，即可以是顺序文件，也可以是索引结构或其他结构类型的文件。 【山东大学 2001 一、7 (1分)】 11. 检索出文件中的关键码值落在某个连续的范围内的全部记录，这种操作称为范围检索。对经常需要做范围检索的文件进行组织，采用散列法优于顺序检索法。【中山大学 1994 一、 数据结构课程作业_A 交卷时间：2017-08-09 10:08:51 一、单选题 1. (7分)设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每个元素占一个空间，问A[3][3](10)存放在什么位置脚注(10)表示用10进制表示。 A. 688 B. 678 C. 692 D. 696 纠错 得分： 7 知识点：第五章 展开解析 答案 C 解析第五章第二节综合题目 2. (7分)若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二分查找，则查找A［3］的比较序列的下标依次为( ) A. 1，2，3 B. 9，5，2，3 C. 9，5，3 D. 9，4，2，3 纠错 得分： 0 知识点：第九章 展开解析 答案 D 解析第九章第一节有序表的查找 (7分)设某完全无向图中有n个顶点，则该完全无向图中有（）条边。 A. n(n-1)/2 B. n(n-1) C. n2 D. n2-1 纠错 得分： 7 知识点：第七章 展开解析 答案 A 解析第七章第一节综合题目 4. (7分)若在任意一棵二叉树中，有n0个叶子结点，有n2个度为2的结点，则：n0=_____ A. n2+1 B. n2-1 C. n2+2 D. n2-2 纠错 得分： 7 知识点：第六章 展开解析 答案 A 解析第六章第二节二叉树的性质 5. (7分)栈的插入和删除操作在（）进行。 A. 栈顶 B. 栈底 C. 任意位置 D. 指定位置 得分： 7 知识点：第三章 展开解析 答案 A 解析第三章第一节栈的表示和实现 6. (7分)设有序表中有1000个元素，则用二分查找查找元素X最多需要比较（）次。 A. 25 B. 10 C. 7 D. 1 纠错 得分： 7 知识点：第九章 展开解析 答案 B 解析第九章第一节有序表的查找 7. (7分)设某棵二叉树的高度为10，则该二叉树上叶子结点最多有（）。 A. 20 B. 256 C. 512 D. 1024 纠错 得分： 7 知识点：第六章 展开解析 答案 C 解析第六章第六节二叉树的性质 第二章习题 1. 描述以下三个概念的区别：头指针，头结点，首元素结点。 2. 填空： （1）在顺序表中插入或删除一个元素，需要平均移动元素，具体移动的元素个数与有关。 （2）在顺序表中，逻辑上相邻的元素，其物理位置相邻。在单链表中，逻辑上相邻的元素，其物理位置相邻。 （3）在带头结点的非空单链表中，头结点的存储位置由指示，首元素结点的存储位置由指示，除首元素结点外，其它任一元素结点的存储位置由指示。3．已知L是无表头结点的单链表，且P结点既不是首元素结点，也不是尾元素结点。按要求从下列语句中选择合适的语句序列。 a. 在P结点后插入S结点的语句序列是：。 b. 在P结点前插入S结点的语句序列是：。 c. 在表首插入S结点的语句序列是：。 d. 在表尾插入S结点的语句序列是：。 供选择的语句有： （1）P->next=S; （2）P->next= P->next->next; （3）P->next= S->next; （4）S->next= P->next; （5）S->next= L; （6）S->next= NULL; （7）Q= P; （8）while(P->next!=Q) P=P->next; （9）while(P->next!=NULL) P=P->next; （10）P= Q; （11）P= L; （12）L= S; （13）L= P; 4. 设线性表存于a(1:arrsize)的前elenum个分量中且递增有序。试写一算法，将X插入到线性表的适当位置上，以保持线性表的有序性。 5. 写一算法，从顺序表中删除自第i个元素开始的k个元素。 6. 已知线性表中的元素（整数）以值递增有序排列，并以单链表作存储结构。试写一高效算法，删除表中所有大于mink且小于maxk的元素（若表中存在这样的元素），分析你的算法的时间复杂度（注意：mink和maxk是给定的两个参变量，它们的值为任意的整数）。 7. 试分别以不同的存储结构实现线性表的就地逆置算法，即在原表的存储空间将线性表（a1, a2..., an）逆置为（an, an-1,..., a1）。 （1）以一维数组作存储结构，设线性表存于a(1:arrsize)的前elenum个分量中。 （2）以单链表作存储结构。 8. 假设两个按元素值递增有序排列的线性表A和B，均以单链表作为存储结构，请编写算法，将A表和B表归并成一个按元素值递减有序排列的线性表C，并要求利用原表（即A 表和B表的）结点空间存放表C。 第1章绪论 1. 填空 （1）（）是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 （2）（）是数据的最小单位，（）是讨论数据结构时涉及的最小数据单位。 （3）从逻辑关系上讲，数据结构主要分为（）、（）、（）和（）。 （4）数据的存储结构主要有（）和（）两种基本方法，不论哪种存储结构，都要存储两方面的内容：（）和（）。 （5）算法具有五个特性，分别是（）、（）、（）、（）、（）。 （6）在一般情况下，一个算法的时间复杂度是（）的函数。 （7）设待处理问题的规模为n，若一个算法的时间复杂度为一个常数，则表示成数量级的形式为（），若为n*log25n，则表示成数量级的形式为（）。 2. 选择题 ⑴顺序存储结构中数据元素之间的逻辑关系是由（）表示的，链式存储结构中的数据元素之间的逻辑关系是由（）表示的。 A 线性结构 B 非线性结构 C 存储位置 D 指针 ⑵假设有如下遗产继承规则：丈夫和妻子可以相互继承遗产；子女可以继承父亲或母亲的遗产；子女间不能相互继承。则表示该遗产继承关系的最合适的数据结构应该是（）。 A 树 B 图 C 线性表 D 集合 ⑶算法指的是（）。 A 对特定问题求解步骤的一种描述，是指令的有限序列。 B 计算机程序 C 解决问题的计算方法 D 数据处理 ⑷下面（）不是算法所必须具备的特性。 A 有穷性 B 确切性 C 高效性 D 可行性 ⑸算法分析的目的是（），算法分析的两个主要方面是（）。 A 找出数据结构的合理性 B 研究算法中输入和输出的关系 C 分析算法的效率以求改进 D 分析算法的易读性和文档性 E 空间性能和时间性能 F 正确性和简明性 G 可读性和文档性H 数据复杂性和程序复杂性 3. 判断题 （1）算法的时间复杂度都要通过算法中的基本语句的执行次数来确定。 （2）每种数据结构都具备三个基本操作：插入、删除和查找。 （3）逻辑结构与数据元素本身的内容和形式无关。 （4）基于某种逻辑结构之上的基本操作，其实现是唯一的。 4. 分析以下各程序段，并用大O记号表示其执行时间。 数据结构章节练习题 第一章绪论 一、单选题 1.一个数组元素a[i]与________的表示等价。 A、 *(a+i) B、 a+i C、 *a+i D、 &a+i 2.下面程序段的时间复杂度为____________。 for(int i=0; i 数据结构习题及解答 第1章 概述 【例1-1】分析以下程序段的时间复杂度。 for(i=0;i 得：T（n）=O( n 2 log) 【例1-4】有如下递归函数fact(n)，分析其时间复杂度。 fact(int n) { if(n<=1) return(1);① else return(n*fact(n-1));② } 解：设fact（n）的运行时间函数是T(n)。该函数中语句①的运行时间是O(1)，语句②的运行时间是T(n-1)+ O(1)，其中O(1)为常量运行时间。 由此可得fact（n）的时间复杂度为O(n)。 习题1 一、单项选择题 1.数据结构是指（1. A ）。 A.数据元素的组织形式 B.数据类型 C.数据存储结构 D.数据定义 2.数据在计算机存储器内表示时，物理地址与逻辑地址不相同的，称之为（2. C ）。 A.存储结构 B.逻辑结构 C.链式存储结构 D.顺序存储结构 3.树形结构是数据元素之间存在一种（3. D ）。 A.一对一关系 B.多对多关系 C.多对一关系 D.一对多关系 4.设语句x++的时间是单位时间，则以下语句的时间复杂度为（4. B）。 for(i=1; i<=n; i++) for(j=i; j<=n; j++) x++; A.O(1) B.O(2 n) C.O(n) D.O(3n) 5.算法分析的目的是（5. C、），算法分析的两个主要方面是（A）。 （1） A.找出数据结构的合理性 B.研究算法中的输入和输出关系 C.分析算法的效率以求改进 D.分析算法的易懂性和文档性 （2） A.空间复杂度和时间复杂度 B.正确性和简明性 C.可读性和文档性 D.数据复杂性和程序复杂性 6.计算机算法指的是（6. C、），它具备输入，输出和（B）等五个特性。 （1） A.计算方法 B.排序方法 C.解决问题的有限运算序列 D.调度方法 （2） A.可行性，可移植性和可扩充性 B.可行性，确定性和有穷性 C.确定性，有穷性和稳定性 D.易读性，稳定性和安全性 7.数据在计算机内有链式和顺序两种存储方式，在存储空间使用的灵活性上，链式存储比顺序存储要（7. B）。 第 1 章 绪 论 (2005-07-14) - 第 1 章 绪 论 课后习题讲解 1. 填空 ⑴（ ）是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 【解答】数据元素 ⑵（ ）是数据的最小单位，（ ）是讨论数据结构时涉及的最小数据单位。 【解答】数据项，数据元素 【分析】数据结构指的是数据元素以及数据元素之间的关系。 ⑶ 从逻辑关系上讲，数据结构主要分为（ ）、（ ）、（ ）和（ ）。 【解答】集合，线性结构，树结构，图结构 ⑷ 数据的存储结构主要有（ ）和（ ）两种基本方法，不论哪种存储结构，都要存储两方面的内容：（ ）和（）。 【解答】顺序存储结构，链接存储结构，数据元素，数据元素之间的关系 ⑸ 算法具有五个特性，分别是（ ）、（ ）、（ ）、（ ）、（ ）。 【解答】有零个或多个输入，有一个或多个输出，有穷性，确定性，可行性 ⑹ 算法的描述方法通常有（ ）、（ ）、（ ）和（ ）四种，其中，（ ）被称为算法语言。 【解答】自然语言，程序设计语言，流程图，伪代码，伪代码 ⑺ 在一般情况下，一个算法的时间复杂度是（ ）的函数。 【解答】问题规模 ⑻ 设待处理问题的规模为n，若一个算法的时间复杂度为一个常数，则表示成数量级的形式为（ ），若为 n*log25n，则表示成数量级的形式为（ ）。 【解答】Ο(1)，Ο(nlog2n) 【分析】用大O记号表示算法的时间复杂度，需要将低次幂去掉，将最高次幂的系数去掉。 2. 选择题 ⑴ 顺序存储结构中数据元素之间的逻辑关系是由（ ）表示的，链接存储结构中的数据元素之间的逻辑关系是由（ ）表示的。 A 线性结构 B 非线性结构 C 存储位置 D 指针 【解答】C，D 【分析】顺序存储结构就是用一维数组存储数据结构中的数据元素，其逻辑关系由存储位置（即元素在数组中的下标）表示；链接存储结构中一个数据元素对应链表中的一个结点，元素之间的逻辑关系由结点中的指针表示。 ⑵ 假设有如下遗产继承规则：丈夫和妻子可以相互继承遗产；子女可以继承父亲或母亲的遗产；子女间不能相互继承。则表示该遗产继承关系的最合适的数据结构应该是（ ）。 A 树 B 图 C 线性表 D 集合 【解答】B 【分析】将丈夫、妻子和子女分别作为数据元素，根据题意画出逻辑结构图。 ⑶ 算法指的是（ ）。 A 对特定问题求解步骤的一种描述，是指令的有限序列。 B 计算机程序 C 解决问题的计算方法 D 数据处理 【解答】A 【分析】计算机程序是对算法的具体实现；简单地说，算法是解决问题的方法；数据处理是通过算法完成的。所以，只有A是算法的准确定义。 ⑷ 下面（ ）不是算法所必须具备的特性。 A 有穷性 B 确切性 C 高效性 D 可行性 【解答】C 【分析】高效性是好算法应具备的特性。 ⑸ 算法分析的目的是（ ），算法分析的两个主要方面是（ ）。 A 找出数据结构的合理性 B 研究算法中输入和输出的关系 C 分析算法的效率以求改进 D 分析算法的易读性和文档性 E 空间性能和时间性能 F 正确性和简明性 G 可读性和文档性 H 数据复杂性和程序复杂性 图 1. 填空题 ⑴设无向图G中顶点数为n，则图G至少有（）条边，至多有（）条边；若G为有向图，则至少有（）条边，至多有（）条边。 【解答】0，n(n-1)/2，0，n(n-1) 【分析】图的顶点集合是有穷非空的，而边集可以是空集；边数达到最多的图称为完全图，在完全图中，任意两个顶点之间都存在边。 ⑵任何连通图的连通分量只有一个，即是（）。 【解答】其自身 ⑶图的存储结构主要有两种，分别是（）和（）。 【解答】邻接矩阵，邻接表 【分析】这是最常用的两种存储结构，此外，还有十字链表、邻接多重表、边集数组等。 ⑷已知无向图G的顶点数为n，边数为e，其邻接表表示的空间复杂度为（）。 【解答】Ｏ(n+e) 【分析】在无向图的邻接表中，顶点表有n个结点，边表有2e个结点，共有n+2e个结点，其空间复杂度为Ｏ(n+2e)=Ｏ(n+e)。 ⑸已知一个有向图的邻接矩阵表示，计算第j个顶点的入度的方法是（）。 【解答】求第j列的所有元素之和 ⑹有向图G用邻接矩阵A[n][n]存储，其第i行的所有元素之和等于顶点i的（）。 【解答】出度 ⑺图的深度优先遍历类似于树的（）遍历，它所用到的数据结构是（）；图的广度优先遍历类似于树的（）遍历，它所用到的数据结构是（）。 【解答】前序，栈，层序，队列 ⑻对于含有n个顶点e条边的连通图，利用Prim算法求最小生成树的时间复杂度为（），利用Kruskal 算法求最小生成树的时间复杂度为（）。 【解答】Ｏ(n2)，Ｏ(elog2e) 【分析】Prim算法采用邻接矩阵做存储结构，适合于求稠密图的最小生成树；Kruskal算法采用边集数组做存储结构，适合于求稀疏图的最小生成树。 ⑼如果一个有向图不存在（），则该图的全部顶点可以排列成一个拓扑序列。 【解答】回路 ⑽在一个有向图中，若存在弧、、，则在其拓扑序列中，顶点vi, vj, vk的相对次序为（）。 【解答】vi, vj, vk 第一章绪论 一、选择题 1.组成数据的基本单位是（） （A）数据项（B）数据类型（C）数据元素（D）数据变量 2.数据结构是研究数据的（）以及它们之间的相互关系。 （A）理想结构，物理结构（B）理想结构，抽象结构 （C）物理结构，逻辑结构（D）抽象结构，逻辑结构 3.在数据结构中，从逻辑上可以把数据结构分成（） （A）动态结构和静态结构（B）紧凑结构和非紧凑结构 （C）线性结构和非线性结构（D）内部结构和外部结构 4.数据结构是一门研究非数值计算的程序设计问题中计算机的（①）以及它们之间的（②）和运算等的学科。 ①（A）数据元素（B）计算方法（C）逻辑存储（D）数据映像 ②（A）结构（B）关系（C）运算（D）算法 5.算法分析的目的是（）。 （A）找出数据结构的合理性（B）研究算法中的输入和输出的关系 （C）分析算法的效率以求改进（D）分析算法的易懂性和文档性 6.计算机算法指的是（①）,它必须具备输入、输出和（②）等5个特性。 ①（A）计算方法（B）排序方法（C）解决问题的有限运算序列（D）调度方法 ②（A）可执行性、可移植性和可扩充性（B）可行性、确定性和有穷性 （C）确定性、有穷性和稳定性（D）易读性、稳定性和安全性 二、判断题 1.数据的机内表示称为数据的存储结构。（） 2.算法就是程序。（） 3.数据元素是数据的最小单位。（） 4.算法的五个特性为：有穷性、输入、输出、完成性和确定性。（） 5.算法的时间复杂度取决于问题的规模和待处理数据的初态。（） 三、填空题 1.数据逻辑结构包括________、________、_________ 和_________四种类型,其中树形结构和图形结构合称为_____。 9-12章数据结构作业答案 第九章查找 选择题 1、对n个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为( A ) A．（n+1）/2 B. n/2 C. n D. [（1+n）*n ]/2 2. 下面关于二分查找的叙述正确的是 ( D ) A. 表必须有序，表可以顺序方式存储，也可以链表方式存储 B. 表必须有序且表中数据必须是整型，实型或字符型 C. 表必须有序，而且只能从小到大排列 D. 表必须有序，且表只能以顺序方式存储 3. 二叉查找树的查找效率与二叉树的( （1）C)有关, 在 (（2)C ）时其查找效率最低 (1): A. 高度 B. 结点的多少 C. 树型 D. 结点的位置 (2): A. 结点太多 B. 完全二叉树 C. 呈单枝树 D. 结点太复杂。 4. 若采用链地址法构造散列表，散列函数为H（key）=key MOD 17，则需 (（1）A) 个链表。 这些链的链首指针构成一个指针数组，数组的下标范围为 (（2）C) （1） A．17 B. 13 C. 16 D. 任意 （2） A．0至17 B. 1至17 C. 0至16 D. 1至16 判断题 1．Hash表的平均查找长度与处理冲突的方法无关。 (错) 2. 若散列表的负载因子α<1，则可避免碰撞的产生。（错） 3. 就平均查找长度而言，分块查找最小，折半查找次之，顺序查找最大。（错） 填空题 1. 在顺序表（8,11,15,19,25,26,30,33,42,48,50）中，用二分（折半）法查找关键码值20， 需做的关键码比较次数为 4 . 算法应用题 1. 设有一组关键字{9,01,23,14,55,20,84,27}，采用哈希函数：H（key）=key mod 7 ，表长 为10，用开放地址法的二次探测再散列方法Hi=(H(key)+di) mod 10解决冲突。要求：对该关 键字序列构造哈希表，并计算查找成功的平均查找长度。 2. 已知散列表的地址空间为A[0..11]，散列函数H（k）=k mod 11，采用线性探测法处理冲 突。请将下列数据{25,16,38,47,79,82,51,39,89,151,231}依次插入到散列表中，并计算出在 等概率情况下查找成功时的平均查找长度。 ３、对长度为20 的有序表进行二分查找，试画出它的一棵判定树，并求等概率情况下的平均 查找长度。 ４、设散列表的长度为15，散列函数H（K）=K%13，给定的关键字序列为20，16，29，82，37，02，06，28，55，39，23，10，试写出分别用拉链法和线性探测法解决冲突时所构造的散 列表，并求出在等概率情况下，这两种方法查找成功时的平均查找长度。(完整word版)数据结构课后习题及答案
数据结构作业
数据结构第1章作业
数据结构章节练习题-答案第7章图
数据结构课后习题答案
数据结构-第六章-图-练习题及答案详细解析(精华版)
数据结构课后习题及答案
数据结构习题及答案-第11章 文件
数据结构课程作业
数据结构课后习题及解析第二章
数据结构作业第1章
最新数据结构C语言版章节练习题(1-6章)知识分享
数据结构各章习题及答案
数据结构第一章课后习题与答案
数据结构 第六章 图 练习题及答案详细解析
严蔚敏 数据结构课后习题及答案解析
数据结构(C语言版)9-12章练习 答案 清华大学出版社
相关主题
文本预览