好文档 - 专业文书写作范文服务资料分享网站

南京工业大学数据结构作业答案(全)

天下 分享 时间: 加入收藏 我要投稿 点赞

作业1

1.数据结构和数据类型两个概念之间有区别吗

答:简单地说,数据结构定义了一组按某些关系结合在一起的数组元素。数据类型不仅定义了一组带结构的数据元素,而且还在其上定义了一组操作。

2.阅读下列C程序段,写出相应的执行结果(每小题4分,共8分) (1)。printf(“Input x”);

scanf(“%d”,&x); if (x<=30) if(x>20) y=x;

else if (x>10) y=2*x;

(2)。long int fact(n)

int n; {long f;

if(n>1)f=n*fact(n-1); else f=1;

if (x>0&&x<30)printf(“x=%d,y=%d”,x,y); return(f);

else printf(“输入数据错!”);

} main() {int n; long y; n=5;

试写出当x分别为18,8时的执行结果。

答:运行结果为:x=18,y=36

x=8,y=运行前的值, 且从x=30开始为数据错

y=fact(n);

printf(“%d,%ld\\n”,n,y); }

3.分析下面各程序段的时间复杂度

1. for (i=0; i

for(i=1; i

for (j=0; j

A[i][j]=0;

3. x=0;

2. s=0;

for i=0; i

for(j=0; j

作业2

1. 【严题集②】试比较顺序存储结构和链式存储结构的优缺点。在什么情况下用顺序表比链表好

答:① 顺序存储时,相邻数据元素的存放地址也相邻(逻辑与物理统一);要求内存中可用存储单元的地址必须是连续的。

优点:存储密度大(=1),存储空间利用率高。缺点:插入或删除元素时不方便。

②链式存储时,相邻数据元素可随意存放,但所占存储空间分两部分,一部分存放结点值,另一部分存放表示结点间关系的指针

优点:插入或删除元素时很方便,使用灵活。缺点:存储密度小(<1),存储空间利用率低。 顺序表适宜于做查找这样的静态操作;链表宜于做插入、删除这样的动态操作。 若线性表的长度变化不大,且其主要操作是查找,则采用顺序表;

若线性表的长度变化较大,且其主要操作是插入、删除操作,则采用链表。

4. i=1; while(i<=n) i=i*3;

2 .【严题集①】描述以下三个概念的区别:头指针、头结点、首元结点(第一个元素结点)。在单链表中设置头结点的作用是什么

答:首元结点是指链表中存储线性表中第一个数据元素a1的结点。为了操作方便,通常在链表的首元结点之前附设一个结点,称为头结点,该结点的数据域中不存储线性表的数据元素,其作用是为了对链表进行操作时,可以对空表、非空表的情况以及对首元结点进行统一处理。头指针是指向链表中第一个结点(或为头结点或为首元结点)的指针。若链表中附设头结点,则不管线性表是否为空表,头指针均不为空。否则表示空表的链表的头指针为空。这三个概念对单链表、双向链表和循环链表均适用。是否设置头结点,是不同的存储结构表示同一逻辑结构的问题。

头结点

head data link 头指针 首元结点

简而言之,

头指针是指向链表中第一个结点(或为头结点或为首元结点)的指针;

头结点是在链表的首元结点之前附设的一个结点;数据域内只放空表标志和表长等信息(内放头指针那还得另配一个头指针!!!)

首元素结点是指链表中存储线性表中第一个数据元素a1的结点。

3. 已知P结点是双向链表的中间结点,试从下列提供的答案中选择合适的语句

序列。

a.在P结点后插入S结点的语句序列是-----------。 b.在P结点前插入S结点的语句序列是-----------。 c.删除P结点的直接后继结点的语句序列是----------。 d.删除P结点的直接前驱结点的语句序列是----------。 e.删除P结点的语句序列是------------。

(1)P->next=P->next->next; (10) P->prior->next=P; (2)P->prior=P->prior->prior; (11) P->next->prior =P; (3) P->next=S; (12)P->next->prior=S; (4) P->prior=S; (13) P->prior->next=S; (5)S->next=P; (14) P->next->prior=P->prior (6)S->prior=P; (15)Q=P->next;

(7) S->next= P->next; (16)Q= P->prior; (8) S->prior= P->prior; (17)free(P); (9) P->prior->next=p->next; (18)free(Q); 解答:

a.(12)(7)(3)(6) 3必须在12和7的后面,其余的顺序可变 b.(13)(8)(4)(5) 同上

c.(15)(1)(11)(18) 不可变 d.(16)(2)(10)(18) 不可变 e.(9)(14)(17)

4. 编写程序,将若干整数从键盘输入,以单链表形式存储起来,然后计算单链表中结点的

个数(其中指针P指向该链表的第一个结点)。 注:统计结点个数是【省统考样题】的要求,也是教材P60 4-6计算链表长度的要求,编程又简单,很容易作为考题。 解:编写C程序如下(已上机通过): 全局变量及函数提前说明:

--------------------------------- #include<> #include<>

typedef struct liuyu{int data;struct liuyu*link;}test; liuyu *p,*q,*r,*head; int m=sizeof(test);

void main () /*第一步,从键盘输入整数,不断添加到链表*/ {int i;

head=(test*)malloc(m); /*m=sizeof(test);*/ p=head; i=0; while (i!=-9999)

{ printf(\ [stop by '-9999']:\ scanf(\

p->data=i; /* input data is saved */ p->link=(test*)malloc(m); /*m=sizeof(test));*/ q=p; p=p->link;

}

q->link=NULL; /*原先用p->link=NULL似乎太晚!*/

p=head; i=0; /*统计链表结点的个数并打印出来*/ while (p->link!=NULL) {printf(\ p=p->link; i++; }

printf(\ i-1); /*结点的个数不包括-9999*/ } 作业3

1.假设正读和反读都相同的字符序列为“回文”,例如,‘abba’和‘abcba’是回文,‘abcde’ 和‘ababab’则不是回文。假设一字符序列已存入计算机,请分析用线性表、堆栈和队列等方式正确输出其回文的可能性

答:线性表是随机存储,可以实现,靠循环变量(j--)从表尾开始打印输出;

堆栈是后进先出,也可以实现,靠正序入栈、逆序出栈即可; 队列是先进先出,不易实现。

哪种方式最好,要具体情况具体分析。若正文在机内已是顺序存储,则直接用线性表从后往前读取即可,或将堆栈栈顶开到数组末尾,然后直接用POP动作实现。(但堆栈是先减后压还是……)

若正文是单链表形式存储,则等同于队列,需开辅助空间,可以从链首开始入栈,全部压入后再依次输出。

2. 顺序队的“假溢出”是怎样产生的如何知道循环队列是空还是满

答:一般的一维数组队列的尾指针已经到了数组的上界,不能再有入队操作,但其实数组中还有空位置,这就叫“假溢出”。

南京工业大学数据结构作业答案(全)

作业11.数据结构和数据类型两个概念之间有区别吗答:简单地说,数据结构定义了一组按某些关系结合在一起的数组元素。数据类型不仅定义了一组带结构的数据元素,而且还在其上定义了一组操作。2.阅读下列C程序段,写出相应的执行结果(每小题4分,共8分)(1)。printf(“Inputx”);scanf(“%d”,&x);if
推荐度:
点击下载文档文档为doc格式
2psec5pggj8jj329nz0t2wkqq4mj6h00m2v
领取福利

微信扫码领取福利

微信扫码分享