复习题库答案讲解

1、数据结构习题 习题一 选择题 1、算法分析的两个主要方面是：（ B ） A 正确性和简明性B 时间复杂度和空间复杂度 C数据复杂性和程序复杂性D 可读性和文档性 2、在数据结构中，从逻辑上可以把数据结构分成（ A动态结构和静态结构 C线性结构和非线性结构 3、计算机算法具备输入、输出和 A有穷性、确定性和稳定性 C有穷性、确定性和可行性 4、算法分析的目的是（ C）。 A找出算法的合理性 C分析算法的有效性以求改进 C）。 B 紧凑结构和非紧凑结构 D 逻辑结构和存储结构 C ）等 5 个特性： B可行性、可移植性和可扩充性 D易读性、稳定性和安全性 B 研究算法的输人与输出关系 D分析算法的

2、易懂性 二、填空题 1、数据结构是一门研究非数值计算的程序设计问题中计算机的 操作对象以及它 们之间的 关系 和运算等的学科。 2、线性结构中元素之间存在 一对一 的关系，树形结构中元素之间存在一对多 的关系，图形结构中元素之间存在 多对多 的关系。 3、_数据项 是数据不可分割的最小单元，是具有独立含义的最小标识单位。例 如构成一个数据元素的字段、域、属性等都可称之为_数据项 。 4、数据的 _存储结构 _指数据元素及其关系在计算机存储器内的表示。存储结构 _是逻 辑结构在计算机里的实现，也称之为映像。 5、所谓算法（ Algorithm ）是对特定问题求解方法和步骤的一种描述，它是指令的一

3、组 _有限序列 _，其中每个指令表示一个或多个操作。 三、问答题 1、用大 O 形式写出下面算法的时间复杂度： i0； s=0； while（s n） i+; s+=i; O（ n） 2、写出以下算法的时间复杂度： for （ i 0; im; i） for（j0 ; jt; j） cij=0 ； for（i=0；i m； i） for （j=o; jt; j+ ） for（ k=0；kn；k） cij ai k*bkj;O（mnt） 习题二 一、选择题 1在一个长度为 n的顺序表中删除第 i 个元素（ 0 in ）时，需要向前移动 （A ）个元素。 A n-iB n-i+1C n-i+1D

4、i+1 2从一个具有 n 个元素的线性表中查找其值等于x 的结点时，在查找成功的情况下， 需平均比较 （ D ）个元素结点。 An/2BnC （n-1）/2D（n +1）/2 3若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点，则 下列存储方式最节省运算时间的是（ A ）： A 带头结点的双循环链表B 双链表 C给出表头指针的单循环链表D单链表 4如果最常用的操作是取第 i 个结点及其前驱结点，那么下列存储方式最节省时间的 是（ C）： A单链表 B单循环链表 C顺序表 D双链表 （ A ） B双链表 D单链表 B一个有限序列，不可以为空 D一个无限序列，不可以为空 i 个

5、元素（0一 1Next） int n; p=head-next; /*p指向链表的第一个结点 */ n=0; while （p!=NULL） if （p-data=x） n+; p=p-next; return（n）; /* 返回结点个数 */ /*count_list*/ L 中值为 x 的结点的直接前驱结点。 2设计一个算法，删除单链表 DeleteNode( Node* L, int x) Node* p,q,r; p = q = r = L; while(p-next ! = NULL) p = p -next; if(p-data = x) break; r = q; q = p;

