银符考试题库-在线练习-数据结构真题2009年下半年

一、单项选择题
在每小题列出的四个备选项中只有一个是符合题目要求的。

1. 按值可否分解，数据类型通常可分为两类，它们是

A.静态类型和动态类型
B.原子类型和表类型
C.原子类型和结构类型
D.数组类型和指针类型

A B C D

C

[解析] 按“值”是否可分解，可将数据类型划分为两类：原子类型，其值不可分解；结构类型，其值可分解为若干个成分。

2. 对于三个函数f(n)=2008n³+8n²+96000，g(n)=8n³+8n+2008和h(n)=8888nlogn+3n²，下列陈述中不成立的是

A.f(n)是O(g(n))
B.g(n)是O(f(n))
C.h(n)是O(nlogn)
D.h(n)是O(n²)

A B C D

C

[解析] 当n充分大时，由题意可得：f(n)与n₃是同阶的，g(n)与n₃是同阶的，h(n)与n₂是同阶的。所以f(n)=O(g(n))，g(n)=O(f(n))，h(n)=O(n²)。

3. 指针p、q和r依次指向某循环链表中三个相邻的结点，交换结点*q和结点*r在表中次序的程序段是

A.p—＞next=r; q—＞next=r—＞next; r—＞next=q;
B.p—＞next=r; r—＞next=q; q—＞next=r—＞next;
C.r—＞next=q; q—＞next=r—＞next; p—＞next=r;
D.r—＞next=q; p—＞next=r; q—＞next=r—＞next;

A B C D

A

4. 若进栈次序为a,b,e，且进栈和出栈可以穿插进行，则可能出现的含3个元素的出栈序列个数是

A.3
B.5
C.6
D.7

A B C D

B

5. 假设以数组A[n]存放循环队列的元素，其头指针front指向队头元素的前一个位置、尾指针rear指向队尾元素所在的存储位置，则在少用一个元素空间的前提下，队列满的判定条件为

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

A B C D

D

[解析] 在循环队列中，在少用一个元素空间的前提下，可约定入队前，测试尾指针在循环意义下加1后是否等于头指针，若相等则认为队满。

