2022年数据结构与算法复习题,DOC.pdf

《2022年数据结构与算法复习题,DOC.pdf》由会员分享，可在线阅读，更多相关《2022年数据结构与算法复习题,DOC.pdf（13页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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

2、n(n-1) 5、数据结构中，在逻辑上可以把数据结构分成（ 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) 4 B)3 C)2 D)12

3、8、设单链表中指针p 指向结点 m ，若要删除 m之后的结点（若存在），则需修改指针的操作为（ 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）n B）2e C ）e D） n+e 10、对下图 V4的度为（ C ） 。A）1 B）2 C）3 D）4 v1 v2 v3 v4 11、在一棵度为 3 的树中，度为 3 的结点个数为 2，度为 2 的结点个数为 1，则度为 0 的结点个数为（ C ） 。A）4 B）5 C）6 D）7

4、 12、在数据结构中，从逻辑上可以把数据结构分为（ C ） 。A）动态结构和静态结构 B）紧凑结构和非紧凑结构C）线性结构和非线性结构 D）内部结构和外部结构13、用一维数组 A进行顺序存储时，若起始地址为loc(A1) ，元素长度为 c，则A的第 i 个数组单元在存放地址loc(Ai)，等于（ B ） 。A）loc(A1)+i*c B）loc(A1)+(i-1)*c C）loc(A1)+i*c+1 D）loc(A1)+(i+1)*c 14、 （ C ）在进行插入操作时，常产生假溢出现象。A）顺序栈 B）循环队列C）顺序队列 D）链队列15、 某线性表中最常用的操作是在最后一个元素之后插入一个

5、元素和删除第一个元素，则采用（ D ）存储方式最节省运算时间。 A) 单链表 B) 仅有头指针的单循环链表 C) 双链表 D) 仅有尾指针的单循环链表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

6、) rear=front-next; D) front=rear-next ; 18、已知栈的最大容量为4。若进栈序列为 1，2，3，4，5，6，且进栈和出栈可以穿插进行 , 则可能出现的出栈序列为（ C ） 。 A) 5，4，3，2，1，6 B) 2 ，3，5，6，1，4 C) 3 ，2，5，4，1，6 D) 1 ，4，6，5，2，3 19、已知广义表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)

7、 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 1 页，共 13 页 - - - - - - - - - - D)Head(Tail(Head(Tail(Tail(L) 20、下列各种数据结构中属于线性结构的有（ A ） 。 A）栈 B) 二叉树 C) 广义表 D) 图21、倘若在对串的插入、删除运算中，期望运算速度最快，则应采用（ C ） 。 A）顺序表示法 B）单字符为结点的单链表表示法 C）等量分块表示法 D）不等量分块表示法22、广义表 head(a,b),(c,d)的运算结果为（ A ） 。

8、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) 只能进行插入 D) 只能进行删除26、以下属于顺序存储结构优点的是（ A ） 。 A) 存储密度大B) 插入运算方便 C）删除运算方便D ）可方便地用于各种逻辑结构的存储表示27、数

9、据结构研究的内容是（ 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=p D）p-next=s; s-next=q; 29、若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ D ）存储方式最节省时间。 A ）顺序表B）双链表C）带头结点

10、的双循环链表D ）单循环链表30、下面关于线性表的叙述中，错误的是哪一个？（ D ） A ）线性表采用顺序存储，必须占用一片连续的存储单元。 B）线性表采用链接存储，便于插入和删除操作。 C）线性表采用链接存储，不必占用一片连续的存储单元。 D）线性表采用顺序存储，便于进行插入和删除操作。31、在一个具有 n 个单元的顺序栈中，假定以地址低端（即0 单元）作为栈底，以 top 作为栈顶指针，当做出栈处理时，top 变化为（ C ） 。 A ）top 不变 B ）top=0 C）top- D ）top+ 32、在一个链队列中，假定front和 rear 分别为队首和队尾指针，则插入一个结点的操作

