当前位置：文档库 › 数据结构(C语言版)第三四章习题答案

数据结构(C语言版)第三四章习题答案

第3章栈和队列

习题

1．选择题

（1）若让元素1，2，3，4，5依次进栈，则出栈次序不可能出现在（）种情况。

A．5，4，3，2，1 B．2，1，5，4，3 C．4，3，1，2，5 D．2，3，5，4，1

（2）若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为（）。

A．i B．n-i C．n-i+1D．不确定（3）数组Ｑ［ｎ］用来表示一个循环队列，ｆ为当前队列头元素的前一位置，ｒ为队尾元素的位置，假定队列中元素的个数小于ｎ，计算队列中元素个数的公式为（）。

A．r-f B．(n+f-r)%n C．n+r-f D．（n+r-f)%n （4）链式栈结点为：(data,link)，top指向栈顶.若想摘除栈顶结点，并将删除结点的值保存到x中,则应执行操作（）。

A．x=top->data;top=top->link；B．top=top->link;x=top->link；

C．x=top;top=top->link；D．x=top->link；

（5）设有一个递归算法如下

int fact(int n) { //n大于等于0

if(n<=0) return 1;

else return n*fact(n-1); }

则计算fact(n)需要调用该函数的次数为（）。

A． n+1 B． n-1 C．n D．n+2 （6）栈在（）中有所应用。

A．递归调用B．函数调用C．表达式求值D．前三个选项都有

（7）为解决计算机主机与打印机间速度不匹配问题，通常设一个打印数据缓冲区。主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是（）。

A．队列B．栈C．线性表D．有序表

（8）设栈S和队列Q的初始状态为空，元素e1、e2、e3、e4、e5和e6依次进入栈S，一个元素出栈后即进入Q，若6个元素出队的序列是e2、e4、e3、e6、e5和e1，则栈S的容量至少应该是（）。

A．2 B．3 C．4 D．6

（9）在一个具有n个单元的顺序栈中，假设以地址高端作为栈底，以top作为栈顶指针，则当作进栈处理时，top的变化为（）。

A．top不变B．top=0 C．top-- D．top++ （10）设计一个判别表达式中左，右括号是否配对出现的算法，采用（）数据结构最佳。

A．线性表的顺序存储结构B．队列

C. 线性表的链式存储结构

D. 栈

（11）用链接方式存储的队列，在进行删除运算时（）。

A. 仅修改头指针

B. 仅修改尾指针

C. 头、尾指针都要修改

D. 头、尾指针可能都要修改

（12）循环队列存储在数组A[0..m]中，则入队时的操作为（）。

A. rear=rear+1

B. rear=(rear+1)%(m-1)

C. rear=(rear+1)%m

D. rear=(rear+1)%(m+1)

（13）最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是（）。

A. (rear+1)%n==front

B. rear==front

C．rear+1==front D. (rear-l)%n==front

（14）栈和队列的共同点是（）。

A. 都是先进先出

B. 都是先进后出

C. 只允许在端点处插入和删除元素

D. 没有共同点

（15）一个递归算法必须包括（）。

A. 递归部分

B. 终止条件和递归部分

C. 迭代部分

D. 终止条件和迭代部分

（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

}

（3）设从键盘输入一整数的序列：a1, a2, a3，…，a n，试编写算法实现：用栈结构存储输入的整数，当a i≠-1时，将a i进栈；当a i=-1时，输出栈顶整数并出栈。算法应对异常情况（入栈满等）给出相应的信息。

#define maxsize 栈空间容量

void InOutS(int s[maxsize])

//s是元素为整数的栈，本算法进行入栈和退栈操作。

{int top=0; //top为栈顶指针，定义top=0时为栈空。

for(i=1; i<=n; i++) //n个整数序列作处理。

{scanf(“%d”,&x); //从键盘读入整数序列。

if(x!=-1) // 读入的整数不等于-1时入栈。

if(top==maxsize-1){printf(“栈满\n”);exit(0);}else s[++top]=x; //x入栈。

else//读入的整数等于-1时退栈。

{if(top==0){printf(“栈空\n”);exit(0);} else printf(“出栈元素是%d\n”,s[top--])；}}

}//算法结束。

（4）从键盘上输入一个后缀表达式，试编写算法计算表达式的值。规定：逆波兰表达式的长度不超过一行，以$符作为输入结束，操作数之间用空格分隔,操作符只可能有+、-、*、/四种运算。例如：234 34+2*$。

[题目分析]逆波兰表达式(即后缀表达式)求值规则如下：设立运算数栈OPND,对表达式从左到右扫描(读入)，当表达式中扫描到数时，压入OPND栈。当扫描到运算符时，从OPND退出两个数，进行相应运算，结果再压入OPND栈。这个过程一直进行到读出表达式结束符$，这时OPND栈中只有一个数，就是结果。

float expr( )

//从键盘输入逆波兰表达式，以‘$’表示输入结束，本算法求逆波兰式表达式的值。

｛float OPND[30]; // OPND是操作数栈。

init(OPND); //两栈初始化。

float num=0.0; //数字初始化。

scanf (“%c”,&x);//x是字符型变量。

while(x!=’$’)

{switch

{case‘0’<=x<=’9’:while((x>=’0’&&x<=’9’)||x==’.’) //拼数

if(x!=’.’) //处理整数

{num=num*10+（ord(x)-ord(‘0’)）; scanf(“%c”,&x);}

else//处理小数部分。

{scale=10.0; scanf(“%c”,&x);

while(x>=’0’&&x<=’9’)

{num=num+(ord(x)-ord(‘0’)/scale;

scale=scale*10; scanf(“%c”,&x); }

}//else

push(OPND,num); num=0.0;//数压入栈，下个数初始化

case x=‘’:break; //遇空格，继续读下一个字符。

case x=‘+’:push(OPND,pop(OPND)+pop(OPND));break;

case x=‘-’:x1=pop(OPND);x2=pop(OPND);push(OPND,x2-x1);break;

case x=‘*’:push(OPND,pop(OPND)*pop(OPND));break;

case x=‘/’:x1=pop(OPND);x2=pop(OPND);push(OPND,x2/x1);break;

default: //其它符号不作处理。

}//结束switch

scanf(“%c”,&x);//读入表达式中下一个字符。

}//结束while（x！=‘$’）

printf(“后缀表达式的值为%f”,pop(OPND));

}//算法结束。

[算法讨论]假设输入的后缀表达式是正确的，未作错误检查。算法中拼数部分是核心。若遇到大于等于‘0’且小于等于‘9’的字符，认为是数。这种字符的序号减去字符‘0’的序号得出数。对于整数，每读入一个数字字符，前面得到的部分数要乘上10再加新读入的数得到新的部分数。当读到小数点，认为数的整数部分已完，要接着处理小数部分。小数部分的数要除以10（或10的幂数）变成十分位，百分位，千分位数等等，与前面部分数相加。在拼数过程中，若遇非数字字符，表示数已拼完，将数压入栈中，并且将变量num 恢复为0，准备下一个数。这时对新读入的字符进入‘+’、‘-’、‘*’、‘/’及空格的判断，因此在结束处理数字字符的case后，不能加入break语句。

