数据结构模拟题.docx

《数据结构模拟题.docx》由会员分享，可在线阅读，更多相关《数据结构模拟题.docx（22页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构模拟题1.在数据结构中，从逻辑上可以把数据结构分成（）。 A动态结构和静态结构B紧凑结构和非紧凑结构C线性结构和非线性结构(正确答案)D内部结构和外部结构2.与数据元素本身的形式、内容、相对位置、个数无关的是数据的（）。 A存储结构B存储实现C逻辑结构(正确答案)D运算实现3.通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着（）。 A数据具有同一特点B不仅数据元素所包含的数据项的个数要相同，而且对应数据项的类型要一致(正确答案)C每个数据元素都一样D数据元素所包含的数据项的个数要相等4.以下说法正确的是（）。 A数据元素是数据的最小单位B数据项是数据的基本单位C数据结构是带

2、有结构的各数据项的集合D一些表面上很不相同的数据可以有相同的逻辑结构(正确答案)答案解析：数据元素是数据的基本单位，数据项是数据的最小单位，数据结构是带有结构的各数据元素的集合。5.算法的时间复杂度取决于（）。 A问题的规模B待处理数据的初态C计算机的配置DA和B(正确答案)答案解析：算法的时间复杂度不仅与问题的规模有关，还与问题的其他因素有关。如某些排序的算法，其执行时间与待排序记录的初始状态有关。为此，有时会对算法有最好、最坏以及平均时间复杂度的评价。6.以下数据结构中，（）是非线性数据结构 A树(正确答案)B字符串C队列D栈7.顺序表中第一个元素的存储地址是100，每个元素的长度为2，则

3、第5个元素的地址是（）。 A110B108(正确答案)C100D120答案解析：顺序表中的数据连续存储，所以第5个元素的地址为:100+24=108。8.在n个结点的顺序表中，算法的时间复杂度是O(1)的操作是（）。 A访问第i个结点（1in）和求第i个结点的直接前驱（2in）(正确答案)B在第i个结点后插入一个新结点（1in）C删除第i个结点（1in）D将n个结点从小到大排序答案解析：在顺序表中插入一个结点的时间复杂度都是O(n2)，排序的时间复杂度为O(n2)或O(nlog2n)。顺序表是一种随机存取结构，访问第i个结点和求第i个结点的直接前驱都可以直接通过数组的下标直接定位，时间复杂度是

4、O(1)。9.向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动 的元素个数为（）。 A8B63.5(正确答案)C63D7答案解析：平均要移动的元素个数为:n/2。10.链接存储的存储结构所占存储空间（）。 A分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针(正确答案)B只有一部分，存放结点值C只有一部分，存储表示结点间关系的指针D分两部分，一部分存放结点值，另一部分存放结点所占单元数11.线性表若采用链式存储结构时，要求内存中可用存储单元的地址（）。 A必须是连续的B部分地址必须是连续的C一定是不连续的D连续或不连续都可以(正确答案)12.线性表L在（）情

5、况下适用于使用链式结构实现。 A需经常修改L中的结点值B需不断对L进行删除插入(正确答案)CL中含有大量的结点DL中结点结构复杂答案解析：链表最大的优点在于插入和删除时不需要移动数据，直接修改指针即可。13.单链表的存储密度（）。 A大于1B等于1C小于1(正确答案)D不能确定答案解析：存储密度是指一个结点数据本身所占的存储空间和整个结点所占的存储空间之比，假设单链表一个结点本身所占的空间为D，指针域所占的空间为N，则存储密度为:D/(D+N)，一定小于1。14.将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是（）。 An(正确答案)B2n-1C2nDn-1答案解析：当第一个有序

6、表中所有的元素都小于（或大于）第二个表中的元素，只需要用第二个表中的第一个元素依次与第一个表的元素比较，总计比较n次。15.在一个长度为n的顺序表中，在第i个元素（1in+1）之前插入一个新元素时须向后移动（）个元素。 An-iBn-i+1(正确答案)Cn-i-1DI16.线性表L=(a1，a2,an)，下列说法正确的是（）。 A每个元素都有一个直接前驱和一个直接后继B线性表中至少有一个元素C表中诸元素的排列必须是由小到大或由大到小D除第一个和最后一个元素外，其余每个元素都有一个且仅有一个直接前驱和直接后继。(正确答案)16.创建一个包括n个结点的有序单链表的时间复杂度是（）。 AO(1)BO

