数据结构练习题答案(2007年11月14日)

1数据结构练习题数据结构练习题（1－5章）一、选择题1、从逻辑上可以把数据结构分为（c）两大类。A．动态结构、静态结构B．顺序结构、链式结构C．线性结构、非线性结构D．初等结构、构造型结构2、以下数据结构中，哪一个是线性结构（D）？A．广义表B.二叉树C.稀疏矩阵D.串3、在下面的程序段中，对x的赋值语句的频度为（C）for(i=1;i=n;i++)for(j=1;j=n;i++)x=x+1;A．O(2n)B．O(n)C．O(n2)D．O(log2n)4、下面关于线性表的叙述中，错误的是哪一个？（B）A．线性表采用顺序存储，必须占用一片连续的存储单元。B．线性表采用顺序存储，便于进行插入和删除操作。C．线性表采用链接存储，不必占用一片连续的存储单元。D．线性表采用链接存储，便于插入和删除操作。5、某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（D）存储方式最节省运算时间。A．单链表B．仅有头指针的单循环链表C．双链表D．仅有尾指针的单循环链表6、静态链表中指针表示的是（B）.A．内存地址B．数组下标C．下一元素地址D．左、右孩子地址7、下面的叙述不正确的是（BC）A．线性表在链式存储时，查找第i个元素的时间同i的值成正比B.线性表在链式存储时，查找第i个元素的时间同i的值无关C.线性表在顺序存储时，查找第i个元素的时间同i的值成正比D.线性表在顺序存储时，查找第i个元素的时间同i的值无关8、若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（C）(1=i=n+1)。A.O(0)B.O(1)C.O(n)D.O(n2)9、在单链表指针为p的结点之后插入指针为s的结点，正确的操作是：（B）。A．p-next=s;s-next=p-next;B．s-next=p-next;p-next=s;C．p-next=s;p-next=s-next;D．p-next=s-next;p-next=s;10、对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是（B）A．head==NULLB．head→next==NULLC．head→next==headD．head!=NULL211、一个栈的输入序列为123…n，若输出序列的第一个元素是n，输出第i（1=i=n）个元素是（B）。A.不确定B.n-i+1C.iD.n-i12、有六个元素6，5，4，3，2，1的顺序进栈，问下列哪一个不是合法的出栈序列？（C）A.543612B.453126C.346521D.23415613、设有三个元素X，Y，Z顺序进栈（进的过程中允许出栈），下列得不到的出栈排列是(C)。A．XYZB.YZXC.ZXYD.ZYX14、假设以数组A[m]存放循环队列的元素,其头尾指针分别为front和rear，则当前队列中的元素个数为（A）。A．(rear-front+m)%mB．rear-front+1C．(front-rear+m)%mD．(rear-front)%m15、若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为多少？(B)A.1和5B.2和4C.4和2D.5和116、下面关于串的的叙述中，哪一个是不正确的？（B）A．串是字符的有限序列B．空串是由空格构成的串C．模式匹配是串的一种重要运算D．串既可以采用顺序存储，也可以采用链式存储17、设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为（C）A．求子串B．联接C．匹配D．求串长18、设有数组A[i,j]，数组的每个元素长度为3字节，i的值为1到8，j的值为1到10，数组从内存首地址BA开始顺序存放，当用以列为主存放时，元素A[5，8]的存储首地址为(B)。A.BA+141B.BA+180C.BA+222D.BA+22519、已知广义表L=（（x,y,z），a，（u，t，w）），从L表中取出原子项t的运算是（D）。A.head（tail（tail（L）））B.tail（head（head（tail（L））））C.head（tail（head（tail（L））））D.head（tail(head（tail（tail（L）））)）20、广义表A=(a,b,(c,d),(e,(f,g))),则下面式子的值为（D）。Head(Tail(Head(Tail(Tail(A)))))A.(g)B.(d)C.cD.d二、判断题1、数据元素是数据的最小单位。(×)2、算法可以用不同的语言描述，如果用C语言或PASCAL语言等高级语言来描述，则算法实际上就是程序了。(Y)3、顺序存储方式的优点是存储密度大，且插入、删除运算效率高。(×)4、线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。(×)35、线性表的特点是每个元素都有一个前驱和一个后继。(×)6、一个稀疏矩阵Am*n采用三元组形式表示，若把三元组中有关行下标与列下标的值互换，并把m和n的值互换，则就完成了Am*n的转置运算。（×）7、所谓取广义表的表尾就是返回广义表中最后一个元素。（×）三、填空题1、数据的物理结构包括数据元素的表示和关系的表示。2、当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用___顺序__存储结构。3、线性表L=（a1,a2,…,an）用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是_(n-1)/2____。4、对于一个具有n个结点的单链表，在已知的结点*p后插入一个新结点的时间复杂度为__O(1)__,在给定值为x的结点后插入一个新结点的时间复杂度为___O(n)_____。5、带头结点的双循环链表L中只有一个元素结点的条件是：__L-next-next==L__6、一个栈的输入序列是：1，2，3则不可能的栈输出序列是__312___。7、用S表示入栈操作，X表示出栈操作，若元素入栈的顺序为1234，为了得到1342出栈顺序，相应的S和X的操作串为_SXSSXSXX__。8、__队列__又称作先进先出表。9、组成串的数据元素只能是__字符___。10、设有C语言描述的二维数组A[10][20],其每个元素占两个字节，第一个元素的存储地址为100，若按行优先顺序存储，则元素A[6][6]存储地址为__352__。四、算法与应用题1.设线性表存放在向量A[arrsize]的前elenum个分量中且递增有序，试写一算法将x插入到线性表的适当位置，以保持线性表的有序性并分析其时间复杂度。#definearrsize100boolsortinsert(ElemtypeA[],intelenum,Elemtypex){inti;if(elenum==arrsize){4printf(“该数组向量已满”)；returnfalse;}i=elenum-1;while(A[i]x&&i=0){A[i+1]=A[i];i--;}A[i+1]=x;returntrue;}//写的还是比较粗糙，有待进一步改进//2005年4月19日2.已知带头结点的动态单链表L中的结点是按整数值递增排列的，试写一算法将值x为的结点插入到表L中，使L仍然有序。///线性表的单链表存储结构typedefstructLnode{ElemTypedata;structLnode*next;}LNode,*LinkList;LinkListsortinsert(LinkListL,intx)/*带头结点*/{LinkListp,q,s;s=(LinkList)malloc(sizeof(LNode));if(!s){printf(“动态空间分配不成功”)；exit(-1);}s-data=x;q=L;p=L-next;while(p!=NULL&&p-datax){q=p;p=p-next;}s-next=q-next;q-next=s;returnL;5}3.在长度大于1的单循环链表L中，既无头结点也无头指针。s为指向链表中某个结点的指针，试编写算法删除结点*s的直接前趋结点。//条件是长度大于一#includeiostreamusingnamespacestd;typedefstructLnode{ElemTypedata;structLnode*next;}LNode,*LinkList;booldelete_prior(LinkLists){LinkListp;LinkListq;q=s;p=s-next;while(p-next!=s){q=p;p=p-next;}q-next=s;deletep;}五、程序填空题1、下面是用c语言编写的对不带头结点的单链表进行就地逆置的算法，该算法用L返回逆置后的链表的头指针，试在空缺处填入适当的语句。voidreverse（linklist&L）{p=null；q=L；while（q！=null）{(1)L=L-next;q-next=p；p=q；(2)q=L___;}(3)L=p；}}}2、对单链表中元素按插入方法排序的C语言描述算法如下，其中L为链表头结点指针。请填充算法中标6出的空白处，完成其功能。（10分）typedefstructnode{intdata;structnode*next;}linknode,*link;voidInsertsort(linkL){linkp,q,r,u;p=L-next;(1)L-next=NULL___;while((2)_p!=NULL__________){r=L;q=L-next;while((3)q!=NUll_&&q-data=p-data){r=q;q=q-next;}u=p-next;(4)_p-next=q___;(5)_r-next=p_;p=u;}}第六章练习选择题1.设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1则T中的叶子数为（D）A．5B．6C．7D．82.设森林F对应的二叉树为B，它有m个结点，B的根为p,p的右子树结点个数为n,森林F中第一棵树的结点个数是（A）A．m-nB．m-n-1C．n+1D．条件不足，无法确定3．若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（B）A．9B．11C．15D．不确定4．具有10个叶结点的二叉树中有（B）个度为2的结点，A．8B．9C．10D．ll5．一棵完全二叉树上有1001个结点，其中叶子结点的个数是（E）A．250B．500C．254D．505E．以上答案都不对6.有n个叶子的哈夫曼树的结点总数为（D）。A．不确定B．2nC．2n+1D．2n-17.一棵具有n个结点的完全二叉树的树高度（深度）是（A）7A．logn+1B．logn+1C．lognD．logn-18．深度为h的满m叉树的第k层有（A）个结点。(1=k=h)A．mk-1B．mk-1C．mh-1D．mh-19．在一棵高度为k的满二叉树中，结点总数为（C）A．2k-1B．2kC．2k-1D．log2k+110．对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采用(C)次序的遍历实现编号。A．先序B.中序C.后序D.从根开始按层次遍历11．树的后根遍历序列等同于该树对应的二叉树的(B).A.先序序列B.中序序列C.后序序列12．已知某二叉树的后序遍历序列是dabec,中序遍历序列是debac,它的前序遍历是（D）。A．acbedB．decabC．deabcD．cedba13．二叉树的先序遍历和中序遍历如下：先序遍历：EFHIGJK；中序遍历:HFIEJKG。该二叉树根的右子树的根是：CA、EB、FC、GD、H14．对于前序遍历与