（5）假设以I和O分别表示入栈和出栈操作。栈的初态和终态均为空，入栈和出栈的操作序列可表示为仅由I和O组成的序列，称可以操作的序列为合法序列，否则称为非法序列。

①下面所示的序列中哪些是合法的？

A. IOIIOIOO

B. IOOIOIIO

C. IIIOIOIO

D. IIIOOIOO

②通过对①的分析，写出一个算法，判定所给的操作序列是否合法。若合法，返回true，否则返回false（假定被判定的操作序列已存入一维数组中）。

①A和D是合法序列，B和C 是非法序列。

②设被判定的操作序列已存入一维数组A中。

int Judge(char A[])

//判断字符数组A中的输入输出序列是否是合法序列。如是，返回true，否则返回false。

{i=0; //i为下标。

j=k=0; //j和k分别为I和字母O的的个数。

while(A[i]!=‘\0’) //当未到字符数组尾就作。

{switch(A[i])

{case‘I’: j++; break; //入栈次数增1。

case‘O’: k++; if(k>j){printf(“序列非法\n”)；exit(0);}

}

i++; //不论A[i]是‘I’或‘O’，指针i均后移。}

if(j!=k) {printf(“序列非法\n”)；return(false);}

else{printf(“序列合法\n”)；return(true);}

}//算法结束。

[算法讨论]在入栈出栈序列（即由‘I’和‘O’组成的字符串）的任一位置，入栈次数（‘I’的个数）都必须大于等于出栈次数（即‘O’的个数），否则视作非法序列，立即给出信息，退出算法。整个序列（即读到字符数组中字符串的结束标记‘\0’），入栈次数必须等于出栈次数（题目中要求栈的初态和终态都为空），否则视为非法序列。

(6）假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素站点(注意不设头指针) ，试编写相应的置空队、判队空、入队和出队等算法。

算法如下：

//先定义链队结构:

typedef struct queuenode{

Datatype data;

struct queuenode *next;

}QueueNode; //以上是结点类型的定义

typedef struct{

queuenode *rear;

}LinkQueue; //只设一个指向队尾元素的指针

(1)置空队

void InitQueue( LinkQueue *Q)

{ //置空队：就是使头结点成为队尾元素

QueueNode *s;

Q->rear = Q->rear->next;//将队尾指针指向头结点

while (Q->rear!=Q->rear->next)//当队列非空，将队中元素逐个出队

{s=Q->rear->next;

Q->rear->next=s->next;

free(s);

}//回收结点空间

}

(2)判队空

int EmptyQueue( LinkQueue *Q)

{ //判队空

//当头结点的next指针指向自己时为空队

return Q->rear->next->next==Q->rear->next;

}

(3)入队

void EnQueue( LinkQueue *Q, Datatype x)

{ //入队

//也就是在尾结点处插入元素

QueueNode *p=(QueueNode *) malloc (sizeof(QueueNode));//申请新结点p->data=x; p->next=Q->rear->next;//初始化新结点并链入

Q-rear->next=p;

Q->rear=p;//将尾指针移至新结点

}

(4)出队

Datatype DeQueue( LinkQueue *Q)

{//出队,把头结点之后的元素摘下

Datatype t;

QueueNode *p;

if(EmptyQueue( Q ))

Error("Queue underflow");

p=Q->rear->next->next; //p指向将要摘下的结点

x=p->data; //保存结点中数据

if (p==Q->rear)

{//当队列中只有一个结点时，p结点出队后，要将队尾指针指向头结点

Q->rear = Q->rear->next; Q->rear->next=p->next;}

else

Q->rear->next->next=p->next;//摘下结点p

free(p);//释放被删结点

return x;

}

（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]; //返回队头元素的值

}

