数据结构模拟练习题1-参考答案

1、数据结构模拟练习题1 参考答案一、单项选择题（每小题2分，共30分）1、 算法的计算量的大小称为计算的（ B ）。A效率 B. 复杂性 C. 现实性 D. 难度2、静态链表中指针表示的是（B）.内存地址 B.数组下标 C.下一元素地址 D.左、右孩子地址3、对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为（C）.O(n)O(n) B. O(n) O(1) C. O(1)O(n) D. O(1) O(1)4、在单链表指针为p的结点之后插入指针为s的结点，正确的操作是：（D ）。Ap->next=s;s->next=p->next; Bp->next=s->

2、;next;p->next=s; Cp->next=s;p->next=s->next; D s->next=p->next;p->next=s;5、设有一顺序栈S，元素s1,s2,s3,s4,s5,s6依次进栈，如果6个元素出栈的顺序是s2,s3,s4, s6 , s5,s1,则栈的容量至少应该是（ B ）A.2 B. 3 C. 5 D.66、串是一种特殊的线性表，其特殊性体现在（B ）。A可以顺序存储 B数据元素是一个字符C可以链接存储 D数据元素可以是多个字符7、若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（ D ）

3、。A9 B11 C15 D不确定 8、列说法中正确的是（ A ）。A任何一棵二叉树中至少有一个结点的度为2B任何一棵二叉树中每个结点的度都为2C任何一棵二叉树中的度肯定等于2D任何一棵二叉树中的度可以小于29、已知一棵二叉树的前序遍历结果为ABCDEF,中序遍历结果为CBAEDF,则后序遍历的结果为（ B ）。ACBEFDA B FEDCBA C CBEDFA D不定 10、下列哪一种图的邻接矩阵是对称矩阵（ B ）。A有向图 B无向图 CAOV网 DAOE网11、在图采用邻接表存储时，求最小生成树的 Prim 算法的时间复杂度为(A ）。A. O(n+e) B. O(n) C. O(n2)

4、D. O(n3)12、适用于折半查找的表的存储方式及元素排列要求为（ D ）。 A链接方式存储，元素无序 B链接方式存储，元素有序C顺序方式存储，元素无序 D顺序方式存储，元素有序13、下图所示的4棵二叉树, （B ）是平衡二叉树。 （A） （B） （C） （D）14、若用冒泡排序方法对序列10,14,26,29,41,52从大到小排序，需进行（C ）次比较。 A. 3 B. 10 C. 15 D. 25 15、下列四个序列中，哪一个是堆（C ）。A. 75,65,30,15,25,45,20,10 B. 75,65,45,10,30,25,20,15C. 75,45,65,30,15,25,

5、20,10 D. 75,45,65,10,25,30,20,15二、判断题（在各题后填写“”或“×”，每小题1分，共10分）1、数据的物理结构是指数据在计算机内的实际存储形式。( ) 2、顺序存储方式的优点是存储密度大，且插入、删除运算效率高。( × )3、循环队列中不存在队列满的问题。 （×）4、完全二叉树一定存在度为1的结点。(× )5、哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近。()6、一个有向图的邻接表和逆邻接表中的结点数可能不等。（ × ）7、含有n个顶点和n-1条边的图一定是连通图。( × )8、当待排序

6、记录已经从小到大排序或已经从大到小排序时，快速排序的执行时间最省。（ × ）9、用shell排序时，若关键字的排列杂乱无序，则效率最高。（ × ）10、平衡二叉树是一种提高查找效率的二叉排序树。()三、 填空题（每空分，共10分）1、在带头结点的非空单链表中，头结点的存储位置由 头指针 指示，首元素结点的存储位置由 头结点指针域 指示，除首元素结点外，其它任一元素结点的存储位置由 前驱结点指针域    指示。2、一个栈的输入序列是：A、B、C，则不可能的栈输出序列是_CAB_。3、以下运算实现在链栈上的退栈，请在_处用请适当句子予以填充。Int Pop(

7、LstackTp *ls,DataType *x) LstackTp *p; if(ls!=NULL) p=ls; *x=_; p->data; ls=ls->next; _; free(p); return(1)； else return(0); 4、 直接定址 法构造的哈希函数肯定不会发生冲突。5、已知N元整型数组a存放N个学生的成绩，已按由大到小排序，以下算法是用对分（折半）查找方法统计成绩大于或等于X分的学生人数，请填空使之完善。 #define N /*学生人数*/int uprx(int aN,int x ) /*函数返回大于等于X分的学生人数*/ int head=1

8、,mid,rear=N; do mid=(head+rear)/2;if(x<=amid) _(1) rear=mid-1 _ else _(2)_head=mid+1 _;while(_(3)_ head>rear _);if (ahead<x) return head-1;return head; 四、应用题（每小题6分，共30分）1、在单链表和双向链表中，能否从当前结点出发访问到任何一个结点?解答：在单链表中不能从当前结点（若当前结点不是第一结点）出发访问到任何一个结点，链表只能从头指针开始，访问到链表中每个结点。在双链表中求前驱和后继都容易，从当前结点向前到第一结点，

9、向后到最后结点，可以访问到任何一个结点。2、HASH方法的平均查找路长决定于什么？ 是否与结点个数N有关？ 处理冲突的方法主要有哪些？解答：解答：哈希方法的平均查找路长主要取决于负载因子（表中实有元素数与表长之比），它反映了哈希表的装满程度，该值一般取0.650.9。散列表存储中解决碰撞的基本方法： 开放定址法 形成地址序列的公式是：Hi=（H（key）+di）% m，其中m是表长，di是增量。根据di取法不同，又分为三种：adi =1，2，m-1 称为线性探测再散列，其特点是逐个探测表空间，只要散列表中有空闲空间，就可解决碰撞，缺点是容易造成“聚集”，即不是同义词的关键字争夺同一散列地址。b

10、di =12，-12，22，-22， ，±k2（km/2） 称为二次探测再散列，它减少了聚集，但不容易探测到全部表空间，只有当表长为形如4j+3（j为整数）的素数时才有可能。cdi =伪随机数序列，称为随机探测再散列。 再散列法 Hi=RHi（key） i=1，2，k，是不同的散列函数，即在同义词产生碰撞时，用另一散列函数计算散列地址，直到解决碰撞。该方法不易产生“聚集”，但增加了计算时间。 链地址法 将关键字为同义词的记录存储在同一链表中，散列表地址区间用H0.m-1表示，分量初始值为空指针。凡散列地址为i（0im-1）的记录均插在以Hi为头指针的链表中。这种解决方法中数据元素个数

11、不受表长限制，插入和删除操作方便，但增加了指针的空间开销。这种散列表常称为开散列表，而中的散列表称闭散列表，含义是元素个数受表长限制。 建立公共溢出区 设H0.m-1为基本表，凡关键字为同义词的记录，都填入溢出区O0.m-1。3、给出一个以下带权图的邻接矩阵表示：（1）每项活动ai的最早开始时间e(ai)和最迟开始时间l(ai)；（2）完成此项工程需要多少天（设弧上权值为天数）；（3）哪些是关键活动；（4）是否存在某项活动，当其提高速度后能使整个工程缩短工期？12345678910a15a26a33a74a53a94a63a815a10a11224a13a12a46解:(1)所有事件的最早发生

12、时间如下： ee(1)=0; ee(2)=5; ee(3)=6; ee(4)=maxee(2)+3, ee(3)+6=12; ee(5)=maxee(3)+3, ee(4)+3=15; ee(6)=ee(4)+4=16; ee(7)=ee(5)+1=16; ee(8)=ee(5)+4=19; ee(9)=maxee(7)+5,ee(8)+2=21; ee(10)=max(ee(6)+4,ee(9)+2=23.所有事件的最迟发生时间如下： le(10)=23; le(9)=le(10)-2=21; le(8)=le(9)-2=19; le(7)=le(9)-5=14; le(6)=le(10)-

13、4=19; le(5)=minle(7)-1,le(8)-4=15; le(4)=minle(6)-4,le(5)-3=12; le(3)=minle(4)-6,le(5)-3=6; le(2)=le(4)-3=9; le(1)= minle(2)-5,le(3)-6=0 (3) 求所有活动的e(),l()和d()如下：活动a1：e(1)=ee(1)=0; l(1)=le(2)-5=4, d(1)=4;活动a2：e(2)=ee(1)=0; l(2)=le(3)-6=0, d(2)=0;活动a3：e(3)=ee(2)=5; l(3)=le(4)-3=8, d(3)=3;活动a4：e(4)=ee(

14、2)=6; l(4)=le(4)-6=6, d(4)=0;活动a5：e(5)=ee(3)=6; l(5)=le(5)-3=12,d(5)=6;活动a6：e(6)=ee(3)=12; l(6)=le(5)-3=12,d(6)=0;活动a7：e(7)=ee(4)=12; l(7)=le(6)-4=15,d(7)=3;活动a8：e(8)=ee(5)=15; l(8)=le(7)-1=15, d(8)=0;活动a9：e(9)=ee(5)=15; l(9)=le(8)-4=15, d(9)=0;活动a10：e(10)=ee(6)=16; l(10)=le(9)-5=16,d(10)=0;活动a11：e(

15、11)=ee(7)=19; l(11)=le(9)-2=19,d(11)=0;活动a12：e(12)=ee(8)=16; l(12)=le(10)-4=19,d(12)=3;活动a13：e(13)=ee(8)=21; l(13)=le(10)-2=21,d(13)=0; （2）完成此项工程最少需要23天。 (3)从以上计算得出，关键活动为a2,a4,a6,a8,a9,a10,a11,a13。这些活动构成了两条关键路径a2，a4，a6，a8，a10，a13和 a2，a4，a6,a9，a11，a13。（4）存在a2,a4,a6,a13活动，当其提高速度后能使整个工程缩短工期。4、已知序列17,18

16、,60,40,7,32,73,65,85，请给出采用冒泡排序法对该序列升序排序时的每一趟结果。解：初始：17 18 60 40 07 32 73 65 85第1趟：17 18 40 07 32 60 65 73 85第2趟：17 18 07 32 40 60 65 73 85第3趟： 17 07 18 32 40 60 65 73 85第4趟： 07 17 18 32 40 60 65 73 85第5趟： 07 17 18 32 40 60 65 73 85第5趟无元素交换，则排序结束。5、设有正文AADBAACACCDACACAAD,字符集为A,B,C,D,设计一套二进制编码，使得上述正文的

17、编码最短。解：字符A，B，C，D出现的次数为9,1,5,3。其哈夫曼编码如下A:1，B:000，C:01，D:0011359000111五、算法设计题（20分）1、试分别以顺序表和单链表作存储结构，各写一个实现线性表的就地(即使用尽可能少的附加空间)逆置的算法，在原表的存储空间内将线性表(a1，a2,. .,an)逆置为(an,. .,a2,a1)。解答：(1)顺序表分析：将顺序表的第一个元素与最后一个元素互换，第二个元素与倒数第二个元素互换。void  invert(SeqList  *L,  int  *num)    int&#

18、160; j;  ElemType  tmp;for(j=0;j<=(*num-1)/2;j+) tmp=Lj;Lj=L*num-j-1;L*num-j-1=tmp;(2)单链表void  invert(LinkList  L)  Node  *p, *q, *r;    if(L->next =NULL)  return;          /*链表为空*/   

19、 p=L->next;        q=p->next;               p->next=NULL;              /* 摘下第一个结点，生成初始逆置表 */while(q!=NULL)             /* 从第二个结点起依次头插入当前逆置表 */   r=q->next;q->next=L->next;L->next=q;q=r;  2、有一链栈，每个结点放一个字符。试编写一个程序，具有下列功能：（1） 从键盘上输入一个字符串入栈，以“！”不入栈；（2） 遍历及显示栈中内容；（3） 执行退栈操作，使栈为空。#include<stdio.h>t