7、(n)CO(n2)(正确答案)DO(nlog2n)答案解析：单链表创建的时间复杂度是O(n)，而要建立一个有序的单链表，则每生成一个新结点时需要和已有的结点进行比较，确定合适的插入位置，所以时间复杂度是O(n2)。17.以下说法错误的是（）。 A求表长、定位这两种运算在采用顺序存储结构时实现的效率不比采用链式存储结构时实现的效率低B顺序存储的线性表可以随机存取C由于顺序存储要求连续的存储区域，所以在存储管理上不够灵活D线性表的链式存储结构优于顺序存储结构(正确答案)答案解析：链式存储结构和顺序存储结构各有优缺点，有不同的适用场合。18.在单链表中，要将s所指结点插入到p所指结点之后，其语句应为

8、（）。 As-next=p+1; p-next=s;B(p).next=s; (s).next=(p).next;Cs-next=p-next; p-next=s-next;Ds-next=p-next; p-next=s;(正确答案)19.在双向链表存储结构中，删除p所指的结点时须修改指针（）。 Ap-next-prior=p-prior; p-prior-next=p-next;(正确答案)Bp-next=p-next-next; p-next-prior=p;Cp-prior-next=p; p-prior=p-prior-prior;Dp-prior=p-next-next; p-ne

9、xt=p-prior-prior;20.在双向循环链表中，在p指针所指的结点后插入q所指向的新结点，其修改指针的操作是（）。 Ap-next=q; q-prior=p; p-next-prior=q; q-next=q;Bp-next=q; p-next-prior=q; q-prior=p; q-next=p-next;Cq-prior=p; q-next=p-next; p-next-prior=q; p-next=q;(正确答案)Dq-prior=p; q-next=p-next; p-next=q; p-next-prior=q;21.若让元素1，2，3，4，5依次进栈，则出栈次序不可

10、能出现在（）种情况。 A5，4，3，2，1B2，1，5，4，3C4，3，1，2，5(正确答案)D2，3，5，4，1答案解析：栈是后进先出的线性表，不难发现C选项中元素1比元素2先出栈，违背了栈的后进先出原则，所以不可能出现C选项所示的情况。22.若已知一个栈的入栈序列是1，2，3，n，其输出序列为p1，p2，p3，pn，若p1=n，则pi为（）。 AiBn-iCn-i+1(正确答案)D不确定答案解析：栈是后进先出的线性表，一个栈的入栈序列是1，2，3，n，而输出序列的第一个元素为n，说明1，2，3，n一次性全部进栈，再进行输出，所以p1=n，p2=n-1，pi=n-i+1。23.数组Qn用来表

11、示一个循环队列，f为当前队列头元素的前一位置，r为队尾元素的位置，假定队列中元素的个数小于n，计算队列中元素个数的公式为（）。 Ar-fB(n+f-r)%nCn+r-fD（n+r-f)%n(正确答案)答案解析：对于非循环队列，尾指针和头指针的差值便是队列的长度，而对于循环队列，差值可能为负数，所以需要将差值加上MAXSIZE（本题为n），然后与MAXSIZE（本题为n）求余，即（n+r-f)%n。24.链式栈结点为:(data,link)，top指向栈顶.若想摘除栈顶结点，并将删除结点的值保存到x中,则应执行操作（）。 Ax=top-data;top=top-link;(正确答案)Btop=t

12、op-link;x=top-link;Cx=top;top=top-link;Dx=top-link;答案解析：x=top-data将结点的值保存到x中，top=top-link栈顶指针指向栈顶下一结点，即摘除栈顶结点。25.设有一个递归算法如下int fact(int n) /n大于等于0if(n=0) return 1;else return nfact(n-1); 则计算fact(n)需要调用该函数的次数为（）。 An+1(正确答案)BBn-1CC nDD n+2答案解析：特殊值法。设n=0，易知仅调用一次fact(n)函数，故选A。26.栈在（）中有所应用。 A递归调用B函数调用C表达

13、式求值D前三个选项都有(正确答案)答案解析：递归调用、函数调用、表达式求值均用到了栈的后进先出性质。27.为解决计算机主机与打印机间速度不匹配问题，通常设一个打印数据缓冲区。主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是（）。 A队列(正确答案)B栈C 线性表D有序表答案解析：解决缓冲区问题应利用一种先进先出的线性表，而队列正是一种先进先出的线性表。28.设栈S和队列Q的初始状态为空，元素e1、e2、e3、e4、e5和e6依次进入栈S，一个元素出栈后即进入Q，若6个元素出队的序列是e2、e4、e3、e6、e5和e1，则栈S的容量至少应该是（）。

