数据结构期末考试题总.pdf
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_05.gif)
《数据结构期末考试题总.pdf》由会员分享,可在线阅读,更多相关《数据结构期末考试题总.pdf(40页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、一、判断题1、栈是限定仅在表尾进行插入和删除操作的线性表。(J)2、引入循环队列的目的是为了克服假溢出时大量移动数据元素。(J )3、区分循环队列的满与空,有牺牲一个存储单元和设标记两种方法。(J)4、若一个栈的输入序列为1,2,3,则3,1,2是不可能的栈输出序列。35、表达式求值是队列应用的 个典型例子。(X)6、任何一个递归过程都可以转换成非递归过程。(J )7,循环队列也存在空间溢出问题。(J)8、栈和队列都是线性表,只是在插入和删除时受到了一些限制。(V)9、K MP算法的特点是在模式匹配时指示主串的指针不会变小。3)1 0、串是一种数据对象和操作都特殊的线性表。(V)1 1、对称矩
2、阵压缩存储后不会失去随机存取功能。(J)1 2、数组可看成线性结构的一种推广,可以对它进行插入,删除等操作。(X)1 3、一个稀疏矩阵Am Xn采用三元组形式表示,若把三元组中有关行下标与列卜标的值互换,并把m 和n的值互换,则完成了 Am Xn的转置运算。(X)1 4、二维以上的数组其实是一种特殊的广义表。1 5、广义表的取表尾运算,其结果通常是个表,但有时也可是个单元素值。(X)1 6、若一个广义表的表头为空表,则此广义表亦为空表。(X)1 7、广义表中的元素或者是一个不可分割的原子,或者是一个非空的广义表。(X)1 8、所谓取广义表的表尾就是返回广义表中最后一个元素。(X)1 9、广义表
3、的同级元素具有线性关系。(V)2 0、一个广义表可以为其它广义表所共享。(-J)2 1、压缩存储的三角矩阵和对称矩阵的存储空间相同。()解答:压缩存储的三角矩阵比压缩存储的对称矩阵多一个存储空间,用来存储常量c。答案:X2 2、广义表中的数据元素类型可以不相同。()解答:广义表的不同元素可以有不同的结构,即数据元素类型可以不相同。答案:J2 3、广义表的元素不可以是广义表。()解答:广义表的元素可以是子表,子表的元素还可以是子表,即广义表是一个多层次的结构。答案:X2 4、两个稀疏矩阵的和仍为稀疏矩阵。()解答:两个稀疏矩阵的和不一定是稀疏矩阵。例如,当两个稀疏矩阵和的非0元个数等于这两个稀疏
4、矩阵非 0 元个数之和时,这两个矩阵的和不一定是稀疏矩阵。答案:X2 5、数组用顺序存储方式存储时;存取每个元素的时间相同。()解答:数组用顺序存储方式存储时,只要知道起始结点的存放地址(即基地址)、维数和每维的上、下界,以及每个数组元素所占用的字节数,就可以将数组元素的存放地址表示为其下标的线性函数。因此,数组中的任一元素可以在相同的时间内存取,即顺序存储的数组是一个随机存取结构。答案:V2 6、队列这种结构是不允许在中间插入和删除数据的。()解答:队列也是一种特殊的线性表,它只允许在端进行插入操作,在另一端进行删除操作,不允许在中间插入和删除数据。答案:J2 7、循环队列只能用顺序表实现。
5、()解答:使用循环队列的目的是解决顺序队列的假溢出现象,所以循环队列只能用顺序表实现。答案:,2 8、顺序栈的“栈满”与“上溢”是没区别的,“栈空”与“下溢”是有区别的。()解答:栈满时若有元素入栈,将产生上溢。栈空时若进行出栈操作,将产生下溢。由此可知,“栈满”与“上溢”有区别的,“栈空”与“下溢”也有区别。答案:X2 9、顺序队列的“假溢出”现象是可以解决的。()解答:顺序队列的“假溢出”现象可以利用循环队列或通过移动元素的方式解决。答案:V3 0、空串与空格串是一样的。()解答:空串中没有字符,其长度为0;空格串中含有空格字符,其长度为空格的个数。答案:X3 1.单链表中指针p 所指向结
6、点存在后继结点的条件是p!=N U L L.X3 2、双循环链表从任何结点出发可以访问该结点的直接前驱和直接后继。,3 3、队列是特殊的线性表,在队列的两端可以进行同样的操作。X3 4、双向循环链表从任意结点出发可以访问链表中的任意结点。43 5、头指针一定要指向头结点。()解答:若链表有头结点,则头指针指向头结点;若链表没有头结点,则头指针指向第一个结点(链表不空),或指向空(链表为空)。答案:X3 6、链表中结点数据域占的存储空间越多,存储密度越大。J3 7、栈是线性表,线性表的所有操作均适用于栈。x3 8、一个三维数组可以看作为是数组元素为二维数组的线性表。J3 9、广义表中的数据元素类
7、型可以不相同。M4 0、串是一种数据对象和操作都特殊的线性表。V4 1、两个稀疏矩阵的和仍为稀疏矩阵。x4 2、串中任意个字符组成的子序列称为该串的子串。x4 3、压缩存储的三角矩阵和对称矩阵的存储空间相同。X4 4、如果两个串含有相同的字符,则这两个串相等。x4 5、数组不适合作为任何二叉树的存储结构。x4 6、在前序遍历二叉树的序列中,任何结点的子树的所有结点都直接跟在该结点之后、Y4 7、若一个树叶是某子树的中序遍历序列中的最后一个结点,则它必是该子树的前序遍历序列中的最后一个结点。V4 8、已知一棵二叉树的前序遍历和后序遍历序列并不能唯一地确定这棵二叉树。M4 9、二叉树用链式存储时,
8、空链域数多于非空链域数。M5 0、K MP算法的特点是在模式匹配时指示主串的指针不会回溯。5 1、后序遍历一棵二叉树等于中序遍历其对应的树。x5 2、满二叉树是完全二叉树。M5 3、单循环链表从任何结点出发可以访问链表中的任何结点()。解答:将单链表中最后一个结点的指针域由空改为指向头结点,这样的单链表称为单向循环链表。即单向循环链表是,个指向后继有向环,从任意结点出发可以访问链表中的任意结点。答案:V5 4、用顺序表存储线性表时,不需要另外开辟空间保存数据元素之间的相互关系。V55双循环链表从任意结点出发可以访问该结点的直接前驱和直接后继()。解答:将双链表的最后一个结点的后继指针域的值由空
9、改为指向头结点,头结点中的前驱指针域的值由空改为指向尾结点,这样的双向链表称为双向循环链表。即双向循环链表是两个有向环,个是指向后继有向环,另一个是指向前驱的有向环。从任意结点出发都可以访问该结点的直接前驱和直接后继。答案:456、稀疏矩阵压缩存储后,必会失去随机存取功能。457、链表中结点数据域占的存储空间越多,存储密度越大()。解答:存储密度=(结点数据本身所占的存储量)/(结点结构所占的存储总量)由此可知,链表中结点数据域占的存储空间越多,存储密度越大。答案:V58、顺序队列和循环队列的队满和队空的判断条件是一样的。x59、带头结点和不带头结点的单链表在查找、删除、求长度等操作上无区别(
10、)。解答:头结点是为了操作的统一、方便而设立的,放在第一元素结点之前,其数据域一般无意义(当然有些情况卜.也可存放链表的长度、用做监视哨等等),有头结点后,对在第一元素结点前插入结点和删除第一结点,其操作与对其它结点的操作统一了。而且无论链表是否为空,头指针均不为空。答案:X60、数据的存储结构是数据的逻辑结构的存储映像,不仅要存储数据元素的值,还要存储元素之间的相互关系。461、单链表中指针p 所指向结点存在后继结点的条件是p!=NULL解答:单链表中指针p 所指向结点存在后继结点的条件是p-next!=NULLo答案:X62、线性表中每个结点都有前驱和后继()。解答:线性表中,第一个结点没
11、有前驱,最后一个节点没有后继。答案:X63、广义表的元素不可以是广义表。X64、头结点就是链表中的第I 个结点。()解答:头结点是为了操作的统一、方便而设立的,放在第一元素结点之前,其数据域一般无意义(当然有些情况卜.也可存放链表的长度、用做监视哨等等),有头结点后,对在第一元素结点前插入结点和删除第一结点,其操作与对其它结点的操作统一了。首元结点也就是第一元素结点,它是头结点后边的第一个结点。答案:X65、线性表中每个结点都有前驱和后继。x66、顺序表可能对存储其中的数据进行排序操作,链表也能进行排序操作。()解答:可以插入和删除操作对链表进行排序。答案:J67、消除递归不一定需要使用栈。X
12、二、单选题1、k=l;fbr(i=0;i n;i+)fbr(j=0;jn;j+)上述程序段的时间复杂度为()。A)O(n2)B)O(n)C)O(2n)D)O(l)2、下面哪一个不是线性表的特性()除最后一个元素外,每个元素都有后继。除第一个元素外,每个元素都有前驱。线性表的长度为n.n邦。线性表是有限序列。3、与线性表的顺序存储不相符的特性是()。A)插入和掰除操作加活B)需要连续存储空间C)便于随机访问D)存储密度大4、下面哪一个不是顺序表的特点()。A)逻辑上相邻的元素,存储在计算机中相邻的存储空间B)在顺序表中查找一个元素与表中元素的分布没有关系C)用动态一维数组存储顺序表最合适D)插入
13、一个元素,平均要移动表长一半的数据元素5、与线性表的链接存储不相符合的特性是()。A)便于插入、删除运算 B)存储空间动态分配C)“此主也的存储空间 D)只能顺序查找6、若线性表采用链式存储,则表中各元素的存储地址A)必须是连续的 B)部分地址必须是连续的C)一定不是连续的D)可以连城也可以不连续7、链表不具有的特点是()可以随机访问任何一个元素插入和删除元素不需要移动元素不必事先估计存储空间所需存储空间与链表长度成正比8、某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素,则采用以下哪种存储方式最节省操作时间()。A)单链表B)仅有头指针的单循环链表C)双链表D)仅 彳j
14、头 指 针 的 双 /next=p-next;p-next=s;p-next=s-next;s-next=p;(3)q-next=s;s-next=p;p-next=s;s-next=q11、链表不具有的特点是()A.插入、删除操作不需要移动元素 B.可随机访问任一元索C.不必事先估计存储空间 D.所需空间与线性长度成正比12、对于一个线性表,若要求既能够进行较快地插入和删除,又能够反映出数据元素之间的关系,则应该(A.以顺序方式存储 B.以链接方式存储C.以散列方式存储 D.以索引方式存储13、在一个单链表中,已知q所指向的结点是p所指向结点的前驱结点,若在q和p之间插入s所指向的结点,则执
15、行()。s-next=p-next;p-next=s;p-next=s-next;s-next=p;q-next=s;s-next=p;p-next=s;s-next=q14、在线性表的卜列存储结构中,读取元素花费时间最少的是().单链表 双链表 循环链表 顺序表解答:顺序表是随机存取,时间复杂度为0(1),链表是顺序存取,时间复杂度为0(n)。答案:15、在单链表上插入一个数据结点的平均时间复杂性为()o 0 0(n)0(logm)0(n2)解答:在单链表上插入个数据结点,时间耗费主要是在杳找插入位置上。在长度为n的单链表的第/个结点后插入一个数据元素时,平均查找次数为:1 .1 +1)/?
16、+1 ,=x-=-2 2时间复杂度为0(n)。答案:16、在顺序表上删除一个数据结点的平均时间复杂性为().0 (n)。(logs)0(n2)解答:在顺序表上删除一个数据结点,时间耗费主要是在数据移动操作匕 在长度为n的顺序表中删除一个数据元素时所需移动的数据元素的平均次数为:金 占 n 2 2平均时间复杂度为0(n)。答案:17、非空双循环链表中,在q所指向的结点前插入一个由p所指向结点的过程依次为()。A)p-next=q;p-prior=q-prior;q-prior=p;q-next=p;B)p-next=q;p-prior=q-prior;q-prior=p;q-prior-next
17、=p;C)p-ncxt=q;p-prior=q-prior;q-prior=p;p-prior-ncxt=p;D)p-next=q;p-prior=q-prior;q-prior=p;p-next-prior=p;18、若进栈序列为1,2,3,4,则不可能得到的出栈序列是A)3,2,l,4 B)3,2,4,l C)4,2,3.1 D)2,3,4,l19、在一个具有n个单元的顺序栈中,假定以地址低端作为栈底,以top作为栈顶指针,则当作退栈处理时,top变化为()top 不变top+=n top top+20、设输入序列为1,2,3,4,借助一个栈可以得到的输出序列是()。1,3,4,2 3,1
18、,4,24,3,1,2 4,1,2,321、若进队序列为1,2,3,则出队序列是()。A)3,2,l B)l,2,3 C)1,3,2 D)3,2,l22、栈和队列都是()。A)顺序存储的线性结构B)限制存取小的线忤结构C)链接存储的线性结构D)限制存取点的非线性结构23、栈和队列都是()顺序存储的线性表链式存储的线性表限制插入、删除位置的线性表限制插入、删除操作位置的非线性结构24、若循环队列的队头指针为fro n t,队尾指针为re a r,则队长的计算公式为()。(rcar+M-front)%MA)rear-front B)front-rear C)rear-front+l D)都不 i:
19、确25、在具有n个单元的顺序存储的循环队列中,假定front和rear分别为队首指针和队尾指针,则判断队列为空的条件是()。A)front=rear+l B)front+1=rear C)front:-rear D)front=026、在一个链队列中,假定front和rear分别为队首指针和队尾指针,则进行插入s所指向结点的操作是()front-next=s;front=s;front=front-next;rear-next=s;rear=s;front=rear-next;27、串 是()一些符号构成的序列一些字母构成的序列一个以上的字符构成的序列任意有限个字符构成的序列28、若将n阶对称
20、矩阵A的 卜三角部分以行序为主序压缩存储到一维数组B中,A的卜标卜.界为0,B的下标下界为1。那么,A中的任一下三角元素aij在矩阵B中的位置为A)i(i+l)/2+j A)i(i+l)/2+j-l C)i(i H)/2+j 1 D)j(j+l)/2+i29、数组A1010的下标下界为1,每个元素占3个字节,存储在起始地址为100的连续内存单元,则元素 A54的地址为().=100+(4*10+3)*3=229 215 270 262 22930、将8阶对称矩阵A的卜三角部分逐行地存储到起始地址为1()0的内存单元中,已知每个元素占4个字节,下标下界都为 0,则 A74的 地 址 为i=j,i
21、*(i+l)/2+j=32 地址=100+32*4=228A)35B)36C)340D)22831、将一个100阶的对称矩阵A按行优先压缩存入一维数组B中,下标的下界都为0,则A中的元素A6564在数组B中的位置为()。A)2194B)2195C)2209D)219732、对稀疏矩阵进行压缩存储的目的是A)便于进行矩阵运算B)便了输入和输出C)省作储)旧D)降低运算的时间复杂度33、下面说法不正确的是()。A)广义点的衣头怠工一个广义之B)广义表的表尾总是一个广义表C)广义表难以用顺序存储结构D)广义表可以是个多层次的结构34、对广义表 A=(x,(a,b),c,d)做运算 head(head
22、(tail(A)后的结果为().A)xB)(a.b)C)aD)c35、广义表(),()的深度为()。A)0 B)1 C)2 D)336、L!知广义表L=(x,y,z),a,(u,t,w),则从L中取出原子项t的操作是()。i hcad(tail(hcad(tail(tail(L)head(head(tail(tail(tail(L)head(tail(tail(tail(taiI(L)head(lail(tail(head(tail(L)37、在树的双亲表示法中对树按层次编号,用数组进行存储,则下面说法不正确的是()。A)兄结点的下标值小于弟结点的下标值B)所有结点的双亲均可以找到。任意结点的
23、孩子信息可以找到D)下标值为i和i+l的结点的关系足孩广和双亲38、有100个结点的完全二叉树由根开始从上到下从左到右对结点进行编号,根结点的编号为1,编号为4 3的 结 点 的 左 孩 子 的 编 号 为 性质5A)50B)48C)98D)8639、在深度为6的完全二叉树中()。最少2 1 1+1,最多211A)最少有31个结点,最多有64个结点B)最少有32结点,最多有6 4个结点C)最少有3 1个结点,最多有63结点D)最少/32 m,最多仃6 3”,也40、假定在一棵二叉树中,度为2的结点数为1 5,度为1的结点数为3 2,则叶子结点个数为()。n0=n2+l性质3A)15B)16C)
24、17D)1841、已知完全二叉树有8 0个结点,则整个二叉树有()个度为1的结点。性质6A)0 B)l C)2 D)不确定42、n个结点的二叉树,若用二叉链表作为存储结构,则非空闲的左、右孩子链域为A)nB)2n C)n-1 D)n+143、假定在一棵二叉树中,度为2的结点数为15个,度为1的结点数为32个,则叶子结点个数为()。A)18 B)17C)16 D)1544、对一棵有n个结点的树,则该树中的度之和为()n n-ln+1 不确定45、在二叉树的先序遍历中,任意一个结点均处在其子孙前面()。根左右A)小:确B)不正确C)有时正确D)不定46、若二叉树的先序遍历序列和后序遍历序列正好相同
25、,则一定是一棵()二叉树不多于一个结点的二叉树结点个数可能大于1且各结点均无左孩子结点个数可能大于1且各结点均无右孩子其中任意个结点的度不为2的47、若一个栈的输出序列的第一个元素是i,则第j个输出元素是()。A.i-j+1 B.i-j C.j-i+1 D.不确定的解析:对输入序列为1,2,3,n,若第一个输出的元素是n,即i=n,则第j个输出的元素是n-j+1,否则不能确定其他元素的输出顺序。例如:输入序列为1 2 3,若第一输出元素是1,则可能的输出序列有123和132。答案:D48、若栈采用顺序存储方式存储,现 两 栈 共 享 空 间topi代表第i个栈(i=l,2)栈顶,栈1的底在v
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 期末 考试题
![提示](https://www.taowenge.com/images/bang_tan.gif)
限制150内