21春西南大学[0012]《数据结构》作业辅导资料.docx

1、西南大学培训与继续教育学院 课程代码：0012学年学季：20211 单项选择题单项选择题 1 1、用某种排序方法对关键字序列（、用某种排序方法对关键字序列（2525，8484，2121，4747，1515，2727，6868，3535，2020）进行排序时，序列的变化情况如下：）进行排序时，序列的变化情况如下： 2020，1515，2121，2525，4747，2727，6868，3535，8484 1515，2020，2121，2525，3535，2727，4747，6868，8484 1515，2020，2121，2525，2727，3535，4747，6868，8484 则所采用的排序方

2、法是（则所采用的排序方法是（） 1.A. 选择排序 2.希尔排序 3.快速排序 4.归并排序 2 2、不定长文件是指（、不定长文件是指（） 1.记录的长度不固定 2.关键字项的长度不固定 3.字段的长度不固定 4.文件的长度不固定 3 3、如下陈述中正确的是（、如下陈述中正确的是（） 1.串中元素只能是字母 2.串是一种特殊的线性表 3.串的长度必须大于零 4.空串就是空白串 4 4、将长度为、将长度为 n n 的单链表链接在长度为的单链表链接在长度为 m m 的单链表之后的算法的时间复杂度为（的单链表之后的算法的时间复杂度为（） 1.O（m+n） 2.O（n） 3.O（m） 4.O（1） 5

3、 5、设数组、设数组 datamdatam作为循环队列作为循环队列 SQSQ 的存储空间，的存储空间，frontfront 为队头指针，为队头指针，rearrear 为队尾指针，则执行出队操作后其头指针为队尾指针，则执行出队操作后其头指针 frontfront 值为（值为（） 1.F. front=(front+1)%m 2.front=(front-1)%m 3.front=front+1 4.front=(front+1)%(m-1) 6 6、一棵深度为、一棵深度为 6 6 的满二叉树有的满二叉树有个分支结点个分支结点 1.30 2.31 3.32 4.33 7 7、把一棵树转换为二叉树后

