《数据结构与算法课程设计试卷A卷+答案》由会员分享,可在线阅读,更多相关《数据结构与算法课程设计试卷A卷+答案(6页珍藏版)》请在金锄头文库上搜索。
1、 学年度第 学期期末考试数据结构与算法课程设计(A)卷专业班级 姓名 学号 一、 单选题(每题的备选答案中只有一个最佳答案,每题2分,共60分)1.在数据结构中,从逻辑上可以把数据结构分成( )。A、动态结构和静态结构 B、紧凑结构和非紧凑结构C、线性结构和非线性结构 D、内部结构和外部结构2.在数据结构中,从存储结构上可以将之分为( )。A、动态结构和静态结构 B、顺序存储和非顺序存储C、紧凑结构和非紧凑结构 D、线性结构和非线性结构3.某算法的时间复杂度是O(n2),表明该算法的( )。A、执行时间与n2成正比 B、问题规模是 n2C、执行时间等于n2 D、问题规模与n2成正比4.for(
2、i=1;i=n;i+)for(j=1;j=n;j+)x=x+1;在这程序段中,x=x+1;的语句频度为( )。A、0(2n) B、O(n) C、O(n2) D、O(log2n)5.以下数据结构中,( )是非线性数据结构。A、树 B、字符串 C、队 D、栈6.顺序存储,存储单元的地址( )。A、一定连续 B、一定不连续 C、不一定连续 D、部分连续,部分不连续7.下列广义表是线性表的是( )A、L(a,b,L) B、L(a,L)C、L(a,b,c) D、L(a,b,(a,b)8.二叉树中第6层上的结点个数最多为( )A、32 B、16 C、12 D、69.已知森林 F=T1,T2,T3,T4,T
3、5,各棵树 Ti(i=1,2,3,4,5)中所含结点的个数分别为 7,3,5,1,2,则与F对应的二叉树的右子树中的结点个数为( )A、2 B、3 C、8 D、1110.n 个顶点的强连通图至少有( )条边。A、n B、n1 C、n1 D、n(n1)11.设无向图的顶点个数为n,则该图最多有( )条边。A、n1 B、n(n1)/2 C、n(n1)/2 D、n212.若表 R 在排序前已按键值递增顺序排序,则( )方法的比较次数最少。A、直接插入排序 B、快速排序 C、归并排序 D、直接选择排序13.下列排序方法中最稳定的是( )A、冒泡排序 B、直接选择排序 C、希尔排序 D、快速排序14.采
4、用分块查找时,若线性表中共有 625 个元素,查找每个元素的概率相同,假设采用顺序查找来确定结点所在的块,则每块分为( )个结点最佳。A、9 B、25 C、6 D、62515.用线性探查法查找散列表,可能要探查多个散列地址。这些位置上的键值( )A、一定都不是同义词 B、一定都是同义词C、不一定是同义词 D、都相同16.下面不属于数据的存储结构的是( )A、散列存储 B、链式存储 C、索引存储 D、压缩存储17.下面对非空线性表的逻辑特征描述不正确的是( )A、只有一个元素没有直接前趋B、只有一个元素没有直接后继C、除开始和终端元素外,任何一个元素都有且仅有一个直接前趋和一个直接后继D、任何一
5、个元素都有可能有多个直接前趋和多个直接后继18.在头指针为 head 且表长于 1 的单循环链表中,指针 p 指向表中某个结点,若 pnextnexthead,则( )A、p 指向头结点 B、p 指向尾结点C. * p的直接后继是头结点 D. * p的直接后继是尾结点19.栈的特点是( )A、先进先出 B、后进后出 C.后进先出 D、随意进出20.最不适合用作链队的链表是( )A、只带队首指针的非循环双向链表 B、只带队首指针的循环双向链表C.只带队尾指针的循环双向链表 D、只带队尾指针的循环单向链表21.设数组 Am为循环队列 Q 的存储空间,front 为队头指针,rear 为队尾指针,采
6、用少用一个无紧空间的方法来解决队空和队满的判定问题,则判定 Q 为空队列的条件是( )A、(rearfron)m1 B、frontrearC.(rearfront)mm1 D.front(rear+1)m22.下列选择中,不属于线性结构的是( )A、线性表 B、双向链表 C、循环队列 D、二叉树23.某线性表 L 含有 n 个元素,采用单循环链表保持,仅有尾指针指向链表的终端结点。在最后一个结点之后插入一个结点及删除第一个结点的时间复杂度分别是( )A、O(1)和O(1) B、O(1)和O(n)C、O(n)和O(1) D、O(n)和O(n)24.下列应用中会用到栈的是( )A、计算后缀表达式的
7、值 B、图的广度优先遍历C、对数组进行希尔排序 D、对散列表进行查找25.设栈初始为空,入栈序列为1,2,3,4,5,下列选项中,不可能得到的出栈序列是( )A、1,2,3,4,5 B、3,1,4,2,5C、4,3,2,5,1 D、5,4,3,2,126.已知广义表LS(c,(d),(e,(f),(g,h),(m,n),head(LS)是( )A、c B、(c) C、(c,(d) D、(c,(d),(e,(f)27.设线性表采用顺序存储方式保存,每个元素占8个存储单元。第1个元素的存储地址为200,则第5个元素占用的最后一个存储单元的地址是( )A、239 B、240 C、247 D、2482
8、8.一棵完全二叉树 T 的全部 K 个叶子结点都在同一层中,每个分结点都有两个孩子结点。T 中包含的结点数是( )A、k B、2k1 C、k2 D、2k129.设字符集中有 n 个字符,对其进行哈夫曼编码,得到的哈夫曼树的结点总数是( )A、2n1 B、2n C、2n1 D、不确定30.设图 G 的邻接矩阵 A 如下所示。G 的各顶点的度依次是( )A=A、1,2,1,2 B、2,2,1,1 C、3,4,2,3 D、4,4,2,2二、 判断题(对的选“A”,错的选“B”,每题2分,共40分)31.数据的运算描述是定义在数据的逻辑结构上的。( )32.数据运算的实现是基于数据的逻辑结构的。( )
9、33.一个数据结构中,如果数据元素值发生改变,则它的逻辑结构也随之改变。( )34.非线性结构中,每个元素最多只有一个前趋元素。( )35.线性表中所有元素的数据类型必须相同。( )36.线性表中的结点按前趋、后继关系可以排成一个线性序列。( )37.线性表中每个元素都有一个前趋元素和一个后继元素。( )38.线性表的长度是线性表占用的存储空间的大小。( )39.线性表的逻辑顺序总与其物理顺序一致。( )40.线性表的顺序存储结构优于链式存储结构。( )41.顺序表具有随机存取特性,而链表不具有随机存取特性。( )42.栈的定义不涉及数据的逻辑结构。( )43.栈和队列都是线性表,只是在插入和
10、删除时受到了一些限制。( )44.栈和队列都是限制存取端的线性表。( )45.队列是一种对进队、出队操作的次序做了限制的线性表。( )46.队列是一种对进队、出队操作的次数做了限制的线性表。( )47.n个元素进队的顺序和出队的顺序总是一致的。( )48.n个元素通过一个队列,其出队序列是唯一的。( )49.串是由有限个字符构成的序列。( )50.串中每个元素只能是字母。( )A卷答案(标准答案及评分标准)三、 单选题(每题的备选答案中只有一个最佳答案,每题2分,共60分)123456789101112131415CBAAADAABC161718192021222324252627282930DDDABDABBAC三、判断题(对的选“A”,错的选“B”,每题2分,共40分)31323334353637383940ABABBBB41424344454647484950ABABAAB第 6 页 共 6 页