11、为（ 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, A 34、 广义表 A= （A,B,(C ,D), (E,(F,G)） ， 则 head(tail(head(tail(tail(A)=（ D ） 。 A ） (G) B） (D)

12、 C ） C D） D 35、设给定问题的规模为变量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-next B）p=p-next C）p=p-nexe-next D）p-next=p 41、设一数列的

13、顺序为1，2，3，4，5，6，通过栈结构不可能排成的顺序数列为（ B ） 。A）3，2，5，6，4，1 B）1，5，4，6，2，3 C）2，4，3，5，1，6 D）4，5，3，6，2，1 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 2 页，共 13 页 - - - - - - - - - - 42、若一棵二叉树具有10 个度为 2 的结点，5 个度为 1 的结点，则度为 0 的结点的个数是 ( B )。A）9 B）11 C）15 D）不能确定43、对待排序的元素序列进行划分，将其分为左、右两个子序列，

14、再对两个子序列施加同样的排序操作，直到子序列为空或只剩一个元素为止。这样的排序方法是（ A ） 。A）直接选择排序 B）直接插入排序C ）快速排序 D）起泡排序44、设有一个 10 阶的对称矩阵 A，采用压缩存储方式，以行序为主存储，a11为第一个元素，其存储地址为1，每元素占 1 个地址空间，则 a85的地址为（ B ） 。A）13 B）33 C）18 D）40 45、如果结点 A有 3 个兄弟，而且 B为 A的双亲，则 B的度为（ B ） 。A）3 B）4 C）5 D）1 46、线索二叉树中某结点D ，没有左孩子的条件是（ B ） 。A）D-Lchild=Null B) D-ltag=1

15、C) D-Rchild=Null D) D-ltag=0 47、栈进行插入和删除操作的特点是（ A ） 。A）LIFO B）FIFO C）FCFS D）HPF 48、与无向图相关的术语有（ C ） 。A）强连通图 B）入度C）路径 D）弧49、 n 个顶点的图的最小生成树必定（ D ） ，是不正确的描述。A）不唯一 B）权的总和唯一C）不含回路 D）有 n 条边50、 若采用邻接矩阵法存储一个n个顶点的无向图，则该邻接矩阵是一个（ D ） 。A）上三角矩阵 B) 稀疏矩阵C) 对角矩阵 D) 对称矩阵51、采用链结构存储线性表时，其地址（ B ） 。A）必须是连续的 B）连续不连续都可以C）部

16、分地址必须是连续 D）必须是不连续的52、倘若在对串的插入、删除运算中，期望运算速度最快，则应采用（ B ） 。A）顺序表示法 B）单字符为结点的单链表表示法C）等量分块表示法 D）不等量分块表示法53、在循环队列中，若front与 rear 分别表示对头元素和队尾元素的位置，则判断循环队列空的条件是 ( C )。A）front=rear+1 B）rear=front+1 C ）front=rear D）front=0二、判断题（对的打，错的打）1、算法和程序都应具有下面一些特征：有输入，有输出，确定性，有穷性，有效性。（1 ）2、顺序表和一维数组一样，都可以按下标随机（或直接）访问。（1 ）

17、3、线性表的链式存储结构优于顺序存储。（0 ）4、对稀疏矩阵进行压缩存储是为了节省存储空间。（1 ）5、数据的逻辑结构反映了数据在计算机中的存储方式。（1 ）6、从一个具有 n 个结点的单链表中查找其值等于x 的结点时，在查找成功的情况下，需平均比较(n+1)/2 个元素结点。（1 ）7、在具有 n 个单元的顺序存储的循环队列中，假定 front 和 rear分别为队头指针和队尾指针，则判断队满的条件为：(rear+l)n= = front。 （1 ）8、选择好的哈希函数就可以完全避免冲突的发生。（0 ）9、 栈和队列都是顺序存取的线性表，它们对存取位置的限制是一样的。 （0 ）10、在铁路的

18、列车调度中， 假设两侧铁道均为单向行驶道，如果进站的列车序列为 123456，则一定能得到435612和 135426的出站序列。（0 ）11、广义表是由零个或多个原子或子表所组成的有限序列，所以广义表可能为空表。 （0 ）12、数组是一种复杂的数据结构， 数组元素之间的关系， 即不是线性的也不是树形的。 （0 ）13、用邻接表存储图所用的空间大小与图的顶点数和边数都有关。（0 ）14、设散列表长度为 m，散列函数为 H（key）=key% p，为了减少发生冲突的可能性， p 应取小于 m 的最大奇数。（1 ）15、 在排序前，关键字值相等的不同记录间的前后相对位置保持不变的排序方法称为稳定的