14、 A2B3(正确答案)C4D 6答案解析：元素出队的序列是e2、e4、e3、e6、e5和e1，可知元素入队的序列是e2、e4、e3、e和e6依次进入栈，易知栈S中最多同时存在3个元素，故栈S的容量至少为3。29. 若一个栈以向量V1.n存储，初始栈顶指针top设为n+1，则元素x进栈的正确操作是（）。 Atop+; Vtop=x;BVtop=x; top+;Ctop-; Vtop=x;(正确答案)DVtop=x; top-;答案解析：初始栈顶指针top为n+1，说明元素从数组向量的高端地址进栈，又因为元素存储在向量空间V1.n中，所以进栈时top指针先下移变为n，之后将元素x存储在Vn。31.

15、设计一个判别表达式中左，右括号是否配对出现的算法，采用（）数据结构最佳。 A线性表的顺序存储结构B队列C. 线性表的链式存储结构D. 栈(正确答案)答案解析：利用栈的后进先出原则。32.用链接方式存储的队列，在进行删除运算时（）。 A. 仅修改头指针B. 仅修改尾指针C. 头、尾指针都要修改D. 头、尾指针可能都要修改(正确答案)答案解析：一般情况下只修改头指针，但是，当删除的是队列中最后一个元素时，队尾指针也丢失了，因此需对队尾指针重新赋值。33.循环队列存储在数组A0.m中，则入队时的操作为（）。 A. rear=rear+1B. rear=(rear+1)%(m-1)C. rear=(r

16、ear+1)%mD. rear=(rear+1)%(m+1)(正确答案)答案解析：数组A0.m中共含有m+1个元素，故在求模运算时应除以m+1。34.最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是（）。 A. (rear+1)%n=frontB. rear=front(正确答案)Crear+1=frontD. (rear-l)%n=front答案解析：最大容量为n的循环队列，队满条件是(rear+1)%n=front，队空条件是rear=front。35.栈和队列的共同点是（）。 A. 都是先进先出B. 都是先进后出C. 只允许在端点处插入和删除元素(正确答案)D

17、. 没有共同点答案解析：栈只允许在栈顶处进行插入和删除元素，队列只允许在队尾插入元素和在队头删除元素。36.一个递归算法必须包括（）。 A. 递归部分B. 终止条件和递归部分(正确答案)C. 迭代部分D. 终止条件和迭代部分37.串是一种特殊的线性表，其特殊性体现在（）。 A可以顺序存储B数据元素是一个字符(正确答案)C可以链式存储D数据元素可以是多个字符若38.串下面关于串的的叙述中，（）是不正确的? A串是字符的有限序列B空串是由空格构成的串(正确答案)C模式匹配是串的一种重要运算D串既可以采用顺序存储，也可以采用链式存储答案解析：空格常常是串的字符集合中的一个元素，有一个或多个空格组成的

18、串成为空格串，零个字符的串成为空串，其长度为零。39.串“ababaaababaa”的next数组为（）。 A012345678999B012121111212C011234223456(正确答案)D012301232234540.串“ababaabab”的nextval为（）。 A010104101(正确答案)B010102101C010100011D01010101141.串的长度是指（）。 A串中所含不同字母的个数B串中所含字符的个数(正确答案)C串中所含不同字符的个数D串中所含非空格字符的个数答案解析：串中字符的数目称为串的长度。42.假设以行序为主序存储二维数组A=array1.10

19、0,1.100，设每个数据元素占2个存储单元，基地址为10，则LOC5,5=（）。 A808B818(正确答案)C1010D1020答案解析：以行序为主，则LOC5,5=（5-1）100+（5-1）2+10=818。43.设有数组Ai,j，数组的每个元素长度为3字节，i的值为1到8，j的值为1到10，数组从内存首地址BA开始顺序存放，当用以列为主存放时，元素A5,8的存储首地址为（）。 ABA+141BBA+180(正确答案)CBA+222DBA+225答案解析：以列序为主，则LOC5,8=（8-1）8+（5-1）3+BA=BA+180。44.设有一个10阶的对称矩阵A，采用压缩存储方式，以行

