1、中国石油大学软件技术基础复习题线性表的习题1下述哪一条是顺序存储结构的优点？A插入运算方便B可方便地用于各种逻辑结构的存储表示C存储密度大D删除运算方便2下面关于线性表的叙述中，错误的是：A线性表采用顺序存储，必须占用一片连续的存储单元B线性表采用顺序存储，便于进行插入和删除操作C线性表采用链式存储，不必占用一片连续的存储单元D线性表采用链式存储，便于插入和删除操作。3某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用_存储方式最节省运算时间。A单链表B仅有头指针的单循环链表C双链表D仅有尾指针的单循环链表4链表不具有的特点是：A插入、删除不需要移动元素B可随机访问
2、任一元素C不必事先估计存储空间D所需空间与线性长度成正比5在n个节点的线性表的数组实现中，算法的时间复杂度是O(1) 的操作是：A访问第i个结点和求第i个结点的直接前驱B在第i个节点后插入一个新节点 O(n)C删除第i个节点 O(n)D以上都不对6在一个以h为头的单循环链表中，p指针指向链尾的条件是：Ap-next=hBp-next=nullCp-next-next=hDp-data=-17在非空双向循环链表中q所指的结点前插入一个由p所指的链结点的过程依次为：rlink(p)q; llink(p)llink(q);llink(q)p;_A rlink(q)p;B rlink(llink(q)
3、p;C rlink(llink(p)p;D rlink(rlink(p)p;8.在双向链表指针p的结点前插入一个指针q的结点的操作是：A. p-llink=q; q-rlink=p; p-llink-rlink=q; q-llink=q;B.p-llink=q;p-llink-rlink=q; q-rlink=p;q-llink=p-llink;C.q-rlink=p;q-llink=p-llink;p-llink-rlink=q;p-llink=q;D.q-llink=p-llink;q-rlink=q;p-llink=q;p-llink=q;9在双向链表存储结构中，删除p所指的结点时需要修
4、改指针_。A. p-llink-rlink=p-rlink; p-rlink-llink=p-llink;B. p-llink=p-llink-llink; p-llink-rlink=p;C. p-rlink-llink=p; p-rlink=p-rlink-rlink;D. p-rlink=p-llink-llink; p-llink=p-rlink-rlink;填空题1. 在单链表中设置头结点的作用_。2. 链表存储的特点是利用_来表示数据元素之间的逻辑关系；顺序存储的线性表示用_来表示数据元素之间的逻辑关系。3. 循环单链表的最大优点是_。4. 带头结点的双循环链表L为空表的条件是_。
5、L-rlink=L & L-llink=L5. 带头结点的双向循环链表L中含有一个结点的条件是：_。6. 线性表L=(a1,a2,an)用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是_。(n-1)/27. 在一个长度为n的顺序表中第i个元素之前插入一个元素时，需要向后移动_个元素。n-i+1栈和队列的习题2.8 设栈S和队列Q的初始状态为空，元素e1,e2,e3,e4,e5,e6依次通过栈S，一个元素出站后即进入队列Q，若出队的顺序为e2,e4,e3,e6,e5,e1，则栈S的容量至少应该为多少？解：栈S的容量至少应该为3。2.9 写出计算循环链表长度的算法
6、。解：设置一个变量len=0；循环编列循环链表，直到链表结束，len+。2.5 设循环队列的容量为70（序号1-70），现经过一系列的入队与退队运算后，有：（1） front=14，rear=21（2） front=23，rear=12问在这两种情况下，循环队列中各有多少个元素？解：（1）元素个数=21-14=7（2）元素个数=12+70-23=592.6 试用图表示在表达式A*(B-D)/T+C*(E*F)执行过程中运算符栈和操作数栈的变化情况。2.20 设树T的度为4，其中度为1，2，3，4的结点个数分别为4，3，2，1。问T中有多少个叶子结点？解：设叶子结点个数为x个。结点个数=度的总和
7、+1X+4+3+2+1=(1*4+2*3+3*2+4*1)+1=21解方程得：x=112.21 已知某二叉树的前序序列为DBACFEG，中序序列为ABCDEFG。请画出该二叉树，并写出二叉树的后序序列。后序序列为：ACBEGFD栈和队列1对于栈操作数据的原则是_。A. 先进先出B. 后进先出C. 后进后出D. 不分顺序2一个栈的输入序列为1,2,3,.,n，若输出序列的第一个元素是n，输出第i个元素是_。A. 不确定B. n-i+1C. iD. n-i3.设栈的输入序列为1,2,n；输出序列为p1,p2,pn；若p1=n则当n=i=1时，pi为_；若存在k1使pk=n，则当ik时，pi为_。A
8、. pi=n-i+1;B. pi不确定C. pi=n-(i-k);4.设栈的输入序列是1,2,3,4，则_不可能是其出栈序列。A. 1,2,4,3 B. 2,1,3,4 C. 1,4,3,2 D. 4,3,1,2 E. 3,2,1,45.如入栈序列为1,2,3,4,5，则可能得到的出栈序列为_。A. 1,2,5,3,4 B. 3,1,2,5,4 C. 3,2,5,4,1 D. 1,4,2,3,5E. 都不可能6.向一个栈顶指针为h的带头结点的链栈中插入指针s所指的结点时，应执行_。A. h-next=s; B. s-next=h; C. s-next=h; h-next=s;D. s-next
9、=h-next; h-next=s;7.某堆栈的输入序列为a,b,c,d，下面的四个序列中，不可能是它的输出序列的是_。A. a,c,b,d B. b,c,d,a C. c,d,b,a D. d,c,a,b8.一个栈的入栈序列为A,B,C,D,E,则栈的不可能的出栈序列是_。A. ABCDE B. EDCBA C. DECBA D. DCEAB9.若一个栈以向量V1.n存储，初始栈顶指针top为n+1，则下面x入栈的正确操作是_。A. top:=top+1; vtop:=x;B. Vtop:=x; top:=top+1;C. top:=top-1; Vtop:=x;D. Vtop:=x; to
10、p:=top-1;10.若栈采用顺序存储方式存储，现两栈共享空间V1.m，topi代表第i个栈（i=1,2）栈顶，栈1的底在v1，栈2的底在vm，则栈满的条件是_。A. top2-top1=0B. top1+1=top2C. top1+top2=mD. top1=top211. 栈在_中应用。A. 递归调用 B. 子程序调用 C. 表达式求值 D. A,B,C12.最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是_。A. (rear+1) MOD n=frontB. rear=frontC. rear+1=frontD. (rear-1) MOD n=front填空
11、题1区分循环队列的满与空，只有两种方法，他们是_和_。2在循环队列中，队列长度为n，存储位置从0到n-1编号，以rear指示实际的队尾元素，现要在此队列中插入一个新元素，新元素的位置是_。rear=(rear+1) mod n3设a=6,b=4,c=2,d=3,e=2，则后缀表达式abc-/de*+的值为_。94表达式3*2(4+2*2-6*3)-5求值过程中，当扫描到6时，对象栈和运算符栈分别为：_和_。3,2,8; ;*(-树的习题1已知一算术表达式的中缀表达式为a-(b+c/d)*e，其后缀表达式为（）。A. a+b*c/d B. a+b*cd/e C. -+*abc/de D. abc
12、d/+e*-2算术表达式a+b*(c+d/e)转换为后缀表达式后为（）。A. ab+cde/* B. abcde/+*+ C. abcde/*+ D. abcde*/+3每个结点的度或者为0或者为2的二叉树称为正则二叉树。n个结点的正则二叉树中有（）个叶子。A. B. C. D. 4设树T的度为4，其中度为1,2,3,4的结点个数分别为4,2,1,1，则T中的叶子个数为（）。A. 5 B. 6 C. 7 D. 85在下述结论中，正确的是（）。 只有一个结点的二叉树的度为0； 二叉树的度为2； 二叉树的左右子树可以任意交换； 深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。A. B.
13、 C. D. 6设森林F对应的二叉树为B，它有m个结点，B的根为p，p的右子树结点个数为n，森林F中第一棵树的结点个数是（）。A. m-n B. m-n-1 C. n+1 D. 条件不足，无法确定7若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（）。A. 9 B. 11 C. 15 D. 不确定8在一棵三元树中度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，则度为0的结点数为（）个。A. 4 B. 5 C. 6 D. 79设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为M1,M2和M3。与森林F对应的二叉树根结点的右子树上的结点个数是（）。
14、A. M1 B. M1+M2 C. M3 D. M2+M310具有10个叶子结点的二叉树中有（）个度为2的结点。A. 8 B. 9 C. 10 D. 1111一棵完全二叉树上有1001个结点，其中叶子结点的个数是（）。A. 250 B. 500 C. 254 D.都不对12已知一棵完全二叉树中共有626个结点，叶子结点的个数应为（）。A. 311 B. 312 C. 313 D. 314 E. 都不对13一棵124个叶子结点的完全二叉树，最多有（）个结点。A. 247 B. 248 C. 249 D. 250 E. 251填空题1树在计算机内的表示方法有_、_和_。2在二叉树中，指针p所指的结
15、点为叶子结点的条件是_。P-lchild=null &-rchild=null3具有256个结点的完全二叉树的深度为_。94已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点，则该树有_个叶子结点。5深度为H的完全二叉树至少有_个结点，至多有_个结点；H和结点总数N之间的关系是_。应用题1设一棵二叉树的前序遍历序列为：ABDFCEGH，中序遍历序列为：BFDAGEHC，画出这棵二叉树，给出后序遍历序列。画出这棵树的双亲孩子链表表示方式。数组的习题1设有数组Ai,j，数组的每个元素长度为3字节，i的值从1到8，j的值从1到10，数组从内存首地址BA开始顺序存放，当用以列为主
16、存放时，元素A5,8的存储首地址为（ ）。A. BA+141 B. BA+180 C. BA+222 D. BA+2252若6行5列的数组以列序为主序顺序存储，首地址为1000，每个元素占2个存储单元，则第3行第4列的元素（假定没有第0行和第0列）的地址是（）。A. 1040 B. 1042 C.1026 D. A,B,C都不对3将一个A1.100, 1.100的三对角矩阵，按行优先存入一维数组B1.298中，A中元素A66,65在数组B中的位置K为（）。A. 198 B. 195 C. 196 D. 1974设有一个n行n列的对称矩阵A，将其下三角部分按行存放在一个一维数组B中，A00存放在
17、B0中，那么第i行的对角元素Aii存放于B中（）处。A. (i+3)*i/2 B. (i+1)*i/2 C. (2n-i+1)*i/2 D. (2n-i-1)*i/2图的习题1图中有关路径的定义是（）。A. 由顶点和相邻顶点序列构成的边所形成的序列B. 由不同顶点所形成的序列C. 由不同边所形成的序列D. 上述定义都不是2设无向图的顶点个数为n，则该图最多有（）条边。A. n-1 B. n(n-1)/2 C. n(n+1)/2 D. 03一个n个顶点的连通无向图，其边的个数至少为（）。A. n-1 B. n C. n+1 D. nlogn4要连通具有n个顶点的有向图，至少需要（）条边。A. n
18、-1 B. n C. n+1 D. 2n5n个结点的完全有向图含有边的数目为（）。A. n*n B. n(n+1) C. n/2 D. n*(n-1)6一个有n个结点的图，最少有（）个连通分量，最多有（）个连通分量。A. 0 B. 1 C. n-1 D. n7在一个无向图中，所有顶点的度数之和等于所有边数（）倍，在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的（）倍。A. 1/2 B. 2 C. 1 D. 48用有向无环图描述表达式(A+B)*(A+B)/A)，至少需要顶点的数目为（）。A. 5 B. 6 C. 8 D. 99用邻接表存储图所用的空间大小为（）。A. 与图的顶点数和边数
19、都有关B. 只与图的边数有关C. 只与图的顶点数有关D. 与边数的平方有关10图G是n个顶点的无向完全图，则下列说法正确的有：A. G的邻接多重表需要n(n-1)个边结点和n个顶点结点B. G的连通分量个数最少C. G为连通图D. G所有顶点的度的总和为n(n-1)填空题1在一个无向图的邻接表中，若表结点的个数是m，则图中边的条数是_条。2若一个具有n个顶点，e条边的无向图是一个森林，则该森林中必有_棵树。3应用题。1 将下列由三棵树组成的森林转换为二叉树。2试找出满足下列条件的二叉树。（1）前序序列与后序序列相同（2）中序序列与后序序列相同（3）前序序列与中序序列相同（4）中序序列与层次遍历
20、序列相同答：前序序列为：根左右中序序列为： 左-根右后序序列为：左右根（1）前序序列=后序序列，或为空树，或只有根结点的二叉树；（2）中序序列=后序序列，或为空树，或任一结点至多只有左子树。（3）前序序列=中序序列，或为空树，或任一结点至多只有右子树。13设G=(V,E)以邻接表存储，如图所示，试画出图的深度优先和广度优先生成树。深度优先遍历序列：广度优先遍历序列：3已知一个无向图如图所示，要求分别用Prim和Kruskal算法生成最小生成树。（假设以1为起点，试画出构造过程）（1）Prim算法（2）Kruskal算法过程： 结果如下：可选（2，4）代替（3，4），（5，6）代替（1，5）。4已知无向图如下所示：（1）给出从V1开始的广度优先遍历序列；（2）画出它的临接表；（3）画出从V1开始的深度优先搜索生成树。答案：（1）广度优先遍历序列：V1,V2,V3,V4,V5,V6,V7,V8（2）临接表为：（3）深度优先遍历序列：V1,V2,V4,V8,V5,V3,V6,V7深度优先搜索生成树：
