《2022年月自考数据结构试题真题 .pdf》由会员分享，可在线阅读，更多相关《2022年月自考数据结构试题真题 .pdf（6页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、1 / 6 全国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-next!=NULL 3.导致栈上溢的操作是(
2、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 ，则运算 substr(S,4,8的结果为 ( A. M A S B. M A STUDC. A STUDEN D. STUD 6.在执行简单的串匹配算法时，最坏的情况为每次匹配比较不等的字
3、符出现的位置均为( A.模式串的最末字符B.主串的第一个字符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/2 B.BT2*i-1 C.BT2*i D.BT2*i+1 9.右图所示二叉树的中序序列是( 精选学习资料 - - - - - - - -
4、 - 名师归纳总结 - - - - - - -第 1 页，共 6 页2 / 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 B.508，314，123， 145，48
5、6，298 C.486，314，123，145，508，298 D.298，123，508， 486，145，314 13.在待排关键字序列基本有序的前提下，效率最高的排序方法是( A.直接插入排序B.快速排序C.直接选择排序D.归并排序14.在下列各棵二叉树中，二叉排序树是( 15.采用 ISAM 或VSAM 组织的文件是( A.索引非顺序文件B.顺序文件C.索引顺序文件D.散列文件第二部分 非选择题 (共70分 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 2 页，共 6 页3 / 6 二、填空题 (本大题共 10小题，每小题2分，共 20分
6、 请在每小题的空格中填上正确答案。错填、不填均无分。16.在一个长度为n的循环链表中，删除其元素值为x的结点的时间复杂度为_。17.已知指针 p指向某单链表中的一个结点，则判别该结点有且仅有一个后继结点的条件是_。18.如果入栈序列是1，3，5，97，99，且出栈序列的第一个元素为99，则出栈序列中第30个元素为 _。19.已知广义表 LS为空表，则其深度为_。20.假设以行优先顺序存储三维数组A567 ，其中元素 A000 的地址为 1100，且每个元素占 2个存储单元，则A432 的地址是 _。21.已知一棵二叉树的先序序列为ABCD ，中序序列为 BCAD ，则它的后序序列为_。22.在
7、含 n个顶点的连通图中，任意两个不同顶点之间的一条简单路径最多包含_条边。23.对关键字序列(50，34， 92，19，11，68，56，41，79进行直接插入排序，当将第7个关键字 56插入到当前的有序子表中时，为寻找插入位置需进行_次关键字之间的比较。24.对有序表进行二分查找的过程可用判定树来描述，其判定树的形态只取决于_。25.将有序表中 n个元素依次插入到一棵空的二叉排序树中，则在等概率查找的情况下，该二叉排序树在查找成功时的平均查找长度是_。三、解答题 (本大题共 4小题，每小题 5分，共 20分 26.(1写出右侧图形表示的广义表L。(2画出其表头与表尾均为(a,(b,c的广义表
8、 L1的图形表。(1 (2 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 页4 / 6 写出在将它调整为大根堆的过程中每一次筛选后R的状态。四、算法阅读题(本大题共 4小题，每小题5
9、分，共 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 return 0 。*x=Q - da
10、taQ-front 。Q- front= (4 。 (5 。return 1。 (1 (2 (3 (4 (5 31.已知具有 n个结点的完全二叉树采用顺序存储结构存储在向量BT1.n 中，结点的数据元素为字符类型，请阅读下列算法，并回答问题：(1假设向量 BT中的内容为：BT A B C D E F 1 2 3 4 5 6 写出执行 f31(BT,6 后的输出结果；(2说明该算法的功能。void f31(char BT,int n int i=1 。 while(i0 if(i printf( %c , BTi。 i=i*2 。 else 精选学习资料 - - - - - - - - - 名师
11、归纳总结 - - - - - - -第 4 页，共 6 页5 / 6 do i=i/2 。 while(i%2 。 if(i0 i+ 。 (1 (2 32.设数组 f的初始元素序列为：f1.9=(1,3,2,3,3,2,1,2,1 阅读下列算法，并回答问题。其中算法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 if (fj=yj
12、+。 else if (fj=x swap(fi,fj。i+ 。j+ 。 else swap(fk,fj。k-。 (1 (2 33.下列算法利用二分查找方法在有序表r中插入元素 x，并保持表 r的有序性，其中参数*n为表r的长度。请在空缺处填入合适的内容，使其成为一个完整的算法。void BinInsert(SeqList r,int *n,DataType x int low=1,high=*n,mid,i。while(low mid= (1 。if (x.keyhigh=mid-1。else (2 。 for(i=*n 。 (3 。i- ri+1=ri 。 (4 。*n+ 。 (1 (2
13、精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 5 页，共 6 页6 / 6 (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的循环链表为经拆分之后的情况应是：请编写完成上述拆分的算法，并进行算法分析。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 6 页，共 6 页