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

1、作业11. 数据结构和数据类型两个概念之间有区别吗答：简单地说，数据结构定义了一组按某些关系结合在一起的数组元素。数据类型不仅定义了一组带结构的数据元素，而且还在其上定义了一组操作。2阅读下列C程序段，写出相应的执行结果（每小题(1 )。printf( “ In put x ”)；scanf( “ %d，&x);if (x<=30)if(x>20) y=x;else if (x>10) y=2*x;if (x>0&&x<30)printf(“x=%d,y=%d ,x,y);else printf("输入数据错！” );试写出当x分

2、别为18，8时的执行结果。答：运行结果为：x=18, y=36x=8 , y=运行前的值，且从x = 30开始为数据错4分，共8分)(2)。 long int fact(n)int n;long f;if(n >1)f= n*fact( n-1);else f=1;return(f);main ()int n;long y;n=5;y=fact( n);printf( “%d,% n” ,n,y);答：运行结果为：5，120此题为递归运算2. s=0;for i=0; i<n; i+) for(j=0; j< n; j+) s+=Bij;sum=s;2答：O(n)4. i=1

3、;while(i<=n)i=i*3;答：O (log 3in)3.分析下面各程序段的时间复杂度1. for (i=0; i<n; i+)for (j=0; j<m; j+)Aij=0;答：0( m*n)3. x=0;for(i=1; i<n; i+)for (j=1; j<=n-i; j+)x+;解：因为x+共执行了 n-1+ n-2+ +1 =n(n-1)/2，所以执行时间为O (n2)"J H "Jf.( IT 1)作业21.【严题集】试比较顺序存储结构和链式存储结构的优缺点。在什么情况下用顺序表比 链表好答： 顺序存储时，相邻数据元素的存

4、放地址也相邻（逻辑与物理统一）；要求内存中可用存储单元的地址必须是连续的。优点：存储密度大（=1）,存储空间利用率高。缺点：插入或删除元素时不方便。链式存储时，相邻数据元素可随意存放，但所占存储空间分两部分，一部分存放结点值，另一部分 存放表示结点间关系的指针优点：插入或删除元素时很方便，使用灵活。缺点：存储密度小（<1），存储空间利用率低。顺序表适宜于做查找这样的静态操作；链表宜于做插入、删除这样的动态操作。若线性表的长度变化不大，且其主要操作是查找，则采用顺序表；若线性表的长度变化较大，且其主要操作是插入、删除操作，则采用链表。2 【严题集】描述以下三个概念的区别：头指针、头结点、首

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

6、头指针首元结点简而言之，头指针是指向链表中第一个结点（或为头结点或为首元结点）的指针；头结点是在链表的首元结点之前附设的一个结点；数据域内只放空表标志和表长等信息（内放头指针 那还得另配一个头指针！ ！）首元素结点是指链表中存储线性表中第一个数据元素ai的结点。3.已知P结点是双向链表的中间结点，试从下列提供的答案中选择合适的语句序列。a 在P结点后插入S结点的语句序列是 b .在P结点前插入S结点的语句序列是 c .删除P结点的直接后继结点的语句序列是 d .删除P结点的直接前驱结点的语句序列是 e .删除P结点的语句序列是 。(1) P->n ext=P->n ext- >

7、;n ext;(2) P->prior=P->prior->prior; P-> next=S;(4) P->prior=S;(5) S-> next=P;(6) S->prior=P;(10) P->prior-> next=P;(11) P-> next->prior =P;(12) P-> next->prior=S;(13) P->prior- >n ext=S;(14) P->n ext->prior=P->prior(15) Q=P-> next;(7) S->

