《2005年10月自考数据结构试题及答案.pdf》由会员分享，可在线阅读，更多相关《2005年10月自考数据结构试题及答案.pdf（7页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、欢迎您阅读并下载本文档，本文档来源于互联网，如有侵权请联系删除！我们将竭诚为您提供优质的文档！1/7 2005 年 10 月自考 数据结构试题 课程代码：02331 一、单项选择题(本大题共 15 小题，每小题 2 分，共 30 分)1.若将数据结构形式定义为二元组(K，R)，其中 K 是数据元素的有限集合，则 R 是 K 上(D)A.操作的有限集合 B.映象的有限集合 C.类型的有限集合 D.关系的有限集合 2.在长度为 n 的顺序表中删除第 i 个元素(1in)时，元素移动的次数为(D)A.n-i+1 B.i C.i+1 D.n-i 3.若不带头结点的单链表的头指针为 head，则该链表为
2、空的判定条件是(A)A.head=NULL B.head-next=NULL C.head!=NULL D.head-next=head 4.引起循环队列队头位置发生变化的操作是(A)A.出队 B.入队 C.取队头元素 D.取队尾元素 5.若进栈序列为 1，2，3，4，5，6，且进栈和出栈可以穿插进行，则不可能出现的出栈序列是(D)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 6.字符串通常采用的两种存储方式是(C)A.散列存储和索引存储 B.索引存储和链式存储 C.顺序存储和链式存储 D.散列存储和顺序存储 7.设主串长为 n
3、，模式串长为 m(mn)，则在匹配失败情况下，朴素匹配算法进行的无效位移次数为(C)A.m B.n-m C.n-m+1 D.n 8.二维数组 A12 18采用列优先的存储方法，若每个元素各占 3 个存储单元，且第 1个元素的地址为 150，则元素 A9 7的地址为(A)A.429 B.432 C.435 D.438 9.对广义表 L=(a,b),(c,d),(e,f)执行操作 tail(tail(L)的结果是(B)A.(e,f)B.(e,f)C.(f)D.()10.下列图示的顺序存储结构表示的二叉树是(A)欢迎您阅读并下载本文档，本文档来源于互联网，如有侵权请联系删除！我们将竭诚为您提供优质的
4、文档！2/7 11.n 个顶点的强连通图中至少含有(B)A.n-1 条有向边 B.n 条有向边 C.n(n-1)/2 条有向边 D.n(n-1)条有向边 12.对关键字序列(56，23，78，92，88，67，19，34)进行增量为 3 的一趟希尔排序的结果为(D)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-树中插入关键字引起结点分裂，则该结点在插入前含有的关键字个数为(C)A.4 B.5 C.8 D
5、.9 14.由同一关键字集合构造的各棵二叉排序树(B)A.其形态不一定相同，但平均查找长度相同 B.其形态不一定相同，平均查找长度也不一定相同 C.其形态均相同，但平均查找长度不一定相同 D.其形态均相同，平均查找长度也都相同 15.ISAM 文件和 VSAM 文件的区别之一是(C)A.前者是索引顺序文件，后者是索引非顺序文件 B.前者只能进行顺序存取，后者只能进行随机存取 C.前者建立静态索引结构，后者建立动态索引结构 D.前者的存储介质是磁盘，后者的存储介质不是磁盘 二、填空题(本大题共 10 小题，每空 2 分，共 20 分)16.数据的逻辑结构在计算机存储器内的表示，称为数据的（存储结
6、构）。欢迎您阅读并下载本文档，本文档来源于互联网，如有侵权请联系删除！我们将竭诚为您提供优质的文档！3/7 17.删 除 双 向 循 环 链 表 中*p的 前 驱 结 点(存 在)应 执 行 的 语 句 是（p-prior=p-prior-prior;p-prior-next=p;）。18.栈下溢是指在（空栈）时进行出栈操作。19.已知 substr(s,i,len)函数的功能是返回串 s 中第 i 个字符开始长度为 len 的子串，strlen(s)函数的功能是返回串 s 的长度。若 s=ABCDEFGHIJK,t=ABCD,执行运算substr(s,strlen(t),strlen(t)后
7、的返回值为（EFGH）。20.去除广义表 LS=(a1,a2,a3,，an)中第 1 个元素，由其余元素构成的广义表称为 LS 的（表尾）。21.已知完全二叉树 T 的第 5 层只有 7 个结点，则该树共有（11）个叶子结点。22.在有向图中，以顶点 v 为终点的边的数目称为 v 的（入度）。23.当关键字的取值范围是实数集合时，无法进行箱排序和（基数）排序。24.产生冲突现象的两个关键字称为该散列函数的（同义词）。25.假设散列文件中一个桶能存放 m 个记录，则桶“溢出”的含义是，当需要插入新的记录时，该桶中（已有 m 个记录）。三、解答题(本大题共 4 小题，每小题 5 分，共 20 分)
8、26.假设以数组 seqnm存放循环队列的元素，设变量 rear 和 quelen 分别指示循环队列中队尾元素的位置和元素的个数。(1)写出队满的条件表达式；(2)写出队空的条件表达式；(3)设 m=40,rear=13,quelen=19,求队头元素的位置；(4)写出一般情况下队头元素位置的表达式。答：(1)quelen=m(2)quelen=0(3)35(4)(rear-quelen+1+m)%m 27.已知一棵二叉树的中序序列为 ABCDEFG，层序序列为 BAFEGCD，请画出该二叉树。答：BAFEGCD 欢迎您阅读并下载本文档，本文档来源于互联网，如有侵权请联系删除！我们将竭诚为您提
9、供优质的文档！4/7 28.画出下图所示有向图的所有强连通分量。答：agfcbed 29.对 7 个关键字进行快速排序，在最好的情况下仅需进行 10 次关键字的比较。(1)假设关键字集合为1,2,3,4,5,6,7，试举出能达到上述结果的初始关键字序列；(2)对所举序列进行快速排序，写出排序过程。答：(1)4 7 1 3 6 5 2 (2)初始关键字：4 7 1 3 6 5 2 一次划分后得：（2 3 1）4（6 5 7）再次划分后得：（1）2（3）4（5）6（7）四、算法阅读题(本大题共 4 小题，每小题 5 分，共 20 分)30.阅读下列算法，并回答问题：(1)设顺序表 L=(3,7,1
10、1,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(ilength&xL-datai)i+;if(ilength&x=L-datai)for(j=i+1;jlength;j+)L-dataj-1=L-dataj;L-length-;else for(j=L-length;ji;j-)L-dataj=L-dataj-1;L-datai=x;L-length+;欢迎您阅读并下
11、载本文档，本文档来源于互联网，如有侵权请联系删除！我们将竭诚为您提供优质的文档！5/7 答：(1)（3,7,11,14,15,20,51）(2)（4,7,14,20,51）(3)当非递减顺序表中存在元素 x 时，从表中删除该元素，否则将 x 按按值的顺序插入到顺序表中。31.已知图的邻接表表示的形式说明如下：#define MaxNum 50 /图的最大顶点数 typedef struct node int adjvex;/邻接点域 struct node*next;/链指针域 EdgeNode;/边表结点结构描述 typedef struct char vertex;/顶点域 EdgeNod
12、e*firstedge;/边表头指针 VertexNode;/顶点表结点结构描述 typedef struct VertexNode adjlistMaxNum;/邻接表 int n,e;/图中当前的顶点数和边数 ALGraph;/邻接表结构描述 下列算法输出图 G 的深度优先生成树(或森林)的边。阅读算法，并在空缺处填入合适的内容，使其成为一个完整的算法。typedef enumFALSE,TRUEBoolean;Boolean visitedMaxNum;void DFSForest(ALGraph*G)int i;for(i=0;in;i+)visitedi=(1);for(i=0;in
13、;i+)if(!visitedi)DFSTree(G,i);void DFSTree(ALGraph*G,int i)EdgeNode*p;Visitedi=TRUE;p=G-adjlisti.firstedge;while(p!=NULL)if(!visitedp-adjvex printf(,G-adjlisti.vertex,G-adjlistp-adjvex.vertex);(2);(3);答：(1)FALSE (2)DFSTree(G,p-adjvex)(3)p=p-next 欢迎您阅读并下载本文档，本文档来源于互联网，如有侵权请联系删除！我们将竭诚为您提供优质的文档！6/7 32.
14、阅读下列算法，并回答问题：(1)假设数组 L8=3,0,5,1,6,4,2,7，写出执行函数调用 f32(L，8)后的 L；(2)写出上述函数调用过程中进行元素交换操作的总次数。void f32(int R,int n)int i,t;for(i=0;in-1;i+)while(Ri!=i)t=RRi;RRi=Ri;Ri=t;答：(1)L8=0,1,2,3,4,5,6,7 (2)共进行 5 次交换。33.已知带头结点的单链表中的关键字为整数，为提高查找效率，需将它改建为采用拉链法处理冲突的散列表。设散列表的长度为 m，散列函数为 Hash(key)=key%m。链表的结点结构为：keynext
15、 请在空缺处填入适当内容，使其成为一个完整算法。void f33(LinkList L,LinkList H,int m)/由带头结点的单链表 L 生成散列表 H，散列表生成之后原链表不再存在 int i,j;LinkList p,q;for(i=0;inext;while(p)q=p-next;j=p-key%m;(2);Hj=p;(3);free(L);答：(1)NULL (2)p-next=Hi (3)p=q 五、算法设计题(本大题 10 分)34.假设以带双亲指针的二叉链表作为二叉树的存储结构，其结点结构的类型说明如下所示：typedef char DataType;欢迎您阅读并下载本
16、文档，本文档来源于互联网，如有侵权请联系删除！我们将竭诚为您提供优质的文档！7/7 typedef struct node DataType data;struct node*lchild,*rchild;/左右孩子指针 struct node*parent;/指向双亲的指针 BinTNode;typedef BinTNode*BinTree;若 px 为指向非空二叉树中某个结点的指针，可借助该结构求得 px 所指结点在二叉树的中序序列中的后继。(1)就后继的不同情况，简要叙述实现求后继操作的方法；(2)编写算法求 px 所指结点的中序序列后继，并在算法语句中加注注释。答：(1)分两种情况讨论
17、 当*px 的右子树不为空时，则从*px 的右孩子开始，沿其左孩子往下查找，直至找到一个没有左孩子的结点为止则该结点为止，则该节点为*px 在中序序列中的后继。当*px 的右子树为空时，则沿*px 的双亲指针链向上查找，直至找到其左子树中包含*px的最年轻祖先，则该祖先结点为*px 的在中序序列中的后继。(2)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;return px;/返回找到的中序序列后继结点的指针 /或者无后继结点时返回空指针