数据结构综合练习三及答案.doc

综合练习三一、判断改错题，正确的打”，错误的打”并改正（每小题2分，共20分）1、顺序存储结构的存储空间的一定是连续地址空间。( )2、队列中，删除和插入运算均在队尾进行。( )3、长度为n的顺序表中删除一个数据元素的时间复杂度为O(n)。( )4、有6个结点的完全二叉树中，共有3个叶子结点。( )5、5个结点的二叉树的二叉链表中共有5个空指针。( )6、快速排序是稳定的排序算法，其时间复杂度为O( n2 )。( )7、哈夫曼树的形态是唯一，所以其带权路径长度也是唯一的。( )8、二叉排序树的中序遍历结果是一个有序序列。( )9、链式存储结构可以使用折半查找。( )10、从双向循环链表的任意结点出发都可以访问到其它全部结点。( )二、应用题（共5小题，每小题10分，共50分）1、已知一棵二叉树的中序遍历结果为DBEACHFI和后序遍历结果为DEBHIFCA。请据此做如下回答：（1）画出该二叉树；（2）该二叉树的深度（根结点是第1层）；（3）该二叉树的先序遍历结果；（4）画出该树的孩子兄弟表示法下的存储结构图。2、已知一组关键字为（19,75,46,13,49, 82,57,31,26,55，79，72），地址空间为0至15，哈希函数取H(key)= key 11（1）用线性探测再散列处理冲突构造该哈希表；（2）求出等概率情况下查找成功的平均查找长度。3、已知有关键字序列3,26,12,61,38,5，分别写出采用下列排序算法进行递增排序的第一趟排序结果。（1）希尔排序（d=3）； （2）二路归并排序；（3）快速排序； （4）冒泡排序； （5）直接选择排序。4、已知一个无向带权图如图示，请据图作答： （1）找出该图中度为4的顶点。（2）画出该无向图的邻接矩阵； （3）使用克鲁斯卡尔算法求出该图的最小生成树。（须有中间过程）5、假设用于通信的电文仅由AI这9个字母组成，且其在电文中出现的频率分别为0.17，0.09，0.02，0.05，0.26，0.03，0.21，0.10，0. 07。请为这个通信系统设计哈夫曼编码。三、算法设计题（每空2分，共30分）1、线性表的顺序存储类型描述如下： typedef struct ElemType dataMaxSize; /存放顺序表元素 int length; /存放顺序表的长度 SqList; /顺序表的类型定义以下运算为在正序的顺序表L中插入值为e的元素并保持正序。请在空白处填上适当的语句。 void InsertElem(SqList *L, ElemType e) if (L-Length= MaxSize) return ; for( i= L-Length-1; i=0&L-datai=e; i-) /移位并定位 ; ; /置入新数据e ; /修改表长 2、顺序循环队列类型SqQueue定义如下: typedef struct ElemType dataMaxSize； int front , rear； /*队首和队尾指针*/ SqQueue 以下是元素入队算法（采用牺牲一个元素空间方法区分空队和满队）。，请在空白处填写适当的语句，使其构成完整的功能。int INQueue ( SqQueue *&q , ElemType e) if ( ) /*队满*/return 0; ; /队列指针修改 ; /元素入队return 1; 3、二叉树的二叉链表中，结点结构定义如下: typedef struct node char data; struct node *lchild ;struct node *rchild; BTNode;设二叉树采用二叉链存储结构存储。下述算法功能为统计给定二叉树上度为2的结点个数并输出相应结点。请在空白处填写适当的语句，使其构成完成的功能。void DisCnt2(BTNode * T ，int *cnt ) /T为二叉树指针，cnt为结点计数变量 if ( ) DisCnt2(BT-lchild);if ( ) printf(%c ,T-data，cnt); /输出该度为2的结点 ; / 计数 ; 4、循环单链表LinkList类型的定义如下: typedef struct Node /*定义链表结点类型*/ ElemType data; struct Node *next; /*指向后继结点*/ LinkList;下述算法功能是在带头结点的循环单链表L上第i个结点之后插入一个值为e的数据元素结点。请在空白处填写适当的语句，使其构成完整的功能。int ListInsertPost(LinkList *&L , int i , ElemType e) int j=0; LinkList *p=L,*q; while ( & ) / 在循环单链表上定位第i个结点 j+; ;if (p=L) return 0; /*未找到位序为i的结点*/ else/*找到位序为i的结点*p*/ q=(LinkList *)malloc(sizeof(LinkList); /*创建新结点*/ q-data=e; ； /*将*q插入到*p之后*/ ； return 1; 综合练习三参考答案一、判断改错题（每小题2分，共20分）1、 评分标准：判断给2分。2、 队列中，删除运算在队头进行，插入运算在队尾进行。 评分标准：判断给1分，改正给1分。3、 评分标准：判断给2分。4、 评分标准：判断给2分。5、 有6个空指针 评分标准：判断给1分，改正给1分。6、 快速排序是不稳定的排序算法，其时间复杂度为O( nlogn )。评分标准：判断1分，改正1分。7、 哈夫曼树的形态不唯一，但其带权路径长度是唯一的。评分标准：判断给1分，改正给1分。8、 评分标准：判断给2分。9、 链式存储结构不可以使用折半查找。评分标准：判断给1分，改正给1分。10、 评分标准：判断给2分。DBACFIEH二、应用题（50分）1、（10分）（1） （4分） A I H F E C D B（2）4 （1分）（3）先序序列：ABDECFHI（1分）（4）（4分）2、（10分）（1）(错一个关键字扣0.5分，8分)H(key)= key 11 Hi(key)=(H(key)+di) % 16 , di=1,2,3,15554613574982261975317972 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15（2）等概率情况下查找成功的平均查找长度=1/12（1+1+1+2+1+2+3+2+4+1+10+7）=35/12 （2分）3、（10分）（1）3，26，5，61，38，12 （2分）（2）3，26，12，61，5，38 （2分）（3）3，26，12，61，38，5 （2分）（4）3，12，26，38，5，61 （2分）（5）3，26，12，61，38，5 （2分）4、（10分）（1）A、B、D、E、F (2分)（2） （3分）ABCDEFGA182346B185812C510D8101520E23121525F420257G67（3）（5分）5、（哈夫曼树6分，编码4分，结果不唯一） 三、算法设计题（30分）1、 （6分） L-datai+1= L-datai; （2分） L-datai+1=e; （2分） L-Length+; 或L-Length= L-Length+1; （2分）2、 （6分）(q-rear+1) % MaxSize = q-front （2分）q-rear =(q-rear+1) % MaxSize; （2分）q-dataq-rear=e; （2分）3、（8分）T!=NULL 或 T