【2018年必威体育精装版整理】数据结构导论作业.doc

数据结构导论 1、章节作业 第一章 概论 1．设计算法在整型数组A[n]中查找值为K的元素，若找到，则输出其位置i(0≤i≤n-1)，否则输出-1作为标志，并分析算法的时间复杂度。 int search (int A[],int n,int k) { int i; i=0; while (i=n-1) if (A[i]!=k) i++; else break; if (i=n-1) return I; else return -1； } 当查找成功时，A[i]与k比较次数≤n；当查找不成功时，A[i]与k比较n次，所以，算法时间复杂度T(n)=O(n)。 2．写出计算方阵A[n][n]与B[n][n]乘积C[n][n]的算法，分析算法的时间复杂度。 void matrixmultiply (int A[][n],int B[][n],int C[][n],int n) { int I,j; for (i=0;in;i++) for (j=0;jn;j++) { C[i][j]=0; for (k=0;kn;k++) C[i][j]+=A[i][j]*B[k][j]; } } 以方阵阶数n作为输出规模。可知第二层循环中的第一条赋值语句共执行n2次，第三层循环体中的乘法和赋值语句共执行n3次，所以此算法的计算量为n3+n2，算法时间复杂T(n)=O(n3) 第二章 线性表 1．设带头结点的单链表的结点结构如下： struct node { DataType data； struct node *next； } Node， *LinkList； 试编写一个函数int count(LinkList head，DataType x)统计单链表中数据域为x的结点个数。 int count(LinkList head,DataType x) { LinkList p=head-next; 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 (mn) { temp=L.data[m]; L.data[m]=L.data[n]; L.data[n]=temp; m++; n--; } } 带头结点的单链表的逆置算法 reverse_2(LinkList head) { LinkList p,q; p=head-next; 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_queue { DataType data; struct linked_queue *next; } LqueueTp; 队列的初始化 void InitQueue(LqueueTp *rear) { LqueueT