耿国华数据结构附录A样卷习题B卷习题.docx

1、耿国华数据结构附录A样卷习题B卷习题数据结构 附录A 样卷一、判断题：(10分)正确在括号内打，错误打X()1.在单链表中，头结点是必不可少的。)2.如果一个二叉树中没有度为 1的结点，则必为满二叉树。()3. 循环链表的结点结构与单链表的结点结构完全相同，只是结点间的连接方式不 同。()4顺序存储结构只能用来存放线性结构； 链式存储结构只能用来存放非线性结构。()5.在一个大根堆中，最小元素不一定在最后。()6.在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和。()7.在采用线性探测法处理冲突的散列表中，所有同义词在表中相邻。)8.内部排序是指排序过程在内存中进行的排序。)9.拓扑排

2、序是指结点的值是有序排列。()10. AOE网所表示的工程至少所需的时间等于从源点到汇点的最长路径的长度。二、选择题(30分，每题1.5分)1.有一个含头结点的单链表，头指针为 head, 则判断其是否为空的条件为:A. head=NIL B.C、不必事先估计存储空间 D、所需空间与线性表的长度成正比4.若某链表中最常用的操作是在最后一个结点之后插入一个结点和删除最后一个结点，则 采用 存储方式最节省运算时间。A、单链表 B、双链表 C、单循环链表 D、带头结点的双循环链表5若线性表最常用的操作是存取第 i个元素及其前驱的值，则采用 存储方式节省时间。A、单链表B、双链表C、单循环链表D、顺序

3、表6.设一个栈的输入序列为AB,c,D,则借助一个栈所得到的输出序列不i可能的是。A、A , B, C,DB、D, CB,AC A, C, D,BD、D, A,B,C7.一个队列的入队序列是1,2,3,4，则队列的输出序列是。A、4, 3, 2, 1B、1 , 2, 3, 4C、1, 4, 3,2D、 3, 2, 4,1&设循环队列中数组的下标范围是 1n，其头尾指针分别为 f, r，若队列中元素个数为 。A、r-f B、r-f+1 C、( r-f+1 ) mod n D、( r-f+n ) mod n9. 串是 。A、不少于一个字母的序列 B、任意个字母的序列C、不少于一个字符的序列 D、有

4、限个字符的序列10. 数组A1.5,1.6 的每个元素占5个单元，将其按行优先次序存储在起始地址为 1000的连续内存单元中，则 A5 , 5的地址是 。A 1140 B、114 C 1120 D、112511.将一棵有100个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，根结点编号为 1，则编号为49的结点的左孩子的编号为 。A、 98 B、 99 C、50 D、 4812对二叉树从1开始编号，要求每个结点的编号大于其左右孩子的编号，同一个结点的 左右孩子中，其左孩子的编号小于其右孩子的编号， 则可采用 实现编号。A、先序遍历 B、中序遍历 C、后序遍历 D、从根开始进行

5、层次遍历13某二叉树的先序序列和后序序列正好相反，则该二叉树一定是 的二叉树。A、空或只有一个结点 B、高度等于其结点数C、任一结点无左孩子 D、任一结点无右孩子14.在有n个叶子结点的哈夫曼树中，其结点总数为 。A、不确定 B、2n C、2n+1 D、2n-115. 一个有n个顶点的无向图最多有 条边。A、n B、n (n-1 ) C、n (n-1 )/2 D、2n16 .任何一个无向连通图的最小生成树 。A、只有一棵 B、有一棵或多棵 C、一定有多棵 D、可能不存在17. 一组记录的关键字为(46, 79 , 56, 38, 40, 84),利用快速排序的方法，以第一个 记录为基准得到的一

