当前位置:文档之家› 数据结构(第3版)习题答案

数据结构(第3版)习题答案

数据结构(第3版)习题答案
数据结构(第3版)习题答案

十二五普通高等教育国家级本科规划教材

第1章绪论

高等学校精品资源共享课程

什么是数据结构

【答】:数据结构是指按一定的逻辑结构组成的一批数据,使用某种存储结构将这批数据存储于计算机中,并在这些数据上定义了一个运算集合。

数据结构涉及哪几个方面

【答】:数据结构涉及三个方面的内容,即数据的逻辑结构、数据的存储结构和数据的运算集合。

两个数据结构的逻辑结构和存储结构都相同,但是它们的运算集合中有一个运算的定义不

一样,它们是否可以认作是同一个数据结构为什么

【答】:不能,运算集合是数据结构的重要组成部分,不同的运算集合所确定的数据结构是不一样的,例如,栈与队列它们的逻辑结构与存储结构可以相同,但由于它们的运算集合不一样,所以它们是两种不同的数据结构。

线性结构的特点是什么非线性结构的特点是什么

【答】:线性结构元素之间的关系是一对一的,在线性结构中只有一个开始结点和一个终端结点,其他的每一个结点有且仅有一个前驱和一个后继结点。而非线性结构则没有这个特点,元素之间的关系可以是一对多的或多对多的。

数据结构的存储方式有哪几种

【答】:数据结构的存储方式有顺序存储、链式存储、散列存储和索引存储等四种方式。

算法有哪些特点它和程序的主要区别是什么

【答】:算法具有(1)有穷性(2)确定性(3)0 个或多个输入(4)1 个或多个输出(5)可行性等特征。程序是算法的一种描述方式,通过程序可以在计算机上实现算法。

抽象数据类型的是什么它有什么特点

【答】:抽象数据类型是数据类型的进一步抽象,是大家熟知的基本数据类型的延伸和发展。抽象数据类型是与表示无关的数据类型,是一个数据模型及定义在该模型上的一组运算。对一个抽象数据类型进行定义时,必须给出它的名字及各运算的运算符名,即函数名,并且规定这些函数的参数性质。一旦定义了一个抽象数据类型及具体实现,程序设计中就可以像使用基本数据类型那样,十分方便地使用抽象数据类型。抽象数据类型的设计者根据这些描述给出操作的具体实现,抽象数据类型的使用者依据这些描述使用抽象数据类型。

算法的时间复杂度指的是什么如何表示

【答】:算法执行时间的度量不是采用算法执行的绝对时间来计算的,因为一个算法在不同的机器上执行所花的时间不一样,在不同时刻也会由于计算机资源占用情况的不同,使得算法在同一台计算机上执行的时间也不一样,另外,算法执行的时间还与输入数据的状态有关,所以对于算法的时间复杂性,采用算法执行过程中其基本操作的执行次数,称为计算量来度量。算

函数名称

1 logn n nlogn n n

2 n!

常数

对数

线性

n 个logn 平方

立方

指数

阶乘

十二五普通高等教育国家级本科规划教材高等学校精品资源共享课程

定义:f (n)=O (g (n)) 当且仅当存在正的常数 c 和n,使得对于所有的n≥n,有 f (n) ≤c g(n)。

上述定义表明,函数 f 顶多是函数g 的 c 倍,除非n 小于n。因此对于足够大的n (如n≥n),g 是f 的一个上限(不考虑常数因子c)。在为函数f 提供一个上限函数g 时,通常使用比较

简单的函数形式。比较典型的形式是含有n 的单个项(带一个常数系数)。表1-1 列出了一些

常用的g 函数及其名称。对于表1-1 中的对数函数logn,没有给出对数基,原因是对于任何大

于 1 的常数 a 和 b 都有logn =logn/loga,所以logn 和logn 都有一个相对的乘法系数1/loga,

其中 a 是一个常量。

表1-1 常用的渐进函数

【答】:算法的空间复杂度是指算法在执行过程中占用的额外的辅助空间的个数。可以将它表

示为问题规模的函数,并通过大写O符号表示空间复杂度。

对于下面的程序段,分析带下划线的语句的执行次数,并给出它们的时间复杂度T(n)。

(1)i++ ;