6. 串的操作函数str定义为：
int str(char*s){
char*p=s;
while(*p!=’\0')p++;
return p=s;
}
则str("abcde")的返回值是

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

A B C D

C

[解析] 由此操作函数可知，循环执行前，P和S均指向字符串的首字符，循环执行结束后，S仍指向首字符，而P指向字符串之后的结束符(\0)，故P—S返回的是整个字符串的长度。

7. 二维数组A[10][6]采用行优先的存储方法，若每个元素占4个存储单元，已知元素A[3][4]的存储地址为1000，则元素A[4][3]的存储地址为

A.1020
B.1024
C.1036
D.1240

A B C D

A

[解析] 由题意可知，自A[3][4]的存储地址1000起共存放了5个元素(即A[3][4]、A[3][5]、A[4][0]、A[4][1]和A[4][2])后，才开始存放A[4][3]，所以A[4][3]的存储地址为1000+5×4=1020。

8. 对广义表L=(a，())执行操作tail(L)的结果是

A.()
B.(())
C.a
D.(a)

A B C D

B

[解析] 广义表的两个特殊的基本运算：取表头Head(LS)和取表尾tail(LS)。根据表头、表尾的定义可知：任何一个非空广义表的表头是表中第一个元素，它可以是原子，也可以是子表，而其表尾必定是子表。值得注意的是广义表()和(())不同。前者是长度为O的空表，对其不能做求表头和表尾的运算；而后者是长度为1的非空表(只不过该表中惟一的一个元素是空表)，对其可进行分解，得到的表头和表尾均是空表()。

9. 已知二叉树的中序序列和后序序列均为ABCDEF，则该二叉树的先序序列为

A.FEDCBA
B.ABCDEF
C.FDECBA
D.FBDCEA

A B C D

A

[解析] 对于前序遍历、中序遍历和后序遍历，将结点按其访问的先后次序排列起来，所得到的结点序列分别称为前序序列、中序序列和后序序列。

10. 已知森林F={T₁，T₂,T₃,T₄,T₅)，各棵树T_i(i=1,2,3,4,5)中所含结点的个数分别为7,3,5,1,2，则与F对应二叉树的右子树中的结点个数为

A.2
B.3
C.8
D.11

A B C D

D

11. 若非连通无向图G含有21条边，则G的顶点个数至少为

A.7
B.8
C.21
D.22

A B C D

B

12. 如图所示的有向图的拓扑序列是

A.c,d,b,a,e
B.c,a,d,b,e
C.c,d,e,a,b
D.c,a,b,d,e

A B C D

B

13. 对关键字序列(6,1,4,3,7,2,8,5)进行快速排序时，以第1个元素为基准的一次划分的结果为

A.(5,1,4,3,6,2,8,7)
B.(5,1,4,3,2,6,7,8)
C.(5,1,4,3,2,6,8,7)
D.(8,7,6,5,4,3,2,1)

A B C D

C

14. 分块查找方法将表分为多块，并要求

A.块内有序
B.块间有序
C.各块等长
D.链式存储

A B C D

B

15. 便于进行布尔查询的文件组织方式是

A.顺序文件
B.索引文件
C.散列文件
D.多关键字文件

A B C D

D

二、填空题

1. 数据的链式存储结构的特点是借助______表示数据元素之间的逻辑关系。

指针

2. 如果需要对线性表频繁进行______或______操作，则不宜采用顺序存储结构。

插入删除

3. 如图所示，可以利用一个向量空间同时实现两个类型相同的栈。其中栈1为空的条件是top1=0，栈2为空的条件是top2=n-1，则“栈满”的判定条件是______。

top1＞>top2(或top2=top1-1或top1-top2+1)

4. 静态存储分配的顺序串在进行插入、置换和______等操作时可能发生越界。

联接

5. 广义表L=(a，(b，()))的深度为______。

3

6. 任意一棵完全二叉树中，度为1的结点数最多为______。

1

7. 求最小生成树的克鲁斯卡尔(Kruskal)算法耗用的时间与图中______的数目正相关。

边

8. 在5阶B-树中，每个结点至多含4个关键字，除根结点之外，其他结点至少含______个关键字。

2

9. 若序列中关键字相同的记录在排序前后的相对次序不变，则称该排序算法是______的。

稳定

10. 常用的索引顺序文件是______文件和______文件。

ISAM VSAM

三、解答题
如图所示，在n×n矩阵A中，所有下标值满足关系式i+j＜n+1的元素a_i,j的值均为0，现将A中其它元素按行优先顺序依次存储到长度为n(n+1)/2的一维数组sa中，其中元素a_1,π存储在sa[0]。
(1)设n=10，元素a_4,9存储在sa[p]，写出下标p的值；
(2)设元素a_i,j存储在sa[k]中，写出由i,j和n计算k的一般公式。

1.

D=8

2.

3. 由字符集{s,t,a,e,i)及其在电文中出现的频度构建的哈夫曼树如图所示。已知某段电文的哈夫曼编码为111000010100，请根据该哈夫曼树进行译码，写出原来的电文。

eatst

已知无向图G的邻接表如图所示，
(1)画出该无向图；
(2)画出该图的广度优先生成森林。

4.

5.

6. 对序列(48,37,63,96,22,31,50,55,11)进行升序的堆排序，写出构建的初始(大根)堆及前两趟重建堆之后的序列状态。
初始堆：
第1趟：
第2趟：

初始堆：(96,55,63,48,22,31,50,37,11)
第1趟：(63,55,50,48,22,3l,11,37,96)
第2趟：(55,48,50,37,22,31,11,63,96)

四、算法阅读题
阅读下列算法，并回答问题：

(1)无向图G如图所示，写出算法f30(&G)的返回值；
(2)简述算法f30的功能。
#define MaxNum 20
int visited[MaxNum];
void DFS(Graph*g,int i);
/*从顶点vi出发进行深度优先搜索，访问顶点v_j时置visited[j]为1*/
int f30(Graph*g)
{ int i,k;
for(i=0;i＜g—＞N;I++)
visited[i]=0;
if(visited[i]==0)
{ k++;
DFS(g,i);
}
return k;
}

1.

3

2.

返回无向图g中连通分量的个数。

假设学生成绩按学号增序存储在带头结点的单链表中，类型定义如下：
typedef struct Node{
int id; /*学号*/
int score; /*成绩*/
srruct Node*next;
}LNode,*LinkList;
阅读算法f31，并回答问题：
(1)设结点结构为

，成绩链表A和B如图所示，画出执行算法f31(A,B)后A所指的链表；

(2)简述算法f31的功能。
void f31(LinkList A,LinkList B)
{ LinkList p,q;
p=A—＞next;
q=B—＞next;
while(p&&q)
{ if(p—＞id p=p—＞next;
else if(p—＞id＞q—＞id)
q=q—＞next;
else
{ if(p—＞score＜60)
if(q—＞score＜60)
p—＞score=q—＞score;
else p—＞score=60;
p=p—＞next;
q=q—＞next;
}
}
}

3.

4.

对于表A中成绩低于60的学生，如果在表B中也有成绩记录，则将表A中的成绩修改为其在表B中的成绩；但若其在表B中的成绩高于60分，则只改为60分。

阅读下列算法，并回答问题：
(1)设串s="OneWorldOneDream"，t="One"，pos是一维整型数组，写出算法f32(s,t,pos)执行之后得到的返回值和pos中的值；
(2)简述算法f32的功能。
int strlen(char*s); /*返回串S的长度*/
int index(char*st，char*t);
/*若串t在串st中出现，则返回在串st中首次出现的下标值，否则返回-1*/
int f32(char*s,char*t,int pos[])
{ int i,j,k,ls,It;
Is=strlen(s);
lt=strlen(t);
if(ls==0|| It==0)return-1;
k=0;
i=0;
do {
j=index(s+i,t);
if(j＞=0)
{ pos[k++]=i+j;
i+=j+it;
}
}while(i+it＜=is&&j>=0);
return k;
}

5.

2；pos[0]=0，pos[1]=8

6.

返回串t在S中出现的次数，并将每次出现的位置依次存放在数组pos中。

二叉排序树的存储结构定义为以下类型：
typedef int KeyType;
typedef struct node{
KeyType key; /*关键字项*/
InfoType otherinfo; /*其它数据项*/
struet node*lchild,*rchild; /*左、右孩子指针*/
}BSTNode,*BSTree;
阅读算法f33，并回答问题：

(1)对如图所示的二叉排序树T，写出f33(T,8)返回的指针所指结点的关键字；
(2)在哪些情况下算法f33返回空指针?
(3)简述算法f33的功能。
BSTNode*f33(BSTree T,KeyType x)
{ BSTNode*P;
if(T==NULL)return NULL;
p=f33(T—＞lehild,x);
if(p!=NULL)return p;
if(T—＞key＞x)return T;
return f33(T—＞rchild,x);
}

7.

10

8.

T是空树或T中所有结点的关键字均不大于给定值X时，返回空指针。

9.

如果二叉排序树T中存在含有关键字大于给定值X的结点，则返回指针指向它们中关键字最小的结点，否则返回空指针。

五、算法设计题

1. 假设线性表采用顺序存储结构，其类型定义如下：
#define ListSize 100
typedef struct{
int data[ListSize];
int length;
}SeqList,*Table;
编写算法，将顺序表L中所有值为奇数的元素调整到表的前端。

参考答案一：
void f34(Table L)
{ int i,j,t;
i=0;
j=L—＞length-1;
while(i＜j)
{ while(i＜j&&L—＞data[i]%2)
i++;
while(i＜j&&L—＞data[j]%2==0)
j--;
if(i＜j)
{ t=L—＞data[i];
L—＞data[i]=L—＞data[j];
L—＞data[j]=t;
i++;
j--;
}
}
}
参考答案二：
void f34(SeqList*L)
{ int i,j=0.t;
for(i=0;i＜L—＞length;i++)
if(L—＞data[i]%2)/*奇数*/
{ if(i!=j)
{ t=L—＞data[i];
L—＞data[i]=L—＞data[j];
L—＞data[j]=t;
}
j++;
}
}