8、next= P-> next;(8) S->prior= P->prior;(16) Q= P->prior;(17) free(P);(9) P->prior->next=p->next;(18)free(Q);解答：a.（12）（7）（3）（6) 3必须在b.（13）（8）（4）（5）同上c.（15）（1）（11）（18）不可变d.（16）（2）（10）（18）不可变e.（9）（14)（17）12和 7 的后面，其余的顺序可变4. 编写程序，将若干整数从键盘输入，以单链表形式存储起来，然后计算单链表中结点的 个数（其中指针 P 指向该链表的第一个结

9、点） 。 注：统计结点个数是【省统考样题】的要 求，也是教材 P60 4-6 计算链表长度的要求，编程又简单，很容易作为考题。解：编写C程序如下（已上机通过）：全局变量及函数提前说明：#include<>#include<>typedef struct liuyuint 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);*

10、/p=head; i=0;while (i!=-9999) printf("/ninput an integerstop by '-9999':");scanf("%d",&i);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; /* 统计链表结点

11、的个数并打印出来 */ while (p->link!=NULL)printf("%d",p->data); p=p->link;i+;printf("n node number=%dn", i-1 ); /* 结点的个数不包括 -9999*/ 作业 31. 假设正读和反读都相同的字符序列为 “回文”，例如， abba '和 abcba '是回文， abcde ' 和 ababab'则不是回文。假设一字符序列已存入计算机，请分析用线性表、堆栈和队列 等方式正确输出其回文的可能性 答：线性表是随机存储，可以

12、实现，靠循环变量(j- )从表尾开始打印输出；堆栈是后进先出，也可以实现，靠正序入栈、逆序出栈即可； 队列是先进先出，不易实现。哪种方式最好， 要具体情况具体分析。 若正文在机内已是顺序存储， 则直接用线性表从 后往前读取即可，或将堆栈栈顶开到数组末尾，然后直接用POP动作实现。(但堆栈是先减后压还是) 若正文是单链表形式存储，则等同于队列，需开辅助空间，可以从链首开始入栈，全部压入后再依次输出。2. 顺序队的“假溢出”是怎样产生的如何知道循环队列是空还是满 答：一般的一维数组队列的尾指针已经到了数组的上界，不能再有入队操作，但其实数组中还有空位置， 这就叫“假溢出” 。采用循环队列是解决假溢

13、出的途径。 另外，解决队满队空的办法有三： 设置一个布尔变量以区别队满还是队空； 浪费一个元素的空间，用于区别队满还是队空。 使用一个计数器记录队列中元素个数(即队列长度) 。我们常采用法，即队头指针、队尾指针中有一个指向实元素，而另一个指向空闲元素。 判断循环队列队空标志是： f=rear 队满标志是： f=(r+1)%N3. 设循环队列的容量为 40(序号从 0到39)，现经过一系列的入队和出队运算后，有 front=11 ， rear=19; front=19 ， rear=11 ；问在这两种情况下，循环队列中各有 元素多少个 答：用 队列长度计算公式： (N rf)% N L= (40

14、1911) % 40=8 L= (401119) % 40=324. 试写一个算法判别读入的一个以'为结束符的字符序列是否是“回文” 。答：编程如下：int Palindrome_Test() 设如下图所示的二叉树 B 的存储结构为二叉链表， root 为根指针， 结点结构为： ( lchild,data,rchild )。其中 lchild ， rchild 分别为指向左右孩子的指针， data 为字符型， root 为根指针，试回答下列问题：(1) .对下列二叉树 B,执行下列算法traversal(root)，试指出其输出结果；C的结点类型定义如下：struct nodechar

15、 data;struct node * lchild, rchild;C算法如下：void traversal(struct node *root)if (root)printf( “%c”, root ->data);traversal(root->lchild);printf( “ %c , root ->data);traversal(root->rchild);(2) .假定二叉树B共有n个结点，试分析算法 traversal(root)的时间复杂度。二叉树B解：这是“先根再左再根再右”，比前序遍历多打印各结点一次，输出结果为:B A D FF DG G特点：每

