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

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

1. 若将数据结构形式定义为二元组(K,R)，其中K是数据元素的有限集合，则R是K上

A.操作的有限集合
B.映象的有限集合
C.类型的有限集合
D.关系的有限集合

A B C D

D

2. 在长度为n的顺序表中删除第i个元素(1≤i≤n)时，元素移动的次数为

A.n-i+1
B.i
C.i+1
D.n-i

A B C D

D

3. 若不带头结点的单链表的头指针为head，则该链表为空的判定条件是

A.head==NULL
B.head—＞next==NULL
C.head!=NULL
D.head—＞next==head

A B C D

A

4. 引起循环队列队头位置发生变化的操作是

A.出队
B.入队
C.取队头元素
D.取队尾元素

A B C D

A

5. 若进栈序列为1,2,3,4,5,6，且进栈和出栈可以穿插进行，则不可能出现的出栈序列是

A.2,4,3,1,5,6
B.3,2,4,1,6,5
C.4,3,2,1,5,6
D.2,3,5,1,6,4

A B C D

D

6. 字符串通常采用的两种存储方式是

A.散列存储和索引存储
B.索引存储和链式存储
C.顺序存储和链式存储
D.散列存储和顺序存储

A B C D

C

7. 设主串长为n，模式串长为m(m≤n)，则在匹配失败情况下，朴素匹配算法进行的无效位移次数为

A.m
B.n-m
C.n-m+1
D.n

A B C D

C

8. 二维数组A[12][18]采用列优先的存储方法，若每个元素各占3个存储单元，且第1个元素的地址为150，则元素A[9][7]的地址为

A.429
B.432
C.435
D.438

A B C D

A

9. 对广义表L=((a,b)，(c,d)，(e,f))执行操作tail(tail(L))的结果是

A.(e,f)
B.((e,f))
C.(f)
D.()

A B C D

B

10. 下列图示的顺序存储结构表示的二叉树是

A B C D

A

11. n个顶点的强连通图中至少含有

A.n-1条有向边
B.n条有向边
C.n(n-1)/2条有向边
D.n(n-1)条有向边

A B C D

B

12. 对关键字序列(56,23,78,92,88,67,19,34)进行增量为3的一趟希尔排序的结果为

A.(19,23,56,34,78,67,88,92)
B.(23,56,78,66,88,92,19,34)
C.(19,23,34,56,67,78,88,92)
D.(19,23,67,56,34,78,92,88)

A B C D

D

13. 若在9阶B-树中插入关键字引起结点分裂，则该结点在插入前含有的关键字个数为

A.4
B.5
C.8
D.9

A B C D

C

14. 由同一关键字集合构造的各棵二叉排序树

A.其形态不一定相同，但平均查找长度相同
B.其形态不一定相同，平均查找长度也不一定相同
C.其形态均相同，但平均查找长度不一定相同
D.其形态均相同，平均查找长度也都相同

A B C D

B

15. ISAM文件和VSAM文件的区别之一是

A.前者是索引顺序文件，后者是索引非顺序文件
B.前者只能进行顺序存取，后者只能进行随机存取
C.前者建立静态索引结构，后者建立动态索引结构
D.前者的存储介质是磁盘，后者的存储介质不是磁盘

A B C D

C

二、填空题

1. 数据的逻辑结构在计算机存储器内的表示，称为数据的______。

存储结构

2. 删除双向循环链表中*p的前驱结点(存在)应执行的语句是______。

