数据结构复习题一.docx

数据结构复习题一.docx

《数据结构复习题一.docx》由会员分享，可在线阅读，更多相关《数据结构复习题一.docx（16页珍藏版）》请在冰点文库上搜索。

数据结构复习题一

第1章绪论

一、选择题

1.算法的计算量的大小称为计算的（   ）。

A．效率         B.复杂性      C.现实性          D.难度

2.算法的时间复杂度取决于（）

A．问题的规模     B.待处理数据的初态     C.A和B

3.计算机算法指的是

（1），它必须具备

（2）这三个特性。

（1）A．计算方法    B.排序方法       C.解决问题的步骤序列     D.调度方法

（2）A．可执行性、可移植性、可扩充性   B.可执行性、确定性、有穷性

C.确定性、有穷性、稳定性         D.易读性、稳定性、安全性  

4.一个算法应该是（    ）。

    A．程序    B．问题求解步骤的描述    

C．数据结构+程序       D．以上都不对.

5.下面关于算法说法错误的是（   ）

A．算法最终必须由计算机程序实现

B.为解决某问题的算法同为该问题编写的程序含义是相同的

C.算法的可行性是指指令不能有二义性         D.以上几个都是错误的

6.下面说法错误的是（   ）

（1）算法原地工作的含义是指不需要任何额外的辅助空间

（2）在相同的规模n下，复杂度O（n）的算法在时间上总是优于复杂度O（2n）的算法

  （3）所谓时间复杂度是指随问题规模的增大，算法执行时间的增长率。

  （4）空间复杂度是算法所需存储空间的量度。

 A．

（1）     B.

（1）,

（2）   C.

（1）,（4）    D.（3）

7.从逻辑上可以把数据结构分为（   ）两大类。

A．动态结构、静态结构      B．顺序结构、链式结构 

C．线性结构、非线性结构    D．初等结构、构造型结构

8.以下与数据的存储结构无关的术语是（   ）。

A．循环队列      B.链表       C.哈希表         D. 栈

9.连续存储设计时，存储单元的地址（   ）。

A．一定连续 B．一定不连续 C．不一定连续 D．部分连续，部分不连续

10.以下属于逻辑结构的是（   ）。

A．顺序表      B.哈希表       C.有序表         D. 单链表

第2章线性表

一、选择题

1.下述哪一条是顺序存储结构的优点？

（   ）

A．存储密度大 B．插入运算方便 C．删除运算方便 D．可方便地用于各种逻辑结构的存储表示

2.下面关于线性表的叙述中，错误的是哪一个？

（   ）

A．线性表采用顺序存储，必须占用一片连续的存储单元。

B．线性表采用顺序存储，便于进行插入和删除操作。

C．线性表采用链接存储，不必占用一片连续的存储单元。

D．线性表采用链接存储，便于插入和删除操作。

3.线性表是具有n个（   ）的有限序列（n>0）。

A．表元素     B．字符     C．数据元素    D．数据项        E．信息项

4.若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（   ）存储方式最节省时间。

A．顺序表     B．双链表       C．带头结点的双循环链表    D．单循环链表

5.某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（   ）存储方式最节省运算时间。

A．单链表    B．仅有头指针的单循环链表    C．双链表      D．仅有尾指针的单循环链表

6.设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用（   ）最节省时间。

A.单链表  B.单循环链表  C.带尾指针的单循环链表  D.带头结点的双循环链表

7.若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点。

则采用（   ）存储方式最节省运算时间。

A．单链表     B．双链表    C．单循环链表    D．带头结点的双循环链表

8.链表不具有的特点是（   ）

A．插入、删除不需要移动元素 B．可随机访问任一元素

 C．不必事先估计存储空间 D．所需空间与线性长度成正比

9.下面的叙述不正确的是（   ）

A．线性表在链式存储时，查找第i个元素的时间同i的值成正比

   B.线性表在链式存储时，查找第i个元素的时间同i的值无关

C.线性表在顺序存储时，查找第i个元素的时间同i的值成正比

D.线性表在顺序存储时，查找第i个元素的时间同i的值无关

10.若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（   ）（1<=i<=n+1）。

A.O（0）     B.O

（1）        C.O（n）         D.O（n2）

11.对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为（   ）。

A．O（n） O（n）     B.O（n） O

（1）      C.O

（1） O（n）       D.O

（1）O

（1）

12.线性表（a1,a2,…,an）以链接方式存储时，访问第i位置元素的时间复杂性为（   ）

A．O（i）     B．O

（1）     C．O（n）      D．O（i-1）

13.非空的循环单链表head的尾结点p满足（   ）。

A．p.next=head      B．p.next=NULL        C．p=NULL    D．p=head

