内容发布更新时间 : 2024/5/21 4:57:46星期一 下面是文章的全部内容请认真阅读。

习题一

1 填空题

(1) (数据元素、或元素、或结点、或顶点、或记录）是数据的基本单位，在计算机程序中作为一个整体进行考虑和处理。

(2)（数据项、或字段）是数据的最小单位，（数据元素）是讨论数据结构时涉及的最小数据单位。 (3)从逻辑关系上讲，数据结构主要分为(集合)、(线性结构)、(树结构)和(图)。

(4)数据的存储结构主要有（顺序存储结构）和（链式存储结构）两种基本方法，不论哪种存储结构，都要存储两方面的内容：（数据元素）和（它们之间的关系 ）。 (5) 算法具有5个特性，分别是（输入）、（输出）、（有穷性）、（确定性）、（可行性）。

(6) 算法的描述方法通常有(自然语言)、(流程图)、(程序设计语言)、(伪代码)4种，其中，(伪代码)被称为算法语言。

(7) 一般情况下，一个算法的时间复杂度是算法（输入规模）的函数。

(8) 设待处理问题的规模为n,若一个算法的时间复杂度为一个常数，则表示成数量级的形式为(O(1))，若为n*log25n, 则表示成数量级的形式为(O(n*log2n))。

2. 选择题: (1) C, D (2) B (3) B (4) A (5) D (6) A (7) C (8) C, E

习题二 1. 填空题

(1) 在顺序表中，等概率情况下，插入和删除一个元素平均需移动(表长的一半)个元素，具体移动元素的个数与(表的长度)和(数据元素所在的位置)有关。

(2) 一个顺序表的第一个元素的存储地址是100，每个数据元素的长度是2，则第5个数据元素的存储地址是（108）。

(3) 设单链表中指针p指向单链表的一个非空结点A，若要删除结点A的直接后继，则需要修改指针的操作为（p->next=(p->next)->next, 或者 q=p->next; p->next=q->next）。

(4) 单链表中设置头结点的作用是(方便运算,减少程序的复杂性，使得空表和非空表处理统一)。 (5) 非空的循环单链表由头指针head指示，则其尾结点(由指针p所指)满足(p->next=head)。

(6) 在有尾指针rear指示的循环单链表中，在表尾插入一个结点s的操作序列是（s->next=rear->next; rear->next=s; rear=s），删除开始结点的操作序列是（q=rear->next->next; rear->next->next=q->next; delete q;）。

注：假设此循环单链表有表头结点

(7) 一个具有n个结点的单链表，在p所指结点后插入一个新结点s的时间复杂性为（ O(1)）；在给定值x的结点后插入一个新结点的时间复杂性为( O(n) ）。

(8) 可由一个尾指针惟一确定的链表有(循环链表)、(双链表)、(双循环链表)。

2. 选择题: (1) A,B (2) D (3) B (4) A (5) A (6) D (7) B (8) B (9) C (10) B (11) B (12) D (13) A (14) A 5. 算法设计 (1) 设计一个时间复杂度为O(n)的算法。实现将数组A[n]中所有元素循环左移k个位置。 算法思想：要使a1…akak+1…an -> ak+1…ana1…ak,可以先让a1…akak+1…an->ak…a1an…ak+1,再让ak… a1 an…ak+1 -> ak+1…ana1…ak ，参见第1章16页的思想火花 算法：void converse(T a[], int i, int j){

for(s=i; s<=(i+j)/2;s++) //将数组a中从i到j中的元素倒置 {temp=a[s];a[s]=a[j-s+i];a[j-s+i]=temp;} } void move(T a[ ], k)

{converse(a,0,k-1);//3次调用函数converse converse(a,k,n-1); converse(a,0,n-1); }

(2) 已知数组A[n]中的元素为整型，设计算法将其调整为左右两部分，左边所有元素为奇数，右边所有元素为偶数，并要求算法的时间复杂度为O(n). 解法1：void tiaozhen(T A[],int n)

{ s=0; t=n-1; while(s

{ while( A[s]%2!=0) s++;//s=s+1 while ( A[t]%2==0) t--; if(s

或 void tiaozhen(T A[],int n) { s=0; t=n-1; while(s

{ if(A[s]%2!=0) s++;//s=s+1 else if(A[t]%2==0) t--;

else {temp=A[s];A[s]=A[t];A[t]=temp; s++;t--;} }}

(3) 试编写在无头结点的单链表上实现线性表的插入操作的算法,并和带头结点的单链表上的插入操作的实现进行比较

void LinkList_1::Insert(int i, T x){ if(i<=0) throw \输入的插入位置值小于1\

if(i==1){s=new Node; s->data=x; s->next=first; first=s; } else{ p=first ; j=0;

while (p && jnext; j++; }

if (!p) throw “插入位置值太大\

else { s=new Node; s->data=x; s->next=p->next; p->next=s; } } }

(4) 试分别以顺序表和单链表作存储结构，各写一实现线性表就地逆置的算法。

算法思想：顺序表的程序参见题（1）的converse.单链表的程序如下，设单链表有表头结点. void LinkList::converse() { p=first->next; first->next=NULL; while(p){

q=p->next; p->next=first->next; first->next=p;p=q; } }

(5) 假设在长度大于1的循环链表中，既无头结点也无头指针，s为指向链表中某个结点的指针，试编写算法删除结点s的前驱结点。 void LinkList::deleteS(Node *s) {p=s;

while(p->next->next!=s) p=p->next; { q=p->next; p->next=q->next; delete q; }

(6) 已知一单链表中的数据元素含有三类字符：字母、数字和其它字符。试编写算法，构造三个循环链表，使每个循环链表中只含同一类字符。

算法思想：1）构造3个带表头结点的循环链表，分别为zifu，shuzi和qita； 2）遍历单链表，按单链表中的当前数据元素的分类插入相应的链表 void fl(Node* zifu, Node *shuzi, Node *qita) { s=new Node; s->next=s; zifu=s; s=new Node; s->next=s; shuzi=s; s=new Node; s->next=s; qita=s;

a=zifu; b=shuzi; c=qita;

p=first->next; //设单链表带头结点 while(p) { q=p; p=p->next;

if((q->data>='a'&&q->data<='z') ||(q->data>='A'&& q->data<='A')) { q->next=a->next; a->next=q; a=q;} else if(q->data>='0' && q->data<='9')

{q->next=b->next; b->next=q; b=q;} else {q->next=c->next; c->next=q; c=q;} }

delete first; }

(7) 设单链表以非递减有序排列，设计算法实现在单链表中删除相同的多余结点。 解： void LinkList::deleteALL()

{ p=first->next; //假设单链表带表头结点。 while(p)

{if(p->next!=NULL && p->next->data==p->data) {q=p->next; p->next=q->next; delete q;} else p=p->next;} }

(8) 判断带头结点的双循环链表是否对称。 解 bool LinkList::equal(DulNode *first) { p=first->next; q=first->prior; while(p!=q&&p->prior!=q) if(p->data==q->data)

{p=p->next; q=q->prior;} else {return 0;} return 1; }

---------------------------------------------------------------------------------------------------------------------------------------- 习题三 1 填空题

(1) 设有一个空栈，栈顶指针为1000H，经过push、push、pop、push、pop、push、push后，栈顶指针为(1003H)。

(2) 栈结构通常采用的两种存储结构是(顺序存储结构和链接存储结构\\顺序栈和链栈)，其判定栈空的条件分别是(top=-1, top=NULL), 判断栈满的条件分别是(top=MaxSize-1, 内存满/内存无可用空间)。 (3) (栈)可作为实现递归函数调用的一种数据结构。 (4) 表达式a*(b+c)-d的后缀表达式是(abc+*d-)。

(5) 栈和队列是两种特殊的线性表，栈的操作特性是(后进先出)，队列的操作特性是(先进先出)，栈和队列的主要区别在于(插入、删除运算的限定不一样 )。 (6) 循环队列的引入是为了克服( 假溢出 )。

(7) 一维数组Data[n]用来表示循环队，队头指针front和队尾指针rear定义为整型变量，计算队中元素个数的公式是( (rear-front+n)%n )。

(8) 用循环链表表示的队列长度为n，若只设头指针，则出队和入队的时间复杂度分别是( O(1) )和( O(n) )。

2. 选择题: (1) C (2) D (3) C (4) B (5) B (6) B (7) D (8) A (9) C 4.解答下列问题 (1) ① 不可以, 因为有序列C, A, B.

② 可以, push, push, push, pop, pop, pop, push, pop, push, pop. (2) 见书本