16、个结点肯定都会被打印两次； 但出现的顺序不同，其规律是： 凡是有左子树的 结点，必间隔左子树的全部结点后再重复出现； 如A, B, D等结点。反之马上就会重复出现。 如C, E，F，G等结点。时间复杂度以访问结点的次数为主，精确值为2*n，时间渐近度为0(n).2. 试写出如图所示的二叉树分别按先序、中序、后序遍历时得到的结点序列。答: DLR A B D F J G K C E H I L MLDR: B F J D G K A C H E L I MLRD J F K G D B H L M I E C A3. 把如图所示的树转化成二叉树。M J答：注意全部兄弟之间都要连线 (包 括度为2

17、的兄弟)，并注意原有连线 结点一律归入左子树，新添连线结 点一律归入右子树。4. 画出和下列二叉树相应的森林。答：注意根右边的子树肯定是森林， 而孩子结点的右子树均为兄弟。5. 编写按层次顺序(同一层自左至右)遍历二叉树的算法(或：按层次输出二叉树中所有结点)。解：思路：既然要求从上到下，从左到右，则利用队列存放各子树结点的指针是个好办法。这是一个循环算法，用 while语句不断循环，直到队空之后自然退出该函数。技巧之处：当根结点入队后，会自然使得左、右孩子结点入队，而左孩子出队时又会立即使得它的左右孩子结点入队，以此产生了按层次输出的效果。法一：if(p->lchild)r=(r+1)

18、%max; qr=p->lchild; if(p->rchild)r=(r+1)%max; qr=p->rchild; /*若左子树不空，则左子树进队*/*若右子树不空，则右子树进队*/return(O);法二：层序遍历二叉树的递归算法void LayerOrder(Bitree T)知如图所示的有向图，请给出该图的(1) 每个顶点的入/出度；(2) 邻接矩阵；(3) 邻接表；4) 逆邻接表。level(liuyu*T)/* liuyu *T,*p,*q1OO;假设max已知*/int f,r;f=0; r=0;/*置空队*/r=(r+1)%max;qr=T;/*根结点进队*

19、/while(f!=r)/*队列不空*/f=(f+1%max);p=qf;/*出队*/prin tf("%d",p->data);/*打印根结点*/答案:7. I 邻播砸眸nt*12345flAFT32I1 i220Zz31g裁接表1:<5A二 rftT4*r* 1 rnrplEGMlia21逆邻接盏2.请对下图的无向带权图：(1 )写出它的邻接矩阵，并按普里姆算法求其最小生成树；(2) 写出它的邻接表，并按克鲁斯卡尔算法求其最小生成树。最小生成树:3.已知二维数组表示的图的邻接矩阵如下图所示。试分别画出自顶点1出发进行遍历所得的深度优先生成树和广度优先生成树。

