数据结构(c语言版)课后习题答案完整版

第1章 绪论

5.选择题:CCBDCA

6.试分析下面各程序段的时间复杂度。 (1)O(1) (2)O(m*n) (3)O(n2)

(4)O(log3n)

(5)因为x++共执行了n-1+n-2+……+1= n(n-1)/2,所以执行时间为O(n2) (6)O(n)

第2章 线性表

1.选择题

babadbcabdcddac 2.算法设计题

(6)设计一个算法,通过一趟遍历在单链表中确定值最大的结点。 ElemType Max (LinkList L ){

if(L->next==NULL) return NULL;

pmax=L->next; //假定第一个结点中数据具有最大值 p=L->next->next;

while(p != NULL ){//如果下一个结点存在 if(p->data > pmax->data) pmax=p; p=p->next; }

return pmax->data;

(7)设计一个算法,通过遍历一趟,将链表中所有结点的链接方向逆转,仍利用原表的存储空间。

void inverse(LinkList &L) { // 逆置带头结点的单链表 L p=L->next; L->next=NULL; while ( p) {

q=p->next; // q指向*p的后继 p->next=L->next;

L->next=p; // *p插入在头结点之后 p = q; } }

(10)已知长度为n的线性表A采用顺序存储结构,请写一时间复杂度为O(n)、空间复杂度为O(1)的算法,该算法删除线性表中所有值为item的数据元素。

[题目分析] 在顺序存储的线性表上删除元素,通常要涉及到一系列元素的移动(删第i个元素,第i+1至第n个元素要依次前移)。本题要求删除线性表中所有值为item的数据元素,并未要求元素间的相对位置不变。因此可以考虑设头尾两个指针(i=1,j=n),从两端向中间移动,凡遇到值item的数据元素时,直接将右端元素左移至值为item的数据元素位置。

void Delete(ElemType A[ ],int n)

∥A是有n个元素的一维数组,本算法删除A中所有值为item的元素。 {i=1;j=n;∥设置数组低、高端指针(下标)。 while(i

{while(i

if(i

[算法讨论] 因元素只扫描一趟,算法时间复杂度为O(n)。删除元素未使用其它辅助空间,最后线性表中的元素个数是j。

第3章 栈和队列

1.选择题

CCDAADABCDDDBCB 2.算法设计题 (2)回文是指正读反读均相同的字符序列,如“abba”和“abdba”均是回文,但“good”不是回文。试写一个算法判定给定的字符向量是否为回文。(提示:将一半字符入栈)

根据提示,算法可设计为: //以下为顺序栈的存储结构定义

#define StackSize 100 //假定预分配的栈空间最多为100个元素 typedef char DataType;//假定栈元素的数据类型为字符 typedef struct{

DataType data[StackSize]; int top; }SeqStack;

int IsHuiwen( char *t)

{//判断t字符向量是否为回文,若是,返回1,否则返回0 SeqStack s; int i , len; char temp; InitStack( &s);

len=strlen(t); //求向量长度

for ( i=0; i

{// 每弹出一个字符与相应字符比较 temp=Pop (&s);

if( temp!=S[i]) return 0 ;// 不等则返回0 else i++; }

return 1 ; // 比较完毕均相等则返回 1 }

(7)假设以数组Q[m]存放循环队列中的元素, 同时设置一个标志tag,以tag == 0和tag == 1来区别在队头指针(front)和队尾指针(rear)相等时,队列状态为“空”还是“满”。试编写与此结构相应的插入(enqueue)和删除(dlqueue)算法。

【解答】

循环队列类定义

#include

template class Queue { public:

Queue ( int=10 ); ~Queue ( ) { delete [ ] Q; } void EnQueue ( Type & item ); Type DeQueue ( ); Type GetFront ( );

void MakeEmpty ( ) { front = rear = tag = 0; }

//置空队列

//判队列空否

int IsEmpty ( ) const { return front == rear && tag == 0; } private:

int rear, front, tag; Type *Q; int m; }

//队尾指针、队头指针和队满标志

//存放队列元素的数组 //队列最大可容纳元素个数

//循环队列的类定义

int IsFull ( ) const { return front == rear && tag == 1; } //判队列满否

构造函数

template

Queue:: Queue ( int sz ) : rear (0), front (0), tag(0), m (sz) { //建立一个最大具有m个元素的空队列。 Q = new Type[m]; assert ( Q != 0 ); }

//创建队列空间

//断言: 动态存储分配成功与否

插入函数

template

void Queue :: EnQueue ( Type &item ) { }

assert ( ! IsFull ( ) ); rear = ( rear + 1 ) % m; Q[rear] = item; tag = 1;

//判队列是否不满,满则出错处理

//队尾位置进1, 队尾指针指示实际队尾位置 //进队列

//标志改1,表示队列不空

删除函数

template

Type Queue :: DeQueue ( ) {

assert ( ! IsEmpty ( ) ); front = ( front + 1 ) % m; tag = 0;

return Q[front];

//判断队列是否不空,空则出错处理

//标志改0, 表示栈不满 //返回原队头元素的值

//队头位置进1, 队头指针指示实际队头的前一位置

}

读取队头元素函数

template

Type Queue :: GetFront ( ) { }

assert ( ! IsEmpty ( ) );

//判断队列是否不空,空则出错处理

//返回队头元素的值

return Q[(front + 1) % m];

第4章 串、数组和广义表

1.选择题

BBCABBBCBBABDCBC 2.综合应用题

(1)已知模式串t=‘abcaabbabcab’写出用KMP法求得的每个字符对应的next和nextval函数值。

模式串t的next和nextval值如下: j t串 next[j] nextval[j] 1 2 3 4 5 6 7 8 9 10 11 12 a b c a a b b a b c a b 0 1 1 1 2 2 3 1 2 3 4 5 0 1 1 0 2 1 3 0 1 1 0 5

(3)数组A中,每个元素A[i,j]的长度均为32个二进位,行下标从-1到9,列下标从1到11,从首地址S开始连续存放主存储器中,主存储器字长为16位。求:

① 存放该数组所需多少单元?

② 存放数组第4列所有元素至少需多少单元?

联系客服:779662525#qq.com(#替换为@) 苏ICP备20003344号-4