14.在单链表指针为p的结点之后插入指针为s的结点，正确的操作是：

（   ）。

A．p->next=s;s->next=p->next; B．s->next=p->next;p->next=s;

C．p->next=s;p->next=s->next; D．p->next=s->next;p->next=s;

15.对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是（   ）

A．head==NULL B．head->next==NULL   

C．head->next==head  D．head!

=NULL

二、综合应用题

1.已知线性表（a1a2a3…an）按顺序存于内存，每个元素都是整数，试设计用最少时间把所有值为负数的元素移到全部正数值元素前边的算法：

例：

（x,-x,-x,x,x,-x…x）变为（-x,-x,-x…x,x,x）。

2.设单链表的表头指针为h，结点结构由data和next两个域构成，其中data域为字符型。

写出算法dc（h,n）,判断该链表的前n个字符是否中心对称。

例如xyx,xyyx都是中心对称。

3.已知非空线性链表由list指出，链结点的构造为（data,link）.请写一算法，将链表中数据域值最小的那个链结点移到链表的最前面。

要求：

不得额外申请新的链结点。

4.试编写在带头结点的单链表中删除（一个）最小值结点的（高效）算法。

voiddelete（Linklist&L）

5.设有一头指针为L的带有表头结点的非循环双向链表，其每个结点中除有pred（前驱指针），data（数据）和next（后继指针）域外，还有一个访问频度域freq。

在链表被起用前，其值均初始化为零。

每当在链表中进行一次Locate（L,x）运算时，令元素值为x的结点中freq域的值增1，并使此链表中结点保持按访问频度非增（递减）的顺序排列，同时最近访问的结点排在频度相同的结点的最后，以便使频繁访问的结点总是靠近表头。

试编写符合上述要求的Locate（L,x）运算的算法，该运算为函数过程，返回找到结点的地址，类型为指针型。

6.已知长度为n的线性表A采用顺序存储结构，请写一时间复杂度为0（n）、空间复杂度为0

（1）的算法，该算法删除线性表中所有值为item的数据元素。

（O

（1）表示算法的辅助空间为常量）。

第3章栈和队列

一、选择题

1.对于栈操作数据的原则是（  ）。

A.先进先出   B.后进先出   C.后进后出    D.不分顺序

2.一个栈的输入序列为123…n，若输出序列的第一个元素是n，输出第i（1<=i<=n）个元素是（   ）。

A.不确定         B.n-i+1         C. i          D.n-i

3.若一个栈的输入序列为1,2,3,…,n，输出序列的第一个元素是i，则第j个输出元素是（    ）。

 A.i-j-1         B.i-j           C.j-i+1     D.不确定的

4.一个栈的输入序列为12345，则下列序列中不可能是栈的输出序列的是（   ）。

  A.23415    B.54132    

C.23145     D.15432

5.输入序列为ABC，可以变为CBA时，经过的栈操作为（   ）

A.push,pop,push,pop,push,pop       

B.push,push,push,pop,pop,pop

   C.push,push,pop,pop,push,pop       

D.push,pop,push,push,pop,pop

6.若一个栈以向量V[1..n]存储，栈为空时栈顶指针top为n+1，则下面x进栈的正确操作是（   ）。

A．top:

=top+1; V[top]:

=x           

B. V[top]:

=x;top:

=top+1   

C.top:

=top-1; V[top]:

=x           

D. V[top]:

=x;top:

=top-1

7.栈在（   ）中应用。

A.递归调用       B.子程序调用      C.表达式求值   D.A，Ｂ，Ｃ

8.一个递归算法必须包括（   ）。

A.递归部分     B.终止条件和递归部分    C.迭代部分     D.终止条件和迭代部分

9.用不带头结点的单链表存储队列时,其队头指针指向队头结点,其队尾指针指向队尾结点，则在进行删除操作时（    ）。

A．仅修改队头指针         B.仅修改队尾指针

C.队头、队尾指针都要修改 D.队头,队尾指针都可能要修改

10.递归过程或函数调用时，处理参数及返回地址，要用一种称为（   ）的数据结构。

A．队列            B．多维数组          C．栈            D.线性表

11.假设以数组A[m]存放循环队列的元素,其头尾指针分别为front和rear，则当前队列中的元素个数为（   ）。

A．（rear-front+m）%m    B．rear-front+1     C．（front-rear+m）%m     D．（rear-front）%m

12.循环队列存储在数组A[0..m]中，则入队时的操作为（   ）。

A.rear=rear+1              B.rear=（rear+1）mod（m-1）

   C.rear=（rear+1）modm      D.rear=（rear+1）mod（m+1）

13.若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为多少？

（ ）

A.1和5        B.2和4         C.4和2        D.5和1 

