2020自考数据结构答案详解

7. (1)O(n*i) (2)O(n平方) 由于不好打 只好用中文代替了.8. 72 30 42 16 26 11 15 5 6 7 8 2 4WPL=30*2+16*3+(5+7+8)*5+(2+4)*6=自己算吧9.临接句阵:0 1 1 1 01 0 0 0 11 0 0 0 11 0 0 0 10 1 1 1 0临接表(单链表的格式: data next):v1 -> v2 -> v3 -> v4 ^v2 -> v1 -> v5 ^v3 -> v1 -> v5 ^v4 -> v1 -> v5 ^v5 -> v2 -> v3 -> v4 ^10 由于不好画图 就不答了.就帮搂主答这几题了.太多了不想回答哈.....累喔 如果错了希望指出来喔

1 、在顺序表（8,11,15,19,25,26,30,33,42,48,50）中，用折半查找法查找关键字值20，需做的关键字比较次数为 4 。2、抽象数据类型的三大要素为 数据对象 、 数据关系 和 基本操作 。3、空格串的长度等于 空格的个数 。4 、栈和队列的区别仅在于 删除 操作定义不相同。5、设一个线性表的长度为50，P是指向线性链表的第10个元素，且P->next->next 指向第 12 元素。6、二叉树的第i层最多有 2^(i-1) 个结点，深度为k的二叉树最多有 2^k-1 个结点。7、利用MST性质来构造最小生成树的两种常用算法为______普里姆算法___和___格鲁斯卡尔算法_______。8、常见的四类基本数据结构有：__集合_、_线性结构_、_树形结构_、_网状结构_。二、判断(对的打∨,错误打×, 10×2 = 20 分)1、由于链式存储结构不要求逻辑上相邻的元素在物理位置上也相邻，因此，它具有随机存取的优点( n)。2、 赫夫曼树是指带权路径长度WPL最小的二叉树。一般而言，在给定条件下构造出的赫夫曼树不是唯一的 (y )。3、 非空完全二叉树的一个任意结点的右子树深度与其左子树深度的差值或者为0或者为1( n)。4、 先序遍历二叉排序树可得到一个关键字有序的序列( n) 。5、 在n个结点的无向图,若边数大于n-1,则该图必是连通图 ( y )。6、 在n个元素进栈后，它们的出栈顺序和进栈顺序一定正好相反( n )。7、 往顺序表中插人一个元素，平均要移动大约一半的元素(y )。8、 类似于算法的时间复杂度，空间复杂度可以作为算法所需存储空间的量度( y )。9、 赫夫曼树一定是满二叉树( n )。10、 队列的基本特征是先进后出( n )。三、选择题（10×2=20分）1、 有六个元素6，5，4，3，2，1 的顺序进栈，问下列哪一个不是合法的出栈序列？( B )A. 2 3 4 1 5 6 B. 1 2 4 5 3 6C. 6 4 5 1 2 3 D. 4 5 3 1 2 62、 一棵完全二叉树上有1001个结点，其中叶子结点的个数是DA. 254 B. 500C. 250 D. 以上答案都不对 3、线性链表不具有的特点(A ).A.随机访问 B.不必事先估计所需存储空间大小C.插入与删除时不必移动元素 D.所需空间与线性表长度成正比4、向顺序栈中压入新元素时,应当(B ).(此题需看书上栈定义)A.先移动栈顶指针,再存入元素 B.先存入元素,再移动栈顶指针C.先后次序无关紧要 D.同时进行5、 具有65个结点的完全二叉树的高度为( B). (根的层次号为1)A.8 B.7C.6 D.56、 由权值分别为3，8，10，2，6的叶子结点生成一棵哈夫曼树，则其中非终端结点数为(C )。A. 2 B. 3C. 4 D. 57、 n个顶点的有向完全图中含有向边的数目最多为( D ) A.n-1 B.n C.n(n-1)/2 D.n(n-1) 8、一个对象序列的排序码为{46,79,56,38,40,84},采用快速排序以位于最左位置的对象为基准而得到的第一次划分结果为(C ). A.{38,46,79,56,40,84} B.{38,79,56,46,40,84} C.{40,38,46,56,79,84} D.{38,46,56,79,40,84} 9、长度为11的哈希表中已经填有关键字17，60，29的记录，采用二次探测再散列方法解决冲突，则填入关键字38其地址应该为( A)（哈希函数为h(key)=key mod 11） A.4 B.5 C.3 D.610、在一个无向图中,所有顶点的度数之和等于所有边数的(B )倍.A.3 B.2 C.1 D.1/2

第18题 (2) 分 对线性表进行二分查找时，要求线性表必须( )。C、顺序存储，且结点按关键字有序排序 第19题 (2) 分 下面关于B树和B+树的叙述中，不正确的是C、都能有效地支持顺序检索 第20题 (2) 分 设输入序列为A,B,C,D，借助一个栈得到的输出序列不可能是( )。C、DABC 第21题 (2) 分 连通图是指图中任意两个顶点之间( )。A、都连通的无向图 第22题 (2) 分 设有向图n个顶点和e条边，进行拓扑排序时，总的计算时间为( )。D)O(n+e)第23题 (2) 分 从理论上讲，将数据以( )结构存放，查找一个数据的时间不依赖于数据的个数n。C、散列表 第24题 (2) 分 n个记录直接选择排序时所需的记录最多交换次数是( )。A、n-1 第25题 (2) 分 连通网的最小生成树是其所有生成树中( )。D、边的权值之和最小的生成树

