数据结构c语⾔版课后习题答案完整版
第1章绪论
5．选择题：CCBDCA
6．试分析下⾯各程序段的时间复杂度。
c语言的冒泡排序算法
（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
{while（i
if（i
if（i
}
[算法讨论] 因元素只扫描⼀趟，算法时间复杂度为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
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
template 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
Queue:: Queue ( int sz ) : rear (0),front (0), tag(0), m (sz) {
//建⽴⼀个最⼤具有m个元素的空队列。
Q =new Type[m]; //创建队列空间
assert ( Q != 0 ); //断⾔：动态存储分配成功与否}
插⼊函数
template
void Queue ::EnQueue ( Type &item) {
assert ( ! IsFull ( ) );//判队列是否不满，满则出错处理
rear = ( rear + 1 ) % m;//队尾位置进1, 队尾指针指⽰实际队尾位置
Q[rear] = item;//进队列
tag = 1;//标志改1，表⽰队列不空
}
删除函数
template
Type Queue ::DeQueue ( ) {
assert ( ! IsEmpty ( ) );//判断队列是否不空，空则出错处理
front =( front + 1 ) % m;//队头位置进1, 队头指针指⽰实际队头的前⼀位置
tag = 0;//标志改0, 表⽰栈不满
return Q[front]; //返回原队头元素的值
}
读取队头元素函数
template
Type Queue ::GetFront ( ) {
assert ( ! IsEmpty ( ) );//判断队列是否不空，空则出错处理
return Q[(front + 1) % m]; //返回队头元素的值
}
第4章串、数组和⼴义表
1．选择题
BBCAB BBCBB ABDCB C
2.综合应⽤题
（1）已知模式串t=‘abcaabbabcab’写出⽤KMP法求得的每个字符对应的next和nextval函数值。
（3）数组A中，每个元素A[i,j]的长度均为32个⼆进位,⾏下标从-1到9，列下标从1到11，从⾸地址S开始连续存放主存储器中，主存储器字长为16位。求：
①存放该数组所需多少单元？
②存放数组第4列所有元素⾄少需多少单元？
③数组按⾏存放时，元素A[7,4]的起始地址是多少？
④数组按列存放时，元素A[4,7]的起始地址是多少？
每个元素32个⼆进制位，主存字长16位，故每个元素占2个字长，⾏下标可平移⾄1到11。
（1）242 （2）22 （3）s+182 （4）s+142
(4)请将⾹蕉banana⽤⼯具 H( )—Head( )，T( )—Tail( )从L中取出。
L=(apple,(orange,(strawberry,(banana)),peach),pear)
H（H（T（H（T（H（T（L）））））））
（5）写⼀个算法统计在输⼊字符串中各个不同字符出现的频度并将结果存⼊⽂件（字符串中的合法字符为A-Z这26个字母和0-9这10个数字）。
void Count（）
//统计输⼊字符串中数字字符和字母字符的个数。
｛int i，num[36]；
char ch；
for（i＝0；i<36；i++）num[i]＝０；// 初始化
while（（ch＝getchar（））!=‘#’） //‘#’表⽰输⼊字符串结束。
if（‘0’<=ch<=‘9’）｛i=ch－48;num[i]++；｝ // 数字字符
else if（‘A’<=ch<=‘Z’）｛i=ch-65+10;num[i]++；｝// 字母字符
for（i=0；i<10；i++） // 输出数字字符的个数
printf（“数字％d的个数＝％d\n”，i，num[i]）；
for（i＝10；i<36；i++）// 求出字母字符的个数
printf（“字母字符％c的个数＝％d\n”，i＋55，num[i]）；
｝// 算法结束。
第5章树和⼆叉树
1．选择题
ADDCA CCBDC CCACC 2．应⽤题
（2）设⼀棵⼆叉树的先序序列： A B D F C E G H ，中序序列： B F D A G E H C ①画出这棵⼆叉树。
②画出这棵⼆叉树的后序线索树。
③将这棵⼆叉树转换成对应的树（或森林）。
(1) (2)
（3）假设⽤于通信的电⽂仅由8个字母组成，字母在电⽂中出现的频率分别为
0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10。
①试为这8个字母设计赫夫曼编码。
②试设计另⼀种由⼆进制表⽰的等长编码⽅案。
③对于上述实例，⽐较两种⽅案的优缺点。
解：⽅案1；哈夫曼编码

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。