《数据结构部分习题.doc》由会员分享，可在线阅读，更多相关《数据结构部分习题.doc（11页珍藏版）》请在金锄头文库上搜索。
1、数据结构部分习题第二章 线性表一、问答题1、简述下列术语：线性表，顺序表，链表。2、何时选用顺序表，何时选用链表作为线性表的存储结构合适?各自的主要优缺点是什么?3、在顺序表中插入和删除一个结点平均需要移动多少个结点?具体的移动次数取决于哪两个因素?4、链表所表示的元素是否有序?如有序，则有序性体现于何处?链表所表示的元素是否一定要在物理上是相邻的?二、单选题1、在表长为n的单链表中,算法时间复杂度为O(n)的操作是( )。 A. 查找单链表中第i个结点 B. 在p结点之后插入一个结点 C. 删除表中第一个结点 D. 删除p结点的直接后继结点2、 在下列链表中不能从当前结点出发访问到其余各结点
2、的是( )。 A. 单链表 B. 单循环链表 C. 双向链表 D. 双向循环链表3、线性表采用顺序存储时，其地址 ( ) A必须是连续的 B部分地址必须是连续的C一定是不连续的 D连续与否均可以4、线性表采用链式存储结构时，其地址 ( )A必须是连续的 B部分地址必须是连续的C.一定是不连续的 D连续与否均可以5、在长度为n的顺序表的第i个数据元素(1in)之前插入一个数据元素,元素的移动次数为 ( )。 A. n-i+1 B. n-i C. i D. i-1 6、对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构为 ( )。 A. 顺序表 B. 用头指针表示的单循环链表C. 用尾指
3、针表示的单循环链表 D. 单链表7、在需要经常查找结点的前驱与后继的场合中，使用( )比较合适。 A单链表 B双向链表 C单循环链表 D循环链表8、在一个单链表h中，若要删除由指针q所指向结点的直接后继结点，则执行（ ）。Ap=q-next;p-next=q-next;Bp=q-next;q-next=p;Cp=q-next;q-next=p-next;Dq-next=q-next-next;q-next=q;9、 9、链表不具有的特点是（ ）。 A可随机访问任一元素 B插入删除不需要移动元素 C不必事先估计存储空间 D所需空间与线性表长度成正比 10、对于一个头指针为h的带表头结点单链表，判
4、定其为空表的条件是( )。 A. h=NULL； Bh-next=NULL； Ch!=NULL； Dh-next= h；11、在非空单链表中，在p结点后插入一个q结点依次执行操作是( )。 A. q-link=p; p-link=q； B. q-link=p-link; p-link=q； C. q-link=p-link；p=q； D. p-link=q；q-link=p；12、以下关于线性表的叙述中，正确的是 ( )。 A. 顺序表可以随机存取 B. 链表可以随机存取 C. 顺序表便于动态处理 D. 顺序表便于插入或删除数据元素 13、在非空的单循环链表h中，某个p结点为尾结点的条件是(
5、)。 A. p=NULL； Bp-link=NULL； Ch!=NULL； Dp-link= h；14. 设p结点是带表头结点双向循环链表的表中结点,在p结点后插入s结点语句序列中正确的是( )A. s-next=p-next；p-next-prior=s； p-next=s；s-prior=p；B. p-next=s；s-next=p-next； p-next-prior=s；s-next=p；C. p-next=s；p-next-prior=s； s-next=p-next；s-next=p；D. p-next-prior=s；p-next=s；s-next=p-next；s-next=p
6、；15、设p结点是带表头结点的双循环链表的表中结点，在p结点之前插入s结点的语句序列中正确的是( )。A. s-prior=p-prior；p-prior-next=s； p-prior=s；s-next=p；B. p-prior=s；p-prior-next=s； s-prior=p-prior；s-next=p；C. p-prior-next=s；p-prior=s； s-prior=p-prior；s-next=p； D. p-prior=s；s-next=p； p-prior-next=s；s-prior=p-prior；16、以下关于静态链表的叙述中，错误的是 ( )。静态链表既有顺
7、序存储的优点又有动态链表的优点，所以它存取表中第i个元素的时间与i无关。 .静态链表能容纳的最多元素个数在表定义时就确定了，以后不能增加。.静态链表与动态链表在元素的插入、删除上类似，不需做元素的移动。A.只有 B.只有 C. 和 D. 、和17、在具有n个结点的单链表中插入一个新结点并使链表仍然有序的时间复杂度是( )。 A. O(1) B. O(n) C. O(nlog2n) D. O(n2)三、算法题1、设顺序表L是递增有序表，试写一算法，将x插入到L中并使L仍是递增有序表。2、写一求单链表的结点数目ListLength(L)的算法。3、写一算法将单链表中值重复的结点删除，使所得的结果链
8、表中所有结点的值均不相同。 4、写一算法从一给定的向量A删除值在x到y(xy)之间的所有元素(注意：x和y是给定的参数，可以和表中的元素相同，也可以不同)。 第三章 栈和队列一、问答题1、设有一个栈，元素进栈的次序为a, b, c。问经过栈操作后可以得到哪些输出序列？2、循环队列的优点是什么?如何判断它的空和满？3、利用栈的基本操作，写一个返回栈S中结点个数的算法int StackSize(SeqStack S) ，并说明S为何不作为引用参数的算法?4、一个双向栈S是在同一向量空间内实现的两个栈，它们的栈底分别设在向量空间的两端。试为此双向栈设计初始化InitStack(S) ，入栈Push(
9、S,i,x)，出栈Pop(S,i,x)算法，其中i为0或1 ，用以表示栈号。5、假设Q0,5是一个循环队列，初始状态为front=rear=0，请画出做完下列操作后队列的头尾指针的状态变化情况，若不能入对，请指出其元素，并说明理由。a. d, e, b, g, h入队b. d, e出队c. i , j , k , l , m入队d. b出队e. n, o, p, q, r入队 二、选择题1、在栈中存取数据遵守的原则是 （ ） A先进先出 B后进先出 C后进后出 D随机进出2、设S是顺序栈,元素a,b,c,d,e,f依次栈,如果出栈顺序为b,c,d,f,e,a,则顺序栈的容量至少应为( )个元素
10、。 A. 2 B. 3 C. 4 D. 53、用一个大小为N的一维数组顺序存储一个栈时，假定用top=N表示栈空，则向栈中插入一个元素时,首先应执行( )语句修改top指针。 Atop+ B top- C top=0 D top=04、设有一个空栈，栈顶指针为1000H,每个元素占一个单位的存储空间，则执行Push,Push,Pop,Push,Pop,Push,Pop,Push操作以后，栈顶指针的位置是（ ）。A. 1000 B. 1001 C. 1002 D. 10035、表达式a*(b+c)-d的后缀表达式是( ) 。Aabcd *+- B. abc+*d - C. abc*+d - D.
11、 -+ * abcd6、一个初始输入序列a、b、c、d，顺序进入栈S，然后依次从栈S中出栈并进入队列Q中，再从队列Q中出队进入栈S，则在栈S中从栈顶到栈底的序列是( ) 。 A. abcd B. dcba C. badc D. adcb7、用一个大小为6的数组来实现循环队列，元素依次按照0,1,2,3,4,5的位置顺序循环存放,当前front和rear的值分别为4和0，现在从队列中删除一个元素,再加入2个元素后,front和rear的值分别是( )。A5和2 B6和1 C2和4 D3和18、设一个循环队列Qmaxsize的队头指针为front 、队尾指针为rear,队列的最大容量为maxsiz
12、e , 除此之外该队列没有其他数据成员，则该队列的队满条件是( )。 A. Q.rear=Q.front B. Q.rear+Q.front =maxsize C. (Q.rear+1)% maxsize =Q.front D. (Q.front+1)% maxsize =Q.rear第4章 树的习题一、选择题（1）关于二叉树下列说法正确的是（ B ）。 A.二叉树的度为2 B.二叉树的度可以小于2 C.每一个结点的度都为2 D.至少有一个结点的度为2（2）设高度为h的二叉树只有度为0和度为2的节点，则此二叉树中结点总数至少为（ B ）。 A.2h B.2h-1 C. 2h+1 D.h+1（3
13、）在树种，结点A有4个兄弟，B是A的双亲，则B的度为（ C ）。 A.3 B.4 C. 5 D. 6（4）若一棵完全二叉树中，某节点无左孩子，则该结点一定是（ D ）。 A.度为1的结点 B.度为2的结点 C.分支节点 D.叶子结点（5）高度为k的完全二叉树至多有（ C ）个结点，至少有（ B ）个结点。 A.2K-1-1 B. 2K-1 C.2K-1 D.2K（6）先序序列为ABC的二叉树有（ C ）棵。 A. 3 B.4 C.5 D.6（7）在有200个结点的完全二叉树中，根的编号为1，则编号为60的结点左孩子编号是（ ），右孩子的编号是（ D ）。 A.30 B.60 C.120 D.121（8）遍历一棵具有n个结点的完全二叉树，在先序，中序和后序序列中，叶子结点的相对次序（ B ）。 A.都不同 B.完全相同 C.先序和中序相同 D.中序与后序相同（9）在由4棵树组成的森林中，1，
