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

1、 附录A 样卷一一、判断题：（10 分）  正确在括号内打，错误打× (  ) 1.在单链表中，头结点是必不可少的。（  ）2如果一个二叉树中没有度为1的结点，则必为满二叉树。 (  ) 3. 循环链表的结点结构与单链表的结点结构完全相同，只是结点间的连接方式不同。 (  ) 4. 顺序存储结构只能用来存放线性结构；链式存储结构只能用来存放非线性结构。 (  ) 5. 在一个大根堆中，最小元素不一定在最后。 (  ) 6. 在一个有向图中，所有顶点的入度之和等于所有

2、顶点的出度之和。（  ）7. 在采用线性探测法处理冲突的散列表中，所有同义词在表中相邻。（  ）8. 内部排序是指排序过程在内存中进行的排序。（  ）9. 拓扑排序是指结点的值是有序排列。 (  )10. AOE网所表示的工程至少所需的时间等于从源点到汇点的最长路径的长度。 二、选择题(30分, 每题1.5分)1有一个含头结点的单链表，头指针为head,  则判断其是否为空的条件为：_   A head=NIL     B. head.next=NIL &

3、#160;    C.  head.next=head    D. head<>NIL或 A head=NULL  B. Head->next=NULL  C.  head->next=head  D. Head!=NULL2非空的循环单链表head的尾指针p满足_。   A.  p.next=NIL      B.  p=NIL   

4、0;     C.  p.next=head      D.  p=head或 A.  p->next=NULL    B.  p=NULL     C.  P->next=head     D.  p=head3链表不具有的特点是        。

5、0;  A、可随机访问任一个元素                        B、插入删除不需要移动元素   C、不必事先估计存储空间                 

6、       D、所需空间与线性表的长度成正比4若某链表中最常用的操作是在最后一个结点之后插入一个结点和删除最后一个结点，则采用        存储方式最节省运算时间。   A、单链表              B、双链表        &

7、#160;   C、单循环链表     D、带头结点的双循环链表5若线性表最常用的操作是存取第i个元素及其前驱的值，则采用        存储方式节省时间。   A、单链表              B、双链表         &

8、#160;  C、单循环链表            D、顺序表6设一个栈的输入序列为A，B，C，D，则借助一个栈所得到的输出序列不可能的是        。    A、 A，B，C，D                &#

9、160;                   B、D，C，B，AC、 A，C，D，B                            

10、        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

11、，18设循环队列中数组的下标范围是1n，其头尾指针分别为f，r，若队列中元素个数为        。   A、r-f                    B 、r-f+1             C

12、、（r-f+1）mod n    D、（r-f+n）mod n9串是        。   A、不少于一个字母的序列                        B、任意个字母的序列   C、不少于一个字符的序列  &

13、#160;                     D、有限个字符的序列10数组A1.5,1.6的每个元素占5个单元，将其按行优先次序存储在起始地址为1000的连续内存单元中，则A5，5的地址是        。   A、1140      

14、0;   B、1145         C、1120         D、112511将一棵有100个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，根结点编号为1，则编号为49的结点的左孩子的编号为        。   A、98      

15、0;       B、99            C、50            D、4812对二叉树从1开始编号，要求每个结点的编号大于其左右孩子的编号，同一个结点的左右孩子中，其左孩子的编号小于其右孩子的编号， 则可采用        实现编号。

16、  A、先序遍历            B、中序遍历         C、后序遍历        D、从根开始进行层次遍历13某二叉树的先序序列和后序序列正好相反，则该二叉树一定是        的二叉树。  A、空或只有一个结点 

17、0;                        B、高度等于其结点数  C、任一结点无左孩子                      

18、    D、任一结点无右孩子14在有n个叶子结点的哈夫曼树中，其结点总数为        。  A、不确定 B、2n     C、2n+1        D、2n-115一个有n个顶点的无向图最多有        条边。  A、n      

19、;    B、n（n-1）         C、n（n-1）/2             D、2n16任何一个无向连通图的最小生成树        。  A、只有一棵          &#

20、160; B、有一棵或多棵         C、一定有多棵            D、可能不存在17一组记录的关键字为（46，79，56，38，40，84），利用快速排序的方法，以第一个记录为基准得到的一次划分结果为        。  A、38，40，46，56，79，84  B、40，38，46，79，56，84&

21、#160; C、40，38，46，56，79，84  D、40，38，46，84，56，7918已知数据表A中每个元素距其最终位置不远，则采用        排序算法最节省时间。    A、堆排序        B、插入排序    C、快速排序    D、直接选择排序19下列排序算法中，      

22、  算法可能会出现下面情况：初始数据有序时，花费时间反而最多。    A、堆排序            B、冒泡排序         C、快速排序        D、SHELL 排序20对于键值序列（12，13，11，18，60，15，7，18，25，100），用筛选法建堆，必须从键值为 

23、       的结点开始。   A、100            B、60            C、12            D、15三、填空题（40分）1 在顺序表（即顺序存储结构的线

24、性表）中插入一个元素，需要平均动       个元素.2.         快速排序的最坏情况，其待排序的初始排列是                           .3.  为防止在图

25、中走回，应设立                             .4. 一个栈的输入序列为123，写出不可能是栈的输出序列                

26、;  。5. N个结点的二叉树,采用二叉链表存放,空链域的个数为             .6. 要在一个单链表中p所指结点之后插入s所指结点时,     应执行                    和    

27、0;                  的操作. 7.Dijkstra算法是按                   的次序产生一点到其余各顶点最短路径的算法.8.在N个结点完全二叉树中，其深度是   

