2023年自考数据结构02331历年试题及答案.doc

《2023年自考数据结构02331历年试题及答案.doc》由会员分享，可在线阅读，更多相关《2023年自考数据结构02331历年试题及答案.doc（127页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、自考数据结构02331历年试题及答案(2023-2023个人整理版)全国2023年1月自学考试数据结构试题一、单项选择题(本大题共15小题，每小题2分，共30分)在每小题列出的四个备选项中只有一个是符合题目规定的，请将其代码填写在题后的括号内。错选、多选或未选均无分。1.下列程序段的时间复杂度为( )9 s=0； for(i=1；in；i+) for(j=1；jnext=NULL；C.head!=NULL；D.head-next=head；3.栈是一种操作受限的线性结构，其操作的重要特性是( )32A.先进先出B.后进先出C.进优于出D.出优于进4.假设以数组An存放循环队列的元素，其头、尾指

2、针分别为front和rear。若设定尾指针指向队列中的队尾元素，头指针指向队列中队头元素的前一个位置，则当前存于队列中的元素个数为( )A.(rear-front-1)nB.(rear-front)nC.(front-rear+1)nD.(rear-front+n)n5.判断两个串大小的基本准则是( )52A.两个串长度的大小B.两个串中首字符的大小C.两个串中大写字母的多少D.相应的第一个不等字符的大小6.二维数组A45按行优先顺序存储，若每个元素占2个存储单元，且第一个元素A00的存储地址为1000，则数组元素A32的存储地址为( )60A.1012B.1017C.1034D.1036a0

3、0a01a02a03a04a327.高度为5的完全二叉树中具有的结点数至少为( )72A.16B.17C.31D.328.已知在一棵度为3的树中，度为2的结点数为4，度为3的结点数为3，则该树中的叶子结点数为( )A.5B.8C.11D.189.下列所示各图中是中序线索化二叉树的是( A )81A10.已知含6个顶点(v0，v1，v2，v3，v4，v5)的无向图的邻接矩阵如图所示，则从顶点v0出发进行深度优先遍历也许得到的顶点访问序列为( )108A.(v0，v1，v2，v5，v4，v3)B.(v0，v1，v2，v3，v4，v5)C.(v0，v1，v5，v2，v3，v4)D.(v0，v1，v4

4、，v5，v2，v3)11.如图所示有向图的一个拓扑序列是( )A.ABCDEFB.FCBEADC.FEDCBAD.DAEBCF12.下列关键字序列中，构成大根堆的是( )A.5，8，1，3，9，6，2，7B.9，8，1，7，5，6，2，33C.9，8，6，3，5，l，2，7D.9，8，6，7，5，1，2，313.对长度为15的有序顺序表进行二分查找，在各记录的查找概率均相等的情况下，查找成功时所需进行的关键字比较次数的平均值为( )172A.B.C.D.14.已知一个散列表如图所示，其散列函数为H(key)=key11，采用二次探查法解决冲突，则下一个插入的关键字49的地址为( D )d 19

5、715.数据库文献是由大量带有结构的( )206A.记录组成的集合B.字符组成的集合C.数据项组成的集合D.数据结构组成的集合二、填空题(本大题共10小题，每小题2分，共20分)请在每小题的空格中填上对的答案。错填、不填均无分。16.估算算法时间复杂度时考虑的问题规模通常是指算法求解问题的_输入量_。 817.在双向循环链表中插入一个新的结点时，应修改_4_个指针域的值。 2818.若进栈序列为a，b，c，且进栈和出栈可以穿插进行，则也许出现_5_个不同的出栈序列。519.链串的结点大小定义为结点的_数据域_中存放的字符个数。 5420.广义表(a，(d，(c)的深度为_3 _。6721.在具

6、有3个结点a，b，c的二叉树中，前序序列为abc且后序序列为cba的二叉树有_4_棵。422.若用邻接矩阵表达有向图，则顶点i的入度等于矩阵中_。第i列非零元素的个数10723.对关键字序列(15，18，11，13，19，16，12，17，10，8)进行增量为5的一趟希尔排序的结果为_。 15，12，11，10，8，16，18，1724.索引顺序查找的索引表由各分块中的最大关键字及各分块的_起始位置_构成。17325.VSAM文献的实现依赖于操作系统中的_分页_存取方法的功能。 215三、解答题(本大题共4小题，每小题5分，共20分)26.假设有一个形如的88矩阵，矩阵元素都是整型量(次对角线

7、以上的元素都是0)。若将上述矩阵中次对角线及其以下的元素按行优先压缩存储在一维数组B中，请回答下列问题：(1)B数组的体积至少是多少?(2)若a18存储在B0中，a56存储在Bk中，则k值为多少?(1) （1+8）*8/2=36 存放次对角线以上的零为37(2) 1227.对关键字序列(5，8，1，3，9，6，2，7)按从小到大进行快速排序。(1)写出排序过程中前两趟的划分结果；(2)快速排序是否是稳定的排序方法?(1)第一趟划分结果；(2，3，1)，5，(9，6，8，7)第二趟划分结果；(1，2，3)，5，(9，6，8，7)第三趟划分结果；(1，2，3)，5，(7，6，8，9)第四趟划分结果

8、； 1，2，3，5，6，7，8，9第一趟划分过程2315968712359687 1235768912356789ji(5，8，1，3，9，6，2，7)1(2，8，1，3，9，6，5，7)2(2，5，1，3，9，6，8，7)3(2，3，1，5，9，6，8，7)4(2，3，1，5，9，6，8，7)第二趟划分过程(2，3，1，5，9，6，8，7)1(1，2，3，5，7，6，8，9) (2)非稳定2315968712355768956789ji第一趟：（2，3，1）5 （9，6，8，7）第二趟： 1，2，3，5 （9，6，8，7）第三趟：1，2，3，5，（7，6，8），9第四趟：1，2，3，5，6，

9、7，8，928.假设通信电文使用的字符集为a，b，c，d，e，f，g，h，各字符在电文中出现的频度分别为：7，26，2，28，13，10，3，11，试为这8个字符设计哈夫曼编码。规定：(1)画出你所构造的哈夫曼树(规定树中左孩子结点的权值不大于右孩子结点的权值)； (2)按左分支为0和右分支为1的规则，分别写出与每个字符相应的编码。(1)(2)29.已知3阶B树如图所示，非根 【1，2】P184根 【1，2】(1)画出将关键字6插入之后的B树；1,3695,8(2)画出在(1)所得树中插入关键字2之后的B树。1,2,3695,81,3695,81,2,3692,5,81692,5,831692

10、358四、算法阅读题(本大题共4小题，每小题5分，共20分)30.假设以带头结点的单链表表达线性表，单链表的类型定义如下：typedef int DataType;typedef struct node DataType data; struct node * next; LinkNode, * LinkList;阅读下列算法，并回答问题：(1)已知初始链表如图所示，画出执行f30(head)之后的链表；题30图(2)简述算法f30的功能。void f30( LinkList head) LinkList p,r, s; if (head - next) r = head - next; p

11、= r-next; r - next = NULL; while (p) s =p; p = p-next; if ( s - data% 2 = = 0) s - next = head - next; head - next = s; else s - next = r - next; r-next = s; r =s; (1)2857(2)31.假设以二叉链表表达二叉树，其类型定义如下：typedef struct node DataType data; struct node * lchild, * rchild; /左右孩子指针 * BinTree ;阅读下列算法，并回答问题：(1)

12、已知以T为根指针的二叉树如图所示， 写出执行f31(T)之后的返回值；(2)简述算法f31的功能。int f31 ( BinTree T) int d; if ( ! T) return 0; d = f31 ( T - lchild) + f31 ( T - rchild) ; if (T - lchild & T - rchild) return d + 1 ; else return d;(1)3(2)记录度为2的结点个数32.设有向图邻接表定义如下：typedef struct VertexNode adjlist MaxVertexNum ; int n，e； 图的当前顶点数和弧数A

13、LGraph； 邻接表类型其中顶点表结点VertexNode边表结点EdgeNode结构为：阅读下列算法，并回答问题：(1)已知某有向图存储在如图所示的邻接 表G中，写出执行f32(G)的输出；(2)简述算法f32的功能。int visited MaxNum ;void DFS(ALGraph * G, int i) EdgeNode * p; visited i = TRUE ; if (G - adjlist i. firstedge = = NULL) printf( % c , G - adjlist i. vertex)； else p = G - adjlist i. firste

14、dge; while (p ! = NULL) if ( ! visitedp - adjvex ) DFS( G, p - adjvex) ; p = p-next;void f32 ( ALGraph * G) int i; for (i = 0; i n; i +) visited i = FALSE ; for (i = 0; i n; i+) if ( ! visitedi ) DFS(G, i) ;(1)ABECD(2)图的深度优先搜寻ABCDE33.下列算法f33的功能是对记录序列进行双向冒泡排序。算法的基本思想为，先从前往后通过互换将关键字最大的记录移动至后端，然后从后往前通过

15、互换将关键字最小的记录移动至前端，如此反复进行，直至整个序列按关键字递增有序为止。请在空缺处填入合适的内容，使其成为完整的算法。#define MAXLEN 100typedef int KeyType;typedef struct KeyType key; InfoType otherinfo; NodeType ;typedef NodeType SqList MAXLEN ;void f33 ( SqList R, int n) int i,j,k; NodeType t; i =0; j =n-l; while (i j) for ( (1) ) k=i;k Rk +l.key) t

16、= Rk; Rk = Rk +1; Rk +1 = t; j-; for (k =j; k i; k - ) if ( (2) ) Rk.key next;max=head-next;while(P)P=p-next;If(p-datamax-data) max=p;x=max-data;delete_L(Lnode *L,int i) Lnode *p,*q;int j;Elemtype x; P=L;j=0; While(p-next!=null&jnext;j+; If(! P-next|inext;x=q-data; P-next=q-next;free(q); Return(x);/

17、*delete_L*/全国2023年10月自学考试数据结构真题一、单项选择题（本大题共15小题，每小题2分，共30分）在每小题列出的四个备选项中只有一个是符合题目规定的，请将其代码填写在题后的括号内。错选、多选或未选均无分。1.按值可否分解，数据类型通常可分为两类，它们是(c)A.静态类型和动态类型B.原子类型和表类型C.原子类型和结构类型D.数组类型和指针类型2. A.A f(n)是0(g(n)B.B g(n)是0(f(n)C.C h(n)是0(nlogn)D.D h(n)是0(n2)答案：C3.指针p、q和r依次指向某循环链表中三个相邻的结点，互换结点*q和结点*r在表中顺序的程序段是()

18、A.p-next=r；q-next=r-next；r-next=q；B.p-next=r；r-next=q；q-next=r-next；C.r-next=q；q-next=r-next；p-next=r；D.r-next=q；p-next=r；q-next=r-next；答案：A4.若进栈顺序为a，b，c，且进栈和出栈可以穿插进行，则也许出现的含3个元素的出栈序列个数是()A.3B.5C.6D.7答案：B5.假设以数组An存放循环队列的元素，其头指针front指向队头元素的前一个位置、尾指针rear指向队尾元素所在的存储位置，则在少用一个元素空间的前提下，队列满的鉴定条件为()A.rear=f

19、rontB.(front+1)n=rearC.rear+1=frontD.(rear+1)n=front答案：D6.串的操作函数str定义为：A.3B.4C.5D.6答案：C7.二维数组A106采用行优先的存储方法，若每个元素占4个存储单元，已知元素A34的存储地址为1000，则元素A43的存储地址为()A.1020B.1024C.1036D.1240答案：A8.对广义表L= (a，()执行操作tail(L)的结果是()A.()B.()C.aD.(a)答案：B9.已知二叉树的中序序列和后序序列均为ABCDEF，则该二叉树的先序序列为()A.FEDCBAB.ABCDEFC.FDECBAD.FBD

20、CEA答案：A10.已知森林F=T1，T2，T3，T4，T5，各棵树Ti(i=1，2，3，4，5)中所含结点的个数分别为7，3，5，1，2，则与F相应的二叉树的右子树中的结点个数为()A.2B.3C.8D.11答案：D11.若非连通无向图G具有21条边，则G的顶点个数至少为()A.7B.8C.21D.22答案：B12.如图所示的有向图的拓扑序列是()A.c，d，b，a，eB.c，a，d，b，eC.c，d，e，a，bD.c，a，b，d，e答案：B13.对关键字序列(6，1，4，3，7，2，8，5)进行快速排序时，以第1个元素为基准的一次划分的结果为()A.(5，1，4，3，6，2，8，7)B.(

21、5，1，4，3，2，6，7，8)C.(5，1，4，3，2，6，8，7)D.(8，7，6，5，4，3，2，1)答案：C14.分块查找方法将表分为多块，并规定()A.块内有序B.块间有序C.各块等长D.链式存储答案：B15.便于进行布尔查询的文献组织方式是()A.顺序文献B.索引文献C.散列文献D.多关键字文献答案：D二、填空题（本大题共10小题，每小题2分，若有两个空格，每个空格1分，共20分）请在每个空格中填上对的答案。错填、不填均无分。1.数据的链式存储结构的特点是借助_指针_表达数据元素之间的逻辑关系。2.假如需要对线性表频繁进行_插入_或_删除_操作，则不宜采用顺序存储结构。3.如图所示

22、，可以运用一个向量空间同时实现两个类型相同的栈。其中栈1为空的条件是top1=0，栈2为空的条件是top2=n-1，则“栈满”的鉴定条件是_ top1top2(或top2=top1-1或top1=top2+1)。4.静态存储分派的顺序串在进行插入、置换和_联接_等操作时也许发生越界。5.广义表L=（a，（b，( )）的深度为_3_。6.任意一棵完全二叉树中，度为1的结点数最多为_1_。7.求最小生成树的克鲁斯卡尔(Kruskal)算法耗用的时间与图中_边_的数目正相关。8.在5阶B树中，每个结点至多含4个关键字，除根结点之外，其他结点至少含_2_个关键字。9.若序列中关键字相同的记录在排序前后

23、的相对顺序不变，则称该排序算法是_稳定_的。10.常用的索引顺序文献是_ ISAM _文献和_ VSAM _文献。三、解答题(本大题共4小题，每小题5分，共20分)1.答案：2.由字符集s，t，a，e，i及其在电文中出现的频度构建的哈夫曼树如图所示。已知某段电文的哈夫曼编码为，请根据该哈夫曼树进行译码，写出本来的电文。答案：eatst(说明：每个字母1分)（5分）3.已知无向图G的邻接表如图所示，(1)画出该无向图；(2)画出该图的广度优先生成森林。4.对序列(48，37，63，96，22，31，50，55，11)进行升序的堆排序，写出构建的初始(大根)堆及前两趟重建堆之后的序列状态。初始堆：

24、第1趟：第2趟：答案：初始堆：（96，55，63，48，22，31，50，37，11）（2分）第1趟：（63，55，50，48，22，31，11，37，96）（2分）第2趟：（55，48，50，37，22，31，11，63，96）（1分）四、算法阅读题(本大题共4小题，每小题5分，共20分)1.阅读下列算法，并回答问题：(1)无向图G如图所示，写出算法f30(&G)的返回值；(2)简述算法f30的功能。#define MaxNum 20int visitedMaxNum；void DFS(Graph *g，int i)；/*从顶点vi出发进行深度优先搜索，访问顶点vj时置visitedj为1*

25、/int f30(Graph *g)int i，k；for (i=0； in； i+)*g-n为图g的顶点数目*visitedi=0；for (i=k=0； in; i+)if (visitedi=0)k+；DFS(g，i)；return k；(1)(2)答案：（1）3（3分）（2）返回无向图g中连通分量的个数。（2分）2.假设学生成绩按学号增序存储在带头结点的单链表中，类型定义如下：typedef struct Node int id;/*学号*/int score；/*成绩*/struct Node *next； LNode， *LinkList；阅读算法f31，并回答问题：(2)简述算法

26、f31的功能。void f31(LinkList A, LinkList B)LinkList p, q;p=A-next;q=B-next;while (p & q)if (p-idid)p=p-next;else if (p-id q-id)q=q-next;else if (p-score score score=q-score;else p-score=60;p=p-next;q=q-next;(1)(2)答案：3.阅读下列算法，并回答问题：(1)设串s=OneWorldOneDream，t=One，pos是一维整型数组，写出算法f32(s，t，pos)执行之后得到的返回值和pos中的

27、值；(2)简述算法f32的功能。int strlen(char*s)； /*返回串s的长度*/int index(char*st，char*t)；*若串t在串st中出现，则返回在串st中初次出现的下标值，否则返回-1*/int f32(char*s, char*t, int pos) int i, j, k, ls, lt;ls=strlen(s);lt=strlen(t);if (ls=0|lt=0) return-1;k=0;i=0;do j=index(s+i, t);if (j=0) posk+=i+j;i+=j+it;while(i+it=0return k;(1)(2)答案：（1）

28、2；pos0=0,pos1=8(说明：每个值1分)（3分）（2）返回串t在s中出现的次数，并将每次出现的位置依次存放在数组pos中。（2分）4.二叉排序树的存储结构定义为以下类型：typedef int KeyType;typedef struct node KeyType key;/*关键字项*/InfoType otherinfo;/*其它数据项*/struct node *lchild, *rchild;/*左、右孩子指针*/ BSTNode, *BSTree；阅读算法f33，并回答问题：(1)对如图所示的二叉排序树T，写出f33(T，8)返回的指针所指结点的关键字；(2)在哪些情况下算

29、法f33返回空指针?(3)简述算法f33的功能。BSTNode *f33(BSTree T, KeyType x) BSTNode *p;if (T=NULL) return NULL;p=f33(T-lchild, x);if (p!=NULL) return p;if (T-key x) return T;return f33(T-rchild, x);(1)(2)(3)答案：（1）10（2分）（2）T是空树或T中所有结点的关键字均不大于给定值x时，返回空指针。（2分）（3）假如二叉排序树T中存在具有关键字大于给定值x的结点，则返回指针指向它们中关键字最小的结点，否则返回空指针。（1分）五

30、、算法设计题（本题10分）1.假设线性表采用顺序存储结构，其类型定义如下：#define ListSize 100typedef struct int dataListSize;int length; SeqList, *Table;编写算法，将顺序表L中所有值为奇数的元素调整到表的前端。答案：参考答案一：void f34(Table L)(或者参数说明为：SeqList *L,1分) int i,j,t;i=0;（初始化，1分）j=L-length-1;while(ij)(循环控制，1分) while(idatai%2)（1分）i+;while(idataj%2=0)（1分）j-;if(id

31、atai;（互换，2分）L-datai=L-dataj;L-dataj=t;i+;(i和j,1分)j-;(其他，如“L-”表达，1分)参考答案二：void f34(SeqList*L)(或者参数说明为：Table L,1分) int i,j=0,t;(初始化，1分)for(i=0;ilength;i+)(循环控制，2分)if(L-datai%2)/*奇数*/（奇数解决框架，1分） if(i!=j)(避免同一元素互换，1分) t=L-datai;(互换，2分)L-datai=L-dataj;L-dataj=t;j+;（1分）（其他，如“L-”表达，1分）全国2023年1月自学考试数据结构试题一、

32、单项选择题(本大题共15小题，每小题2分，共30分) 在每小题列出的四个备选项中只有一个是符合题目规定的，请将其代码填写在题后的括号内。错选、多选或未选均无分。1若一个算法的时间复杂度用T(n)表达，其中n的含义是（ A ）A问题规模 B语句条数C循环层数 D函数数量2具有线性结构的数据结构是（ C ）线性结构有：顺序表、栈和队列、串A树 B图C栈和队列 D广义表3将长度为n的单链表连接在长度为m的单链表之后，其算法的时间复杂度为（ B ）AO(1) BO(m)CO(n)DO(m+n)插入到长度为m的单链表，需找到表尾，时间复杂度为o(m)，连接的时间复杂度为0(1),所以总的时间复杂度为0(

33、m)4在带头结点的双向循环链表中插入一个新结点，需要修改的指针域数量是（ C ）A2个 B3个 C4个D6个void DInsertBefore(DListNode *p,DataType x)/在带头结点的双链表中，将值为x的新结点插入结点*p之前，设pNULL DListNode *s=malloc(sizeof(ListNode);s-data=x;s-prior=p-prior; s-next=p;p-prior-next=s;p-prior=s; 5假设以数组A60存放循环队列的元素，其头指针是front=47，当前队列有50个元素，则队列的尾指针值为（ B ）A3 B37C50 D

34、97对于循环向量中的循环队列，写出通过队头队尾指针表达的队列长度公式。（front指向实际队头，rear指向实际队尾的下一元素位置。）当rearfront时，队列长度L=rear-front；当rearfront时，L=m+(rear-front)。这两种情况可统一为L=(m+(rear-front)%m，这里m为向量的大小。本题中m=606若栈采用链式存储结构，则下列说法中对的的是（ B ） A需要判断栈满且需要判断栈空 B不需要判断栈满但需要判断栈空 C需要判断栈满但不需要判断栈空 D不需要判断栈满也不需要判断栈空由于链栈中的结点是动态分派的，可以不考虑上溢，所以无需定义stackFull

35、运算。7若串str=”Software”，其子串的数目是（ D ）A8 B9C36 D378设有一个10阶的下三角矩阵A，采用行优先压缩存储方式，all为第一个元素，其存储地址为1000，每个元素占一个地址单元，则a85的地址为 （ C ）A1012 B1017C1032 D1039在n阶方阵A这个下三角矩阵中，第i（i从0开始）行（0in）有i+1个元素，元素总数为：n(n+1)/2，并将元素放在一个向量sa0. n(n+1)/2-1中。若ij，则aij在左下三角矩阵中，sak与aij的相应关系是k=i(i+1)/2+j。若ij，则aij在右上三角矩阵中，sak与aij的相应关系是k=j(j

36、+1)/2+i。若all为第一个元素， a85与a00为第一个元素时的a(85-(11-00)= a74位置同样，k=7*8/2+4=32，则a85的地址=1000+32=1032；若a44为第一个元素， a85与a00为第一个元素时的a(85-(44-00)= a41位置同样，k=4*5/2+1=11，则a85的地址=1000+11=1011；9允许结点共享的广义表称为（ D ）A纯表 B线性表C递归表 D再入表10下列数据结构中，不属于二叉树的是（ A ）AB树 B树是一种平衡的多叉树BAVL树 AVL树是自平衡二叉查找树C二叉排序树 D哈夫曼树 哈夫曼树是最优二叉树11对下面有向图给出了四种也许的拓扑序列，其中错误的是（ C ）A1，5，2，6，3，4 B1，5，6，2，3，4C5，1，6，3，4，2 D5，1，2，6，4，312以v1为起始结点对下图进行深度优先遍历，对的的遍历序列是（ D ）Av1，v2，v3，v4，v5，v6，v7 Bv1，v2，v5，v4，v3，v7，v6Cv1，v2，v3，v4，v7，v5，v6