数据的逻辑结构与数据元素本身的内容和形式无关

1、客观题第一章 绪论一、判断题(1）数据的逻辑结构与数据元素本身的内容和形式无关。 (2）数据元素是数据的最小单位。 (3）算法是对解题方法和步骤的描述。 (4）程序和算法原则上没有区别，在讨论数据结构时可以通用。 (5）从逻辑关系上讲，数据结构主要分为线性结构和非线性结构两类。 (6）数据的存储结构是数据的逻辑结构的存储映像。二、选择题 (l）数据结构通常是研究数据的（ ）及它们之间的相互联系。 A存储结构和逻辑结构 B存储和抽象 C联系和抽象 D联系与逻辑 (2) 下列与数据元素有关的叙述中错误的是（ ）。A数据元素是有独立含义的数据最小单位 B数据元素是描述数据的基本单位 C数据元素可以称

2、做结点 D数据元素可以称做记录 (3）数据结构中，在逻辑上可以把数据结构分成：( ）。 A动态结构和静态结构 B紧凑结构和非紧凑结构 C线性结构和非线性结构 D内部结构和外部结构(4）数据在计算机存储器内表示时，物理地址和逻辑地址相同并且是连续的，称之为 ( ）。 A存储结构 B逻辑结构 C顺序存储结构 D链式存储结构(5）非线性结构的数据元素之间存在（ ）。 A一对一关系 B一对多关系 C多对多关系 D. B 或 C(6）在非线性结构中，每个结点（ ）。 A. 无直接前驱 B只有一个直接前驱和个数不受限制的直接后继 C只有一个直接前驱和直接后继 D有个数不受限制的直接前驱和直接后继 (7）除

3、了考虑存储数据结构本身所占用的空间外，实现算法所用的辅助空间的多少称为算法的（ ）。 A时间效率 B空间效率 C硬件效率 D软件效率 (8)以下属于顺序存储结构优点的是（ ）。 A存储密度大 B插入运算方便 C删除运算方便 D可方便地用于各种逻辑结构的存储表示 (9)数据结构研究的内容是（ ）。 A数据的逻辑结构 B数据的存储结构 C建立在相应逻辑结构和存储结构上的算法 D包括以上三个方面 (10)链式存储的存储结构所占存储空间（ ）。 A分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针 B只有一部分，存放结点值 C只有一部分，存储表示结点间关系的指针 D分两部分，一部分存放结点值

4、，另一部分存放结点所占单元数(11)一个正确的算法应该具有 5 个特性，除输入、输出特性外，另外 3 个特性是（ ）。 A确定性、可行性、有穷性 B易读性、确定性、有效性 C有穷性、稳定性、确定性 D可行性、易读性、有穷性 (12)以下关于数据的逻辑结构的叙述中正确的是（ ）。 A数据的逻辑结构是数据间关系的描述 B数据的逻辑结构反映了数据在计算机中的存储方式 C数据的逻辑结构分为顺序结构和链式结构 D数据的逻辑结构分为静态结构和动态结构 (13)设问题的规模为 n ，分析以下程序段： k = n ; /* n l */m = 0 ;while ( k = ( m + l ) * ( m -

5、l ) ) m +；以上程序段的算法时间复杂度是( ) A. O( n ) B. O(1) C. O() D. O( n2 )(14)设问题的规模为n ，分析以下程序段：a = 10 ; b = l00 ; while （b 0 ) a + + ; b ； 以上程序段的算法时间复杂度是（ ）。A.O( n ) B. O(1) C. O() D. O( n2 )(15)设语句 s=s+i 的时间是单位时间，则语句： s=0; for (i=l;inextP C.P-next= =NULL D. P-nextL (19)指针 P 所指的元素是双循环链表 L 的尾元素的条件是（ ）。 A. PL B

6、. P-priorL C. PNULL D. P-nextL (20)不带头结点的单链表L为空的条件是( )A. L!NULL B. LNULL C. L-nextNULL D. L-nextL(21)带头结点的单链表L为空的条件是( )A. L!NULL B. LNULL C. L-nextNULL D. L-nextL(22)两个指针 P 和 Q ，分别指向单链表的两个元素， P 所指元素是 Q 所指元素前驱的条件是（ ）。 A. P-nextQ-next B. P-nextQ C. Q-nextP D. PQ (23)在长度为 n 的顺序表中，若要删除第 i (1in ）个元素，则需要向

7、前移动元素的次数为（ ）。 A. 1 B. n 一 i C. n 一 i + 1 D. n 一 i 一 l (24)在长度为 n 的顺序表中第 i (1in）个位置上插入一个元素时，为留出插入位置所需移动元素的次数为（ ）。A. n - i B. i C. n i + 1 D. n - i - l (25)假定己建立以下动态链表结构，且指针 Pl 和 P2 已指向如图所示的结点：则以下可以将 P2 所指结点从链表中删除并释放该结点的语句组是( ) A. pl - next = p2 - next ; free ( pl ) ; B. pl = p2 ; free ( p2 ) ;C. pl -

8、 next = p2 - next ；free ( p2 ) ; D. pl = p2 - next ; free ( p2) ; (26)若已建立如图所示的单向链表： 则以下不能将 s 所指的结点插入到链表尾部，构成新的单向链表的语句组是（ ）。 A. s一next = a - next 一next ; a - next - next = s ;B. a = a - next; a 一next =s ; s 一next = NULL ;C. s 一next = NULL ; a = a一 next; a一 next = s ;D. a = a 一next ; s 一next = a 一nex

9、t ; a - next = s 一 next ;(27)有如下函数： Void fun( struct node * hl , struct node * h2 ) struct node * t ; t = hl ; while ( t - n ext ! 0 ) t = t 一 next ; t - next = h2 ; 其中形参 hl 和 h2 分别指向 2 个不同链表的第一个结点，此函数的功能是（ ）。 A将链表 h2 接到链表 h1 后 B将链表 h1 接到链表 h2 后 C找到链表 hl 的最后一个结点由指针返回 D将链表 hl 拆分成两个链表 第三章 栈一、判断题 (l）栈是

10、运算受限制的线性表。 (2）在栈空的情况下，不能作出栈操作，否则产生溢出。 (3）栈一定是顺序存储的线性结构。 (4）空栈就是所有元素都为0的栈。 (5) 不管堆栈采用何种存储结构，只要不为空，就可以任意的删除数据元素。(6) 在 c语言中设顺序栈的长度为 MAXLEN ，则 top = MAXLEN 时表示栈满。 (7）一个栈的输入序列为：A, B, C, D，可以得到输出序列： C, A, B, D。二、选择题 (1)设用一维数组元素 a1-an存储一个栈，令 an为栈底，用整型变量 t 指示当前栈顶位置， at为栈顶元素。当从栈中弹出一个元素时，变量 t 的变化为（ ）。 At=t +

11、1 Bt=t-1 C. t 不变 D t=n(2)有 6 个元素按 6 、 5 、 4 、 3 、 2 、 1 的顺序进栈，进栈过程中可以出栈，则以下可能的出栈序列是（ ）。 A . 1 、 4 、 3 、 5 、 2 、 6 B . 6 、 5 、 4 、 3 、 2 、 l C . 3 、 l 、 4 、 2 、 6 、 5 D . 3 、 6 、 5 、 4 、 2 、 l(3)以下叙述中错误的是（ ）。 A栈是限制存取操作只能在一端进行的线性表 B消除递归不是必须使用栈 C对同一组输入序列进行合法的入、出栈操作，得到的输出序列一定相同 D实现递归必定使用工作栈 (4)以下不属于栈的基本

12、运算的是（ ）。 A删除栈顶元素 B删除栈底元素 C判断栈是否为空 D将栈置为空栈 (5)若以链表作为栈的存储结构，则退栈操作时（ ）。 A必须判别栈是否满 B必须判别栈元素的类型 C必须判别栈是否空 D不用作任何判别 (6)设入栈序列是 1 、 2 、 、 n ，入栈过程中不允许中途出栈，则第 i 个输出的元素是 ( ）。 A不确定 B.i C. n - i D. n - i + 1 (7)铁路调度用“栈”，假设进栈车厢编队序列为“ ABC （进栈过程中可以出栈），出栈则有许多编队序列，以下不可能出现的序列是（ ）。 A. ABC B. CBA C. BAC D. CAB (8)当栈中当前元

13、素为 n 个，此时进行进栈运算时发生上溢，则该栈的最大容量为（ ）。 A. n/2 B. n 一 1 C. n D. n + 1 (9)在栈中存取数据的原则是（ ）。 A先进先出 B后进先出 C后进后出 D随意进出 (10)插入和删除只能在一端进行的线性表，称为（ ）。 A队列 B循环队列 C栈 D. 循环栈 (11)在栈中，出栈操作的时间复杂度为（ ）。 A. O(l) B. O(log2n) C. O(n) D. O(n2) (12)顺序栈为空的判断条件是（ ）。A. top=0 B. top=1 C. top=-1 D. top=m(13)元素 A, B, C, D依次进栈以后，栈顶元素

14、是（ ）。 A. A B. B C. C D. D (14)顺序栈存储空间的实现使用（ ）存储栈元素。 A链表 B数组 C循环链表 D变量 (15)一个顺序栈一但说明，其占用空间的大小（ ）。 A已固定 B可以变动 C不能固定 D动态变化 (16)链栈 LS 的示意图如下，栈顶元素是（ ）。第四章 队列一、判断题(l）队列是限制在两端进行操作的线性表。(2）判断顺序队列为空的标准是头指针和尾指针均指向同一个结点。 (3）在链队列做出队操作时，会改变 front 指针的值。 (4）在循环队列中，若尾指针rear大于头指针front, 其元素个数为rear-front 。(5）队列是一种“后进先出

15、”的线性表。 (6）在单向循环队列中，若头指针为h，那么p所指的结点为尾结点的条件是p=h 。二、选择题 (1)若用单链表来表示链队列，则应该选用（ ）。 A带尾指针的非循环链表 B带头指针的非循环链表 C带尾指针的循环链表 D带头指针的循环链表 (2)设有一个空队列，若进入队列的序列为 1 , 2 , 3 , 4 ，则合法的出队序列是（ ）。 A. 3 , 2 , 4 , 1 B. 4 , 2 , 3 , l C. 4 , 3 , 2 , 1 D. l , 2 , 3 , 4 (3)若利用数组 a0an-1作为一个循环队列， f 为当前队头元素的前一个位置，r为队尾元素的位置，假定队中元素的

16、个数总是小于 n ，则当前队中元素的个数为（ ）。 A. r 一 f B. n + f 一 r C. n + r 一1 D. ( n + r 一 f) % n (4)栈和队列都是（ ）。 A顺序存储的线性结构 B链式存储的线性结构 C限制存取点的线性结构 D限制存取点的非线性结构 (5)以下不属于队列基本运算的是（ ）。 A从队尾插入一个新元素 B从队列中删除第 i 个元素 C判断一个队列是否为空 D读取队头元素的值(6)在队列的顺序存储结构中，会产生队列中有剩余空间，但确不能执行入队操作的“假溢出”现象，在以下几种方法中，不能解决假溢出问题的是（ ）。 A采用首尾相接的循环队列 B当有元素入

17、队时，将己有元素向队头移动 C当有元素出队时，将己有元素向队头移动 D申请新的存储单元存放入队元素 (7)设队列空间 n=40 ：队尾指针 rear=6 ；队头指针 front = 25 ，则此循环队列中当前元素的数目是（ ）。 A. 19 B. 21 C. 11 D. 29 (8)设循环队列的队首指针用 front 表示，队尾指针用 rear 表示，则判断队空的条件是( )A. front = = rear Bfront+1 = = rear C. rear+1=front D.rear= =0(9)设循环队列存储于数组元素 a1an中，其队头和队尾指针分别用front和 rear 表示，则

18、判断队满的条件是（ ）。 A. ( rear 一 1 ) % n = front B. ( front + 1 ) % n = = rearC. ( rear + 1 ) % n = =front D. ( front 一 l ) % n = = rear (10)循环队列的特点之一是不会产生（ ）。 A上溢出 B下溢出 C队满 D假溢出 (11)设用数组 datam + l作为循环队列 q 的存储空间， front 为队头指针， rear 为队尾指针，则执行出队操作应执行的语句是（ ）。 A. front = front + 1 ; B. front = ( front + l ) % (

19、m + l ) ; C. rear=（ rear + l ) % m ; D. front = ( front + l ) % m ; (12)在队列中存取数据应遵循的原则是（）。A先进先出 B后进先出 C先进后出 D. 随意进出(13)设长度为 n 的链队列用单循环链表表示，若只设头指针，则入队操作的时间复杂度为 ( ）。A. O( l ) B. O(log2n ) C. O(n) D. O(n2)(14)设长度为 n 的链队列用单循环链表示，若只设尾指针，则出队操作的时间复杂度为（ ）。A. O( l ) B. O(log2n ) C. O(n) D. O(n2) (15)队列是限定在（

20、）进行操作的线性表。 A中间 B队头 C队尾 D端点 (16)一个循环队列一旦说明，其占用空间的大小（ ）。 A已固定 B可以变动 C不能固定 D动态变化 (17)在一个顺序存储的循环队列中，队头指针指向队头元素的（）位置。A前一个 B后一个 C后面 D当前 (18)当利用大小为 n 的数组顺序存储一个队列时，该队列的最后一个元素的下标为（ ）。A. n-2 B. n-1 C. n D.n+1(19)从一个顺序循环队列中删除一个元素时，首先需要做的操作是（ ) 。A队头指针减 1 B. 取出队头指针所指的元素C队头指针加 1 D. 取出队尾指针所指的元素(20)若 4 个元素按 A, B, C

21、, D，顺序进队 Q ，队头元素是（ )。A. A B. B C. C D. D第五章 串一、判断题(1)串中任意个字符组成的子序列称为该串的子串。(2)设 S 串的长度为 n ，子串的长度为 m ，那么子串定位算法的平均时间复杂度在最好情况下是0 ( n + m ）。(3)在顺序存储结构中，串的插入算法是非常方便的。(4)设有两个串s1和s2，其中s2是s1的子串，把s2在 s1中首次出现的位置找出来的算法叫作求子串的算法。(5) 空串是任意串的子串。(6）串的长度是指串中不同字符的个数。 (7）串是 n 个字母的有限序列。 (8）空串不等于空白串。 (9）如果两个串含有相同的字符，则说明它

22、们相等。 (10）如果一个串中所有的字符均在另一个串中出现，则说明前者是后者的子串。 二、选择题 (1)下面关于串的叙述中，错误的是（ ）。 A串是由字符组成的有限序列 B模式匹配是串的一种主要运算C空串是由空格组成的串 D串可以顺序存储，也可以链式存储 (2)假设有两个字符串S1和S2,其中 Sl = ABCDXYZ , S2= REST，那么如果进行了下面的运算concatstr ( substr (S1, 3 , 2 ) , Substr (S1, Strlen ( S2 ) , 3 ) ) ，其结果应是（ ）。 A. CDXYZ B. CDDXY C. CDREST D. CDRES

23、(3)设有一个字符串 S = ABC 123 XYZ ，问该串的长度为（ ）。 A. 9 B. 10 C. 11 D. 12 (4)设有一个字符串 S = windows ，其子串的数目是（ ）。 A. 25 个 B. 26 个 C. 27 个 D. 28 个 (5)串是一种特殊的线性表，其特殊性表现在（ ）。 A串中允许有空串 B串可以顺序存储 C串可以链式存储 D数据元素是一个字符 (6)设有S1, S2, S3, S4, S5, S6六个字符串，其值分别为: S1 = It is a book ，S2， S3 = t is , S4 = boot , s5 = , S6 = It is

24、，则在 S2 , S3 , S4 , S5 , S6 中，属于字符串S1 的子串的是（ ）。 A. S2 , S3 , S5 , S6 B. S3 , S6 C. S2 , S3 , S5 D. S3 , S5 , S6 (7)设有两个串 p 和 q ，求 q 在 p 中首次出现的位置的运算称作（ ）。 A连接 B模式匹配 C求子串 D求串长(8)设两个字符串的串值分别为 s1=ABCDEFG , s2=PQRST ，则ConcatStr (SubStr(s1,2,LenStr(s2),SubStr(s1,LenStr(s2),2)）的结果串（ ）。 A. BCDEF B. BCDEFG C.

25、 BCPQRST D. BCDEFEF(9)串是（ ）。 A不少于一个字母的序列 B任意个字符的序列 C不少于一个字符的序列 D有限个字符的序列 (10)以下论断正确的是（ ）。 A. 是空串， 空格串 B. beijing是bei jing的子串 C. somethingSomethig D. BIT = = BITE (11)若字符串ABCDEFG采用链式存储，假设每个字符占用 1 个字节，每个指针占用 2 个字节。则该字符串的存储密度为（ ）。 A. 20% B. 40% C. 50% D. 33.3% (12)上题若需提高存储密度至50% ，则每个结点应存储（ ）个字符（假设字符串的结

26、束标志也占用 1 个字节）。A. 2 B. 3 C. 4 D. 5(13)某串的长度小于一个常数，则采用（）存储方式最节省空间。 A 链式 B 顺序 C堆结构 D无法确定(14)在实际应用中，要输入多个字符串，且长度无法预定，则应该采用（ ）存储方式比较合适。 A 链式 B 顺序 C堆结构 D无法确定第六章 树和二叉树一、判断题(1)树结构中每个结点最多只有一个直接前驱。(2)二叉树中每个结点的度最大为 2 ，因此二叉树是一种特殊的树。(3)由树转化为二叉树，其根结点的右子树总是空的。 (4)若有一个结点是某二叉树的前序遍历序列中的第一个结点，则它也一定是这棵二叉树的中序遍历序列中的第一个结点

27、。(5)若一个树叶是某二叉树的前序遍历序列中的最后一个结点，则它也一定是这棵二叉树的中序遍历序列中的最后一个结点。 (6)若一个树叶是某二叉树的中序遍历序列中的最后一个结点，则它也一定是这棵二叉树的前序遍历序列中的最后一个结点。 (7)若有一个结点是某二叉树的前序遍历序列中的第一个结点，则它也一定是这棵二叉树的后序遍历序列中的最后一个结点。 (8)在二叉树中，具有一个子女的父结点，在中序遍历序列中没有后继结点。而具有两个子女的父结点，在中序遍历序列中，它的后继结点最多只能有一个子女结点。 (9)虽然已知二叉树的前序遍历和中序遍历序列，但还不能惟一确定出这棵二叉树，因为并不知道二叉树的根结点是哪

28、一个。 (10)中序线索二叉树的优点之一是便于在中序下查找前驱结点和后继结点。 (11)二叉树中一旦插入了结点，则该二叉树就不再是二叉树。(12)用一维数组存储二叉树时，总是以前序遍历存储结点。 (13)在满二叉树中，存在度为 1 的结点。 (14)在任意一棵二叉树中，终端结点的个数等于度为 2 的结点个数加 1 。 (15)哈夫曼树是带权值的树，且权值较大的结点离根较近。 (16)前序遍历序列与中序遍历序列完全相同的二叉树有：空二叉树或任一结点均无左子树的非空二叉树。(17)中序遍历序列与后序遍历序列完全相同的二叉树有：空二叉树或任一结点均无右子树的非空二叉树。 (18)前序遍历序列与后序遍

29、历序列完全相同的二叉树只有空二叉树。(19）完全二叉树一定是满二叉树。 (20）在中序线索二叉树中，右线索若不为空，则一定指向其双亲。 (21）在前序遍历二叉树的序列中，任何结点的子树的所有结点都是直接跟在该结点之后。 (22）二叉树按某种顺序线索后，任一结点均有指向其前驱和后继的线索。 (23）二叉树的前序遍历中，任意一个结点均处于其子树结点的前面。二、选择题 (1)深度为 h 的二叉树至多有（ ）个结点。 A. 2h B. 2h-1 C. 2h-1 D. 2h-1-1(2)对于二叉树来说，第 K 层至多有（ ）个结点。 A. 2K B. 2K-1 C. 2K-1 D. 2K-1-1(3)结

30、点前序为 ABC 的不同二叉树有（ ）种形态。 A. 3 B. 4 C. 5 D. 6(4)某二叉树的先序遍历序列为： IJKLMNO，中序遍历序列为：JLKINMO，则后序遍历序列为（ ）。A. JLKMNOI B. LKNJOMI C. LKJNOMI D .LKNOJMI(5)某二叉树的后序遍历序列为：DABEC, 中序遍历序列为：DEBAC，则先序遍历序列为（ ）。A. ACBED B.DECAB C.DEABC D.CEDBA(6)具有 35 个结点的完全二叉树的深度为（ ）。 A. 5 B. 6 C. 7 D. 8 (7)二叉树按某种顺序线索化后，任一结点均有指向其前驱和后继的线索

31、，这种说法 ( )。 A正确 B错误 C.不确定 D都有可能 (8)根据树的定义，具有 3 个结点的树有（ ）种树型。 A. 2 B. 3 C. 4 D. 5 (9)下列 4 棵树， ( )不是完全二叉树。(10)树最适合用来表示（ ）。 A有序数据元素 B无序数据元素 C元素之间无联系的数据 D元素之间有分支层次的关系 (11)对于一棵满二叉树，m个树叶， n个结点，深度为h ，则（ ）。 A. n=h+m B. h+m=2n C. m=h-1 D. n=2h-l (12)一棵 n 个结点的二叉树，其空指针域的个数为（ ）。 A. n B. n+l C. n-1 D不确定 (13)任何一棵二

32、叉树的叶子结点在前序、中序、后序遍历序列中的相对次序（ ）。 A不发生改变 B发生改变 C不能确定 D以上都不对 (14)A, B为一棵二叉树上的两个叶子结点，在中序遍历时， A 在 B 前的条件是（ ）。 A. A在B的右方 B. A是B的祖先 C. A在B的左方 D. A是B的子孙(15)线索二叉树是一种（ ）结构。 A.物理 B逻辑 C逻辑和存储 D线性(16)如果结点 A 是结点 B 的双亲，而且结点 B 有 4 个兄弟，则结点 A 的度是（ ）。 A. 2 B. 3 C. 4 D. 5 (17)设有一棵二叉树，其 1 度结点有 m 个， 2 度结点有 n 个，则该二叉树的结点总数为

33、( ）。 A. m + n B. 2 * m + n C. m + 2 * n D. m + 2 * n + l (18)设有一棵二叉树，其先序遍历序列是： ABCDEFG ，中序遍历序列是： CBDAFEG , 则该二叉树的后序遍历序列是（ ）。 A. CDBFGEA B. CDFGBEA C. CDBAFGE D. CDBFEGA (19)设有一棵树的度为 4 ，其中度为 1 、 2 、 3 、 4 的结点个数分别为 4 、 2 、 1 、 1 ，则这棵树中叶子结点的个数为（ ）。 A. 5 B. 6 C. 7 D. 8 (20)用顺序存储结构将完全二叉树的结点逐层存放在数组 Bn中，其根

34、结点从 B1开始存放，若结点 Bi有子女，则其左孩子结点应是（ ）。 A. B 2i 一 l B. B 2i + l C. B 2i D. B i / 2 (21)设森林 F 中有三棵树，第一、第二和第三棵树的结点个数分别为 a , b 和 c ，对应的二叉树根结点的右子树上的结点个数是（ ）。 A. a B. a + b C. c D. b + c (22)设有 13 个值，由它们组成一棵哈夫曼树，则该哈夫曼树中结点个数共有（ ）。 A. 13 B. 12 C. 26 D. 25 (23)设电文中出现的字母为 A 、 B 、 C 、 D 和 E ，每个字母在电文中出现的次数分别为： 6 ,

35、23 , 3 , 5 和 12 ，按哈夫曼编码，则字母 C 的编码应是（ ）。 A. 10 B. 110 C. 1110 D. 1111 (24)设树中有一结点 x ，在先根序列中的序号为 Pre ( x ) ，在后根序列中的序号为 post ( x ) , 若树中的结点 x 是结点 y 的祖先，则下列 4 个条件中正确的是（ ）。 A. pre ( x ) pre ( y ）且 post ( x ) post ( y ) B. pre ( x ) post ( y ) C. Pre ( x ) pre ( y ）且 post ( x ) pre ( y ）且 post ( x ) P ost ( y ) (25)有关二叉树的下列说法正确的是（ ）。 A二叉树的度为 2 B二叉树中任何一个结点的度都为 2 C一棵二叉树的度可以小于 2 D任何一棵二叉树中至少有一个结点的度为 2 (26)已知一棵二叉树的先序遍历序列为 EFHIGJK ，中序遍历序列为 HFIEJGK ，则该二叉树根的右子树的根是（ ）。 A. E B. F C. G D. J(27)在完全二叉树中，如果一个结点是叶子结点，