数据结构(c语言版)课后习题答案完整版资料 下载本文

内容发布更新时间 : 2024/12/25 10:07:16星期一 下面是文章的全部内容请认真阅读。

.

第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 ){//如果下一个结点存在 }

return pmax->data;

if(p->data > pmax->data) pmax=p; p=p->next;

(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

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

第3章 栈和队列

1.选择题

CCDAADABCDDDBCB 2.算法设计题

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

.