数据结构题库.docx

1、数据结构题库选择对于线性表，适用于使用链式结构的情况是（ ）A需经常修改中的结点值 B需不断对进行删除插入 C中含有大量的结点 D中结点结构复杂数据结构中，与所使用的计算机无关的是数据的（ ）A存储结构 B物理结构 C 逻辑结构 D 线性结构若用一个大小为6的数组来实现循环队列，且当前队尾和队头的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，则（ ）A队尾为1、队头为5 B. 队尾为2、队头为4 C. 队尾为4、队头为2 D. 队尾为5、队头为1在一个栈顶指针为HS的链栈中，将一个S指针所指的结点入栈，实现语句是（ ）AHS-next=s BS-next=HS-next；HS-ne

2、xt=sCS-next=HS-next；HS=s DS-next=HS；HS=HS-next从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放入已排序序列的正确位置上，这种排序方法是（ ）A希尔排序 B冒泡排序 C插入排序 D选择排序堆排序是一种（ ）A插入排序 B选择排序 C交换排序 D归并排序在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的（ ）A1/2倍 B1倍 C2倍 D4倍 二叉树是非线性数据结构，所以（ ）A它不能用顺序存储结构存储B它不能用链式存储结构存储; C它能采用顺序存储结构和链式存储结构存储D它既不能使用顺序存储结构和也不能使用链式存储结

3、构存储若一个满二叉树有m个树叶，n个结点，深度为h，则m、n、h满足关系（ ）An=h+m Bh+m=2n Cm=h-1 Dn=2h-1采用直接选择排序，总的比较次数为（ ）AO（n） BO（log2 n） CO（n log2 n） DO（n2）计算机算法必须具备输入、输出和（ ）等5个特性。 A可行性、可移植性和可扩充性 B可行性、确定性和有穷性 C确定性、有穷性和稳定性 D易读性、稳定性和安全性设有两个串p和q，求q在p中首次出现的位置的运算称作（ ） 连接 模式匹配 求子串 求串长把一棵树转换为二叉树后，这棵二叉树的形态是 （ ） 唯一的 有多种 有多种，但根结点都没有左孩子 有多种，但

4、根结点都没有右孩子广度优先遍历类似于二叉树的（ ） A先序遍历 B. 中序遍历 C. 后序遍历 D. 层次遍历对22个记录的有序表作折半查找，当查找失败时，至少需要比较（ ）次关键字。 A3 B4 C5 D 6数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称之为：（ ）A存储结构 B. 逻辑结构 C. 顺序存储结构 D. 链式存储结构设无向图G中有100个顶点，则该无向图的最小生成树上有（ ）条边。A100 B. 99 C. 98 D. 200设带有头结点的单向循环链表的头指针变量为head，则其判空条件是（ ）。A. head=0 B. head-next=0 C. hea

5、d-next=head D. head!=0栈中元素的进出原则是（ ）A先进先出 B. 后进先出 C. 队空则进 D. 队满则出两个字符串相等的充要条件是（ ）。A. 两个字符串的长度相等 B. 两个字符串中对应位置上的字符相等C. 同时具备(A)和(B)两个条件 D. 以上答案都不对设输入序列1、2、3、n经过栈作用后，输出序列中的第一个元素是n，则输出序列中的第i个输出元素是（ ）。A. n-i B. n-1-i C. n+l-i D. 不能确定设有一组初始记录关键字序列为(34，45，56，64，72，81，92)，则按照折半查找法,由这组记录关键字生成的二叉判定树的深度为（ ）。 A.

6、 3 B. 4 C. 5 D. 6设指针q指向单链表中结点A，指针p指向单链表中结点A的后继结点B，指针s指向被插入的结点X，则在结点A和结点B插入结点X的操作序列为（ ）。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；抽象数据类型（Abstract Data Type, 简称ADT）是指一个数学模型以及定义在该模型上的一组（ ）。 A 操作 B. 成员变量 C. 数据 D. 数据类型下面程序的时间复杂度为（ ）for（i=1，s=0； i=n；