6、次划分结果为 。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中每个元素距其最终位置不远，则采用 排序算法最节省时间。A、堆排序 B、插入排序 C、快速排序 D、直接选择排序19. 下列排序算法中， 算法可能会出现下面情况：初始数据有序时，花费 时间反而最多。A、堆排序 B、冒泡排序 C、快速排序 D、SHELL排序20.对于键值序列(12, 13, 11, 18, 60, 15, 7, 18, 25, 100)，用筛选法建堆，必须从键值为 的结点开始。B、60A、100

7、12 D、 15三、填空题（40分）1在顺序表（即顺序存储结构的线性表）中插入一个元素，需要平均动 个元素2.3.立快速排序的最坏情况，其待排序的初始排列是 _为防止在图中走回，应设4.一个栈的输入序列为 123,写出不可能是栈的输出序列 。5.N个结点的二叉树，采用二叉链表存放，空链域的个数为 .6.要在一个单链表中 p所指结点之后插入 s所指结点时，应执行 和 的操作.7.Dijkstra 算法是按 的次序产生一点到其余各顶点最短路径的算法.8.在N个结点完全二叉树中， 其深度是 9.对二叉排序树进行 遍历，可得到结点的有序排列.10. 设一哈希表表长 M为100，用除留余数法构造哈希函数

8、，即 H（ K） =K MOD3 （ P=M ,为使函数具有较好性能， P应选 11.单链表与多重链表的区别是 12. 深度为 6 （根层次为 1 ）的二叉树至多有 个结点。13已知二维数组 A0.200.10 采用行序为主方式存储，每个元素占 4个存储单元，并且A00的存储地址是 1016，则A105 的存储地址是 14.循环单链表 La中，指针P所指结点为表尾结点的条件是 15.在查找方法中，平均查找长度与结点个数无关的查找方法16.队列的特性是 17. 具有3个结点的二叉树有 种18. 已知一棵二叉树的前序序列为 ABDFCE中序序列为 DFBACE后序序列为 19已知一个图的邻接矩阵表

9、示，要删除所有从第 i个结点出发的边，在邻接矩阵运算是四、构造题：(30分)1.已知关键字序列为：(75, 33, 52, 41, 12, 88, 66, 27 )哈希表长为10,哈希函数为：H(k)=K MOD 7,解决冲突用线性探测再散列法，构造哈希表，求等概率下查找成功的平均 查找长度。2.已知无向图如图1所示，(1)给出图的邻接表。(2)从A开始，给出一棵广度优先生成树。3.给定叶结点权值：(1 , 3, 5, 6, 7, 8),构造哈夫曼树，并计算其带权路径长度。4从空树开始，逐个读入并插入下列关键字，构造一棵二叉排序树:(24, 88, 42, 97, 22, 15, 7, 13)

10、。5对长度为8的有序表，给出折半查找的判定树，给出等概率情况下的平均查找长度。6.已知一棵树如图 2所示，要求将该树转化为二叉树。五、算法设计题（40分）算法题可用类 PASCAL或类C语言,每题20分1. 已知一棵二叉树采用二叉链表存放，写一算法，要求统计出并输出二叉树中非终端结点（输出无顺序要求）。叉树中叶子结点个数2.编写算法，判断带头结点的双循环链表 L是否对称。对称是指：设各元素值 ai,a2,.,a n,则有ai=an+i即指： ai = a n, a2= a n-i 。结点结构为 priordatan ext数据结构 附录 B 样卷二 一、简答题( 15分，每小题 3 分)1.简

11、要说明算法与程序的区别。2.在哈希表中，发生冲突的可能性与哪些因素有关？为什么？3.说明在图的遍历中，设置访问标志数组的作用。4.说明以下三个概念的关系：头指针，头结点，首元素结点。5.在一般的顺序队列中，什么是假溢出？怎样解决假溢出问题？、判断题( 10分，每小题 1 分)正确在括号内打，错误打X( ) (1)广义表 ( a ), b), c ) 的 表头是 ( a ), b) ，表尾是 ( c ) 。( ) ( 2)在哈夫曼树中，权值最小的结点离根结点最近。( ) ( 3)基数排序是高位优先排序法。( ) ( 4)在平衡二叉树中，任意结点左右子树的高度差(绝对值)不超过 1。()(5)在单

