资源描述：
《数据结构部分习题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、习题一 1．试列举出实际生活中的一些数据，并指出其数据元素、数据项、数据元素之间的关系，并定义若干基本运算。答：（略） 2．求下列程序段的时间复杂度： x=1;2.有初始的无序序列{98,65,38,40,12,51,100,77,26,88},给出对其进行归并排序(升序)的每一趟的结果。2.已知序列{15,18,60,41,6,32,83,75,95}。请给出采用冒泡排序法对该序列作升序排序时的每一趟的结果。2.结果如下：初始序列：15，18，60，41，6，32，83，75，95第一趟：15，18，41，6，32，60，75，83，95
2、第二趟：15，18，6，32，41，60，75，83，95第三趟：15，6，18，32，41，60，75，83，95第四趟：6，15，18，32，41，60，75，83，95第五趟：6，15，18，32，41，60，75，83，95 第五趟排序时已无元素交换，则排序结束。⒋设散列函数Ｈ(Ｋ)＝Ｋ%７，采用拉链法处理冲突，对下面输入序列，；要求：构造出该散列表，并求出在等概率情况下成功的平均查找长度。输入序列：100,90,120,60,78,35,42,31,15,20,22,12,16,27⒌对数据表（25,50,70,100,43,7,1
3、2）采用直接插入排序算法进行排序，写出每趟的结果。 ⒋散列表如下：在等概率情况下成功的平均查找长度为(1*7+2*5+3*1+4*1)/14=24/14。⒌插入排序算法每趟的结果如下：[25],50,70,100,43,7,12[25,50],70,100,43,7,12[25,50,70],100,43,7,12[25,50,70,100],43,7,12[25,43,50,70,100],7,12[7,25,43,50,70,100],12[7,12,25,43,50,70,100] for(i=2;i<=n;i++) for(j
4、=1;j<=i;j++)x++;答：时间复杂度为O(n2)。习题二 1．若某线性表中最常用的操作是在第ｉ个元素之前插入一个元素和删除第ｉ个元素，则采用＿＿＿＿存储方式最节省运算时间。 a.散列表b.单链表c.二叉链表d.顺序表 答：b 2．判断：线性表采用链表存储后，线性表的长度等于链表中的结点个数。答：× 3．在单链表中，若要在指针Ｐ所指结点后插入指针Ｓ所指结点，则需执行下列两条语句：Ｓ->next=Ｐ->next；＿＿＿＿＿＿＿＿＿。 答：Ｐ->next=S;4．单链表中指针Ｐ所指结点存在后继结点的条件是＿＿＿＿＿＿＿＿。答：Ｐ->
5、next!=NULL 5．编写算法，判断带头结点的单循环链表Ｌ中从第三项起的各结点的值是否是其前面两项之差的绝对值。已知Ｌ的结点数不少于３，且各结点有data和next两个字段。 答：BOOLjudge(node*L){node*p,*q;q=L->next;p=q->next->next; while(p!=L&&p->data==abs(q->data-q->next->data)){p=p->next; q=q->next; } if(p==L)returnTRUE;elsereturnFALSE;
6、 }习题三 1．设输入序列为Ａ，Ｂ，Ｃ，Ｄ。借助一个栈可以得到的输出序列是＿＿＿＿。 a.Ａ,Ｃ,Ｄ,Ｂb.Ｃ,Ａ,Ｄ,Ｂc.Ｄ,Ｃ,Ａ,Ｂd.Ｄ,Ａ,Ｂ,Ｃ答：a ⒉栈和队列都是＿＿＿＿。a.顺序存储的线性表b.链式存储的线性表 c.限制存储点的线性表d.限制存储点的非线性结构 答：c 3．判断：栈只能采用链式存储方式。 答：× 4设有一个链栈，其中各结点中有data和next两字段，栈顶指针为Ls（≠NULL），则执行退栈的基本操作是＿＿＿＿＿＿＿＿＿＿。 答：Ls=Ls->next; 5、数组Ｂ[４,６]的元素占４个
7、单元。从首地址1000开始将其按行优先方式存储，则元素Ｂ[３,４]的地址为＿＿＿＿＿＿＿＿。 答：1088习题四 1．已知完全二叉树有80个结点，则整个二叉树有＿＿＿＿＿＿个度为１的结点。 a.０b.１c.２d.不确定答：b 2．若二叉树的先序序列和中序序列正好相同，则一定是一棵＿＿＿＿＿＿的二叉树。a.结点个数可能大于１且无左子树b.结点个数可能大于１且无左孩子c.结点个数可能大于１且各结点均无左孩子 d.其中任意一个结点的度不为２答：c3．判断：由二叉树的先序序列和后序序列不能唯一确定一棵二叉树。答：√ 4．在有ｎ（ｎ＞０）个结点的
8、二叉链表中，空链域的个数为＿＿＿＿＿＿。答：n＋1 5设二叉树采用二叉链表表示，设计算法仅打印出其中所有叶子结点的值。答：voidpreorder(b
