2020自考数据结构答案解析题

第一题26、15、19、25

1 、在顺序表（8,11,15,19,25,26,30,33,42,48,50）中，用折半查找法查找关键字值20，需做的关键字比较次数为 4 。2、抽象数据类型的三大要素为 数据 、 数据之间结构 和 操作 。3、空格串的长度等于 0 。4 、栈和队列的区别仅在于 插入&&删除 操作定义不相同。5、设一个线性表的长度为50，P是指向线性链表的第10个元素，且P->next->next 指向第 11 元素。6、二叉树的第i层最多有 2^(i-1) 个结点，深度为k的二叉树最多有 2^k-1 个结点。7、利用MST性质来构造最小生成树的两种常用算法为______PRIM___和___KRUSKAL_______。8、常见的四类基本数据结构有：__栈______、____队列_____、____树______、______链表_____。（不确定，数据结构太多，究竟要写那几个？）明天再打 二、判断(对的打∨,错误打×, 10×2 = 20 分)1、 由于链式存储结构不要求逻辑上相邻的元素在物理位置上也相邻，因此，它具有随机存取的优点( y)。2、 赫夫曼树是指带权路径长度WPL最小的二叉树。一般而言，在给定条件下构造出的赫夫曼树不是唯一的 (y )。3、 非空完全二叉树的一个任意结点的右子树深度与其左子树深度的差值或者为0或者为1( y )。4、 先序遍历二叉排序树可得到一个关键字有序的序列( n) 。5、 在n个结点的无向图,若边数大于n-1,则该图必是连通图 ( n )。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个结点，其中叶子结点的个数是BA. 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的叶子结点生成一棵哈夫曼树，则其中非终端结点数为(A )。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其地址应该为( D)（哈希函数为h(key)=key mod 11） A.4 B.5 C.3 D.610、在一个无向图中,所有顶点的度数之和等于所有边数的(B )倍.A.3 B.2 C.1 D.1/2打完了，为了数据结构考试攒人品~

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;}

第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、边的权值之和最小的生成树

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 由于不好画图 就不答了.就帮搂主答这几题了.太多了不想回答哈.....累喔 如果错了希望指出来喔

accacdbc