耿国华数据结构附录样卷答案

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

2、E网所表示的工程至少所需的时间等于从源点到汇点的最长路径的长度。一、选择题(30分，每题15分)1. 有一个含头结点的单链表，头指针为head,则判断其是否为空的条件为:A.head=NILB. head*. next=NILC. head*. next=headD. headONIL或A.headNULL B. Head->nextNULLC. head->nex t=head D.Head!=NULL2.非空的循环单链表head的尾指针p满足一0A.p) next二NILB. p=NILC. p next=headD p=head或A.p->next=NULLB. p=N

3、ULLC. P->next=headD.p=head3.链表不具有的特点是oA.可随机访问任一个元素B、插入删除不需要移动元素C.不必事先估计存储空间D.所需空间与线性表的长度成正比4. 若某链表中最常用的操作是在最后一个结点之后插入一个结点和删除最后一个结点，则釆用存储方式最节省运算时间。A、单链表B、双链表C、单循环链表 D.带头结点的双循环链表5. 若线性表最帘用的操作是存取第i个元索及其前驱的值，则采用存储方式节省时间。A、单链表B、双链表C、单循环链表D、顺序表6. 设一个栈的输入序列为A, B, C, D,则借助一个栈所得到的输岀序列不可能的是oA、 A, B> C&g

4、t; DB、D,C,B,AC、A, C, D, BD、D,A,B,C7. 一个队列的入队序列是1, 2,3, 4,则队列的输出序列是OA. 4, 3, 2, 11, 2, 3, 4C、 1,4,3,2D、 3, 2, 4, 18.设循环队列中数组的下标范围是Pn,其头尾指针分别为f, r,若队列中元素个数 为OA. r-fB r-f+1C、(r-f+l)mod n D. (r-f+n)mod n9. 串是oA、不少于一个字母的序列B、任意个字母的序列C、不少于一个字符的序列D、有限个字符的序列10. 数组A1.5,1.6的每个元素占5个单元，将其按行优先次序存储在起始地址为1000的连续内存单

5、元中.则A5, 5的地址是。A. 1140B、 1145C、 1120D、 112511. 将一棵有100个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，根结点编号为1,则编号为49的结点的左孩了的编号为oA. 98B、99C、50D、4812. 朮二叉树从1开始编号，要求每个结点的编号人于其左右孩子的编号，同一个结点的左右孩子中，其左孩了的编号小于其右孩子的编号，则可采用实现编号。A、先序遍历B、中序遍历C、后序遍历D.从根开始进行层次遍历13. 某二叉树的先序序列和后序序列正好相反，则该二叉树一定是的二叉树。A.空或只有一个结点B.高度等于其结点数C>任一结点无左

6、孩子D.任一结点无右孩子14. 在有n个叶了结点的哈夫曼树中，其结点总数为oA.不确定 Bx 2n C. 2n+lD、2nT15. 一个有n个顶点的无向图最多有条边。A> nB> n (nT)C n (nT) /2D. 2n16. 任何一个无向连通图的最小生成树oA.只有一棵B、有一棵或多棵C、一定有多棵D、可能不存在17. 一组记录的关键字为(46, 79, 56, 38, 40, 84),利用快速排序的方法，以第一个记录为基准得到的一次划分结果为oA. 38,40,46,56,79, 84B、40,38,46,79,56, 84C> 40,38,46,56,79, 84D

7、、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),用筛选法建堆，必须从键值为的结点开始。A、 100B、 60C、 12D、 15三、填空题(40分)1在顺序表(即顺序存储结构的线性表)屮插入一个元索，需要平均动个元索.2. 快速排序的最坏悄

