数据结构题库(3)

第四章数组和串

1.串的长度是指 ( B ) 。

A．串中所含不同字母的个数 B．串中所含字符的个数

C．串中所含不同字符的个数 D．串中所含非空格字符的个数 2.串是任意有限个( B )

A.符号构成的序列 B.字符构成的序列 C.符号构成的集合 D.字符构成的集合 3.设矩阵A(aij,1<=i,j<=10)的元素满足:

aij<>0(i>=j,1<=i,j<=10),aij =0 (i

若将A的所有非0元素以行为主序存于首地址为2000的存储区域中，每个元素占4个单元,则元素A[5][9]的首地址为( C )

A.2340 B.2336 C.2220 D.2160

4.设有一个二维数组A[m][n]，假设A[0][0]存放位置在600(10)，A[3][3]存放位置在678(10)，每个元素占一个空间，问A[2][3](10)存放在什么位置？(脚注(10)表示用10进制表示,m>3)D

A．658 B．648 C．633 D．653 5. 字符串通常采用的两种存储方式是(C)

A. 散列存储和索引存储 B. 索引存储和链式存储

C. 顺序存储和链式存储 D. 散列存储和顺序存储

6.设主串长为n，模式串长为m(m≤n)，则在匹配失败情况下，朴素匹配算法进行的无效位移次数为(C)

A. m B. n-m C. n-m+1 D. n 7. 二维数组A［12］［18］采用列优先的存储方法，若每个元素各占3个存储单元，且第1个元素的地址为150，则元素A［9］［7］的地址为(A)

A. 429 B. 432 C. 435 D. 438

8.若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二分查找,则查找A［3］的比较序列的下标依次为( D )

A. 1，2，3 B. 9，5，2，3 C. 9，5，3 D. 9，4，2，3 9.如下陈述中正确的是（ A ）

A．串是一种特殊的线性表 B．串的长度必须大于零 C．串中元素只能是字母 D．空串就是空白串

10.数组Ｑ［ｎ］用来表示一个循环队列，ｆ为当前队列头元素的前一位置，ｒ为队尾元素的位置，假定队列中元素的个数小于ｎ，计算队列中元素的公式为(B) Ａ．r－f; B.（n＋f－r）% n; C.n-r+f Ｄ．（n＋r－f）% n

11．下列关于一维数组的说法，错误的是（D）

A一维数组又称为向量B一维数组既可以是逻辑结构也可以是物理结构

C一维数组可以通过下标直接访问D不用找到数据元素的存储地址就可以访问它的值

12．设矩阵A（aij ，l≤i,j≤ 10）的元素满足： aij≠0(i≥j, l≤i, j≤ 10) aij=0 (i

13.现将A的所有非0元素以行序为主序存放在首地址为2000的存储区域中，每个元素占有4个单元，则元素A[9][5]的首址为( D ) A2340 B、2336 C、2164 D、2160 14.数组通常具有的操作是（）。B

A.顺序存取B.直接存取C.散列存取D.索引存取

15.在二维数组中，每个数组元素同时处于（）个向量中。C

A． 0 B.1 C.2 D.n

16.多维数组实际上是由（）实现的。A

A.一维数组B.多项式C.三元组表D.简单变量

17.在二维数组A[8][10]中，每一个数组元素A[i][j]占用3个存储空间，所有数组元素相继存放于一个连续的存储空间中，则存放该数组至少需要的存储空间是（）。C

A.80 B.100 C.240 D.270

18.一个二维数组A[10][20]按行存放于一个连续的存储空间中，A[0][0]的存储地址是200，每个数组元素占1个存储单元，则A[6][2]的地址为（）。B

A.226 B.322 C.341 D.342

19.一个二维数组A[10][20]按列存放于一个连续的存储空间中，A[0][0]的存储地址是200，每个数组元素占1个存储单元，则A[6][2]的地址为（）。A

A.226 B.322 C.341 D.342 20.在二维数组A[9][10]中，每个数组元素占3个存储单元，从首地址SA开始按行连续存放。在这种情况下，元素A[][]的起始地址为（）。D

A.SA+141 B.SA+144 C.SA+222 D.SA+255 21.字符串可定义为n（n>=0）个字符的有限（），其中n是字符串的长度，表明字符串中字符的个数。C

A. 集合B.数列C.序列D.聚合

22.串是一种特殊的线性表，其特殊体现在（）。B

A.可以顺序存储B.数据元素是一个字符 C.可以链接存储D.数据元素可以是多个字符 23.有n个字符的字符串的非空子串个数最多有（）。D

A.n-1 B.n C.n(n-1)/2 D.n(n+1)/2 24.两个字符串相等的条件是（）。D

A. 两个串的长度相等 B. 两个串包含的字符相等

C. 两个串的长度相等，并且两个串包含的字符相同 D. 两个串的长度相等，并且对应位置上的字符相同

25.设有两个串T和P，求P在T中首次出现的位置的运算叫做（）。B

A.求子串B.模式匹配C.串替换D.串连接 26.在以下关于串的说法中正确的是（）。C

A. 空串是由空格组成的串

B. 子串是从串中抽取出若干字符组成的串

C. 用块链存储表示实现的串的结点大小为4，说明每个结点可存储4个字符 D. 串长度是指串中不同字符的个数

第五章树和二叉树应用

1.已知含10个结点的二叉排序树是一棵完全二叉树，该二叉排序树在等概率情况下查找成功的平均查找长度等于（ B）。

(A)1.0 (B)2.9 (C)3.4 (D)5.5 2. 下列四个序列中，哪一个是堆（ C ）。

A. 75,65,30,15,25,45,20,10 B. 75,65,45,10,30,25,20,15 C. 75,45,65,30,15,25,20,10 D. 75,45,65,10,25,30,20,15

3.从具有n个结点的二叉排序树中查找一个元素时,最坏情况下的时间复杂度为__A___. A) O(n) B) O(1) C) O(log2n) D) O(n2) 4.以下序列不是堆的是（D）。

