数据结构C++考试题及答案.docx
- 文档编号:1263087
- 上传时间:2023-04-30
- 格式:DOCX
- 页数:35
- 大小:121.03KB
数据结构C++考试题及答案.docx
《数据结构C++考试题及答案.docx》由会员分享,可在线阅读,更多相关《数据结构C++考试题及答案.docx(35页珍藏版)》请在冰点文库上搜索。
数据结构C++考试题及答案
数据结构试题一
一、单项选择题(每小题3分,共30分)
1、在有n个叶子结点的哈夫曼树中,其结点总数为()。
A、不确定B、2nC、2n+1D、2n-1
2、下列序列中,()是执行第一趟快速排序得到的序列(排序的关键字类型是字符串)。
A、[da,ax,eb,de,bb]ff[ha,gc]B、[cd,eb,ax,da]ff[ha,gc,bb]C、[gc,ax,eb,cd,bb]ff[da,ha]D、[ax,bb,cd,da]ff[eb,gc,ha]
3、若线性表最常用的操作是存取第i个元素及其前驱的值,则采用()存储方式节省时间。
A、单链表B、双链表C、单循环链表D、顺序表
4、下列排序算法中,时间复杂度不受数据初始状态影响,恒为O(nlogn)的是()。
A、堆排序B、冒泡排序C、直接选择排序D、快序排序
5、某二叉树的先序序列和后序序列正好相反,则该二叉树一定是()的二叉树。
A、空或只有一个结点B、高度等于其结点数
C、任意结点无左孩子D、任意结点无右孩子
6、下列排序算法中,某一趟结束后未必能选出一个元素放在其最终位置上的是()。
A、堆排序B、冒泡排序C、直接选择排序D、快序排序
7、快速排序算法在最好情况下的时间复杂度为()。
A、O(n)B、O(n2)C、O(nlogn)D、O(logn)
8、已知数据表A中每个元素距其最终位置不远,则采用()排序算法最省时间。
A、堆排序B、插入排序C、直接选择排序D、快序排序
9、带权有向图G用邻接矩阵A存储,则顶点i的入度为A中()。
A、第i行非∞的元素之和B、第i列非∞的元素之和
C、第i行非∞且非0的元素之和D、第i列非∞且非0的元素之和
10、在有n个结点且为完全二叉树的二叉排序树中查找一个键值,其平均比较次数的数量级为()。
A、O(n)B、O(n2)C、O(nlogn)D、O(logn)
二、判断题(认为对的在题后的括号内打“√”,错的打“ⅹ”,每小题1分,共10分)
1.对任意一个图,从它的某个顶点出发进行一次深度优先或广度优先搜索遍历可访问该图的每个顶点。
()
2.在索引顺序表上实现分快查找,在等概率查找情况下,其平均查找长度不仅与表的个数有关,而且与每一块中的元素个数有关。
()
3、只有在初始数据为逆序时,冒泡排序所执行的比较次数最多。
()
4、图G的最小生成树的代价一定小于其他生成树的代价。
()
5、已知一棵树的先序序列和后序序列,一定能构造出该树。
()
6、对一个堆按层次遍历,不一定能得到一个有序序列。
()
7、设与一棵树T所对应的二叉树为BT,则与T中的叶子结点所对应的BT中的结点也一定是叶子结点。
()
8、不管ADT栈是用数组实现,还是用链表的指针实现,POP(S)与Push(x,S)的耗时均为O(n)。
()
9、如果删除二叉排序树中一个结点,再按照二叉排序树的构造原则重新插入上去,一定能得到原来的二叉排序树。
()
10、快速排序是排序算法中最快的一种。
()
三、填空题(每小题2分,共20分)
1、在双向循环表中,在p所指的结点之后插入指针f所指的结点,其操作为:
_________=p;f→next=p→next;_____=f;p→next=f。
2、在有序表A[1…20]中,采用二分查找算法查找元素值等于A[12]的元素,所比较过的元素的下标依次为__________。
3、若某串的长度小于一个常数,则采用_________存储方式最节省空间。
4、在有n个顶点的有向图中,每个顶点的度最大可达_________。
5、已知二叉树中叶子数为50,仅有一个孩子的结点数为30,则总结点数为__________。
6、设键值序列为{K1,K2,…,Kn},用筛选法建堆则必须从第_______个元素开始筛选。
7、在二叉链表中判断某指针p所指结点为叶子结点的条件是_________。
8、直接选择排序算法在最好情况下所作的交换元素的次数为________。
9、有n个球队参加的足球联赛按主客场制进行比赛,共需进行_______比赛。
10、下列排序算法中,占用辅助空间最多的是_________(堆排序,希尔排序,快速排序,归并排序)。
四、简答题(每题10分,共60分)
1、在单链表、双链表和单循环链表中,若仅知道指针p指向某结点,不知道头指针,能否将结点p从相应的链表中删去?
若可以,其时间复杂度各为多少?
2、设有一组关键字(17,13,14,153,29,35)需插入到表长为12的散列表中,请回答以下问题:
(1)设计一个适合该散列表的散列函数。
(2)用设计的散列函数将上述关键字插入到散列表中,并用线性探测法解决冲突,画出其结构;并指出用线性探测法解决冲突时构造散列表的装填因子为多少?
3、对n个顶点的无向图和有向图,采用邻接矩阵和邻接表表示时,如何判别下列有关问
(1)图中有多少条边?
(2)任意两个顶点i和j是否有边相连?
(3)任意一个顶点的度是多少?
4、已知下面二叉排序树的各结点的值依次为1…9,请标出各结点的值。
5、具有3个结点的树和具有3个结点的二叉树,它们的所有不同形态有哪些?
6、分析以下程序段中语句x=x+y的执行次数。
x=0;y=0;
for(inti=1;i<=n;i++)
for(intj=1;j<=i;j++)
for(intk=1;k<=j;k++)
x=x+y;
五、算法设计题(每题15分,共30分)
说明:
可以使用任何高级程序设计语言或伪(类)程序设计语言。
1、假设以二叉链表作为二叉树存储结构,其类型定义如下:
typedefstructnode
{chardata;
structnode*lchild,*rchild;//左右孩子指针
}BinTNode,*BinTree;
写一函数,完成以下功能:
对二叉树中每个结点,如果其左孩子为空(右孩子不为空),则将其右孩子设置为左孩子。
2、试设计将数组A[0…n-1]中所有奇数移到所有偶数之前的算法。
要求不另增加存储空间且时间复杂度为O(n)。
数据结构试题1参考答案
一、1——5:
DADAB6——10:
CCBDD
二、1——5:
ⅹ√ⅹⅹ√6——10:
√ⅹⅹⅹⅹ
三、1、①f→prior,②p→next→prior2、1015123、顺序压缩4、2(n-1)5、1296、n/2的最小整数7、(p→lchild==NULL)&&(p→rchild==NULL)
8、09、n(n-1)10、归并排序
四、1、答案:
在单链表中不能删除,而在双链表和单循环链表中可以删除p结点。
双链表的删除时间复杂度为O
(1),单循环链表删除p结点的时间复杂度为O(n)。
2、答案:
(1)由于散列表的长度为12,则可选不超过表长的最大素数11作为除留余数法的模,则可得其散列函数为h(k)=k%11。
(2)若用线性探测法解决冲突,则可构造出散列表如下:
13
14
35
17
29
153
012345678910
11
此时,其装填因子为6/12=1/2,若用链式法解决冲突,则其散列表为:
3、答案:
(1)无向图的邻接矩阵所有数值之和除以2,为边数。
有向图邻接矩阵各行数值之和为总边数。
邻接表表示无向图内部顶点个数除以2,有向图内部顶点个数。
(2)无向图中I行和J列的交叉点的值是否为1。
有向图I行J列交叉点或I列和J行交叉点的值为1。
(3)无向图顶点的度为每一行的数值之和;有向图顶点度为该行和该列数值之和。
4答案:
5、答案:
具有3个结点的树的形态为:
三个结点的两种树形态,无左右之分。
具有3个结点的二叉树的形态为:
5种形态,有左右之分。
6:
答案:
五、1、答案:
voidexchange(BinTreeT)
{if(T)
{if(!
T→lchild&&T→rchild)
{T→lchild=T→rchild;
T→rchild=NULL;}
exchange(T→lchild);
exchange(T→rchild);}}
2、答案:
intoddbefore(A,n)//将数组A[0…n-1]中所有奇数移到所有偶数之前
intA[];
{intc,i,j;i=0;j=n-1;//初始化i、j
while(i {while((A[i]%2==1)&&(i i++; while((A[i]%2==0)&&(i j--; if(i A[i]=A[j];A[j]=c;i++; j--;}} return (1) }//oddbefore 数据结构试题2 一、单项选择题(每小题3分,共30分) 1、下列排序算法中,()排序在每趟结束后,不一定能选出一个元素放到其排好序的最终位置上。 A、选择B、冒泡C、归并D、堆 2、若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素,则采用()存储方式最节省运算时间。 A、单链表B、仅有头指针的单循环链表C、双链表D、仅有尾指针的单循环链表 3、串的长度是()。 A、串中不同字符的个数B、串中不同字母的个数 C、串中所含字符的个数且字符个数大于0D、串中所含字符的个数 4、有一个散列表,表长度m为100,采用除余法构造散列函数,即H(k)=k%P,(P小于等于m),为使散列函数有较好的性能,P的选择应是()。 A、99B、97C、91D、93 5、在包括n个键值的二叉排序树中查找一个键值,其平均比较的量级为()。 A、O(n)B、O(logn)C、O(nlogn)D、O(n) 6、对有14个元素的有序表A[1…14]作二分查找,查找A[4]时的被比较元素依次为()。 A、A[1],A[2],A[3],A[4]B、A[1],A[14],A[7],A[4] C、A[7],A[3],A[5],A[4]D、A[7],A[5],A[3],A[4] 7、具有65个结点的完全二叉树其深度为()。 A、8B、7C、6D、5 8、带权有向图G用邻接矩阵A存储,则顶点i的入度等于A中()。 A、第i行非无穷元素之和B、第i列非无穷元素之和 C、第i行非零且非无穷元素个数D、第i列非零且非无穷元素个数 9、队列操作的原则是()。 A、先进先出B、后进先出C、只能进行插入D、只能进行删除 10、若表R在排列前已按元素键值递增顺序排序,采用()的比较次数少。 A、直接插入排序B、快速排序C、归并排序D、选择排序 二、判断题(认为对的,在题后的括号内打“√”,错的打“ⅹ”,每小题1分,共10分)1、在栈空的情况下,不能做退栈运算,否则产生下溢。 () 2、在快速排序算法中,取待排序的n个记录中的第一个的键值为基准,将所有记录分为两组,读记录就排在这两组的中间,这也是该记录的最终位置。 () 3、在索引顺序表查找方法中,对索引顺序表可以使用顺序表查找方法,也可以使用二分查找方法。 () 4、设有键值序列(k1,k2,…,kn),当i>n/2时,任何一个序列(k1,k2,…,kn)一定是堆。 () 5、在向二叉排序树中插入一个新结点时,需要比较结点的次数可能大于此二叉树的高度h。 () 6、在一个有向图的邻接表或逆邻接表中,如果某个顶点的链表为空,则该顶点的度一定为零。 () 7、双循环链表中,任一结点的前驱指针均为不空。 () 8、线性表采用链式存储方式和顺序存储方式,执行插入、删除运算的算法时间复杂度都是O(n),因而两种存储方式的插入、删除运算所花费的时间相同。 () 9、如果有向图G=(V,E)的拓扑序列不唯一,则图中必有两条弧 () 10、矩阵压缩存储的方法是用三元组表存储矩阵元素。 () 三、填空题(每小题2分,共20分) 1、设sq[1…maxsize]为一个顺序存储的栈,变量top指示栈顶元素的位置。 作进栈操作时,必须判别____。 如要把栈顶元素取到x中,需执行语句_____。 2、设一个二叉树共有50个叶结点(终端结点),则共有_______个度为2的结点。 3、在单链表中,若要在指针p所指结点(data,next)后插入指针s所指结点,则需要执行下列两条语句: s→next=p→next;_________。 4、3个结点可构成_________棵不同形状的树。 5、利用直接选择排序算法对n个记录进行排序,最坏情况下,记录交换的次数为_______ 6、如果含n个顶点的图是一个环,则它有_________棵生成树。 7、如果要将序列{50,16,23,68,94,70,73}建成堆,则只需把16与______相互交换即可。 8、在一棵高度为h的平衡二叉树中,最少含有_________个结点,最多含有2h-1个结点。 9、假设一个9阶的上三角矩阵A按列优先顺序压缩存储在一维数组B中,其中B[0]存储矩阵中第1个元素a11,则B[31]中存放的元素是___________。 10、在单链表上难以实现的排序方法有___________和堆排序。 四、简答题(每题10分,共60分) 1、在单链表、双链表和单循环链表中,若仅知道指针p指向某结点,不知道头指针,能否将结点p从相应的链表中删去? 若可以,其时间复杂度各为多少? 2、一项工程由P1、P2、…、P6六项子工程组成,这些工程之间有下列关系: P1 请给出工程P的三种可能的施工顺序。 3、设散列表长度为14,散列函数H(x)=∟2/i」,其中i为键值中第一个字母在字母表中的序号,若键值的输入顺序为Jan,Feb,Mar,Apr,May,Jun,Jul,Aug,Sep,Oct,Nov,Dec,用拉链法处理冲突,要求: (1)构造散列表。 (2)求出在等概率情况下,查找成功的平均查找长度。 4、设下图所示的二叉树是由森林转化而成的,试将它还原为森林。 5、何为队列的“假溢出”现象? 如何解决? 6、分析以下程序段中语句x=x+y的执行次数。 x=0;y=0; for(inti=1;i<=n;i++) for(intj=1;j<=i;j++) for(intk=1;k<=j;k++) x=x+y; 五、算法设计题(每题15分,共30分) 说明: 可以使用任何高级程序设计语言或伪(类)程序设计语言。 1、设计一个算法,求出指定结点在给定的二叉排序树中所在的层次。 2、已知线性表的元素按递增顺序排列,并以带头结点的单链表作存储结构。 试编写一个删除表中所有值大于min且小于max的元素(若表中存在这样的元素)的算法。 数据结构试题2答案 一、1——5: CDDBB6——10: CBDAA 二、1——5: √√√ⅹⅹ6——10: ⅹ√ⅹⅹⅹ 三、1、①栈是否满(或top=maxsize)②x=sq[top]2、493、p→next=s; 4、25、n-16、n7、508、h9、A8210、快速排序 四、1、答案: 在单链表中不能删除,而在双链表和单循环链表中可以删除p结点。 双链表的删除时间复杂度为O (1),单循环链表删除p结点的时间复杂度为O(n)。 2、答案: 可给出有向图表示各子工程间的关系按照入度为零的结点先访问的原则,访问各个结点即可。 找出3个可能的施工顺序如下: P1,P2,P3,P4,P5,P6 P1,P4,P2,P3,P5,P6 P4,P5,P1,P2,P3,P6 3、答案: (1): (2)ASL=(1*7+2*4+3*1)/12=5。 4、答案: 5、答案: 队列的“假溢出”现象是指用数组实现的顺序队列中,对尾指针已达到数组的下标上界产生上溢而对头指针之前还有若干空间闲置的现象。 解决的办法之一是利用循环队列技术使数组空间首尾相连。 6、答案: 五、1、答案: intlevel(t,p); bitree*t,*p; {intcount; count=0; if(t==NULL) return(0); else{count=count+1;while(t→data! =p→data){ if(t→data t=t→rchild; else t=t→lchild; count=count+1;}} return(count); } 2、答案: delete(head,max,min)//删除有序单链表中所有值大于min且小于max的元素linklist*head; intmax,min; {linklist*p,*q; if(head! =NULL) {q=head; p=head→next;} while((p! =NULL)&&(p→data p=p→next; q→next=p;} 数据结构试题3 一、单项选择题(每小题3分,共30分) 1、假设有n个关键字,它们具有相同的Hash函数值,用线性探测法把这n个关键字存入到Hash地址空间中要做()次探测。 A、n2B、n(n+1)C、n(n+1)/2D、n(n-1)/2 2、若有一个栈的输入序列是1,2,3,…,n输出序列的第一个元素是n,则第i个输出元素是()。 A、n-iB、n-i-1C、n-i+1D、不确定 3、在一棵度为3的树中,度为3的结点数为2个,度为2的结点数为1个,度为1的结点树为2个,那么度为0的结点数为()。 A、4B、5C、6D、7 4、在一个具有n个结点的无向完全图中,包含有()条边。 A、n(n-1)/2B、n(n-1)C、n(n+1)/2D、n2 5、已知一个有序表为(13,18,24,35,47,50,62,83,90,115,134),当二分检索值为90的元素时,需()次比较可检索成功。 A、1B、2C、3D、4 6、在所有排序方法中,关键字的比较次数与记录的初始排序无关的是()。 A、Shell排序B、冒泡排序C、直接插入排序D、直接选择排序 7、已知8个元素(34,76,45,18,36,54,92,65),按照依次插入结点的方法生成一棵二叉排序树,该树的深度为()。 A、4B、5C、6D、7 8、设有一个10阶的对称矩阵A,采用压缩存储方式以行序为主存储,a00为第一个元素,其存储地址为0,每个元素占有1个存储地址空间,则a85的地址为()。 A、13B、33C、17D、32 9、设关键字序列为: 3,7,6,9,8,1,4,5,2。 进行排序的最小交换次数为()。 A、6B、7C、8D、20 10、给定权的集合{15,3,14,2,6,9,16,17},所构造出的哈夫曼树的带 权路径长度为()。 A、129B、219C、189D、229 二、判断题(认为对的,在题后的括号内打“√”,错的打“ⅹ”,每小题1分,共10分) 1、在单链表中任何两个元素的存储位置之间都有固定的联系,因为可以从头结点进行查找任何一个元素。 () 2、若一个叶子结点是某子树的中序遍历序列的最后一个结点,则它必是该子树的先序遍历中的最后一个结点。 () 3、用相邻矩阵法存储一个图时,不在考虑压缩存储的情况下,所占用的存储空间大小与图中结点的个数有关,而与图的边数无关。 () 4、哈希表的查找效率主要取决于哈希建表时所选取的哈希函数和处理冲突 的方法两个方面。 () 5、因为算法和程序没有区别,所以在数据结构中二者是通用的。 () 6、进栈操作push(x,s)作用于链接栈时,无须判满。 () 7、稳定排序算法是最好的。 () 8、二叉搜索树的左、右子树都是二叉搜索树。 () 9、先序遍历一棵二叉搜索树所得的结点访问序列不可能是键值递增序列。 () 10、表中的每一个元素都有一个前驱和后继元素。 () 三、填空题(每小题2分,共20分) 1、在散列表(Hash)查找中,评判一个散列函数优劣的两个主要条件是_______和________。 2、设根结点处在第一层,那么具有n个结点的完全二叉树,其高度为_____。 3、快速排序方法的最坏时间复杂度为______,平均时间复杂度为___。 4、给定表(55,63,44,38,75,80,31,56),用筛选法建立初始堆,则初始堆表为_________。 5、设图G的顶点数为n,边数为e,各顶点的度数为D(Vi),则e=________。 6、将5个不同的数据进行排序,至少需要比较_____次,至多需要比较_______次。 7、二分折半查找的查找速度一般比顺序查找的速度快,设有100个元素,用二分折半查找时,最大比较次数是____,最小比较次数是_____。 8、由a,b,c3个结点构成的二叉树,共有_________种不同的结构。 9、在一棵高度为h的平衡二叉树中,至少含有________个结点,最多含有2h-1个结点。 10、在一个单链表中删除*p结点,应执行如下操作: q=p→next; p→data=p→next→data; p→next=________; free(q); 四、简答题(每题10分,共60分) 1、在单链表、双链表和单循环链表中,若仅知道指针p指向某结点,不知道头指针,能否将结点p从相应的链表中删去? 若可以,其时间复杂度各为多少? 2、假设用于通讯的电文仅有8个字母组成,字母在电文中出现的频率分别为: 7,19,2,6,32,3,21,10。 试用这8个频率值构造哈夫曼树,并画出该哈夫曼所对应的森林。 3、已知一个长度为12的表(Jan,Feb,Mar,Apr,May,June,July
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 C+ 考试题 答案