《2022年月自考数据结构试题真题.docx》由会员分享，可在线阅读，更多相关《2022年月自考数据结构试题真题.docx（9页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、精选学习资料 - - - - - - - - - 全国2005年1月高等训练自学考试数据结构试卷课程代码： 02331 第一部分 挑选题 共30分 一、单项挑选题 本大题共 15小题,每道题 2分,共 30分 在每道题列出的四个备选项中只有一个是符合题目要求的,请将其代码填写在题后的括号内；错选、多项或未选均无分；1.数据元素及其关系在运算机储备器内的表示,称为数据的 A. 规律结构 B.储备结构C.线性结构 D.非线性结构2.某带头结点的单链表的头指针为 head,判定该链表为非空的条件是 A.head=NULL B.head-next=NULL C.head.=NULL D.head-ne
2、xt.=NULL 3.导致栈上溢的操作是 A. 栈满时执行的出栈 B.栈满时执行的入栈C.栈空时执行的出栈 D.栈空时执行的入栈4.设数组 Am 为循环队列 Q的储备空间, front 为队头指针, rear为队尾指针,就判定 Q为空队列的条件是 A.rear - front%m= =1 B.front= =rear C.rear- front%m= =m - 1 D.front= =rear+1%m 5.假设 S= I AM A STUDENT ,就运算 substrS,4,8的结果为 A. M A S B. M A STUDC. A STUDEN D. STUD6.在执行简洁的串匹配算法时
3、,最坏的情形为每次匹配比较不等的字符显现的位置均为 A. 模式串的最末字符 B.主串的第一个字符C.模式串的第一个字符 D.主串的最末字符7.从广义表 L=d,c,d 中分解得到 d的操作为 A.headheadheadL B.headtailheadL C.tailheadheadL D.tailtailheadL 8.假设一棵完全二叉树按层次遍历的次序依次存放在数组 BTm 中,其中根结点存放在 BT0,如 BTi 中的结点有左孩子,就左孩子存放在 A.BTi/2 B.BT2*i-1 C.BT2*i D.BT2*i+1 9.右图所示二叉树的中序序列是 1 / 6 名师归纳总结 - - -
4、- - - -第 1 页,共 6 页精选学习资料 - - - - - - - - - A.DHEBAFIJCG B.DHEBAFJICG C.DBHEAFCJIG D.DBHEAFJICG 10.连通图是指图中任意两个顶点之间 A. 都连通的无向图 B.都不连通的无向图C.都连通的有向图 D.都不连通的有向图11.下图所示带权无向图的最小生成树的权为 A.14 B.15 C.17 D.18 12.对记录序列 314,298, 508,123,486,145依次按个位和十位进行两趟基数排序之后所得结果为 A.123 ,145,298,314,486,508 C.486,314,123,145,5
5、08,298 B.508 ,314,123, 145,486,298 D.298,123,508, 486,145,314 13.在待排关键字序列基本有序的前提下,效率最高的排序方法是 A. 直接插入排序 B.快速排序C.直接挑选排序 D.归并排序14.在以下各棵二叉树中,二叉排序树是 15.采纳 ISAM 或VSAM 组织的文件是 A. 索引非次序文件 B.次序文件C.索引次序文件 D.散列文件其次部分 非挑选题 共70分 2 / 6 名师归纳总结 - - - - - - -第 2 页,共 6 页精选学习资料 - - - - - - - - - 二、填空题 本大题共 10小题,每道题 2分,
6、共 20分 请在每道题的空格中填上正确答案；错填、不填均无分；16.在一个长度为 n的循环链表中,删除其元素值为 x的结点的时间复杂度为 _；17.已知指针 p指向某单链表中的一个结点,就判别该结点有且仅有一个后继结点的条件是 _；18.假如入栈序列是1,3,5, ,97,99,且出栈序列的第一个元素为99,就出栈序列中第30个元素为 _；19.已知广义表 LS为空表,就其深度为 _；20.假设以行优先次序储备三维数组A567 ,其中元素 A000 的地址为 1100,且每个元素占 2个储备单元,就 A432 的地址是 _；21.已知一棵二叉树的先序序列为 ABCD ,中序序列为 BCAD ,
7、就它的后序序列为 _；22.在含 n个顶点的连通图中,任意两个不同顶点之间的一条简洁路径最多包含 _条边；23.对关键字序列 50,34, 92,19,11,68,56,41,79进行直接插入排序,当将第 7个关键字 56插入到当前的有序子表中时,为查找插入位置需进行 较；_次关键字之间的比24.对有序表进行二分查找的过程可用判定树来描述,其判定树的形状只取决于 _；25.将有序表中 n个元素依次插入到一棵空的二叉排序树中,就在等概率查找的情形下,该二叉排序树在查找胜利时的平均查找长度是 _；三、解答题 本大题共 4小题,每道题 5分,共 20分 26.1写出右侧图形表示的广义表 L ；2画出
8、其表头与表尾均为 1 2 a,b,c 的广义表 L1的图形表；27.试推导一棵满 k叉树上的叶子结点数a与非叶子结点数b之间满意以下关系： a=k-1b+1 28.假设用迪杰斯特拉Dijkstra 算法求以下图中从顶点a到其余各顶点的最短路径,按求解过程依次写出各条最短路径及其长度；29.已知关键字序列在 R1.8 中的初始状态为R 48 70 33 65 24 56 12 92 1 2 3 4 5 6 7 8 3 / 6 名师归纳总结 - - - - - - -第 3 页,共 6 页精选学习资料 - - - - - - - - - 写出在将它调整为大根堆的过程中每一次挑选后 R的状态；四、算
9、法阅读题 本大题共 4小题,每道题 5分,共 20分 30.假如期望循环队列中的向量单元都能得到利用,就可设置一个标志域 tag,每当尾指针和 头指针值相同时,以 tag的值为 0或1来区分队列状态是“空” 仍是 “ 满”；请对以下函数填空,使其分别实现与此结构相应的入队列和出队列的算法；int EnQueueCirQueue *Q,DataType x if 1 return 0 ；Q- dataQ- rear=x ；Q- rear=Q - rear+1% MAXQSIZE 2 return 1 ； int DeQueueCirQueue *Q,DataType *x if 3 return
10、 0 ；*x=Q - dataQ-front ；Q- front= 4 ； 5 ；return 1； 1 2 3 4 5 31.已知具有 n个结点的完全二叉树采纳次序储备结构储备在向量 素为字符类型,请阅读以下算法,并回答疑题：1假设向量 BT 中的内容为：BT A B C D E F 1 2 3 4 5 6 写出执行 f31BT,6 后的输出结果；2说明该算法的功能；void f31char BT,int n int i=1 ； whilei0 ifi printf %c , BTi i=i*2 ； else 4 / 6 BT1.n 中,结点的数据元名师归纳总结 - - - - - - -第
11、 4 页,共 6 页精选学习资料 - - - - - - - - - do i=i/2 ； whilei%2 ； ifi0 i+ ； 1 2 32.设数组 f 的初始元素序列为：f1.9=1,3,2,3,3,2,1,2,1 阅读以下算法,并回答疑题；其中算法 值；f32中调用的函数 swapa,b用以完成交换 a和b的1写出执行 f32f,9,3,1 之后 f1.9 中的元素序列,并写出在执行过程中调用 swap函数的 次数；2简述算法 f32的功能；void f32int f,int n,int x,int y int i=1,j=1,k=n ； while j if fj=yj+； els
12、e if fj=x ；i+ ；j+ ； swapfi,fj else swapfk,fj；k-； 1 2 33.以下算法利用二分查找方法在有序表r中插入元素 x,并保持表 r的有序性,其中参数*n为表r的长度；请在空缺处填入合适的内容,使其成为一个完整的算法；void BinInsertSeqList r,int *n,DataType x int low=1,high=*n,mid,i；whilelow mid= 1 ；if x.keyhigh=mid-1；else 2 ； fori=*n ； 3 ；i- ri+1=ri ； 4 ；*n+ ； 1 2 5 / 6 名师归纳总结 - - - -
13、 - - -第 5 页,共 6 页精选学习资料 - - - - - - - - - 3 4 五、算法设计题 此题共 10分 34.假设一元多项式以循环链表表示,链表的结点结构为：typedef struct PNode float coef ； /系数 int exp ； /指数 struct PNode *next ；*LinkList；h表示的代数多项式拆分成两个多项式循环链表 h1和h2,其中 现需要将一个用循环链表h1仅含多项式的奇次项,h2仅含多项式的偶次项；要求利用原链表中的结点构成链表 h 1和h2；例如多项式 7x 8+5x 3- 4x的循环链表为经拆分之后的情形应是：请编写完成上述拆分的算法,并进行算法分析；6 / 6 名师归纳总结 - - - - - - -第 6 页,共 6 页