第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(）
第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；
//以下为顺序栈的存储结构定义
＃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
}
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 c语言的冒泡排序算法front == rear && tag == 0； ｝ //判队列空否
int IsFull ( ) const { return front == rear ＆＆ tag == 1； } //判队列满否
private:
int rear, front， tag； //队尾指针、队头指针和队满标志
Type ＊Q; //存放队列元素的数组
int m； //队列最大可容纳元素个数
｝
构造函数
template 〈class Type>
Queue〈Type〉：: Queue （ int sz ） : rear （0）， front （0), tag（0)， m (sz) ｛
//建立一个最大具有m个元素的空队列。
Q = new Type[m］; //创建队列空间
assert （ Q ！= 0 ); //断言： 动态存储分配成功与否
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。
发表评论