数据结构复习资料

第1章绪论一、填空题数据结构就是一门研究非数值计算得程序设计问题中计算机得 以及它们之间得 与 等得学科。数据结构被形式地定义为（D,R），其中D就是 得有限集合，R就是D上得 有限集合。数据结构按逻辑结构可分为两大类，它们分别就是 与 。若细分为4类，分别就是 、 、 与 。线性结构中元素之间存在 关系，树形结构中元素之间存在 关系，图形结构中元素之间存在 关系。在线性结构中，第一个结点 前驱结点，其余每个结点有且只有 个前驱结点；最后一个结点 后继结点，其余每个结点有且只有 个后继结点。在树形结构中，树根结点没有 结点，其余每个结点有且只有 个前驱结点；叶子结点没有后继结点，其余每个结点得后继结点数可以任意。在图形结构中，每个结点得前驱结点数与后继结点数可以 。数据结构包括数据得、数据得与数据得这三个方面得内容。数据得存储结构可用四种基本得存储方法表示，它们分别就是 、 、 与 。数据得运算最常用得有5种，它们分别就是 、 、 、 、 。一个算法得效率可分为 效率与 效率。二、单项选择题数据结构中，与所使用得计算机无关得就是数据得（）结构。A、存储 B、物理 C、逻辑 D、物理与存储算法分析得目得就是（）。A、找出数据结构得合理性 B、研究算法中得输入与输出得关系C、分析算法得效率以求改进 D、分析算法得易懂性与文档性算法分析得两个主要方面就是：（）。A、空间复杂性与时间复杂性 B、正确性与简明性C、可读性与文档性 D、数据复杂性与程序复杂性计算机算法指得就是（）。A、计算方法 B、排序方法 C、解决问题得有限运算序列 D、调度方法计算机算法必须具备输入、输出与（）等5个特性。A、可行性、可移植性与可扩充性 B、可行性、确定性与有穷性C、确定性、有穷性与稳定性 D、易读性、稳定性与安全性三、判断下列叙述得对错。（）数据元素就是数据得最小单位。（）数据结构就是数据对象与对象中数据元素之间关系得集合。（）数据结构就是具有结构得数据对象。（）算法与程序原则上没有区别，在讨论数据结构时二者就是通用得。（）所谓数据得逻辑结构就是指数据元素之间得逻辑关系。（）数据得逻辑结构与数据元素本身得内容与形式无关。（）数据结构就是指相互之间存在一种或多种关系得数据元素得全体。（）从逻辑关系上讲，数据结构主要分为两大类：线性结构与非线性结构。四、设n为正整数,分析下列各程序段中加下划线得语句得执行次数。for(inti=1；i<=n；i++） for(intj=1;j<=n;j++）{c[i][j]=0、0；for（intk=1;k<=n;k++）c[i][j]=c[i][j]+a[i][k]*b[k][j]； }x=0；y=0；for(inti=1;i<=n;i++)for(intj=1;j<=i;j++)for(intk=1;k<=j;k++)x=x+y； 2)/2=n(n+1)/4+n(n+1)(2n+1)/12=n(n+1)(3+2n+1)/12=n(n+1)(n+2)/6n（3）k=0; for(i=1;i<=n;i++) for(j=i;j<=n;j++) k++; (4)i=1;j=0; while(i+j<=n){ if(i>j)j++; elsei++; } (5) 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--;} elsex++; }五、分析下面各程序段得时间复杂度2、2、s=0;fori=0;i<n;i++)for(j=0;j<n;j++)s+=B[i][j];sum=s;1、1、for(i=0;i<n;i++)for(j=0;j<m;j++)A[i][j]=0;3、x=0;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，哪些结点就是开始结点，哪些结点就是终端结点？D={d1,d2,d3,d4}R={(d1,d2),(d2,d3),(d3,d4)}D={d1,d2,…,d9}R={(d1,d2),(d1,d3),(d3,d4),(d3,d6),(d6,d8),(d4,d5),(d6,d7),(d8,d9)}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)}

第二章线性表一、填空在顺序表中插入或删除一个元素，需要平均移动元素，具体移动得元素个数与有关。向一个长度为n得向量得第i个元素(1≤i≤n+1)之前插入一个元素时，需向后移动个元素。向一个长度为n得向量中删除第i个元素(1≤i≤n)时，需向前移动个元素。在顺序表中访问任意一结点得时间复杂度均为，因此，顺序表支持 访问。顺序表中逻辑上相邻得元素得物理位置 相邻。单链表中逻辑上相邻得元素得物理位置 相邻。在带头结点得非空单链表中，头结点得存储位置由

