一、单项选择题(每题 2分,共10分)
1.表头表尾均为空表的广义表是( )。
① () ② (()) ③ ((),()) ④ ((()))
2. 对 下列 4个序列,以第一个关键字为基础进行用快速排序算法进行排序,在第一趟过程中移动记录次数最多的是 ( )
① 92,96,100,110,42,35,30,88
② 92,96,88,42,30,35,110,100
③ 100,96,92,35,30,110,88,42
④ 42,30,35,92,100,96,88,110
3. 实现图的广度优先搜索算法时,使用的数据结构是 ( )
① 栈
② 队列
③ 十字链表
④ 三元组
4.在有向图G的邻接矩阵中,顶点Vi 的度是 ( )。
① 邻接矩阵中第 i行元素之和
② 邻接矩阵中第 i列元素之和
③ 邻接矩阵中第 i行和第i列元素之和
④ 邻接矩阵中第 i行元素之和与第i列元素之和的最大值
5.能有效缩短关键路径长度的方法是( )
① 缩短任意一个活动的持续时间
② 缩短关键路径上任意一个关键活动的持续时间
③ 缩短多条关键路径上共有的任意一个关键活动的持续时间
④ 缩短所有关键路径上共有的任意一个关键活动的持续时间
二、填空题(每空 2分,共 8 分)
1. 由一棵二叉树的后序序列和 可唯一确定这棵二叉树。
2. 二叉树结点数 n与边数e的关系为 。
3. 在各种查找算法中,平均查找长度与关键字个数 n无关的方法是 。
4. 若希望得到树高较矮的生成树,则采用图的 遍历算法。
三、判断题(用√表示对,用×表示错。每题 2分,共 12 分)
1. 循环队列中不存在队列满的问题。( )
2. 将一个新结点插入到二叉排序树中,该结点一定成为叶结点。( )
3. 用单链表示的有序表可以使用折半查找方法来提高查找速度。( )
4. 若有向图中每个顶点的入度和出度均为 1,则该有向图必有回路。( )
5. 已知二叉排序树的先序序列,能唯一确定该二叉排序树。( )
6. 交换完全二叉树所有结点的左右子树,得到的二叉树仍是完全二叉树。( )
四、简答题(每题 6分,共 30 分)
1.若一个有向图的邻接矩阵中主对角线以下的元素均为0,则该图一定不存在回路。该说法是否正确?为什么?
2. 在完全二叉树中,设结点数为 n,
( 1)如何断定该完全二叉树中度为1的结点数n1?
( 2)给定结点x的编号m,又如何根据该编号断定x是否为叶结点?
3. 当查找表有既能较快查找又能适应动态变化的需求时,选用什么查找方法最适合?并简述其理由。
4. 在某个通信系统中,报文的字符集为 a,b,c,d,e,f,g,h八种,其出现频率分别为6,28,8,9,13,22,4和1,试为各字符设计二进制编码,使得报文编码长度最短。给出各字符的二进制编码和报文编码长度。
5. 设 L是不带头结点单链表的头指针,P是指向链表中某个结点的指针,该结点既不是第一个结点,也不是最后一个结点,S是指向待插入新结点的指针,用下面 ① -- ⑦选项完成 A、B功能。
A. 在P所指结点前面插入 S所指结点的语句序列是( );
B. 在第一个结点前面插入 S所指结点的语句序列是( );
① P↑.next :=S;
② Q:= P;
③ L:= S;
④ P:= L;
⑤ WHILE ( P↑.next <> Q ) DO P:= P↑.next;
⑥ S↑.next:= P↑.next;
⑦ S↑.next:= L↑.next;
五、算法题(共 15 分)
1. 设p,q分别指向两个不带头结点的单循环链表中的某个结点,试编写一个算法,用O(1)时间将这两个单链表合并为一个,并令p指向p和q两者data域值较小的结点。(5分)
PROC xyz( p, q );
{ p,q分别指向两个不带头结点的单循环链表中的某个结点,结点结构为数据域data和指针域next}
ENDP;
2. 设二叉树采用二叉链表存储,结点结构为 lchild、data和rchild,试编写输出二叉树中从根结点到每个叶结点的路径的算法。设二叉树最长路径结点个数小于m,可以使用队列S[1:m],初始时S.rear=S.front=1。(10分)
PROC RootToLeaf(bt:bitreptr );
{ bt为二叉树根指针,S[1:m]为队列, 初始时S.rear=S.front=1}
ENDP;{ RootToLeaf }
责任编辑:虫虫