A、100，85，98，77，80，60，82，40，20，10，66 B、100，98，85，82，80，77，66，60，40，20，10 C、10，20，40，60，66，77，80，82，85，98，100 D、100，85，40，77，80，60，66，98，82，10，20

5.分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是( C )。

A．（100，80， 90， 60， 120，110，130） B.（100，120，110，130，80， 60， 90） C.（100，60， 80， 90， 120，110，130） D. (100，80， 60， 90， 120，130，110) 6．设某二叉树中度数为0的结点数为N0，度数为1的结点数为Nl，度数为2的结点数为N2，则下列等式成立的是（C ）。 (A) N0=N1+1 (B) N0=Nl+N2 (C) N0=N2+1 (D) N0=2N1+l 7.设某哈夫曼树中有199个结点，则该哈夫曼树中有（ B）个叶子结点。 (A) 99 (B) 100 (C) 101 (D) 102

8.设二叉排序树上有n个结点，则在二叉排序树上查找结点的平均时间复杂度为（ B ）。

2

(A) O(n) (B) O(n) (C) O(nlog2n) (D) O(1og2n) 9.深度为6(根的层次为1)的二叉树至多有( B )结点 A.64 B.63 C.31 D.32

10.将含100个结点的完全二叉树从根这一层开始，每层从左至右依次对结点编号，根结点的编号为1。编号为47的结点X的双亲的编号为( C ) A.24 B.25 C.23 D.2无法确定

11.堆是一个键值序列{K1,K2,...,Ki,...,Kn},对i=1,2,...,└n/2 ┘，满足( A ) A. Ki<=K2i且Ki<=K2i+1(2i+1<=n) B.Ki

12.从具有 n 个结点的二叉排序树中查找一个元素时，在最坏情况下的时间复杂度为( C ).

A. O (n) B.O（1） C.O (log 2 n) D.O (n 2 )

13.由权值分别为3,8,6,2,5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（ D ）。

A 72 B 24 C 48 D 53

14.根据给定的序列（4,15,5,8,6,20,28,3,）构造二叉排序树。其平均查找长度ASL约为（ C ）。

A 4 B 5 C 3 D 6 15.已知有序顺序表为：5,15,21,30,33,40,43,51,64,75,87,92,98。在该顺序表上进行二分查找时，其二叉判定树的最低层的元素个数为（ C ）。 A 4 B 7 C 6 D 5

16.从二叉搜索树中查找一个元素时，其时间复杂度大致为（C）