19、排序方法。（1 ）16、 引入线索二叉树的目的是为了能在二叉树中方便的进行插入与删除。（0 ）17、算法分析的主要任务是研究数据之间的逻辑关系。（0 ）18、在一个长度为 n 的顺序表中删除第i 个元素 (0 i n)时，需向前移动 n i 个元素。 （0 ）19、在具有 n 个单元的顺序存储的循环队列中，假定front 和 rear分别为队头指针和队尾指针，则判断队空的条件为：rear= = front。 （0 ）20、在铁路的列车调度中， 假设两侧铁道均为单向行驶道，如果进站的列车序列为 123456，则只能得到 654321的出站序列。（0 ）21、在一棵二叉树中，假定每个结点只有左孩子

20、，没有右孩子，对它分别进行前序遍历和中根遍历，则具有相同的结果。（0 ）22、广义表 (a,b),a,b)的表头和表尾是相等的。（0 ）23、线性表可以看成是广义表的特例，如果广义表中的每个元素是原子，则广义表便成为线性表。（1 ）精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 3 页，共 13 页 - - - - - - - - - - 24、插入和删除操作是数据结构中最基本的两种操作，所以这两种操作在数组中也会经常使用。（0 ）25、线索二叉树是一种物理结构。 （ 1 ）26、一个带权无向连通图的最小

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

22、为_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、若已知一个栈的进栈序列是1，2

23、，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

24、 中有向边的集合 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、在一个具

25、有 n 个顶点的有向完全图中，包含有_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、

26、假设用 front表示队头元素在一维数组中的前一位置，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、

27、指向前趋节点和后继节点的指针称为线索，加了线索的二叉树称为_线索二叉树 _。35、常用的图的遍历方法有两种；深度优先搜索和_广度优先搜索 _。精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 4 页，共 13 页 - - - - - - - - - - 36、为了能有效地应用HASH查找技术，必须解决的两个问题是_构造一个好的 hash 函数_和_确定解决冲突的方法 _。37、顺序表中逻辑上相邻的元素的物理位置相邻 。单链表中逻辑上相邻的元素的物理位置不 相邻。38、在一个长度为n 的数组的第 i 个元素

28、(1in+1)之前插入一个元素时，需向后移动n-i 个元素。四、简答题。1、已知两个一元多项式A(x)和 B(x)如下：A(x) = 3 + 5x + 7x5 + 9x15B(x) = 4x 7x5+ 21x7 要求给出图形示意表示：（1）采用单链表表示一元多项式A(x)和 B(x) （2）给出求和 A(x)+B(x)多项式的单链表（要求给出结点指针变化过程）2、简述下列术语：数据，数据元素、数据对象、数据结构、存储结构。数据：指所有能够输入到计算机中并被计算机程序处理的符号集合。数据元素：数据集合中的一个实体，是计算机程序中加工处理的基本单位。数据对象：性质相同的数据元素的集合。是数据的一个

29、子集。数据结构：相互之间存在一种或多种关系的数据元素的集合。即包括数据元素的集合和数据元素之间的关系的集合。存储结构：数据结构在计算机中的表示（也称映像）叫做物理结构。又称为存储结构。3、简述栈和线性表的差别。4、试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。抽象数据类型包含一般数据类型的概念，但含义比一般数据类型更广、更抽象。一般数据类型由具体语言系统内部定义，直接提供给编程者定义用户数据，因此称它们为预定义数据类型。抽象数据类型通常由编程者定义，包括定义它所使用的数据和在这些数据上所进行的操作。5、已知一棵树边的集合为(i,m),(i,n),(e,i),(b,e),

