当前位置：文档之家 › 数据结构题库

数据结构题库

  • 格式：doc
  • 大小：160.00 KB
  • 文档页数：9

线性结构题 1. 栈和队列的共同特点是( A )。 (A) 只允许在端点处插入和删除元素 (B) 都是先进后出 (C) 都是先进先出 (D) 没有共同点 2. 以下数据结构中哪一个是非线性结构？( D ) (A) 队列 (B) 栈 (C) 线性表 (D) 二叉树 3. 设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每个元素占一个空间，问A[3][3](10)存放在( C )位置。脚注(10)表示用10进制表示。 (A) 688 (B) 678 (C) 692 (D) 696

4．设某数据结构的二元组形式表示为A=(D，R)，D={01，02，03，04，05，06，07，08，09}，R={r}，r={<01，02>，<01，03>，<01，04>，<02，05>，<02，06>，<03，07>，<03，08>，<03，09>}，则数据结构A是（ B ）。 (A) 线性结构 (B) 树型结构 (C) 物理结构 (D) 图型结构 5．下面程序的时间复杂为（ B ） for（i=1，s=0； i<=n； i++） {t=1；for(j=1；j<=i；j++) t=t*j；s=s+t；} (A) O(n) (B) O(n2) (C) O(n3) (D) O(n4) 6.下列程序段的时间复杂度为（ A ）。 i=0，s=0； while (s(A) O(n1/2) (B) O(n1/3) (C) O(n) (D) O(n2) 7. 为解决计算机主机与打印机之间速度不匹配的问题，通常设置一个打印数据缓冲区。主机将要打印输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是（ B ） (A)栈 (B)队列 (C)树 (D)图 8． 已知二级数组a[50][40]按行序为主序存放，每个元素占4个字节空间，若数组a的首元素a[1][1]地址为2012，计算a[23][21]的内存地址为（ B ）。 (A)5600 (B)5612 (C)2912 (D)3600 9．设输入序列为1、2、3、4、5、6，则通过栈的作用后可以得到的输出序列为（ B ）。 (A) 5，3，4，6，1，2 (B) 3，2，5，6，4，1 (C) 3，1，2，5，4，6 (D) 1，5，4，6，2，3 10．设有一个10阶的下三角矩阵A（包括对角线），按照从上到下、从左到右的顺序存储到连续的55个存储单元中，每个数组元素占1个字节的存储空间，则A[5][4]地址与A[0][0]的地址之差为（ B ）。 (A) 10 (B) 19 (C) 28 (D) 55 11．广义表A=（a,b（c,d）,(e,(f,g))），则head(tail(head(tail(tail(A)))))值为（ D ） (A)（g） (B)(d) (C)(c) (D)(d) 12．数据的最小单位是（ A ）。 (A) 数据项 (B) 数据类型 (C) 数据元素 (D) 数据变量 13．函数substr(“DATASTRUCTURE”，5，9)的返回值为（ A ）。 (A) “STRUCTURE” (B) “DATA” (C) “ASTRUCTUR” (D) “DATASTRUCTURE” 14．在线性表中，一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（ A ）。 （A）110 （B）108 （C）100 （D）120 15．栈中元素的进出原则是（ B ）。 （Ａ）先进先出 （B）后进先出 （Ｃ）栈空则进 （Ｄ）栈满则出

16．设指针q指向单链表中结点A，指针p指向单链表中结点A的后继结点B，指针s指

向被插入的结点X，则在结点A和结点B插入结点X的操作序列为（ B ）。 (A) s->next=p->next；p->next=-s； (B) q->next=s； s->next=p； (C) p->next=s->next；s->next=p； (D) p->next=s；s->next=q； 非线性结构 1.具有n(n>0)个结点的完全二叉树的深度为 C 。 (Ａ) log2(n) (Ｂ)  log2(n) (Ｃ)  log2(n) +1 (Ｄ) log2(n)+1 2.树最适合用来表示( C )。 (A) 有序数据元素 (B) 无序数据元素 (C) 元素之间具有分支层次关系的数据 (D) 元素之间无联系的数据 3.二叉树的第k层的结点数最多为( D ). (A) 2k-1 (B) 2K+1 (C) 2K-1 (D) 2k-1

4．设一棵完全二叉树有700个结点，则共有( D )个叶子结点。 （A）200 （B）250 （C）300 （D）350 5.若有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 6.对n个记录的文件进行快速排序，所需要的辅助存储空间大致为( C ) (A) O（1） (B) O（n） (C) O（1og2n） (D) O（n2）

7．设一组初始关键字记录关键字为(20，15，14，18，21，36，40，10)，则以20为基准记录的一趟快速排序结束后的结果为( A )。 (A) 10，15，14，18，20，36，40，21 (B) 10，15，14，18，20，40，36，21 (C) 10，15，14，20，18，40，36，2l (D) 15，10，14，18，20，36，40，21 8．设无向图G中有n个顶点e条边，则其对应的邻接表中的表头结点和表结点的个数分别为（ D ）。 (A) n，e (B) e，n (C) 2n，e (D) n，2e 9．设有5000个待排序的记录关键字，如果需要用最快的方法选出其中最小的10个记录关键字，则用下列（ B ）方法可以达到此目的。 (A) 快速排序 (B) 堆排序 (C) 归并排序 (D) 插入排序 10.下列四种排序中（ D ）的空间复杂度最大。 (A) 插入排序 (B) 冒泡排序 (C) 堆排序 (D) 归并排序 11．设一棵二叉树的深度为k，则该二叉树中最多有（ D ）个结点。 (A) 2k-1 (B) 2k (C) 2k-1 (D) 2k-1 12．设一组初始记录关键字序列为(25，50，15，35，80，85，20，40，36，70)，其中含有5个长度为2的有序子表，则用归并排序的方法对该记录关键字序列进行一趟归并后的结果为（ ）。 (A) 15，25，35，50，20，40，80，85，36，70 (B) 15，25，35，50，80，20，85，40，70，36 (C) 15，25，35，50，80，85，20，36，40，70 (D) 15，25，35，50，80，20，36，40，70，85 13．设有序表中有1000个元素，则用二分查找查找元素X最多需要比较（ B ）次。 (A) 25 (B) 10 (C) 7 (D) 1 14．设某棵二叉树的高度为10，则该二叉树上叶子结点最多有（ C ）。 (A) 20 (B) 256 (C) 512 (D) 1024 15．在一个具有n个顶点的无向连通图中,要连通全部顶点至少需要（ C ）条边。 （A） n （B） n+1 （C） n-1 （D） n/2 16.对于线性表（7，34，55，25，64，46，20，10）进行散列存储时，若选用H（K）=K %9

作为散列函数，则散列地址为1的元素有（ D ）个， (A) 1 (B) 2 (C) 3 (D)4 17.设有6个结点的无向图，该图至少应有( A )条边才能确保是一个连通图。 (A) 5 (B) 6 (C) 7 (D) 8

18. 二叉排序树中左子树上所有结点的值均（ A ）根结点的值。 (A) < (B) > (C) = (D) != 19. 设一组权值集合W=(15，3，14，2，6，9，16，17)，要求根据这些权值集合构造一棵哈夫曼树，则这棵哈夫曼树的带权路径长度为（ D ）。 (A) 129 (B) 219 (C) 189 (D) 229 20.设某棵二叉树中只有度数为0和度数为2的结点且度数为0的结点数为n，则这棵二叉中共有（ C ）个结点。 (A) 2n (B) n+l (C) 2n-1 (D) 2n+l 21.设一组初始记录关键字序列为(Q，H，C，Y，P，A，M，S，R，D，F，X)，则按字母升序的第一趟冒泡排序结束后的结果是（ D ）。 (A) F，H，C，D，P，A，M，Q，R，S，Y，X (B) P，A，C，S，Q，D，F，X，R，H，M，Y (C) A，D，C，R，F，Q，M，S，Y，P，H，X (D) H，C，Q，P，A，M，S，R，D，F，X，Y 22.设用邻接矩阵A表示有向图G的存储结构，则有向图G中顶点i的入度为（B ）。 (A) 第i行非0元素的个数之和 (B) 第i列非0元素的个数之和 (C) 第i行0元素的个数之和 (D) 第i列0元素的个数之和

填空题： 1. 设F和R分别表示顺序循环队列的头指针和尾指针，该队列最存储空间为N个，则判断该循环队列为空的条件为___F==A________，判断队列为满时条件为 (R+1)%N==F 。 2. 一个线性表是n≧0个数据元素a1,a2,a3,……an的有限序列，表中每个数据元素，除第一个和最后一个外，有且仅有一个 直接前驱 和一个 直接后继 。

3. 不论是顺序存储结构的栈还是链式存储结构的栈，其入栈和出栈操作的时间复杂度均为_0(1)_____。 4. 设输入序列为1、2、3，则经过栈的作用后可以得到___5_____种不同的输出序列。 5. 若用链表存储一棵二叉树时，每个结点除数据域外，还有指向左孩子和右孩子的两个指针。在这种存储结构中，n个结点的二叉树共有____2n___个指针域，其中有___n-1__个指针域是存放了地址，有_____n+1____个指针是空指针。 6. 对于一个具有n个顶点和e条边的有向图和无向图，在其对应的邻接表中，所含边结点分别有_ ___个和______个。在一个具有n个顶点的无向完全图中，包含有________条边，在一个具有n个顶点的有向完全图中，包含有________条边。 7. 在快速排序、堆排序、归并排序中，___归并______排序是稳定的。

8. ___中序_______遍历二叉排序树中的结点可以得到一个递增的关键字序列（填先序、中序或后序）。 9. 设查找表中有100个元素，如果用二分法查找方法查找数据元素X，则最多需要比较____7____次就可以断定数据元素X是否在查找表中。 10. 设有向图G中有n个顶点e条有向边，所有的顶点入度数之和为d，则e和d的关系为___e=d______。设某无向图中顶点数和边数分别为n和e，所有顶点的度数之和为d，则e=__d/2_____。 11. 设一组初始记录关键字序列为(55，63，44，38，75，80，31，56)，则利用筛选法建立的初始堆为___31,38,44,56,75,80,55,63_____。

合集下载

《数据结构》复习题题库

《数据结构》复习题题库

一、单项选择题（本大题共71小题，每小题2分，共142分）1、一个对象序列的排序码为{46，79，56，38，40，84}，采用快速排序以位于最左位置的对象为基准而得到的第一次划分结果为（）。

（）A．{38，46，79，56，40，84}B．{38，79，56，46，40，84}C．{40，38，46，56，79，84}D．{38，46，56，79，40，84}标准答案：C2、广义表（（a）,a）的表头是（）。

（）A．aB．bC．(a)D．((a))标准答案：C3、数组A中，每个元素A的长度为3个字节，行下标i从1到8，列下标j从1到10，从首地址SA开始连续存放在存储器内，存放该数组至少需要的单元数是（）。

（）A．80B．100C．240D．270标准答案：C4、在一个单链表HL中，若要向表头插入一个由指针p指向的结点，则执行（）。

（）A．HL=p；p->next=HL；B．p->next=HL；HL=p；C．p->next=HL；p=HL；D．p->next=HL->next；HL->next=p；标准答案：B5、一个具有n个顶点的无向完全图的边数为（）。

（）A．(n+1)/2B．n(n-1)/2C．n(n-1)D．n(n+1)标准答案：B6、如果待排序序列中两个数据元素具有相同的值，在排序后它们的位置发生颠倒，则称该排序是不稳定的。

下列选项中，（）就是不稳定的排序方法。

（）A．起泡排序B．归并排序C．直接插入法排序D．简单选择排序标准答案：D7、按照二叉树的定义，具有3个结点的二叉树有（）种。

（）A．3B．4C．5D．6标准答案：C8、设有1000个元素，用二分法查找时，最大比较次数是（）。

（）A．1B．7C．10D．25标准答案：C9、树适合用来表示（）。

（）A．有序数据元素B．无序数据元素C．元素之间具有分支层次关系的数据D．元素之间无联系的数据标准答案：C10、设有两个串p和q，求p在q中首次出现的位置的运算称作（）。

数据结构与算法试题库(附答案)

数据结构与算法试题库(附答案)

数据结构与算法试题库（附答案）一、单选题（共86题，每题1分，共86分）1.对于任意一棵高度为 5 且有 10 个结点的二叉树，若采用顺序存储结构保存，每个结点占 1 个存储单元（仅存放结点的数据信息），则存放该二叉树需要的存储单元的数量至少是：A、31B、10C、16D、15正确答案：A2.数组 A[0..6, 0..5] 的每个元素占 5 个字节，将其按列优先次序存储在起始地址为 1000 的内存单元中，则元素 A[5, 5] 的地址是( )。

A、1175B、1180C、1200D、1205正确答案：C3.一个有N个顶点的强连通图至少有多少条边？A、NB、N+1C、N(N−1)D、N−1正确答案：A4.用二分查找从100个有序整数中查找某数，最坏情况下需要比较的次数是：A、10B、7C、50D、99正确答案：B5.已知一个长度为16的顺序表L，其元素按关键字有序排列。

若采用二分查找法查找一个L中不存在的元素，则关键字的比较次数最多是：A、4B、7C、6D、5正确答案：D6.对空栈 S 进行 Push 和 Pop 操作，入栈序列为 a, b, c, d, e，经过 Push, Push, Pop, Push, Pop, Push, Push, Pop 操作后，得到的出栈序列是：A、b, c, eB、b, c, aC、b, a, cD、b, a, e正确答案：A7.若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用哪种存储方式最节省时间？A、双链表B、单循环链表C、顺序表D、带头结点的双循环链表正确答案：C8.下列各种数据结构中属于线性结构的有()A、树B、图C、队列D、集合正确答案：C9.如果AVL树的深度为6（空树的深度定义为−1），则此树最少有多少个结点？A、12B、20C、33D、64正确答案：C10.对N个记录进行快速排序，在最坏的情况下，其时间复杂度是：A、O(N2)B、O(N)C、O(N2logN)D、O(NlogN)正确答案：A11.稀疏矩阵采用三元组存储的时候，一般需要一个行逻辑链接的顺序表，用以指出每一行的第一个非零元素在三元组中的位置。

数据结构试题集(8套卷子+答案)

数据结构试题集(8套卷子+答案)

《数据结构》试卷一一、填空题：（共２０分）1、当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用存储结构。

2、队列是限制插入只能在表的一端，而删除在表的另一端进行的线性表，其特点是。

3、在一棵二叉树中，度为０的结点个数为n0，度为２的个数为n2，则n0= 。

4、二叉树的前序遍历序列等同于该二叉树所对应森林的遍历序列5、对一棵二叉排序树，若以遍历该树，将得到一个以关键字递增顺序排列的有序序列。

6、三个结点a,b,c组成二叉树，共有种不同的结构。

7、在AVL树中，由于在Ａ结点的右孩子的右子树上插入结点，使Ａ结点的平衡因子由-1变为-2，使其失去平衡，应采用型平衡旋转。

8、图的遍历有两种,它们是。

9、堆排序的时间复杂度为。

10、在含有N个结点的二叉链表中有空链域，通常用这些空链域存储线索，从而得另一种链式存储结构----线索链表。

二、单项选择题（共２０分）１、若进栈序列为１，２，３，４，假定进栈和出栈可以穿插进行，则可能的出栈序列是（）（A）２，４，１，３（B）３，１，４，２（C）３，４，１，２（D）１，２，３，４２、有一棵非空的二叉树，（第０层为根结点），其第i层上最多有多少个结点？（）（A）２i（B）２1-i（C）２1+i（D） i３、设电文中出现的字母为A，B，C，D，E，每个字母在电文中出现的次数分别为９，２７，３，５，１１，按huffman编码，则字母A编码为（）（A）１０（B）１１０（C）１１１０（D）１１１１４、下面关于数据结构的叙述中，正确的叙述是（）（A）顺序存储方式的优点是存储密度大，且插、删除运算效率高（B）链表中每个结点都恰好包含一个指针（C）包含n个结点的二叉排序树的最大检索长度为logn2（D）将一棵树转为二叉树后，根结点无右子树５、程序段：y:＝0while n>=(y+1)*(y+1) doy:=y+1enddo的时间复杂度为（）（A）O(n) （B）O(n2) （C）O(n2/1) （D）O(1)6、排序方法中,关键码比较的次数与记录的初始排列无关的是( )(A) shell排序 (B) 归并排序 (C) 直接插入排序 (D) 直接选择排序7、数组q[0..n-1]作为一个环行队列,f 为当前队头元素的前一位置,r为队尾元素的位置,假定队列中元素的个数总小于n,则队列中元素个数为( )(A) r-f (B) n+f-r (C) n+r-f (D) (n+r-f) mod n8、为了有效的利用散列查找技术,需要解决的问题是:( )Ⅰ:找一个好的散列函数Ⅱ:设计有效的解决冲突的方法Ⅲ:用整数表示关键码值(A) Ⅰ和Ⅲ (B) Ⅰ和Ⅱ (C) Ⅱ和Ⅲ (D) Ⅰ,Ⅱ和Ⅲ9、引入线索二叉树的目的是（）(A) 加快查找结点的前驱或后继的速度(B) 为了能在二叉树中方便的进行插入与删除(C) :为了能方便的找到双亲(D) 使二叉树的遍历结果唯一10、用二分（折半）查找表的元素的速度比用顺序法（）(A) 必然快(B) 必然慢(C): 相等(D): 不能确定三、简答题：（共40分）１、已知某二叉树按中序遍历序列为BFDAEGC，按前序遍历序列为ABDFCEG,试画出该二叉树形状，并写出它的后序遍历序列。

数据结构试题(含答案)

数据结构试题(含答案)

数据结构试题一、单选题1、在数据结构的讨论中把数据结构从逻辑上分为（C ）A 内部结构与外部结构B 静态结构与动态结构C 线性结构与非线性结构D 紧凑结构与非紧凑结构。

2、采用线性链表表示一个向量时，要求占用的存储空间地址（D ）A 必须是连续的B 部分地址必须是连续的C 一定是不连续的D 可连续可不连续3、采用顺序搜索方法查找长度为n的顺序表时，搜索成功的平均搜索长度为（ D ）。

A nB n/2C (n-1)/2D (n+1)/24、在一个单链表中，若q结点是p结点的前驱结点，若在q与p之间插入结点s，则执行（ D ）。

A s→link = p→link;p→link = s;B p→link = s; s→link = q;C p→link = s→link;s→link = p;D q→link = s;s→link = p;5、如果想在4092个数据中只需要选择其中最小的5个，采用（ C ）方法最好。

A 起泡排序B 堆排序C 锦标赛排序D 快速排序6、设有两个串t和p，求p在t中首次出现的位置的运算叫做（ B ）。

A 求子串B 模式匹配C 串替换D 串连接7、在数组A中，每一个数组元素A[i][j]占用3个存储字，行下标i从1到8，列下标j从1到10。

所有数组元素相继存放于一个连续的存储空间中，则存放该数组至少需要的存储字数是（ C ）。

A 80B 100C 240D 2708、将一个递归算法改为对应的非递归算法时，通常需要使用（ A ）。

A 栈B 队列C 循环队列D 优先队列9、一个队列的进队列顺序是1, 2, 3, 4，则出队列顺序为（ C ）。

10、在循环队列中用数组A[0..m-1] 存放队列元素，其队头和队尾指针分别为front和rear，则当前队列中的元素个数是（ D ）。

A ( front - rear + 1) % mB ( rear - front + 1) % mC ( front - rear + m) % mD ( rear - front + m) % m11、一个数组元素a[i]与（ A ）的表示等价。