2016上半年数据结构C++(二)答案

数据结构（C++）作业二一、单选题（每题2分，共20分）1、链表不具有的特点是__A__。A.可随机访问任一元素B.插入删除不需要移动元素C.不必事先估计存储空间D.所需空问与线性表长度成正比2、假设图的顶点数=n,边数=e，那么当用邻接表表示图时，拓扑排序算法的时间复杂度为__B______。A.O(n2)B.O(n+e)C.O(n*e)DO(n3)3、广义表((f),(f))的表尾是C。A.fB.(f)C.((f))D.()4、若指针L指向一带头结点的循环单链表的头结点，该表为空表的条件是__C____为真值；A.!(L-link);B.L==(L-link)-link;C.L-link;D.L==L-link;5、采用分块查找时，若线性表中共有625个元素，查找每个元素的概率相同，假设采用顺序查找来确定结点所在的块时，每块应分为__B_____个结点最佳。A.10B.25C.6D.6256、若线性表最常用的操作是存取第i个元素及其直接前驱的值，则采用___D__存储方式节省时间。A．顺序表B．双链表C．单循环链表D．单链表7、下列排序算法中时间复杂度不受数据初始状态影响，恒为O(n2)的是__C_______。A、堆排序B、起泡排序C、直接选择排序D、快速排序8、若某链表中最常用的操作是在最后一个结点之后插入一个结点和删除最后一个结点，则采用____D____存储方式最节省运算时间（假设链表仅设有一个first指针）。A.单链表B.双链表C.单循环链表D.带头结点的双循环链表9、一棵左右子树均不为空的二叉树在后序线索化后（不带头结点的线索化），其空指针域数为B_____。A、0B、1C、2D、不确定10、某二叉树的先序序列和后序序列正好相反，则该二叉树一定是_c___的二叉树。A.空或只有一个结点B.高度等于其结点数（空树高度为0）C.任一结点无左孩子D.任一结点无右孩子二、填空作图解答题（第4小题6分，其余9分，共60分）1.依次插入30，43，21，9，15，51并由空树构成一棵平衡二叉树，画出该平衡二叉树形成过程及其中序线索二叉树。2.已知广义表为（(),‘a’,(2,(‘c’,5,8)))；试画出该广义表的存储表示。3.用快速排序对下列关键字进行排序（图示）,基准元素取第一个元素。7033796746243040写出两趟排序的结果。第一趟排序之后:{40,33,67,46,24,30}70{79}或{40,33,30,67,46,24}70{79};第二趟排序之后:{30,33,24}40{67,46}70,79或{24,33,30}40{46,67}70,79;若基准元素按“三者取中”的原则取，则两趟排序的结果是：第一趟排序之后:;第二趟排序之后:;4.已知9个结点的值分别为1～9，请将各结点的值填入下面二叉排序树中：5.如下图已知哈希表为空，哈希函数为H（Key）=KeyMOD11,冲突解决方法分别用线性探测再散列和二次探测再散列。填入在依次插入关键字14，37，25，16之后的情况，并求等概率情况下所要求的平均查找长度。（1）线性探测再散列01234567891014372516（2）二次探测再散列01234567891025143716线性探测再散列查找不成功时的平均查找长度=____6/4=3/2=1.5_;二次探测再散列查找成功时的平均查找长度=____21/11_;6.已知一字符串bcbdebcecbdcabd，试设计其赫夫曼编码并画出相应的赫夫曼树。a：1；b：5；c：4；d：3；e：2；7.在下面数组a中链接存储着一个线性表，其表头“指针”为head==0，可利用空间表第一个元素的“指针”av==5：a012345678data6056423812742520link437-128-116a012345678519324678现在依次进行如下操作：1)在元素56前插入元素78；2）删除元素60；3）删除25；4）在元素56后插入66；5）在元素66前插入88。请问，在进行上面操作后，av==8,并将此时数组a的内容填入下表：三、程序填空题（每空2分，共20分）1.下面是仅给出了部分操作的二叉树类的定义和实现。试在程序的每一划线部分填入一条语句或表达式，完成计算度为1的结点个数的操作countNodes1()。typedefstructBinNode{intdata;structBinNode*leftchild,*rightchild;}BinNode,*BinTree;voidInitBinTree(BinTree&root)//初始化二叉树root{root=Null;}voidDestroyBinTree(BinTree&root)//销毁二叉树root{if(root==NULL)return;DestroyBinTree(root-leftchild);DestroyBinTree(root-rightchild);free(root);}intcountNodes1(BinTree&root)//计算二叉树root中度为1的结点数{if(①root!=NULL_){if(root-leftchild!=NULL&&root-rightchild!=NULL)__②returncountnoders(root-leftchild)+countnodes(root-rightchild)_____;elseif(root-leftchild==NULL&&__③_root-rightchild!=NULL_________)__④return1+countnodes1(root-rightchild)_____;elseif(root-leftchild!=NULL&&root-rightchild==NULL)__⑤_returncountnodes1(root-rightchild)+1_____________;}return0;}data8856423812742520link471-152-1362.下面是某种线性表类的定义和实现(仅给出了部分操作)。函数DE()是用来判断线性表是否对称（即线性表},,,{21naaa满足1iniaa，2,,2,1ni）。试在程序的每一划线部分填入一条语句或表达式,完成函数DE()。typedefstructNode{intdata;structNode*next,*prev;}Node,*List;voidInitList(List&L)//初始化线性表L{L=(List)malloc(sizeof(Node));L-next=L;L-prev=L;}voidDestroyList(List&L)//销毁线性表L{Node*p,*q;q=L-prev;while(___⑥L!=q____){p=q;q=q-prev;free(p);}free(L);}boolDE(List&L)//判断线性表L对称否{Node*p,*q;⑦p=l-next;q=L-prev;while(p-data==q-data){if(p==q||⑧p-next====q)returnTRUE;else{⑨p=p-next;⑩q=q-next;}}returnFALSE;}2.下面是某种线性表类的定义和实现(仅给出了部分操作)。函数DE()是用来判断线性表是否对称（即线性表},,,{21naaa满足1iniaa，2,,2,1ni）。试在程序的每一划线部分填入一条语句或表达式,完成函数DE()。typedefstructNode{intdata;structNode*next,*prev;}Node,*List;voidInitList(List&L)//初始化线性表L{L=(List)malloc(sizeof(Node));L-next=L;L-prev=L;}voidDestroyList(List&L)//销毁线性表L{Node*p,*q;q=L-prev;while(___⑥L!=q______){p=q;q=q-prev;free(p);}free(L);}boolDE(List&L)//判断线性表L对称否{Node*p,*q;⑦p=l-next;q=L-prev;while(p-data==q-data){if(p==q||⑧p-next====q)returnTRUE;else{⑨p=p-next;⑩q=q-next;}}returnFALSE;}