《数据结构导论各章节作业.doc》由会员分享，可在线阅读，更多相关《数据结构导论各章节作业.doc（23页珍藏版）》请在三一文库上搜索。
1、章节作业第一章 概论1设计算法在整型数组An中查找值为K的元素，若找到，则输出其位置i(0in-1)，否则输出-1作为标志，并分析算法的时间复杂度。解答 ：Int search （int A ，int n ，int k） int I ；I=0；While （i=n-1）If (Ai！=k) i+；Else break;If (i=n-1) return I ;Else return -1;2写出计算方阵Ann与Bnn乘积Cnn的算法，分析算法的时间复杂度。Void matrixmultiply (int A n ,int Bn,int Cn,int n) int I ,j;For (i=0;i
2、n;i+) For (j=0;jn;j+) cij=0; For (k=0 ;knext; Int m=0;While ( p!=NULL) if (p-data=x) m+;P=p-next;Return m;2试分别以顺序表和带头结点的单链表作存储结构，各写一个实现线性表的就地(即使用尽可能少的附加空间)逆置的算法，在原表的存储空间内将线性表(a1，a2，an)逆置为(an，an-1，a1)。解：顺序表逆置算法如下；Void inverse_sqlist SeqList L int m,n,k;DataType temp;M=0;n=L.length-1;While (mnext;q=p;
3、r=Null;while (p!=NULL) p=p-next;q-next=r;r=q;q=p;Head-next=r;第三章 栈、队列和数组1有一个整数序列，其输入顺序为20，30，90，-10，45，78，试利用栈将其输出序列改变为30，-10，45，90，78，20，试给出该整数序列进栈和出栈的操作步骤。(用push(x)表示x进栈，pop(x)表示x出栈)解答：Push（20），push(30),pop(30),push(90),push(-10),pop(-10),push(45),pop(45),pop(90),push(78),pop(78),pop(20)2设有编号为1，2，
4、3，4的四辆列车，顺序进入一个栈式结构的站台，试写出这四辆列车开出车站的所有可能的顺序。解答：考虑几种情况； 1、1234、1243、1324、1342、1432； 2、2134、2143、2314、2341、2431； 3、3214、3241、3421； 4、4321 但是这里的 4123、4132、4213、4231都不是正解 综上四辆车的出站所有可能所有的顺序有14种。3假设以带头结点的循环链表表示队列，并且只设一个指针指向队列尾结点(注意不设头指针)，试编写相应的初始化队列、入队列和出队列算法。解答： Typedef struct linked_queue DataType data;
5、 Struct linked_queue * next ; LqueueTp; 队列的初始化Void initqueue LqueueTp *rear lqueueTp *p; P=(lqueueTp *)malloc(suzeof(LqueueTp);Rear=p;Rear-next=rear;入队列Void ENQueue(LqueueTp *rear ; DataType x) LqueieTp *p; P=(lqueueTp*)malloc(sizeof(LqueueTp); p-data=x; p-next=rear-bext;rear-next=p;rear=p; 出队列outQu
6、eue (LqueueTp *rear.DataType *x) LqueueTp *h,*p;If (rear=rear-next) error (“队空”)；return 0;Else H=rear-next;P=h-next;*x=p-data;h-next=p-next;if (p=rear)rear=h;free (p)return l;4假设以数组cycquem存放循环队列的元素，同时设变量rear和quelen分别指示循环队列中队列尾元素位置和内含元素的个数。试给出此循环队列的队列满和队列空的条件，并写出相应的入队列和出队列的算法。循环队列的算法如下；Typedef struct
7、 cycqueue DataType datam;Int rear;Int quelen;CycqueueTp;cycqueueTp *cq;入队列 int EnCycQueue (CycqueueTp *cq; DataType x) if (cq-quelen=m)error(“队列满”)；returne 0；Else cq-rear=(cq-rear+1)%m; Cq-datacq-rear=x; Cq-quelen=cq-quelen+1; Return 1; 出对列 Int OutCycQueue(CycqueueTp *cq) if(cq-quelen=0)error (“队列空”
8、)；return 0;Else Cq-quelen=cq-quelen-1;*x=cq-data(cq-rear+m-cq-quelen)%m; Return 1;取队列首元素 DataType GetHead(CycquueTp *cq) DataType x;X=cq-data(cq-rear+m-cq-quelen)%m;Return x;第四章 树和二叉树1算法设计题 (1)以二叉链表作存储结构，试编写求二叉树叶子结点个数的算法。算法描述如下： Typedef struct btnode DataType data; Struct btnode *lchild ,*rchild; *B
9、inTree; Int leafnode_num(BinTree bt) if ( bi=NULL) return 0;Else If (bt-lchild=NULL)&(bt-rchild=NULL) Return 1;Else Return leafnode_num(bt-lchid)+leafnode_num(bt-rchild); (2)设计算法求二叉树的结点的个数。算法设计如下：Typedef struct btnode DataType data; Struct btnode *lchild,*rchild;*BinTree;Int node_num (BinTree bt) if
10、 (bt=NULL) return 0;Else Return node_num(bt-lchild)+node_num(bt-rchild)+1; (3)设计算法按先序次序打印二叉树T中叶子结点的值。算法设计如下：Typedef struct btnode int data; Struct btnode *lchild,*rchild;*BinTree;Void preorder (BinTree bt) if (bt!=NULL) if (bt-lchild=NULL)&(bt-rchild=NULL) Printf(“%d”,bt-data); Preorder(bt-lchild);
11、Preorder(bt-rchild);2树的存储结构采用孩子兄弟链表，试编写树的按层次遍历算法树的按照层次遍历可以采用队列的辅助实现 Typedef struct tnode int data ; Struct tnode *son,*brother;*Tree;Void tree_travel(Tree root) initQueue(Q); If (root!=NULL) EnQueue (Q,root );While (!EmptyQueue(Q) p=GetHead(Q);OutQueue(Q);Printf(“%d”,p-data);P=p-son;While (p!=NULL)
12、EnQueue（Q,p）;P=p-brother;第五章 图1求下列有向图中从顶点vo到其余各顶点的最短路径及长度(给出求解的过程)。步骤SUDist1Dist2Dist3Dist4Dist5Dist6第一步v0123Max_intMax_intMax_int第二步v0,v1V11232Max_intMax_int第三步 v0,v1,v2V41232Max_int3第四步v0.v1.v2,v3.v4V21232Max_int3第五步v0,v1,v2,v4,v3V3123263第六步v0,v1,v4,v2,v3,v6V6123263第七步v0,v1,v4,v2,v3,v6,v5V512363 2
13、写出将一个无向图的邻接矩阵转换成邻接表的算法。算法设计如下：#define vnum 20 Typedef struct graph VertexType vexsvnum; Int arcsvnumvnum; Int vexnum,arcnum; GraphTp_Mat;Typedef struct arcnode int adhvex; Struct arcnode * nextarc;ArcNodeTp;Typedef struct vexnode int vertex; arcNodeTp * firstarc; AdjiList adjlist;Int vexnum,arcnum;G
14、raphTp_Adj;Void Matrix_to_Adjlist(GraphTp_Mat * ga,GraphTp_Adj *gb) int I ,j ; ArcNodeTp *p; gb-vexnum=ga-vexnum; gb-vexnum=ga-vexnum;i+for(i=0;ivexnum;i+) gb-adhlisti.vertex=I; gb-adhlisi.firstarc=NULL;For (i=0;ivexnum;i+) For (j=0;jvexnum;j+) If (ga-arcsij=1)P=(ArcNodeTp *)malloc (sizeof(ArcNodeTp
15、);p-adjvex=j;p-nextarc=ga-adjlisi.firstarc;ga-adjlisi.firstarc=p;第六章 查找1假设线性表中结点是按键值递增的顺序排列，试写一顺序查找算法，将岗哨设在高下标端。然后分别求出等概率情况下查找成功和不成功时的平均查找长度。1. 算法如下：Int search_sqtable(sqtable R,KeyType k)/顺序查找算法，将岗哨设在倒下标端 Int i=0; R. elem R.n , key = k; While (R. elem i. keyk) i+; If (R. elem i. keyk) return binsea
16、rch_2(R,K.Low.mid1)； Else return binsearch_2(R.K.mid+1;high);3试写出从大到小输出二叉排序树中所有不小于x的元素的算法。Void paint_NLT(BinTree T,int x)/从大到小输出二叉排列树T中所有不小于x的元素 If (T！=NULL) Paint_NLT(T-rchilld,x); If (T-date=x) Print(“%dn”,t-date); Paint_NLT(T-lhilld,x); 第七章 排序1对于给定的一组键值：83，40，63，13，84，35，96，57，39，79，6l，15，分别画出应用直
17、接插入排序、直接选择排序、冒泡排序、归并排序对上述序列进行排序过程。(1)对于序列： 83 40 63 13 84 35 96 57 39 79 61 15直接插入排序：83 40 63 13 84 35 96 57 39 79 61 1540 83 63 13 84 35 96 57 39 79 61 1540 63 83 13 84 35 96 57 39 79 61 1513 40 63 83 84 35 96 57 39 79 61 1513 40 63 83 84 35 96 57 39 79 61 1513 35 40 63 83 84 96 57 39 79 61 1513 35
18、 40 63 83 84 96 57 39 79 61 1513 35 40 57 63 83 84 96 39 79 61 1513 35 39 57 57 63 83 84 96 79 61 1513 35 39 40 57 63 79 83 84 96 61 1513 15 39 40 57 61 63 79 83 84 96 1513 15 35 39 40 57 61 63 79 83 84 96直接排序83 40 63 13 84 35 96 57 39 79 61 1513 40 63 83 84 35 96 57 39 79 61 1513 40 63 83 84 35 96
19、57 39 79 61 1513 35 40 63 83 84 96 57 39 79 61 1513 35 40 63 83 84 96 57 39 79 61 1513 35 40 57 63 83 84 96 39 79 61 1513 35 39 57 57 63 83 84 96 79 61 1513 35 39 40 57 63 79 83 84 96 61 1513 15 39 40 57 61 63 79 83 84 96 1513 15 35 39 40 57 61 63 79 83 84 96冒泡排序：初始数据： 25 11 22 34 5 44 76 61 100 3 1
20、4 120 第一趟结果：11 22 25 5 34 44 61 76 3 14 100 120第二趟结果：11 22 5 25 34 44 61 3 14 76 100 120第三趟结果：5 5 22 25 34 44 3 14 61 76 100 120第四趟结果：5 11 22 25 34 44 3 14 61 76 100 120第五趟结果：5 11 22 3 14 22 25 34 44 61 100 120第六趟结果：5 11 3 14 22 25 34 44 61 76 100 120第七趟结果：5 11 3 14 22 25 34 44 61 76 100 120第八趟结果：5
21、3 5 25 34 44 61 3 14 76 100 120第九趟结果：3 5 5 25 34 44 61 3 14 76 100 120第十趟结果：3 5 5 25 34 44 61 3 14 76 100 120归并排序83 40 63 13 84 35 96 57 39 79 61 1540 83 63 13 84 35 96 57 39 79 61 1513 35 40 63 83 84 96 57 39 79 61 1513 35 40 57 63 83 84 96 39 79 61 1513 35 39 57 57 63 83 84 96 79 61 152若对序列(tang，d
22、eng，an，wan，shi，bai，fang，liu)按字典顺序进行排序，分别写出： 泡排序第一趟的结果；泡排序第一趟的结果；Deng an tang shi bai fang liu wan 第一个元素为分界的快速排序第一趟的结果；第一个元素为分界的快速排序第一趟的结果；Liu deng an liu bai fang tang wan 排序时的初始堆。3对如下关键字序列(3，8，85，12，37，50)按堆排序算法进行从小到大排序，要求画出排序全过程的示意图。建初始堆4举例说明排序章介绍的各排序方法中哪些是不稳定的?稳定排序有直接插入，冒泡排序，归并排序。不稳定排序有快速排序，直接选择排序，堆排序。举例如下：快速排序初始状态 40 65 38 49 97 65 13 60排序后 13 38 40 49 60 65 65 97堆排序初始状态 65 38 75 97 80 13 27 65 排序后 13 27 38 65 65 75 80 97直接排序初始状态 40 65 38 49 97 65 13 60排序后 13 38 40 49 60 65 65 97