20、探度优先生成树广席比先生處树基于图的深度优先搜索策略写一算法，判别以邻接表方式存储的有向图中是否存在由顶点Vi到顶点Vj的路径(i工j )。注意：算法中涉及的图的基本操作必须在此存储结构上实现。int visitedMAXSIZE; irstarc;p;p=p->nextarc)k=p->adjvex;if(!visitedk&&exist_path(k,j) return 1;假定对有序表：(3, 4, 5, 7, 24,30, 42, 54, 63, 72, 87, 95)进行折半查找，试回答下列问题：(1) 画出描述折半查找过程的判定树；(2) 若查找元素54

21、,需依次与哪些元素比较(3) 若查找元素90,需依次与哪些元素比较(4) 假定每个元素的查找概率相等，求查找成功时的平均查找长度。解：(2) 查找元素 54,需依次与 30, 63, 42, 54 等元素比较；(3) 查找元素 90,需依次与 30, 63,87, 95, 72等元素比较；(4) 求ASL之前，需要统计每个元素的查找次数。判定树的前3层共查找1 + 2 X 2+ 4 X3=17 次；但最后一层未满，不能用 8X 4,只能用5 X 4=20次，所以 ASL= 1/12 (17 + 20)= 37/12 2. 设哈希(Hash)表的地址范围为 017,哈希函数为：H ( K)= K

22、 MOD 16。 K为关键字，用线性探测法再散列法处理冲突，输入关键字序列：(10, 24, 32, 17, 31, 30, 46, 47, 40, 63, 49)造出Hash表，试回答下列问题：(1) 画出哈希表的示意图；(2) 若查找关键字63,需要依次与哪些关键字进行比较(3) 若查找关键字60,需要依次与哪些关键字比较(4) 假定每个关键字的查找概率相等，求查找成功时的平均查找长度。解：(1)画表如下:012345678910111213141516173217634924401030314647(2) 查找63,首先要与 H(63)=63%16=15号单元内容比较，即63 vs 31

23、 ,no;然后顺移，与46,47,32,17,63相比，一共比较了 6次！(3) 查找60,首先要与H(60)=60%16=12号单元内容比较，但因为12号单元为空(应当有 空标记)，所以应当只比较这一次即可。(4) 对于黑色数据元素，各比较 1次；共6次；对红色元素则各不相同，要统计移位的位数。“63”需要6次，“49”需要3次，“40”需要2次，“ 46”需要3次，“ 47”需要3次，所以 ASL=1/11 ( 6+ 2 + 3X 3)= 17/11= 3.在一棵空的二叉查找树中依次插入关键字序列为12, 7, 17, 11, 16, 2, 13, 9, 21, 4,请画出所得到的二叉查找

24、树。答：12 / 、717 、2 11 16 21 /4 913验算方法：用中序遍历应得到排序结果：2,4,7,9,11,12,13,16,17, 214.试写一个判别给定二叉树是否为二叉排序树的算法，设此二叉树以二叉链表作存储结 构。且树中结点的关键字均不同。解：注意仔细研究二叉排序树的定义。易犯的典型错误是按下述思路进行判别：“若一棵非空的二叉树其左、右子树均为二叉排序树，且左子树的根的值小于根结点的值，又根结点 的值不大于右子树的根的值，则是二叉排序树”(刘注：即不能只判断左右孩子的情况，还要判断左右孩子与双亲甚至根结点的比值也要 遵循(左小右大)原则)。若要采用递归算法，建议您采用如下

25、的函数首部：bool BisortTree(BiTree T, BiTree&PRE)，其中PRE为指向当前访问结点的前驱的指针。(或者直接存储前驱的数值，随时与当前根结点比较)一个漂亮的算法设计如下：int last=0 , flag=1 ;用某种排序方法对线性表(25, 84,21,47,15,27,68,35,20)进行排序时，元素序列的变化情况如下：25, 84 , 21,47,15,27,68,35,20 宀 20, 15, 21,25, 47, 27,68,35, 84 宀 15, 20, 21,25, 35, 27, 47, 68, 84 宀15, 20, 21,25,

26、27, 35, 47, 68, 84,问采用的是什么排序方法答：用的是快速排序方法。注意每一趟要振荡完全部元素才算一个中间结果。2.对于整数序列 100, 99, 98,3, 2, 1,排序法，它们的比较次数和交换次数各是多少 答：冒泡排序的比较和交换次数将最大，都是 快速排序则看按什么数据来分子表。如果按100来分，则很惨，也会是n(n-1)/2若按中间数据50或51来分表，则： 第1轮能确定1个元素，即在1个子表中比较和交换了 第2轮能再确定 第3轮能再确定 第4轮能再确定2个元素,4个元素,8个元素,即在即在即在32个元素，即在如果将它完全倒过来，分别用冒泡排序和快速1+2+n-1= n

27、(n-1)/2= 50 X 99=4545 次2个子表中比较和交换了4个子表中比较和交换了8个子表中比较和交换了1n 1 个元素；n ( 2-1 ) n 3个元素； n 7个元素； n 15个元素；32个子表中比较和交换了2n( 2 -1 )3n( 2 -1 )n ( 24-1 )n 65 个元素；n ( 26-1 )n( 100 1)个元第6轮能再确定第7轮则能全部确定，(因为27=128), 在100个子表中比较和交换了素；比较和交换总次数为：7n (21 1 + 22 1 + 23 1 + 26 1 + 100 1) = 7n+7 (1 + 2 + 4+ + 64+100)=7n (8+

28、16+32+164)=700-220= 480 次若从中间选择初始元素，则ASL= (n+1) log 2n (2 1 + 22+ 23+ + 2m)= nlog 2n+log 2n (2123+ 2 + 2 +n) 0(nlog 2n)3.以关键字序列(256, 301, 751, 129, 937, 863, 742, 694, 076, 438)为例，分别写出执行以下算法的各趟排序结束时，关键字序列的状态，并说明这 些排序方法中，哪些易于在链表(包括各种单、双、循环链表)上实现直接插入排序希尔排序冒泡排序 快速排序 直接选择排序堆排序归并排序基数排序(8分)解：先回答第2问：皆易于在链表

29、上实现。 直接插入排序的中间过程如下： 希尔排序的中间过程如下：第一趟：(256,301,75T119,937,)163.742,«Mrg76T43R 笫二越;(256,301,751 )329,937-86.742.076,438 第三榭？( 129,25伉301931. B63.742*694.076,43® 第四趙；(129.250JDL751.937),863,7+2,fi94,07fi.43B第六題；(»29T256,n0I1742T75bS63,W).W.(Wb,43S 第七施:(129*256.30! .6M.742.75LM ,9?7)4.W弟八趙

30、：(076.129,256,301 694.742,751 ,«63.937>,43«黑九趙：(076.129,156.301.418,*)94.742.751,937)(2)希东押序(収也=汕以。第一越：256.301,694,076.438,863J42.751J29.93j第二垮；076,3()1,129,256,43S76M4, 742,751笫三076J29.256.301,43«,6W.742,751 ,SfWR9T冒泡排序的中间过程如下： 过程如下：256t3OL 731J2, 937 h 863.742,694,076,43S 節256.30

31、lJ29.75K«63,742.6W.O76,438,937 那二fiS； 256j29.30L73L742,fiW,C76,43fl,S63,937 第三尊；129.25.301,742.6,07.438,751,.937 第四趟：i29t256T30i.W.076,4.742.751*863,937 第五趣；12/6,561,0亦4徹妙存42*為1.%3詡37 12,256,076.301,4 旳4# ML 7九敘玄滋7 笫七 M： 129,076,256.301,438,694,742.751.863,537 JBAiSi (176?»29.256,30*,458的4

32、,了4Z751 *胎人93? 第九垮：厲129*230匚4鬪.刚彳斗乙7頁.跡3好7 直接选择排序的中间过程如下： 的中间过程如下：快速排序的中间256,301,751.129,997,»63,?42 明.旳6£38(OWJ29),256X75l.<n7*863,742.«i>MIT4 第二超；076.12Q,25*>t(O .301 ,94,7+2751 (8W朋7 第三制；076J29.256,301,438.(034,742),751.(865,937 第PU趙；076.129,256,301+4M.W.742.75l,(H6337) 第五

33、題：076.1.256,301,438,694,742.751*863,937 堆排序(大根堆)第一趟：(256.34)1 )»751J20.937.742.6SM.O76,43R 第二趙半(256,31)1,751) J29,937.8,742.694.076.438 第三ig： (129.236.301863 J42.6WtO76.43«35期做(!29.256,3015937-742.694.076.438 第1i勒：(滋,25®刚厉J妁脚7)*742,的407队4詔 第六直(12.254,742.75! .863.937).94,076.438 邹七掘I： (129.256,1,604,742.751,863.957).438 第Afg: <076.129.256,301,694.7421751 ,S6J,