14.栈的特点是（ ① ）,队列的特点是（ ② ）,栈和队列都是（ ③ ）。

若进栈序列为1,2,3,4则（ ④ ）不可能是一个出栈序列（不一定全部进栈后再出栈）；若进队列的序列为1,2,3,4则（ ⑤ ）是一个出队列序列。

①,②:

A.先进先出         B.后进先出       C.进优于出     D.出优于进

③:

A.顺序存储的线性结构    B.链式存储的线性结构 

C.限制存取点的线性结构  D.限制存取点的非线性结构

④,⑤:

A.3,2,1,4   B.3,2,4,1   C.4,2,3,1  D.4,3,2,1   F.1,2,3,4   G.1,3,2,4

15.栈和队列的共同点是（   ）。

A.都是先进先出                       B.都是先进后出  

C.只允许在端点处插入和删除元素       D.没有共同点

16.设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4,e5和e6依次通过栈S，一个元素出栈后即进队列Q，若6个元素出队的序列是e2，e4，e3,e6,e5,e1则栈S的容量至少应该是（   ）。

A．6         B.4         C.3         D.2

17.用单链表表示的链式队列的队头在链表的（   ）位置。

A．链头            B．链尾              C．链中

二、综合应用题

1.有5个元素，其入栈次序为：

A，B，C，D，E，在各种可能的出栈次序中，以元素C，D最先出栈（即C第一个且D第二个出栈）的次序有哪几个？

2.设从键盘输入一整数的序列：

a1,a2,a3，…，an,试编写算法实现：

用栈结构存储输入的整数，当ai≠-1时，将ai进栈；当ai=-1时，输出栈顶整数并出栈。

算法应对异常情况（栈空等）给出相应的信息。

3.设表达式以字符形式已存入数组E[n]中，‘#’为表达式的结束符，试写出判断表达式中括号（‘（’和‘）’）是否配对的C语言描述算法;（注：

算法中可调用栈操作的基本算法。

）

第4章树和二叉树

一、选择题

1.设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1 则T中的叶子数为（   ）

A．5           B．6         C．7          D．8

2.在下述结论中，正确的是（   ）

①只有一个结点的二叉树的度为0; ②二叉树的度为2； ③二叉树的左右子树可任意交换;

④深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。

A．①②③       B．②③④     C．②④      D．①④

3.设森林F对应的二叉树为B，它有m个结点，B的根为p,p的右子树结点个数为n,森林F中第一棵树的结点个数是（   ）

A．m-n  B．m-n-1   C．n+1  D．条件不足，无法确定

4.若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（ ）

A．9           B．11        C．15      D．不确定

5.设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为M1，M2和M3。

与森林F对应的二叉树根结点的右子树上的结点个数是（   ）。

A．M1         B．M1+M2      C．M3          D．M2+M3

6.具有10个叶结点的二叉树中有（ ）个度为2的结点，

A．8          B．9            C．10         D．ll

7.若一棵二叉树有126个节点，在第7层（根节点在第1层）至多有（   ）个节点。

A．32  B．64   C．63    D．不存在第7层   

8.设给定权值总数有n个，其哈夫曼树的结点总数为（   ）

A．不确定       B．2n        C．2n+1        D．2n-1

9.下列关于哈夫曼树的说法中最准确的是（）。

A．最优树     B．叶子节点带有权值的二叉树      C.最优二叉树    D．叶子节点带有权值的树

10.有关二叉树下列说法正确的是（   ）

A．二叉树的度为2 B．一棵二叉树的度可以小于2  

C．二叉树中至少有一个结点的度为2  D．二叉树中任何一个结点的度都为2

11.二叉树的第I层上最多含有结点数为（ ）

A．2I         B．2I-1-1          C．2I-1           D．2I -1

12.一个具有1025个结点的二叉树的高h为（   ）

A．11         B．10       C．11至1025之间     D．10至1024之间

13.一棵二叉树高度为h,所有结点的度或为0，或为2，则这棵二叉树最少有（   ）结点

A．2h    B．2h-1       C．2h+1        D．h+1  

14.对于有n个结点的二叉树,其高度为（   ）

A．nlog2n     B．log2n         C．⎣log2n⎦+1      D．不确定

15.一棵具有n个结点的完全二叉树的树高度（深度）是（   ）

A．⎣log2n⎦+1      B．log2n+1       C．⎣log2n⎦     D．log2n-1

16.高度为K的二叉树最大的结点数为（   ）。

A．2k     B．2k-1         C．2k-1       D．2k-1-1

17.一棵高为K的完全二叉树至少有（   ）个结点

A．2k–1          B.2k-1–1        C.2k-1      D.2k

