章节作业 - 图文

数据结构导论章节作业

第一章 概论

1．设计算法在整型数组A[n]中查找值为K的元素，若找到，则输出其位置i(0≤i≤n-1)，否则输出-1作为标志，并分析算法的时间复杂度。 答：

typrdef (){ int i; long a[n+1]; //读入数组 for(i=0;i

if(a[i]==k) {

printf(\输出位置 break; }

//确定是否找到 if(i==n)

printf(\如果没找到输出-1 return 0; //结束程序 }

从头开始扫描，并设一个变量find=0，如果找到了一个值等于K，输出相应位置，如果一直扫描到结尾还是没有符合条件的值，输出-1。算法的时间复杂度为O(n)。

2．写出计算方阵A[n][n]与B[n][n]乘积C[n][n]的算法，分析算法的时间复杂度。 答：int i, j, k;

for(i = 0; i < n; i++) {

for(j = 0; j < n; j++)

{

c[i][j] = 0;

for(k = 0; k < n; k++)

{

c[i][j] += a[i][k] * b[k][j]; }

} }

算法的时间复杂度是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 num=0; While(P!=0) {

If(p->data==x)m++; p=p->next; }

return m; }

2．试分别以顺序表和带头结点的单链表作存储结构，各写一个实现线性表的就地(即使用尽可能少的附加空间)逆置的算法，在原表的存储空间内将线性表(a1，a2，…，an)逆置为(an，an-1，…，a1)。

答：顺序表逆置算法描述如下： Void inverse_sqlList(SeqList L) {

Int m,n,k;

DataType temp; M=0;

N=L.Length-1; While(m

{temp=L.data[n]; L.data[n]=temp; m++; n--; } }

带头节点的单链表的逆置算法，用两种方法来解。 解法一：

reversr_1(LinkList head) {

LinkList p,q,r; P=p->next; q=p;

r=NULL; //p,q,r三个辅助指针变量 while(p!=NULL) {

P=p->next; q->next=r; r=q; q=p; }

head->next=r; //最后，r指向逆置后的第一个节点 }

解法二：

应用前插技巧。

reversr_2(LinkList head) {

LinkList p,q; P=head->next; Head->next=NULL; r=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的四辆列车，顺序进入一个栈式结构的站台，试写出这四辆列车开出车站的所有可能的顺序。

答：考虑一下几种情况：

（1） 若列车1最先开车出站，则列车可能的出站顺序有：

1234、1243、1324、1342、1432；

（2） 若列车2最先开车出站，则列车可能的出站顺序有：

2134、2143、2314、2341、2431；

（3） 若列车3最先开车出站，则列车可能的出站顺序有：

3214、3241、3421；

（4） 若列车4最先开车出站，可能的出站顺序有：

4321；

这里注意：4123、4132、4213、4231都不是本题的解。

综合（1）（2）（3）（4）四辆车开车出站的所有可能的顺序有14种。

3．假设以带头结点的循环链表表示队列，并且只设一个指针指向队列尾结点(注意不设头指针)，试编写相应的初始化队列、入队列和出队列算法。 答： typedef struct linked_queue { DateType date; strct linked_queue * next; } LqueueTp; //算法描述如下： (1)队列初始化 void InitQueue(LqueueTp* rear) { LqueueTp*p; p=(LqueueTp*)malloc(sizeof(LqueueTp)); rear=p; rear->next=rear; //将队列设置成循环链表，且置队列为空 } (2)入队列

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; //移动队列尾指针

}

(3)出队列

OutQueue(LqueueTp* rear,DadaType *x) { LqueueTp*p,*p; if(read=read->next) {

error(\队空\} else { }

h=read->next; //找到链表头结点 p=h->next; //找到队列第一元素结点 *x=p->data;

h->next=p->next;

if(p==rear)read=h; // 若队列 只有一个结点，移动队free(p); return 1;

列尾指针 }

4．假设以数组cycque[m]存放循环队列的元素，同时设变量rear和quelen分别指示循环队列中队列尾元素位置和内含元素的个数。试给出此循环队列的队列满和队列空的条件，并写出相应的入队列和出队列的算法。 答：type struct cycqueue {

DataType data[m]; Int rear; Int quelen; }CycqueueTp; CyqueueTp * cq;

该循环队列的队列满的条件是：（cq->quelen==m）。 队列空条件是：（cq->queue==0）。 (1) 入队列

Int EnCyQueue(CycqueueTp * cq;DataType x) {

If(cq->queuen==m) {

error(“队列满”),return 0; }//队列满，入队列失败 else {

本文来源：https://www.bwwdw.com/article/9l62.html