数据结构与算法复习题含答案

《数据结构与算法复习题含答案》由会员分享，可在线阅读，更多相关《数据结构与算法复习题含答案（12页珍藏版）》请在装配图网上搜索。

1、 数据结构与算法2015-2016学年第1学期考试复习题一、 选择题（下面各小题有一个正确答案，请将正确答案的编号填写在各小题的括号）。1、在一棵具有5层的满二叉树中结点总数为（ A ）。A) 31 B）32C）33 D）162、串的逻辑结构与（ D ）的逻辑结构不相同。A）线性表 B）栈C）队列 D）集合3、以下序列中，执行第一趟快速排序后得到的序列是（ A ）。A）d,a,e,d,bfh,g B) c,e,a,dfh,g,bC) g,a,e,c,bfd,h D) a,b,c,d,fe,g,h4、n个顶点的强连通图至少有（ A ）条边。A）n B）n+1 C）n-1 D）n(n-1)5、数据

2、结构中，在逻辑上可以把数据结构分成（ B ）。A）动态结构和静态结构B）线性结构和非线性结构C）紧凑结构和非紧凑结构D）部结构和外部结构6、链式存储的存储结构所占存储空间（ A ）。A）分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针B）只有一部分，存放结点值C）只有一部分，存储表示结点间关系的指针D）分两部分，一部分存放结点值，另一部分存放结点所占单元数7、有一个有序表1，4，6，10，18，35，42，53，67，71，78，84，92，99。当用二分查找法查找键值为84的结点时，经（ B ）比较后查找成功。A) 4B)3C)2D)128、设单链表中指针p指向结点m，若要删除m

3、之后的结点（若存在），则需修改指针的操作为（ A ）。A）p-next=p-next-next; B） p=p-next;C）p=p-next-next; D） p-next=p;9、n个顶点，e条边的有向图的邻接矩阵中非零元素有（ C ）个。A）nB）2eC）e D） n+e10、对以下图V4的度为（ C ）。A）1 B）2 C）3 D）4v1 v2 v3 v411、在一棵度为3的树中，度为3的结点个数为2，度为2的结点个数为1，则度为0的结点个数为（ C ）。A）4 B）5C）6 D）712、在数据结构中，从逻辑上可以把数据结构分为（ C ）。A）动态结构和静态结构B）紧凑结构和非紧凑结构

4、C）线性结构和非线性结构D）部结构和外部结构13、用一维数组A进行顺序存储时，若起始地址为loc(A1)，元素长度为c，则A的第i个数组单元在存放地址loc(Ai)，等于（ B ）。A）loc(A1)+i*cB）loc(A1)+(i-1)*cC）loc(A1)+i*c+1D）loc(A1)+(i+1)*c14、（ C ）在进行插入操作时，常产生假溢出现象。A）顺序栈 B）循环队列C）顺序队列 D）链队列15、某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ D ）存储方式最节省运算时间。 A) 单链表 B) 仅有头指针的单循环链表 C) 双链表 D) 仅有尾指针

5、的单循环链表16、向一个栈顶指针为hs的链栈中插入一个s结点时，应执行（ D ）。 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;17、在一个链队列中，假定front和rear分别为队首和队尾指针，则删除一个结点的操作为（ B ）。 A) rear=rear-next;B) front=front-next; C) rear=front-next;D) front=rear-next;18、已知栈的最大容量为4。若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿

