数据结构习题与答案

1、图书馆的数目检索系统采用（）关系的数据结构。

A.树形

B.图状

C.线性

D.集合

正确答案：C

2、（）是相互之间存在一种或多种特定关系的数据元素的集合。

A.数据

B.数据项

C.数据元素

D.数据结构

正确答案：D

3、（）是一个值的集合和定义在这个值集上的一组操作的总称。

A.数据项

B.数据结构

C.数据类型

D.数据元素

正确答案：C

4、算法的确定性是指（）

A.算法中没有逻辑错误

B.算法中的每一条指令必须有确切的含义

C.当输入数据非法时，算法也能作出反应或进行处理

D.在任何情况下，算法不会出现死循环

5、用顺序结构存储，删除最后一个结点时（）

A.可能会移动其它结点位置

B.其它

C.一定不会移动其它结点位置

D.会移动其它结点位置

正确答案：C

6、链表中逻辑上相邻的元素的物理地址相邻。

A.一定不

B.其它

C.不一定

D.必定

正确答案：C

7、在具有m个单元的循环队列中，队头指针为front，队尾指针为rear，则队满的条件是（）

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

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

C.rear+1==front

D.front==rear

正确答案：A

8、若以S和X分别表示进栈和退栈操作，则对初始状态为空的栈可以进行的栈操作系列合法的是（）

A.SXSXXSSX

B.SXXSXSSX

C.SSSXXSXX

D.SXSSXXXX

正确答案：C

9、设计一个迷宫求解的算法，采用（）数据结构最佳。

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

B.栈

C.队列

D.线性表的顺序存储结构

正确答案：B

10、循环队列存储在数组A[0..m-1],则出队时的操作为（）。

A.front=front+1

B.ront=(front+1)mod m

C.front=(front mod m)+1

D.front=(front+1)mod (m-1)

正确答案：B

11、设s=’I AM A STUDENT’ , t=’GOOD’ , q=’WORKER’则Concat(Substring(s,6,2)

,Concat(t,Replace(s,’STUDENT’,q)))=( )。

A.A GOOD WORKER

B.A GOOD I AM A WORKER

C.ST GOODSTUDENT

D.A GOOD STUDENT

正确答案：B

12、设串sl=″Data_Structures_with_Java″,s2=“it″，则子串定位函数index(s1,s2)的值为（）。

A.16

B.15

C.17

D.18

正确答案：D

13、数组A中，每个元素A的长度为3个字节，行下标i从1到8，列下标j从1到10，从首地址SA 开始连续存放在存储器内，存放该数组至少需要的单元数是（）。

A.100

B.80

C.270

D.240

正确答案：D

14、假设有二维数组A6×8，每个元素用相邻的6个字节存储，存储器按字节编址。已知A的起始存储位置为1000，计算数组A按行存储时元素A[14]第一个字节的位置（）。

A.1072

B.1018

C.1030

D.1024

正确答案：A

15、广义表（（（））,a,((b,c),(),d),(((e)))）的长度为（）。

A.4

B.5

C.2

D.3

正确答案：A