30、(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 的子孙？ i m n （7） 哪些是 e 的兄弟？哪些是 f 的兄弟？ dgfh degh （8） 结点 b 和 n 的层次各是多少？ 2 5 （9） 树的深度是多少？ 5 （10）以结点 c 为根的子树的深度是多少？ 2 （11）树的度是多

31、少？ 3 6、何谓队列的“假溢出”现象，如何解决？假溢出是是队列在一端进入插入，TOP值就会增加，在另一端删除，当判断TOP=MAX-1 是，就会说明已经队满， 但实际在队列的另一端还是有存储空间的，这就是“假溢出”。解决方法：设置队列为循环队列就可以了。TOP= （TOP+1 ）MOD （MAX-1 ） 。7、简述队列和堆栈这两种数据类型的相同点和差异处。8、先序： abdce 中序： bdaec 后序： dbeca 9、对于下图，试给出：（1）每个顶点的入度，出度。d(1)+ = 1, d(1)- = 2 d(2)+ = 2, d(1)- = 2 d(3)+ = 3, d(3)- = 1

32、d(4)+ = 3, d(4)- = 0 d(5)+ = 2, d(5)- = 3 d(6)+ = 1, d(6)- = 2 （2）邻接矩阵和入边表图示。（3）强连通分量。23652 a b d c e 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 5 页，共 13 页 - - - - - - - - - - 1 4 5 6 2 3 邻接表000010001011000000111000000101001000入边表 (逆邻接表 )000100100100010101000010110000010010

33、10、已知一组元素的排序码为: （46,74,16,53,14,26,40,38,86,65,27,34）写出用直接选择排序方法进行每趟排序的结果。【14】,74,16,53,46,26,40,38,86,65,27,34 【14,16 】,74,53,46,26,40,38,86,65,27,34 【14,16,26 】,53,46,74,40,38,86,65,27,34 【14,16,26,27 】,46,74,40,38,86,65,53,34 【14,16,26,27,34】,74,40,38,86,65,53,46 【14,16,26,27,34,38】,40,74,86,65,5

34、3,46 【14,16,26,27,34,38,40】,74,86,65,53,46 【14,16,26,27,34,38,40,46】,86,65,53,74 【14,16,26,27,34,38,40,46,53】,65,86,74 【14,16,26,27,34,38,40,46,53,65】,86,74 【14,16,26,27,34,38,40,46,53,65,74】,86 【14,16,26,27,34,38,40,46,53,65,74,86】11、设二叉树的顺序存储结构如下：123456 789 1011 1213 14 15 16 17 18 19 20 E AF D H

35、C G I B （1） 根据其存储结构，画出该二叉树。（2） 写出按前序、中序、后序遍历该二叉树所得的结点序列。前序：EADCBFHGI 中序：ABCDEFGHI 后序：BCDAGIHFE （3） 画出二叉树的后序线索化树。12 、 已 知 某 电 文 中 只 有ABCDE 共5个 字 母 ， 权 值 集 合W=0.25,0.10,0.20,0.30,0.15， 试分析 Huffman 树的生成过程， 画出存储结构表（初态和终态），以及最终的 Huffman 树，并用 0/1 给 ABCDE 这 5 个字母分别编码，最后写出电文： BAACDE 的 Huffman 编码。A(00),B(110

36、),C(10),D(01),E(111). BAACDE(11000001001111); 13、某系统在通信联络中只可能出现八种字符，它们分别是ABCDEFGH，其概率分别为 0.05 ，0.19 ，0.18 ，0.09 ，0.12 ，0.23 ，0.13，0.01。现要对这八种字符进行 Huffman 编码，写出该编码值。画出该Huffman 树(权值大的结点做左孩子) ，在所有的结点上标出其权值，并求出这棵树的带权路径长度。精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 6 页，共 13 页 - -

37、 - - - - - - - - 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.79 14、已知一组元素为（ 46，25，78，62，12，37，70，29） ，试画出按元素排列次序插入生成的一棵二叉排序树。15、简述起泡算法的过程，并写出使用起泡排序方法对下面的整数数列进行排序的结果（写出每趟排序后的结果） ： 97 ，66，49，38，26，17，9，6 。66，49，38，26，17，9，

38、6,(97) 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.

39、 画出失衡后的二叉排序树，标明各结点平衡因子b. 画出重新平衡后的二叉排序树，标明各结点平衡因子17、什么是有向网？已知有向网G=(V,E)，其中顶点集 V=a,b,c,d,e ，边集为：E=, , , ，E 中的每条边是一个三元组，分别表示弧尾，弧头和边的长度（权重） 。画出有向网 G，写出其邻接矩阵。0030020000010000100000005精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 7 页，共 13 页 - - - - - - - - - - 18、 关键字集合为 19, 36,23,

40、82,14,55,68,11, 01， 哈希函数为：Hash(key)=key mod 7，试写出哈希表的链地址处理图。19、写出如下所示二叉树的叶子结点和非终端结点以及各结点所在的层次、树的深度、树的深度，并且写出该树的先序遍历、中序遍历、后序遍历和层次遍历的结果。叶子结点 : GHMJ 非终端结点 : 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 层次： ABCDEFGHMJ ABCDEFGHMJ20

41、、用快速排序方法对数据集 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 56 78 90(23 45 12 56) 78 (90)21、对于下面两个图，求出：（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(

42、2)+ = 1, d(2)- = 3 d(3)+ = 2, d(3)- = 1, d(4)+ = 2, d(0)- = 0 （2）画出有向图的邻接距阵。0000010000110010010101001（3）下面是否是连通图或强连通图，如果不是，画出连通分量或强连通分量。22、给出下列 AOV 网的可能的拓扑排序序列。拓扑排序序列是否唯一？在什么情况下拓扑排序无法完成。CDBAE 或 DCBAE 或不唯一在含有回路的时候拓扑排序无法完成AEBDC23、已知二叉树的先序序列和中序序列分别为HDACBGFE 和 ADCBHFEG 。（1）画出该二叉树4 0 3 1 2 0 1 2 4 3 精品资料

43、 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 8 页，共 13 页 - - - - - - - - - - （2）写出其后序序列；ABCDEFGH 24、已知带权无向图的邻接表如下所示，其中边表结点的结构为：依此邻接表从顶点C 出发进行深度优先遍历。（1）画出由此无向图；（2）写出遍历过程中得到的从顶点C 开始的可能的一个顶点序列。DCABEF 五、算法阅读题1、阅读下面的算法typedef int Datatype; typedef Struct node Datatype data; Struct node

44、 *next; lklist; void delredundant(lklist *&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;

45、 bitree; bitree *q20; int r=0,f=0,flag=0; void preorder(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 )

46、break; if (flag= =0) printf(not found xn); else if (idata); else printf(not parent); 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 9 页，共 13 页 - - - - - - - - - - 问：该算法的功能是什么？找到根节点到某个节点的路径3、阅读下面的算法int minnum=-32768, flag=1; typedef Struct node int key; Struct node *lchild,*rchi

47、ld; bitree; void inorder(bitree *bt) if (bt!=0) inorder(bt-lchild); if(minnumbt-key) flag=0; minnum=bt-key; inorder(bt-rchild); 问：该算法的功能是什么？找最小值4、已知一个算法设计如下：LinkList mynote(LinkList L) /L 是不带头结点的单链表的头指针if(L&L-next) q=L；L=L next；p=L；S1：while(pnext) p=pnext；S2：pnext=q；qnext=NULL ；return L； 问：（1）说明语句 S

48、1的功能（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.key) low=mid+1; else if(k= =rmid.key) found=1; else high=mid-1; if(found= =1) return(mid); else return(0); 问：该算法的功能是什么？二分查找关键字，若找到返回

49、其下标，若没有找到返回0 6、已知二叉树的存储结构为二叉链表，阅读下面算法。typedef Struct node DateType data ；Struct node * next；ListNode；typedef ListNode * LinkList ；LinkList Leafhead=NULL ；Void Inorder (BinTree T) LinkList s；If(T) Inorder(Tlchild) ；If (!T lchild)&(!T rchild) s=(ListNode*)malloc(sizeof(ListNode) ；sdata=Tdata；snext=Lea

50、fhead；Leafhead=s ； Inorder(Trchild) ； 对于如下所示的二叉树(1) 画出执行上述算法后所建立的结构；(2) 说明该算法的功能。精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 10 页，共 13 页 - - - - - - - - - - 中序建立线索二叉树7、 已知一个算法设计如下：void ABC(BTNode * BT) if BT ABC (BT-left); ABC (BT-right); coutdata0)&(flag=1) flag=0; for(j=1;