(8）如果允许在循环队列的两端都可以进行插入和删除操作。要求：

①写出循环队列的类型定义；

②写出“从队尾删除”和“从队头插入”的算法。

[题目分析] 用一维数组v[0..M-1]实现循环队列，其中M是队列长度。设队头指针front和队尾指针rear，约定front指向队头元素的前一位置，rear指向队尾元素。定义front=rear时为队空，(rear+1)%m=front 为队满。约定队头端入队向下标小的方向发展，队尾端入队向下标大的方向发展。

（1）#define M 队列可能达到的最大长度

typedef struct

{ elemtp data[M];

int front,rear;

} cycqueue;

（2）elemtp delqueue ( cycqueue Q)

//Q是如上定义的循环队列，本算法实现从队尾删除，若删除成功，返回被删除元素，

否则给出出错信息。

{ if(Q.front==Q.rear) {printf(“队列空”); exit(0);}

Q.rear=(Q.rear-1+M)%M; //修改队尾指针。

return(Q.data[(Q.rear+1+M)%M]); //返回出队元素。

}//从队尾删除算法结束

void enqueue (cycqueue Q, elemtp x)

// Q是顺序存储的循环队列，本算法实现“从队头插入”元素x。

{if (Q.rear==(Q.front-1+M)%M) {printf(“队满”; exit(0);)

Q.data[Q.front]=x; //x 入队列

Q.front=(Q.front-1+M)%M; //修改队头指针。

}// 结束从队头插入算法。

（9）已知Ackermann函数定义如下:

①写出计算Ack(m,n)的递归算法，并根据此算法给出出Ack(2,1)的计算过程。

②写出计算Ack(m,n)的非递归算法。

int Ack(int m,n)

{if (m==0) return(n+1);

else if(m!=0&&n==0) return(Ack(m-1,1));

else return(Ack(m-1,Ack(m,m-1));

}//算法结束

（1）Ack(2,1)的计算过程

Ack(2,1)=Ack(1,Ack(2,0)) //因m<>0,n<>0而得

=Ack(1,Ack(1,1)) //因m<>0,n=0而得

=Ack(1,Ack(0,Ack(1,0))) // 因m<>0,n<>0而得

= Ack(1,Ack(0,Ack(0,1))) // 因m<>0,n=0而得

=Ack(1,Ack(0,2)) // 因m=0而得

=Ack(1,3) // 因m=0而得

=Ack(0,Ack(1,2)) //因m<>0,n<>0而得

= Ack(0,Ack(0,Ack(1,1))) //因m<>0,n<>0而得

= Ack(0,Ack(0,Ack(0,Ack(1,0)))) //因m<>0,n<>0而得

= Ack(0,Ack(0,Ack(0,Ack(0,1)))) //因m<>0,n=0而得

= Ack(0,Ack(0,Ack(0,2))) //因m=0而得

= Ack(0,Ack(0,3)) //因m=0而得

= Ack(0,4) //因n=0而得

=5 //因n=0而得

（2）int Ackerman( int m, int n)

{int akm[M][N];int i,j;

for(j=0;j

for(i=1;i

{akm[i][0]=akm[i-1][1];

for(j=1;j

akm[i][j]=akm[i-1][akm[i][j-1]];

}

return(akm[m][n]);

}//算法结束

（10）已知f为单链表的表头指针, 链表中存储的都是整型数据，试写出实现下列运算的递归算法：

①求链表中的最大整数；

②求链表的结点个数；

③求所有整数的平均值。

#include //定义在头文件"RecurveList.h"中

class List;

class ListNode {//链表结点类

friend class List;

private:

int data;//结点数据

ListNode *link;//结点指针

ListNode ( const int item ) : data(item), link(NULL) { }//构造函数

};

class List { //链表类

private:

ListNode *first, current;

int Max ( ListNode *f );

int Num ( ListNode *f );

float Avg ( ListNode *f, int&n );

public:

List ( ) : first(NULL), current (NULL) { }//构造函数

~List ( ){ }//析构函数

ListNode* NewNode ( const int item );//创建链表结点, 其值为item

void NewList ( const int retvalue );//建立链表, 以输入retvalue结束

void PrintList ( );//输出链表所有结点数据

int GetMax ( ) { return Max ( first ); }//求链表所有数据的最大值

int GetNum ( ) { return Num ( first ); }//求链表中数据个数

float GetAvg ( ) { return Avg ( first ); }//求链表所有数据的平均值};

ListNode* List:: NewNode ( const int item ) {//创建新链表结点

ListNode *newnode = new ListNode (item);

return newnode;

}

void List::NewList ( const int retvalue ) {//建立链表, 以输入retvalue结束first = NULL; int value;ListNode *q;

cout << "Input your data:\n"; //提示

cin >> value; //输入

while ( value != retvalue ) { //输入有效

q = NewNode ( value ); //建立包含value的新结点

if ( first == NULL ) first = current = q;//空表时, 新结点成为链表第一个结点

else {current->link = q;current = q; } //非空表时, 新结点链入链尾

cin >> value;//再输入

}

current->link = NULL; //链尾封闭

}

void List::PrintList ( ) {//输出链表

cout << "\nThe List is : \n";

ListNode *p = first;

while ( p != NULL ) { cout << p->data << ' '; p = p->link; }

cout << ‘\n’;

}

int List ::Max ( ListNode *f ) {//递归算法: 求链表中的最大值if ( f ->link == NULL ) return f ->data; //递归结束条件

int temp = Max ( f ->link );//在当前结点的后继链表中求最大值

if ( f ->data > temp ) return f ->data;//如果当前结点的值还要大, 返回当前检点值

else return temp;//否则返回后继链表中的最大值}

int List ::Num ( ListNode *f ) {//递归算法: 求链表中结点个数if ( f == NULL ) return 0;//空表, 返回0

return 1+ Num ( f ->link );//否则, 返回后继链表结点个数加1 }

float List :: Avg ( ListNode *f , int&n ) {//递归算法: 求链表中所有元素的平均值

if ( f ->link == NULL ) //链表中只有一个结点, 递归结束条件{n = 1; return ( float ) (f ->data ); }

else { float Sum = Avg ( f ->link, n ) * n;n++;return ( f ->data + Sum ) / n; } }

#include "RecurveList.h" //定义在主文件中

int main ( int argc, char* argv[ ] ) {

List test; int finished;

cout << “输入建表结束标志数据：”;

cin >> finished;//输入建表结束标志数据

test.NewList ( finished );//建立链表

test.PrintList ( );//打印链表

cout << "\nThe Max is : " << test.GetMax ( );

cout << "\nThe Num is : " << test.GetNum ( );

cout << "\nThe Ave is : " << test.GetAve () << '\n';

printf ( "Hello World!\n" );

return 0;

}

第4章串、数组和广义表

习题

1．选择题

（1）串是一种特殊的线性表，其特殊性体现在（）。

A．可以顺序存储B．数据元素是一个字符

C．可以链式存储D．数据元素可以是多个字符若

（2）串下面关于串的的叙述中，（）是不正确的？

A．串是字符的有限序列B．空串是由空格构成的串

C．模式匹配是串的一种重要运算D．串既可以采用顺序存储，也可以采用链式存储

（3）串“ababaaababaa”的next数组为（）。

A．012345678999 B．012121111212 C．011234223456 D．0123012322345

（4）串“ababaabab”的nextval为（）。

A．010104101 B．010102101 C．010100011 D．010101011

（5）串的长度是指（）。

A．串中所含不同字母的个数B．串中所含字符的个数

C．串中所含不同字符的个数D．串中所含非空格字符的个数

（6）假设以行序为主序存储二维数组A=array[1..100,1..100]，设每个数据元素占2个存储单元，基地址为10，则LOC[5,5]=（）。

A．808 B．818 C．1010 D．1020 （7）设有数组A[i,j]，数组的每个元素长度为3字节，i的值为1到8，j的值为1到10，数组从内存首地址BA开始顺序存放，当用以列为主存放时，元素A[5,8]的存储首地址为（）。

A．BA+141 B．BA+180 C．BA+222 D．BA+225 （8）设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（）。

A．13 B．33 C．18 D．40

（9）若对n阶对称矩阵A以行序为主序方式将其下三角形的元素(包括主对角线上所有元素)依次存放于一维数组B[1..(n(n+1))/2]中，则在B中确定a ij（i

A．i*(i-1)/2+j B．j*(j-1)/2+i C．i*(i+1)/2+j D．j*(j+1)/2+i （10）A[N，N]是对称矩阵，将下面三角（包括对角线）以行序存储到一维数组T[N(N+1)/2]中，则对任一上三角元素a[i][j]对应T[k]的下标k是（）。

A．i(i-1)/2+j B．j(j-1)/2+i C．i(j-i)/2+1 D．j(i-1)/2+1 （11）设二维数组A[1.. m，1.. n]（即m行n列）按行存储在数组B[1.. m*n]中，

则二维数组元素A[i,j]在一维数组B中的下标为（）。

A．(i-1)*n+j B．(i-1)*n+j-1 C．i*(j-1) D．j*m+i-1

（12）数组A[0..4,-1..-3,5..7]中含有元素的个数（）。

A．55 B．45 C．36 D．16

（13）广义表A=(a,b,(c,d),(e,(f,g)))，则Head(Tail(Head(Tail(Tail(A)))))的值为（）。

A．(g) B．(d) C．c D．d

（14）广义表((a,b,c,d))的表头是（），表尾是（）。

A．a B．( ) C．(a,b,c,d) D．(b,c,d)

（15）设广义表L=((a,b,c))，则L的长度和深度分别为（）。

A．1和1 B．1和3 C．1和2 D．2和3

（1）已知模式串t=‘abcaabbabcab’写出用KMP法求得的每个字符对应的next 和nextval函数值。

（2）设目标为t=“abcaabbabcabaacbacba”,模式为p=“abcabaa”

①计算模式p的naxtval函数值；

②不写出算法,只画出利用KMP算法进行模式匹配时每一趟的匹配过程。

①p的nextval函数值为0110132。（p的next函数值为0111232）。

②利用KMP(改进的nextval)算法，每趟匹配过程如下：

第一趟匹配：abcaabbabcabaacbacba

abcab(i=5,j=5)

第二趟匹配：abcaabbabcabaacbacba

abc(i=7,j=3)

第三趟匹配：abcaabbabcabaacbacba

a(i=7,j=1)

第四趟匹配：abcaabbabcabaac bacba

(成功) abcabaa(i=15,j=8)

（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]）；

｝// 算法结束。

（6）写一个递归算法来实现字符串逆序存储，要求不另设串存储空间。

[题目分析]实现字符串的逆置并不难，但本题“要求不另设串存储空间”来实现字符串逆序存储，即第一个输入的字符最后存储，最后输入的字符先存储，使用递归可容易做到。

void InvertStore(char A[])

//字符串逆序存储的递归算法。

{ char ch;

static int i = 0;//需要使用静态变量

scanf ("%c",&ch);

if (ch!= '.') //规定'.'是字符串输入结束标志

{InvertStore(A);

A[i++] = ch;//字符串逆序存储

}

A[i] = '\0'; //字符串结尾标记

}//结束算法InvertStore。

（7）编写算法，实现下面函数的功能。函数void insert(char*s,char*t,int pos)将字符串t插入到字符串s中，插入位置为pos。假设分配给字符串s的空间足够让字符串t插

入。（说明：不得使用任何库函数）

[题目分析]本题是字符串的插入问题，要求在字符串s的pos位置，插入字符串t。首先应查找字符串s的pos位置，将第pos个字符到字符串s尾的子串向后移动字符串t的长度，然后将字符串t复制到字符串s的第pos位置后。

对插入位置pos要验证其合法性，小于1或大于串s的长度均为非法，因题目假设给字符串s的空间足够大，故对插入不必判溢出。

void insert(char *s,char *t,int pos)

//将字符串t插入字符串s的第pos个位置。

{int i=1,x=0; char *p=s,*q=t; //p，q分别为字符串s和t的工作指针

if(pos<1) {printf(“pos参数位置非法\n”);exit(0);}

while(*p!=’\0’&&i

//若pos小于串s长度，则查到pos位置时，i=pos。

if(*p == '/0') {printf("%d位置大于字符串s的长度",pos);exit(0);}

else//查找字符串的尾

while(*p!= '/0') {p++; i++;} //查到尾时，i为字符‘\0’的下标，p也指向‘\0’。

while(*q!= '\0') {q++; x++; } //查找字符串t的长度x，循环结束时q指向'\0'。

for(j=i;j>=pos ;j--){*(p+x)=*p; p--;}//串s的pos后的子串右移，空出串t的位置。

q--; //指针q回退到串t的最后一个字符

for(j=1;j<=x;j++) *p--=*q--; //将t串插入到s的pos位置上[算法讨论] 串s的结束标记('\0')也后移了，而串t的结尾标记不应插入到s中。

（8）已知字符串S1中存放一段英文，写出算法format(s1,s2,s3,n),将其按给定的长度n格式化成两端对齐的字符串S2, 其多余的字符送S3。

[题目分析]本题要求字符串s1拆分成字符串s2和字符串s3，要求字符串s2“按给定长度n格式化成两端对齐的字符串”，即长度为n且首尾字符不得为空格字符。算法从左到右扫描字符串s1，找到第一个非空格字符，计数到n，第n个拷入字符串s2的字符不得为空格，然后将余下字符复制到字符串s3中。

void format (char *s1,*s2,*s3)

//将字符串s1拆分成字符串s2和字符串s3，要求字符串s2是长n且两端对齐{char *p=s1, *q=s2;

int i=0;

while(*p!= '\0' && *p== ' ') p++;//滤掉s1左端空格

if(*p== '\0') {printf("字符串s1为空串或空格串\n");exit(0); }

while( *p!='\0' && i

if(*p =='\0'){ printf("字符串s1没有%d个有效字符\n",n); exit(0);}

if(*(--q)==' ' ) //若最后一个字符为空格，则需向后找到第一个非空格字符

{p-- ; //p指针也后退

while(*p==' '&&*p!='\0') p++;//往后查找一个非空格字符作串s2的尾字符

if(*p=='\0') {printf("s1串没有%d个两端对齐的字符串\n",n); exit(0); }

*q=*p; //字符串s2最后一个非空字符

*(++q)='\0'; //置s2字符串结束标记

}

*q=s3;p++; //将s1串其余部分送字符串s3。

while (*p!= '\0') {*q=*p; q++; p++;}

*q='\0'; //置串s3结束标记

}

(9)设二维数组a[1..m, 1..n] 含有m*n 个整数。

①写一个算法判断a中所有元素是否互不相同?输出相关信息(yes/no)；

②试分析算法的时间复杂度。

[题目分析]判断二维数组中元素是否互不相同，只有逐个比较,找到一对相等的元素，就可结论为不是互不相同。如何达到每个元素同其它元素比较一次且只一次？在当前行，每个元素要同本行后面的元素比较一次（下面第一个循环控制变量p的for循环），然后同第i+1行及以后各行元素比较一次，这就是循环控制变量k和p的二层for循环。

int JudgEqual(ing a[m][n],int m,n)

//判断二维数组中所有元素是否互不相同，如是，返回1；否则，返回0。

{for(i=0;i

for(j=0;j

{ for(p=j+1;p

if(a[i][j]==a[i][p]) {printf(“no”); return(0); }

//只要有一个相同的，就结论不是互不相同

for(k=i+1;k

for(p=0;p

if(a[i][j]==a[k][p]) {printf(“no”); return(0); }

}// for(j=0;j

printf(yes”); return(1); //元素互不相同

}//算法JudgEqual结束

（2）二维数组中的每一个元素同其它元素都比较一次，数组中共m*n个元素，第1个元素同其它m*n-1个元素比较，第2个元素同其它m*n-2 个元素比较，……，第m*n-1个元素同最后一个元素(m*n)比较一次,所以在元素互不相等时总的比较次数为(m*n-1)+(m*n-2)+…+2+1=（m*n）(m*n-1)/2。在有相同元素时,可能第一次比较就相同,也可能最后一次比较时相同,设在(m*n-1)个位置上均可能相同,这时的平均比较次数约为（m*n）(m*n-1)/4，总的时间复杂度是O(n4)。

(10)设任意n个整数存放于数组A(1:n)中，试编写算法，将所有正数排在所有负数前面（要求算法复杂性为0(n)）。

[题目分析]本题属于排序问题，只是排出正负，不排出大小。可在数组首尾设两个指针i和j，i自小至大搜索到负数停止，j自大至小搜索到正数停止。然后i和j所指数据交换，继续以上过程，直到i=j为止。

void Arrange(int A[],int n)

//n个整数存于数组A中，本算法将数组中所有正数排在所有负数的前面

{int i=0,j=n-1,x; //用类C编写，数组下标从0开始

while(i

{while(i0) i++;

while(i

if(i

}

}//算法Arrange结束.

[算法讨论]对数组中元素各比较一次，比较次数为n。最佳情况(已排好,正数在前,负数在后)不发生交换，最差情况(负数均在正数前面)发生n/2次交换。用类c编写，数组界偶是0..n-1。空间复杂度为O(1).

数据结构C语言版期末考试试题(有答案)

“数据结构”期末考试试题一、单选题(每小题2分，共12分) 1．在一个单链表HL中，若要向表头插入一个由指针p指向的结点，则执行( )。 A． HL＝ps p一>next＝HL B． p一>next＝HL；HL＝p3 C． p一>next＝Hl；p＝HL； D． p一>next＝HL一>next;HL一>next＝p； 2．n个顶点的强连通图中至少含有( )。 A.n—l条有向边 B.n条有向边 C.n(n—1)／2条有向边 D.n(n一1)条有向边 3.从一棵二叉搜索树中查找一个元素时，其时间复杂度大致为( )。 A.O(1) B.O(n) C.O(1Ogzn) D.O(n2) 4．由权值分别为3，8，6，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为( )。 A．24 B．48 C． 72 D． 53 5．当一个作为实际传递的对象占用的存储空间较大并可能需要修改时，应最好把它说明为( )参数，以节省参数值的传输时间和存储参数的空间。 A.整形 B.引用型 C.指针型 D.常值引用型· 6．向一个长度为n的顺序表中插人一个新元素的平均时间复杂度为( )。 A．O(n) B．O(1) C．O(n2) D．O(10g2n) 二、填空题(每空1分，共28分) 1．数据的存储结构被分为——、——、——和——四种。 2．在广义表的存储结构中，单元素结点与表元素结点有一个域对应不同，各自分别为——域和——域。 3．——中缀表达式 3十x*(2.4／5—6)所对应的后缀表达式为————。 4．在一棵高度为h的3叉树中，最多含有——结点。 5．假定一棵二叉树的结点数为18，则它的最小深度为——，最大深度为——· 6．在一棵二叉搜索树中，每个分支结点的左子树上所有结点的值一定——该结点的值，右子树上所有结点的值一定——该结点的值。 7．当向一个小根堆插入一个具有最小值的元素时，该元素需要逐层——调整，直到被调整到——位置为止。 8．表示图的三种存储结构为——、——和———。 9．对用邻接矩阵表示的具有n个顶点和e条边的图进行任一种遍历时，其时间复杂度为——，对用邻接表表示的图进行任一种遍历时，其时间复杂度为——。 10．从有序表(12，18，30，43，56，78，82，95)中依次二分查找43和56元素时，其查找长度分别为——和——· 11．假定对长度n＝144的线性表进行索引顺序查找，并假定每个子表的长度均

数据结构c语言版试题大全含答案

1 绪论沈阳理工大学应用技术学院信息与控制学院计算机科学与技术教研室 2011-5-8

数据结构(c语言版)期末考试复习试题

《数据结构与算法》（c语言版）期末考复习题一、选择题。 1．在数据结构中，从逻辑上可以把数据结构分为 C 。 A．动态结构和静态结构B．紧凑结构和非紧凑结构 C．线性结构和非线性结构D．内部结构和外部结构 2．数据结构在计算机内存中的表示是指 A 。 A．数据的存储结构B．数据结构C．数据的逻辑结构D．数据元素之间的关系 3．在数据结构中，与所使用的计算机无关的是数据的 A 结构。 A．逻辑B．存储C．逻辑和存储D．物理 4．在存储数据时，通常不仅要存储各数据元素的值，而且还要存储 C 。A．数据的处理方法B．数据元素的类型 C．数据元素之间的关系D．数据的存储方法 5．在决定选取何种存储结构时，一般不考虑 A 。 A．各结点的值如何B．结点个数的多少 C．对数据有哪些运算D．所用的编程语言实现这种结构是否方便。 6．以下说法正确的是 D 。 A．数据项是数据的基本单位

B．数据元素是数据的最小单位 C．数据结构是带结构的数据项的集合 D．一些表面上很不相同的数据可以有相同的逻辑结构 7．算法分析的目的是 C ，算法分析的两个主要方面是 A 。（1）A．找出数据结构的合理性B．研究算法中的输入和输出的关系C．分析算法的效率以求改进C．分析算法的易读性和文档性（2）A．空间复杂度和时间复杂度B．正确性和简明性 C．可读性和文档性D．数据复杂性和程序复杂性 8．下面程序段的时间复杂度是O(n2) 。 s =0; for( I =0; i

数据结构c语言版期末考试复习试题

《数据结构与算法》复习题一、选择题。 1在数据结构中，从逻辑上可以把数据结构分为 C 。 A ?动态结构和静态结构B.紧凑结构和非紧凑结构 C.线性结构和非线性结构 D.内部结构和外部结构 2?数据结构在计算机内存中的表示是指_A_。 A .数据的存储结构B.数据结构 C .数据的逻辑结构 D .数据元素之间的关系 3.在数据结构中，与所使用的计算机无关的是数据的A结构。 A .逻辑 B .存储C.逻辑和存储 D .物理 4.在存储数据时，通常不仅要存储各数据元素的值，而且还要存储_C A .数据的处理方法 B .数据元素的类型 C.数据元素之间的关系 D .数据的存储方法 5.在决定选取何种存储结构时，一般不考虑A A .各结点的值如何C.对数据有哪些运算 B .结点个数的多少 D .所用的编程语言实现这种结构是否方 6.以下说法正确的是D A .数据项是数据的基本单位 B .数据元素是数据的最小单位 C.数据结构是带结构的数据项的集合 D .一些表面上很不相同的数据可以有相同的逻辑结构 7.算法分析的目的是 C ，算法分析的两个主要方面是 A 。 (1) A .找出数据结构的合理性B.研究算法中的输入和输出的关系 C .分析算法的效率以求改进C.分析算法的易读性和文档性 (2) A .空间复杂度和时间复杂度B.正确性和简明性 &下面程序段的时间复杂度是0( n2) s =0; for( I =0; i

数据结构(C语言版)期末复习

数据结构（C语言版）期末复习汇总第一章绪论数据结构：是一门研究非数值计算程序设计中的操作对象，以及这些对象之间的关系和操作的学科。数据结构分为：逻辑结构、物理结构、操作三部分逻辑结构：集合、线性结构、树形结构、图（网）状结构物理结构（存储结构）：顺序存储结构、链式存储结构算法：是为了解决某类问题而规定的一个有限长的操作序列。算法五个特性：有穷性、确定性、可行性、输入、输出评价算法优劣的基本标准（4个）：正确性、可读性、健壮性、高效性及低存储量语句频度的计算。算法的时间复杂度：常见有：O(1)，O(n)，O(n2)，O(log2n)，O(nlog2n)，O(2n) 第二章线性表线性表的定义和特点：线性表：由n(n≥0)个数据特性相同的元素构成的有限序列。线性表中元素个数n(n≥0)定义为线性表的长度，n=0时称为空表。非空线性表或线性结构，其特点：（1）存在唯一的一个被称作“第一个”的数据元素；（2）存在唯一的一个被称作“最有一个”的数据元素；（3）除第一个之外，结构中的每个数据元素均只有一个前驱；（4）除最后一个之外，结构中的每个数据元素均只有一个后继。顺序表的插入：共计n个元素，在第i位插入，应移动（n-i+1）位元素。顺序表的删除：共计n个元素，删除第i位，应移动（n-i）位元素。线性表的两种存储方式：顺序存储、链式存储。顺序存储概念：以一组连续的存储空间存放线性表；优点：逻辑相邻，物理相邻；可随机存取任一元素；存储空间使用紧凑；缺点：插入、删除操作需要移动大量的元素；预先分配空间需按最大空间分配，利用不充分；表容量难以扩充；操作：查找、插入、删除等查找： ListSearch(SqlList L,ElemType x,int n) { int i; for (i=0;i

数据结构复习题集答案(c语言版严蔚敏)

人生难得几回搏，此时不搏更待何时？第1章绪论 1.1 简述下列术语：数据数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型解：数据是对客观事物的符号表示在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称数据元素是数据的基本单位在计算机程序常作为一个整体进行考虑和处理数据对象是性质相同的数据元素的集合是数据的一个子集数据结构是相互之间存在一种或多种特定关系的数据元素的集合存储结构是数据结构在计算机中的表示数据类型是一个值的集合和定义在这个值集上的一组操作的总称抽象数据类型是指一个数学模型以及定义在该模型上的一组操作是对一般数据类型的扩展 1.2 试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别解：抽象数据类型包含一般数据类型的概念但含义比一般数据类型更广、更抽象一般数据类型由具体语言系统部定义直接提供给编程者定义用户数据因此称它们为预定义数据类型抽象数据类型通常由编程者定义包括定义它所使用的数据和在这些数据上所进行的操作在定义抽象数据类型中的数据部分和操作部分时要求只定义到数据的逻辑结构和操作说明不考虑数据的存储结构和操作的具体实现这样抽象层次更高更能为其他用户提供良好的使用接口 1.3 设有数据结构(D R) 其中

试按图论中图的画法惯例画出其逻辑结构图解： 1.4 试仿照三元组的抽象数据类型分别写出抽象数据类型复数和有理数的定义（有理数是其分子、分母均为自然数且分母不为零的分数）解： ADT Complex{ 数据对象：D={r i|r i为实数} 数据关系：R={} 基本操作： InitComplex(&C re im) 操作结果：构造一个复数C 其实部和虚部分别为re和im DestroyCmoplex(&C) 操作结果：销毁复数C Get(C k &e) 操作结果：用e返回复数C的第k元的值 Put(&C k e) 操作结果：改变复数C的第k元的值为e IsAscending(C) 操作结果：如果复数C的两个元素按升序排列则返回1 否则返回0 IsDescending(C) 操作结果：如果复数C的两个元素按降序排列则返回1 否则返回0 Max(C &e) 操作结果：用e返回复数C的两个元素中值较大的一个 Min(C &e) 操作结果：用e返回复数C的两个元素中值较小的一个

数据结构(第4版)习题及实验参考答案数据结构复习资料完整版(c语言版)

数据结构基础及深入及考试复习资料习题及实验参考答案见附录结论 1、数据的逻辑结构是指数据元素之间的逻辑关系。即从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。 2、数据的物理结构亦称存储结构，是数据的逻辑结构在计算机存储器内的表示（或映像）。它依赖于计算机。存储结构可分为4大类：顺序、链式、索引、散列 3、抽象数据类型：由用户定义，用以表示应用问题的数据模型。它由基本的数据类型构成，并包括一组相关的服务（或称操作）。它与数据类型实质上是一个概念，但其特征是使用与实现分离，实行封装和信息隐蔽（独立于计算机）。 4、算法：是对特定问题求解步骤的一种描述，它是指令的有限序列，是一系列输入转换为输出的计算步骤。 5、在数据结构中，从逻辑上可以把数据结构分成（ C ） A、动态结构和表态结构 B、紧凑结构和非紧凑结构 C、线性结构和非线性结构 D、内部结构和外部结构 6、算法的时间复杂度取决于（ A ） A、问题的规模 B、待处理数据的初态 C、问题的规模和待处理数据的初态线性表 1、线性表的存储结构包括顺序存储结构和链式存储结构两种。 2、表长为n的顺序存储的线性表，当在任何位置上插入或删除一个元素的概率相等时，插入一个元素所需移动元素的平均次数为（ E ），删除一个元素需要移动的元素的个数为（ A ）。 A、(n-1)/2 B、n C、n+1 D、n-1 E、n/2 F、(n+1)/2 G、(n-2)/2 3、“线性表的逻辑顺序与存储顺序总是一致的。”这个结论是（ B ） A、正确的 B、错误的 C、不一定，与具体的结构有关 4、线性表采用链式存储结构时，要求内存中可用存储单元的地址（ D ） A、必须是连续的 B、部分地址必须是连续的C一定是不连续的D连续或不连续都可以 5、带头结点的单链表为空的判定条件是（ B ） A、head==NULL B、head->next==NULL C、head->next=head D、head!=NULL 6、不带头结点的单链表head为空的判定条件是（ A ） A、head==NULL B、head->next==NULL C、head->next=head D、head!=NULL 7、非空的循环单链表head的尾结点P满足（ C ） A、p->next==NULL B、p==NULL C、p->next==head D、p==head 8、在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是（ B ） A、O(1) B、O(n) C、O(n2) D、O(nlog2n) 9、在一个单链表中，若删除p所指结点的后继结点，则执行（ A ）

数据结构C语言版期末考试题库单选题

一、单项选择 1 . 数据在计算机内有链式和顺序两种存储方式，在存储空间使用的灵活性上，连式存储比顺序存储要 A . 低 B . 高 C . 相同 D . 不好说 2 . 通常对数组进行的两种基本操作是（） A . 建立与删除 B . 索引和修改 C . 查找和修改 D . 查找与索引 3 . 如果F是由有序树T转换而来的二叉树，那么T中结点的前序就是F 中结点的（）。 A . 中序 B . 前序 C . 层次序 D . 后序 4 . 由树的定义，具有3个结点的树有（）种形态 A . 2 B . 3 C . 4 D . 5 5 . 以下说法错误的是 ( ) A . 二叉树可以是空集 B . 二叉树的任一结点都有两棵子树 C . 二叉树与树具有相同的

树形结构 D . 二叉树中任一结点的两棵子树有次序之分 6 . 若节点的存储地址与其关键字之间存在某种映射关系，则称这种存储结构为 A . 顺序存储结构 B . 链式存储结构 C . 索引存储结构 D . 散列存储结构 7 . 已知二叉树的前序遍历访问顺序是abdgcefh,中序遍历访问顺序是dgbaechf,则其后序遍历的结点访问顺序是（） A . bdgcefha B . gdbecfha C . bdgaechf D . gdbehfca 8 . 算法分析的两个主要方面 A . 空间复杂度和时间复杂度 B . 正确性和简明性 C . 可读性和文档性 D . 数据复杂性和程序复杂性 9 . 设顺序线性表的长度为30，分成5块，每块6个元素，如果采用分块查找，则其平均查找长度为（）。 (A) 6 (B) 11 (C) 5 (D) 6.5 A . B . C . D . 10 . 若邻接表中有奇数个表节点，则一定（） A . 图中有奇数个顶点 B . 图中有偶数个顶点 C . 图为无向图 D . 图为有向图

数据结构C语言版(第2版)严蔚敏人民邮电出版社课后习题答案

数据结构（C语言版）（第2版）课后习题答案李冬梅 2015.3

目录第1章绪论 (1) 第2章线性表 (5) 第3章栈和队列 (13) 第4章串、数组和广义表 (26) 第5章树和二叉树 (33) 第6章图 (43) 第7章查找 (54) 第8章排序 (65)

第1章绪论 1．简述下列概念：数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型。答案：数据：是客观事物的符号表示，指所有能输入到计算机中并被计算机程序处理的符号的总称。如数学计算中用到的整数和实数，文本编辑所用到的字符串，多媒体程序处理的图形、图像、声音、动画等通过特殊编码定义后的数据。数据元素：是数据的基本单位，在计算机中通常作为一个整体进行考虑和处理。在有些情况下，数据元素也称为元素、结点、记录等。数据元素用于完整地描述一个对象，如一个学生记录，树中棋盘的一个格局（状态）、图中的一个顶点等。数据项：是组成数据元素的、有独立含义的、不可分割的最小单位。例如，学生基本信息表中的学号、姓名、性别等都是数据项。数据对象：是性质相同的数据元素的集合，是数据的一个子集。例如：整数数据对象是集合N={0，±1，±2，…}，字母字符数据对象是集合C={‘A’，‘B’，…，‘Z’，‘a’，‘b’，…，‘z’}，学生基本信息表也可是一个数据对象。数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。换句话说，数据结构是带“结构”的数据元素的集合，“结构”就是指数据元素之间存在的关系。逻辑结构：从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。因此，数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。存储结构：数据对象在计算机中的存储表示，也称为物理结构。抽象数据类型：由用户定义的，表示应用问题的数学模型，以及定义在这个模型上的一组操作的总称。具体包括三部分：数据对象、数据对象上关系的集合和对数据对象的基本操作的集合。 2．试举一个数据结构的例子，叙述其逻辑结构和存储结构两方面的含义和相互关系。答案：例如有一张学生基本信息表，包括学生的学号、姓名、性别、籍贯、专业等。每个学生基本信息记录对应一个数据元素，学生记录按顺序号排列，形成了学生基本信息记录的线性序列。对于整个表来说，只有一个开始结点(它的前面无记录)和一个终端结点(它的后面无记录)，其他的结点则各有一个也只有一个直接前趋和直接后继。学生记录之间的这种关系就确定了学生表的逻辑结构，即线性结构。这些学生记录在计算机中的存储表示就是存储结构。如果用连续的存储单元(如用数组表示)来存放这些记录，则称为顺序存储结构；如果存储单元不连续，而是随机存放各个记录，然后用指针进行链接，则称为链式存储结构。即相同的逻辑结构，可以对应不同的存储结构。 3．简述逻辑结构的四种基本关系并画出它们的关系图。

数据结构(c语言版)课后习题答案完整版

第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(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

《数据结构(C语言描述)》期末试卷要点

专业《数据结构（C 语言描述）》期末试卷（ — 学年第学期）一、填空(10分) 1、一个m 阶B-树中，每个结点最少有( ceil(m/2) )个儿子结点,m 阶B+树中每个结点(除根外)最多有( m )个儿子结点. 2、n(n>0)个结点构成的二叉树，叶结点最多有( floor((n+1)/2) )个，最少有( 1 )个。若二叉树有m 个叶结点，则度为2的结点有( m-1 )个。 3、顺序查找方法适用于存储结构为( 顺序表和线性链表 )的线性表，使用折半查找方法的条件是(查找表为顺序存贮的有序表 ) 4、广义表A=(( )，(a ，(b ，c))，d)的表尾Gettail(A)为( ((a,(b,c)),d) ) 5、直接插入排序，起泡排序和快速排序三种方法中，( 快速排序 )所需的平均执行时间最小；( 快速排序 )所需附加空间最大。二、选择(10分) 1、倒排文件的主要优点是：( C ) A 、便于进行插入和删除 B 、便于进行文件的合并 C 、能大大提高基于非主关键字数据项的查找速度 D 、易于针对主关键字的逆向检索 2 下面程序段的时间复杂性为( C ) y=0; while(n>=(y+1)*(y+1)) { y++; } A 、O(n) B 、O(n 2) C 、 O(sqrt(n)) D 、 O(1) 3、若从二叉树的任一结点出发到根的路径上所经过的结点序列按其关键字有序，则该二叉树是( C ) A 、二叉排序树 B 、哈夫曼树 C 、堆 D 、AVL 树 4、栈和队列都是（ B ） A 、顺序存储的线性结构 B 、限制存取点的线性结构 C 、链式存储的线性结构 D 、限制存取点的非线性结构 5、用顺序查找方法查找长度为n 的线性表时，在等概率情况下的平均查找长度为（ D ） A 、n B 、n/2 C 、(n-1)/2 D 、(n+1)/2 三、简答（30分） 1、已知一棵二叉树的前序扫描序列和中序扫描序列分别为ABCDEFGHIJ 和BCDAFEHJIG ，试给出该二叉树的后序序列并绘出该二叉树对应的森林。院（系）班级姓名学号 ……………………………………………装…………………………订………………………线……………………………………………

严蔚敏数据结构题集(C语言版)完整答案.doc

严蔚敏数据结构C 语言版答案详解第1章绪论 1.1 简述下列术语：数据，数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。解：数据是对客观事物的符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。数据对象是性质相同的数据元素的集合，是数据的一个子集。数据结构是相互之间存在一种或多种特定关系的数据元素的集合。存储结构是数据结构在计算机中的表示。数据类型是一个值的集合和定义在这个值集上的一组操作的总称。抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。是对一般数据类型的扩展。 1.2 试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。解：抽象数据类型包含一般数据类型的概念，但含义比一般数据类型更广、更抽象。一般数据类型由具体语言系统内部定义，直接提供给编程者定义用户数据，因此称它们为预定义数据类型。抽象数据类型通常由编程者定义，包括定义它所使用的数据和在这些数据上所进行的操作。在定义抽象数据类型中的数据部分和操作部分时，要求只定义到数据的逻辑结构和操作说明，不考虑数据的存储结构和操作的具体实现，这样抽象层次更高，更能为其他用户提供良好的使用接口。 1.3 设有数据结构(D,R)，其中 {}4,3,2,1d d d d D =，{}r R =，()()(){}4,3,3,2,2,1d d d d d d r = 试按图论中图的画法惯例画出其逻辑结构图。解： 1.4 试仿照三元组的抽象数据类型分别写出抽象数据类型复数和有理数的定义（有理数是其分子、分母均为自然数且分母不为零的分数）。解： ADT Complex{ 数据对象：D={r,i|r,i 为实数} 数据关系：R={} 基本操作： InitComplex(&C,re,im) 操作结果：构造一个复数C ，其实部和虚部分别为re 和im DestroyCmoplex(&C) 操作结果：销毁复数C Get(C,k,&e) 操作结果：用e 返回复数C 的第k 元的值

数据结构(c语言版)复习资料

数据结构复习资料一、填空题 1. 数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和运算等的学科。 2. 数据结构被形式地定义为（D, R），其中D是数据元素的有限集合，R是D上的关系有限集合。 3. 数据结构包括数据的逻辑结构、数据的存储结构和数据的运算这三个方面的内容。 4. 数据结构按逻辑结构可分为两大类，它们分别是线性结构和非线性结构。 5. 线性结构中元素之间存在一对一关系，树形结构中元素之间存在一对多关系，图形结构中元素之间存在多对多关系。 6．在线性结构中，第一个结点没有前驱结点，其余每个结点有且只有 1个前驱结点；最后一个结点没有后续结点，其余每个结点有且只有1个后续结点。 7. 在树形结构中，树根结点没有前驱结点，其余每个结点有且只有 1个前驱结点；叶子结点没有后续结点，其余每个结点的后续结点数可以任意多个。 8. 在图形结构中，每个结点的前驱结点数和后续结点数可以任意多个。 9．数据的存储结构可用四种基本的存储方法表示，它们分别是顺序、链式、索引和散列。 10. 数据的运算最常用的有5种，它们分别是插入、删除、修改、查找、排序。 11. 一个算法的效率可分为时间效率和空间效率。

12. 在顺序表中插入或删除一个元素，需要平均移动表中一半元素，具体移动的元素个数与表长和该元素在表中的位置有关。 13. 线性表中结点的集合是有限的，结点间的关系是一对一的。 14. 向一个长度为n的向量的第i个元素(1≤i≤n+1)之前插入一个元素时，需向后移动n-i+1 个元素。 15. 向一个长度为n的向量中删除第i个元素(1≤i≤n)时，需向前移动n-i 个元素。 16. 在顺序表中访问任意一结点的时间复杂度均为 O(1)，因此，顺序表也称为随机存取的数据结构。 17. 顺序表中逻辑上相邻的元素的物理位置必定相邻。单链表中逻辑上相邻的元素的物理位置不一定相邻。 18．在单链表中，除了首元结点外，任一结点的存储位置由其直接前驱结点的链域的值指示。 19．在n个结点的单链表中要删除已知结点*p，需找到它的前驱结点的地址，其时间复杂度为O（n）。 20. 向量、栈和队列都是线性结构，可以在向量的任何位置插入和删除元素；对于栈只能在栈顶插入和删除元素；对于队列只能在队尾插入和队首删除元素。 21. 栈是一种特殊的线性表，允许插入和删除运算的一端称为栈顶。不允许插入和删除运算的一端称为栈底。 22. 队列是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。 23. 不包含任何字符（长度为0）的串称为空串；由一个或多个空格（仅由空格符）组成的串称为空白串。 24. 子串的定位运算称为串的模式匹配；被匹配的主串称为目标串，子串称为模式。

数据结构c语言版期末考试复习试题

《数据结构与算法》复习题一、选择题。 1．在数据结构中，从逻辑上可以把数据结构分为 C 。 A．动态结构和静态结构B．紧凑结构和非紧凑结构 C．线性结构和非线性结构D．内部结构和外部结构 2．数据结构在计算机内存中的表示是指 A 。 A．数据的存储结构B．数据结构C．数据的逻辑结构D．数据元素之间的关系3．在数据结构中，与所使用的计算机无关的是数据的 A 结构。 A．逻辑B．存储C．逻辑和存储D．物理 4．在存储数据时，通常不仅要存储各数据元素的值，而且还要存储 C 。 A．数据的处理方法B．数据元素的类型 C．数据元素之间的关系D．数据的存储方法 5．在决定选取何种存储结构时，一般不考虑 A 。 A．各结点的值如何B．结点个数的多少 C．对数据有哪些运算D．所用的编程语言实现这种结构是否方便。 6．以下说法正确的是 D 。 A．数据项是数据的基本单位 B．数据元素是数据的最小单位 C．数据结构是带结构的数据项的集合 D．一些表面上很不相同的数据可以有相同的逻辑结构 7．算法分析的目的是 C ，算法分析的两个主要方面是 A 。（1）A．找出数据结构的合理性B．研究算法中的输入和输出的关系C．分析算法的效率以求改进C．分析算法的易读性和文档性（2）A．空间复杂度和时间复杂度B．正确性和简明性 C．可读性和文档性D．数据复杂性和程序复杂性 8．下面程序段的时间复杂度是O(n2) 。 s =0; for( I =0; i

数据结构C语言版章节练习题

数据结构章节练习题第一章绪论一、单选题 1.一个数组元素a[i]与________的表示等价。 A、*(a+i) B、a+i C、*a+i D、&a+i 2.下面程序段的时间复杂度为____________。 for(int i=0; i

数据结构教案C语言版

数据结构教案C语言版 Last updated on the afternoon of January 3, 2021

课程教案课程名称：数据结构授课教师：学习对象：任课时间：一、学生情况分析数据结构是计算机专业的一门核心专业课程。学生在前期的学习中已经学习了C语言程序设计课程。通过本课程学习使学生对提高编写程序的能力以及解决实际问题的能力。二、课程教学目标《数据结构》是计算机学科中一门核心专业基础课。主要介绍如何合理地组织数据、有效地存储和处理数据，正确地设计算法以及对算法的分析和评价。通过本课程的学习，使学生深透地理解数据结构的逻辑结构和物理结构的基本概念以及有关算法，培养基本的、良好的程序设计技能，编制高效可靠的程序，为学习操作系统、编译原理和数据库等课程奠定基础。三、课程教学内容第一章绪论教学内容： 1）什么是数据结构

2）抽象数据类型概念；数据类型；数据抽象与抽象数据类型；用于描述数据结构的语言 3）数据结构的抽象层次 4）算法定义 5）性能分析与度量；算法的性能标准；算法的后期测试；算法的事前估计；空间复杂度度量；时间复杂度度量；时间复杂度的渐进表示法；教学要求：了解：数据结构基本概念及数据结构的抽象层次了解：抽象数据类型概念了解：算法的定义及算法特性掌握：算法的性能分析与度量方法第二章线性表教学内容： 1）线性表的定义和特点 2）线性表的顺序存储及查找、插入和删除操作 3）线性表的链式存储及查找、插入和删除操作 4）使用线性表的实例教学要求：了解：线性表的定义和特点熟练掌握：线性表的顺序存储结构的查找、插入和删除等基本操作熟练掌握：单链表、循环链表及双向链表的定义及实现掌握：熟练掌握单链表的应用方法

数据结构C语言版习题参考答案

附录习题参考答案习题1参考答案 1.1.选择题 (1). A. (2). A. (3). A. (4). B.,C. (5). A. (6). A. (7). C. (8). A. (9). B. (10.) A. 1.2.填空题 (1). 数据关系 (2). 逻辑结构物理结构 (3). 线性数据结构树型结构图结构 (4). 顺序存储链式存储索引存储散列表（Hash）存储 (5). 变量的取值范围操作的类别 (6). 数据元素间的逻辑关系数据元素存储方式或者数据元素的物理关系 (7). 关系网状结构树结构 (8). 空间复杂度和时间复杂度 (9). 空间时间 (10). Ο(n) 1.3 名词解释如下：数据：数据是信息的载体，是计算机程序加工和处理的对象，包括数值数据和非数值数据。数据项：数据项指不可分割的、具有独立意义的最小数据单位，数据项有时也称为字段或域。数据元素：数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理，一个数据元素可由若干个数据项组成。数据逻辑结构：数据的逻辑结构就是指数据元素间的关系。数据存储结构：数据的物理结构表示数据元素的存储方式或者数据元素的物理关系。数据类型：是指变量的取值范围和所能够进行的操作的总和。算法：是对特定问题求解步骤的一种描述，是指令的有限序列。 1.4 语句的时间复杂度为： (1) Ο(n2) (2) Ο(n2) (3) Ο(n2) (4) Ο(n-1) (5) Ο(n3) 1.5 参考程序： main() { int X,Y,Z； scanf(“%d, %d, %d”,&X,&Y,Z)； if (X>=Y) if(X>=Z) if (Y>=Z) { printf(“%d, %d, %d”,X,Y,Z);} else { printf(“%d, %d, %d”,X,Z,Y);}

数据结构(c语言版)课后习题答案完整版资料

第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(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