16、下面说法不正确的是 ( ）。

A.广义表可以是一个多层次的结构

B.广义表难以用顺序存储结构

C.广义表的表头总是一个广义表

D.广义表的表尾总是一个广义表

正确答案：C

17、已知一棵树边的集合为{, , , , , , , , , , , , },问这棵树中结点G的双亲结点为( )。

A.I

B.C

C.B

D.A

正确答案：B

18、一棵二叉树中，叶子的个数为10，则其度为2的结点的个数为（）。

A.10

B.12

C.9

D.11

正确答案：C

19、假如一棵二叉树的中序遍历结果为ABCD，则结点A和结点D的关系一定不是( )。

A.结点A是结点D的左子树上的结点

B.结点A是结点D的右子树上的结点

C.结点A是结点D的双亲结点

D.结点A与结点D具有共同的双亲的右子树上的结点

正确答案：B

20、已知一棵树边的集合为{, , , , , , , , , , , , },将此树转化为二叉树后，E的左孩子为（）

A.B

B.A

C.C

D.I

正确答案：D

21、一棵哈夫曼树有17个结点，则其叶子结点的个数是（）。

A.10

B.8

C.7

D.9

正确答案：D

22、下图中结点B的出度为( )

A.1

B.3

C.2

D.0

正确答案：A

23、对于一个具有n个顶点的无向图,若采用邻接矩阵表示,则该矩阵的大小为（）

A.n ×n

B.(n-1)× (n-1)

C.n×(n+1)

D.(n-1)×n

正确答案：A

24、采用邻接表存储的图的宽度优先遍历算法类似于二叉树的（）

A.先序遍历

B.后序遍历

C.层次遍历

D.中序遍历

正确答案：C

25、下面的无向带权图的最小生成树包含的边有( )

A.ae eb bc cd df eg

B.ae ge gf eb bc cd

C.ae ed dc cb eg df

D.ag gf fd dc cb be

正确答案：C

26、判定一个有向图是否存在回路除了可以利用拓扑排序方法外,还可以利用（）

A.深度优先遍历算法

B.求最短路径的Dijkstm方法

C.求关键路径的方法

D.宽度优先遍历算法

正确答案：A

27、对线性表进行二分查找时,要求线性表必须（）。

A.以顺序方式存储

B.以顺序方式存储,且结点按关键字有序排序

C.以链接方式存储

D.以链接方式存储,且结点按关键字有序排序

正确答案：B

28、下列描述中不符合二叉排序树特点的是（）

A.根结点的关键字大于左、右子树中所有结点的关键字

B.左子树中所有结点的关键字小于根结点的关键字

C.右字树中所有结点的关键字大于根节点的关键字

D.关键字插入的顺序影响二叉排序树的形态

正确答案：A

29、设哈希表长m=14，哈希函数H(key)=key%11。表中已有4个结点：

addr (15)=4; addr (38)=5; addr (61)=6; addr (84)=7

如用二次探测再散列处理冲突，关键字为49的结点的地址是（）。

A.9

B.3

C.8

D.5

正确答案：A

30、设一组初始记录关键字序列为(50，40，95，20，15，70，60，45)，则以增量d=4 的一趟希尔排序结束后前4条记录关键字为（）。

A.15，20，40，45

B.15，40，60，20

C.45，40，15，20

D.40，50，20，95

正确答案：B

31、快速排序方法在情况下最不利于发挥其长处。( )

A.要排序的数据个数为奇数

B.要排序的数据中含有多个相同值

C.要排序的数据已基本有序

D.要排序的数据量太大

正确答案：C

32、一组记录的排序码为(46,79,56,38,40,84),则利用堆排序的方法建立的初始推为（）

A.84,79,56,38,40,46

B.84,79,56,46,40,38

C.79,46,56,38,40,80

D.84,56,79,40,46,38

正确答案：A

33、设一组初始记录关键字序列为(25，50，15，35，80，85，20，40，36，70)，其中含有5个长度为2的有序子表，则用归并排序的方法对该记录关键字序列进行一趟归并后的结果为（ A ）。

A.15，25，35，50，20，40，80，85，36，70

B.15，25，35，50，80，20，85，40，70，36

C.15，25，35，50，80，20，36，40，70，85

D.15，25，35，50，80，85，20，36，40，70

正确答案：A

34、设有1000个无序的元素,希望用最快的速度挑选出其中前10个最大的元素,最好的排序方法是（）。

A.插入排序

B.堆排序

C.快速排序

D.选择排序

正确答案：D

35、具有10个记录的序列，采用冒泡排序最少的比较次数是 ( )

A.54

B.1

C.81

D.9

正确答案：D

36、设一组初始记录关键字序列为(345，253，674，924，627)，则用基数排序需要进行（）趟的分配和回收才能使得初始关键字序列变成有序序列。

A.4

B.3

C.8

D.5

正确答案：B

二、填空题

1、假设有两个按元素值递增有序排列的线性表A和B，均以单链表作存储结构，请编写算法将A表和B表归并成一个按元素值递减有序(即非递增有序，允许表中含有值相同的元素)排列的线性表C，并要求利用原表(即A表和B表)的结点空间构造C表。

// 将合并逆置后的结果放在C表中，并删除B表

Status ListMergeOppose_L(LinkList &A,LinkList &B,LinkList &C){

LinkList pa,pb,qa,qb;

pa=A;

pb=B;

qa=pa; // 保存pa的前驱指针

qb=pb; // 保存pb的前驱指针

pa=pa->next;

pb=pb->next;

A->next=NULL;

C=A;

while(pa&&pb){

if(pa->datadata){

qa=pa;

pa=pa->next;

qa->next=A->next;

A->next=qa;

} else{

qb=pb;

pb=pb->next;

//将当前最小结点插入A表表头

A->next=qb;

}

}

while(pa){

qa=pa;

pa=pa->next;

qa->next=A->next;

A->next=qa;

}

while(pb){

qb=pb;

pb=pb->next;

qb->next=A->next;

A->next=qb;

}

pb=B;

free(pb);

return OK;

}

正确答案：qb->next=A->next;

2、假设某个单向循环链表的长度大于1，且表中既无头结点也无头指针。已知s为指向链表中某个结点的指针，试编写算法在链表中删除指针s所指结点的前驱结点。

Status ListDelete_CL(LinkList &S){

LinkList p,q;

if(S==S->next)return ERROR;

q=S;

p=S->next;

while( ){

q=p;

p=p->next;

}

q->next=p->next;

free(p)；

return OK;

}

正确答案：p->next!=s

3、试写一个算法，识别依次读入的一个以@为结束符的字符序列是否为形如‘序列1&序列2’模式的字符序列。其中序列1和序列2中都不含字符‘&’，且序列2是序列1的逆序列。例如，

‘a+b&b+a’是属该模式的字符序列，而‘1+3&3-1’则不是。

BOOL Symmetry(char a[]){

int i=0;

Stack s;

InitStack(s);

ElemType x;

while(a[i]!='&' && a[i]){

;

i++;

}

if(a[i]) return FALSE;

i++;

while(a[i]){

Pop(s,x);

if(x!=a[i]){

DestroyStack(s);

return FALSE;

}

i++;

}

return TRUE;

}

正确答案：Push(s,a[i])

4、假设称正度和反读都相同的字符序列为“回文”，例如，‘abba’和‘abcba’是回文，‘abcde’和‘ababab’则不是回文。试写一个算法判别读入的一个以‘@’为结束符的字符序列是否是“回文”。

Status SymmetryString(char* p){

Queue q;

if(!InitQueue(q)) return 0;

Stack s;

InitStack(s);

ElemType e1,e2;

while(*p){

Push(s,*p);

;

p++;

}

while(!StackEmpty(s)){

Pop(s,e1);

DeQueue(q,e2);

if(e1!=e2) return FALSE;

}

return OK;

}

正确答案：EnQueue(q,*p)

5、试按教科书5.5节图5.10所示的结点结构编写复制广义表的递归算法。

// 由广义表L复制广义表T

int CopyGList(GList& T,GList& L){

if(!L) T=NULL;

else{

T=new GLNode;

if(!T) exit(OVERFLOW);

T->tag=L->tag;

if(L->tag==ATOM) T->atom=L->atom;

else{

;

CopyGList(T->tp,L->tp);

}

}

return OK;

}

正确答案：CopyGList(T->hp,L->hp)

6、编写递归算法，将二叉树中所有结点的左、右子树相互交换。

Status ExchangeBiTree(BiTree& T)

{

BiTree p;

if(T){

p=T->lchild;

T->lchild=T->rchild;

T->rchild=p;

;

ExchangeBiTree(T->rchild);

}

return OK;

}

正确答案：ExchangeBiTree(T->lchild)

7、试写一个算法，为一棵二叉树建立后序线索二叉树。

Status PostOrderThreading(BiThrTree& T,BiThrTree& pre);//首先建立后序线索树Status FindNextInBiThrTree(BiThrTree& q,TElemType *p);//再进行查找

// 后序线索二叉树的算法

Status PostOrderThreading(BiThrTree& Thrt,BiThrTree& T){

BiThrTree pre;

Thrt=new BiThrNode; // 为线索二叉树建立头结点

if(!Thrt) exit(OVERFLOW);

Thrt->LTag=Link;

Thrt->RTag=Thread;

Thrt->rchild=Thrt;// 右子树回指

if(!T) Thrt->lchild=Thrt;// 若二叉树空，左子树回指 else{

Thrt->lchild=T;

pre=Thrt;

PostThreading(T,pre); // 后序遍历进行后序线索化 pre->rchild=Thrt;// 最后一个结点线索化

pre->RTag=Thread;

Thrt->rchild=pre;

}

return OK;

}