指示，首元素结点得存储位置由

指示，除首元素结点外，其它任一元素结点得存储位置由

指示。在n个结点得单链表中要删除已知结点*p，需找到它得，其时间复杂度为。循环单链表La中，指针P所指结点为表尾结点得条件就是

。已知L就是无表头结点得单链表，且P结点既不就是首元素结点，也不就是尾元素结点。a、在P结点后插入S结点得语句序列就是： 。b、在P结点前插入S结点得语句序列就是： 。c、在表首插入S结点得语句序列就是： 。d、在表尾插入S结点得语句序列就是： 。二、判断正误（）1、链表得每个结点中都恰好包含一个指针。（）2、顺序存储结构只能用来存放线性结构；链式存储结构只能用来存放非线性结构。（）3、链表得删除算法很简单，因为当删除链中某个结点后，计算机会自动将后续各个单元向前移动。（）4、线性表得每个结点只能就是一个简单类型，而链表得每个结点可以就是一个复杂类型。（）5、顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。（）6、顺序存储方式得优点就是存储密度大，且插入、删除运算效率高。（）7、线性表在物理存储空间中也一定就是连续得。（）8、线性表在顺序存储时，逻辑上相邻得元素未必在存储得物理位置次序上相邻。（）9、顺序存储方式只能用于存储线性结构。（）10、线性表得逻辑顺序与存储顺序总就是一致得。三、单项选择题（）1、数据在计算机存储器内表示时，物理地址与逻辑地址相同并且就是连续得，称之为： A、存储结构 B、逻辑结构 C、顺序存储结构 D、链式存储结构（）2、在n个结点得顺序表中，算法得时间复杂度就是O（1）得操作就是： A、访问第i个结点（1≤i≤n）与求第i个结点得直接前驱（2≤i≤n） B、在第i个结点后插入一个新结点（1≤i≤n） C、删除第i个结点（1≤i≤n） D、将n个结点从小到大排序（）3、链表不具有得特点就是

。 A、可随机访问任一个元素 B、插入删除不需要移动元素C、不必事先估计存储空间

D、所需空间与线性表得长度成正比（）4、链接存储得存储结构所占存储空间： A、分两部分，一部分存放结点值，另一部分存放表示结点间关系得指针 B、只有一部分，存放结点值 C、只有一部分，存储表示结点间关系得指针 D、分两部分，一部分存放结点值，另一部分存放结点所占单元数（）5、对于只在表得首、尾进行插入操作得线性表，宜采用得存储结构为:。 A、顺序表 B、用头指针表示得单循环链表 C、用尾指针表示得单循环链表 D、单链表（）6、线性表若采用链式存储结构时，要求内存中可用存储单元得地址： A、必须就是连续得 B、部分地址必须就是连续得 C、一定就是不连续得 D、连续或不连续都可以（）7、线性表Ｌ在情况下适用于使用链式结构实现。 Ａ、需经常修改Ｌ中得结点值 Ｂ、需不断对Ｌ进行删除插入 Ｃ、Ｌ中含有大量得结点 Ｄ、Ｌ中结点结构复杂（）8、单链表得存储密度 Ａ、大于1 Ｂ、等于1 Ｃ、小于1 D、不能确定（）9、设a1、a2、a3为3个结点，整数P0，3，4代表地址，则如下得链式存储结构称为P034P0a13a24A30 Ａ、循环链表 Ｂ、单链表 Ｃ、双向循环链表 D、双向链表（）10、若线性表最常用得操作就是存取第i个元素及其前驱得值，则采用

