数据结构复习资料

1、第1章绪论一、填空题1 .数据结构就是一门研究非数值计算得程序设计问题中计算机得 以及它 们之间得 与 等得学科。2 .数据结构被形式地定义为（D,R）,其中D就是 得有限集合，R就是D上得 有限集合。3 .数据结构按逻辑结构可分为两大类，它们分别就是 与。若 细分为4类，分别就是、与_4 .线性结构中元素之间存在 关系，树形结构中元素之间存在 关 系，图形结构中元素之间存在 关系。5 .在线性结构中，第一个结点 前驱结点，其余每个结点有且只有 个 前驱结点；最后一个结点 后继结点，其余每个结点有且只有 个后继 结点。6 .在树形结构中，树根结点没有 结点，其余每个结点有且只有 个前驱 结点；

2、叶子结点没有后继结点，其余每个结点得后继结点数可以任意。7 .在图形结构中，每个结点得前驱结点数与后继结点数可以 。8 .数据结构包括数据得 、数据得 与数据得 这三个方面得内容。9 .数据得存储结构可用四种基本得存储方法表示，它们分别就是 、10 .数据得运算最常用得有 5种，它们分别就是 11 . 一个算法得效率可分为 效率与 效率。二、单项选择题1 .数据结构中，与所使用得计算机无关得就是数据得（）结构。C、逻辑D、物理与存储B、研究算法中得输入与输出得关系D、分析算法得易懂性与文档性B、正确性与简明性D、数据复杂性与程序复杂性B、排序方法A、存储B、物理2 .算法分析得目得就是（）。A

3、、找出数据结构得合理性C、分析算法得效率以求改进3 .算法分析得两个主要方面就是：（）。A、空间复杂性与时间复杂性C、可读性与文档性4 .计算机算法指得就是（）。A、计算方法C、解决问题得有限运算序列D、调度方法5 .计算机算法必须具备输入、输出与()等5个特性。A、可行性、可移植性与可扩充性B、可行性、确定性与有穷性C、确定性、有穷性与稳定性D、易读性、稳定性与安全性三、判断下列叙述得对错。1 .()数据元素就是数据得最小单位。2 .()数据结构就是数据对象与对象中数据元素之间关系得集合。3 .()数据结构就是具有结构得数据对象。4 .()算法与程序原则上没有区别，在讨论数据结构时二者就是通

4、用得。5 .()所谓数据得逻辑结构就是指数据元素之间得逻辑关系。6 .()数据得逻辑结构与数据元素本身得内容与形式无关。7 .()数据结构就是指相互之间存在一种或多种关系得数据元素得全体。8 .()从逻辑关系上讲，数据结构主要分为两大类：线性结构与非线性结构。 四、设n为正整数，分析下列各程序段中加下划线得语句得执行次数。(1) for (int i = 1 ; i <= n ; i+ )for (int j = 1; j <= n; j+)cij=0、0;for (int k = 1; k <= n; k+ )cij = cij + aik * b»；(2) x

5、= 0; y = 0 ;for ( int i = 1; i <= n; i+)for( int j = 1; j <= i; j+)for( int k = 1; k <= j; k+)x = x + y ； n inji i 2)/2=n(n+1)/4+n(n+1)(2n+1)/12=n(n+1)(3+2n+1)/12=n(n+1)(n+2)i 1 j 1i 1/6n(3) k=0;for(i=1; i<=n; i+)for(j=i; j<=n; j+)k+; i=1; j=0;while(i+j<=n) if(i>j) j+；else i+;(5

6、) x=n; y=0;while(x>=(y+1)*(y+1)y+ ;(6) x=91; y=100;while(y>0) if(x>100)x-=10;y-; else x+;五、分析下面各程序段得时间复杂度for (i=0; i<n; i+)for (j=0; j<m; j+)3、x=0;、闻般柳黑啊02、s=0;for i=0; i<n; i+)for(j=0; j<n; j+)；S= (D,R),试按各小题所给条件画出念些逻脚构彳3+=,如背 相对于关濡j瞰精+转是开始结点，哪些结点就是终端结点？ whiies<m=s ；并确定1.D=d

7、1，x+;3,d4R=(d1,d2),(d2,d3),(d3,d4) 2.D=d1,d2,d9R=(d1,d2),(d1,d3),(d3,d4),(d3,d6),(d6,d8),(d4,d5), (d6,d7),(d8,d9)3.D=d1,d2,d9R=(d1,d3),(d1,d8),(d2,d3),(d2,d4),(d2,d5),(d3,d9), (d5,d6),(d8,d9),(d9,d7), (d4,d7), (d4,d6)第二章线性表一、填空1、在顺序表中插入或删除一个元素，需要平均移动 元素，具体移动得元素个数与 有关。2、向一个长度为 n得向量得第i个元素(1W iwn+l)之前插

