数据结构题库.docx
《数据结构题库.docx》由会员分享，可在线阅读，更多相关《数据结构题库.docx（14页珍藏版）》请在冰点文库上搜索。
数据结构题库
选择
对于线性表Ｌ，适用于使用链式结构的情况是（）
A．需经常修改Ｌ中的结点值B．需不断对Ｌ进行删除插入
C．Ｌ中含有大量的结点D．Ｌ中结点结构复杂
数据结构中，与所使用的计算机无关的是数据的（）
A．存储结构B．物理结构C．逻辑结构D．线性结构
若用一个大小为6的数组来实现循环队列，且当前队尾和队头的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，则（）
A．队尾为1、队头为5B.队尾为2、队头为4
C.队尾为4、队头为2D.队尾为5、队头为1
在一个栈顶指针为HS的链栈中，将一个S指针所指的结点入栈，实现语句是（）
A．HS->next=sB．S->next=HS->next；HS->next=s
C．S->next=HS->next；HS=sD．S->next=HS；HS=HS->next
从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放入已排序序列的正确位置上，这种排序方法是（）
A．希尔排序B．冒泡排序C．插入排序D．选择排序
堆排序是一种（）
A．插入排序B．选择排序C．交换排序D．归并排序
在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的（）
A．1/2倍B．1倍C．2倍D．4倍
二叉树是非线性数据结构，所以（）
A．它不能用顺序存储结构存储
B．它不能用链式存储结构存储;
C．它能采用顺序存储结构和链式存储结构存储
D．它既不能使用顺序存储结构和也不能使用链式存储结构存储
若一个满二叉树有m个树叶，n个结点，深度为h，则m、n、h满足关系（）
A．n=h+mB．h+m=2nC．m=h-1D．n=2h-1
采用直接选择排序，总的比较次数为（）
A．O（n）B．O（log2n）C．O（nlog2n）D．O（n2）
计算机算法必须具备输入、输出和（）等5个特性。
A．可行性、可移植性和可扩充性B．可行性、确定性和有穷性
C．确定性、有穷性和稳定性D．易读性、稳定性和安全性
设有两个串p和q，求q在p中首次出现的位置的运算称作（）
Ａ．连接Ｂ．模式匹配Ｃ．求子串Ｄ．求串长
把一棵树转换为二叉树后，这棵二叉树的形态是（）
Ａ．唯一的Ｂ．有多种
Ｃ．有多种，但根结点都没有左孩子Ｄ．有多种，但根结点都没有右孩子
广度优先遍历类似于二叉树的（）
A．先序遍历B.中序遍历C.后序遍历D.层次遍历
对22个记录的有序表作折半查找，当查找失败时，至少需要比较（）次关键字。
A．3B．4C．5D．6
数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称之为：
（）
A．存储结构B.逻辑结构C.顺序存储结构D.链式存储结构
设无向图G中有100个顶点，则该无向图的最小生成树上有（）条边。
A．100B.99C.98D.200
设带有头结点的单向循环链表的头指针变量为head，则其判空条件是（）。
A.head==0B.head->next==0C.head->next==headD.head!
=0
栈中元素的进出原则是（）
A．先进先出B.后进先出C.队空则进D.队满则出
两个字符串相等的充要条件是（）。
A.两个字符串的长度相等B.两个字符串中对应位置上的字符相等
C.同时具备（A）和（B）两个条件D.以上答案都不对
设输入序列1、2、3、…、n经过栈作用后，输出序列中的第一个元素是n，则输出序列中的第i个输出元素是（）。
A.n-iB.n-1-iC.n+l-iD.不能确定
设有一组初始记录关键字序列为（34，45，56，64，72，81，92），则按照折半查找法,由这组记录关键字生成的二叉判定树的深度为（）。
A.3B.4C.5D.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；
抽象数据类型（AbstractDataType,简称ADT）是指一个数学模型以及定义在该模型上的一组（）。
A．操作B.成员变量
C.数据D.数据类型
下面程序的时间复杂度为（）
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）
以下数据结构中哪一个是非线性结构？
（）
A.队列 B.栈C.线性表 D.二叉树
用5个权值{3,2,4,5,1}构造的哈夫曼（Huffman）树的带权路径长度是（）。
A．33B．32C．34D．15
设串s1=‘ABCDEFG’，s2=‘PQRST’，函数con（x,y）返回x和y串的连接串，subs（s,i,j）返回串s的从序号i开始的j个字符组成的子串，len（s）返回串s的长度，则con（subs（s1,2,len（s2））,subs（s1,len（s2）,2））的结果串是：
A．BCDEFB．BCDEFGC．BCPQRSTD．BCDEFEF
已知图的邻接表如下所示，根据算法，则从顶点0出发按广度优先遍历的结点序列是（）
A．0321B.0123C.0132D.0312
数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的结构是（）
A．存储结构B．逻辑结构
C．顺序存储结构D．链式存储结构
算法分析的主要方面是（）
A．空间复杂性和时间复杂性B．正确性和简明性
C．可读性和文档性D．数据复杂性和程序复杂性
递归过程或函数调用时，要处理参数及返回地址，应使用的数据结构为（）
A．队列B．多维数组C．栈D．二叉树
将5个不同的数据进行排序，至多需要比较（）
A．8次B．9次C．10次D．25次
在所有的排序方法中，关键字比较的次数与记录的初始排列次序无关的是（）
A．希尔排序B．冒泡排序
C．直接插入排序D．直接选择排序
在表长为ｎ的链表中进行线性查找，它的平均查找长度为（）
A．ＡＳＬ＝ｎB．ＡＳＬ＝（ｎ＋１）／２
C．ＡＳＬ＝
＋１D．ＡＳＬ≈ｌｏｇ２（ｎ＋１）－１
在一个图中，所有顶点的度数之和等于图的边数的（）
A．1/2倍B．1倍C．2倍D．4倍
环形顺序队列中是否可以插入下一个元素（）
A．与对头指针和队尾指针的值有关
B．只与队尾指针的值有关，与对头指针的值无关
C．只与数组大小有关，与对头指针和队尾指针的值无关
D．与曾经进行过多少次插入操作有关
数组A中每个元素的长度为3字节，行下标i从1到8，列下标j从1到10，在存储器内从首地址SA开始连续存放该数组，至少需要的空间是（）
A．80字节B．100字节C．240字节D．270字节
判定一个循环队列QU（最多元素为m0）为满队列的条件是（）
A．QU->front==（QU->rear+1）%m0B．QU->rear－QU->front－1==m0C．QU->front==QU->rearD．QU->front==QU->rear+1
设有两个串p和q，求q在p中首次出现的位置的运算称作（）
A．连接B．模式匹配C．求子串D．求串长
用邻接表表示图进行广度优先遍历时，通常是采用（）来实现算法的。
A．栈B.队列C.树D.图
下面关于工程计划的AOE网的叙述中，不正确的是（）
A．关键活动不按期完成就会影响整个工程的完成时间
B．任何一个关键活动提前完成，那么整个工程将会提前完成
C．所有的关键活动都提前完成，那么整个工程将会提前完成
D．某些关键活动若提前完成，那么整个工程将会提前完成
链表适用于（）查找
A．顺序B．二分法C．顺序，也能二分法D．随机
判断
线性表在顺序存储时，逻辑上相邻的元素未必在存储的物理位置次序上相邻。
栈和队列是一种非线性数据结构。
两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。
设目标T=”abccdcdccbaa”，模式P=“cdcc”，则第6次匹配成功。
二叉树中每个结点的两棵子树是有序的。
线性表的逻辑顺序和存储顺序总是一致的。
栈可以作为实现过程调用的一种数据结构。
栈和队列的存储方式既可是顺序方式，也可是链接方式。
若二叉树用二叉链表作存贮结构，则在n个结点的二叉树链表中只有n—1个非空指针域。
序列{12,36,27,65,40,34,98,81,73,55,49}是小顶堆。
设一个无向图的顶点数目为n,如果它是完全图，则边的数目为n（n-1）/2。
在循环队列中，front指向队头元素的前一个位置，rear指向队尾元素的位置，则队满的条件是front=rear。
填空
算法分析的目的是：
。
向一个长度为n的向量中第i个元素（1≤i≤n+1）之前插入一个元素时，需向后移动个元素。
对于栈只能在插入和删除元素；对于队列只能在插入和删除元素。
一棵深度为6的满二叉树有个分支结点和个叶子。
若要求一个稀疏图G的最小生成树，最好用算法来求解。
若要求一个稠密图H的最小生成树，最好用算法来求解。
在数据存放无规律而言的线性表中进行检索的最佳方法是查找。
通常从四个方面评价算法的质量：
、、和。
在一个长度为11的一维数组（也称向量）中删除第i个元素（0≤i≤10）时，需从第个元素起向前移动个元素。
设表的长度为n，则在等概率情况下顺序查找的平均查找长度为。
折半查找有序表（4，6，12，20，28，38，50，70，88，100），若查找表中元素20，它将依次与表中元素比较大小。
将以无序序列关键字为{50,30,20,80,40,35,23,25,10,85,90,88}的记录构造成一棵二叉排序树后，节点关键字为40的左孩子是______，85的右孩子是_。
对于一棵非空二叉树，它的根结点作为第一层，则它的第3层上最多能有个结点。
由３个结点所构成的二叉树有种形态。
具有12个结点的完全二叉树有个度为2的结点。
一棵深度为6的满二叉树有个分支结点和个叶子。
图有、等存储结构，遍历图有、等方法。
设初始记录关键字序列为（49,38,65,97,76,13,27,50），则用筛选法思想建堆必须从关键字为____的记录开始进行筛选。
在一个单链表中，若p所指结点不是最后结点，要在p之后插入s所指结点，实现语句是s->next=；p->next=。
用普里姆（Prim）算法求具有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;ifor（j=1;j<=n-i;j++）
x++;
（2）i=1;
while（i<=n）
i=i*3;
设循环队列的容量为40（序号从0到39），现经过一系列的入队和出队运算后，有①front=11，rear=29;②front=29，rear=11；问在这两种情况下，循环队列中各有元素多少个？
有一电文共使用八种字符a,b,c,d,e,f,g,h,其出现频率依次为3,7,9,16,22,
14,8,5,请完成以下内容：
（1）试画出对应的编码哈夫曼树（要求左子树根结点的权小于等于右子树根结点的权）。
（2）求出每个字符的哈夫曼编码。
（3）译出编码系列11000111000110011的相应电文。
根据题图所示的连通图，
（1）写出它的邻接矩阵
（2）请根据邻接矩阵写出以顶点3为根的深度优先搜索序列
（3）请画出此深度优先生成树；
给定二叉树的两种遍历序列，其中，前序遍历序列为ABDFJGKCEHILM；中序遍历序列为BFJDGKACHELIM，试画出该二叉树树形，并写出按后序遍历时得到的结点序列。
设哈希（Hash）表的地址范围为0～17，哈希函数为：
H（K）＝KMOD16。
K为关键字，用线性探测法处理冲突，输入关键字序列：
（10，24，32，17，31，30，46，47，40，63，49）
造出Hash表，试回答下列问题：
1.画出哈希表的示意图；
2.若查找关键字63，需要依次与哪些关键字进行比较？
3.假定每个关键字的查找概率相等，求查找成功时的平均查找长度。
在如下数组A中链接存储了一个线性表，表头指针为A[0].next，写出该线性表。
A01234567
data
60
50
78
90
34
40
next
3
5
7
2
0
4
1
给定二叉树的两种遍历序列，其中，前序遍历序列为D，A，C，E，B，H，F，G，I；中序遍历序列为D，C，B，E，H，A，G，I，F，试画出该二叉树树形，并写出按后序遍历时得到的结点序列。
用6个权值{7，8，9，2，4，3}构造一棵哈夫曼树，请画出该树，并求其带权路径长度。
下图表示了一个有向图的邻接表存储结构，首先请画出此有向图的形状，然后再按此图的邻接表存储结构写出从C点开始依据深度优先遍历该图的结果。
对有序表：
（3，4，5，7，24，30，42，54，63，72，87，95）进行折半查找，试回答下列问题：
（1）画出描述折半查找过程的判定树；
（2）若查找元素54，需依次与哪些元素比较？
（3）假定每个元素的查找概率相等，求查找成功时的平均查找长度。
在一棵空的二叉查找树中依次插入关键字序列为12，7，17，11，16，2，13，9，21，4，请画出所得到的二叉查找树。
设无向图G如下图所示，画出它的最小生成树的图并计算最小生成树各边上的权值之和。
C的结点类型定义如下：
structnode
{chardata;
structnode*lchild,rchild;
};
C算法如下：
voidtraversal（structnode*root）
{if（root）
{printf（“%c”,root->data）;
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个结点，试分析算法traversal（root）的时间复杂度。
二叉树B
已知待散列的线性表为（36，15，40，63，22），散列用的一维地址空间为[0,1,…,6]，假定选用的散列函数是H（K）=Kmod7（K为关键字），冲突处理为线性探测再散列法，增量为1，试求以下问题：
（1）计算出每一个元素的散列地址并在下图中填写出散列表：
`0123456
（2）求出在查找每一个元素概率相等情况下的平均查找长度。
已知序列（10，18，4，3，6，12，1，9，18，8）请用快速排序写出每一趟排序的结果。
算法设计
将无向图的邻接矩阵转为对应邻接表的c语言算法
实现折半查找的c语言算法
对下图的二叉树，执行下列算法search（root）后输出结果是（此题4分）
voidsearch（structnode*root）
{if（root）
{search（root->lchild）;
printf（“%c”,root->data）;
search（root->rchild）;
printf（“%c”,root->data）;
}
}
算法设计：
统计出单链表HL中结点的值等于给定值x的结点数，结构体的申明及函数头部已给出。
typedefstructLnode{
intdata;//数据域
structLnode*next;//指针域
}LNode;
intCountX（LNode*HL,intx）
下列程序判断字符串s 是否对称，对称则返回1，否则返回0；如 f（"abba"）返回1，f（"abab"）返回0；
intf（【1】）
{int i=0,j=0;
while（s[j]）【2】;
for（j--;i return（【4】）
}
已知一个顺序表L，其中的元素按值非递减有序排列。
设计一个算法实现：
在顺序表中插入一个元素x后保持该顺序表仍按值非递减有序排列。
#defineMAXSIZE100
typedefstruct
{
intdata[MAXSIZE];
intlen;
}List;
voidins（List&L,intx）
升级会员 