《数据结构试题库答案 nana》由会员分享，可在线阅读，更多相关《数据结构试题库答案 nana（43页珍藏版）》请在金锄头文库上搜索。
1、数据结构试题及答案 一、单项选择题一、单项选择题 (1) 一个算法应该是（ ） 。 A) 程序 B) 问题求解步骤的描述 C) 要满足五个基本属性 D) A 和 C (2) 算法指的是（ ） 。 A) 计算机程序 B) 解决问题的计算方法 C) 排序算法 D) 解决问题的有限运算序列。 (3) 与数据元素本身的形式、内容、相对位置、个数无关的是数据的（ ） 。 A) 存储结构 B) 逻辑结构 C) 算法 D)操作 (4) 从逻辑上可以把数据结构分为（ ）两大类。 A) 动态结构、静态结构 B) 顺序结构、链式结构 C) 线性结构、非线性结构 D) 初等结构、构造型结构 (5) 下列叙述中正确的
2、是( )。 A）一个逻辑数据结构只能有一种存储结构B）数据的逻辑结构属于线性结构，存储结构属于非线性结构 C）一个逻辑数据结构可以有多种存储结构，且各种存储结构不影响 数据处理的效率 D）一个逻辑数据结构可以有多种存储结构，且各种存储结构影响数 据处理的效率 (6) 数据的基本单位是（ ）A) 数据项B) 数据类型 C) 数据元素 D) 数据变量(7) 下列程序的时间复杂度为（ ）i=0；s=0；while（s=n ; i+)for ( j=1; j=n ; j+)x:=x+1; A) O(2n) B)O(n) C) O(n2) D) O(log2n) (11)程序段 for ( i:=n-1
3、; i=i ; j+)if (ajaj+1 ) t=aj; aj= aj+1; aj+1= t; 其中 n 为正整数，则最后一行的语句频度在最坏情况下是（ ） 。 A) O(n） B) O(nlogn) C) O(n3) D) O(n2) (12) 设有一个递归算法如下： int fact(int n) /* 大于等于 0 */if ( nnext= =headB) rear-next-next= =head C) head-next= =rearD) head-next-next= =rear (17)从一个长度为 n 的顺序表中删除第 i 个元素 （1in）时，需向前移动的元素的个数是（
4、） 。A)n-iB)n-i+1C)n-i-1D)i(18)已知一个有序表为 （13，18，24，35，47，50，62，83，90，115，134） ，当二分检 索值为 90 的元素时，检索成功需比较的次数是（ ） 。A)1 B)2C)3D)4(19)假设以行优先顺序存储三维数组 R696，其中 元素 R000的地址为 2100，且每个元素占 4 个存储单元，则 存储地址为 2836 的元素是（ ） 。 A) R333B) R334C) R435 D) R434 (20)设有一个 10 阶的对称矩阵 A，采用压缩存储方式以 行序为主序存储，a00 为第一个元素，其存储地址为 0，每个元素 占有
5、 1 个存储地址空间，则 a45 的地址为（ ） 。A) 13B) 35C) 17D) 36(21)线性表采用链式存储时，节点的存储的地址（ ） 。 A) 必须是不连续的 B) 连续与否均可 C) 必须是连续的 D) 和头节点的存储地址相 连续 (22)用链表表示线性表的优点是（ ） 。 A) 便于随机存取 B) 花费的存储空间比顺序 表少 C) 数据元素的物理顺序与逻辑顺序相同 D) 便于插入与删除 (23)链表不具有的特点是（ ） 。 A) 插入、删除不需要移动元素 B) 可随机访问任一元素 C) 不必事先估计存储空间 D) 所需空间与线性长度 成正比 (24)在长度为 n 的顺序表中删除
6、第 i 个元素(1in) 时，元素移动的次数为( )。 A) n-i+1 B) i C) i+1 D) n-i (25)采用顺序搜索方法查找长度为 n 的顺序表示，搜索 成功的平均搜索长度为（ ） 。A) n B) n/2 C) (n-1)/2 D) (n+1)/2 (26)将长度为 n 的单链表链接在长度为 m 的单链表之后 的算法的时间复杂度为（ ） 。 A) O(1) B) O(n) C) O(m) D) O(m+n) (27)若不带头结点的单链表的头指针为 head，则该链表 为空的判定条件是( )。 A) head=NULL B) head-next=NULLC) head!=NUL
7、L D) head-next=head (28)某线性表中最常用的操作是在最后一个元素之后插 入一个元素和删除第一个元素，则采用（ ）存储方式最节省运 算时间。 A) 单链表 B) 仅有头指针的单循环链表 C) 双链表 D) 仅有尾指针的单循环链表 (29)若允许表达式内多种括号混合嵌套，则为检查表达 式中括号是否正确配对的算法，通常选用的辅助结构是（ ） 。A) 栈B) 线性表C) 队列D) 二 叉排序树 (30)顺序栈 S 中 top 为栈顶指针，指向栈顶元素所在的 位置，elem 为存放栈的数组，则元素 e 进栈操作的主要语句为（ ） 。A) s.elemtop=e； s.top=s.t
8、op+1；B) s.elemtop+1=e；s.top=s.top+1； C) s.top=s.top+1；s.elemtop+1=e；D) s.top=s.top+1；s.elemtop=e； (31)循环队列 sq 中，用数组 elem025存放数据 元素，sq.front 指示队头元素的前一个位置，sq.rear 指示队尾元 素的当前位置，设当前 sq.front 为 20，sq.rear 为 12，则当前队 列中的元素个数为（ ） 。A) 8 B) 16 C) 17 D) 18(32)链式栈与顺序栈相比，一个比较明显的优点是（ ） 。 A) 插入操作更加方便 B) 通常不会出现栈满的情
9、 况 C) 不会出现栈空的情况 D) 删除操作更加方便 (33)一个递归的定义可以用递归过程求解，也可以用非 递归过程求解，但单从运行时间来看，通常递归过程比非递归过程 （ ） 。 A) 较快 B) 较慢 C) 相同 D) 不定 (34)若已知一个栈的入栈序列是 1,2,3,4n，其输出 序列为 p1,p2,p3,pn，若 p1= =n,则 pi 为（ ） 。 A) i B) n= =i C) n-i+1 D) 不确定 (35)一个栈的入栈序列是 a,b,c,d,e，则栈的不可能的 输出序列是( ) 。 A) edcba B) decba C) dceab D) abcde (36)若进栈序列
10、为 1，2，3，4，5，6，且进栈和出栈可 以穿插进行，则不可能出现的出栈序列是( )。 A) 2，4，3，1，5，6 B) 3，2，4，1，6，5 C) 4，3，2，1，5，6 D) 2，3，5，1，6，4 (37)对于栈操作数据的原则是（ ） 。 A) 先进先出 B) 后进先出 C) 后进后出 D) 不分顺序 (38)栈和队列的共同点是（ ） 。 A) 都是先进先出 B) 都是先进后出 C) 只允许在端点处插入和删除元素 D) 没有共同点 (39)一个队列的入队序列是 1，2，3，4，则队列的输出 序列是（ ） 。 A) 4,3,2,1 B) 1,2,3,4 C)1,4,3,2 D) 3,
11、2,4,1 (40)设数组 datam作为循环队列 SQ 的存储空间， front 为队头指针，rear 为队尾指针，则执行出对操作后其头指针front 值为（ ） 。 A) front=front+1 B) front=(front+1)%(m-1) C) front=(front-1)%m D) front=(front+1)%m (41)引起循环队列队头位置发生变化的操作是( )。 A) 出队B) 入队 C) 取队头元素 D) 取 队尾元素(2)设以数组 Am存放循环队列的元素，其头尾指针分别为 front 和rear，则当前队列中的元素个数为（ ）。A）(rear-front+m)%m
12、 B）rear-front+1C）(front-rear+m)%m D）(rear-front)%m (42)二维数组 A1218采用列优先的存储方法，若每 个元素各占 3 个存储单元，且 A00地址为 150，则元素 A97的 地址为( )。 A) 429 B) 432 C) 435 D) 438 (43)设有一个 10 阶的对称矩阵 A1010，采用压缩方 式按行将矩阵中下三角部分的元素存入一维数组 B中，A00 存入 B0中，则 A85在 B中（ ）位置。 A) 32 B) 33 C) 41 D) 65 (44)若对 n 阶对称矩阵 A 以行序为主序方式将其下三角 形的元素(包括主对角线
13、上所有元素)依次存放于一维数组 B1.(n(n+1)/2中，则在 B 中确定 aij（i, ,G 的拓扑 序列是（ ） 。 A) V1,V3,V4,V6,V2,V5,V7 B) V1,V3,V2,V6,V4,V5,V7 C) V1,V3,V4,V5,V2,V6,V7 D) V1,V2,V5,V3,V4,V6,V7 (81)关键路径是事件结点网络中（ ） 。 A) 从源点到汇点的最长路径 B) 从源点到汇点的最短 路径 C) 最长回路 D) 最短回路 (82)有 n 个结点的有向完全图的弧数是（ ） 。A) n2B) 2nC) n(n-1)D) 2n(n+1)(83)设图的邻接链表如题 12 图所示，则该图的边的数 目是（ ） 。A) 4 B) 5 C) 10D) 20(84)在一个图中，所有顶点的度数之和等于图的边数的 （ ）倍。 A) 1/2 B) 1 C) 2 D) 4 (85)在一个有向图中，所有顶点的入度之和等于所有顶 点的出度之和的（ ）倍。83 题图A) 1/2 B) 1 C) 2 D) 4 (86)有 8 个结点的无向图最多有（ ）条边。 A) 14 B) 28 C) 56 D) 11
