自考数据结构试题和答案

1、WORD格式2021年 1 月高等教育考试数据构造试题和答案课程代码： 02331一、单项选择题( 本大题共15 小题，每题2 分，共 30 分 )在每题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多项选择或未选均无分。1假设一个算法的时间复杂度用T(n) 表示，其中 n 的含义是A A问题规模B语句条数C循环层数D函数数量2具有线性构造的数据构造是C A树B图C栈和队列D广义表线性构造有：顺序表、栈和队列、串3将长度为 n 的单链表连接在长度为m的单链表之后，其算法的时间复杂度为C A O(1)B O(m)C O(n)D O(m+n)4在带头结点的双向循环

2、链表中插入一个新结点，需要修改的指针域数量是D A2 个B3个C4 个D6个P28 中void DInsertBefore(DListNode *p,DataType x)/在带头结点的双链表中，将值为x 的新结点插入结点 *p之前，设 p NULLDListNode *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 个元素，那

3、么队列的尾指针值为 D 专业资料整理WORD格式A 3B 37专业资料整理WORD格式C 50D 97专业资料整理WORD格式辅导书P22 中专业资料整理WORD格式对于循环向量中的循环队列，写出通过队头队尾指针表示的队列长度公式。front指向实际队头，rear指向实际队专业资料整理WORD格式尾的下一元素位置。 专业资料整理WORD格式当rear front时，队列长度L=rear-front；当rear<front时，L=m+(rear-front)。这两种情况可统一为专业资料整理WORD格式L=(m+(rear-front)%m，这里m为向量的大小。此题中m=60专业资料整理WO

4、RD格式6假设栈采用链式存储构造，那么以下说法中正确的选项是B 专业资料整理WORD格式A 需要判断栈满且需要判断栈空B 不需要判断栈满但需要判断栈空C 需要判断栈满但不需要判断栈空D不需要判断栈满也不需要判断栈空P36 中专业资料整理WORD格式因为链栈中的结点是动态分配的，可以不考虑上溢，所以无需定义stackFull运算。专业资料整理WORD格式7假设串str=Software ，其子串的数目是D 专业资料整理WORD格式A 8B 9专业资料整理WORD格式C 36D 37专业资料整理WORD格式P51 中任意个连续字符组成的子序列称为该串的子串。8设有一个 10 阶的下三角矩阵 A，采

5、用行优先压缩存储方式，all为第一个元素，其存储地址为1000，每个元素占一个地址单元，那么a85的地址为 C A 1012B 1017C 1032D 1039P61 中在 n 阶方阵 A 这个下三角矩阵中，第i i从 0 开场行 0 i<n 有 i+1个元素，元素总数为：n(n+1)/2 ，并将元素放在一个向量sa0. n(n+1)/2-1中。假设 i j ，那么aij在左下三角矩阵中，sak与 aij的对应关系是k=i(i+1)/2+j。假设 i<j，那么aij 在右上三角矩阵中，saka。与 ij 的对应关系是k=j(j+1)/2+i假设 all为第一个元素，a 85与a00

6、为第一个元素时的a(85-(11-00)= a 74位置一样，k=7*8/2+4=32，那么a的地址85=1000+32=1032；假设a44为第一个元素，a 85与a00为第一个元素时的a(85-(44-00)= a 41位置一样，k=4*5/2+1=11，那么a85的地址专业资料整理WORD格式=1000+11=1011；专业资料整理WORD格式9允许结点共享的广义表称为D P67专业资料整理WORD格式A纯表B线性表专业资料整理WORD格式C递归表D再入表专业资料整理WORD格式10以下数据构造中，不属于二叉树的是BB 树是一种平衡的多叉树专业资料整理WORD格式AB 树B AVL 树A

7、VL 树是自平衡二叉查找树专业资料整理WORD格式C二叉排序树 D哈夫曼树11对下面有向图给出了四种可能的拓扑序列，其中错误的选项是哈夫曼树是最优二叉树C 辅导书中P97 第 10题专业资料整理WORD格式A 1， 5， 2， 6， 3，4B 1， 5， 6， 2， 3，4C 5， 1， 6， 3， 4，2D 5， 1， 2， 6， 4，312以 v1 为起始结点对以下列图进展深度优先遍历，正确的遍历序列是D A v1， v2， v3， v4， v5， v6， v7B v1， v2， v5， v4， v3， v7， v6C v1， v2， v3， v4， v7， v5， v6D v1， v2，

8、 v5， v6， v7， v3， v4P108P110 的图 7.10P114115 的图7.12 、图 7.13 、 7.14深度优先遍历类似于树的前序遍历。其特点是尽可能先对纵深方向进展搜索。13以下排序算法中不稳定的是A P164A快速排序B归并排序C冒泡排序D直接插入排序稳定：直接插入、冒泡、归并、基数不稳定：直接选择、希尔、快速、堆14一个有序表为 (1 ， 3， 9，12，32， 41， 45，62，75，77， 82， 95，100) ，当采用 折半查找 方法查找值32 时，查找成功需要的比较次数是B mid 1=45， mid 2=9， mid3=32专业资料整理WORD格式A

9、 2B 3C 4D 8P171中二分查找 Binary Search又称折半查找，它是一种效率较高的查找方法。但是，二分查找要求线性表是有序表，即表中结点按关键字有序，并且要用向量作为表的存储构造。一般设有序表是递增有序的。二分查找的根本思想是：设Rlow.high是当前的查找区间，首先确定该区间的中点位置mid=(low+high)/2，然后将待查的 K 值与 Rmid.key比较，假设相等，那么查找成功并返回此位置，否那么须确定新的查找区间；假设Rmid.key>K，那么由表的有序性可知Rmid.n.keys均大于 K，因此假设表中存在关键字等于 K 的结点，那么该结点必定是在位置m

10、id 左边的子表 R1.mid-1中，故新的查找区间是左子表R1.mid-1；类似地，假设 Rmid.key<K，那么要查找的 K 必在 mid 的右子表 Rmid+1.n中，即新的查找区间是右子表Rmid+1.n 。下一次查找是针对新的查找区间进展的。因此，我们可以从初始的查找区间R1.n 开场，每经过一次与当前查找区间的中点位置上的结点关键字的比较，就可确定查找是否成功，不成功那么当前的查找区间就缩小一半。这一过程重复直至找到关键字为K 的结点，或者直至当前的查找区间为空即查找失败时为止。专业资料整理WORD格式15采用ISAM组织文件的方式属于D P211-212专业资料整理WOR

11、D格式A链组织B顺序组织专业资料整理WORD格式C散列组织D索引组织专业资料整理WORD格式二、填空题( 本大题共10 小题，每题2 分，共20 分)专业资料整理WORD格式请在每题的空格中填上正确答案。错填、不填均无分。专业资料整理WORD格式16数据元素及其关系在计算机存储器内的表示称为存储构造 。 P117长度为n 的线性表采用单链表构造存储时，在等概率情况下查找第i 个元素的时间复杂度是18下面是在顺序栈上实现的一个栈根本操作，该操作的功能是_取栈顶元素 _。 P34O(n) 。专业资料整理WORD格式typedef struct专业资料整理WORD格式DataType data100

12、；专业资料整理WORD格式int top；专业资料整理WORD格式SeqStack；专业资料整理WORD格式DataType StackTop(SeqStack*S) if(StackEmpty(S)Error( Stack is empty) ；专业资料整理WORD格式return S->dataS->top；专业资料整理WORD格式专业资料整理WORD格式19在串匹配中，一般将主串称为目标串，将子串称为_模式串20广义表C=(a(b ， c) ， d) ，那么： tail(head(tail(C)= _P66 中_。 P55()_。专业资料整理WORD格式假设广义表LS 非空

13、n 1通常用圆括号将广义表括起来，用逗号分割其中的元素。用大写字母表示广义表，用小写字母表示原子。 ，那么 a1是LS的表头，其余元素组成的表称为LS 的表尾。长度：元素的个数深度：表展开后所含括号的层数从最里面往最外面数21用 6 个权值分别为6、13、18、30、7 和 16 的结点构造一棵哈夫曼(Huffman) 树，该树 的带权路径长度为_231_。P90 中结点的带权路径长度，是该结点到树根之间的路径长度与结点上权的乘积。WPL=30× 1+18× 2+16× 3+13× 4+6× 5+7× 5=30+36+48+52+30

14、+35=23122有向图如下所示，其中顶点A 到顶点 C 的最短路径长度是_35_。P90 中树的路径长度是从树根到树中每一结点的路径长度之和。显然，在结点数目一样的二叉树中，完全二叉树的路径长度最短。P122 中源点 s 到终点 v 的最短路径长度简称为最短距离。P73 中完全二叉树Complete Binary Tree，见图 6.7 的 b假设一颗二叉树至多只有最下面的两层上结点的度数P70 中，一个结点拥有的子树数称为该结点的度Degree 。一颗树的度是指该树中的结点的最大度数。度为零的结点称为叶子Leaf 或终端结点。可以小于2，而且最下层上的结点都集中在该层最左边的假设干位置上，

15、那么此二叉树称为完全二叉树。专业资料整理WORD格式23对序列55 ， 46， 13， 05， 94， 17， 42 进展基数排序，第一趟排序后的结果是42,13,94,55,05,46,17。专业资料整理WORD格式P162 中专业资料整理WORD格式基数排序的根本思想是：从低位到高位依次对Kjj=d-1,d-2,d-3 ,0 进展箱排序。在d 趟箱排序中，所需的箱专业资料整理WORD格式子数就是基数rd 。专业资料整理WORD格式如被排序的记录关键字K0-99 间整数的例子，就是一个基数radix 为 10， d 为 2 的基数排序。i 取值X围是专业资料整理WORD格式箱号0123456

16、789第一次装箱 (a)42139455,054617内容箱号0123456789第二次装箱 (b)513,1742,465594内容24高度为 3 的 3 阶 B- 树最少的关键字总数是_7_。辅导书 P147 中最多关键字总数的解答一颗高度为h 的 k 阶 B- 树中最多可容纳多少个关键字？解 要使高为 h 的 k 阶 B- 树容纳最多的关键字，那么每个结点中的关键自数据就必须到达最大值k-1. 因此这时的B- 树实际上可看成是满k 叉树。不妨设根的层数为1，那么第 1 层只有 1 个根结点，第2 层上共有 k 个结点，第3 层上共有 k2个结点，第 h 层上共有kh-1个结点，树中结点总

17、数为：由每个结点可容纳k-1 关键字可知，树中可容纳的关键字总数为：n=(k-1) × m=(k-1) ×=kh-1以 h=3， k=101 为例，相应的 B- 树最多可容纳1013-1=100+10100+1020210=1030300 个关键字，树中结点总数为3( 101 -1)/100=1+101+10201=10303。示意图如下：第 1层：1个结点100个关键字第 2 层： 101 个结点101× 100=10100 个关键字2第 3 层：101 =10201 个结点10201× 100=1020210 个关键字P182 中最少关键字总数的解答

18、一颗 m m3阶的 B-树，每个非根结点中所包含的关键字个数j 满足： m/2 -1 j m-1。即每个非根结点至少应有 m/2 -1 个关键字，至多有 m-1 个关键字。注： m/2是指不小于即大于等于 m/2 的最小整数。一颗高度为 h 的 m阶 B- 树中最少可容纳的关键字总数为： m/2h -1 ，最少可容纳的结点总数为h m/2 -1专业资料整理WORD格式 m/2 -1以 h=3， m=3为例，相应的B-树最少可容纳的关键字总数为第 1层：1个结点 m/2 -1=1 个关键字第 2层：2个结点2 个关键字2第 3层：2 =4个结点h 3 m/2 -1= 2 -1=7个。示意图如下：

19、专业资料整理WORD格式4 个关键字25 VSAM通常作为大型索引顺序文件的标准组织，其动态索引构造采用的是_B+树 _。 P214三、解答题 (本大题共4 小题，每题5 分，共 20 分)26假设二叉树的RNL遍历算法定义如下：假设二叉树非空，那么依次执行如下操作：(1) 遍历右子树；(2) 访问根节点；(3) 遍历左子树。一棵二叉树如下列图，请给出其RNL遍历的结果序列。GCFABDP77 页图 6.11 中的中序序列LNR、前序序列NLR、后序序列LRN27一个无向图G=(V，E) ，其中 V=A， B，C， D， E， F ，邻接矩阵表示如下所示。请答复以下问题：(1) 请画出对应的图

20、 G。 P103 中的图 7.7012345ABCDEF0A0101001B1011102C0100013D110010专业资料整理WORD格式4E0101015F001010(2) 画出图 G的邻接表存储构造。 P105 中图 7.8vertexfirstedgeadjvexnext专业资料整理WORD格式012345ABCDEF1302341501413524专业资料整理WORD格式28一顶点表边表组待排记录的关键字序列为(16 ， 12，18 ，60，15， 36， 14， 18， 25， 85) ，用堆排序方法建小根堆，请给出初始建堆后的序列。P154 中，注： n=10，从第 n/2

21、 1i 个结点起进展调整。假设i=5 ，那么与 i=10或 i=11进展互换；即 i 与 2i或 2i+1中的关键字进展互换。P152 中，堆排序利用了大根堆( 或小根堆 ) 堆顶记录的关键字最大( 或最小 ) 这一特征，大根堆排序结果是递增有序的，小根堆排序结果是递减有序的。16161218121860153614181536141825856025851234567891012345678910161218601536141825851612181815361460258516i=412i=5 ，不调整，调整121415141816361818153618602585专业资料整理WORD格

22、式6025851234567891016121418153618602585i=3 ，调整1234567891012151418163618602585i=2，不调整i=1，调整小根堆初始建堆后的序列专业资料整理WORD格式29一棵二叉排序树如下列图。请答复以下问题：(1) 画出插入元素 23 后的树构造；23(2) 请画出在原图中删除元素 57 后的树构造。P174 中二叉排序树 (Binary Sort Tree)性质 (BST 性质 ) ：假设它的左子树非空，那么左子树上所有结点的值均小于根结点的值；假设它的右子树非空，那么右子树上所有结点的值均大于根结点的值；专业资料整理WORD格式左

23、右子树本身又各是一棵二叉排序树。二叉排序树BST的特点 1 二叉排序树中任一结点x，其左 ( 右 ) 子树中任一结点y( 假设存在 ) 的关键字必小 ( 大 ) 于 x 的关键字。 2 二叉排序树中，各结点关键字我理解是中间节点，即N是惟一的。还有另外一个重要性质：按中序遍历LNR 该树所得到的中序序列是一个递增有序序列，RNL 那么得到一个递减有序序列。四、算法阅读题(本大题共4 小题，每题5 分，共 20 分 )30以下程序，Ls 指向带头结点的单链表。Typedef struct node DataType data;struct node * next; * LinkList;void

24、 f30( LinkList Ls ) LinkList p, q; q = Ls->next;if ( q && q->next ) Ls->next = q->next; p=qwhile ( p->next ) p = p->next;p->next = q;q->next = NULL;请答复以下问题：(1) 当 Ls 指向的链表如以下列图所示，请画出执行本函数之后的链表的结果。专业资料整理WORD格式(2) 请简述算法的功能。专业资料整理WORD格式删除单链表的中间结点和尾结点。31字符串处理函数f31 程序如下。专业资

25、料整理WORD格式int f31(char*strl， char*str2)专业资料整理WORD格式 while(*strl=*str2&&(*strl!= 0)专业资料整理WORD格式strl+；专业资料整理WORD格式str2+；专业资料整理WORD格式专业资料整理WORD格式return(*strl-*str2 " l 0) ；请答复以下问题：(1) 假设调用语句是f31( abcde， abcdf ) ，那么函数的返回值是什么"答：A 的 ASCII 065A 的 ASCII 097由于 'e ' 对应的 ASCII 码是 101，

26、'f' 对应的 ASCII 码是 102，那么 'e ''f'=101 102=-1再按照条件表达式的形式为逻辑表达式？表达式 1：表达式 2假设逻辑表达式的值为非零，那么条件表达式的值等于表达式1 的值；假设逻辑表达式的值为零，那么条件表达式的值等于表达式2 的值。那么函数的返回值是 1。假设调用语句是f31( abcde， abcde) ，那么函数的返回值是什么"答：由于字符串完毕标识'0' 对应的 ASCII 码是 0，那么 *strl-*str2=0再按照条件表达式的形式为逻辑表达式？表达式 1：表达式 2假设逻

27、辑表达式的值为非零，那么条件表达式的值等于表达式1 的值；假设逻辑表达式的值为零，那么条件表达式的值等于表达式2 的值。那么函数的返回值是0。(2) 简述该函数的功能。答：如果两个字符串结点*strl和 *strl中的字符相等，且字符串结点*strl中的字符不等于字符串完毕标识 '0'，那么两个字符串结点*strl和*strl中的字符指针自加运算。如果条件不满足，那么字符串结点*strl和 *strl中的字符相减。假设逻辑表达式的值为非零，那么条件表达式的值等于1；假设逻辑表达式的值为零，那么条件表达式的值等于0。32数组 A 中存储有n 个整数，请阅读以下程序。专业资料整理W

28、ORD格式void f32(intA， int n)专业资料整理WORD格式 int i， j ， k， x； k=n-l ；while(k>0)i=k； k=0 ；for(j=O； j<i ；j+)if(Aj>Aj+1)x=Aj；Aj=Aj+l；Aj+1=x；k=j； end of if end of while return ；请答复以下问题：(1) 当 A=10 ， 8，2， 4， 6， 7 时，执行f32(A ， 6) 后，数组A 中存储的结果是什么"答：数组A 中存储的结果是10。(2) 说明该算法的功能。答：数组A 中存储有n 个整数，当k=n-1 时，

29、那么第k 个向量是最后一个整数。当 k>0 时，即数组 A 非空时，设 i=k ， k=0，如果 j=0 ，且 j<i 即 j 小于 k时， j 自加即数组下标自加 ；同时比较第 j 个整数和第 j+1 个整数。如果第 j 个整数大于第 j+1 个整数，那么通过语句x=Aj；Aj=Aj+l；Aj+1=x；进展交换，同时令k=j 。如果 j 大于等于i 即 j 大于等于 k时，那么完毕执行if语句和 while语句，并返回。33下面程序实现二分查找算法。Typedef struct专业资料整理WORD格式KeyType key；专业资料整理WORD格式InfoType otherin

30、fo；专业资料整理WORD格式SeqListN+1；专业资料整理WORD格式int BinSearch(SeqList R, int n， KeyType K)专业资料整理WORD格式 int low=1，high=n ；专业资料整理WORD格式while(1)low<=high)专业资料整理WORD格式mid=(1ow+high) 2；if(2)Rmid.key=Kreturn mid；if(Rmid.key>K)high=mid-1；)专业资料整理WORD格式else专业资料整理WORD格式(3)low=mid+1；专业资料整理WORD格式return O； BinSearch

31、请在空白处填写适当内容，使该程序功能完整。(1) low<=high(2) Rmid.key=K(3) low=mid+1五、算法设计题(此题 10 分 )34二叉树采用二叉链表存储，其结点构造定义如下：专业资料整理WORD格式typedef struct NodeElmType data；struct Node *lchild*BiTree；， *rchild；专业资料整理WORD格式请编写递归函数SumNodes(BiTree T)，返回二叉树T 的结点总数。专业资料整理WORD格式递归含义见P44专业资料整理WORD格式辅导书P64 P74第四题的第2 小题中专业资料整理WORD格

32、式答：求二叉数的结点总数满足如下的递归定义：专业资料整理WORD格式假设T 为空，那么以T 为根的二叉树中结点总数为0；专业资料整理WORD格式否那么，以T 为根的二叉树中结点总数应该是根T 的左子树和右子树中结点数之和再加上根本身。专业资料整理WORD格式int SumNodes(BiTree T)专业资料整理WORD格式/T的初值指向某二叉链表的根结点if(! T)/T为空return 0;elsereturn SumNodes(T->lchild)+ SumNodes(T->rchild)+1;专业资料整理WORD格式辅导书 P66 P76 第四题的第 2 小题中问：写一递归

33、算法求二叉树中度为2 的结点总数答：二叉树中度 2 度结点数的递归定义如下：当 T 为空或 T 是叶子时，以T 为根的二叉树的 2 度结点数为 0；当 T 是 2 度结点时，以T 为根的二叉树的2 度结点数为 T 的左右子树中2度结点数之和再加上T 结点本身；当 T 是 1 度结点时，以T 为根的二叉树中2 度结点数为 T 的左右子树中2度结点数之和。算法如下：int D2Nodes(BinTree T)if(! T ! T->lchild && ! T->rchild)/ 逻辑运算符的执行优先次序是： ！非 ->&&与-> 或，即 T

34、为空或 T 是叶子return 0;if(T->lchild && T->rchild)/T是 2 度结点return 1+D2Nodes(T->lchild)+D2Nodes(T->rchild);else /T是 1 度结点return D2Nodes(T->lchild)+D2Nodes(T->rchild);二、在任何事情上都不要觉得自己受了多大的委屈，哭哭啼啼和别别扭扭改变不了糟糕的现状。心子开一点，认真地该干啥干啥，反倒走得顺畅许多。扛得住多少东西，最后就会得到多少东西，大致就是这么个理儿吧。三、生命本没有意义，你要能给他什么意义

35、，他就有什么意义。与其终日冥想人生有何意义，不如试用此生做点有意义的事。四、爱怕沉默。太多的人，以为爱到深处是无言。其实，爱是很难描述的一种情感，需要详尽的表达和传递。五、有些路，只能一个人走。六、有一种落差是，你配不上自己的野心，也辜负了所受的苦难。七、有些决定，只需要一分钟，可是，却会用一辈子，去懊悔那一分钟。八、 “突然想通了 ,这五个字说来简单，要做到可真不容易。我佛如来在菩堤树下得道，就因为他“突然想通了 达.摩祖师面壁十八年，才总算“突然想通了无.论什么事，你只要能“突然想通了,你就不会有烦恼，但到达这地步之前，你一定已不知道有过多少烦恼。专业资料整理WORD格式九、如果他总为别人撑伞，你何苦非为他等在雨中。专业资料整理WORD格式十、我对前任的感觉很简单，哪怕他的女朋友来我面前秀恩爱，我也不会觉得烦。就像在看别人吃一碗很香的卤肉饭，吧唧嘴巴弄得很大声，但我自己心里是明白的：我吃过那种饭，其实没那么好吃。十一、为什么我们总是不懂得珍惜眼前人？在未可预知的重逢里，我们以为总会重逢，