Status PostThreading(BiThrTree& T,BiThrTree& pre){ if(T){

if(T->LTag==Link) PostThreading(T->lchild,pre); if(T->RTag==Link) PostThreading(T->rchild,pre); if(!T->lchild){

T->LTag=Thread;

;

}

if(pre && !pre->rchild){

pre->RTag=Thread;

pre->rchild=T;

}

pre=T;

}

return OK;

}

正确答案：T->lchild=pre

8、编写算法实现建立图的邻接表

Status CreateAG(ALGraph &G){

int n,e,k,i,j;

cout<<"请输入顶点数：";

cin>>n;

cout<<"请输入边数：";

cin>>e;

G.vernum=n;

G.arcnum=e;

// 建立顶点数组

for(k=0;k

cout<<"请输入顶点信息：";

cin>>G.vertices[k].data;

G.vertices[k].firstarc=NULL;

}

// 建立邻接表

VertexType v1,v2;

ArcNode *p,*q;

for(k=0;k

cout<<"请输入弧的始点和终点信息，中间用空格分开:";

cin>>v1>>v2;

i=LocateVex(G,v1);

if(i<0 || i>G.vernum-1) return ERROR;

j=LocateVex(G,v2);

if(j<0 || j>G.vernum-1) return ERROR;

if(i==j) return ERROR;

p=new ArcNode;

if(!p) return ERROR;

p->adjvex=j;

p->nextarc=NULL;

q=G.vertices[i].firstarc;

if(!q) G.vertices[i].firstarc=p;

else{

while(q->nextarc) ； // 指针定位于邻接表的尾结点

q->nextarc=p;

}

}

return OK;

}