6、delete q; r-next = p; 3设计一个算法，将一个不带头结点的单链表L(至少有一个结点)逆置，即最后一 个结点变成第一个结点，原来倒数第二个结点变成第二个结点，如此等等。 void reverse_list( linklist* head ) /* 逆置带头结点的单链表 */ linklist * s, * p; p=head-next; /*p指向线性表的第一个元素 */ head-next=NULL; /*初始空表 */ while ( p != NULL ) s=p; p=p-next; s-next=head-next; head-next=s; /* 将 s 结点插入

7、逆表 */ /*reverse_list*/ 4 在一个带头结点的单链表中，头指针为 head ，它的数据域的类型为整型，而且按由 小到大的顺序排列，编写一个算法 insertx list ()，在该链表中插人值为 x 的元素， 并使该链表仍然有序。 linklist *insertx_list(linklist *head, int x) /* 在带头结点的单链表中插入值为 x 的元素，使该链表仍然有序 */ linklist *s, *p, *q; s=(linklist *)malloc(sizeof(linklist); /*建立数据域为 x 的结点 */ s-data=x; s-ne

8、xt=NULL; if (head-next=NULL | xnext-data ) /* 若单链表为空或 x 小于链表第一个结点的数据域 */ s-next=head-next; head-next=s; else q=head-next; p=q-next; while( p != NULL p=p-next; s-next=p; q-next=s; /*if*/ /*insertx_list 习题三 C）。 D e， d， c， ） b，a 、选择题 l一个栈的序列是： a，b， c， Aa，b，c，d， e Bd， 2判定一个栈 S（最多元素为 d，e，则栈的不可能输出的序列是（ e，

9、c， b，a Cd，c，e， a，b MaxSize ）为栈满的条件是： （ D A S top!= - 1 B S top=- 1 CS top=MaxSize -1 D 3若一进栈序列为 1，2，3，n，其出栈序列为 S top!=MaxSize -1 P1,P2,P3, Pn，如果 Pn=n,则 Pi 1 inext=s ； r=s； B r-next=s ； f=s； C s-next=r ； r=s； D s-next=f ； f=s； 5若用一个大小为 8 的一维数组来实现循环队列，且当前 front 和 rear 的值分别为 4 和 1，当从队列中删除一个元素，再加入两个元素后，

10、front 和 rear 的值分别是（ B ）： A 3和5 B 5和3 C 2 和 6D 6 和 2 6 判断一个循环队列 MaxSize ）为空的条件是： （A ） Q（最多元素为 A Q-front=Q-rear B Q-front= ( Q-rear +1) %MaxSize C Q-front!=Q-rear D Q-front!= ( Q-rear +1) %MaxSize 7 向一个带头结点、栈顶指针为 top 的链栈中插人一个 *S 结点的时候， 应当执行语句 C )。 A top-next=S ；B S-next=top ； top=S； C S-next=top-next

11、； top-next=S ； D S-next=top ； top=S-next ； 8在一个链队列中，假定 front 和 rear 分别为头指针和尾指针，则插入一个结点*S 的 操作是（ C ）。 A front front-next C rear-next=S ； rear=S 9栈与队列都是（ C ）。 A链式存储的线性结构 C限制存取点的线性结构 10若进栈序列为 l， 2，3，4，则（ B S-next=rear ； rear=S D S-next=front ； front S B链式存储的非线性结构 D限制存取点的非线性结构 C ）不可能是一个出栈序列。 A 3，2，4，1 B

12、l，2，3，4C 4，2，3，1D4，3，2，l 11在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印数据缓冲区， 主机将要输出的数据依次写人该缓冲区， 而打印机则从该缓冲区中取走数据打印。 该缓冲区 应该是一个（ B ）结构。 A 堆栈B队列C数组 D线性表 、填空题 1栈和队列的共同点是 都是限制存取点的线性结构 。 2通常元素进栈的操作是 先进后出或后进先出 。 3栈（ stack）是限定在 表尾 一端进行插人或删除操作的线性表。在栈中，允许插人 和删除操作的一端称为 栈顶 _，而另一端称为 栈底 _。不含元素的栈称为 _空栈 。 4队列( Queue)也是一种 特殊的线性表

13、 _，但它与栈不同，队列中所有的插人均限 定在表的一端进行，而所有的删除则限定在表的另一端进行。允许插人的一端称为队尾 _ 允许删除的一端称为 队头 _。 5队列中允许进行删除的一端称为 队头 _；允许进行插入的一端称为 _队尾 三、问答题 1设有一个数列的输入顺序为 abcdef，若采用栈结构，并以 J 和 C 分别表示进栈和出栈操 作，试问下列输出序列是否是合法序列？如是，请用进栈和出栈操作表示其合法序列。 (1) 能否得到输出顺序为 cbefda 的序列？ J(a),J(b),J(c),C( ),C( ),J(d),J(e),C( ),J(f),C( ),C( ),C( ) (2) 能否

14、得到输出顺序为 aedfbc154623 的序列？ 不能 2设输入元素为 4、5、 6、B、A，入栈次序为 456BA ，元素经过栈后到达输出序列，当所 有元素均到达输出序列后，有哪些序列可以作为高级语言的变量名？ 3假设 Q0 10 是一个线性队列，初始状态为 front=rear=0 ，画出做完下列操作后队列的 头尾指针的状态变化情况，若不能入队，请指出其元素，并说明理由。 (1) d，e，b，g，h 入队 (2) d，e 出队 (3) i，j，k，l，m 入队 (4) b 出队 (5) n，o，p 入队 4设有 4个元素 A、B、C 和D 进栈，给出它们所有可能的出栈秩序。 14种 A、

15、 B、 C、 D A、 B、 D、 C A、 C、 B、 D A、 C、 D、B A 、 D、 C、 B B、 A、 C、 D B、 A、 D、 C B、 C、 A、 D B、 C、 D、A B、 D、 C、 A C、 B、 A、 D C、 B、 D、 A C、 D、 B、 A D、 C、 B、A 四、程序设计题 1假设表达式中有三种括号：圆括号“ ()”、方括号“ ”和花括号“ ”用 C语言编 写程序判断读人的表达式中不同括号是否正确配对，假定读人的表达式以”#”结束。 #include stdio.h #include stdlib.h #define FALSE 0 #define TR

16、UE 1 #define LEN sizeof( struct node ) struct node char data; struct node *next; ; typedef struct node *stack; void push_stack(stack *, char ); int pop_stack(stack *); void main() stack s; int valid=TRUE; char ch,symble; symble=getchar(); s=NULL; push_stack( while (symble != # ) else if (symble=( |

17、symble= | symble= ) push_stack( symble=getchar(); else if ( s=NULL ) valid=FALSE; else ch=pop_stack( symble=getchar(); else valid=FALSE; if ( valid = TRUE ) printf( The string is valid. n); else printf(The string is valid. n); void push_stack( stack *topptr, char ch ) stack newptr; newptr=(struct no

18、de * ) malloc( LEN ); newptr-data=ch; newptr-next=*topptr; *topptr=newptr; int pop_stack( stack topptr ) stack tempptr; char popvalue; if (topptr!=NULL ) tempptr=topptr; popvalue=topptr-data; topptr=topptr-next; free( tempptr ); return popvalue; else return 0; 习题四 、选择项 4设有两个串 S2， S1，那么求串 S2 在 S1 中首次

19、出现的位置的运算称为： （ C ） A求子串B求串长 C模式匹配 D 串连接 4设有串 S=Computer ，则其子串的数目是（ B ）。 A36B 37C8D9 4下列是 C 语言中“ ASDF567HJKL ”子串的是：（ C ） AASDFBDF56 C“F567HJ”D“DFHJ ” 5空串与空格串（ B ）。 A相同B不相同C可能相同D 无法确定 、境空题 其中， S称为串名_；串中的 Ci（1=i0) ， 2串中字符的个数称为 串的长度 _。 3不含有任何字符的串称为 空串 _，它的长度为 _0_。 4由一个或多个空格构成的串称为 空白串 _，它的长度为 所含空格的个数 _。 5

20、串中任意多个连续字符组成的子序列称为该串的字串_；包含 字串 _的串称为主串。 三、问答题 1、现有串 s1=ABCD123 ， s2=abcde，假设函数 con（x,y）返回 x 和 y 串的连接串， 函数 subs（s,i,j） 返回串 s 的从序号 i 的字符开始的 j 个字符组成的子串，函数 len（s）返回串 s 的长度，求： ( 1) L1=subs(s1,2,len(s2) ( BCD12 ) ( 2) L2=subs(s1,len(s2),2)( 12) (3) con(L1,L2)(ABCD123abcde ) 四、程序设计题 l编写算法实现将窜 S1 中的第 i 个字符到

21、第 j 个字符之间的字符 (不包括第 i 个字符 和第 j 个字符 )之间的字符用串 S2 替换。假设串的存储结构为： define MAXSIZE 81 struct string intlen ； char ch MAXSIZE ； stringtype ； void replace (stringtype s1, int i, int j, stringtype s2) stringtype s100; int h,k; if ( i=h h=i; h+ ) s.chh=s1.chh; /* 把 s1 的前 i 个字符赋值给 s*/ s.len=i; h=1; while(hs2.len

22、) /* 连接串 s2*/ s.chs.len+h=s2.chh; h+; s.len=s.len+s2.len; for ( k=s.len+1; h=j; h1）个 相同类型数据 的有序组合，数组中的数据是按顺序存 储在一块 地址连续 _的存储单元中。 2数组中的每一个数据通常称为 数组元素 ， _数组元素 _用下标区分，其中下标 的个数由数组的 维数 决定。 3广义表是 n（ n=0 ）个元素的序列。记作： A（a1，a2， an），其中， A 是广义 表的 名称 ，n 是它的 长度 _，当 n=0 的时候称为 空表 _ 。 4广义表的深度一般定义为广义表元素最大的层数 _，或者说是广义

23、表 括号的层数 _。 利用递归的定义，广义表的深度就是所有子表中 最大深度加 1_。 10 三、问答题 1现有一个稀疏矩阵如下图所示，写出其对应的三元组表示，并求出其转置矩阵的三元组 表示。 1 0 0 0 0 0 (1,2,2 )，(2，3， 4 0 -3 ），（3,1,1 ），（3,4,4 ） (1,3,1 )，(2,1,2 ) ,(3,2,-3),(4,3,4) ) 2写一个创建稀疏矩阵相应三元组的算法。 #define MAXSIZE 1000 /*假设非零元个数的最大值是 1000*/ typedef struct int i, j; elemtype v; triple; type

24、def struct triple dataMAXSIZE+1; /*data0 用于存放稀疏矩阵行，列和非零元个数 */ int mu, nu, tu; /*稀疏矩阵行、列和非零元的个数 */ spmatrix; spmatrix a; void CreatTripleTable (int array_aMN,spmatrix a) /*array_a 是一个稀疏矩阵 ,a 是产生的相对应的三元组存储 */ int i,j,k=1; for (i=0;iM;i+) /* 按行优先顺序扫描 array_a 的元素 , 不为 0 者存入 B 中 */ for (j=0;jleft=0 D t-l

25、eft=NULL 且 t-ltag=1 3在线索化二叉树中， A t-left=NULL Ct-ltag=1 4设深度为 h 的二叉树上只有叶子结点和同时具有左右子树的结点， 含的结点数目至少为（ D 则此类二叉树中所包 A2h B2h C2h1 D2h-l 5二叉村第 k 层上最多有（ C ）个结点。 A2k B2k-1 k-1 C2k-1 D 2k- 6二叉树的深度为 k，则二叉树最多有（ D ）个结点。 A2k B2k-1 C2k-1 k D 2 - ）。 1 7设某一二叉树先序遍历为 A abdec 8设某一二叉树中序遍历为 A adbec 9 N 个结点的线索二叉树中， abdec，

26、中序遍历为 B debac badce，后序遍历为 B decab 线索的数目是（ 1 dbeac，则该二叉树后序遍历的顺序是 CdebcaD abedc bdeca，则该三叉树先序遍历的顺序是 C debac D abode C ）。 D ）。 B ）。 C2N 的先序遍历是 T2 的 C后序 的后序遍历是 T2 的 C后序 AN-1BN 1 将一棵树 T 转换为一棵二叉树 T2 ， A 先序B 中序 将一棵树 T 转换为一棵二叉树 T2 ， A先序 设一棵二叉树度 A6 一棵非空的二叉树，先序遍历与后序遍历正好相反，则该二叉树满足（ A 无左孩子 C只有一个叶子结点 14线索二叉树是一种（

27、 D A逻辑结构 C逻辑和线性结构 15权值为 l， 2， 6，8的四个结点构成的哈夫曼树的带权路径长度是（ A29B 31C 17D20 10 11 12 13 则T 则T B中序 2 的结点数是 7 ， B7 D 2N1 A ）。 D无法确定 B ）。 D无法碉定 度为 1 的结点数是 6，则叶子结点数是（ 9 C C8 D ）。 ）。 ）。 B无右孩子 D任意二叉树 B线性结构 D物理结构 ）。 、填空题 1树 （Tree）是 n（n 0）个结点的 _有限 _集。 2深度为 5 的二叉树至多有 31 个结点。 3树中任意结点允 许有零个或多个孩子结点，除根结点以外,其余结点都有 12 双

28、亲结点。 4在一棵二叉树中， 度为零的结点个数为 n0，度为 2 的结点个数为 n2,那么 n0=n2+1 5结点的度是指结点所拥有的 子树的数目 。 6一个结点的子树中的任一结点都称为该结点的 子孙结点 _。 7从根到该结点所经分支上的所有结点称为该结点的祖先结点 。 8具有 同一双亲 的结点互称为兄弟结点，简称为兄弟。 9从根结点开始定义，根为 _第一 _层，根的孩子为 _第二_层，依次往下类推，若 某结点在第 k 层，则其子树的根就在 _第 k+1_ 层。 10如果树中各结点的各子树无排列顺序，即可以互换位置，则称为该树为无序树 11二又树( Binary Tree )是结点的有限集合，

29、这个集合或者是空，或者是由一个根结 点和 两棵互不相交 _的称为 _左子树 _和 _右子树 _的二叉树构成。 12二叉树第 i 层上最多有 _2*i-1_ 个结点。 13深度为 k 的二又树最多有 个结点 (k l)。 14在任意二叉树中， 叶子结点的数目 (即度为 0的结点数 )等于度为 2的结点数 加 1_ 15一棵深度为 k 且具有 2k-1 个结点的二叉树称为 满二叉树 ，这类二叉树的特点是， 二叉树中每一层结点的个数都是 _最大结点 的个数。 16 _完全二叉树 是那种在一棵二叉树中，除最后一层外，若其余层都是满的，并且最 后一层或者是满的，或者所缺少的结点都在右边。 17具有 n

30、个结点的完全二叉树的深度是 _ log2 n 1。 18先序遍历二叉树的操作定义为：若二叉树为空，则为空操作；否则进行如下操作： 访问二叉树 根结点 ；先序遍历二叉树 左子树 ；先序遍历二叉树 _右子树 19中序遍历二叉树的操作定义为：若二叉树为空，则为空操作；否则进行如下操作： 中序遍历二叉树 _左子树 ；访问二又树 _根结点 ；中序遍历二又树 右子树 。 20后序遍历二叉树的操作定义为：若二叉树为空，则为空操作；否则进行如下操作： 后序遍历二叉树 _ 左子树 ；后序遍历二叉树 _右子树 _；访问二叉树 _根结点 _ 。 21线索二叉树( Threaded Binary Tree)是充分利用

31、二义链表的n+1 个空的指针域作 为线索来标志每一个结点的 前驱_和_后继_信息。当某个结点有左孩子的时候， 使其 _左指 针域 _指向其左孩子， 无左孩子的时候， 使其左指针域指向该结点的 直接前驱结点 _；当某个 结点有有孩子的时候，使其右指针域指向该结点的右孩子 _，无右孩子的时候，使其有指针 域指向该结点的 直接后继结点 _。 22线索二叉树的线索链表中，指向结点前驱和后继的指针称为线索 ；加上线索 的二叉树称为 线索二叉树 ；对二叉树以某种次序进行遍历使其成为线索二叉 树的过程称为 线索化 。 23哈夫曼树( Huffman Tree )又称 最优二叉树 。它是 n 个带权叶子结点构

32、成的所有二 叉树中，带权路径长度 WPL_ 最小的二叉树 。 三、问答题 1一棵树表达成如下形式： DA ，B，C，D，E，F，G， H，I，J，K，L，M ，N，O R=A，B，A，C，A，D，B，E，B，F， C，G，D，H， D，I， D ， J， K ， F， K，L， F， M ， I，N， I，O 13 其中 D 为结点集合， R 为边的集合。请根据以上内容回答以下问题： (1) 画出这棵树。 (2) 该树的根结点是哪一个？ (3) 哪些是叶子结点？ (4) F 结点的双亲是谁？ (5) F 结点的祖先是哪些？ (6) F 结点的孩子是哪些？ (7) F 结点的兄弟是哪些？ (8)

33、 F 结点的堂兄弟是哪些？ (9) F 结点的度是多少？ (10) F 结点的层次是多少？ (11) D 结点的子孙有哪些？ (12) 以结点 D 为根的子树度是多少？ (13) 以结点 D 为根的子树层是多少？ (14) 该树的层是多少？ (15) 该树的度是多少？ 2画出图 6-1 中树的二叉树表示形式。 a) 图 6-l 3已知某二叉树的先序遍历的结果是： A，B，D，QC，E，H，L，I，K，M，F和 J， 它的中序遍历的结果是： QD，B，A，L，H，E，K，LM，C，F和 J，请画出这棵二叉树， 并且写出该二叉树后序通历的结果。 4设 A、B、C、D、E、F 六个字母出现的概率分别

34、为 7,19,2,6,32,3 ，构建哈夫曼树 (请 按左子树根结点的权小于等于右子树根结点的权的次序构造) ，计算出带权路径长度 WPL， 并设计每个字母的哈夫曼编码 5假设一棵二叉树的后序序列为 DCEGBFHKJI，A 中序序列为 DCBGEAHFIJ，K请完成下列 操作：(1)画出该二叉树； (2) 写出该二叉树的先序遍历序列； ( 3)画出该二叉树的中序遍 历线索二叉树。 6假设一棵二叉树的先序序列为 ABDGCEHLIKMFJ ，中序序列为 GDBALHEKIMCFJ ， 请完成下列操作。 (1) 画出该二叉树； (2) 写出该二叉树的后序遍历序列； (3) 画出该二叉树的中序遍历

35、线索二叉树。 7假设通讯电文中只用到 A，B，C，D，E，F 六个字母，它们在电文中出现的相对频率 分别为： 7，2，15，9，4，19，要求画出哈夫曼树(请按左子树根结点的权小于等于右子树 根结点的权的次序构造) ，并计算出带权路径长度 WPL，试设计每个字母的哈夫曼编码。 14 8有七个带权结点 , 其权值分别为 2,6,7,1,5,9,13, 试以它们为叶子结点构造一棵哈夫 曼树（请按照每个结点的左子树根结点的权小于等于右子树根结点的权的次序构造） , 并计 算出带权路径长度 WP。L 9假设一棵哈夫曼树共有 n0个叶子结点，试证明树中共有 2no-l 个结点。 10假设通信用的报文由

36、9个字母 A、B、C、D、E、F、G、H和 I 构成，它们出现的 频率分别是： 10、 20、 5、 15、 8、 2、3、 7和 30。请用这 9个字母出现得频率作为权值求： （l）设计一棵哈夫曼树。 （ 2）计算其带权路径长度 WPL 值。 （3）写出每个字符的哈夫曼编码。 四、程序设计题 1. 自己设计一棵二叉树，编写一个完整的程序，输出该二叉树的先序、中序和后序序 列。（程序中应包括二叉树的生成函数，先序、中序、后序遍历函数） 。 2已知一棵二叉树的先序遍历序列和中序遍历序列，请写出根据二又树先序遍历序列 和中序遍历序列构造一棵二叉树的算法。 15 习题七 、选择题 1在一个无向图 G

37、 中，所有顶点的度数之和等于所有边数之和的( C )倍。 A l/2B 1C2D4 2对某个无向图的邻接矩阵来说： ( A) A 第 i 行上的非零元素的个数和第 i 列上的非零元素的个数一定相等 B矩阵中的非零元素的个数等于图中的边数 C第 i 行上、第 i 列上非零元素的总数等于顶点 Vi 的度数 D矩阵中非全零行的行数等于图中的顶点数 3采用邻接表存储的图的深度优先遍历算法类似于二叉树的：( A ) A 先序遍历 B中序遍历 C后序遍历 D按层遍历 4 在一个具有 n 个顶点的无向图中，要连通全部顶点至少需要 条边： ( A ) A n-1 Bn Cn+1 D n/2 5 在一个有向图中

38、，所有顶点的入度之和等于所有顶点的出度之和的( B )倍。 Al/2 B1 C 2 D 4 6 一个具有 n 个顶点的无向图包含( C )条边。 An Bn1 C n-1 D n/2 7 一个具有 n 个顶点的无向完全图包含( C )条边。 A n(n-l) B n(n+l) C n(n-l)/2 D n(n-l)/2 8. 一个具有 n 个顶点的有向完全图包含( A )条边。 An(n-1) Bn(n+l) C n(n-l)/2 D n(n+l)/2 9 无向图的邻接矩阵是一个( A )。 A 对称矩阵B 零矩阵 C 上三角矩阵 D 对角矩阵 、填空题 1在图中，任何两个数据元素之间都可能存

39、在关系，因此图的数据元素之间是多对多 的关系。 2在有 n 个顶点的有向图中，至多有N(N-1) 条边。 3具有 10 个顶点的无向图，边的总数最多为45 。 4在一个具有 n 个顶点的无向图中，要连通全部顶点至少需要 n-1 条边。 5具有 n (n-1)/2 条边的无向图称为 _无向完全图 ，简称为 完全图 ， 其中 n 表示无向图中顶点的个数， n(n-1)/2 是具有 n 个顶点无向图所拥有边的 最大数目 _。 6具有 n 个顶点的有向图，如果它同时具有 n(n-1) 条弧，则称该图为 有向完全图 _，其 中 n(n-1) 是具有 n 个顶点有向图所拥有弧的 最大数目 _。 7 如果图

40、中的边或弧带有权，则称这种图为网络 。 8顶点 v 的度定义为 _以该顶点为一个端点的边 的数目，记为 D(v) 。 9在有向图中，顶点 v 的度又分为 _入度_和_出度，入度_是以顶点 v 为 头的弧的数目，或者说是以该顶点为终点的边的数目，记为ID(v) ；_出度 是以顶点 v 为尾的弧的数目，或者说是以顶点为起点的边的数目，记为OD(v) ；顶点 v 的度是它的 _入 度_和_出度_之和，即 D(v)=ID(v) OD(v) 。 10 路径长度 _是指一条路径上所经过的边或弧的数目。 11若一条路径上除开始结点和结束结点外( 开始结点和结束结点也可以为不同顶点) ， 16 其余顶点均不相

41、同，则称该路径为 简单路径 。 12 若一条路径上的开始结点和结束结点为同一个顶点，则称该路径为回路 或_环。同时除了第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路称 简单回路 _或 简单环 。 13一个 _无环的有向图 _称为有向无环图，简称为 DAG 图。 三、问答题 1已知一个无向图的邻接矩阵如图所示， 请画出该无向图， 并写出从顶点 0 出发分别进 行深度优先和广度优先搜索遍历得到的顶点序列。 5依据以下无向图，使用普里姆算法，写出构造该图的最小生成树的过程。 G 的最小生成树的过程 17 习题八 一、选择题 1.顺序查找方法适合于存储结构为(D )的线性表 A. 散列存储B.

42、索引存储 C.散列存储或索引存储D.顺序存储或链接存储 2采用折半查找法查找长度为 n 的线性表时，每个元素的平均查找长度为： ( D ) A O(n2) BO(n log2n)CO(n) D O(log2n) 3对线性表进行折半查找时要求线性表必须：(B ) A以顺序方式存储 B 以顺序方式存储，且结点按关键字有序排序 C以链式方式存储 D 以链式方式存储，且结点按关键字有序排序 4可以在哈希查找过程中处理冲突的方法是：(B ) A 关键字比较法 B线性探查法 C数字分析法D 除留余数法 5.己知一个有序表为 (11,22,33,44,55,66,77, 88,99), 则折半查找元素 55

43、 需要比较 ( A )次。 D.4 A.1 B.2 C.3 6.顺序查找法与二分查找法对存储结构的要求是( D ) 。 A. 顺序查找与二分查找均只是适用于顺序表 B. 顺序查找与二分查找均既适用于顺序表 , 也适用于链表 C. 顺序查找只是适用于顺序表 D. 二分查找适用于顺序表 二、填空题 1. 折半查找 ( Binary Search) 又称为 二分查找 ， 是一种效率较高的一种 查找算法。 2. 分 块查找 (Blocking Search) 又称为索引顺序 查找 ，是一 种以索 引顺序 表 的形式来来进行的查找方法 。分块查找是 顺序查找 的一种改进 ，它是一种介于 顺序查找 和 折

44、半查找之间的查找方法。 3. 如果对查找表只进行查询某个 特定的 数据元素是否在查找表中 , 以及查找某 特 定的 数据元素的各种属性两种类型的基本操作, 而不进行插入和删除数据元素的查找表称 为 静态查找表 。 4. 如果在查找表中进行查找的过程中，同时插入查找表中不存在的数据元素，或者查 找表中删除已存在的某个数据元素，则称此类查找表为 动态查找表 。 5. 用折半法查找一个线性表时，该线性表必须具有的特点是 顺序存储结构的有序表 。 6. 在一个查找表中，能够惟一的标识一个数据元素( 或记录 )的关键字称为 主关键字 。 7. 二叉排序树 (Binary Sort Tree) ，又称为

45、二叉查找树 ，它或者是一棵空树，或者是具 有下列性质的一棵二叉树： (1) 若左子树不空，则左子树上所有结点的值 都小于根结点 的值 。 (2) 若右子树不空，则右子树上所有结点的值 都大于根结点的值 。 (3) 左右子树又分别是 二叉排序树 。 8. 对有序表 (25,30,32,38,47,54,62,68,90,95) 用二分查找法查找 32，则所需的比较次数 为 3 。 三、问答题 1输入一个正整数序列 3,45,91,25,14,76,56,65, 建立一棵二叉排序树，再从该树上删除 结点 76，请画出初始二叉排序树和删除结点后的二叉排序树。 18 2关键字序列 A=(36,27,68,33,97,40,81,24,23,90,32,14) 共 12 个数据，哈希表长为 13 ， 采用的哈希函数为 ：h (key) = key % 13 。如果采用开放定址的线性探测再散列方法解决冲突， 请构造哈希表并求其平均查找长度。 3已知一个顺序存储的有序表为 (17,25,33,37,47,53,59,65,73,77) ，试画出对应的折半查 找判定树，并求其平均查找长度。 4设有一组关键字 81,25,91,24,49,56,83,66 ，采用散列函数 h(key)=key % 11 ，采用线 性探查法解决冲突， 试在 010 的散列地址空