计算机软件基础(二)习题解解答

《计算机软件基础(二)习题解解答》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、算机软件基础习题解答第一章概论（答案参阅）1、P12、P23、P44、P45、P56、P27、P78、P59、P72、第二章数据结构一、选择题1.BP18(2)2.DP16(5)3.DP26(40)4.CP23(1)5.DP30(3)即：98+((8-1)×8+(3-1))×5＝3886.CP35(2)7.BP34(3)8.AP35(45)9.BP36(7)10.CP36(48)11.AP38(5)12.BP45(41)二、填空题1.数据元素数、字符串、一个或多个数据项P9(40)2.顺序存储结构P11(9)3.随机P15(48)顺序P16(40)4

2、.栈顶　栈底　P22（38）5.队列　P256.行下标　列下标　该元素的值7.２i-1　P358.右孩子　P38(40)9.线性查找　P45(30)10.n22（）即探测总次数为1+2+3+…+n-111.Log2256=8三、判断题1.B2.B3.B4.B5.B6.A7.A8.A9.B四、问答题1.P112.对一个已建立好的单链表（表头指针为head），编写一算法计算该链表中的结点个数。（要求给出结点的结构描述）统计结点个数intListLength(LinkListhead){inti=0;LinkListp=head->next;While(p

3、){i++;p=p->next;}returni;}3.给定一个n项元素的线性表V，写一个过程将元素排列的次序颠倒过来，#definen100IntV[n];Intk=0,front=1,rear=n;Scanf(“%d”,&V[n]);While(front!=rear);V[0]=V[front];V[front]=V[rear];V[rear]=V[0];frout++;rear--;4．试设计实现在单链表中删去值相同的多余结点的算法del(LinkList*head){//删除单链表中值相同的多余结点LinkList*p,*s,*q;p=he

4、ad->next;while(p!=NULL&&p->next!=NULL){s=p;//s指向要删除结点的前趋q=p->next;while(q!=NULL){if(q->data==p->data)}//查找值相同的结点并删除{s->next=q->next;free(q);q=s->next;}else{s=q;q=q->next;}}p=p->next;}}5.P206．设计计算线性链表长度的算法intListlength(LinklistL)//求链表长度{Linklistp;intj=0;p=L;while(p->next!=NULL){

5、++j;p=p->next;}returnj;}7.设一线性链表，其结点值为正整数序列，且按值从小到大链接，设计算法，将此线性链表分成两个纯属链表，其中一个结点值均为奇数，而另一个均为偶数，且也是从小到大链接。把原链表中头节点和第二个节点地址传入函数void*f(structstu*head,structstu*head1){structstu*p1,*p2;p1=head;p2=head1;for(inti=1;p1->next!=NULL&&p2->next!=NULL;i++)if(i%2!=0)//是奇数节点p1=p2->next;//指向下

6、个奇数节点else//是偶数节点p2=p1->next;//指向下个偶数节点p1->next=NULL;p2->next=NULL;}8.设有一个循环单链表长度大于１,且表中既无头结点也无头指针。已知S为指向链表中某一结点的指针，写出在链表中删除S指针所指结点的前趋结点的算法link*p,*q;p=s;while(p->next->next!=s){p=p->next;}q=p->next;p->next=s;deleteq;9.已知指针ha和hb分别指两个单链表的头结点，且头结点的数据域中存放链表的长度，试写一算法将两个链表连拉在一起，即令其中一个

7、表的首元结点连在另一表最后一个结点之后，hc指向连接后的链表的头结点，并要求算法以尽可能短的时间内完成运算。LinkListLink(LinkListL1,LinkListL2){//将两个单链表连接在一起ListNode*p,*q;p=L1;q=L2;while(p->next)p=p->next;//查找终端结点p->next=q->next;//将L2的开始结点链接在L1之后returnL1;}本算法的主要操作时间花费在查找L1的终端结点上，与L2的长度无关。10.ABA11.可能的出站顺序是：1432、1243、1234、2341、2431、

8、3421、432112.P2213.P271214.用选择题3的结果按(n+r-f+1)%n计算（1）9（2