耿国华数据结构附录A样卷习题答案及B卷习题答案

1数据结构附录A样卷一一、判断题：（10分）正确在括号内打√，错误打×(×)1.在单链表中，头结点是必不可少的。（×）2．如果一个二叉树中没有度为1的结点，则必为满二叉树。(√)3.循环链表的结点结构与单链表的结点结构完全相同，只是结点间的连接方式不同。(×)4.顺序存储结构只能用来存放线性结构；链式存储结构只能用来存放非线性结构。(√)5.在一个大根堆中，最小元素不一定在最后。(√)6.在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和。（√）7.在采用线性探测法处理冲突的散列表中，所有同义词在表中相邻。（√）8.内部排序是指排序过程在内存中进行的排序。（×）9.拓扑排序是指结点的值是有序排列。(×)10.AOE网所表示的工程至少所需的时间等于从源点到汇点的最长路径的长度。二、选择题(30分,每题1.5分)1．有一个含头结点的单链表，头指针为head,则判断其是否为空的条件为：___B___A．head==NULLB.Head-next==NULLC.head-next==headD.Head!=NULL2．非空的循环单链表head的尾指针p满足___C____。A.p-next=NULLB.p==NULLC.P-next==headD.p==head3．链表不具有的特点是A。A、可随机访问任一个元素B、插入删除不需要移动元素C、不必事先估计存储空间D、所需空间与线性表的长度成正比4．若某链表中最常用的操作是在最后一个结点之后插入一个结点和删除最后一个结点，则采用D存储方式最节省运算时间。A、单链表B、双链表C、单循环链表D、带头结点的双循环链表5．若线性表最常用的操作是存取第i个元素及其前驱的值，则采用D存储方式节省时间。A、单链表B、双链表C、单循环链表D、顺序表6．设一个栈的输入序列为A，B，C，D，则借助一个栈所得到的输出序列不可能的是D。A、A，B，C，DB、D，C，B，AC、A，C，D，BD、D，A，B，C7．一个队列的入队序列是1，2，3，4，则队列的输出序列是B。A、4，3，2，1B、1，2，3，4C、1，4，3，2D、3，2，4，18．设循环队列中数组的下标范围是1~n，其头尾指针分别为f，r，若队列中元素个数为D。A、r-fB、r-f+1C、（r-f+1）modnD、（r-f+n）modn9．串是D。A、不少于一个字母的序列B、任意个字母的序列C、不少于一个字符的序列D、有限个字符的序列10．数组A[1..5,1..6]的每个元素占5个单元，将其按行优先次序存储在起始地址为1000的连续内存单元中，则A[5，5]的地址是A。A、1140B、1145C、1120D、112511．将一棵有100个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，根结点编号为1，则编号为49的结点的左孩子的编号为A。A、98B、99C、50D、4812．对二叉树从1开始编号，要求每个结点的编号大于其左右孩子的编号，同一个结点的左右孩子中，其左孩子的编号小于其右孩子的编号，则可采用C实现编号。A、先序遍历B、中序遍历C、后序遍历D、从根开始进行层次遍历13．某二叉树的先序序列和后序序列正好相反，则该二叉树一定是B的二叉树。A、空或只有一个结点B、高度等于其结点数C、任一结点无左孩子D、任一结点无右孩子14．在有n个叶子结点的哈夫曼树中，其结点总数为C。A、不确定B、2nC、2n+1D、2n-1215．一个有n个顶点的无向图最多有C条边。A、nB、n（n-1）C、n（n-1）/2D、2n16．任何一个无向连通图的最小生成树B。A、只有一棵B、有一棵或多棵C、一定有多棵D、可能不存在17．一组记录的关键字为（46，79，56，38，40，84），利用快速排序的方法，以第一个记录为基准得到的一次划分结果为C。A、38，40，46，56，79，84B、40，38，46，79，56，84C、40，38，46，56，79，84D、40，38，46，84，56，7918．已知数据表A中每个元素距其最终位置不远，则采用B排序算法最节省时间。A、堆排序B、插入排序C、快速排序D、直接选择排序19．下列排序算法中，C算法可能会出现下面情况：初始数据有序时，花费时间反而最多。A、堆排序B、冒泡排序C、快速排序D、SHELL排序20．对于键值序列（12，13，11，18，60，15，7，18，25，100），用筛选法建堆，必须从键值为B的结点开始。A、100B、60C、12D、15三、填空题（40分）1在顺序表（即顺序存储结构的线性表）中插入一个元素，需要平均动表长的一半个元素.2.快速排序的最坏情况，其待排序的初始排列是排好序列.4.一个栈的输入序列为123，写出不可能是栈的输出序列312。5.N个结点的二叉树,采用二叉链表存放,空链域的个数为N+1.6.要在一个单链表中p所指结点之后插入s所指结点时,应执行S-next=P-next和P-next=S的操作.7.Dijkstra算法是按路径递增的次序产生一点到其余各顶点最短路径的算法.8.在N个结点完全二叉树中，其深度是Log(2)(N).9.对二叉排序树进行中序遍历,可得到结点的有序排列.10．设一哈希表表长M为100，用除留余数法构造哈希函数，即H（K）=KMODP（P〈=M〉,为使函数具有较好性能，P应选9711．单链表与多重链表的区别是链域个数不同12．深度为6（根层次为1）的二叉树至多有63个结点。13．已知二维数组A[0..20][0..10]采用行序为主方式存储，每个元素占4个存储单元,并且A[0][0]的存储地址是1016,则A[10][5]的存储地址是147614．循环单链表La中，指针P所指结点为表尾结点的条件是P-next=head15．在查找方法中，平均查找长度与结点个数无关的查找方法是散列查找。16．队列的特性是先进先出317．具有3个结点的二叉树有5种18．已知一棵二叉树的前序序列为ABDFCE，中序序列为DFBACE，后序序列为FDBECA19．已知一个图的邻接矩阵表示，要删除所有从第i个结点出发的边，在邻接矩阵运算是将矩阵第i行全部置0四、构造题：（30分）1．已知关键字序列为：（75,33,52,41,12,88,66,27）哈希表长为10，哈希函数为：H(k)=KMOD7,解决冲突用线性探测再散列法，构造哈希表，求等概率下查找成功的平均查找长度。答：计算函数值(1)哈希表（4分，每对1个0.5分）index0123456789key2752887533411266ASL=(1+2+1+2+4+1+7+5)/8=23/82．已知无向图如图1所示，（1）给出图的邻接表。（2）从A开始，给出一棵广度优先生成树。key7533524112886627计算函数值Key%755365436比较次数Cmp1212417543．给定叶结点权值：（1，3，5，6，7，8），构造哈夫曼树，并计算其带权路径长度30171398674513WPL=1*4+3*4+5*3+6*2+7*2+8*2=734．从空树开始，逐个读入并插入下列关键字，构造一棵二叉排序树：（24，88，42，97，22，15，7，13）。2422881542977135．对长度为8的有序表，给出折半查找的判定树，给出等概率情况下的平均查找长度。ASL=(1+2*2+4*3+1*4)/8=21/8=2.626．已知一棵树如图2所示，要求将该树转化为二叉树。1ABCD2BACF3CABDEF4DACF5EBCF6FDCE310756245ABCEDFIGJHK五、算法设计题(40分)[算法题可用类PASCAL或类C语言,每题20分]1．已知一棵二叉树采用二叉链表存放，写一算法，要求统计出二叉树中叶子结点个数并输出二叉树中非终端结点（输出无顺序要求）。structBtree{intdata;structBtree*left;structBtree*right;};intcount(Btree*T){Btree*st[50];inttop=-1;Btree*p;intsum=0;if(T!=NULL){top++;st[top]=T;while(top-1){p=st[top];top--;if(p-right!=NULL){top++;st[top]=p-right;}if(p-left!=NULL){top++;st[top]=p-left;}if(p-left==NULL&&p-right==NULL){sum++;}}returnsum;}}2．编写算法，判断带头结点的双循环链表L是否对称。对称是指：设各元素值a1,a2,...,an,则有ai=an-i+1即指：a1=an，a2=an-1。。。。。。结点结构为priordatanext数据结构附录B样卷二一、简答题（15分，每小题3分）1.简要说明算法与程序的区别。算法是解决特定问题的操作序列，可以用多种方式描述。程序是算法在计算机中的实现，与具体的计算机语言有关。2.在哈希表中，发生冲突的可能性与哪些因素有关？为什么？主要与哈希函数、装填因子α有关。如果用哈希函数计算的地址分布均匀，则冲突的可能性较小，如果装填因子α较小，则哈希表较稀疏，发生冲突的可能性较小。63.说明在图的遍历中，设置访问标志数组的作用。图中结点可能有多个前驱，设置访问标志数组主要是为了避免重复访问同一个结点。4.说明以下三个概念的关系：头指针，头结点，首元素结点。头指针指向头结点，头结点的后继域指向首元素结点。5.在一般的顺序队列中，什么是假溢出？怎样解决假溢出问题？当队尾到达数组最后一个单元时，就认为队满，但此时数组前面可能还有空单元，因此叫假溢出。解决的方法是采用循环队列，即令最后一个单元的后继是第一个单元。二、判断题（10分，每小题1分）正确在括号内打√，错误打×(√)（1）广义表(((a),b),c)的表头是((a),b)，表尾是(c)。(×)（2）在哈夫曼树中，权值最小的结点离根结点最近。(×)（3）基数排序是高位优先排序法。(√)（4）在平衡二叉树中，任意结点左右子树的高度差（绝对值）不超过1。(×)（5）在单链表中，给定任一结点的地址p，则可用下述语句将新结点s插入结点p的后面：p-next=s;s-next=p-next;(√)（6）抽象数据类型（ADT）包括定义和实现两方面，其中定义是独立于实现的，定义仅给出一个ADT的逻辑特性，不必考虑如何在计算机中实现。(×)（7）数组元素的下标值越大，存取时间越长。(√)（8）用邻接矩阵法存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中结点个数有关，而与图的边数无关。(×)（9）拓扑排序是按AOE网中每个结点事件的最早发生时间对结点进行排序。(×)（10）长度为1的串等价于一个字符型常量。三、单项选择题（10分,每小题1分）1．排序时扫描待排序记录序列，顺次比较相邻的两个元素的大小，逆序时就交换位置。这是哪种排序方法的基本思想？DA、堆排序B、直接插入排序C、快速排序D、冒泡排序2．已知一个有向图的邻接矩阵表示，要删除所有从第i个结点发出的边，应该：BA）将邻接矩阵的第i行删除B）将邻接矩阵的第i行元素全部置为0C）将邻接矩阵的第i列删除D）将邻接矩阵的第i列元素全部置为03．有一个含头结点的双向循环链表，头指针为head,则其为空的条件是：CA.head-priro==NULLB.head-next==NULLC.head-next==headD.head-next-priro==NULL4.在顺序表(3,6,8,10,12,15,16,18,21,25,30)中，用折半法查找关键码值11，所需的关键码比较次数为：CA)2B)3C)4D)55.以下哪一个不是队列的基本运算？BA）从队尾插入一个新元素B）从队列中删除第i个元素C）判断一个队列是否为空D）读取队头元素的值6.在长度为n的顺序表的第i个位置上插入一个元素（1≤i≤n+1