厦门大学数据结构习题.docx
- 文档编号:8939247
- 上传时间:2023-05-16
- 格式:DOCX
- 页数:24
- 大小:44.53KB
厦门大学数据结构习题.docx
《厦门大学数据结构习题.docx》由会员分享,可在线阅读,更多相关《厦门大学数据结构习题.docx(24页珍藏版)》请在冰点文库上搜索。
厦门大学数据结构习题
作业:
1-1,7,82-1,2,4,7,9,11,13,193-2,3,7,8,13,14
4-3,9,135-1,2,6,85-1,2,6,7,8,12,14,17
习题1绪论
1-1名词解释:
数据结构。
数据结构:
相互之间存在一定关系的数据元素的集合
1-2数据结构的基本逻辑结构包括哪四种?
⑴集合:
数据元素之间就是“属于同一个集合”
⑵线性结构:
数据元素之间存在着一对一的线性关系
⑶树结构:
数据元素之间存在着一对多的层次关系
⑷图结构:
数据元素之间存在着多对多的任意关系
1-3数据结构一般研究的内容不包括()。
(A)集合的基本运算
(B)数据元素之间的逻辑关系
(C)在计算机中实现对数据元素的操作
(D)数据元素及其关系在计算机中的表示
选D
数据的逻辑结构、数据的存储结构、数据的运算
1-4算法包括哪五种特性?
2.算法的五大特性:
√
⑴输入:
一个算法有零个或多个输入。
⑵输出:
一个算法有一个或多个输出。
⑶有穷性:
一个算法必须总是在执行有穷步之后结束,且每一步都在有穷时间内完成。
⑷确定性:
算法中的每一条指令必须有确切的含义,对于相同的输入只能得到相同的输出。
⑸可行性:
算法描述的操作可以通过已经实现的基本操作执行有限次来实现。
1-5简述算法及其时间复杂度。
1.算法(Algorithm):
是对特定问题求解步骤的一种描述,是指令的有限序列。
算法复杂度(AlgorithmComplexity):
算法占用机器资源的多少,主要有算法运行所需的机器时间和所占用的存储空间。
时间复杂度(TimeComplexity):
算法运行所需要的执行时间,T(n)=O(f(n))。
空间复杂度(SpaceComplexity):
算法运行所需要的存储空间度量,S(n)=O(f(n))。
1-6设数组A中只存放正数和负数。
试设计算法,将A中的负数调整到前半区间,正数调整到后半区间。
分析算法的时间复杂度。
A[n+1]
For(inti=n-1,j=0;i>j;i--)
{
If(a[i]>0)continue;
Else{
A[n]=A[i];
A[i]=A[j];
A[j]=A[n];
J++;
}
}
时间复杂度为O(n)
1-7将上三角矩阵A=(aij)n⨯n的非0元素逐行存于B[(n*(n+1)/2]中,使得B[k]=aij且k=f1(i)+f2(j)+c(f1,f2不含常数项),试推导函数f1,f2和常数c。
1-8描述下列递归函数的功能。
intF(intm,intn)
{
if(n>m)returnF(n,m);
elseif(n==0)returnm;
else
{
r=m%n;
returnF(n,r);
}
}
求m与n的最大公约数
1-9编写递归算法:
0,m=0且n≥0
g(m,n)=
g(m-1,2n)+n,m>0且n≥0
1-10将下列递归过程改写为非递归过程。
voidtest(int&s)
{
intx;
scanf(“%d”,&x);
if(x==0)s=0;
else
{
test(s);
s+=x;
}
}
1-9(不考)
doubleg(doublem,doublen)
{
if(m==0&&n>=0)
return0;
else
returng(m-1,2*n)+n;
}
习题2表
2-1如果长度为n的线性表采用顺序存储结构存储,则在第i(1≤i≤n+1)个位置插入一个新元素的算法的时间复杂度为()。
(A)O
(1)(B)O(n)(C)O(nlog2n)(D)O(n2)
B
2-2在一个有127个元素的顺序表中插入一个新元素,要求保持顺序表元素的原有(相对)顺序不变,则平均要移动()个元素。
(A)7(B)32(C)64(D)127
Cn/2+1
2-3将关键字2,4,6,8,10,12,14,16依次存放于一维数组A[0...7]中,如果采用折半查找方法查找关键字,在等概率情况下查找成功时的平均查找长度为()。
(A)21/8(B)7/2(C)4(D)9/2
A
3,2,3,1,3,2,3,4
公式法
2-4已知顺序表L递增有序。
设计一个算法,将a和b插入L中,要求保持L递增有序且以较高的效率实现。
先用折半查找法查询位置,然后移动
voidinsert(intL[],inta,intb)//a
{
inti=0,p,q;
n=length(L);//L现有长度
//查找确定a、b的位置
for(;i { if(L[i]<=a&&(a { p=i+1;//a的最终位置 n++; break; } } for(;i { if(L[i]<=b&&(b { q=i+2;//b的最终位置 n++; break; } } //移动元素,插入a,b for(i=n+1;i>q;i--) L[i]=L[i-2]; L[q]=b;//插入b for(i=q-1;i>p;i--) L[i]=L[i-1]; L[p]=a;//插入a } 2-5简单描述静态查找和动态查找的区别。 静态查找 没有改变顺序表的查找。 动态查找表 可能需要在表中进行插入操作或删除操作的查找。 2-6综合比较顺序表和链表。 (1)存储空间利用率高——只存储元素值。 (2)随机存取——可以通过计算来确定顺序表中第i个数据元素的存储地址Li=L0+(i-1)*m,其中,L0为第一个数据元素的存储地址, m为每个数据元素所占用的存储单元数。 (3)插入和删除数据元素会引起大量结点移动. 顺序表: 内存中地址连续 长度不可变更 支持随机查找可以在O (1)内查找元素 适用于需要大量访问元素的而少量增添/删除元素的程序 链表: 内存中地址非连续 长度可以实时变化 不支持随机查找查找元素时间复杂度O(n) 适用于需要进行大量增添/删除元素操作而对访问元素无要求的程序 2-7解释链表的“头指针、头结点和首元素结点”三个概念。 “头指针”是指向头结点的指针。 "头结点"是为了操作的统一、方便而设立的,放在首元素结点之前,其数据域一般无意义(当然有些情况下也可存放链表的长度、用做监视哨等等)。 “首元结点”也就是第一元素结点,它是头结点后边的第一个结点。 2-8描述下列算法的主要功能是()。 ①构造头结点L,取q=L; ②产生1个结点p; ③q−>next=p; ④输入p−>data的值; ⑤取q=p; ⑥重复执行②至⑤n次; ⑦p−>next=NULL; (A)通过输入n个数据元素构建链表L (B)采用前插法,在链表L中输入n个数据元素 (C)通过产生n个结点构建链栈L,q为栈顶指针 (D)在链队列L中输入n个数据元素,q为队尾指针 A 2-9设L是不带头结点的单链表的头指针,k是一个正整数,则下列算法的主要功能是()。 LinkSearch(LinkListL,intk) { k0=0; p=L->next;//next为单链表的指针域 q=p; while(p) { if(k0<=k)k0++; elseq=q->next; p=p->next; } q->next=0; } (A)计算单链表L的长度 (B)查找单链表L中倒数第k个结点 (C)删除单链表L中最后面的k个结点 (D)将单链表L中第k个结点q的指针置0 只遍历一次的高效算法 (排除法) B 2-10设链表L不带头结点,试分析算法的功能。 A(Linklist&L) { if(L&&L->next) { Q=L; L=L->next; P=L; while(P->next)P=P->next; P->next=Q; Q->next=NULL; } }//A算法结束 2-11设两个循环链表的长度分别为n和m,则将这两个循环链表连接成一个循环链表,最好的时间复杂度为()。 (A)O (1)(B)O(n)(C)O(m)(D)O(min(n,m)) 2-12设有6个数据元素A,B,C,D,E,F依次进栈。 如果6个数据元素的出栈顺序为B,C,D,F,E,A,则该栈的最小容量为()。 (A)2(B)3(C)4(D)5 2-13设进栈序列为123,试给出所有可能的出栈序列。 2-14如果进栈序列为123456,能否得到出栈序列435612和135426? 2-15简述算法的功能(设数据元素类型为int): voidproc(LinkQueue*Q) { LinkStackS; InitStack(S); while(! EmptyQueue(Q)) { DeleteQueue(Q,d); Push(S,d); } while(! EmptyStack(S)) { Pop(S,d); InsertQueue(Q,d); } } 2-16按照格式要求给出调用F(3,'A','B','C')的运行结果: voidF(intn,charx,chary,charz) { if(n==1)printf("1%c→%c\n",x,z); else { F(n-1,x,z,y); printf("%d%c→%c\n",n,x,z); F(n-1,y,x,z); } } 2-17已知一维数组B[0..20]用于存储一个下三角矩阵A元素。 设A中第一个元素的下标为1,1,则数组元素B[10]对应A中下标为()的元素。 (A)2,5(B)4,3(C)5,1(D)6,1 2-18已知An⨯n为稀疏矩阵。 试从时间和空间角度比较,采用二维数组和三元组顺序表两种存储结构计算∑aij的优缺点。 2-19链地址法是Hash表的一种处理冲突的方法,它是将所有哈希地址相同的数据元素都存放在同一个链表中。 关于链地址法的叙述,不正确的是()。 (A)平均查找长度较短 (B)相关查找算法易于实现 (C)链表的个数不能少于数据元素的个数 (D)更适合于构造表前无法确定表长的情况 2-20设哈希(Hash)函数H(k)=(3k)%11,用线性探测再散列法处理冲突,di=i。 已知为关键字序列22,41,53,46,30,13,01,67构造哈希表如下: 哈希地址012345678910 关键字2241300153461367 则在等概率情况下查找成功时的平均查找长度是()。 (A)2(B)24/11(C)3(D)3.5 2-21有100个不同的关键字拟存放在哈希表L中。 处理冲突的方法为线性探测再散列法,其平均查找长度为。 试计算L的长度(一个素数),要求在等概率情况下,查找成功时的平均查找长度不超过3。 素数表: 101,103,107,109,113,127,131,137,139,149,151,157,163,167。 习题3树 3-1若深度为5的完全二叉树第5层有3个叶子结点,则该二叉树一共有()个结点。 (A)8(B)13(C)15(D)18 D 利用公式前四层有2^5-1=15个节点,总共为15+3=18个。 3-2设树T的度为4,其中度为1,2,3和4的结点个数分别为4,2,1,1则T中的叶子数为()。 (A)5(B)6(C)7(D)8 一共有1*4+2*2+3+4=15个度,4+2+1+1=8个节点 叶子为15-8+1=8 解析: 节点数=度数+1 此题也可用画图法(图略) 3-3已知二叉树T中有50个叶子结点,试计算T的总结点数的最小值。 由于是二叉树,那么可知欲使节点数最小,则该二叉树需满足至多存在一个结点的入度为1(即——使每两个结点都有一个父节点)。 50/2=25,(25-1)/2=1212/2=66/2=3(3+1)/2=22/2=1红色部分+1为之前25个结点归根时剩下的1个。 那么总共有50+25+12+6+3+2+1=99个结点 节点数/2+1=叶子数 3-4已知一棵度为k的树中,有n1个度为1的结点,n2个度为2的结点,…,nk个度为k的结点。 试计算该树的叶子结点数。 解析: 节点数=度数+1 叶子结点为 3-5对于任意非空二叉树,要设计出其后序遍历的非递归算法而不使用栈结构,最适合的方法是对该二叉树采用()存储结构。 (A)二叉链表(B)三叉链表(C)索引(D)顺序 B 解析: 三叉链表比二叉链表多一个指向父结点的指针 3-6一棵二叉树的叶子结点在其先序、中序和后序序列中的相对位置()。 (A)肯定发生变化(B)可能发生变化(C)不会发生变化(D)无法确定 B 解析: 举例子说明即可 3-7设二叉树T按照二叉链表存储,试分析下列递归算法的主要功能。 intF(BiTreeT) { if(! T)return0; if(! T->Lchild&&! T->Rchild)return1; returnF(T->Lchild)+F(T->Rchild); } 求二叉树T的叶子结点数 intF(BiTreeT) { if(! T)return0; if(! T->Lchild&&! T->Rchild)return1; returnF(T->Lchild)+F(T->Rchild)+1; } 求二叉树T的结点数 3-8已知二叉树T的先序序列为ABCDEF,中序序列为CBAEDF,则T的后序序列为()。 (A)CBEFDA(B)FEDCBA(C)CBEDFA(D)不确定 A 3-9简述由先序序列和中序序列构造二叉树的基本操作方法。 略 3-10已知二叉树的先序序列为ebadcfhgikj,中序序列为abcdefghijk,试画出该二叉树。 略 3-11已知二叉树T的中序序列和后序序列分别为 (中序)3,7,11,14,18,22,27,35 (后序)3,11,7,14,27,35,22,18 试画出二叉树T。 略 3-12已知二叉树T按照二叉链表存储,设计算法,计算T中叶子结点的数目。 intF(BiTreeT) { if(! T)return0; if(! T->Lchild&&! T->Rchild)return1; returnF(T->Lchild)+F(T->Rchild); } 3-13已知二叉树T按照二叉链表存储,设计算法,交换T的左子树和右子树。 递归: IntExchangeBTree(BiTreeT) { temp=(BiTree)malloc(sizeof(BiTNode)); if(! T)return; if(! T->lchild&&! T->rchild)return; temp=T->lchild; T->lchild=T->rchild; T->rchild=temp; ExchangeBTree(T->lchild); ExchangeBTree(T->rchild); } 3-14先序后继线索化算法是根据二叉链表建立先序后继线索二叉链表,其基本原则是在前驱空指针域中写入后继线索,即将右子树的()指针写入左子树的最后一个叶子结点右指针域。 (A)线索(B)根结点(C)前驱结点(D)后继结点 3-15设计算法,在先序线索二叉树中,查找给定结点p在先序序列中的后继。 线索二叉树: 根据某次遍历,在二叉树中的相关空指针域都写入线索(后继线索或前驱线索),即成为线索二叉树。 线索二叉树可理解为已经线索化的二叉树。 先序后继: 先序遍历中得到的后继(先序前驱,中序后继,中序前驱,后序后继,后序前驱)。 线索二叉树的存储结构 typedefstructNode{ Typedata;//数据元素域 structNode*Lchild;//左孩子域 structNode*Rchild;//右孩子域 intTag;//0: 分支结点,1: 叶子结点 }BiTNode,*BiTree; findBirthNode(BiTNodep) { If(p->tag==0)//p的左子树非空,指向左子树 Returnp->Lchild; Else//p为空,后驱则是右子树 Returnp->Rchild; } 3-16设计一种二进制编码,使传送数据a,act,case,cat,ease,sea,seat,state,tea的二进制编码长度最短。 要求描述: (1)数据对象;a,c,t,s,e (2)权值集;8,3,5,5,6 (3)哈夫曼树;略 (4)哈夫曼编码。 00,010,011,10,11 3-17按照“逐点插入方法”建立一个二叉排序树,树的形状取决于()。 (A)数据序列的存储结构(B)数据元素的输入次序 (C)序列中的数据元素的取值范围(D)使用的计算机的软、硬件条件 B 显然D错误,A也错误因为大小是相对的,对于C,1,3,5和1,10,100相对位置一样,假若插入次序也一样的话,树的形状也不会变得,所以选B 3-18用利用逐点插入法建立序列(50,72,43,85,75,20,35,45,65,30)对应的二叉排序树以后,查找元素35要在元素间进行()次比较。 (A)3(B)4(C)5(D)8 B 150 24372 320456585 43575 30 3-19在平衡二叉树中,插入关键字46后得到一颗新的平衡二叉树。 在新的平衡二叉树中,关键字37所在结点的左、右孩子结点中保存的关键字是()。 (A)18,46(B)25,46(C)25,53(D)25,69 C 3-20用依次插入关键字的方法,为序列{5,4,2,8,6,9}构造一棵平衡二叉树(要求分别画出构造过程中的各棵不平衡二叉树)。 每次都将平衡树平衡 3-21给定n个整数,设计算法实现: (1)构造一棵二叉排序树; (2)从小到大输出这n个数。 intSearchBST(BiTreeT,intkey,BiTree&p) { //在T中递归查找关键字值=key的数据元素 if(! T)return0;//查找不成功 if(key==T->key)return1;//查找成功 p=T;//p记录双亲结点 if(key returnSearchBST(T->rchild,key,p); }//SearchBST //二叉排序树的插入算法 voidInsertBST(BiTree&T,inta[n])//数组保存n个整数 { BiTreep=T;//p指向双亲结点 Inti; For(i=0;i { if(SearchBST(T->lchild,a[i],p))return0;//查找成功 BiTrees=(BiTree)malloc(sizeof(BiTnode));//申请结点 s->key=a[i]; s->lchild=s->rchild=NULL; if(! T->lchild)T->lchild=s;//s为根结点 elseif(a[i] elsep->rchild=s;//s为p的右孩子 } }//InsertBST //用中序遍历即可从大到小输出 习题4排序 ADDCCBBCD4-1在下列排序算法中,时间复杂度最好的是()。 (A)堆排序(B)插入排序(C)冒泡排序(D)选择排序 4-2如果顺序表中的大部分数据元素按关键字值递增有序,则采用()算法进行升序排序,比较次数最少。 (A)快速排序(B)归并排序(C)选择排序(D)插入排序 4-3对关键字序列56,23,78,92,88,67,19,34进行增量为3的一趟希尔排序(Shell升序或降序)的结果为()。 (A)19,23,78,56,34,67,92,88(B)23,56,78,67,88,92,19,34 (C)19,23,34,56,67,78,88,92(D)92,88,78,56,34,67,19,23 4-4若一组记录的关键码为46,79,56,38,40,84,则利用快速排序方法且以第一个记录为基准,得到的一次划分结果为()。 (A)38,40,46,56,79,84(B)40,38,46,79,56,84 (C)40,38,46,56,79,84(D)40,38,46,84,56,79 4-5对数据84,47,25,15,21进行排序。 如果前三趟的排序结果如下: 第1趟: 15,47,25,84,21 第2趟: 15,21,25,84,47 第3趟: 15,21,25,47,84 则采用的排序方法是()。 (A)冒泡排序(B)快速排序(C)选择排序(D)插入排序 4-6对数据36,12,57,86,9,25进行排序,如果前三趟的排序结果如下: 第1趟: 12,36,57,9,25,86 第2趟: 12,36,9,25,57,86 第3趟: 12,9,25,36,57,86 则采用的排序方法是()。 (A)希尔排序(B)起泡排序(C)归并排序(D)基数排序 B 4-7根
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 厦门大学 数据结构 习题