28、                    .9.对二叉排序树进行          遍历, 可得到结点的有序排列.10设一哈希表表长M为100 ，用除留余数法构造哈希函数，即H（K）=K MOD P（P=M,  为使函数具有较好性能，P应选       

29、;               11单链表与多重链表的区别是                  12深度为6（根层次为1）的二叉树至多有             

30、;   个结点。13已知二维数组A0.200.10采用行序为主方式存储，每个元素占4个存储单元,并且A00的存储地址是1016, 则A105的存储地址是             14循环单链表La中，指针P所指结点为表尾结点的条件是              15在查找方法中，平均查找长度与结点个数无关的查找方法是&#

31、160;              。16队列的特性是                  17具有3个结点的二叉树有           种18已知一棵二叉树的前序序列为ABDFCE，中序序列为DFB

32、ACE，后序序列为           19已知一个图的邻接矩阵表示，要删除所有从第i个结点出发的边，在邻接矩阵运算是                          四、构造题：（30 分）1已知关键字序列为：（75, 33, 52, 41, 1

33、2, 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）。&

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

35、160;  即指：a1= an，a2= an-1  。    结点结构为 priordatanext 数据结构 附录B 样卷二一、简答题（15分，每小题3分）1. 简要说明算法与程序的区别。2. 在哈希表中，发生冲突的可能性与哪些因素有关？为什么？3. 说明在图的遍历中，设置访问标志数组的作用。4. 说明以下三个概念的关系：头指针，头结点，首元素结点。5. 在一般的顺序队列中，什么是假溢出？怎样解决假溢出问题？二、判断题（10分，每小题1分） 正确在括号内打，错误打×( )（1）广义表( a ), b), c ) 的表头是(

36、 a ), b)，表尾是( c )。( )（2）在哈夫曼树中，权值最小的结点离根结点最近。( )（3）基数排序是高位优先排序法。( )（4）在平衡二叉树中，任意结点左右子树的高度差（绝对值）不超过1。( )（5）在单链表中，给定任一结点的地址p，则可用下述语句将新结点s插入结点p的后面 ：p->next = s; s->next = p->next;( )（6）抽象数据类型（ADT）包括定义和实现两方面，其中定义是独立于实现的，定义仅给出一个ADT的逻辑特性，不必考虑如何在计算机中实现。( )（7）数组元素的下标值越大，存取时间越长。( )（8）用邻接矩阵法存储一个图时，在不

37、考虑压缩存储的情况下，所占用的存储空间大小只与图中结点个数有关，而与图的边数无关。( )（9）拓扑排序是按AOE网中每个结点事件的最早发生时间对结点进行排序。( )（10）长度为1的串等价于一个字符型常量。三、单项选择题（10分, 每小题1分）1排序时扫描待排序记录序列，顺次比较相邻的两个元素的大小，逆序时就交换位置。这是哪种排序方法的基本思想？ A、堆排序B、直接插入排序C、快速排序D、冒泡排序2 已知一个有向图的邻接矩阵表示，要删除所有从第i个结点发出的边，应该：A）将邻接矩阵的第i行删除 B）将邻接矩阵的第i行元素全部置为0C）将邻接矩阵的第i列删除 D）将邻接矩阵的第i列元素全部置为0

38、3有一个含头结点的双向循环链表，头指针为head, 则其为空的条件是：A. head->priro=NULL B. head->next=NULL C. head->next=head D. head->next-> 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）读取队头元素的

39、值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(log2n) B) O(n) C) O(nlog2n) D) 不直接依赖于n9将一棵有100个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，根结点编号为1，则编号最大的非叶结点的编号为： A、48B、49C、50D、

40、5110某二叉树结点的中序序列为A、B、C、D、E、F、G，后序序列为B、D、C、A、F、G、E，则其左子树中结点数目为：A）3 B）2 C）4 D）5四、填空题（10分，每空1分）1填空完成下面一趟快速排序算法：int QKPass ( RecordType r , int low， int high) x = r low ； while ( low < high )while ( low < high && r . key >= x.key ) high - -；if ( low < high ) r = r high ； low+; while (

41、 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已知一个3行、4列的二维数组A（各维下标均从1开始），如果按“以列为主”的顺序存储，则排在第8个位置的元素是： 5高度为h的完全二叉树最少有 个结点。五、构造题（20 分）1（4分）已

42、知数据结构DS的定义如下，请给出其逻辑结构图示。DS = (D, R)D = 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, d>, <g, f> 2（6分）对以下关键字序列建立哈希表：（SUN, MON, TUE, WED, THU, FRI, SAT）,哈希函数为H(K)

43、 =（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 ，要求给出哈夫曼树，并计算其带权路径长度WPL。六、算法分析题（10分）阅读下面程序，并回答有关问题。其中BSTree为用二叉链表表示的二叉排序树类型。（1） 简要说明程序功能。（5分）（2） n个结点的满二叉树的深度h是多少？（3分）（3） 假设二叉排序树*bst是有n个结点的满二叉树,

44、给出算法的时间复杂度。（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 < q -> key ) f = q; q = q -> lchild; else f = q; q = q -> rchild; if ( K < f -> key ) f -> lchild = s; else f -> rchild = s; return 1; 七、算法设计题（25分）1 已知一个带头结点的整数单链表L，要求将其拆分为一个正整数单链表L1和一个负整数单链表L2。（9分）2 无向图采用邻接表存储结构，编写算法输出图中各连通分量的结点序列。（8分） 3 编写