数据结构2012-2013海南大学

1.栈的逻辑特点是___先进后出，________，队列的逻辑特点是____先进先出_____。2.线性表的顺序存储结构是一种（A）的存储结构，线性结构的链式存储是一种（B）的存储结构。A．随机存取B.顺序存取C.索引存取D.散列存取3.向一个栈顶指针为top的带头结点的非空的链栈中删除结点，则其操作步骤是（C）A.top-next=s;top=sB.s-next=top-next;top-next=s;free(s)C.s=top;top=top-next;free(s)D.s=top-next;top=top-next;free(s)4.向一个栈顶指针top的链栈中插入一个s所指的结点时，执行的操作是（B）A.top-next=s;top=sB.s-next=top-next;top-next=s;free(s)C.s=top;top=top-next;free(s)D.s=top-next;top=top-next;free(s)5.设链队列的队头指针为front，队尾指针为rear，队列为空的条件是___front==rear___；_________，队列为满的条件是____front==(rear+1)%m________。6.带头结点head的单向循环链表为空的判断条件是（B）A.head==NULLB.head-next==NULLC.head-next==headD.head!=NULL7.在一个长度为n的单链表的第i（0=in）个元素后面插入一个元素时，需要向后移动（D）个元素。A．n-iB.n-i+1C.n-i-1D.08.在一个长度为n的顺序存储的线性表中，删除第i个元素(1≤i≤n+1)时，需要从前向后依次前移（C）个元素。A．n-iB.n-i+1C.n-i-1D.09.若某线性表最常用的操作是在最后一个元素之后插入一个元素和删除进入表中的最后一个元素，则采用（b）存储方式最节省运算时间和存储空间。A.单链表B.仅有头指针的单循环链表C.双向链表D.仅有头尾指针的单循环链表单链表最后一个元素之后插入一个元素的时间复杂度为O（n）仅有尾指针的单循环链表最后一个元素之后插入一个元素的时间复杂度为O（1）10.设有一个顺序栈S，元素abcdef依次进栈，如果6个元素出栈的顺序是bdcfea，则栈的容量至少应该是（B）A.2B.3C.5D.611.设有一个顺序栈S，元素a,b,c,d,e,f依次进栈，如果6个元素的出栈顺序为a,c,d,b,f,e,则栈的容量至少应该是（D）A.2B.3C.5D.612.试编写算法，在一个循环单链表中删除结点S，且要求函数返回该链表的一个入口指针。假设表长大于1，且表中即无头结点，也无头指针，函数原型为voiddelete_xyz(NODE*S)。NODE*deletexyz(NODE*S){}13.一棵有124个叶结点的完全二叉树，最多有（a）个结点A、247B、248C、249D、25114.一棵非空的二叉树的前序遍历序列和后序遍历序列正好相同，则该二叉树一定满足（A）A.所有的结点均无左孩子B.所有的结点均无右孩子C.只有一个孤立的结点D.是任意一棵二叉树一棵非空的二叉树的前序遍历序列和后序遍历序列正好相反，则该二叉树一定满足（B）A.所有的结点均无左孩子B.所有的结点均无右孩子C.只有一个孤立的结点D.是任意一棵二叉树15.由同一关键字集合构造的各棵二叉排序树(b)A.其形态不一定相同，但平均查找长度相同B.其形态不一定相同，平均查找长度也不一定相同C.其形态均相同，但平均查找长度不一定相同D.其形态均相同，平均查找长度也都相同16.将含100个结点的完全二叉树从根开始，每层从左到右依次对结点编号，根结点的编号为1，则编号为31的结点的双亲的编号为______15___，其右子的编号为____63_____。17.设树F由T1，T2，T3三棵子树组成，与F对应的二叉树为B。已知T1,T2,T3的结点数分别为x，y，z，则该二叉树B的左子树中有__x-1__个结点，右子树中有____y+z1去······~__个结点。、18.对下图所示的树，分别写出其先序和后序序列，并转换成对应的二叉树19.设h是带表头结点的单链表的头指针，请设计一个逆置这个单链表的程序。即原链表为(a1,a2,a3…an)，逆置后变为(an,an-1…a2,a1)。（6分）单链表结点结构为：typedefstructnode{intdata;___*link}LNode;（2分）voidinvert(LNode*h){LNode*s,*p;p=h-link;h-link=________;（2分）while(p!=NULL){s=p;p=p-link;____（S-next=H-next;）_________（2分）h-link=s;}}20.已知字符A、B、C、D的使用频率（权值）分别为22，7，9，27。对其进行HUFFMAN编码，各字符对应的编码为（）A）A（001）B（100）C（110）D（0）B）A（100）B（101）C（0）D（11）C）A（11）B（100）C（111）D（0）D)A（100）B（1011）C（11）D（0）21已知某二叉树BINTREE的结点结构如下,根结点的指针为T，试编写一算法，求该二叉树的深度。函数形式（参考）：voidBiTreeDepth(BiTreeT,intlevel,int&depth)22、代码如下：（6分）下面是在递增有序表R[n]中的下标在low到high范围内的区域查找键值为K的元素的二分查找的递归算法，请在划线处填上适当的内容。/*有序表R进行二分查找递归算法*/inthalfsearch（R,low,high,k）intlow,high,k;/*在顺序表R上进行二分查找,k为给定的关键字值*/int;rectypeR[];{intmid;if（lowhigh）_______________/*检索失败*/else{mid=(high+low)/2;/*设置查找的中间位置mid*/switch（k）{caseR[mid].keyk:return（halfsearch（R,_________________）;break;caseR[mid].keyk:return（halfsearch（R,________________）;break;caseR[mid].key==k:return（mid）;break;}/*SWITCH*/}/*ELSE*/}/*HALFSEARCH*/