3.28void InitCiQueue(CiQueue&Q)//初始化循环链表表示的队列Q{Q=(CiLNode*)malloc(sizeof(CiLNode));Q->next=Q;}//InitCiQueuevoidEnCiQueue(CiQueue&Q,int x)//把元素x插入循环列表表示的队列Q,Q指向队尾元素，Q->next指向头结点，Q->next->next指向队尾元素{p=(CiLNode*)malloc(sizeof(CiLNode));p->data=x;p->next=Q->next;//直接把p加在Q的后面Q->next=p;Q=p;//修改尾指针}Status DeCiQueue(CiQueue&Q,int x)//从循环链表表示的队列Q头部删除元素x{if(Q==Q->next)return INFEASIBLE;//队列已空p=Q->next->next;x=p->data;Q->next->next=p->next;free(p);rturn OK;}//DeCiqueue3.31int Palindrome_Test(){InitStack(S);InitQueue(Q);while((c=getchar())!='@'){Push(S,c);EnQueue(Q,c);}while(!StackEmpty(S)){pop(S,a);DeQueue(Q,b);if(a!=b)return ERROR;}return OK;}

( )逻辑结构相同但存储不同 可以是不同的数据结构 例如 线性表的逻辑结构属于线性结构 采用顺序存储结构为顺序表 而采用链式存储结构称为线性链表

( )栈和队列的逻辑结构相同 其存储表示也可相同(顺序存储和链式存储) 但由于其运算集合不同而成为不同的数据结构

( )数据结构的评价非常复杂 可以考虑两个方面 一是所选数据结构是否准确 完整的刻划了问题的基本特征;二是是否容易实现(如对数据分解是否恰当;逻辑结构的选择是否适合于运算的功能 是否有利于运算的实现;基本运算的选择是否恰当 )

评价好的算法有四个方面 一是算法的正确性;二是算法的易读性;三是算法的健壮性;四是算法的时空效率(运行)

( )见上面题 ( )见上面题 ( )见上面题

( )算法的时间复杂性是算法输入规模的函数 算法的输入规模或问题的规模是作为该算法输入的数据所含数据元素的数目 或与此数目有关的其它参数 有时考虑算法在最坏情况下的时间复杂度或平均时间复杂度

( )算法是对特定问题求解步骤的描述 是指令的有限序列 其中每一条指令表示一个或多个操作 算法具有五个重要特性 有穷性 确定性 可行性 输入和输出

( )频度 在分析算法时间复杂度时 有时需要估算基本操作的原操作 它是执行次数最多的一个操作 该操作重复执行的次数称为频度

集合 线性结构 树形结构 图形或网状结构 逻辑结构 存储结构 操作(运算)

通常考虑算法所需要的存储空间量和算法所需要的时间量 后者又涉及到四方面 程序运行时所需输入的数据总量 对源程序进行编译所需时间 计算机执行每条指令所需时间和程序中指令重复执行的次数

D是数据元素的有限集合 S是D上数据元素之间关系的有限集合

数据结构 这一术语有两种含义 一是作为一门课程的名称;二是作为一个科学的概念 作为科学概念 目前尚无公认定义 一般认为 讨论数据结构要包括三个方面 一是数据的逻辑结构 二是数据的存储结构 三是对数据进行的操作(运算) 而数据类型是值的集合和操作的集合 可以看作是已实现了的数据结构 后者是前者的一种简化情况

见上面题

将学号 姓名 平均成绩看成一个记录(元素 含三个数据项) 将 个这样的记录存于数组中 因一般无增删操作 故宜采用顺序存储

typedef struct

{int num;//学号

char name[ ];//姓名

float score;/平均成绩

}node;

node student[ ];

见上面题 ( )

应从两方面进行讨论 如通讯录较少变动(如城市私人电话号码) 主要用于查询 以顺序存储较方便 既能顺序查找也可随机查找;若通讯录经常有增删操作 用链式存储结构较为合适 将每个人的情况作为一个元素(即一个结点存放一个人) 设姓名作关键字 链表安排成有序表 这样可提高查询速度

线性表中的插入 删除操作 在顺序存储方式下平均移动近一半的元素 时间复杂度为O(n);而在链式存储方式下 插入和删除时间复杂度都是O( )

对算法A 和A 的时间复杂度T 和T 取对数 得nlog 和 logn 显然 算法A 好于A

struct node

{int year month day; };

typedef struct

{int num;//帐号

char name[ ];//姓名

struct node date;//开户年月日

int tag;//储蓄类型 如 零存 一年定期……

float put;//存入累加数;

float interest;//利息

float total;//帐面总数

}count;

( )n ( )n+ ( )n ( )(n+ )(n )/ ( )(n+ )(n )/ ( )n