第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;
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 ==c语言的冒泡排序算法 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; //存放队列元素的数组
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 ); //断言: 动态存储分配成功与否
}
插入函数
template<class Type>
void Queue<Type> :: EnQueue ( Type &item ) {
assert ( ! IsFull ( ) ); //判队列是否不满，满则出错处理
rear = ( rear + 1 ) % m; //队尾位置进1, 队尾指针指示实际队尾位置
Q[rear] = item; //进队列
tag = 1; //标志改1，表示队列不空
}
删除函数
template<class Type>
Type Queue<Type> :: DeQueue ( ) {
assert ( ! IsEmpty ( ) ); //判断队列是否不空，空则出错处理
front = ( front + 1 ) % m; //队头位置进1, 队头指针指示实际队头的前一位置
tag = 0; //标志改0, 表示栈不满
return Q[front]; //返回原队头元素的值
}
读取队头元素函数
template<class Type>
Type Queue<Type> :: GetFront ( ) {
assert ( ! IsEmpty ( ) ); //判断队列是否不空，空则出错处理
return Q[(front + 1) % m]; //返回队头元素的值
}
第4章 串、数组和广义表
1．选择题
BBCABBBCBBABDCBC
2.综合应用题
（1）已知模式串t=‘abcaabbabcab’写出用KMP法求得的每个字符对应的next和nextval函数值。
模式串t的next和nextval值如下：
j | 1 2 3 4 5 6 7 8 9 10 11 12 |
t串 | a b c a a b b a b c a b |
next[j] | 0 1 1 1 2 2 3 1 2 3 4 5 |
nextval[j] | 0 1 1 0 2 1 3 0 1 1 0 5 |
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。
发表评论