《数据结构与算法题库下发版.doc》由会员分享，可在线阅读，更多相关《数据结构与算法题库下发版.doc（57页珍藏版）》请在金锄头文库上搜索。
1、一、单选题知识点一：绪论1.设有如下遗产继承规则:丈夫和妻子可以互相继承遗产;子女可以继承父亲或母亲的遗产:子女间不能相互继承。则表示该遗产继承关系的最合适数据结构应该是( )。A树 B.图 C.数组 D.二叉树 2.设有一遗传关系:X是Y的父亲，X可以把它的属性遗传给Y。则表示该遗传关系最适合的数据结构为( )。A.向量 B.树 C.图 D.广义表 3.在数据结构中，从逻辑上可以把数据结构分成 ( )A.动态结构和静态结构 B.紧凑结构和非紧凑结构C.线性结构和非线性结构 D.内部结构和外部结构4.数据结构在计算机内存中的表示是指 ( )A.数据的存储结构B.数据结构 C.数据的逻辑结构D.
2、数据元素之间的关系 5. 计算机算法指( ) A.计算方法B.排序方法 C.解决问题的有限运算序列D.调度方法 6. 在以下的叙述中，正确的是 A.线性表的线性存储结构优于链表存储结构 B.二维数组是其数据元素为线性表的线性表 C.校的操作方式是先进先出 D.队列的操作方式是先进后出 7.在决定选取何种存储结构时，一般不考虑( ) A.各结点的值如何B.结点个数的多少 C.对数据有哪些运算D.所用编程语言实现这种结构是否方便 8. 在存储数据时，通常不仅要存储各数据元素的值，而且还要存储( )A.数据的处理方法B.数据元素的类型 C.数据元素之间的关系D.数据的存储方法 9.以下说法正确的是(
3、 ) A.数据元素是数据的最小单位 B.数据项是数据的基本单位C.数据结构是带结构的数据项的集合 D.一些表面上很不相同的数据可以有相同的逻辑结构 10设计一个“好”的算法应达到的目标为（ ）。A.正确性、可读性、健壮性及效率与低存储量需求 B.正确性、可读性、健壮性及有穷性C.正确性、可读性、健壮性及可行性 D.正确性、可读性、健壮性及确定性知识点二：线性表11.与线性表的链接存储相符的特性是( )。 A.插入和删除操作灵活 B.需要连续存储空间 C.便于随机访问 D.存储密度大12.在单向循环链表中，若头指针为h，那么p所指结点为尾结点的条件是( )。 A. p=NULL B. p-nex
4、t=NULL C. p=h D. p-next=h13.与线性表的链接存储不相符的特性是( )。 A.插入和删除操作灵活 B.需要连续的存储空间C.存储空间动态分配 D.需另外开辟空间来保存元素间的关系14.以h为头指针的带头结点的单向循环链表为空的条件是( )。 A. h=NULL B. h-next=NULL C. h-next=h D. h-next-next=h 15.与线性表的链式存储不相符合的特性是( )。 A插入和删除操作灵活B.需要连续的存储空间 C.存储空间动态分配D.非紧凑结构16. 链表不具备的特点是( )A.可随机访问任一结点B.插入删除不需要移动元素 C.不必事先估计
5、存储空间D.所需空间与其长度成正比 17. 带头结点的单链表head为空的判定条件是 ( )A. head = NULL B. head-next=NULL C. head-next = head D. head!=NULL 18.需要分配较大空间，插入和删除不需要移动元素的线性表，其存储结构 A.单链表B.静态链表c.线性链表D. 顶序存储结构 19. 如果最常用的操作是取第i个结点及其前驱，则采用存储方式最节省时间。 A.单链表B.双链表C.单循环链表D.顺序表 20. 在一个具有n个结点的有序单链表中插入一个新结点并仍然保持有序的 时间复杂度是 A. 0(1) B. O(n) C. 0(
6、n2) D. 0(nlog2n) 21. 与单链表相比，双链表的优点之一是 ( )A.插入、删除操作更简单 B.可以进行随机访问 C.可以省略表头指针或表尾指针 D.顺序访问相邻结点更灵活 22.一维数组和线性表的区别是 ( )A.前者长度固定，后者长度可变 B.后者长度固定，前者长度可变 C.两者长度均固定 D.两者长度均可变 知识点三：栈和队列23.若进队序列为1， 2， 3， 4，则出队序列是( )。 A. 4， 3， 2， 1 B. 1， 2， 3， 4 C. 1， 3， 2， 4 D.3， 2， 4， 124.设输入序列为1， 2， 3， 4借助一个栈不可能得到的输出序列是( )。
7、A.1， 2， 3， 4 B.4， 3， 2， 1 C.3， 4， 1， 2 D. 1， 3， 4， 225.若进栈序列为1，2，3,4则不可能得到的出栈序列为（ )。 A. 3， 2， 1， 4 B. 3， 2， 4， 1 C. 4， 2， 3， 1 D.2， 3， 4， 1 26.栈应用的典型事例是（ ）。A.排队 B.查找 C.归并 D.用“算符优先法”进行表达式求值27.栈和队列都是( )。 A.顺序存储的线性结构 B.链式存储的线性结构 C.限制存取点的线性结构 D.限制存取点的非线性结构28.对于顺序存储的队列，存储空间大小为n，头、尾指针分别为F和R，若将其看成一个首尾相接的圆环
8、，则队列中元素个数为( )。 A. R-F B. n+R-F C. C(R-F+1)%n D. (n+R-F)%n29.从一个顺序队列删除元素时，首先需要 。A. 前移一位队首指针 B. 后移一位队首指针C. 取出队首指针所指位置上的元素 D.取出队尾指针所指位置上的元素30. 假定一个顺序队列的队首和队尾指针分别为f 和r，则判断队空的条件为 。A. f+1=r B. r+1=f C. f=0 D. f=r31.初始为空的堆栈中依次插入元素:f 、e、d、c、b、a以后，连续进行了3次删除操作，此时的栈顶元素是（ ）。A.c B.d C.b D.e32在解决计算机主机与打印机之间速度不匹配问
9、题时通常设置一个打印数据缓冲区，这样主机将要输出的数据依次写入该缓冲区，而打印机则从该缓冲区中取出数据打印。该缓冲区应该是一个（ ）结构。A.堆 B.队列 C.数组 D.线性表33设一个栈的入栈序列是ABCD，则借助于一个栈所得到的出栈序列不可能是（ ）。A.ABCD B.DCBA C.ACDB D.DABC34设栈最大长度为3，入栈序列为1、2、3、4、5、6，则不可能的出栈序列是（ ）。A.1、2、3、4、5、6 B.2、1、3、4、5、6C.3、4、2、1、5、6 D.4、3、2、1、5、635设栈的输入序列是1，2，n，若输出序列的第一个元素是n，则第i个输出元素是（ ）。A.n-i+
10、1 B.i C.n-i D.前面都不正确知识点四：串36串的长度是（ ）。A.串中不同字母的个数 B.串中不同字符的个数C.串中所含数字的个数 D.串中所有字符的个数37（ ）是C语言中abcd32lABCD的子串。A.abed B.32lAB C.abcABC D.21AB 38串是（ ）。A.不少于一个字符的序列 B.有限个字符的序列C.不少于一个字母的序列 D.任意个字母的序列39设有两个串p和q，求q在p中首次出现的位置的运算称做( ) A.连接 B.模式匹配 C.求子串 D.求串长 40若串s=software ，其真子串(不含自身)的个数是 A.8 B.37 C.36 D.9 41
11、有串sl =ABCDEFG， s2=PQRST，假设函数con(x,y)返回x和y串的连接串，subs( s，i，j)返回串S的从序号i的字符开始的j个字符组成的子串， len(s)返回串S的长 度，则con( subs( s 1 ，2，len( s2) )，subs( s 1 ，len( s2 )，2)的结果串是 A.BCDEF B.BCDEFG C.BCPQRST D.CDEFGFG 42串是一种特殊的线性表，其特殊性体现在 ( )A.可以顺序存储B.数据元素是一个字符 C.可以链式存储D.数据元素可以是多个字符 知识点五：数组和广义表43.己知广义表A=(a，b)(c，d)，则head(
12、A)等于( )。 A. ( a，b ) B. ( a，b ) C. a， b D. a44. 设一个具有t个非零元素的m*n大小的稀疏矩阵采用顺序存储，求其转置矩阵的普通转置算法的时间复杂度为_ _。A. O(m) B. O(n) C. O(n+t) D. O(n*t)45一个三对角矩阵Ann已按行压缩存储到一维数组B中，则B的长度至少为（ ）。A.3n+1 B.3n C.3n-1 D.3n-246二维数组A1020采用列序为主方式存储，每个元素占1个存储单元， 并且AOO的存储地址是200，则A612的地址是( )A. 328 B. 327 C.326 D. 32947.多维数组的数组元素之
13、间的关系， A.是线性的B.是树形的 C.既是线性的，又是树形的D.既不是线性的，也不是树形的 知识点六：树和二叉树48.n个结点的二叉树，若用二叉链表作为存储结构，则非空闲的左、右孩子链域为 ( )。 A.n B. 2n C. n-l D. n+l 49.对于下边的二叉树，其中序序列为( )。 A. DBAFCG B. DBAFGC C. ABDCFG D. ABCDFG 50.在一棵二叉树上，第5层的结点数最多为( )。 A.8 B. 15 C. 16 D. 32 51.对于下面的二叉树，其中序序列为( )。 A. ABCDEFG B. ABDECFG C. DBEAFCG D. ADEBCFG 52n个结点的二叉树中，用二叉链表做存储，非空指针数目为( )。 A. n B. 2n C. n-1 D. n+1 53. 由权值分别为3,8,6,2,5的叶子结点生成一棵哈夫曼树，它的带权路径长度为_。A. 24 B. 48 C. 72 D. 5154.二叉树的先序
