《2002年10月自考数据结构试题真题.pdf》由会员分享，可在线阅读，更多相关《2002年10月自考数据结构试题真题.pdf（6页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、欢迎您阅读并下载本文档，本文档来源于互联网，如有侵权请联系删除！我们将竭诚为您提供优质的文档！更多优质免费自考资料尽在豆瓣小组-自考乐园俱乐部（）欢迎加入.欢迎交流.止不住的惊喜等着你.02331#数据结构试题第 1 页 共 6 页 全国 2002 年 10 月高等教育自学考试 数据结构试题 课程代码：02331 一、单项选择题(本大题共 15 小题，每小题 2 分，共 30 分)在每小题列出的四个选项中只有一个选项是符合题目要求的，请将正确选项前的字母填在题后的括号内。1.若结点的存储地址与其关键字之间存在某种映射关系，则称这种存储结构为()A.顺序存储结构 B.链式存储结构 C.索引存储结
2、构 D.散列存储结构 2.在长度为 n 的顺序表的第 i(1in+1)个位置上插入一个元素，元素的移动次数为()A.n-i+1 B.n-i C.i D.i-1 3.对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构为()A.顺序表 B.用头指针表示的单循环链表 C.用尾指针表示的单循环链表 D.单链表 4.若进栈序列为 a,b,c，则通过入出栈操作可能得到的 a,b,c 的不同排列个数为()A.4 B.5 C.6 D.7 5.为查找某一特定单词在文本中出现的位置，可应用的串运算是()A.插入 B.删除 C.串联接 D.子串定位 6.已知函数 Sub(s,i,j)的功能是返回串 s 中
3、从第 i 个字符起长度为 j 的子串，函数 Scopy(s,t)的功能为复制串 t 到 s。若字符串 S=SCIENCESTUDY，则调用函数 Scopy(P,Sub(S,1,7)后得到()A.P=SCIENCE B.P=STUDY C.S=SCIENCE D.S=STUDY 7.三维数组 A456按行优先存储方法存储在内存中，若每个元素占 2 个存储单元，且数组中第一个元素的存储地址为 120，则元素 A45的存储地址为()A.356 B.358 C.360 D.362 8.如右图所示广义表是一种()A.线性表 B.纯表 C.结点共享表 D.递归表 9.下列陈述中正确的是()A.二叉树是度为
4、 2 的有序树 B.二叉树中结点只有一个孩子时无左右之分 C.二叉树中必有度为 2 的结点 D.二叉树中最多只有两棵子树，并且有左右之分 10.n 个顶点的有向完全图中含有向边的数目最多为()欢迎您阅读并下载本文档，本文档来源于互联网，如有侵权请联系删除！我们将竭诚为您提供优质的文档！更多优质免费自考资料尽在豆瓣小组-自考乐园俱乐部（）欢迎加入.欢迎交流.止不住的惊喜等着你.02331#数据结构试题第 2 页 共 6 页 A.n-1 B.n C.n(n-1)/2 D.n(n-1)11.已知一个有向图如右所示，则从顶点 a 出发进行深度优先偏历，不可能得到的 DFS 序列为()A.a d b e
5、 f c B.a d c e f b C.a d c b f e D.a d e f c b 12.在最好和最坏情况下的时间复杂度均为 O(nlogn)且稳定的排序方法是()A.快速排序 B.堆排序 C.归并排序 D.基数排序 13.不可能生成右图所示二叉排序树的关键字序列是()A.4 5 3 1 2 B.4 2 5 3 1 C.4 5 2 1 3 D.4 2 3 1 5 14.ALV 树是一种平衡的二叉排序树，树中任一结点的()A.左、右子树的高度均相同 B.左、右子树高度差的绝对值不超过 1 C.左子树的高度均大于右子树的高度 D.左子树的高度均小于右子树的高度 15.在 VSAM 文件的
6、控制区间中，记录的存储方式为()A.无序顺序 B.有序顺序 C.无序链接 D.有序链接 二、填空题(本大题共 10 小题，每小题 2 分，若有两个空格，每个空格 1 分，共 20 分)16.若一个算法中的语句频度之和为 T(n)=3720n+4nlogn，则算法的时间复杂度为_。17.在如图所示的链表中，若在指针 p 所指的结点之后插入数据域值相继为 a 和 b 的两个结点，则可用下列两个语句实现该操作，它们依次是_和_。欢迎您阅读并下载本文档，本文档来源于互联网，如有侵权请联系删除！我们将竭诚为您提供优质的文档！更多优质免费自考资料尽在豆瓣小组-自考乐园俱乐部（）欢迎加入.欢迎交流.止不住的
7、惊喜等着你.02331#数据结构试题第 3 页 共 6 页 18.假设以 S 和 X 分别表示进栈和退栈操作，则对输入序列 a,b,c,d,e 进行一系列栈操作SSXSXSSXXX 之后，得到的输出序列为_。19.串 S=I am a worker的长度是_。20.假设一个 10 阶的下三角矩阵 A 按列优顺序压缩存储在一维数组 C 中，则 C 数组的大小应为_。21.在 n 个结点的线索二叉链表中，有_个线索指针。22.若采用邻接矩阵结构存储具有 n 个顶点的图，则对该图进行广度优先遍历的算法时间复杂度为_。23.对关键字序列(52，80，63，44，48，91)进行一趟快速排序之后得到的结
8、果为_。24.由 10000 个结点构成的二叉排序树，在等概率查找的假设下，查找成功时的平均查找长度的最大值可能达到_。25.若要找出所有工资低于 1500 元，职称是副教授，及所有工资低于 2000 元，职称是教授的记录，则查询条件是_。三、解答题(本大题共 4 小题，每小题 5 分，共 20 分)26.已知一个 6 行 5 列的稀疏矩阵中非零元的值分别为：-90，41，-76，28，-54，65 和-8，它们在矩阵中的列号依次为：1，4，5，1，2，4 和 5。当以带行表的三元组表作存储结构时，其行表 RowTab 中的值依次为 0，0，2，2，3 和 5。请写出该稀疏矩阵(注：矩阵元素的
9、行列下标均从 1 开始)。27.已知树 T 的先序遍历序列为 ABCDEFGHJKL，后序遍历序列为 CBEFDJIKLHGA。请画出树 T。28.对关键字序列(72，87，61，23，94，16，05，58)进行堆排序，使之按关键字递减次序排列。请写出排序过程中得到的初始堆和前三趟的序列状态。初始堆：_ 第 1 趟：_ 第 2 趟：_ 第 3 趟：_ 29.在关键字序列(07，12，15，18，27，32，41，92)中用二分查找法查找和给定值 92 相等的关键字，请写出查找过程中依次和给定值“92”比较的关键字。四、算法阅读题(本大题共 4 小题，每小题 5 分，共 20 分)30.以下函
10、数中，h 是带头结点的双向循环链表的头指针。(1)说明程序的功能；(2)当链表中结点数分别为1和6(不包括头结点)时，请写出程序中while循环体的执行次数。int f(DListNode*h)DListNode*p,*q;int j=1;p=h-next;q=h-prior;while(p!=q&p-prior!=q)欢迎您阅读并下载本文档，本文档来源于互联网，如有侵权请联系删除！我们将竭诚为您提供优质的文档！更多优质免费自考资料尽在豆瓣小组-自考乐园俱乐部（）欢迎加入.欢迎交流.止不住的惊喜等着你.02331#数据结构试题第 4 页 共 6 页 if(p-data=q-data)p=p-n
11、ext;q=q-prior;else j=0;return j;31.设栈 S=(1,2,3,4,5,6,7),其中 7 为栈顶元素。请写出调用 algo(&s)后栈 S 的状态。void algo(Stack*S)int i=0;Queue Q;Stack T;InitQueue(&Q);InitStack(&T);while(!StackEmpty(S)if(i=!i)!=0)Push(&T,Pop(&S);else EnQueue(&Q,Pop(&S);while(!QueueEmpty(Q)Push(&S,DeQueue(&Q);while(!StackEmpty(T)Push(&S,
12、Pop(&T)；32.已知带权图的邻接矩阵表示和邻接表表示的形式说明分别如下：#define MaxNum 50/图的最大顶点数#define INFINITY INT_MAX/INT_MAX 为最大整数，表示 typedef struct char vexsMaxNum;/字符类型的顶点表 int edgesMaxNumMaxMum;/权值为整型的邻接矩阵 int n,e;/图中当前的顶点数和边数 MGraph;/邻接矩阵结构描述 typedef struct node int adjvex;/邻接点域 int weight;/边的权值 struct node*next;/链指针域 Edge
13、Node;/边表结点结构描述 typedef struct char vertex;/顶点域 EdgeNode*firstedge;/边表头指针 欢迎您阅读并下载本文档，本文档来源于互联网，如有侵权请联系删除！我们将竭诚为您提供优质的文档！更多优质免费自考资料尽在豆瓣小组-自考乐园俱乐部（）欢迎加入.欢迎交流.止不住的惊喜等着你.02331#数据结构试题第 5 页 共 6 页 VertexNode;/顶点表结点结构描述 typedef struct VertexNode adjlistMaxNum;/邻接表 int n,e;/图中当前的顶点数和边数 ALGraph;/邻接表结构描述 下列算法是
14、根据一个带权图的邻接矩阵存储结构 G1 建立该图的邻接表存储结构 G2，请填入合适的内容，使其成为一个完整的算法。void convertM(MGraph*G1,ALGraph*G2)int i,j;EdgeNode*p;G2-n=G1-n;G2-e=G1-e;for(i=0;in;i+)G2-adjlisti.vertex=G1-vexsi;G2-adjlisti.firstedge=(1);for(i=0;in;i+)for(j=0;jn;j+)if(G1-edgesijweight=(2);p-adjvex=j;p-next=G2-adjlisti.firstedge;(3);(1)(2
15、)(3)33.阅读下列算法，并回答下列问题：(1)该算法采用何种策略进行排序?(2)算法中 Rn+1的作用是什么?Typedef struct KeyType key;infoType otherinfo;nodeType;typedef nodeType SqListMAXLEN;欢迎您阅读并下载本文档，本文档来源于互联网，如有侵权请联系删除！我们将竭诚为您提供优质的文档！更多优质免费自考资料尽在豆瓣小组-自考乐园俱乐部（）欢迎加入.欢迎交流.止不住的惊喜等着你.02331#数据结构试题第 6 页 共 6 页 void sort(SqList R,int n)/n 小于 MAXLEN-1 i
16、nt k;i;for(k=n-1;k=1;k-)if(Rk.keyRk+1.key)Rn+1=Rk;for(i=k+1;Ri.keyRn+1.key;i+)Ri-1=Ri;Ri-1=Rn+1;五、算法设计题(本题共 10 分)34.假设二叉树 T 采用如下定义的存储结构：typedef struct node DataType data;struct node*lchild,*rchild,*parent;PBinTree;其中，结点的 lchild 域和 rchild 域已分别填有指向其左、右孩子结点的指针，而 parent 域中的值为空指针(拟作为指向双亲结点的指针域)。请编写一个递归算法，将该存储结构中各结点的 parent域的值修改成指向其双亲结点的指针。