当前位置:首页 >> 数学 >>

数据结构课后习题答案(1~5章)

精品文档 第 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<j) {while(i<j && A[i]!=item)i++; ∥若值不为 item,左移指针。 if(i<j)while(i<j && A[j]==item)j--;∥若右端元素值为 item,指针左移 if(i<j)A[i++]=A[j--]; } [算法讨论] 因元素只扫描一趟,算法时间复杂度为 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<len/2; i++)//将一半字符入栈 Push( &s, t[i]); while( !EmptyStack( &s)) {// 每弹出一个字符与相应字符比较 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 <assert.h> template <class Type> 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; } //判队列空否 int IsFull ( ) const { return front == rear && tag == 1; } //判队列满否 private: int rear, front, tag; Type *Q; //队尾指针、队头指针和队满标志 //存放队列元素的数组 . 精品文档