8、入一个元素时，需向后移动 个元素。3、向一个长度为n得向量中删除第i个元素(iwiwn)时，需向前移动 个元4、在顺序表中访问任意一结点得时间复杂度均为 ,因此，顺序表支持访问。5、顺序表中逻辑上相邻得元素得物理位置 相邻。单链表中逻辑上相邻得元素得物理位置 相邻。6、在带头结点得非空单链表中，头结点得存储位置由 指示，首元素结点得存储位 置由 指示，除首元素结点外，其它任一元素结点得存储位置由 指示。7、在n个结点得单链表中要删除已知结点*p,需找到它得 ,其时间复杂度为。8、循环单链表La中，指针P所指结点为表尾结点得条件就是 。9、已知L就是无表头结点得单链表，且 P结点既不就是首元素结

9、点，也不就是尾元素结 点°a) a、 在 P 结点后插入 S结点得语句序列就是： b) 在P结点前插入 S结点得语句序列就是： Oc、在表首插入S结点得语句序列就是： Od、在表尾插入S结点得语句序列就是： O二、判断正误( )1、链表得每个结点中都恰好包含一个指针。( )2、顺序存储结构只能用来存放线性结构；链式存储结构只能用来存放非线性结构。( )3、链表得删除算法很简单，因为当删除链中某个结点后，计算机会自动将后续各个单元向前移动。( )4、线性表得每个结点只能就是一个简单类型，而链表得每个结点可以就是一个复杂类型。( )5、顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存

10、取。( )6、顺序存储方式得优点就是存储密度大，且插入、删除运算效率高。( )7、线性表在物理存储空间中也一定就是连续得。()8、线性表在顺序存储时，逻辑上相邻得元素未必在存储得物理位置次序上相邻。)9、顺序存储方式只能用于存储线性结构。()10、线性表得逻辑顺序与存储顺序总就是一致得。三、单项选择题()1、数据在计算机存储器内表示时，物理地址与逻辑地址相同并且就是连续得，称之为：A、存储结构B、逻辑结构C、顺序存储结构D、链式存储结构 ()2、在n个结点得顺序表中，算法得时间复杂度就是O (1)得操作就是：A、访问第i个结点(iwiwn)与求第i个结点得直接前驱(2WiWn)B、在第i个结点

11、后插入一个新结点(iwiwn)C、删除第i个结点(1w iwn)D、将n个结点从小到大排序()3、链表不具有得特点就是 。A、可随机访问任一个元素B、插入删除不需要移动元素C、不必事先估计存储空间D、所需空间与线性表得长度成正比()4、链接存储得存储结构所占存储空间：A、分两部分，一部分存放结点值，另一部分存放表示结点间关系得指针B、只有一部分，存放结点值C、只有一部分，存储表示结点间关系得指针D、分两部分，一部分存放结点值，另一部分存放结点所占单元数 ()5、对于只在表得首、尾进行插入操作得线性表，宜采用得存储结构为：A、顺序表B、用头指针表示得单循环链表C、用尾指针表示得单循环链表D、单链

12、表()6、线性表若采用链式存储结构时，要求内存中可用存储单元得地址：A、必须就是连续得C、一定就是不连续得B、部分地址必须就是连续得D、连续或不连续都可以)7、线性表L在 情况下适用于使用链式结构实现。A、需经常修改L中得结点值C、L中含有大量得结点()8、单链表得存储密度A、大于1B、等于1()9、设a1、a2、a3为3个结点，整数称为B、需不断对L进行删除插入D、L中结点结构复杂C、小于1D、不能确定P0, 3, 4代表地址，则如下得链式存储结构P0a13a2434A30A、循环链表B、单链表)10、若线性表最常用得操作就是存取第C、双向循环链表D、双向链表i个元素及其前驱得值，则采用存储

13、方式节省时间。A、单链表B、双链表C、单循环链表D、顺序表四、简答题1、试比较顺序存储结构与链式存储结构得优缺点。在什么情况下用顺序表比链表好？2、在单链表与单循环链表中，若仅知道指针 p指向某一结点，不知道表头指针，能否将结 点*p从链表中删去？若可以，其时间复杂度各为多少？ 五、阅读分析题指出以下算法中得错误与低效(即费时)之处，并将它改写为一个既正确又高效得算法。Status DeleteK(SqList&a, int i, int k)本过程从顺序存储结构得线性表 a中删除第i个元素起得k个元素 if ( i<1 | k<0 | i+k> a、length )