p—＞prior=p—＞prior—＞prior;
p—＞prior—＞next=p;
(或p—＞prior—＞prior—＞next=p;
p—＞prior=p—＞prior—＞prior;

3. 栈下溢是指在______时进行出栈操作。

栈空

4. 已知substr(s,i,len)函数的功能是返回串s中第i个字符开始长度为len的子串，strlen(s)函数的功能是返回串s的长度。若s="ABCDEFGHUK"，t="ABCD"，执行运算substr(s,strlen(t),strlen(t))后的返回值为______。

"EFGH"

5. 去除广义表LS=(a₁，a₂，a₃，……，a_n)中第1个元素，由其余元素构成的广义表称为LS的______。

表尾

6. 已知完全二叉树T的第5层只有7个结点，则该树共有______个叶子结点。

11

7. 在有向图中，以顶点V为终点的边的数目称为V的______。

入度

8. 当关键字的取值范围是实数集合时，无法进行箱排序和______排序。

基数

9. 产生冲突现象的两个关键字称为该散列函数的______。

同义词

10. 假设散列文件中一个桶能存放m个记录，则桶“溢出”的含义是，当需要插入新的记录时，该桶中______。

已有m个同义词的记录(或：已有m个记录；或：已满)

三、解答题
假设以数组seqn[m]存放循环队列的元素，设变量rear和qHelen分别指示循环队列中队尾元素的位置和元素的个数。
(1)写出队满的条件表达式；
(2)写出队空的条件表达式；
(3)设m=40，rear=13，quelen=19，求队头元素的位置；
(4)写出一般情况下队头元素位置的表达式。

1.

quelen=m

2.

quelen=0

3.

35

4.

(rear-quelen+1+m)%m

5. 已知一棵二叉树的中序序列为ABCDEFG，层序序列为BAFEGCD，请画出该二叉树。

6. 画出下图所示有向图的所有强连通分量。

该图的强连通分量分别为：

对7个关键字进行快速排序，在最好的情况下仅需进行10次关键字的比较。
(1)假设关键字集合为{1,2,3,4,5,6,7}，试举出能达到上述结果的初始关键字序列；
(2)对所举序列进行快速排序，写出排序过程。

7.

4 7 1 3 6 5 2

8.

初始关键字 4 7 1 3 6 5 2
一次划分后得 (2 3 1)4(6 5 7)
继续划分后得 (1)2(3) (5)6(7)

四、算法阅读题
阅读下列算法，并回答问题：
(1)设顺序表L=(3,7,11,14,20,51)，写出执行f30(&L,15)之后的L；
(2)设顺序表L=(4,7,10,14,20,51)，写出执行f30(&L,10)之后的L；
(3)简述算法的功能。
void f30(SeqList*L,DataType x)
{
int i=0,j;
while(i＜L-＞length&&x＞L-＞data[i])i++
if(i＜L—＞length&& x==L—＞data[i]{
for(j=i+1;j＜L—＞length;j++)
L—＞data[j-1]=L—＞data[j];
L—＞length--;
}else{
for(j=L—＞length;j＞i;j--)
L—＞data[j]=L—＞data[j-1];
L—＞data[i]=x;
L—＞length++;
}
}

1.

(3,7,11,14,15,20,51)

2.

(4,7,14,20,51)

3.

当非递减顺序表中存在元素x时，从表中删除该元素；否则将X保序插入到顺序表中。

已知图的邻接表表示的形式说明如下：
#define MaxNum 50 //图的最大顶点数
typedef struct node{
int adjvex; //邻接点域
struct node*next; //链指针域
}EdgeNode; //边表结点结构描述
typedef struct{
char vertex; //顶点域
EdgeNode*firstedge;//边表头指针
}VertexNode; //顶点表结点结构描述
typedef struet{
VertexNode adjlist[MaxNum];//邻接表
int n,e; //图中当前的顶点数和边数
}ALGraph; //邻接表结构描述
下列算法输出图G的深度优先生成树(或森林)的边。阅读算法，并在空缺处填入合适的内容，使其成为一个完整的算法。
typedef enum{FALSE,TRUE}Boolean;
Boolean visited[MaxNurn];
void DFSForest(ALGraph*G){
int i;
for(i=0;i＜G—＞n;i++)visited[i]= 4 ;
for(i=0;i＜G—＞n;i++)if(!visited[i])DFSTree(G,i);
}
void DFSTree(ALGraph*G,int i){
EdgeNode*p;
visited[i]=TRUE;
p=G—＞adjlist[i].firstedge;
while(p!=NULL){
if(!visited[p—＞adjvex]){
printf("＜%c,%c",G—＞adjlist[i].vertex,
G—＞adjlist[p—＞adjvex].vertex);
5 ;
}
6 ;
}
}

4.

FALSE

5.

DFSTree(G,P—＞adjvex)

6.

p=p—＞next

阅读下列算法，并回答问题：
(1)假设数组L[8]={3,0,5,1,6,4,2,7}，写出执行函数调用f32(L,8)后的L；
(2)写出上述函数调用过程中进行元素交换操作的总次数。
void fS2(int R[],int n){
int i,t;
for(i=0;i＜n-1;i++)
while(R[i]!=i){
t=R[R[i-1];
R[R[i]]=R[i];
R[i]=t;
}
}

7.

L[8]={0,1,2,3,4,5,6,7,}

8.

共进行5次元素交换。

已知带头结点的单链表中的关键字为整数，为提高查找效率，需将它改建为采用拉链法处理冲突的散列表。设散列表的长度为m，散列函数为Hash(key)=key%m。链表的结点结构为：

。请在空缺处填入适当内容，使其成为一个完整算法。
void f33(LinkList L,LinkList H[],int m)
{//由带头结点的单链表L生成散列表H，散列表生成之后原链表不再存在
int i,j;
LinkList p,q;
for(i=0;i＜m;i++)
H[i]=[ 9 ];
p=L—＞next;
while(p)
{
q=p—＞next
j=p—＞key%m;
[ 10 ];
H[j]=p;
[ 11 ];
}
free(L);
}

9.

NULL

10.

p—＞next=H[j]

11.

p=q

五、算法设计题
假设以带双亲指针的二叉链表作为-二叉树的存储结构，其结点结构的类型说明如下所示：
typedef char DataType;
typedef struct node{
DataType data;
struct node*lchild,*rchild; //左右孩子指针
struct node*parent; //指向双亲的指针
}BinTNode;
typedef BinTNode*BinTree;
若px为指向非空二叉树中某个结点的指针，可借助该结构求得px所指结点在二叉树的中序序列中的后继。

1. 就后继的不同情况，简要叙述实现求后继操作的方法；

分两种情况讨论
①当*px的右子树不为空时，则从*px的右孩子开始，沿其左孩子往下查找，直至找到一个没有左孩子的结点为止，则该结点为*pX在中序序列中的后继；
②当*px的右子树为空时，则沿*px的双亲指针链向上查找，直至找到其左子树中包含*px的最年轻祖先，则该祖先结点为*px在中序序列中的后继。

2. 编写算法求px所指结点的中序序列后继，并在算法语句中加注注释。

BinTree f34(BinTree px)
{
BinTree q=px—＞rchild;
if(q!=NULL){ //沿左孩子往下查找
px=q;
while(px—＞lchild!=NULL)
px=px—＞lchild;
}
else{ //沿双亲指针链向上查找
while(px!=NULL&&px—＞rchild==q){
q=px;
px=px—＞parent;
}
}
retun px； //返回所找到的中序序列后继结点的指针
//或者无后继结点时返回空指针
}