数据结构题库

[名词解释] 结点的带权路径长度

[名词解释] 深度优先搜索

[单选题]设单循环链表中结点的结构为（data，link），且first为指向链表表头的指针，current为链表当前指针，在循环链表中检测current是否达到链表表尾的语句是（）。A . current->link=nullB . first->link=currentC . first=currentD . current->link=first

[单选题]设单链表中结点结构为（data，link）.若想摘除结点*p的直接后继，则应执行下列哪一个操作（）A . p->link=p->link->linkB . p=p->link；p->link=p->link->linkC . p->link=p->linkD . p=p->link->link

[单选题]有一个100×90的稀疏矩阵，非0元素有10，设每个整型数占2个字节，则用三元组表示该矩阵时，所需的字节数是（）。A . 20B . 66C . 18000D . 33

[单选题]在数据结构中，与所使用的计算机无关的是数据的（）结构。A . 逻辑B . 存储C . 逻辑和存储D . 物理

[判断题] 对具有n个结点的堆进行插入一个元素运算的时间复杂度为O（n）。A . 正确B . 错误

[填空题,简答题] 子串的定位运算称为串的模式匹配；（）称为目标串，（）称为模式。

[填空题] 已知一个有向图的邻接矩阵表示，删除所有从第i个顶点出发的方法是（）。

[单选题]在数据结构中，从逻辑上可以把数据结构分为（）。A . 动态结构和静态结构B . 紧凑结构和非紧凑结构C . 线性结构和非线性结构D . 内部结构和外部结构

[判断题] 若二叉树用二叉链表作存贮结构，则在n个结点的二叉树链表中只有n—1个非空指针域。A . 正确B . 错误

[填空题] n个顶点e条边的图，若采用邻接矩阵存储，则空间复杂度为（）。

[单选题]串是一种特殊的线性表，其特殊性体现在（）A . 可以顺序存储B . 数据元素是一个字符C . 可以链式存储D . 数据元素可以是多个字符

[名词解释] 快速排序

[单选题]算法的计算量的大小称为计算的（）。A . 效率B . 复杂性C . 现实性D . 难度

[名词解释] 堆排序

[单选题]假设有60行70列的二维数组a[1…60，1…70]以列序为主序顺序存储，其基地址为10000，每个元素占2个存储单元，那么第32行第58列的元素a[32，58]的存储地址为。（无第0行第0列元素）（）A . 16902B . 16904C . 14454D . 答案A，B，C均不对

[名词解释] 不稳定排序

[名词解释] 连通分量

[单选题]与单链表相比，双链表的优点之一是（）。A . 插入、删除操作更简单B . 可以进行随机访问C . 可以省略表头指针或表尾指针D . 顺序访问相邻结点更灵活

[填空题] 用Dijkstra算法求某一顶点到其余各顶点间的最短路径是按路径长度（）的次序来得到最短路径的。

[单选题]在长度为n的顺序表的第i个位置上插入一个元素（1≤i≤n＋1），元素的移动次数为（）。A . n–i＋1B . n–iC . iD . i–1

[判断题] 二叉树中所有结点个数是2k-1-1，其中k是树的深度。A . 正确B . 错误

[名词解释] 归并排序

[单选题]设串的长度为n，则它的子串个数为（）。A . nB . n（n+1）C . n（n+1）/2D . n（n+1）/2+1

[判断题] 对于一棵具有n个结点，其高度为h的二叉树，进行任一种次序遍历的时间复杂度为O（n）。A . 正确B . 错误

[判断题] 线性表的逻辑顺序总是与其物理顺序一致。A . 正确B . 错误

[单选题]设串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

[填空题] 若要求一个稠密图G的最小生成树，最好用（）算法来求解

[名词解释] 强连通图