《数据结构》 期末试题及答案 共3套.docxVIP

《数据结构》期末考试 试卷1 一，简答题(每题5分，共20分) 1、具有n个结点的k又树，若采用k又链表存储，则空链域有多少个？(要 求写出求解步骤)。 2、分析二叉排序树的性能(最好、最坏和平均查找性能)。 3、希尔排序基本思想。 4、图遍历中，设置访问标志数组visited]]的作用。 二、单项选择题(每题1分，共10分)1、在一棵平衡二叉排序树中，每个结点的平衡因子的取值范围是() A)-l~lB)-2~2 C)1-2D)0~l2、在单链表中，下列说法正确的是() A)单链表中头结点是必不可少的；B)单链表中头指针是必不可少的； C)在单链表中可以实现随机存取；D)单链表的存储密度小于顺序表3、假设以数组A[M]存放循环队列的元素，其头尾指示器分别为front和rear, 则当前队列中的元素个数为()o A) rear-front+1B) (rear-front+l)%M C) (front-rear +M)%MD) (rear-front+M)%M4、已知广义表L=((a,b,c), (d,e,f)),运用下列()运算可以得到结果:eo A) head (tail(L))B) tail(head(L)) C) head(tai 1(head(tai 1(L)))) D) head(tai 1(tai 1(head (L))))5、线索二叉树中，某结点p是叶子结点，下列()表达式的值为真。 A) p-lchild= =NULLB) p-ltag= =1p-rtag= =1 C) p-ltag= =0D) p-lchild= =NULL p-rchild= =NULL6、一个具有567个结点的完全二叉树的高度为() A) 9 B) 10 C) 11 D) 127、具有n个顶点的强连通图，至少有()条边 A) n-1 B) n C) n(n-l) D) n(n-l)/28、在含n个顶点和。条边的无向图的邻接矩阵中，零元素的个数为() A) e B) 2e C) n2-e D)n2-2e《数据结构》期末考试试卷2参考答案 一、 简答题1、n个结点的k叉树采用k叉链表存储，链域总数为k*n,又：『B+1.B为分支总数即非 空链域总数,B=n-1,所以空链域总数为:（k-l） *n+U2、访问标志数组的作用是：保证图中的每个顶点都被访问到，且仅访问一次。 3、折半查找的前提条件是1）列表元素顺序存储：2）列表元素按关键字有序存储： 4、冒泡排序最好情况：移动元素次数为0,关键字比较次数为：n-I次； 冒泡排序最坏情况：移动元素次数为3n*（n-l）/2,关键字比较次数为n*（n-l）/2o二、选择题 二、选择题 LA2.D3.D 二、选择题 LA2.D3.D 二、选择题LA2.D3.D4.C5.C 二、选择题 LA2.D3.D 4.C5.C 6. A 7.D8.B 9.D I0.B 三、 填空题 三、 填空题 三、 填空题1、O (log2n 三、 填空题 1、O (log2n) 5、最少k,最多2k-l 2、p-itag= =1p-rtag= =13、n-14、稠密 6、1.4237、高度为48、快速排序 四、 构造题 1. 1）该树的孩子兄弟表示法为：（2分） 2）转化的二叉树为：（2分） 3）先序遍历序列为：ABECFGD （2分）后序遍历序列为:EBFGCDA （2分）2. I）此为有向图的邻接表表示法，该图为: 2）深度优先搜索得到的遍历序列为：VI, V4, V5, V6, V2, V7, V3; 深度优先生成树为： 3）其邻接矩阵表示法为： 顶点数组：邻接矩阵: 1 VI 0 0 0 1 1 0 1 2 V2 0 0 0 1 0 0 0 3 V3 0 0 0 0 0 1 1 4 V4 0 0 0 0 0 0 0 5 V5 0 1 0 0 0 1 0 6 V6 0 0 0 0 0 0 0 7 V7 0 0 1 1 1 0 0 3、1）构造的哈希表为：（4分）2) 地址 0 I 2 3 4 5 6 7 8 9 元素 63 36 22 40 13 6 比较 次数 1 1 2 1 1 2 (2 分)查找成功时的 AS L=(l + l + 2+l + l+ 2)/6 = 8/6 o r 4/3 (2 分)查找不成功时的 AS L= (4 + 3 + 24-1 + 1+4 + 3) / 7 = 1 8/74、据题意，欲得到递增有序，需要建大根堆（I分）。建初堆过程如下: 初始状态（从13开始调整（1 初始状态（从13开始调整（1分）） 初始状态（从13开始调整（1分）） 初始状态（从13开始调整（1分））（调整完毕，从15开始调整（1 初始状态（从13开始调整（1分）） （调整完毕，从15开始调整（1分）） （调整完毕，从3