(2)for(i=0;i

if (a[i]

(3)for(i=0;i

for(j=0;j

printf(“%d”,i+j);

(4)for (i=1;i<=n-1;i++)

{ k=i;

for(j=i+1;j<=n;j++)

if(a[j]>a[j+1]) k=j;

t=a[k]; a[k]=a[i]; a[i]=t;

}

(5)for(i=0;i

for(j=0;j

{++x;s=s+x;}

【答】:(1)O(1);(2)O(n);(3)O(n);(4)O(n);(5)O(n)

十二五普通高等教育国家级本科规划教材高等学校精品资源共享课程第2章线性表及其顺序存储

选择题

(1)表长为n的顺序存储的线性表,当在任何位置上插入或删除一个元素的概率相等时,插入一个元素所需移动元素的平均个数为(

为( A )。

E),删除一个元素所需移动元素的平均个数

A.(n1)/2 E.n/2B.n

F.(n+1)/2

C.n+1

G.(n2)/2

D.n1

(2)设栈S和队列Q的初始状态为空,元素e1、e2、e3、e4、e5 和e6 依次通过栈S,一个元素出栈后即进入队列Q,若 6 个元素出队的序列为e2、e4、e3、e6、e5 和e1,则栈S 的容量至少应该为( C )。

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

(3)设栈的输入序列为1、2、3… n,若输出序列的第一个元素为n,则第i个输出的元素为( B )。

A.不确定B.ni+1C.i D.ni

(4)在一个长度为n 的顺序表中删除第i 个元素(1<=i<=n)时,需向前移动( A )个

元素。

A.ni B.ni+1C.ni1D.i

(5)若长度为n的线性表采用顺序存储结构存储,在第i个位置上插入一个新元素的时

间复杂度为( A )。

A.O(n)B.O(1)C.O(n)D.O(n)

(6)表达式a*(b+c)d 的后缀表达式是(B)。

A.abcd*+B.abc+*d C.abc*+d D.+*abcd

(7)队列是一种特殊的线性表,其特殊性在于( C )。

A.插入和删除在表的不同位置执行B.插入和删除在表的两端位置执行

C.插入和删除分别在表的两端执行D.插入和删除都在表的某一端执行(8)栈是一种特殊的线性表,具有( B )性质。

A.先进先出B.先进后出C.后进后出D.顺序进出(9)顺序循环队列中(数组的大小为n),队头指示front 指向队列的第 1 个元素,队尾指示rear 指向队列最后元素的后 1 个位置,则循环队列中存放了n 1 个元素,即循环队列满

的条件为(B)。

A.(rear+1)%n=front1 C.(rear)%n=front B.(rear+1)%n=front D.rear+1=front

(10)顺序循环队列中(数组的大小为6),队头指示front 和队尾指示rear 的值分别为3和0,当从队列中删除 1 个元素,再插入 2 个元素后,front 和rear 的值分别为( D )。

A.5 和1B.2 和4C.1 和5D.4 和2

什么是顺序表什么是栈什么是队列

【答】:当线性表采用顺序存储结构时,即为顺序表。栈是一种特殊的线性表,它的特殊性表现在约定了在这种线性表中数据的插入与删除操作只能在这种线性表的同一端进行(即栈顶),因此,栈具有先进后出、后进先出的特点。队列也是一种特殊的线性表,它的特殊性表现在约定了在这种线性表中数据的插入在表的一端进行,数据的删除在表的另一端进行,因此队列具有先进先出,后进后出的特点。

设计一个算法,求顺序表中值为x 的结点的个数。

【答】:顺序表的存储结构定义如下(文件名):

#include <>

#define N 100 typedef int datatype; typedef struct {

datatype data[N];

int length;

} seqlist;/*预定义最大的数据域空间*/

/*假设数据类型为整型*/

/*此处假设数据元素只包含一个整型的关键字域*/ /*线性表长度*/

/*预定义的顺序表类型*/

算法countx(L,x)用于求顺序表L 中值为x 的结点的个数。

int countx(seqlist *L,datatype x)

{int c=0;

int i;

for (i=0;ilength;i++)

if (L->data[i]==x) c++;

return c;

}

设计一个算法,将一个顺序表倒置。即,如果顺序表各个结点值存储在一维数组 a 中,倒置的结果是使得数组 a 中的a[0]等于原来的最后一个元素,a[1] 等于原来的倒数第 2 个元素,…,a 的最后一个元素等于原来的第一个元素。

【答】:顺序表的存储结构定义同题,实现顺序表倒置的算法程序如下:

void verge(seqlist *L)

{int t,i,j;

i=0;

j=L->length-1;

while (i

{ t=L->data[i];

L->data[i++]=L->data[j];

L->data[j--]=t;

}

}

已知一个顺序表中的各结点值是从小到大有序的,设计一个算法,插入一个值为x 的结点,使顺序表中的结点仍然是从小到大有序。

【答】:顺序表的定义同题,实现本题要求的算法程序如下:

void insertx(seqlist *L,datatype x)

{int j;

if (L->length

{ j=L->length-1;

while (j>=0 && L->data[j]>x)

{ L->data[j+1]=L->data[j];

j--;

}

L->data[j+1]=x;

L->length++;

}

}

将下列中缀表达式转换为等价的后缀表达式。

(1) 5+6*7

(2) (5-6)/7

(3) 5-6*7*8

(4) 5*7-8

(5) 5*(7-6)+8/9

(6) 7*(5-6*8)-9

【答】:

(7) 5+6*7

(8) (5-6)/7

(9) 5-6*7*8

(10)5*7-8

(11)5*(7-6)+8/9

(12)7*(5-6*8)-9后缀表达式:5 6 7*+

后缀表达式:5 6-7/

后缀表达式:5 6 7*8*-后缀表达式:5 7* 8-

后缀表达式:5 7 6-*8 9/+后缀表达式:7 5 6 8*-*9-

循环队列存储在一个数组中,数组大小为n,队首指针和队尾指针分别为front 和rear,请

写出求循环队列中当前结点个数的表达式。

【答】:循环队列中当前结点个数的计算公式是:(n+rear-front)%n

编号为1,2,3,4 的四列火车通过一个栈式的列车调度站,可能得到的调度结果有哪些如果

有n 列火车通过调度站,请设计一个算法,输出所有可能的调度结果。

【答】:

方法一:

算法思想:逐次输出所有可能,用回溯法。即:

总体:对原始序列中的每一个元素,总是先入栈,后出栈

1.入栈后的操作:a.该元素出栈;b.下一个元素入栈;

2.出栈后的操作:a.(栈中其他元素)继续出栈;b. (原始序列中)下一个数入栈;

注意:回溯法,关键在于回溯,即在某分支结点X:处理X 的一个子分支,再退回分支X,

接着处理X 的下一个子分支,若所有X 的子分支处理完,再退回上一层分支节点。所谓“退回”,

实际上就是恢复。

程序代码:

#include <>

#define MAX 26

typedef struct s{

char a[MAX];

int top;

}Stack;

/*定义一些全局变量*/

Stack S; /*定义全局性的栈*/

char d[MAX],seq[MAX]; /*d[MAX]用于存储原始入栈序列,seq[MAX]用于存储输出序列*/ int len; /*定义将通过栈的元素个数*/

int count=0; /* 用于统计输出序列的个数*/

void initStack(Stack *S) /*初始化空栈*/

{ S->top=-1; }

void push(Stack *S, char x) /*进栈*/

{if (S->top>=MAX) return;

S->top++;

S->a[S->top]=x;

}

char pop(Stack *S)/*出栈*/

{if (S->top==-1)

{ printf("ERROR, POP Empty Stack");

return -1;

}

S->top--;

return S->a[S->top+1];

}

int isEmpty(Stack *S)/*判断栈是否为空*/

{if (S->top==-1) return 1;

return 0;

}

void outSeq(char *seq, int len)/*输出顶点序列*/

{int i;

for(i=0; i

printf("%2c",seq[i]);

printf("\n");

}

void scheduler(int pos, int seq_pos)

{/*pos: 处理到原始数据中的第pos 个元素,

seq_pos:若出栈,应放在当前输出数组的第seq_pos 个位置*/

int i=0;char t;

/*对任何一个数,总是先进栈,再出栈。另外,这里不需要循环,类似于“查找数组中元素”用递归*/

if(pos

push(&S,d[pos]);

scheduler(pos+1,seq_pos);

pop(&S);

}

if (!isEmpty(&S)){/*一个数出栈后,有两种处理方式:要么继续出栈,要么继续下一个数的进

栈*/

t=pop(&S);

seq[seq_pos++]=t;

scheduler(pos,seq_pos);

push(&S,t);

}

if (pos>=len && isEmpty(&S))

{ outSeq(seq,len); count++; }

}

int main(){

int i;

printf("\nplease input the num be scheduled: ");

scanf("%d", &len); /*用len 存储待调度的火车数量*/

for(i=0; i

d[i]='a'+i; /*创建火车编号,如a、b、c、...等*/

printf("the original seq is:");

outSeq(d,len);

initStack(&S);

scheduler(0,0);

printf("\n count=%5d", count);

return 0;

}

方法二:

解题思路:栈具有先进后出、后进先出的特点,因此,任何一个调度结果应该是1,2,3,4 全排列中的一个元素。由于进栈的顺序是由小到大的,所以出栈序列应该满足以下条件:对

于序列中的任何一个数其后面所有比它小的数应该是倒序的,例如4321 是一个有效的出栈序

列,1423 不是一个有效的出栈结果(4 后面比它小的两个数2,3 不是倒序)。据此,本题可以通过算法产生n 个数的全排列,然后将满足出栈规则的序列输出。

产生n 个数的全排列有递归与非递归两种实现算法。

产生全排列的递归算法:

设R={r,r,…,r}是要进行排列的n 个元素,R=R-{r}。集合X 中元素的全排列记为

perm(X)。(r)perm(X)表示在全排列perm(X)的每一个排列前加上前缀r 得到的排列。R 的全排

列可归纳定义如下:

当n=1 时,perm(R)=(r),其中r 是集合R 中惟一的元素;

当n>1 时,perm(R)由(r)perm(R),(r)perm(R),…,(r)perm(R)构成。

依此递归定义,可设计产生perm(R)的递归算法如下:

递归解法:

#include<>

int cont=1;/*全局变量,用于记录所有可能的出栈序列个数*/

void print(int str[],int n);

/*求整数序列str[]从k 到n 的全排列*/

void perm(int str[],int k,int n)

{int i,temp;

if (k==n-1) print(str,n);

else

{ for (i=k;i

{temp=str[k]; str[k]=str[i]; str[i]=temp;

perm(str,k+1,n); /*递归调用*/

temp=str[i]; str[i]=str[k]; str[k]=temp;

}

}

}

/*本函数判断整数序列str[]是否满足进出栈规则,若满足则输出*/

void print(int str[],int n)

{int i,j,k,l,m,flag=1,b[2];

for(i=0;i

{ m=0;

for(j=i+1;j

if (str[i]>str[j]) {if (m==0) b[m++]=str[j];

else {if (str[j]>b[0]) {flag=0;}

else b[0]=str[j];

}

}

}

if(flag)/*满足出栈规则则输出str[]中的序列*/

{printf(" %2d:",cont++);

for(i=0;i

printf("%d",str[i]);

printf("\n");

}

}

int main()

{int str[100],n,i;

printf("input a int:"); /*输出排列的元素个数*/

scanf("%d",&n);

for(i=0;i

str[i]=i+1;

printf("input the result:\n");

perm(str,0,n);

printf("\n");

return 0;

}

当参与进出栈的元素个数为 4 时,输出的结果如下图所示。

该算法执行的时间复杂度为O(n!)。随着n 的增大,算法的执行效率非常的低。

非递归解法:()

对一组数穷尽所有排列,还可一种更直接的方法,将一个排列看作一个长整数,则所有排列对应着一组整数,将这组整数按从小到大的顺序排成一个数列,从对应最小的整数开始,按

数列的递增顺序逐一列举每个排列对应的每一个整数,这能更有效地完成排列的穷举。从一个

排列找出对应数列的下一个排列可在当前排列的基础上作部分调整来实现。倘若当前排列为

1,2,4,6,5,3,并令其对应的长整数为124653。要寻找比长整数124653 更大的排列,可从该排列的最后一个数字顺序向前逐位考察,当发现排列中的某个数字比它前一个数字大时,如本例中

的 6 比它的前一位数字 4 大,则说明还有可能对应更大整数的排列。但为顺序从小到大列举出所有的排列,不能立即调整得太大,如本例中将数字 6 与数字 4 交换得到的排列为126453 就不是排列124653 的下一个排列。为得到排列124653 的下一个排列,应从已考察过的那部分数

字中选出比数字 4 大,但又是它们中最小的那一个数字,比如数字5,与数字 4 交换。该数字也是从后向前考察过程中第一个比 4 大的数字,5 与 4 交换后,得到排列125643。在前面数字1,2,5 固定的情况下,还应选择对应最小整数的那个排列,为此还需将后面那部分数字的排

列颠倒,如将数字6,4,3 的排列顺序颠倒,得到排列1,2,5,3,4,6,这才是排列1,2,4,6,5,3 的下一个排列。按照以上想法可以编写非递归程序实现n 个数的全排列,对满足进出栈

规则的排列则计数并输出。

/*本程序输出1 2 ... n 个序列进栈出栈的序列*/

#include <>

int pl(int n)

{ int a[100];

int flag=1,flag1=0; FILE *rf ;

int i,j,k,x,count=0; rf = fopen("", "w") ; for (i=1;i<=n;i++)

a[i]=i; while (flag)

{ flag1=1;/*最大处理范围为99 个数*/

/* 用于存放进出栈序列结果*/

/*初始序列*/

/* 还剩余未输出的排列*/

/* 判断本次排列是否符合进栈出栈序列*/

for (i=1;i<=n;i++)

{ j=i+1;

while (j<=n && a[j]>a[i]) j++; /* 找a[i]后第一个比a[i]小的元素a[j]*/

k=j+1;

while (k<=n)/* 如果a[j]后还有比a[i]小且比a[j]大的元素,则此排列无效*/ {if ( a[k] a[j]) flag1=0;

k++;

}

}

if (flag1)

{ for (i=1;i<=n;i++)/*输出当前排列*/

{ printf("%4d",a[i]); fprintf(rf,"%4d",a[i]);}

printf("\n"); fprintf(rf,"\n");

count++; }

i=n;/*计数器加1*/

/*从后向前找相邻位置后大前小的元素值*/

while (i>1 && a[i]

if (i==1) flag=0; /*未找到则结束*/

else

{j=i-1;i=n;/* 若找到,则在该位置的后面从右向左找第一个比该元素大的值*/ while (i>j && a[i]

k=a[j];

a[j]=a[i];

a[i]=k;

k=j+1;

for ( i=k+1;i<=n;i++)/*交换两元素的值*/

/*对交换后后面的数据由小到大排序*/ /*插入排序*/

{j=i-1;

x=a[i];

while (j>=k && x

a[j+1]=x;

}

}

}

fclose(rf);

return count;

}

void main()

{int n,m=0;

/*返回排列总个数*/

printf("please input n:"); scanf("%d",&n);

m=pl(n);

printf("\nm=%d",m);/*输入排列规模*/

/*输出满足进出栈的排列总个数*/

}

程序运行时如果输入4,则输出的结果如下图所示。

该算法的时间复杂度也是O(n!)。

结论:如果n 个数按编号由小到大的顺序进栈,进栈的过程中可以出栈,则所有可能的出栈序

列的总数为:

(2n)! (n 1)n!n!

十二五普通高等教育国家级本科规划教材高等学校精品资源共享课程第3章线性表的链式存储

选择题

(1)两个有序线性表分别具有n个元素与m个元素且n≤m,现将其归并成一个有序表,其最少的比较次数是( A )。

A.n B.m C.n1D.m+n (2)非空的循环单链表head 的尾结点(由p 所指向)满足(C)。

A.p->next==NULL B.p==NULL C.p->next==head D.p==head (3)在带头结点的单链表中查找x应选择的程序体是( C )。

A.node *p=head->next; while (p && p->info!=x) p=p->next;

if (p->info==x)return p else return NULL;

B.node *p=head; while (p&& p->info!=x) p=p->next; return p;

C.node *p=head->next;while (p&&p->info!=x) p=p->next; return p;

D.node *p=head; while (p->info!=x) p=p->next ; return p;

(4)线性表若采用链式存储结构时,要求内存中可用存储单元的地址( D )。

A.必须是连续的C.一定是不连续的B.部分地址必须是连续的D.连续不连续都可以

(5)在一个具有n个结点的有序单链表中插入一个新结点并保持单链表仍然有序的时间复杂度是(B)。

A.O(1)B.O(n)C.O(n)D.O(n log)(6)用不带头结点的单链表存储队列时,其队头指针指向队头结点,其队尾指针指向队尾结点,则在进行删除操作时( D )。

A.仅修改队头指针

C.队头、队尾指针都要修改B.仅修改队尾指针

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

(7)若从键盘输入n个元素,则建立一个有序单向链表的时间复杂度为( B )。

A.O(n)B.O(n)C.O(n)D.O(n×log2)

(8)下面哪个术语与数据的存储结构无关( D )。

A.顺序表B.链表C.散列表D.队列

(9)在一个单链表中,若删除p 所指结点的后续结点,则执行( A )。

A.p->next=p->next->next; C.p->next=p->next;B.p=p->next; p->next=p->next->next; D.p =p->next->next;

(10)在一个单链表中,若p 所指结点不是最后结点,在p 之后插入s 所指结点,则执行( B )。

A.s->next=p;p->next=s; C.s->next=p->next;p=s;B.s->next=p->next;p->next=s; D.p->next=s;s->next=p;

设计一个算法,求一个单链表中的结点个数。【答】:单链表存储结构定义如下(相关文件:)#include <>

#include <>

typedef struct node

{ int data;

struct node *next;

}linknode;

typedef linknode *linklist;

/*尾插法创建带头结点的单链表*/

linklist creatlinklist()

{ linklist head,r,s;

int x;

head=r=(linklist)malloc(sizeof(linknode));

printf("\n 请输入一组以0 结束的整数序列:\n");

scanf("%d",&x);

while (x)

{ s=(linklist)malloc(sizeof(linknode));

s->data=x;

r->next=s;

r=s;

scanf("%d",&x);

}

r->next=NULL;

return head;

}

/*输出带头结点的单链表*/

void print(linklist head)

{ linklist p;

p=head->next;

printf("List is:\n");

while(p)

{ printf("%5d",p->data);

p=p->next;

}

printf("\n");

}

基于上述结构定义,求单链表中的结点个数的算法程序如下:int count(linklist head)

{int c=0;

linklist p=head;

while (p)

{c++;

p=p->next;

}

return c;

}

设计一个算法,求一个带头结点单链表中的结点个数。

【答】:带头结点的单链表的存储结构定义同题,实现本题功能的算法程序如下()

#include ""

int count(linklist head)

{ int c=0;

linklist p=head->next;

while (p)

{c++;

p=p->next;

}

return c;

}

main()/*测试函数*/

{linklist head;

head=creatlinklist();

print(head);

printf("\nLength of head is:%d",count(head));

getch();

}

当输入 5 个数据时,产生的输出结果如下图所示:

设计一个算法,在一个单链表中值为y 的结点前面插入一个值为x 的结点。即使值为x 的新结点成为值为y 的结点的前驱结点。

【答】:

#include ""

void insert(linklist head,int y,int x)

{/*在值为y 的结点前插入一个值为x 的结点*/

linklist pre,p,s;

pre=head;

}

while (p && p->data!=y)

{ pre=p;

p=p->next;

}

if (p)/*找到了值为y 的结点*/

{ s=(linklist)malloc(sizeof(linknode));

s->data=x;

s->next=p;

pre->next=s;

}

void main()

{linklist head;

int y,x;

head=creatlinklist();

print(head);

/*测试程序*/

/*创建单链表*/

/*输出单链表*/

printf("\n 请输入y 与x 的值:\n");

scanf("%d %d",&y,&x);

insert(head,y,x);

print(head);

}

程序的一种运行结果如下图所示:

设计一个算法,判断一个单链表中各个结点值是否有序。

【答】:

#include ""

int issorted(linklist head,char c)

/*当参数c=’a’时判断链表是否为升序,当参数c=’d’是判断链表是否为降序*/ { int flag=1;

linklist p=head->next;

switch (c)

}

while (p &&p->next && flag)

{if (p->data<=p->next->data) p=p->next;

else flag=0;

}

break;

case 'd':/*判断带头结点的单链表head 是否为降序*/

while (p &&p->next && flag)

{if (p->data>=p->next->data) p=p->next;

else flag=0;

}

break;

}

return flag;

int main()/*测试程序*/

{ linklist head;

head=creatlinklist();

print(head);

if (issorted(head,'a')) printf("单链表head 是升序排列的!\n");

else

if (issorted(head,'d')) printf("单链表head 是降序排列的!\n");

else printf("单链表head 是无序的!\n");

}

程序运行时的三种输出结果如下图所示:

设计一个算法,利用单链表原来的结点空间将一个单链表就地转置。【答】:

#include ""

void verge(linklist head)

十二五普通高等教育国家级本科规划教材

{/*本函数的功能是就地倒置带头结点的单链表*/

linklist p,q;

p=head->next;

head->next=NULL;

高等学校精品资源共享课程

while (p)/*每次从原表取一个结点插入到新表的最前面*/

{q=p;

p=p->next;

q->next=head->next;

head->next=q;

}

}

int main()

{linklist head;

head=creatlinklist(); print(head);

verge(head);

print(head);/*测试函数*/

/*创建单链表*/

/*输出原单链表*/

/*就地倒置单链表*/

/*输出倒置后的单链表*/

}

设计一个算法,将一个结点值自然数的单链表拆分为两个单链表,原表中保留值为偶数的结点,而值为奇数的结点按它们在原表中的相对次序组成一个新的单链表。

【答】:

#include ""

linklist sprit(linklist head)

{/*将带头结点的单链表head 中的奇数值结点删除生成新的单链表并返回*/ linklist L,pre,p,r;

L=r=(linklist)malloc(sizeof(linknode));

r->next=NULL;

pre=head;

p=head->next;

while (p)

{if (p->data%2==1)

{

pre->next=p->next;

r->next=p;

r=p;

p=pre->next;

}

/*删除奇数值结点*/

else

{pre=p;

/*保留偶数值结点*/

十二五普通高等教育国家级本科规划教材

}

高等学校精品资源共享课程

r->next=NULL;

return L;

}

int main()

{linklist head,L;

head=creatlinklist();

print(head);

L=sprit(head);

/*置链表结束标记*/

/*测试函数*/

/*创建单链表*/

/*输出原单链表*/

/*分裂单链表head*/

printf("\n 原单链表为:\n");

print(head);/*输出倒置后的单链表*/

printf("\n 分裂所得奇数单链表为:\n");

print(L);

}

本程序的一组测试情况如下图所示。

设计一个算法,对一个有序的单链表,删除所有值大于x 而不大于y 的结点。

【答】:

#include ""

void deletedata(linklist head,datatype x,datatype y)

{/*删除带头结点单链表中所有结点值大于x 而不大于y 的结点*/

linklist pre=head,p,q;

p=head->next;/*初始化*/

while (p && p->data<=x)/*找第1 处大于x 的结点位置*/

{pre=p;

p=p->next;

}

while (p && p->data<=y)

p=p->next;

q=pre->next;

/*找第1 处小于y 的位置*/

/*删除大于x 而小于y 的结点*/

pre->next=p;

pre=q->next;

while (pre!=p)

{free(q);

q=pre;

pre=pre->next;

}

}

void main()

/*释放被删除结点所占用的空间*/ /*测试函数*/

{linklist head,L;

datatype x,y;

head=creatlinklist(); print(head);/*创建单链表*/ /*输出原单链表*/

printf("\n 请输入要删除的数据区间:\n");

scanf("%d%d",&x,&y);

deletedata(head,x,y);

print(head);/*输出删除后的单链表*/

}

设计一个算法,在双链表中值为y 的结点前面插入一个值为x 的新结点。即使值为x 的新结点成为值为y 的结点的前驱结点。

【答】:

首先定义双链表的数据结构,相关文件,内容如下:

typedef int datatype; /*预定义的数据类型*/

typedef struct dlink_node{ /*双链表结点定义*/

datatype data;

struct dlink_node *llink,*rlink;

}dnode;

typedef dnode* dlinklist;/*双链表结点指针类型定义*/

/*尾插法创建带头结点的双链表*/

dlinklist creatdlinklist(void)

{ dlinklist head,r,s;

datatype x;

head=r=(dlinklist) malloc(sizeof(dnode)); /*建立双链表的头结点*/

head->llink=head->rlink=NULL;

printf("\n 请输入双链表的内容:(整数序列,以0 结束)\n");

scanf("%d",&x);

while (x)/*输入结点值信息,以0 结束*/

{ s=(dlinklist ) malloc(sizeof(dnode));

s->data=x;

s->rlink=r->rlink;/*将新结点s 插入到双链表链尾*/

s->llink=r;

r->rlink=s;

r=s;

scanf("%d",&x);

}

return head;

}

/*输出双链表的内容*/

void print(dlinklist head)

{ dlinklist p;

p=head->rlink;

printf("\n 双链表的内容是:\n");

while (p)

{ printf("%5d",p->data);

p=p->rlink;

}

}

本题的求解程序如下:

#include <>

#include ""

void insertxaty(dlinklist head,datatype y,datatype x)

{ dlinklist s,p;

/*首先在双链表中找y 所在的结点,然后在y 前面插入新结点*/ p=head->rlink;

while (p && p->data!=y)

p=p->rlink;

if (!p) printf("\n 双链表中不存在值为y 的结点,无法插入新结点!\n"); else /*插入值为x 的新结点*/

{ s=(dlinklist)malloc(sizeof(dnode));

s->data=x;

s->rlink=p;

s->llink=p->llink;

p->llink->rlink=s;

p->llink=s;

}

}

void main()/*测试函数*/

{ dlinklist head;

datatype x,y;

数据结构第三章习题答案

第三章习题 1.按图3.1(b)所示铁道(两侧铁道均为单向行驶道)进行车厢调度,回答: ⑴如进站的车厢序列为123,则可能得到的出站车厢序列是什么? ⑵如进站的车厢序列为123456,能否得到435612和135426的出站序列,并说明原因。(即写出 以“S”表示进栈、以“X”表示出栈的栈操作序列)。 2.设队列中有A、B、C、D、E这5个元素,其中队首元素为A。如果对这个队列重复执行下列4步 操作: (1)输出队首元素; (2)把队首元素值插入到队尾; (3)删除队首元素; (4)再次删除队首元素。 直到队列成为空队列为止,得到输出序列: (1)A、C、E、C、C (2) A、C、E (3) A、C、E、C、C、C (4) A、C、E、C 3.给出栈的两种存储结构形式名称,在这两种栈的存储结构中如何判别栈空与栈满? 4.按照四则运算加、减、乘、除和幂运算(↑)优先关系的惯例,画出对下列算术表达式求值时操 作数栈和运算符栈的变化过程: A-B*C/D+E↑F 5.试写一个算法,判断依次读入的一个以@为结束符的字母序列,是否为形如‘序列1& 序列2’ 模式的字符序列。其中序列1和序列2中都不含字符’&’,且序列2是序列1的逆序列。例如,‘a+b&b+a’是属该模式的字符序列,而‘1+3&3-1’则不是。 6.假设表达式由单字母变量和双目四则运算算符构成。试写一个算法,将一个通常书写形式且书写 正确的表达式转换为逆波兰式。 7.假设以带头结点的循环链表表示队列,并且只设一个指针指向队尾元素结点(注意不设头指针), 试编写相应的队列初始化、入队列和出队列的算法。 8.要求循环队列不损失一个空间全部都能得到利用, 设置一个标志域tag , 以tag为0或1来区分 头尾指针相同时的队列状态的空与满,请编写与此结构相应的入队与出队算法。

数据结构试题库答案

数据结构试题及答案 一、单项选择题 (1)一个算法应该就是()。 A)程序???B)问题求解步骤得描述 C)要满足五个基本属性??D) A与C (2)算法指得就是()。 A)计算机程序???B)解决问题得计算方法 C)排序算法???D)解决问题得有限运算序列。 (3)与数据元素本身得形式、内容、相对位置、个数无关得就是数据得()。 A) 存储结构B) 逻辑结构C)算法D)操作 (4)从逻辑上可以把数据结构分为( )两大类。 A)动态结构、静态结构??B) 顺序结构、链式结构 C)线性结构、非线性结构???D)初等结构、构造型结构 (5)下列叙述中正确得就是()。 A)一个逻辑数据结构只能有一种存储结构 B)数据得逻辑结构属于线性结构,存储结构属于非线性结构 C)一个逻辑数据结构可以有多种存储结构,且各种存储结构不影响数据处理得效率 D)一个逻辑数据结构可以有多种存储结构,且各种存储结构影响数据处理得效率 (6)数据得基本单位就是() ?A) 数据项??B) 数据类型C)数据元素??D)数据变量 (7)下列程序得时间复杂度为() i=0;s=0; while(s

2017年数据结构期末考试题及答案A

2017年数据结构期末考试题及答案 一、选择题(共计50分,每题2分,共25题) 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. 在以下的叙述中,正确的是B ° A. 线性表的顺序存储结构优于链表存储结构 B. 二维数组是其数据元素为线性表的线性表 C?栈的操作方式是先进先出 D.队列的操作方式是先进后出

8. 通常要求同一逻辑结构中的所有数据元素具有相同的特性,这意味着 A. 数据元素具有同一特点 B. 不仅数据元素所包含的数据项的个数要相同,而且对应的数据项的类型要一致 C. 每个数据元素都一样 D. 数据元素所包含的数据项的个数要相等 9 ?链表不具备的特点是 A 。 A.可随机访问任一结点 B.插入删除不需要移动元素 C?不必事先估计存储空间 D.所需空间与其长度成正比 10. 若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一 个结点,则采用 D 存储方式最节省运算时间。 A.单链表B ?给出表头指针的单循环链表 C.双链表D ?带头结点 的双循环链表 11. 需要分配较大空间,插入和删除不需要移动元素的线性表,其存储结构是 B 。 A.单链表B .静态链表 C.线性链表 D .顺序存储结构 12 .非空的循环单链表head的尾结点(由p所指向)满足C 。 A. p—>next 一NULL B. p — NULL C. p—>next == head D. p = = head 13 .在循环双链表的p所指的结点之前插入s所指结点的操作是 D 。 A .p—> prior-> prior=s B .p—> prior-> n ext=s C.s —> prior—> n ext = s D.s —> prior—> prior = s 14 .栈和队列的共同点是C 。 A.都是先进后出 B .都是先进先出 C.只允许在端点处插入和删除元素 D .没有共同点

《数据结构》题库及答案

《数据结构》题库及答案 一、选择题 1.线性表的顺序存储结构是一种 的存储结构,线性表的链式存储结构是一种 的存储结构。 a. 随机存储; b.顺序存储; c. 索引存取; d. HASH 存取 2.一个栈的入栈序列是a,b,c,d,e ,则栈的不可能的输出序列是 。 a. edcba; b. decba; c. dceab; d.abcde 3.一个队列的入队序列是1,2,3,4,则队列的输出序列是 。 a. 4,3,2,1; b. 1,2,3,4; c. 1,4,3,2; d.3,2,4,1 4.在一个单链表中,已知p 结点是q 结点的直接前驱结点,若在p 和q 之间插入结点s ,则执行的操作是 。 a. s->nxet=p->next; p->next=s; b. p->next=s->next; s->next=p; c. q->next=s; s->next=p; d. p->next=s; s->next=q; 5.设有两个串p,q ,求q 在p 中首次出现的位置的运算称作 。 a.联接 b.模式匹配 c.求子串 d.求串长 6.二维数组M 的成员是6个字符(每个字符占一个存储单元)组成的串,行下标i 的范围从0到8,列下标j 的范围从1到10,则存放M 至少需要 个字节。 a. 90 b.180 c.240 d.540 7.在线索二叉树中,结点p 没有左子树的充要条件是 。 a. p->lch==NULL b. p->ltag==1 c. p->ltag==1且p->lch=NULL d. 以上都不对 8.在栈操作中,输入序列为(A ,B ,C ,D ),不可能得到的输出序列为:______ A 、(A , B , C , D ) B 、(D ,C ,B ,A ) C 、(A ,C ,D ,B ) D 、(C ,A ,B ,D ) 9.已知某二叉树的后序序列是dabec ,中序序列是debac ,则它的先序序列是 。 A 、acbed B 、decab C 、deabc D 、cedba 10.设矩阵A 是一个对称矩阵,为了节省存储空间,将其下三角部分(见下图)按行序存放在一维数组B[1..n(n-1)/2]中,对任一上三角部分元素)(j i a ij ,在一维数组B 的存放位置是 。

完整版数据结构习题集第3章栈和队列

第3章栈和队列 一、选择题 1.栈结构通常采用的两种存储结构是(A )。 A、顺序存储结构和链表存储结构 B、散列和索引方式 C、链表存储结构和数组 D、线性链表结构和非线性存储结构 2.设栈ST 用顺序存储结构表示,则栈ST 为空的条件是( B ) A、ST.top-ST.base<>0 B、ST.top-ST.base==0 C、ST.top-ST.base<>n D、ST.top-ST.base==n 3.向一个栈顶指针为HS 的链栈中插入一个s 结点时,则执行( C ) A、HS->next=s; B、s->next=HS->next;HS->next=s; C、s->next=HS;HS=s; D、s->next=HS;HS=HS->next; 4.从一个栈顶指针为HS 的链栈中删除一个结点,用x 保存被删除结点的值,则执行( C) A 、x=HS;HS=HS->next; B 、HS=HS->next;x=HS->data; C 、x=HS->data;HS=HS->next; D 、s->next=Hs;Hs=HS->next; 5.表达式a*(b+c)-d 的后缀表达式为( B ) A、abcdd+- B、abc+*d- C、abc*+d- D、-+*abcd 6.中缀表达式A-(B+C/D)*E 的后缀形式是( D ) A、AB-C+D/E* B、ABC+D/E* C、ABCD/E*+- D、ABCD/+E*- 7.一个队列的入列序列是1,2,3,4,则队列的输出序列是( B ) A、4,3,2,1 B、1,2,3,4 C、1,4,3,2 D、3,2,4,1 8.循环队列SQ 采用数组空间SQ.base[0,n-1]存放其元素值,已知其头尾指针分别是front 和rear,则判定此循环队列为空的条件是() A、Q.rear-Q.front==n B、Q.rear-Q.front-1==n C、Q.front==Q.rear D、Q.front==Q.rear+1 9.循环队列SQ 采用数组空间SQ.base[0,n-1]存放其元素值,已知其头尾指针分别是front 和rear,则判定此循环队列为满的条件是() A、Q.front==Q.rear B、Q.front!=Q.rear C、Q.front==(Q.rear+1)%n D、Q.front!=(Q.rear+1)%n 10.若在一个大小为6 的数组上实现循环队列,且当前rear 和front 的值分别为0 和3,当从 队列中删除一个元素,再加入两个元素后,rear 和front 的值分别为() A、1,5 B、2, 4 C、4,2 D、5,1 11.用单链表表示的链式队列的队头在链表的()位置 A、链头 B、链尾 C、链中 12.判定一个链队列Q(最多元素为n 个)为空的条件是() A、Q.front==Q.rear B、Q.front!=Q.rear C、Q.front==(Q.rear+1)%n D、Q.front!=(Q.rear+1)%n 13.在链队列Q 中,插入s 所指结点需顺序执行的指令是() A 、Q.front->next=s;f=s; B 、Q.rear->next=s;Q.rear=s;

数据结构考试题库

数据结构考试题库

绪论 一、填空题 1.数据的逻辑结构被分为集合、(线性结构)、(树形结构)和(图状结构)四种。 2.物理结构是数据结构在计算机中的表示,又称为(存储结构)。 3.数据元素的逻辑结构包括( 线性)、(树)和图状结构3种类型,树形结构和图状结构合称为(非线性结构)。 4.(数据元素)是数据的基本单位,(数据项)是数据不可分割的最小单位。 5.线性结构中元素之间存在(一个对一个)关系,树形结构中元素之间存在(一个对多个)关系,图状结构中元素之间存在(多个对多个)关系。 ?6.数据结构是一门研究非数值计算的程序设计问题中:计算机的(数据元素)以及它们之间的(关系)和(运筹)等的学科。 7.算法的五个重要特性为有穷性、确定性、(输入)、(输出)和(可行性)。 二、选择题 1.数据的不可分割的基本单位是(D)。 A.元素 B.结点 C.数据类型 D.数据项 *2.线性表的逻辑顺序与存储顺序总是一致的,这种说法(B)。 A.正确 B.不正确 C.不确定 D.无法选择 3.线性结构是指数据元素之间存在一种(D)。 精心整理,用心做精品2

A.一对多关系 B.多对多关系 C.多对一关系 D.一对一关系 4.在数据结构中,从逻辑上可以把数据结构分成(A)。 A.动态结构和静态结构 B.紧凑结构和非紧凑结构 C.线性结构和非线性结构 D.内部结构和外部结构 5.线性表若采用链式存储结构时,要求内存中可用存储单元的 地址( D)。 A.必须是连续的 B.部分地址必须是连续的 C.一定是不连续的 D.连续不连续都可以 三、简答题 1.算法的特性是什么。 答:有穷性确定性可行性有0或多个输入有1或多个输出线性结构 一、填空题 1.在一个长度为n的线性表中删除第i个元素(1≤i≤n)时,需向前移动(n-i)个元素。 2.从循环队列中删除一个元素时,其操作是(先移动队首指针,后取出元素)。 3.在线性表的单链接存储中,若一个元素所在结点的地址为p,则其后继结点的地址为(p->next)。 4.在一个单链表中指针p所指向结点的后面插入一个指针q所指向的结点时,首先把(p->next)的值赋给q->next,然后(q->date)的值赋给p->next。 5.从一个栈删除元素时,首先取出(栈顶元素),然后再使(栈顶指针)减1。 6.子串的定位操作通常称做串的(模式匹配)。 精心整理,用心做精品3

数据结构试题(含答案)

一.是非题 (正确的打“√”,错误的打“×”。) 1. 数据结构可用三元式表示(D,S,P)。其中:D是数据对象,S是D上的关系, P是对D的基本操作集。× 2. 线性表的链式存储结构具有可直接存取表中任一元素的优点。× 3. 字符串是数据对象特定的线性表。 4. 二叉树是一棵结点的度最大为二的树。× 5.邻接多重表可以用以表示无向图,也可用以表示有向图。× 6.可从任意有向图中得到关于所有顶点的拓扑次序。× 7.一棵无向连通图的生成树是其极大的连通子图。× 8.二叉排序树的查找长度至多为log2n。× 9.对于一棵m阶的B-树.树中每个结点至多有m 个关键字。除根之外的所有非终端结点至少有┌m/2┐个关键字。× 10.对于目前所知的排序方法,快速排序具有最好的平均性能。 11. 顺序存储方式的优点是存储密度大,且插入、删除运算效率高。× 12. 二维数组是其数据元素为线性表的线性表。 13. 连通图G的生成树是一个包含G的所有n个顶点和n-1条边的子图。× 14. 折半查找不适用于有序链表的查找。 15. 完全二叉树必定是平衡二叉树。 16. 中序线索二叉树的优点是便于在中序下查找直接前驱结点和直接后继结点。 17. 队列是与线性表完全不同的一种数据结构。× 18. 平均查找长度与记录的查找概率有关。 19. 二叉树中每个结点有两个子结点,而对一般的树,则无此限制,所以,二叉树是树的特殊情形。× 20. 算法的时间复杂性越好,可读性就越差;反之,算法的可读性越好,则时间复杂性就越差。× 二.选择题 1. 若对编号为1,2,3的列车车厢依次通过扳道栈进行调度,不能得到 ( e ) 的序列。 a:1,2,3 b:1,3,2 c:2,1,3 d:2,3,1 e:3,1,2 f:3,2,1 2. 递归程序可借助于( b )转化为非递归程序。 a:线性表 b: 栈 c:队列 d:数组 3. 在下列数据结构中( c )具有先进先出(FIFO)特性, ( b )具有先进后出(FILO)特性。 a:线性表 b:栈 c:队列 d:广义表 4. 对字符串s=’data-structure’ 执行操作replace(s,substring(s,6,8),’bas’)

数据结构试题及答案(10套最新)

单选题(每题2分,共20分) 1. 1. 对一个算法的评价,不包括如下(B )方面的内容。 A .健壮性和可读性 B .并行性 C .正确性 D .时空复杂度 2.2. 在带有头结点的单链表HL 中,要向表头插入一个由指针 p 指向 的结点,则执行(A )。 A. p->next=HL->next; HL->next=p; B. p->next=HL; HL=p; 都具有相同的(A )。 A.行号 B .列号 C .元素值 D .非零元素个数 9. 快速排序在最坏情况下的时间复杂度为(D )。 A. O(log 2n) B . O(nlog 2n) C . 0(n) D 10.10. 从二叉搜索树中查找一个元素时,其时间复杂度大致 为 A. O(n) B. O(1) C. O(log 2 n) D. O(n 二、 运算题(每题6分,共24分) 1. 1. 数据结构是指数据及其相互之间的 _________________ 。当结点之 间存在M 对N (M N)的联系时,称这种结构为 __________________________ 。 2. 2. 队列的插入操作是在队列的_ _尾 ________ 行,删除操作是在队 列的 ____ 首 _____ 行。 3. 3. 当用长度为N 的数组顺序存储一个栈时,假定用top==N 表示栈 C. p->next=HL; p=HL; 3. 3. A. C. D. HL=p; p-> next=HL; 对线性表,在下列哪种情况下应当采用链表表示? 经常需要随机地存取元素 B. 表中元素需要占据一片连续的存储空间 一个栈的输入序列为1 2 3, 4. 4. 列的是(C ) A. 2 3 1 C. 3 1 2 AOV 网 是一种(D ) 有向 图 B .无向图 (B ) 经常需要进行插入和删除操作 D.表中元素的个数不变 则下列序列中不可能是栈的输出序 B. 3 2 1 5. 5. 6. .无向无环图 D .有向无环图 采用 开放定址法处理散列表的冲突时,其平均查找长度( B. 高于链接法处理冲突 D .高于二分查找 7. 8. 6. A.低于链接法处理冲突 .与链接法处理冲突相同 7. 参数。 A.值 8. B)。 若需要利用形参直接访问实参时,应将形参变量说明为( B .函数 C .指针 D .引用 在稀疏矩阵的带行指针向量的链接存储中,每个单链表中的结点 9. .0(n 2) (C )。 2 )

数据结构期末考试试题及答案

数据结构期末考试试题及答案 、选择题 评价一个算法时间性能的主要标准是()。1. A、算法易于调试 B、算法易于理解 C、算法的稳定性和正确性 D、算法的时间复杂度 )等五个特性。计算机算法具备有输入、输出、 2. A、可行性、可移植性和可扩充性 B、可行性、确定性和有穷性 C、确定性、有穷性和稳定性 D、XX、稳定性和XX 。带头结点的单链表head为空的判定条件是()3. A、h ead==NULL B、h ead->next==NULL C、head->next==head D、head!=NULL 以下关于线性表的说法不正确的是()。4. A、线性表中的数据元素可以是数字、字符、记录等不同类型。 B、线性表中包含的数据元素个数不是任意的。

C、线性表中的每个结点都有且只有一个直接前趋和直接后继。 D、存在这 样的线性表:表中各结点都没有直接前趋和直接后继。 在顺序表中,只要知道(),就可在相同时间内求出任一结点的存储地址。 5.A、基地址 B、结点大小 C、向量大小 D、基地址和结点大小 ()运算中,使用顺序表比链表好。6. A、插入 B、删除 C、根据序号查找 D、根据元素值查找一个长度为n的顺序表中,向第i个元素之前插入一个新元素时,需要向后移动()个元素7.A、n-i B、n-i+1 C、n-i-1 D、i ()适合作为经常在首尾两端操作线性表的存储结构。8. A、顺序表 B、单链表 C、循环链表 D、双向链表

栈和队列的共同点是() 9. A、都是先进后出 B、都是先进先出 C、只允许在端点处插入和删除元素 D、没有共同点 一个队列的入列序列是1234,则队列的输出序列是()。10. A 、4321 B 、12 3 4 C 、1432 D 、 3241队列与一般的线性表的区别在于()。11. A、数据元素的类型不同 B、运算是否受限制 C、数据元素的个数不同 D、逻辑结构不同 假上溢”现象会出现在()中。12. A、循环队列 B、队列 C、链队列 、顺序队列D.二、填空

数据结构第三章栈和队列3习题

第三章栈和队列试题 一、单项选择题 1.栈的插入和删除操作在()进行。 A. 栈顶 B. 栈底 C. 任意位置 D. 指定位置 2.当利用大小为n的数组顺序存储一个栈时,假定用top==n表示栈空,则向这个栈插入一个元素时, 首先应执行()语句修改top指针。 A. top++; B. top--; C. top = 0; D. top; 3.若让元素1,2,3依次进栈,则出栈次序不可能出现()种情况。 A. 3, 2, 1 B. 2, 1, 3 C. 3, 1, 2 D. 1, 3, 2 4.在一个顺序存储的循环队列中,队头指针指向队头元素的()位置。 A. 前一个 B. 后一个 C. 当前 D. 后面 5.当利用大小为n的数组顺序存储一个队列时,该队列的最大长度为()。 A. n-2 B. n-1 C. n D. n+1 6.从一个顺序存储的循环队列中删除一个元素时,需要()。 A. 队头指针加一 B. 队头指针减一 C. 取出队头指针所指的元素 D. 取出队尾指针所指的元素 7.假定一个顺序存储的循环队列的队头和队尾指针分别为front和rear,则判断队空的条件为()。 A. front+1 == rear B. rear+1 == front C. front == 0 D. front == rear 8.假定一个链式队列的队头和队尾指针分别为front和rear,则判断队空的条件为()。 A. front == rear B. front != NULL C. rear != NULL D. front == NULL 9.设链式栈中结点的结构为(data, link),且top是指向栈顶的指针。若想在链式栈的栈顶插入一 个由指针s所指的结点,则应执行操作()。 A. top->link = s; B.s->link = top->link; top->link = s; C. s->link = top; top = s; D. s->link = top; top = top->link; 10.设链式栈中结点的结构为(data, link),且top是指向栈顶的指针。若想摘除链式栈的栈顶结点, 并将被摘除结点的值保存到x中,则应执行操作()。 A. x = top->data; top = top->link; B. top = top->link; x = top->data; C. x = top; top = top->link; D. x = top->data; 11.设循环队列的结构是 #define MaxSize 100 typedef int ElemType;

算法与数据结构题库与答案

一、单项选择题 1 某算法的时间复杂度是O(n 2 ) ,表明该算法()。 A 问题规模是n2 B 问题规模与n2成正比 C 执行时间等于n2 D 执行时间与n2成正比 2、关于数据结构的描述,不正确的是()。 A数据结构相同,对应的存储结构也相同。 B数据结构涉及数据的逻辑结构、存储结构和施加其上的操作等三个方面。 C数据结构操作的实现与存储结构有关。 D定义逻辑结构时可不考虑存储结构。 3、按排序策略分来,起泡排序属于()。 A插入排序B选择排序C交换排序D归并排序 4、利用双向链表作线性表的存储结构的优点是()。 A便于进行插入和删除的操作 B 提高按关系查找数据元素的速度 C节省空间D便于销毁结构释放空间 5、一个队列的进队顺序为1,2,3,4,则该队列可能的输出序列是()。 A 1,2,3,4 B 1,3,2,4 C 1,4,2,3 D 4,3,2,1 6、 Dijkstra算法是按()方法求出图中从某顶点到其余顶点最短路径的。 A按长度递减的顺序求出图的某顶点到其余顶点的最短路径 B按长度递增的顺序求出图的某顶点到其余顶点的最短路径 C通过深度优先遍历求出图中从某顶点到其余顶点的所有路径 D通过广度优先遍历求出图的某顶点到其余顶点的最短路径 7、字符串可定义为n( n≥ 0)个字符的有限()。其中,n是字符串的长度,表明字符串中字符的个数。 A集合B数列C序列D聚合 8、在二维数组A[9][10]中,每个数组元素占用 3 个存储单元,从首地址SA 开始按行连续存放。在这种情况下,元素A[8][5]的起始地址为()。 A SA+141 B SA+144 C SA+222 D SA+255 9、已知广义表为L(A(u,v,(x,y),z),C(m,(),(k,l,n),(())),((())),(e,(f,g),h)),则它的长度是()。 A2B3C4D5 10.对于具有n(n>1)个顶点的强连通图,其有向边条数至少有_____。 A. n+1 B. n C. n-1 D. n-2 11.一个递归算法必须包括 __________ 。 A. 递归部分 B . 结束条件和递归部分 C. 迭代部分 D. 结束条件和迭代部分 12.从逻辑上看可以把数据结构分为__________两大类。 A.动态结构、静态结构B.顺序结构、链式结构 C.线性结构、非线性结构D.初等结构、构造型结构 13、若在长度为n 的顺序表的表尾插入一个新元素的渐进时间复杂度为()。 A O(n) B O(1) C O(n 2) D O(log 2n) 14.采用顺序搜素方式搜索长度为 n 的线性表时,在等概率情况下,搜索成功时的平均搜索 长度为 __________。 A. n B. n/2 C . (n+1)/2 D. (n-1)/2 15、非空的循环单链表first的链尾结点(由p 所指向)满足()。 A p->link==NULL; B P==NULL;

数据结构作业及答案

第一章绪论 一、选择题 1.数据结构是一门研究非数值计算的程序设计问题中计算机的1以及它们之间的2和运算等的学科。1 A.数据元素 B.计算方法 C.逻辑存储 D.数据映像 2 A.结构 B.关系 C.运算 D.算法 2.数据结构被形式地定义为(K, R),其中K是1的有限集,R是K上的2有限集。 1 A.算法 B.数据元素 C.数据操作 D.逻辑结构 2 A.操作 B.映像 C.存储 D.关系 3.在数据结构中,从逻辑上可以把数据结构分成。 A.动态结构和静态结构 B.紧凑结构和非紧凑结构 C.线性结构和非线性结构 D.内部结构和外部结构 4.线性结构的顺序存储结构是一种1的存储结构,线性表的链式存储结构是一种2的存储结构。A.随机存取 B.顺序存取 C.索引存取 D.散列存取 5.算法分析的目的是1,算法分析的两个主要方面其一是指2,其二是指正确性和简单性。1 A.找出数据结构的合理性 B.研究算法中的输入和输出的关系 C.分析算法的效率以求改进 D.分析算法的易懂性和文档性 2 A.空间复杂度和时间复杂度 B.研究算法中的输入和输出的关系 C.可读性和文档性 D.数据复杂性和程序复杂性k 6.计算机算法指的是1,它必须具备输入、输出和2等5个特性。 1 A.计算方法 B.排序方法 C.解决问题的有限运算序列 D.调度方法 2 A.可执行性、可移植性和可扩充性 B.可行性、确定性和有穷性 C.确定性、有穷性和稳定性 D.易读性、稳定性和安全性 7.线性表的逻辑顺序与存储顺序总是一致的,这种说法。A.正确 B.不正确 8线性表若采用链式存储结构时,要求内存中可用存储单元的地址。 A.必须连续的 B.部分地址必须连续的 C.一定是不续的D连续不连续都可以 9.以下的叙述中,正确的是。A.线性表的存储结构优于链式存储结构 B.二维数组是其数据元素为线性表的线性表C.栈的操作方式是先进先出D.队列的操作方式是先进后出10.每种数据结构都具备三个基本运算:插入、删除和查找,这种说法。A.正确B.不正确 二、填空题1.数据逻辑结构包括三种类型、和,树形结构和图形结构合称为。2.在线性结构中,第一个结点前驱结点,其余每个结点有且只有个前驱结点;最后一个结点后续结点,其余每个结点有且只有个后续结点。3.算法的五个重要特性是、、、、。 4.下面程序段的时间复杂度是。 for( i = 0; i < n; i++) for( j = 0; j < m; j++) A[i][j] = 0; 5.下面程序段的时间复杂度是。 i = s = 0; while ( s < n) { i ++; /* i = i +1*/ s += i; /* s = s + i*/ } 6.下面程序段的时间复杂度是。 s = 0; for( i = 0; i < n; i++) for( j = 0; j < n; j++) s += B[i][j]; sum = s; 7.下面程序段的时间复杂度是。 i = 1; while ( i <= n ) i = i * 3;

《数据结构》期末考试题及答案

2011-2012学年第一学期期末考查 《数据结构》试卷 (答案一律写在答题纸上,在本试卷上做答无效) 一、选择(每题1分,共10分) 1.长度为n的线性表采用顺序存储结构,一个在其第i个位置插入新元素的算法时间复杂度为(D) A.O(0) B.O(1) C.O(n) D.O(n2) 2.六个元素按照6,5,4,3,2,1的顺序入栈,下列哪一个是合法的出栈序列?(D) A.543612 B.453126 C.346512 D.234156 3.设树的度为4,其中度为1、2、3、4的结点个数分别是4、2、1、2,则树中叶子个数为(B ) A.8 B.9 C.10 D.11 4.设森林F对应的二叉树B有m个结点,B的右子树结点个数为n,森林F中第一棵树的结点个数是( B ) A. m-n B.m-n-1 C.n+1 D.m+n 5.若一棵二叉树具有10个度为2的结点,5个度为1的结点,则度为0的结点个数是(B) A.9 B.11 C.15 D.不确定 6.下列哪一个方法可以判断出一个有向图是否有环。(A) A.深度优先遍历 B.拓扑排序 C.求最短路径 D.求关键路径 7.第7层有10个叶子结点的完全二叉树不可能有(B )个结点。 A.73 B.234 C.235 D.236 8.分别用以下序列构造二叉排序树,与用其他三个序列构造的结果不同的是(B) A.(100,80,90,60,120,110,130) B.(100, 120, 110,130,80, 60,90) C.(100,60,80,90,120,110,130) D.(100,80, 60,90, 120, 130,110) 9.对一组数据(84,47,25,15,21)排序,数据的排列次序在排序过程中变化如下:(1)84 47 25 15 21 (2)15 47 25 84 21 (3)15 21 25 84 47(4)15 21 25 47 84则采用的排序方法是(B ) A.选择排序 B.起泡排序 C.快速排序 D.插入排序 10.对线性表进行折半查找时,要求线性表必须(D) A.以顺序方式存储 B.以顺序方式存储,且数据元素有序

数据结构考试及答案()

数据结构考试及答案()

作者: 日期: 2

数据结构试题 一、单选题 1、在数据结构的讨论中把数据结构从逻辑上分为(C) A 内部结构与外部结构 B 静态结构与动态结构 C 线性结构与非线性结构 D 紧凑结构与非紧凑结构。 2、采用线性链表表示一个向量时,要求占用的存储空间地址(D) A 必须是连续的B部分地址必须是连续的 C 一定是不连续的D可连续可不连续 3、采用顺序搜索方法查找长度为n的顺序表时,搜索成功的平均搜索长度为 (D )。 An B n/2 C (n-1)/2 D (n+1)/2 4、在一个单链表中,若q结点是p结点的前驱结点,若在q与p之间插入结点s,则执行(D )o A s—link = p—link ;p—link = s; B p—link = s; s—link = q; C p—link = s—link ;s—link = p; D q—link = s; s—link = p; 5、如果想在4092个数据中只需要选择其中最小的5个,采用(C )方法最好。 A 起泡排序 B 堆排序C锦标赛排序 D 快速 排序 6、设有两个串t和p,求p在t中首次出现的位置的运算叫做(B )o A 求子串B模式匹配C 串替换 D 串连接 7、在数组A中,每一个数组元素A[i][j] 占用3个存储字,行下标i从1到8,

列下标j从1到10。所有数组元素相继存放于一个连续的存储空间中,则存放 该数组至少需要的存储字数是( C )。 A 80 B 100 C 240 D 270 8、将一个递归算法改为对应的非递归算法时,通常需要使用( A )。 A 栈B队列C循环队列D优先队列 9、一个队列的进队列顺序是1,2, 3, 4 ,则出队列顺序为(C )。 10、在循环队列中用数组A[0.. m-1]存放队列元素,其队头和队尾指针分别为front和rear,则当前队列中的元素个数是( D )。 A ( front - rear + 1) % m B (rear - front + 1) %m C ( front - rear + m) % m D ( rear - front + n) % m 11、一个数组元素a[i]与(A )的表示等价。 A * (a+i) B a+i C *a+i D &a+i 12、若需要利用形参直接访问实参,则应把形参变量说明为( B )参数 A指针 B 引用C值 D 变量 13、下面程序段的时间复杂度为(C) for (i nt i=0;i

数据结构试题及答案(10套最新)

一、单选题(每题 2 分,共20分) 1. 1.对一个算法的评价,不包括如下(B )方面的内容。 A.健壮性和可读性B.并行性C.正确性D.时空复杂度 2. 2.在带有头结点的单链表HL中,要向表头插入一个由指针p指向的结 点,则执行(A )。 A. p->next=HL->next; HL->next=p; B. p->next=HL; HL=p; C. p->next=HL; p=HL; D. HL=p; p->next=HL; 3. 3.对线性表,在下列哪种情况下应当采用链表表示?( B ) A.经常需要随机地存取元素 B.经常需要进行插入和删除操作 C.表中元素需要占据一片连续的存储空间 D.表中元素的个数不变 4. 4.一个栈的输入序列为1 2 3,则下列序列中不可能是栈的输出序列的是 ( C ) A. 2 3 1 B. 3 2 1 C. 3 1 2 D. 1 2 3 5. 5.AOV网是一种(D )。 A.有向图B.无向图C.无向无环图D.有向无环图 6. 6.采用开放定址法处理散列表的冲突时,其平均查找长度(B)。 A.低于链接法处理冲突 B. 高于链接法处理冲突 C.与链接法处理冲突相同D.高于二分查找 7.7.若需要利用形参直接访问实参时,应将形参变量说明为(D )参数。 A.值B.函数C.指针D.引用 8.8.在稀疏矩阵的带行指针向量的链接存储中,每个单链表中的结点都具 有相同的( A )。 A.行号B.列号C.元素值D.非零元素个数 9.9.快速排序在最坏情况下的时间复杂度为(D )。 A.O(log2n) B.O(nlog2n) C.0(n) D.0(n2) 10.10.从二叉搜索树中查找一个元素时,其时间复杂度大致为( C )。 A. O(n) B. O(1) C. O(log2n) D. O(n2) 二、运算题(每题 6 分,共24分) 1. 1.数据结构是指数据及其相互之间的______________。当结点之间存在M 对N(M:N)的联系时,称这种结构为_____________________。 2. 2.队列的插入操作是在队列的_ _尾______进行,删除操作是在队列的____ 首______进行。 3. 3.当用长度为N的数组顺序存储一个栈时,假定用top==N表示栈空,则 表示栈满的条件是___top==0___(要超出才为满)_______________。 4. 4.对于一个长度为n的单链存储的线性表,在表头插入元素的时间复杂度 为_________,在表尾插入元素的时间复杂度为____________。

数据结构练习题第三章栈、队列和数组习题及答案

第三章栈、队列和数组 一、名词解释: 1.栈、栈顶、栈底、栈顶元素、空栈 2.顺序栈 3.链栈 4.递归 5.队列、队尾、队头 6.顺序队 7.循环队 8.队满 9.链队10.随机存储结构11.特殊矩阵12.稀疏矩阵13.对称方阵14.上(下)三角矩阵 二、填空题: 1.栈修改的原则是_________或称________,因此,栈又称为________线性表。在栈顶 进行插入运算,被称为________或________,在栈顶进行删除运算,被称为________ 或________。 2.栈的基本运算至少应包括________、________、________、________、________五 种。 3.对于顺序栈,若栈顶下标值top=0,此时,如果作退栈运算,则产生“________”。 4.对于顺序栈而言,在栈满状态下,如果此时在作进栈运算,则会发生“________”。 5.一般地,栈和线性表类似有两种实现方法,即________实现和________实现。 6.top=0表示________,此时作退栈运算,则产生“________”;top=sqstack_maxsize-1 表示________,此时作进栈运算,则产生“________”。 7.以下运算实现在顺序栈上的初始化,请在________处用适当的句子予以填充。 int InitStack(SqStackTp *sq) { ________; return(1);} 8.以下运算实现在顺序栈上的进栈,请在________处用适当的语句予以填充。 Int Push(SqStackTp *sq,DataType x) { if(sp->top==sqstack_maxsize-1}{error(“栈满”);return(0);} else{________________: ________________=x; return(1);} } 9.以下运算实现在顺序栈上的退栈,请在________________用适当句子予以填充。 Int Pop(SqStackTp *sq,DataType *x) {if(sp->top==0){error(“下溢”);return(0);} else{*x=________________; ________________; return(1);} } 10. 以下运算实现在顺序栈上判栈空,请在________________处用适当句子予以填充。 Int EmptyStack(SqStackTp *sq) {if(________________) return(1); else return(0); } 11.以下运算实现在顺序栈上取栈顶元素,请在________________处用适当句子予以填充。 Int GetTop(SqStackTp *sq,DataType *x) {if(________________) return(0);

2015年数据结构期末考试题及答案

2012年数据结构期末考试题及答案 一、选择题 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<n;i++) for(j=0;j<n;j++) s +=B[i][j]; sum =s ; 9.下面程序段的时间复杂度是O(n*m)。 for(i =0;i<n;i++) for(j=0;j<m;j++) A[i][j] =0; 10.下面程序段的时间复杂度是O(log3n)。 i =0; while(i<=n) i =i * 3; 11.在以下的叙述中,正确的是B。 A.线性表的顺序存储结构优于链表存储结构 B.二维数组是其数据元素为线性表的线性表 C.栈的操作方式是先进先出 D.队列的操作方式是先进后出 12.通常要求同一逻辑结构中的所有数据元素具有相同的特性,这意味着B 。 A.数据元素具有同一特点 B.不仅数据元素所包含的数据项的个数要相同,而且对应的数据项的类型要一致 C.每个数据元素都一样 D.数据元素所包含的数据项的个数要相等 13.链表不具备的特点是A。 A.可随机访问任一结点B.插入删除不需要移动元素 C.不必事先估计存储空间D.所需空间与其长度成正比 14.不带头结点的单链表head为空的判定条件是A。

相关主题
文本预览
相关文档 最新文档