数据结构试题(含答案)讲解

1、数据结构试题单选题在数据结构的讨论中把数据结构从逻辑上分为 内部结构与外部结构线性结构与非线性结构（C）静态结构与动态结构 紧凑结构与非紧凑结构。采用线性链表表示一个向量时,A 必须是连续的C 一定是不连续的3、采用顺序搜索方法查找长度为要求占用的存储空间地址（ D ）B部分地址必须是连续的D可连续可不连续的顺序表时，搜索成功的平均搜索长度为（4、AnBn/2在一个单链表中，若q结点是C（n-1）/2p结点的前驱结点，若在qD （n +1）/2p之间插入结点S，则执行s Ti nk = p t link; p t link = s;p t link = s; st link = q;p t l

2、ink = st link； st link = p;q t link = s; st link = p;如果想在4092个数据中只需要选择其中最小的A起泡排序设有两个串t12、若需要利用形参直接访问实参,A指针B 引用13、下面程序段的时间复杂度为（for (int i=0;i<m;i+)for (int j=0;j<n;j+)aij=i*j;A O（m 2）B O（n 2）14、下面程序段的时间复杂度为（int f(unsigned int n) if(n= =0 | n= =1)return 1;else return n*f(n-1);则应把形参变量说明为（值B )D 变量

3、C O(m*n)参数。D O(m+n)A O（1）B O（n）线性表若是采用链式存储结构时, 必须是连续的15、部分地址必须是连续的C O（n2）要求内存中可用存储单元的地址D O(n !)5个，采用（B堆排序C锦标赛排序和p，求p在t中首次出现的位置的运算叫做（B模式匹配C 串替换每一个数组元素Aij占用3个存储字，行下标）方法最好。D 快速排序一定是不连续的连续或不连续都可以）°D串连接i从1到8，列下标j从1到A 求子串7、在数组A中，10。所有数组元素相继存放于一个连续的存储空间中，则存放该数组至少需要的存储字数是16、数据结构的定义为（D，S），其中D是（B ）的集合。A算

4、法B数据元素C数据操作D逻辑结构10、在循环队列中用数组 A0.m-1存放队列元素，其队头和队尾指针分别为front和rear，则当前队列中的元素个数是（D)oA(front - rear+ 1) % mB(rear - front + 1) % mC(front - rear+ m) % mD(rear - front + m) % m11、一个数组元素ai与（A)的表示等价。A* (a+i )B a+iC *a+iD& a+i（ C ）°A 80B 100C 240D 2708、 将一个递归算法改为对应的非递归算法时，通常需要使用（A ）°A 栈B队列C循环队列

5、D 优先队列9、 一个队列的进队列顺序是1,2, 3, 4，则出队列顺序为（ C ）°17、算法分析的目的是（A ） °A找岀数据结构的合理性B研究算法中输入和输岀的关系C分析算法的效率以求改进D分析算法的易懂性和文档性18、 在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行（B ）°A s->link=p;p->link=s;B s->link=p->link;p->link=s;C s->link=p->link;p=s;D p->link=s;s->link=p;19、 设单链表中

6、结点结构为（data,link）.已知指针q所指结点是指针p所指结点的直接前驱，若在 *q与*p之间插入结点*s，则应执行下列哪一个操作（ B ）A s->link=p->link; p->link=s;B q->link=s; s->link=pC p->link=s->link;s->link=p;D p->link=s; s->link=q;20、设单链表中结点结构为(data,link).若想摘除结点*p的直接后继，则应执行下列哪一个操作 (A )A p->link=p->link->link;p=p->

