南京工业大学数据结构作业答案
作业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;
if (x>0&&x<30)printf(“x=%d,y=%d”,x,y);
else printf(“输入数据错！”);
试写出当x 分别为18，8时的执行结果。
答：运行结果为：x=18，y=36
x=8，y=运行前的值， 且从x ＝30开始为数据错
3．分析下面各程序段的时间复杂度
作业2
（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,%ld\n”,n,y); }
答：运行结果为： 5，120 此题为递归运算
2. s=0;
for i=0; i for(j=0; j ） 1. for (i=0; i for (j=0; j A[i][j]=0; 答：O （m*n ） 3. x=0; for(i=1; i for (j=1; j<=n-i; j++) x++; 解：因为x++共执行了n-1+n-2+ (1) n(n-1)/2，所以执行时间为O （n 2 ） 4. i=1; while(i<=n) i=i*3; 答：O （log 3n ） 1. 【严题集②】试比较顺序存储结构和链式存储结构的优缺点。在什么情况下用顺序表比 链表好 答：①顺序存储时，相邻数据元素的存放地址也相邻（逻辑与物理统一）；要求内存中可用存储单元的地 址必须是连续的。 优点：存储密度大（＝1），存储空间利用率高。缺点：插入或删除元素时不方便。 ②链式存储时，相邻数据元素可随意存放，但所占存储空间分两部分，一部分存放结点值，另一部分 存放表示结点间关系的指针 优点：插入或删除元素时很方便，使用灵活。缺点：存储密度小（<1），存储空间利用率低。 顺序表适宜于做查找这样的静态操作；链表宜于做插入、删除这样的动态操作。 若线性表的长度变化不大，且其主要操作是查找，则采用顺序表； 若线性表的长度变化较大，且其主要操作是插入、删除操作，则采用链表。 2 .【严题集①】描述以下三个概念的区别：头指针、头结点、首元结点（第一个元素结点）。 在单链表中设置头结点的作用是什么 答：首元结点是指链表中存储线性表中第一个数据元素a1的结点。为了操作方便，通常在链表的首元 结点之前附设一个结点，称为头结点，该结点的数据域中不存储线性表的数据元素，其作用是为了对链表 进行操作时，可以对空表、非空表的情况以及对首元结点进行统一处理。头指针是指向链表中第一个结点 （或为头结点或为首元结点）的指针。若链表中附设头结点，则不管线性表是否为空表，头指针均不为空。 否则表示空表的链表的头指针为空。这三个概念对单链表、双向链表和循环链表均适用。是否设置头结点， 是不同的存储结构表示同一逻辑结构的问题。 头结点 ? 头指针首元结点 简而言之， 头指针是指向链表中第一个结点（或为头结点或为首元结点）的指针； 头结点是在链表的首元结点之前附设的一个结点；数据域内只放空表标志和表长等信息（内放头指针那还得另配一个头指针！！！） 首元素结点是指链表中存储线性表中第一个数据元素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("/ninput an integer [stop 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; /*统计链表结点的个数并打印出来*/ while (p->link!=NULL) {printf("%d",p->data); p=p->link; i++; } printf("\n node number=%d\n", i-1); /*结点的个数不包括-9999*/ } 作业3 1.假设正读和反读都相同的字符序列为“回文”，例如，‘abba’和‘abcba’是回文，‘abcde’和‘ababab’则不是回文。假设一字符序列已存入计算机，请分析用线性表、堆栈和队列等方式正确输出其回文的可能性 答：线性表是随机存储，可以实现，靠循环变量（j--）从表尾开始打印输出； 堆栈是后进先出，也可以实现，靠正序入栈、逆序出栈即可； 队列是先进先出，不易实现。 哪种方式最好，要具体情况具体分析。若正文在机内已是顺序存储，则直接用线性表从后往前读取即可，或将堆栈栈顶开到数组末尾，然后直接用POP动作实现。（但堆栈是先减后压还是……） 若正文是单链表形式存储，则等同于队列，需开辅助空间，可以从链首开始入栈，全部压入后再依次输出。 2. 顺序队的“假溢出”是怎样产生的如何知道循环队列是空还是满 答：一般的一维数组队列的尾指针已经到了数组的上界，不能再有入队操作，但其实数组中还有空位置，这就叫“假溢出”。 采用循环队列是解决假溢出的途径。 另外，解决队满队空的办法有三： ①设置一个布尔变量以区别队满还是队空； ②浪费一个元素的空间，用于区别队满还是队空。 ③使用一个计数器记录队列中元素个数（即队列长度）。 我们常采用法②，即队头指针、队尾指针中有一个指向实元素，而另一个指向空闲元素。 判断循环队列队空标志是： f=rear 队满标志是：f=(r+1)%N 3.设循环队列的容量为40（序号从0到39），现经过一系列的入队和出队运算后，有 ① front=11，rear=19; ② front=19，rear=11；问在这两种情况下，循环队列中各有元素多少个 答：用队列长度计算公式： (N＋r－f)% N ① L=（40＋19－11）% 40=8 ② L=（40＋11－19）% 40=32 4. 试写一个算法判别读入的一个以‘@’为结束符的字符序列是否是“回文”。 答：编程如下： int Palindrome_Test()设如下图所示的二叉树B的存储结构为二叉链表，root为根指针，结点结构为：（lchild,data,rchild）。其中lchild，rchild分别为指向左右孩子的指针，data为字符型，root为根指针，试回答下列问题： (1).对下列二叉树B，执行下列算法traversal(root)，试指出其输出结果； C的结点类型定义如下： struct node {char 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 解：这是“先根再左再根再右”，比前序遍历多打印各结点一次，输出结果为：A B C C E E B A D F F D G G 特点：①每个结点肯定都会被打印两次；②但出现的顺序不同，其规律是：凡是有左子树的结点，必间隔左子树的全部结点后再重复出现；如A ，B ，D 等结点。反之马上就会重复出现。如C ，E ，F ，G 等结点。 时间复杂度以访问结点的次数为主，精确值为2*n ，时间渐近度为O(n). 2. 试写出如图所示的二叉树分别按先序、中序、后序遍历时得到的结点序列。 答：DLR ：A B D F J G K C E H I L M LDR: B F J D G K A C H E L I M LRD ：J F K G D B H L M I E C A 3.把如图所示的树转化成二叉树。 答：注意全部兄弟之间都要连线（包括度为2的兄弟）,并注意原有连线结点一律归入左子树，新添连线结点一律归入右子树。 A B E C K F H D L G I M J 4.画出和下列二叉树相应的森林。 A B D C F G E 答：注意根右边的子树肯定是森林， 而孩子结点的右子树均为兄弟。 5.编写按层次顺序（同一层自左至右）遍历二叉树的算法 (或:按层次输出二叉树中所有结点) 。 解：思路：既然要求从上到下，从左到右，则利用队列存放各子树结点的指针是个好办法。 这是一个循环算法，用while语句不断循环，直到队空之后自然退出该函数。 技巧之处：当根结点入队后，会自然使得左、右孩子结点入队，而左孩子出队时又会立即使 得它的左右孩子结点入队，……以此产生了按层次输出的效果。 法一： level(liuyu*T) /* liuyu *T,*p,*q[100]; 假设max已知*/ {int f,r; f=0; r=0; /*置空队*/ r=(r+1)%max; q[r]=T; /*根结点进队*/ while(f!=r) /*队列不空*/ {f=(f+1%max); p=q[f]; /*出队*/ printf("%d",p->data); /*打印根结点*/ if(p->lchild){r=(r+1)%max; q[r]=p->lchild;} /*若左子树不空，则左子树进队*/ if(p->rchild){r=(r+1)%max; q[r]=p->rchild;} /*若右子树不空，则右子树进队*/ } return(0); } 法二：层序遍历二叉树的递归算法 void LayerOrder(Bitree T) 知如图所示的有向图，请给出该图的: （1）每个顶点的入/出度； （2）邻接矩阵； （3）邻接表； （4）逆邻接表。 答案： 2.请对下图的无向带权图： （1）写出它的邻接矩阵，并按普里姆算法求其最小生成树； （2）写出它的邻接表，并按克鲁斯卡尔算法求其最小生成树。 最小生成树： 3.已知二维数组表示的图的邻接矩阵如下图所示。试分别画出自顶点1出发进行遍历所得的深度优先生成树和广度优先生成树。 4. 试 基 于图的深度优先搜索策略写一算法，判别以邻接表方式存储的有向图中是否存在由顶点v i 到顶点v j的路径（i≠j）。注意：算法中涉及的图的基本操作必须在此存储结构上实现。int visited[MAXSIZE]; irstarc;p;p=p->nextarc) { k=p->adjvex; if(!visited[k]&&exist_path(k,j)) return 1;假定对有序表：（3，4，5，7，24，30，42，54，63，72，87，95）进行折半查找，试回答下列问题： （1）画出描述折半查找过程的判定树； （2）若查找元素54，需依次与哪些元素比较 （3）若查找元素90，需依次与哪些元素比较 （4）假定每个元素的查找概率相等，求查找成功时的平均查找长度。 解： （1）先画出判定树如下（注：mid=?(1+12)/2?=6）： 30 5 63 3 7 42 87 4 24 54 72 95 (2) 查找元素54，需依次与30, 63, 42, 54 等元素比较； (3) 查找元素90，需依次与30, 63,87, 95, 72等元素比较； （4）求ASL之前，需要统计每个元素的查找次数。判定树的前3层共查找1＋2×2＋4×3=17次； 但最后一层未满，不能用8×4，只能用5×4=20次， 所以ASL＝1/12（17＋20）＝37/12≈ 2.设哈希（Hash）表的地址范围为0～17，哈希函数为：H（K）＝K MOD 16。 K为关键字，用线性探测法再散列法处理冲突，输入关键字序列： （10，24，32，17，31，30，46，47，40，63，49） 造出Hash表，试回答下列问题： （1）画出哈希表的示意图； （2）若查找关键字63，需要依次与哪些关键字进行比较 （3）若查找关键字60，需要依次与哪些关键字比较 （4）假定每个关键字的查找概率相等，求查找成功时的平均查找长度。 解：（1）画表如下： 然后顺移，与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＋3×3）＝17/11=≈ 3.在一棵空的二叉查找树中依次插入关键字序列为12，7，17，11，16，2，13，9，21，4， 请画出所得到的二叉查找树。 答： 12 7 17 2 11 16 21 4 9 13 验算方法：用中序遍历应得到排序结果： 2,4,7,9,11,12,13,16,17，21 4.试写一个判别给定二叉树是否为二叉排序树的算法，设此二叉树以二叉链表作存储结构。且树中结点的关键字均不同。 解：注意仔细研究二叉排序树的定义。易犯的典型错误是按下述思路进行判别：“若一棵非空的二叉树其左、右子树均为二叉排序树，且左子树的根的值小于根结点的值，又根结点的值不大于右子树的根的值，则是二叉排序树” （刘注：即不能只判断左右孩子的情况，还要判断左右孩子与双亲甚至根结点的比值也要遵循（左小右大）原则）。 若要采用递归算法，建议您采用如下的函数首部： 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，27, 35, 47, 68, 84，问采用的是什么排序方法 答：用的是快速排序方法。注意每一趟要振荡完全部元素才算一个中间结果。 2.对于整数序列100，99，98，…3，2，1，如果将它完全倒过来，分别用冒泡排序和快速排序法，它们的比较次数和交换次数各是多少 答：冒泡排序的比较和交换次数将最大，都是1+2+…+n-1=n(n-1)/2＝50×99=4545次 快速排序则看按什么数据来分子表。 如果按100来分，则很惨，也会是n(n-1)/2！ 若按中间数据50或51来分表，则： 第1轮能确定1个元素，即在1个子表中比较和交换了n－1个元素；n－（21-1） 第2轮能再确定2个元素，即在2个子表中比较和交换了n－3个元素；n－（22-1） 第3轮能再确定4个元素，即在4个子表中比较和交换了n－7个元素；n－（23-1） 第4轮能再确定8个元素，即在8个子表中比较和交换了n－15个元素；n－（24-1）…… 第6轮能再确定32个元素，即在32个子表中比较和交换了n－65个元素；n－（26-1） 第7轮则能全部确定，（因为27=128），在100个子表中比较和交换了n－（100－1）个元素； 比较和交换总次数为：7n－(21－1＋22－1＋23－1……＋26－1＋100－1) ＝7n+7－(1＋2＋4＋……＋64+100)=7n－(8+16+32+164)=700-220=480次 若从中间选择初始元素，则ASL=（n+1）log2n－(21＋22＋23+……＋2m)= nlog2n+log2n－(21＋22＋23+……＋n)≈O（nlog2n） 3.以关键字序列（256，301，751，129，937，863，742，694，076，438）为例，分别写出执行以下算法的各趟排序结束时，关键字序列的状态，并说明这些排序方法中，哪些易于在链表（包括各种单、双、循环链表）上实现 ①直接插入排序②希尔排序③冒泡排序④快速排序 ⑤直接选择排序⑥堆排序⑦归并排序⑧基数排序（8分）解：先回答第2问：①⑤⑦⑧皆易于在链表上实现。 ①直接插入排序的中间过程如下：②希尔排序的中间过 程如下： ③冒泡排序的中间过程如下：④快速排序的中间 过程如下： ⑤直接选择排序的中间过程如下：⑥堆排序（大根堆） 的中间过程如下： ⑦归并排序排序的中间过程如下： ⑧基数排序的中间过程如下： 4.序列的“中值记录”指的是：如果将此序列排序后，它是第[n/2]个记录。试写一个求中值记录的算法。 typedef struct { int gt; t++; else if(a[j] } mid=0; min_dif=abs(b[0].gt-b[0].lt); for(i=0;i return mid; }//Get_Mid