12、链表中，给定任一结点的地址 P,则可用下述语句将新结点 s插入结点p的后面 ： p-next = s; s-next = p-next;()(6)抽象数据类型(ADT包括定义和实现两方面，其中定义是独立于实现的，定 义仅给出一个ADT的逻辑特性，不必考虑如何在计算机中实现。( ) ( 7)数组元素的下标值越大，存取时间越长。( ) (8)用邻接矩阵法存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中结点个数有关，而与图的边数无关。()(9)拓扑排序是按 AOE网中每个结点事件的最早发生时间对结点进行排序。( ) ( 10)长度为 1 的串等价于一个字符型常量。三、单项选择题(

13、 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-next=NULLC. head-next=head D. head-ne

14、xt- Priro=NULL4.在顺序表 ( 3, 6, 8, 10, 12, 15, 16, 18, 21, 25, 30 ) 中，用折半法查找关键码值 11，所需的关键码比较次数为：A) 2 B) 3 C) 4 D) 55.以下哪一个不是队列的基本运算?A)从队尾插入一个新元素C )判断一个队列是否为空 在长度为n的顺序表的第n - i + 1 B) n6.A)7.A) C) &B )从队列中删除第i个元素D )读取队头元素的值个位置上插入一个元素(K i n+1)，元素的移动次数为: -i C) i D) i - 1对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构为 ：顺序表