8、况，其待排序的初始排列是.3. 为防止在图中走回，应设立.4. 一个栈的输入序列为123,写出不可能是栈的输出序更。5. N个结点的二叉树，采用二叉链表存放，空链域的个数为6. 要在一个单链表中p所指结点之后插入s所指结点时，应执行 和 的操作.7. Dijkstra算法是按的次序产生一点到其余各顶点最短路径的算法.8. 在N个结点完全二叉树中，其深度是9. 对二叉排序树进行遍历，可得到结点的有序排列.10.设一哈希表表长M为100 ,用除留余数法构造哈希函数，即H (K)二KMODP (P <=M> ,为使函数具有较好性能，P应选11单链表与多重链表的区别是12. 深度为6 (根

9、层次为1)的二叉树至多有个结点。13. 已知-维数组A0. 20 0. 10采用行序为主方式存储，每个元素占4个存储单元,并且A0 0的存储地址是1016,则A10 5的存储地址是14. 循环单链表3中，指针P所指结点为表尾结点的条件是15. 在查找方法屮，平均查找长度与结点个数无关的查找方法是 o16. 队列的特性是17. 具有3个结点的二叉树有 种18. 已知一棵一.叉树的前序序列为ABDFCE,屮序序列为DFBACE,后序序列为19. 已知一个图的邻接矩阵表示，要删除所自从第i个结点出发的边，在邻接矩阵运算是四、构造题：(30分)1.已知关键字序列为：(75, 33, 52, 41, 1

10、2, 8& 66, 27)哈希表长为10,哈希函数 为：H(k)=K MOD 7,解决冲突用线性探测再散列法，构造哈希表，求等概率下竇找成功的平均 查找长度。E 12. 已知无向图如图1所示，(1) 给出图的邻接表。(2) 从A开始，给出一棵广度优先生成树。3.给定叶结点权值：(1, 3, 5, 6, 7, 8),构造哈夫曼树，并计算其带权路径长度。4.从空树开始，逐个读入并插入下列关键字，构造一棵二叉排序树:（24, 88, 42, 97, 22, 15, 7, 13） 5.对长度为8的有序表，给出折半賁找的判定树，给出等概率情况下的平均査找长度。6. 已知一棵树如图2所示，要求将该

11、树转化为二叉树。五. 算法设计题（40分）算法题可用类PASCAL或类C语言每题20分1. 已知一棵二叉树采用二叉链表存放，写一算法，要求统计出二叉树中叶子结点个数并 输出二叉树中非终端结点（输岀无顺序要求）。2. 编写算法.判断带头结点的双循环链表L是否对称。 对称是指：设各元索值ahan,则有ai=an-i*i即指：&!= 3n> fl2= fln-l结点结构为priordatanext数据结构附录B样卷二一.简答题（15分，每小题3分）1. 简要说明算法与程序的区别。2. 在哈希表中，发生冲突的可能性与哪些因素有关？为什么？3. 说明在图的遍历屮，设置访问标志数组的作用。4

12、. 说明以下三个概念的关系：头指针，头结点，首元素结点。5. 在一般的顺序队列中.什么是假溢出？怎样解决假溢出问题？二、判断题（10分，每小题1分）正确在括号内打错谋打X（）（1）广义表（a ）, b）, c ）的表头是（a ）, b）,表尾是（c ）o（）（2）在哈夫曼树屮，权值最小的结点离根结点最近。（）（3）基数排序是高位优先排序法。（）（4）在平衡二叉树屮，任意结点左右子树的高度建（绝对值）不超过1。（）（5）在单链表中，给定任一结点的地址p,则可用下述语句将新结点s插入结点p 的后面:p->next = s; s->next = p-next;（）（6）抽彖数据类型（AD

13、T）包括定义和实现两方面，其中定义是独立于实现的，定 义仅给出一个ADT的逻辑特性，不必考虑如何在计算机中实现。（）（7）数组元素的下标值越大，存取时间越长。（）（8）用邻接矩阵法存储一个图时，在不考虑压缩存储的情况下，所占用的存储空 间大小只与图中结点个数有关，而与图的边数无关。（）（9）拓扑排序是按A0E网中每个结点事件的最早发生时间对结点进行排序。（）（10）长度为1的串等价于一个字符型常杲。三、单项选择题（10分，每小题1分）1. 排序时扫描待排序记录序列，顺次比较相邻的两个元素的大小，逆序时就交换位置。这 是哪种排序方法的基木思想？A.堆排序 B.直接插入排序C.快速排序D.冒泡排序

14、2. 已知一个有向图的邻接矩阵表示，要删除所有从第i个结点发出的边，应该:A)将邻接矩阵的第i行删除 B)将邻接矩阵的第i行元索全部置为0O将邻接矩阵的第i列删除 D)将邻接矩阵的第i列元素全部腔为03. 有一个含头结点的双向循环链表，头指针为head,処其为空的条件是：A. head->pr i ro=NULLC head->next=head4在顺序表(3, 6, & 10, 12, 15, 值11,所需的关键码比较次数为：A) 2B) 3C) 4B. head->next=NULLD. head-next- priro=NULL16, 1& 21, 25

15、, 30 )中，用折半法杏找关键码D) 55. 以下哪一个不是队列的基木运算？A)从队尾插入一个新元素B)从队列中删除第i个元素C)判断一个队列是否为空D)读取队头元素的值6. 在长度为n的顺序表的第i个位置上插入一个元索(1W i Wn+1),元索的移动次数为:A) n i + 1B) n - iC) iD) i - 17. 对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构为：A)顺序表B)用头指针表示的循环单链表O用尾指针表示的循环单链表D)单链表8. 对包含n个元素的哈希表进行査找，平均查找长度为：A) 0(log2n) B) 0(n) C) O(nlogm) D)不直接依赖