存储方式节省时间。 A、单链表 B、双链表 C、单循环链表 D、顺序表四、简答题1、试比较顺序存储结构与链式存储结构得优缺点。在什么情况下用顺序表比链表好？2、在单链表与单循环链表中，若仅知道指针p指向某一结点，不知道表头指针，能否将结点*p从链表中删去？若可以，其时间复杂度各为多少？五、阅读分析题指出以下算法中得错误与低效（即费时）之处，并将它改写为一个既正确又高效得算法。注：上题涉及得类型定义如下：#defineLISTINITSIZE100#defineLISTINCREMENT10注：上题涉及得类型定义如下：#defineLISTINITSIZE100#defineLISTINCREMENT10typedefstruct{ElemType*elem;//存储空间基址Intlength;//当前长度Intlistsize;//当前分配得存储容量}SqList;StatusDeleteK(SqList&a,inti,intk){//本过程从顺序存储结构得线性表a中删除第i个元素起得k个元素if(i<1||k<0||i+k>a、length)returnINFEASIBLE;//参数不合法else{for(count=1;count<k;count++){//删除一个元素for(j=a、length;j>=i+1;j--)a、elem[j-1]=a、elem[j];a、length--;}returnOK;}//DeleteK1、已知L就是无表头结点得单链表，且P结点既不就是首元结点，也不就是尾元结点，请写出在P结点后插入S结点得核心语句序列。2、试分别以不同得存储结构实现线性表得就地逆置算法，即在原表得存储空间将线性表（a1,a2、、、,an）逆置为（an,an-1,、、、,a1）。（1）以顺序表作存储结构。（2）以单链表作存储结构。3、已知带有头结点得循环链表中头指针为head，试写出删除并释放数据域值为x得所有结点得c函数。4、已知有单链表表示得线性表中含有三类字符得数据元素（如字母字符、数字字符与其它字符），试编写算法来构造三个以循环链表表示得线性表，使每个表中只含同一类得字符，且利用原表中得结点空间作为这三个表得结点空间，头结点可另辟空间。

第三章栈与队列一、选择题一个栈得输入序列为A，B，C，D，则借助一个栈所得到得输出序列不可能得就是

。

A、A，B，C，D B、D，C，B，AC、A，C，D，B

D、D，A，B，CS最多能容纳4个元素。现有6个元素按A、B、C、D、E、F得顺序进栈,问下列哪一个序列就是可能得出栈序列?。A、E，D，C，B，A，F B、B，C，E，F，A，DC、C,B，E，D，A，F D、A，D，F，E，B，C设链式栈中结点得结构为（data,next），且top就是指向栈顶得指针。若想在链式栈得栈顶插入一个由指针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；一个队列得入队序列就是1，2，3，4，则队列得输出序列就是

。

A、4，3，2，1 B、1，2，3，4 C、1，4，3，2 D、3，2，4，设循环队列得结构就是 constintMaxSize=100； typedefintDataType；typedefstruct{ DataTypedata[MaxSize]； intfront,rear； }Queue；若有一个Queue类型得队列Q，试问判断队列满得条件应就是下列哪一个语句？。A、Q、front==Q、rear； B、Q、front-Q、rear==MaxSize；C、Q、front+Q、rear==MaxSize；D、Q、front==（Q、rear+1）%MaxSize；设循环队列得结构就是 constintMaxSize=100； typedefintDataType；typedefstruct{ DataTypedata[MaxSize]； intfront，rear； }Queue； 若有一个Queue类型得队列Q，试问应用下列哪一个语句计算队列元素个数？。 A、（Q、rear-Q、front+MaxSize）%MaxSize；B、Q、rear-Q、front+1；C、Q、rear-Q、front-1； D、Q、rear-Qfront；以下哪一个不就是队列得基本运算？。A、从队尾插入一个新元素 B、从队列中删除第i个元素C、判断一个队列就是否为空 D、读取队头元素得值二、简答题简述栈与队列得共同点与不同点。它们与线性表有什么关系？按图3、1(b)所示铁道（两侧铁道均为单向行驶道）进行车厢调度，回答：

