数据结构.docx
- 文档编号:18514890
- 上传时间:2023-08-19
- 格式:DOCX
- 页数:17
- 大小:30.32KB
数据结构.docx
《数据结构.docx》由会员分享,可在线阅读,更多相关《数据结构.docx(17页珍藏版)》请在冰点文库上搜索。
数据结构
第一次作业
一、填空题
1.通常从四个方面评价算法的质量:
正确性、易读性、强壮性和高效率。
2.一个算法的时间复杂度为(n3+n2log2n+14n)/n2,其数量级表示为O(n)。
3.假定一棵树的广义表表示为A(C,D(E,F,G),H(I,J)),则树中所含的结点数为____9____个,树的深度为____3____,树的度为___3___。
4.后缀算式923+-102/-的值为____-1____。
中缀算式(3+4X)-2Y/3对应的后缀算式为____34X*+2Y*3/-_。
5.若用链表存储一棵二叉树时,每个结点除数据域外,还有指向左孩子和右孩子的两个指针。
在这种存储结构中,n个结点的二叉树共有__2n__个指针域,其中有__n-1__个指针域是存放了地址,有n+1___个指针是空指针。
6.对于一个具有n个顶点和e条边的有向图和无向图,在其对应的邻接表中,所含边结点分别有___e____个和____2e____个。
7.AOV网是一种__有向无回路的图。
8.在一个具有n个顶点的无向完全图中,包含有_n(n-1)/2___条边,在一个具有n个顶点的有向完全图中,包含有_n(n-1)__条边。
9.假定一个线性表为(12,23,74,55,63,40),若按Key%4条件进行划分,使得同一余数的元素成为一个子表,则得到的四个子表分别为__(12,40)_、__()____、__(74)__和(23,55,63)。
10.向一棵B_树插入元素的过程中,若最终引起树根结点的分裂,则新树比原树的高度_增加1_。
11.在堆排序的过程中,对任一分支结点进行筛运算的时间复杂度_O(log2n)____,整个堆排序过程的时间复杂度为___O(nlog2n)___。
12.在快速排序、堆排序、归并排序中,_归并__排序是稳定的。
二、选择题
1.栈和队列的共同特点是(A)。
A.只允许在端点处插入和删除元素
B.都是先进后出
C.都是先进先出
D.没有共同点
2.用链接方式存储的队列,在进行插入运算时(D).
A.仅修改头指针 B.头、尾指针都要修改
C.仅修改尾指针D.头、尾指针可能都要修改
3.以下数据结构中哪一个是非线性结构?
(D)
A.队列 B.栈C.线性表 D.二叉树
4.设有一个二维数组A[m][n],假设A[0][0]存放位置在644(10),A[2][2]存放位置在676(10),每个元素占一个空间,问A[3][3](10)存放在什么位置?
脚注(10)表示用10进制表示。
(C)
A.688B.678C.692D.696
5.树最适合用来表示(C)。
A.有序数据元素B.无序数据元素
C.元素之间具有分支层次关系的数据D.元素之间无联系的数据
6.二叉树的第k层的结点数最多为(D).
A.2k-1B.2K+1C.2K-1 D.2k-1
7.若有18个元素的有序表存放在一维数组A[19]中,第一个元素放A[1]中,现进行二分查找,则查找A[3]的比较序列的下标依次为(D)
A.1,2,3B.9,5,2,3
C.9,5,3D.9,4,2,3
8.对n个记录的文件进行快速排序,所需要的辅助存储空间大致为(C)
A.O
(1) B.O(n) C.O(1og2n)D.O(n2)
9.对于线性表(7,34,55,25,64,46,20,10)进行散列存储时,若选用H(K)=K%9作为散列函数,则散列地址为1的元素有(D)个,
A.1B.2C.3D.4
10.设有6个结点的无向图,该图至少应有(A)条边才能确保是一个连通图。
A.5B.6C.7D.8
第二次作业
一、问答题
1、在如下数组A中链接存储了一个线性表,表头指针为A[0].next,试写出该线性表。
A01234567
data
60
50
78
90
34
40
next
3
5
7
2
0
4
1
1.线性表为:
(78,50,40,60,34,90)
2、已知一个图的顶点集V和边集E分别为:
V={1,2,3,4,5,6,7};
E={(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15,(3,5)12,(3,6)9,(4,6)4,(4,7)20,(5,6)18,(6,7)25};
(1,2)3,(4,6)4,(1,3)5,(1,4)8,(2,5)10,(4,7)20
二、算法设计
1.统计出单链表HL中结点的值等于给定值X的结点数。
intCountX(LNode*HL,ElemTypex)
intCountX(LNode*HL,ElemTypex)
{inti=0;LNode*p=HL;//i为计数器
while(p!
=NULL)
{if(P->data==x)i++;
p=p->next;
}//while,出循环时i中的值即为x结点个数
returni;
}//CountX
2.设有一组初始记录关键字序列(K1,K2,…,Kn),要求设计一个算法能够在O(n)的时间复杂度内将线性表划分成两部分,其中左半部分的每个关键字均小于Ki,右半部分的每个关键字均大于等于Ki。
voidquickpass(intr[],ints,intt)
{
inti=s,j=t,x=r[s];
while(i while(i while(i } r[i]=x; 3.设有两个集合A和集合B,要求设计生成集合C=A∩B的算法,其中集合A、B和C用链式存储结构表示。 typedefstructnode{intdata;structnode*next;}lklist; voidintersection(lklist*ha,lklist*hb,lklist*&hc) { lklist*p,*q,*t; for(p=ha,hc=0;p! =0;p=p->next) {for(q=hb;q! =0;q=q->next)if(q->data==p->data)break; if(q! =0){t=(lklist*)malloc(sizeof(lklist));t->data=p->data;t->next=hc;hc=t;} } } 第三次作业 一、选择题 1.设一维数组中有n个数组元素,则读取第i个数组元素的平均时间复杂度为(C)。 (A)O(n)(B)O(nlog2n)(C)O (1)(D)O(n2) 2.设一棵二叉树的深度为k,则该二叉树中最多有(D)个结点。 (A)2k-1(B)2k(C)2k-1(D)2k-1 3.设某无向图中有n个顶点e条边,则该无向图中所有顶点的入度之和为(D)。 (A)n(B)e(C)2n(D)2e 4.在二叉排序树中插入一个结点的时间复杂度为(B)。 (A)O (1)(B)O(n)(C)O(log2n)(D)O(n2) 5.设某有向图的邻接表中有n个表头结点和m个表结点,则该图中有(C)条有向边。 (A)n(B)n-1(C)m(D)m-1 6.设一组初始记录关键字序列为(345,253,674,924,627),则用基数排序需要进行(A)趟的分配和回收才能使得初始关键字序列变成有序序列。 (A)3(B)4(C)5(D)8 7.设用链表作为栈的存储结构则退栈操作(B)。 (A)必须判别栈是否为满(B)必须判别栈是否为空 (C)判别栈元素的类型(D)对栈不作任何判别 8.下列四种排序中(A)的空间复杂度最大。 (A)快速排序(B)冒泡排序(C)希尔排序(D)堆 9.设某二叉树中度数为0的结点数为N0,度数为1的结点数为Nl,度数为2的结点数为N2,则下列等式成立的是(C)。 (A)N0=N1+1(B)N0=Nl+N2(C)N0=N2+1(D)N0=2N1+l 10.设有序顺序表中有n个数据元素,则利用二分查找法查找数据元素X的最多比较次数不超过(A)。 (A)log2n+1(B)log2n-1(C)log2n(D)log2(n+1) 二、填空题 1.设有n个无序的记录关键字,则直接插入排序的时间复杂度为__O(n2),快速排序的平均时间复杂度为_O(nlog2n)__。 2.设指针变量p指向双向循环链表中的结点X,则删除结点X需要执行的语句序列为p>llink->rlink=p->rlink;p->rlink->llink=p->rlink(设结点中的两个指针域分别为llink和rlink)。 3.根据初始关键字序列(19,22,01,38,10)建立的二叉排序树的高度为____3___。 4.4.深度为k的完全二叉树中最少有__2k-1__个结点。 5.设初始记录关键字序列为(K1,K2,…,Kn),则用筛选法思想建堆必须从第_n/2 个元素开始进行筛选。 6.设哈夫曼树中共有99个结点,则该树中有__50___个叶子结点;若采用二叉链表作为存储结构,则该树中有__51_个空指针域。 7.设有一个顺序循环队列中有M个存储单元,则该循环队列中最多能够存储__m-1_个队列元素;当前实际存储_,(R-F+M)%M_个队列元素(设头指针F指向当前队头元素的前一个位置,尾指针指向当前队尾元素的位置)。 8£®设顺序线性表中有n个数据元素,则第i个位置上插入一个数据元素需要移动表中n+1-i个数据元素;删除第i个位置上的数据元素需要移动表中n-i_个元素。 9£®设一组初始记录关键字序列为(20,18,22,16,30,19),则以20为中轴的一趟快速排序结果为_(19,18,16,20,30,22)_。 10£®设一组初始记录关键字序列为(20,18,22,16,30,19),则根据这些初始关键字序列建成的初始堆为_(16,18,19,20,32,22)_。 1.11£®设某无向图G中有n个顶点,用邻接矩阵A作为该图的存储结构,则顶点i和顶点j互为邻接点的条件是__A[i][j]=1___。 12.设无向图对应的邻接矩阵为A,则A中第i上非0元素的个数__等于__第i列上非0元素的个数(填等于,大于或小于)。 2.13£®设前序遍历某二叉树的序列为ABCD,中序遍历该二叉树的序列为BADC,则后序遍历该二叉树的序列为__BDCA__。 14.设散列函数H(k)=kmodp,解决冲突的方法为链地址法。 要求在下列算法划线处填上正确的语句完成在散列表hashtalbe中查找关键字值等于k的结点,成功时返回指向关键字的指针,不成功时返回标志0。 typedefstructnode{intkey;structnode*next;}lklist; voidcreatelkhash(lklist*hashtable[]) { inti,k;lklist*s; for(i=0;i for(i=0;i { s=(lklist*)malloc(sizeof(lklist));s->key=a[i]; k=a[i]%p;s->next=hashtable[k];____hashtable[k]=s_______; } } 三、简答题 已知一个图的顶点集V和边集E分别为: V={1,2,3,4,5,6,7}; E={(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15, (3,5)12,(3,6)9,(4,6)4,(4,7)20,(5,6)18,(6,7)25}; 用克鲁斯卡尔算法得到最小生成树,试写出在最小生成树中依次得到的各条边 (1,2)3,(4,6)4,(1,3)5,(1,4)8,(2,5)10,(4,7)20 第四次作业 一、填空题 1.设有一个顺序共享栈S[0: n-1],其中第一个栈项指针top1的初值为-1,第二个栈顶指针top2的初值为n,则判断共享栈满的条件是top1+1=top。 2.顺序存储结构存储表头结点的优点是可以随机访问到任一个顶点的简单链表。 3.设有一个n阶的下三角矩阵A,如果按照行的顺序将下三角矩阵中的元素(包括对角线上元素)存放在n(n+1)个连续的存储单元中,则A[i][j]与A[0][0]之间有i(i+1)/2+j-1_个数据元素。 4.栈的插入和删除只能在栈的栈顶进行,后进栈的元素必定先出栈,所以又把栈称为_FILO___表;队列的插入和删除运算分别在队列的两端进行,先进队列的元素必定先出队列,所以又把队列称为___FIFO_____表。 5.设一棵完全二叉树的顺序存储结构中存储数据元素为ABCDEF,则该二叉树的前序遍历序列为ABDECF,中序遍历序列为DBEAFC,后序遍历序列为DEBFCA。 6.设一棵完全二叉树有128个结点,则该完全二叉树的深度为__8____,有___64___叶子结点。 7.设有向图G的存储结构用邻接矩阵A来表示,则A中第i行中所有非零元素个数之和等于顶点i的_出度_,第i列中所有非零元素个数之和等于顶点i的_入度__。 8.设一组初始记录关键字序列(k1,k2,……,kn)是堆,则对i=1,2,…,n/2而言满足的条件为__ki<=k2i&&ki<=k2i+1_。 9.下面程序段的功能是实现冒泡排序算法,请在下划线处填上正确的语句。 voidbubble(intr[n]) { for(i=1;i<=n-1;i++) { for(exchange=0,j=0;j<__n-i____;j++) if(r[j]>r[j+1]){temp=r[j+1];_r[j+1]=r[j]_;r[j]=temp;exchange=1;} if(exchange==0)return; } } 10.下面程序段的功能是实现二分查找算法,请在下划线处填上正确的语句。 structrecord{intkey;intothers;}; intbisearch(structrecordr[],intk) { intlow=0,mid,high=n-1; while(low<=high) { ___mid=(low+high)/2__________; if(r[mid].key==k)return(mid+1);elseif(___mid=(low+high)/2_____)high=mid-1;elselow=mid+1; } return(0); } 二、算法设计 1.设单链表中有仅三类字符的数据元素(大写字母、数字和其它字符),要求利用原单链表中结点空间设计出三个单链表的算法,使每个单链表只包含同类字符。 typedefchardatatype; typedefstructnode{datatypedata;structnode*next;}lklist; voidsplit(lklist*head,lklist*&ha,lklist*&hb,lklist*&hc) { lklist*p;ha=0,hb=0,hc=0; for(p=head;p! =0;p=head) { head=p->next;p->next=0; if(p->data>='A'&&p->data<='Z'){p->next=ha;ha=p;} elseif(p->data>='0'&&p->data<='9'){p->next=hb;hb=p;}else{p->next=hc;hc=p;} } } 2.设计在链式存储结构上交换二叉树中所有结点左右子树的算法。 typedefstructnode{intdata;structnode*lchild,*rchild;}bitree; voidswapbitree(bitree*bt) { bitree*p; if(bt==0)return; swapbitree(bt->lchild);swapbitree(bt->rchild); p=bt->lchild;bt->lchild=bt->rchild;bt->rchild=p; } 3.在链式存储结构上建立一棵二叉排序树。 #definen10 typedefstructnode{intkey;structnode*lchild,*rchild;}bitree; voidbstinsert(bitree*&bt,intkey) { if(bt==0){bt=(bitree*)malloc(sizeof(bitree));bt->key=key;bt->lchild=bt->rchild=0;} elseif(bt->key>key)bstinsert(bt->lchild,key);elsebstinsert(bt->rchild,key); } voidcreatebsttree(bitree*&bt) { inti; for(i=1;i<=n;i++)bstinsert(bt,random(100)); } 第五次作业 一、填空题 1.设需要对5个不同的记录关键字进行排序,则至少需要比较__4____次,至多需要比较____10___次。 2.快速排序算法的平均时间复杂度为O(nlog2n),直接插入排序算法的平均时间复杂度为O(n2)。 3.设二叉排序树的高度为h,则在该树中查找关键字key最多需要比较__n___次。 4.设在长度为20的有序表中进行二分查找,则比较一次查找成功的结点数有___1_____个,比较两次查找成功有结点数有___2___个。 5.设一棵m叉树脂的结点数为n,用多重链表表示其存储结构,则该树中有n(m-1)+1个空指针域。 6.设指针变量p指向单链表中结点A,则删除结点A的语句序列为: q=p->next;p->data=q->data;p->next=q->next;feee(q); 7.数据结构从逻辑上划分为三种基本类型: _线性结构、树型结构和图型结构。 8.设无向图G中有n个顶点e条边,则用邻接矩阵作为图的存储结构进行深度优先或广度优先遍历时的时间复杂度为O(n2);用邻接表作为图的存储结构进行深度优先或广度优先遍历的时间复杂度为O(n+e)。 9.设散列表的长度为8,散列函数H(k)=k%7,用线性探测法解决冲突,则根据一组初始关键字序列(8,15,16,22,30,32)构造出的散列表的平均查找长度是__8/3______。 10.设一组初始关键字序列为(38,65,97,76,13,27,10),则第3趟冒泡排序结束后的结果为_(38,13,27,10,65,76,97)。 11.设一组初始关键字序列为(38,65,97,76,13,27,10),则第3趟简单选择排序后的结果为_(10,13,27,76,65,97,38)__。 12.设有向图G中的有向边的集合E={<1,2>,<2,3>,<1,4>,<4,5>,<5,3>,<4,6>,<6,5>},则该图的一个拓扑序列为124653。 13.下面程序段的功能是建立二叉树的算法,请在下划线处填上正确的内容。 typedefstructnode{intdata;structnode*lchild;_structnode*rchild__;}bitree; voidcreatebitree(bitree*&bt) { scanf("%c”,&ch); if(ch=='#')__bt=0___;else {bt=(bitree*)malloc(sizeof(bitree));bt->data=ch; createbitree(bt->lchild);createbitree(bt->rchild);} } 14.下面程序段的功能是利用从尾部插入的方法建立单链表的算法,请在下划线处填上正确的内容。 typedefstructnode{intdata;structnode*next;}lklist; voidlklistcreate(__lklist___*&head) { for(i=1;i<=n;i++) { p=(lklist*)malloc(sizeof(lklist));scanf("%d”,&(p->data));p->next=0; if(i==1)head=q=p;else{q->next=p;q=p;} } } 二、算法设计 1.设计在链式存储结构上合并排序的算法。 voidmergelklist(lklist*ha,lklist*hb,lklist*&hc) { lklist*s=hc=0; while(ha! =0&&hb! =0) if(ha->data else{if(s==0)hc=s=hb;else{s->next=hb;s=hb;};hb=hb->next;} if(ha==0)s->next=hb;elses->next=ha; } 2.设计在二叉排序树上查找结点X的算法。 bitree*bstsearch1(bitree*t,intkey) { bitree*p=t; while(p! =0)if(p->key==key)return(p);elseif(p->key>key)p=p->lchild;elsep=p->rchild; return(0); } 3.设关键字序列(k1,k2,…,kn-1)是堆,设计算法将关键字序列(k1,k2,…,kn-1,x)调整为堆。 voidadjustheap(intr[],intn) { intj=n,i=j/2,temp=r[j-1]; while(i>=1)if(temp>=r[i-1])break;else{r[j-1]=r[i-1];j=i;i=i/2;} r[j-1]=temp; } 第六次
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构