16、于 n9. 将一棵有100个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，根结点编号为1,则编号最大的非叶结点的编号为：A、48B. 49 C、 5010.某二叉树结点的中序序列为A. B、C、D、E、F、G,后序序列为B. D、C. A. F、G. E, 则其左子树中结点数日为：A) 3B) 2C) 4D) 5四. 填空题(10分，每空1分)1. 填空完成下血一趙快速排序算法： int QKPass ( RecordType r , int low, int high) x = r T low 1：while ( low < high )while ( low &l

17、t; high && r . key >= x. key )high；if ( low < high ) r = r high ； low+; while ( low < high && r . key < x. key )low+;if ( low < high ) r = r low ； high; r low = x； return low ;2. 假没用循环单链表实现队列，若队列非空，且队尾指针为R,则将新结点S加入队列时,需执行下面语句： ； ； R=S；3. 通常是以算法执行所耗费的和所占用的来判断一个算法的优劣。4.

18、已知一个3行.4列的二维数组A (各维下标均从1开始)，如果按“以列为主”的顺序存储，则排在第8个位置的元素是：5. 高度为h的完全二叉树最少有 个结点。五. 构造题（20分）1. （4分）已知数据结构DS的定义如下，请给出其逻辑结构图示。DS = （D, R）0 = a, b, c, d, e, f, g R = T T = <a, b>,<a, g>,<b, g>,<c, b>,<d,c>, <d,f>,<e, d>,<f, a>,<f, e>,<g, c>,<g,

19、d>, <g,f> 2. （6分）对以下关键字序列建立哈希表：（SUN, MON, TUE, WED, THU, FRI, SAT），哈希 函数为H（K） = （K中最厉一个字母在字母表屮的序号）MOD 7。用线性探测法处理冲突，要 求构造一个装填因了为0. 7的哈希表，并计算出在等概率情况下資找成功的平均資找长度。3. （6分）将关键字序列（3, 26, 12, 61, 38, 40, 97, 75, 53,87）调整为人根堆。4. （4分）已知权值集合为:5, 7, 2, 3, 6, 9,要求给出哈夫曼树，并计算其带权路 径长度WPLo六、算法分析题（10分）阅读下面程序

20、，并冋答有关问题。其中BSTree为用一叉链表表示的一叉排序树类型。（1）简要说明程序功能。（5分）（2）n个结点的满二叉树的深度h是多儿？ （3分）（3）假设二叉排序树祐$亡是有n个结点的满一叉树，给出算法的时间复杂度。（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 =

21、NULL; q = *bst;while( q != NULL ) if ( K < q -> key ) f = q； q = q - lchild： else f = q; q = q -> rchild; if ( K < f -> key ) f -> lchild = s;elsef -> rchild = s;return 1;)七、算法设计题(25分)1.己知一个带头结点的幣数单链表L,要求将其拆分为一个正敝数单链表L1和一个负鞭 数单链表L2。(9分)2. 无向图采用邻接表存储结构，编写算法输出图中各连通分武的结点序列。（8分）3. 编

22、写一个建立二叉树的算法，要求采用二叉链表存储结构。（8分）数据结构附录A样卷参考答案:判断题题号12345678910答案XXJXJVVJXX二：选择题題1234567891011121314151617181920答BCADDDBDDAACBCCBCBCB三：填空1表长的半 2排好序列3, J 312 5N+16 S>ne：a=：P>M)d P>n£)d=S 7路径递增8Tqq(2)(Z)<)中序 10 97 II 链域个数不同 12 63 H 147614 Pwghwul 15 fife列査找16先进先出17 5 18 FDBECA 19将炬阵第i行全部置

23、0四，构造题计算函数值key7533Si4112886627Key%755365436(1)哈希表(4分.每对1个0.5分)index0123456789key2752887533411266(2)比较次数(3分)kevr7535524112886627Cmp12124175/SL=( 1 +2+1 +2+4+1 +7+5 )/8=23/«5,(1)(2)ASL=(1 +2»2+4*3+1 *4 )/8=21/8=2.62数拡结构附录B样卷：参考答案一、简容题（15分，毎小题3分）6. 算法是解决特定问题的操作序列.可以用多种方式描述。程序是算法在计算机屮的实现，与具体 的计算