15、 B)用尾指针表示的循环单链表 D)对包含n个元素的哈希表进行查找，用头指针表示的循环单链表 单链表平均查找长度为：2n) D)不直接依赖于nA) O(log 2n) B) 0(n) C) 0(nlog9.将一棵有100个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，根结点编号为A 、 48 B 4910.某二叉树结点的中序序列为 则其左子树中结点数目为：A) 3 B ) 2四、填空题(10分，每空1分)1.填空完成下面一趟快速排序算法：1,则编号最大的非叶结点的编号为:DE、C、50A、B、C、51F、G 后序序列为 B、D C A、F、G E,int QKPass (

16、RecordType r , i nt low x = r low ;while ( low high )inthigh)while ( low high & r high -;if ( low = x.key )=r high Iow+; while ( low high & r .key x. key)low+; if ( low high ) r =r low ；high-; r low = x ; return low ;2.假设用循环单链表实现队列， 若队列非空，且队尾指针为 R,则将新结点S加入队列时,需执行下面语句:;R=S3 通常是以算法执行所耗费的和所占用的来判断一个算法的优

17、劣。4.已知一个3行、4列的二维数组 A (各维下标均从1开始)，如果按“以列为主”的顺序存储，则排在第8个位置的元素是:5.高度为h的完全二叉树最少有个结点。五、构造题(20分)1. ( 4分)已知数据结构 DS的定义如下，请给出其逻辑结构图示。DS = (D, R)D = a, b, c, d, e, f, g R = T T = , , , , , ., , , , , 2（ 6分）对以下关键字序列建立哈希表： （SUN, MON, TUE, WED, THU, FRI, SAT ）,哈希函数为H（K） = （K中最后一个字母在字母表中的序号） M0D7。用线性探测法处理冲突，要求构造一

18、个装填因子为 0.7 的哈希表， 并计算出在等概率情况下查找成功的平均查找长度。3.（ 6 分）将关键字序列（ 3， 26， 12， 61， 38， 40， 97， 75， 53， 87 ）调整为大根堆。4（4分）已知权值集合为： 5， 7， 2， 3， 6， 9 ，要求给出哈夫曼树，并计算其带权路 径长度 WPL。六、算法分析题( 10 分) 阅读下面程序，并回答有关问题。其中 BSTree 为用二叉链表表示的二叉排序树类型。(1)简要说明程序功能。 (5 分)(2)n 个结点的满二叉树的深度 h 是多少？( 3分)(3)假设二叉排序树 *bst 是有 n 个结点的满二叉树 , 给出算法的时

19、间复杂度。 (2分)int Proc (BSTree *bst, KeyType K) BSTree f, q, s; s=(BSTree)malloc(sizeof(BSTNode);s- key = K; s- lchild = NULL; s- rchild = NULL; if ( *bst = NULL ) *bst = s; return 1; f = NULL; q = *bst;while( q != NULL ) if ( K key ) f = q; q = q - lchild; else f = q; q = q - rchild; if （ K key ） f - I

20、child = s;else f - rchild = s;return 1;七、算法设计题（25分）1.已知一个带头结点的整数单链表 L,要求将其拆分为一个正整数单链表 L1和一个负整数单链表L2。（ 9分）2.无向图采用邻接表存储结构，编写算法输出图中各连通分量的结点序列。 （8分）3.编写一个建立二叉树的算法，要求采用二叉链表存储结构。 （8分）数据结构附录A样卷一参考答案:判断题题号12345678910答案XXVXVVVVXX:选择题题1234567891011121314151617181920答BCADDDBDDAACBCCBCBCB三：填空1 表长的一半 2 排好序列 3, 4

21、 312 5 N+1 6 S-next=P-next P-next=S 7 路径递增8 Log(2)(N) 9 中序 10 97 11 链域个数不同 12 63 13 1476 14 P-next=head 15 散列查找 16 先进先出 17 5 18 FDBECA 19将矩阵第i行全部置 0四，构造题1，计算函数值key7533524112886627Key%755365436（1）哈希表（4分，每对1个0.5分）index0123456789key2752887533411266比较次数（3分）key7533524112886627Cmp12124175ASL=(1+2+1+2+4+1+

22、7+5)/8=23/85， (1)(2) ASL=(1+2*2+4*3+1*4)/8=21/8=2.62数据结构附录B样卷二参考答案一、简答题（15分，每小题3分）6.算法是解决特定问题的操作序列，可以用多种方式描述。程序是算法在计算机中的实现，与具体 的计算机语言有关。7.主要与哈希函数、装填因子a有关。如果用哈希函数计算的地址分布均匀， 则冲突的可能性较小，如果装填因子a较小，则哈希表较稀疏，发生冲突的可能性较小。8.图中结点可能有多个前驱，设置访问标志数组主要是为了避免重复访问同一个结点。9.头指针指向头结点，头结点的后继域指向首元素结点。10.当队尾到达数组最后一个单元时， 就认为队满

23、，但此时数组前面可能还有空单元， 因此叫假溢出解决的方法是采用循环队列，即令最后一个单元的后继是第一个单元。二、 判断题(10分，每小题1分)(1) (V) ( 2) ( X ) (3) ( X ) (4) (V) ( 5) ( X )(6) (V) ( 7) ( X ) (8) (V) (9) ( X ) ( 10) ( X )三、 单项选择题(10分，每小题1分)1. D) 2.B)3 .C) 4. C ) 5. B)6. A) 7.C)8.D) 9 . C ) 10 . C四、填空题(10 分,每空1分)1. highlowlowhigh2.S-next=R-next ; R-next=S ;3.时间 空间 4 . A2, 3 5 . 2 h-1五、构造题(20分)1. ( 4 分)2. (6 分)012-34 56789SUNMONTHUFRIWED TUESATASLsucc = ( 1X4 + 2X2 + 3)/7 =11 / 73. (6 分)六、算法分析题(10分)解：(1)在二叉排序树中插入关键字为 K的结点(2)h = log 2 ( n+1 ) 或h = log 2 n + 1 (方括号表示向下取整)(3)O ( log 2 ( n+1 ) 或 0 ( log 2 n )