20、序为主存储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（）。 A13B32C33(正确答案)D4045.若对n阶对称矩阵A以行序为主序方式将其下三角形的元素(包括主对角线上所有元素)依次存放于一维数组B1.(n(n+1)/2中，则在B中确定aij（ij）的位置k的关系为（）。 Ai(i-1)/2+jBj(j-1)/2+i(正确答案)Ci(i+1)/2+jDj(j+1)/2+i46.二维数组A的每个元素是由10个字符组成的串，其行下标i=0,1,8,列下标j=1,2,10。若A按行先存储，元素A8,5的起始地址与当A按列先存储时的元素（）的起始地址相同。设每个字符

21、占一个字节。 AA8,5BA3,10(正确答案)C. A5,8DA0,9答案解析：设数组从内存首地址M开始顺序存放，若数组按行先存储，元素A8,5的起始地址为:M+（8-0）10+（5-1）1=M+84;若数组按列先存储，易计算出元素A3,10的起始地址为:M+（10-1）9+（3-0）1=M+84。故选B。47.设二维数组A1. m，1. n（即m行n列）按行存储在数组B1. mn中，则二维数组元素Ai,j在一维数组B中的下标为（）。 A(i-1)n+j(正确答案)B(i-1)n+j-1Ci(j-1)Djm+i-1答案解析：特殊值法。取i=j=1，易知A1,1的的下标为1，四个选项中仅有A选

22、项能确定的值为1，故选A。48.数组A0.4,-1.-3,5.7中含有元素的个数（）。 A55B45(正确答案)C36D16答案解析：共有533=45个元素。49.广义表A=(a,b,(c,d),(e,(f,g)，则Head(Tail(Head(Tail(Tail（）)的值为（D ）。 A(g)(正确答案)B(d)CcDd答案解析：Tail(A)=(b,(c,d),(e,(f,g);Tail(Tail(A)=( (c,d),(e,(f,g); Head(Tail(Tail(A)= (c,d);Tail(Head(Tail(Tail(A)=(d);Head(Tail(Head(Tail(Tail

23、(A)=d。50.广义表(a,b,c,d)的表头是（），表尾是（ B ）。 AaB( )C(a,b,c,d)(正确答案)D(b,c,d)答案解析：表头为非空广义表的第一个元素，可以是一个单原子，也可以是一个子表，(a,b,c,d)的表头为一个子表(a,b,c,d);表尾为除去表头之外，由其余元素构成的表，表为一定是个广义表，(a,b,c,d)的表尾为空表( )。51.设广义表L=(a,b,c)，则L的长度和深度分别为（）。 A1和1B1和3C1和2(正确答案)D2和3答案解析：广义表的深度是指广义表中展开后所含括号的层数，广义表的长度是指广义表中所含元素的个数。根据定义易知L的长度为1，深度为

24、2。52.把一棵树转换为二叉树后，这棵二叉树的形态是（）。 A唯一的(正确答案)B.有多种C有多种，但根结点都没有左孩子D有多种，但根结点都没有右孩子答案解析：因为二叉树有左孩子、右孩子之分，故一棵树转换为二叉树后，这棵二叉树的形态是唯一的。53.由3个结点可以构造出多少种不同的二叉树?（） A2B3C4D5(正确答案)答案解析：五种情况如下:54.一棵完全二叉树上有1001个结点，其中叶子结点的个数是（）。 A250B500C254D501(正确答案)答案解析：设度为0结点（叶子结点）个数为A，度为1的结点个数为B，度为2的结点个数为C，有A=C+1，A+B+C=1001，可得2C+B=10

25、00，由完全二叉树的性质可得B=0或1，又因为C为整数，所以B=0，C=500，A=501，即有501个叶子结点。55.一个具有1025个结点的二叉树的高h为（）。 A11B10C11至1025之间(正确答案)D10至1024之间答案解析：若每层仅有一个结点，则树高h为1025;且其最小树高为log21025+1=11，即h在11至1025之间。56.（5）深度为h的满m叉树的第k层有（）个结点。(1=k=h) Amk-1(正确答案)Bmk-1Cmh-1Dmh-1答案解析：深度为h的满m叉树共有mh-1个结点，第k层有mk-1个结点。57.利用二叉链表存储树，则根结点的右指针是（）。 A指向最

26、左孩子B指向最右孩子C空(正确答案)D非空答案解析：利用二叉链表存储树时，右指针指向兄弟结点，因为根节点没有兄弟结点，故根节点的右指针指向空。58.对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采用（）遍历实现编号。 A先序B. 中序C. 后序(正确答案)D. 从根开始按层次遍历答案解析：根据题意可知按照先左孩子、再右孩子、最后双亲结点的顺序遍历二叉树，即后序遍历二叉树。59.若二叉树采用二叉链表存储结构，要交换其所有分支结点左、右子树的位置，利用（）遍历方法最合适。 A前序B中序C后序(正确答案)D按层

27、次答案解析：后续遍历和层次遍历均可实现左右子树的交换，不过层次遍历的实现消耗比后续大，后序遍历方法最合适。60.在下列存储形式中，（）不是树的存储形式? A双亲表示法B孩子链表表示法C孩子兄弟表示法D顺序存储表示法(正确答案)答案解析：树的存储结构有三种:双亲表示法、孩子表示法、孩子兄弟表示法，其中孩子兄弟表示法是常用的表示法，任意一棵树都能通过孩子兄弟表示法转换为二叉树进行存储。61.一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足（）。 A所有的结点均无左孩子B所有的结点均无右孩子C只有一个叶子结点(正确答案)D是任意一棵二叉树答案解析：因为先序遍历结果是“中左右”

28、，后序遍历结果是“左右中”，当没有左子树时，就是“中右”和“右中”;当没有右子树时，就是“中左”和“左中”。则所有的结点均无左孩子或所有的结点均无右孩子均可，所以A、B不能选，又所有的结点均无左孩子与所有的结点均无右孩子时，均只有一个叶子结点，故选C。62.设哈夫曼树中有199个结点，则该哈夫曼树中有（）个叶子结点。 A99B100(正确答案)C101D102答案解析：在哈夫曼树中没有度为1的结点，只有度为0（叶子结点）和度为2的结点。设叶子结点的个数为n0，度为2的结点的个数为n2，由二叉树的性质n0=n2+1，则总结点数n= n0+n2=2n0-1，得到n0=100。63.若X是二叉中序线

29、索树中一个有左孩子的结点，且X不为根，则X的前驱为（）。 AX的BX的右子树中最左的结点CX的左子树中最右结点(正确答案)DX的左子树中最右叶结点63.引入二叉线索树的目的是（）。 A加快查找结点的前驱或后继的速度(正确答案)B为了能在二叉树中方便的进行插入与删除C为了能方便的找到双亲D使二叉树的遍历结果唯一64.设F是一个森林，B是由F变换得的二叉树。若F中有n个非终端结点，则B中右指针域为空的结点有（）个。 An1BnCn + 1(正确答案)Dn + 265.n（n2）个权值均不相同的字符构成哈夫曼树，关于该树的叙述中，错误的是（）。 A该树一定是一棵完全二叉树(正确答案)B树中一定没有度

30、为1的结点C树中两个权值最小的结点一定是兄弟结点D树中任一非叶结点的权值一定不小于下一层任一结点的权值答案解析：哈夫曼树的构造过程是每次都选取权值最小的树作为左右子树构造一棵新的二叉树，所以树中一定没有度为1的结点、两个权值最小的结点一定是兄弟结点、任一非叶结点的权值一定不小于下一层任一结点的权值。66.在一个图中，所有顶点的度数之和等于图的边数的（）倍。 A1/2B1C2(正确答案)D467.在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（）倍。 A1/2B1(正确答案)C2D4答案解析：有向图所有顶点入度之和等于所有顶点出度之和。68.具有n个顶点的有向图最多有（）条边。 An

31、Bn(n-1)Cn(n+1)(正确答案)Dn2答案解析：有向图的边有方向之分，即为从n个顶点中选取2个顶点有序排列，结果为n(n-1)。69.n个顶点的连通图用邻接距阵表示时，该距阵至少有（）个非零元素。 AnB2(n-1)(正确答案)Cn/2DDn270.G是一个非连通无向图，共有28条边，则该图至少有（）个顶点。 A7B8C9(正确答案)D10答案解析：8个顶点的无向图最多有87/2=28条边，再添加一个点即构成非连通无向图，故至少有9个顶点。71.若从无向图的任意一个顶点出发进行一次深度优先搜索可以访问图中所有的顶点，则该图一定是（）图。 A非连通B连通(正确答案)C强连通D有向答案解析

32、：即从该无向图任意一个顶点出发有到各个顶点的路径，所以该无向图是连通图。72.下面（）算法适合构造一个稠密图G的最小生成树。 A Prim算法(正确答案)BKruskal算法CFloyd算法DDijkstra算法答案解析：Prim算法适合构造一个稠密图G的最小生成树，Kruskal算法适合构造一个稀疏图G的最小生成树。73.用邻接表表示图进行广度优先遍历时，通常借助（）来实现算法。 A栈B. 队列(正确答案)C. 树D图答案解析：广度优先遍历通常借助队列来实现算法，深度优先遍历通常借助栈来实现算法。74.用邻接表表示图进行深度优先遍历时，通常借助（）来实现算法。 A栈(正确答案)B. 队列C. 树D图答案解析：广度优先遍历通常借助队列来实现算法，深度优先遍历通常借助栈来实现算法。75.深度优先遍历类似于二叉树的（）。 A先序遍历(正确答案)B中序遍历C后序遍历D层次遍历