7、i+） t=1；for(j=1；jfront = = (QU-rear+1)% m0 BQU-rear QU-front 1= = m0 CQU-front = = QU-rear DQU-front = = QU-rear+1设有两个串p和q，求q在p中首次出现的位置的运算称作（ ）A连接 B模式匹配 C求子串 D求串长用邻接表表示图进行广度优先遍历时，通常是采用（ ）来实现算法的。A栈 B. 队列 C. 树 D. 图 下面关于工程计划的AOE网的叙述中，不正确的是（ ） A关键活动不按期完成就会影响整个工程的完成时间 B任何一个关键活动提前完成，那么整个工程将会提前完成 C所有的关键活动都

8、提前完成，那么整个工程将会提前完成 D某些关键活动若提前完成，那么整个工程将会提前完成链表适用于（ ）查找A顺序 B二分法 C顺序，也能二分法 D随机判断线性表在顺序存储时，逻辑上相邻的元素未必在存储的物理位置次序上相邻。栈和队列是一种非线性数据结构。两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。 设目标T=”abccdcdccbaa”，模式P=“cdcc”，则第6次匹配成功。二叉树中每个结点的两棵子树是有序的。线性表的逻辑顺序和存储顺序总是一致的。栈可以作为实现过程调用的一种数据结构。栈和队列的存储方式既可是顺序方式，也可是链接方式

9、。若二叉树用二叉链表作存贮结构，则在n个结点的二叉树链表中只有n1个非空指针域。序列12, 36, 27, 65, 40, 34, 98, 81, 73, 55, 49 是小顶堆。 设一个无向图的顶点数目为n,如果它是完全图，则边的数目为n(n-1)/2。在循环队列中，front指向队头元素的前一个位置，rear指向队尾元素的位置，则队满的条件是 front=rear。填空算法分析的目的是： 。向一个长度为n的向量中第i个元素(1in+1)之前插入一个元素时，需向后移动 个元素。对于栈只能在 插入和删除元素；对于队列只能在 插入和 删除元素。一棵深度为6的满二叉树有 个分支结点和 个叶子。若要

10、求一个稀疏图G的最小生成树，最好用 算法来求解。若要求一个稠密图H的最小生成树，最好用 算法来求解。在数据存放无规律而言的线性表中进行检索的最佳方法是 查找。通常从四个方面评价算法的质量： 、 、 和 。在一个长度为11的一维数组（也称向量）中删除第i个元素(0i10)时，需从第 个元素起向前移动 个元素。设表的长度为n，则在等概率情况下顺序查找的平均查找长度为 。折半查找有序表（4，6，12，20，28，38，50，70，88，100），若查找表中元素20，它将依次与表中元素 比较大小。将以无序序列关键字为50, 30, 20, 80, 40, 35, 23, 25, 10, 85, 90,

11、 88的记录构造成一棵二叉排序树后，节点关键字为40的左孩子是_， 85的右孩子是_。对于一棵非空二叉树，它的根结点作为第一层，则它的第3层上最多能有 个结点。由个结点所构成的二叉树有 种形态。具有12个结点的完全二叉树有 个度为2的结点。一棵深度为6的满二叉树有 个分支结点和 个叶子。图有 、 等存储结构，遍历图有 、 等方法。设初始记录关键字序列为(49,38,65,97,76,13,27,50)，则用筛选法思想建堆必须从关键字为_的记录开始进行筛选。在一个单链表中，若p所指结点不是最后结点，要在p之后插入s所指结点，实现语句是s-next= ；p-next= 。用普里姆(Prim)算法求

12、具有n个顶点e条边的图的最小生成树的时间复杂度为 ；用克鲁斯卡尔(Kruskal)算法的时间复杂度是 。线性有序表（a1，a2，a3，a256)是从小到大排列的，对一个给定的值k，用二分法检索表中与k相等的元素，在查找不成功的情况下，最多需要检索 次。若有100个结点，用二分法查找时，最大比较次数是 。一棵具有513个结点的完全二叉树，它的深度为 。在对一组记录（54，38，96，23，15，72，60，45，83）进行直接插入排序时，当把第7个记录60插入到有序表时，为寻找插入位置至少需比较 次。 计算分析下面各程序段的时间复杂度（1） x=0; for(i=1; in; i+) for (

13、j=1; j=n-i; j+)x+;（2） i=1; while(idata); traversal(root-lchild); printf(“%c”, root-data);traversal(root-rchild);设如下图所示的一棵二叉树B，它的存储结构为二叉链表，root为根指针，结点结构为：（lchild,data,rchild）。其中lchild，rchild分别为指向左右孩子的指针，data为字符型，root为根指针，试回答下列问题：1). 对下列二叉树B，执行如右算法traversal(root)，试指出其输出结果；2). 假定二叉树B共有n个结点，试分析算法travers

14、al(root)的时间复杂度。二叉树B已知待散列的线性表为（36，15，40，63，22），散列用的一维地址空间为0,1,6，假定选用的散列函数是H（K）= K mod 7 (K为关键字)，冲突处理为线性探测再散列法，增量为1，试求以下问题：（1）计算出每一个元素的散列地址并在下图中填写出散列表： 0 1 2 3 4 5 6（2）求出在查找每一个元素概率相等情况下的平均查找长度。已知序列（10，18，4，3，6，12，1，9，18，8）请用快速排序写出每一趟排序的结果。算法设计将无向图的邻接矩阵转为对应邻接表的c语言算法实现折半查找的c语言算法对下图的二叉树，执行下列算法search(root

15、)后输出结果是 （此题4分）void search (struct node *root) if (root) search (root-lchild); printf(“%c”, root-data);search (root-rchild);printf(“%c”, root-data); 算法设计：统计出单链表HL中结点的值等于给定值x的结点数，结构体的申明及函数头部已给出。 typedef struct Lnode int data; /数据域 struct Lnode *next; /指针域LNode;int CountX(LNode* HL,int x)下列程序判断字符串s是否对称，对称则返回1，否则返回0；如f(abba)返回1，f(abab)返回0；int f( 【1】 ) inti=0,j=0; while ( sj ) 【2】 ; for(j-; ij & 【3】 ; i+,j-);return( 【4】 )已知一个顺序表L，其中的元素按值非递减有序排列。设计一个算法实现：在顺序表中插入一个元素x后保持该顺序表仍按值非递减有序排列。 #define MAXSIZE 100typedef struct int dataMAXSIZE; int len;List;void ins(List &L , int x)