4、，这棵二叉树的形态是（、把一棵树转换为二叉树后，这棵二叉树的形态是（ ） 1.唯一的 2.有多种 3.有多种，但根结点都没有左孩子 4.有多种，但根结点都没有右孩子 8 8、若需要在、若需要在 O(nlogO(nlog2 2n)n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（） 1.快速排序 2.堆排序 3.归并排序 4.直接插入 9 9、设哈希表长、设哈希表长 m=14,m=14,哈希函数哈希函数 H(key)=keyH(key)=key MODMOD 1111。表中已有。表中已有 4 4 个结点：个

5、结点：addr(15)=4,addr(38)=5,addr(61)=6,addr(84)=7addr(15)=4,addr(38)=5,addr(61)=6,addr(84)=7 其余地址为空，如用二次探其余地址为空，如用二次探 测再散列处理冲突，则关键字为测再散列处理冲突，则关键字为 4949 的地址为（的地址为（ ）: : 1.3 2.5 3.8 4.9 1010、由个结点所构成的二叉树有、由个结点所构成的二叉树有种形态种形态. . 1.2 2.3 3.4 4.5 1111、一个具有、一个具有 n n 个顶点的有向图最多有（个顶点的有向图最多有（）条边）条边 1.n(n-1)/2 2.n(

6、n+1)/2 3.n(n-1) 4.n2 1212、判断一个循环队列、判断一个循环队列 Q Q（最多（最多 n n 个元素）为满的条件是个元素）为满的条件是: : 1.Q-front=(Q-rear+1)%n 2.Q-rear=Q-front+1 3.Q-front=(Q-rear-1)%n 4.Q-rear=Q-front 1313、在单链表中，指针、在单链表中，指针 p p 指向元素为指向元素为 x x 的结点，实现删除的结点，实现删除 x x 的后继的语句是的后继的语句是: : 1.p=p-next 2.p=p-next-next 3.p-next=p 4.p-next=p-next-n

7、ext 1414、在双向循环链表中，在、在双向循环链表中，在 p p 指针所指的结点后插入一个指针指针所指的结点后插入一个指针 q q 所指向的新结点，修改指针的操作是所指向的新结点，修改指针的操作是: : 1.p-next=q;q-prior=p;p-next-prior=q;q-next=q; 2.q-prior=p;q-next=p-next;p-next-prior=q;p-next=q; 3.q-next=p-next;q-prior=p;p-next=q;p-next=q; 4.p-next=q;p-next-prior=q;q-prior=p;q-next=p-next; 151

8、5、在一棵度为、在一棵度为 3 3 的树中的树中, ,度为度为 3 3 的结点个数为的结点个数为 2,2,度为度为 2 2 的结点个数为的结点个数为 1,1,则度为则度为 0 0 的结点个数为的结点个数为( () ) 1.C. 7 2.6 3.4 4.5 1616、算法指的是（、算法指的是（） 1.B. 排序算法 2.E. 解决问题的计算方法 3.计算机程序 4.解决问题的有限运算序列 1717、在含、在含 n n 个顶点和个顶点和 e e 条边的无向图的邻接矩阵中条边的无向图的邻接矩阵中, ,零元素的个数为零元素的个数为( () ) 1.n*n2e 2.e 3.n*ne 4.2e 1818、

9、线性表采用链式存储时，结点的存储地址（、线性表采用链式存储时，结点的存储地址（） 1.D. 连续与否均可 2.必须是连续的 3.和头结点的存储地址相连续 4.必须是不连续的 多项选择题多项选择题 1919、抽象数据类型的组成部分分别为、抽象数据类型的组成部分分别为: :（ ） 1.数据对象 2.存储结构 3.数据关系 4.基本操作 2020、不具有线性结构的数据结构是：（、不具有线性结构的数据结构是：（ ） 1.图 2.栈 3.广义表 4.树 判断题判断题 2121、树在实际应用中采用多种不同的形式表示和存储、树在实际应用中采用多种不同的形式表示和存储 1.A. 2.B. 2222、完全二叉树

10、一定是满二叉树完全二叉树一定是满二叉树 1.A. 2.B. 2323、在完全二叉树中，叶节点个数比分支节点个数多、在完全二叉树中，叶节点个数比分支节点个数多 1 1 1.A. 2.B. 2424、任何二叉搜索树中同一层的结点从左到右是有序的（从小到大）。任何二叉搜索树中同一层的结点从左到右是有序的（从小到大）。 1.A. 2.B. 2525、栈和队列逻辑上都是线性表、栈和队列逻辑上都是线性表 1.A. 2.B. 2626、算法分析的两个主要方面是时间复杂度和空间复杂度的分析。算法分析的两个主要方面是时间复杂度和空间复杂度的分析。 1.A. 2.B. 2727、若用链表来表示一个线性表，则表中元

11、素的地址一定是连续的。若用链表来表示一个线性表，则表中元素的地址一定是连续的。 1.A. 2.B. 2828、链表的每个结点中都恰好包含一个指针、链表的每个结点中都恰好包含一个指针 1.A. 2.B. 2929、如果将所有中国人按照生日来排序，则使用哈希排序算法最快、如果将所有中国人按照生日来排序，则使用哈希排序算法最快 1.A. 2.B. 3030、用循环单链表表示的链队列中，可以不设队头指针，仅在队尾设置队尾指针。、用循环单链表表示的链队列中，可以不设队头指针，仅在队尾设置队尾指针。 1.A. 2.B. 3131、在单链表中，要访问某个结点，只要知道该结点的地址即可；因此，单链表是一种随机

12、存取结构。、在单链表中，要访问某个结点，只要知道该结点的地址即可；因此，单链表是一种随机存取结构。 1.A. 2.B. 3232、一般树和二叉树的结点数都可以为一般树和二叉树的结点数都可以为 0;0; 1.A. 2.B. 3333、通过对堆栈通过对堆栈 S S 操作：操作：Push(S,1),Push(S,1), Push(S,2),Push(S,2), Pop(S),Pop(S), Push(S,3),Push(S,3), Pop(S),Pop(S), Pop(S)Pop(S)。输出的序列为：。输出的序列为：123123 1.A. 2.B. 3434、不论是入队列操作还是入栈操作不论是入队列

13、操作还是入栈操作, ,在顺序存储结构上都需要考虑在顺序存储结构上都需要考虑 溢出溢出 情况。情况。 1.A. 2.B. 3535、一棵有一棵有 124124 个结点的完全二叉树，其叶结点个数是确定的个结点的完全二叉树，其叶结点个数是确定的 1.A. 2.B. 主观题主观题 3636、中序遍历二叉排序树所得到的序列是、中序遍历二叉排序树所得到的序列是_序列（填有序或无序）。序列（填有序或无序）。 参考答案：参考答案： 有序 3737、若一个线性表中最常用的操作是取第、若一个线性表中最常用的操作是取第 i i 个元素和找第个元素和找第 i i 个元素的前趋元素，则采用（个元素的前趋元素，则采用（）

14、存储方式最节省时间）存储方式最节省时间. . 参考答案：参考答案： 顺序表 3838、设某无向图中顶点数和边数分别为、设某无向图中顶点数和边数分别为 n n 和和 e e，所有顶点的度数之和为，所有顶点的度数之和为 d d，则，则 e=_e=_。 参考答案：参考答案： d/2 3939、快速排序的最坏时间复杂度为快速排序的最坏时间复杂度为_，平均时间复杂度为，平均时间复杂度为_。 参考答案：参考答案： O(n*n)，O(nlog2n) 4040、设一棵完全二叉树中有设一棵完全二叉树中有 500500 个结点，则该二叉树的深度为个结点，则该二叉树的深度为_；若用二叉链表作为该完全二叉树的存储结构

15、，则共有；若用二叉链表作为该完全二叉树的存储结构，则共有_个空指个空指 针域。针域。 参考答案：参考答案： 9，501 4141、为了能有效地应用、为了能有效地应用 HASHHASH 查找技术，必须解决的两个问题是查找技术，必须解决的两个问题是_和和_。 参考答案：参考答案： 构造一个好的 HASH 函数，确定解决冲突的方法 4242、设有向图、设有向图 G G 用邻接矩阵用邻接矩阵 AnnAnn作为存储结构，则该邻接矩阵中第作为存储结构，则该邻接矩阵中第 i i 行上所有元素之和等于顶点行上所有元素之和等于顶点 i i 的的_，第，第 i i 列上所有元素之和等于顶点列上所有元素之和等于顶点

16、 i i 的的_。 参考答案：参考答案： 出度，入度 4343、在一个长度为、在一个长度为 n n 的顺序表中删除第的顺序表中删除第 i i 个元素，需要向前移动（个元素，需要向前移动（）个元素）个元素. . 参考答案：参考答案： n-1 4444、 1 1、已知栈的基本操作函数：、已知栈的基本操作函数： intint InitStack(SqStackInitStack(SqStack *S);*S); /构造空栈构造空栈 intint StackEmpty(SqStackStackEmpty(SqStack *S);/*S);/判断栈空判断栈空 intint Push(SqStack*S,

17、ElemTypePush(SqStack*S,ElemType e);/e);/入栈入栈 intint Pop(SqStackPop(SqStack *S,ElemType*S,ElemType *e);/*e);/出栈出栈 函数函数 conversionconversion 实现十进制数转换为八进制数，请将函数补充完整。实现十进制数转换为八进制数，请将函数补充完整。 voidvoid conversion()conversion() InitStack(S);InitStack(S); scanf(scanf(“%d%d”, while(N)while(N) （1 1）; ; N=N/8;N

18、=N/8; while(while(（2 2）) Pop(S,Pop(S, printf(printf(“%d%d”,e);,e); /conversion/conversion 参考答案：参考答案： （1）Push(S,N%8)（2）!StackEmpty(S) 4545、带头结点的单链表、带头结点的单链表 headhead 为空的判定条件是（为空的判定条件是（）。）。 参考答案：参考答案： head-next=NULL 4646、下面程序段的功能实现数据、下面程序段的功能实现数据 x x 进栈，要求在下划线处填上正确的语句。进栈，要求在下划线处填上正确的语句。 typedeftypedef

19、 structstruct intint s100;s100; intint top;top; sqstack;sqstack; voidvoid push(sqstackpush(sqstack ); elseelse _;_;_;_; 参考答案：参考答案： stack.top+，stack.sstack.top=x 4747、一个循环队列、一个循环队列 Q Q 的存储空间大小为的存储空间大小为 M,M,其队头和队尾指针分别为其队头和队尾指针分别为 frontfront 和和 rearrear，则循环队列中元素的个数为：，则循环队列中元素的个数为：。 参考答案：参考答案： (rear-fro

20、nt+M)%M 4848、设串长为、设串长为 n n，模式串长为，模式串长为 m m，则，则 KMPKMP 算法所需的附加空间为算法所需的附加空间为( () ) 参考答案：参考答案： O(m) 4949、一个线性表为、一个线性表为 B=B=（1212，2323，4545，5757，2020，0303，7878，3131，1515，3636），设散列表为），设散列表为 HT0.12HT0.12，散列函数为，散列函数为 H H（keykey）= = keykey % % 1313 并用线性探查法解决冲突，请画出散列表，并计算等概率情况下查找成功的并用线性探查法解决冲突，请画出散列表，并计算等概率情

21、况下查找成功的 平均查找长度。平均查找长度。 参考答案：参考答案： 0123456789101112 78 15 03 57 45 20 31 23 36 12 查找成功的平均查找长度：ASL SUCC=14/10= 1.4 5050、写出用直接插入排序将关键字序列、写出用直接插入排序将关键字序列54,23,89,48,64,50,25,90,3454,23,89,48,64,50,25,90,34排序过程的每一趟结果。排序过程的每一趟结果。 参考答案：参考答案： 初始：54，23，89，48，64，50，25，90，34 1：（23，54），89，48，64，50，25，90，34 2：（2

22、3，54，89），48，64，50，25，90，34 3：（23，48，54，89），64，50，25，90，34 4：（23，48，54，64，89），50，25，90，34 5：（23，48，50，54，64，89），25，90，34 6：（23，25，48，50，54，64，89），90，34 7：（23，25，48，50，54，64，89，90），34 8：（23，25，48，50，54，64，89，90，34） 5151、阅读以下二叉树操作算法，指出该算法的功能。、阅读以下二叉树操作算法，指出该算法的功能。 TemplateTemplate calss voidvoidBinTree

23、BinTree ： unknownunknown (BinTreeNode*t)(BinTreeNode*t) BinTreeNodeBinTreeNodeType*p*p =t,=t, *temp;*temp; ifif (p!=NULL)(p!=NULL) temptemp = = p pleftchild;leftchild; p pleftchildleftchild = = p prightchild;rightchild; p prightchildrightchild = = temp;temp; unknown(punknown(pleftchild);leftchild);

24、undnown(pundnown(prightchild);rightchild); 该算法的功能是：该算法的功能是：_ 参考答案：参考答案： 该算法的功能是：交换二叉树的左右子树的递归算法。 5252、已知一棵二叉树的前序遍历的结果序列是、已知一棵二叉树的前序遍历的结果序列是 ABECKFGHIJABECKFGHIJ，中序遍历的结果是，中序遍历的结果是 EBCDAFHIGJEBCDAFHIGJ，试写出这棵二叉树的后序遍历结果。，试写出这棵二叉树的后序遍历结果。 参考答案：参考答案： EDCBIHJGFA 5353、已知一组记录的排序码为（、已知一组记录的排序码为（4646，7979，5656

25、，3838，4040，80,80,9595，2424），写出对其进行快速排序的每一次划分结果。），写出对其进行快速排序的每一次划分结果。 参考答案：参考答案： 划分次序 划分结果 第一次 382440 4656809579 第二次 243840 4656809579 第三次 2438404656809579 第四次 2438404656809579 第五次 2438404656798095 第六次 2438404656798095 5454、设待排序序列为、设待排序序列为10,18,4,3,6,12,1,9,15,810,18,4,3,6,12,1,9,15,8请写出希尔排序每一趟的结果。增量

26、序列为请写出希尔排序每一趟的结果。增量序列为 5 5，3 3，2 2，1 1。 参考答案：参考答案： 初始：10，18，4，3，6，12，1，9，15，8 d=5：10，1，4，3，6，12，18，9，15，8 d=3：3，1，4，8，6，12，10，9，15，18 d=2：3，1，4，8，6，9，10，12，15，18 d=1：1，3，4，6，8，9，10，12，15，18 5555、写出下列程序的时间复杂度、写出下列程序的时间复杂度 s=0;s=0; forfor i=0;i=0; in;in; i+)i+) for(j=0;for(j=0; jn;jn; j+)j+) s+=Bij;s+

27、=Bij; sum=s;sum=s; 参考答案：参考答案： O（n2） 5656、设循环队列的容量为、设循环队列的容量为 4040（序号从（序号从 0 0 到到 3939），现经过一系列的入队和出队运算后，有），现经过一系列的入队和出队运算后，有 front=11front=11，rear=19;rear=19; front=19front=19，rear=11rear=11；问在这两种情况下，循环队列中各有元素多少个？；问在这两种情况下，循环队列中各有元素多少个？ 参考答案：参考答案： （1）L=（401911）% 40=8（2）L=（401119）% 40=32 5757、写出下列程序的时

28、间复杂度、写出下列程序的时间复杂度 for(i=0;for(i=0;in;in; i+)i+) forfor (j=0;(j=0; jm;jm; j+)j+) Aij=0;Aij=0; 参考答案：参考答案： O（m*n） 5858、设给定一个权值集合、设给定一个权值集合 W=(3W=(3，5 5，7 7，9 9，11)11)，要求根据给定的权值集合构造一棵哈夫曼树并计算哈夫曼树的带权路径长度，要求根据给定的权值集合构造一棵哈夫曼树并计算哈夫曼树的带权路径长度 WPLWPL。 参考答案：参考答案： 哈夫曼树略，WPL=78 5959、设一组初始记录关键字集合为、设一组初始记录关键字集合为(25(

29、25，1010，8 8，2727，3232，68)68)，散列表的长度为，散列表的长度为 8 8，散列函数，散列函数 H(k)=kH(k)=k modmod 7 7，要求分别用线性探测和链地址法作为解决冲，要求分别用线性探测和链地址法作为解决冲 突的方法设计哈希表。突的方法设计哈希表。 参考答案：参考答案： 6060、设完全二叉树的顺序存储结构中存储数据、设完全二叉树的顺序存储结构中存储数据 ABCDEABCDE，要求给出该二叉树的链式存储结构并给出该二叉树的前序、中序和后序遍历序列。，要求给出该二叉树的链式存储结构并给出该二叉树的前序、中序和后序遍历序列。 参考答案：参考答案： 链式存储结构略，前序 ABDEC，中序 DBEAC，后序 DEBCA。