《数据结构》习题库之一：选择题1.算法分析的目的是（）A.研究算法的输入与输出之间的关系B.找出数据结构的合理性C.分析算法的效率以求改进算法D.分析算法的可读性与可移植性2. 在由list所指的非空线性链表中删除由p指的链结点的下一个链结点的过程是依次执行q=p->link,（）,delete q。
A.p->link=qB.q->link=pC.q->link=p->linkD.p->link=q->link3.依次在初始为空的队列中插入元素为a,b,c,d以后，紧接着作了两次删除操作，此时的队头元素是（）A.aB.bC.cD.d4.若某堆栈的输入序列为 1，2，3，…，n-1，n，输出序列的第1个元素为n，则第i个输出元素为（）A.n-i+1B.n-1C.iD.哪个元素无所谓5.设计递归问题的非递归算法一般需要用到（）机制。
A.数组B.堆栈C.队列D.二叉树6.已知非空二叉树采用顺序存储结构，树中结点的数据信息依次存放在一个一维数组中，即 ABC □DEF□□G□□H□□该二叉树的中序列遍历序列为（）A.G,D,B,A,F,H.C,EB.G,B,D,A,F,H,C,EC.B,D,G,A,F,H,C,ED.B,G,D,A,F,H,C,E7.在一棵度为3的树中，度为3的结点有2个，度为2的结点有1个，度为1的结点有2个，那么，该树有（）个叶结点。
A.4B.5C.6D.78. 向具有n个结点的、结构均衡的二叉搜索树中插入一个元素的时间复杂度大致为（）。
A. O(1)B. O(log2n )C. O(n)D. O(nlog2n)9.在初始为空的散列表中依次插入关键字序列(MON,TUE,WED,THU,FRI,SAT,SUN),散列函数为H(k)=i MOD 7，其中，i为关键字k的第一个字母在英文字母表中的序号，地址值域为 [0:6] ，采用线性再散列法处理冲突。
插入后的散列表应该如（）所示。
A. 0 1 2 3 4 5 6THU TUE WED FRI SUN SAT MONB. 0 1 2 3 4 5 6TUE THU WED FRI SUN SAT MONC. 0 1 2 3 4 5 6TUE THU WED FRI SAT SUN MOND. 0 1 2 3 4 5 6TUE THU WED SUN SAT FRI MON10. 对数据元素序列(49，72，68，13，38，50，97，27)进行排序，前三趟排序结束时的结果依次为：第一趟：13，72，68，49，50，97，27；第二趟：13，27，68，49，38，50，97，72；第三趟：13，27，38，49，68，50，97，72；该排序采用的方法是（）A.插入排序法B.选择排序法C.泡排序法D.堆积排序法11.广义表中元素分为（）A.原子元素B.表元素C.原子元素和表元素D.任意元素12.求字符串T在字符串S中首次出现的位置的操作称为（）A.串的模式匹配B.求子串C.求串的长度D.串的连接13.树型结构最适合用来描述（）A.有序的数据元素B.无序的数据元素C.数据元素之间的具有层次关系的数据D.数据元素之间没有关系的数据14.若二叉树中度为2的结点有15个，度为1的结点有10个,（）个叶结点。
A.25B.30C.31D.4115.若深度为6的完全二叉树的第6层有3个叶结点，则该二叉树一共有（）个结点。
A.15B.16C.17D.1816.若某完全二叉树的深度为h，则该完全二叉树中至少有（）个结点。
A.2hB.2h-1C.2h-1-1D.2h-1+117.在非空二叉树的中序遍历序列中，二叉树的根结点的左边应该（）A.只有左子树上的所有结点B.只有左子树上的部分结点C.只有右子树上的所有结点D.只有右子树上的部分结点18.对于任意非空二叉树，要设计出其后序遍历的非递归算法而不使用堆栈结构，最适合的方法是对该二叉树采用（）存储结构。
A.三叉链表B.二叉链表C.顺序D.索引19.对于一个数据序列，按照“逐点插入方法”建立一个二叉排序树，该二叉排序树的形状取决于（）A.该序列的存储结构B.序列中的数据元素的取值范围C.数据元素的输入次序D.使用的计算机的软、硬件条件20.下面关于哈夫曼树的说法，不正确的是（）A.对应于一组权值构造出的哈夫曼树一般不是唯一的B.哈夫曼树具有最小带权路径长度C.哈夫曼树中没有度为1的结点D.哈夫曼树中除了度为1的结点外，还有度为2的结点和叶结点21.线性链表中各链结点之间的地址（）A.连续与否都可以B.部分地址必须连续C.一定不连续D.必须连续22.删除非空双向循环链表中由q所指的链结点的过程是依次执行以下三个动作：q->llink->rlink=q->rlink,（）,delete q。
A.q->llink=qB.q->rlink->llink=qC.q->rlink->llink=q->llinkD.q->llink=q->rlink23.在包含有1000个元素的线性表中实现如下四个操作，所需要的执行时间最长的是（）A.线性表采用顺序存储结构，在第10个元素后面插入一个新的元素B.线性表采用链式存储结构，在第10个元素后面插入一个新的元素C.线性表采用顺序存储结构，删除第990个元素D.线性表采用链式存储结构，删除p指的链结点24.因此在初始为空的队列中插入元素a,b,c,d以后，紧接着作了两次删除操作，此时的队尾元素是（）A.aB.bC.cD.d25.若不考虑结点的数据信息的组合情况，具有3个结点的二叉树共有（）种形态。
A.2B.3C.4D.526.对任何一棵二叉树，若n0，n1，n2分别是度为0，1，2的结点的个数，则 n0=（）A.n1+1B.n1+n2C.n2+1D.2n1+127.下面的序列中（）是最大堆。
A.1,2,8,5,3,9,10,4B.1,5,10,6,7,8,9,2C.9,8,7,6,4,8,2,1D.9,8,7,6,5,4,3,128.在下述的排序方法中，不属于内排序方法的是（）A.插入排序法B.选择排序法C.拓扑排序法D.归并排序法29.采用顺序查找方法查找长度为n的线性表，平均查找长度为（）。
A.nB.n/2C.(n+1)/2D.(n-1)/230.对线性表采用折半查找法，该线性表必须（）。
A.采用顺序存储结构B.采用链式存储结构C.采用顺序存储结构，且元素按值有序D.采用链式存储结构，且元素按值有序31.已知二叉树的前序序列为ABDCEFG，中序序列为DBCAFEG，则后序序列为（）。
A.DCBAFGEB.DCBFGEAC.DCBFEGAD.DCBGFEA32.按逐点插入法建立对应于序列(54，28，16，34，73，62，95，60，26，43)的二叉排序树后，查找62要进行（）次比较。
A.6次B.5次C.3次D.2次33.根据堆积定义，下面的四个序列中，（）是堆积。
A.75，65，30，15，25，45，20，10B.75，65，45，10，30，25，20，15C.75，45，65，30，15，25，20，10D.75，45，65，10，25，30，20，1534.正常情况下，删除非空的顺序存储结构的堆栈的栈顶元素，栈顶指针top的变化是（）。
A.top不变B.top←0C.top←top+1D.top←top-135.中缀表达式(A-B*C)/D+E的后缀形式是（）。
A.A-BC*D/E+B.ABC*-D/E+C.ABC*-DE/+D.ABC*-D/+E36.对二叉树进行（）遍历可以得到结点的排序序列。
A.前序B.中序C.后序D.按层次37.一个具有n个顶点的连通图的生成树中有（）条边。
A.n-1B.nC.┗n/2┛D.n+138.对具有八个元素的序列(49,38,65,97,76,13,27,50)按从小到大排序，（）是选择排序法第一趟的结果。
A.13,65,38,97,76,49,27,50B.13,27,38,49,50,65,76,97C.97,76,65,50,49.38,27,13D.13,38,65,97,76,49,27,5039.在长度为n的线性表A[1:n]的第i个位置插入一个元素，需要后移（）个元素。
A.n-1B.n-i+1C.n-i-1D.i40.中缀表达式A-(B+C/D)*E的后缀形式是（）A.AB-C+D/E*B.ABC+D/-E*C.ABCD/E*+-D.ABCD/+E*-41.具有n个结点的完全二叉树的深度为（）(符号┗x┛表示取不大于x的最大整数)A.┗log2n┛B.┗log2n┛-1C.┗log2(n+1)┛D.┗log2n┛+142.具有n个顶点的无向图最多有（）条边。
A.n(n-1)/2B.n(n+1)/2C.n2/2D.2n43.根据堆的定义，下列的四个序列中（）是一个堆。
A.75 65 30 15 25 45 20 10B.75 65 45 10 30 25 20 15C.75 45 65 30 15 25 20 10D.75 45 65 10 25 30 20 1544.若长度为n的线性表采用顺序存储结构，删除它的第i数据元素之前，需要先依次向前移动（）个数据元素。
A.n-iB.n+iC.n-i-1D.n-i+145.在单链表中，已知q指的结点是q指的结点的直接前驱结点，若在q和p指的结点之间插入一个由s指的结点，则需执行（）。
A.s->link=p->link，p->link=sB.q->link=s，s->link=pC.p->link=s->link，s->link=pD.p->link=s，s->link=q46.在非空双向循环链表中由q所指的那个链结点前面插入一个由p指的链结点的动作对应的语句依次为:p->rlink=q,p->llink=q->llink,p=p->llink,（）。
A.q->rlink=pB.q->llink->rlink=pC.p->llink->rlink=pD.p->rlink->rlink=p47.为了节省存储空间，将n阶对称矩阵A中包括主对角线元素在内的下三角部分的所有元素按照行序为主序方式存放在一维数组B[1:n(n-1)/2]中，对任意下三角部分的元素aij(i≥j)在B的下标k是（）A.i(i-1)/2+jB.(i(i-1))/2+jC.i(i+1)/2+jD.(i(i+1))/2+j48.某堆栈的输入序列为a,b,c,d,下面的四个序列中，（）不可能是它的输出序列。