18.对于先序遍历和中序遍历结果相同的二叉树是（   ）。

A．无左子树的二叉树       B．无右子树的二叉树        C．所有节点只有左子树的二叉树       D．所有节点只有右子树的二叉树

19.对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采用（   ）次序的遍历实现编号。

A．先序          B.中序         C.后序         D.从根开始按层次遍历

20.树的后根遍历序列等同于该树对应的二叉树的（   ）.

A.先序序列                  B.中序序列           C.后序序列

21.在下列存储形式中，哪一个不是树的存储形式？

（   ）

A．双亲表示法 B．孩子链表表示法C．孩子兄弟表示法D．顺序存储表示法

22.一棵二叉树的前序遍历序列为ABCDEFG，它的中序遍历序列可能是（   ）

A．CABDEFG          B．ABCDEFG      C．DACEFBG          D．ADCFEG    

23.已知一棵二叉树的前序遍历结果为ABCDEF,中序遍历结果为CBAEDF,则后序遍历的结果为（   ）。

A．CBEFDA      B．FEDCBA      C．CBEDFA      D．不定   

24.某二叉树中序序列为A,B,C,D,E,F,G，后序序列为B,D,C,A,F,G,E则前序序列是（   ）。

A．E,G,F,A,C,D,B     B．E,A,C,B,D,G,F     C．E,A,G,C,F,B,D     D．上面的都不对

25.二叉树的先序遍历和中序遍历如下：

先序遍历：

EFHIGJK；中序遍历:

HFIEJKG。

该二叉树根的右子树的根是（   ）。

A、E        B、F　    C、G　     D、H  

26.某二叉树T有n个结点，设按某种顺序对T中的每个结点进行编号，编号为1，2，…，n，且有如下性质：

T中任一结点V，其编号等于左子树上的最小编号减1，而V的右子树的结点中，其最小编号等于V左子树上结点的最大编号加1。

这时是按（   ）编号的。

A.中序遍历序列B.前序遍历序列C.后序遍历序列 D.层次顺序

27.一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足（   ）。

A．完全二叉树 B．只有两个结点的二叉树 C.二叉排序树  D.任一节点只有一个孩子结点

28.任何一颗二叉树的叶子结点在先序序列，中序序列和后序序列中的相对次序（   ）。

A．不发生改变　　B．发生改变  C．不能确定　D．以上都不对 

29.若对二叉树进行中序遍历，具有左、右子树的结点，其后继是该结点的（   ）。

A．双亲结点   B．其左子树中最右下角元素   C．其右孩子   D．其右子树中最左下角元素

30.在完全二叉树中，若一个结点是叶结点，则它没（   ）。

   A．左子结点   B．右子结点　 C．左子结点和右子结点   D．左子结点，右子结点和兄弟结点

31.一棵左子树为空的二叉树在先序线索化后，其中空的链域的个数是：

（   ）。

A．不确定        B.0       C.1       D.2  

32.一棵左右子树均不空的二叉树在先序线索化后，其中空的链域的个数是：

（   ）。

A.0           B.1       C.2         D.不确定

33.若X是二叉中序线索树中一个有左孩子的结点，且X不为根，则x的前驱为（   ）。

A.X的双亲 B.X的右子树中最左的结点 C.X的左子树中最右结点 D.X的左子树中最右叶结点

34.引入线索二叉树的目的是（   ）

A．加快查找结点的前驱或后继的速度  B．为了能在二叉树中方便的进行插入与删除

C．为了能方便的找到双亲     D．使二叉树的遍历结果唯一

35.n个结点的线索二叉树上含有的线索数为（   ）

A．2n     B．n－l      C．n＋l        D．n

36.设F是一个森林，B是由F变换得的二叉树。

若F中有n个非终端结点，则B中右指针域为空的结点有（   ）个。

A．n-1      B．n      C．n+1      D．n+2 

37.在叶子数目和权值相同的所有二叉树中，最优二叉树一定是完全二叉树，该说法（   ）。

 A．正确 B．错误

38.下述编码中哪一个不是前缀码（       ）。

A．（00，01，10，11） B．（0，1，00，11） C．（0，10，110，111） D．（1，01，000，001）

39.一棵有n个结点的二叉树，按层次从上到下，同一层从左到右顺序存储在一维数组A[1..n]中，则二叉树中第i个结点（i从1开始用上述方法编号）的右孩子在数组A中的位置是（   ）

A．A[2i]（2i<=n） B．A[2i+1]（2i+1<=n） C．A[i-2]  D．条件不充分，无法确定

40.从下列有关树的叙述中,选出5条正确的叙述（   ）。

A．二叉树中每个结点有两个子结点,而树无此限制,因此二叉树是树的特殊情况。

B．当