A. O(N) B.O(1) c.O(log2n) D.O(n*n） 17.设二叉排序树中关键字由1至1000的整数构成，现要查找关键字为363的结点，下述关键字序列哪一个不可能是在二叉排序树上查找到的序列?（C）

(a) 2，252，401，398，330, 344，397，363; (b) 924, 220, 911, 244, 898, 258, 362, 363; (c) 925, 202, 911, 240, 912, 245, 363;

(d) 2, 399, 387, 219, 266, 382, 381, 278, 363.

18.下列关键字下列中，（D）是堆。

A.16,72,31,23,94,53 B.94,23,31,72,16,53 C.16,53,23,94,31,72 D.16,23,53,31,94,72

19.在含有n个关键字的小根堆（堆顶元素最小）中，关键字最大的记录有可能存储在（D ）位置上。

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

20.已知8个元素为{34，76，45，18，26，54，92，65}，按照依次插入结点的方法生成一棵二叉排序树，最后两层上结点的总数为（B）。 A．1 B．2 C．3 D．4

21.用自底向上的方式可以构造出最有二叉查找树，但算法的时间复杂度达到（C）

23

A:O(n) B:O(n) C:O(n) D:O（1） 22.（ B ）二叉排序树可以得到一个从小到大的有序序列。 A 先序遍历 B 中序遍历 C 后序遍历 D 层次遍历

23.设按照从上到下、从左到右的顺序从1开始对完全二叉树进行顺序编号，则编号为i结点的左孩子结点的编号为（ B ）。

A 2i+1 B 2i C i/2 D 2i-1

24.设某棵二叉树的高度为10，则该二叉树上叶子结点最多有（C ）。 A 20 B 256 C 512 D 1024

25.二叉树为二叉排序树的充分必要条件是其任一结点的值均大于其左孩子的值、小于其右孩子的值。这种说法（ B ）。 A．正确 B. 错误

26.下列关于二叉树遍历的叙述中，正确的是( AD ) 。 A. 若一个树叶是某二叉树的中序遍历的最后一个结点，则它必是该二叉树的前序遍历最后一个结点

B．若一个点是某二叉树的前序遍历最后一个结点，则它必是该二叉树的中序遍历的最后一个结点

C．若一个结点是某二叉树的中序遍历的最后一个结点，则它必是该二叉树的前序最后一个结点

D．若一个树叶是某二叉树的前序最后一个结点，则它必是该二叉树的中序遍历最后一个结点

27.k层二叉树的结点总数最多为( A ).

A2k-1 B.2K+1 C.2K-1 D. 2k-1445、对线性表进行二

28.由同一关键字集合构造的各棵二叉排序树(B) A. 其形态不一定相同，但平均查找长度相同

B. 其形态不一定相同，平均查找长度也不一定相同 C. 其形态均相同，但平均查找长度不一定相同 D. 其形态均相同，平均查找长度也都相同 29．二叉树是非线性数据结构，所以。 （ C ）

（Ａ）它不能用顺序存储结构存储; （Ｂ）它不能用链式存储结构存储;

（Ｃ）顺序存储结构和链式存储结构都能存储; （Ｄ）顺序存储结构和链式存储结构都不能使用

30．把一棵树转换为二叉树后，这棵二叉树的形态是。 （ A ） （Ａ）唯一的（Ｂ）有多种

（Ｃ）有多种，但根结点都没有左孩子（Ｄ）有多种，但根结点都没有右孩子 31. 下面描述根树转换成二叉树的特性中，正确的是 (C) 。

A、根树转换成的二叉树是唯一的，二叉树的根结点有左、右孩子。

B、根树转换成的二叉树是不唯一的，二叉树的根结点只有左孩子。 C、根树转换成的二叉树是唯一的，二叉树的根结点只有左孩子。 D、根树转换成的二叉树是不唯一的，二叉树的根结点有左、右孩子。

32．.某二叉树先序遍历的结点序列是abdgcefh，中序遍历的结点序列是dgbaechf，则其后序遍历的结点序列是 ( D ) 。

A、bdgcefha B、gdbecfha C、bdgaechf D、gdbehfca

33． 设n，m为一棵二叉树上的两个结点，在中序遍历时，n在m前的条件是( C ) 。 A、n在m右方 B、n是m祖先 C、n在m左方 D、n是m子孙

34． 二叉树第i 层结点的结点个数最多是（设根的层数为1）( A ) A）2i-1 B）2i-1 C）2*i D） 2*i-1 35．树最适合用来表示?。

A. 有序数据元素 B. 无序数据元素

C. 元素之间具有分支层次关系的数据 D. 元素之间无联系的数据

36．设哈夫曼树中的叶子结点总数为m，若用二叉链表作为存储结构，则该哈夫曼树中总共有（ B ）个空指针域。

(A) 2m-1 (B) 2m (C) 2m+1 (D) 4m

37．设某棵二叉树的中序遍历序列为ABCD，前序遍历序列为CABD，则后序遍历该二叉树得到序列为（ A ）。

(A) BADC (B) BCDA (C) CDAB (D) CBDA

38.一棵具有35个结点的完全二叉树的高度为( )。假定空树的高度为一1。 A．5 B．6 C．7 D．8

39.在二叉树中某一结点的深度为3，高度为4，该树的高度至少为（ B）。 A.5 B.6 C.7 D.8

40．一棵有n个结点的树的所有结点的度数之和为（A）。 A.n-1 B.n C.n+1 D.2n

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

A．所有的结点均无左孩子 B．所有的结点均无右孩子

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库数据结构题库(3)在线全文阅读。