《耿国华数据结构附录A样卷习题答案及B卷习题答案》由会员分享，可在线阅读，更多相关《耿国华数据结构附录A样卷习题答案及B卷习题答案（8页珍藏版）》请在金锄头文库上搜索。
1、- 数据构造 附录A 样卷一一、判断题：10 分正确在括号内打，错误打( ) 1.在单链表中，头结点是必不可少的。 2如果一个二叉树中没有度为1的结点，则必为满二叉树。( ) 3. 循环链表的结点构造与单链表的结点构造完全一样，只是结点间的连接方式不同。( ) 4. 顺序存储构造只能用来存放线性构造；链式存储构造只能用来存放非线性构造。( ) 5. 在一个大根堆中，最小元素不一定在最后。( ) 6. 在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和。 7. 在采用线性探测法处理冲突的散列表中，所有同义词在表中相邻。 8. 内部排序是指排序过程在内存中进展的排序。 9. 拓扑排序是指结点
2、的值是有序排列。( )10. AOE网所表示的工程至少所需的时间等于从源点到汇点的最长路径的长度。二、选择题(30分, 每题1.5分)1有一个含头结点的单链表，头指针为head, 则判断其是否为空的条件为：_A head=NILB. head.ne*t=NIL C. head.ne*t=head D. headNIL或 A head=NULL B. Head-ne*t=NULL C. head-ne*t=head D. Head!=NULL2非空的循环单链表head的尾指针p满足_。 A. p.ne*t=NIL B. p=NIL C. p.ne*t=head D. p=head或 A. p-n
3、e*t=NULLB. p=NULLC. P-ne*t=head D. p=head3链表不具有的特点是。 A、可随机访问任一个元素 B、插入删除不需要移动元素 C、不必事先估计存储空间 D、所需空间与线性表的长度成正比4假设*链表中最常用的操作是在最后一个结点之后插入一个结点和删除最后一个结点，则采用存储方式最节省运算时间。 A、单链表 B、双链表 C、单循环链表 D、带头结点的双循环链表5假设线性表最常用的操作是存取第i个元素及其前驱的值，则采用存储方式节省时间。 A、单链表 B、双链表 C、单循环链表 D、顺序表6设一个栈的输入序列为A，B，C，D，则借助一个栈所得到的输出序列不可能的是。
4、 A、 A，B，C，D B、D，C，B，AC、 A，C，D，B D、D，A，B，C7一个队列的入队序列是1，2，3，4，则队列的输出序列是。 A、4，3，2，1 B、1，2，3，4 C、1，4，3，2 D、3，2，4，18设循环队列中数组的下标范围是1n，其头尾指针分别为f，r，假设队列中元素个数为。 A、r-f B 、r-f+1 C、r-f+1mod n D、r-f+nmod n9串是。 A、不少于一个字母的序列 B、任意个字母的序列 C、不少于一个字符的序列 D、有限个字符的序列10数组A1.5,1.6的每个元素占5个单元，将其按行优先次序存储在起始地址为1000的连续内存单元中，则A5，
5、5的地址是。 A、1140 B、1145 C、1120 D、112511将一棵有100个结点的完全二叉树从根这一层开场，每一层从左到右依次对结点进展编号，根结点编号为1，则编号为49的结点的左孩子的编号为。 A、98 B、99 C、50 D、4812对二叉树从1开场编号，要求每个结点的编号大于其左右孩子的编号，同一个结点的左右孩子中，其左孩子的编号小于其右孩子的编号， 则可采用实现编号。 A、先序遍历 B、中序遍历 C、后序遍历 D、从根开场进展层次遍历13*二叉树的先序序列和后序序列正好相反，则该二叉树一定是的二叉树。 A、空或只有一个结点 B、高度等于其结点数 C、任一结点无左孩子 D、任
6、一结点无右孩子14在有n个叶子结点的哈夫曼树中，其结点总数为。 A、不确定 B、2n C、2n+1 D、2n-115一个有n个顶点的无向图最多有条边。 A、n B、nn-1 C、nn-1/2 D、2n16任何一个无向连通图的最小生成树。 A、只有一棵 B、有一棵或多棵 C、一定有多棵 D、可能不存在17一组记录的关键字为46，79，56，38，40，84，利用快速排序的方法，以第一个记录为基准得到的一次划分结果为。 A、38，40，46，56，79，84 B、40，38，46，79，56，84 C、40，38，46，56，79，84 D、40，38，46，84，56，7918数据表A中每个元素
7、距其最终位置不远，则采用排序算法最节省时间。 A、堆排序 B、插入排序 C、快速排序 D、直接选择排序19以下排序算法中，算法可能会出现下面情况：初始数据有序时，花费时间反而最多。 A、堆排序 B、冒泡排序 C、快速排序 D、SHELL 排序20对于键值序列12，13，11，18，60，15，7，18，25，100，用筛选法建堆，必须从键值为的结点开场。 A、100 B、60 C、12 D、15三、填空题40分1在顺序表即顺序存储构造的线性表中插入一个元素，需要平均动个元素.2. 快速排序的最坏情况，其待排序的初始排列是 .3. 为防止在图中走回，应设立 .4. 一个栈的输入序列为123，写出
8、不可能是栈的输出序列。5. N个结点的二叉树,采用二叉链表存放,空链域的个数为.6. 要在一个单链表中p所指结点之后插入s所指结点时, 应执行和 的操作.7.Dijkstra算法是按的次序产生一点到其余各顶点最短路径的算法.8.在N个结点完全二叉树中，其深度是 .9.对二叉排序树进展遍历, 可得到结点的有序排列.10设一哈希表表长M为100 ，用除留余数法构造哈希函数，即HK=K MOD PP=M, 为使函数具有较好性能，P应选11单链表与多重链表的区别是12深度为6根层次为1的二叉树至多有个结点。13二维数组A0.200.10采用行序为主方式存储，每个元素占4个存储单元,并且A00的存储地址
9、是1016, 则A105的存储地址是14循环单链表La中，指针P所指结点为表尾结点的条件是15在查找方法中，平均查找长度与结点个数无关的查找方法是。16队列的特性是17具有3个结点的二叉树有种18一棵二叉树的前序序列为ABDFCE，中序序列为DFBACE，后序序列为19一个图的邻接矩阵表示，要删除所有从第i个结点出发的边，在邻接矩阵运算是四、构造题：30 分1关键字序列为：75, 33, 52, 41, 12, 88, 66, 27哈希表长为10，哈希函数为：H(k)=K MOD 7, 解决冲突用线性探测再散列法，构造哈希表，求等概率下查找成功的平均查找长度。2无向图如图1所示， 1给出图的邻
10、接表。 2从A开场，给出一棵广度优先生成树。3给定叶结点权值：1，3，5，6，7，8，构造哈夫曼树，并计算其带权路径长度。4从空树开场，逐个读入并插入以下关键字，构造一棵二叉排序树： 24，88，42，97，22，15，7，13。5对长度为8的有序表，给出折半查找的判定树，给出等概率情况下的平均查找长度。6一棵树如图2所示，要求将该树转化为二叉树。五、算法设计题(40分)算法题可用类PASCAL或类C语言,每题20分1 一棵二叉树采用二叉链表存放，写一算法，要求统计出二叉树中叶子结点个数并输出二叉树中非终端结点输出无顺序要求。2编写算法，判断带头结点的双循环链表L是否对称。对称是指：设各元素值
11、a1,a2,.,an, 则有ai=an-i+1即指：a1= an，a2= an-1 。结点构造为 priordatane*t数据构造 附录B 样卷二一、简答题15分，每题3分1. 简要说明算法与程序的区别。2. 在哈希表中，发生冲突的可能性与哪些因素有关.为什么.3. 说明在图的遍历中，设置访问标志数组的作用。4. 说明以下三个概念的关系：头指针，头结点，首元素结点。5. 在一般的顺序队列中，什么是假溢出.怎样解决假溢出问题.二、判断题10分，每题1分正确在括号内打，错误打( )1广义表( a ), b), c ) 的表头是( a ), b)，表尾是( c )。( )2在哈夫曼树中，权值最小的
12、结点离根结点最近。( )3基数排序是高位优先排序法。( )4在平衡二叉树中，任意结点左右子树的高度差绝对值不超过1。( )5在单链表中，给定任一结点的地址p，则可用下述语句将新结点s插入结点p的后面：p-ne*t = s; s-ne*t = p-ne*t;( )6抽象数据类型ADT包括定义和实现两方面，其中定义是独立于实现的，定义仅给出一个ADT的逻辑特性，不必考虑如何在计算机中实现。( )7数组元素的下标值越大，存取时间越长。( )8用邻接矩阵法存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中结点个数有关，而与图的边数无关。( )9拓扑排序是按AOE网中每个结点事件的最早
13、发生时间对结点进展排序。( )10长度为1的串等价于一个字符型常量。三、单项选择题10分, 每题1分1排序时扫描待排序记录序列，顺次比较相邻的两个元素的大小，逆序时就交换位置。这是哪种排序方法的根本思想. A、堆排序B、直接插入排序C、快速排序D、冒泡排序2一个有向图的邻接矩阵表示，要删除所有从第i个结点发出的边，应该：A将邻接矩阵的第i行删除 B将邻接矩阵的第i行元素全部置为0C将邻接矩阵的第i列删除 D将邻接矩阵的第i列元素全部置为03有一个含头结点的双向循环链表，头指针为head, 则其为空的条件是：A. head-priro=NULL B. head-ne*t=NULL C. head
14、-ne*t=head D. head-ne*t- priro=NULL4. 在顺序表 ( 3, 6, 8, 10, 12, 15, 16, 18, 21, 25, 30 ) 中，用折半法查找关键码值11，所需的关键码比较次数为： A) 2 B) 3 C) 4 D) 55. 以下哪一个不是队列的根本运算.A从队尾插入一个新元素 B从队列中删除第i个元素 C判断一个队列是否为空 D读取队头元素的值6. 在长度为n的顺序表的第i个位置上插入一个元素1 i n+1，元素的移动次数为：A) n i + 1 B) n i C) i D) i 1 7对于只在表的首、尾两端进展插入操作的线性表，宜采用的存储构造为:A) 顺序表 B) 用头指针表示的循环单链表C) 用尾指针表示的循环单链表 D) 单链表8对包含n个元素的哈希表进展查找，平均查找长度为：A) O(lo