正确答案：q=q->nextarc

9、编写算法实现从邻接表中取出某个顶点V的存储位置。int LocateVex(ALGraph& G,VertexType v)

{

int i=0;

while( &&i

if(G.vertices[i].data==v) return i;

else return -1;

}

正确答案：G.vertices[i].data!=v

10、试将折半查找的算法改写成递归算法。

Int bisearch (sqlist L,int low, int high , elemtype x ) { If (low>high) reeturn( 0 );

else { mid=(low+high)/2;

if (L.data[mid]= =x) return (mid);

else if (L.data[mid]>x) bisearch(L,low,mid-1,x); else ;

}

}//bisearch

正确答案：bisearch(L,mid+1,high,x)

11、设计算法判定给定二叉树是否为二叉排序树。

void BSTree(BiTree t,int &flag,int &last);//声明

Status IsBSTree(BiTree t){

int flag = 1;

int last =0;

BSTree(t,flag,last);

return flag;

}

void BSTree(BiTree t,int &flag,int &last){//取地址不需要返回值

if(t->lchild&&flag) BSTree(t->lchild,flag,last);//遍历左子树

if(t->data.key>last&&flag) last = t->data.key;

else flag=0;

//last原为父节点值，但到了树叶节点后被树叶节点的key值覆盖，然后开始向上反馈key

if(t->rchild&&flag) ；

}

正确答案：BSTree(t->rchild,flag,last)

12、试以L.r[k+1]作为监视哨改写教科书10.2.1节中给出的直接插入排序算法。其中，L.r[1..k]为待排序记录且k

void InsertionSort ( SqList &L ) { // 对顺序表 L 作直接插入排序。

for ( i=k-1-1; i>=1; --i ){

if (L.r[i+1].key < L.r[i].key){

L.r[k+1] = L.r[i]; // 复制为监视哨

for ( j=i+1; L.r[k+1].key > L.r[j].key; ++ j )

L.r[j] = L.r[j+1]; // 记录前移

}//end if

；

}//end for

} // InsertSort

正确答案：L.r[j-1] = L.r[k+1]

13、编写算法，对n个关键字取整数值的记录序列进行整理，以使所有关键字为负值的记录排在关键字为非负值的记录之前，要求：

(1)采用顺序存储结构，至多使用一个记录的辅助存储空间；

(2)算法的时间复杂度为O(n);

void Divide(int a[ ],int n){//把数组a中所有值为负的记录调到非负的记录之前

low=0;high=n-1;

while（low

while(low=0) high--; //以0作为虚拟的枢轴记录 ;

while(low

a[low]<->a[high];

}

}//Divide

正确答案：a[low]<->a[high]