2024计算机考研《数据结构考研通关800题》下载分享
链接：https://pan.baidu.com/s/1zBIvGvPbaMpAlpPGNuq-zQ
提取码：unjo
内容预览
[P1000] 研究数据结构就是研究( )
A. 数据的逻辑结构 B. 数据的存储结构
C. 数据的逻辑结构和存储结构 D. 数据的逻辑结构、存储结构及其基本操作（研究非数值计算的程序设计问题中，计算机操作对象以及他们之间的关系和操作）
[P1001] 算法分析的两个主要方面是( )
A. 空间复杂度和时间复杂度 B. 正确性和简单性
C. 可读性和文档性 D. 数据复杂性和程序复杂性
[P1002] 具有线性结构的数据结构是（ ）。
A. 图 B. 树 C. 广义表（线性表的推广） D. 栈
[P1003] 计算机中的算法指的是解决某一个问题的有限运算序列，它必须具备输入、输出、（ ）等5个特性。
A. 可执行性、可移植性和可扩充性 B. 可执行性、有穷性和确定性
C. 确定性、有穷性和稳定性 D. 易读性、稳定性和确定性
[P1004] 下面程序段的时间复杂度是( )
for(i=0;i<m;i++)
for(j=0;j<n;j++)
a[i][j]=i*j;
A. O(m2) B. O(n2) C. O(m*n) D. O(m+n)
[P1005] 算法是（ ）。为了解决某一问题而规定的一个有限长的操作序列
A.计算机程序 B. 解决问题的计算方法
C. 排序算法 D. 解决问题的有限运算序列
[P1006] 某算法的语句执行频度为（3n+nlog2n+n2+8）,其时间复杂度表示( )
A. O(n) B. O(nlog2n) C. O(n2) D. O(log2n)
[P1007] i=1;
while(i<=n)
i=i*3;
A. O(n) B. O(3n) C. O(log3n) D. O(n3)
[P1008] 数据结构是一门研究非数值计算的程序设计问题中计算机的数据元素以及它们之间的（ ）和运算等的学科。
A. 结构 B. 关系 C. 运算 D. 算法
[P1009] 下面程序段的时间复杂度是( )
i=s=0;
while(s<n){
i++;s+=i;
}
A. O(sqrt(n)) B. O(n2) C. O(log2n) D. O(n3)
[P1010] 抽象数据类型的三个组成部分分别为( )
A. 数据对象、数据关系和基本操作 B. 数据元素、逻辑结构和存储结构
C. 数据项、数据元素和数据类型 D. 数据元素、数据结构和数据类型
[P1011] 通常从正确性、易读性、健壮性、高效性等4个方面评价算法的质量，以下解释错误的是( )
A. 正确性算法应能正确地实现预定的功能
B. 易读性算法应易于阅读和理解，以便调试、修改和扩充
C. 健壮性当环境发生变化时，算法能适当地做出反应或进行处理，不会产生不需要的运行结果
D. 高效性即达到所需要的时间性能空间
[P1012] 下列程序段的时间复杂度为( )
x=n;y=0;
while(x>=(y+1)*(y+1))
y=y+1;
A. O(n) B.O(sqrt(n)) C. O(1) D. O(n2)
[P1013] 程序段“i=1;while(i<=n) i=i*2;”的时间复杂度为
[P1014] 数据结构的四种基本类型中， 的元素是一对多关系。
[P1015] 将数量级O(1),O(N),O(N2),O(N3),O(NLOG2N),O(LOG2N),O(2N)按增长率由小到大排序。
[P1016] 数据结构被形式地定义为（D, R），其中D是 的有限集合，R是D上的 有限集合。
[P1017] 数据结构包括数据的 、数据的 和数据的 这三个方面的内容。
[P1018] 数据结构按逻辑结构可分为两大类，它们分别是 和
[P1019] 线性结构中元素之间存在 关系，树形结构中元素之间存在 关系，图形结构中元素之间存在多对多关系。
[P1020] 在线性结构中，第一个结点 前驱结点，其余每个结点有且只有 个前驱结点；最后一个结点 后续结点，其余每个结点有且只有1个后续结点。
[P1021] 在树形结构中，树根结点没有 结点，其余每个结点有且只有 个前驱结点；叶子结点没有 结点，其余每个结点的后续结点数可以 。
[P1022] 在图形结构中，每个结点的前驱结点数和后续结点数可以 。
[P1023] 数据的存储结构可用四种基本的存储方法表示，它们分别是 。
[P1024] 数据的运算最常用的有5种，它们分别是 。
[P1025] 一个算法的效率可分为 效率和 效率。
[P1026] 任何一个C程序都由 和若干个被调用的其它函数组成。
[P1027] 非线性结构是数据元素之间存在一种：( )
A）一对多关系 B）多对多关系 C）多对一关系 D）一对一关系
[P1028] 数据结构中，与所使用的计算机无关的是数据的 结构
A) 存储 B) 物理 C) 逻辑 D) 物理和存储
[P1029] 算法分析的目的是：( )
A) 找出数据结构的合理性 B) 研究算法中的输入和输出的关系
C) 分析算法的效率以求改进 D) 分析算法的易懂性和文档性
[P1030] 算法分析的两个主要方面是：( )
A) 空间复杂性和时间复杂性 B) 正确性和简明性
C) 可读性和文档性 D) 数据复杂性和程序复杂性
[P1031] 计算机算法指的是：( )
A) 计算方法 B) 排序方法 C) 解决问题的有限运算序列 D) 调度方法
[P1032] 计算机算法必须具备输入、输出和 等5个特性。
A) 可行性、可移植性和可扩充性 B) 可行性、确定性和有穷性
C) 确定性、有穷性和稳定性 D) 易读性、稳定性和安全性
[P1033] 数据结构和数据类型两个概念之间有区别吗？
[P1034] 简述线性结构与非线性结构的不同点。
[P1035] 分析下面各程序段的时间复杂度
1. for (i=0; i<n; i++)
for (j=0; j<m; j++)
A[i][j]=0;
2. s=0;
for (i=0; i<n; i++)
for(j=0; j<n; j++)
s+=B[i][j];
sum=s;
3. x=0;
for(i=1; i<n; i++)
for (j=1; j<=n-i; j++)
x++;
4. i=1;
while(i<=n)
i=i*3;
[P1036] 若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素算法的时间复杂度（ ）。
A. O(log2n) B.O(1) C. O(n) D.O(n2)
[P1037] 若一个线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用（ ）存储方式最节省时间。
A. 顺序表 B. 单链表 C. 双链表 D. 单循环链表
[P1038] 具有线性结构的数据结构是（ ）。
A. 图 B. 树 C. 广义表 D. 栈
[P1039] 在一个长度为n的顺序表中，在第i个元素之前插入一个新元素时，需向后移动（ ）个元素。
A. n-i B. n-i+1 C. n-i-1 D. i
[P1040] 非空的循环单链表head的尾结点p满足（ ）。
A. p->next==head B. p->next==NULL
C. p==NULL D. p==head
[P1041] 链表不具有的特点是（ ）。
A. 可随机访问任一元素 B. 插入删除不需要移动元素
C. 不必事先估计存储空间 D. 所需空间与线性表长度成正比
[P1042] 在双向循环链表中，在p指针所指的结点后插入一个指针q所指向的新结点，修改指针的操作是（ ）。
A. p->next=q;q->prior=p;p->next->prior=q;q->next=q;
B. p->next=q;p->next->prior=q;q->prior=p;q->next=p->next;
C. q->prior=p;q->next=p->next;p->next->prior=q;p->next=q;
D. q->next=p->next;q->prior=p;p->next=q;p->next=q;
[P1043] 线性表采用链式存储时，结点的存储地址（ ）。
A. 必须是连续的 B. 必须是不连续的
C. 连续与否均可 D. 和头结点的存储地址相连续
[P1044] 在一个长度为n的顺序表中删除第i个元素，需要向前移动（ ）个元素。
A. n-i B. n-i+1 C. n-i-1 D. i+1
[P1045] 线性表是n个（ ）的有限序列。
A. 表元素 B. 字符 C. 数据元素 D. 数据项
[P1046] 从表中任一结点出发，都能扫描整个表的是（ ）。
A. 单链表 B. 顺序表 C. 循环链表 D. 静态链表
[P1047] 在具有n个结点的单链表上查找值为x的元素时，其时间复杂度为（ ）。
A. O(n) B. O(1) C. O(n2) D. O(n-1)
[P1048] 线性表L=(a1,a2,……,an)，下列说法正确的是（ ）。
A. 每个元素都有一个直接前驱和一个直接后继
B. 线性表中至少要有一个元素
C. 表中诸元素的排列顺序必须是由小到大或由大到小
D. 除第一个和最后一个元素外，其余每个元素都由一个且仅有一个直接前驱和直接后继
[P1049] 一个顺序表的第一个元素的存储地址是90，每个元素的长度为2，则第6个元素的存储地址是（ ）。
A. 98 B. 100 C. 102 D. 106
[P1050] 在线性表的下列存储结构中，读取元素花费的时间最少的是（ ）。
A. 单链表 B. 双链表 C. 循环链表 D. 顺序表
[P1051] 在一个单链表中，若删除p所指向结点的后继结点，则执行（ ）。
A. p->next=p->next->next;
B. p=p->next;p->next=p->next->next;
C. p =p->next;
D. p=p->next->next;
[P1052] 将长度为n的单链表连接在长度为m的单链表之后的算法的时间复杂度为（ ）。
A. O(1) B. O(n) C. O(m) D. O(m+n)
[P1053] 线性表的顺序存储结构是一种（ ）存储结构。
A. 随机存取 B. 顺序存取 C. 索引存取 D. 散列存取
[P1054] 顺序表中，插入一个元素所需移动的元素平均数是（ ）。
A. (n-1)/2 B. n C. n+1 D. (n+1)/2
[P1055] 循环链表的主要优点是（ ）。
A. 不再需要头指针
B. 已知某结点位置后能容易找到其直接前驱
C. 在进行插入、删除运算时能保证链表不断开
D. 在表中任一结点出发都能扫描整个链表
[P1056] 不带头结点的单链表head为空的判定条件是（ ）。
A. head==NULL B. head->next==NULL
C. head->next==head D. head!=NULL
[P1057] 在下列对顺序表进行的操作中，算法时间复杂度为O(1)的是（ ）。
A. 访问第i个元素的前驱 B. 在第i个元素之后插入一个新元素
C. 删除第i个元素 D. 对顺序表中元素进行排序
[P1058] 已知指针p和q分别指向某单链表中第一个结点和最后一个结点。假设指针s指向另一个单链表中某个结点，则在s所指结点之后插入上述链表应执行的语句为（ ）。
A. q->next=s->next；s->next=p；
B. s->next=p；q->next=s->next；
C. p->next=s->next；s->next=q；
D. s->next=q；p->next=s->next；
[P1059] 在以下的叙述中，正确的是（ ）。
A. 线性表的顺序存储结构优于链表存储结构
B. 线性表的顺序存储结构适用于频繁插入/删除数据元素的情况
C. 线性表的链表存储结构适用于频繁插入/删除数据元素的情况
D. 线性表的链表存储结构优于顺序存储结构
[P1060] 在表长为n的顺序表中，当在任何位置删除一个元素的概率相同时，删除一个元素所需移动的平均个数为（ ）。
A. (n-1)/2 B. n/2 C. (n+1)/2 D. n
[P1061] 在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q和p之间插入一个结点s，则执行（ ）。
A. s->next=p->next; p->next=s;
B. p->next=s->next;s->next=p;
C. q->next=s;s->next=p;
D. p->next=s;s->next=q;
[P1062] 在单链表中，指针p指向元素为x的结点，实现删除x的后继的语句是（ ）。
A. p=p->next; B. p->next=p->next->next;
C. p->next=p; D. p=p->next->next;
[P1063] 在头指针为head且表长大于1的单循环链表中，指针p指向表中某个结点，若p->next->next==head，则（ ）。
A. p指向头结点 B. p指向尾结点
C. p的直接后继是头结点 D. p的直接后继是尾结点
[P1064] 设单链表的结点结构为（data,next）。已知指针p指向单链表中的结点，q指向新结点，欲将q插入到p结点之后，则需要执行的语句：
[P1065] 线性表的逻辑结构是 ，其所含元素的个数称为线性表的 。
[P1066] 写出带头结点的双向循环链表L为空表的条件 。
[P1067] 带头结点的单链表head为空的条件是 。
[P1068] 在一个单链表中删除p所指结点的后继结点时，应执行以下操作：
q= p->next;
p->next= ;
[P1669] 设某二叉树中度数为 0 的结点数为 N0，度数为 1 的结点数为 N1，度数为 2 的结点数为 N2，则下列等式成立的是（ ）。
(A) N0=N1+1 (B) N0=N1+N2
(C) N0=N2+1 (D) N0=2N1+l
[P1670] 设有序顺序表中有 n 个数据元素，则利用二分查找法查找数据元素 X 的最多比较次数不超过（ ）。
(A) log2n+1 (B) log2n-1 (C) log2n (D) log2(n+1)
[P1671] 数据的最小单位是（ ）。
(A) 数据项 (B) 数据类型 (C) 数据元素 (D) 数据变量
[P1672] 设一组初始记录关键字序列为(50，40，95，20，15，70，60，45)，则以增量 d=4 的一趟希尔排序结束后前 4 条记录关键字为（ ）。
(A) 40，50，20，95 (B) 15，40，60，20
(C) 15，20，40，45 (D) 45，40，15，20
[P1673] 设一组初始记录关键字序列为(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
[P1674] 函数 substr(“DATASTRUCTURE”，5，9)的返回值为（ ）。
(A) “STRUCTURE” (B) “DATA”
(C) “ASTRUCTUR” (D) “DATASTRUCTURE”
[P1675] 设一个有序的单链表中有 n 个结点，现要求插入一个新结点后使得单链表仍然保持有序，则该操作的时间复杂度为（ ）。
(A) O(log2n) (B) O(1) (C) O(n^2) (D) O(n)
[P1676] 设一棵 m 叉树中度数为 0 的结点数为 N0，度数为 1 的结点数为 N1，……，度数为 m 的结点数为 Nm，则 N0=（ ）。
(A) N1+N2+……+Nm (B) 1+N2+2N3+3N4+……+(m-1)Nm
(C) N2+2N3+3N4+……+(m-1)Nm (D) 2N1+3N2+……+(m+1)Nm
[P1677] 设有序表中有 1000 个元素，则用二分查找查找元素 X 最多需要比较（ ）次。
(A) 25 (B) 10 (C) 7 (D) 1
[P1678] 设连通图 G 中的边集 E={(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)}，则从顶点 a 出发可以得到一种深度优先遍历的顶点序列为（ ）。
(A) abedfc (B) acfebd (C) aebdfc (D) aedfcb
[P1679] 设输入序列是 1、2、3、……、n，经过栈的作用后输出序列的第一个元素是 n，则输出序列中第 i 个输出元素是（ ）。
(A) n-i (B) n-1-i (C) n+1-i (D) 不能确定
[P1680] 设一组初始记录关键字序列为(45，80，55，40，42，85)，则以第一个记录关键字 45为基准而得到一趟快速排序的结果是（ ）。
(A) 40，42，45，55，80，83
(B) 42，40，45，80，85，88
(C) 42，40，45，55，80，85
(D) 42，40，45，85，55，80
[P1681] 设一组权值集合 W={2，3，4，5，6}，则由该权值集合构造的哈夫曼树中带权路径长度之和为（ ）。
(A) 20 (B) 30 (C) 40 (D) 45
[P1682] 执行一趟快速排序能够得到的序列是（ ）。
(A) [41，12，34，45，27] 55 [72，63]
(B) [45，34，12，41] 55 [72，63，27]
(C) [63，12，34，45，27] 55 [41，72]
(D) [12，27，45，41] 55 [34，63，72]
[P1683] 设一条单链表的头指针变量为 head 且该链表没有头结点，则其判空条件是（ ）。
(A) head==0 (B) head->next==0
(C) head->next==head (D) head!=0
[P1684] 时间复杂度不受数据初始状态影响而恒为 O(nlog2n)的是（ ）。
(A) 堆排序 (B) 冒泡排序 (C) 希尔排序 (D) 快速排序
[P1685] 一趟排序结束后不一定能够选出一个元素放在其最终位置上的是（ ）。
(A) 堆排序 (B) 冒泡排序 (C) 快速排序 (D) 希尔排序
[P1686] 设某棵三叉树中有 40 个结点，则该三叉树的最小高度为（ ）。
(A) 3 (B) 4 (C) 5 (D) 6
[P1687] 顺序查找不论在顺序线性表中还是在链式线性表中的时间复杂度为（ ）。
(A) O(n) (B) O(n2) (C) O(n1/2) (D) O(1og2n)
[P1688] 二路归并排序的时间复杂度为（ ）。
(A) O(n) (B) O(n2) (C) O(nlog2n) (D) O(log2n)
[P1689] 设指针变量 front 表示链式队列的队头指针，指针变量 rear 表示链式队列的队尾指针，指针变量 s 指向将要入队列的结点 X，则入队列的操作序列为（ ）。
(A) front->next=s；front=s； (B) s->next=rear；rear=s；
(C) rear->next=s；rear=s； (D) s->next=front；front=s；
[P1690] 设某无向图中有 n 个顶点 e 条边，则建立该图邻接表的时间复杂度为（ ）。
(A) O(n+e) (B) O(n^2) (C) O(ne) (D) O(n^3)
[P1691] 设某哈夫曼树中有 199 个结点，则该哈夫曼树中有（ ）个叶子结点。
(A) 99 (B) 100 (C) 101 (D) 102
[P1692] 设二叉排序树上有 n 个结点，则在二叉排序树上查找结点的平均时间复杂度为（ ）。
(A) O(n) (B) O(n^2) (C) O(nlog2n) (D) O(log2n)
[P1693] 设用邻接矩阵 A 表示有向图 G 的存储结构，则有向图 G 中顶点 i 的入度为（ ）。
(A) 第 i 行非 0 元素的个数之和 (B) 第 i 列非 0 元素的个数之和
(C) 第 i 行 0 元素的个数之和 (D) 第 i 列 0 元素的个数之和
[P1694] 设无向图 G 中有 n 个顶点，则该无向图的最小生成树上有（ ）条边。
(A) n (B) n-1 (C) 2n (D) 2n-1
[P1695] 设一组初始记录关键字序列为(60，80，55，40，42，85)，则以第一个关键字 45 为基准而得到的一趟快速排序结果是（ ）。
(A) 40，42，60，55，80，85 (B) 42，45，55，60，85，80
(C) 42，40，55，60，80，85 (D) 42，40，60，85，55，80
[P1696] （ ）二叉排序树可以得到一个从小到大的有序序列。
(A) 先序遍历 (B) 中序遍历 (C) 后序遍历 (D) 层次遍历
[P1697] 程序段 s=i=0；do {i=i+1； s=s+i；}while(i<=n)；的时间复杂度为（ ）。
(A) O(n) (B) O(nlog2n) (C) O(n^2) (D) O(n^3/2)
[P1698] 设带有头结点的单向循环链表的头指针变量为 head，则其判空条件是（ ）。
(A) head==0 (B) head->next==0
(C) head->next==head (D) head!=0
[P1699] 设某棵二叉树的高度为 10，则该二叉树上叶子结点最多有（ ）。
(A) 20 (B) 256 (C) 512 (D) 1024
[P1700] 设一组初始记录关键字序列为(13，18，24，35，47，50，62，83，90，115，134),则利用二分法查找关键字 90 需要比较的关键字个数为（ ）。
(A) 1 (B) 2 (C) 3 (D) 4
[P1701] 设指针变量 top 指向当前链式栈的栈顶，则删除栈顶元素的操作序列为（ ）。
(A) top=top+1; (B) top=top-1;
(C) top->next=top; (D) top=top->next;
[P1702] 字符串的长度是指（ ）。
(A) 串中不同字符的个数 (B) 串中不同字母的个数
(C) 串中所含字符的个数 (D) 串中不同数字的个数
[P1703] 建立一个长度为 n 的有序单链表的时间复杂度为（ ）
(A) O(n) (B) O(1) (C) O(n2) (D) O(log2n)
[P1704] 两个字符串相等的充要条件是（ ）。
(A) 两个字符串的长度相等
(B) 两个字符串中对应位置上的字符相等
(C) 同时具备(A)和(B)两个条件
(D) 以上答案都不对
[P1705] 设某散列表的长度为 100，散列函数 H(k)=k % P，则 P 通常情况下最好选择（ ）。
(A) 99 (B) 97 (C) 91 (D) 93
[P1706] 在二叉排序树中插入一个关键字值的平均时间复杂度为（ ）。
(A) O(n) (B) O(log2n) (C) O(nlog2n) (D) O(n^2)
[P1707] 设一个顺序有序表 A[1:14]中有 14 个元素，则采用二分法查找元素 A[4]的过程中比较元素的顺序为( )。
(A) A[1]，A[2]，A[3]，A[4] (B) A[1]，A[14]，A[7]，A[4]
(C) A[7]，A[3]，A[5]，A[4] (D) A[7]，A[5] ，A[3]，A[4]
[P1708] 设一棵完全二叉树中有 65 个结点，则该完全二叉树的深度为（ ）。
(A) 8 (B) 7 (C) 6 (D) 5
