《2023年1月自考数据结构试题真题.doc》由会员分享，可在线阅读，更多相关《2023年1月自考数据结构试题真题.doc（9页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、全国2023年1月高等教育自学考试数据结构试题课程代码：02331第一部分 选择题 (共30分)一、单项选择题(本大题共15小题，每小题2分，共30分)在每小题列出的四个备选项中只有一个是符合题目规定的，请将其代码填写在题后的括号内。错选、多选或未选均无分。1.数据元素及其关系在计算机存储器内的表达，称为数据的( )A.逻辑结构B.存储结构C.线性结构D.非线性结构2.某带头结点的单链表的头指针为head，鉴定该链表为非空的条件是( )A.head=NULLB.head-next=NULLC.head!=NULLD.head-next!=NULL3.导致栈上溢的操作是( )A.栈满时执行的出栈
2、B.栈满时执行的入栈C.栈空时执行的出栈D.栈空时执行的入栈4.设数组Am为循环队列Q的存储空间，front为队头指针，rear为队尾指针，则鉴定Q为空队列的条件是( )A.(rear-front)%m= =1B.front= =rearC.(rear-front)%m= =m-1D.front= =(rear+1)%m5.假设S=I AM A STUDENT，则运算substr(S,4,8)的结果为( )A.M A SB.M A STUDC.A STUDEND.STUD6.在执行简朴的串匹配算法时，最坏的情况为每次匹配比较不等的字符出现的位置均为( )A.模式串的最末字符B.主串的第一个字符
3、C.模式串的第一个字符D.主串的最末字符7.从广义表L=(d),c,d)中分解得到(d)的操作为( )A.head(head(head(L)B.head(tail(head(L)C.tail(head(head(L)D.tail(tail(head(L)8.假设一棵完全二叉树按层次遍历的顺序依次存放在数组BTm中，其中根结点存放在BT0，若BTi中的结点有左孩子，则左孩子存放在( )A.BTi/2B.BT2*i-1C.BT2*iD.BT2*i+19.右图所示二叉树的中序序列是( )A.DHEBAFIJCGB.DHEBAFJICGC.DBHEAFCJIGD.DBHEAFJICG10.连通图是指图
4、中任意两个顶点之间( )A.都连通的无向图B.都不连通的无向图C.都连通的有向图D.都不连通的有向图11.下图所示带权无向图的最小生成树的权为( )A.14B.15C.17D.1812.对记录序列(314，298，508，123，486，145)依次按个位和十位进行两趟基数排序之后所得结果为( )A.123，145，298，314，486，508B.508，314，123，145，486，298C.486，314，123，145，508，298D.298，123，508，486，145，31413.在待排关键字序列基本有序的前提下，效率最高的排序方法是( )A.直接插入排序B.快速排序C.直接
5、选择排序D.归并排序14.在下列各棵二叉树中，二叉排序树是( )15.采用ISAM或VSAM组织的文献是( )A.索引非顺序文献B.顺序文献C.索引顺序文献D.散列文献第二部分 非选择题 (共70分)二、填空题(本大题共10小题，每小题2分，共20分)请在每小题的空格中填上对的答案。错填、不填均无分。16.在一个长度为n的循环链表中，删除其元素值为x的结点的时间复杂度为_。17.已知指针p指向某单链表中的一个结点，则判别该结点有且仅有一个后继结点的条件是_。18.假如入栈序列是1，3，5，97，99，且出栈序列的第一个元素为99，则出栈序列中第30个元素为_。19.已知广义表LS为空表，则其深
6、度为_。20.假设以行优先顺序存储三维数组A567，其中元素A000的地址为1100，且每个元素占2个存储单元，则A432的地址是_。21.已知一棵二叉树的先序序列为ABCD，中序序列为BCAD，则它的后序序列为_。22.在含n个顶点的连通图中，任意两个不同顶点之间的一条简朴途径最多包含_条边。23.对关键字序列(50，34，92，19，11，68，56，41，79)进行直接插入排序，当将第7个关键字56插入到当前的有序子表中时，为寻找插入位置需进行_次关键字之间的比较。24.对有序表进行二分查找的过程可用鉴定树来描述，其鉴定树的形态只取决于_。25.将有序表中n个元素依次插入到一棵空的二叉排
7、序树中，则在等概率查找的情况下，该二叉排序树在查找成功时的平均查找长度是_。三、解答题(本大题共4小题，每小题5分，共20分)26.(1)写出右侧图形表达的广义表L。(2)画出其表头与表尾均为(a,(b,c)的广义表L1的图形表。(1)(2)27.试推导一棵满k叉树上的叶子结点数a与非叶子结点数b之间满足以下关系： a=(k-1)b+128.假设用迪杰斯特拉(Dijkstra)算法求下列图中从顶点a到其余各顶点的最短途径，按求解过程依次写出各条最短途径及其长度。29.已知关键字序列在R1.8中的初始状态为R487033652456129212345678 写出在将它调整为大根堆的过程中每一次筛
8、选后R的状态。四、算法阅读题(本大题共4小题，每小题5分，共20分)30.假如希望循环队列中的向量单元都能得到运用，则可设立一个标志域tag,每当尾指针和头指针值相同时，以tag的值为0或1来区分队列状态是“空”还是“满”。请对下列函数填空，使其分别实现与此结构相应的入队列和出队列的算法。int EnQueue(CirQueue *Q,DataType x)if( (1) ) return 0;Q-dataQ-rear=x;Q-rear=(Q-rear+1)% MAXQSIZE (2) return 1;int DeQueue(CirQueue *Q,DataType *x)if( (3) )
9、 return 0;*x=Q-dataQ-front;Q-front= (4) ; (5) ;return 1;(1)(2)(3)(4)(5)31.已知具有n个结点的完全二叉树采用顺序存储结构存储在向量BT1.n中，结点的数据元素为字符类型，请阅读下列算法，并回答问题：(1)假设向量BT中的内容为：BTABCDEF123456写出执行f31(BT,6)后的输出结果；(2)说明该算法的功能。void f31(char BT,int n) int i=1; while(i0) if(i0) i+; (1)(2)32.设数组f的初始元素序列为：f1.9=(1,3,2,3,3,2,1,2,1)阅读下列
10、算法，并回答问题。其中算法f32中调用的函数swap(a,b)用以完毕互换a和b的值。(1)写出执行f32(f,9,3,1)之后f1.9中的元素序列，并写出在执行过程中调用swap函数的次数。(2)简述算法f32的功能。void f32(int f,int n,int x,int y) int i=1,j=1,k=n; while (j=k) if (fj=y)j+; else if (fj=x) swap(fi,fj);i+;j+; else swap(fk,fj;k-;(1)(2)33.下列算法运用二分查找方法在有序表r中插入元素x，并保持表r的有序性，其中参数*n为表r的长度。请在空缺处
11、填入合适的内容，使其成为一个完整的算法。void BinInsert(SeqList r,int *n,DataType x) int low=1,high=*n,mid,i;while(low=high) mid= (1) ;if (x.keyrmid.key)high=mid-1;else (2) ;for(i=*n; (3) ;i-)ri+1=ri; (4) ;*n+;(1)(2)(3)(4)五、算法设计题(本题共10分)34.假设一元多项式以循环链表表达，链表的结点结构为：typedef struct PNode float coef; /系数int exp; /指数struct PNode *next;*LinkList;现需要将一个用循环链表h表达的代数多项式拆提成两个多项式循环链表h1和h2，其中h1仅含多项式的奇次项，h2仅含多项式的偶次项。规定运用原链表中的结点构成链表h1和h2。例如多项式7x8+5x3-4x的循环链表为经拆分之后的情况应是：请编写完毕上述拆分的算法，并进行算法分析。