7、;link; p->link=p->link->link;C p->link=p->link;21、设单循环链表中结点的结构为(data,link )p=p->link->link;，且rear是指向非空的带表头结点的单循环链表的尾结点的指针。若想删除链表第一个结点，则应执行下列哪一个操作(A s=rear; rear=rear->link;delete s;B rear=rear->link;deleterear;C rear=rear->link->link;delete rear;D s=rear->link->

8、;link;typedef int Data Type;typedef struct Data Type dataMaxsize;Int front, rear; Queue;若有一个Queue类型的队列Q,试问判断队列满的条件应是下列哪一个语句(A Q.front= = Q.rear;B Q.front - Q.rear= = Maxsize;rear->link->link=s->link;delete s;22、设单循环链表中结点的结构为(data,link 表当前指针，在循环链表中检测，且first为指向链表表头的指针， current是否达到链表表尾的语句是( D

9、)。curre nt 为链A current->link =nullB first->link=currentC first=currentD current->link=first23、一个栈的入栈序列为b，c,则出栈序列不可能的是C c,a,b24、c,b,aB b,a,c栈的数组表示中，top为栈顶指针，栈空的条件是(C )。a,c,bA )。25、top=0B top=maxSize栈和队列的共同特点是(C )。都是先进后岀只允许在端点处插入和删除C top=maxSize都是先进先岀没有共同点D top=-126、假定一个顺序存储的循环队列的队头和队尾指针分别为f+

10、1= =rB 叶仁=ff和r ,则判断队空的条件为(DC f= =0D f= =r).27、当利用大小为的数组顺序存储一个队列时，该队列的最大长度为(A n-2B n-1D n+128、当利用大小为个元素时，首先应执行的数组顺序存储一个栈时，假定用 top= =n 表示栈空，则向这个栈插入一 ()语句修改top指针。A top+;29、设链式栈中结点的结构为(C Q.front + Q.rear= = Maxsize;31、设有一个递归算法如下：D Q.front= = (Q.rea 叶1)% Maxsize;int fact (int n ) if (n<=0) return 1;el

11、se return n*fact(n-1);下面正确的叙述是(B )A计算fact(n)需要执行n次递归C此递归算法最多只能计算到fact(8)32、设有一个递归算法如下int x (intif (n<=3)else returnn) return 1;x(n_2)+x(n_4)+1;试问计算x(x(8)时需要计算(D )次33、设有广义表D(a,b,D),其长度为A aB 334、广义表A(a),则表尾为(B fact(7)=5040D以上结论都不对函数。C 16D 18次B )，深度为(CB top-;C top=0;D top;data, link ) ，且 top是指向栈顶的指针

12、。若想摘除链式栈的栈顶 结点，并将被摘除结点的值保存到x中，则应执行下列(A )操作。B ()35、下列广义表是线性表的有(空表(a)A x=top->data; top=top->link;C x=top; top=top->link;30、设循环队列的结构是：B top=top->link; x=top->data;D x=top->data;A E ( a,(b,c)36、递归表、再入表、纯表、线性表之间的关系为A 再入表 > 递归表 > 纯表 > 线性表E(a,E)C E (a,b)E(a,L()递归表 > 线性表 >

13、再入表 > 纯表const int Maxsize=100;C 递归表 > 再入表 > 纯表 > 线性表D递归表 > 再入表 > 线性表 > 纯表37、某二叉树的前序和后序序列正好相反，则该二叉树一定是(B )的二叉树。A 24C 48B da1+I*mD 53m个存储单元，若第一个结点的地址为da1,C da1-l*mD da1+(l+1)*m）以数组方式存储D以链接方式存储的线性表。）顺序存储或链接存储D 索引存储的有序表时，元素的平均搜索长度为（B n+1D n+e48、平均搜索长度为（C不直接依赖于C ）n D 上述都不对四种四种A空或只有一个

14、结点B高度等于其结点数C任一结点无左孩子D任一结点无右孩子38、 对于任何一棵二叉树T,如果其终端结点数为no,度为2的结点为n2.，则（A ）A n o= n2+1 B n 2= n o+1 C n 0= 2n 2+1D n 2=2n o+139、由权值分别为11，8，6，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（B）B 7340、已知一个顺序存储的线性表，设每个结点需占 则第I个结点的地址为（A ）oA da1+（l-1）*m41、34具有35个结点的完全二叉树的深度为42、对线性表进行折半搜索时，要求线性表必须 A 以链接方式存储且结点按关键码有序排列C以数组方式存储且结点按

15、关键码有序排列43、顺序搜索算法适合于存储结构为（A散列存储C压缩存储44、 采用折半搜索算法搜索长度为nA O （n2）B O （n log 2n）C O （log 2n）45、对于一个具有n个顶点和e条边的无向图，进行拓扑排序时，总的时间为C n-146、判断一个有向图是否存在回路，除了可以利用拓扑排序方法外，还可以利用（A求关键路径的方法B 求最短路径的Dijkstra方法C深度优先遍历算法D广度优先遍历算法47、在10阶B-树中根结点所包含的关键码个数最多为（ C ），最少为（A10对包含n个元素的散列表进行搜索，O （log 2n）B O （n）填空题（）数据的逻辑结构被分为集合结构

16、、线性结构、树形结构、图形结构数据的存储结构被分为顺序结构、链接结构、索引结构、散列结构3、 一种抽象数据类型包括（数据）和（操作）两个部分。4、 设有两个串p和q，求p在q中首次出现的位置的运算称为（模式匹配）5、栈、队列逻辑上都是（线性存储）结构。6、线性结构反映结点间的逻辑关系是（一对一）的，图中的数据元素之间的关系是（多对多）的，树形结构中数据元素间的关系是（一对多）的。7、栈中存取数据的原则（后进先出），队列中存取数据的原则（先进先出）& 串是由（ 零个或多个）字符组成的序列。（长度为零的串）称为空串，（由一个或多个空格组成的串）称为空格串。9、设目标串T= ” abccdc

17、dccbaa ”，模式P= ” cdcc ”则第（6）次匹配成功。10、 一维数组的逻辑结构是（线性结构），存储结构是（顺序存储表示）。对于二维数组，有（行优先顺序）和（列优先顺序）两种不同的存储方式，对于一个二维数组Amn,若采用按行优先存放的方式，则任一数组元素Aij相对于A00的地址为（n*i+j ）。11、 向一个顺序栈插入一个元素时，首先使（栈顶指针）后移一个位置，然后把待插入元素（写） 到这个位置上。从一个顺序栈删除元素时，需要前移一位（栈顶指针）。12、 在一个循环队列Q中，判断队空的条件为（ Q.front= =Q.rear ）,判断队满的条件为（Q.rea 叶1）%MaxSi

18、ze= =q.front）13、对于一棵具有n个结点的树，该树中所有结点的度数之和为（n-1）。14、 一棵高度为5的满二叉树中的结点数为（63 ）个，一棵高度为3满四叉树中的结点数为（85）个。15、若对一棵二叉树从0开始进行结点编号，并按此编号把它顺序存储到一维数组中，即编号为0的结点存储到 a0中，其余类推，则ai元素的左子女结点为（2*i+1 ），右子女结点为（2*i+2），双亲结点（i>=1 ）为（i-1）/2 n ）.16、在一个最大堆中，堆顶结点的值是所有结点中的（最大值），在一个最小堆中，堆顶结点的 值是所有结点中的（最小值）。17、 已知具有n个元素的一维数组采用顺序存

19、储结构，每个元素占k个存储单元，第一个元素的地址为 LOC（a1），那么，LOC（ai）= L0C（a1）+（i-1）*k。18、 在霍夫曼编码中，若编码长度只允许小于等于4,则除掉已对两个字符编码为 0和10夕卜，还可以最多对（4 ）个字符编码。19、 设高度为h的空二叉树的高度为-1，只有一个结点的二叉树的高度为0，若设二叉树只有度为2上度为0的结点，则该二叉树中所含结点至少有（2h+1）个。20、由一棵二叉树的前序序列和（中序序列）可唯一确定这棵二叉树。21、以折半搜索方法搜索一个线性表时，此线性表必须是（顺序）存储的（有序）表。22、 已知完全二叉树的第 8层有8个结点，则其叶子结点数

20、是（68 ）o若完全二叉树的第7有10 个叶子结点，则整个二叉树的结点数最多是（235 ）23、 对于折半搜索所对应的判定树，它既是一棵（二叉搜索树），又是一棵（理想平衡树）。24、假定对长度n=50的有序表进行折半搜索，则对应的判定树高度为（5）,判定树中前5层的结点数为（3 1），最后一层的结点数为（19）。25、 在一个无向图中，所有顶点的度数之和等于所有边数的（2）倍。在一个具有n个顶点的无向完全图中，包含有（n（n-1）/2 ）条边，在一个具有 n个顶点的有向完全图中，包含有（n（n-1）条边。26、 对于一个具有n个顶点和e条边的连通图，其生成树中的顶点数和边数分别为（n ）和（n

21、-1 ）27、 设线性表中元素的类型是实型，其首地址为1024，则线性表中第 6个元素的存储位置是（1044）。28、 在插入和选择排序中，若初始数据基本正序，则选择（插入排序），若初始数据基本反序， 则最好选择（选择排序）。29、算法是对特定问题的求解步驟的一种描述，它是（指令）的有限序列，每一条（指令）表示 一个或多个操作。30、 对于一个具有n个顶点肯e条边的无向图，进行拓朴排序时，总的进间为（ n）31、 构造哈希函数有三种方法，分别为（平方取中）法、（除留余数）法、（折迭移位）法。32、处理冲突的三种方法，分别为 （线性探测）、（随机探测）、（链地址法）。33、 对于含有n个顶点和e

22、条边的无向连通图，利用普里姆算法产生的最小生成树， 其时间复杂 度为（0（n2）、利用克鲁斯卡尔算法产生的最小生成树，其时间复杂度为（0（elog 2e）34、 快速排序在平均情况下的时间复杂度为（0 （nlog 2n），在最坏情况下的时间复杂度为（0（n2）;快速排序在平均情况下的空间复杂度为（0（ log 2n）,在最坏情况下的空间复杂度为（0（ n ）。35、假定一组记录的排序码为（46，79,5 6,38,40,80)，对其进行归并排序的过程中，第二趟排序后的结果是（3 84 65 679 408 0)36、假定一组记录的排序码为（46，79,5 6,3 8,40,80)，对其进行快速

23、排序的第一次划分的结果是（3 84 0 46567 98 0)。37、 一个结点的子树的（个数）称为该结点的度。度为（ 零）的结点称为叶结点或终端结点。度不为（零）的结点称为分支结点或非终端结点。树中各结点度的（ 最大值 ）称为树的度。38、 设Ki=Kj（1<=i<=n, 1<=jv=n,jv>i）且在排序前的序列中 Ri领先于R （i<j）,若排序后的序 列中Ri仍领先于 Rj，则这种排序方法是（稳定的），反之是（不稳定的）。40、在堆排序的过程中，对任一分支结点进行调整运算的时间复杂度为（0（log 2n），整个排序过程的时间复杂度为（0（ nlog 2n）

24、。41、在索引表中，每个索引项至少包含有（关键码值）域和（子表地址）域这两项。42、假定一个线性表为（” abed ”，” baabd ”，” beef ”，” cfg ”，” ahij”，” bkwte ”，” ccdt ” / aayb ”），若按照字符串的第一个字母进行划分，使得同一个字母被划分在一个子表中，则得到的a，b，c三个子表的长度分别为（3），（3），（2）。43、 对于包含5 0个关键码的3阶B-树，其最小高度为（4），最大高度为（5）。44、从一棵B-树删除关键码的过程，若最终引起树根结点的合并，则新树比原树的高度（减1）45、假定要对长度n=100的线性表进行散列存储，

25、并采用开散列法处理冲突， 则对于长度m=20的散列表，每个散列地址的同义词子表的长度平均为（5）。46、在散列存储中，装载因子 a又称为装载系数，若用 m表示散列表的长度，n表示待散列存储 的元素的个数，则a等于（n/m ）。47、 在有向图的邻接矩阵中，第 i行中“ 1 ”的个数是第i个顶点的（岀度），第i列中“ T的个 数是第i个顶点的（入度）。在无向图的邻接矩阵中，第 i行（列）中“ 1 ”的个数是第i个顶点的（度），矩阵中“ 1 ”的个数的一半是图中的（边数）。48、在对m阶B-树中，每个非根结点的关键码数最少为（m/2 n -1 ）个，最多为（m-1 ）个，其子树棵数最少为（m/2

26、n ），最多为（m ）。三、判断题1、数据元素是数据的最小单位（X）o2、 数据的逻辑结构是指各数据元素之间的逻辑关系，是用户按使用需要建立的（V）.3、数据结构是指相互之间存在一种或多种关系的数据元素的全体（X）。4、从逻辑关系上讲，数据结构主要分为两大类：线性结构和非线性结构（V）。5、线性表的逻辑顺序与物理顺序总是一致的（X）。6、二维数组是其数组元素为线性表的线性表（X）。7、每种数据结构都应具备三种基本运算：插入、删除、搜索（V）。8、 非空线性表中任意一个数据元素都有且仅有一个直接前驱元素。（X ）9、 空串与由空格组成的串没有区别。（X ）10、 将T在S中首次出现的位置作为 T

27、在S中的位置的操作称为串的模式匹配。（V）11、 深度为h的非空二叉树的第h层最多有2h-1个结点（X ）12、 完全二叉树就是满二叉树。（X）13、 已知一棵二叉树的前序序列和中序序列可以唯一地构造岀该二叉树。（V ）14、 带权连通图的最小生成树的权值之和一定小于它的其它生成树的权值之和。（V）15、线性表的顺序存储结构的特点是逻辑关系上相邻的两个元素在物理位置上也相邻。(1 ) AB-*C+(3)AB&&EF>!|16、若有一个结点是二叉树中某个子树的中序遍历结果序列的最后一个结点，则它一定是该子树的前序遍历结果序列的最后一个结点。（V）17、任一棵二叉搜索树的平均

28、搜索时间都小于用顺序搜索法搜索同样结点的顺序表的平均搜索 时间。（X）18、 最优二叉搜索树一定是平衡的二叉搜索树。（V）19、 AOE网是一种带权的无环连通图。（V ）20、对于同一组待输入的关键码集合，虽然各关键码的输入次序不同，但得到的二叉搜索树都是 相同的（X）。21、二叉排序树可以是一棵空树（ V ）22、 线性表中所有结点的类型必须相同。（V ）23、n个结点的有向图，若它有 n（n - 1）条边，则它一定是强连通的。（ V ）24、任何无环的有向图，其结点都可以排在一个拓扑序列里。（ V）25、 队列逻辑上是一个下端口和上端能增加又能减少的线性表（X ）26、 二叉树是树的一种特

29、殊情况（V ）27、用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中顶点个数有关，而与图的边数无关（V）。28、 邻接表只能用于有向图的存储，邻接矩阵对于有向图和无向图的存储都适用。（X）29、 连通分量是无向图中的极小连通子图。（X）30、 在AOE网络中一定只有一条关键路径。（X）31、 关键活动不按期完成就会影响整个工程的完成时间。（V）32、 平衡二叉树的左右子树深度之差的绝对值不超过1 o （V ）33、 快速排序是对起泡排序的一种改进。（V ）34、直接选择排序稳定。（X ）35、 堆排序占用的辅助空间很大。（X ）36、在散列法中采取开散列法来解决冲

30、突时，其装载因子的取值一定在（0,1）之间。（X）37、 B-树是一种动态索引结构，它既适用于随机搜索，也适用于顺序搜索。（X）38、 在散列法中，一个可用散列函数必须保证绝对不产生冲突。（X）39、 任何一个关键活动延迟，那么整个工程将会延迟。（V）40、 任何一个关键活动提前完成，那么整个工程将会提前完成。（X）四、运算应用题1、在一个有n个元素的顺序表的第i个元素（1 - i -n）之前插入一个新元素时，需要向 后移动多少个元素？ 答案：需要向后移动 n-i + 1个元素2、当一个栈的进栈序列为 1234567时，可能的出栈序列有多少种？6457321是否是合理的岀栈序列？答案：可能的岀

31、栈序列有种，6457321不是合理的岀栈序列3、简单（直接）选择排序是一种稳定的排序方法吗？试举例说明？答案：是不稳定的排序方法。下面就是不稳定的例子。只要能举岀反例即可。 275275*512061i = 1 061275*512275i = 2 061275 *512275i = 3 061275 *275512 4、设有序顺序表为 10, 20, 30, 40, 50, 60, 70，采用折半搜索时，搜索成功的平均搜索长度是多少？答案：ASLsucc = （1*1 + 2*2 + 3*4 ） / 7 = 17 / 75、在结点个数为n（n>1）的各棵树中，高度最小的树的高度是多少？

32、它有多少个叶结点？多少 个分支结点？高度最大的树的高度是多少？它有多少个叶结点？多少个分支结点？答案：结点个数为n时，高度最小的树的高度为1，有2层；它有n-1个叶结点，1个分支结点；高度最大的树的高度为 n-1,有n层；它有1个叶结点，n-1个分支结点。6、一棵高度为h的满k叉树有如下性质：第h层上的结点都是叶结点，其余各层上每个结点都 有k棵非空子树，如果按层次自顶向下，同一层自左向右，顺序从1开始对全部结点进行编号，试 问：（1）各层的结点个数是多少？（2）编号为i的结点的父结点（若存在）的编号是多少？（3）编号为i的结点的第m个孩子结点（若存在）的编号是多少？（4）编号为i的结点有右兄

33、弟的条件是什么？其右兄弟结点的编号是多少？（5）若结点个数为n,则高度h是n的什么函数关系？答案：（1）各层的结点个数是 口（i=0,1,2,.,h）（2）编号为i的结点的父结点（若存在）的编号是（i+k-2）/k（3） 编号为i的结点的第m个孩子结点（若存在）的编号是（i-1）*k+m+1（4 ）当（i-1）%k<>0时有右兄弟，右兄弟的编号为i+1（5）若结点个数为 n，则高度h和n的关系为：h=log k（n*（k-1）+1）-1（n=0时h=-1）7、写岀下列中缀表达式的后缀形式：（1）A* - B + C（2） （A + B） * D + E / （F + A * D）

34、+ C（3） A && B| ! （E > F）注：按 C+ 的优先级）!（A && !（ （B < C）|（C > D） ） ）|（C < E）答案：各中缀表达式的后缀形式如下：(2) AB+D*EFAD*+/+C+(4) ABC<CD>|!&& !CE<|Cu1413121110 9 8 = 4298、画岀下列广义表的图形表示和它们的存储表示: D(A(c), B(e), C(a, L(b, c, d)(2) J1(J2(J1, a, J3(J1), J3(J1)广义表（2）的图形表示为:9、题目：1

35、1、将下面的森林变换成二叉树（7分）广义表（2）的存储表示为:425答案：其中的一个拓扑序列为：V1，将给定的图简化为最小的生成树,12、1V2，V3，V4，要求从顶点V5，V6，V7出发。（7分）答案:11、根据所给有向图，写岀一个拓扑序列。（5 分）（7 分）0.05，0.29，0.07，0.08，0.14，0.23，0.03，0.11试设计赫夫曼编码。答案：为方便起见，设各种字符的权值w=5,29,7,8,14,23,3,11。因为n=8，所以要构造的赫夫曼树共有m=2n-1=2*8-1=15个结点。生成的赫夫曼树为下图所示。概率为0.05的字符编码为：0110概率为0.03的字符编码为

36、：0111概率为0.29的字符编码为：10概率为0.14的字符编码为：110概率为0.07的字符编码为：1110概率为0.08的字符编码为：111114、已知一棵二叉树的前序遍历的结果是ABECDFGHIJ,中序遍历的结果是 EBCDAFHIGJ,答案：根据前序序列和中序序列能得到唯一的二叉树，所得二叉树如图：这棵二叉树的后序遍历序列为：EDCBIHJGFA15、在结点个数为 n(n>1)的各棵树中，高度最小的树的高度是多少？它有多少个叶结点？多少 个分支结点？高度最大的树的高度是多少？它有多少个叶结点？多少个分支结点？答案：结点个数为n时，高度最小的树的高度为1，有2层；它有n-1个叶

37、结点，1个分支结点；高度最大的树的高度为 n-1,有n层；它有1个叶结点，n-1个分支结点。16、 对于一个高度为 h的AVL树，其最少结点数是多少？反之，对于一个有n个结点的AVL 树,其最大高度是多少？最小高度是多少？答案：设高度为h(空树的高度为-1)的AVL树的最少结点为 Nh，则Nh = F h+3 -1。Fh是斐波那契数。又设 AVL树有n个结点，则其最大高度不超过3/2*log 2(n+1),最小高度为log 2(n+1) n -1。17、 7-7 设有序顺序表中的元素依次为017, 094, 154, 170, 275,503, 509, 512, 553, 612, 677,

38、765, 897, 908 。试画岀对其进行折半搜索时的判定树，并计算搜索成功的平均搜索长度和搜索不成功的平均搜索长度。答案：折半搜索时的判定树为：ASLsucc=1/14(1+2*2+3*4+4*7) =45/14ASLunsucc=1/15(3*1+4*14 ) =59/1518、试对下图所示的 AOE网络10(1) 这个工程最早可能在什么时间结束。(2) 求每个事件的最早开始时间Vei和最迟开始时间Vli。(3) 求每个活动的最早开始时间e()和最迟开始时间l()。(4) 确定哪些活动是关键活动。画出由所有关键活动构成的图，指出哪些活动加速可使整个工程unknown ( w-1 );fo

39、r ( int i = 1 ; i <= w; i+ ) cout <<w<<'cout << endl;Ve01915293843Vl01915373843答案:提前完成。答案：按拓朴有序的顺序计算各个顶点的最早可能开始时间Ve和最迟允许开始时间 Vl，然后再计算各个活动的最早可能开始时间e和最迟允许开始时间I,根据l-e是否等于0来确定关键活动，从而确定关键路径。调用语句为12 2unknown (4)<1,2><1,3><3,2><2,4><2,5><3,5><

40、4,6i><5,6>334 4t行结果n ( int n ) e00151919152938 44L17015271927372、给出递归过程的扌l-e170080128vd unknowcout <<此工程最早完成时间为43，关键路径为<1,3><3,2><2,5><5,6>if ( int ( nn19、已知有五个待排序的记录，其关键字分别为：256，301，751，129，937,863076，438请用快速排序的方法将它们从小到大排列。答案：第一次排序：(076，129)，256，第二次排序:076，129，

41、256，第三次排序:076，129，256，第四次排序:076，129，256，301，第五次排序:076，129，256，301，742 ， 694 ，/ 10 ) ) unknown ( int ( n / 10 );调用语句为unknown ( 582 )。(751，937，863，742，694，301，439 )!，301，694，742)，751，( 863，937 )438，(694，742)，751，( 863，937 )301，694，742，751，( 863，937)438，(438438，694，742，751，863，937285答案：3、给岀递归过程的执行结果int

42、 unknown ( int m ) int value;if ( ! m ) value = 3 ;else value = unknown ( m-1 ) + 5 ;20、设有150个记录要存储到散列表中，并利用线性探查法解决冲突，要求找到所需记录的平均比较次数不超过 2次。试问散列表需要设计多大？(设 堤散列表的装载因子，则有ASLsucc=(1+1/ (1- ：) )/2)。答案：已知要存储的记录数为n = 150,查找成功的平均查找长度为ASLsucc < 2，则有：ASLsucc=1/2(1+1/(1-< 2 解得 辱 2/3 ，又有：Cfen/m=150/m两式联立得

43、：150/m < 2/3,解得：m > 225.所以散列表需要设计 225个单位。五、算法分析题1、给岀下列递归过程的执行结果void unknown ( int w ) if ( w ) return value;执行语句为 cout << unknown (3)。答案： 184、 设有一个二维数组 Amn，假设A00存放位置在644 (10)，A22存放位置在676每个元素占一个空间，问A33 ( 10)存放在什么位置？脚注(10)表示用10进制表示。答案：设数组元素 Ai j存放在起始地址为Loc(i,j)的存储单元中。因为：Loc(2,2)= Loc(0,0)+

44、2*n+2=644+2*n+2=676所以：n=(676-2-644)/2=15所以：Loc(3,3)= Loc(0,0)+3*15+3=644+45+3=692(10)，5、 设单链表结构为struct ListNode int data ;ListNode * link pct link = pb; pc = pb ; pb = pb T|ink；下面的程序是以单链表为存储结构 ，实现二路归并排序的算法，要求链表不另外占用存储空 间，排序过程中不移动结点中的元素，只改各链结点中的指针，排序后r仍指示结果链表的第一个 结点。在初始状态下，所有待排序记录链接在一个以 r为头指针的单链表中。例如

45、，r*在算法实现时，利用了一个队列做为辅助存储，存储各有序链表构成的归并段的链头指针。初始时，各初始归并段为只有一个结点的有序链表。队列的数据类型为Queue，其可直接使用的63A相关操作有置空队列操作：makeEmpty ();将指针x加入到队列的队尾操作：EnQueue ( ListNode * x );退出队头元素，其值由函数返回的操作：ListNode *DlQueue ();判队列空否的函数，空则返回1,不空则返回0: int IsEmpty ()。解决方法提示：程序首先对待排序的单链表进行一次扫描，将它划分为若干有序的子链表，其表头指针存放在一个指针队列中。当队列不空时，从队列中退

46、岀两个有序子链表，对它们进行二路归并，结果链表的表头指 针存放到队列中。如果队列中退岀一个有序子链表后变成空队列，则算法结束。这个有序子链表即为所求。在算法实现时有 6处语句缺失，请阅读程序后补上。(1) 两路归并算法void merge ( ListNode * ha ，ListNode * hb，ListNode * & he ) ListNode *pa，*pb，*pe ;if ( hatdata <= hbtdata ) he = ha; pa = hatlink； pb = hb ; else he = hb; pb = hbtlink; pa = ha ; pe =

47、he;while ( pa && pb )if ( pa t data <= pb tdata) pe t link = pa;pe = pa;pa = pa t link;elseif ( pa ) pe t link = pa; else pe t link = pb;(2) 归并排序主程序void mergesort ( ListNode * r ) ListNode * s，t;Queue Q ;if ( ! r ) return;s = r;Q.EnQueue ( r );while ( s ) t = st link ;while ( t != 0 &

48、& st data <= tt data ) s = t; t = t t link;if ( t ) st link = 0 ; s = t;Q.EnQueue ( s );while ( !Q.lsEmpty( ) ) r = Q.DlQueue ();if ( Q.IsEmpty ( ) ) break;s = Q.DlQueue ();merge ( r，s，t );Q.EnQueue ( t );6、请读下列程序，该程序是在单链表中删除一个结点的算法，为空岀的地方填上正确的语句。(7分)void demo2(LinkList head，L istNode *p)/hea

49、d是带头结点的单链表，删除P指向的结点ListNode *q=head;while(q&& q->next!=p ) q=q->next;if (q) Error( “ *p not in head ” );q->next=p->next;free(p);10、已知一完全二叉树从根结点开始，自顶向下，同一层自左向右连续编号，根结点的编号为0 ,阅读以下程序请回答该程序所实现的功能：templatevclass type >void linkedtosequent(Bintreenode<Type> *t,type a ,int i)if

50、 (t!=Null)a=t->getData();linkedtosequent(t->getleftchild(),a,2*i+1); linkedtosequent(t->getrightchild(),a,2*i+2);主程序调用方式：linkedtosequent(t.root,a,0);答案：该程序的功能是：将用二叉链表表示的完全二叉树转换为二叉树的顺序(数组)表示。8、设散列表为HT13,散列函数为 H (key) = key %13。用闭散列法解决冲突，对下列关键码序列 12, 23, 45, 57, 20, 03, 78, 31, 15, 36 造表。(1)采

51、用线性探查法寻找下一个空位，画岀相应的散列表，并计算等概率下搜索成功的平均搜索长度和搜索不成功的平均搜索长度。 采用双散列法寻找下一个空位 ，再散列函数为 RH ( key) = (7* key) % 10 + 1,寻找下一个空 位的公式为 Hi = (H i-1 + RH ( key) % 13, H 1 = H ( key)。画出相应的散列表，并计算等概率下搜 索成功的平均搜索长度。答案：使用散列函数H(key)=key mod 13 有：H (12 ) =12 , H (23) =10 , H (45) =6 , H (57) =5 , H (20) =7 , H (03) =3 , H

52、 (78 ) =0 , H (31 ) =5 , H (15 ) =2 , H (36) =10利用线性探查法造表：0123456789101112781503574520312336121111114121搜索成功的平均搜索长度为：ASLsucc =1/10( 1+1+1+1+1+1+4+1+2+1) =14/10搜索不成功的平均搜索长度为：ASLunsucc =1/13(2+1+3+2+1+5+4+3+2+1+5+4+3) =36/13利用双散列法造表：Hi = (H i-1 + RH(key) ) %13, Hi =H(key)012345678910111278150357452031

53、36231211111135119、阅读下面程序，指岀其算法的功能并求岀其时间复杂度(1) int Prime(int n)int i=2,x=(int)sqrt(n); while(i<=x) if(n%i=0)break; i+;if(i>x) return 1;else return 0;(2)int sum1(int n)int p=1,s=0;for(int i=1;i<=n;i+)p*=i;s+=p;return s;答案：(1 )程序功能是判断n是否是一个素数，若是则返回数值1，否则返回数值 0,该算法的时间复杂度为O (sqrt(n).(2)程序功能是计算刀ni=1 i!，该算法的时间复杂度为O (n).10、判断一个带表头结点的双向循环链表L是否对称相等的算法如下所示，请在算法的处填入正确的语句。int symmetry(DblList DL) int sym=1;DblNode p=DL->rLink, q=DL->lLink;Whi