数据结构习题(有答案)
- 格式：doc
- 大小：718.00 KB
- 文档页数：24
if (elem[i-1]= =e) //找到，进行删除操作
{ for ( j=i; j<length; j++) // ai至an依次前移
Elem[j-1] = elem[j];
length - - ; //表长减一
return 1 ; //删除成功，返回1
}
return 0 ; //未找到，删除不成功，返回0
要求：给出问题分析、算法描述、源程序及运行截图，在线提交。
1.设a, b, c为3个整数，求其中位于中间值的整数。
1.设计算法：在顺序表中删除值为e的元素，删除成功，返回1；否则，返回0。
int Sqlist<T>::DeleteElem( T e )
{ for (i=1; i<=length; i++) //按值顺序查找* i可从0开始
(2)借助栈T，将栈S中所有值为e的数据元素删除之。
3.编写一个算法，将一个非负的十进制整数N转换为B进制数，并输出转换后的结果。当N=248D，B分别为8和16时，转换后的结果为多少？
#include“stack.h”
int NumTrans( int N, int B) {//十进制整数N转换为B进制数
if ( head==NULL) throw“表空!”; //空表，不能删
else if ( i==1) { //删除第1个元素
p=Head; x=p->data; //保存被删元素值
Head= p->next ;
delete p ;
}
else { //元素定位到第ai-1
p=Head; j=1 ; //定位查找起始位置
{ int p=1;
for (int j=1; j<=i; j++) p*=j;
s+=p;
}
return s;
}
解：
(1) , T(n)=O(n)
(2) , T(n)=O(n2)
1.4算法设计
有3枚硬币，其中有1枚是假的，伪币与真币重量略有不同。如何借用一架天平，找出伪币？以流程图表示算法。
上机练习题
}
(2)statusalgo_2(SqStack S,inte){
SqStack T;
int d;
while(!S.tackEmpty()){
d = S.Pop();
if(d!=e ) T.Push(d);}
while(!T.StackEmpty()){
d=T.Pop();
T.Push(d);}
}
解：(1)借助一个数组，将栈中的元素逆置。
return 0 ; //不匹配，多左括号
else
return 1 ; //匹配
} //#
5.简述栈和队列的逻辑特点，各举一个应用实例。
6.写出下列中缀表达式的后缀表达式。
(1)-A+B-C+D
(2)(A+B)*D+E/(F+A*D)+C
(3) A&&B||!(E>F)
(1) A-B+C-D+
(2) AB+D*EFAD*+/+C+
}
retrun x; //返回被删除元素值
}//#
6.用教材定义的顺序表的基本操作实现下列操作：
template <calss T>
int DeleteElem(SqList L, T e)
#include“SqList.h“
template <calss T>
int DeleteElem(SqList L, T e){ //
while ( p && j<i ) { p=p->next; j++;}
(2)定位到第i个结点的前驱ai-1；
p=head; j=0;
while ( p && j<i-1 ) { p=p->next; j++;}
(3)定位到尾结点；
p=head;
while ( p ->next ) p=p->next;
i = L.LocateElem(e) ; //按值查找
if (!i) //未找到
return 0;
else //找到
delete (i) ; //删除被找到的元素
}
7.已知L是有表头结点的单链表，且P结点既不是首元结点，也不是尾结点，试写出实现下列功能的语句序列。
(1)在P结点后插入S结点；
(2)在P结点前插入S结点；
{ stack S; //借助一个栈
int x;
cin>>x;
while (gt;x; }
sum=0;
cout<<sum;
while ( x=S.pop() ) {
sum+=x; cout<<sum; }
} //
10.简述以下算法的功能（栈和队列的元素类型均为int）。
stack<int> S; //建立一个栈
while( N!=0) { // N非零
i=N%B ; //从低到高，依次求得各位
N=N/B;
S.push(i); }//各位入栈
while ( !S.StackEmpty()) { //栈不空
{ i= S.pop();
If (i>9) i=’A’+10-i;
(4)定位到尾结点的前驱。
p=head;
while ( p->next->next ) p=p->next;
4.描述一下三个概念的区别：头指针，头结点，首元结点。并给予图示。
头指针：是一个指针变量，里面存储的是链表中首结点的地址，并以此来标识一个链表。
头结点：附加在第一个元素结点之前的一个结点，头指针指向头结点。
解：325641可以
154623不可以。
2.简述以下算法的功能（栈的元素类型为int）。
(1)statusalgo_1( SqStack S ){
inti, n, A [255];
n=0;
while(!S.StackEmpty() ){n++; A[n]= S.Pop();}
for( i=1; i<= n ; i++) S.Push(A[i]);
while { p->next && j<i-1 } {
p=p->next; j++ ; }
if ( !p->next || j>i-1 ); //定位失败
throw“删除位置不合理”;
else { //定位成功，进行结点删除
q=p->next;
x=p>data;
p->next=q->next;
delete q;
假设以数组sem存放循环队列的兀素冋时设变量rear和front分别作为队首队尾指针且队首指针指向队首前一个位置队尾指针指向队尾兀素处初始时rearfornt1写出这样设计的循环队列入队出队的算法
第
1.1有下列几种二元组表示的数据结构，试画出它们分别对应的图形表示，并指出它们分别属于何种结构。
(1) A= ( D，R )，其中，D = { a1，a2，a3，a4}，R={ }
case’)’//右括号
if (s.StackEmpty()) return 0; //栈空，不匹配，多右括号
else { s.Pop(); break; } //左括号出栈
}//switch
p++; //取表达式下一个字符
} // while
if (!s.StackEmpty()) //表达式结束，栈不空
x=x+y;
(3)
1.3指出下列个算法的功能，并求其时间复杂度。
(1) int sum1(int n)
{
int p=1,s=0;
for (int i=1;i<=n; i++)
{ p*= i; s+=p;}
return s;
}
(2) int sum2 (int n)
{ int s=0;
for ( int i=1; i<=n; i++)
int blank_match(char *exp) {用字符串存表达式
SqStack<char> s; //创建一个栈
char *p=exp; //工作指针p指向表达式首
while ( *p!=’=’) { //不是表达式结束符
switch(p) {
case’(’: //左括号，入栈
s.push(ch); break;
}
2.分析顺序表中元素定位算法int SqList<T>::Locate ( T e )的时间复杂度。
解：设表长为n，等概率下，每个元素被定位的概率为：p=1/n
定位成功第i个元素，需比较i次
3.对于有头结点的单链表，分别写出定位成功时，实现下列定位语句序列。
(1)定位到第i个结点ai；
p=head; j=0;
(3) AB&&EF ! ||
7.计算后缀表达式：4 5 * 3 2 + -的值。
解：15
8.将下列递推过程改写为递归过程。
void recursion( int n ) {
int i=n;
while( i>1) {
cout<<i; i--; }
}
解：void recurision(int j)
{ for ( j=i; j<length; j++) // ai至an依次前移
Elem[j-1] = elem[j];
length - - ; //表长减一
return 1 ; //删除成功，返回1
}
return 0 ; //未找到，删除不成功，返回0
要求：给出问题分析、算法描述、源程序及运行截图，在线提交。
1.设a, b, c为3个整数，求其中位于中间值的整数。
1.设计算法：在顺序表中删除值为e的元素，删除成功，返回1；否则，返回0。
int Sqlist<T>::DeleteElem( T e )
{ for (i=1; i<=length; i++) //按值顺序查找* i可从0开始
(2)借助栈T，将栈S中所有值为e的数据元素删除之。
3.编写一个算法，将一个非负的十进制整数N转换为B进制数，并输出转换后的结果。当N=248D，B分别为8和16时，转换后的结果为多少？
#include“stack.h”
int NumTrans( int N, int B) {//十进制整数N转换为B进制数
if ( head==NULL) throw“表空!”; //空表，不能删
else if ( i==1) { //删除第1个元素
p=Head; x=p->data; //保存被删元素值
Head= p->next ;
delete p ;
}
else { //元素定位到第ai-1
p=Head; j=1 ; //定位查找起始位置
{ int p=1;
for (int j=1; j<=i; j++) p*=j;
s+=p;
}
return s;
}
解：
(1) , T(n)=O(n)
(2) , T(n)=O(n2)
1.4算法设计
有3枚硬币，其中有1枚是假的，伪币与真币重量略有不同。如何借用一架天平，找出伪币？以流程图表示算法。
上机练习题
}
(2)statusalgo_2(SqStack S,inte){
SqStack T;
int d;
while(!S.tackEmpty()){
d = S.Pop();
if(d!=e ) T.Push(d);}
while(!T.StackEmpty()){
d=T.Pop();
T.Push(d);}
}
解：(1)借助一个数组，将栈中的元素逆置。
return 0 ; //不匹配，多左括号
else
return 1 ; //匹配
} //#
5.简述栈和队列的逻辑特点，各举一个应用实例。
6.写出下列中缀表达式的后缀表达式。
(1)-A+B-C+D
(2)(A+B)*D+E/(F+A*D)+C
(3) A&&B||!(E>F)
(1) A-B+C-D+
(2) AB+D*EFAD*+/+C+
}
retrun x; //返回被删除元素值
}//#
6.用教材定义的顺序表的基本操作实现下列操作：
template <calss T>
int DeleteElem(SqList L, T e)
#include“SqList.h“
template <calss T>
int DeleteElem(SqList L, T e){ //
while ( p && j<i ) { p=p->next; j++;}
(2)定位到第i个结点的前驱ai-1；
p=head; j=0;
while ( p && j<i-1 ) { p=p->next; j++;}
(3)定位到尾结点；
p=head;
while ( p ->next ) p=p->next;
i = L.LocateElem(e) ; //按值查找
if (!i) //未找到
return 0;
else //找到
delete (i) ; //删除被找到的元素
}
7.已知L是有表头结点的单链表，且P结点既不是首元结点，也不是尾结点，试写出实现下列功能的语句序列。
(1)在P结点后插入S结点；
(2)在P结点前插入S结点；
{ stack S; //借助一个栈
int x;
cin>>x;
while (gt;x; }
sum=0;
cout<<sum;
while ( x=S.pop() ) {
sum+=x; cout<<sum; }
} //
10.简述以下算法的功能（栈和队列的元素类型均为int）。
stack<int> S; //建立一个栈
while( N!=0) { // N非零
i=N%B ; //从低到高，依次求得各位
N=N/B;
S.push(i); }//各位入栈
while ( !S.StackEmpty()) { //栈不空
{ i= S.pop();
If (i>9) i=’A’+10-i;
(4)定位到尾结点的前驱。
p=head;
while ( p->next->next ) p=p->next;
4.描述一下三个概念的区别：头指针，头结点，首元结点。并给予图示。
头指针：是一个指针变量，里面存储的是链表中首结点的地址，并以此来标识一个链表。
头结点：附加在第一个元素结点之前的一个结点，头指针指向头结点。
解：325641可以
154623不可以。
2.简述以下算法的功能（栈的元素类型为int）。
(1)statusalgo_1( SqStack S ){
inti, n, A [255];
n=0;
while(!S.StackEmpty() ){n++; A[n]= S.Pop();}
for( i=1; i<= n ; i++) S.Push(A[i]);
while { p->next && j<i-1 } {
p=p->next; j++ ; }
if ( !p->next || j>i-1 ); //定位失败
throw“删除位置不合理”;
else { //定位成功，进行结点删除
q=p->next;
x=p>data;
p->next=q->next;
delete q;
假设以数组sem存放循环队列的兀素冋时设变量rear和front分别作为队首队尾指针且队首指针指向队首前一个位置队尾指针指向队尾兀素处初始时rearfornt1写出这样设计的循环队列入队出队的算法
第
1.1有下列几种二元组表示的数据结构，试画出它们分别对应的图形表示，并指出它们分别属于何种结构。
(1) A= ( D，R )，其中，D = { a1，a2，a3，a4}，R={ }
case’)’//右括号
if (s.StackEmpty()) return 0; //栈空，不匹配，多右括号
else { s.Pop(); break; } //左括号出栈
}//switch
p++; //取表达式下一个字符
} // while
if (!s.StackEmpty()) //表达式结束，栈不空
x=x+y;
(3)
1.3指出下列个算法的功能，并求其时间复杂度。
(1) int sum1(int n)
{
int p=1,s=0;
for (int i=1;i<=n; i++)
{ p*= i; s+=p;}
return s;
}
(2) int sum2 (int n)
{ int s=0;
for ( int i=1; i<=n; i++)
int blank_match(char *exp) {用字符串存表达式
SqStack<char> s; //创建一个栈
char *p=exp; //工作指针p指向表达式首
while ( *p!=’=’) { //不是表达式结束符
switch(p) {
case’(’: //左括号，入栈
s.push(ch); break;
}
2.分析顺序表中元素定位算法int SqList<T>::Locate ( T e )的时间复杂度。
解：设表长为n，等概率下，每个元素被定位的概率为：p=1/n
定位成功第i个元素，需比较i次
3.对于有头结点的单链表，分别写出定位成功时，实现下列定位语句序列。
(1)定位到第i个结点ai；
p=head; j=0;
(3) AB&&EF ! ||
7.计算后缀表达式：4 5 * 3 2 + -的值。
解：15
8.将下列递推过程改写为递归过程。
void recursion( int n ) {
int i=n;
while( i>1) {
cout<<i; i--; }
}
解：void recurision(int j)
