数据结构导论作业.doc

数据结构导论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； 当查找成功时，Ai与k比较次数n；当查找不成功时，Ai与k比较n次，所以，算法时间复杂度T(n)=O(n)。2写出计算方阵Ann与Bnn乘积Cnn的算法，分析算法的时间复杂度。void matrixmultiply (int An,int Bn,int Cn,int n) int I,j;for (i=0;in;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;head-next=NULL;while (p!=NULL)q=p-next;p-next=head-next;head-next=p;p=q;第三章 栈、队列和数组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，3，4的四辆列车，顺序进入一个栈式结构的站台，试写出这四辆列车开出车站的所有可能的顺序。一号列车先出站：1234,1243,1324,1342,1432;二号列车先出站：2134,2143,2314,2341,2431；三好列车先出站：3214,3241,3421；四号列车先出站：4321；但是这里的 4123、4132、4213、4231都不是正解,所以共有14种可能3假设以带头结点的循环链表表示队列，并且只设一个指针指向队列尾结点(注意不设头指针)，试编写相应的初始化队列、入队列和出队列算法。类型定义：typedef struct linksd_queueDataType data;struct linked_queue *next; LqueueTp;队列的初始化void InitQueue(LqueueTp *rear) LqueueTp *p;p=(LqueueTp *)malloc(sizeof(LqueueTp);rear=p;rear-next=rear;入队列void EnQueue(LqueueTp *rear;DataType x) LqueueTp *p;p=(LqueueTp*)malloc(sizeof(LqueueTp);p-data=x;p-next=rear-next;rear-next=p;rear=p出队列OutQueue(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 1;4假设以数组cycquem存放循环队列的元素，同时设变量rear和quelen分别指示循环队列中队列尾元素位置和内含元素的个数。试给出此循环队列的队列满和队列空的条件，并写出相应的入队列和出队列的算法。类型定义：typedef struct cycqueueDataType datam;int rear;int quelen; CycqueueTp;CycqueueTp *cq队列满条件是：（cq-quelen=m）。队列空条件是：（cq-quelen=0）入队列：int EnCycQueue(CycqueueTp *cq;DataType x)if (cq-quelen=m) error; return 0;else cq-rear=(cq-rear+1)%m;cq-datacq-rear=x;cq-quelen=cq-quelen+1;return 1;出队列：int OutCyQueue(CycqueueTp *cq)if (cq-quelen=0) error; return 0;else cq-quelen=cq-quelen-1;*x=cq-data(cq-rear+m-cq-quelen)% m;return 1;取队列首元素：DataType GetHead(CycqueueTp *cq) DataType x;x=cq-datacq-rear=m-cq-quelen% m;return x;第四章 树和二叉树1算法设计题 (1)以二叉链表作存储结构，试编写求二叉树叶子结点个数的算法。typedef struct btnode DataType data;struct btnode *lchild,*rchild;*BinTree;int leafnode_num(BinTree bt )if (bt=NULL) return 0 ;elseif (bt-lchild=NULL) & （bt-rchild=NULL）return 1;elsereturn leafnode_num (bt-lchild)+leafnode_num (bt-rchild); (2)设计算法求二叉树的结点的个数。typedef struct btnodeDataType data;struct btnode *lchild,*rchild;*BinTree;int node_num (BinTree bt)if (bt=NULL) return 0;elsereturn 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-dta);preorder(bt-lchild);preorder(bt-rchild);2树的存储结构采用孩子兄弟链表，试编写树的按层次遍历算法typedef struct tnode int data;struct tnode *son,*brother;*Tree;void tree_travel (Tree root ) InitQueue(Q);if (root1=NULL) EnQueue( q , root );while (!EmptyQueue(Q) p=GetHead(Q); OutQueue (Q);prinf(“%d” , p-data);p=p-son;while (p!=NULL) Enqueue (Q , p);p=p-brother;第五章 图1求下列有向图中从顶点vo到其余各顶点的最短路径及长度(给出求解的过程)。 步骤Sudist1dist2dist3dist4dist5dist6第1步v0123Max_intMax_intMax_int第2步v0,v1V11232Max_intMax_int第3步v0,v1,v4V41232Max_int3第4步v0,v1,v4,v2V21232Max_int3第5步v0,v1,v4,v2,v3V3123263第6步v0,v1,v4,v2,v3,v6V6123263第7步v0,v1,v4,v2,v3,v6,v5V51232632写出将一个无向图的邻接矩阵转换成邻接表的算法。#define vnum 20typedef struct graph VertexType vexsvnum;int arcsvnumvnum;int vexnum,arcnum; GraphTp_Mat;typedef struct arcnodeint adjvex;struct arcnode *nextarc; ArcNodeTp;typedef struct vexnode int vertex;ArcNodeTp *firstarc;AdjLisvnum;typedef struct graph AdjLis adjlist;int vexnum,arcnum; GraphTp_Adj;void Matrix_to_Adjlis(GraphTp_Mat *ga,GraphTp_Adj *gp) int I,j;ArcNodeTp *p;gp-vexnum=ga-vexnum;gp-arcnum=ga-arcnum;for ( i =0;Ivexnum;i+) gp-adjlisi.vertex=I;gp-adjlisi.firstarc=NULL;for (i=0;Ivexnum;i+)for (j=0;jvesnum;j+)if (ga-arcsij=1)p=(ArcNodeTp *)malloc(sizeof(ArcNodeTp);p-adjvex=j;p-nextarc=ga-adjlisi.firstarc;ga-adjlisi.firstarc=p;第六章 查找1假设线性表中结点是按键值递增的顺序排列，试写一顺序查找算法，将岗哨设在高下标端。然后分别求出等概率情况下查找成功和不成功时的平均查找长度。int search_sqtable(Sqtable R,KeyType k)int i=0;R. elem R.n.key=k;while (R. elem i.keyki=R.n) return -1;else return i;2试编写算法求键值为k结点在给定的二叉排序树中所在的层数。int level_count(BinTree bst,KeyType k)int lev=0;BSTNode *p=bst;while (p!=NULL)lev+;if (p-data=k) return lev;if (p-datarchild;elsep=p-lchild;return 0;3试写出从大到小输出二叉排序树中所有不小于x的元素的算法。void Print_NLT(BinTree T,int x)if (T!=NULL)Print_NLT(T-rchild,x);If (T-data=x)printf(“%dn”,T-data);Print_NLT(T-lchild,x);第七章 排序1对于给定的一组键值：83，40，63，13，84，35，96，57，39，79，6l，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 40 63 83 84 96 57 39 79 61 1513 35 40 57 63 83 84 96 39 79 61 1513 35 39 40 57 63 83 84 96 79 61 1513 35 39 40 57 63 79 83 84 96 61 1513 35 39 40 57 61 63 79 83 84 96 1513 15 35 39 40 57 61 63 79 83 84 96直接选择排序:84 40 63 13 84 35 96 57 39 79 61 1513 40 63 83 84 35 96 57 39 79 61 1513 15 63 83 84 35 96 57 39 79 61 4013 15 35 83 84 63 96 57 39 79 61 4013 15 35 39 84 63 96 57 83 79 61 4013 15 35 39 40 63 96 57 83 79 61 8413 15 35 39 40 57 96 63 83 79 61 8413 15 35 39 40 57 61 63 83 79 96 8413 15 35 39 40 57 61 63 83 79 96 8413 15 35 39 40 57 61 63 83 79 96 8413 15 35 39 40 57 61 63 79 83 96 8413 15 35 39 40 57 61 63 79 83 96 8413 15 35 39 40 57 61 63 79 83 84 96冒泡排序： 初始数据： 25 11 22 34 5 44 76 61 100 3 14 120第1趟结果： 11 22 25 5 34 44 61 76 3 14 100 120第2趟结果： 11 22 5 25 34 44 61 3 14 76 100 120第3趟结果： 5 5 22 25 34 44 3 14 61 76 100 120第4趟结果： 5 11 22 25 34 3 14 44 61 76 100 120第5趟结果： 5 11 22 25 3 14 34 44 61 76 100 120第6趟结果： 5 11 22 3 14 25 34 44 61 76 100 120第7趟结果： 5 11 3 14 22 25 34 44 61 76 100 120第8趟结果： 5 3 11 14 22 25 34 44 61 76 100 120第9趟结果： 3 5 11 14 22 25 34 44 61 76 100 120第10趟结果： 3 5 11 14 22 25 34 44 61 76 100 120归并排序：83 40 63 13 84 35 96 57 39 79 61 1540 83 13 63 35 84 57 96 39 79 15 6113 40 63 83 35 57 84 96 15 39 61 7913 35 40 57 63 83 84 96 15 39 61 7913 15 35 3