1、数据结构真题 2005 年下半年及答案解析(总分：154.98，做题时间：90 分钟)一、B单项选择题/B(总题数：15，分数：30.00)1.若将数据结构形式定义为二元组(K,R)，其中 K 是数据元素的有限集合，则 R 是 K 上( )（分数：2.00）A.操作的有限集合B.映象的有限集合C.类型的有限集合D.关系的有限集合2.在长度为 n 的顺序表中删除第 i 个元素(1in)时，元素移动的次数为 ( )（分数：2.00）A.n-i+1B.iC.i+1D.n-i3.若不带头结点的单链表的头指针为 head，则该链表为空的判定条件是 ( )（分数：2.00）A.head=NULLB.hea
2、dnext=NULLC.head!=NULLD.headnext=head4.引起循环队列队头位置发生变化的操作是 ( )（分数：2.00）A.出队B.入队C.取队头元素D.取队尾元素5.若进栈序列为 1,2,3,4,5,6，且进栈和出栈可以穿插进行，则不可能出现的出栈序列是( )（分数：2.00）A.2,4,3,1,5,6B.3,2,4,1,6,5C.4,3,2,1,5,6D.2,3,5,1,6,46.字符串通常采用的两种存储方式是 ( )（分数：2.00）A.散列存储和索引存储B.索引存储和链式存储C.顺序存储和链式存储D.散列存储和顺序存储7.设主串长为 n，模式串长为 m(mn)，则在
3、匹配失败情况下，朴素匹配算法进行的无效位移次数为 ( )（分数：2.00）A.mB.n-mC.n-m+1D.n8.二维数组 A1218采用列优先的存储方法，若每个元素各占 3 个存储单元，且第 1 个元素的地址为150，则元素 A97的地址为 ( )（分数：2.00）A.429B.432C.435D.4389.对广义表 L=(a,b)，(c,d)，(e,f)执行操作 tail(tail(L)的结果是 ( )（分数：2.00）A.(e,B.(e,)C.(D.()10.下列图示的顺序存储结构表示的二叉树是 ( ) （分数：2.00）A.B.C.D.11.n 个顶点的强连通图中至少含有 ( )（分数
4、：2.00）A.n-1 条有向边B.n 条有向边C.n(n-1)/2 条有向边D.n(n-1)条有向边12.对关键字序列(56,23,78,92,88,67,19,34)进行增量为 3 的一趟希尔排序的结果为( )（分数：2.00）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)13.若在 9 阶 B-树中插入关键字引起结点分裂，则该结点在插入前含有的关键字个数为( )（分数：2.00）A.4B.5C.8D.914.由同一关键字
5、集合构造的各棵二叉排序树 ( )（分数：2.00）A.其形态不一定相同，但平均查找长度相同B.其形态不一定相同，平均查找长度也不一定相同C.其形态均相同，但平均查找长度不一定相同D.其形态均相同，平均查找长度也都相同15.ISAM 文件和 VSAM 文件的区别之一是 ( )（分数：2.00）A.前者是索引顺序文件，后者是索引非顺序文件B.前者只能进行顺序存取，后者只能进行随机存取C.前者建立静态索引结构，后者建立动态索引结构D.前者的存储介质是磁盘，后者的存储介质不是磁盘二、B填空题/B(总题数：10，分数：20.00)16.数据的逻辑结构在计算机存储器内的表示，称为数据的 1。（分数：2.0
6、0）填空项 1:_17.删除双向循环链表中*p 的前驱结点(存在)应执行的语句是_。（分数：2.00）填空项 1:_18.栈下溢是指在 1 时进行出栈操作。（分数：2.00）填空项 1:_19.已知 substr(s,i,len)函数的功能是返回串 s 中第 i 个字符开始长度为 len 的子串，strlen(s)函数的功能是返回串 s 的长度。若 s=“ABCDEFGHUK“，t=“ABCD“，执行运算 substr(s,strlen(t),strlen(t)后的返回值为 1。（分数：2.00）填空项 1:_20.去除广义表 LS=(a1，a 2，a 3，a n)中第 1 个元素，由其余元素
7、构成的广义表称为 LS 的 1。（分数：2.00）填空项 1:_21.已知完全二叉树 T 的第 5 层只有 7 个结点，则该树共有 1 个叶子结点。（分数：2.00）填空项 1:_22.在有向图中，以顶点 V 为终点的边的数目称为 V 的 1。（分数：2.00）填空项 1:_23.当关键字的取值范围是实数集合时，无法进行箱排序和 1 排序。（分数：2.00）填空项 1:_24.产生冲突现象的两个关键字称为该散列函数的 1。（分数：2.00）填空项 1:_25.假设散列文件中一个桶能存放 m 个记录，则桶“溢出”的含义是，当需要插入新的记录时，该桶中 1。（分数：2.00）填空项 1:_三、B解
8、答题/B(总题数：2，分数：30.00)假设以数组 seqnm存放循环队列的元素，设变量 rear 和 qHelen 分别指示循环队列中队尾元素的位置和元素的个数。 (1)写出队满的条件表达式； (2)写出队空的条件表达式； (3)设 m=40，rear=13，quelen=19，求队头元素的位置； (4)写出一般情况下队头元素位置的表达式。（分数：19.98）(1).（分数：3.33）_(2).（分数：3.33）_(3).（分数：3.33）_(4).（分数：3.33）_对 7 个关键字进行快速排序，在最好的情况下仅需进行 10 次关键字的比较。 (1)假设关键字集合为1,2,3,4,5,6,
9、7，试举出能达到上述结果的初始关键字序列； (2)对所举序列进行快速排序，写出排序过程。（分数：10.00）(1).（分数：5.00）_(2).（分数：5.00）_四、B算法阅读题/B(总题数：4，分数：55.00)阅读下列算法，并回答问题： (1)设顺序表 L=(3,7,11,14,20,51)，写出执行 f30( while(iL-lengthjLlength;j+) Ldataj-1=Ldataj; Llength-; else for(j=Llength;ji;j-) Ldataj=Ldataj-1; Ldatai=x; Llength+; （分数：15.00）(1).（分数：5.00
10、）填空项 1:_(3).（分数：5.00）_已知图的邻接表表示的形式说明如下： #define MaxNum 50 /图的最大顶点数 typedef struct node int adjvex; /邻接点域 struct node*next; /链指针域 EdgeNode; /边表结点结构描述 typedef struct char vertex; /顶点域 EdgeNode*firstedge;/边表头指针 VertexNode; /顶点表结点结构描述 typedef struet VertexNode adjlistMaxNum;/邻接表 int n,e; /图中当前的顶点数和边数 AL
11、Graph; /邻接表结构描述 下列算法输出图 G 的深度优先生成树(或森林)的边。阅读算法，并在空缺处填入合适的内容，使其成为一个完整的算法。 typedef enumFALSE,TRUEBoolean; Boolean visitedMaxNurn; void DFSForest(ALGraph*G) int i; for(i=0;iGn;i+)visitedi=U (1) /U; for(i=0;iGn;i+)if(!visitedi)DFSTree(G,i); void DFSTree(ALGraph*G,int i) EdgeNode*p; visitedi=TRUE; p=Gadj
12、listi.firstedge; while(p!=NULL) if(!visitedpadjvex) printf(“%c,%c“,Gadjlisti.vertex, Gadjlistpadjvex.vertex); U (2) /U; U (3) /U; （分数：15.00）(1).（分数：5.00）填空项 1:_填空项 1:_阅读下列算法，并回答问题： (1)假设数组 L8=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;in
13、-1;i+) while(Ri!=i) t=RRi-1; RRi=Ri; Ri=t; （分数：10.00）(1).（分数：5.00）填空项 1:_已知带头结点的单链表中的关键字为整数，为提高查找效率，需将它改建为采用拉链法处理冲突的散列表。设散列表的长度为 m，散列函数为 Hash(key)=key%m。链表的结点结构为：。请在空缺处填入适当内容，使其成为一个完整算法。 void f33(LinkList L,LinkList H,int m) /由带头结点的单链表 L 生成散列表 H，散列表生成之后原链表不再存在 int i,j; LinkList p,q; for(i=0;im;i+) H
14、i=U (1) /U; p=Lnext; while(p) q=pnext j=pkey%m; U (2) /U; Hj=p; U (3) /U; free(L); （分数：15.00）(1).（分数：5.00）填空项 1:_填空项 1:_五、B算法设计题/B(总题数：1，分数：20.00)假设以带双亲指针的二叉链表作为-二叉树的存储结构，其结点结构的类型说明如下所示： typedef char DataType; typedef struct node DataType data; struct node*lchild,*rchild; /左右孩子指针 struct node*parent;
15、 /指向双亲的指针 BinTNode; typedef BinTNode*BinTree; 若 px 为指向非空二叉树中某个结点的指针，可借助该结构求得 px 所指结点在二叉树的中序序列中的后继。（分数：20.00）(1).就后继的不同情况，简要叙述实现求后继操作的方法；（分数：10.00）_(2).编写算法求 px 所指结点的中序序列后继，并在算法语句中加注注释。（分数：10.00）_数据结构真题 2005 年下半年答案解析(总分：154.98，做题时间：90 分钟)一、B单项选择题/B(总题数：15，分数：30.00)1.若将数据结构形式定义为二元组(K,R)，其中 K 是数据元素的有限集
16、合，则 R 是 K 上( )（分数：2.00）A.操作的有限集合B.映象的有限集合C.类型的有限集合D.关系的有限集合 解析：2.在长度为 n 的顺序表中删除第 i 个元素(1in)时，元素移动的次数为 ( )（分数：2.00）A.n-i+1B.iC.i+1D.n-i 解析：3.若不带头结点的单链表的头指针为 head，则该链表为空的判定条件是 ( )（分数：2.00）A.head=NULL B.headnext=NULLC.head!=NULLD.headnext=head解析：4.引起循环队列队头位置发生变化的操作是 ( )（分数：2.00）A.出队 B.入队C.取队头元素D.取队尾元素解
17、析：5.若进栈序列为 1,2,3,4,5,6，且进栈和出栈可以穿插进行，则不可能出现的出栈序列是( )（分数：2.00）A.2,4,3,1,5,6B.3,2,4,1,6,5C.4,3,2,1,5,6D.2,3,5,1,6,4 解析：6.字符串通常采用的两种存储方式是 ( )（分数：2.00）A.散列存储和索引存储B.索引存储和链式存储C.顺序存储和链式存储 D.散列存储和顺序存储解析：7.设主串长为 n，模式串长为 m(mn)，则在匹配失败情况下，朴素匹配算法进行的无效位移次数为 ( )（分数：2.00）A.mB.n-mC.n-m+1 D.n解析：8.二维数组 A1218采用列优先的存储方法，
18、若每个元素各占 3 个存储单元，且第 1 个元素的地址为150，则元素 A97的地址为 ( )（分数：2.00）A.429 B.432C.435D.438解析：9.对广义表 L=(a,b)，(c,d)，(e,f)执行操作 tail(tail(L)的结果是 ( )（分数：2.00）A.(e,B.(e,) C.(D.()解析：10.下列图示的顺序存储结构表示的二叉树是 ( ) （分数：2.00）A. B.C.D.解析：11.n 个顶点的强连通图中至少含有 ( )（分数：2.00）A.n-1 条有向边B.n 条有向边 C.n(n-1)/2 条有向边D.n(n-1)条有向边解析：12.对关键字序列(5
19、6,23,78,92,88,67,19,34)进行增量为 3 的一趟希尔排序的结果为( )（分数：2.00）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) 解析：13.若在 9 阶 B-树中插入关键字引起结点分裂，则该结点在插入前含有的关键字个数为( )（分数：2.00）A.4B.5C.8 D.9解析：14.由同一关键字集合构造的各棵二叉排序树 ( )（分数：2.00）A.其形态不一定相同，但平均查找长度相同B.其形态不一定相
20、同，平均查找长度也不一定相同 C.其形态均相同，但平均查找长度不一定相同D.其形态均相同，平均查找长度也都相同解析：15.ISAM 文件和 VSAM 文件的区别之一是 ( )（分数：2.00）A.前者是索引顺序文件，后者是索引非顺序文件B.前者只能进行顺序存取，后者只能进行随机存取C.前者建立静态索引结构，后者建立动态索引结构 D.前者的存储介质是磁盘，后者的存储介质不是磁盘解析：二、B填空题/B(总题数：10，分数：20.00)16.数据的逻辑结构在计算机存储器内的表示，称为数据的 1。（分数：2.00）填空项 1:_ （正确答案：存储结构）解析：17.删除双向循环链表中*p 的前驱结点(存
21、在)应执行的语句是_。（分数：2.00）填空项 1:_ （正确答案：pprior=ppriorprior;）解析：ppriornext=p; (或 ppriorpriornext=p; pprior=ppriorprior;18.栈下溢是指在 1 时进行出栈操作。（分数：2.00）填空项 1:_ （正确答案：栈空）解析：19.已知 substr(s,i,len)函数的功能是返回串 s 中第 i 个字符开始长度为 len 的子串，strlen(s)函数的功能是返回串 s 的长度。若 s=“ABCDEFGHUK“，t=“ABCD“，执行运算 substr(s,strlen(t),strlen(t)
22、后的返回值为 1。（分数：2.00）填空项 1:_ （正确答案：“EFGH“）解析：20.去除广义表 LS=(a1，a 2，a 3，a n)中第 1 个元素，由其余元素构成的广义表称为 LS 的 1。（分数：2.00）填空项 1:_ （正确答案：表尾）解析：21.已知完全二叉树 T 的第 5 层只有 7 个结点，则该树共有 1 个叶子结点。（分数：2.00）填空项 1:_ （正确答案：11）解析：22.在有向图中，以顶点 V 为终点的边的数目称为 V 的 1。（分数：2.00）填空项 1:_ （正确答案：入度）解析：23.当关键字的取值范围是实数集合时，无法进行箱排序和 1 排序。（分数：2.
23、00）填空项 1:_ （正确答案：基数）解析：24.产生冲突现象的两个关键字称为该散列函数的 1。（分数：2.00）填空项 1:_ （正确答案：同义词）解析：25.假设散列文件中一个桶能存放 m 个记录，则桶“溢出”的含义是，当需要插入新的记录时，该桶中 1。（分数：2.00）填空项 1:_ （正确答案：已有 m 个同义词的记录(或：已有 m 个记录；或：已满)）解析：三、B解答题/B(总题数：2，分数：30.00)假设以数组 seqnm存放循环队列的元素，设变量 rear 和 qHelen 分别指示循环队列中队尾元素的位置和元素的个数。 (1)写出队满的条件表达式； (2)写出队空的条件表达
24、式； (3)设 m=40，rear=13，quelen=19，求队头元素的位置； (4)写出一般情况下队头元素位置的表达式。（分数：19.98）(1).（分数：3.33）_正确答案：()解析：(2).（分数：3.33）_正确答案：()解析：quelen=0(3).（分数：3.33）_正确答案：()解析：35(4).（分数：3.33）_正确答案：()解析：(rear-quelen+1+m)%m_解析：_解析：对 7 个关键字进行快速排序，在最好的情况下仅需进行 10 次关键字的比较。 (1)假设关键字集合为1,2,3,4,5,6,7，试举出能达到上述结果的初始关键字序列； (2)对所举序列进行快
25、速排序，写出排序过程。（分数：10.00）(1).（分数：5.00）_正确答案：()解析：(2).（分数：5.00）_正确答案：()解析：初始关键字 4 7 1 3 6 5 2 一次划分后得 (2 3 1)4(6 5 7) 继续划分后得 (1)2(3) (5)6(7)四、B算法阅读题/B(总题数：4，分数：55.00)阅读下列算法，并回答问题： (1)设顺序表 L=(3,7,11,14,20,51)，写出执行 f30( while(iL-lengthjLlength;j+) Ldataj-1=Ldataj; Llength-; else for(j=Llength;ji;j-) Ldataj=
26、Ldataj-1; Ldatai=x; Llength+; （分数：15.00）(1).（分数：5.00）解析：填空项 1:_ （正确答案：(4,7,14,20,51)）解析：(3).（分数：5.00）_正确答案：()解析：当非递减顺序表中存在元素 x 时，从表中删除该元素；否则将 X 保序插入到顺序表中。已知图的邻接表表示的形式说明如下： #define MaxNum 50 /图的最大顶点数 typedef struct node int adjvex; /邻接点域 struct node*next; /链指针域 EdgeNode; /边表结点结构描述 typedef struct char
27、 vertex; /顶点域 EdgeNode*firstedge;/边表头指针 VertexNode; /顶点表结点结构描述 typedef struet VertexNode adjlistMaxNum;/邻接表 int n,e; /图中当前的顶点数和边数 ALGraph; /邻接表结构描述 下列算法输出图 G 的深度优先生成树(或森林)的边。阅读算法，并在空缺处填入合适的内容，使其成为一个完整的算法。 typedef enumFALSE,TRUEBoolean; Boolean visitedMaxNurn; void DFSForest(ALGraph*G) int i; for(i=0
28、;iGn;i+)visitedi=U (1) /U; for(i=0;iGn;i+)if(!visitedi)DFSTree(G,i); void DFSTree(ALGraph*G,int i) EdgeNode*p; visitedi=TRUE; p=Gadjlisti.firstedge; while(p!=NULL) if(!visitedpadjvex) printf(“%c,%c“,Gadjlisti.vertex, Gadjlistpadjvex.vertex); U (2) /U; U (3) /U; （分数：15.00）(1).（分数：5.00）解析：填空项 1:_ （正确答
29、案：DFSTree(G,Padjvex)）解析：填空项 1:_ （正确答案：p=pnext）解析：阅读下列算法，并回答问题： (1)假设数组 L8=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;in-1;i+) while(Ri!=i) t=RRi-1; RRi=Ri; Ri=t; （分数：10.00）(1).（分数：5.00）解析：填空项 1:_ （正确答案：共进行 5 次元素交换。）解析：已知带头结点的单链表中的关键字为整数，
30、为提高查找效率，需将它改建为采用拉链法处理冲突的散列表。设散列表的长度为 m，散列函数为 Hash(key)=key%m。链表的结点结构为：。请在空缺处填入适当内容，使其成为一个完整算法。 void f33(LinkList L,LinkList H,int m) /由带头结点的单链表 L 生成散列表 H，散列表生成之后原链表不再存在 int i,j; LinkList p,q; for(i=0;im;i+) Hi=U (1) /U; p=Lnext; while(p) q=pnext j=pkey%m; U (2) /U; Hj=p; U (3) /U; free(L); （分数：15.00
31、）(1).（分数：5.00）解析：填空项 1:_ （正确答案：pnext=Hj）解析：填空项 1:_ （正确答案：p=q）解析：五、B算法设计题/B(总题数：1，分数：20.00)假设以带双亲指针的二叉链表作为-二叉树的存储结构，其结点结构的类型说明如下所示： typedef char DataType; typedef struct node DataType data; struct node*lchild,*rchild; /左右孩子指针 struct node*parent; /指向双亲的指针 BinTNode; typedef BinTNode*BinTree; 若 px 为指向非空
32、二叉树中某个结点的指针，可借助该结构求得 px 所指结点在二叉树的中序序列中的后继。（分数：20.00）(1).就后继的不同情况，简要叙述实现求后继操作的方法；（分数：10.00）_正确答案：()解析：分两种情况讨论 当*px 的右子树不为空时，则从*px 的右孩子开始，沿其左孩子往下查找，直至找到一个没有左孩子的结点为止，则该结点为*pX 在中序序列中的后继； 当*px 的右子树为空时，则沿*px 的双亲指针链向上查找，直至找到其左子树中包含*px 的最年轻祖先，则该祖先结点为*px 在中序序列中的后继。(2).编写算法求 px 所指结点的中序序列后继，并在算法语句中加注注释。（分数：10.00）_正确答案：()解析：BinTree f34(BinTree px) BinTree q=pxrchild; if(q!=NULL) /沿左孩子往下查找 px=q; while(pxlchild!=NULL) px=pxlchild; else /沿双亲指针链向上查找 while(px!=NULL px=pxparent; retun px； /返回所找到的中序序列后继结点的指针 /或者无后继结点时返回空指针
