数据结构练习题 习题1 绪论
1.1 单项选择题
1. 数据结构是一门研究非数值计算的程序设计问题中,数据元素的① 、数据信息在计算机中的② 以及一组相关的运算等的课程。
① A．操作对象 Ｂ．计算方法 Ｃ．逻辑结构 Ｄ．数据映象 ② A．存储结构 Ｂ．关系 Ｃ．运算 Ｄ．算法 2. 数据结构DS(Data Struct)可以被形式地定义为DS=（D，R），其中D是① 的有限集合，R是D上的② 有限集合。
① A．算法 Ｂ．数据元素 Ｃ．数据操作 Ｄ．数据对象 ② A．操作 Ｂ．映象 Ｃ．存储 Ｄ．关系 3. 在数据结构中，从逻辑上可以把数据结构分成 。
A．动态结构和静态结构 Ｂ．紧凑结构和非紧凑结构 Ｃ．线性结构和非线性结构 Ｄ．内部结构和外部结构 4. 算法分析的目的是① ，算法分析的两个主要方面是② 。
① A. 找出数据结构的合理性 B. 研究算法中的输入和输出的关系
C. 分析算法的效率以求改进 D. 分析算法的易懂性和文档性 ② A. 空间复杂性和时间复杂性 B. 正确性和简明性
C. 可读性和文档性 D. 数据复杂性和程序复杂性
5. 计算机算法指的是① ，它必具备输入、输出和② 等五个特性。 ① A. 计算方法 B. 排序方法
C. 解决问题的有限运算序列 D. 调度方法
② A. 可行性、可移植性和可扩充性 B. 可行性、确定性和有穷性 C. 确定性、有穷性和稳定性 D. 易读性、稳定性和安全性
1.2 填空题（将正确的答案填在相应的空中）
1. 数据逻辑结构包括 、 和 三种类型，树形结构和图形结构合称为 。
2. 在线性结构中，第一个结点 前驱结点，其余每个结点有且只有 个前驱结点；最后一个结点 后续结点，其余每个结点有且只有 个后续结点。
3. 在树形结构中，树根结点没有 结点，其余每个结点有且只有 个直接前驱结点，叶子结点没有 结点，其余每个结点的直接后续结点可以 。
4. 在图形结构中，每个结点的前驱结点数和后续结点数可以 。
5. 线性结构中元素之间存在 关系，树形结构中元素之间存在 关系，图形结构中元素之间存在 关系。 6. 算法的五个重要特性是__ __ , __ __ , ___ _ , __ __ , _ ___。 7. 分析下面算法（程序段），给出最大语句频度 ，该算法的时间复杂度是__ __。
for (i=0;i 8. 分析下面算法（程序段），给出最大语句频度 ，该算法的时间复杂度是__ __。 for (i=0;i A[i][j]=0; 9. 分析下面算法（程序段），给出最大语句频度 ，该算法的时间复杂度是__ __。 s=0; for (i=0;i sum=s; 10. 分析下面算法（程序段）给出最大语句频度 ，该算法的时间复杂度是__ __。 i=s=0; while (s s+=i; //s=s+i } 11. 分析下面算法（程序段）给出最大语句频度 ，该算法的时间复杂度是__ __。 i=1; while (i<=n) i=i*2; 1.3 算法设计题 1. 试写一算法,自大到小依次输出顺序读入的三个数X,Y和Z的值. 2. 试写一算法,求出n个数据中的最大值。写出最大语句频度，该算法的时间复杂度。 习题答案 1.1 1. C , A 2. B,D 3. C 4. C, A 5. C,B 1.2 1. 线性结构、树形结构、图形结构，非线性结构 2. 没有、1、没有、1 3. 前驱、1、后续、任意多个 4. 任意多个 5. 一对一、一对多、多对多 6. 有穷性、确定性、可行性、输入、输出 22 7. 最大语句频度：n ， 时间复杂度：. O (n) 2 8. 最大语句频度：n (n+1)/2 ， 时间复杂度：. O (n) 33 9. 最大语句频度：n 1， 时间复杂度：. O (n) 110. 最大语句频度：n ， 时间复杂度：. O (n) 11. 最大语句频度：log2n， 时间复杂度：. O (log2n ) 习题2 线性表 2.1 单项选择题 1. 一个向量（即一批地址连续的存储单元）第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是__ __。 A. 110 B. 108 C. 100 D. 120 2. 线性表的顺序存储结构是一种__ _的存储结构，而链式存储结构是一种__ _的存储结构。 A．随机存取 B．索引存取 C．顺序存取 D．散列存取 3. 线性表的逻辑顺序与存储顺序总是一致的，这种说法__ _。 A. 正确 B. 不正确 4. 线性表若采用链式存储结构时，要求内存中可用存储单元的地址__ _。 A. 必须是连续的 B. 部分地址必须是连续的 C. 一定是不连续的 D. 连续或不连续都可以 5. 在以下的叙述中，正确的是__ _。 A. 线性表的顺序存储结构优于链表存储结构 B. 线性表的顺序存储结构适用于频繁插入/删除数据元素的情况 C. 线性表的链表存储结构适用于频繁插入/删除数据元素的情况 D. 线性表的链表存储结构优于顺序存储结构 6. 每种数据结构都具备三个基本运算：插入、删除和查找，这种说法__ _。 A. 正确 B. 不正确 7. 不带头结点的单链表head为空的判定条件是____。 A. head= =NULL B. head->next= =NULL C. head->next= =head D. head!=NULL 228. 带头结点的单链表head为空的判定条件是____。 A. head= =NULL B. head->next= =NULL C. head->next= =head D. head!=NULL 9. 非空的循环单链表head的尾结点（由p所指向）满足____。 A. p->next= =NULL B. p= =NULL C. p->next= =head D. p= =head 10. 在双向循环链表的p所指结点之后插入s所指结点的操作是____。 A. p->right=s; s->left=p; p->right->left=s; s->right=p->right; B. p->right=s; p->right->left=s; s->left=p; s->right=p->right; C. s->left=p; s->right=p->right; p->right=s; p->right->left=s; D. s->left=p; s->right=p->right; p->right->left=s; p->right=s; 11. 在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q和p之间插入s结点，则执行____。 A. s->next=p->next; p->next=s; B. p->next=s->next; s->next=p; B. q->next=s; s->next=p; C. p->next=s; s->next=q; 12. 在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行____。 A. s->next=p; p->next=s; B. s->next=p->next; p->next=s; C. s->next=p->next; p=s; C. p->next=s; s->next=p; 13. 在一个单链表中，若删除p所指结点的后续结点，则执行____。 A. p->next= p->next->next； B. p= p->next; p->next= p->next->next； C. p->next= p->next; D. p= p->next->next； 14. 从一个具有n个结点的单链表中查找其值等于x结点时，在查找成功的情况下，需平均比较____个结点。 A. n B. n/2 C. (n-1)/2 D. (n+1)/2 15. 在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是__ __。 2 A. O(1) B. O(n) C. O (n) D. O (nlog2n) 16. 给定有n个元素的向量，建立一个有序单链表的时间复杂度是__ __。 2 A. O(1)） B. O(n) C. O (n) D. O (n*log2n) 2.2 填空题（将正确的答案填在相应的空中） 1. 单链表可以做__ __的链接存储表示。 2. 在双链表中，每个结点有两个指针域，一个指向____ __，另一个指向___ __。 3. 在一个单链表中p所指结点之前插入一个s (值为e)所指结点时，可执行如下操作： q=head; while (q->next!=p) q=q->next; s= new Node; s->data=e; q->next= ; //填空 s->next= ; //填空 4. 在一个单链表中删除p所指结点的后继结点时，应执行以下操作： q= p->next; p->next= _ ___; //填空 delete ; //填空 5. 在一个单链表中p所指结点之后插入一个s所指结点时，应执行s->next=__ __和p->next=____的操作。 6. 对于一个具有n个结点的单链表，在已知p所指结点后插入一个新结点的时间复杂度是__ __；在给定值为x的结点后插入一个新结点的时间复杂度是__ __。 2.3 算法设计题: 1.设顺序表va中的数据元数递增有序。试写一算法，将x插入到顺序表的适当位置上，以保持该表的有序性。 Status Insert_SqList(SqList &va,int x) { if(va.length+1>maxsize) return ERROR; va.length++; for(i=va.length-1;va.elem[i]>x&&i>=0;i--) va.elem[i+1]=va.elem[i]; va.elem[i+1]=x; return OK; } 2.试写一算法，实现顺序表的就地逆置，即利用原表的存储空间将线性表（a1, a2,…. an）逆置为(an, an-1,…., a1)。 void reverse(int a[], int size) { int i,j,tmp; for(i=0, j=size-1; i tmp=a[i]; a[i]=a[j]; a[j]=tmp; } } 3. 已知线性表中的元素以值递增有序排列，并以单链表作存储结构。试写一算法，删除表中所有大于x且小于y的元素（若表中存在这样的元素）同时释放被删除结点空间。 void del(LinkList L,elemtype a,elemtype b) { p= L;q=p->next; while(q!=L && q->data q=q->next; } while(q!=L && q->data q=q->next; free(r); } if(p!=q) p->next=q; } 4. 试写一算法，实现单链表的就地逆置(要求在原链表上进行)。 void converse(NODEPTR L) { NODEPTR p,q; p=L->next; q=p->next; L->next=NULL; while(p) /* 对于当前结点p，用头插法将结点p插入到头结点之后 */ { p->next=L->next; L->next=p; p=q; q=q->next; } } 习题答案 2.1 1. B 2. A, C 3. B 4. D 5. C 6. A 7. A 8. B 9. C 10. D 11.B 12.B 13.A 14.D 15.B 16.C 2.2 1. 线性结表 2. 前驱结点、后继结点 3. s, p 4. q->next, q 5. p->next, s 6. O (1) , O (n) 习题3 栈和队列 3.1 单项选择题 1. 一个栈的入栈序列a，b，c，d，e，则栈的不可能的输出序列是____。 A. edcba B. decba C. dceab D. abcde 2. 若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为____。 A. i B. n=i C. n-i+1 D. 不确定 3. 栈结构通常采用的两种存储结构是____。 A. 顺序存储结构和链式存储结构 B. 散列方式和索引方式 C. 链表存储结构和数组 D. 线性存储结构和非线性存储结构 4. 判定一个顺序栈ST（最多元素为m0）为空的条件是____。 A. top !=0 B. top= =0 C. top !=m0 D. top= =m0-1 5. 判定一个顺序栈ST（最多元素为m0）为栈满的条件是____。 A. top！=0 B. top= =0 C. top！=m0 D. top= =m0-1 6. 栈的特点是____，队列的特点是____。 A. 先进先出 B. 先进后出 7. 向一个栈顶指针为HS的链栈中插入一个s所指结点时，则执行__ __。 (不带空的头结点) A. HS—＞next=s; B. s—＞next= HS—＞next; HS—＞next=s; C. s—＞next= HS; HS=s; D. s—＞next= HS; HS= HS—＞next; 8. 从一个栈顶指针为HS的链栈中删除一个结点时，用x保存被删结点的值，则执行__ __。(不带空的头结点) A. x=HS; HS= HS—＞next; B. x=HS—＞data; C. HS= HS—＞next; x=HS—＞data; D. x=HS—＞data; HS= HS—＞next; 9. 一个队列的数据入列序列是1，2，3，4，则队列的出队时输出序列是____ 。 A. 4，3，2，1 B. 1，2，3，4 C. 1，4，3，2 D. 3，2，4，1 10. 判定一个循环队列QU（最多元素为m0）为空的条件是____。 A. rear - front= =m0 B. rear-front-1= =m0 C. front= = rear D. front= = rear+1 11. 判定一个循环队列QU（最多元素为m0, m0= =Maxsize-1）为满队列的条件是____。 A. ((rear- front)+ Maxsize)% Maxsize = =m0 B. rear-front-1= =m0 C. front= =rear D. front= = rear+1 12. 循环队列用数组A[0，m-1]存放其元素值，已知其头尾指针分别是front和rear，则当前队列中的元素个数是____。 A. (rear-front+m)%m B. rear-front+1 C.rear-front-1 D. rear-front 13. 栈和队列的共同点是____。 A. 都是先进后出 B. 都是先进先出 C. 只允许在端点处插入和删除元素 D. 没有共同点 3.2 填空题（将正确的答案填在相应的空中） 1. 向量、栈和队列都是____结构，可以在向量的____位置插入和删除元素；对于栈只能在____插入和删除元素；对于队列只能在____插入元素和____删除元素。 2. 向一个长度为n的向量的第i个元素（1≤i≤n+1）之前插入一个元素时，需向后移动____个元素。 3. 向一个长度为n的向量中删除第i个元素（1≤i≤n）时，需向前移动____个元素。 4. 在具有n个单元的循环队列中，队满时共有____个元素。 习题答案 3.1 1. C 2. C 3. A 4. B 5.D 6. BA 7.C 8. B 9. C 10. C 11. A 12. A 13.C 3.2 1. 线性、任何、栈顶、队尾、队首 2. n-i+1 3. n-i 4. n-1 习题6 树和二叉树 6.1 单项选择题 1. 由于二叉树中每个结点的度最大为2，所以二叉树是一种特殊的树，这种说法____。 A. 正确 B. 错误 2. 假定在一棵二叉树中，双分支结点数为15，单分支结点数为30个，则叶子结点数为 个。 A．15 B．16 C．17 D．47 3. 按照二叉树的定义，具有3个结点的不同形状的二叉树有____种。 A. 3 B. 4 C. 5 D. 6 4. 按照二叉树的定义，具有3个不同数据结点的不同的二叉树有____种。 A. 5 B. 6 C. 30 D. 32 5. 深度为5的二叉树至多有____个结点。 A. 16 B. 32 C. 31 D. 10 6. 设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为_ ___。 A. 2h B. 2h-1 C. 2h+1 D. h+1 7. 对一个满二叉树，m个树叶，n个结点，深度为h，则____ 。 h A. n=h+m B. h+m=2n C. m=h-1 D. n=2 -1 8. 任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序____。 A.不发生改变 B.发生改变 C.不能确定 D.以上都不对 9. 如果某二叉树的前根次序遍历结果为stuwv，中序遍历为uwtvs，那么该二叉树的后序为____。 A. uwvts B. vwuts C. wuvts D. wutsv 10. 二叉树的前序遍历序列中，任意一个结点均处在其子女结点的前面，这种说法____。 A. 正确 B. 错误 11. 某二叉树的前序遍历结点访问顺序是abdgcefh，中序遍历的结点访问顺序是dgbaechf，则其后序遍历的结点访问顺序是____。 A. bdgcefha B. gdbecfha C. bdgaechf D. gdbehfca 12. 在一非空二叉树的中序遍历序列中，根结点的右边____。 A. 只有右子树上的所有结点 B. 只有右子树上的部分结点 C. 只有左子树上的部分结点 D. 只有左子树上的所有结点 13. 如图6.1所示二叉树的中序遍历序列是____。 A. abcdgef B. dfebagc C. dbaefcg D. defbagc a a b c b c d g d e f e 图6.1 h g f 14. 一棵二叉树如图6.2所示，其中序遍历的序列为__ __。 a 图6.2 A. abdgcefh B. dgbaechf C. gdbehfca D. abcdefgh 15．设a,b为一棵二叉树上的两个结点，在中序遍历时，a在b前的条件是 。 A．a在b的右方 B．a在b的左方 C．a是b的祖先 D．a是b的子孙 16. 已知某二叉树的后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是____。 A. acbed B. decab C. deabc D. cedba 17. 实现任意二叉树的后序遍历的非递归算法而不使用栈结构，最佳方案是二叉树采用____存储结构。 A. 二叉链表 B. 广义表存储结构 C. 三叉链表 D. 顺序存储结构 18. 如图6.3所示的4棵二叉树，____不是完全二叉树。 (A) (B) (C) (D) 图6.3 20. 在线索化二叉树中，t所指结点没有左子树的充要条件是____。 A. t—＞left=NULL B. t—＞ltag=1 C. t—＞ltag=1且t—＞left=NULL D. 以上都不对 21. 二叉树按某种顺序线索化后，任一结点均有指向其前驱和后续的线索，这种说法____。 A. 正确 B. 错误 22. 二叉树为二叉排序树的充分必要条件是其任一结点的值均大于其左孩子的值、小于其右孩子的值。这种说法____。 A. 正确 B. 错误 23. 具有五层结点的二叉平衡树至少有____个结点。 A. 10 B. 12 C. 15 D. 17 24. 树的基本遍历策略可分为先根遍历和后根遍历；二叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历。这里，我们把由树转化得到的二叉树叫做这棵数对应的二叉树。结论____是正确的。 A.树的先根遍历序列与其对应的二叉树的先序遍历序列相同 B.树的后根遍历序列与其对应的二叉树的后序遍历序列相同 C.树的先根遍历序列与其对应的二叉树的中序遍历序列相同 D.以上都不对 25. 树最适合用来表示____。 A. 有序数据元素 B. 无序数据元素 C. 元素之间具有分支层次关系的数据 D. 元素之间无联系的数据 6.2 填空题（将正确的答案填在相应的空中） 1. 有一棵树如图6.5所示，回答下面的问题： ⑴ 这棵树的根结点是____； ⑵ 这棵树的叶子结点是____； k1 ⑶ 结点k3的度是____； k 2 k 4 k ⑷ 这棵树的度是____； 3 ⑸ 这棵树的深度是____； k 5 k 6 ⑹ 结点k3的子女是____； ⑺ 结点k3的父结点是__ 图6.5 一棵树 k 7 2. 指出树和二叉树的三个主要差别____、____、____。__； 3. 从概念上讲，树与二叉树是两种不同的数据结构，将树转化为二叉树的基本目的是___ _。 4. 一棵二叉树的结点数据采用顺序存储结构，存储于数组t中，如图6.6所示，则该二叉树的链接表示形式为__ __。 5. 深度为k的完全二叉树至少有____个结点。至多有____个结点，若按自上而下，从左到右次序给结点编号（从1开始），则编号最小的叶子结点的编号是____。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 e a f d g c j l h b 图6.6 一棵二叉树的顺序存储数组t 6. 在一棵二叉树中，度为零的结点的个数为n 0，度为2的结点的个数为 n 2，则有n0=____。 7. 一棵二叉树的第i（i≥1）层最多有____个结点；一棵有n（n>0）个结点的满二叉树共有____个叶子和____个非终端结点。 8. 结点最少的树为____，结点最少的二叉树为____。 9. 现有按中序遍历二叉树的结果为abc，问有____种不同形态的二叉树可以得到这一遍历结果，这些二叉树分别是____。 10. 由如图6.7所示的二叉树，回答以下问题： ⑴ 其中序遍历序列为____； a ⑵ 其前序遍历序列为____； ⑶ 其后序遍历序列为____； b c de f h 6.3 简答题 i 1. 根据二叉树的定义，具有三个结点的二叉树有5种不同的形态，请将它们分别画出。 图6.7 一棵二叉树 2. 假设一棵 二叉树的先序序列为EBADCFHGIKJ和中序序列为ABCDEFGHIJK。 请画出该树。 3. 由如图6.7所示的二叉树，回答以下问题： a （1）画出该二叉树的中序线索二叉树； （2）画出该二叉树的后序线索二叉树； b c d （3）画出该二叉树对应的森林。 4. 已知一棵树如图6.8所示，转化为一棵二叉树，表示为____。 e f g 图6.8 一棵树 5. 以数据集{4，5，6，7，10，12，18}为结点权值，画出构造Huffman树的每一步图示，计算其带权路径长度为。 6. 一棵含有N个结点的k叉树,可能达到的最大深度和最小深度各为多少? 7. 证明:一棵满k叉树上的叶子结点数n0和非叶子结点数n1之间满足以下关系: n0=(k-1)n1+1 6.4 算法设计题 1. 编写按层次顺序（同一层自左至右）遍历二叉树的算法。 2．试编写算法，对一棵二叉树,统计叶子的个数。 3．试编写算法，对一棵二叉树根结点不变，将左、右子树进行交换，树中每个结点的左、右子树进行交换。 7. 假设用于通讯的电文仅有八个字母(a,b,c,d,e,f,g,h)组成，字母在电文中出现的频率分别为0.07, 0.19, 0.02, 0.06, 0.32, 0.03, 0.21, 0.10。试为这八个字母设计哈夫曼编码。 使用0-7的二进制表示形式是另一种编码方案。对于上述实例，比较两种方案的优缺点。 8. 试编写算法，对一棵以孩子-兄弟链表表示的树统计叶子的个数。假设一棵 二叉树的先序序列为EBADCFHGIKJ和中序序列为ABCDEFGHIJK。请画出该树。 习题答案 6.1 1. B 2. B 3. C 4. C 5. C 6. A 7. D 8. A 9. C 10. A 11. D 2. A 13. B 14. B 15. B 16. D 17. C 18. C 19. B 20. B 21. B 22. B 23. B 24. A 25. C 6.2 1. ⑴ k1 ⑵ k2,k5,k7,k4 ⑶ 2 ⑷ 3 ⑸ 4 ⑹ k5,k6 ⑺ k1 2. 树的结点个数至少为1(不同教材规定不同)，而二叉树的结点个数可以为0； e 树中结点的最大度数没有限制，而二叉树结点的最大度数为2； 树的结点无左、右之分，而二叉树的结点有左、右之分； af 3. 树可采用孩子-兄弟链表（二叉链表）做存储结构，目的并利用二叉树的已有算法解 d g 决树的有关问题。 4. 如图6.9所示 c l h j k-1kk-2 5. 2 、 2 -1 、 2 +1 6. n2+1 i-1[logn+1]-1[logn+1]b 7. 2 22 22 –1 图6.9 8. 只有一个结点的树；空的二叉树 9. 5；如图6.10所示 c b a ac a b a c c b a b c b 图6.10 树形5种 10. dgbaechif 、abdgcefhi 、gdbeihfca 、 6.3 1. 5种, 图6.11 2. 二叉树如图6.12所示。 E 图6.11 树形5种 BF D C G H I K 3. 中序线索二叉树如图6.13（左）所示；后序该二叉树转换后的的森林如图6.14所示。 aa bcNULLA线索二叉树如图6.13（右）所示； bca 图6.12 fc e j J f defdeb h i d 4. 图6.8的树转化为一棵二叉树如下，图6.15： jhNULLjha i图8.18 中序和后序线索树i图 6.14 b 对应的森林 c e d i g 图 6.15 一棵树的孩子兄弟表 5. 画出构造Huffman树如图6.16所示，计算其带权路径长度为 。 6. 一棵含有N个结点的k叉树,可能达到的最大深度 h=N-k+1 ， 最小深度各为: logkN+1。 62 37 25 19 13 18 12 10 9 7 6 4 5 图6.16 Huffman树 图6.13 习题7 图 7.1 单项选择题 1．在一个图中，所有顶点的度数之和等于所有边数的____倍。 A. 1/2 B. 1 C. 2 D. 4 2．任何一个无向连通图的最小生成树 。 A.只有一棵 B.有一棵或多棵 C.一定有多棵 D.可能不存在 3．在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的____倍。 A. 1/2 B. 1 C. 2 D. 4 4．一个有n个顶点的无向图最多有____条边。 A. n B. n(n-1) C. n(n-1)/2 D. 2n 5．具有4个顶点的无向完全图有____条边。 A. 6 B. 12 C. 16 D. 20 6．具有6个顶点的无向图至少应有____条边才能确保是一个连通图。 A. 5 B. 6 C. 7 D. 8 7．在一个具有n个顶点的无向图中，要连通全部顶点至少需要____条边。 A. n B. n+1 C. n-1 D. n/2 8．对于一个具有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是____。 22 A. n B. (n-1) C. n-1 D. n 9．对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则表头向量的大小为_①___；所有邻接表中的接点总数是_②___。 ① A. n B. n+1 C. n-1 D. n+e ② A. e/2 B. e C.2e D. n+e 10．已知一个图如图7.1所示，若从顶点a出发按深度搜索法进行遍历，则可能得到 的一种顶点序列为__①__；按宽度搜索法进行遍历，则可能得到的一种顶点序列 为__②__。 ① A. a,b,e,c,d,f B. e,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 a c b e f d 图 7.1 一个无向图 11．已知一有向图的邻接表存储结构如图7.2所示。 3 2 ^ 1 2 ^ 4 5 ^ 3 4 ^ 4 ^ 2 5 图7.2 一个有向图的邻接表存储结构 ⑴ 根据有向图的深度优先遍历算法，从顶点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 ⑵ 根据有向图的宽度优先遍历算法，从顶点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 12．采用邻接表存储的图的深度优先遍历算法类似于二叉树的____。 A. 先序遍历 B. 中序遍历 C. 后序遍历 D. 按层遍历 13．采用邻接表存储的图的宽度优先遍历算法类似于二叉树的____。 A. 先序遍历 B. 中序遍历 C. 后序遍历 D. 按层遍历 14．判定一个有向图是否存在回路除了可以利用拓扑排序方法外，还可以利用____。 A. 求关键路径的方法 B. 求最短路径的Dijkstra方法 C. 宽度优先遍历算法 D. 深度优先遍历算法 15．关键路径是事件结点网络中 。 A.从源点到汇点的最长路径 B.从源点到汇点的最短路径 C.最长的回路 D.最短的回路 16．下面不正确的说法是 。 （1）在AOE网中，减小一个关键活动上的权值后，整个工期也就相应减小； （2）AOE网工程工期为关键活动上的权之和； （3）在关键路径上的活动都是关键活动，而关键活动也必在关键路径上。 A.（1） B.（2） C.（3） D.（1）、（2） 17．用DFS遍历一个无环有向图，并在DFS算法退栈返回时打印出相应的顶点，则输出的顶点序列是 。 A.逆拓朴有序的 B.拓朴有序的 C.无序的 18．在图7.3所示的拓朴排列的结果序列为 。 A.125634 B.516234 C.123456 D.521634 图7.3有向图 19．一个有n个顶点的无向连通图，它所包含的连通分量个数为 。 A.0 B.1 C.n D.n+1 20．对于一个有向图，若一个顶点的入度为k1,、出度为k2，则对应邻接表中该顶点单链表中的结点数为 。 A.k1 B.k2 C.k1-k2 D.k1+k2 21．对于一个有向图，若一个顶点的入度为k1,、出度为k2，则对应逆邻接表中该顶点单链表中的结点数为 。 A.k1 B.k2 C.k1-k2 D.k1+k2 7.2 填空题（将正确的答案填在相应饿空中） 1．n个顶点的连通图至少____条边。 2．在无权图G的邻接矩阵A中，若(vi,vj)或＜vi,vj＞属于图G的边集合，则对应元素A[i][j]等于____，否则等于____。 3．在无向图G的邻接矩阵A中，若A[i][j]等于1，则A[j][i ]等于____。 4．已知图G的邻接表如图7.4所示，其从顶点v1出发的深度有限搜索序列为____，其从顶点v1出发的宽度优先搜索序列为____。 v5 v4 v2 v1 v2 v5 v3 v3 v6 v4 ^ v5 v4 v6 v3 v6 ^ 图7.4 图G的邻接表 5．已知一个有向图的邻接矩阵表示，计算第i个结点的入度的方法是____。 6．已知一个图的邻接矩阵表示，删除所有从第i个结点出发的边的方法是____。 7．如果含n个顶点的图形成一个环，则它有 棵生成树。 8．一个非连通无向图，共有28条边，则该图至少有 个顶点。 9．遍历图的过程实质上是 。BFS遍历图的时间复杂度为 ，DFS遍历图的时间复杂度为 ，两者不同之处在于 ，反映在数据结构上的差别是 。 10．一个图的 表示法是唯一的，而 表示法是不唯一的。 11．有向图中的结点前驱后继关系的特征是 。 12．若无向图G的顶点度数最小值大于等于 时，G至少有一条回路。 13．根据图的存储结构进行某种次序的遍历，得到的顶点序列是 的。 7.3 综合题 1．已知如图7.5所示的有向图，请给出该图的: （1）每个顶点的入/出度； （2）邻接距阵； （3）邻接表； （4）逆邻接表； （5）强连通分量。 1 6 2 3 5 4 图7。5一个有向图 2．请用克鲁斯卡尔和普里姆两种算法分别为图7.6、图7.7构造最小生成树： （1） a 16 15 11 b 15 c 15 d 14 12 13 16 21 e 图7.6 f （2） 6 12 1 4 3 9 12 7 2 15 6 16 20 4 132 5 5 图7.73．试列出图7.8中全部的拓扑排序序列。 1 2 3 10 4 5 图7.8 6 4．请用图示说明图7.9从顶点a到其余各顶点之间的最短路径。 b 5 d 6 3 a 2 3 2 f 3 c e 5 图7.9 4 5．已知AOE网有9个结点：V1，V2，V3，V4，V5，V6，V7，V8，V9，其邻接矩阵如下： (1)请画出该AOE图。 (2)计算完成整个计划需要的时间。 (3)求出该AOE网的关键路径。 ∝ 6 4 5 ∝ ∝ ∝ ∝ ∝ ∝ ∝ ∝ ∝ 1 ∝ ∝ ∝ ∝ ∝ ∝ ∝ ∝ 1 ∝ ∝ ∝ ∝ ∝ ∝ ∝ ∝ ∝ 2 ∝ ∝ ∝ ∝ ∝ ∝ ∝ ∝ ∝ 9 7 ∝ ∝ ∝ ∝ ∝ ∝ ∝ ∝ 4 ∝ ∝ ∝ ∝ ∝ ∝ ∝ ∝ ∝ 2 ∝ ∝ ∝ ∝ ∝ ∝ ∝ ∝ 4 ∝ ∝ ∝ ∝ ∝ ∝ ∝ ∝ ∝ 习题答案 7.1 1. C 2.B 3.B 4. C 5. A 6. A 8.D 9. AC 10.DB 11. CB 12. A 13. D 14.D 16.A 17.A 18.B 19.B 20.B 21.A 7.2 1.n-1 2. 1;0 3. 1 4.v1,v2,v3,v6,v5, v4；v1,v2,v5,v4,v3, v6 5.求矩阵第i列非零元素之和 6. 将矩阵第i行全部置为零 7.n 8.9 9.对每个顶点查找其邻接点的过程；O（e）（e为图中的边数）；O（e）； 遍历图的顺序不同；DFS采用栈存储访问过的结点，BFS采用队列存储访问过 的结点。 10．邻接矩阵 邻接表 11．一个结点可能有若干个前驱，也可能有若干个后继 12．2 13．唯一 7.3 1. 1 5 6 2 4 2. 3 7.C 15.A (1)． （2） 3． a 11 b 13 15 c 14 d 12 f e 6 12 5 23644 1 52634 156234 5612343 516234 512634 512364 1 12 7 5 6 5 4 10 9 4． b W=5 2 a 3 c W=3 5．(1)该AOE图为： d 3 W=6 3 f W=9 4 e W=7 26157197421543428649(2)完成整个计划需要18天。 (3)关键路径为：（V1，V2，V5，V7，V9）和（V1，V2， V5，V8，V9，） 习题8 查找 8.1 单项选择题 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（n） B. O(nlog2n) C. O(n) D. O(log2n) 5.二分查找和二叉排序树的时间性能____。 A. 相同 B. 不相同 6.有一个有序表为{1，3，9，12，32，41，45，62，75，77，82，95，100}，当二分查找值82为的结点时，____次比较后查找成功。 A. 1 B. 2 C. 4 D. 8 7.设哈希表长m=14，哈希函数H(key)=key。表中已有4个结点： addr (15)=4; addr (38)=5; addr (61)=6; addr (84)=7 如用二次探测再散列处理冲突，关键字为49的结点的地址是____。 A. 8 B. 3 C. 5 D. 9 8.有一个长度为12的有序表，按二分查找法对该表进行查找，在表内各元素等概率情况下查找成功所需的平均比较次数为____。 A. 35/12 B. 37/12 C. 39/12 D. 43/12 9．对于静态表的顺序查找法，若在表头设置岗哨，则正确的查找方式为 。 A.从第0个元素往后查找该数据元素 B.从第1个元素往后查找该数据元素 C.从第n个元素往开始前查找该数据元素 D.与查找顺序无关 10．解决散列法中出现的冲突问题常采用的方法是 。 A.数字分析法、除余法、平方取中法 B.数字分析法、除余法、线性探测法 C.数字分析法、线性探测法、多重散列法 D.线性探测法、多重散列法、链地址法 11．采用线性探测法解决冲突问题，所产生的一系列后继散列地址 。 A.必须大于等于原散列地址 B.必须小于等于原散列地址 C.可以大于或小于但不能等于原散列地址 D.地址大小没有具体限制 12．对于查找表的查找过程中，若被查找的数据元素不存在，则把该数据元素插入到集合中。这种方式主要适合于 。 A.静态查找表 B.动态查找表 C.静态查找表与动态查找表 D两种表都不适合 13.散列表的平均查找长度 。 A.与处理冲突方法有关而与表的长度无关 B.与处理冲突方法无关而与表的长度有关 C.与处理冲突方法有关而与表的长度有关 D.与处理冲突方法无关而与表的长度无关 8.2 填空题（将正确的答案填在相应的空中） 1.顺序查找法的平均查找长度为____；折半查找法的平均查找长度为____；哈希表查找法采用链接法处理冲突时的平均查找长度为____。 2.在各种查找方法中，平均查找长度与结点个数n无关的查找方法是____。 3.折半查找的存储结构仅限于____，且是____。 4. 假设在有序线性表A[1..20]上进行折半查找，则比较一次查找成功的结点数为____，则比较二次查找成功的结点数为____，则比较三次查找成功的结点数为____，则比较四次查找成功的结点数为____，则比较五次查找成功的结点数为____，平均查找长度为____。 5. 对于长度为n的线性表，若进行顺序查找，则时间复杂度为____；若采用折半法查找，则时间复杂度为____； 6．已知有序表为（12，18，24，35，47，50，62，83，90，115，134），当用折半查找90时，需进行 次查找可确定成功；查找47时，需进行 次查找成功；查找100时，需进行 次查找才能确定不成功。 7．二叉排序树的查找长度不仅与 有关，也与二叉排序树的 有关。 8．一个无序序列可以通过构造一棵 树而变成一个有序树，构造树的过程即为对无序序列进行排序的过程。 9．平衡二叉排序树上任一结点的平衡因子只可能是 、 或 。 10． 法构造的哈希函数肯定不会发生冲突。 11．在散列函数H(key)=key%p中，p应取____。 12．在散列存储中，装填因子?的值越大，则____；?的值越小，则____。 2 8.3 综合练习题: 1. 画出对长度为10的有序表进行折半查找的判定树，并求其等概率时查找成功的平均查找长度。 4. 选取哈稀函数H（k）=（3k）MOD 11。用开放定址法处理冲突，di=i（（7k）MOD 10+1）（I=1，2，3，…）.试在0-10的散列地址空间中对关键字序列（22,41,53,46,30,13,01,67）造哈希表，并求等概率情况下查找成功时的平均查找长度。 5. 已知一组关键字{49，38，65，97，76，13，27，44，82，35，50}，画出由此生成的二叉排序树，注意边插入边平衡。 习题答案 8.1 1．B 2．C 3．C 4．D 5．B 6．C 7．D 8．B 9．C 10．D 11．C 12．B 13．C 8.2 1. （n+1）/2 、((n+1)*log2(n+1))/n-1 、1+?（?为装填因子） 2. 哈希表查找法 3. 顺序存储结构、有序的 4. 1、2、4、8、5、3．7 （依题意，构造一棵有序二叉树，共12个结点，第一层1个结点，第二层2个结点，第三层4个结点，第四层5个结点，则：ASL=（1*1+2*2+3*4+4*5）/12=37/12） 5. O（n）、O(log2n) 6．2、4、3 7．结点个数n、生成过程 8．二叉排序树 9．0、1、-1 10．直接定址 11．素数 12．存取元素时发生冲突的可能性就越大、存取元素时发生冲突的可能性就越小 习题9 排序 9.1 单项选择题 1. 在所有排序方法中，关键字比较的次数与记录的初始排列次序无关的是____。 A. 希尔排序 B. 起泡排序 C. 插入排序 D. 选择排序 2. 设有1000个无序的元素，希望用最快的速度挑选出其中前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. 38，46, 56，79， 40，84， C. 84，79，56，46，40，38 D. 84，56，79，40，46，38 5. 一组记录的关键码为（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 6. 一组记录的排序码为（25，48，16，35，79，82，23，40，36，72），其中含有5个长度为2的有序表，按归并排序的方法对该序列进行一趟归并后的结果为____。 A. 16，25，35，48，23，40，79，82，36，72 B. 16，25，35，48，79，82，23，36，40，72 C. 16，25，48，35，79，82，23，36，40，72 D. 16，25，35，48，79，23，36，40，72，82 7. 排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为____。 A. 希尔排序 B. 起泡排序 C. 插入排序 D. 选择排序 8. 排序方法中，从未排序序列中挑选元素，并将其依次放入已排序序列（初始时为空）的一端的方法，称为____。 A. 希尔排序 B. 归并排序 C. 插入排序 D. 选择排序 9. 用某种排序方法对线性表（ 25，84，21，47，15，27，68，35，20）进行排序时，元素序列的变化情况如下： ⑴ 25，84，21，47，15，27，68，35，20 ⑵ 20，15，21，25，47，27，68，35，84 ⑶ 15，20，21，25，35，27，47，68，84 ⑷ 15，20，21，25，27，35，47，68，84 则所采用的排序方法是____。 A. 选择排序 B. 希尔排序 C. 归并排序 D. 快速排序 10. 下述几种排序方法中，平均查找长度最小的是____。 A. 插入排序 B. 选择排序 C. 快速排序 D. 归并排序 11. 下述几种排序方法中，要求内存量最大的是____。 A. 插入排序 B. 选择排序 C. 快速排序 D. 归并排序 12. 快速排序方法在____情况下最不利于发挥其长处。 A. 要排序的数据量太大 B. 要排序的数据中含有多个相同值 C. 要排序的数据已基本有序 D. 要排序的数据个数为奇数 9.2 填空题 （将正确的答案填在相应的空中） 1. 在对一组记录（54，38，96，23，15，72，60，45，83）进行直接插入排序时，当把第7个记录60插入到有序表时，为寻找插入位置需比较____。 2. 在利用快速排序方法对一组记录（54，38，96，23，15，72，60，45，83）进行快速排序时，递归调用而使用的栈所能达到的最大深度为____，共需递归调用的次数为____，其中第二次递归调用是对____一组记录进行快速排序。 3. 在堆排序，快速排序和归并排序中，若只从存储空间考虑，则应首先选取____方法，其次选取____方法，最后选取____方法；若只从排序结果的稳定性考虑，则应选取____方法；若只从平均情况下排序最快考虑，则应选取____方法；若只从最坏情况下排序最快并且要节省内存考虑，则应选取____方法。 4. 在插入排序、希尔排序、选择排序、快速排序、堆排序、归并排序和基数排序中，排序是不稳定的有____。 5. 在在插入排序、希尔排序、选择排序、快速排序、堆排序、归并排序和基数排序中，平均比较次数最少的排序是____，需要内存容量最多的是____。 6. 在堆排序和快速排序中，若原始记录接近正序或反序，则选用____，若原始记录无序，则最好选用____。 7. 在插入和选择排序中，若初始数据基本正序，则选用____；若初始数据基本反序，则选用____。 8. 对n个元素的序列进行起泡排序时，最少的比较次数是____。 9.3 综合题 1. 以关键码序列（503,087,512,061,908,170,897,275,653,426），为例，手工执行以下排序算法，写出每一趟排序结束时的关键码状态： （1） 直接插入排序； （2） 希尔排序（增量d[1]=5）； （3） 快速排序； （4） 堆排序； （5） 归并排序； （6） 基数排序。 2. 判别以下序列是否为堆（小顶堆或大顶堆）。如果不是，则把它调整为堆（要求记录交换次数最少）。 (1）(100,86,48,73,35,39,42,57,66,21); (2)(12,70,33,65,24,56,48,92,86,33) (3)(103,97,56,38,66,23,42,12,30,52,06,20) (4)(05,56,20,23,40,38,29,61,35,76,28,100). 习题答案 9.1 1. D 2. C 3. A 4. B 5. C 6. A 7. C 8. D 9.D 10. C 11. D 12. C 9.2 1. 5 2. 2; 4; （23，38，15） 3. 堆排序、快速排序、归并排序、归并排序、快速排序、堆排序 4. 希尔排序、选择排序、快速排序和堆排序 5. 快速排序、基数排序 6. 堆排序、快速排序 7. 插入排序、选择排序 8. n-1