14、 return INFEASIBLE;参数不合法elsefor(count = 1; count <k; count + ) 删除一个元素for ( j = a、length; j>=i+1;j-) a、elemj-1 = a、elemj;a、length -; return OK; DeleteK注：上题涉及得类型定义如下:# define LIST INIT SIZE 100# define LISTINCREMENT 10 typedef struct 存储空间基址当前长度当前分配得存储容量Elem Type *elem;Intlength;Intlistsize;SqLis

15、t;六、编程题1、已知 L 就是无表头结点得单链表，且P 结点既不就是首元结点，也不就是尾元结点，请写出在 P 结点后插入S 结点得核心语句序列。2、 试分别以不同得存储结构实现线性表得就地逆置算法，即在原表得存储空间将线性表（ a1,a2、, an） 逆置为（an, an-i,、, ai）。（ 1）以顺序表作存储结构。（ 2）以单链表作存储结构。3、已知带有头结点得循环链表中头指针为head,试写出删除并释放数据域值为x得所有结点得c 函数。4、已知有单链表表示得线性表中含有三类字符得数据元素（如字母字符、数字字符与其它字符），试编写算法来构造三个以循环链表表示得线性表，使每个表中只含同一类

16、得字符，且利用原表中得结点空间作为这三个表得结点空间，头结点可另辟空间。第三章栈与队列一、选择题1、一个栈得输入序列为A, B, C, D,则借助一个栈所得到得输出序列不可能得就A、A, B, C, DB D, C, B, AC A, C, D, BD> D, A, B, C2、S最多能容纳4个元素。现有 6个元素按A、B、C D E、F得顺序进栈，问下列哪一 个序列就是可能得出栈序列？。A、E, D,C,B,A,FB、B,C,E,F, A, DCC, B ,E,D,A,FDA,D,F,E, B, C3、设链式栈中结点得结构为(data, next )，且top就是指向栈顶得指针。若想在

17、链式栈得栈顶插入一个由指针s所指得结点，则应执行下列哪一个操作？。A、top->next = s ;B s->next = top->next ; top->next = s ;C s->next = top ; top = s ;D> s->next = top ; top = top->next ;4、一个队列得入队序列就是1, 2, 3, 4,则队列得输出序列就是 。A、4, 3, 2, 1 B 1, 2, 3, 4 C 1, 4, 3, 2 D、3, 2, 4, 1 5、设循环队列得结构就是const int MaxSize = 100;

18、typedef int DataType ;typedef struct DataType dataMaxSize ;int front, rear ; Queue ;若有一个Queue类型得队列Q,试问判断队列满得条件应就是下列哪一个语句？ A、Q、front = Q 、rear ;B、Q front - Q 、rear = MaxSize ;C。front + Q 、rear = MaxSize ; D Q、front = (Q rear+1 ) % MaxSize;6、设循环队列得结构就是const int MaxSize = 100;typedef int DataType ;type

19、def struct DataType dataMaxSize ;int front , rear ; Queue ;若有一个Queue类型得队列Q试问应用下列哪一个语句计算队列元素个数？ A、(Q rear - Q 、front + MaxSize ) % MaxSize ; B、。rear - Q 、front +1;C。rear - Q 、front -1;D、Q、rear - Qfront ;7、以下哪一个不就是队列得基本运算？ 。A、从队尾插入一个新元素已从队列中删除第i个元素C判断一个队列就是否为空D读取队头元素得值二、简答题1、简述栈与队列得共同点与不同点。它们与线性表有什么关系

20、？2、按图3、1(b)所示铁道(两侧铁道均为单向行驶道)进行车厢调度，回答： 如进站得车厢序列为123,则可能得到得出站车厢序列就是什么？如进站得车厢序列为 123456,能否得到435612与135426得出站序列，并说明原因。(即写出以“S”表示进栈、以“ X”表示出栈得栈操作序列)。3、设有一个顺序栈 S,元素s1, s2, s3, s4, s5, s6依次进栈，如果 6个元素得出栈顺序为 s2, s3, s4,s6, s5, s1 ，则顺序栈得容量至少应为多少？4、 简述以下算法得功能(其中栈与队列得元素类型均为int ) ：( 1 ) void proc_1(Stack S) int