6、插进行,则可能出现的出栈序列为（ C ）。 A) 5，4，3，2，1，6B) 2，3，5，6，1，4 C) 3，2，5，4，1，6D) 1，4，6，5，2，319、已知广义表L=(x,y,z),a,(u,t,w)，从L 表中取出原子项t 的操作是（ D ）。 A) Head(Head(Tail(Tail(L) B) Tail(Head(Head(Tail(L) C) Head(Tail(Head(Tail(L) D)Head(Tail(Head(Tail(Tail(L)20、以下各种数据结构中属于线性结构的有（ A ）。 A）栈 B) 二叉树C) 广义表 D) 图21、倘若在对串的插入、删除运

7、算中，期望运算速度最快，则应采用（ C ）。 A）顺序表示法 B）单字符为结点的单链表表示法 C）等量分块表示法 D）不等量分块表示法22、广义表head(a,b),(c,d)的运算结果为（ A ）。 A）(a,b) B）(c,d) C）空表 D）（a,b）,(c,d)）23、 n个顶点的图的最小生成树必定（ D ），是不正确的描述。 A）不唯一 B）权的总和唯一 C）不含回路 D）有n条边24、采用链结构存储线性表时，其地址（ B ）。 A）必须是连续的B）连续不连续都可以 C）部分地址必须是连续D）必须是不连续的25、队列的操作的原则是（ A ）。 A）先进先出 B) 后进先出C) 只能进

8、行插入 D) 只能进行删除26、以下属于顺序存储结构优点的是（ A ）。 A) 存储密度大B) 插入运算方便 C）删除运算方便D）可方便地用于各种逻辑结构的存储表示27、数据结构研究的容是（ D ）。 A）数据的逻辑结构 B）数据的存储结构 C）建立在相应逻辑结构和存储结构上的算法 D）包括以上三个方面28、在一个单链表中，已知q结点是p结点的前趋结点，若在q和p之间插入s结点，则须执行（ A ）。 A）q-next=s;s-next=p;B）s-next=p-next;p-next=s; C）p-next=s-next;s-next=pD）p-next=s;s-next=q;29、若某线性表

9、最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ D ）存储方式最节省时间。 A）顺序表B）双链表C）带头结点的双循环链表D）单循环链表30、下面关于线性表的表达中，错误的是哪一个？（ D ） A）线性表采用顺序存储，必须占用一片连续的存储单元。 B）线性表采用存储，便于插入和删除操作。 C）线性表采用存储，不必占用一片连续的存储单元。 D）线性表采用顺序存储，便于进行插入和删除操作。31、在一个具有n个单元的顺序栈中，假定以地址低端（即0单元）作为栈底，以top作为栈顶指针，当做出栈处理时，top变化为（ C ）。 A）top不变 B）top=0C）top-D）top

10、+32、在一个链队列中，假定front和rear分别为队首和队尾指针，则插入一个结点的操作为（ B ）。A）front=front-next;B） rear=rear-next;C） rear=front-next; D） front=rear-next;33、设有一个栈，元素的进栈次序为A,B,C,D,E,以下是不可能的出栈序列是（ C ）。 A） A,B,C,D,E B） B,C,D,E,A C） E,A,B,C,D D） E,D,C,B,A34、广义表A=（A,B,(C,D),(E,(F,G)），则head(tail(head(tail(tail(A)=（ D ）。 A） (G) B）

11、(D) C） C D） D35、设给定问题的规模为变量n，解决该问题的算法所需时间为Tn=O(f(n),Tn表示式中记号O表示（ A ）。A）一个数量级别 B）一个平均值C）一个最大值 D）一个均方值36、线性表的实现有利于（ A ）运算。A）插入 B）读元素C）查找 D）定位37、串的逻辑结构与（ D ）的逻辑结构不同。A）线性表 B）栈C）队列 D）树38、下面程序段的时间复杂度是( A )。s =0; for( i =0; in; i+) for(j=0;jnext=p-next-nextB）p=p-nextC）p=p-nexe-next D）p-next=p41、设一数列的顺序为1，2

12、，3，4，5，6，通过栈结构不可能排成的顺序数列为（ B ）。A）3，2，5，6，4，1 B）1，5，4，6，2，3C）2，4，3，5，1，6 D）4，5，3，6，2，142、若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点的个数是( B )。A）9 B）11 C）15 D）不能确定43、对待排序的元素序列进行划分，将其分为左、右两个子序列，再对两个子序列施加同样的排序操作，直到子序列为空或只剩一个元素为止。这样的排序方法是（ A ）。A）直接选择排序 B）直接插入排序 C）快速排序 D）起泡排序44、设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第

13、一个元素，其存储地址为1，每元素占1个地址空间，则a85的地址为（ B ）。A）13 B）33 C）18 D）4045、如果结点A有3个兄弟，而且B为A的双亲，则B的度为（ B ）。A）3 B）4 C）5 D）146、线索二叉树中某结点D，没有左孩子的条件是（ B ）。A）D-Lchild=Null B) D-ltag=1C) D-Rchild=Null D) D-ltag=047、栈进行插入和删除操作的特点是（ A ）。A）LIFO B）FIFOC）FCFS D）HPF48、与无向图相关的术语有（ C ）。A）强连通图 B）入度C）路径 D）弧49、 n个顶点的图的最小生成树必定（ D ），

14、是不正确的描述。A）不唯一 B）权的总和唯一C）不含回路 D）有n条边50、若采用邻接矩阵法存储一个n个顶点的无向图，则该邻接矩阵是一个（ D ）。A）上三角矩阵 B) 稀疏矩阵C) 对角矩阵 D) 对称矩阵51、采用链结构存储线性表时，其地址（ B ）。A）必须是连续的B）连续不连续都可以C）部分地址必须是连续D）必须是不连续的52、倘若在对串的插入、删除运算中，期望运算速度最快，则应采用（ B ）。A）顺序表示法 B）单字符为结点的单链表表示法C）等量分块表示法 D）不等量分块表示法53、在循环队列中，若front与rear 分别表示对头元素和队尾元素的位置，则判断循环队列空的条件是( C

15、 )。A）front=rear+1 B）rear=front+1 C）front=rear D）front=0二、判断题（对的打，错的打 ）1、算法和程序都应具有下面一些特征：有输入，有输出，确定性，有穷性，有效性。（1）2、顺序表和一维数组一样，都可以按下标随机（或直接）访问。（ 1 ）3、线性表的链式存储结构优于顺序存储。（ 0 ）4、对稀疏矩阵进行压缩存储是为了节省存储空间。（ 1）5、数据的逻辑结构反映了数据在计算机中的存储方式。（ 1 ）6、从一个具有n个结点的单链表中查找其值等于x的结点时，在查找成功的情况下，需平均比较 (n+1)/2个元素结点。（ 1 ）7、在具有n个单元的顺序

16、存储的循环队列中，假定front和rear分别为队头指针和队尾指针，则判断队满的条件为：(rear+l)n=front。（ 1 ）8、选择好的哈希函数就可以完全避免冲突的发生。（ 0 ）9、栈和队列都是顺序存取的线性表，它们对存取位置的限制是一样的。（ 0 ）10、在铁路的列车调度中，假设两侧铁道均为单向行驶道，如果进站的列车序列为123456，则一定能得到435612和135426的出站序列。（ 0 ）11、广义表是由零个或多个原子或子表所组成的有限序列，所以广义表可能为空表。（ 0 ）12、数组是一种复杂的数据结构，数组元素之间的关系，即不是线性的也不是树形的。（ 0 ）13、用邻接表存储

17、图所用的空间大小与图的顶点数和边数都有关。（ 0 ）14、设散列表长度为m，散列函数为H（key）=key% p，为了减少发生冲突的可能性，p应取小于m的最大奇数。（ 1 ）15、在排序前，关键字值相等的不同记录间的前后相对位置保持不变的排序方法称为稳定的排序方法。（ 1 ）16、引入线索二叉树的目的是为了能在二叉树中方便的进行插入与删除。（ 0 ）17、算法分析的主要任务是研究数据之间的逻辑关系。（ 0 ）18、在一个长度为n的顺序表中删除第i个元素(0in)时，需向前移动n-i个元素。（ 0 ）19、在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队头指针和队尾指针，则

18、判断队空的条件为：rear=front。（ 0 ）20、在铁路的列车调度中，假设两侧铁道均为单向行驶道，如果进站的列车序列为123456，则只能得到654321的出站序列。（ 0 ）21、在一棵二叉树中，假定每个结点只有左孩子，没有右孩子，对它分别进行前序遍历和中根遍历，则具有相同的结果。（ 0）22、广义表(a,b),a,b)的表头和表尾是相等的。（ 0 ）23、线性表可以看成是广义表的特例，如果广义表中的每个元素是原子，则广义表便成为线性表。（ 1 ）24、插入和删除操作是数据结构中最基本的两种操作，所以这两种操作在数组中也会经常使用。（ 0 ）25、线索二叉树是一种物理结构。（ 1 ）2

19、6、一个带权无向连通图的最小生成树有一棵或多棵。（ 1 ）27、对线性表进行二分查找时，要求线性表必键值有序的表。（ 1 ）29、树中所有结点的度等于所有结点数加1。（ 0 ）30、图的深度优先搜索是一种典型的回溯搜索的例子，可以通过递归算法求解。（ 1 ）三、填空题。1、在一个带头结点的单循环链表中，p指向尾结点的直接前驱，则指向头结点的指针head可用p表示为：p-next-next。2、有向图的边称为 弧 ，边的始点称为 弧尾 ，边的终点称为 弧头 。有向图顶点的度为 出度 和 入度 之和。3、若一个算法中的语句频度之和为T（n）=3n+nlog2n+n2，则算法的时间复杂度为 O(T（

20、n）)_ 。4、如下程序段的时间复杂度为_O(m*n)_ for(i=1; i=n; i+) m=n-i; for (j=1; j=m; j+) sum+=j;5、设某数据结构的二元组形式表示为A=(D，R)，D=1，2，3，4，5，6，7，8，9，R=r，r=，则该数据结构是_树形_结构。6、从一个具有n个结点的单链表中查找值等于x的结点时，在查找成功的情况下，平均比较次数为：_(n+1)/2_。7、在中序线索二叉树中，左线索指向 前驱或左孩子 。8、对于一个以顺序实现的循环队列Q0.m-1，队头、队尾指针分别为f,r，其判空的条件是 f=r ，判满的条件是(r+1)%m=f。9、若已知一个

21、栈的进栈序列是1，2，3， ，n，其输出序列为p1，p2，p3， ，pn，若p1=n，则pi为_n-i+1_。10、设有n个结点的完全二叉树，如果按照从自上到下、从左到右从1开始顺序编号，则第i个结点的右孩子结点的编号为_2n+1_。11、在一棵二叉树中，如果度为2的结点有25个，则该树的叶子结点一定有_26_个。12、在一个具有n个顶点的无向完全图中，包含有_n(n-1)/2_条边。13、线性结构的逻辑特征是 除头结点和尾节点外每个节点仅有一个前驱和一个后继结点 。14、设一组权值集合W=2，3，4，5，6，则由该权值集合构造的哈夫曼树中带权路径长度之和为_45_15、设有向图G中有向边的集

22、合E=，则该图的拓扑序列为_13245_。16、一个队列的入队序列是1，2，3，4，则出队序列为：_1234_。17、设有一个顺序循环队列中有M个存储单元，则该循环队列中最多能够存储_M-1_个队列元素。18、队列Q，经过以下运算：InitQueue(Q)(初始化队列); InQueue(Q,a); InQueue(Q,b); DeQueue(Q, x); DeQueue(Q, x); 后x值是_b_。19、数据结构包括了 数据的逻辑结构 、 数据的存储结构 、 数据的运算 三个方面的容。20、设一棵完全二叉树中有300个结点，则该二叉树的深度为_9_。21、在一个具有n个顶点的有向完全图中，

23、包含有_n*(n-1)_条边。22、一棵深度为 10 的完全二叉树的结点总数的最小值为_29-1_，最大值为_210-1_。23、有一个有序表3，7，8，15，18，22，34， 67，75， 84，92，100,当用二分查找法查找键值为92的结点时，经_3_次比较后查找成功。24、递归算法必须依赖 堆栈 的处理来实现。25、队列的运算特点是 先进先出 ，栈的运算特点是 先进后出 。26、设有向图G中有向边的集合E=，则该图的拓扑序列为_1423_。27、在一个长度为n的顺序表L中，删除下标为i的结点，需要移动的结点数为_n-i-1_。28、假设用front表示队头元素在一维数组中的前一位置，

24、rear表示对尾元素在一维数组中的位置，则队列为空的条件是_front=rear_。29、一棵含7个结点的完全二叉树的深度为_3_。30、已知二维数组A610，每个数组元素占4个存储单元，若按行优先顺序存放数组元素a35的存储地址是1000，则a00的存储地址是_860_。31、含n个顶点的无向连通图中至少含有_n-1_条边。32、对于栈只能在_栈顶_插入和删除元素。33、树是n个节点的有限集合，其中有且仅有一个_根_节点没有前趋节点，而包含度为0的节点称为_n+1/2_节点。34、指向前趋节点和后继节点的指针称为线索，加了线索的二叉树称为_线索二叉树_。35、常用的图的遍历方法有两种；深度优

25、先搜索和_广度优先搜索_。36、为了能有效地应用HASH查找技术，必须解决的两个问题是_构造一个好的hash函数_和_确定解决冲突的方法_。37、顺序表中逻辑上相邻的元素的物理位置 相邻 。单链表中逻辑上相邻的元素的物理位置 不 相邻。38、在一个长度为n的数组的第i个元素(1in+1)之前插入一个元素时，需向后移动 n-i 个元素。四、简答题。1、已知两个一元多项式A(x)和B(x)如下：A(x) = 3 + 5x + 7x5 + 9x15 B(x) = 4x 7x5+ 21x7要求给出图形示意表示：（1）采用单链表表示一元多项式A(x)和B(x)（2）给出求和A(x)+B(x)多项式的单链

26、表（要求给出结点指针变化过程）2、简述以下术语：数据，数据元素、数据对象、数据结构、存储结构。数据：指所有能够输入到计算机中并被计算机程序处理的符号集合。数据元素：数据集合中的一个实体，是计算机程序中加工处理的基本单位。数据对象：性质相同的数据元素的集合。是数据的一个子集。数据结构：相互之间存在一种或多种关系的数据元素的集合。即包括数据元素的集合和数据元素之间的关系的集合。存储结构：数据结构在计算机中的表示（也称映像）叫做物理结构。又称为存储结构。3、简述栈和线性表的差别。4、试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。抽象数据类型包含一般数据类型的概念，但含义比一般

27、数据类型更广、更抽象。一般数据类型由具体语言系统部定义，直接提供给编程者定义用户数据，因此称它们为预定义数据类型。抽象数据类型通常由编程者定义，包括定义它所使用的数据和在这些数据上所进行的操作。5、已知一棵树边的集合为(i,m),(i,n),(e,i),(b,e),(b,d),(a,b),(g,j),(g,k),(c,g),(c,f),(h,l),(c,h),(a,c)用树形表示法画出此树，并回答以下问题。（1） 哪个是根结点？ a（2） 哪些是叶结点？ d m n j k f l（3） 哪个是g的双亲？ c（4） 哪些是g的祖先？ a b c（5） 哪些是g的孩子？ j k（6） 哪些是e的

28、子？ i m n（7） 哪些是e的兄弟？哪些是f的兄弟？ dgfh degh（8） 结点b和n的层次各是多少？ 2 5（9） 树的深度是多少？ 5（10） 以结点c为根的子树的深度是多少？ 2（11） 树的度是多少？ 36、何谓队列的“假溢出”现象，如何解决？假溢出是是队列在一端进入插入，TOP值就会增加，在另一端删除，当判断TOP=MAX-1是，就会说明已经队满，但实际在队列的另一端还是有存储空间的，这就是“假溢出”。 解决方法：设置队列为循环队列就可以了。TOP=（TOP+1）MOD （MAX-1）。7、简述队列和堆栈这两种数据类型的相同点和差异处。8、abdce先序：abdce中序：bd

29、aec后序：dbeca9、对于以下图，试给出：（1）每个顶点的入度，出度。d(1)+ = 1, d(1)- = 2d(2)+ = 2, d(1)- = 2d(3)+ = 3, d(3)- = 1d(4)+ = 3, d(4)- = 0d(5)+ = 2, d(5)- = 3d(6)+ = 1, d(6)- = 2（2）邻接矩阵和入边表图示。（3）强连通分量。23652 1 4 5 6 2 3邻接表 入边表(逆邻接表)10、已知一组元素的排序码为:（46,74,16,53,14,26,40,38,86,65,27,34）写出用直接选择排序方法进行每趟排序的结果。14,74,16,53,46,26

30、,40,38,86,65,27,3414,16,74,53,46,26,40,38,86,65,27,3414,16,26,53,46,74,40,38,86,65,27,3414,16,26,27,46,74,40,38,86,65,53,3414,16,26,27,34,74,40,38,86,65,53,4614,16,26,27,34,38,40,74,86,65,53,4614,16,26,27,34,38,40,74,86,65,53,4614,16,26,27,34,38,40,46,86,65,53,7414,16,26,27,34,38,40,46,53,65,86,7414

31、,16,26,27,34,38,40,46,53,65,86,7414,16,26,27,34,38,40,46,53,65,74,8614,16,26,27,34,38,40,46,53,65,74,8611、设二叉树的顺序存储结构如下：123456 789 1011 121314 15 16 17 18 19 20E AFDHCGIB（1） 根据其存储结构，画出该二叉树。（2） 写出按前序、中序、后序遍历该二叉树所得的结点序列。前序：EADCBFHGI中序：ABCDEFGHI后序：BCDAGIHFE（3） 画出二叉树的后序线索化树。12、已知某电文中只有ABCDE共5个字母，权值集合W=0

32、.25,0.10,0.20,0.30,0.15，试分析Huffman树的生成过程，画出存储结构表（初态和终态），以与最终的Huffman树，并用0/1给ABCDE这5个字母分别编码，最后写出电文：BAACDE的Huffman编码。A(00),B(110),C(10),D(01),E(111).BAACDE(111);13、某系统在通信联络中只可能出现八种字符，它们分别是ABCDEFGH，其概率分别为0.05，0.19，0.18，0.09，0.12，0.23，0.13，0.01。现要对这八种字符进行Huffman编码，写出该编码值。画出该Huffman树(权值大的结点做左孩子)，在所有的结点上标

33、出其权值，并求出这棵树的带权路径长度。 A(01010)B(11) C(000) D(0100) E(011) F(10) G(001) H(01011)L(n)=0.05*5+0.19*2+0.18*3+0.09*4+0.12*3+0.23*2+0.13*3+0.01*5 = 2.7914、已知一组元素为（46，25，78，62，12，37，70，29），试画出按元素排列次序插入生成的一棵二叉排序树。15、简述起泡算法的过程，并写出使用起泡排序方法对下面的整数数列进行排序的结果（写出每趟排序后的结果）： 97，66，49，38，26，17，9，6。66，49，38，26，17，9，6,(97

34、)49，38，26，17，9，6,(66, 97)38，26，17，9，6,(49, 66, 97)26，17，9，6,(38, 49, 66, 97)17，9，6,(26, 38, 49, 66, 97)9，6,(17, 26, 38, 49, 66, 97)6,(9, 17, 26, 38, 49, 66, 97)(6, 9, 17, 26, 38, 49, 66, 97)16、画出以下二叉排序树的平衡结果图，要求：（1）已知初始查找表的关键字序列为（70,100,80,30,75），构造并画出初始二叉排序树，标明各结点平衡因子+。（2）插入关键字20，a. 画出失衡后的二叉排序树，标明各

35、结点平衡因子b. 画出重新平衡后的二叉排序树，标明各结点平衡因子17、什么是有向网？已知有向网G=(V,E)，其中顶点集V=a,b,c,d,e，边集为：E=, , , ，E中的每条边是一个三元组，分别表示弧尾，弧头和边的长度（权重）。画出有向网G，写出其邻接矩阵。18、关键字集合为19, 36,23, 82,14,55,68,11, 01，哈希函数为：Hash(key)=key mod 7，试写出哈希表的链地址处理图。19、写出如下所示二叉树的叶子结点和非终端结点以与各结点所在的层次、树的深度、树的深度，并且写出该树的先序遍历、中序遍历、后序遍历和层次遍历的结果。叶子结点:GHMJ非终端结点:

36、 ABCDEF结点所在层次: A(1),B(2),C(2),D(3),E(3),F(3),G(4)H(4),J(4),M(4)树的深度: 4先序：ABDGEHCFMJ中序：DGBEHACMFJ后序：GDHEBMJFCA层次：ABCDEFGHMJ20、用快速排序方法对数据集23 45 12 90 78 56进行排序，写出快速排序第一趟的详细过程，以与简述后面的递归过程。23 45 12 90 78 5623 45 12 90 78 5623 45 12 90 78 5623 45 12 56 78 9023 45 12 5678 90(23 45 12 56)78(90)21、对于下面两个图，求

37、出：（1）无向图中每个顶点的度，有向图中每个顶点的入度，出度和度。d(0)=4, d(1)=2, d(2)=3, d(3)=3, d(4)=2.d(0)+ = 2, d(0)- = 2, d(1)+ = 1, d(1)- = 2, d(2)+ = 1, d(2)- = 3d(3)+ = 2, d(3)- = 1, d(4)+ = 2, d(0)- = 0（2）画出有向图的邻接距阵。（3）下面是否是连通图或强连通图，如果不是，画出连通分量或强连通分量。403120124322、给出以下AOV网的可能的拓扑排序序列。拓扑排序序列是否唯一？在什么情况下拓扑排序无法完成。CDBAE或DCBAE或不唯一

38、在含有回路的时候拓扑排序无法完成23、已知二叉树的先序序列和中序序列分别为HDACBGFE和ADCBHFEG。（1）画出该二叉树（2）写出其后序序列；ABCDEFGH24、已知带权无向图的邻接表如下所示，其中边表结点的结构为：依此邻接表从顶点C出发进行深度优先遍历。（1）画出由此无向图；（2）写出遍历过程中得到的从顶点C开始的可能的一个顶点序列。DCABEF五、算法阅读题1、阅读下面的算法typedef int Datatype;typedef Struct node Datatype data;Struct node *next;lklist;void delredundant(lklist

39、 *&head) lklist *p,*q,*s; for(p=head;p!=0;p=p-next) for(q=p-next,s=q;q!=0; ) if (q-data=p-data) s-next=q-next; free(q);q=s-next; else s=q;q=q-next; 问：该算法的功能是什么? 2、阅读下面的算法typedef int Datatype;typedef Struct node Datatype data;Struct node *lchild,*rchild; bitree;bitree *q20; int r=0,f=0,flag=0;void pr

40、eorder(bitree *bt, char x) if (bt!=0 & flag=0)if (bt-data=x) flag=1; return;else r=(r+1)%20; qr=bt; preorder(bt-lchild,x); preorder(bt-rchild,x); void parent(bitree *bt,char x) int i; preorder(bt,x); for(i=f+1; ilchild-data=x | qi-rchild-data) break; if (flag=0) printf(not found xn); else if (idata)

41、; else printf(not parent);问：该算法的功能是什么？找到根节点到某个节点的路径3、阅读下面的算法int minnum=-32768,flag=1;typedef Struct nodeint key; Struct node *lchild,*rchild;bitree;void inorder(bitree *bt) if (bt!=0) inorder(bt-lchild); if(minnumbt-key)flag=0; minnum=bt-key; inorder(bt-rchild);问：该算法的功能是什么？找最小值4、已知一个算法设计如下：LinkList

42、mynote(LinkList L) /L是不带头结点的单链表的头指针 if(L&L-next) q=L；L=Lnext；p=L； S1： while(pnext) p=pnext；S2： pnext=q；qnext=NULL； return L； 问：（1）说明语句S1的功能（2）说明语句组S2的功能（3）设链表表示的线性表为（a1,a2, ,an）,写出算法执行后的返回值所表示的线性表5、已知一个算法设计如下：int unkown(JD r,int n,int k) int low,high,mid,found; low=1; high=n; found=0;while(lowrmid.k

43、ey) low=mid+1; else if(k=rmid.key) found=1; else high=mid-1; if(found=1) return(mid);else return(0);问：该算法的功能是什么？二分查找关键字，若找到返回其下标，若没有找到返回06、已知二叉树的存储结构为二叉链表，阅读下面算法。 typedef Struct node DateType data； Struct node * next； ListNode； typedef ListNode * LinkList ； LinkList Leafhead=NULL； Void Inorder (BinT

44、ree T) LinkList s； If(T) Inorder(Tlchild)； If (!Tlchild)&(!Trchild) s=(ListNode*)malloc(sizeof(ListNode)； sdata=Tdata； snext=Leafhead； Leafhead=s； Inorder(Trchild)； 对于如下所示的二叉树(1) 画出执行上述算法后所建立的结构；(2) 说明该算法的功能。中序建立线索二叉树7、 已知一个算法设计如下：void ABC(BTNode * BT) if BT ABC (BT-left); ABC (BT-right); coutdata0)

45、&(flag=1) flag=0; for(j=1;jrj+1.key) flag=1; x=rj; rj=rj+1; rj+1=x; m-; 问：该算法的功能是什么？冒泡法升序排列某个数组9、阅读下面的算法typedef char Datatype;typedef Struct node Datatype data; Struct node *lchild,*rchild; bitree;void createbitree(bitree *&bt) char ch; scanf(%c,&ch); if(ch=#) bt=0; return;bt=(bitree*)malloc(sizeof(

46、bitree);bt-data=ch;createbitree(bt-lchild); createbitree(bt-rchild);问：该算法的功能是什么？先序创建二叉树10、阅读下面的算法void Search(BTNode * BT) if BT Search(BT-left);Search(BT-right); coutdatalchild) _ (1) ADDQ(Q, p-lchild)_; /左孩子不空，左孩子入队if(p-rchild) _ (2)ADDQ(Q, p-rchild)_; /右孩子不空，右孩子入队/下面交换左右孩子q=_（3）p-rchild_; /p-rchil

47、d=_（4）p-lchild_; _ （5）p-lchild_=q; 2、以下算法将以二叉链表存储的二叉树中的叶子结点按从左到右的顺序链成一个带头结点的双向循环链表，时，结点的Lchild域作为前链域，指向结点的直接前驱，结点的Rchild域作为后链域，指向结点的直接后继。算法中，使用一个顺序栈stack，栈顶指针为top，p，t为辅助指针，head为双向循环链表的头指针。试填充算法中的空格，以完整算法。void leafchain(BiTree &bt)p=(BiTree)malloc(sizeof(BiTNode); if(!p)printf(“OVERFLOWn”;exit(1); he

48、ad=p; top=1; if(bt) /如果树不为空 top+; stacktop=bt; / 入栈 while(top) /栈不空 t=stacktop; top-; / 出栈 if(!t-Lchild & !t-Rchild) /该节点的左右孩子都为空，那么这是叶子节点/双链表的创建操作 (1) p-Rchild = t; t-Lchild=p; (2) t-Rchild = NULL; else if( (3) t-Lchild)top+; stacktop= t-Rchild ; /如果有左孩子那么左孩子入栈 if( (4) t-Rchild)top+; stacktop= (5)

49、; /如果有右孩子那么右孩子入栈 p-Rchild=head; head-Lchild=p; /构成循环链表 3、以下算法的功能是在链式结构上实现简单项选择择排序，请在空白处填入适当的容。void simpleselectsorlklist(lklist *&head) lklist *p,*q,*s; int min,t; if(head=0 |head-next=0) return;/如果为空表或只有一个节点，不用排序了 for(q=head; q!=0;q=q-next) /只要节点存在，那么一直向后移动/此时的q一直指向乱序的第一个位置 （1）min = q-data； /min赋初值s=q; /s指向无序的第一个元素 for(p=q-next; p!=0;p=p-next) /p从s的下一个位置开始找if