数据结构——用C语言描述（第3版）试卷答案1.docx

《数据结构（第三版）》 耿国华等编 高等教育出版社 《数据结构》期末考试 试卷1 一、简答题（每题5分，共20分） 1、具有n个结点的k叉树，若采用k叉链表存储，则空链域有多少个？（要求写出求解步骤）。 2、分析二叉排序树的性能（最好、最坏和平均查找性能）。 3、希尔排序基本思想。 4、图遍历中，设置访问标志数组visited[]的作用。 二、单项选择题（每题1分，共10分） 1、 在一棵平衡二叉排序树中，每个结点的平衡因子的取值范围是（ ） A) -1~1 B) -2~2 C) 1~2 D) 0~1 2、 在单链表中，下列说法正确的是（） A) 单链表中头结点是必不可少的； B) 单链表中头指针是必不可少的； C) 在单链表中可以实现随机存取； D) 单链表的存储密度小于顺序表 3、假设以数组A[M]存放循环队列的元素，其头尾指示器分别为front和rear，则当前队列中的元素个数为( )。 A) rear-front+1 B) (rear-front+1)%M C) (front-rear +M)%M D) (rear-front+M)%M 4、已知广义表L=((a,b,c),(d,e,f)),运用下列（ ）运算可以得到结果：e。 A) head（tail(L)）　　　 B) tail(head(L)) C) head(tail(head(tail(L))))　D) head(tail(tail(head(L)))) 5、 线索二叉树中，某结点p是叶子结点,下列（ ）表达式的值为真。 A) p-lchild= =NULL?? B) p-ltag= =1p-rtag= =1 C) p-ltag= =0? D) p-lchild= =NULL p-rchild= =NULL 6、一个具有567个结点的完全二叉树的高度为（? ? ） A) 9? B) 10 ?? C) 11 ?? D) 12 7、具有n个顶点的强连通图，至少有（ ?）条边 A) n-1?????? B) n????C) n(n-1)???? D) n(n-1)/2 8、在含n个顶点和e条边的无向图的邻接矩阵中，零元素的个数为（） A) e B) 2e C) n2-e D)n2-2e 9、对关键字序列(20,15,14,18,36,40,10,21) 进行快速排序，以第一个关键字为基准得到的一趟划分后的结果是（ ）。 A) (10,15,14,18,20,36,40,21) B) (10,15,14,18,20,40,36,21) C) (10,15,14,20,18,40,36,21) D) (15,10,14,18,20,36,40,21) 10、下列四种排序方法中，不稳定的方法是( )。 A) 冒泡排序 B) 直接插入排序 C) 归并排序 D) 快速排序 三、填空题（每空2分，共20分） 1、一个算法中，基本操作的语句频度为(n3+n2log2n+14n)/n2，该算法的时间复杂度为 ( ) 2、 65个结点的完全二叉树，按层次，从左到右编号，则最后一个非叶子结点的编号为( )。 3、折半查找的两个前提条件分别是（ ）和（ ） 4、一个有序表为{ 4，8，12，16，20，24，28}，采用折半查找法查找值为24时需要比较（ ）次。 5、有向图的邻接表表示法中，第i条链上边表结点的个数为该顶点的（ ）。 6、已知一个带头结点的链栈，其头指针为top；指针s指向一个新结点，要将结点s进栈，则进栈的语句应为：（ ）和（ ）。 7、有一种排序算法，其时间复杂度为O（n2），关键字比较次数与待排序记录的初始排列顺序无关且排序不稳定，则该排序算法是（ ） 8、对二叉排序树进行中序遍历，会得到一个（ ）第 第 页（共 页） 四、构造题（每题6分，共30分） 1、假定用于通信的某电文仅由8个字母构成，各字母在电文中出现的频率分别为（12，5，3，7，14，21，9，15）。请完成： 1）构造哈夫曼树；2）为这8个字母设计不等长的Huffman编码，并计算WPL。 2、已知一个图的顶点为A、B、C、D，其邻接矩阵的下三角元素全为0（包括主对角线元素），其他元素均为1。请画出该图，并给出其邻接表。 3、用普利姆算法从顶点A出发，构造图1所示连通网的最小生成树（写出过程）。 图1 4、一个线性序列{38，25，74，63，5