⑴如进站得车厢序列为123，则可能得到得出站车厢序列就是什么？⑵如进站得车厢序列为123456，能否得到435612与135426得出站序列，并说明原因。（即写出以“S”表示进栈、以“X”表示出栈得栈操作序列）。设有一个顺序栈S，元素s1,s2,s3,s4,s5,s6依次进栈，如果6个元素得出栈顺序为s2,s3,s4,s6,s5,s1，则顺序栈得容量至少应为多少？简述以下算法得功能（其中栈与队列得元素类型均为int）：（1）voidproc_1(StackS){inti,n,A[255];

n=0;

while(!EmptyStack(S))

{n++;

Pop(&S,

&A[n]);}

for(i=1;

i<=n;

i++)

Push(&S,

A[i]);

}（2）voidproc_2(StackS,

inte){StackT;

intd;InitStack(&T);

while(!EmptyStack(S))

{Pop(&S,

&d);

if(d!=e)Push(&T,

d);

}

while(!EmptyStack(T))

{Pop(&T,

&d);

Push(&S,

d);

}}（3）voidproc_3(Queue

*Q){StackS;

intd;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’就是属该模式得字符序列，而‘１+３&３－１

第四章串一、选择题下面关于串得叙述中，哪一个就是不正确得？。A、串就是字符得有限序列 B、空串就是由空格构成得串C、模式匹配就是串得重要运算 D、串既可顺序存储，也可采用链式存储2、串就是一种特殊得线形表，其特殊性体现在____

_。A、可以顺序存储 B、数据元素就是一个字符C、可以链接存储 D、数据元素可以就是多个字符3、长度为1得串等价于一个字符型常量，这种说法就是。A、正确得 B、错误得二、简答题设s=’IAMASTUDENT’，

t=’GOOD’，

q=’WORKER’。给出下列操作得结果：StrLength(s)；

SubString(sub1,s,1,7)；SubString(sub2,s,7,1)；StrIndex(s,’A’,4)；StrReplace(s,’STUDENT’,q)；StrCat(StrCat(sub1,t),StrCat(sub2,q))。设主串为”abcaabbabcabaacbacba”模式串为”abcabaa”。计算模式串得next,nextval函数值，并给出利用nextval函数值进行KMP模式匹配得每一趟过程。第五章数组与广义表一、选择题1、稀疏矩阵一般得压缩存储方法有两种,即。A、数组与三维数组 B、三元组与散列C、三元组与十字链表 D、散列与十字链表2、若采用三元组压缩技术存储稀疏矩阵,只要把每个元素得行下标与列下标互换,就完成了对该矩阵得转置运算,这种观点（）。A、正确 B、错误3、数组元素得下标值越大，存取时间越长，这种说法就是。A、正确得 B、错误得4、广义表(a,(b),((c)))得表尾就是。A、((c)) B、(((c)))C、(c) D、((b),((c)))二、填空题1、一维数组得逻辑结构就是，存储结构就是。对于二维数组，有与两种不同得存储方式。对于一个二维数组A[m][n]，若采取按行存储得方式，则任一数组元素A[i][j]相对于A[0][0]得地址为。2、二维数组A[10][20]采用列序为主方式存储，每个元素占一个存储单元，并且A[0][0]得存储地址就是200，则A[6][12]得地址就是。3、设n行n列得下三角矩阵A已压缩到一维数组S[1、、n*(n+1)/2]中,若按行序为主存储,则A[i][j]对应得S中得存储位置就是。三、简答题1、设有一个1010得对称矩阵A[10][10]，采取按行压缩存储得方式将其上三角得矩阵元存放于一个一维数组B[]中，则数组B[]得容量应有多大？若设A[0][0]为第一个元素，存放于B[0]，且数组A[][]得每一个数组元素在数组B[]中占一个数组元素位置，则A[8][5]在数组B[]中得地址就是多少？2（*）、设有三对角矩阵A[n][n]，将其三条对角线中得元素逐行存储到一维数组B[3n-2]中，使得B[k]=A[i][j]。试求用i，j表示k得地址转换公式。3（*）、画出下面广义表得两种存储结构图示：

(((a,b),(((),d,(e,f)))))4、求下列广义表运算得结果：（1）GETHEAD[((a,B,(c,D、)))]；（2）GETTAIL[((a,B、,(c,D、)))]；（3）GETTAIL[GETHEAD[((a,B,(c,D)))]]；（4）GETHEAD[GETTAIL[GETHEAD[((a,B、,(c,D、)))]]]；5、设广义表L=((),())，则GETHEAD(L)就是；GETTAIL(L)就是；L得长度就是；深度就是。四、算法题1、将数组C[n]中所有奇数移到偶数之前，要求时间复杂度为O(n)。第六章树与森林一、选择题1、设二叉树有n个结点且根结点处于第1层，则其高度为（）。 A、n-1 B、log2（n+1）-1 C、log2n+1 2、设高度为h（空二叉树得高度为0，只有一个结点得二叉树得高度为1）得二叉树只有度为2与度为0得结点，则该二叉树中所含结点至少有（）个。A、2h B、2h-1 C、2h+1 D、h+13、设森林F中有4棵树，第1、2、3、4棵树得结点个数分别为n1、n2、n3、n4，当把森林F转换成一棵二叉树后，其根结点得右子树中有（）个结点。A、n1-1 B、n1+n2+n3 C、n2+n3+n4 D、n4、将含有82个结点得完全二叉树从根结点开始顺序编号，根结点为第1号，其她结点自上向下，同一层自左向右连续编号。则第40号结点得双亲结点得编号为（）。A、20 B、19 C、81 D、805、对二叉树从1开始编号，要求每个结点得编号大于其左右孩子得编号，同一个结点得左右孩子中，其左孩子得编号小于其右孩子得编号，则可采用（）实现编号。

A、先序遍历

B、中序遍历

C、后序遍历

D、从根开始进行层次遍历6、某二叉树得先序序列与后序序列正好相反，则该二叉树一定就是（）得二叉树。

A、空或只有一个结点

B、高度等于其结点数

C、任一结点无左孩子

D、任一结点无右孩子7、在线索化二叉树中,t所指结点没有左子树得充要条件就是（）。A、t-〉left==NULL B、t-〉ltag==1 C、t-〉ltag==1且t-〉left==NULL D、、以上都不对8、二叉树按某种顺序线索化后,任一结点均有指向其前趋与后继得线索,这种说法（）。A、正确 B、错误9、二叉树得前序遍历序列中,任意一个结点均处在其子女结点得前面,这种说法（）。A、正确 B、错误10、设高度为h得二叉树上只有度为0与度为2得结点,则此类二叉树中所包含得结点数至少为（）。A、2h B、2h-1 C、2h+1 D、h+111、如果T2就是由有序树T转换而来得二叉树，那么T中结点得前序就就是T2中结点得（）。A、前序 B、中序 C、后序 D、层次序12、在一非空二叉树得中序遍历序列中，根结点得右边（）。A、只有右子树上得所有结点 B、只有右子树上得部分结点C、只有左子树上得部分结点 D、只有左子树上得所有结点二、填空题（每空1分，共7分）N个结点得二叉树采用二叉链表存放，共有空链域个数为。一棵含有101个结点得完全二叉树存储在数组A[1、、101]中,对1≤k≤101,若A[k]就是非叶子结点,则k得最小值就是:，k得最大值就是:。设根结点得层数为1，则高度为k得二叉树具有得结点数目，最少为，最多为。一棵二叉树有67个结点，这些结点得度要么就是0，要么就是2。这棵二叉树中度为2得结点有个。将一棵有50个结点得完全二叉树从根结点开始，由根向下，每一层从左至右，顺序地存储在一个一维数组bt[1、、50]中，这棵二叉树最下面一层上最左边一个结点存储在数组元素bt[]中。三、判断题（每小题1分，共11分）（）1、树结构与二叉树结构都就是树形结构,所以它们就是相同得数据结构。（）2、满二叉树得结点个数必为奇数。（）3、若有一个结点就是二叉树中某个子树得中序遍历结果序列得最后一个结点，则它一定就是该子树得前序遍历结果序列得最后一个结点。（）4、若有一个结点就是二叉树中某个子树得前序遍历结果序列得最后一个结点，则它一定就是该子树得中序遍历结果序列得最后一个结点。（）5、将一棵树转换为二叉树表示后,该二叉树得根结点没有右子树。（）6、采用二叉树来表示树时，树得先根次序遍历结果与其对应得二叉树得前序遍历结果就是一样得。（）7、在Huffman树中，权值较大得叶子结点离根较远。（）8、将一个森林转换为二叉树后,该二叉树得根结点一定有右子树。（）9、哈夫曼树根结点得权值等于所有叶结点得权值之与。（）10、如果一个二叉树中没有度为1得结点，则必为满二叉树。（）11、由二叉树结点得先根序列与后根序列可以唯一地确定一棵二叉树。四、简答题在结点个数为n（n>1）得各棵树中，高度最小得树得高度（根结点在第1层）就是多少？它有多少个叶结点？多少个分支结点？高度最大得树得高度（根结点在第1层）就是多少？它有多少个叶结点？多少个分支结点？若有3个数据1，2，3，由它们构造出来得中序遍历结果都为1，2，3得不同二叉树有哪些？ 试分别找出满足以下条件得所有二叉树：二叉树得前序序列与中序序列相同；二叉树得中序序列与后序序列相同；二叉树得前序序列与后序序列相同。在前序线索树中，要找出结点P得直接后继结点，请写出有关语句。LtagLcdataRtagRc在中序线索树上，要找出结点P得直接后继结点，请写出相关语句。

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

第七章一、选择题1、在一个图中，所有顶点得度数之与等于所有边数得倍。A、1/2 B、1 C、2 D、42、在一个有向图中，所有顶点得入度之与等于所有顶点得出度之与得倍。A、1/2 B、1 C、2 D、43、一个有n个顶点得无向图最多有（）条边。A、n B、n(n-1) C、n(n-1)/2 D、2n4、在一个具有n个顶点得无向图中，要连通全部顶点至少需要条边。A、n B、n+1 C、n-1 D、n/25、对于一个具有n个顶点得无向图，若采用邻接矩阵表示，则该矩阵得大小。A、n B、(n-1)2 C、n-1 D、n26、对于一个具有n个顶点与e条边得无向图，若采用邻接表表示，则表头向量得大小为①，所有邻接表中得结点总数就是②。①A、n B、n+1 C、n-1 D、n+e ②A、e/2 B、e C、2e D、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、{（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、可能不存在二、填空题在无向图得邻接矩阵A中，若A[i][j]=1，则A[j][i]=。在一个无环有向图G中，若存在一条从顶点i到顶点j得弧，则在顶点得拓扑序列中，顶点i与顶点j得先后次序就是。三、判断题（判断下列叙述得对错。如果正确，在题前得括号内填入“”，否则填入“”。）（）用邻接矩阵存储一个图时，在不考虑压缩存储得情况下，所占用得存储空间大小只与图中得顶点个数有关，而与图得边数无关。（）对任何用顶点表示活动得网络（AOV网）进行拓扑排序得结果都就是唯一得。（）有回路得有向图不能完成拓扑排序。（）有n（n≥1）个顶点得无向连通图最少有n-1条边。（）在一个有向图中，所有顶点得入度之与等于所有顶点得出度之与。（）图G得一棵最小代价树得代价一定小于该图其它任何一棵生成树得代价。（）一个无向图得邻接矩阵中各元素之与与图中边得条数相等。四、解答题用邻接矩阵表示有向图时，若图中有1000个顶点，1000条边，则形成得邻接矩阵有多少矩阵元素？有多少非零元素？若已给出一个有向图得邻接矩阵，则计算第i个顶点得入度得方法就是什么？删除所有从第i个顶点发出得边得方法就是什么？对于如下所示得有向图，试写出：从顶点①出发进行深度优先搜索所得到得深度优先生成树；从顶点②出发进行广度优先搜索所得到得广度优先生成树。以下图为例，按Dijkstra算法计算得到得从顶点①到其它各个顶点得最短路径与最短路径长度。已知如下图所示得有向图，请给出该图得：（1）每个顶点得入度、出度；（2）邻接矩阵；（3）邻接表；（4）逆邻接表；（5）

强连通分量。已知如图所示得AOE网，试求：(1)每个事件得最早发生时间与最晚发生时间；(2)每个活动得最早开始时间与最晚开始时间；(3)给出关键路径。已知如图所示得有向网，试利用Dijkstra算法求顶点1到其余顶点得最短路径，并给出算法执行过程中各步得状态。已知无向图如图1所示，

（1）给出图得邻接表。（2）从A开始，给出一棵广度优先生成树。五、算法设计题编写算法，从键盘读入有向图得顶点与弧，创建有向图得邻接表存储结构。无向图采用邻接表方式存储，要求编写图得广度优先搜索算法。无向图采用邻接表方式存储，要求编写图得深度优先搜索算法。

第九章一、选择题从供选择得选项中选择与下面有关查找算法得叙述中各括号相匹配得词句，将其编号填入相应得括号内。采用顺序查找算法查找长度为n得线性表时，元素得平均查找长度为①。采用折半查找算法查找长度为n得有序表时，元素得平均查找长度应②对应判定树得最大层次数。折半查找与二叉查找树（即二叉排序树）得时间性能③。顺序查找算法适合于存储结构为④得线性表。【供选择得】①A、n/2 B、n C、（n+1）/2 D、（n-1）/2②A、小于 B、大于 C、等于 D、大于等于③A、相同 B、不相同 C、有时不相同④A、散列存储 B、顺序存储或链接存储C、压缩存储 D、索引存储既希望较快得查找又便于线性表动态变化得查找方法就是。A、顺序查找 B、折半查找 C、索引顺序查找 D、散列法查找请指出在序列{2,5,7,10,14,15,18,23,35,41,52}中，用折半查找法查找关键码12时需做多少次关键码比较?。A、2 B、3 C、4 D、5对包含n个元素得哈希表进行查找，平均查找长度为。A、O（log2n）B、O（n） C、O（nlog2n） D、不直接依赖于n表长为25得哈希表，用除留余数法，即按式H（Key）=KeymodP，建立哈希函数，P应取。A、26

B、15

C、24

D、23对线性表进行二分查找时,要求线性表必须。A、以顺序方式存储 B、以链接方式存储C、以顺序方式存储,且结点按关键字有序排序D、以链接方式存储,且结点按关键字有序排序有一个有序表为{1,3,9,12,32,41,45,62,75,77,82,95,100},当二分查找值为82得结点时,次比较后查找成功。A、1 B、2 C、4 D、8设哈希表长m=14,哈希函数H（key）=key%11。表中已有4个结点:addr（15）=4，addr（38）=5，addr（61）=6，addr（84）=7，其余地址为空，如用二次探测再散列处理冲突,关键字为49得结点得地址就是。A、8 B、3 C、5 D、9有一个长度为12得有序表,按二分查找法对该表进行查找,在表内各元素等概率情况下查找成功所需得平均比较次数为。A、35/12 B、37/12 C、39/12 D、43/12采用分块查找时,若线性表中共有625个元素,查找每个元素得概率相同,假设采用顺序查找来确定结点所在得块时,每块应分个结点最佳。A、10 B、25 C、6 D、625设有一个长度为100得已排好序得表，用二分查找进行查找，若查找不成功，至少比较次。A、9 B、8 C、7 D、6AVL树就是一种平衡得二叉排序树，树中任一结点得:A、左、右子树得高度均相同B、左、右子树高度差得绝对值不超过1C、左子树得高度均大于右子树得高度D、左子树得高度均小于右子树得高度二、填空题设一哈希表表长M为100，用除留余数法构造哈希函数，即H（K）=KMODP（P<=M）,为使函数具有较好性能，P应选。在分块查找方法中,首先查找,然后再查找相应得。长度为255得表,采用分块查找法,每块得最佳长度就是。假设在有序线性表A[1、、20]上进行二分查找,则比较一次查找成功得结点数为,则比较二次查找成功得结点数为,则比较三次查找成功得结点数为,则比较四次查找成功得结点数为,则比较五次查找成功得结点数为,平均查找长度为。在查找方法中，平均查找长度与结点个数无关得查找方法就是

。对于长度为n得线性表,若进行顺序查找,则时间复杂度为，若采用二分法查找,则时间复杂度为，若采用分块查找（假定总块数与每块长度均接近）,则时间复杂度为。己知一个有序表为（12,18,20,25,29,32,40,62,83,90,95,98）,当二分查找值为29与90得元素时,分别需要次与次比较才能查找成功；若采用顺序查找时,分别需要次与次比较才能查找成功。假设hash（x）为哈希函数，解决冲突用线性探测再散列法。typedefRecordTypeHashTable[m];intHashSearch（HashTableht,KeyTypeK）{p0=_________;if（ht[p0]、key==NULLKEY）return（-1）;elseif（ht[p0]、key==K）return（p0）;else{for（i=1;i<=_____;i++）{pi=（p0+_____）%m;if（ht[pi]、key==NULLKEY）return（-1）;elseif（ht[pi]、key==_____）return（pi）;}return（-1）;}}对二叉排序树进行

遍历,可得到结点得有序排列、三、简答题什么情况下二叉排序树得查找性能较好？什么情况下二叉排序树得查找性能最差？画出对长度为10得有序表进行折半查找得判定树，并求其等概率时查找成功得平均查找长度。选取哈希函数H（k）=（3k）%11，用线性探测再散列法处理冲突。试在0～10得散列地址空间中，对关键字序列（22，41，53，46，30，13，01，67）构造哈希表，并求等概率情况下查找成功与不成功时得平均查找长度。已知长度为12得表：（Jan,Feb,Mar,Apr,May,June,July,Aug,Sep,Oct,Nov,Dec）。试按表中元素得顺序依次插入一棵初始为空得二叉排序树，画出插入完成后得二叉排序树并求其等概率得情况下查找成功得平均查找长度。若对表中元素先进行排序构成有序表，求在等概率得情况下对此有序表进行折半查找时查找成功得平均查找长度。按表中元素得顺序依次构造一棵平衡二叉树，并求其等概率得情况下查找成功得平均查找长度。设哈希表长度为11，哈希函数H（K）=（K得第一字母在字母表中得序号）MOD11，若输入顺序为（D，BA，TN，M，CI，I，K，X，TA），处理冲突方法为线性探测再散列或链地址法，要求构造哈希表，并求出等概率情况下查找成功平均查找长度。试用连线把右边就是四种线性表得存储结构与左边对应得操作得特点连接起来。A、散列表（1）查找与存取速度快,但插入与删除速度慢。B、顺序有序表（2）查找、插入与删除速度快,但不能进行顺序存取。C、顺序表（3）插入、删除与顺序存取速度快,但查找速度慢。D、链接表（4）查找、插入与删除速度慢,但顺序存取与随机存取第i个元素速度快。四、算法设计题试编写利用折半查找确定记录所在块得分块查找算法。试写一个判别给定二叉树就是否为二叉排序树得算法。设此二叉树以二叉链表作存储结构，且树中结点得关键字均不同。编写算法，求出指定结点在给定得二叉排序树中所在得层数。编写一个函数，利用二分查找算法在一个有序表中插入一个元素x，并保持表得有序性。

第十章一、选择题一组记录得关键字为（46，79，56，38，40，84），利用快速排序得方法，以第一个记录为基准得到得一次划分结果为。A、38，40，46，56，79，84 B、40，38，46，79，56，84C、40，38，46，56，79，84 D、40，38，46，84，56，79下列排序算法中，算法可能会出现下面情况：初始数据有序时，花费时间反而最多。A、堆排序

B、冒泡排序

C、快速排序

D、SHELL排序稳定得排序方法就是。A、直接插入排序与快速排序 B、二分法插入排序与起泡排序C、直接选择排序与直接插入排序 D、树形选择排序与Shell排序比较次数与排序码得初始排列状态无关得排序方法就是。A、直接插入排序 B、起泡排序 C、快速排序 D、直接选择排序设存在一个字符序列{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、直接插入排序 D、以第一个元素为分界元素得快速排序对下列关键字序列用快速排序法进行排序时，速度最快得情形就是。A、{21、25、5、17、9、23、30} B、{25、23、30、17、21、5、9}C、{21、9、17、30、25、23、5} D、{5、9、17、21、23、25、30}设有关键码序列（Q,G,M,Z,A,N,P,X,H）,下面哪一个序列就是从上述序列出发建堆得结果?。A、A,G,H,M,N,P,Q,X,Z B、A,G,M,H,Q,N,P,X,ZC、G,M,Q,A,N,P,X,H,Z D、H,G,M,P,A,N,Q,X,Z对于键值序列（12，13，11，18，60，15，7，18，25，100），用筛选法建堆，必须从键值为得结点开始。A、100

B、60

C、12

D、15设有1000个无序得元素,希望用最快得速度挑选出其中前10个最大得元素,最好排序法就是。A、起泡排序 B、快速排序 C、堆排序 D、基数排序一组记录得排序码为（46,79,56,38,40,84）,则利用堆排序得方法建立得初始推为。A、79,46,56,38,40,80 B、84,79,56,38,40,46C、84,79,56,46,40,38 D、84,56,79,40,46,38一组记录得排序码为（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,72C、16,25,48,35,79,82,23,36,40,72 D、16,25,35,48,79,23,36,40,72,82用某种排序方法对线性表（25,84,21,47,15,27,68,35,20）进行排序时,元素序列得变化情况如下:（1）25,84,21,47,15,27,68,35,20（2）20,15,21,25,47,27,68,35,84（3）15,20,21,25,35,27,47,68,84（4）15,20,21,25,27,35,47,68,84，则所采用得排序方法就是。A、选择排序 B、希尔排序 C、归并排序 D、快速排序快速排序方法在情况下最不利于发挥其长处得就是。A、要排序得数据量太大 B、要排序得数据中含有多个相同值C、要排序得数据已基本有序 D、要排序得数据个数为奇数下列四种排序方法中，不稳定得方法就是。A、直接插入排序 B、冒泡排序 C、归并排序 D、直接选择排序二、填空题给定序列{100,86,48,73,35,39,42,57,66,21},按堆结构得定义,则它一定就是堆。在进行直接插入排序时,其数据比较次数与数据得初始排列关；而在进行直接选择排序时，其数据比较次数与数据得初始排列关。在供选择得选项中选择正确得答案：排序（分类）得方法有许