21、 i, n, A255;n=0;while(!EmptyStack(S)n+; Pop(&S, &An);for(i=1; i<=n;i+)Push(&S,Ai);( 2) void proc_2(Stack S, int e) Stack T; int d;InitStack(&T);while(!EmptyStack(S) Pop(&S, &d);if (d!=e) Push( &T,d);while(!EmptyStack(T) Pop(&T, &d);Push( &S,d);( 3) void pro

22、c_3(Queue *Q) Stack S; int d;InitStack(&S);while(!EmptyQueue(*Q)DeleteQueue(Q, &d);Push( &S,d);while(!EmptyStack(S) Pop(&S, &d); EnterQueue(Q ， d)三、算法题1、试写一个算法，判断依次读入得一个以为结束符得字母序列，就是否为形如序列1 &序列2模式得字符序列。其中序列1 与序列 2 中都不含字符&，且序列2 就是序列1得逆序列。例如，'a+b&b+a'就是属该模式得字符序列

23、，而T +3 &3 1 '则不就是。第四章串一、选择题1、下面关于串得叙述中，哪一个就是不正确得？ 。A、串就是字符得有限序列B、空串就是由空格构成得串C 模式匹配就是串得重要运算D串既可顺序存储，也可采用链式存储2、串就是一种特殊得线形表，其特殊性体现在。A、可以顺序存储B、数据元素就是一个字符C可以链接存储DK数据元素可以就是多个字符3、长度为1得串等价于一个字符型常量，这种说法就是 。A、正确得B、错误得二、简答题1、设 s=' I AM A STUDENT , t= ' GOOD, q=' WORKEDR。给出下列操作得结果： StrLength

24、(s) ; SubString (subl, s, 1,7) ; SubString (sub2, s, 7,1) ;StrIndex(s, ' A' 4); StrReplace(s, ' STUDENIT ,q) ; StrCat (StrCat (sub1, t), StrCat (sub2, q)。2、设主串为"abcaabbabcabaacbacba模式串为"abcabaa”。 计算模式串得next,nextval函数值，并给出利用 nextval函数值进行KMP莫式匹配得每一趟过程。第五章数组与广义表一、选择题1、稀疏矩阵一般得压缩存储方

25、法有两种A、数组与三维数组C、三元组与十字链表2、若采用三元组压缩技术存储稀疏矩阵对该矩阵得转置运算，这种观点()。A正确，即。B、三元组与散列D、散列与十字链表,只要把每个元素得行下标与列下标互换，就完成了B、错误3、数组元素得下标值越大，存取时间越长，这种说法就是A、正确得B、错误得 4、广义表(a, ( b ), ( ( c )得表尾就是 A、( c )B、( c )C、( c )D、( b ), ( ( c )二、填空题1、一维数组得逻辑结构就是 ,存储结构就是 。对于二维数组，有 与 两种不同得存储方式。X于一个二维数组Amn,若采取按行存储得方式，则任一数组元素Aij相对于A00得

26、地址为。2、二维数组 A1020采用列序为主方式存储，每个元素占一个存储单元，并且 A00得存储地址就是 200,则A612得地址就是 。3、设n行n列得下三角矩阵 A已压缩到一维数组S1、n*(n+1)/2中，若按行序为主存储，则Aij 对应得S中得存储位置就是。三、简答题1、设有一个10 10得对称矩阵A1010,采取按行压缩存储得方式将其上三角得矩阵元存 放于一个一维数组B中，则数组B得容量应有多大？若设 A00为第一个元素，存放于B0,且数组A得每一个数组元素在数组B中占一个数组元素位置，则 A85在数组B中得地址就是多少？2(*)、设有三对角矩阵Ann,将其三条对角线中得元素逐行存储

27、到一维数组B3n-2 中，使得Bk = Aij。试求用i, j表示k得地址转换公式。3(*)、画出下面广义表得两种存储结构图示：(a, b), ( ), d, (e, f)4、求下列广义表运算得结果：(1) GET HEAD(a,B,(c,D、);(2) GET TAIL(a,B、，(c,D、);(3) GET TAILGETHEAD(a,B,(c,D) ;(4) GET HEADGETTAILGETHEAD(a,B、,(c,D、);5、设广义表 L=(),(),则 GETHEAD(L) 就是; GETTAIL(L) 就是; L 得 长度就是 ;深度就是 。四、算法题1、将数组Cn中所有奇数移

28、到偶数之前，要求时间复杂度为O(n)。第六章树与森林一、选择题1、设二叉树有n个结点且根结点处于第1层，则其高度为()。A、n-1B、log2 (n+1) -1 C、log 2n +1D、不确定2、设高度为h (空二叉树彳#高度为0,只有一个结点得二叉树得高度为1)得二叉树只有度为2与度为。得结点，则该二叉树中所含结点至少有()个。A、2hB、2h -1C、2h +1D、 h +13、设森林F中有4棵树，第1、2、3、4棵树得结点个数分别为 m、n2、n3、n4,当把森林F转换成一棵二叉树后，其根结点得右子树中有()个结点。A n-1B、m+n2+n3C、n2+n3+n4D、n14、将含有82

29、个结点得完全二叉树从根结点开始顺序编号，根结点为第1号，其她结点自上向下，同一层自左向右连续编号。则第40号结点得双亲结点得编号为()。A 20B、 19C、 81D、 80 5、对二叉树从1开始编号，要求每个结点得编号大于其左右孩子得编号，同一个结点得左右孩子中，其左孩子得编号小于其右孩子得编号，则可采用()实现编号。A、先序遍历B、中序遍历 C、后序遍历D、从根开始进行层次遍历6、某二叉树得先序序列与后序序列正好相反，则该二叉树一定就是()得二叉树。A、空或只有一个结点B、高度等于其结点数C、任一结点无左孩子D、任一结点无右孩子7、在线索化二叉树中，t所指结点没有左子树得充要条件就是()。

30、A、t- > left=NULL B、t-ltag=1 C、t-ltag=1 且 t-left=NULLD、以上者 B不对8、二叉树按某种顺序线索化后，任一结点均有指向其前趋与后继得线索，这种说法()。A、正确B、错误9、二叉树得前序遍历序列中，任意一个结点均处在其子女结点得前面，这种说法()。A、正确B、错误10、设高度为h得二叉树上只有度为 0与度为2得结点，则此类二叉树中所包含得结点数至 少为()。A、2hB、2h-1C、2h+1D、h+111、如果T2就是由有序树T转换而来得二叉树，那么 T中结点得前序就就是 T2中结点得 ( )。A、前序B、中序C、后序D、层次序12、在一非空

31、二叉树得中序遍历序列中，根结点得右边()。A、只有右子树上得所有结点B、只有右子树上得部分结点C、只有左子树上得部分结点D、只有左子树上得所有结点二、填空题(每空1分，共7分)1、 N个结点得二叉树采用二叉链表存放，共有空链域个数为 。2、 一棵含有101个结点得完全二叉树存储在数组A1、101中，对14W101,若Ak就是非叶子结点,则k得最小彳1就是：, k得最大值就是：。3、设根结点得层数为1,则高度为k得二叉树具有得结点数目，最少为,最多为。4、 一棵二叉树有67个结点，这些结点得度要么就是 0,要么就是2。这棵二叉树中度为 2 得结点有 个。5、将一棵有50个结点得完全二叉树从根结点

32、开始，由根向下，每一层从左至右，顺序地存储在一个一维数组 bt1、50中，这棵二叉树最下面一层上最左边一个结点存储在数组元 素bt中。三、判断题(每小题 1分，共11分)( )1、树结构与二叉树结构都就是树形结构，所以它们就是相同得数据结构。( )2、满二叉树得结点个数必为奇数。( )3、若有一个结点就是二叉树中某个子树得中序遍历结果序列得最后一个结点，则它一定就是该子树得前序遍历结果序列得最后一个结点。( )4、若有一个结点就是二叉树中某个子树得前序遍历结果序列得最后一个结点，则它一定就是该子树得中序遍历结果序列得最后一个结点。( )5、将一棵树转换为二叉树表示后，该二叉树得根结点没有右子树

33、。( )6、采用二叉树来表示树时，树得先根次序遍历结果与其对应得二叉树得前序遍历结果就是一样得。( )7、在Huffman树中，权值较大得叶子结点离根较远。( )8、将一个森林转换为二叉树后，该二叉树得根结点一定有右子树。( )9、哈夫曼树根结点得权值等于所有叶结点得权值之与。( )10、如果一个二叉树中没有度为1得结点，则必为满二叉树。( )11、由二叉树结点得先根序列与后根序列可以唯一地确定一棵二叉树。四、简答题1、在结点个数为n (n>1)得各棵树中，高度最小得树得高度(根结点在第1层)就是多少？它有多少个叶结点？多少个分支结点？高度最大得树得高度(根结点在第1层)就是多少？它有多

34、少个叶结点？多少个分支结点？2、若有3个数据1, 2, 3,由它们构造出来得中序遍历结果都为1, 2, 3得不同二叉树有哪些？3、试分别找出满足以下条件得所有二叉树：(1) 二叉树得前序序列与中序序列相同；(2) 二叉树得中序序列与后序序列相同；(3) 二叉树得前序序列与后序序列相同。4、在前序线索树中，要找出结点P得直接后继结点，请写出有关语句。LtagLcdataRtagRc5、在中序线索树上，要找出结点P得直接后继结点，请写出相关语句。Itag1cdatartagrc四、构造题1、已知一棵二叉树得前序遍历结果就是ABECDFGHIJ ,中序遍历结果就是EBCDAFHIGJ ,试画出这棵二

35、叉树，并写出它得后序遍历序列。2、 假定用于通信彳#电文仅由 8个字母cl, c2, c3, c4, c5, c6, c7, c8组成， 各 字母在电文中出现得频度分别为 5, 25, 3, 6, 10, 11, 36, 4。试为这8个字母设 计不等长Huffman编码，并给出该电文得总码数。3、画出与下列树对应得二叉树：五、算法设计题1、若用二叉链表作为二叉树得存储表示，试编写递归算法，统计二叉树中叶结点得个数。2、若用二叉链表作为二叉树得存储表示，试编写递归算法，交换每个结点得左孩子与右孩子。3、设二叉树按二叉链表存放，写算法判别一棵二叉树就是否就是一棵正则二叉树。正则二叉树就是指：在二叉

36、树中不存在子树个数为1得结点。4、设一颗二叉树以二叉链表为存储结构，设计一个算法求此二叉树上度为1得结点个数。第七章一、选择题1、在一个图中，所有顶点得度数之与等于所有边数得 倍。A、1/2B、1C、2D、42、在一个有向图中，所有顶点得入度之与等于所有顶点得出度之与得 倍。A、1/2B、1C、2D、43、一个有n个顶点得无向图最多有()条边。A、nB、n(n-1)C、n(n-1)/2D、2n4、在一个具有n个顶点得无向图中，要连通全部顶点至少需要 条边。A、nB、n+1C、n-1D、n/25、对于一个具有n个顶点得无向图，若采用邻接矩阵表示，则该矩阵得大小 。A、nB、(n-1)2C、n-1

37、D、n26、对于一个具有 n个顶点与e条边得无向图，若采用邻接表表示，则表头向量得大小为，所有邻接表中得结点总数就是。 A、nB、n+1C、n-1D、n+e A、e/2B、eC、2eD、n+e7、采用邻接表存储得图得深度优先遍历算法类似于二叉树得 。A、先序遍历B、中序遍历C、后序遍历D、按层遍历8、用Prim算法求下列连通得带权图得最小代价生成树，在算法执行得某刻，已选取得顶 点集合U = 1, 2, 3,边得集合TE= (1, 2), (2, 3) ,要选取下一条权值最小得边， 应当从 组中选取。A、(1,4) ,(3,4),(3,5), (2,5)B、(4,5),(1,3),(3,5)C

38、、(1,2),(2,3),(3,5)D、(3,4) ,(3,5),(4,5), (1,4)9(*)、下面关于工程计划得事件结点网络得叙述中，哪一个就是不正确得？ 。A、关键活动不按期完成就会影响整个工程得完成时间。B、任何一个关键活动提前完成，那么整个工程将会提前完成。C、所有得关键活动都提前完成，那么整个工程才会提前完成。D、某些关键活动若提前完成 ，那么整个工程将会提前完成。E、任何一个关键活动延迟将会导致整个工程延迟。10、任何一个无向连通图得最小生成树 。A、只有一棵B、有一棵或多棵C、一定有多棵D、可能不存在二、填空题1、在无向图得邻接矩阵 A中，若Aij = 1 ,则A皿i = 。

39、2、在一个无环有向图 G中，若存在一条从顶点 i到顶点j得弧，则在顶点得拓扑序列中， 顶点i与顶点j得先后次序就是。三、判断题(判断下列叙述得对错。如果正确，在题前得括号内填入“”，否则填入" ”。)1、()用邻接矩阵存储一个图时，在不考虑压缩存储得情况下，所占用得存储空间大小 只与图中得顶点个数有关，而与图得边数无关。2、()对任何用顶点表示活动得网络( AOV网)进行拓扑排序得结果都就是唯一得。3、()有回路得有向图不能完成拓扑排序。4、()有n (n>1)个顶点得无向连通图最少有n-1条边。5、()在一个有向图中，所有顶点得入度之与等于所有顶点得出度之与。6、()图G得一

40、棵最小代价树得代价一定小于该图其它任何一棵生成树得代价。7、()一个无向图得邻接矩阵中各元素之与与图中边得条数相等。四、解答题1、用邻接矩阵表示有向图时，若图中有1000个顶点，1000条边，则形成得邻接矩阵有多少矩阵元素？有多少非零元素？2、若已给出一个有向图得邻接矩阵，则计算第i个顶点得入度得方法就是什么？删除所有从第i个顶点发出得边得方法就是什么？3、对于如下所示得有向图，试写出：(1) 从顶点出发进行深度优先搜索所得到得深度优先生成树；(2) 从顶点出发进行广度优先搜索所得到得广度优先生成树。4、 以下图为例，按Dijkstra算法计算得到得从顶点到其它各个顶点得最短路径与最短路径长度

41、。5、 已知如下图所示得有向图，请给出该图得:(1)每个顶点得入度、出度；(2)邻接矩阵；(3)邻接表；(4)逆邻接表；(5)强连通分量。6、 已知如图所示得 AOE网，试求：(1)每个事件得最早发生时间与最晚发生时间；(2)每个活动得最早开始时间与最晚开始时间；(3)给出关键路径。ID10S 3图7、 已知如图所示得有向网，试利用 Dijkstra算法求顶点1到其余顶点得最短路径，并给出算法执行过程中各步得状态。题T图8、 已知无向图如图1所示，(1)给出图得邻接表。(2)从A开始，给出一棵广度优先生成树。五、算法设计题1、编写算法，从键盘读入有向图得顶点与弧，创建有向图得邻接表存储结构。2

42、、无向图采用邻接表方式存储，要求编写图得广度优先搜索算法。3、无向图采用邻接表方式存储，要求编写图得深度优先搜索算法。第九章一、选择题1、从供选择得选项中选择与下面有关查找算法得叙述中各括号相匹配得词句，将其编号填入相应得括号内。(1) 采用顺序查找算法查找长度为n得线性表时，元素得平均查找长度为。(2) 采用折半查找算法查找长度为n得有序表时，元素得平均查找长度应 对应判定树得最大层次数。(3) 折半查找与二叉查找树(即二叉排序树)得时间性能 。(4) 顺序查找算法适合于存储结构为得线性表。【供选择得】A、n/2B> nC、(n+1) /2(n-1 ) /2A、小于C、A、A、C、2、

43、I相同B 不相同C、有时不相同散列存储B、顺序存储或链接存储压缩存储H索引存储氏希望较快得查找又便于线性表动态变化得查找方法就是_OA顺!序查找日折半查找C、索引顺序查找散列法查找3、请指出在序列 2, 5, 7,10,14,15,18, 23, 35,41,52 中，用折半查找法查找关键码12时需做多少次关键码比较？。A 2日 3C、4Dk 54、对包含n个元素得哈希表进行查找，平均查找长度为 。A、O (log 2n) B 、O (n)G O (nlog 2n)D、不直接依赖于 n5、表长为25得哈希表，用除留余数法，即按式 H (Key) =Key mod P,建立哈希函数，P 应取。A

44、 26B 15C 24D 236、对线性表进行二分查找时，要求线性表必须。A、以顺序方式存储B、以链接方式存储C以顺序方式存储，且结点按关键字有序排序DK以链接方式存储，且结点按关键字有序排序7、有一个有序表为1,3,9,12,32,41,45,62,75,77,82,95,100,当二分查找值为82 得结点时，次比较后查找成功。A 1B 2C、4D> 88、设哈希表长 m=14，哈希函数 H (key) =key%11。表中已有 4个结点：addr (15) =4, addr (38) =5, addr (61) =6, addr (84) =7,其余地址为空，如用二次探测再散列处理

45、冲突，关键字为49得结点得地址就是 。A 8B 3C 5D、99、有一个长度为12得有序表，按二分查找法对该表进行查找，在表内各元素等概率情况下查找成功所需得平均比较次数为 。A 35/12B 37/12C、39/12D> 43/1210、 采用分块查找时，若线性表中共有625个元素，查找每个元素得概率相同，假设采用顺序查找来确定结点所在得块时，每块应分 个结点最佳。A 10B 25C 6D、62511、 设有一个长度为 100得已排好序得表，用二分查找进行查找，若查找不成功，至少比较 次。A 9日 8C、7Dk 612、 AVL树就是一种平衡得二叉排序树，树中任一结点得：A、左、右子树

46、得高度均相同B 、左、右子树高度差得绝对值不超过1C左子树得高度均大于右子树得高度D、左子树得高度均小于右子树得高度二、填空题1、设一哈希表表长 M为100 ,用除留余数法构造哈希函数，即 H (K) =K MODP (P<=M , 为使函数具有较好性能，P应选 。2、在分块查找方法中,首先查找，然后再查找相应得。3、长度为255得表，采用分块查找法，每块得最佳长度就是 。4、假设在有序线性表 A1、20上进行二分查找，则比较一次查找成功得结点数为 , 则比较二次查找成功得结点数为,则比较三次查找成功得结点数为, 则比较四次查找成功得结点数为,则比较五次查找成功得结点数为 , 平均查找长

47、度为。5、在查找方法中，平均查找长度与结点个数无关得查找方法就 6、对于长度为n得线性表，若进行顺序查找，则时间复杂度为，若采用二分法查找则时间复杂度为 ,若采用分块查找(假定总块数与每块长度均接近)，则时间复杂度为。7、己知一个有序表为(12,18,20,25,29,32,40,62,83,90,95,98)，当二分查找值为 29 与90得元素时，分别需要 次与 次比较才能查找成功；若采用顺序查找时，分别需要 次与 次比较才能查找成功。8、假设hash (x)为哈希函数，解决冲突用线性探测再散列法。typedef RecordType HashTable m ;int HashSearch

48、( HashTable ht, KeyType K )p0 =;if ( ht p0 、key = NULLKEY ) return (- 1);else if ( ht p0 、key = K ) return ( p0 );elsefor (i=1; i<=; i+)pi =( p0 +) % m;if( ht pi 、key = NULLKEY ) return ( - 1);else if( ht pi 、 key =) return ( pi );return ( - 1);9、对二叉排序树进行 遍历，可得到结点得有序排列、三、简答题1、 什么情况下二叉排序树得查找性能较好？什

49、么情况下二叉排序树得查找性能最差？2、 画出对长度为10得有序表进行折半查找得判定树，并求其等概率时查找成功得平均查找长度。3、 选取哈希函数 H (k) = (3k) %11,用线性探测再散列法处理冲突。试在 010得散列地址空间中，对关键字序列(22， 41， 53， 46， 30， 13， 01 ， 67)构造哈希表，并求等概率情况下查找成功与不成功时得平均查找长度。4、 已知长度为12 得表： ( Jan,Feb,Mar,Apr,May,June,July,Aug,Sep,Oct,Nov,Dec ) 。(1) 试按表中元素得顺序依次插入一棵初始为空得二叉排序树，画出插入完成后得二叉排序

50、树并求其等概率得情况下查找成功得平均查找长度。(2) 若对表中元素先进行排序构成有序表，求在等概率得情况下对此有序表进行折半查找时查找成功得平均查找长度。(3) 按表中元素得顺序依次构造一棵平衡二叉树，并求其等概率得情况下查找成功得平均查找长度。5、 设哈希表长度为11,哈希函数H (K) = ( K得第一字母在字母表中得序号)MOD1,1若输入顺序为(D，BA，TN，M，CI ， I ，K，X，TA)，处理冲突方法为线性探测再散列或链地址法，要求构造哈希表，并求出等概率情况下查找成功平均查找长度。6、 试用连线把右边就是四种线性表得存储结构与左边对应得操作得特点连接起来。A、散列表(1)查找

51、与存取速度快，但插入与删除速度慢。日顺序有序表 (2)查找、插入与删除速度快，但不能进行顺序存取。C顺序表(3)插入、删除与顺序存取速度快，但查找速度慢。D链接表(4)查找、插入与删除速度慢，但顺序存取与随机存取第i个元素速度快。四、算法设计题1、 试编写利用折半查找确定记录所在块得分块查找算法。2、 试写一个判别给定二叉树就是否为二叉排序树得算法。设此二叉树以二叉链表作存储结构，且树中结点得关键字均不同。3、 编写算法，求出指定结点在给定得二叉排序树中所在得层数。4、 编写一个函数，利用二分查找算法在一个有序表中插入一个元素x， 并保持表得有序性。第十章、选择题1、一组记录得关键字为(46,

52、 79, 56, 38, 40, 84),利用快速排序得方法，以第一个记录为基准得到得一次划分结果为A 38, 40,46, 56,79,84B、40,38, 46,79,56, 84C 40, 38,46, 56,79,84D40,38, 46,84,56, 792、下列排序算法中，算法可能会出现下面情况：初始数据有序时，花费时间反而最A、堆排序已冒泡排序C快速排序D> SHELL排序3、稳定得排序方法就是。A、直接插入排序与快速排序B、二分法插入排序与起泡排序C直接选择排序与直接插入排序H树形选择排序与 Shell排序4、比较次数与排序码得初始排列状态无关得排序方法就是 。A直接插入

53、排序日起泡排序C快速排序D直接选择排序5、设存在一个字符序列 Q, H, C, Y, P, A, M, S, R, D, F, X ,问新序列 F, H, C,D, P, A, M, Q, R, S, Y, X 就是下列 排序法一趟排序得结果。A起泡排序B、初始步长为4得shell排序C直接插入排序H以第一个元素为分界元素得快速排序6、对下列关键字序列用快速排序法进行排序时，速度最快得情形就是 。A、21、25、5、17、9、23、30 B、25、23、30、17、21、5、9C 21、9、17、30、25、23、5D 5、9、17、21、23、25、307、设有关键码序列(Q,G,M,Z,A,N,P,X,H )，下面哪一个序列就是从上述序列出发建堆得结 果？ 。A、A,G,H,M,N,P,Q,X,ZC G,M,Q,A,N,P,X,H,ZB、A,G,M,H,Q,N,P,X,ZD H,G,M,P,A,N,Q,X,Z8、对于键值序列(12, 13,11, 18, 60, 15, 7, 18, 25, 100),用筛选法建堆，必须从键值为 得结点开始。A、1000 159、设有1000个无序得元素，希望用最快得速度挑选出其中